Post Syndicated from daroc original https://lwn.net/Articles/1106537/
The BPF verifier has historically worked by tracing every possible path of
execution through a program, checking, at each instruction, that various safety
properties hold. This works, but it can result in an exponential increase in the
number of states that need checking in programs with complicated control-flow.
Alexei Starovoitov, one of the kernel’s core BPF maintainers, has shared
a patch set that substantially reworks how the verifier tracks states, in
order to reduce the size of that exponential explosion.