Older Linux kernels rejected any eBPF program containing a backward jump. What does the verifier require of a loop today, and what problem does the bpf_loop() helper solve?

## Why loops are a verifier problem at all eBPF programs run in kernel context, frequently with preemption disabled, sometimes in an interrupt handler, on paths that fire per packet or per syscall. There is no scheduler that will step in if your program takes an hour, and no watchdog to kill it. So one of the verifier's two core obligations — alongside memory safety — is proving that the program **terminates**. Every accepted program has a bounded worst-case instruction count. ## The original rule: a loop-free graph The first verifier took the simplest possible route to that proof: it built the control-flow graph and required it to be acyclic. Any backward jump was a rejection. That makes termination trivial — the longest path is bounded by the program length — at the cost of banning loops entirely. Programmers worked around it by unrolling: ```c #pragma unroll for (int i = 0; i < 8; i++) total += buf[i]; ``` clang expands that into eight straight-line copies, so the emitted bytecode has no backward jump and the graph stays acyclic. It works, and it is still a reasonable choice for small fixed counts, but it has obvious limits: the trip count must be a compile-time constant, and the instruction count grows linearly with it, so an unrolled loop of a few hundred iterations bloats the program. ## Bounded loops (Linux 5.3) Since 5.3 the verifier accepts real backward jumps when it can bound them. The mechanism is that its abstract interpreter tracks the loop variable's value range across iterations, simulating the loop until it can show the exit condition is reached — or until it can prove the state has converged. A loop like: ```c for (int i = 0; i < 64; i++) total += i; ``` is fine because the counter starts known, increases by a known amount, and is compared against a constant. Loops the verifier cannot bound are still rejected: a `while` on a value read from a map, a counter modified inside the body in a way it cannot follow, or a condition it cannot relate to the induction variable. The catch is that verification effort scales with the iterations. The verifier is *simulating* those iterations, and every simulated instruction counts against its complexity budget — so a loop that is perfectly bounded at 100,000 iterations will be rejected not for being unbounded but for being too expensive to prove. ## bpf_loop() (Linux 5.17) `bpf_loop()` decouples the two. You call it with a maximum iteration count, a callback, and a context pointer: ```c static long body(__u32 index, void *ctx) { /* ... */ return 0; } bpf_loop(nr_iterations, body, &my_ctx, 0); ``` The verifier checks the callback body **once**, as a subprogram, and then trusts the helper to run it up to `nr_iterations` times at runtime; the callback returning non-zero breaks out early. Verification cost is now independent of the trip count, which is what makes loops over thousands of elements practical. The tradeoff is a function call per iteration rather than inlined straight-line code, so for very small fixed counts unrolling is still faster. Linux **6.4** added *open-coded iterators*, which give the same runtime-iteration property with ordinary `for`-loop syntax and the ability to break out naturally, and they have become the preferred style on kernels new enough to have them. ## Choosing between them - **Small, fixed count (under a few dozen):** unroll. Cheapest at runtime, negligible verification cost. - **Moderate, bounded count:** a plain bounded loop, provided the verifier's budget absorbs the simulation. - **Large or data-dependent count, up to a known ceiling:** `bpf_loop()` or open-coded iterators. Verification cost stays flat. ## What this means when you are debugging Two different rejections look similar and are not. "Back-edge from insn X to Y" or an unbounded-loop complaint means the verifier could not prove termination — the loop's shape is the problem. A complaint about processing too many instructions means the loop *is* bounded but the simulation was too expensive — the trip count is the problem. The first is fixed by restructuring the condition so the bound is derivable; the second by moving iteration to runtime with `bpf_loop()`. Reaching for the wrong fix is a common waste of an afternoon.