[PATCH bpf-next 00/11] bpf: fixes and follow-ups for 32-/64-bit scalar evolution

[PATCH bpf-next 00/11] bpf: fixes and follow-ups for 32-/64-bit scalar evolution

[Eduard Zingerman]

Fixes:
- bpf: look for current loop in upper frames in states_equal()
- bpf: do not intersect with current register range on clamp
- bpf: reject pointer operands for 32-bit recurrences/latches

Follow-ups:
- bpf: (zext32 (zext32 X)) -> (zext32 X) SCEV simplification rule
- bpf: check the iteration count before the predicted exit value

Note: this supersedes [1].

[1] bpf: reject pointer operands for 32-bit recurrences/latches
    https://lore.kernel.org/bpf/a7b9422e00b9a3f5438e996f01e97bef476040e0.camel@gmail.com/

There are some veristat improvements after clamping changes and new
zext32 simplification rule.

A: master; B: scev-simpler-clamp. Corpora: cilium, meta, scx, selftests.
Object exclusions: verifier_scev.bpf.o.
Histogram: selected programs, without the table filters.

Total progs: 8071
 -85 .. -75  %: 1
 -35 .. -25  %: 3
 -25 .. -20  %: 18
 -20 .. -10  %: 5
 -10 .. 0    %: 13
   0 .. 5    %: 8031

Tables: success in both runs; baseline Insns >= 5,000.
Ranked by percentage change, then instruction-count change, file, program.
Meta names are anonymized; numbered objects are distinct files.

Top wins
--------

File                       Program                            Insns (A)  Insns (B)      Insns (DIFF)
-------------------------  ---------------------------------  ---------  ---------  ----------------
profiler-06.bpf.o          on_perf_event                          94751      64595  -30156 (-31.83%)
profiler-19.bpf.o          sched_switch_offcpu                    21906      15726   -6180 (-28.21%)
profiler-12.bpf.o          sched_switch                           12105       9015   -3090 (-25.53%)
profiler-26.bpf.o          handle_cu_mem_address_reserve          12702       9738   -2964 (-23.33%)
profiler-26.bpf.o          handle_cu_mem_create                   12702       9738   -2964 (-23.33%)
profiler-26.bpf.o          handle_malloc                          12702       9738   -2964 (-23.33%)
profiler-26.bpf.o          handle_cu_mem_map                      12900       9936   -2964 (-22.98%)
profiler-09.bpf.o          on_custom_event_start                  12951       9987   -2964 (-22.89%)
profiler-09.bpf.o          trace_func_entry                       12951       9987   -2964 (-22.89%)
profiler-19.bpf.o          sched_waking                            6642       5160   -1482 (-22.31%)
profiler-27.bpf.o          handle_cuda_launch_exc                  6665       5183   -1482 (-22.24%)
profiler-27.bpf.o          handle_cuda_launch                      6678       5196   -1482 (-22.19%)
profiler-12.bpf.o          on_custom_event_begin                   6885       5403   -1482 (-21.53%)
profiler-12.bpf.o          on_custom_event_end                     6889       5407   -1482 (-21.51%)
profiler-26.bpf.o          handle_mtia_cached_alloc               13870      10906   -2964 (-21.37%)
profiler-26.bpf.o          handle_mtia_allocate_enter             13931      10967   -2964 (-21.28%)
profiler-26.bpf.o          handle_pytorch_malloc                  14223      11259   -2964 (-20.84%)
profiler-19.bpf.o          oncpu                                   7178       5696   -1482 (-20.65%)
profiler-12.bpf.o          on_task_enqueued                        7223       5741   -1482 (-20.52%)
profiler-12.bpf.o          sched_waking                            7258       5776   -1482 (-20.42%)
profiler-12.bpf.o          on_task_dequeued                        7398       5916   -1482 (-20.03%)
profiler-12.bpf.o          on_request_context_event                7489       6007   -1482 (-19.79%)
profiler-12.bpf.o          on_pytorch_event                        7490       6008   -1482 (-19.79%)
profiler-12.bpf.o          on_task_stats                           7572       6090   -1482 (-19.57%)
profiler-12.bpf.o          oncpu                                   7676       6194   -1482 (-19.31%)
profiler-12.bpf.o          get_crochet_walltime_stacks            22063      18973   -3090 (-14.01%)
profiler-24.bpf.o          get_task_stacks                        64928      61154    -3774 (-5.81%)

---
Eduard Zingerman (11):
      bpf: reject pointer operands for 32-bit recurrences/latches
      bpf: do not intersect with current register range on clamp
      bpf: look for current loop in upper frames in states_equal()
      bpf: check the iteration count before the predicted exit value
      bpf: (zext32 (zext32 X)) -> (zext32 X) SCEV simplification rule
      bpf: print 32-bit SCEV bounds as 32-bit numbers
      selftests/bpf: pointer operands for 32-bit recurrences/latches
      selftests/bpf: cases with empty range error under old clamping logic
      selftests/bpf: case reporting infinite loop w/o current_loop() changes
      selftests/bpf: 32-bit copy of the counter compared at the latch
      selftests/bpf: Restore stack pointer subrange pruning coverage

 include/linux/bpf_verifier.h                       |   1 +
 kernel/bpf/log.c                                   |   8 +
 kernel/bpf/scev.c                                  |  47 +++--
 kernel/bpf/states.c                                |  10 +-
 tools/testing/selftests/bpf/progs/verifier_scev.c  | 235 ++++++++++++++++++++-
 .../selftests/bpf/progs/verifier_stack_ptr.c       |  30 +--
 6 files changed, 289 insertions(+), 42 deletions(-)
---
base-commit: b116ac6087541d3d98031e786adbe9c733cd6df3
change-id: 20261022-scev-simpler-clamp-4b5486b201d2

[PATCH bpf-next 01/11] bpf: reject pointer operands for 32-bit recurrences/latches

[Eduard Zingerman]

Avoid inferring loop bounds for the following program shapes:

     32-bit latch (A)      |    32-bit recurrence (B)
  -------------------------+--------------------------
     r1 = ... pointer ...  |    r1 = ... pointer ...
     r2 = ... pointer ...  |    r2 = ... pointer ...
  l: r1 += 8               | l: w1 += 8
     ...                   |    ...
     if w1 < w2 goto l     |    if r1 < r2 goto l

(A) Scalar bounds for pointers represent only offsets from their
    common origin values. The 32-bit operations also depend on the
    runtime base address: the addresses can wrap at 32 bits without
    the tracked offsets wrapping. Thus, offsets alone do not determine
    the iteration count.

(B) 32-bit operations on pointers either prohibited (wX += 1)
    or convert them to scalars (wX = wX). No need to deal with
    this at SCEV level.

Fixes: 32e962577d2d ("bpf: Support 32-bit linear scalar evolution")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/scev.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index fea77772ca96..f9e2ca6a5a12 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -2024,7 +2024,8 @@ static void log_incompatible_scev_values(struct bpf_verifier_env *env, const cha
 }
 
 static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_state *st,
-				  const struct scev_value *a, const struct scev_value *b)
+				  const struct scev_value *a, const struct scev_value *b,
+				  const struct linear_latch *latch)
 {
 	const struct bpf_reg_state *ra, *rb;
 
@@ -2035,7 +2036,7 @@ static bool scev_value_compatible(struct bpf_verifier_env *env, struct bpf_func_
 	}
 	ra = scev_reg_for_read(env, st, a->ptr_reg);
 	rb = scev_reg_for_read(env, st, b->ptr_reg);
-	if (ra && rb && bpf_same_memory_origin(ra, rb))
+	if (ra && rb && bpf_same_memory_origin(ra, rb) && !latch->zext32 && !latch->jmp32)
 		return true;
 
 incompatible:
@@ -2267,7 +2268,7 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		}
 		return false;
 	}
-	if (!scev_value_compatible(env, st, &initial_val, &bound_val))
+	if (!scev_value_compatible(env, st, &initial_val, &bound_val, latch))
 		return false;
 
 	initial = initial_val.value;
