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

Commit Message

Yonghong Song July 12, 2024, 11:44 p.m. UTC

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

Signed-off-by: Yonghong Song <[e-mail]>
---
 .../selftests/bpf/progs/verifier_ldsx.c       | 106 ++++++++++++++++++
 1 file changed, 106 insertions(+)

Comments

Eduard Zingerman July 16, 2024, 12:44 a.m. UTC | #1

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.

[...]

> +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)).

> +__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);
> +}

[...]

Yonghong Song July 16, 2024, 10:38 p.m. UTC | #2

On 7/15/24 5:44 PM, Eduard Zingerman wrote:
> 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.

I added some logic in reg_bounds.c.

diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
index eb74363f9f70..c88602908cfe 100644
--- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
+++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
@@ -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?

>
> [...]
>
>> +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)).

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.

>> +__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);
>> +}
> [...]

Eduard Zingerman July 17, 2024, 12:12 a.m. UTC | #3

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

[...]

> diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> index eb74363f9f70..c88602908cfe 100644
> --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
> @@ -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?

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

	return range_improve(x_t, x, y_cast);

[...]

Yonghong Song July 17, 2024, 6:06 a.m. UTC | #4

On 7/16/24 5:12 PM, Eduard Zingerman wrote:
> On Tue, 2024-07-16 at 15:38 -0700, Yonghong Song wrote:
>
> [...]
>
>> diff --git a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
>> index eb74363f9f70..c88602908cfe 100644
>> --- a/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
>> +++ b/tools/testing/selftests/bpf/prog_tests/reg_bounds.c
>> @@ -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?
> 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.

>
> [...]

Patch

diff --git a/tools/testing/selftests/bpf/progs/verifier_ldsx.c b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
index d4427d8e1217..3b96a9436a0c 100644
--- a/tools/testing/selftests/bpf/progs/verifier_ldsx.c
+++ b/tools/testing/selftests/bpf/progs/verifier_ldsx.c
@@ -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")