Skip to contentSkip to conversation

bpf: refine u32/s32 bounds when ranges cross min/max boundary

PATCH Applied Eduard Zingerman 4 participants 8 messages Mar 7 – Mar 9

Subsystems (4)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

v3 cover bpf: refine u32/s32 bounds when ranges cross min/max boundary

Cover the following cases in range refinement logic for 32-bit ranges:
- s32 range crosses U32_MAX/0 boundary, positive part of the s32 range overlaps with u32 range.
- s32 range crosses U32_MAX/0 boundary, negative part of the s32 range overlaps with u32 range.

These cases are already handled for 64-bit range refinement.

Changelog:
- v2 -> v3:
- Reverted da653de268d3 (Paul)
- Removed !BPF_F_TEST_REG_INVARIANTS flag from

    crossing_32_bit_signed_boundary_2() (Paul)

- v1 -> v2:
- Extended commit message and comments (Emil)
- Targeting 'bpf' tree instead of bpf-next (Alexei)

v1: https://lore.kernel.org/bpf/[email protected]/T
v2: https://lore.kernel.org/bpf/[email protected]/
---
Eduard Zingerman (3):
bpf: refine u32/s32 bounds when ranges cross min/max boundary selftests/bpf: test refining u32/s32 bounds when ranges cross min/max boundary Revert "selftests/bpf: Update reg_bound range refinement logic"

 kernel/bpf/verifier.c                              | 24 +++++++
 .../testing/selftests/bpf/prog_tests/reg_bounds.c  | 76 +++++++++++++++++-----
 .../testing/selftests/bpf/progs/verifier_bounds.c  | 39 ++++++++++-
 3 files changed, 120 insertions(+), 19 deletions(-)

---
base-commit: 56145d237385ca0e7ca9ff7b226aaf2eb8ef368b
change-id: 20260305-bpf-32-bit-range-overflow-00351dfb8083

author maintainer
#1 lore raw

PATCH v3 1/3 bpf: refine u32/s32 bounds when ranges cross min/max boundary

Same as in __reg64_deduce_bounds(), refine s32/u32 ranges in __reg32_deduce_bounds() in the following situations:

- s32 range crosses U32_MAX/0 boundary, positive part of the s32 range overlaps with u32 range:

0 U32_MAX

  |  [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]              |
  |----------------------------|----------------------------|
  |xxxxx s32 range xxxxxxxxx]                       [xxxxxxx|
  0                     S32_MAX S32_MIN                    -1

- s32 range crosses U32_MAX/0 boundary, negative part of the s32 range overlaps with u32 range:

0 U32_MAX

  |              [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]  |
  |----------------------------|----------------------------|
  |xxxxxxxxx]                       [xxxxxxxxxxxx s32 range |
  0                     S32_MAX S32_MIN                    -1

- No refinement if ranges overlap in two intervals.

This helps for e.g. consider the following program:

call %[bpf_get_prandom_u32];
w0 &= 0xffffffff;

   if w0 < 0x3 goto 1f;    // on fall-through u32 range [3..U32_MAX]
   if w0 s> 0x1 goto 1f;   // on fall-through s32 range [S32_MIN..1]
   if w0 s< 0x0 goto 1f;   // range can be narrowed to  [S32_MIN..-1]

r10 = 0;
1: ...;

The reg_bounds.c selftest is updated to incorporate identical logic, refinement based on non-overflowing range halves:

((x ∩ [0, smax]) ∩ (y ∩ [0, smax])) ∪
((x ∩ [smin,-1]) ∩ (y ∩ [smin,-1]))

---
 kernel/bpf/verifier.c                              | 24 +++++++++
 .../testing/selftests/bpf/prog_tests/reg_bounds.c  | 62 ++++++++++++++++++++--
 2 files changed, 82 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +24 -0
index 401d6c4960eccfa90893660b7d8aece859787f7f..f960b382fdb3d4a4f5f2a66a525c2f594de529ff 100644
@@ -2511,6 +2511,30 @@ static void __reg32_deduce_bounds(struct bpf_reg_state *reg)
 	if ((u32)reg->s32_min_value <= (u32)reg->s32_max_value) {
 		reg->u32_min_value = max_t(u32, reg->s32_min_value, reg->u32_min_value);
 		reg->u32_max_value = min_t(u32, reg->s32_max_value, reg->u32_max_value);
+	} else {
+		if (reg->u32_max_value < (u32)reg->s32_min_value) {
+			/* See __reg64_deduce_bounds() for detailed explanation.
+			 * Refine ranges in the following situation:
+			 *
+			 * 0                                                   U32_MAX
+			 * |  [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]              |
+			 * |----------------------------|----------------------------|
+			 * |xxxxx s32 range xxxxxxxxx]                       [xxxxxxx|
+			 * 0                     S32_MAX S32_MIN                    -1
+			 */
+			reg->s32_min_value = (s32)reg->u32_min_value;
+			reg->u32_max_value = min_t(u32, reg->u32_max_value, reg->s32_max_value);
+		} else if ((u32)reg->s32_max_value < reg->u32_min_value) {
+			/*
+			 * 0                                                   U32_MAX
+			 * |              [xxxxxxxxxxxxxx u32 range xxxxxxxxxxxxxx]  |
+			 * |----------------------------|----------------------------|
+			 * |xxxxxxxxx]                       [xxxxxxxxxxxx s32 range |
+			 * 0                     S32_MAX S32_MIN                    -1
+			 */
+			reg->s32_max_value = (s32)reg->u32_max_value;
+			reg->u32_min_value = max_t(u32, reg->u32_min_value, reg->s32_min_value);
+		}
 	}
 }
 
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +58 -4

