Skip to contentSkip to conversation

bpf: Get better reg range with ldsx and 32bit compare

PATCH Superseded Yonghong Song 3 participants 9 messages Jul 18, 2024 – Jul 24, 2024

Subsystems (4)

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

PATCH v4 1/2 bpf: Get better reg range with ldsx and 32bit compare

With latest llvm19, the selftest iters/iter_arr_with_actual_elem_count failed with -mcpu=v4.

The following are the details:
0: R1=ctx() R10=fp0
; int iter_arr_with_actual_elem_count(const void *ctx) @ iters.c:1420
0: (b4) w7 = 0 ; R7_w=0
; int i, n = loop_data.n, sum = 0; @ iters.c:1422
1: (18) r1 = 0xffffc90000191478 ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144)
3: (61) r6 = *(u32 *)(r1 +128) ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
; if (n > ARRAY_SIZE(loop_data.data)) @ iters.c:1424

  4: (26) if w6 > 0x20 goto pc+27       ; R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))
  5: (bf) r8 = r10                      ; R8_w=fp0 R10=fp0
  6: (07) r8 += -8                      ; R8_w=fp-8
  ; bpf_for(i, 0, n) { @ iters.c:1427
  7: (bf) r1 = r8                       ; R1_w=fp-8 R8_w=fp-8
  8: (b4) w2 = 0                        ; R2_w=0
  9: (bc) w3 = w6                       ; R3_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R6_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))

10: (85) call bpf_iter_num_new#45179 ; R0=scalar() fp-8=iter_num(ref_id=2,state=active,depth=0) refs=2
11: (bf) r1 = r8 ; R1=fp-8 R8=fp-8 refs=2
12: (85) call bpf_iter_num_next#45181 13: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
; bpf_for(i, 0, n) { @ iters.c:1427
13: (15) if r0 == 0x0 goto pc+2 ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
14: (81) r1 = *(s32 *)(r0 +0) ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) refs=2
15: (ae) if w1 < w6 goto pc+4 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=scalar(smin=0xffffffff80000000,smax=smax32=umax32=31,umax=0xffffffff0000001f,smin32=0,var_off=(0x0; 0xffffffff0000001f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2 ; sum += loop_data.data[i]; @ iters.c:1429
20: (67) r1 <<= 2 ; R1_w=scalar(smax=0x7ffffffc0000007c,umax=0xfffffffc0000007c,smin32=0,smax32=umax32=124,var_off=(0x0; 0xfffffffc0000007c)) refs=2
21: (18) r2 = 0xffffc90000191478 ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
23: (0f) r2 += r1
math between map_value pointer and register with unbounded min value is not allowed

The source code:
int iter_arr_with_actual_elem_count(const void *ctx)

  {
        int i, n = loop_data.n, sum = 0;

        if (n > ARRAY_SIZE(loop_data.data))
                return 0;

        bpf_for(i, 0, n) {
                /* no rechecking of i against ARRAY_SIZE(loop_data.n) */
                sum += loop_data.data[i];
        }

        return sum;

}

The insn #14 is a sign-extenstion load which is related to 'int i'.
The insn #15 did a subreg comparision. Note that smin=0xffffffff80000000 and this caused later insn #23 failed verification due to unbounded min value.

Actually insn #15 R1 smin range can be better. Before insn #15, we have
R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff)
With the above range, we know for R1, upper 32bit can only be 0xffffffff or 0. Otherwise, the value range for R1 could be beyond [smin=0xffffffff80000000,smax=0x7fffffff].

After insn #15, for the true patch, we know smin32=0 and smax32=32. With the upper 32bit 0xffffffff, then the corresponding value is [0xffffffff00000000, 0xffffffff00000020]. The range is obviously beyond the original range [smin=0xffffffff80000000,smax=0x7fffffff] and the range is not possible. So the upper 32bit must be 0, which implies smin = smin32 and smax = smax32.

This patch fixed the issue by adding additional register deduction after 32-bit compare insn. If the signed 32-bit register range is non-negative then 64-bit smin is in range of [S32_MIN, S32_MAX], then the actual 64-bit smin/smax should be the same as 32-bit smin32/smax32.

With this patch, iters/iter_arr_with_actual_elem_count succeeded with better register range:

from 15 to 20: R0=rdonly_mem(id=7,ref_obj_id=2,sz=4) R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R8=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=3) refs=2

---
 kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +36 -0
index 8da132a1ef28..46532437c4bb 100644
@@ -2182,6 +2182,42 @@ static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg)
 		reg->smin_value = max_t(s64, reg->smin_value, new_smin);
 		reg->smax_value = min_t(s64, reg->smax_value, new_smax);
 	}
