java-topology/docs/tickets/linux-0001-headerdep-hash.md

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

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

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.

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