Skip to contentSkip to conversation

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

PATCH Superseded Yonghong Song 3 participants 8 messages Jul 12, 2024 – Jul 17, 2024

Subsystems (4)

v3 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

PATCH v3 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..40abed6459f3 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)
+	 *
+	 * It 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 v3 2/2 selftests/bpf: Add ldsx selftests for ldsx and subreg compare

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

---
 .../selftests/bpf/progs/verifier_ldsx.c       | 106 ++++++++++++++++++
 1 file changed, 106 insertions(+)
tools/testing/selftests/bpf/progs/verifier_ldsx.c +106 -0
index d4427d8e1217..3b96a9436a0c 100644
@@ -144,6 +144,112 @@ __naked void ldsx_s32_range(void)
 	: __clobber_all);
 }
 
+#define MAX_ENTRIES 12
+
+struct test_val {
+        int foo[MAX_ENTRIES];
+};
+
+struct {
+        __uint(type, BPF_MAP_TYPE_HASH);
+        __uint(max_entries, 1);
+        __type(key, long long);
+        __type(value, struct test_val);
+} map_hash_48b SEC(".maps");
+
+SEC("socket")
+__description("LDSX, S8, subreg compare")
+__success __success_unpriv
+__naked void ldsx_s8_subreg_compare(void)
+{
+	asm volatile (
+	"call %[bpf_get_prandom_u32];"
+	"*(u64 *)(r10 - 8) = r0;"
+	"w6 = w0;"
+	"if w6 > 0x1f goto l0_%=;"
+	"r7 = *(s8 *)(r10 - 8);"
+	"if w7 > w6 goto l0_%=;"
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"r2 = r10;"
+	"r2 += -8;"
+	"r1 = %[map_hash_48b] ll;"
+	"call %[bpf_map_lookup_elem];"
+	"if r0 == 0 goto l0_%=;"
+	"r0 += r7;"
+	"*(u64 *)(r0 + 0) = 1;"
+"l0_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_get_prandom_u32),
+	  __imm_addr(map_hash_48b),
+	  __imm(bpf_map_lookup_elem)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("LDSX, S16, subreg compare")
+__success __success_unpriv
+__naked void ldsx_s16_subreg_compare(void)
+{
+	asm volatile (
+	"call %[bpf_get_prandom_u32];"
+	"*(u64 *)(r10 - 8) = r0;"
+	"w6 = w0;"
+	"if w6 > 0x1f goto l0_%=;"
+	"r7 = *(s16 *)(r10 - 8);"
+	"if w7 > w6 goto l0_%=;"
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"r2 = r10;"
+	"r2 += -8;"
+	"r1 = %[map_hash_48b] ll;"
+	"call %[bpf_map_lookup_elem];"
+	"if r0 == 0 goto l0_%=;"
+	"r0 += r7;"
+	"*(u64 *)(r0 + 0) = 1;"
+"l0_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_get_prandom_u32),
+	  __imm_addr(map_hash_48b),
+	  __imm(bpf_map_lookup_elem)
+	: __clobber_all);
+}
+
+SEC("socket")
+__description("LDSX, S32, subreg compare")
+__success __success_unpriv
+__naked void ldsx_s32_subreg_compare(void)
+{
+	asm volatile (
+	"call %[bpf_get_prandom_u32];"
+	"*(u64 *)(r10 - 8) = r0;"
+	"w6 = w0;"
+	"if w6 > 0x1f goto l0_%=;"
+	"r7 = *(s32 *)(r10 - 8);"
+	"if w7 > w6 goto l0_%=;"
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"r2 = r10;"
+	"r2 += -8;"
+	"r1 = %[map_hash_48b] ll;"
+	"call %[bpf_map_lookup_elem];"
+	"if r0 == 0 goto l0_%=;"
+	"r0 += r7;"
+	"*(u64 *)(r0 + 0) = 1;"
+"l0_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_get_prandom_u32),
+	  __imm_addr(map_hash_48b),
+	  __imm(bpf_map_lookup_elem)
+	: __clobber_all);
+}
+
 #else
 
 SEC("socket")
Signature · 1 line
2.43.0
maintainer
#2 lore raw

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

On Fri, 2024-07-12 at 16:44 -0700, Yonghong Song wrote:

Note: it feels like these test cases should be a part of the

      reg_bounds.c:test_reg_bounds_crafted(), e.g.:

diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c index eb74363f9f70..4918414f8e36 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c

  @@ -2108,6 +2108,7 @@ 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, 0x00000000ffffffffULL}},
};

