When a BPF Map Freezes a CPU

The trouble began with a soft lockup warning in production—a single line that pointed at the BPF LPM trie, one of the kernel's most relied-upon data structures. At Cloudflare, BPF trie maps (BPF_MAP_TYPE_LPM_TRIE) sit at the heart of packet routing and access control logic, including Magic Firewall rule evaluation. When those maps hold millions of entries, the current kernel implementation starts to show severe cracks: lookups can take hundreds of milliseconds, and freeing a map can pin a CPU for over ten seconds, at times causing customer-facing packet loss.

The root cause is a combination of design decisions in kernel/bpf/lpm_trie.c that do not scale well under dense, production-scale data. Before getting to the specifics, it helps to recall how tries accomplish prefix matching and where the BPF version falls short.

The Mechanics of a Trie

A trie is a tree that stores keys implicitly by their traversal path, unlike a binary search tree (BST) which must store the full key in every node to enable comparisons. Tries store keys by splitting them bit-by-bit, so a shared prefix occupies only a single set of nodes. That makes them memory-efficient for redundant data and natural for longest-prefix matching, which is why IP routing tables and CIDR lookups lean on them.

If a trie inspects one bit at a time, it's a binary trie; check more bits per hop and it becomes a multibit trie. Multibit tries chew through words faster, trading memory for traversal depth. Two notable further optimizations exist:

  • Path compression: collapsing long runs of single-child nodes into one, storing the skipped bits elsewhere.
  • Level compression: replacing a fully populated upper section of the tree with a single node with 2^depth children — the approach used by Linux's own IP route lookup in net/ipv4/fib_trie.c.

The kernel's BPF LPM trie implementation happens to use only a shallow version of the first trick and none of the second.

Why Lookups Get Slow

The BPF LPM trie is fundamentally a binary trie: each internal node has exactly two child pointers. While leaf nodes can do multibit comparisons, any branching decision in the internal structure is strictly two-way. In a dense tree, that has consequences. Consider a map storing keys 0, 1, and 3: you could ask for a three-way branch from the root, but the implementation forces you through an intermediate node just to decide which of the other two values you meant. That single extra hop per decision point is exactly where the traversal time disappears.

Path compression exists in a limited form—intermediate nodes appear only when two keys diverge by one bit—but with dense keys, it rarely kicks in. The pure binary structure also rules out level compression entirely. Worst-case, a fully populated trie degenerates into a binary search tree with height proportional to log2(nr_entries), and each level brings multiple chances for cache and TLB misses.

BPF LPM tries allocate nodes individually from a kernel freelist, so they land at arbitrary addresses. Every hop along a traversal path is a pointer chase that could fall outside the CPU's cache — or worse, beyond the TLB. Benchmark measurements on an AMD EPYC 9684X with 10K dense entries show lookup throughput degrading notably as the tree gains height, even before the map size forces dTLB misses to dominate. The result: throughput at around 1.5 million ops/sec with a million entries and dropping further beyond that.

Freeing Is the Worst Case

Lookup performance isn't the only sore spot. Freeing a BPF LPM trie map takes a striking amount of time even at modest sizes. The selftests benchmark on the EPYC system saw a 10K-entry map free operation take long enough that, at production scale, the kernel emitted soft lockup warnings and hung a core for seconds at a time. Because nodes are scattered across memory, tearing down a large map requires touching each one individually, hitting the same cache and TLB pitfalls as a traversal but doing so for every node in the tree.

Plotting the Next Step

The problems are now documented in benchmarks that Cloudflare has upstreamed to the Linux kernel. The obvious path forward is reusing the level-compressed trie logic from net/ipv4/fib_trie.c, which handles IP routes well precisely because it compresses those dense upper levels. Refactoring that into a common implementation that BPF maps can share is the natural first move. The work, and future benchmarks along the way, will be the subject of upcoming posts.