Skip to contentSkip to conversation

selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4

PATCH In review Yonghong Song 4 participants 15 messages Jul 8, 2024 – Jul 9, 2024

Subsystems (4)
lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

PATCH 1/1 selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4

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 smin range can be better. Since after comparison, we know smin32=0 and smax32=32. With insn #14 being a sign-extension load. We will know top 32bits should be 0 as well. Current verifier is not able to handle this, and this patch is a workaround to fix test failure by changing variable 'i' type from 'int' to 'unsigned' which will give proper range during comparison.

; bpf_for(i, 0, n) { @ iters.c:1428
13: (15) if r0 == 0x0 goto pc+2 ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
14: (61) r1 = *(u32 *)(r0 +0) ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) refs=2
...
from 15 to 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=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:1430
20: (67) r1 <<= 2 ; R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=124,var_off=(0x0; 0x7c)) refs=2
21: (18) r2 = 0xffffc90000185478 ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
23: (0f) r2 += r1
mark_precise: frame0: last_idx 23 first_idx 20 subseq_idx -1
...

---
 tools/testing/selftests/bpf/progs/iters.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/iters.c +2 -1
index 16bdc3e25591..d1801d151a12 100644
@@ -1419,7 +1419,8 @@ SEC("raw_tp")
 __success
 int iter_arr_with_actual_elem_count(const void *ctx)
 {
-	int i, n = loop_data.n, sum = 0;
+	unsigned i;
+	int n = loop_data.n, sum = 0;
 
 	if (n > ARRAY_SIZE(loop_data.data))
 		return 0;
Signature · 1 line
2.43.0
#1 lore raw
Quoted 81 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 smin range can be better. Since after comparison, we know smin32=0 and smax32=32. With insn #14 being a sign-extension load. We will know top 32bits should be 0 as well. Current verifier is not able to handle this, and this patch is a workaround to fix test failure by changing variable 'i' type from 'int' to 'unsigned' which will give proper range during comparison.

; bpf_for(i, 0, n) { @ iters.c:1428
13: (15) if r0 == 0x0 goto pc+2 ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
14: (61) r1 = *(u32 *)(r0 +0) ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) refs=2
...
from 15 to 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=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:1430
20: (67) r1 <<= 2 ; R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=124,var_off=(0x0; 0x7c)) refs=2
21: (18) r2 = 0xffffc90000185478 ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
23: (0f) r2 += r1
mark_precise: frame0: last_idx 23 first_idx 20 subseq_idx -1
...

---
 tools/testing/selftests/bpf/progs/iters.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/iters.c +0 -0
index 16bdc3e25591..d1801d151a12 100644

tools/testing/selftests/bpf/progs/iters.c SEC("raw_tp") · line 1426

Quoted 9 lines
tools/testing/selftests/bpf/progs/iters.c +2 -1
@@ -1419,7 +1419,8 @@ SEC("raw_tp")
 __success
 int iter_arr_with_actual_elem_count(const void *ctx)
 {
-       int i, n = loop_data.n, sum = 0;
+       unsigned i;
+       int n = loop_data.n, sum = 0;
 
        if (n > ARRAY_SIZE(loop_data.data))
                return 0;

I think we only have one realistic test that checks 'range vs range' verifier logic.
Since "int i; bpf_for(i"
is a very common pattern in all other bpf_for tests it feels wrong to workaround like this.

What exactly needs to be improved in 'range vs range' logic to handle this case?

author reviewer
#2 lore raw
Quoted 88 lines · Alexei Starovoitov
Quoted 87 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 smin range can be better. Since after comparison, we know smin32=0 and smax32=32. With insn #14 being a sign-extension load. We will know top 32bits should be 0 as well. Current verifier is not able to handle this, and this patch is a workaround to fix test failure by changing variable 'i' type from 'int' to 'unsigned' which will give proper range during comparison.

   ; bpf_for(i, 0, n) { @ iters.c:1428
   13: (15) if r0 == 0x0 goto pc+2       ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
   14: (61) r1 = *(u32 *)(r0 +0)         ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) refs=2
   ...
   from 15 to 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
   20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=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:1430
   20: (67) r1 <<= 2                     ; R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=124,var_off=(0x0; 0x7c)) refs=2
   21: (18) r2 = 0xffffc90000185478      ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
   23: (0f) r2 += r1
   mark_precise: frame0: last_idx 23 first_idx 20 subseq_idx -1
   ...
