[PATCH bpf-next v2 1/2] bpf: reject pointer operands for 32-bit recurrences/latches

[PATCH bpf-next v2 1/2] 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: df4761bd441c ("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.56.0

[PATCH bpf-next v2 2/2] 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>
---
 .../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 661ce9ca8f93..1d6b4839e197 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.56.0

Re: [PATCH bpf-next v2 1/2] bpf: reject pointer operands for 32-bit recurrences/latches

[Eduard Zingerman]

On Wed, 2026-10-21 at 11:56 -0700, Eduard Zingerman wrote:

Please let me know if this should target 'bpf' instead of 'bpf-next'
since 7.4 request was sent.

Re: [PATCH bpf-next v2 1/2] bpf: reject pointer operands for 32-bit recurrences/latches

[Alexei Starovoitov]

On Wed, Oct 21, 2026 at 11:56 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> Fixes: df4761bd441c ("bpf: Support 32-bit linear scalar evolution")

sorry, few commits were dropped from bpf-next.
It's 32e962577d2d now.

> +			/* 32-bit ALU operations on pointers convert them to scalars */
> +			if (coefs.zext32 && reg->type != SCALAR_VALUE)
> +				goto cant_widen;

le64 does the same without zext32.

     r7 = map_value, r1 = 0
  l: r7 = le64 r7
     if r7 < 100 goto out
     if r7 > 1000 goto out
     r7 += 8
     r1 += 1
     if r1 != 4 goto l

On little endian transfer() treats le64 as a nop, so r7 at the header
is (linear r7 8), while check_alu_op() makes it an unknown scalar.
At the backedge r7 is a scalar 108..1008 and bpf_clamp_scev_regs()
intersects it with 0..24, the offsets of map_value at the loop entry:
  verifier bug: scev clamp produced empty range for r7

Should bpf_clamp_scev_regs() skip the reg when
	entry_reg->type != reg->type
?

Re: [PATCH bpf-next v2 1/2] bpf: reject pointer operands for 32-bit recurrences/latches

[Eduard Zingerman]

On Wed, 2026-10-21 at 22:22 +0000, Alexei Starovoitov wrote:
> On Wed, Oct 21, 2026 at 11:56 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > Fixes: df4761bd441c ("bpf: Support 32-bit linear scalar evolution")
> 
> sorry, few commits were dropped from bpf-next.
> It's 32e962577d2d now.

Uh-oh.

> > +			/* 32-bit ALU operations on pointers convert them to scalars */
> > +			if (coefs.zext32 && reg->type != SCALAR_VALUE)
> > +				goto cant_widen;
> 
> le64 does the same without zext32.
> 
>      r7 = map_value, r1 = 0
>   l: r7 = le64 r7
>      if r7 < 100 goto out
>      if r7 > 1000 goto out
>      r7 += 8
>      r1 += 1
>      if r1 != 4 goto l
> 
> On little endian transfer() treats le64 as a nop, so r7 at the header
> is (linear r7 8), while check_alu_op() makes it an unknown scalar.
> At the backedge r7 is a scalar 108..1008 and bpf_clamp_scev_regs()
> intersects it with 0..24, the offsets of map_value at the loop entry:
>   verifier bug: scev clamp produced empty range for r7

I'm going to drop intersection from clamping, testing it now.

> Should bpf_clamp_scev_regs() skip the reg when
> 	entry_reg->type != reg->type
> ?

Not clamping would be bad, as the induction variable would get a range
outside of it's possible in-loop range on a backedge.
For this particular case, I think le64 should just stay a separate
expression, not a noop. E.g. during transfer() "r7 = (le64 r7)",
hence no SCEV would be computed for it.
I'll check if there are other operations that have similar effect.

My take is that this is a separate issue.
I can pack the fix with this patch as a patch-set, if you'd like that.

Re: [PATCH bpf-next v2 1/2] bpf: reject pointer operands for 32-bit recurrences/latches

[Eduard Zingerman]

On Wed, 2026-10-21 at 15:50 -0700, Eduard Zingerman wrote:
> On Wed, 2026-10-21 at 22:22 +0000, Alexei Starovoitov wrote:
> > On Wed, Oct 21, 2026 at 11:56 AM Eduard Zingerman <eddyz87@gmail.com> wrote:

...

> > le64 does the same without zext32.
> > 
> >      r7 = map_value, r1 = 0
> >   l: r7 = le64 r7
> >      if r7 < 100 goto out
> >      if r7 > 1000 goto out
> >      r7 += 8
> >      r1 += 1
> >      if r1 != 4 goto l
> > 
> > On little endian transfer() treats le64 as a nop, so r7 at the header
> > is (linear r7 8), while check_alu_op() makes it an unknown scalar.
> > At the backedge r7 is a scalar 108..1008 and bpf_clamp_scev_regs()
> > intersects it with 0..24, the offsets of map_value at the loop entry:
> >   verifier bug: scev clamp produced empty range for r7

Actually, I don't think there is anything to fix:
- check_alu_op() errors out if le64 is applied to a pointer.
- (linear r7 8) means that every path over the loop body
  is guaranteed to construct the linear equation.

Meaning that le64 would remain visible to the main verification pass
and would be rejected.

I'll re-spin these two patches as a part of bigger series with a
correct fixes tag but otherwise unchanged.