russell@unturf.com
db29a08762
B&W print-friendly diagrams + tinkerpop-0001 + wave-3 proof sections. Squash of 94 local commits onto remote master.
1.2 KiB
1.2 KiB
| id | repo | severity | status | created |
|---|---|---|---|---|
| linux-0001 | linux | MEDIUM | PATCHED | 2026-03-23 |
Defect
File: scripts/headerdep.pl:153
Pattern: grep {} @$top BFS cycle detection in header dependency checker
Complexity: O(V²)
Language: Perl
Description
The Linux kernel's headerdep.pl tool checks for cycles in header file include dependencies using BFS. At line 153, it tests whether a header is already in the current path using Perl's grep {} over an array reference @$top. This is a linear scan of all headers seen so far. Since the check is performed for every header encountered during BFS traversal, the total cost is O(V²) in the number of header files processed.
Fix
Replace: grep { $_ eq $header } @$top
With: exists $top_set{$header}
Data structure change: @$top: array → %top_set: hash (maintained in parallel)
Work required
- Patch in
defects/linux/patch/ - Unit test — asserts exact operation counts before/after (in
defects/linux/unit/) - Integration test (in
defects/linux/integration/) - Benchmark — before/after on V=100,200,400,800 (in
defects/linux/bench/) - White paper section