---
  tools/testing/selftests/bpf/progs/iters.c | 3 ++-
  1 file changed, 2 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/iters.c +2 -1
index 16bdc3e25591..d1801d151a12 100644
@@ -1419,7 +1419,8 @@ SEC("raw_tp")
  __success
  int iter_arr_with_actual_elem_count(const void *ctx)
  {
-       int i, n = loop_data.n, sum = 0;
+       unsigned i;
+       int n = loop_data.n, sum = 0;
 
Quoted 7 lines

tools/testing/selftests/bpf/progs/iters.c SEC("raw_tp") · line 1426

Quoted 2 lines
tools/testing/selftests/bpf/progs/iters.c +0 -0
         if (n > ARRAY_SIZE(loop_data.data))
                 return 0;

I think we only have one realistic test that checks 'range vs range' verifier logic.
Since "int i; bpf_for(i"
is a very common pattern in all other bpf_for tests it feels wrong to workaround like this.

Agree. We should fix this in verifier to be user friendly.

Quoted 3 lines

What exactly needs to be improved in 'range vs range' logic to handle this case?

We can add a bit in struct bpf_reg_state like below

	struct bpf_reg_state {
		...
		enum bpf_reg_liveness live;
		bool precise;
	}
to
	struct bpf_reg_state {
		...
		enum bpf_reg_liveness live;
		unsigned precise:1;
		unsigned 32bit_sign_ext:1;  /* for *(s32 *)(...) */
	}

When the insn 15 is processed with 'true' branch
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

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.
call bpf_get_prandom_u32;
r1 = r0;
r1 <<= 32;
call bpf_get_prandom_u32;
r1 |= r0; /* r1 is 64bit random number */
r2 = 0xffffffff80000000 ll;
if r1 s< r2 goto end;
if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
if w1 < w6 goto end;
... <=== w1 range [0,31]

       <=== but if we have upper bit as 0xffffffff........, then the range will be
       <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
       <=== so the only possible way for upper 32bit range is 0.

end:

Therefore, looks like we do not need 32bit_sign_exit. Just from R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) with refined range in true path of 'if w1 < w6 goto ...', we can further refine w1 range properly.

#3 lore raw
Quoted 128 lines · Yonghong Song
Quoted 88 lines · Alexei Starovoitov
Quoted 87 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 smin range can be better. Since after comparison, we know smin32=0 and smax32=32. With insn #14 being a sign-extension load. We will know top 32bits should be 0 as well. Current verifier is not able to handle this, and this patch is a workaround to fix test failure by changing variable 'i' type from 'int' to 'unsigned' which will give proper range during comparison.

   ; bpf_for(i, 0, n) { @ iters.c:1428
   13: (15) if r0 == 0x0 goto pc+2       ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
   14: (61) r1 = *(u32 *)(r0 +0)         ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) refs=2
   ...
   from 15 to 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
   20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=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:1430
   20: (67) r1 <<= 2                     ; R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=124,var_off=(0x0; 0x7c)) refs=2
   21: (18) r2 = 0xffffc90000185478      ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
   23: (0f) r2 += r1
   mark_precise: frame0: last_idx 23 first_idx 20 subseq_idx -1
   ...
---
  tools/testing/selftests/bpf/progs/iters.c | 3 ++-
  1 file changed, 2 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/iters.c +2 -1
