* [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
@ 2024-07-08 15:46 Yonghong Song
2024-07-08 16:27 ` Alexei Starovoitov
0 siblings, 1 reply; 15+ messages in thread
From: Yonghong Song @ 2024-07-08 15:46 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, kernel-team,
Martin KaFai Lau
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
...
Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
---
tools/testing/selftests/bpf/progs/iters.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 16bdc3e25591..d1801d151a12 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -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;
--
2.43.0
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 15:46 [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4 Yonghong Song
@ 2024-07-08 16:27 ` Alexei Starovoitov
2024-07-08 18:34 ` Yonghong Song
0 siblings, 1 reply; 15+ messages in thread
From: Alexei Starovoitov @ 2024-07-08 16:27 UTC (permalink / raw)
To: Yonghong Song
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 8:46 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>
> 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
> ...
>
> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> ---
> tools/testing/selftests/bpf/progs/iters.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
> index 16bdc3e25591..d1801d151a12 100644
> --- a/tools/testing/selftests/bpf/progs/iters.c
> +++ b/tools/testing/selftests/bpf/progs/iters.c
> @@ -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?
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 16:27 ` Alexei Starovoitov
@ 2024-07-08 18:34 ` Yonghong Song
2024-07-08 20:18 ` Alexei Starovoitov
0 siblings, 1 reply; 15+ messages in thread
From: Yonghong Song @ 2024-07-08 18:34 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, Martin KaFai Lau
On 7/8/24 9:27 AM, Alexei Starovoitov wrote:
> On Mon, Jul 8, 2024 at 8:46 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>> 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
>> ...
>>
>> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
>> ---
>> tools/testing/selftests/bpf/progs/iters.c | 3 ++-
>> 1 file changed, 2 insertions(+), 1 deletion(-)
>>
>> diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
>> index 16bdc3e25591..d1801d151a12 100644
>> --- a/tools/testing/selftests/bpf/progs/iters.c
>> +++ b/tools/testing/selftests/bpf/progs/iters.c
>> @@ -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.
Agree. We should fix this in verifier to be user friendly.
>
> 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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 18:34 ` Yonghong Song
@ 2024-07-08 20:18 ` Alexei Starovoitov
2024-07-08 21:19 ` Yonghong Song
2024-07-08 21:31 ` Eduard Zingerman
0 siblings, 2 replies; 15+ messages in thread
From: Alexei Starovoitov @ 2024-07-08 20:18 UTC (permalink / raw)
To: Yonghong Song
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 11:34 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>
>
> On 7/8/24 9:27 AM, Alexei Starovoitov wrote:
> > On Mon, Jul 8, 2024 at 8:46 AM Yonghong Song <yonghong.song@linux.dev> wrote:
> >> 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
> >> ...
> >>
> >> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
> >> ---
> >> tools/testing/selftests/bpf/progs/iters.c | 3 ++-
> >> 1 file changed, 2 insertions(+), 1 deletion(-)
> >>
> >> diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
> >> index 16bdc3e25591..d1801d151a12 100644
> >> --- a/tools/testing/selftests/bpf/progs/iters.c
> >> +++ b/tools/testing/selftests/bpf/progs/iters.c
> >> @@ -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.
>
> Agree. We should fix this in verifier to be user friendly.
>
> >
> > 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.
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?
> <=== 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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 20:18 ` Alexei Starovoitov
@ 2024-07-08 21:19 ` Yonghong Song
2024-07-08 21:31 ` Eduard Zingerman
1 sibling, 0 replies; 15+ messages in thread
From: Yonghong Song @ 2024-07-08 21:19 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, Martin KaFai Lau
On 7/8/24 1:18 PM, Alexei Starovoitov wrote:
> On Mon, Jul 8, 2024 at 11:34 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>>
>> On 7/8/24 9:27 AM, Alexei Starovoitov wrote:
>>> On Mon, Jul 8, 2024 at 8:46 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>>>> 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
>>>> ...
>>>>
>>>> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
>>>> ---
>>>> tools/testing/selftests/bpf/progs/iters.c | 3 ++-
>>>> 1 file changed, 2 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
>>>> index 16bdc3e25591..d1801d151a12 100644
>>>> --- a/tools/testing/selftests/bpf/progs/iters.c
>>>> +++ b/tools/testing/selftests/bpf/progs/iters.c
>>>> @@ -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.
>> Agree. We should fix this in verifier to be user friendly.
>>
>>> 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.
> 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.
>
>> <=== 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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 20:18 ` Alexei Starovoitov
2024-07-08 21:19 ` Yonghong Song
@ 2024-07-08 21:31 ` Eduard Zingerman
2024-07-08 22:11 ` Andrii Nakryiko
2024-07-09 2:09 ` Alexei Starovoitov
1 sibling, 2 replies; 15+ messages in thread
From: Eduard Zingerman @ 2024-07-08 21:31 UTC (permalink / raw)
To: Alexei Starovoitov, Yonghong Song
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, Martin KaFai Lau
On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
[...]
> > 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.
>
> 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.
>
> > <=== 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.
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 21:31 ` Eduard Zingerman
@ 2024-07-08 22:11 ` Andrii Nakryiko
2024-07-08 22:12 ` Andrii Nakryiko
2024-07-09 2:09 ` Alexei Starovoitov
1 sibling, 1 reply; 15+ messages in thread
From: Andrii Nakryiko @ 2024-07-08 22:11 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Alexei Starovoitov, Yonghong Song, bpf, Alexei Starovoitov,
Andrii Nakryiko, Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
>
> [...]
>
> > > 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.
> >
> > 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.
Yep, also curious.
But meanwhile, I'm intending to update bpf_for() to something like
below to avoid this code generation pattern:
diff --git a/tools/lib/bpf/bpf_helpers.h b/tools/lib/bpf/bpf_helpers.h
index 305c62817dd3..86dc854a713b 100644
--- a/tools/lib/bpf/bpf_helpers.h
+++ b/tools/lib/bpf/bpf_helpers.h
@@ -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
> 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.
>
> >
> > > <=== 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.
> >
>
^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 22:11 ` Andrii Nakryiko
@ 2024-07-08 22:12 ` Andrii Nakryiko
2024-07-09 2:03 ` Alexei Starovoitov
0 siblings, 1 reply; 15+ messages in thread
From: Andrii Nakryiko @ 2024-07-08 22:12 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Alexei Starovoitov, Yonghong Song, bpf, Alexei Starovoitov,
Andrii Nakryiko, Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 3:11 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
> >
> > [...]
> >
> > > > 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.
> > >
> > > 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.
>
> 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
>
> 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
>
> > 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.
> >
> > >
> > > > <=== 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.
> > >
> >
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 22:12 ` Andrii Nakryiko
@ 2024-07-09 2:03 ` Alexei Starovoitov
2024-07-09 16:45 ` Andrii Nakryiko
0 siblings, 1 reply; 15+ messages in thread
From: Alexei Starovoitov @ 2024-07-09 2:03 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Eduard Zingerman, Yonghong Song, bpf, Alexei Starovoitov,
Andrii Nakryiko, Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 3:12 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Jul 8, 2024 at 3:11 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
> > >
> > > [...]
> > >
> > > > > 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.
> > > >
> > > > 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.
> >
> > 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
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-08 21:31 ` Eduard Zingerman
2024-07-08 22:11 ` Andrii Nakryiko
@ 2024-07-09 2:09 ` Alexei Starovoitov
2024-07-09 16:49 ` Andrii Nakryiko
1 sibling, 1 reply; 15+ messages in thread
From: Alexei Starovoitov @ 2024-07-09 2:09 UTC (permalink / raw)
To: Eduard Zingerman
Cc: Yonghong Song, bpf, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
>
> [...]
>
> > > 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.
> >
> > 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?
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-09 2:03 ` Alexei Starovoitov
@ 2024-07-09 16:45 ` Andrii Nakryiko
2024-07-09 17:22 ` Alexei Starovoitov
0 siblings, 1 reply; 15+ messages in thread
From: Andrii Nakryiko @ 2024-07-09 16:45 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Eduard Zingerman, Yonghong Song, bpf, Alexei Starovoitov,
Andrii Nakryiko, Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 7:04 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Mon, Jul 8, 2024 at 3:12 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Jul 8, 2024 at 3:11 PM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > >
> > > > On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
> > > >
> > > > [...]
> > > >
> > > > > > 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.
> > > > >
> > > > > 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.
> > >
> > > 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
>
> 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?
> 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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-09 2:09 ` Alexei Starovoitov
@ 2024-07-09 16:49 ` Andrii Nakryiko
2024-07-09 17:23 ` Alexei Starovoitov
0 siblings, 1 reply; 15+ messages in thread
From: Andrii Nakryiko @ 2024-07-09 16:49 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Eduard Zingerman, Yonghong Song, bpf, Alexei Starovoitov,
Andrii Nakryiko, Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Mon, Jul 8, 2024 at 7:09 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
> >
> > [...]
> >
> > > > 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.
> > >
> > > 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?
>
> 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?
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-09 16:45 ` Andrii Nakryiko
@ 2024-07-09 17:22 ` Alexei Starovoitov
2024-07-09 18:12 ` Andrii Nakryiko
0 siblings, 1 reply; 15+ messages in thread
From: Alexei Starovoitov @ 2024-07-09 17:22 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Eduard Zingerman, Yonghong Song, bpf, Alexei Starovoitov,
Andrii Nakryiko, Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Tue, Jul 9, 2024 at 9:45 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Jul 8, 2024 at 7:04 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Mon, Jul 8, 2024 at 3:12 PM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Mon, Jul 8, 2024 at 3:11 PM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > >
> > > > > On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
> > > > >
> > > > > [...]
> > > > >
> > > > > > > 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.
> > > > > >
> > > > > > 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.
> > > >
> > > > 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
> >
> > 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.
> > 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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-09 16:49 ` Andrii Nakryiko
@ 2024-07-09 17:23 ` Alexei Starovoitov
0 siblings, 0 replies; 15+ messages in thread
From: Alexei Starovoitov @ 2024-07-09 17:23 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Eduard Zingerman, Yonghong Song, bpf, Alexei Starovoitov,
Andrii Nakryiko, Daniel Borkmann, Kernel Team, Martin KaFai Lau
On Tue, Jul 9, 2024 at 9:49 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Mon, Jul 8, 2024 at 7:09 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
> > >
> > > [...]
> > >
> > > > > 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.
> > > >
> > > > 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?
> >
> > 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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4
2024-07-09 17:22 ` Alexei Starovoitov
@ 2024-07-09 18:12 ` Andrii Nakryiko
0 siblings, 0 replies; 15+ messages in thread
From: Andrii Nakryiko @ 2024-07-09 18:12 UTC (permalink / raw)
To: Alexei Starovoitov, Eduard Zingerman, Yonghong Song
Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
Kernel Team, Martin KaFai Lau
On Tue, Jul 9, 2024 at 10:22 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Tue, Jul 9, 2024 at 9:45 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Mon, Jul 8, 2024 at 7:04 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Mon, Jul 8, 2024 at 3:12 PM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Mon, Jul 8, 2024 at 3:11 PM Andrii Nakryiko
> > > > <andrii.nakryiko@gmail.com> wrote:
> > > > >
> > > > > On Mon, Jul 8, 2024 at 2:31 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > > > >
> > > > > > On Mon, 2024-07-08 at 13:18 -0700, Alexei Starovoitov wrote:
> > > > > >
> > > > > > [...]
> > > > > >
> > > > > > > > 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.
> > > > > > >
> > > > > > > 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.
> > > > >
> > > > > 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
> > >
> > > 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.
>
> > > 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.
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?
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2024-07-09 18:12 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-07-08 15:46 [PATCH bpf-next] selftests/bpf: Workaround iters/iter_arr_with_actual_elem_count failure when -mcpu=cpuv4 Yonghong Song
2024-07-08 16:27 ` Alexei Starovoitov
2024-07-08 18:34 ` Yonghong Song
2024-07-08 20:18 ` Alexei Starovoitov
2024-07-08 21:19 ` Yonghong Song
2024-07-08 21:31 ` Eduard Zingerman
2024-07-08 22:11 ` Andrii Nakryiko
2024-07-08 22:12 ` Andrii Nakryiko
2024-07-09 2:03 ` Alexei Starovoitov
2024-07-09 16:45 ` Andrii Nakryiko
2024-07-09 17:22 ` Alexei Starovoitov
2024-07-09 18:12 ` Andrii Nakryiko
2024-07-09 2:09 ` Alexei Starovoitov
2024-07-09 16:49 ` Andrii Nakryiko
2024-07-09 17:23 ` Alexei Starovoitov
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox