bpf: unify state pruning handling of invalid/misc stack slots
Subsystems (4)
Eduard Zingerman
maintainercover bpf: unify state pruning handling of invalid/misc stack slots
This change unifies states pruning handling of NOT_INIT registers, STACK_INVALID/STACK_MISC stack slots for regular and iterator/callback based loop cases.
The change results in a modest verifier performance improvement:
========= selftests: master vs loop-stack-misc-pruning =========
File Program Insns (A) Insns (B) Insns (DIFF) ------------------------------- -------------------- --------- --------- ---------------- test_tcp_custom_syncookie.bpf.o tcp_custom_syncookie 38307 18430 -19877 (-51.89%) xdp_synproxy_kern.bpf.o syncookie_tc 23035 19067 -3968 (-17.23%) xdp_synproxy_kern.bpf.o syncookie_xdp 21022 18516 -2506 (-11.92%)
Total progs: 4173 Old success: 2520 New success: 2521 total_insns diff min: -99.99% total_insns diff max: 0.00%
0 -> value: 0
value -> 0: 0total_insns abs max old: 837,487total_insns abs max new: 837,487
-100 .. -90 %: 1 -60 .. -50 %: 3 -50 .. -40 %: 2 -40 .. -30 %: 2 -30 .. -20 %: 8 -20 .. -10 %: 4 -10 .. 0 %: 5 0 .. 5 %: 4148
========= scx: master vs loop-stack-misc-pruning =========
File Program Insns (A) Insns (B) Insns (DIFF) ------------------------- ---------------- --------- --------- ---------------- scx_arena_selftests.bpf.o arena_selftest 257545 243678 -13867 (-5.38%) scx_chaos.bpf.o chaos_dispatch 13989 12804 -1185 (-8.47%) scx_layered.bpf.o layered_dispatch 27600 13925 -13675 (-49.55%)
Total progs: 305 Old success: 292 New success: 292 total_insns diff min: -49.55% total_insns diff max: 0.00%
0 -> value: 0
value -> 0: 0total_insns abs max old: 257,545total_insns abs max new: 243,678
-50 .. -45 %: 7 -30 .. -20 %: 5 -20 .. -10 %: 14 -10 .. 0 %: 18 0 .. 5 %: 261
There is also a significant verifier performance improvement for some bpf_loop() heavy Meta internal programs (~ -40% processed instructions).
---
Eduard Zingerman (2):
bpf: allow states pruning for misc/invalid slots in iterator loops selftests/bpf: iterator based loop and STACK_MISC states pruning
kernel/bpf/verifier.c | 10 ++--- tools/testing/selftests/bpf/progs/iters.c | 65 +++++++++++++++++++++++++++++++ 2 files changed, 69 insertions(+), 6 deletions(-)
---
base-commit: ccaa6d2c9635a8db06a494d67ef123b56b967a78
change-id: 20251230-loop-stack-misc-pruning-18b1ac62ae1a
Eduard Zingerman
maintainerPATCH 1/2 bpf: allow states pruning for misc/invalid slots in iterator loops
Within an iterator or callback based loop, it should be safe to prune the current state if the old state stack slot is marked as STACK_INVALID or STACK_MISC:
- either all branches of the old state lead to a program exit;
- or some branch of the old state leads the current state.
This is the same logic as applied in non-loop cases when states_equal() is called in NOT_EXACT mode.
The test case that exercises stacksafe() and demonstrates the difference in verification performance is included in the next patch. I'm not sure if it is possible to prepare a test case that exercises regsafe(); it appears that the compute_live_registers() pass makes this impossible.
Nevertheless, for code readability reasons, I think that stacksafe() and regsafe() should handle STACK_INVALID / NOT_INIT symmetrically. Hence, this commit changes both functions.
--- kernel/bpf/verifier.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +4 -6
@@ -19086,11 +19086,9 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,if (exact ==EXACT )return regs_exact (rold, rcur, idmap); -if (rold->type ==NOT_INIT ) { -if (exact ==NOT_EXACT || rcur->type ==NOT_INIT ) -/* explored state can't have used this */ -return true; - } +if (rold->type ==NOT_INIT ) +/* explored state can't have used this */ +return true;/* Enforce that register types have to match exactly, including their * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
@@ -19259,7 +19257,7 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old, spi = i /BPF_REG_SIZE ; -if (exact !=NOT_EXACT && +if (exact ==EXACT && (i >= cur->allocated_stack || old->stack[spi].slot_type[i %BPF_REG_SIZE ] != cur->stack[spi].slot_type[i %BPF_REG_SIZE ]))
Signature · 1 line
2.52.0
Eduard Zingerman
maintainerPATCH 2/2 selftests/bpf: iterator based loop and STACK_MISC states pruning
In reply to Eduard ZingermanThe test case first initializes 9 stack slots as STACK_MISC, then conditionally updates each of them to SCALAR spill inside an iterator based loop. This leads to 2**9 combinations of MISC/SPILL marks for these slots at the iterator next call.
The loop converges only if the verifier treats such states as equivalent, otherwise visited states are evicted from the states cache too quickly.
--- tools/testing/selftests/bpf/progs/iters.c | 65 +++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+)
tools/testing/selftests/bpf/progs/iters.c +65 -0
@@ -1997,6 +1997,71 @@ static void loop_cb4(void) "goto 2b;" : : __imm(bpf_get_prandom_u32) + ); +} + +SEC("raw_tp") +__success +__naked int stack_misc_vs_scalar_in_a_loop (void ) +{ + asmvolatile ( +"*(u8 *)(r10 - 15) = 1;" /* This marks stack slot fp[-16] as STACK_MISC. */ +"*(u8 *)(r10 - 23) = 1;" +"*(u8 *)(r10 - 31) = 1;" +"*(u8 *)(r10 - 39) = 1;" +"*(u8 *)(r10 - 47) = 1;" +"*(u8 *)(r10 - 55) = 1;" +"*(u8 *)(r10 - 63) = 1;" +"*(u8 *)(r10 - 71) = 1;" +"*(u8 *)(r10 - 79) = 1;" +"r1 = r10;" +"r1 += -8;" +"r2 = 0;" +"r3 = 10;" +"call %[bpf_iter_num_new];" +"loop_%=:" +"r1 = r10;" +"r1 += -8;" +"call %[bpf_iter_num_next];" +"if r0 == 0 goto loop_end_%=;" + +#define maybe_change_stack_slot(off) \ +"call %[bpf_get_prandom_u32];" \ +"if r0 == 42 goto +1;" \ +"goto +1;" \ + "*(u64 *)(r10 " #off ") = r0;" + +/* +* When comparing verifier states fp[-16] will be +* either STACK_MISC or SCALAR. Pruning logic should +* consider old STACK_MISC equivalent to current SCALAR +* to avoid states explosion. +*/ + maybe_change_stack_slot(-16) + maybe_change_stack_slot(-24) + maybe_change_stack_slot(-32) + maybe_change_stack_slot(-40) + maybe_change_stack_slot(-48) + maybe_change_stack_slot(-56) + maybe_change_stack_slot(-64) + maybe_change_stack_slot(-72) + maybe_change_stack_slot(-80) + +#undef maybe_change_stack_slot + + "goto loop_%=;" + "loop_end_%=:" + "r1 = r10;" + "r1 += -8;" + "call %[bpf_iter_num_destroy];" + "r0 = 0;" + "exit;" + : + : __imm(bpf_get_prandom_u32), + __imm(bpf_iter_num_new), + __imm(bpf_iter_num_next), + __imm(bpf_iter_num_destroy), + __imm_addr(amap) : __clobber_all ); }
Signature · 1 line
2.52.0
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 9 lines · On Tue, 30 Dec 2025 21:36:02 -0800 you wrote:
This change unifies states pruning handling of
NOT_INITregisters, STACK_INVALID/STACK_MISC stack slots for regular and iterator/callback based loop cases.The change results in a modest verifier performance improvement:
========= selftests: master vs loop-stack-misc-pruning =========
[...]
Here is the summary with links:
- [bpf-next,1/2] bpf: allow states pruning for misc/invalid slots in iterator loops
https://git.kernel.org/bpf/bpf-next/c/840692326e92 - [bpf-next,2/2] selftests/bpf: iterator based loop and STACK_MISC states pruning https://git.kernel.org/bpf/bpf-next/c/4fd99103eef3
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html