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