# 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`