index 16bdc3e25591..d1801d151a12 100644
@@ -1419,7 +1419,8 @@ SEC("raw_tp")
  __success
  int iter_arr_with_actual_elem_count(const void *ctx)
  {
-       int i, n = loop_data.n, sum = 0;
+       unsigned i;
+       int n = loop_data.n, sum = 0;
 
Quoted 7 lines

tools/testing/selftests/bpf/progs/iters.c SEC("raw_tp") · line 1426

Quoted 2 lines
tools/testing/selftests/bpf/progs/iters.c +0 -0
         if (n > ARRAY_SIZE(loop_data.data))
                 return 0;

I think we only have one realistic test that checks 'range vs range' verifier logic.
Since "int i; bpf_for(i"
is a very common pattern in all other bpf_for tests it feels wrong to workaround like this.

Agree. We should fix this in verifier to be user friendly.

Quoted 3 lines

What exactly needs to be improved in 'range vs range' logic to handle this case?

We can add a bit in struct bpf_reg_state like below

        struct bpf_reg_state {
                ...
                enum bpf_reg_liveness live;
                bool precise;
        }
to
        struct bpf_reg_state {
                ...
                enum bpf_reg_liveness live;
                unsigned precise:1;
                unsigned 32bit_sign_ext:1;  /* for *(s32 *)(...) */
        }

When the insn 15 is processed with 'true' branch
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

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 7 lines
        <=== so the only possible way for upper 32bit range is 0.

end:

Therefore, looks like we do not need 32bit_sign_exit. Just from R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) with refined range in true path of 'if w1 < w6 goto ...', we can further refine w1 range properly.

yep. looks like it.
We can hard code this special logic for this specific smin/smax pair, but the gut feel is that we can generalize it further.

author reviewer
#4 lore raw
Quoted 137 lines · Alexei Starovoitov
Quoted 124 lines · Yonghong Song
Quoted 88 lines · Alexei Starovoitov
Quoted 87 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 smin range can be better. Since after comparison, we know smin32=0 and smax32=32. With insn #14 being a sign-extension load. We will know top 32bits should be 0 as well. Current verifier is not able to handle this, and this patch is a workaround to fix test failure by changing variable 'i' type from 'int' to 'unsigned' which will give proper range during comparison.

    ; bpf_for(i, 0, n) { @ iters.c:1428
    13: (15) if r0 == 0x0 goto pc+2       ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) refs=2
    14: (61) r1 = *(u32 *)(r0 +0)         ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) refs=2
    ...
    from 15 to 20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=0 R8=fp-8 R10=fp0 fp-8=iter_num(ref_id=2,state=active,depth=1) refs=2
    20: R0=rdonly_mem(id=3,ref_obj_id=2,sz=4) R1=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=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:1430
    20: (67) r1 <<= 2                     ; R1_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=124,var_off=(0x0; 0x7c)) refs=2
    21: (18) r2 = 0xffffc90000185478      ; R2_w=map_value(map=iters.bss,ks=4,vs=1280,off=1144) refs=2
    23: (0f) r2 += r1
    mark_precise: frame0: last_idx 23 first_idx 20 subseq_idx -1
    ...
---
   tools/testing/selftests/bpf/progs/iters.c | 3 ++-
   1 file changed, 2 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/iters.c +2 -1
index 16bdc3e25591..d1801d151a12 100644
@@ -1419,7 +1419,8 @@ SEC("raw_tp")
   __success
   int iter_arr_with_actual_elem_count(const void *ctx)
   {
-       int i, n = loop_data.n, sum = 0;
+       unsigned i;
+       int n = loop_data.n, sum = 0;
 
Quoted 7 lines

tools/testing/selftests/bpf/progs/iters.c SEC("raw_tp") · line 1426

Quoted 2 lines
tools/testing/selftests/bpf/progs/iters.c +0 -0
          if (n > ARRAY_SIZE(loop_data.data))
                  return 0;

I think we only have one realistic test that checks 'range vs range' verifier logic.
Since "int i; bpf_for(i"
is a very common pattern in all other bpf_for tests it feels wrong to workaround like this.

Agree. We should fix this in verifier to be user friendly.

Quoted 2 lines

What exactly needs to be improved in 'range vs range' logic to handle this case?

We can add a bit in struct bpf_reg_state like below

         struct bpf_reg_state {
                 ...
                 enum bpf_reg_liveness live;
                 bool precise;
         }
to
         struct bpf_reg_state {
                 ...
                 enum bpf_reg_liveness live;
                 unsigned precise:1;
                 unsigned 32bit_sign_ext:1;  /* for *(s32 *)(...) */
         }
When the insn 15 is processed with 'true' branch
    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

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
    call bpf_get_prandom_u32;
    r1 = r0;
    r1 <<= 32;
    call bpf_get_prandom_u32;
    r1 |= r0;  /* r1 is 64bit random number */
    r2 = 0xffffffff80000000 ll;
    if r1 s< r2 goto end;
    if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
    if w1 < w6 goto end;
    ...  <=== w1 range [0,31]
         <=== but if we have upper bit as 0xffffffff........, then the range will be
         <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Right.

Quoted 11 lines
Quoted 8 lines
         <=== so the only possible way for upper 32bit range is 0.

end:

Therefore, looks like we do not need 32bit_sign_exit. Just from R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) with refined range in true path of 'if w1 < w6 goto ...', we can further refine w1 range properly.

