[PATCH bpf-next 1/2] bpf: Walk a short loop for what it loads if something looks at it

[PATCH bpf-next 1/2] bpf: Walk a short loop for what it loads if something looks at it

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

  for (i = 0; i < 64; i++) {
          if (have)
                  sum += t->pid;
          t = v->task;                  /* __kptr: a task or NULL */
          have = t && t->prio > 100;
  }

t is loaded anew in each iteration. The first iteration of such a loop is
verified on its own, and the states that return to the loop head stand for
the other iterations. There have becomes [0, 1], also next to t == NULL:

  R2 invalid mem access 'scalar'

  for (i = 0; i < 64; i++) {
          sum += a[cur];                /* u8 a[16] */
          cur = order[i];               /* static const u8 order[64] */
  }

cur is order[0] after the first iteration and a byte after the next one:

  R4 unbounded memory access, make sure to bounds check any such access

Both load if the verifier goes through the iterations one by one: have goes
with t, each order[i] is a constant. It did so before the first iteration
was kept apart, and it still does for what a call returns.

Do the same for what is loaded and then looked at: t is the base of a load,
cur is an offset. A stack slot that the loop fills and that is only copied
later is no reason for a walk. test_rbtree_remove_many_noalloc() of
libarena is walked again: 22060 -> 27699 insns.

