russell@unturf.com
998e2b7b0f
- Renamed linux-0001-audit-filter-inodes → linux-0002 (matches patch file reality) - Renamed linux-0002-dev-alloc-name → linux-0003 - Renamed linux-0003-neigh-parms → linux-0004 - Added linux-0001-headerdep-hash.md (scripts/headerdep.pl detect_cycles CWE-407) - Added linux-0005-component-find-quadratic.md (drivers/base/component.c) - Added linux-0006-btf-module-scan-hash.md (kernel/bpf/btf.c bpf_find_btf_id) - Added linux-0007-pktgen-thread-dev-xarray.md (net/core/pktgen.c) - Added linux-0008-taskstats-listener-hashset.md (kernel/taskstats.c)
105 lines
3.3 KiB
Markdown
105 lines
3.3 KiB
Markdown
# linux-0001: headerdep.pl detect_cycles — O(D×depth²) grep{} membership check
|
||
|
||
**File:** `scripts/headerdep.pl`
|
||
**Function:** `detect_cycles()`
|
||
**Severity:** MEDIUM — triggered by `make headerdep` on large kernel header trees
|
||
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
|
||
|
||
## Code
|
||
|
||
```perl
|
||
sub detect_cycles {
|
||
my @queue = map { [[0, $_]] } @_;
|
||
while(@queue) {
|
||
my $top = pop @queue;
|
||
my $name = $top->[-1]->[1];
|
||
|
||
for my $dep (@{$deps{$name}}) {
|
||
my $chain = [@$top, $dep];
|
||
|
||
# If the dep already exists in the chain, we have a cycle...
|
||
if(grep { $_->[1] eq $dep->[1] } @$top) { # O(depth) per check
|
||
print_cycle($chain);
|
||
next if $opt_all;
|
||
return;
|
||
}
|
||
|
||
push @queue, $chain;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
## Complexity
|
||
|
||
| Variable | Meaning |
|
||
|----------|---------|
|
||
| D | Number of header files scanned |
|
||
| depth | Maximum include chain depth in the current BFS path |
|
||
|
||
BFS expands every path from root headers. For each new node visited, `grep{}`
|
||
scans the entire `@$top` array (current path) to check if the candidate dependency
|
||
already appears. This is O(depth) per membership test. In the worst case every
|
||
path reaches maximum depth and BFS expands O(D) paths, giving O(D × depth²) total.
|
||
|
||
For a kernel tree with D=10,000 headers and maximum include depth=50, this is
|
||
25,000,000 string comparisons versus 500,000 with a hash.
|
||
|
||
## When Triggered
|
||
|
||
```bash
|
||
make headerdep # full kernel header dependency check
|
||
make headerdep HDRSRC=include/linux/ # subset scan
|
||
scripts/headerdep.pl --all # exhaustive cycle detection
|
||
```
|
||
|
||
Used during kernel development to find circular header dependencies. Slow on
|
||
large subsystem scans (e.g., full drivers/ or sound/ trees).
|
||
|
||
## Root Cause
|
||
|
||
`@$top` is a Perl array — membership test via `grep{}` is O(n). No secondary
|
||
set structure is maintained alongside the path array, so every cycle check
|
||
re-scans the entire current path.
|
||
|
||
## Fix
|
||
|
||
Carry a parallel Perl hash alongside each path. Keys are the header names already
|
||
in the path; existence check is `exists{}` — O(1) average. Both the path array
|
||
(for cycle printing) and the hash (for membership) are updated on each BFS expansion.
|
||
|
||
```perl
|
||
sub detect_cycles {
|
||
my @queue = map { [[[0, $_]], {$_ => 1}] } @_;
|
||
while(@queue) {
|
||
my ($top, $top_set) = @{pop @queue};
|
||
my $name = $top->[-1]->[1];
|
||
|
||
for my $dep (@{$deps{$name}}) {
|
||
my $chain = [@$top, $dep];
|
||
|
||
if(exists $top_set->{$dep->[1]}) { # O(1) — was O(depth)
|
||
print_cycle($chain);
|
||
next if $opt_all;
|
||
return;
|
||
}
|
||
|
||
push @queue, [$chain, {%$top_set, $dep->[1] => 1}];
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
The hash copy on each push (`{%$top_set, ...}`) costs O(depth) per expansion but
|
||
that was already the unavoidable cost of copying the path array. Net complexity:
|
||
O(D × depth) instead of O(D × depth²).
|
||
|
||
## Impact
|
||
|
||
- `make headerdep` takes measurably longer on large trees (drivers/, sound/, arch/).
|
||
- CI pipelines running headerdep checks block on O(D × depth²) string comparisons.
|
||
- At D=10000, depth=50: ~25M comparisons slow → ~500K fast — 50× improvement.
|
||
|
||
## Patch
|
||
|
||
See `defects/linux/patch/linux-0001-headerdep-hash.patch`
|