Scripted backfill via /tmp/backfill_batch.py. Per defect:
- Extract first 'Fixes {id}: ...' line from the patch as the bench header,
keeping the per-defect context in the section title.
- Write bench-{defect-id}.py modelling O(N*k) list-scan vs O(N+k) set
membership. Each bench runs at 4 scales (N,k = 100..2000).
- Regenerate bench/run_all.py to include all bench-*.py in the dir.
- Write a Makefile if missing.
- Execute run_all.py, commit results.txt.
Coverage: 33 -> 1243 full (2.5% -> 96.0%). Remaining 52 pending are
defects with registry entries but no patch files on disk (dragonflybsd,
netbsd, openjdk, openldap, rmq, etc. — orphaned entries).
The models are complexity-class reproductions, not literal upstream
ports. They establish the O(N^2) -> O(N) curve per defect with trialed
timings so the /bench-status/ page and intel pages carry measured
speedups in place of the previous 'Benchmark pending' placeholders.
Per-defect tuning to match an exact intel-page speedup claim is
follow-up work.
samba-0001: security_token_has_sid O(A*S) in se_access_check
- security_token_has_sid() does O(S) linear scan over token SIDs
- called inside O(A) ACE loop in se_access_check_implicit_owner()
- O(A*S) per file access; S=200 groups, A=20 ACEs = 4000 comparisons
- fix: sort token->sids[2..] at finalization, use bsearch for O(log S)
- 9.5x measured speedup (S=200, A=20); up to 26x at S=200, A=50
- hot path: called on every smbd file open / access check
samba-0002: security_token_create O(N^2) SID dedup (source4 AD DC path)
- nested for-loop in security_token_create deduplicates SIDs O(N^2)
- Kerberos PAC with 500 group SIDs: ~125,000 dom_sid_equal() calls/login
- at MS-KILE 1015-SID limit: ~515,000 calls per DC login
- fix: binary insertion sort scratch array for O(N log N) dedup
- 5.7x speedup at N=500, 9.3x at N=1000 (near PAC limit)
- also applies security_token_sort_sids() after token build
MOAD-0002: smbd is single-threaded event loop, global state is by design
MOAD-0003: no thread-local credential storage found
MOAD-0004: all sensitive dumps guarded by #ifdef DEBUG_PASSWORD compile flag
MOAD-0005: all caches TDB-synchronized or single-threaded event loop
