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 <[email protected]>
---
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
Hi,
On Thu, Jul 28, 2022 at 8:31 PM Kuee K1r0a <[email protected]> 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 <[email protected]>
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
>
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 <[email protected]>
---
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
Hi Youlin,
On Thu, Jul 28, 2022 at 9:44 PM Youlin Li <[email protected]> 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 <[email protected]>
> ---
> 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
>
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 <[email protected]>
---
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
On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <[email protected]> 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 <[email protected]>
Looks good to me. Thanks Youlin.
Acked-by: Hao Luo <[email protected]>
Hao
On 7/30/22 12:48 AM, Hao Luo wrote:
> On Fri, Jul 29, 2022 at 3:43 PM Youlin Li <[email protected]> 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 <[email protected]>
>
> Looks good to me. Thanks Youlin.
>
> Acked-by: Hao Luo <[email protected]>
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