Merge branch 'bpf-unify-state-pruning-handling-of-invalid-misc-stack-slots'

Eduard Zingerman says:

====================
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: 0
total_insns abs max old: 837,487
total_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: 0
total_insns abs max old: 257,545
total_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).
====================

Link: https://patch.msgid.link/20251230-loop-stack-misc-pruning-v1-0-585cfd6cec51@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>

2 files changed, 69 insertions, 6 deletions

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0baae7828af2..3d44c5d06623 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]))
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 69061f030957..7f27b517d5d5 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
 	);
 }