# UNDF: UNDF-2026-000000400
# foundationdb-0001 — canLaunchSrc: std::count nested inside O(S×R) double loop

**Project:** FoundationDB
**File:** `fdbserver/datadistributor/DDRelocationQueue.actor.cpp`
**Function:** `canLaunchSrc`
**Severity:** MEDIUM
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Defect

`canLaunchSrc` checks whether a data relocation can be launched without overloading
source servers. The outer loop iterates over `relocation.src` (team size, S = 3–5
storage servers). The inner loop iterates over `cancellableRelocations` (the queue of
in-flight cancellable moves, R entries). Inside the inner loop, `std::count` performs
an O(S') linear scan of each cancellable relocation's `src` vector (also of size ~S'):

```cpp
for (int i = 0; i < relocation.src.size(); i++) {          // O(S)
    auto busyCopy = busymap[relocation.src[i]];
    for (int j = 0; j < cancellableRelocations.size(); j++) {  // O(R)
        auto& servers = cancellableRelocations[j].src;
        if (std::count(servers.begin(), servers.end(), relocation.src[i]))  // O(S')
            busyCopy.removeWork(...);
    }
    ...
}
```

Total: **O(S × R × S')** where R grows with the number of concurrent relocations.
In a large cluster undergoing rebalancing, R can reach hundreds or thousands,
making this O(n²) in the relocation queue depth.

## Fix

Pre-build an `unordered_set<UID>` for each cancellable relocation's `src` servers
before the outer loop (or use a flat `unordered_map<UID, work_to_cancel>` indexed
by server). The inner loop then becomes an O(1) map lookup.

```cpp
// Build per-server cancellable work map once
std::unordered_map<UID, std::vector<int>> cancellable_by_server;
for (int j = 0; j < cancellableRelocations.size(); j++) {
    for (const auto& uid : cancellableRelocations[j].src) {
        cancellable_by_server[uid].push_back(j);
    }
}

for (int i = 0; i < relocation.src.size(); i++) {
    auto busyCopy = busymap[relocation.src[i]];
    // O(1) map lookup instead of O(R * S') double scan
    auto it = cancellable_by_server.find(relocation.src[i]);
    if (it != cancellable_by_server.end()) {
        for (int j : it->second) {
            busyCopy.removeWork(cancellableRelocations[j].priority,
                                cancellableRelocations[j].workFactor);
        }
    }
    ...
}
```

Complexity: **O(S + R×S' + S)** = **O(R×S')** build + **O(S)** lookup, dominated by
the one-time build. This removes the multiplicative factor between S and the inner
O(R×S') scan.

## Impact

During cluster rebalancing or after storage server failures, `canLaunchSrc` is called
for every candidate relocation in the queue (line 1090, inside a hot loop). As the
queue grows, each call degrades from O(R) to O(S×R×S') causing compounding slowdown
in data distribution scheduling decisions.

## Location

```
fdbserver/datadistributor/DDRelocationQueue.actor.cpp
  canLaunchSrc()     lines 436–477
  call site          line 1090
```