94 lines not on this page · raw message

Signature · 1 line
2.53.0
#2 lore raw
Should this have a Fixes: tag? The 64-bit version of this refinement was added by commit 00bf8d0c6c9b ("bpf: Improve bounds when s64 crosses sign boundary"), which explicitly noted that the same…
Quoted 6 lines

Should this have a Fixes: tag? The 64-bit version of this refinement was added by commit 00bf8d0c6c9b ("bpf: Improve bounds when s64 crosses sign boundary"), which explicitly noted that the same logic could apply to s32/u32 ranges but did not implement it. This patch fills that gap.

A Fixes: tag pointing to that commit would help with stable backports:

Fixes 00bf8d0c6c9b ("bpf: Improve bounds when s64 crosses sign boundary")

---
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/22788511420

author maintainer
#3 lore raw
Quoted 13 lines · On Sat, 2026-03-07 at 01:35 +0000, [email protected] wrote:
Quoted 6 lines

Should this have a Fixes: tag? The 64-bit version of this refinement was added by commit 00bf8d0c6c9b ("bpf: Improve bounds when s64 crosses sign boundary"), which explicitly noted that the same logic could apply to s32/u32 ranges but did not implement it. This patch fills that gap.

Quoted 4 lines

A Fixes: tag pointing to that commit would help with stable backports:

Fixes 00bf8d0c6c9b ("bpf: Improve bounds when s64 crosses sign boundary")

Nope, not necessary.

Quoted 6 lines

---
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/22788511420

author maintainer
#4 lore raw

PATCH v3 2/3 selftests/bpf: test refining u32/s32 bounds when ranges cross min/max boundary

In reply to Eduard Zingerman

Two test cases for signed/unsigned 32-bit bounds refinement when s32 range crosses the sign boundary:
- s32 range [S32_MIN..1] overlapping with u32 range [3..U32_MAX], s32 range tail before sign boundary overlaps with u32 range.
- s32 range [-3..5] overlapping with u32 range [0..S32_MIN+3], s32 range head after the sign boundary overlaps with u32 range.

This covers both branches added in the __reg32_deduce_bounds().

Also, crossing_32_bit_signed_boundary_2() no longer triggers invariant violations.

---
 .../testing/selftests/bpf/progs/verifier_bounds.c  | 39 +++++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/verifier_bounds.c +38 -1
index 97065a26cf70603c3e4b8d43d3a04248828398fc..e526315c718ad7e7905d95cc9b52b229cb12af39 100644
@@ -1148,7 +1148,7 @@ l0_%=:	r0 = 0;						\
 SEC("xdp")
 __description("bound check with JMP32_JSLT for crossing 32-bit signed boundary")
 __success __retval(0)
