freenode
Kernel & Low-Level

BPF verifier rewrite joins states instead of walking every path

Alexei Starovoitov's 49-patch series for bpf-next keeps equations in verifier state so more programs load without cost growing on every loop trip.

Linux BPF's verifier is getting a new core. Alexei Starovoitov has posted a 49-patch series for bpf-next that replaces the main analysis, including the scalar-evolution code used to estimate how many times a loop runs, with multi-pass joining of verifier states and equations that record how numbers relate.

The point is which programs are allowed to load, and how expensive that decision is. Starovoitov wrote that more valid programs load and that "the verdict depends less on the code pattern." Work is not supposed to grow with the number of iterations of a loop unless an error has to be examined trip by trip. When a program is rejected, the log is meant to show a path to the bug. He also wrote: "The proof is separate from the guesses. There is less code."

Against both the 7.4-rc3 verifier, which walks one path after another, and current bpf-next, which already joins some states, the series joins by default. Two states stay apart only after an error, or when a bound the program requires depends on a value. Numbers that do not affect that decision no longer multiply the states the verifier must keep. Limits shift from a fixed budget of instructions and jumps toward cost and memory.

A few user-visible rules move with the machinery. A static function that leaves a pointer to its own stack in a return register is no longer rejected at the exit; the register is unreadable in the caller, and only a read fails. Joined pointers to strings in read-only data can be accepted when one terminating zero covers every string in the range, except for format checks and for builds that still have to account for speculative execution. Loops with no trip count, and no error that asks for peeling, may now load only if they use a may_goto bound. One program that used to load is rejected because the compiler merged two bpf_obj_drop calls on different types into one; Starovoitov marks the helper so those calls stay separate.

He reports that 331,763 builds of 6,005 programs from other projects load on 7.4-rc3, on bpf-next, and on the series. On several large programs, including pieces used by Tetragon, the number of instructions the verifier processes falls once states are joined instead of explored apart. The verifier documentation, which still described a path walk with pruning, is rewritten from scratch.