java-topology/docs/tickets/linux-0006-btf-module-scan-hash.md

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

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.

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