yep. looks like it.
We can hard code this special logic for this specific smin/smax pair, but the gut feel is that we can generalize it further.

Great. Let me try to implement such a logic in verifier.

maintainer
#5 lore raw
In reply to Alexei Starovoitov

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 19 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Sorry, could you please explain this a bit more.
The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have 0xffffFFFF for upper bits => r1 += r2 would fail.
What do I miss?

The non-cpuv4 version of the program does non-sign-extended load:

14: (61) r1 = *(u32 *)(r0 +0) ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4)

                                  R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
15: (ae) if w1 < w6 goto pc+4   ; R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
                                  R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))

Tbh, it looks like LLVM deleted some info that could not be recovered in this instance.

Quoted 13 lines
Quoted 8 lines
        <=== so the only possible way for upper 32bit range is 0.

end:

Therefore, looks like we do not need 32bit_sign_exit. Just from R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) with refined range in true path of 'if w1 < w6 goto ...', we can further refine w1 range properly.

yep. looks like it.
We can hard code this special logic for this specific smin/smax pair, but the gut feel is that we can generalize it further.

#6 lore raw
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 19 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 1 line

Sorry, could you please explain this a bit more.

Yep, also curious.

But meanwhile, I'm intending to update bpf_for() to something like below to avoid this code generation pattern:

tools/lib/bpf/bpf_helpers.h +0 -0
index 305c62817dd3..86dc854a713b 100644
@@ -394,7 +394,18 @@ extern void bpf_iter_num_destroy(struct
bpf_iter_num *it) __weak __ksym;
                /* iteration step */
                         \
                int *___t = bpf_iter_num_next(&___it);
                         \
                /* termination and bounds check */
                         \
-               (___t && ((i) = *___t, (i) >= (start) && (i) <
(end)));                         \
+               (___t && ({
                         \
+                       __label__ l_false;
                         \
+                       _Bool ok = 0;
                         \
+                       (i) = *___t;
                         \
+                       asm volatile goto ("
                         \
+                               if %[_i] s< %[_start] goto
%l[l_false];                         \
+                               if %[_i] s>= %[_end] goto %l[l_false];
                         \
+                       " :: [_i]"r"(i), [_start]"ri"(start),
[_end]"ri"(end) :: l_false);      \
+                       ok = 1;
                         \
+               l_false:
                         \
+                       ok;
                         \
+               }));
                         \
        });
                         \

)
#endif /* bpf_for */

This produces this code for cpuv4:

    1294:       85 10 00 00 ff ff ff ff call -0x1
    1295:       15 00 10 00 00 00 00 00 if r0 == 0x0 goto +0x10 <LBB34_4>
    1296:       61 01 00 00 00 00 00 00 r1 = *(u32 *)(r0 + 0x0)
    1297:       c5 01 0e 00 00 00 00 00 if r1 s< 0x0 goto +0xe <LBB34_4>
    1298:       7d 71 0d 00 00 00 00 00 if r1 s>= r7 goto +0xd <LBB34_4>
    1299:       bf 11 20 00 00 00 00 00 r1 = (s32)r1