+
+	/* Here we would like to handle a special case after sign extending load,
+	 * when upper bits for a 64-bit range are all 1s or all 0s.
+	 *
+	 * Upper bits are all 1s when register is in a range:
+	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
+	 * Upper bits are all 0s when register is in a range:
+	 *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
+	 * Together this forms are continuous range:
+	 *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
+	 *
+	 * Now, suppose that register range is in fact tighter:
+	 *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
+	 * Also suppose that it's 32-bit range is positive,
+	 * meaning that lower 32-bits of the full 64-bit register
+	 * are in the range:
+	 *   [0x0000_0000, 0x7fff_ffff] (W)
+	 *
+	 * If this happens, then any value in a range:
+	 *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
+	 * is smaller than a lowest bound of the range (R):
+	 *   0xffff_ffff_8000_0000
+	 * which means that upper bits of the full 64-bit register
+	 * can't be all 1s, when lower bits are in range (W).
+	 *
+	 * Note that:
+	 *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
+	 *  - 0x0000_0000_ffff_ffff == (s64)S32_MAX
+	 * These relations are used in the conditions below.
+	 */
+	if (reg->s32_min_value >= 0 && reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX) {
+		reg->smin_value = reg->umin_value = reg->s32_min_value;
+		reg->smax_value = reg->umax_value = reg->s32_max_value;
+		reg->var_off = tnum_intersect(reg->var_off,
+					      tnum_range(reg->smin_value, reg->smax_value));
+	}
 }
 
 static void __reg_deduce_bounds(struct bpf_reg_state *reg)
Signature · 1 line
2.43.0
author reviewer
#1 lore raw

PATCH v4 2/2 selftests/bpf: Add reg_bounds tests for ldsx and subreg compare

Add a few reg_bounds selftests to test 32/16/8-bit ldsx and subreg comparison. Without the previous patch, all added tests will fail.

---
 .../selftests/bpf/prog_tests/reg_bounds.c       | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +17 -0
