* [PATCH bpf-next 1/2] bpf: allow states pruning for misc/invalid slots in iterator loops
2025-12-31 5:36 [PATCH bpf-next 0/2] bpf: unify state pruning handling of invalid/misc stack slots Eduard Zingerman
@ 2025-12-31 5:36 ` Eduard Zingerman
2025-12-31 5:36 ` [PATCH bpf-next 2/2] selftests/bpf: iterator based loop and STACK_MISC states pruning Eduard Zingerman
2025-12-31 17:10 ` [PATCH bpf-next 0/2] bpf: unify state pruning handling of invalid/misc stack slots patchwork-bot+netdevbpf
2 siblings, 0 replies; 4+ messages in thread
From: Eduard Zingerman @ 2025-12-31 5:36 UTC (permalink / raw)
To: bpf, ast, andrii; +Cc: daniel, martin.lau, kernel-team, yonghong.song, eddyz87
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.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 10 ++++------
1 file changed, 4 insertions(+), 6 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0baae7828af220accd4086b9bad270e745f4aff9..3d44c5d066239f1f86ec8d2f40d3a6abac222d66 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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]))
--
2.52.0
^ permalink raw reply related [flat|nested] 4+ messages in thread* [PATCH bpf-next 2/2] selftests/bpf: iterator based loop and STACK_MISC states pruning
2025-12-31 5:36 [PATCH bpf-next 0/2] bpf: unify state pruning handling of invalid/misc stack slots Eduard Zingerman
2025-12-31 5:36 ` [PATCH bpf-next 1/2] bpf: allow states pruning for misc/invalid slots in iterator loops Eduard Zingerman
@ 2025-12-31 5:36 ` Eduard Zingerman
2025-12-31 17:10 ` [PATCH bpf-next 0/2] bpf: unify state pruning handling of invalid/misc stack slots patchwork-bot+netdevbpf
2 siblings, 0 replies; 4+ messages in thread
From: Eduard Zingerman @ 2025-12-31 5:36 UTC (permalink / raw)
To: bpf, ast, andrii; +Cc: daniel, martin.lau, kernel-team, yonghong.song, eddyz87
The 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.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
tools/testing/selftests/bpf/progs/iters.c | 65 +++++++++++++++++++++++++++++++
1 file changed, 65 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 69061f0309579eada74e5f2a68640470ff94a8b3..7f27b517d5d5668a0d2204cb8f9a0632806c3959 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -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)
+{
+ asm volatile(
+ "*(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
);
}
--
2.52.0
^ permalink raw reply related [flat|nested] 4+ messages in thread* Re: [PATCH bpf-next 0/2] bpf: unify state pruning handling of invalid/misc stack slots
2025-12-31 5:36 [PATCH bpf-next 0/2] bpf: unify state pruning handling of invalid/misc stack slots Eduard Zingerman
2025-12-31 5:36 ` [PATCH bpf-next 1/2] bpf: allow states pruning for misc/invalid slots in iterator loops Eduard Zingerman
2025-12-31 5:36 ` [PATCH bpf-next 2/2] selftests/bpf: iterator based loop and STACK_MISC states pruning Eduard Zingerman
@ 2025-12-31 17:10 ` patchwork-bot+netdevbpf
2 siblings, 0 replies; 4+ messages in thread
From: patchwork-bot+netdevbpf @ 2025-12-31 17:10 UTC (permalink / raw)
To: Eduard Zingerman
Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song
Hello:
This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:
On Tue, 30 Dec 2025 21:36:02 -0800 you wrote:
> 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 =========
>
> [...]
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!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 4+ messages in thread