/* Go over crafted hard-coded cases. This is fast, so we do it as part of

Which produces the following log:

VERIFIER LOG:
========================
...
21: (ae) if w6 < w7 goto pc+3 ; R6=scalar(id=1,smin=0xffffffff80000000,smax=0xffffffff)

                                          R7=scalar(id=2,smin=smin32=0,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f))
  ...  
  from 21 to 25: ... R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=30,var_off=(0x0; 0x1f))
                     R7=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f)
  25: ... R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=30,var_off=(0x0; 0x1f))
          R7=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f))

...

However, this would require adjustments to reg_bounds.c logic to include this new range rule.

[...]

tools/testing/selftests/bpf/progs/verifier_ldsx.c __naked void ldsx_s32_range(void) · line 161

Quoted 2 lines
tools/testing/selftests/bpf/progs/verifier_ldsx.c +2 -0
+SEC("socket")
+__description("LDSX, S8, subreg compare")
                     ^^^ ^^^

Nit: test_progs parsing logic for -t option is too simplistic to
understand comas inside description, for example here is happens after the command below:

# ./test_progs-cpuv4 -t "verifier_ldsx/LDSX, S8, subreg compare"
#455/1 verifier_ldsx/LDSX, S8:OK
#455/2 verifier_ldsx/LDSX, S8 @unpriv:OK
#455/3 verifier_ldsx/LDSX, S16:OK
#455/4 verifier_ldsx/LDSX, S16 @unpriv:OK
#455/5 verifier_ldsx/LDSX, S32:OK
...

As far as I understand, this happens because test_progs tries to match words LDSX, S8 and "subreg compare" separately.

This does not happen when comas are not used in the description (or if description is omitted in favor of the C function name of the test
(it is not possible to do -t verifier_ldsx/ldsx_s8_subreg_compare
if __description is provided)).

Quoted 28 lines
tools/testing/selftests/bpf/progs/verifier_ldsx.c +28 -0
+__success __success_unpriv
+__naked void ldsx_s8_subreg_compare(void)
+{
+	asm volatile (
+	"call %[bpf_get_prandom_u32];"
+	"*(u64 *)(r10 - 8) = r0;"
+	"w6 = w0;"
+	"if w6 > 0x1f goto l0_%=;"
+	"r7 = *(s8 *)(r10 - 8);"
+	"if w7 > w6 goto l0_%=;"
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"r2 = r10;"
+	"r2 += -8;"
+	"r1 = %[map_hash_48b] ll;"
+	"call %[bpf_map_lookup_elem];"
+	"if r0 == 0 goto l0_%=;"
+	"r0 += r7;"
+	"*(u64 *)(r0 + 0) = 1;"
+"l0_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_get_prandom_u32),
+	  __imm_addr(map_hash_48b),
+	  __imm(bpf_map_lookup_elem)
+	: __clobber_all);
+}

[...]

author reviewer
#3 lore raw

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

Quoted 32 lines · Eduard Zingerman

On Fri, 2024-07-12 at 16:44 -0700, Yonghong Song wrote:

Note: it feels like these test cases should be a part of the

       reg_bounds.c:test_reg_bounds_crafted(), e.g.:
   diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
   index eb74363f9f70..4918414f8e36 100644
   --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
   +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
   @@ -2108,6 +2108,7 @@ 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, 0x00000000ffffffffULL}},
    };
    
    /* Go over crafted hard-coded cases. This is fast, so we do it as part of

Which produces the following log:

   VERIFIER LOG:
   ========================
   ...
   21: (ae) if w6 < w7 goto pc+3         ; R6=scalar(id=1,smin=0xffffffff80000000,smax=0xffffffff)
                                           R7=scalar(id=2,smin=smin32=0,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f))
   ...
   from 21 to 25: ... R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=30,var_off=(0x0; 0x1f))
                      R7=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f)
   25: ... R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=30,var_off=(0x0; 0x1f))
           R7=scalar(id=2,smin=umin=smin32=umin32=1,smax=umax=smax32=umax32=31,var_off=(0x0; 0x1f))
   ...
Quoted 2 lines

However, this would require adjustments to reg_bounds.c logic to include this new range rule.

I added some logic in reg_bounds.c.

tools/testing/selftests/bpf/prog_tests/reg_bounds.c +19 -0
index eb74363f9f70..c88602908cfe 100644
@@ -441,6 +441,22 @@ 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(S64, max_t(S64, y_cast.a, x.a),
+                                            min_t(S64, y_cast.b, x.b));
+               }
+
                /* 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 +2124,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

The logic is very similar to kernel implementation but has a difference in generating the final range. In reg_bounds implementation, the range is narrowed by intersecting y_cast and x range which are necessary.

In kernel implementation, there is no interection since we only have one register and two register has been compared before.

Eduard, could you take a look at the above code?

Quoted 19 lines

[...]

Review

Quoted 2 lines
(quoted diff) +2 -0
+SEC("socket")
+__description("LDSX, S8, subreg compare")
                      ^^^ ^^^

Nit: test_progs parsing logic for -t option is too simplistic to
understand comas inside description, for example here is happens after the command below:

# ./test_progs-cpuv4 -t "verifier_ldsx/LDSX, S8, subreg compare"
#455/1 verifier_ldsx/LDSX, S8:OK
#455/2 verifier_ldsx/LDSX, S8 @unpriv:OK
#455/3 verifier_ldsx/LDSX, S16:OK
#455/4 verifier_ldsx/LDSX, S16 @unpriv:OK
#455/5 verifier_ldsx/LDSX, S32:OK
...

Quoted 7 lines

As far as I understand, this happens because test_progs tries to match words LDSX, S8 and "subreg compare" separately.

This does not happen when comas are not used in the description (or if description is omitted in favor of the C function name of the test
(it is not possible to do -t verifier_ldsx/ldsx_s8_subreg_compare
if __description is provided)).

There are around 10 (or more) verifier_*.c files which has ',' in their description. So I think we should add ',' support in test_progs infrastructure w.r.t. description tag. I think this can be a follow up.

Quoted 29 lines
Quoted 28 lines
(quoted diff) +28 -0
+__success __success_unpriv
+__naked void ldsx_s8_subreg_compare(void)
+{
+	asm volatile (
+	"call %[bpf_get_prandom_u32];"
+	"*(u64 *)(r10 - 8) = r0;"
+	"w6 = w0;"
+	"if w6 > 0x1f goto l0_%=;"
+	"r7 = *(s8 *)(r10 - 8);"
+	"if w7 > w6 goto l0_%=;"
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"r2 = r10;"
+	"r2 += -8;"
+	"r1 = %[map_hash_48b] ll;"
+	"call %[bpf_map_lookup_elem];"
+	"if r0 == 0 goto l0_%=;"
+	"r0 += r7;"
+	"*(u64 *)(r0 + 0) = 1;"
+"l0_%=:"
+	"r0 = 0;"
+	"exit;"
+	:
+	: __imm(bpf_get_prandom_u32),
+	  __imm_addr(map_hash_48b),
+	  __imm(bpf_map_lookup_elem)
+	: __clobber_all);
+}

[...]

maintainer
#4 lore raw

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

On Tue, 2024-07-16 at 15:38 -0700, Yonghong Song wrote:

[...]

Quoted 38 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +19 -0
index eb74363f9f70..c88602908cfe 100644
@@ -441,6 +441,22 @@ 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(S64, max_t(S64, y_cast.a, x.a),
+                                            min_t(S64, y_cast.b, x.b));
+               }
+
                 /* 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 +2124,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
Quoted 8 lines

The logic is very similar to kernel implementation but has a difference in generating the final range. In reg_bounds implementation, the range is narrowed by intersecting y_cast and x range which are necessary.

In kernel implementation, there is no interection since we only have one register and two register has been compared before.

Eduard, could you take a look at the above code?

I think this change is correct.
The return clause could be simplified a bit:

	return range_improve(x_t, x, y_cast);

[...]

author reviewer
#5 lore raw

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

Quoted 46 lines · Eduard Zingerman

On Tue, 2024-07-16 at 15:38 -0700, Yonghong Song wrote:

[...]

Quoted 42 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +19 -0
index eb74363f9f70..c88602908cfe 100644
@@ -441,6 +441,22 @@ 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(S64, max_t(S64, y_cast.a, x.a),
+                                            min_t(S64, y_cast.b, x.b));
+               }
+
                  /* 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 +2124,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

The logic is very similar to kernel implementation but has a difference in generating the final range. In reg_bounds implementation, the range is narrowed by intersecting y_cast and x range which are necessary.

Quoted 8 lines
Quoted 4 lines

In kernel implementation, there is no interection since we only have one register and two register has been compared before.

Eduard, could you take a look at the above code?

I think this change is correct.
The return clause could be simplified a bit:

	return range_improve(x_t, x, y_cast);

Indeed. This is much simpler. I will use reg_bounds testing instead of verifier_ldsx testing in next revision.

Quoted 2 lines

[...]

maintainer Acked-by on v3 1/2
#6 lore raw
In reply to Yonghong Song

On Fri, 2024-07-12 at 16:43 -0700, Yonghong Song wrote:

[...]

Quoted 4 lines

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.

[...]

[...]

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

Quoted 8 lines
kernel/bpf/verifier.c +8 -0
+	 * 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)
+	 *
+	 * It this happens, then any value in a range:
           ^^

Sorry, one more typo, should be "If".
Maybe could be changed when the patch would be applied.

[...]

Acked-by
#7 lore raw
Quoted 4 lines · Eduard Zingerman

On Fri, 2024-07-12 at 16:43 -0700, Yonghong Song wrote:

[...]

Quoted 8 lines
Quoted 4 lines

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.

[...]

Other than the already mentioned typo LGTM,

Quoted 15 lines

[...]

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

Quoted 8 lines
kernel/bpf/verifier.c +8 -0
+	 * 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)
+	 *
+	 * It this happens, then any value in a range:
           ^^

Sorry, one more typo, should be "If".
Maybe could be changed when the patch would be applied.

[...]