# linux-0006: bpf_find_btf_id — O(F×M) idr_for_each_entry scan per BPF map create

**File:** `kernel/bpf/btf.c`
**Function:** `bpf_find_btf_id()`
**Severity:** HIGH — triggered on every BPF map creation involving kptr fields
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Code

```c
s32 bpf_find_btf_id(const char *name, u32 kind, struct btf **btf_p)
{
    /* ... check vmlinux BTF first (fast) ... */

    /* If name is not found in vmlinux's BTF then search in module's BTFs */
    spin_lock_bh(&btf_idr_lock);
    idr_for_each_entry(&btf_idr, btf, id) {    // O(M) — all loaded modules
        /* ... btf_find_by_name_kind(btf, name, kind) ... */
    }
    spin_unlock_bh(&btf_idr_lock);
}
```

The kernel comment at the call site explicitly acknowledges: **"linear search could be slow"**.

Every kptr field in a BPF map struct requires one call to `bpf_find_btf_id()`.
A struct with F kptr fields costs O(F × M) idr iterations per `BPF_MAP_CREATE` syscall.

## Complexity

| Variable | Meaning |
|----------|---------|
| F | Number of kptr fields in the BPF map value type |
| M | Number of kernel modules loaded with BTF |

On a production Kubernetes node running eBPF observability tools:
- M=200 modules loaded (driver modules, filesystem modules, network modules)
- F=10 kptr fields per BPF map type
- Every `BPF_MAP_CREATE`: 200 × 10 = **2,000 idr iterations**

eBPF programs compiled with complex struct types (e.g., Cilium's connection
tracking maps) issue multiple `BPF_MAP_CREATE` calls during program load.

## When Triggered

- `BPF_MAP_CREATE` with a value type containing kptr fields (BPF_TYPE_KPTR,
  BPF_TYPE_KPTR_REF): one `bpf_find_btf_id()` call per field.
- `bpftool map create`, Cilium agent startup, BCC tools with kptr maps.
- Kernel module load/unload (btf_idr changes) does NOT invalidate the slow path —
  it just makes future misses equally slow.

## Root Cause

`btf_idr` is an IDR (integer to pointer map) optimised for sequential integer
allocation, not name-based lookup.  `idr_for_each_entry()` visits every BTF
object in registration order.  There is no secondary name index.

The vmlinux BTF check (done first) is efficient — it calls `btf_find_by_name_kind`
directly on the vmlinux BTF object.  Only the module BTF path is slow.

## Fix

Add a secondary `DECLARE_HASHTABLE(btf_name_ht, 10)` (1024 buckets) in btf.c.
Cache entries store: `name_hash ^ kind`, `btf_id`, `btf *`, and a name copy.

`bpf_find_btf_id()` checks the cache before the idr walk.  On miss, the idr walk
runs as before, then the result is inserted into the cache.  On module unload,
`btf_free_id()` evicts the corresponding cache entry.

```c
/* Fast path — O(1) on cache hit */
u32 key = btf_name_hash(name, kind);
hash_for_each_possible(btf_name_ht, ce, node, key) {
    if (ce->key == key && ce->kind == kind &&
        strncmp(ce->name, name, sizeof(ce->name)) == 0) {
        *btf_p = ce->btf;
        btf_get(*btf_p);
        return ce->btf_id;   /* no re-scan */
    }
}
/* Slow fallback — O(M) idr walk on cache miss */
idr_for_each_entry(&btf_idr, btf, id) { ... }
/* Populate cache on positive hit */
```

## Impact

- Each `BPF_MAP_CREATE` with kptr fields pays O(F × M) in the uncached case.
- Cilium on a loaded node: F=8 fields × M=200 modules = 1600 idr iterations
  per map create, versus 8 hash probes on warm cache.
- eBPF program hot-reload (common in CI/CD pipelines): O(F × M) per reload event.

## Patch

See `defects/linux/patch/linux-0006-btf-module-scan-hash.patch`