java-topology/docs/tickets/linux-0003-dev-alloc-name-nested-altname-scan.md

linux-0003: __dev_alloc_name — O(D×A) nested sscanf on every interface rename

File: net/core/dev.c Function: __dev_alloc_name() (line ~1358) Severity: MEDIUM — triggered on every ip link add, ip link set name, container veth creation CWE: CWE-407 (Inefficient Algorithmic Complexity)

Code

static int __dev_alloc_name(struct net *net, const char *name, char *res)
{
    /* ... */
    for_each_netdev(net, d) {                          // O(D) — all devices
        struct netdev_name_node *name_node;

        netdev_for_each_altname(d, name_node) {        // O(A) — alt names per device
            if (!sscanf(name_node->name, name, &i))   // string parse each time
                continue;
            if (i < 0 || i >= max_netdevices)
                continue;
            snprintf(buf, IFNAMSIZ, name, i);
            if (!strncmp(buf, name_node->name, IFNAMSIZ))
                __set_bit(i, inuse);
        }
        /* same sscanf/snprintf/strncmp on d->name */
    }
    i = find_first_zero_bit(inuse, max_netdevices);
    /* ... */
}

Complexity

Variable	Meaning
D	Number of net devices in the namespace
A	Number of alternative names per device

Total work per call: O(D × A × sscanf_cost).

sscanf with a format containing %d is not O(1); it involves format string parsing. Container-heavy hosts (Kubernetes nodes) routinely carry D=500+ veth/bridge/vlan devices, each with 1-3 alt names from ip link property add.

When Triggered

• ip link add vethN type veth in a pod namespace — creates two interfaces, both call dev_alloc_name() with format "veth%d".
• A node creating 100 pods triggers 200 calls; if D=400 devices already exist with A=2 alt names, each call walks 800 entries.
• Batch pod launches show O(D²) total work as D grows.

Root Cause

The bitmap approach is correct for the final find_first_zero_bit, but the bitmap is populated by rescanning all devices + alt names on every call. The primary device name already uses the hash (dev_name_hash), but alt names bypass the hash and fall into the linear netdev_for_each_altname walk.

Fix

Maintain a sorted or hash-keyed index of all allocated numeric suffixes per name prefix. On device/altname registration, insert the suffix into the prefix's free map; on deregistration, remove it. __dev_alloc_name then does one map lookup to find the first free slot in O(log D) or O(1) amortized.

Simpler interim fix: skip the netdev_for_each_altname inner loop when counting in-use slots for the primary name format, since alt names use different formats (verified by netdev_name_node_alt_create — alt names are explicit strings, not %d patterns). Add a guard:

netdev_for_each_altname(d, name_node) {
    /* Alt names created via 'ip link property add' are never %d patterns;
     * skip sscanf unless the alt name could plausibly match. */
    if (!memchr(name_node->name, '0' + (i % 10), IFNAMSIZ))
        continue;   /* fast reject — not numeric */
    /* ... existing sscanf logic ... */
}

Full fix: maintain per-prefix bitmaps in a global xarray keyed by name prefix hash.

Impact

• O(D×A) work per interface creation; D and A both grow with container density.
• On a Kubernetes node with 500 pods: ~1000 devices × 2 alt names = 2000 sscanf calls per new pod creation, versus O(1) with an index.
• Multiplied by pod churn rate (100/min), this is 200,000 sscanf calls/min.

Patch

See defects/linux/patch/linux-0003-dev-alloc-name-nested-altname.patch