# UNDF: (pending)
# ceph-0002: `BlueStore::_do_remove` — O(E×U) `std::find` over `unshared_blobs` vector

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | ceph-0002 |
| Severity | MEDIUM |
| Ecosystem | Ceph |
| File | `src/os/bluestore/BlueStore.cc` |
| Lines | 18099–18115 (function `BlueStore::_do_remove`) |
| Complexity | O(E×U) where E = extents per object, U = unshared blobs |
| Hot path | Object deletion — every `rados rm`, RGW object delete, CephFS unlink |

## Defect

In `BlueStore::_do_remove()`, after computing which shared blobs can be
"unshared" (because the object being deleted was the last reference), the code
iterates the object's full extent map and for each extent calls `std::find`
over the `unshared_blobs` vector to check membership:

```cpp
vector<SharedBlob*> unshared_blobs;
unshared_blobs.reserve(maybe_unshared_blobs.size());
for (auto& p : expect) {
    if (p.first->persistent->ref_map == p.second) {
        SharedBlob *sb = p.first;
        unshared_blobs.push_back(sb);           // U entries
        ...
    }
}

if (unshared_blobs.empty()) {
    return 0;
}

// Scan every extent in the object to clear just-unshared blobs
for (auto& e : h->extent_map.extent_map) {          // O(E) loop
    const bluestore_blob_t& b = e.blob->get_blob();
    SharedBlob *sb = e.blob->get_shared_blob().get();
    if (b.is_shared() &&
        std::find(unshared_blobs.begin(), unshared_blobs.end(),  // O(U) scan
                  sb) != unshared_blobs.end()) {
        bluestore_blob_t& blob = e.blob->dirty_blob();
        blob.clear_flag(bluestore_blob_t::FLAG_SHARED);
        ...
    }
}
```

`unshared_blobs` is a `vector<SharedBlob*>` and membership is tested with
`std::find` — O(U) per extent.  Total cost: **O(E × U)**.

**Typical sizes:**
- A 1 GiB RGW object with 4 KiB blocks: E ≈ 262,144 extents
- A highly-shared object with many clones: U can reach tens of thousands
- Product: billions of pointer comparisons per delete

Even for moderate objects (E=10,000, U=100): 1,000,000 comparisons that
could be 100 with a hash set.

## Fix

Replace `vector<SharedBlob*> unshared_blobs` with
`unordered_set<SharedBlob*> unshared_set` for O(1) lookup:

```cpp
// CWE-407 fix: use an unordered_set for O(1) membership test
std::unordered_set<SharedBlob*> unshared_set;
unshared_set.reserve(maybe_unshared_blobs.size());

for (auto& p : expect) {
    dout(20) << " ? " << *p.first << " vs " << p.second << dendl;
    if (p.first->persistent->ref_map == p.second) {
        SharedBlob *sb = p.first;
        dout(20) << __func__ << "  unsharing " << *sb << dendl;
        unshared_set.insert(sb);
        txc->unshare_blob(sb);
        uint64_t sbid = c->make_blob_unshared(sb);
        string key;
        get_shared_blob_key(sbid, &key);
        txc->t->rmkey(PREFIX_SHARED_BLOB, key);
    }
}

if (unshared_set.empty()) {
    return 0;
}

// And now a run through .head extents to clear up freshly unshared blobs.
for (auto& e : h->extent_map.extent_map) {
    const bluestore_blob_t& b = e.blob->get_blob();
    SharedBlob *sb = e.blob->get_shared_blob().get();
    if (b.is_shared() &&
        unshared_set.count(sb)) {                            // O(1) lookup
        dout(20) << __func__ << "  unsharing " << e << dendl;
        bluestore_blob_t& blob = e.blob->dirty_blob();
        blob.clear_flag(bluestore_blob_t::FLAG_SHARED);
        e.blob->get_dirty_shared_blob() = nullptr;
        h->extent_map.dirty_range(e.logical_offset, e.length);
    }
}
txc->write_onode(h);

return 0;
```

Required include: `#include <unordered_set>` (already available via `#include "include/ceph_hash.h"` or add directly).

## Speedup

| Extents (E) | Unshared (U) | Before | After | Ratio |
|-------------|-------------|--------|-------|-------|
| 1,000 | 10 | 10,000 | 1,000 | 10× |
| 10,000 | 100 | 1,000,000 | 10,000 | 100× |
| 262,144 | 1,000 | 262,144,000 | 262,144 | 1,000× |

At E=262,144 (1 GiB object, 4 KiB blocks) and U=1,000 shared blobs the
speedup is ~1,000× — the delete operation goes from O(billions of pointer
comparisons) to O(262,144 hash lookups).

## Notes

The `maybe_unshared_blobs` source set at line 18010 is already a
`set<SharedBlob*>` (ordered), so it inherently avoids duplicates.  The
subsequent `unshared_blobs` vector was needlessly downgraded to linear-scan
membership.  Converting to `unordered_set` restores O(1) lookup without any
correctness risk — `SharedBlob*` pointer equality is the intended comparison.
