bpf: improve verifier handling for 32bit signed compare operations
Subsystems (4)
cover bpf: improve verifier handling for 32bit signed compare operations
Commit b7a0d65d80a0 ("bpf, testing: Workaround a verifier failure for test_progs") worked around a verifier failure where the register is copied to another later refined register, but the original register is used after refinement. The pattern looks like:
call ...
w1 = w0
w1 += -1
if w1 > 6 goto -24
w0 += w8
...
Register "w1" is refined, but "w0" is used later without taking advantage of new "w1" range, and eventually leading verifier to reject the program.
Instead of complicating verifier for such analysis, llvm patch https://reviews.llvm.org/D72787 added a phase to undo some original optimization and produces the code like below:
call ...
if w0 s< 0x1 goto pc-22
if w0 s> 0x7 goto pc-23
w0 += w8
...
Current verifier still rejects the above code. This patch intends to enhance verifier to handle the above pattern.
Note that the verifier is able to handle the case at non-alu32 mode,
call ...
if r0 s< 0x1 goto pc-22
if r0 s> 0x7 goto pc-23
r0 += r8
So the problem as described in
https://lore.kernel.org/netdev/[email protected]/
can be resolved with just compiler change.
The implementation in this patch set is just to cater the above pattern or similar to the above pattern. If you have some cases where the compiler generates a copy of register to refine but still use the original register later, please let me know, we could improve llvm/kernel to accommodate your use case.
Yonghong Song (2):
bpf: improve verifier handling for 32bit signed compare operations selftests/bpf: add selftests for verifier handling 32bit signed
compares
include/linux/bpf_verifier.h | 2 + kernel/bpf/verifier.c | 73 +++++++++++++++--- .../selftests/bpf/progs/test_sysctl_loop1.c | 5 +- tools/testing/selftests/bpf/verifier/jmp32.c | 76 +++++++++++++++++++ 4 files changed, 142 insertions(+), 14 deletions(-)
Signature · 1 line
2.17.1
PATCH 1/2 bpf: improve verifier handling for 32bit signed compare operations
Commit b7a0d65d80a0 ("bpf, testing: Workaround a verifier failure for test_progs") worked around a verifier failure where the register is copied to another later refined register, but the original register is used after refinement. Another similar example is
https://lore.kernel.org/netdev/[email protected]/
LLVM commit https://reviews.llvm.org/D72787 added a phase to adjust optimization such that the original register is directly refined and used later. Another issue exposed by the llvm is verifier cannot handle the following code:
call bpf_strtoul
if w0 s< 1 then ...
if w0 s> 7 then ...
... use w0 ...
Unfortunately, the verifier is not able to handle the above code well and will reject it.
call bpf_strtoul
R0_w=inv(id=0) R8=invP0
if w0 s< 0x1 goto pc-22
R0_w=inv(id=0) R8=invP0
if w0 s> 0x7 goto pc-23
R0=inv(id=0) R8=invP0
w0 += w8
R0_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R8=invP0After "w0 += w8", we got a very conservative R0 value, which later on caused verifier rejection.
This patch added two register states, s32_min_value and s32_max_value, to bpf_reg_state. These two states capture the signed 32bit
min/max values refined due to 32bit signed sle/slt/sge/sgt comparisons.
1. whenever refined s32_min_value, s32_max_value is captured, reg->var_off will be refined if possible.
2. For any ALU32 operation where the dst_reg will have upper 32bit cleared, if s32_min_value >= 0 and s32_max_value has been narrowed due to previous signed compare operation, the dst_reg as an input can ignore upper 32bit values, this may produce better output dst_reg value range.
3. s32_min_value and s32_max_value is reset if the corresponding register is redefined.
The following shows the new register states for the above example.
call bpf_strtoul
R0_w=inv(id=0) R8=invP0
if w0 s< 0x1 goto pc-22
R0_w=inv(id=0,smax_value=9223372034707292159,umax_value=18446744071562067967,
s32_min_value=1,var_off=(0x0; 0xffffffff7fffffff))
R8=invP0
if w0 s> 0x7 goto pc-23
R0=inv(id=0,smax_value=9223372032559808519,umax_value=18446744069414584327,
s32_min_value=1,s32_max_value=7,var_off=(0x0; 0xffffffff00000007))
R8=invP0
w0 += w8
R0_w=inv(id=0,umax_value=7,var_off=(0x0; 0x7)) R8=invP0With the above LLVM patch and this commit, the original workaround in Commit b7a0d65d80a0 is not needed any more.
--- include/linux/bpf_verifier.h | 2 + kernel/bpf/verifier.c | 73 +++++++++++++++++++++++++++++++----- 2 files changed, 65 insertions(+), 10 deletions(-)
include/linux/bpf_verifier.h +2 -0
@@ -123,6 +123,8 @@ struct bpf_reg_state {s64 smax_value;/* maximum possible (s64)value */ u64 umin_value;/* minimum possible (u64)value */ u64 umax_value;/* maximum possible (u64)value */ +s32 s32_min_value;/* minimum possible (s32)value */ +s32 s32_max_value;/* maximum possible (s32)value */ /* parentage chain for liveness checking */ struct bpf_reg_state *parent;/* Inside the callee two registers can be both PTR_TO_STACK like
kernel/bpf/verifier.c +63 -10
166 lines not on this page · raw message
Signature · 1 line
2.17.1
John Fastabend
reviewerQuoted 7 lines · Yonghong Song
Commit
b7a0d65d80a0("bpf, testing: Workaround a verifier failure fortest_progs") worked around a verifier failure where the register is copied to another later refined register, but the original register is used after refinement. Another similar example is
https://lore.kernel.org/netdev/[email protected]/LLVM commit https://reviews.llvm.org/D72787 added a phase
FWIW I was going to try and see if we could refine the bounds by walking parents chain. But that is an experiment tbd.
Quoted 22 lines
to adjust optimization such that the original register is directly refined and used later. Another issue exposed by the llvm is verifier cannot handle the following code:
callbpf_strtoul
if w0 s< 1 then ...
if w0 s> 7 then ...
... use w0 ...Unfortunately, the verifier is not able to handle the above code well and will reject it.
callbpf_strtoulR0_w=inv(id=0) R8=invP0 if w0 s< 0x1 goto pc-22 R0_w=inv(id=0) R8=invP0 if w0 s> 0x7 goto pc-23 R0=inv(id=0) R8=invP0 w0 += w8 R0_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R8=invP0After "w0 += w8", we got a very conservative R0 value, which later on caused verifier rejection.
Quoted 9 lines
This patch added two register states,
s32_min_valueands32_max_value, tobpf_reg_state. These two states capture the signed 32bit
min/max values refined due to 32bit signed sle/slt/sge/sgt comparisons.
1. whenever refineds32_min_value,s32_max_valueis captured,reg->var_offwill be refined if possible.
2. For any ALU32 operation where thedst_regwill have upper 32bit cleared, ifs32_min_value>= 0 ands32_max_valuehas been narrowed due to previous signed compare operation, thedst_regas an input can ignore upper 32bit values, this may produce better outputdst_regvalue range.
Can you comment a bit more on the s32_min_value < 0 case? Regardless of the s32_{min|max}_value the result should be zero extended and smin_value=0. This is enforced by verifier_zext(), an aside but I think we should just remove verifier_zext its not very useful if all jits have to comply imo.
If smin_value=0 && s32_max_value>=0 then we should be safe to propagate s32_max_value into smax_Value as well.
Quoted 5 lines
3.
s32_min_valueands32_max_valueis reset if the corresponding register is redefined.The following shows the new register states for the above example.
callbpf_strtoul
Quoted 11 lines
R0_w=inv(id=0) R8=invP0
if w0 s< 0x1 goto pc-22
R0_w=inv(id=0,smax_value=9223372034707292159,umax_value=18446744071562067967,
s32_min_value=1,var_off=(0x0; 0xffffffff7fffffff))
R8=invP0
if w0 s> 0x7 goto pc-23
R0=inv(id=0,smax_value=9223372032559808519,umax_value=18446744069414584327,
s32_min_value=1,s32_max_value=7,var_off=(0x0; 0xffffffff00000007))
R8=invP0
w0 += w8
R0_w=inv(id=0,umax_value=7,var_off=(0x0; 0x7)) R8=invP0And we should also have smin_value=0?
Quoted 43 lines
With the above LLVM patch and this commit, the original workaround in Commit
b7a0d65d80a0is not needed any more.Signed-off-by Yonghong Song <[email protected]>--- include/linux/bpf_verifier.h | 2 + kernel/bpf/verifier.c | 73 +++++++++++++++++++++++++++++++----- 2 files changed, 65 insertions(+), 10 deletions(-)include/linux/bpf_verifier.h +2
-0@@ -123,6 +123,8 @@ struct bpf_reg_state {s64 smax_value;/* maximum possible (s64)value */ u64 umin_value;/* minimum possible (u64)value */ u64 umax_value;/* maximum possible (u64)value */ +s32 s32_min_value;/* minimum possible (s32)value */ +s32 s32_max_value;/* maximum possible (s32)value */ /* parentage chain for liveness checking */ struct bpf_reg_state *parent;/* Inside the callee two registers can be both PTR_TO_STACK like kernel/bpf/verifier.c +8
-0@@ -543,6 +543,14 @@ static void print_verifier_state(struct bpf_verifier_env *env,if (reg->umax_value !=U64_MAX )verbose (env,",umax_value=%llu" , (unsigned long long )reg->umax_value); +if (reg->s32_min_value != reg->umin_value && + reg->s32_min_value !=S32_MIN ) +verbose (env,",s32_min_value=%d" , + (int )reg->s32_min_value); +if (reg->s32_max_value != reg->umax_value && + reg->s32_max_value !=S32_MAX ) +verbose (env,",s32_max_value=%d" , + (int )reg->s32_max_value);if (!tnum_is_unknown (reg->var_off)) {char tn_buf[48 ];
kernel/bpf/verifier.c static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) · line 937
Quoted 7 lines
kernel/bpf/verifier.c +4
-0@@ -923,6 +931,10 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) reg->smax_value = (s64 )imm; reg->umin_value = imm; reg->umax_value = imm; + +/* no need to be precise, just reset s32_{min,max}_value */ + reg->s32_min_value =S32_MIN ; + reg->s32_max_value =S32_MAX ;
If its known it would make more sense to me to set the min/max value vs this shortcut. Otherwise we wont have bounds to compare against on a JMP32.
kernel/bpf/verifier.c static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) · line 938
Quoted 1 line
kernel/bpf/verifier.c +0
-0}
Still thinking through the rest, but figured it would be worth kicking the couple comments above out.. I'm trying to understand if the coerce_reg_size() can be made a bit cleaner.
Thanks,
John
Quoted 11 lines · John Fastabend
Quoted 7 lines · Yonghong Song
Commit
b7a0d65d80a0("bpf, testing: Workaround a verifier failure fortest_progs") worked around a verifier failure where the register is copied to another later refined register, but the original register is used after refinement. Another similar example is
https://lore.kernel.org/netdev/[email protected]/LLVM commit https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D72787&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=DA8e1B5r073vIqRrFz7MRA&m=MoQP7VnsPjDQ8_NbLoNfOhFXJ0BWpjIq29RBOqKCVO0&s=a9JM4PoQiQlvFWOgb7Jn2y-dv1D78nK5gaFe4uLOgDU&e= added a phase
FWIW I was going to try and see if we could refine the bounds by walking parents chain. But that is an experiment tbd.
My current implementation is limited to use cases I see. So please do ahead to experiment with your use cases if you want to, or let me know I can implement for you.
Quoted 33 lines
Quoted 23 lines
to adjust optimization such that the original register is directly refined and used later. Another issue exposed by the llvm is verifier cannot handle the following code:
call bpf_strtoul if w0 s< 1 then ... if w0 s> 7 then ... ... use w0 ...Unfortunately, the verifier is not able to handle the above code well and will reject it.
callbpf_strtoulR0_w=inv(id=0) R8=invP0 if w0 s< 0x1 goto pc-22 R0_w=inv(id=0) R8=invP0 if w0 s> 0x7 goto pc-23 R0=inv(id=0) R8=invP0 w0 += w8 R0_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R8=invP0After "w0 += w8", we got a very conservative R0 value, which later on caused verifier rejection.
Quoted 9 lines
This patch added two register states,
s32_min_valueands32_max_value, tobpf_reg_state. These two states capture the signed 32bit
min/max values refined due to 32bit signed sle/slt/sge/sgt comparisons.
1. whenever refineds32_min_value,s32_max_valueis captured,reg->var_offwill be refined if possible.
2. For any ALU32 operation where thedst_regwill have upper 32bit cleared, ifs32_min_value>= 0 ands32_max_valuehas been narrowed due to previous signed compare operation, thedst_regas an input can ignore upper 32bit values, this may produce better outputdst_regvalue range.
Quoted 4 lines
Can you comment a bit more on the
s32_min_value< 0 case? Regardless of the s32_{min|max}_value the result should be zero extended and smin_value=0. This is enforced byverifier_zext(), an aside but I think we should just removeverifier_zextits not very useful if all jits have to comply imo.
I am not aware of verifier_zext, need to take a look.
The reason I required s32_min_value >= 0 is in coerce_reg_to_size() eventually we have reg->smin_value = reg->umin_value,
so smin_value >= 0 here. I am not fully understand why we did this way and thought requiring s32_min_value >= 0 will at least making the eventually smin_value/smax_value correctly.
If you can help explain coerce_reg_to_size(), especially why we do
reg->smin_value = reg->umin_value;
Quoted 21 lines
If smin_value=0 && s32_max_value>=0 then we should be safe to propagate
s32_max_valueintosmax_Valueas well.Quoted 5 lines
3.
s32_min_valueands32_max_valueis reset if the corresponding register is redefined.The following shows the new register states for the above example.
callbpf_strtoulQuoted 11 lines
R0_w=inv(id=0) R8=invP0 if w0 s< 0x1 goto pc-22 R0_w=inv(id=0,smax_value=9223372034707292159,umax_value=18446744071562067967, s32_min_value=1,var_off=(0x0; 0xffffffff7fffffff)) R8=invP0 if w0 s> 0x7 goto pc-23 R0=inv(id=0,smax_value=9223372032559808519,umax_value=18446744069414584327, s32_min_value=1,s32_max_value=7,var_off=(0x0; 0xffffffff00000007)) R8=invP0 w0 += w8 R0_w=inv(id=0,umax_value=7,var_off=(0x0; 0x7)) R8=invP0
Quoted 1 line
And we should also have smin_value=0?
Right, I need to check smin_value update in function adjust_scalar_min_max_vals().
Quoted 43 lines
Quoted 43 lines
With the above LLVM patch and this commit, the original workaround in Commit
b7a0d65d80a0is not needed any more.Signed-off-by Yonghong Song <[email protected]>--- include/linux/bpf_verifier.h | 2 + kernel/bpf/verifier.c | 73 +++++++++++++++++++++++++++++++----- 2 files changed, 65 insertions(+), 10 deletions(-)include/linux/bpf_verifier.h +2
-0@@ -123,6 +123,8 @@ struct bpf_reg_state {s64 smax_value;/* maximum possible (s64)value */ u64 umin_value;/* minimum possible (u64)value */ u64 umax_value;/* maximum possible (u64)value */ +s32 s32_min_value;/* minimum possible (s32)value */ +s32 s32_max_value;/* maximum possible (s32)value */ /* parentage chain for liveness checking */ struct bpf_reg_state *parent;/* Inside the callee two registers can be both PTR_TO_STACK like kernel/bpf/verifier.c +8
-0@@ -543,6 +543,14 @@ static void print_verifier_state(struct bpf_verifier_env *env,if (reg->umax_value !=U64_MAX )verbose (env,",umax_value=%llu" , (unsigned long long )reg->umax_value); +if (reg->s32_min_value != reg->umin_value && + reg->s32_min_value !=S32_MIN ) +verbose (env,",s32_min_value=%d" , + (int )reg->s32_min_value); +if (reg->s32_max_value != reg->umax_value && + reg->s32_max_value !=S32_MAX ) +verbose (env,",s32_max_value=%d" , + (int )reg->s32_max_value);if (!tnum_is_unknown (reg->var_off)) {char tn_buf[48 ];
Quoted 11 lines
kernel/bpf/verifier.c static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) · line 937
Quoted 8 lines
kernel/bpf/verifier.c +4
-0@@ -923,6 +931,10 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) reg->smax_value = (s64 )imm; reg->umin_value = imm; reg->umax_value = imm; + +/* no need to be precise, just reset s32_{min,max}_value */ + reg->s32_min_value =S32_MIN ; + reg->s32_max_value =S32_MAX ;If its known it would make more sense to me to set the min/max value vs this shortcut. Otherwise we wont have bounds to compare against on a JMP32.
With JMP32, we will do a coerce_reg_to_size(). For a single constant, we should be okay as long as the value is in 32bit range. But for consistent reasons, I can make s32_{min|max}_value more precise here.
Quoted 6 lines
kernel/bpf/verifier.c static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) · line 938
Quoted 2 lines
kernel/bpf/verifier.c +0
-0}Still thinking through the rest, but figured it would be worth kicking the couple comments above out.. I'm trying to understand if the
coerce_reg_size()can be made a bit cleaner.
Thanks for the review! The logic is pretty complex. Indeed coerce_reg_to_size() is one place I did not fully understand how it works.
Quoted 4 lines
Thanks,
John
PATCH 2/2 selftests/bpf: add selftests for verifier handling 32bit signed compares
In reply to Yonghong SongAdded a few verifier tests for 32bit signed compares.
$ ./test_verifier ... #557/p jsle32, jsge32, mov : combining range OK #558/p jslt32, jsgt32, add : combining range OK #559/p jslt32, jsgt32 : negative lower bound OK ...
Also reverted the workaround in test_sysctl_loop1.c since the kernel verifier is able to handle the case now.
$ ./test_progs ... #4/18 test_sysctl_loop1.o:OK ... For non-alu32 mode where llvm optimization (https://reviews.llvm.org/D72787) also kicked in, existing verifier can handle it well: $ ./test_progs-no-alu32 ... #4/18 test_sysctl_loop1.o:OK ...
--- .../selftests/bpf/progs/test_sysctl_loop1.c | 5 +- tools/testing/selftests/bpf/verifier/jmp32.c | 76 +++++++++++++++++++ 2 files changed, 77 insertions(+), 4 deletions(-)
tools/testing/selftests/bpf/progs/test_sysctl_loop1.c +1 -4
@@ -44,10 +44,7 @@ int sysctl_tcp_mem(struct bpf_sysctl *ctx)unsigned long tcp_mem[TCP_MEM_LOOPS ] = {};char value[MAX_VALUE_STR_LEN ];unsigned char i, off =0 ; -/* a workaround to prevent compiler from generating -* codes verifier cannot handle yet. -*/ -volatile int ret; +int ret;if (ctx->write)return 0 ;
tools/testing/selftests/bpf/verifier/jmp32.c +76 -0
79 lines not on this page · raw message
Signature · 1 line
2.17.1