Fixes: df9b13a441c9 ("bpf: Keep the first iteration of a counted loop apart")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/scev.c     | 9 +++++----
 kernel/bpf/verifier.c | 2 +-
 2 files changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index 5415fcf9df2f..2a7d0c59f73b 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -3749,13 +3749,14 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
 		}
 		/*
 		 * What is loaded from memory or returned by a call in every iteration is the same
-		 * kind of thing in all of them. One iteration tells what. There is nothing more
-		 * to find out when iterations are looked at one by one. But for what goes with it:
-		 * a call returns NULL and a flag is set. So a walk comes first for a call.
+		 * kind of thing in all of them. One iteration tells what. A walk through the
+		 * iterations tells more: what goes with it, like a flag that is set if it's not
+		 * NULL, and each number of a table in .rodata. So a walk comes first. What is
+		 * loaded is often a leftover in a stack slot: not if nothing looks at it.
 		 */
 		if (expr_is_fresh(env, header_env->reg2expr[r], &call)) {
 			__set_bit(r, iters->fresh_regs);
-			if (!call)
+			if (!call && !bpf_flow_is_needed(env, insn_idx, r))
 				continue;
 		} else {
 			__set_bit(r, iters->forget_regs);
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 09a44723bb2e..479c52cc2f56 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -21636,7 +21636,7 @@ int bpf_flow_loop_enter(struct bpf_verifier_env *env, bool *backedge, bool *drop
 	entry->entry_state = entry_state;
 	entry->terminates = true;
 	/*
-	 *	idx = 0; for (i = 0; i < 100; i++) idx = table[idx];
+	 *	idx = 0; for (i = 0; i < 100000; i++) idx = table[idx];
 	 * What the loop makes of idx is not known before its body is looked at, and what idx is
 	 * at the entry goes with i == 0 only. So the state goes through the first iteration as
 	 * it is. The state that comes back to the head has idx in 0..255.
-- 
2.55.0

[PATCH bpf-next 2/2] selftests/bpf: Test short loops that carry what they load

[Alexei Starovoitov]

From: Alexei Starovoitov <ast@kernel.org>

A loop of 4 iterations loads a number and sets a flag if the number is a
valid index. The next iteration tests the flag only. Another loop takes the
index of the next iteration from a table in .rodata. Both load if the loop
is walked. Each has a twin that reads past the end of the map value.

A loop that fills a stack slot with what it loads is not walked if the slot
is only copied later: 17 insns for 40 iterations.

The two tests of a first iteration that is kept apart get 100000
iterations. 10 are walked now.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../selftests/bpf/progs/verifier_loop_need.c  | 95 +++++++++++++++++++
 .../selftests/bpf/progs/verifier_scev.c       | 14 +--
 2 files changed, 102 insertions(+), 7 deletions(-)

diff --git a/tools/testing/selftests/bpf/progs/verifier_loop_need.c b/tools/testing/selftests/bpf/progs/verifier_loop_need.c
index 281f94bfeb47..cfc98aeb155b 100644
--- a/tools/testing/selftests/bpf/progs/verifier_loop_need.c
+++ b/tools/testing/selftests/bpf/progs/verifier_loop_need.c
@@ -346,6 +346,101 @@ __naked void read_in_the_first_iteration(void)
 	SUM_OF_PREV(1, 40, "*(u64 *)(r10 - 8) = r9;");
 }
 
+/*
+ *	for (i = 0; i < 4; i++) { if (ok) sum += v[x]; x = *v; ok = x <= max; }
+ * x is loaded in every iteration and ok goes with it. One state for all iterations has both values
+ * of ok for each x.
+ */
+#define LOADED_WITH_FLAG(max)						\
+	asm volatile (							\
+	"r6 = %[vals] ll;"						\
+	"r7 = 0;"							\
+	"r8 = 0;"							\
+	"r9 = 0;"							\
+"1:	if r9 == 0 goto 2f;"						\
+	"r1 = r6;"							\
+	"r1 += r8;"							\
+	"r0 = *(u8 *)(r1 + 0);"						\
+"2:	r8 = *(u64 *)(r6 + 0);"						\
+	"r9 = 0;"							\
+	"if r8 > " #max " goto 3f;"					\
+	"r9 = 1;"							\
+"3:	r7 += 1;"							\
+	"if r7 < 4 goto 1b;"						\
+	"r0 = 0;"							\
+	"exit;"								\
+	:: __imm_addr(vals) : __clobber_all)
+
+OK("a short loop is walked for the flag that goes with what it loads")
+__naked void loaded_with_flag(void)
+{
+	LOADED_WITH_FLAG(63);
+}
+
+BAD("the flag is set for a number that is too large")
+__msg("invalid access to map value")
+__naked void loaded_with_wrong_flag(void)
+{
+	LOADED_WITH_FLAG(64);
+}
+
+/*
+ *	for (i = 0; i < 4; i++) { sum += v[x]; x = table[i]; }
+ * The table is in .rodata: in a walk each x is a known number.
+ */
+const u8 in_vals[4] = { 8, 16, 56, 255 }, past_vals[4] = { 8, 16, 57, 0 };
+
+#define INDEX_FROM_RODATA(table)					\
+	asm volatile (							\
+	"r6 = %[vals] ll;"						\
+	"r7 = 0;"							\
+	"r8 = 0;"							\
+"1:	r1 = r6;"							\
+	"r1 += r8;"							\
+	"r0 = *(u64 *)(r1 + 0);"					\
+	"r1 = %[" #table "] ll;"					\
+	"r1 += r7;"							\
+	"r8 = *(u8 *)(r1 + 0);"						\
+	"r7 += 1;"							\
+	"if r7 < 4 goto 1b;"						\
+	"r0 = 0;"							\
+	"exit;"								\
+	:: __imm_addr(vals), __imm_addr(table) : __clobber_all)
+
+OK("a short loop is walked for the numbers that it loads from .rodata")
+__naked void index_from_rodata(void)
+{
+	INDEX_FROM_RODATA(in_vals);
+}
+
+BAD("a number from .rodata is too large")
+__msg("invalid access to map value")
+__naked void index_from_rodata_too_large(void)
+{
+	INDEX_FROM_RODATA(past_vals);
+}
+
+/* A slot holds a leftover pointer. The loop fills it with what it loads. It's only copied later. */
+OK("no walk for what the loop loads if nothing looks at it")
+__log_level(2) __msg("processed 17 insns")
+__naked void leftover_in_a_slot(void)
+{
+	asm volatile (
+	"r6 = %[vals] ll;"
+	"*(u64 *)(r10 - 8) = r6;"
+	"r7 = 0;"
+"1:	if r7 >= 40 goto 2f;"
+	"r1 = *(u64 *)(r6 + 0);"
+	"*(u64 *)(r10 - 8) = r1;"
+	"r7 += 1;"
+	"goto 1b;"
+"2:	r1 = *(u64 *)(r10 - 8);"
+	"*(u64 *)(r6 + 0) = r1;"
+	"r0 = 0;"
+	"exit;"
+	:: __imm_addr(vals) : __clobber_all);
+}
+
 /* What a call returns is made anew in every iteration, like what is loaded */
 OK("a long loop carries what a call returns")
 int call_in_a_long_loop(void *ctx)
diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index c1aede6fa4ae..5c9c832fbbe0 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -4411,17 +4411,17 @@ __naked void post_cond_jlt32_copy(void)
 }
 
 /*
- * The loop loads r6 again in every iteration. It's 0 at the entry and a byte in all iterations
- * but the first one: the first iteration is verified on its own, the state that comes back to
- * the head stands for the rest.
+ * The loop loads r6 again in every iteration, and is too long for a walk. r6 is 0 at the entry and
+ * a byte in all iterations but the first one: the first iteration is verified on its own, the state
+ * that comes back to the head stands for the rest.
  */
 SEC("socket")
 __success __retval(0)
 __log_level(2)
-__msg("header_count is 10 ")
+__msg("header_count is 100000 ")
 __msg("can't widen r6, expr is _")
 __not_msg("widening r8")
-__msg("clamping r8 to 0..9 step 1")
+__msg("clamping r8 to 0..0x1869f step 1")
 __naked void index_loaded_in_previous_iteration(void)
 {
 	asm volatile ("					\
@@ -4439,7 +4439,7 @@ __naked void index_loaded_in_previous_iteration(void)
 	r0 = *(u8 *)(r1 + 0);				\
 	r6 = *(u8 *)(r7 + 0);				\
 	r8 += 1;					\
-	if r8 < 10 goto 1b;				\
+	if r8 < 100000 goto 1b;				\
 2:	r0 = 0;						\
 	exit;						\
 "	:
@@ -4473,7 +4473,7 @@ __naked void first_iteration_loads_less(void)
 	goto 3f;					\
 2:	r6 = *(u16 *)(r7 + 0);				\
 3:	r8 += 1;					\
-	if r8 < 10 goto 1b;				\
+	if r8 < 100000 goto 1b;				\
 4:	r0 = 0;						\
 	exit;						\
 "	:
-- 
2.55.0

Re: [PATCH bpf-next 1/2] bpf: Walk a short loop for what it loads if something looks at it

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Sat,  7 Nov 2026 17:58:18 +0000 you wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
>   for (i = 0; i < 64; i++) {
>           if (have)
>                   sum += t->pid;
>           t = v->task;                  /* __kptr: a task or NULL */
>           have = t && t->prio > 100;
>   }
> 
> [...]

Here is the summary with links:
  - [bpf-next,1/2] bpf: Walk a short loop for what it loads if something looks at it
    https://git.kernel.org/bpf/bpf-next/c/3fba1a6cf43a
  - [bpf-next,2/2] selftests/bpf: Test short loops that carry what they load
    https://git.kernel.org/bpf/bpf-next/c/1f56fd122f47

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html