# 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

```c
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:

```c
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`