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

## Finding

Three O(T²) defects in RocksDB's point lock manager across the lock, unlock, and cleanup hot paths. All three defects are in `lock/point/point_lock_manager.cc` — the shared-lock transaction tracking path exercised by every transactional RocksDB write. Patched. Patches ready for upstream review.

## The Defects

**rocksdb-001 (PATCHED — HIGH):** `lock/point/point_lock_manager.cc:791`

```cpp
// LockInfo.txn_ids is autovector<TransactionID>
// Inside shared lock acquisition — called per transaction per write:
auto it = std::find(lock_info.txn_ids.begin(), lock_info.txn_ids.end(), txn_id);
```

`std::find` on `autovector<TransactionID>` performs an O(T) scan for each transaction acquiring a shared lock. With T concurrent transactions sharing the same key, acquiring each lock costs O(T) scans, producing **O(T²) total** across all lock acquisitions for that key.

**rocksdb-001 (PATCHED — HIGH):** `lock/point/point_lock_manager.cc:1513`

```cpp
// Unlock path — same autovector, same linear scan:
auto it = std::find(lock_info.txn_ids.begin(), lock_info.txn_ids.end(), txn_id);
```

Same root cause on the unlock path. Every unlock of a shared key pays O(T) to locate the transaction ID in the shared holder list.

**rocksdb-001 (PATCHED — HIGH):** `lock/point/point_lock_manager.cc:1706`

```cpp
// Cleanup / expiry path — same autovector scan:
auto it = std::find(lock_info.txn_ids.begin(), lock_info.txn_ids.end(), txn_id);
```

Same pattern in the lock cleanup path invoked on transaction abort or expiry. All three sites share the same `LockInfo.txn_ids autovector` and the same O(T) scan pattern.

## Complexity Proof

Let:
- T = number of concurrent transactions holding a shared lock on the same key

For T transactions on a hot shared key (e.g., a frequently-read row in optimistic concurrency):
- Each lock acquisition scans up to T existing holders: O(T) per acquisition
- Across T acquisitions: O(T²) total scan cost
- Same on unlock and cleanup: three separate O(T²) exposure sites
- Fixed (`unordered_set<TransactionID>`): O(1) per lookup, O(T) total across all T operations

At T=100 concurrent readers on a shared key: defective=10,000 comparisons per path, fixed=100. **100× per path; all three paths fire per transaction lifecycle.**

`autovector` is a RocksDB-internal vector optimized for small sizes with inline storage — it has no O(1) membership test. Under shared-lock churn (many readers, hot keys) the linear scan dominates.

## Impact

Every RocksDB deployment using transactions with shared locks (`GetForUpdate` with shared=true, optimistic transactions with read-your-writes) hits all three paths. MyRocks (MySQL on RocksDB), MongoRocks, and any application using the TransactionDB API is affected. Workloads with hot shared rows — counters, frequently-read metadata keys, join keys in OLTP — maximize T and hit the O(T²) worst case. The lock, unlock, and cleanup paths all fire per transaction, so the overhead compounds across the full transaction lifecycle.

## The Fix

**rocksdb-001 (all three sites):** Replace `autovector<TransactionID>` in `LockInfo.txn_ids` with `std::unordered_set<TransactionID>` (or maintain a parallel set for O(1) membership while keeping the vector for ordered iteration if needed):

```cpp
// Before — lock path (same pattern at lines 791, 1513, 1706)
auto it = std::find(lock_info.txn_ids.begin(), lock_info.txn_ids.end(), txn_id);
if (it == lock_info.txn_ids.end()) { ... }

// After
// CWE-407 fix: unordered_set for O(1) transaction ID membership instead of O(T) autovector scan.
if (lock_info.txn_id_set.count(txn_id) == 0) { ... }
lock_info.txn_id_set.insert(txn_id);
```

`TransactionID` is `uint64_t` — standard hash support, no additional specialization required. The fix applies identically to all three sites.

## Patch

Fix available: `defects/rocksdb/patch/rocksdb-001-point-lock-hashset.patch`

Three-location change in `lock/point/point_lock_manager.cc` plus `LockInfo` struct update. No behavioral change — set membership semantics match the existing duplicate-check use case exactly.

## What We Ask

1. Confirm receipt and assign a GitHub issue or security advisory reference.
2. Validate the patch against the transaction lock manager test suite.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the RocksDB 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*
