Skip to contentSkip to conversation

bpf: Fix state pruning regression in bpf_loop() callbacks

PATCH In review David Windsor 2 participants 3 messages Oct 8 – Oct 14

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

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

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()")
kernel/bpf/verifier.c +0 -2
index e3814152b52f8139a5565b2e4ac1b80d82d1ea65..1e300ca71a8a833eb4c2a340b4f94342f54af5f2 100644
@@ -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);
 	}
 }
Signature · 1 line
2.53.0
#1 lore raw

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

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

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +58 -0
index 75dd922e4e9f87ebc947ee6e621a789cad10431e..c1c3099a6a20391c8b36b39eedd9cc6ce893d996 100644
@@ -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";
Signature · 1 line
2.53.0
maintainer
#2 lore raw
In reply to David Windsor
Quoted 6 lines · 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.

Quoted 6 lines

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.

The patch does not apply, clean_live_states() no longer exists. Also, before submitting v2, please re-read the series [1] in order to understand the motivation for the change. States w/o branches can still contribute their precision marks to their parent states, in case if these states form a loop on a state graph.
The loops are formed on e.g. iterator or callback-based loops convergence.

[1] https://lore.kernel.org/bpf/[email protected]/

pw-bot: cr.

Quoted 18 lines
Fixes f597664454bd ("bpf: bpf_scc_visit instance and backedges accumulation for bpf_loop()")
kernel/bpf/verifier.c +0 -2
index e3814152b52f8139a5565b2e4ac1b80d82d1ea65..1e300ca71a8a833eb4c2a340b4f94342f54af5f2 100644
@@ -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);
  	}
  }