Repository navigation
Description
Summary
Since #394, a recursive scan's parent found after the budget stopped admission calls stopAdmitting again. stopAdmitting rebuilds its lookup tables with a pass over the whole wordlist on every call, so each late parent costs O(wordlist) on the dispatcher goroutine.
Where
internal/scan/dispatcher.go:467-475(expand,case d.capped)internal/scan/dispatcher.go:324-340(countUnbuiltbuildslabels/indexover all entries)internal/scan/dispatcher.go:366-381(countUnbuiltRepeatsbuildsprefixes/walkover all entries)
Details
countUnbuilt (single-label entries with any exact -exclude pattern) and countUnbuiltRepeats (multi-label entries, no exclusions) each start with for i, entry := range d.cfg.Entries { … } to build tables that depend only on Entries, multi and the scope. They never depend on the frontier, so the result is the same on every call. Before #394 they ran once. Now they run once per parent found after the cap.
Impact
BenchmarkCapRecursiveDotted, which is one such pass over 100k entries, measures 2.7 ms/op. That is roughly 30-80 ms per late parent at 1-3M entries. When the budget hits, the jobs channel can hold about 40 jobs per worker (handoffPerWorker x maxChunk). At -t 1000 that is about 40k jobs in flight, which at a 0.5% find rate gives about 200 late parents: several seconds of serial dispatcher CPU. The unbuffered enqueue blocks every worker that found a name in the meantime. This matters most for -max-duration, which is meant to stop on time. Recursive scans with -ct/-sources (multi-label names) or with -exclude take this path.
The multi-label-with-exclusions branch, which still builds every remaining candidate, is tracked in #365.
Suggested fix
Compute the frontier-independent tables once per dispatcher, lazily on the first stopAdmitting, and keep them on the struct: the walk index list for countUnbuiltRepeats and the labels/index maps for countUnbuilt. A late parent then costs O(len(walk)) or O(patterns under the parent).
Acceptance criteria
- A benchmark: 1M entries plus one dotted entry, capped at
MaxQueries: 1, then 200expandcalls. Its time per call is independent of the wordlist size. - The Capped recursive scan counts excluded children of late parents as skipped #393/Count a capped expand's children as stopAdmitting counts its remainder #394 counting tests still pass
Getting started
- Relevant files:
internal/scan/dispatcher.go,internal/scan/dispatcher_test.go(BenchmarkCapRecursiveDotted) - How to run tests:
go test ./internal/scan/ -run Capped -bench Cap - Related: Smaller performance costs: cap walk, wordlist copies, serial AXFR, -dL, MCP queue #365, Capped recursive scan counts excluded children of late parents as skipped #393, Count a capped expand's children as stopAdmitting counts its remainder #394
Filed by repo-audit/full-audit at dd5b156. Severity: medium. Effort: S. audit-key: performance|internal/scan/dispatcher.go|expand
Activity