@@ -2700,6 +2701,9 @@ int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta
 		reg = scev_reg_for_linear(cur_func, r);
 		/* If SCEV for r is (linear <reg> <slope>) */
 		if (reg && is_simple_linear(scev, r_scev, &coefs) && is_widenable_reg_type(reg)) {
+			/* 32-bit ALU operations on pointers convert them to scalars */
+			if (coefs.zext32 && reg->type != SCALAR_VALUE)
+				goto cant_widen;
 			/* Spills at varying offsets lose precision */
 			if (test_bit(r, loop->store_base_regs)) {
 				spill_base = true;

-- 
2.53.0

[PATCH bpf-next 02/11] bpf: do not intersect with current register range on clamp

[Eduard Zingerman]

scev.c:bpf_clamp_scev_regs() is called each time verifier returns to a
loop header via a backedge. It's purpose is to re-establish computed
variable ranges for registers with linear SCEVs.
It can be defined as:
- For each register R with linear SCEV compute:
  - loop_range(R) := entry_range(R) * iterations_count
  - range(R) := range(R) ∩ loop_range(R)

Such formulation is necessary to avoid ranges over-approximation in
examples like below:

        r1 = 0;              SCEVs: r1 = (linear r1 1)
        r3 = 0;                     r3 = (linear r3 1)
  loop:   r3 += 1;
          r1 += 1;
          if r1 < 5 goto loop;
        r0 = 0;
        exit;

- At loop entry r3 is widened to be in a range r3 ∈ {0,1,2,3,4}.
- After increment it becomes r3 ∈ {1,2,3,4,5}.
- On a second iteration the bpf_clamp_scev_regs() forces r3 to become
  r3 ∈ {1,2,3,4}. W/o clamping logic r3 range wouldn't shrink
  preventing loop from converging in states.c:states_equal().

However, intersection logic might lead to assigning an empty range to
a register, as in example below:

        r1 = 0;           verification
        r3 = 0;               path
  loop:   r3 += 1;              | <---------.
          if r3 != 5 goto +0;   | r3 ∈ {5}  |
          r1 += 1;              |           |
          if r1 != 5 goto loop; '-----------'
        r0 = 0;
        exit;

- At header r3 ∈ {0,1,2,3,4}.
- While exploring the branch `if r3 != 5 goto ...` with r3 ∈ {5}.
- On a second iteration:

    r3 := {0,1,2,3,4} ∩ {5} = ∅

Which stops verification with the following error:

  verifier bug: scev clamp produced empty range for r3

Technically this means that the current verification path is
impossible at runtime and should not be traced further.

This commit mitigates the above by removing the intersection logic,
the function is now defined as:
- For each register R with linear SCEV compute:
  - range(R) := entry_range(R) * iterations_count

This is still sound, provided that SCEV expressions loop execution
counts are correct.

Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/scev.c                                      | 6 ------
 tools/testing/selftests/bpf/progs/verifier_scev.c      | 2 +-
 tools/testing/selftests/bpf/progs/verifier_stack_ptr.c | 7 ++-----
 3 files changed, 3 insertions(+), 12 deletions(-)

diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index f9e2ca6a5a12..d67e793d7a18 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -2896,12 +2896,6 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur
 			continue;
 
 		linear_bounds(entry_reg, max_header_count, &coefs, &bounds);
-		bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
-		bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
-		if (cnum64_is_empty(bounds.r64)) {
-			verifier_bug(env, "scev clamp produced empty range for r%d", r);
-			return -EFAULT;
-		}
 		if (log->level & BPF_LOG_LEVEL2) {
 			bpf_log(log, "loop header at %d, clamping ", insn_idx);
 			log_reg(env, r);
diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 661ce9ca8f93..14594ba5dbfd 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -1592,7 +1592,7 @@ __msg_next("  r0=(+ r0 -1) / (linear (+ r0 -1) -1)")
 __msg("loop header at 1, header_count is 3 ")
 __msg("loop header at 1, widening r0 to 1..3 step 1")
 __msg("1: R0=scalar(smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=3,var_off=(0x0; 0x3)) loop_stack=1")
-__msg("loop header at 1, clamping r0 to 1..2 (s32 1..2) step 1")
+__msg("loop header at 1, clamping r0 to 1..3 step 1")
 __msg("processed 5 insns")
 __naked void post_cond_jne_neg_step(void)
 {
diff --git a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
index 7fa7bc207850..dc176f407c36 100644
--- a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
+++ b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
@@ -601,11 +601,8 @@ __flag(BPF_F_TEST_STATE_FREQ)
  */
 __msg("loop header at 3, widening r7 to -72..-16 step 8")
 __msg("R7=fp(smin=smin32=-64,smax=smax32=-8")
-/*
- * back-edge state is clamped to the remaining iterations and pruned
- * at the header, because [-64, -16] is within the widened [-72, -16]
- */
-__msg("loop header at 3, clamping r7 to -64..-16 (s32 -64..-8) step 8")
+/* back-edge state is clamped to the widened range and pruned at the header */
+__msg("loop header at 3, clamping r7 to -72..-16 step 8")
 __msg("from 5 to 3: safe")
 __msg("processed 9 insns")
 __naked void stack_ptr_subrange_in_loop(void)

-- 
2.53.0

Re: [PATCH bpf-next 02/11] bpf: do not intersect with current register range on clamp

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 4661 bytes --]

> bpf: do not intersect with current register range on clamp

TL;DR:
- This patch alone may make the verifier reject valid bounded loops with
  "infinite loop detected"; the fix is later in the series, which breaks
  bisection
- Nested loops may still be wrongly rejected after the later fix

> diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
> --- a/kernel/bpf/scev.c
> +++ b/kernel/bpf/scev.c

[ ... ]

> @@ -2893,18 +2893,12 @@ int bpf_clamp_scev_regs(struct bpf_verifier_env *env, struct bpf_func_state *cur
>  		reg = scev_reg_for_linear(cur_func_state, r);
>  		if (!entry_reg || !reg || entry_reg->type == NOT_INIT || reg->type == NOT_INIT ||
>  		    is_unbound_scev_reg(env, entry_st, r))
>  			continue;
>
>  		linear_bounds(entry_reg, max_header_count, &coefs, &bounds);
> -		bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
> -		bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
> -		if (cnum64_is_empty(bounds.r64)) {
> -			verifier_bug(env, "scev clamp produced empty range for r%d", r);
> -			return -EFAULT;
> -		}
>  		if (log->level & BPF_LOG_LEVEL2) {
>  			bpf_log(log, "loop header at %d, clamping ", insn_idx);
>  			log_reg(env, r);
>  			bpf_log(log, " to ");
>  			log_bounds(env, &bounds);
>  			bpf_log(log, "\n");

With the intersection gone, the clamped range depends only on the loop
entry state.  bpf_widen_scev_regs() computes the same thing, since it calls
linear_bounds() on the same entry register with the same max_header_count.

So every backedge now gives the induction variable the widened range again,
and the induction variable no longer changes between iterations.  Before
this patch it narrowed each time:

  [0..9] -> [1..9] -> [2..9]

bpf_is_state_visited() only sends a checkpoint with branches > 0 to
RANGE_WITHIN pruning when current_loop() finds the same entry_state for the
old and the current state.  Otherwise it falls through to the infinite loop
check:

    if (states_maybe_looping(&sl->state, cur) &&
        states_equal(env, &sl->state, cur, EXACT) && ...) {
            verbose(env, "infinite loop detected at insn %d\n", insn_idx);
            return -EINVAL;
    }

At this commit current_loop() only looks at st->frame[st->curframe], so it
returns NULL for checkpoints inside a subprogram called from the body of a
terminating loop.

One trigger is a valid bounded loop where the first iteration changes some
caller state that blocks the match at the header (for example, the callee
turns a caller spill into STACK_MISC), while the callee states of
iterations 1 and 2 are otherwise identical.  The old intersection kept the
caller's induction variable different in iteration 2, so
states_equal(EXACT) failed and verification continued.  With this patch
the states compare EXACT-equal and the program is rejected with "infinite
loop detected".  The clamp_callee_state_pruning test in 120b396ad6dc
("selftests/bpf: case reporting infinite loop w/o current_loop() changes")
is this case.

Doesn't this commit on its own reject valid programs?

A fix appears later in the series in cf18840bc068 ("bpf: look for current
loop in upper frames in states_equal()"), whose changelog says:

  Doing skip_inf_loop_check is necessary after the previous patch:
  Clamping now reproduces the widened range at every back edge

Since bisection can land on this commit, could that change be folded into
this patch or ordered before it?

A related question about the end of the series.  cf18840bc068 only helps
when the current frame has no active loop.  Consider states inside an inner
loop that is entered again on the second iteration of a terminating outer
loop.  current_loop() finds the inner loop in both states, but its
entry_state differs, because handle_loop_entry_exit() splits a new one on
each entry.  So the EXACT check runs, and loop_stack_safe() does not
compare entry_state.

With the outer induction variable now the same on every outer iteration, a
program like the one below looks like it would still hit "infinite loop
detected" after cf18840bc068 (with the old code the outer induction
variable was [1..9] on the second outer iteration and the EXACT compare
failed):

    w1 = 1;
    *(u32 *)(r10 - 8) = r1;
    r6 = 0;
1:  r7 = 0;
2:  *(u32 *)(r10 - 4) = 1;   /* fp-8 spill -> STACK_MISC */
    r7 += 1;
    if r7 < 3 goto 2b;
    r6 += 1;
    if r6 < 10 goto 1b;
    r0 = *(u32 *)(r10 - 8);
    exit;

Is that case covered somewhere I missed?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/40044354980

Re: [PATCH bpf-next 02/11] bpf: do not intersect with current register range on clamp

[Eduard Zingerman]

On Sat, 2026-10-24 at 00:41 +0000, bot+bpf-ci@kernel.org wrote:

...

> Since bisection can land on this commit, could that change be folded into
> this patch or ordered before it?

Commits should remain separate for documentation purposes.
Full test suite passes on both.

> A related question about the end of the series.  cf18840bc068 only helps
> when the current frame has no active loop.  Consider states inside an inner
> loop that is entered again on the second iteration of a terminating outer
> loop.  current_loop() finds the inner loop in both states, but its
> entry_state differs, because handle_loop_entry_exit() splits a new one on
> each entry.  So the EXACT check runs, and loop_stack_safe() does not
> compare entry_state.
> 
> With the outer induction variable now the same on every outer iteration, a
> program like the one below looks like it would still hit "infinite loop
> detected" after cf18840bc068 (with the old code the outer induction
> variable was [1..9] on the second outer iteration and the EXACT compare
> failed):
> 
>     w1 = 1;
>     *(u32 *)(r10 - 8) = r1;
>     r6 = 0;
> 1:  r7 = 0;
> 2:  *(u32 *)(r10 - 4) = 1;   /* fp-8 spill -> STACK_MISC */
>     r7 += 1;
>     if r7 < 3 goto 2b;
>     r6 += 1;
>     if r6 < 10 goto 1b;
>     r0 = *(u32 *)(r10 - 8);
>     exit;
> 
> Is that case covered somewhere I missed?

This example is valid. Need to relax the condition in the
current_loop() or bpf_is_state_visited().

Re: [PATCH bpf-next 02/11] bpf: do not intersect with current register range on clamp

[Alexei Starovoitov]

On Sat Oct 24, 2026 at 6:57 AM UTC, Eduard Zingerman wrote:
> On Sat, 2026-10-24 at 00:41 +0000, bot+bpf-ci@kernel.org wrote:
>
> ...
>
>> Since bisection can land on this commit, could that change be folded into
>> this patch or ordered before it?
>
> Commits should remain separate for documentation purposes.
> Full test suite passes on both.
>
>> A related question about the end of the series.  cf18840bc068 only helps
>> when the current frame has no active loop.  Consider states inside an inner
>> loop that is entered again on the second iteration of a terminating outer
>> loop.  current_loop() finds the inner loop in both states, but its
>> entry_state differs, because handle_loop_entry_exit() splits a new one on
>> each entry.  So the EXACT check runs, and loop_stack_safe() does not
>> compare entry_state.
>> 
>> With the outer induction variable now the same on every outer iteration, a
>> program like the one below looks like it would still hit "infinite loop
>> detected" after cf18840bc068 (with the old code the outer induction
>> variable was [1..9] on the second outer iteration and the EXACT compare
>> failed):
>> 
>>     w1 = 1;
>>     *(u32 *)(r10 - 8) = r1;
>>     r6 = 0;
>> 1:  r7 = 0;
>> 2:  *(u32 *)(r10 - 4) = 1;   /* fp-8 spill -> STACK_MISC */
>>     r7 += 1;
>>     if r7 < 3 goto 2b;
>>     r6 += 1;
>>     if r6 < 10 goto 1b;
>>     r0 = *(u32 *)(r10 - 8);
>>     exit;
>> 
>> Is that case covered somewhere I missed?
>
> This example is valid. Need to relax the condition in the
> current_loop() or bpf_is_state_visited().

so you're going to respin it or follow up?

It's fine to ignore CI in patch 3.
We'll be removing states.c soon.

Re: [PATCH bpf-next 02/11] bpf: do not intersect with current register range on clamp

[Alexei Starovoitov]

On Sat, Oct 24, 2026 at 6:03 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Sat Oct 24, 2026 at 6:57 AM UTC, Eduard Zingerman wrote:
> > On Sat, 2026-10-24 at 00:41 +0000, bot+bpf-ci@kernel.org wrote:
> >
> > ...
> >
> >> Since bisection can land on this commit, could that change be folded into
> >> this patch or ordered before it?
> >
> > Commits should remain separate for documentation purposes.
> > Full test suite passes on both.
> >
> >> A related question about the end of the series.  cf18840bc068 only helps
> >> when the current frame has no active loop.  Consider states inside an inner
> >> loop that is entered again on the second iteration of a terminating outer
> >> loop.  current_loop() finds the inner loop in both states, but its
> >> entry_state differs, because handle_loop_entry_exit() splits a new one on
> >> each entry.  So the EXACT check runs, and loop_stack_safe() does not
> >> compare entry_state.
> >>
> >> With the outer induction variable now the same on every outer iteration, a
> >> program like the one below looks like it would still hit "infinite loop
> >> detected" after cf18840bc068 (with the old code the outer induction
> >> variable was [1..9] on the second outer iteration and the EXACT compare
> >> failed):
> >>
> >>     w1 = 1;
> >>     *(u32 *)(r10 - 8) = r1;
> >>     r6 = 0;
> >> 1:  r7 = 0;
> >> 2:  *(u32 *)(r10 - 4) = 1;   /* fp-8 spill -> STACK_MISC */
> >>     r7 += 1;
> >>     if r7 < 3 goto 2b;
> >>     r6 += 1;
> >>     if r6 < 10 goto 1b;
> >>     r0 = *(u32 *)(r10 - 8);
> >>     exit;
> >>
> >> Is that case covered somewhere I missed?
> >
> > This example is valid. Need to relax the condition in the
> > current_loop() or bpf_is_state_visited().
>
> so you're going to respin it or follow up?
>
> It's fine to ignore CI in patch 3.
> We'll be removing states.c soon.

respin. The better fix is probably:
-               bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
-               bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
-               if (cnum64_is_empty(bounds.r64)) {
-                       verifier_bug(env, "scev clamp produced empty
range for r%d", r);
-                       return -EFAULT;
+               r64 = cnum64_intersect(reg->r64, bounds.r64);
+               r32 = cnum32_intersect(reg->r32, bounds.r32);
+               /*
+                * The state at the head doesn't know how the
variables depend on each other.
+                * It lets r6 = 0, r7 = 9 into the loop when both
count from 0, and r7 = 10
+                * comes back. No run gets here like that, so any
range is right for r7.
+                * Take the one it has at the head: the rest of the
state is still compared
+                * with the head, and what was pruned on the way here
relies on that.
+                */
+               if (!cnum64_is_empty(r64) && !cnum32_is_empty(r32)) {
+                       bounds.r64 = r64;
+                       bounds.r32 = r32;

Re: [PATCH bpf-next 02/11] bpf: do not intersect with current register range on clamp

[Eduard Zingerman]

On Sat, 2026-10-24 at 22:10 -0700, Alexei Starovoitov wrote:
> On Sat, Oct 24, 2026 at 6:03 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Sat Oct 24, 2026 at 6:57 AM UTC, Eduard Zingerman wrote:
> > > On Sat, 2026-10-24 at 00:41 +0000, bot+bpf-ci@kernel.org wrote:
> > >
> > > ...
> > >
> > > > Since bisection can land on this commit, could that change be folded into
> > > > this patch or ordered before it?
> > >
> > > Commits should remain separate for documentation purposes.
> > > Full test suite passes on both.
> > >
> > > > A related question about the end of the series.  cf18840bc068 only helps
> > > > when the current frame has no active loop.  Consider states inside an inner
> > > > loop that is entered again on the second iteration of a terminating outer
> > > > loop.  current_loop() finds the inner loop in both states, but its
> > > > entry_state differs, because handle_loop_entry_exit() splits a new one on
> > > > each entry.  So the EXACT check runs, and loop_stack_safe() does not
> > > > compare entry_state.
> > > >
> > > > With the outer induction variable now the same on every outer iteration, a
> > > > program like the one below looks like it would still hit "infinite loop
> > > > detected" after cf18840bc068 (with the old code the outer induction
> > > > variable was [1..9] on the second outer iteration and the EXACT compare
> > > > failed):
> > > >
> > > >     w1 = 1;
> > > >     *(u32 *)(r10 - 8) = r1;
> > > >     r6 = 0;
> > > > 1:  r7 = 0;
> > > > 2:  *(u32 *)(r10 - 4) = 1;   /* fp-8 spill -> STACK_MISC */
> > > >     r7 += 1;
> > > >     if r7 < 3 goto 2b;
> > > >     r6 += 1;
> > > >     if r6 < 10 goto 1b;
> > > >     r0 = *(u32 *)(r10 - 8);
> > > >     exit;
> > > >
> > > > Is that case covered somewhere I missed?
> > >
> > > This example is valid. Need to relax the condition in the
> > > current_loop() or bpf_is_state_visited().
> >
> > so you're going to respin it or follow up?
> >
> > It's fine to ignore CI in patch 3.
> > We'll be removing states.c soon.
>
> respin. The better fix is probably:
> -               bounds.r64 = cnum64_intersect(reg->r64, bounds.r64);
> -               bounds.r32 = cnum32_intersect(reg->r32, bounds.r32);
> -               if (cnum64_is_empty(bounds.r64)) {
> -                       verifier_bug(env, "scev clamp produced empty
> range for r%d", r);
> -                       return -EFAULT;
> +               r64 = cnum64_intersect(reg->r64, bounds.r64);
> +               r32 = cnum32_intersect(reg->r32, bounds.r32);
> +               /*
> +                * The state at the head doesn't know how the
> variables depend on each other.
> +                * It lets r6 = 0, r7 = 9 into the loop when both
> count from 0, and r7 = 10
> +                * comes back. No run gets here like that, so any
> range is right for r7.
> +                * Take the one it has at the head: the rest of the
> state is still compared
> +                * with the head, and what was pruned on the way here
> relies on that.
> +                */
> +               if (!cnum64_is_empty(r64) && !cnum32_is_empty(r32)) {
> +                       bounds.r64 = r64;
> +                       bounds.r32 = r32;

Well, it's a minimal change, but I think it is still prone to
counter-examples. I'd still like to remove the clamping logic
altogether and adjust the bpf_is_state_visited() as follows:

--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1532,10 +1532,10 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
                         */
                        old_loop = current_loop(&sl->state);
                        cur_loop = current_loop(cur);
-                       if (old_loop && cur_loop &&
-                           old_loop->terminates && cur_loop->terminates &&
-                           old_loop->entry_state == cur_loop->entry_state) {
-                               if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
+                       if (old_loop && cur_loop) {
+                               if (old_loop->terminates && cur_loop->terminates &&
+                                   old_loop->entry_state == cur_loop->entry_state &&
+                                   states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
                                        loop = true;
                                        goto hit;
                                }

Because of the `goto skip_inf_loop_check` check immediately after that
it would avoid the whole set of such problems. (And will be in the
same line as iterators).

An alternative, if we want to preserve clamping (but I see no reason to),
would be an additional check in check_cond_jmp_op(),
when jump prediction is done. There, for a latch condition,
a call to scev.c can be made, checking if induction variables would
have an empty range.

[PATCH bpf-next 03/11] bpf: look for current loop in upper frames in states_equal()

[Eduard Zingerman]

When checking if current loop exploration terminates, look for active
loops in upper frames as well. E.g. for the following program:

  int main(...) {
    for (int i = 0; i < 10; i++) {
      ...
      foo(...);
      ...
    }
  }

  void foo(...) {
    ...
  }

Checkpoints created inside foo() now count as loop checkpoints,
plus states.c:bpf_is_state_visited() does skip_inf_loop_check
for states inside foo().

Doing skip_inf_loop_check is necessary after the previous patch:
- Clamping now reproduces the widened range at every back edge.
- Meaning that induction variable ranges no longer vary between
  iterations.
- So a loop calling a subprogram can reach a callee state identical
  to the one from a previous iteration.
- Hence for states inside a callee an infinite loop check in
  states.c:bpf_is_state_visited() might report:

    infinite loop detected at insn 12

See selftest clamp_callee_state_pruning introduced later in this
series.

Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/states.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index d7df6632a5c4..306ad208a8e4 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c
@@ -1361,10 +1361,14 @@ static bool need_loop_checkpoint(struct bpf_verifier_env *env, int insn_idx)
 static struct loop_stack_entry *current_loop(struct bpf_verifier_state *st)
 {
 	struct bpf_func_state *frame = st->frame[st->curframe];
+	int fr;
 
-	if (frame->loop_stack_cnt == 0)
-		return NULL;
-	return &frame->loop_stack[frame->loop_stack_cnt - 1];
+	for (fr = st->curframe; fr >= 0; fr--) {
+		frame = st->frame[fr];
+		if (frame->loop_stack_cnt)
+			return &frame->loop_stack[frame->loop_stack_cnt - 1];
+	}
+	return NULL;
 }
 
 int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)

-- 
2.53.0

Re: [PATCH bpf-next 03/11] bpf: look for current loop in upper frames in states_equal()

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: current_loop() ignores outer loops when inner loop is re-entered
--

commit 999e70b9b80c780cef9257c5cc41cf3820aa644f
Author: Eduard Zingerman <eddyz87@gmail.com>

bpf: look for current loop in upper frames in states_equal()

This commit updates current_loop() to search upper call frames for an active
loop entry when checking if the current loop exploration terminates in
bpf_is_state_visited(). This allows checkpoints inside callees invoked from a
bounded loop to be pruned and to skip false-positive infinite loop checks.

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index d7df6632a5c47..306ad208a8e41 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
> @@ -1361,10 +1361,14 @@ static bool need_loop_checkpoint(struct bpf_verifier_env *env, int insn_idx)
>  static struct loop_stack_entry *current_loop(struct bpf_verifier_state *st)
>  {
>  	struct bpf_func_state *frame = st->frame[st->curframe];
> +	int fr;
>  
> -	if (frame->loop_stack_cnt == 0)
> -		return NULL;
> -	return &frame->loop_stack[frame->loop_stack_cnt - 1];
> +	for (fr = st->curframe; fr >= 0; fr--) {
> +		frame = st->frame[fr];
> +		if (frame->loop_stack_cnt)
> +			return &frame->loop_stack[frame->loop_stack_cnt - 1];
> +	}

[Severity: Medium]
What happens if a terminating outer loop enters a terminating inner loop
(either in a callee or nested in the same function) on a subsequent outer
iteration without having been pruned at the outer loop header?

On each fresh entry into the inner loop, handle_loop_entry_exit() allocates a
new entry_state via bpf_split_cur_state():

kernel/bpf/verifier.c:handle_loop_entry_exit() {
	...
	/* Create a loop_entry checkpoint before widening */
	err = bpf_split_cur_state(env);
	if (err)
		return err;

	entry->min_header_count = iters.min_header_count;
	entry->max_header_count = iters.max_header_count;
	entry->entry_state = cur->parent;
	entry->terminates = true;
	...
}

When the outer loop takes its backedge into a second iteration (for example,
when a 32-bit stack spill becomes STACK_MISC during iteration 1 so the outer
header does not immediately prune) and re-enters the inner loop, the inner
loop receives a distinct entry_state from the one recorded in the first outer
iteration's checkpoint.

Because current_loop() unconditionally returns the innermost active loop entry,
bpf_is_state_visited() only compares the inner loop's entry_state pointers:

kernel/bpf/states.c:bpf_is_state_visited() {
	...
	old_loop = current_loop(&sl->state);
	cur_loop = current_loop(cur);
	if (old_loop && cur_loop &&
	    old_loop->terminates && cur_loop->terminates &&
	    old_loop->entry_state == cur_loop->entry_state) {
		if (states_equal(env, &sl->state, cur, RANGE_WITHIN)) {
			loop = true;
			goto hit;
		}
		goto skip_inf_loop_check;
	}
	...
}

Since old_loop->entry_state != cur_loop->entry_state for the re-entered inner
loop, this check fails without noticing that an enclosing terminating loop in
the same or upper frame still has a matching entry_state.

Execution then falls through to the infinite loop check, where
loop_stack_safe() does not compare entry_state:

kernel/bpf/states.c:loop_stack_safe() {
	...
	for (i = 0; i < old->loop_stack_cnt; i++) {
		if (old_stack[i].loop_id == cur_stack[i].loop_id &&
		    old_stack[i].max_header_count == cur_stack[i].max_header_count &&
		    old_stack[i].terminates == cur_stack[i].terminates)
			continue;
		return false;
	}
	...
}

Won't states_maybe_looping() and states_equal(env, &sl->state, cur, EXACT)
then match the inner loop checkpoint from the previous outer iteration and
falsely reject the program with an infinite loop error?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261023-scev-simpler-clamp-v1-0-d43a07eda7af@gmail.com?part=3

Re: [PATCH bpf-next 03/11] bpf: look for current loop in upper frames in states_equal()

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 6057 bytes --]

> bpf: look for current loop in upper frames in states_equal()

TL;DR:
- Possible false "infinite loop detected" rejection of terminating programs
  when a callee has its own loop; current_loop() stops at the callee's loop
- Subject and commit message imprecise

>     bpf: look for current loop in upper frames in states_equal()
>
>     When checking if current loop exploration terminates, look for active
>     loops in upper frames as well. E.g. for the following program:
>       int main(...) {
>         for (int i = 0; i < 10; i++) {
>           ...
>           foo(...);
>           ...
>         }
>       }
>       void foo(...) {
>         ...
>       }
>     Checkpoints created inside foo() now count as loop checkpoints,
>     plus states.c:bpf_is_state_visited() does skip_inf_loop_check
>     for states inside foo().
>     Doing skip_inf_loop_check is necessary after the previous patch:
>     - Clamping now reproduces the widened range at every back edge.
>     - Meaning that induction variable ranges no longer vary between
>       iterations.
>     - So a loop calling a subprogram can reach a callee state identical
>       to the one from a previous iteration.
>     - Hence for states inside a callee an infinite loop check in
>       states.c:bpf_is_state_visited() might report:
>         infinite loop detected at insn 12
>     See selftest clamp_callee_state_pruning introduced later in this
>     series.
>     Fixes: 6ccf49f79327 ("bpf: Use SCEV to widen bounded loops")
>     Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>

The subject says the lookup changes "in states_equal()", but states_equal()
is not modified by this patch and does not call current_loop(). The only
caller of current_loop() is bpf_is_state_visited().

The body says "Checkpoints created inside foo() now count as loop
checkpoints", which could be read as referring to the loop_checkpoint flag
from need_loop_checkpoint(). That function still only looks at
cur->frame[cur->curframe], so callee checkpoints still don't get
force_new_state or the n = 64 eviction threshold. What changes is that they
now take the RANGE_WITHIN / skip_inf_loop_check path in
bpf_is_state_visited().

Could the subject name bpf_is_state_visited() (or current_loop()), and could
the body be more precise about what changes for callee checkpoints?

> diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
> index d7df6632a5c4..306ad208a8e4 100644
> --- a/kernel/bpf/states.c
> +++ b/kernel/bpf/states.c
> @@ -1361,10 +1361,14 @@ static bool need_loop_checkpoint(struct bpf_verifier_env *env, int insn_idx)
>  static struct loop_stack_entry *current_loop(struct bpf_verifier_state *st)
>  {
>  	struct bpf_func_state *frame = st->frame[st->curframe];
> +	int fr;
>
> -	if (frame->loop_stack_cnt == 0)
> -		return NULL;
> -	return &frame->loop_stack[frame->loop_stack_cnt - 1];
> +	for (fr = st->curframe; fr >= 0; fr--) {
> +		frame = st->frame[fr];
> +		if (frame->loop_stack_cnt)
> +			return &frame->loop_stack[frame->loop_stack_cnt - 1];
> +	}
> +	return NULL;
>  }

Does this cover a callee that has an active loop of its own?

current_loop() stops at the first frame with a non-empty loop_stack. If the
callee is inside its own terminating loop, the callee's loop is returned
instead of the caller's loop.

That callee loop is re-entered on every iteration of the caller's loop, and
each entry gets a new entry_state (handle_loop_entry_exit() sets
entry->entry_state = cur->parent after bpf_split_cur_state()). The check in
bpf_is_state_visited():

    if (old_loop && cur_loop &&
        old_loop->terminates && cur_loop->terminates &&
        old_loop->entry_state == cur_loop->entry_state) {

therefore fails across caller iterations, and those states fall through to
the exact-match infinite-loop check. That looks like the same false positive
the commit message describes.

For example, take the clamp_callee_state_pruning selftest added later in the
series, with the callee body wrapped in its own bounded loop:

    caller: slot = 32-bit spill;
            for (r6 = 0; r6 < 10; r6++) callee(&slot);
    callee: for (r7 = 0; r7 < 5; r7++) {
                slot[1] = 1;
                bpf_get_prandom_u32();  /* P */
            }

In the first invocation, P gets a checkpoint S_P(1) after the scrub. The
caller loop header and every callee point before the scrub still hold the
spill. On the caller backedge r6 is clamped to 0..9, the same range as the
first widening, but the slot is now STACK_MISC, so the header does not
match. With this patch the pre-scrub callee points do not match either
(spill vs STACK_MISC under RANGE_WITHIN).

In the second invocation the callee loop is entered again with a new
entry_state, r7 is widened to the same 0..4 with id 0
(scratch_widened_reg_id()), and the slot is already STACK_MISC. At P,
S_P(1) still has branches > 0 because the second invocation descends from
it. current_loop() returns the callee loop for both states, with different
entry_states.

states_maybe_looping() memcmp() up to step passes, and the exact
states_equal() passes too: frame 0 r6 is 0..9 in both, the stack is
STACK_MISC in both, and loop_stack_safe() compares only loop_id,
max_header_count and terminates. The result is "infinite loop detected at
insn P" for a program that terminates.

Should current_loop(), or its caller in bpf_is_state_visited(), also take a
terminating loop in an upper frame (or an enclosing loop) with a matching
entry_state into account when the innermost loop entries differ? The same
pattern also appears with nested loops within a single frame.

This is a remaining false rejection rather than a safety problem, coming
from the clamping change in 3a3d77b09ac6 that this patch only partly
addresses. No later patch in the series appears to touch
kernel/bpf/states.c.


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/40044354980

[PATCH bpf-next 04/11] bpf: check the iteration count before the predicted exit value

[Eduard Zingerman]

The comment before `total_change` computation:

    /*
     * compute_backedge_taken_count() guarantees that 'total_change'
     * does not overflow in 64-bit domain.
     */
    total_change = initial + step * backedge_taken_count;

Is not true before the check:

    if (backedge_taken_count >= U32_MAX - 1)
        return false;

Move the check before `total_change` computation in order to reconcile
the code with comments. Old position is not a bug the check was
performed either way.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/scev.c | 19 ++++++++-----------
 1 file changed, 8 insertions(+), 11 deletions(-)

diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index d67e793d7a18..e3c2220f89c9 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -2307,11 +2307,15 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 	if (!compute_backedge_taken_count(op, initial, step, bound, &backedge_taken_count))
 		return false;
 
+	/*
+	 * max_header_count is u32 and U32_MAX means "infinite",
+	 * check to avoid overflow below.
+	 */
+	if (backedge_taken_count >= U32_MAX - 1)
+		return false;
+
 	if (latch->zext32 || latch->jmp32) {
-		/*
-		 * compute_backedge_taken_count() guarantees that 'total_change'
-		 * does not overflow in 64-bit domain.
-		 */
+		/* total_change is guaranteed not to overflow at this point */
 		total_change = initial + step * backedge_taken_count;
 		if (latch->jmp32 && is_signed_op(op)) {
 			if ((s64)total_change < S32_MIN || (s64)total_change > S32_MAX)
@@ -2322,13 +2326,6 @@ static bool compute_max_iters(struct bpf_verifier_env *env,
 		}
 	}
 
-	/*
-	 * max_header_count is u32 and U32_MAX means "infinite",
-	 * check to avoid overflow below.
-	 */
-	if (backedge_taken_count >= U32_MAX - 1)
-		return false;
-
 	/* The header executes once on entry and once for each taken backedge, hence +1. */
 	iters->max_header_count = backedge_taken_count + 1;
 	/*

-- 
2.53.0

[PATCH bpf-next 05/11] bpf: (zext32 (zext32 X)) -> (zext32 X) SCEV simplification rule

[Eduard Zingerman]

The compiler can preserve an induction variable across a call by
copying it to a callee-saved register. For example:

        w1 = 0;
loop:
        w7 = w1;
        call foo;
        w1 = w7;
        w1 += 2;
        if w7 < 10 goto loop;

When building expressions for the loop body, each 32-bit move adds a
zero extension:

        w7 = w1;    r7 = (zext32 r1)
        w1 = w7;    r1 = (zext32 (zext32 r1))
        w1 += 2;    r1 = (zext32 (+ (zext32 (zext32 r1)) 2))

The existing ALU32 simplification rules allow recognizing the header
SCEV for r1 as:

        (zext32 (linear r1 2))

Substituting this SCEV into r7's expression at the latch produces:

        (zext32 (zext32 (linear r1 2)))

Add the simplification rule:

        (zext32 (zext32 X)) -> (zext32 X)

This allows recognizing the saved induction variable in r7 as a
32-bit linear SCEV and computing the loop iteration bound.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/scev.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index e3c2220f89c9..12b147faa32a 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -1502,6 +1502,10 @@ static int simplify(struct scev *scev, u32 id, void *priv)
 		return t;
 	}
 
+	/* (zext32 (zext32 X)) -> (zext32 X) */
+	if (is_zext32(scev, id, &a) && is_zext32(scev, a, &b))
+		return a;
+
 	return id;
 }
 

-- 
2.53.0

[PATCH bpf-next 06/11] bpf: print 32-bit SCEV bounds as 32-bit numbers

[Eduard Zingerman]

bpf: Simplify printing of SCEV bounds

- Print large 32-bit bounds without sign extension.
- Omit 32-bit bounds when they coincide with 64-bit bounds.

Before:
  loop header at ..., widening r0 to 0x80000000..0xffffffff (s32 0xffffffff80000000..-1) step 1
  loop header at ..., widening r0 to 0..3 (s32 0..3) step 1

After:
  loop header at ..., widening r0 to 0x80000000..0xffffffff (s32 0x80000000..-1) step 1
  loop header at ..., widening r0 to 0..3 step 1

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h                      | 1 +
 kernel/bpf/log.c                                  | 8 ++++++++
 kernel/bpf/scev.c                                 | 8 +++++---
 tools/testing/selftests/bpf/progs/verifier_scev.c | 2 +-
 4 files changed, 15 insertions(+), 4 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 5926f13ff43c..e51984cb3035 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1280,6 +1280,7 @@ __printf(3, 4) void verbose_linfo(struct bpf_verifier_env *env,
 				  u32 insn_off,
 				  const char *prefix_fmt, ...);
 void bpf_verbose_snum(struct bpf_verifier_env *env, s64 num);
+void bpf_verbose_snum32(struct bpf_verifier_env *env, s32 num);
 
 #define verifier_bug_if(cond, env, fmt, args...)						\
 	({											\
diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
index 5432c0fc442b..fa29d9b994e4 100644
--- a/kernel/bpf/log.c
+++ b/kernel/bpf/log.c
@@ -535,6 +535,14 @@ void bpf_verbose_snum(struct bpf_verifier_env *env, s64 num)
 		verbose(env, "%#llx", num);
 }
 
+void bpf_verbose_snum32(struct bpf_verifier_env *env, s32 num)
+{
+	if (is_snum_decimal(num))
+		verbose(env, "%d", num);
+	else
+		verbose(env, "%#x", (u32)num);
+}
+
 int tnum_strn(char *str, size_t size, struct tnum a)
 {
 	/* print as a constant, if tnum is fully known */
diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c
index 12b147faa32a..04d4962448e2 100644
--- a/kernel/bpf/scev.c
+++ b/kernel/bpf/scev.c
@@ -2456,11 +2456,13 @@ static void log_bounds(struct bpf_verifier_env *env, const struct bounds *bounds
 	bpf_verbose_snum(env, cnum64_smin(bounds->r64));
 	bpf_log(log, "..");
 	bpf_verbose_snum(env, cnum64_smax(bounds->r64));
-	if (bounds->r32.size < U32_MAX) {
+	if (bounds->r32.size < U32_MAX &&
+	    (cnum32_smin(bounds->r32) != cnum64_smin(bounds->r64) ||
+	     cnum32_smax(bounds->r32) != cnum64_smax(bounds->r64))) {
 		bpf_log(log, " (s32 ");
-		bpf_verbose_snum(env, cnum32_smin(bounds->r32));
+		bpf_verbose_snum32(env, cnum32_smin(bounds->r32));
 		bpf_log(log, "..");
-		bpf_verbose_snum(env, cnum32_smax(bounds->r32));
+		bpf_verbose_snum32(env, cnum32_smax(bounds->r32));
 		bpf_log(log, ")");
 	}
 	bpf_log(log, " step %u", bounds->step);
diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 14594ba5dbfd..96c98443f346 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -1771,7 +1771,7 @@ __success
 __log_level(2)
 __flag(BPF_F_TEST_STATE_FREQ)
 __msg("loop header at 1, header_count is 4")
-__msg("loop header at 1, widening r0 to 0..3 (s32 0..3) step 1")
+__msg("loop header at 1, widening r0 to 0..3 step 1")
 __msg("loop header at 1, clamping r0")
 __msg("4: R0=3")
 __naked void pre_cond_je32(void)

-- 
2.53.0

Re: [PATCH bpf-next 06/11] bpf: print 32-bit SCEV bounds as 32-bit numbers

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1343 bytes --]

> bpf: print 32-bit SCEV bounds as 32-bit numbers

TL;DR: Commit message only: a stray second subject line, "bpf: Simplify
printing of SCEV bounds", at the top of the body looks unintended and could
probably be dropped. Not a bug.

>     bpf: print 32-bit SCEV bounds as 32-bit numbers
>
>     bpf: Simplify printing of SCEV bounds
>
>     - Print large 32-bit bounds without sign extension.
>     - Omit 32-bit bounds when they coincide with 64-bit bounds.
>
>     Before:
>       loop header at ..., widening r0 to 0x80000000..0xffffffff (s32 0xffffffff80000000..-1) step 1
>       loop header at ..., widening r0 to 0..3 (s32 0..3) step 1
>
>     After:
>       loop header at ..., widening r0 to 0x80000000..0xffffffff (s32 0x80000000..-1) step 1
>       loop header at ..., widening r0 to 0..3 step 1
>
>     Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>

This isn't a bug, but is the line "bpf: Simplify printing of SCEV bounds" at
the top of the commit message body meant to be there?  It reads like a second
subject line that differs from the real subject, and could probably be
dropped.


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/40044354980

[PATCH bpf-next 07/11] selftests/bpf: pointer operands for 32-bit recurrences/latches

[Eduard Zingerman]

Add four tests for pointer operands in 32-bit SCEV analysis.
Check that loop bounds are not inferred for the following program shapes:

     32-bit latch          |    32-bit recurrence
  -------------------------+--------------------------
     r6 = ... pointer ...  |    r6 = ... pointer ...
     r7 = ... pointer ...  |    r7 = ... pointer ...
  l: r6 += 1               | l: w6 += 1
     ...                   |    ...
     if w6 < w7 goto l     |    if r6 < r7 goto l

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/verifier_scev.c | 109 ++++++++++++++++++++++
 1 file changed, 109 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 96c98443f346..8eeb4d73da98 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -2971,6 +2971,115 @@ __naked void ptr_stack_other_frame(void)
 "	::: __clobber_all);
 }
 
+SEC("xdp")
+__success
+__log_level(2)
+__msg("scev: incompatible latch operands r6 (map_value), r7 (map_value)")
+__msg("loop header at 11, can't compute iterations count at 14")
+__naked void ptr_map_value_jmp32(void)
+{
+	asm volatile ("					\
+	*(u64 *)(r10 - 8) = 0;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map] ll;					\
+	call %[bpf_map_lookup_elem];			\
+	if r0 == 0 goto 2f;				\
+	r6 = r0;					\
+	r7 = r6;					\
+	r7 += 4;					\
+	r9 = 0;						\
+1:"	LIMIT_ITERATIONS				\
+"	r6 += 1;					\
+	if w6 < w7 goto 1b;				\
+2:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map)
+	: __clobber_all);
+}
+
+SEC("xdp")
+__failure
+__log_level(2)
+__msg("loop header at 11, can't compute iterations count")
+__msg("R6 32-bit pointer arithmetic prohibited")
+__naked void ptr_map_value_alu32_latch(void)
+{
+	asm volatile ("					\
+	*(u64 *)(r10 - 8) = 0;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map] ll;					\
+	call %[bpf_map_lookup_elem];			\
+	if r0 == 0 goto 2f;				\
+	r6 = r0;					\
+	r7 = r6;					\
+	r7 += 4;					\
+	r9 = 0;						\
+1:"	LIMIT_ITERATIONS				\
+"	w6 += 1;					\
+	if r6 < r7 goto 1b;				\
+2:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map)
+	: __clobber_all);
+}
+
+SEC("xdp")
+__success
+__log_level(2)
+__msg("loop header at 11, can't compute iterations count")
+__naked void ptr_map_value_alu32_latch2(void)
+{
+	asm volatile ("					\
+	*(u64 *)(r10 - 8) = 0;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map] ll;					\
+	call %[bpf_map_lookup_elem];			\
+	if r0 == 0 goto 2f;				\
+	r6 = r0;					\
+	r7 = r6;					\
+	r7 += 4;					\
+	r9 = 0;						\
+1:"	LIMIT_ITERATIONS				\
+"	r6 += 1;					\
+	w8 = w6;					\
+	if r8 < r7 goto 1b;				\
+2:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map)
+	: __clobber_all);
+}
+
+SEC("xdp")
+__success
+__log_level(2)
+__msg("loop header at 8, can't widen r0, expr is (zext32 (+ r0 1))")
+__naked void ptr_map_value_alu32_non_latch(void)
+{
+	asm volatile ("					\
+	*(u64 *)(r10 - 8) = 0;				\
+	r2 = r10;					\
+	r2 += -8;					\
+	r1 = %[map] ll;					\
+	call %[bpf_map_lookup_elem];			\
+	if r0 == 0 goto 2f;				\
+	r1 = 0;						\
+1:	r1 += 1;					\
+	w0 = w0;					\
+	w0 += 1;					\
+	if r1 < 4 goto 1b;				\
+2:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem), __imm_addr(map)
+	: __clobber_all);
+}
+
 /* Metadata and packet data have different origins. */
 SEC("xdp")
 __success

-- 
2.53.0

[PATCH bpf-next 08/11] selftests/bpf: cases with empty range error under old clamping logic

[Eduard Zingerman]

A 64-bit and 32-bit examples leading to an empty register range error
when scev.c:bpf_clamp_scev_regs() intersected current register state
with computed iteration range:

        r1 = 0;           verification
        r3 = 0;               path
  loop:   r3 += 1;              | <---------.
          if r3 != 5 goto +0;   | r3 ∈ {5}  |
          r1 += 1;              |           |
          if r1 != 5 goto loop; '-----------'
        r0 = 0;
        exit;

- At header r3 ∈ {0,1,2,3,4}.
- After `if r3 != 5 goto ...` continued with r3 ∈ {5}.
- On a second iteration bpf_clamp_scev_regs() computed:

    r3 := {0,1,2,3,4} ∩ {5} = ∅

  And reported an error:

    verifier bug: scev clamp produced empty range for r3

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/verifier_scev.c | 55 +++++++++++++++++++++++
 1 file changed, 55 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 8eeb4d73da98..213a2b6a5027 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -1604,6 +1604,61 @@ __naked void post_cond_jne_neg_step(void)
 "	::: __clobber_all);
 }
 
+/*
+ * r1 and r3 are widened independently, so the r3 == 5 path reaches the back
+ * edge with r3 past the last value it takes at the header.
+ */
+SEC("socket")
+__success
+__log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("loop header at 2, header_count is 5 ")
+__msg("loop header at 2, widening r1 to 0..4 step 1")
+__msg("loop header at 2, widening r3 to 0..4 step 1")
+__msg("3: (55) if r3 != 0x5 goto pc+1 {{.*}}; R3=5")
+__msg("loop header at 2, clamping r3 to 0..4 step 1")
+__msg("from 6 to 2: safe")
+__naked void clamp_dependent_overshoot(void)
+{
+	asm volatile ("					\
+	r1 = 0;						\
+	r3 = 0;						\
+1:	r3 += 1;					\
+	if r3 != 5 goto 2f;				\
+	r2 = 0;						\
+2:	r1 += 1;					\
+	if r1 != 5 goto 1b;				\
+	r0 = 0;						\
+	exit;						\
+"	::: __clobber_all);
+}
+
+/* Same with a 32-bit dependent register, SCEV (zext32 (linear r3 1)) */
+SEC("socket")
+__success
+__log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("loop header at 2, header_count is 5 ")
+__msg("loop header at 2, widening r1 to 0..4 step 1")
+__msg("loop header at 2, widening r3 to 0..4 step 1")
+__msg("3: (56) if w3 != 0x5 goto pc+1 {{.*}}; R3=5")
+__msg("loop header at 2, clamping r3 to 0..4 step 1")
+__msg("from 6 to 2: safe")
+__naked void clamp_dependent_overshoot32(void)
+{
+	asm volatile ("					\
+	r1 = 0;						\
+	w3 = 0;						\
+1:	w3 += 1;					\
+	if w3 != 5 goto 2f;				\
+	r2 = 0;						\
+2:	r1 += 1;					\
+	if r1 != 5 goto 1b;				\
+	r0 = 0;						\
+	exit;						\
+"	::: __clobber_all);
+}
+
 SEC("xdp")
 __success
 __log_level(2)

-- 
2.53.0

[PATCH bpf-next 09/11] selftests/bpf: case reporting infinite loop w/o current_loop() changes

[Eduard Zingerman]

Add a test equivalent to the following pseudo-code:

  void scrub_slot_callee(u32 *slot)
  {
          slot[1] = 1;        /* turn the caller's spill into STACK_MISC */
          ... checkpoint on first iteration ...
  }

  int caller(void)
  {
          u32 slot[2];

          slot[0] = 1;        /* 32-bit spill */
          for (int i = 0; i < 10; i++) {
                  scrub_slot_callee(slot);
          }
          return slot[0];
  }

Verification proceeds as follows:
- First iteration: the stack slot is a spill at the call site and
  STACK_MISC at the callee's return.
- Backedge: the counter is clamped to 0..9, but the stack slot is now
  STACK_MISC, so the state does not match the header checkpoint.
- Second iteration: the stack difference prevents a match at the call
  site, but the states match exactly at the callee's return.
- The callee frame has no active loop. If current_loop() checks only
  that frame, bpf_is_state_visited() reports an infinite loop.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/verifier_scev.c | 40 +++++++++++++++++++++++
 1 file changed, 40 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 213a2b6a5027..078803e71197 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -2567,6 +2567,46 @@ __naked void no_widen_any_stack_origin(void)
 "	::: __clobber_all);
 }
 
+__naked __noinline __used static int scrub_slot_callee(void)
+{
+	asm volatile ("					\
+	*(u32 *)(r1 + 4) = 1;				\
+	call %[bpf_get_prandom_u32];			\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+/*
+ * The callee turns the caller's fp-8 into misc, so the states at the call site
+ * differ between the first and the second iteration, while the states inside
+ * the callee are identical. Verification fails with an infinite loop error if
+ * states.c:current_loop() does not search upper frames for active loops.
+ */
+SEC("socket")
+__success
+__log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg("loop header at 3, widening r6 to 0..9 step 1")
+__msg("loop header at 3, clamping r6 to 0..9 step 1")
+__msg("12: safe")
+__naked void clamp_callee_state_pruning(void)
+{
+	asm volatile ("					\
+	w1 = 1;						\
+	*(u32 *)(r10 - 8) = r1;				\
+	r6 = 0;						\
+1:	r1 = r10;					\
+	r1 += -8;					\
+	call scrub_slot_callee;				\
+	r6 += 1;					\
+	if r6 < 10 goto 1b;				\
+	r0 = *(u32 *)(r10 - 8);				\
+	exit;						\
+"	::: __clobber_all);
+}
+
 /*
  * r7 starts as 1 + 6*k and invariant r8 as 1 + 9*k (0 <= k <= 3).
  * The (any r7 r8) union must preserve base 1 and step gcd(6, 9) = 3.

-- 
2.53.0

[PATCH bpf-next 10/11] selftests/bpf: 32-bit copy of the counter compared at the latch

[Eduard Zingerman]

When building SCEV expressions for the loop:

  w7 = w1;    r7 = (zext32 r1)
  w1 = w7;    r1 = (zext32 (zext32 r1))
  w1 += 2;    r1 = (zext32 (+ (zext32 (zext32 r1)) 2))

Computed SCEV expression for r1:

  (zext32 (linear r1 2))

Substituting this into r7's expression at the latch:

  (zext32 (zext32 (linear r1 2)))

Without (zext32 (zext32 X)) -> (zext32 X) simplification rule
the latch would not be recognized as linear and head_count
won't be computed.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/verifier_scev.c | 27 +++++++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c
index 078803e71197..bbc25da41018 100644
--- a/tools/testing/selftests/bpf/progs/verifier_scev.c
+++ b/tools/testing/selftests/bpf/progs/verifier_scev.c
@@ -3652,4 +3652,31 @@ __naked void dominating_exit_bounds_count(void)
 "	::: __clobber_all);
 }
 
+/*
+ * The counter is copied to a callee-saved register for the call and the copy is compared.
+ */
+SEC("xdp")
+__success
+__log_level(2)
+__flag(BPF_F_TEST_STATE_FREQ)
+__msg(" scev at latch 5:")
+__msg("  r7=(zext32 r1) / (zext32 (linear r1 2))")
+__msg("loop header at 1, header_count is 100 ")
+__msg("loop header at 1, widening r1 to 0..198 step 2")
+__naked void post_cond_jlt32_copy(void)
+{
+	asm volatile ("					\
+	w1 = 0;						\
+1:	w7 = w1;					\
+	call %[bpf_get_prandom_u32];			\
+	w1 = w7;					\
+	w1 += 2;					\
+	if w7 < 198 goto 1b;				\
+	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";

-- 
2.53.0

[PATCH bpf-next 11/11] selftests/bpf: Restore stack pointer subrange pruning coverage

[Eduard Zingerman]

After the clamping changes, r7 returns to the header with [-72, -16]
instead of the narrower [-64, -16], so the test no longer checks subrange
pruning. Assign an invariant fp-16 pointer to r7 in the loop, giving r7 an
ANY SCEV that is not clamped and restoring strict-subrange coverage.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../selftests/bpf/progs/verifier_stack_ptr.c       | 27 +++++++++++++---------
 1 file changed, 16 insertions(+), 11 deletions(-)

diff --git a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
index dc176f407c36..e6a9021b197b 100644
--- a/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
+++ b/tools/testing/selftests/bpf/progs/verifier_stack_ptr.c
@@ -588,32 +588,37 @@ __naked void stack_check_size_512_with_may_goto(void)
 
 /*
  * Verify that old PTR_TO_STACK state is considered a super-set of
- * new PTR_TO_STACK state when new variable range is a sub-range
- * of the old range, e.g. old [-72, -16] vs new [-64, -16].
+ * new PTR_TO_STACK state when the new offset is within the old range,
+ * e.g. old [-72, -16] vs new {-16}.
  */
 SEC("socket")
 __success
 __log_level(2)
 __flag(BPF_F_TEST_STATE_FREQ)
 /*
- * r7 is widened to [-72, -16] at the loop header (insn 3),
- * the loop body sees [-64, -8] after 'r7 += 8'
+ * r7 is widened to [-72, -16] at the loop header (insn 5),
+ * the loop body sees [-64, -8] after 'r7 += 8'.
  */
-__msg("loop header at 3, widening r7 to -72..-16 step 8")
+__msg("loop header at 5, widening r7 to -72..-16 step 1")
 __msg("R7=fp(smin=smin32=-64,smax=smax32=-8")
-/* back-edge state is clamped to the widened range and pruned at the header */
-__msg("loop header at 3, clamping r7 to -72..-16 step 8")
-__msg("from 5 to 3: safe")
-__msg("processed 9 insns")
+/* 'r7 = r8' sets r7 to fp-16; its ANY SCEV is not clamped. */
+__msg("R7=fp-16 R8=fp-16 loop_stack=5")
+__not_msg("clamping r7")
+/* back-edge state is pruned because {-16} is within [-72, -16]. */
+__msg("from 8 to 5: safe")
+__msg("processed 12 insns")
 __naked void stack_ptr_subrange_in_loop(void)
 {
 	asm volatile ("					\
 	r7 = r10;					\
 	r7 += -72;					\
+	r8 = r10;					\
+	r8 += -16;					\
 	r6 = 0;						\
-	r7 += 8;					\
+1:	r7 += 8;					\
+	r7 = r8;					\
 	r6 += 1;					\
-	if r6 < 8 goto -3;				\
+	if r6 < 8 goto 1b;				\
 	r0 = 0;						\
 	exit;						\
 "	::: __clobber_all);

-- 
2.53.0

Re: [PATCH bpf-next 00/11] bpf: fixes and follow-ups for 32-/64-bit scalar evolution

[Alexei Starovoitov]

On Fri, Oct 23, 2026 at 5:04 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Follow-ups:
> - bpf: (zext32 (zext32 X)) -> (zext32 X) SCEV simplification rule

Hit that as well. I'm going to send a patch for it asap.

Re: [PATCH bpf-next 00/11] bpf: fixes and follow-ups for 32-/64-bit scalar evolution

[Eduard Zingerman]

On Fri, 2026-10-23 at 22:11 -0700, Alexei Starovoitov wrote:
> On Fri, Oct 23, 2026 at 5:04 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > Follow-ups:
> > - bpf: (zext32 (zext32 X)) -> (zext32 X) SCEV simplification rule
> 
> Hit that as well. I'm going to send a patch for it asap.

It is a part of this patch-set:

  bpf: (zext32 (zext32 X)) -> (zext32 X) SCEV simplification rule
  selftests/bpf: 32-bit copy of the counter compared at the latch