index eb74363f9f70..cd9bafe9c057 100644
@@ -441,6 +441,20 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
 	if (t_is_32(y_t) && !t_is_32(x_t)) {
 		struct range x_swap;
 
+		/* If we know that
+		 *   - *x* is in the range of signed 32bit value
+		 *   - *y_cast* range is 32-bit sign non-negative, and
+		 * then *x* range can be narrowed to the interaction of
+		 * *x* and *y_cast*. Otherwise, if the new range for *x*
+		 * allows upper 32-bit 0xffffffff then the eventual new
+		 * range for *x* will be out of signed 32-bit range
+		 * which violates the origin *x* range.
+		 */
+		if (x_t == S64 && y_t == S32 &&
+		    !(y_cast.a & 0xffffffff80000000ULL) && !(y_cast.b & 0xffffffff80000000) &&
+		    (long long)x.a >= S32_MIN && (long long)x.b <= S32_MAX)
+			return range_improve(x_t, x, y_cast);
+
 		/* some combinations of upper 32 bits and sign bit can lead to
 		 * invalid ranges, in such cases it's easier to detect them
 		 * after cast/swap than try to enumerate all the conditions
@@ -2108,6 +2122,9 @@ static struct subtest_case crafted_cases[] = {
 	{S32, U32, {(u32)S32_MIN, 0}, {0, 0}},
 	{S32, U32, {(u32)S32_MIN, 0}, {(u32)S32_MIN, (u32)S32_MIN}},
 	{S32, U32, {(u32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
+	{S64, U32, {0x0, 0x1f}, {0xffffffff80000000ULL, 0x000000007fffffffULL}},
+	{S64, U32, {0x0, 0x1f}, {0xffffffffffff8000ULL, 0x0000000000007fffULL}},
+	{S64, U32, {0x0, 0x1f}, {0xffffffffffffff80ULL, 0x000000000000007fULL}},
 };
 
 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
Signature · 1 line
2.43.0
#3 lore raw

Re: [PATCH bpf-next v4 2/2] selftests/bpf: Add reg_bounds tests for ldsx and subreg compare

In reply to Yonghong Song
Quoted 9 lines · Yonghong Song

Add a few reg_bounds selftests to test 32/16/8-bit ldsx and subreg comparison. Without the previous patch, all added tests will fail.

---
 .../selftests/bpf/prog_tests/reg_bounds.c       | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

wow, I already forgot most of the things in here... :(

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 446

Quoted 11 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +3 -0
index eb74363f9f70..cd9bafe9c057 100644
@@ -441,6 +441,20 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
        if (t_is_32(y_t) && !t_is_32(x_t)) {
                struct range x_swap;
 
+               /* If we know that
+                *   - *x* is in the range of signed 32bit value
+                *   - *y_cast* range is 32-bit sign non-negative, and

sign -> signed?

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 447

Quoted 1 line
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +1 -0
+                * then *x* range can be narrowed to the interaction of

what does it mean "narrowed to the interaction"?

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 453

Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +6 -0
+                * *x* and *y_cast*. Otherwise, if the new range for *x*
+                * allows upper 32-bit 0xffffffff then the eventual new
+                * range for *x* will be out of signed 32-bit range
+                * which violates the origin *x* range.
+                */
+               if (x_t == S64 && y_t == S32 &&

tbh, given this is so specific for x_t == S64 and y_T == S32, I'd move it out from this if into an independent condition, it doesn't benefit from being inside

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 454

Quoted 1 line
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +1 -0
+                   !(y_cast.a & 0xffffffff80000000ULL) && !(y_cast.b & 0xffffffff80000000) &&

isn't this just a much more convoluted way of checking:

y_cast.a <= 0x7fffffffULL && y_cast.b <= 0x7fffffffULL

? Is & + negation really easier to follow?...

Quoted 19 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +6 -1
+                   (long long)x.a >= S32_MIN && (long long)x.b <= S32_MAX)
+                       return range_improve(x_t, x, y_cast);
+
                /* some combinations of upper 32 bits and sign bit can lead to
                 * invalid ranges, in such cases it's easier to detect them
                 * after cast/swap than try to enumerate all the conditions
@@ -2108,6 +2122,9 @@ static struct subtest_case crafted_cases[] = {
        {S32, U32, {(u32)S32_MIN, 0}, {0, 0}},
        {S32, U32, {(u32)S32_MIN, 0}, {(u32)S32_MIN, (u32)S32_MIN}},
        {S32, U32, {(u32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
+       {S64, U32, {0x0, 0x1f}, {0xffffffff80000000ULL, 0x000000007fffffffULL}},
+       {S64, U32, {0x0, 0x1f}, {0xffffffffffff8000ULL, 0x0000000000007fffULL}},
+       {S64, U32, {0x0, 0x1f}, {0xffffffffffffff80ULL, 0x000000000000007fULL}},
 };
 
 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
--

2.43.0

author reviewer
#4 lore raw

Re: [PATCH bpf-next v4 2/2] selftests/bpf: Add reg_bounds tests for ldsx and subreg compare

Quoted 19 lines · Andrii Nakryiko
Quoted 8 lines · Yonghong Song

Add a few reg_bounds selftests to test 32/16/8-bit ldsx and subreg comparison. Without the previous patch, all added tests will fail.

---
  .../selftests/bpf/prog_tests/reg_bounds.c       | 17 +++++++++++++++++
  1 file changed, 17 insertions(+)

wow, I already forgot most of the things in here... :(

Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +0 -0
index eb74363f9f70..cd9bafe9c057 100644
@@ -441,6 +441,20 @@ static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t,
         if (t_is_32(y_t) && !t_is_32(x_t)) {
                 struct range x_swap;
 
Quoted 4 lines

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 446

Quoted 3 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +3 -0
+               /* If we know that
+                *   - *x* is in the range of signed 32bit value
+                *   - *y_cast* range is 32-bit sign non-negative, and

sign -> signed?

Ack

Quoted 3 lines

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 447

Quoted 2 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +1 -0
+                * then *x* range can be narrowed to the interaction of

what does it mean "narrowed to the interaction"?

Let us change to '*x* range can be improved with *y_cast*.

Quoted 10 lines

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 453

Quoted 7 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +6 -0
+                * *x* and *y_cast*. Otherwise, if the new range for *x*
+                * allows upper 32-bit 0xffffffff then the eventual new
+                * range for *x* will be out of signed 32-bit range
+                * which violates the origin *x* range.
+                */
+               if (x_t == S64 && y_t == S32 &&

tbh, given this is so specific for x_t == S64 and y_T == S32, I'd move it out from this if into an independent condition, it doesn't benefit from being inside

Okay, I can do this.

Quoted 5 lines

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct range range_refine(enum num_t x_t, struct range x, enum num_t y_t, · line 454

Quoted 2 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +1 -0
+                   !(y_cast.a & 0xffffffff80000000ULL) && !(y_cast.b & 0xffffffff80000000) &&

isn't this just a much more convoluted way of checking:

y_cast.a <= 0x7fffffffULL && y_cast.b <= 0x7fffffffULL

Yes, this is indeed simpler. I can use this one.

Quoted 22 lines

? Is & + negation really easier to follow?...

Quoted 19 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +6 -1
+                   (long long)x.a >= S32_MIN && (long long)x.b <= S32_MAX)
+                       return range_improve(x_t, x, y_cast);
+
                 /* some combinations of upper 32 bits and sign bit can lead to
                  * invalid ranges, in such cases it's easier to detect them
                  * after cast/swap than try to enumerate all the conditions
@@ -2108,6 +2122,9 @@ static struct subtest_case crafted_cases[] = {
         {S32, U32, {(u32)S32_MIN, 0}, {0, 0}},
         {S32, U32, {(u32)S32_MIN, 0}, {(u32)S32_MIN, (u32)S32_MIN}},
         {S32, U32, {(u32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
+       {S64, U32, {0x0, 0x1f}, {0xffffffff80000000ULL, 0x000000007fffffffULL}},
+       {S64, U32, {0x0, 0x1f}, {0xffffffffffff8000ULL, 0x0000000000007fffULL}},
+       {S64, U32, {0x0, 0x1f}, {0xffffffffffffff80ULL, 0x000000000000007fULL}},
  };
 
  /* Go over crafted hard-coded cases. This is fast, so we do it as part of
--

2.43.0

#5 lore raw
In reply to Yonghong Song
Quoted 57 lines · Yonghong Song

With latest llvm19, the selftest iters/iter_arr_with_actual_elem_count failed with -mcpu=v4.

The following are the details:
0: R1=ctx() R10=fp0
; int iter_arr_with_actual_elem_count(const void *ctx) @ iters.c:1420
0: (b4) w7 = 0 ; R7_w=0
; int i, n = loop_data.n, sum = 0; @ iters.c:1422
1: (18) r1 = 0xffffc90000191478 ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144)
3: (61) r6 = *(u32 *)(r1 +128) ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
; if (n > ARRAY_SIZE(loop_data.data)) @ iters.c:1424

  4: (26) if w6 > 0x20 goto pc+27       ; R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))
  5: (bf) r8 = r10                      ; R8_w=fp0 R10=fp0
  6: (07) r8 += -8                      ; R8_w=fp-8
  ; bpf_for(i, 0, n) { @ iters.c:1427
  7: (bf) r1 = r8                       ; R1_w=fp-8 R8_w=fp-8
  8: (b4) w2 = 0                        ; R2_w=0
  9: (bc) w3 = w6                       ; R3_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R6_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))

10: (85) call bpf_iter_num_new#45179 ; R0=scalar() fp-8=iter_num(ref_id=2,state=active,depth=0) refs=2
11: (bf) r1 = r8 ; R1=fp-8 R8=fp-8 refs=2
12: (85) call bpf_iter_num_next#45181 13: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
; bpf_for(i, 0, n) { @ iters.c:1427
13: (15) if r0 == 0x0 goto pc+2 ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
14: (81) r1 = *(s32 *)(r0 +0) ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) refs=2
15: (ae) if w1 < w6 goto pc+4 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=scalar(smin=0xffffffff80000000,smax=smax32=umax32=31,umax=0xffffffff0000001f,smin32=0,var_off=(0x0; 0xffffffff0000001f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2 ; sum += loop_data.data[i]; @ iters.c:1429
20: (67) r1 <<= 2 ; R1_w=scalar(smax=0x7ffffffc0000007c,umax=0xfffffffc0000007c,smin32=0,smax32=umax32=124,var_off=(0x0; 0xfffffffc0000007c)) refs=2
21: (18) r2 = 0xffffc90000191478 ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
23: (0f) r2 += r1
math between map_value pointer and register with unbounded min value is not allowed

The source code:
int iter_arr_with_actual_elem_count(const void *ctx)

  {
        int i, n = loop_data.n, sum = 0;

        if (n > ARRAY_SIZE(loop_data.data))
                return 0;

        bpf_for(i, 0, n) {
                /* no rechecking of i against ARRAY_SIZE(loop_data.n) */
                sum += loop_data.data[i];
        }

        return sum;

}

