Scalar Evolution for BPF Verifier
Eduard Zingerman
maintainerHi Everyone,
I would like to suggest "Scalar Evolution for the BPF Verifier" as a topic for discussion at the upcoming LSF/MM/BPF conference.
There are several ways to encode a loop in a BPF program:
1. Directly, using a loop counter together with for(){}, while(){} or goto statements.
2. Using iterators in conjunction with for(){}, while(){} or goto statements.
3. Using the bpf_loop() helper and a callback function.
While (1) is the most natural way to express loops for many use cases, it also has significant verification drawbacks: each loop iteration is verified separately and in full. When combined with nested loops or a high degree of branching within the loop body, this can quickly lead to hitting the 1M instruction verification limit.
Scalar Evolution is a static analysis technique used by both LLVM and GCC to estimate the number of iterations a loop in a program’s control-flow graph will execute at runtime. The core idea of the technique is a one-pass traversal of the program’s control-flow graph, assigning recurrence relations to variables within loop bodies. For example, consider the program below:
while (i != 10) {
f(i);
i++;
g(i);
}Scalar Evolution analysis would first track the evolution of the variable 'i' within the loop body:
while (i != 10) { // i = i0 at loop entry <---. Arrive back to
f(i); // i = i0 | the loop entry
i += 2; // i = i0 + 2 | with i = i0 + 2.
g(i); // i = i0 + 2 |
} // '------------------------'It would then conclude that the recurrence relation for 'i' at the loop header is 'i0 + 2*k', where 'k' is the loop iteration number. When combined with loop nesting information and information about conditions guarding loop back-edges, this recurrence relation can be used to compute the number of iterations the loop will execute:
'k = (10 - i0) / 2'.
I am currently working on adapting this technique for the BPF verifier and hope to have a working RFC ready sometime next month. At the conference, I would like to present the main ideas behind this adaptation and discuss both the coding patterns understood by this analysis and those for which it fails to provide improvements.
References:
- R. van Engelen, "Symbolic Evaluation of Chains of Recurrences for Loop Optimization"
https://www.researchgate.net/publication/2801813_Symbolic_Evaluation_of_Chains_of_Recurrences_for_Loop_Optimization
- R. van Engelen, "Efficient Symbolic Analysis for Optimizing Compilers"
https://www.researchgate.net/publication/2385991_Efficient_Symbolic_Analysis_for_Optimizing_Compilers
- R. van Engelen, "The CR\# Algebra and its Application in Loop Analysis and Optimization"
https://www.researchgate.net/publication/382316876_The_CR_Algebra_and_its_Application_in_Loop_Analysis_and_Optimization
- LLVM SCEV implementation source code
https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ScalarEvolution.cpp
- John Fastabend, "Using SCEV to establish pre and post-conditions over BPF code"
https://lpc.events/event/4/contributions/450/
- My work-in-progress implementation:
https://github.com/eddyz87/bpf/tree/scev
Best regards,
Eduard Zingerman