Quoted 29 lines

The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have 0xffffFFFF for upper bits => r1 += r2 would fail.
What do I miss?

The non-cpuv4 version of the program does non-sign-extended load:

14: (61) r1 = *(u32 *)(r0 +0) ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4)

                                  R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
15: (ae) if w1 < w6 goto pc+4   ; R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
                                  R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))

Tbh, it looks like LLVM deleted some info that could not be recovered in this instance.

Quoted 13 lines
Quoted 8 lines
        <=== so the only possible way for upper 32bit range is 0.

end:

Therefore, looks like we do not need 32bit_sign_exit. Just from R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) with refined range in true path of 'if w1 < w6 goto ...', we can further refine w1 range properly.

yep. looks like it.
We can hard code this special logic for this specific smin/smax pair, but the gut feel is that we can generalize it further.

#7 lore raw
Quoted 34 lines · Andrii Nakryiko
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 26 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 7 lines
Quoted 1 line

Sorry, could you please explain this a bit more.

Yep, also curious.

But meanwhile, I'm intending to update bpf_for() to something like below to avoid this code generation pattern:

Well, thank you, Gmail, for messed up formatting. See [0] for properly formatted diff.

[0] https://gist.github.com/anakryiko/08a4374259469803af4ea2185296b0cb

Quoted 39 lines

This produces this code for cpuv4:

    1294:       85 10 00 00 ff ff ff ff call -0x1
    1295:       15 00 10 00 00 00 00 00 if r0 == 0x0 goto +0x10 <LBB34_4>
    1296:       61 01 00 00 00 00 00 00 r1 = *(u32 *)(r0 + 0x0)
    1297:       c5 01 0e 00 00 00 00 00 if r1 s< 0x0 goto +0xe <LBB34_4>
    1298:       7d 71 0d 00 00 00 00 00 if r1 s>= r7 goto +0xd <LBB34_4>
    1299:       bf 11 20 00 00 00 00 00 r1 = (s32)r1
Quoted 29 lines

The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have 0xffffFFFF for upper bits => r1 += r2 would fail.
What do I miss?

The non-cpuv4 version of the program does non-sign-extended load:

14: (61) r1 = *(u32 *)(r0 +0) ; R0=rdonly_mem(id=3,ref_obj_id=2,sz=4)

                                  R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
15: (ae) if w1 < w6 goto pc+4   ; R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff))
                                  R6=scalar(id=1,smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f))

Tbh, it looks like LLVM deleted some info that could not be recovered in this instance.

Quoted 13 lines
Quoted 8 lines
        <=== so the only possible way for upper 32bit range is 0.

end:

Therefore, looks like we do not need 32bit_sign_exit. Just from R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) with refined range in true path of 'if w1 < w6 goto ...', we can further refine w1 range properly.

yep. looks like it.
We can hard code this special logic for this specific smin/smax pair, but the gut feel is that we can generalize it further.

#8 lore raw
Quoted 41 lines · Andrii Nakryiko
Quoted 38 lines · Andrii Nakryiko
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 19 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 1 line

Sorry, could you please explain this a bit more.

Yep, also curious.

Quoted 8 lines
Quoted 3 lines

But meanwhile, I'm intending to update bpf_for() to something like below to avoid this code generation pattern:

Well, thank you, Gmail, for messed up formatting. See [0] for properly formatted diff.

[0] https://gist.github.com/anakryiko/08a4374259469803af4ea2185296b0cb

Not that simple. It needs sizeof(start)==8 extra hack like bpf_cmp(). And the same with 'end'. So it will get just as ugly. Let's make the verifier smarter instead.

#9 lore raw
Quoted 48 lines · Alexei Starovoitov
Quoted 45 lines · Andrii Nakryiko
Quoted 41 lines · Andrii Nakryiko
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 19 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 1 line

Sorry, could you please explain this a bit more.

Yep, also curious.

But meanwhile, I'm intending to update bpf_for() to something like below to avoid this code generation pattern:

