java-topology/docs/tickets/dendrite-0002-backfill-bwextrems-double-loop.md

dendrite-0002: CWE-407 in dendrite — backfill ServersAtEvent bwExtrems nested loop

Severity: MEDIUM File: roomserver/internal/perform/perform_backfill.go:438 Pattern:

successor := ""
FindSuccessor:
for sucID, prevEventIDs := range b.bwExtrems {   // O(E) backward extremities
    for _, pe := range prevEventIDs {              // O(P) prev events per extremity
        if pe == eventID {                         // O(1) string comparison
            successor = sucID
            break FindSuccessor
        }
    }
}

Complexity: O(E × P) — scans all backward extremities × all prev event IDs to find a successor Fix: Pre-build a reverse map prevToSuccessor map[string]string when bwExtrems is populated, then successor = prevToSuccessor[eventID] Speedup: 100–1000× for rooms with large backward extremity sets (E=100 extremities, P=10 prev events each) Hot path: ServersAtEvent() — called for every backfill request, which occurs frequently during federation room catch-up