selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
Subsystems (4)
Yonghong Song
reviewerPATCH 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
@@ -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
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
; intiter_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:14244: (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 ==0x0goto 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 betweenmap_valuepointer and register with unbounded min value is not allowedThe source code:
intiter_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 ==0x0goto 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_idx23first_idx20subseq_idx-1
...Signed-off-by Yonghong Song <[email protected]>--- tools/testing/selftests/bpf/progs/iters.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)tools/testing/selftests/bpf/progs/iters.c +0
-0
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?
Yonghong Song
reviewerQuoted 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 allowedThe 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 ...Signed-off-by Yonghong Song <[email protected]>--- tools/testing/selftests/bpf/progs/iters.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)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 ;
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
-0if (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 otherbpf_fortests 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.
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 allowedThe 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 ...Signed-off-by Yonghong Song <[email protected]>--- tools/testing/selftests/bpf/progs/iters.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)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 ;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
-0if (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 otherbpf_fortests 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_statelike belowstruct 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+4the 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.
Yonghong Song
reviewerQuoted 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 allowedThe 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 ...Signed-off-by Yonghong Song <[email protected]>--- tools/testing/selftests/bpf/progs/iters.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)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 ;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
-0if (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 otherbpf_fortests 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_statelike belowstruct 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+4the 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 ==0xffffFFFFthen 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.
Eduard Zingerman
maintainerOn 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 ==0xffffFFFFthen 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.
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 ==0xffffFFFFthen 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
@@ -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)r1Quoted 29 lines
The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have
0xffffFFFFfor 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.
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 ==0xffffFFFFthen 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)r1Quoted 29 lines
The w1 < w6 comparison only infers information about sub-registers. So the range for the full register r1 would still have
0xffffFFFFfor 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.
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 ==0xffffFFFFthen 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.
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 ==0xffffFFFFthen 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.
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 ==0xffffFFFFthen 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 forbpf_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 thebpf_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.
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 ==0xffffFFFFthen 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 forbpf_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 thebpf_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?
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 ==0xffffFFFFthen 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 have0xffffFFFFfor 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.
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 ==0xffffFFFFthen 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 have0xffffFFFFfor 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?
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 ==0xffffFFFFthen 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 have0xffffFFFFfor 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.