BPF List
 help / color / mirror / Atom feed
* [PATCH bpf-next 1/2] bpf: Walk a short loop for what it loads if something looks at it
@ 2026-11-07 17:58 Alexei Starovoitov
  2026-11-07 17:58 ` [PATCH bpf-next 2/2] selftests/bpf: Test short loops that carry what they load Alexei Starovoitov
  2026-11-07 19:50 ` [PATCH bpf-next 1/2] bpf: Walk a short loop for what it loads if something looks at it patchwork-bot+netdevbpf
  0 siblings, 2 replies; 3+ messages in thread
From: Alexei Starovoitov @ 2026-11-07 17:58 UTC (permalink / raw)
  To: bpf; +Cc: daniel, andrii, eddyz87, memxor

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


^ permalink raw reply related	[flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-11-07 19:50 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-07 17:58 [PATCH bpf-next 1/2] bpf: Walk a short loop for what it loads if something looks at it Alexei Starovoitov
2026-11-07 17:58 ` [PATCH bpf-next 2/2] selftests/bpf: Test short loops that carry what they load Alexei Starovoitov
2026-11-07 19:50 ` [PATCH bpf-next 1/2] bpf: Walk a short loop for what it loads if something looks at it patchwork-bot+netdevbpf

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox