russell@unturf.com 998e2b7b0f linux: fix ticket doc numbering; add missing docs for 0001/0005/0006/0007/0008

- 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)

2026-04-04 11:41:36 -04:00

2.9 KiB

Raw Permalink Blame History

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

/* __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.

/* 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

2.9 KiB Raw Permalink Blame History Unescape Escape