Hash table memory usage and a BPF interpreter bug

Ready to give LWN a try?

With a subscription to LWN, you can stay current with what is happening in the Linux and free-software community and take advantage of subscriber-only site features. We are pleased to offer you a free trial subscription, no credit card required, so that you can see for yourself. Please, join us!

Anton Protopopov led a short discussion at the 2025 Linux Storage, Filesystem, Memory-Management, and BPF Summit about amount of memory used by hash tables in BPF programs. He thinks that the current memory layout is inefficient, and wants to split the structure that holds table entries into two variants for different kinds of maps. When that proposal proved uncontroversial, he also took the chance to talk about a bug in BPF's call instruction.

Hash table memory use

Protopopov began with an explanation of the current structure of BPF hash tables. Each hashed bucket is a linked list of items; the table itself just stores a pointer to the first item in the list and a spinlock. Each item in the list is an htab_elem structure. This contains a hash of the key, a copy of the whole key, and two unions that are used in different ways by per-CPU and normal hash tables.

Half of the structure, 24 bytes, is only used by per-CPU BPF maps. Maps that are shared between CPUs are essentially wasting that space, Protopopov said. In a hash table with 100,000 elements, that's a total of about 2.4MB. To get some idea of how much of an impact that really had, he tried removing the per-CPU elements from htab_elem and running some benchmarks. The benchmarks reflected lower memory usage in line with his predictions, and were 7% faster as well.

There are obviously users of the per-CPU BPF maps, though. Even without considering users' BPF programs, there are a number of uses throughout the kernel as well. So Protopopov's question to the assembled BPF developers was: how can we remove the per-CPU data from htab_elem properly?

Alexei Starovoitov asked what per-CPU data was taking 24 bytes in the structure. Protopopov pointed at the bpf_lru_node element that is used to manage information on how recently a given key was accessed. Starovoitov asked whether the information could be shuffled around in the structure without removing it, but that doesn't seem to be possible, because the other components of the structure are used by all of the different types of BPF map.

Ultimately, the best Protopopov had been able to do was to split the structure into two variants of different sizes, and allocate the appropriate one based on the type of the map. Because BPF hash tables are widely used, that resulted in a big patch, so he wanted to solicit feedback first. After some additional discussion about alignment within the structure, he agreed to write a first pass of a patch set following that approach for people to look at.

Translated call instructions

Call instructions in BPF refer to functions by number, in the order in which they're defined in a BPF program. During loading, libbpf (or another user-space loader) replaces these numbers with the actual offsets of the function within the memory allocated for the program. The verifier processes the program in this form. After the program is verified, however, there's a final step: translating BPF bytecode so that it can be executed.

In most configurations, the BPF program is compiled to native machine code by the BPF just-in-time compiler (JIT). If the JIT is disabled (or doesn't support the current architecture), however, the BPF bytecode is directly interpreted instead. This interpreter stores the relative offset of a call instruction's destination from the instruction pointer in a 16-bit field.

So if there are two function calls with enough instructions between them to overflow this 16-bit field, Protopopov said, then the offset to the called function is incorrect. This breaks several things, including bpftool, the BPF program, and potentially the verifier's guarantees. Since the problem requires an unusual set of conditions to manifest, Protopopov wasn't exactly sure how big of a problem this was.

Starovoitov thought that Protopopov might be confusing two different variants of BPF bytecode; Starovoitov didn't think that the interpreter would run the version with the smaller 16-bit field. Protopopov was adamant that it would, however. Daniel Borkmann thought that such code was broken, and ought to be rejected — at run time, by the interpreter, since this issue is only apparent after verification.

Blaise Boscaccy asked whether Protopopov had tried using the invalid program counter to break BPF's security. Protopopov replied that he hadn't. If Protopopov is correct about the issue, and it poses a security risk, the only vulnerable kernels will be those running on architectures without support for the JIT. Borkmann thought that all such architectures were "niche". Ultimately, the discussion ended without a concrete commitment from anyone to investigate further. At the time of writing, the problem does not appear to have been discussed on the mailing list.