Quoted 6 lines
Quoted 4 lines

Well, thank you, Gmail, for messed up formatting. See [0] for properly formatted diff.

[0] https://gist.github.com/anakryiko/08a4374259469803af4ea2185296b0cb

Not that simple. It needs sizeof(start)==8 extra hack like bpf_cmp().

I'm forgetting the details, but I feel like sizeof() == 4 was important for bpf_cmp() to compare wX registers instead of always comparing Rx. But in this case I think we are fine with always working with full 64-bit Rx registers. Or is there some correctness issue involved?

Quoted 2 lines

And the same with 'end'. So it will get just as ugly. Let's make the verifier smarter instead.

Oh, absolutely, let's. But that doesn't solve the problem of someone using bpf_for() with the latest Clang on an older kernel that doesn't yet have this smartness, does it? Which is why I want to mitigate that on the bpf_for() side in addition to improvements on the verifier side.

#10 lore raw
Quoted 56 lines · Andrii Nakryiko
Quoted 53 lines · Alexei Starovoitov
Quoted 49 lines · Andrii Nakryiko
Quoted 34 lines · Andrii Nakryiko
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 26 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 7 lines
Quoted 1 line

Sorry, could you please explain this a bit more.

Yep, also curious.

But meanwhile, I'm intending to update bpf_for() to something like below to avoid this code generation pattern:

Well, thank you, Gmail, for messed up formatting. See [0] for properly formatted diff.

[0] https://gist.github.com/anakryiko/08a4374259469803af4ea2185296b0cb

Quoted 7 lines
Quoted 1 line

Not that simple. It needs sizeof(start)==8 extra hack like bpf_cmp().

I'm forgetting the details, but I feel like sizeof() == 4 was important for bpf_cmp() to compare wX registers instead of always comparing Rx. But in this case I think we are fine with always working with full 64-bit Rx registers. Or is there some correctness issue involved?

it's a correctness issue.
sizeof()==8 has to go via "r" otherwise it's a silent truncation by llvm.

Quoted 8 lines
Quoted 2 lines

And the same with 'end'. So it will get just as ugly. Let's make the verifier smarter instead.

Oh, absolutely, let's. But that doesn't solve the problem of someone using bpf_for() with the latest Clang on an older kernel that doesn't yet have this smartness, does it? Which is why I want to mitigate that on the bpf_for() side in addition to improvements on the verifier side.

There is no urgency here.
Here it's a combination of the very latest llvm trunk and -mcpu=v4. -mcpu=v4 is rare. Users can continue with -mcpu=v3 or released llvm.

#11 lore raw
Quoted 80 lines · Alexei Starovoitov
Quoted 56 lines · Andrii Nakryiko
Quoted 53 lines · Alexei Starovoitov
Quoted 49 lines · Andrii Nakryiko
Quoted 34 lines · Andrii Nakryiko
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 26 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 7 lines
Quoted 1 line

Sorry, could you please explain this a bit more.

Yep, also curious.

But meanwhile, I'm intending to update bpf_for() to something like below to avoid this code generation pattern:

Well, thank you, Gmail, for messed up formatting. See [0] for properly formatted diff.

[0] https://gist.github.com/anakryiko/08a4374259469803af4ea2185296b0cb

Quoted 7 lines
Quoted 1 line

Not that simple. It needs sizeof(start)==8 extra hack like bpf_cmp().

I'm forgetting the details, but I feel like sizeof() == 4 was important for bpf_cmp() to compare wX registers instead of always comparing Rx. But in this case I think we are fine with always working with full 64-bit Rx registers. Or is there some correctness issue involved?

it's a correctness issue.
sizeof()==8 has to go via "r" otherwise it's a silent truncation by llvm.

Quoted 8 lines
Quoted 2 lines

And the same with 'end'. So it will get just as ugly. Let's make the verifier smarter instead.

Oh, absolutely, let's. But that doesn't solve the problem of someone using bpf_for() with the latest Clang on an older kernel that doesn't yet have this smartness, does it? Which is why I want to mitigate that on the bpf_for() side in addition to improvements on the verifier side.

