russell@unturf.com
998e2b7b0f
- Renamed linux-0001-audit-filter-inodes → linux-0002 (matches patch file reality) - Renamed linux-0002-dev-alloc-name → linux-0003 - Renamed linux-0003-neigh-parms → linux-0004 - Added linux-0001-headerdep-hash.md (scripts/headerdep.pl detect_cycles CWE-407) - Added linux-0005-component-find-quadratic.md (drivers/base/component.c) - Added linux-0006-btf-module-scan-hash.md (kernel/bpf/btf.c bpf_find_btf_id) - Added linux-0007-pktgen-thread-dev-xarray.md (net/core/pktgen.c) - Added linux-0008-taskstats-listener-hashset.md (kernel/taskstats.c)
85 lines
2.9 KiB
Markdown
85 lines
2.9 KiB
Markdown
# 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`
|