86 lines
3.1 KiB
Markdown
86 lines
3.1 KiB
Markdown
# UNDF: UNDF-2026-000000457
|
||
# make-0001: implicit.c pattern_search file->deps O(R×D×F) → O(R×D+F)
|
||
|
||
## Defect
|
||
|
||
- **File**: `src/implicit.c`
|
||
- **Function**: `pattern_search`
|
||
- **Lines**: ~796 (Savannah HEAD, 2025-03-27)
|
||
- **CWE**: 407 — Inefficient Algorithmic Complexity
|
||
- **Severity**: HIGH
|
||
|
||
## Pattern
|
||
|
||
```c
|
||
/* Outer: for (intermed_ok = 0; intermed_ok < 2; ++intermed_ok) */
|
||
/* Outer: for (ri = 0; ri < nrules; ri++) */
|
||
/* Middle: while(1) / for (d = dl; d != 0; d = d->next) */
|
||
|
||
if (df && df->is_target)
|
||
explicit = 1;
|
||
else
|
||
for (dp = file->deps; dp != 0; dp = dp->next) /* O(F) */
|
||
if (streq (d->name, dep_name (dp))) /* O(F) linear scan */
|
||
break;
|
||
```
|
||
|
||
## Complexity
|
||
|
||
- `R` = number of pattern rules (can be hundreds of built-in + user-defined rules)
|
||
- `D` = number of pattern prerequisites per rule (typically 1-5)
|
||
- `F` = number of explicit prerequisites of the current target file
|
||
|
||
For each target, `pattern_search` runs through R rules × D deps × F explicit deps.
|
||
The O(F) inner linear scan is performed for every `(rule, dep)` pair.
|
||
|
||
**Worst case**: target with F=100 deps and R=200 rules with D=5 deps each:
|
||
- Without fix: 200 × 5 × 100 = 100,000 string comparisons
|
||
- With fix: build hash set once from F deps (O(F)), then O(1) per lookup:
|
||
200 × 5 × 1 = 1,000 lookups + 100 hash inserts = ~1,100 ops
|
||
- **Speedup**: ~91× at F=100, scales as O(F)
|
||
|
||
## Root Cause
|
||
|
||
The function `pattern_search` is the hot path called for every target that
|
||
needs an implicit rule. In a project with many targets (e.g. a large
|
||
parallel make with hundreds of object files, each with many explicit
|
||
prerequisites), this inner loop fires F times per (rule, dep) combination.
|
||
|
||
`file->deps` is a linked list — no random access or hashing. The membership
|
||
test `streq(d->name, dep_name(dp))` scans the whole list every time.
|
||
|
||
## Fix
|
||
|
||
Build a `hash_set` (or a `struct hash_table` using GNU Make's `hashmap`
|
||
infrastructure) from `file->deps` **once** before the rule loop begins.
|
||
Replace the inner `for (dp = file->deps; ...)` linear scan with an O(1)
|
||
hash lookup.
|
||
|
||
```c
|
||
/* CWE-407 fix: build a set of explicit dep names once before the rule loop.
|
||
The inner for(dp = file->deps; ...) scan was O(F) per (rule, dep) pair,
|
||
giving O(R * D * F) total. A hash set gives O(R * D + F). */
|
||
struct hash_table *dep_name_set = make_file_dep_name_set (file);
|
||
|
||
/* ... inside the rule/dep loops ... */
|
||
|
||
if (df && df->is_target)
|
||
explicit = 1;
|
||
else
|
||
dp = dep_name_set_contains (dep_name_set, d->name) ? (struct dep *)1 : 0;
|
||
```
|
||
|
||
GNU Make already uses `struct hash_table` (see `hash.h`) for file name
|
||
lookup (`hash_find_item`). The same infrastructure applies here.
|
||
|
||
## Evidence
|
||
|
||
Confirmed present in:
|
||
- `src/implicit.c` in GNU Make mirror (mirror/make on GitHub, ~2024)
|
||
- `src/implicit.c` in GNU Make Savannah HEAD (`cgit/make.git`, 2025-03-27)
|
||
|
||
Lines 796-797 (Savannah):
|
||
```c
|
||
for (dp = file->deps; dp != 0; dp = dp->next)
|
||
if (streq (d->name, dep_name (dp)))
|
||
```
|