* [PATCH bpf] bpf: Do more tight ALU bounds tracking
@ 2022-07-29 3:30 Kuee K1r0a
2022-07-29 3:51 ` Hao Luo
0 siblings, 1 reply; 14+ messages in thread
From: Kuee K1r0a @ 2022-07-29 3:30 UTC (permalink / raw)
To: ast
Cc: daniel, john.fastabend, andrii, martin.lau, song, yhs, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kernel, Kuee K1r0a
32bit bounds and 64bit bounds are updated separately in
adjust_scalar_min_max_vals() currently, let them learn from each other to
get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().
Before:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
6: (95) exit
It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.
After:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
6: (95) exit
Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Kuee K1r0a <liulin063@gmail.com>
---
kernel/bpf/verifier.c | 9 ++++++---
1 file changed, 6 insertions(+), 3 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0efbac0fd126..888aa50fbdc0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
break;
}
- /* ALU32 ops are zero extended into 64bit register */
- if (alu32)
+ if (alu32) {
+ /* ALU32 ops are zero extended into 64bit register */
zext_32_to_64(dst_reg);
- reg_bounds_sync(dst_reg);
+ __reg_combine_32_into_64(dst_reg);
+ } else {
+ __reg_combine_64_into_32(dst_reg);
+ }
return 0;
}
--
2.25.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
2022-07-29 3:30 [PATCH bpf] bpf: Do more tight ALU bounds tracking Kuee K1r0a
@ 2022-07-29 3:51 ` Hao Luo
2022-07-29 4:43 ` Youlin Li
0 siblings, 1 reply; 14+ messages in thread
From: Hao Luo @ 2022-07-29 3:51 UTC (permalink / raw)
To: Kuee K1r0a
Cc: ast, daniel, john.fastabend, andrii, martin.lau, song, yhs,
kpsingh, sdf, jolsa, bpf, linux-kernel
Hi,
On Thu, Jul 28, 2022 at 8:31 PM Kuee K1r0a <liulin063@gmail.com> wrote:
>
> 32bit bounds and 64bit bounds are updated separately in
> adjust_scalar_min_max_vals() currently, let them learn from each other to
> get more tight bounds tracking. Similar operation can be found in
> reg_set_min_max().
>
> Before:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
> 6: (95) exit
>
> It can be seen that even if the 64bit bounds is clear here, the 32bit
> bounds is still in the state of 'UNKNOWN'.
>
> After:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
> 6: (95) exit
>
> Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
> Signed-off-by: Kuee K1r0a <liulin063@gmail.com>
Please sign with your real name. Thanks.
> ---
> kernel/bpf/verifier.c | 9 ++++++---
> 1 file changed, 6 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0efbac0fd126..888aa50fbdc0 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> break;
> }
>
> - /* ALU32 ops are zero extended into 64bit register */
> - if (alu32)
> + if (alu32) {
> + /* ALU32 ops are zero extended into 64bit register */
> zext_32_to_64(dst_reg);
> - reg_bounds_sync(dst_reg);
> + __reg_combine_32_into_64(dst_reg);
> + } else {
> + __reg_combine_64_into_32(dst_reg);
> + }
> return 0;
> }
>
> --
> 2.25.1
>
^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH bpf] bpf: Do more tight ALU bounds tracking
2022-07-29 3:51 ` Hao Luo
@ 2022-07-29 4:43 ` Youlin Li
2022-07-29 17:11 ` Hao Luo
0 siblings, 1 reply; 14+ messages in thread
From: Youlin Li @ 2022-07-29 4:43 UTC (permalink / raw)
To: ast
Cc: daniel, john.fastabend, andrii, martin.lau, song, yhs, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kernel, Youlin Li
32bit bounds and 64bit bounds are updated separately in
adjust_scalar_min_max_vals() currently, let them learn from each other to
get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().
Before:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
6: (95) exit
It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.
After:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
6: (95) exit
Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
Signed-off-by: Youlin Li <liulin063@gmail.com>
---
kernel/bpf/verifier.c | 9 ++++++---
1 file changed, 6 insertions(+), 3 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0efbac0fd126..888aa50fbdc0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
break;
}
- /* ALU32 ops are zero extended into 64bit register */
- if (alu32)
+ if (alu32) {
+ /* ALU32 ops are zero extended into 64bit register */
zext_32_to_64(dst_reg);
- reg_bounds_sync(dst_reg);
+ __reg_combine_32_into_64(dst_reg);
+ } else {
+ __reg_combine_64_into_32(dst_reg);
+ }
return 0;
}
--
2.25.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
2022-07-29 4:43 ` Youlin Li
@ 2022-07-29 17:11 ` Hao Luo
2022-07-29 22:42 ` Youlin Li
0 siblings, 1 reply; 14+ messages in thread
From: Hao Luo @ 2022-07-29 17:11 UTC (permalink / raw)
To: Youlin Li
Cc: ast, daniel, john.fastabend, andrii, martin.lau, song, yhs,
kpsingh, sdf, jolsa, bpf, linux-kernel
Hi Youlin,
On Thu, Jul 28, 2022 at 9:44 PM Youlin Li <liulin063@gmail.com> wrote:
>
> 32bit bounds and 64bit bounds are updated separately in
> adjust_scalar_min_max_vals() currently, let them learn from each other to
> get more tight bounds tracking. Similar operation can be found in
> reg_set_min_max().
>
> Before:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
> 6: (95) exit
>
> It can be seen that even if the 64bit bounds is clear here, the 32bit
> bounds is still in the state of 'UNKNOWN'.
>
> After:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
> 6: (95) exit
>
> Fixes: 3f50f132d840 ("bpf: Verifier, do explicit ALU32 bounds tracking")
This change looks to me like an improvement, rather than a bug fix. We
probably don't need this tag.
> Signed-off-by: Youlin Li <liulin063@gmail.com>
> ---
> kernel/bpf/verifier.c | 9 ++++++---
> 1 file changed, 6 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0efbac0fd126..888aa50fbdc0 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -8934,10 +8934,13 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> break;
> }
>
> - /* ALU32 ops are zero extended into 64bit register */
> - if (alu32)
> + if (alu32) {
> + /* ALU32 ops are zero extended into 64bit register */
> zext_32_to_64(dst_reg);
> - reg_bounds_sync(dst_reg);
> + __reg_combine_32_into_64(dst_reg);
This __reg_combine_32_into_64 can be replaced with simply
reg_bounds_sync, because the above zext_32_to_64 has already
propagated 32 to 64. Using reg_bounds_sync would be more efficient.
It turns out we can now fold reg_bounds_sync into zext_32_to_64. Can
you do that and resend? IMO that will make the code slightly cleaner.
> + } else {
> + __reg_combine_64_into_32(dst_reg);
> + }
> return 0;
> }
>
> --
> 2.25.1
>
^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH bpf] bpf: Do more tight ALU bounds tracking
2022-07-29 17:11 ` Hao Luo
@ 2022-07-29 22:42 ` Youlin Li
2022-07-29 22:48 ` Hao Luo
0 siblings, 1 reply; 14+ messages in thread
From: Youlin Li @ 2022-07-29 22:42 UTC (permalink / raw)
To: ast
Cc: daniel, john.fastabend, andrii, martin.lau, song, yhs, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kernel, Youlin Li
In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
to get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().
Also, we can now fold reg_bounds_sync() into zext_32_to_64().
Before:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
6: (95) exit
It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.
After:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
6: (95) exit
Signed-off-by: Youlin Li <liulin063@gmail.com>
---
kernel/bpf/verifier.c | 10 ++++++----
1 file changed, 6 insertions(+), 4 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0efbac0fd126..1f5c6e3634d6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4383,6 +4383,7 @@ static void zext_32_to_64(struct bpf_reg_state *reg)
{
reg->var_off = tnum_subreg(reg->var_off);
__reg_assign_32_into_64(reg);
+ reg_bounds_sync(reg);
}
/* truncate register to smaller size (in bytes)
@@ -8934,10 +8935,12 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
break;
}
- /* ALU32 ops are zero extended into 64bit register */
- if (alu32)
+ if (alu32) {
+ /* ALU32 ops are zero extended into 64bit register */
zext_32_to_64(dst_reg);
- reg_bounds_sync(dst_reg);
+ } else {
+ __reg_combine_64_into_32(dst_reg);
+ }
return 0;
}
@@ -9126,7 +9129,6 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
insn->dst_reg);
}
zext_32_to_64(dst_reg);
- reg_bounds_sync(dst_reg);
}
} else {
/* case: R = imm
--
2.25.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
2022-07-29 22:42 ` Youlin Li
@ 2022-07-29 22:48 ` Hao Luo
2022-08-08 13:25 ` Daniel Borkmann
0 siblings, 1 reply; 14+ messages in thread
From: Hao Luo @ 2022-07-29 22:48 UTC (permalink / raw)
To: Youlin Li
Cc: ast, daniel, john.fastabend, andrii, martin.lau, song, yhs,
kpsingh, sdf, jolsa, bpf, linux-kernel
On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <liulin063@gmail.com> wrote:
>
> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
> to get more tight bounds tracking. Similar operation can be found in
> reg_set_min_max().
>
> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
>
> Before:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
> 6: (95) exit
>
> It can be seen that even if the 64bit bounds is clear here, the 32bit
> bounds is still in the state of 'UNKNOWN'.
>
> After:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
> 6: (95) exit
>
> Signed-off-by: Youlin Li <liulin063@gmail.com>
Looks good to me. Thanks Youlin.
Acked-by: Hao Luo <haoluo@google.com>
Hao
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
2022-07-29 22:48 ` Hao Luo
@ 2022-08-08 13:25 ` Daniel Borkmann
[not found] ` <CANdZH3U7axKg6zDY+iswF2d1fBYY1Xo2jeVsbgMYMoJfd1AYJg@mail.gmail.com>
0 siblings, 1 reply; 14+ messages in thread
From: Daniel Borkmann @ 2022-08-08 13:25 UTC (permalink / raw)
To: Hao Luo, Youlin Li
Cc: ast, john.fastabend, andrii, martin.lau, song, yhs, kpsingh, sdf,
jolsa, bpf, linux-kernel
On 7/30/22 12:48 AM, Hao Luo wrote:
> On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <liulin063@gmail.com> wrote:
>>
>> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
>> to get more tight bounds tracking. Similar operation can be found in
>> reg_set_min_max().
>>
>> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
>>
>> Before:
>>
>> func#0 @0
>> 0: R1=ctx(off=0,imm=0) R10=fp0
>> 0: (b7) r0 = 0 ; R0_w=0
>> 1: (b7) r1 = 0 ; R1_w=0
>> 2: (87) r1 = -r1 ; R1_w=scalar()
>> 3: (87) r1 = -r1 ; R1_w=scalar()
>> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
>> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
>> 6: (95) exit
>>
>> It can be seen that even if the 64bit bounds is clear here, the 32bit
>> bounds is still in the state of 'UNKNOWN'.
>>
>> After:
>>
>> func#0 @0
>> 0: R1=ctx(off=0,imm=0) R10=fp0
>> 0: (b7) r0 = 0 ; R0_w=0
>> 1: (b7) r1 = 0 ; R1_w=0
>> 2: (87) r1 = -r1 ; R1_w=scalar()
>> 3: (87) r1 = -r1 ; R1_w=scalar()
>> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
>> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
>> 6: (95) exit
>>
>> Signed-off-by: Youlin Li <liulin063@gmail.com>
>
> Looks good to me. Thanks Youlin.
>
> Acked-by: Hao Luo <haoluo@google.com>
Thanks Youlin! Looks like the patch breaks CI [0] e.g.:
#142/p bounds check after truncation of non-boundary-crossing range FAIL
Failed to load prog 'Permission denied'!
invalid access to map value, value_size=8 off=16777215 size=1
R0 max value is outside of the allowed memory range
verification time 296 usec
stack depth 8
processed 15 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
Please take a look. Also it would be great to add a test_verifier selftest to
assert above case from commit log against future changes.
Thanks,
Daniel
[0] https://github.com/kernel-patches/bpf/runs/7696324041?check_suite_focus=true
^ permalink raw reply [flat|nested] 14+ messages in thread
* Fwd: [PATCH bpf] bpf: Do more tight ALU bounds tracking
[not found] ` <CANdZH3U7axKg6zDY+iswF2d1fBYY1Xo2jeVsbgMYMoJfd1AYJg@mail.gmail.com>
@ 2022-08-08 15:14 ` Kuee k1r0a
2022-08-08 15:42 ` Daniel Borkmann
0 siblings, 1 reply; 14+ messages in thread
From: Kuee k1r0a @ 2022-08-08 15:14 UTC (permalink / raw)
To: haoluo
Cc: Alexei Starovoitov, john.fastabend, Andrii Nakryiko, martin.lau,
song, yhs, kpsingh, sdf, jolsa, bpf, linux-kernel
---------- Forwarded message ---------
From: Kuee k1r0a <liulin063@gmail.com>
Date: Mon, Aug 8, 2022 at 11:11 PM
Subject: Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
To: Daniel Borkmann <daniel@iogearbox.net>
On Mon, Aug 8, 2022 at 9:25 PM Daniel Borkmann <daniel@iogearbox.net> wrote:
>
> On 7/30/22 12:48 AM, Hao Luo wrote:
> > On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <liulin063@gmail.com> wrote:
> >>
> >> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
> >> to get more tight bounds tracking. Similar operation can be found in
> >> reg_set_min_max().
> >>
> >> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
> >>
> >> Before:
> >>
> >> func#0 @0
> >> 0: R1=ctx(off=0,imm=0) R10=fp0
> >> 0: (b7) r0 = 0 ; R0_w=0
> >> 1: (b7) r1 = 0 ; R1_w=0
> >> 2: (87) r1 = -r1 ; R1_w=scalar()
> >> 3: (87) r1 = -r1 ; R1_w=scalar()
> >> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> >> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
> >> 6: (95) exit
> >>
> >> It can be seen that even if the 64bit bounds is clear here, the 32bit
> >> bounds is still in the state of 'UNKNOWN'.
> >>
> >> After:
> >>
> >> func#0 @0
> >> 0: R1=ctx(off=0,imm=0) R10=fp0
> >> 0: (b7) r0 = 0 ; R0_w=0
> >> 1: (b7) r1 = 0 ; R1_w=0
> >> 2: (87) r1 = -r1 ; R1_w=scalar()
> >> 3: (87) r1 = -r1 ; R1_w=scalar()
> >> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> >> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
> >> 6: (95) exit
> >>
> >> Signed-off-by: Youlin Li <liulin063@gmail.com>
> >
> > Looks good to me. Thanks Youlin.
> >
> > Acked-by: Hao Luo <haoluo@google.com>
>
> Thanks Youlin! Looks like the patch breaks CI [0] e.g.:
>
> #142/p bounds check after truncation of non-boundary-crossing range FAIL
> Failed to load prog 'Permission denied'!
> invalid access to map value, value_size=8 off=16777215 size=1
> R0 max value is outside of the allowed memory range
> verification time 296 usec
> stack depth 8
> processed 15 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
>
> Please take a look. Also it would be great to add a test_verifier selftest to
> assert above case from commit log against future changes.
>
> Thanks,
> Daniel
>
> [0] https://github.com/kernel-patches/bpf/runs/7696324041?check_suite_focus=true
This test case fails because the 32bit boundary information is lost
after the 11th instruction is executed:
Before:
11: (07) r1 += 2147483647 ;
R1_w=scalar(umin=70866960383,umax=70866960638,var_off=(0x1000000000;
0xffffffff),u32_min=2147483647,u32_max=-2147483394)
After:
11: (07) r1 += 2147483647 ;
R1_w=scalar(umin=70866960383,umax=70866960638,var_off=(0x1000000000;
0xffffffff))
This may be because, in previous versions of the code, when
__reg_combine_64_into_32() was called, the 32bit boundary was
completely deduced from the 64bit boundary, so there was a call to
__mark_reg32_unbounded() in __reg_combine_64_into_32().
But now, before adjust_scalar_min_max_vals() calls
__reg_combine_64_into_32() , the 32bit bounds are already calculated
to some extent, and __mark_reg32_unbounded() will eliminate these
information.
Simply copying a code without __mark_reg32_unbounded() should work,
perhaps it would be more elegant to introduce a flag into
__reg_combine_64_into_32()?
Sorry for not completing the tests because I did not 'make selftests'
successfully, and uploaded the code that caused the error.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Fwd: [PATCH bpf] bpf: Do more tight ALU bounds tracking
2022-08-08 15:14 ` Fwd: " Kuee k1r0a
@ 2022-08-08 15:42 ` Daniel Borkmann
2022-08-10 10:08 ` [PATCH 1/2] bpf: Fix 32bit bounds update in ALU64 Youlin Li
2022-08-10 10:09 ` [PATCH 2/2] bpf, selftests: Add verifier test case for ALU64 Youlin Li
0 siblings, 2 replies; 14+ messages in thread
From: Daniel Borkmann @ 2022-08-08 15:42 UTC (permalink / raw)
To: Kuee k1r0a, haoluo
Cc: Alexei Starovoitov, john.fastabend, Andrii Nakryiko, martin.lau,
song, yhs, kpsingh, sdf, jolsa, bpf, linux-kernel
On 8/8/22 5:14 PM, Kuee k1r0a wrote:
> ---------- Forwarded message ---------
> From: Kuee k1r0a <liulin063@gmail.com>
> Date: Mon, Aug 8, 2022 at 11:11 PM
> Subject: Re: [PATCH bpf] bpf: Do more tight ALU bounds tracking
> To: Daniel Borkmann <daniel@iogearbox.net>
>
>
> On Mon, Aug 8, 2022 at 9:25 PM Daniel Borkmann <daniel@iogearbox.net> wrote:
>>
>> On 7/30/22 12:48 AM, Hao Luo wrote:
>>> On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <liulin063@gmail.com> wrote:
>>>>
>>>> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
>>>> to get more tight bounds tracking. Similar operation can be found in
>>>> reg_set_min_max().
>>>>
>>>> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
>>>>
>>>> Before:
>>>>
>>>> func#0 @0
>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>> 0: (b7) r0 = 0 ; R0_w=0
>>>> 1: (b7) r1 = 0 ; R1_w=0
>>>> 2: (87) r1 = -r1 ; R1_w=scalar()
>>>> 3: (87) r1 = -r1 ; R1_w=scalar()
>>>> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
>>>> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
>>>> 6: (95) exit
>>>>
>>>> It can be seen that even if the 64bit bounds is clear here, the 32bit
>>>> bounds is still in the state of 'UNKNOWN'.
>>>>
>>>> After:
>>>>
>>>> func#0 @0
>>>> 0: R1=ctx(off=0,imm=0) R10=fp0
>>>> 0: (b7) r0 = 0 ; R0_w=0
>>>> 1: (b7) r1 = 0 ; R1_w=0
>>>> 2: (87) r1 = -r1 ; R1_w=scalar()
>>>> 3: (87) r1 = -r1 ; R1_w=scalar()
>>>> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
>>>> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
>>>> 6: (95) exit
>>>>
>>>> Signed-off-by: Youlin Li <liulin063@gmail.com>
>>>
>>> Looks good to me. Thanks Youlin.
>>>
>>> Acked-by: Hao Luo <haoluo@google.com>
>>
>> Thanks Youlin! Looks like the patch breaks CI [0] e.g.:
>>
>> #142/p bounds check after truncation of non-boundary-crossing range FAIL
>> Failed to load prog 'Permission denied'!
>> invalid access to map value, value_size=8 off=16777215 size=1
>> R0 max value is outside of the allowed memory range
>> verification time 296 usec
>> stack depth 8
>> processed 15 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
>>
>> Please take a look. Also it would be great to add a test_verifier selftest to
>> assert above case from commit log against future changes.
>>
>> Thanks,
>> Daniel
>>
>> [0] https://github.com/kernel-patches/bpf/runs/7696324041?check_suite_focus=true
>
> This test case fails because the 32bit boundary information is lost
> after the 11th instruction is executed:
> Before:
> 11: (07) r1 += 2147483647 ;
> R1_w=scalar(umin=70866960383,umax=70866960638,var_off=(0x1000000000;
> 0xffffffff),u32_min=2147483647,u32_max=-2147483394)
> After:
> 11: (07) r1 += 2147483647 ;
> R1_w=scalar(umin=70866960383,umax=70866960638,var_off=(0x1000000000;
> 0xffffffff))
>
> This may be because, in previous versions of the code, when
> __reg_combine_64_into_32() was called, the 32bit boundary was
> completely deduced from the 64bit boundary, so there was a call to
> __mark_reg32_unbounded() in __reg_combine_64_into_32().
>
> But now, before adjust_scalar_min_max_vals() calls
> __reg_combine_64_into_32() , the 32bit bounds are already calculated
> to some extent, and __mark_reg32_unbounded() will eliminate these
> information.
>
> Simply copying a code without __mark_reg32_unbounded() should work,
> perhaps it would be more elegant to introduce a flag into
> __reg_combine_64_into_32()?
>
> Sorry for not completing the tests because I did not 'make selftests'
> successfully, and uploaded the code that caused the error.
Under tools/testing/selftests/bpf/, you can run test_progs and test_verifier
through the vmtest script, e.g. `./vmtest.sh -- ./test_progs` should ease
running it. The whole `make selftests` is not necessary given here we care
about BPF, CI is running these where 2 failed and need investigation:
test_progs: PASS
test_progs-no_alu32: FAIL (returned 1)
test_maps: PASS
test_verifier: FAIL (returned 1)
Fwiw, for the test_verifier failure case at least, we should then adapt it
in a separate commit with an analysis explaining why it is okay to alter the
test; plus a 3rd commit adding new test cases as mentioned earlier.
Thanks a lot, Kuee!
Daniel
^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH 1/2] bpf: Fix 32bit bounds update in ALU64
2022-08-08 15:42 ` Daniel Borkmann
@ 2022-08-10 10:08 ` Youlin Li
2022-08-17 20:31 ` Daniel Borkmann
2022-08-10 10:09 ` [PATCH 2/2] bpf, selftests: Add verifier test case for ALU64 Youlin Li
1 sibling, 1 reply; 14+ messages in thread
From: Youlin Li @ 2022-08-10 10:08 UTC (permalink / raw)
To: daniel, haoluo
Cc: ast, john.fastabend, andrii, martin.lau, song, yhs, kpsingh, sdf,
jolsa, bpf, linux-kernel, Youlin Li
The commit ("bpf: Do more tight ALU bounds tracking") introduces a bug
that fails some selftests.
in previous versions of the code, when
__reg_combine_64_into_32() was called, the 32bit boundary was
completely deduced from the 64bit boundary, so there was a call to
__mark_reg32_unbounded() in __reg_combine_64_into_32(). But before
adjust_scalar_min_max_vals() calls
__reg_combine_64_into_32() , the 32bit bounds are already calculated
to some extent, and __mark_reg32_unbounded() will eliminate these
information.
Simply remove the call to __reg_combine_64_into_32() and copying a code
without __mark_reg32_unbounded() should work.
Before:
./test_verifier 142
#142/p bounds check after truncation of non-boundary-crossing range FAIL
Failed to load prog 'Permission denied'!
invalid access to map value, value_size=8 off=16777215 size=1
R0 max value is outside of the allowed memory range
verification time 149 usec
stack depth 8
processed 15 insns (limit 1000000) max_states_per_insn 0
total_states 0 peak_states 0 mark_read 0
Summary: 0 PASSED, 1 SKIPPED, 1 FAILED
After:
./test_verifier 142
#142/p bounds check after truncation of non-boundary-crossing range OK
Summary: 1 PASSED, 1 SKIPPED, 0 FAILED
Signed-off-by: Youlin Li <liulin063@gmail.com>
---
kernel/bpf/verifier.c | 12 +++++++++++-
1 file changed, 11 insertions(+), 1 deletion(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 11d8bb54ba6b..7ea6e0372d62 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9014,7 +9014,17 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
/* ALU32 ops are zero extended into 64bit register */
zext_32_to_64(dst_reg);
} else {
- __reg_combine_64_into_32(dst_reg);
+ if (__reg64_bound_s32(dst_reg->smin_value) &&
+ __reg64_bound_s32(dst_reg->smax_value)) {
+ dst_reg->s32_min_value = (s32)dst_reg->smin_value;
+ dst_reg->s32_max_value = (s32)dst_reg->smax_value;
+ }
+ if (__reg64_bound_u32(dst_reg->umin_value) &&
+ __reg64_bound_u32(dst_reg->umax_value)) {
+ dst_reg->u32_min_value = (u32)dst_reg->umin_value;
+ dst_reg->u32_max_value = (u32)dst_reg->umax_value;
+ }
+ reg_bounds_sync(dst_reg);
}
return 0;
}
--
2.25.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* [PATCH 2/2] bpf, selftests: Add verifier test case for ALU64
2022-08-08 15:42 ` Daniel Borkmann
2022-08-10 10:08 ` [PATCH 1/2] bpf: Fix 32bit bounds update in ALU64 Youlin Li
@ 2022-08-10 10:09 ` Youlin Li
1 sibling, 0 replies; 14+ messages in thread
From: Youlin Li @ 2022-08-10 10:09 UTC (permalink / raw)
To: daniel, haoluo
Cc: ast, john.fastabend, andrii, martin.lau, song, yhs, kpsingh, sdf,
jolsa, bpf, linux-kernel, Youlin Li
Add a test case to ensure that 32-bit bounds can be learned from 64-bit
bounds when performing 64-bit ALU operations.
Make use of dead code elimination, so that we can see the verifier
bailing out on unmodified kernels.
Before:
./test_verifier 165
#165/p 32-bit bounds update in ALU64 FAIL
Failed to load prog 'Permission denied'!
R2 !read_ok
verification time 49 usec
stack depth 0
processed 8 insns (limit 1000000) max_states_per_insn 0 total_states
0 peak_states 0 mark_read 0
Summary: 0 PASSED, 1 SKIPPED, 1 FAILED
After:
./test_verifier 165
#165/p 32-bit bounds update in ALU64 OK
Summary: 1 PASSED, 1 SKIPPED, 0 FAILED
Signed-off-by: Youlin Li <liulin063@gmail.com>
---
tools/testing/selftests/bpf/verifier/bounds.c | 17 +++++++++++++++++
1 file changed, 17 insertions(+)
diff --git a/tools/testing/selftests/bpf/verifier/bounds.c b/tools/testing/selftests/bpf/verifier/bounds.c
index 33125d5f6772..b9aee2f2c66e 100644
--- a/tools/testing/selftests/bpf/verifier/bounds.c
+++ b/tools/testing/selftests/bpf/verifier/bounds.c
@@ -753,3 +753,20 @@
.result_unpriv = REJECT,
.result = ACCEPT,
},
+{
+ "32-bit bounds update in ALU64",
+ .insns = {
+ BPF_MOV64_IMM(BPF_REG_0, 0),
+ BPF_MOV64_IMM(BPF_REG_1, 0),
+ BPF_ALU64_IMM(BPF_NEG, BPF_REG_1, 0),
+ BPF_ALU64_IMM(BPF_NEG, BPF_REG_1, 0),
+ BPF_ALU64_IMM(BPF_ARSH, BPF_REG_1, 63),
+ BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 2),
+ BPF_JMP32_IMM(BPF_JGE, BPF_REG_1, 1, 1),
+ BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+ BPF_JMP32_IMM(BPF_JLE, BPF_REG_1, 2, 1),
+ BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+ BPF_EXIT_INSN()
+ },
+ .result = ACCEPT,
+},
--
2.25.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH 1/2] bpf: Fix 32bit bounds update in ALU64
2022-08-10 10:08 ` [PATCH 1/2] bpf: Fix 32bit bounds update in ALU64 Youlin Li
@ 2022-08-17 20:31 ` Daniel Borkmann
2022-08-27 13:57 ` [PATCH bpf v2 1/2] bpf: Do more tight ALU bounds tracking Youlin Li
0 siblings, 1 reply; 14+ messages in thread
From: Daniel Borkmann @ 2022-08-17 20:31 UTC (permalink / raw)
To: Youlin Li, haoluo
Cc: ast, john.fastabend, andrii, martin.lau, song, yhs, kpsingh, sdf,
jolsa, bpf, linux-kernel
On 8/10/22 12:08 PM, Youlin Li wrote:
> The commit ("bpf: Do more tight ALU bounds tracking") introduces a bug
> that fails some selftests.
>
> in previous versions of the code, when
> __reg_combine_64_into_32() was called, the 32bit boundary was
> completely deduced from the 64bit boundary, so there was a call to
> __mark_reg32_unbounded() in __reg_combine_64_into_32(). But before
> adjust_scalar_min_max_vals() calls
> __reg_combine_64_into_32() , the 32bit bounds are already calculated
> to some extent, and __mark_reg32_unbounded() will eliminate these
> information.
>
> Simply remove the call to __reg_combine_64_into_32() and copying a code
> without __mark_reg32_unbounded() should work.
>
> Before:
> ./test_verifier 142
> #142/p bounds check after truncation of non-boundary-crossing range FAIL
> Failed to load prog 'Permission denied'!
> invalid access to map value, value_size=8 off=16777215 size=1
> R0 max value is outside of the allowed memory range
> verification time 149 usec
> stack depth 8
> processed 15 insns (limit 1000000) max_states_per_insn 0
> total_states 0 peak_states 0 mark_read 0
> Summary: 0 PASSED, 1 SKIPPED, 1 FAILED
>
> After:
> ./test_verifier 142
> #142/p bounds check after truncation of non-boundary-crossing range OK
> Summary: 1 PASSED, 1 SKIPPED, 0 FAILED
>
> Signed-off-by: Youlin Li <liulin063@gmail.com>
> ---
> kernel/bpf/verifier.c | 12 +++++++++++-
> 1 file changed, 11 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 11d8bb54ba6b..7ea6e0372d62 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9014,7 +9014,17 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
> /* ALU32 ops are zero extended into 64bit register */
> zext_32_to_64(dst_reg);
> } else {
> - __reg_combine_64_into_32(dst_reg);
> + if (__reg64_bound_s32(dst_reg->smin_value) &&
> + __reg64_bound_s32(dst_reg->smax_value)) {
> + dst_reg->s32_min_value = (s32)dst_reg->smin_value;
> + dst_reg->s32_max_value = (s32)dst_reg->smax_value;
> + }
> + if (__reg64_bound_u32(dst_reg->umin_value) &&
> + __reg64_bound_u32(dst_reg->umax_value)) {
> + dst_reg->u32_min_value = (u32)dst_reg->umin_value;
> + dst_reg->u32_max_value = (u32)dst_reg->umax_value;
> + }
> + reg_bounds_sync(dst_reg);
Hm, this doesn't apply to the bpf tree. Is this on top of your previous patch [0]?
Please squash both together in that case and resubmit your previous one as a v2.
[0] https://lore.kernel.org/bpf/9f954e67-67fc-e3b9-d810-22bfea95d2aa@iogearbox.net/
Thanks,
Daniel
^ permalink raw reply [flat|nested] 14+ messages in thread
* [PATCH bpf v2 1/2] bpf: Do more tight ALU bounds tracking
2022-08-17 20:31 ` Daniel Borkmann
@ 2022-08-27 13:57 ` Youlin Li
2022-08-30 0:19 ` Hao Luo
0 siblings, 1 reply; 14+ messages in thread
From: Youlin Li @ 2022-08-27 13:57 UTC (permalink / raw)
To: daniel, haoluo
Cc: ast, john.fastabend, andrii, martin.lau, song, yhs, kpsingh, sdf,
jolsa, bpf, linux-kernel, Youlin Li
In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
to get more tight bounds tracking. Similar operation can be found in
reg_set_min_max().
Note that we cannot simply add a call to __reg_combine_64_into_32(). In
previous versions of the code, when __reg_combine_64_into_32() was
called, the 32bit boundary was completely deduced from the 64bit
boundary, so there was a call to __mark_reg32_unbounded() in
__reg_combine_64_into_32(). But in adjust_scalar_min_max_vals(), the 32bit
bounds are already calculated to some extent, and __mark_reg32_unbounded()
will eliminate these information.
Simply copying a code without __mark_reg32_unbounded() should work.
Also, we can now fold reg_bounds_sync() into zext_32_to_64().
Before:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
6: (95) exit
It can be seen that even if the 64bit bounds is clear here, the 32bit
bounds is still in the state of 'UNKNOWN'.
After:
func#0 @0
0: R1=ctx(off=0,imm=0) R10=fp0
0: (b7) r0 = 0 ; R0_w=0
1: (b7) r1 = 0 ; R1_w=0
2: (87) r1 = -r1 ; R1_w=scalar()
3: (87) r1 = -r1 ; R1_w=scalar()
4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
6: (95) exit
Signed-off-by: Youlin Li <liulin063@gmail.com>
---
v1 -> v2:
Replaced the call to __reg_combine_64_into_32() with the code in
__reg_combine_64_into_32(), and removed the call to
__mark_reg32_unbounded().
Sorry for the delay, I've been busy looking for a job recently :)
kernel/bpf/verifier.c | 20 ++++++++++++++++----
1 file changed, 16 insertions(+), 4 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3eadb14e090b..b7403773e834 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -4383,6 +4383,7 @@ static void zext_32_to_64(struct bpf_reg_state *reg)
{
reg->var_off = tnum_subreg(reg->var_off);
__reg_assign_32_into_64(reg);
+ reg_bounds_sync(reg);
}
/* truncate register to smaller size (in bytes)
@@ -9010,10 +9011,22 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
break;
}
- /* ALU32 ops are zero extended into 64bit register */
- if (alu32)
+ if (alu32) {
+ /* ALU32 ops are zero extended into 64bit register */
zext_32_to_64(dst_reg);
- reg_bounds_sync(dst_reg);
+ } else {
+ if (__reg64_bound_s32(dst_reg->smin_value) &&
+ __reg64_bound_s32(dst_reg->smax_value)) {
+ dst_reg->s32_min_value = (s32)dst_reg->smin_value;
+ dst_reg->s32_max_value = (s32)dst_reg->smax_value;
+ }
+ if (__reg64_bound_u32(dst_reg->umin_value) &&
+ __reg64_bound_u32(dst_reg->umax_value)) {
+ dst_reg->u32_min_value = (u32)dst_reg->umin_value;
+ dst_reg->u32_max_value = (u32)dst_reg->umax_value;
+ }
+ reg_bounds_sync(dst_reg);
+ }
return 0;
}
@@ -9202,7 +9215,6 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
insn->dst_reg);
}
zext_32_to_64(dst_reg);
- reg_bounds_sync(dst_reg);
}
} else {
/* case: R = imm
--
2.25.1
^ permalink raw reply related [flat|nested] 14+ messages in thread
* Re: [PATCH bpf v2 1/2] bpf: Do more tight ALU bounds tracking
2022-08-27 13:57 ` [PATCH bpf v2 1/2] bpf: Do more tight ALU bounds tracking Youlin Li
@ 2022-08-30 0:19 ` Hao Luo
0 siblings, 0 replies; 14+ messages in thread
From: Hao Luo @ 2022-08-30 0:19 UTC (permalink / raw)
To: Youlin Li
Cc: daniel, ast, john.fastabend, andrii, martin.lau, song, yhs,
kpsingh, sdf, jolsa, bpf, linux-kernel
Hi Youlin,
On Sat, Aug 27, 2022 at 6:57 AM Youlin Li <liulin063@gmail.com> wrote:
>
> In adjust_scalar_min_max_vals(), let 32bit bounds learn from 64bit bounds
> to get more tight bounds tracking. Similar operation can be found in
> reg_set_min_max().
>
> Note that we cannot simply add a call to __reg_combine_64_into_32(). In
> previous versions of the code, when __reg_combine_64_into_32() was
> called, the 32bit boundary was completely deduced from the 64bit
> boundary, so there was a call to __mark_reg32_unbounded() in
> __reg_combine_64_into_32(). But in adjust_scalar_min_max_vals(), the 32bit
> bounds are already calculated to some extent, and __mark_reg32_unbounded()
> will eliminate these information.
>
> Simply copying a code without __mark_reg32_unbounded() should work.
>
> Also, we can now fold reg_bounds_sync() into zext_32_to_64().
>
> Before:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0xffffffff)) <--- [*]
> 6: (95) exit
>
> It can be seen that even if the 64bit bounds is clear here, the 32bit
> bounds is still in the state of 'UNKNOWN'.
>
> After:
>
> func#0 @0
> 0: R1=ctx(off=0,imm=0) R10=fp0
> 0: (b7) r0 = 0 ; R0_w=0
> 1: (b7) r1 = 0 ; R1_w=0
> 2: (87) r1 = -r1 ; R1_w=scalar()
> 3: (87) r1 = -r1 ; R1_w=scalar()
> 4: (c7) r1 s>>= 63 ; R1_w=scalar(smin=-1,smax=0)
> 5: (07) r1 += 2 ; R1_w=scalar(umin=1,umax=2,var_off=(0x0; 0x3)) <--- [*]
> 6: (95) exit
>
> Signed-off-by: Youlin Li <liulin063@gmail.com>
> ---
It might be better to put the code that performs the actual bounds
deduction into a helper function. It avoids code duplication. But the
current version looks fine to me. Thanks for the patch!
Acked-by: Hao Luo <haoluo@google.com>
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2022-08-30 0:19 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-29 3:30 [PATCH bpf] bpf: Do more tight ALU bounds tracking Kuee K1r0a
2022-07-29 3:51 ` Hao Luo
2022-07-29 4:43 ` Youlin Li
2022-07-29 17:11 ` Hao Luo
2022-07-29 22:42 ` Youlin Li
2022-07-29 22:48 ` Hao Luo
2022-08-08 13:25 ` Daniel Borkmann
[not found] ` <CANdZH3U7axKg6zDY+iswF2d1fBYY1Xo2jeVsbgMYMoJfd1AYJg@mail.gmail.com>
2022-08-08 15:14 ` Fwd: " Kuee k1r0a
2022-08-08 15:42 ` Daniel Borkmann
2022-08-10 10:08 ` [PATCH 1/2] bpf: Fix 32bit bounds update in ALU64 Youlin Li
2022-08-17 20:31 ` Daniel Borkmann
2022-08-27 13:57 ` [PATCH bpf v2 1/2] bpf: Do more tight ALU bounds tracking Youlin Li
2022-08-30 0:19 ` Hao Luo
2022-08-10 10:09 ` [PATCH 2/2] bpf, selftests: Add verifier test case for ALU64 Youlin Li
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.