russell@unturf.com
a7b08c7e05
solang-0001: add_external_functions emits_events Vec::contains O(F×E²) MEDIUM src/sema/external_functions.rs:93-103 — dedup accumulator Vec uses linear scan for each event per function; fix: IndexSet (already a dependency) for O(1) dedup tor/bitcoin/transmission/libtorrent/solc: CLEAN markers added after full scan Tor: nodes_have_common_family_id F=1-3 IDs, O(N×F²) ≈ O(9N), not scalable issue Bitcoin: TxGraph/sets throughout, no linear scan in hot paths Transmission: bitfields for piece tracking, sorted binary search for string table libtorrent: sorted vectors with lower_bound, DHT uses binary search on results solc: unordered_set/set throughout OverrideChecker, SMTEncoder, FunctionCallGraph
22 lines
1.4 KiB
Markdown
22 lines
1.4 KiB
Markdown
# CLEAN — libtorrent (C++ BitTorrent library)
|
|
Scanned 2026-03-29 for CWE-407 (algorithmic complexity / linear scan membership).
|
|
|
|
## Areas Checked
|
|
|
|
- `src/piece_picker.cpp` — piece selection: `have_peers` is `std::unordered_set` per
|
|
piece_pos (O(1) count/insert). `m_recent_extents` is a `std::vector` capped at 5
|
|
entries by design — the `contains()` scan is trivially O(1) in practice.
|
|
`m_pieces` sorted vector uses `lower_bound` for O(log N) insert.
|
|
- `src/kademlia/traversal_algorithm.cpp` — DHT Kademlia traversal: `m_results` is a
|
|
sorted vector; new entries use `std::lower_bound` for O(log N) insertion. Dedup
|
|
is by node-ID comparison on the sorted prefix, not a full linear scan.
|
|
- `src/kademlia/routing_table.cpp` — routing table bucket management: `find_if` over
|
|
per-bucket vectors (K=8 nodes per bucket by Kademlia protocol) — effectively O(1).
|
|
- `src/peer_list.cpp` — peer list: sorted multimap range lookups via
|
|
`find_if(range.first, range.second, ...)` — O(k) over equal-range, not full list.
|
|
- `src/peer_connection.cpp` — `m_accept_fast` / `m_allowed_fast` / `m_suggested_pieces`
|
|
scans: these lists are bounded by BitTorrent protocol constants
|
|
(Fast Extension caps at 10 pieces, Suggest Piece typically ≤10).
|
|
|
|
**Result: No actionable CWE-407 defects found. libtorrent uses sorted vectors with
|
|
binary search, unordered sets, and protocol-bounded lists throughout.**
|