The insn #14 is a sign-extenstion load which is related to 'int i'.
The insn #15 did a subreg comparision. Note that smin=0xffffffff80000000 and this caused later insn #23 failed verification due to unbounded min value.

Actually insn #15 R1 smin range can be better. Before insn #15, we have
R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff)
With the above range, we know for R1, upper 32bit can only be 0xffffffff or 0. Otherwise, the value range for R1 could be beyond [smin=0xffffffff80000000,smax=0x7fffffff].

Quoted 7 lines

After insn #15, for the true patch, we know smin32=0 and smax32=32. With the upper 32bit 0xffffffff, then the corresponding value is [0xffffffff00000000, 0xffffffff00000020]. The range is obviously beyond the original range [smin=0xffffffff80000000,smax=0x7fffffff] and the range is not possible. So the upper 32bit must be 0, which implies smin = smin32 and smax = smax32.

This patch fixed the issue by adding additional register deduction after 32-bit compare

__reg_deduce_mixed_bounds() is called from reg_bounds_sync() pretty much after every arithmetic operation or any comparison. Is the above logic true universally or only after signed comparison? If the latter, then we can't just do it unconditionally inside __reg_deduce_mixed_bounds().

Quoted 41 lines

insn. If the signed 32-bit register range is non-negative then 64-bit smin is in range of [S32_MIN, S32_MAX], then the actual 64-bit smin/smax should be the same as 32-bit smin32/smax32.

