# linux-0007: __pktgen_NN_threads / pktgen_change_name — O(T×D) nested list scan

**File:** `net/core/pktgen.c`
**Functions:** `__pktgen_NN_threads()`, `pktgen_change_name()`
**Severity:** MEDIUM — 20× measured speedup at T=10, D=100
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Code

```c
/* __pktgen_NN_threads — O(T×D) per device lookup */
list_for_each_entry(t, &pn->pktgen_threads, th_list) {   // O(T)
    pkt_dev = pktgen_find_dev(t, ifname, exact);          // O(D/T) per thread
    if (pkt_dev) { ... break; }
}

/* pktgen_change_name — O(T×D) per interface rename */
list_for_each_entry(t, &pn->pktgen_threads, th_list) {        // O(T)
    if_lock(t);
    list_for_each_entry(pkt_dev, &t->if_list, list) {          // O(D/T)
        if (pkt_dev->odev != dev) continue;
        proc_remove(pkt_dev->entry);
        pkt_dev->entry = proc_create_data(dev->name, ...);
        break;
    }
    if_unlock(t);
}
```

## Complexity

| Variable | Meaning |
|----------|---------|
| T | Number of pktgen threads (one per CPU by default) |
| D | Total pktgen devices across all threads |

`pktgen_net.pktgen_threads` is a linked list of `pktgen_thread` objects.
Each thread has an `if_list` of `pktgen_dev` objects.  Every device lookup or
rename notification walks T × (D/T) = D entries total.

At T=10 threads, D=1000 devices across all threads: each lookup walks ~100
devices per thread × 10 threads = 1000 comparisons on average.

**Measured ratio: 20×** at T=10, D=100 (1000 total lookups benchmarked).

## When Triggered

- `__pktgen_NN_threads`: every proc read/write to `/proc/net/pktgen/pgctrlN`,
  every `pktgen_add_device`, `pktgen_remove_device`.
- `pktgen_change_name`: every `NETDEV_CHANGENAME` notifier event — any
  `ip link set name` call triggers this for all pktgen nets.

## Fix

Add two `DECLARE_HASHTABLE` structures to `struct pktgen_net`:
- `dev_ht` keyed by `(unsigned long)net_device*` — for `pktgen_change_name`
- `name_ht` keyed by `jhash(odevname)` — for `__pktgen_NN_threads`

Each `pktgen_dev` gains `struct hlist_node dev_hnode` and `struct hlist_node name_hnode`.

```c
/* pktgen_change_name — O(1) */
hash_for_each_possible(pn->dev_ht, pkt_dev, dev_hnode, (unsigned long)dev >> 3) {
    if (pkt_dev->odev == dev) { /* found */ break; }
}

/* __pktgen_NN_threads — O(1) */
u32 key = jhash(ifname, strlen(ifname), 0);
hash_for_each_possible(pn->name_ht, pkt_dev, name_hnode, key) {
    if (strcmp(pkt_dev->odevname, ifname) == 0) { /* found */ break; }
}
```

Insert into both tables on `pktgen_add_dev()`; remove from both on `pktgen_remove_dev()`.

## Impact

- Network performance testing environments with many pktgen devices.
- Each device rename (`ip link set name`) triggers `pktgen_change_name` across
  all pktgen threads and devices.
- At T=8, D=1000: 1000 comparisons per rename → 1 hash probe.

## Patch

See `defects/linux/patch/linux-0007-pktgen-thread-dev-xarray.patch`