A large eBPF program is rejected with the verifier reporting that it processed too many instructions, even though the program itself is far shorter than the instruction limit. What is the verifier counting, and how do you restructure the program so it loads?
answer
- paths, not lines of code
- every branch forks the state
- pruning is what saves you
- verify a subprogram once, not per caller
- mask instead of comparing
basics
~20 sThe verifier counts instructions it simulates across every reachable path, not instructions in the program, so branches and loops multiply the work. Reduce path explosion: cut branches, help its bounds tracking, move iteration into bpf_loop(), and split logic into independently verified global subprograms or tail calls.
solid answer
~60 sThe number in that message is the verifier's **exploration budget**, not your program size. To prove safety it walks every reachable path, simulating instructions with abstract register state; each branch potentially doubles the work, and each bounded-loop iteration is re-walked. A 2,000-instruction program with deeply nested conditionals can easily require millions of simulated steps, and the verifier gives up at roughly a million (the log's final line reports processed instructions against that limit). State pruning saves it — when the verifier reaches an instruction in a state equivalent to one it already proved safe, it stops re-exploring — but heavily branchy code defeats pruning. The fixes are all about shrinking the explored graph: make bounds obvious (mask an index with `& (SIZE - 1)` rather than a chain of comparisons), replace unrolled or large loops with `bpf_loop()` so the body is verified once, factor code into **global** subprograms which are verified independently of their callers, or split the pipeline across tail calls. Unprivileged programs face a much smaller ceiling — 4,096 instructions of program length — as well.
go deeper
Know that eBPF programs face a size limit and that very large programs may simply be refused; the details of path exploration are not expected of you yet.
Explain that verification is path-sensitive, so branches and loop iterations multiply the instructions the verifier simulates, and that this is a different number from the program's own length.
Diagnose from the log's processed-instruction and state counts, then apply the right lever — masking to sharpen bounds, bpf_loop() for iteration, global subprograms for reuse, tail calls for genuine pipeline splits — rather than randomly deleting code.
Treat the complexity budget as a portability constraint: the oldest kernel in the fleet defines it, so minimum-kernel load tests belong in CI and program structure becomes an architectural decision, not a local one.
## Two different limits, one confusing message There are two distinct numbers, and the rejection usually concerns the second: 1. **Program length** — how many instructions the loaded program contains. Historically 4,096; since Linux 5.2 a privileged program may hold up to about a million. Unprivileged loads still face the old 4,096-instruction ceiling. 2. **Verification complexity** — how many instructions the verifier *simulates* while proving safety, capped at roughly one million. This is the one people hit, and it is why a 900-instruction program can be rejected for being too complex. The verifier log's closing line reports the processed count against the limit, along with state counts, which is the fastest way to tell how close you were. ## Why the counts diverge so violently Verification is path-sensitive. At every conditional the verifier forks its state and explores both sides, because safety must hold on *every* path. Nested conditionals therefore multiply: ten independent two-way branches in sequence describe up to 1,024 distinct paths through the code that follows. Bounded loops compound it further, since the verifier re-walks the body per iteration to track how ranges evolve. What keeps this from being hopeless is **state pruning**. The verifier records the state it held at instructions it has already verified; when it arrives at the same instruction in a state that is *equivalent or narrower*, it can stop, because the rest of that path was already proved. Well-shaped programs prune aggressively and verify in a few thousand steps. Programs where every path carries subtly different register ranges prune badly, and the exploration explodes. This explains an infuriating property: adding a seemingly harmless check somewhere early can push a program from loading in 30,000 steps to failing at a million, because it split states that used to merge. ## The techniques that actually work **Make bounds trivially derivable.** The single biggest lever. Replace a chain of comparisons with a mask: ```c idx &= (MAX_ENTRIES - 1); /* one instruction, exact range */ ``` After a mask the verifier knows the exact range in one step, rather than carrying a union of ranges down every branch. The same applies to clamping a length before a memory access rather than branching on several possible lengths. **Move iteration to runtime.** An unrolled or large bounded loop is simulated per iteration. `bpf_loop()` (Linux 5.17) verifies the callback once and iterates in the kernel; open-coded iterators (6.4) do the same with nicer syntax. This alone can drop processed-instruction counts by orders of magnitude. **Use global subprograms.** A `static` helper is typically inlined and re-verified in the caller's context on every path that reaches it. A **global** (non-static) subprogram with a BTF-described signature is verified *once, on its own*, against its declared argument types, and callers then only check that they pass matching arguments. Turning a hot helper from `static` to global is often a one-word fix for a complexity rejection. **Split with tail calls.** A tail call replaces the current program with another one from a program array, resetting the analysis: each stage is a separately verified program. It costs an indirect jump and loses the caller's stack, so use it to split genuine pipeline stages rather than to hide complexity. **Cut work you do not need.** Early-return on the uninteresting cases at the top of the program. Every instruction after an early return is one the verifier does not explore on that path. ## Reading the failure properly Before restructuring, get the data. Raise the log level so the final statistics line is visible and note the processed count and state counts; if you were at 990,000 and pruning is working, one targeted mask may be enough, whereas being an order of magnitude over means a structural change is required. Bisect by commenting out branches until it loads, then reintroduce them — the branch that triples the count is usually obvious once you measure. Also remember that the verifier improves every release. Programs rejected on an older kernel may verify comfortably on a newer one because pruning and range tracking got smarter. On a mixed fleet, the oldest kernel you support is the one that defines your complexity budget, and it belongs in CI — a load-only smoke test against the minimum supported kernel catches this before a rollout does.
- What is state pruning, and why does branchy code defeat it?The verifier remembers the register and stack state at instructions it has already proved safe; reaching the same instruction in an equivalent or narrower state lets it stop exploring. Branchy code arrives at shared instructions carrying subtly different value ranges each time, so states are never equivalent, nothing prunes, and exploration multiplies.
- Why does changing a helper from static to global sometimes fix a complexity rejection?A static helper is typically inlined and re-verified inside the caller on every path that reaches it. A global subprogram with a BTF-described signature is verified once, standalone, against its declared argument types; callers merely check the arguments they pass. The body's cost is paid a single time instead of once per path.
- How would you stop this class of failure reaching production?Pin the minimum supported kernel and run a load-only test against it in CI, since the verifier's pruning and range tracking improve every release and a program that loads on your laptop can be rejected on an older node. Record the processed-instruction count from the log as a rough budget indicator over time.
saying these in an interview costs you the question
- Thinks the limit counts lines in the source program
- Assumes a bounded loop costs the verifier nothing
- Believes adding checks always helps the verifier
- Reaches for tail calls before reducing branching
- Ignores that the limit differs by kernel version and privilege