With this patch, iters/iter_arr_with_actual_elem_count succeeded with better register range:

from 15 to 20: R0=rdonly_mem(id=7,ref_obj_id=2,sz=4) R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R8=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=3) refs=2

---
 kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +18 -0
index 8da132a1ef28..46532437c4bb 100644
@@ -2182,6 +2182,42 @@ static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg)
                reg->smin_value = max_t(s64, reg->smin_value, new_smin);
                reg->smax_value = min_t(s64, reg->smax_value, new_smax);
        }
+
+       /* Here we would like to handle a special case after sign extending load,
+        * when upper bits for a 64-bit range are all 1s or all 0s.
+        *
+        * Upper bits are all 1s when register is in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
+        * Upper bits are all 0s when register is in a range:
+        *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
+        * Together this forms are continuous range:
+        *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
+        *
+        * Now, suppose that register range is in fact tighter:
+        *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
+        * Also suppose that it's 32-bit range is positive,
+        * meaning that lower 32-bits of the full 64-bit register
+        * are in the range:
+        *   [0x0000_0000, 0x7fff_ffff] (W)
+        *

kernel/bpf/verifier.c static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) · line 2212

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+        * If this happens, then any value in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
+        * is smaller than a lowest bound of the range (R):
+        *   0xffff_ffff_8000_0000
+        * which means that upper bits of the full 64-bit register
+        * can't be all 1s, when lower bits are in range (W).
+        *
+        * Note that:
+        *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
+        *  - 0x0000_0000_ffff_ffff == (s64)S32_MAX

?? S32_MAX = 0x7fffffff, so should the right part be U32_MAX or the left part should be 0x0000_0000_7fff_ffff ?

kernel/bpf/verifier.c static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) · line 2217

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+        * These relations are used in the conditions below.
+        */
+       if (reg->s32_min_value >= 0 && reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX) {
+               reg->smin_value = reg->umin_value = reg->s32_min_value;
+               reg->smax_value = reg->umax_value = reg->s32_max_value;

let's please not mix signed and unsigned 32 -> 64 bit conversions, they are confusing and tricky enough in each domain individually, there is no point in mixing them

Quoted 9 lines
kernel/bpf/verifier.c +3 -1
+               reg->var_off = tnum_intersect(reg->var_off,
+                                             tnum_range(reg->smin_value, reg->smax_value));
+       }
 }
 
 static void __reg_deduce_bounds(struct bpf_reg_state *reg)
--

2.43.0

maintainer
#6 lore raw

On Fri, 2024-07-19 at 15:46 -0700, Andrii Nakryiko wrote:

[...]