-__flag(!BPF_F_TEST_REG_INVARIANTS) /* known invariants violation */
+__flag(BPF_F_TEST_REG_INVARIANTS)
 __naked void crossing_32_bit_signed_boundary_2(void)
 {
 	asm volatile ("					\
@@ -2000,4 +2000,41 @@ __naked void bounds_refinement_multiple_overlaps(void *ctx)
 	: __clobber_all);
 }
 
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void signed_unsigned_intersection32_case1(void *ctx)
+{
+	asm volatile("									\
+	call %[bpf_get_prandom_u32];							\
+	w0 &= 0xffffffff;								\
+	if w0 < 0x3 goto 1f;		/* on fall-through u32 range [3..U32_MAX]  */	\
+	if w0 s> 0x1 goto 1f;		/* on fall-through s32 range [S32_MIN..1]  */	\
+	if w0 s< 0x0 goto 1f;		/* range can be narrowed to  [S32_MIN..-1] */	\
+	r10 = 0;			/* thus predicting the jump. */			\
+1:	exit;										\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+SEC("socket")
+__success
+__flag(BPF_F_TEST_REG_INVARIANTS)
+__naked void signed_unsigned_intersection32_case2(void *ctx)
+{
+	asm volatile("									\
+	call %[bpf_get_prandom_u32];							\
+	w0 &= 0xffffffff;								\
+	if w0 > 0x80000003 goto 1f;	/* on fall-through u32 range [0..S32_MIN+3] */	\
+	if w0 s< -3 goto 1f;		/* on fall-through s32 range [-3..S32_MAX] */	\
+	if w0 s> 5 goto 1f;		/* on fall-through s32 range [-3..5] */		\
+	if w0 <= 5 goto 1f;		/* range can be narrowed to  [0..5] */		\
+	r10 = 0;			/* thus predicting the jump */			\
+1:	exit;										\
+"	:
+	: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0
author maintainer
#5 lore raw

PATCH v3 3/3 Revert "selftests/bpf: Update reg_bound range refinement logic"

In reply to Eduard Zingerman

This reverts commit da653de268d32a80e135c9eb960a8147c186f1bc. Removed logic is now covered by range_refine_in_halves() which handles both 32-bit and 64-bit refinements.

---
 tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 14 --------------
 1 file changed, 14 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +0 -14
index 04938d0d431b38e086b50fe28b99e4ad2682742e..cb8dd2f63296b826491c8a010f4ece4aa20c0560 100644
@@ -519,20 +519,6 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 		return range_intersection(x_t, x, x_swap);
 	}
 
-	if (!t_is_32(x_t) && !t_is_32(y_t) && x_t != y_t) {
-		if (x_t == S64 && x.a > x.b) {
-			if (x.b < y.a && x.a <= y.b)
-				return range(x_t, x.a, y.b);
-			if (x.a > y.b && x.b >= y.a)
-				return range(x_t, y.a, x.b);
-		} else if (x_t == U64 && y.a > y.b) {
-			if (y.b < x.a && y.a <= x.b)
-				return range(x_t, y.a, x.b);
-			if (y.a > x.b && y.b >= x.a)
-				return range(x_t, x.a, y.b);
-		}
-	}
-
 	/* otherwise, plain range cast and intersection works */
 	return range_intersection(x_t, x, y_cast);
 }
Signature · 1 line
2.53.0
reviewer Reviewed-by on v3 3/3
#6 lore raw

Re: [PATCH bpf v3 3/3] Revert "selftests/bpf: Update reg_bound range refinement logic"

Quoted 6 lines · Eduard Zingerman

This reverts commit da653de268d32a80e135c9eb960a8147c186f1bc. Removed logic is now covered by range_refine_in_halves() which handles both 32-bit and 64-bit refinements.

Quoted 29 lines
---
 tools/testing/selftests/bpf/prog_tests/reg_bounds.c | 14 --------------
 1 file changed, 14 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +0 -14
index 04938d0d431b38e086b50fe28b99e4ad2682742e..cb8dd2f63296b826491c8a010f4ece4aa20c0560 100644
@@ -519,20 +519,6 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 		return range_intersection(x_t, x, x_swap);
 	}
 
-	if (!t_is_32(x_t) && !t_is_32(y_t) && x_t != y_t) {
-		if (x_t == S64 && x.a > x.b) {
-			if (x.b < y.a && x.a <= y.b)
-				return range(x_t, x.a, y.b);
-			if (x.a > y.b && x.b >= y.a)
-				return range(x_t, y.a, x.b);
-		} else if (x_t == U64 && y.a > y.b) {
-			if (y.b < x.a && y.a <= x.b)
-				return range(x_t, y.a, x.b);
-			if (y.a > x.b && y.b >= x.a)
-				return range(x_t, x.a, y.b);
-		}
-	}
-
 	/* otherwise, plain range cast and intersection works */
 	return range_intersection(x_t, x, y_cast);
 }
#7 lore raw
In reply to Eduard Zingerman
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:

Quoted 9 lines · On Fri, 6 Mar 2026 16:54:23 -0800 you wrote:

Cover the following cases in range refinement logic for 32-bit ranges:
- s32 range crosses U32_MAX/0 boundary, positive part of the s32 range overlaps with u32 range.
- s32 range crosses U32_MAX/0 boundary, negative part of the s32 range overlaps with u32 range.

These cases are already handled for 64-bit range refinement.

[...]

Here is the summary with links:
- [bpf,v3,1/3] bpf: refine u32/s32 bounds when ranges cross min/max boundary

    https://git.kernel.org/bpf/bpf/c/fbc7aef517d8
  - [bpf,v3,2/3] selftests/bpf: test refining u32/s32 bounds when ranges cross min/max boundary
    https://git.kernel.org/bpf/bpf/c/f81fdfd16771
  - [bpf,v3,3/3] Revert "selftests/bpf: Update reg_bound range refinement logic"
    https://git.kernel.org/bpf/bpf/c/d87c9305a884

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html