Skip to contentSkip to conversation

bpf: reject pointer operands for 32-bit recurrences/latches

PATCH In review Eduard Zingerman 2 participants 6 messages Oct 21 – Oct 23

Subsystems (3)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

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

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")
---
 kernel/bpf/scev.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)
kernel/bpf/scev.c +7 -3
index fea77772ca96..f9e2ca6a5a12 100644
@@ -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;
Signature · 1 line
2.56.0
author maintainer
#1 lore raw

PATCH v2 2/2 selftests/bpf: pointer operands for 32-bit recurrences/latches

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
---
 .../selftests/bpf/progs/verifier_scev.c       | 109 ++++++++++++++++++
 1 file changed, 109 insertions(+)
tools/testing/selftests/bpf/progs/verifier_scev.c +109 -0
index 661ce9ca8f93..1d6b4839e197 100644
@@ -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
Signature · 1 line
2.56.0
#3 lore raw
In reply to Eduard Zingerman
Quoted 1 line · Eduard Zingerman
Fixes df4761bd441c ("bpf: Support 32-bit linear scalar evolution")

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

kernel/bpf/scev.c int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta · line 2706

Quoted 3 lines
kernel/bpf/scev.c +3 -0
+			/* 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

?

author maintainer
#4 lore raw
Quoted 5 lines · Alexei Starovoitov
Quoted 1 line · Eduard Zingerman
Fixes df4761bd441c ("bpf: Support 32-bit linear scalar evolution")

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

Uh-oh.

Quoted 14 lines

kernel/bpf/scev.c int bpf_compute_loop_iters(struct bpf_verifier_env *env, struct bpf_verifier_sta · line 2706

Quoted 3 lines
kernel/bpf/scev.c +3 -0
+			/* 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
Quoted 5 lines

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.

Quoted 3 lines

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.

author maintainer
#5 lore raw
Quoted 2 lines · Eduard Zingerman
Quoted 1 line · Alexei Starovoitov

On Wed, Oct 21, 2026 at 11:56 AM Eduard Zingerman <[email protected]> wrote:

...

Quoted 10 lines
Quoted 10 lines

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
Quoted 5 lines
Quoted 5 lines

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.