Quoted 28 lines
Quoted 17 lines
kernel/bpf/verifier.c +17 -0
+       /* Here we would like to handle a special case after sign extending load,
+        * when upper bits for a 64-bit range are all 1s or all 0s.
+        *
+        * Upper bits are all 1s when register is in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
+        * Upper bits are all 0s when register is in a range:
+        *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
+        * Together this forms are continuous range:
+        *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
+        *
+        * Now, suppose that register range is in fact tighter:
+        *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
+        * Also suppose that it's 32-bit range is positive,
+        * meaning that lower 32-bits of the full 64-bit register
+        * are in the range:
+        *   [0x0000_0000, 0x7fff_ffff] (W)
+        *

kernel/bpf/verifier.c static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) · line 2212

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+        * If this happens, then any value in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
+        * is smaller than a lowest bound of the range (R):
+        *   0xffff_ffff_8000_0000
+        * which means that upper bits of the full 64-bit register
+        * can't be all 1s, when lower bits are in range (W).
+        *
+        * Note that:
+        *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
+        *  - 0x0000_0000_ffff_ffff == (s64)S32_MAX
Quoted 2 lines

?? S32_MAX = 0x7fffffff, so should the right part be U32_MAX or the left part should be 0x0000_0000_7fff_ffff ?

Oops, that's on me, yes it should be 0x0000_0000_7fff_ffff here.

[...]

author reviewer
#7 lore raw
In reply to Andrii Nakryiko
Quoted 63 lines · Andrii Nakryiko
Quoted 62 lines · Yonghong Song

With latest llvm19, the selftest iters/iter_arr_with_actual_elem_count failed with -mcpu=v4.

The following are the details:

   0: R1=ctx() R10=fp0
   ; int iter_arr_with_actual_elem_count(const void *ctx) @ iters.c:1420
   0: (b4) w7 = 0                        ; R7_w=0
   ; int i, n = loop_data.n, sum = 0; @ iters.c:1422
   1: (18) r1 = 0xffffc90000191478       ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144)
   3: (61) r6 = *(u32 *)(r1 +128)        ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
   ; if (n > ARRAY_SIZE(loop_data.data)) @ iters.c:1424
   4: (26) if w6 > 0x20 goto pc+27       ; R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))
   5: (bf) r8 = r10                      ; R8_w=fp0 R10=fp0
   6: (07) r8 += -8                      ; R8_w=fp-8
   ; bpf_for(i, 0, n) { @ iters.c:1427
   7: (bf) r1 = r8                       ; R1_w=fp-8 R8_w=fp-8
   8: (b4) w2 = 0                        ; R2_w=0
   9: (bc) w3 = w6                       ; R3_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R6_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))
   10: (85) call bpf_iter_num_new#45179          ; R0=scalar() fp-8=iter_num(ref_id=2,state=active,depth=0) refs=2
   11: (bf) r1 = r8                      ; R1=fp-8 R8=fp-8 refs=2
   12: (85) call bpf_iter_num_next#45181 13: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
   ; bpf_for(i, 0, n) { @ iters.c:1427
   13: (15) if r0 == 0x0 goto pc+2       ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
   14: (81) r1 = *(s32 *)(r0 +0)         ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) refs=2
   15: (ae) if w1 < w6 goto pc+4 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=scalar(smin=0xffffffff80000000,smax=smax32=umax32=31,umax=0xffffffff0000001f,smin32=0,var_off=(0x0; 0xffffffff0000001f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
   ; sum += loop_data.data[i]; @ iters.c:1429
   20: (67) r1 <<= 2                     ; R1_w=scalar(smax=0x7ffffffc0000007c,umax=0xfffffffc0000007c,smin32=0,smax32=umax32=124,var_off=(0x0; 0xfffffffc0000007c)) refs=2
   21: (18) r2 = 0xffffc90000191478      ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
   23: (0f) r2 += r1
   math between map_value pointer and register with unbounded min value is not allowed

The source code:

   int iter_arr_with_actual_elem_count(const void *ctx)
   {
         int i, n = loop_data.n, sum = 0;

         if (n > ARRAY_SIZE(loop_data.data))
                 return 0;

         bpf_for(i, 0, n) {
                 /* no rechecking of i against ARRAY_SIZE(loop_data.n) */
                 sum += loop_data.data[i];
         }

         return sum;
   }

The insn #14 is a sign-extenstion load which is related to 'int i'.
The insn #15 did a subreg comparision. Note that smin=0xffffffff80000000 and this caused later insn #23 failed verification due to unbounded min value.

Actually insn #15 R1 smin range can be better. Before insn #15, we have
R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff)
With the above range, we know for R1, upper 32bit can only be 0xffffffff or 0. Otherwise, the value range for R1 could be beyond [smin=0xffffffff80000000,smax=0x7fffffff].

After insn #15, for the true patch, we know smin32=0 and smax32=32. With the upper 32bit 0xffffffff, then the corresponding value is [0xffffffff00000000, 0xffffffff00000020]. The range is obviously beyond the original range [smin=0xffffffff80000000,smax=0x7fffffff] and the range is not possible. So the upper 32bit must be 0, which implies smin = smin32 and smax = smax32.

Quoted 6 lines
Quoted 1 line

This patch fixed the issue by adding additional register deduction after 32-bit compare

__reg_deduce_mixed_bounds() is called from reg_bounds_sync() pretty much after every arithmetic operation or any comparison. Is the above logic true universally or only after signed comparison? If the latter, then we can't just do it unconditionally inside __reg_deduce_mixed_bounds().

It is not just for signed extension. Some other arithmetic operation may produce such a range as well.

Quoted 46 lines
Quoted 46 lines

insn. If the signed 32-bit register range is non-negative then 64-bit smin is in range of [S32_MIN, S32_MAX], then the actual 64-bit smin/smax should be the same as 32-bit smin32/smax32.

With this patch, iters/iter_arr_with_actual_elem_count succeeded with better register range:

from 15 to 20: R0=rdonly_mem(id=7,ref_obj_id=2,sz=4) R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R8=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=3) refs=2

---
  kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
  1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +22 -0
index 8da132a1ef28..46532437c4bb 100644
@@ -2182,6 +2182,42 @@ static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg)
                 reg->smin_value = max_t(s64, reg->smin_value, new_smin);
                 reg->smax_value = min_t(s64, reg->smax_value, new_smax);
         }
