BPF verifier adopts call graphs, lifts frame limit to 32

Alexei Starovoitov has reworked how the Linux BPF verifier measures nested calls, replacing an exponential walk of every call chain with call-graph analysis and raising the maximum frames from 16 to 32 for JITed programs.

The old path walked each chain of subprogram calls one by one. When each of N global functions called the next in both branches of a conditional, the program executed only N calls, yet the verifier examined 2^N chains. Twenty-eight such functions took about 24 seconds to load; thirty took 105 seconds. A 32-frame case could run for minutes.

Most of that work did not depend on any particular chain. Recursion, tail-call reachability, callback and private-stack rules, arena stack usage, and frame counts all depend on who calls whom. The series builds a call graph with transitive closure, moves those checks onto the graph, and drops the walk.

Load times fall sharply: 28 functions load in 0.7 ms rather than 24 seconds, and 250 fully interconnected global functions load in about 20 ms. Peak verifier memory rises only a few percent on selftests, sched_ext, and Cilium workloads.

The higher limit targets Rust BPF programs that nest crates deeply and already hit 16 frames. Depth beyond 16 still requires the JIT; such programs are rejected when the JIT is off instead of falling back to the interpreter. Starovoitov notes the rust-bpf programs that need 32 frames still require further verifier changes before they load.

One verdict shift: a tail call in an async callback that calls nothing is now rejected, matching other callbacks, because an async callback has no context for a tail call and the instruction can only be dead code.