Quoted 3 lines

There is no urgency here.
Here it's a combination of the very latest llvm trunk and -mcpu=v4. -mcpu=v4 is rare. Users can continue with -mcpu=v3 or released llvm.

Ok, fair enough, I can hold off on this for now (though eventually people will switch and will want to run on old kernels, so the problem doesn't really go away).

But really it's quite annoying that we don't have a proper way to just say "give me whatever register makes sense so I can embed it in the assembly and do something simple with it".

Yonghong, Eduard, is this something that can be figured out to let us do straightforward pieces of embedded assembly like bpf_cmp() or this bpf_for() hack?

#12 lore raw
In reply to Eduard Zingerman
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 19 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 5 lines

Sorry, could you please explain this a bit more.
The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have 0xffffFFFF for upper bits => r1 += r2 would fail.
What do I miss?

Not sure how to rephrase the above differently...
Because smin=0xffffffff80000000...
so full reg cannot be 0xffffFFFF0...123
so when lower 32-bit are compared with unsigned and range of rhs is less than 8000000 it means that the upper 32-bit of full reg are zero.

#13 lore raw
Quoted 40 lines · Alexei Starovoitov
Quoted 32 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 19 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Quoted 5 lines

Sorry, could you please explain this a bit more.
The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have 0xffffFFFF for upper bits => r1 += r2 would fail.
What do I miss?

Quoted 5 lines

Not sure how to rephrase the above differently...
Because smin=0xffffffff80000000...
so full reg cannot be 0xffffFFFF0...123
so when lower 32-bit are compared with unsigned and range of rhs is less than 8000000 it means that the upper 32-bit of full reg are zero.

yep, I think that makes sense. This has to be a special case when the upper 32 bits are either all zeroes or ones, right?

#14 lore raw
Quoted 43 lines · Andrii Nakryiko
Quoted 40 lines · Alexei Starovoitov
Quoted 37 lines · Eduard Zingerman

On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:

[...]

Quoted 19 lines
Quoted 6 lines

the 32bit_sign_ext will indicate the register r1 is from 32bit sign extension, so once w1 range is refined, the upper 32bit can be recalculated.

Can we avoid 32bit_sign_exit in the above? Let us say we have
r1 = ...; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff), R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=32,var_off=(0x0; 0x3f)) if w1 < w6 goto pc+4
where r1 achieves is trange through other means than 32bit sign extension e.g.

Quoted 12 lines
   call bpf_get_prandom_u32;
   r1 = r0;
   r1 <<= 32;
   call bpf_get_prandom_u32;
   r1 |= r0;  /* r1 is 64bit random number */
   r2 = 0xffffffff80000000 ll;
   if r1 s< r2 goto end;
   if r1 s> 0x7fffFFFF goto end; /* after this r1 range (smin=0xffffffff80000000,smax=0x7fffffff) */
   if w1 < w6 goto end;
   ...  <=== w1 range [0,31]
        <=== but if we have upper bit as 0xffffffff........, then the range will be
        <=== [0xffffffff0000001f, 0xffffffff00000000] and this range is not possible compared to original r1 range.
Quoted 7 lines

Just rephrasing for myself...
Because smin=0xffffffff80000000 if upper 32-bit == 0xffffFFFF then lower 32-bit has to be negative.
and because we're doing unsigned compare w1 < w6 and w6 is less than 80000000
we can conclude that upper bits are zero.
right?

Sorry, could you please explain this a bit more.
The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have 0xffffFFFF for upper bits => r1 += r2 would fail.
What do I miss?

Quoted 8 lines
Quoted 5 lines

Not sure how to rephrase the above differently...
Because smin=0xffffffff80000000...
so full reg cannot be 0xffffFFFF0...123
so when lower 32-bit are compared with unsigned and range of rhs is less than 8000000 it means that the upper 32-bit of full reg are zero.

yep, I think that makes sense. This has to be a special case when the upper 32 bits are either all zeroes or ones, right?

yes. exactly.