+
+       /* Here we would like to handle a special case after sign extending load,
+        * when upper bits for a 64-bit range are all 1s or all 0s.
+        *
+        * Upper bits are all 1s when register is in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
+        * Upper bits are all 0s when register is in a range:
+        *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
+        * Together this forms are continuous range:
+        *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
+        *
+        * Now, suppose that register range is in fact tighter:
+        *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
+        * Also suppose that it's 32-bit range is positive,
+        * meaning that lower 32-bits of the full 64-bit register
+        * are in the range:
+        *   [0x0000_0000, 0x7fff_ffff] (W)
+        *
+        * If this happens, then any value in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
+        * is smaller than a lowest bound of the range (R):
+        *   0xffff_ffff_8000_0000
Quoted 8 lines

kernel/bpf/verifier.c static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) · line 2212

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+        * which means that upper bits of the full 64-bit register
+        * can't be all 1s, when lower bits are in range (W).
+        *
+        * Note that:
+        *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
+        *  - 0x0000_0000_ffff_ffff == (s64)S32_MAX

?? S32_MAX = 0x7fffffff, so should the right part be U32_MAX or the left part should be 0x0000_0000_7fff_ffff ?

Will make a change in the next revision.

Quoted 9 lines

kernel/bpf/verifier.c static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) · line 2217

Quoted 6 lines
kernel/bpf/verifier.c +5 -0
+        * These relations are used in the conditions below.
+        */
+       if (reg->s32_min_value >= 0 && reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX) {
+               reg->smin_value = reg->umin_value = reg->s32_min_value;
+               reg->smax_value = reg->umax_value = reg->s32_max_value;

let's please not mix signed and unsigned 32 -> 64 bit conversions, they are confusing and tricky enough in each domain individually, there is no point in mixing them

Okay, will do.

Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +3 -1
+               reg->var_off = tnum_intersect(reg->var_off,
+                                             tnum_range(reg->smin_value, reg->smax_value));
+       }
  }
 
  static void __reg_deduce_bounds(struct bpf_reg_state *reg)
--

2.43.0

#8 lore raw
Quoted 67 lines · Yonghong Song
Quoted 64 lines · Andrii Nakryiko
Quoted 63 lines · Yonghong Song

With latest llvm19, the selftest iters/iter_arr_with_actual_elem_count failed with -mcpu=v4.

The following are the details:

   0: R1=ctx() R10=fp0
   ; int iter_arr_with_actual_elem_count(const void *ctx) @ iters.c:1420
   0: (b4) w7 = 0                        ; R7_w=0
   ; int i, n = loop_data.n, sum = 0; @ iters.c:1422
   1: (18) r1 = 0xffffc90000191478       ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144)
   3: (61) r6 = *(u32 *)(r1 +128)        ; R1_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) R6_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
   ; if (n > ARRAY_SIZE(loop_data.data)) @ iters.c:1424
   4: (26) if w6 > 0x20 goto pc+27       ; R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))
   5: (bf) r8 = r10                      ; R8_w=fp0 R10=fp0
   6: (07) r8 += -8                      ; R8_w=fp-8
   ; bpf_for(i, 0, n) { @ iters.c:1427
   7: (bf) r1 = r8                       ; R1_w=fp-8 R8_w=fp-8
   8: (b4) w2 = 0                        ; R2_w=0
   9: (bc) w3 = w6                       ; R3_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R6_w=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))
   10: (85) call bpf_iter_num_new#45179          ; R0=scalar() fp-8=iter_num(ref_id=2,state=active,depth=0) refs=2
   11: (bf) r1 = r8                      ; R1=fp-8 R8=fp-8 refs=2
   12: (85) call bpf_iter_num_next#45181 13: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
   ; bpf_for(i, 0, n) { @ iters.c:1427
   13: (15) if r0 == 0x0 goto pc+2       ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
   14: (81) r1 = *(s32 *)(r0 +0)         ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) refs=2
   15: (ae) if w1 < w6 goto pc+4 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=scalar(smin=0xffffffff80000000,smax=smax32=umax32=31,umax=0xffffffff0000001f,smin32=0,var_off=(0x0; 0xffffffff0000001f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
   ; sum += loop_data.data[i]; @ iters.c:1429
   20: (67) r1 <<= 2                     ; R1_w=scalar(smax=0x7ffffffc0000007c,umax=0xfffffffc0000007c,smin32=0,smax32=umax32=124,var_off=(0x0; 0xfffffffc0000007c)) refs=2
   21: (18) r2 = 0xffffc90000191478      ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
   23: (0f) r2 += r1
   math between map_value pointer and register with unbounded min value is not allowed

The source code:

   int iter_arr_with_actual_elem_count(const void *ctx)
   {
         int i, n = loop_data.n, sum = 0;

         if (n > ARRAY_SIZE(loop_data.data))
                 return 0;

         bpf_for(i, 0, n) {
                 /* no rechecking of i against ARRAY_SIZE(loop_data.n) */
                 sum += loop_data.data[i];
         }

         return sum;
   }

The insn #14 is a sign-extenstion load which is related to 'int i'.
The insn #15 did a subreg comparision. Note that smin=0xffffffff80000000 and this caused later insn #23 failed verification due to unbounded min value.

Actually insn #15 R1 smin range can be better. Before insn #15, we have
R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff)
With the above range, we know for R1, upper 32bit can only be 0xffffffff or 0. Otherwise, the value range for R1 could be beyond [smin=0xffffffff80000000,smax=0x7fffffff].

After insn #15, for the true patch, we know smin32=0 and smax32=32. With the upper 32bit 0xffffffff, then the corresponding value is [0xffffffff00000000, 0xffffffff00000020]. The range is obviously beyond the original range [smin=0xffffffff80000000,smax=0x7fffffff] and the range is not possible. So the upper 32bit must be 0, which implies smin = smin32 and smax = smax32.

This patch fixed the issue by adding additional register deduction after 32-bit compare

Quoted 8 lines
Quoted 5 lines

__reg_deduce_mixed_bounds() is called from reg_bounds_sync() pretty much after every arithmetic operation or any comparison. Is the above logic true universally or only after signed comparison? If the latter, then we can't just do it unconditionally inside __reg_deduce_mixed_bounds().

It is not just for signed extension. Some other arithmetic operation may produce such a range as well.

Agreed. It took me a bit to grok this more intuitively, but I think I got there. :)

