[PATCH bpf 1/2] bpf: Fix state pruning regression in bpf_loop() callbacks

[PATCH bpf 1/2] bpf: Fix state pruning regression in bpf_loop() callbacks

[David Windsor]

Commit f597664454bd ("bpf: bpf_scc_visit instance and backedges
accumulation for bpf_loop()") left dead stack slots in cached callback
states while SCC backedges were pending, defeating state pruning and
causing previously valid programs to hit the verifier instruction limit. On
affected kernels, ActPlane fails to load with -E2BIG.

Removing the incomplete_read_marks() check from clean_live_states() is
safe because zero-branch states have already had their stack read/write
effects propagated into the liveness masks consumed by
clean_verifier_state(). Pending SCC backedges only defer verifier-state
precision propagation and cannot add stack-liveness requirements after
cleanup.

Fixes: f597664454bd ("bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()")

Signed-off-by: David Windsor <dwindsor@gmail.com>

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e3814152b52f8139a5565b2e4ac1b80d82d1ea65..1e300ca71a8a833eb4c2a340b4f94342f54af5f2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -19791,8 +19791,6 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
 		if (sl->state.cleaned)
 			/* all regs in this state in all frames were already marked */
 			continue;
-		if (incomplete_read_marks(env, &sl->state))
-			continue;
 		clean_verifier_state(env, &sl->state);
 	}
 }
-- 
2.53.0

[PATCH bpf 2/2] selftests/bpf: cover bpf_loop() state pruning regression

[David Windsor]

Exercise 18 independent conditional stores to dead callback stack slots,
reproducing the verifier state explosion fixed by the preceding commit.

Signed-off-by: David Windsor <dwindsor@gmail.com>

diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index 75dd922e4e9f87ebc947ee6e621a789cad10431e..c1c3099a6a20391c8b36b39eedd9cc6ce893d996 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -783,4 +783,62 @@ __naked void check_add_const_regsafe_off(void)
 	: __clobber_common);
 }
 
+#define DEAD_STACK_SLOT(off) \
+	"call %[bpf_get_prandom_u32];" \
+	"if r0 == 0 goto 1f;" \
+	"*(u64 *)(r10 - " #off ") = 1;" /* dead stack store */ \
+	"goto 2f;" \
+	"1: *(u64 *)(r10 - " #off ") = 2;" /* dead stack store */ \
+	"2:;"
+
+__used __naked
+static void dead_stack_cb(void)
+{
+	asm volatile (
+		DEAD_STACK_SLOT(8)
+		DEAD_STACK_SLOT(16)
+		DEAD_STACK_SLOT(24)
+		DEAD_STACK_SLOT(32)
+		DEAD_STACK_SLOT(40)
+		DEAD_STACK_SLOT(48)
+		DEAD_STACK_SLOT(56)
+		DEAD_STACK_SLOT(64)
+		DEAD_STACK_SLOT(72)
+		DEAD_STACK_SLOT(80)
+		DEAD_STACK_SLOT(88)
+		DEAD_STACK_SLOT(96)
+		DEAD_STACK_SLOT(104)
+		DEAD_STACK_SLOT(112)
+		DEAD_STACK_SLOT(120)
+		DEAD_STACK_SLOT(128)
+		DEAD_STACK_SLOT(136)
+		DEAD_STACK_SLOT(144)
+		"r0 = 0;"
+		"exit;"
+		:
+		: __imm(bpf_get_prandom_u32)
+		: __clobber_all
+	);
+}
+
+#undef DEAD_STACK_SLOT
+
+SEC("?raw_tp")
+__success __flag(BPF_F_TEST_STATE_FREQ) __log_level(4)
+__naked void callback_dead_stack(void)
+{
+	asm volatile (
+		"r1 = 100;"
+		"r2 = dead_stack_cb ll;"
+		"r3 = 0;"
+		"r4 = 0;"
+		"call %[bpf_loop];" /* trigger state pruning */
+		"r0 = 0;"
+		"exit;"
+		:
+		: __imm(bpf_loop)
+		: __clobber_all
+	);
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.53.0