63 lines
2 KiB
Markdown
63 lines
2 KiB
Markdown
# UNDF: UNDF-2026-000000354
|
||
# binutils-0001 — ldlang.c unique_section_p O(S×U) linked-list scan
|
||
|
||
**Severity:** MEDIUM
|
||
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)
|
||
**File:** `ld/ldlang.c`
|
||
**Functions:** `unique_section_p` (line 389), `lang_add_unique` (line 10269)
|
||
**Repo:** https://sourceware.org/git/binutils-gdb.git
|
||
|
||
## Defect
|
||
|
||
`unique_section_list` is a singly-linked list. Two O(N) linear scans exist:
|
||
|
||
### 1. `unique_section_p` — O(U) per call, called O(S) times → O(S×U) total
|
||
|
||
```c
|
||
// ld/ldlang.c:402
|
||
for (unam = unique_section_list; unam; unam = unam->next)
|
||
if (name_match (unam->name, secnam) == 0)
|
||
return true;
|
||
```
|
||
|
||
Called from three section-placement paths during linking:
|
||
- `output_section_callback_sort` (line 776) — called per matching section
|
||
- `output_section_callback_nosort` (line 3002, 3024) — called per matching section
|
||
- orphan section placement (line 7784) — called per unplaced section
|
||
|
||
For a large binary with S=100K input sections and U=1K unique-section patterns (common in embedded/RTOS linker scripts with per-function sections), this is 100M `name_match` calls.
|
||
|
||
### 2. `lang_add_unique` — O(U) dedup scan on each insertion
|
||
|
||
```c
|
||
// ld/ldlang.c:10273
|
||
for (ent = unique_section_list; ent; ent = ent->next)
|
||
if (strcmp (ent->name, name) == 0)
|
||
return;
|
||
```
|
||
|
||
Called O(U) times during linker script parsing. Each call scans the entire existing list → O(U²) total for adding U entries.
|
||
|
||
## Fix
|
||
|
||
Replace `unique_section_list` linked list with a hash set.
|
||
|
||
```c
|
||
// Replace:
|
||
static struct unique_sections *unique_section_list;
|
||
|
||
// With:
|
||
static htab_t unique_section_htab; /* htab_t keyed on section name */
|
||
```
|
||
|
||
- `unique_section_p`: htab_find → O(1) average
|
||
- `lang_add_unique`: htab_find_slot → O(1) average
|
||
|
||
## Complexity
|
||
|
||
| Scenario | Before | After |
|
||
|----------|--------|-------|
|
||
| S=100K sections, U=1K unique patterns | O(100M) | O(100K) |
|
||
| U=100 unique entries, insert all | O(5K) dedup | O(100) |
|
||
|
||
**Speedup at S=10K, U=500:** ~500x op-count reduction for `unique_section_p`.
|