russell@unturf.com
7491349edc
bullet3-0001: btGhostObject::addOverlappingObjectInternal O(N²) linear dedup per broadphase step — even carries "too slow" self-admission comment (HIGH) bullet3-0002: btSoftRigidCollisionAlgorithm::processCollision O(C×D) per frame on m_collisionDisabledObjects plain array (MEDIUM) allegro5: CLEAN (vector_contains only on non-hot setup paths) box2d: CLEAN (v3 rewrite uses b2HashSet throughout) dry: CLEAN (HashSet/HashMap on all hot dedup paths)
21 lines
2 KiB
Markdown
21 lines
2 KiB
Markdown
# CLEAN — Ceph Distributed Storage
|
||
Scanned 2026-03-29 for CWE-407 (algorithmic complexity: O(N²) linear membership tests, O(2^D) diamond recursion).
|
||
|
||
## Scope
|
||
- `src/crush/CrushWrapper.cc` — CRUSH placement algorithm
|
||
- `src/crush/mapper.c` — CRUSH mapper
|
||
- `src/osd/OSDMap.cc` — OSD map and PG upmap balancing
|
||
- `src/osd/PeeringState.cc` — PG peering and acting set selection
|
||
- `src/osd/PrimaryLogPG.cc` — primary log, snapshot clone operations
|
||
- `src/mon/OSDMonitor.cc` — monitor OSD management
|
||
|
||
## Findings
|
||
- **`CrushWrapper.cc` rebalancing** — `std::find` on `orig` (PG placement output vector, size = replication_factor, typically 3–8). Outer loop is over `underfull` OSD candidates. Inner find is O(replication_factor) = O(constant). Not scalable O(N²). CLEAN.
|
||
- **`OSDMap.cc` pg_upmap moved-count tracking** — `std::find` on `up2` (replication_factor entries). O(constant) inner. CLEAN.
|
||
- **`OSDMap.cc` underfull candidate scan** — `std::find` on `underfull` list; both loops are over OSD deviation_osd list × underfull list. In practice bounded by OSD count (~hundreds) × replication_factor. Not exponential. CLEAN.
|
||
- **`PeeringState.cc` acting set membership** — `std::find` on `acting` (replication_factor entries). O(constant). CLEAN.
|
||
- **`PrimaryLogPG.cc` snapshot clone list** — `std::find` on `snapset.clones`. In Ceph docs clones are bounded per object (default `rbd_max_snap_count` = 510, but typically far fewer). Snapshot clone lookup is called once per object read; not O(N²) across objects. CLEAN.
|
||
- **`OSDMonitor.cc` pg_upmap CLI** — `std::find` on user-supplied OSD lists for dedup; bounded by the CLI argument count. CLEAN.
|
||
- **CRUSH mapper (`mapper.c`)** — C code using integer arrays; collision avoidance uses modular arithmetic (straw2 algorithm), no linear membership scan. CLEAN.
|
||
|
||
**Result: No actionable CWE-407 defects. All inner `std::find` calls in Ceph operate on replication-factor-sized (O(1)) vectors or small user-supplied lists; scalable paths use hash maps and sorted data structures.**
|