# UNDF: UNDF-2026-000000026
# ceph-0001 — `OSDMap::calc_pg_upmaps`: O(N×U) `std::find` on `underfull` vector inside OSD scan loop

## Status
PATCHED

## Severity
HIGH (>50× speedup at N=1000 OSDs, U=500 underfull)

## Location
`src/osd/OSDMap.cc`, function `OSDMap::calc_pg_upmaps()`, line 5981–5983:

```cpp
for (auto& [deviation, osd] : deviation_osd) {
    if (std::find(underfull.begin(), underfull.end(), osd) ==
                  underfull.end())
        break;
```

## Description
`calc_pg_upmaps()` is Ceph's cluster rebalancing algorithm. It runs up to
`max` iterations (default configurable, commonly 100) trying to add or remove
PG upmap entries to equalize OSD fill levels.

Inside the outer `while (max--)` loop, after failing to find improvements for
overfull OSDs, the code scans `deviation_osd` (a `multimap<float, int>` of
**all OSDs sorted by deviation**) looking for underfull OSDs to try
`try_drop_remap_underfull` on.

For each OSD in `deviation_osd` it calls:
```cpp
std::find(underfull.begin(), underfull.end(), osd)
```
`underfull` is a `vector<int>` populated by `fill_overfull_underfull()` with
all OSDs whose deviation is below `-max_deviation`. In a large cluster this
can be hundreds of entries.

The loop runs over **all OSDs** in `deviation_osd`, calling `std::find` on the
`underfull` vector each time:

```
Cost per while-iteration = O(N_osds × |underfull|)
Total cost = max_iters × O(N_osds × |underfull|)
```

In a 1000-OSD cluster with 500 underfull OSDs and max=100:
```
100 × 1000 × 500 = 50,000,000 linear comparisons
```

`underfull` is **read-only** in this loop — it is the ideal candidate for
conversion to `std::unordered_set<int>` for O(1) membership test.

The same defect appears in CrushWrapper's `try_remap_rule()` (called via
`try_pg_upmap`), where `std::find(orig.begin(), orig.end(), item)` is called
inside `for (auto item : underfull)`, making it doubly-nested O(U × |orig|).

## Patch

### OSDMap.cc — deviation_osd scan loop

```cpp
// Before the while(max--) loop, or after fill_overfull_underfull():
std::unordered_set<int> underfull_set(underfull.begin(), underfull.end());
std::unordered_set<int> more_underfull_set(more_underfull.begin(), more_underfull.end());

// In the scan loop (line 5981):
for (auto& [deviation, osd] : deviation_osd) {
-   if (std::find(underfull.begin(), underfull.end(), osd) ==
-                 underfull.end())
+   if (underfull_set.find(osd) == underfull_set.end())
        break;
    ...
}
```

Note: `underfull` is rebuilt each `while` iteration so the set must be rebuilt
after each `fill_overfull_underfull()` call. Alternatively, change
`fill_overfull_underfull()` to return an `unordered_set` directly.

### CrushWrapper.cc — try_remap_rule underfull inner loop

```cpp
// Before: for (auto item : underfull) { ... std::find(orig.begin(), orig.end(), item) ... }
// Build orig_set once before the underfull loop:
std::unordered_set<int> orig_set(orig.begin(), orig.end());

for (auto item : underfull) {
    ...
-   if (std::find(orig.begin(), orig.end(), item) != orig.end()) {
+   if (orig_set.count(item)) {
        continue;
    }
    ...
}
```

## Speedup estimate
| N OSDs | |underfull| | max_iters | Defective ops | Fixed ops  | Ratio |
|--------|------------|-----------|--------------|------------|-------|
| 100    | 50         | 100       | 500,000      | 10,000     | 50×   |
| 1,000  | 500        | 100       | 50,000,000   | 100,000    | 500×  |
| 5,000  | 2,500      | 100       | 1,250,000,000| 500,000    | 2500× |

## Patch file
See `ceph-0001-osdmap-underfull-set.patch`
