# UNDF: UNDF-2026-000000151
# linux-0008 — `taskstats`: O(|CPUs|×L) nested scan in `add_del_listener`

## Status
PATCHED

## Severity
MEDIUM (>10× speedup at |CPUs|=64, L=50 listeners)

## Location
`kernel/taskstats.c`, function `add_del_listener()` (REGISTER path, ~line 308)

## Description
`add_del_listener` handles the `TASKSTATS_CMD_ATTR_REGISTER_CPUMASK` genetlink command.
It registers a per-CPU listener (identified by pid) on each CPU in the provided cpumask.

The inner REGISTER path:
```c
for_each_cpu(cpu, mask) {                                    // O(|mask|) = O(C)
    ...
    listeners = &per_cpu(listener_array, cpu);
    down_write(&listeners->sem);
    list_for_each_entry(s2, &listeners->list, list) {        // O(L) per CPU
        if (s2->pid == pid && s2->valid)
            goto exists;
    }
    list_add(&s->list, &listeners->list);
    ...
}
```

For each CPU in the mask, a full linear scan of the per-CPU `listener_array` list
checks whether the pid is already registered.  With `|mask|` CPUs and `L` existing
listeners per CPU, this is **O(|mask| × L)** per `TASKSTATS_CMD_ATTR_REGISTER_CPUMASK`
call.

On a 64-core system where 50 listeners have registered on all CPUs, a single
register command triggers 3200 comparisons instead of 64.

## Complexity
- Slow: O(|CPUs| × L) per registration command
- Fast: O(|CPUs|) with O(1) hash table lookup per CPU
- At C=64, L=50: 3200 iterations → 64 with the fix

## Patch (conceptual — C)
Add a `DECLARE_HASHTABLE(pid_ht, 8)` inside `struct listener_array` (256 buckets,
keyed by `(unsigned long)pid`).  Add `struct hlist_node pid_hnode` to `struct listener`.

REGISTER path replaces `list_for_each_entry` scan with:
```c
hash_for_each_possible(listeners->pid_ht, s2, pid_hnode, (unsigned long)pid) {
    if (s2->pid == pid && s2->valid) goto exists;
}
list_add(&s->list, &listeners->list);
hash_add(listeners->pid_ht, &s->pid_hnode, (unsigned long)pid);
```

DEREGISTER path: adds `hash_del(&s->pid_hnode)` alongside `list_del()`.

Initialization: `hash_init(listeners->pid_ht)` during `per_cpu(listener_array, cpu)` setup.

## Patch file
See `linux-0008-taskstats-listener-hashset.patch`