Quoted 76 lines
Quoted 47 lines
Quoted 47 lines

insn. If the signed 32-bit register range is non-negative then 64-bit smin is in range of [S32_MIN, S32_MAX], then the actual 64-bit smin/smax should be the same as 32-bit smin32/smax32.

With this patch, iters/iter_arr_with_actual_elem_count succeeded with better register range:

from 15 to 20: R0=rdonly_mem(id=7,ref_obj_id=2,sz=4) R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f)) R6=scalar(id=1,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) R7=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R8=scalar(id=9,smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=3) refs=2

---
  kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
  1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +22 -0
index 8da132a1ef28..46532437c4bb 100644
@@ -2182,6 +2182,42 @@ static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg)
                 reg->smin_value = max_t(s64, reg->smin_value, new_smin);
                 reg->smax_value = min_t(s64, reg->smax_value, new_smax);
         }
+
+       /* Here we would like to handle a special case after sign extending load,
+        * when upper bits for a 64-bit range are all 1s or all 0s.
+        *
+        * Upper bits are all 1s when register is in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_ffff_ffff]
+        * Upper bits are all 0s when register is in a range:
+        *   [0x0000_0000_0000_0000, 0x0000_0000_ffff_ffff]
+        * Together this forms are continuous range:
+        *   [0xffff_ffff_0000_0000, 0x0000_0000_ffff_ffff]
+        *
+        * Now, suppose that register range is in fact tighter:
+        *   [0xffff_ffff_8000_0000, 0x0000_0000_ffff_ffff] (R)
+        * Also suppose that it's 32-bit range is positive,
+        * meaning that lower 32-bits of the full 64-bit register
+        * are in the range:
+        *   [0x0000_0000, 0x7fff_ffff] (W)
+        *
+        * If this happens, then any value in a range:
+        *   [0xffff_ffff_0000_0000, 0xffff_ffff_7fff_ffff]
+        * is smaller than a lowest bound of the range (R):
+        *   0xffff_ffff_8000_0000
Quoted 8 lines

kernel/bpf/verifier.c static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) · line 2212

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+        * which means that upper bits of the full 64-bit register
+        * can't be all 1s, when lower bits are in range (W).
+        *
+        * Note that:
+        *  - 0xffff_ffff_8000_0000 == (s64)S32_MIN
+        *  - 0x0000_0000_ffff_ffff == (s64)S32_MAX

?? S32_MAX = 0x7fffffff, so should the right part be U32_MAX or the left part should be 0x0000_0000_7fff_ffff ?

Will make a change in the next revision.

Quoted 9 lines

kernel/bpf/verifier.c static void __reg_deduce_mixed_bounds(struct bpf_reg_state *reg) · line 2217

Quoted 6 lines
kernel/bpf/verifier.c +5 -0
+        * These relations are used in the conditions below.
+        */
+       if (reg->s32_min_value >= 0 && reg->smin_value >= S32_MIN && reg->smax_value <= S32_MAX) {
+               reg->smin_value = reg->umin_value = reg->s32_min_value;
+               reg->smax_value = reg->umax_value = reg->s32_max_value;

let's please not mix signed and unsigned 32 -> 64 bit conversions, they are confusing and tricky enough in each domain individually, there is no point in mixing them

Okay, will do.

Quoted 10 lines
Quoted 10 lines
kernel/bpf/verifier.c +3 -1
+               reg->var_off = tnum_intersect(reg->var_off,
+                                             tnum_range(reg->smin_value, reg->smax_value));
+       }
  }
 
  static void __reg_deduce_bounds(struct bpf_reg_state *reg)
--

2.43.0