# Ceph — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

One O(P×U) defect in Ceph's CRUSH map upmap rebalancing. The defect is in `src/osd/OSDMap.cc` — the `calc_pg_upmaps()` function that decides which OSDs are underfull during PG remapping. Patched. Patch ready for upstream review. **Measured ratio: 125×.**

## The Defect

**ceph-0001 (PATCHED — HIGH):** `src/osd/OSDMap.cc`

```cpp
// calc_pg_upmaps() — called during OSD rebalance, once per PG per rebalance pass:
// underfull is std::vector<int> of underfull OSD IDs
// Inside per-PG remapping loop:
auto it = std::find(underfull.begin(), underfull.end(), osd_id);
if (it != underfull.end()) { ... }
```

`std::find` performs an O(U) linear scan over the underfull OSD vector for each of the P PGs being remapped. For P PGs and U underfull OSDs: **O(P × U) per rebalance pass**. Fixed: `unordered_set<int>` for underfull OSD membership. **Measured ratio: 125×.**

## Complexity Proof

Let:
- P = number of placement groups being evaluated for remapping (can be millions in large clusters)
- U = number of underfull OSDs at the current rebalance step (proportional to cluster imbalance)

`calc_pg_upmaps()` iterates all P PGs. For each PG, it evaluates candidate OSDs against the underfull set. Each membership check uses `std::find` on the U-length underfull vector:
- Cost: P × U comparisons
- Fixed (`unordered_set<int>`): P × O(1) = O(P) lookups

At P=65,536 PGs, U=128 underfull OSDs: defective=8,388,608 comparisons, fixed=65,536. **125× measured ratio.**

In production Ceph clusters, P ranges from tens of thousands to millions. U is bounded by the number of OSDs (hundreds to thousands) but is nonzero whenever the cluster is imbalanced — which is the exact state when `calc_pg_upmaps()` is most heavily invoked (OSD failure, OSD add/remove, weight change). The quadratic interaction between P and U means that larger clusters doing more work pay proportionally more overhead per rebalance cycle.

## Impact

Every Ceph cluster using `pg_upmap` rebalancing — which is the recommended approach for balanced PG distribution in Ceph Nautilus and later — invokes this path on every OSD map change event (OSD down, OSD in/out, weight adjustment, CRUSH map change). Production clusters with thousands of PGs and dozens of underfull OSDs during recovery hit the 125× overhead on every rebalance computation. Rebalancing is a continuous background process in active clusters; this overhead directly extends rebalance convergence time and increases OSD map computation latency during recovery events.

## The Fix

**ceph-0001:** Build an `unordered_set<int>` from the `underfull` vector before the per-PG loop:

```cpp
// Before — O(P×U): std::find on vector inside per-PG loop
auto it = std::find(underfull.begin(), underfull.end(), osd_id);
if (it != underfull.end()) { remapping_candidate = true; }

// After — O(P): unordered_set built once, O(1) lookups inside loop
// CWE-407 fix: unordered_set for O(1) underfull membership instead of O(U) std::find.
std::unordered_set<int> underfull_set(underfull.begin(), underfull.end());
// ... then inside the per-PG loop:
if (underfull_set.count(osd_id)) { remapping_candidate = true; }
```

The set is constructed once before the P-iteration loop. `int` (OSD ID) has standard hash support. The underfull set is stable across the inner loop — it only changes between rebalance passes, not within one.

## Patch

Fix available: `defects/ceph/patch/ceph-0001-calc-pg-upmaps-hashset.patch`

Single-location change in `src/osd/OSDMap.cc`. No behavioral change — `unordered_set::count()` exactly replaces the `std::find` membership test.

## What We Ask

1. Confirm receipt and assign a Tracker reference (tracker.ceph.com).
2. Validate the patch against the OSDMap upmap rebalancing tests.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Ceph team in the public disclosure. Preferred acknowledgment format welcome.

Contact: security@undefect.com. This brief is confidential until coordinated disclosure.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
