| Message ID | 20200825064608.2017937-1-yhs@fb.com |
|---|---|
| State | Accepted |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | fix a verifier failure with xor | expand |
On Mon, Aug 24, 2020 at 11:46:08PM -0700, Yonghong Song wrote: > bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. > Compared to llvm 10, llvm 11 and 12 generates xor instruction which > is not handled properly in verifier. The following illustrates the > problem: > > 16: (b4) w5 = 0 > 17: ... R5_w=inv0 ... > ... > 132: (a4) w5 ^= 1 > 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > ... > 37: (bc) w8 = w5 > 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) > R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > ... > 41: (bc) w3 = w8 > 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > 45: (56) if w3 != 0x0 goto pc+1 > ... R3_w=inv0 ... > 46: (b7) r1 = 34 > 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0) > 47: (0f) r7 += r1 > 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) > 48: (b4) w9 = 0 > 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) > 49: (69) r1 = *(u16 *)(r7 +0) > invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) > R7 offset is outside of the packet > > At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative > value of w5. At insn 45, in reality the condition should be always false. > But due to conservative value for w3, the verifier evaluates it could be > true and this later leads to verifier failure complaining potential > packet out-of-bound access. > > This patch implemented proper XOR support in verifier. > In the above example, we have: > 132: R5=invP0 > 132: (a4) w5 ^= 1 > 133: R5_w=invP1 > ... > 37: (bc) w8 = w5 > ... > 41: (bc) w3 = w8 > 42: R3_w=invP1 > ... > 45: (56) if w3 != 0x0 goto pc+1 > 47: R3_w=invP1 > ... > processed 353 insns ... > and the verifier can verify the program successfully. > > Cc: John Fastabend <john.fastabend@gmail.com> > Signed-off-by: Yonghong Song <yhs@fb.com> > --- > kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 66 insertions(+) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index dd24503ab3d3..a08cabc0f683 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg, > __update_reg_bounds(dst_reg); > } > > +static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg, > + struct bpf_reg_state *src_reg) > +{ > + bool src_known = tnum_subreg_is_const(src_reg->var_off); > + bool dst_known = tnum_subreg_is_const(dst_reg->var_off); > + struct tnum var32_off = tnum_subreg(dst_reg->var_off); > + s32 smin_val = src_reg->s32_min_value; > + > + /* Assuming scalar64_min_max_xor will be called so it is safe > + * to skip updating register for known case. > + */ > + if (src_known && dst_known) > + return; why? I've looked at _and() and _or() variants that do the same and couldn't quite remember why it's ok to do so. > + > + /* We get both minimum and maximum from the var32_off. */ > + dst_reg->u32_min_value = var32_off.value; > + dst_reg->u32_max_value = var32_off.value | var32_off.mask; > + > + if (dst_reg->s32_min_value >= 0 && smin_val >= 0) { > + /* XORing two positive sign numbers gives a positive, > + * so safe to cast u32 result into s32. > + */ > + dst_reg->s32_min_value = dst_reg->u32_min_value; > + dst_reg->s32_max_value = dst_reg->u32_max_value; > + } else { > + dst_reg->s32_min_value = S32_MIN; > + dst_reg->s32_max_value = S32_MAX; > + } > +} > + > +static void scalar_min_max_xor(struct bpf_reg_state *dst_reg, > + struct bpf_reg_state *src_reg) > +{ > + bool src_known = tnum_is_const(src_reg->var_off); > + bool dst_known = tnum_is_const(dst_reg->var_off); > + s64 smin_val = src_reg->smin_value; > + > + if (src_known && dst_known) { > + /* dst_reg->var_off.value has been updated earlier */ right, but that means that there is sort-of 'bug' (unnecessary operation) that caused me a lot of head scratching. scalar_min_max_and() and scalar_min_max_or() do the alu in similar situation: if (src_known && dst_known) { __mark_reg_known(dst_reg, dst_reg->var_off.value | src_reg->var_off.value); I guess it's still technically correct to repeat alu operation. second & and second | won't change the value of dst_reg, but it feels that it's correct by accident? John ? > + __mark_reg_known(dst_reg, dst_reg->var_off.value); > + return; > + } > + > + /* We get both minimum and maximum from the var_off. */ > + dst_reg->umin_value = dst_reg->var_off.value; > + dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask; I think this is correct, but I hope somebody else can analyze this as well. John, Ed ? > + > + if (dst_reg->smin_value >= 0 && smin_val >= 0) { > + /* XORing two positive sign numbers gives a positive, > + * so safe to cast u64 result into s64. > + */ > + dst_reg->smin_value = dst_reg->umin_value; > + dst_reg->smax_value = dst_reg->umax_value; > + } else { > + dst_reg->smin_value = S64_MIN; > + dst_reg->smax_value = S64_MAX; > + } > + > + __update_reg_bounds(dst_reg); > +}
On 8/25/20 6:58 PM, Alexei Starovoitov wrote: > On Mon, Aug 24, 2020 at 11:46:08PM -0700, Yonghong Song wrote: >> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. >> Compared to llvm 10, llvm 11 and 12 generates xor instruction which >> is not handled properly in verifier. The following illustrates the >> problem: >> >> 16: (b4) w5 = 0 >> 17: ... R5_w=inv0 ... >> ... >> 132: (a4) w5 ^= 1 >> 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... >> ... >> 37: (bc) w8 = w5 >> 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) >> R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... >> ... >> 41: (bc) w3 = w8 >> 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... >> 45: (56) if w3 != 0x0 goto pc+1 >> ... R3_w=inv0 ... >> 46: (b7) r1 = 34 >> 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0) >> 47: (0f) r7 += r1 >> 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) >> 48: (b4) w9 = 0 >> 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) >> 49: (69) r1 = *(u16 *)(r7 +0) >> invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) >> R7 offset is outside of the packet >> >> At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative >> value of w5. At insn 45, in reality the condition should be always false. >> But due to conservative value for w3, the verifier evaluates it could be >> true and this later leads to verifier failure complaining potential >> packet out-of-bound access. >> >> This patch implemented proper XOR support in verifier. >> In the above example, we have: >> 132: R5=invP0 >> 132: (a4) w5 ^= 1 >> 133: R5_w=invP1 >> ... >> 37: (bc) w8 = w5 >> ... >> 41: (bc) w3 = w8 >> 42: R3_w=invP1 >> ... >> 45: (56) if w3 != 0x0 goto pc+1 >> 47: R3_w=invP1 >> ... >> processed 353 insns ... >> and the verifier can verify the program successfully. >> >> Cc: John Fastabend <john.fastabend@gmail.com> >> Signed-off-by: Yonghong Song <yhs@fb.com> >> --- >> kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++ >> 1 file changed, 66 insertions(+) >> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c >> index dd24503ab3d3..a08cabc0f683 100644 >> --- a/kernel/bpf/verifier.c >> +++ b/kernel/bpf/verifier.c >> @@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg, >> __update_reg_bounds(dst_reg); >> } >> >> +static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg, >> + struct bpf_reg_state *src_reg) >> +{ >> + bool src_known = tnum_subreg_is_const(src_reg->var_off); >> + bool dst_known = tnum_subreg_is_const(dst_reg->var_off); >> + struct tnum var32_off = tnum_subreg(dst_reg->var_off); >> + s32 smin_val = src_reg->s32_min_value; >> + >> + /* Assuming scalar64_min_max_xor will be called so it is safe >> + * to skip updating register for known case. >> + */ >> + if (src_known && dst_known) >> + return; > > why? > I've looked at _and() and _or() variants that do the same and > couldn't quite remember why it's ok to do so. Yes, I copied what _and() and _or() did. What I thought is if both known, 64bit scalar_min_max_xor() handled this and did not go though the approximation below, so that is why we return here. John, could you confirm? > >> + >> + /* We get both minimum and maximum from the var32_off. */ >> + dst_reg->u32_min_value = var32_off.value; >> + dst_reg->u32_max_value = var32_off.value | var32_off.mask; >> + >> + if (dst_reg->s32_min_value >= 0 && smin_val >= 0) { >> + /* XORing two positive sign numbers gives a positive, >> + * so safe to cast u32 result into s32. >> + */ >> + dst_reg->s32_min_value = dst_reg->u32_min_value; >> + dst_reg->s32_max_value = dst_reg->u32_max_value; >> + } else { >> + dst_reg->s32_min_value = S32_MIN; >> + dst_reg->s32_max_value = S32_MAX; >> + } >> +} >> + >> +static void scalar_min_max_xor(struct bpf_reg_state *dst_reg, >> + struct bpf_reg_state *src_reg) >> +{ >> + bool src_known = tnum_is_const(src_reg->var_off); >> + bool dst_known = tnum_is_const(dst_reg->var_off); >> + s64 smin_val = src_reg->smin_value; >> + >> + if (src_known && dst_known) { >> + /* dst_reg->var_off.value has been updated earlier */ > > right, but that means that there is sort-of 'bug' (unnecessary operation) > that caused me a lot of head scratching. > scalar_min_max_and() and scalar_min_max_or() do the alu in similar situation: > if (src_known && dst_known) { > __mark_reg_known(dst_reg, dst_reg->var_off.value | > src_reg->var_off.value); > I guess it's still technically correct to repeat alu operation. > second & and second | won't change the value of dst_reg, > but it feels that it's correct by accident? > John ? I think for or and add, additional dst_reg op src_reg is okay. For example, for "and", the computation looks like dst = dst & src dst = dst & src result will be the same as dst = dst & src and the second is redundant and can be replaced with dst. The same for or, dst = dst | src dst = dst | src is the same as "dst = dst | src" and the second is redundant. So for and/or, the __mark_reg_known can just take dst_reg->var_off.value, but the current code is also correct but can be simplified. This is not the case xor (^). The extra computation will change expected value. > >> + __mark_reg_known(dst_reg, dst_reg->var_off.value); >> + return; >> + } >> + >> + /* We get both minimum and maximum from the var_off. */ >> + dst_reg->umin_value = dst_reg->var_off.value; >> + dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask; > > I think this is correct, but I hope somebody else can analyze this as well. > John, Ed ? Please do double check. Thanks. > >> + >> + if (dst_reg->smin_value >= 0 && smin_val >= 0) { >> + /* XORing two positive sign numbers gives a positive, >> + * so safe to cast u64 result into s64. >> + */ >> + dst_reg->smin_value = dst_reg->umin_value; >> + dst_reg->smax_value = dst_reg->umax_value; >> + } else { >> + dst_reg->smin_value = S64_MIN; >> + dst_reg->smax_value = S64_MAX; >> + } >> + >> + __update_reg_bounds(dst_reg); >> +}
Yonghong Song wrote: > > > On 8/25/20 6:58 PM, Alexei Starovoitov wrote: > > On Mon, Aug 24, 2020 at 11:46:08PM -0700, Yonghong Song wrote: > >> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. > >> Compared to llvm 10, llvm 11 and 12 generates xor instruction which > >> is not handled properly in verifier. The following illustrates the > >> problem: > >> > >> 16: (b4) w5 = 0 > >> 17: ... R5_w=inv0 ... > >> ... > >> 132: (a4) w5 ^= 1 > >> 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > >> ... > >> 37: (bc) w8 = w5 > >> 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) > >> R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > >> ... > >> 41: (bc) w3 = w8 > >> 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > >> 45: (56) if w3 != 0x0 goto pc+1 > >> ... R3_w=inv0 ... > >> 46: (b7) r1 = 34 > >> 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0) > >> 47: (0f) r7 += r1 > >> 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) > >> 48: (b4) w9 = 0 > >> 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) > >> 49: (69) r1 = *(u16 *)(r7 +0) > >> invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) > >> R7 offset is outside of the packet > >> > >> At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative > >> value of w5. At insn 45, in reality the condition should be always false. > >> But due to conservative value for w3, the verifier evaluates it could be > >> true and this later leads to verifier failure complaining potential > >> packet out-of-bound access. > >> > >> This patch implemented proper XOR support in verifier. > >> In the above example, we have: > >> 132: R5=invP0 > >> 132: (a4) w5 ^= 1 > >> 133: R5_w=invP1 > >> ... > >> 37: (bc) w8 = w5 > >> ... > >> 41: (bc) w3 = w8 > >> 42: R3_w=invP1 > >> ... > >> 45: (56) if w3 != 0x0 goto pc+1 > >> 47: R3_w=invP1 > >> ... > >> processed 353 insns ... > >> and the verifier can verify the program successfully. > >> > >> Cc: John Fastabend <john.fastabend@gmail.com> > >> Signed-off-by: Yonghong Song <yhs@fb.com> > >> --- Thanks! Although we use llvm11 (+ some extra patches) and I haven't seen this yet if I get some time I'll try to see if I can get something to generate this code. Acked-by: John Fastabend <john.fastabend@gmail.com> > >> kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++ > >> 1 file changed, 66 insertions(+) > >> > >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > >> index dd24503ab3d3..a08cabc0f683 100644 > >> --- a/kernel/bpf/verifier.c > >> +++ b/kernel/bpf/verifier.c > >> @@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg, > >> __update_reg_bounds(dst_reg); > >> } > >> > >> +static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg, > >> + struct bpf_reg_state *src_reg) > >> +{ > >> + bool src_known = tnum_subreg_is_const(src_reg->var_off); > >> + bool dst_known = tnum_subreg_is_const(dst_reg->var_off); > >> + struct tnum var32_off = tnum_subreg(dst_reg->var_off); > >> + s32 smin_val = src_reg->s32_min_value; > >> + > >> + /* Assuming scalar64_min_max_xor will be called so it is safe > >> + * to skip updating register for known case. > >> + */ > >> + if (src_known && dst_known) > >> + return; > > > > why? > > I've looked at _and() and _or() variants that do the same and > > couldn't quite remember why it's ok to do so. > > Yes, I copied what _and() and _or() did. What I thought is > if both known, 64bit scalar_min_max_xor() handled this and did > not go though the approximation below, so that is why we return here. > John, could you confirm? > > > > >> + > >> + /* We get both minimum and maximum from the var32_off. */ > >> + dst_reg->u32_min_value = var32_off.value; > >> + dst_reg->u32_max_value = var32_off.value | var32_off.mask; > >> + > >> + if (dst_reg->s32_min_value >= 0 && smin_val >= 0) { > >> + /* XORing two positive sign numbers gives a positive, > >> + * so safe to cast u32 result into s32. > >> + */ > >> + dst_reg->s32_min_value = dst_reg->u32_min_value; > >> + dst_reg->s32_max_value = dst_reg->u32_max_value; > >> + } else { > >> + dst_reg->s32_min_value = S32_MIN; > >> + dst_reg->s32_max_value = S32_MAX; > >> + } > >> +} > >> + > >> +static void scalar_min_max_xor(struct bpf_reg_state *dst_reg, > >> + struct bpf_reg_state *src_reg) > >> +{ > >> + bool src_known = tnum_is_const(src_reg->var_off); > >> + bool dst_known = tnum_is_const(dst_reg->var_off); > >> + s64 smin_val = src_reg->smin_value; > >> + > >> + if (src_known && dst_known) { > >> + /* dst_reg->var_off.value has been updated earlier */ > > > > right, but that means that there is sort-of 'bug' (unnecessary operation) > > that caused me a lot of head scratching. > > scalar_min_max_and() and scalar_min_max_or() do the alu in similar situation: > > if (src_known && dst_known) { > > __mark_reg_known(dst_reg, dst_reg->var_off.value | > > src_reg->var_off.value); > > I guess it's still technically correct to repeat alu operation. > > second & and second | won't change the value of dst_reg, > > but it feels that it's correct by accident? > > John ? It is a hold-out from when we went from having a 32-bit var-off and a 64-bit var-off. I'll send a patch its clumsy and not needed for sure. The other subtle piece here we should clean up. Its possible to have a const in the subreg but a non-const in the wider 64-bit reg. In this case we skip marking the 32-bit subreg as known and rely on the 64-bit case to handle it. But, we may if the 64-bit reg is not const fall through and update the 64-bit bounds. Then later we call __update_reg32_bounds() and this will use the var_off, previously updated. The 32-bit bounds are then updated using this var_off so they are correct even if less precise than we might expect. I believe xor is correct here as well. I need to send another patch with a comment for the BTF_ID types. I'll add some test cases for this 64-bit non-const and subreg const so we don't break it later. I'm on the fence if we should tighten the bounds there as well. I'll see if it helps readability to do explicit 32-bit const handling there. I had it in one of the early series with the 32-bit bounds handling, but dropped for what we have now. > > I think for or and add, additional dst_reg op src_reg is okay. For > example, for "and", the computation looks like > dst = dst & src > dst = dst & src > result will be the same as > dst = dst & src > and the second is redundant and can be replaced with dst. > The same for or, > dst = dst | src > dst = dst | src > is the same as "dst = dst | src" and the second is redundant. So > for and/or, the __mark_reg_known can just take dst_reg->var_off.value, > but the current code is also correct but can be simplified. > > This is not the case xor (^). The extra computation will > change expected value. Right. > > > > >> + __mark_reg_known(dst_reg, dst_reg->var_off.value); > >> + return; > >> + } > >> + > >> + /* We get both minimum and maximum from the var_off. */ > >> + dst_reg->umin_value = dst_reg->var_off.value; > >> + dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask; > > > > I think this is correct, but I hope somebody else can analyze this as well. > > John, Ed ? > > Please do double check. Thanks. LGTM, but I see a couple follow up patches with tests, comments, and dropping the duplicate ALU op I'll try to do those Friday, unless someone else does them first. > > > > >> + > >> + if (dst_reg->smin_value >= 0 && smin_val >= 0) { > >> + /* XORing two positive sign numbers gives a positive, > >> + * so safe to cast u64 result into s64. > >> + */ > >> + dst_reg->smin_value = dst_reg->umin_value; > >> + dst_reg->smax_value = dst_reg->umax_value; > >> + } else { > >> + dst_reg->smin_value = S64_MIN; > >> + dst_reg->smax_value = S64_MAX; > >> + } > >> + > >> + __update_reg_bounds(dst_reg); > >> +}
On Wed, Aug 26, 2020 at 3:06 PM John Fastabend <john.fastabend@gmail.com> wrote: > > It is a hold-out from when we went from having a 32-bit var-off > and a 64-bit var-off. I'll send a patch its clumsy and not needed > for sure. please follow up with such patches. > The other subtle piece here we should clean up. Its possible > to have a const in the subreg but a non-const in the wider > 64-bit reg. In this case we skip marking the 32-bit subreg > as known and rely on the 64-bit case to handle it. But, we > may if the 64-bit reg is not const fall through and update > the 64-bit bounds. Then later we call __update_reg32_bounds() > and this will use the var_off, previously updated. The > 32-bit bounds are then updated using this var_off so they > are correct even if less precise than we might expect. I > believe xor is correct here as well. makes sense. I think it's correct now, but I agree that cleaning this up would be good as well. > I need to send another patch with a comment for the BTF_ID > types. I'll add some test cases for this 64-bit non-const and > subreg const so we don't break it later. I'm on the fence > if we should tighten the bounds there as well. I'll see if > it helps readability to do explicit 32-bit const handling > there. I had it in one of the early series with the 32-bit > bounds handling, but dropped for what we have now. Not following. Why is this related to btf_id ? > LGTM, but I see a couple follow up patches with tests, comments, > and dropping the duplicate ALU op I'll try to do those Friday, unless > someone else does them first. yes. please :) I've pushed this set to bpf-next in the meantime. Thanks everyone!
Alexei Starovoitov wrote: > On Wed, Aug 26, 2020 at 3:06 PM John Fastabend <john.fastabend@gmail.com> wrote: > > > > It is a hold-out from when we went from having a 32-bit var-off > > and a 64-bit var-off. I'll send a patch its clumsy and not needed > > for sure. > > please follow up with such patches. Great will go ahead and do this. > > > The other subtle piece here we should clean up. Its possible > > to have a const in the subreg but a non-const in the wider > > 64-bit reg. In this case we skip marking the 32-bit subreg > > as known and rely on the 64-bit case to handle it. But, we > > may if the 64-bit reg is not const fall through and update > > the 64-bit bounds. Then later we call __update_reg32_bounds() > > and this will use the var_off, previously updated. The > > 32-bit bounds are then updated using this var_off so they > > are correct even if less precise than we might expect. I > > believe xor is correct here as well. > > makes sense. I think it's correct now, but I agree that cleaning > this up would be good as well. > > > I need to send another patch with a comment for the BTF_ID > > types. I'll add some test cases for this 64-bit non-const and > > subreg const so we don't break it later. I'm on the fence > > if we should tighten the bounds there as well. I'll see if > > it helps readability to do explicit 32-bit const handling > > there. I had it in one of the early series with the 32-bit > > bounds handling, but dropped for what we have now. > > Not following. Why is this related to btf_id ? Its not related at all. I was just looking at patches on my stack here and I have unrelated comment only patch to clarify PTR_TO_BTF_ID_OR_NULL and PTR_TO_BTF_ID. > > > LGTM, but I see a couple follow up patches with tests, comments, > > and dropping the duplicate ALU op I'll try to do those Friday, unless > > someone else does them first. > > yes. please :) will do. > > I've pushed this set to bpf-next in the meantime. > Thanks everyone!
On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: > > bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. > Compared to llvm 10, llvm 11 and 12 generates xor instruction which Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If yes, is there something that one can do to prevent Clang from using xor in such situations? > is not handled properly in verifier. The following illustrates the > problem: > > 16: (b4) w5 = 0 > 17: ... R5_w=inv0 ... > ... > 132: (a4) w5 ^= 1 > 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > ... > 37: (bc) w8 = w5 > 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) > R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > ... > 41: (bc) w3 = w8 > 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... > 45: (56) if w3 != 0x0 goto pc+1 > ... R3_w=inv0 ... > 46: (b7) r1 = 34 > 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0) > 47: (0f) r7 += r1 > 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) > 48: (b4) w9 = 0 > 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) > 49: (69) r1 = *(u16 *)(r7 +0) > invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) > R7 offset is outside of the packet > > At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative > value of w5. At insn 45, in reality the condition should be always false. > But due to conservative value for w3, the verifier evaluates it could be > true and this later leads to verifier failure complaining potential > packet out-of-bound access. > > This patch implemented proper XOR support in verifier. > In the above example, we have: > 132: R5=invP0 > 132: (a4) w5 ^= 1 > 133: R5_w=invP1 > ... > 37: (bc) w8 = w5 > ... > 41: (bc) w3 = w8 > 42: R3_w=invP1 > ... > 45: (56) if w3 != 0x0 goto pc+1 > 47: R3_w=invP1 > ... > processed 353 insns ... > and the verifier can verify the program successfully. > > Cc: John Fastabend <john.fastabend@gmail.com> > Signed-off-by: Yonghong Song <yhs@fb.com> > --- > kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 66 insertions(+) > [...]
On 9/1/20 1:07 PM, Andrii Nakryiko wrote: > On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: >> >> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. >> Compared to llvm 10, llvm 11 and 12 generates xor instruction which > > Does this mean that some perfectly working BPF programs will now fail > to verify on older kernels, if compiled with llvm 11 or llvm 12? If Right. > yes, is there something that one can do to prevent Clang from using > xor in such situations? The xor is generated by the combination of llvm simplifyCFG and instrCombine phase. The following is a hack to prevent compiler from generating xor's. diff --git a/tools/testing/selftests/bpf/progs/test_sk_assign.c b/tools/testing/selftests/bpf/progs/test_sk_assi gn.c index 1ecd987005d2..b10ce8e9437e 100644 --- a/tools/testing/selftests/bpf/progs/test_sk_assign.c +++ b/tools/testing/selftests/bpf/progs/test_sk_assign.c @@ -97,15 +97,28 @@ handle_udp(struct __sk_buff *skb, struct bpf_sock_tuple *tuple, bool ipv4) __be16 dport; int ret; - tuple_len = ipv4 ? sizeof(tuple->ipv4) : sizeof(tuple->ipv6); - if ((void *)tuple + tuple_len > (void *)(long)skb->data_end) - return TC_ACT_SHOT; + if (ipv4) { + tuple_len = sizeof(tuple->ipv4); + if ((void *)tuple + tuple_len > (void *)(long)skb->data_end) + return TC_ACT_SHOT; + + sk = bpf_sk_lookup_udp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0); + if (sk) + goto assign; - sk = bpf_sk_lookup_udp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0); - if (sk) - goto assign; + dport = tuple->ipv4.dport; + } else { + tuple_len = sizeof(tuple->ipv6); + if ((void *)tuple + tuple_len > (void *)(long)skb->data_end) + return TC_ACT_SHOT; + + sk = bpf_sk_lookup_udp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0); + if (sk) + goto assign; + + dport = tuple->ipv6.dport; + } - dport = ipv4 ? tuple->ipv4.dport : tuple->ipv6.dport; if (dport != bpf_htons(4321)) return TC_ACT_OK; @@ -129,18 +142,34 @@ handle_tcp(struct __sk_buff *skb, struct bpf_sock_tuple *tuple, bool ipv4) __be16 dport; int ret; - tuple_len = ipv4 ? sizeof(tuple->ipv4) : sizeof(tuple->ipv6); - if ((void *)tuple + tuple_len > (void *)(long)skb->data_end) - return TC_ACT_SHOT; + if (ipv4) { + tuple_len = sizeof(tuple->ipv4); + if ((void *)tuple + tuple_len > (void *)(long)skb->data_end) + return TC_ACT_SHOT; - sk = bpf_skc_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0); - if (sk) { - if (sk->state != BPF_TCP_LISTEN) - goto assign; - bpf_sk_release(sk); + sk = bpf_skc_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0); + if (sk) { + if (sk->state != BPF_TCP_LISTEN) + goto assign; + bpf_sk_release(sk); + } + + dport = tuple->ipv4.dport; + } else { + tuple_len = sizeof(tuple->ipv6); + if ((void *)tuple + tuple_len > (void *)(long)skb->data_end) + return TC_ACT_SHOT; + + sk = bpf_skc_lookup_tcp(skb, tuple, tuple_len, BPF_F_CURRENT_NETNS, 0); + if (sk) { + if (sk->state != BPF_TCP_LISTEN) + goto assign; + bpf_sk_release(sk); + } + + dport = tuple->ipv6.dport; } - dport = ipv4 ? tuple->ipv4.dport : tuple->ipv6.dport; if (dport != bpf_htons(4321)) return TC_ACT_OK; The fundamental idea is the following. If you have code like if (cond) { BLOCK1; } else { BLOCK2; } BLOCK3; if (cond) { BLOCK4; } else { BLOCK5; } change the source code to if (cond) { BLOCK1; BLOCK3; BLOCK4; } else { BLOCK2; BLOCK3; BLOCK4; } If the condition is used in two different places, the compiler might do some transformation for control flow and later on instr simplification decides to use xor in certain cases. The new code has some code duplication. Not sure whether we should refactor the code or just add some note to selftests README.rst to describe this particular failure. > >> is not handled properly in verifier. The following illustrates the >> problem: >> >> 16: (b4) w5 = 0 >> 17: ... R5_w=inv0 ... >> ... >> 132: (a4) w5 ^= 1 >> 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... >> ... >> 37: (bc) w8 = w5 >> 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) >> R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... >> ... >> 41: (bc) w3 = w8 >> 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... >> 45: (56) if w3 != 0x0 goto pc+1 >> ... R3_w=inv0 ... >> 46: (b7) r1 = 34 >> 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0) >> 47: (0f) r7 += r1 >> 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) >> 48: (b4) w9 = 0 >> 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) >> 49: (69) r1 = *(u16 *)(r7 +0) >> invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) >> R7 offset is outside of the packet >> >> At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative >> value of w5. At insn 45, in reality the condition should be always false. >> But due to conservative value for w3, the verifier evaluates it could be >> true and this later leads to verifier failure complaining potential >> packet out-of-bound access. >> >> This patch implemented proper XOR support in verifier. >> In the above example, we have: >> 132: R5=invP0 >> 132: (a4) w5 ^= 1 >> 133: R5_w=invP1 >> ... >> 37: (bc) w8 = w5 >> ... >> 41: (bc) w3 = w8 >> 42: R3_w=invP1 >> ... >> 45: (56) if w3 != 0x0 goto pc+1 >> 47: R3_w=invP1 >> ... >> processed 353 insns ... >> and the verifier can verify the program successfully. >> >> Cc: John Fastabend <john.fastabend@gmail.com> >> Signed-off-by: Yonghong Song <yhs@fb.com> >> --- >> kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++ >> 1 file changed, 66 insertions(+) >> > > [...] >
Yonghong Song wrote: > > > On 9/1/20 1:07 PM, Andrii Nakryiko wrote: > > On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: > >> > >> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. > >> Compared to llvm 10, llvm 11 and 12 generates xor instruction which > > > > Does this mean that some perfectly working BPF programs will now fail > > to verify on older kernels, if compiled with llvm 11 or llvm 12? If > > Right. > > > yes, is there something that one can do to prevent Clang from using > > xor in such situations? > > The xor is generated by the combination of llvm simplifyCFG and > instrCombine phase. Another option would be to move it out of the isAsCheapAsAMove on the llvm side. But, probably better to force the workaround until kernels get support. Even with it being more expensive it wouldn't mean we never get it so likely not a great idea. Just thought it might be worth mentioning. If you have your own llvm and don't have these kernels yet it looks like a win. > > The following is a hack to prevent compiler from generating xor's.
On 9/1/20 10:27 PM, John Fastabend wrote: > Yonghong Song wrote: >> >> >> On 9/1/20 1:07 PM, Andrii Nakryiko wrote: >>> On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: >>>> >>>> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. >>>> Compared to llvm 10, llvm 11 and 12 generates xor instruction which >>> >>> Does this mean that some perfectly working BPF programs will now fail >>> to verify on older kernels, if compiled with llvm 11 or llvm 12? If >> >> Right. >> >>> yes, is there something that one can do to prevent Clang from using >>> xor in such situations? >> >> The xor is generated by the combination of llvm simplifyCFG and >> instrCombine phase. > > Another option would be to move it out of the isAsCheapAsAMove on the John, do you mean the following change? diff --git a/llvm/lib/Target/BPF/BPFInstrInfo.td b/llvm/lib/Target/BPF/BPFInstrInfo.td index 4298e2eaec04..7448a2499d40 100644 --- a/llvm/lib/Target/BPF/BPFInstrInfo.td +++ b/llvm/lib/Target/BPF/BPFInstrInfo.td @@ -293,9 +293,9 @@ let isAsCheapAsAMove = 1 in { defm AND : ALU<BPF_AND, "&=", and>; defm SLL : ALU<BPF_LSH, "<<=", shl>; defm SRL : ALU<BPF_RSH, ">>=", srl>; - defm XOR : ALU<BPF_XOR, "^=", xor>; defm SRA : ALU<BPF_ARSH, "s>>=", sra>; } + defm XOR : ALU<BPF_XOR, "^=", xor>; defm MUL : ALU<BPF_MUL, "*=", mul>; defm DIV : ALU<BPF_DIV, "/=", udiv>; } Tried the above change with latest trunk. xor still generated :-( I did not trace down to exact llvm optimization location for this particular optimization instance. > llvm side. But, probably better to force the workaround until kernels > get support. Even with it being more expensive it wouldn't mean we never > get it so likely not a great idea. Just thought it might be worth > mentioning. If you have your own llvm and don't have these kernels yet > it looks like a win. > >> >> The following is a hack to prevent compiler from generating xor's.
Yonghong Song <yhs@fb.com> writes: > On 9/1/20 1:07 PM, Andrii Nakryiko wrote: >> On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: >>> >>> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. >>> Compared to llvm 10, llvm 11 and 12 generates xor instruction which >> >> Does this mean that some perfectly working BPF programs will now fail >> to verify on older kernels, if compiled with llvm 11 or llvm 12? If > > Right. > >> yes, is there something that one can do to prevent Clang from using >> xor in such situations? > > The xor is generated by the combination of llvm simplifyCFG and > instrCombine phase. > > The following is a hack to prevent compiler from generating xor's. Wait, so this means that we can no longer tell people to just use the newest LLVM version - now we have to keep track of a minimum *and* maximum LLVM version for each kernel version? Could we maybe try to not *keep* making it harder for people to use BPF? :/ As for the patch, sure, make the verifier smarter, but I also feel like LLVM should be fixed to not suddenly emit such xor instructions... -Toke
On Wed, Sep 02, 2020 at 11:33:09AM +0200, Toke Høiland-Jørgensen wrote: > Yonghong Song <yhs@fb.com> writes: > > > On 9/1/20 1:07 PM, Andrii Nakryiko wrote: > >> On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: > >>> > >>> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. > >>> Compared to llvm 10, llvm 11 and 12 generates xor instruction which > >> > >> Does this mean that some perfectly working BPF programs will now fail > >> to verify on older kernels, if compiled with llvm 11 or llvm 12? If > > > > Right. > > > >> yes, is there something that one can do to prevent Clang from using > >> xor in such situations? > > > > The xor is generated by the combination of llvm simplifyCFG and > > instrCombine phase. > > > > The following is a hack to prevent compiler from generating xor's. > > Wait, so this means that we can no longer tell people to just use the > newest LLVM version - now we have to keep track of a minimum *and* > maximum LLVM version for each kernel version? No. The only way is forward. Everyone has to upgrade their llvm periodically. > Could we maybe try to not *keep* making it harder for people to use BPF? :/ Whom do you mean by "we" ? > As for the patch, sure, make the verifier smarter, but I also feel like > LLVM should be fixed to not suddenly emit such xor instructions... I don't think there is anything to be "fixed". It's not a bug form llvm developers point of view. At least I suspect that's the response you will get if you post the same sentence on llvm-dev mailing list. If you care to help, please bisect which llvm commit introduced this change. May be author (whoever that was) will have ideas how to pessimize it specifically for bpf backend. But I suspect they will refuse to do so. The discussion about partial disable of optimizations was brought up several times. tldr optimizations cannot be disabled effectively. Pretty much all of them may cause trouble for the verifier and all of them are often necessary for the verifier as well. Please read this thread: http://clang-developers.42468.n3.nabble.com/Disable-certain-llvm-optimizations-at-clang-frontend-tp4068601.html
Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: > On Wed, Sep 02, 2020 at 11:33:09AM +0200, Toke Høiland-Jørgensen wrote: >> Yonghong Song <yhs@fb.com> writes: >> >> > On 9/1/20 1:07 PM, Andrii Nakryiko wrote: >> >> On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: >> >>> >> >>> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. >> >>> Compared to llvm 10, llvm 11 and 12 generates xor instruction which >> >> >> >> Does this mean that some perfectly working BPF programs will now fail >> >> to verify on older kernels, if compiled with llvm 11 or llvm 12? If >> > >> > Right. >> > >> >> yes, is there something that one can do to prevent Clang from using >> >> xor in such situations? >> > >> > The xor is generated by the combination of llvm simplifyCFG and >> > instrCombine phase. >> > >> > The following is a hack to prevent compiler from generating xor's. >> >> Wait, so this means that we can no longer tell people to just use the >> newest LLVM version - now we have to keep track of a minimum *and* >> maximum LLVM version for each kernel version? > > No. The only way is forward. Everyone has to upgrade their llvm periodically. Right, great! But surely that implies that a regression such as that described here, where a new LLVM version turns a previously-valid program into one that no longer verifies is a bug, no? >> Could we maybe try to not *keep* making it harder for people to use BPF? :/ > > Whom do you mean by "we" ? I mean "we as a community who would like BPF to be as useful as possible to as many people as possible". Usability is a big part of this. >> As for the patch, sure, make the verifier smarter, but I also feel like >> LLVM should be fixed to not suddenly emit such xor instructions... > > I don't think there is anything to be "fixed". It's not a bug form > llvm developers point of view. At least I suspect that's the response > you will get if you post the same sentence on llvm-dev mailing list. > If you care to help, please bisect which llvm commit introduced this > change. May be author (whoever that was) will have ideas how to > pessimize it specifically for bpf backend. But I suspect they will > refuse to do so. The discussion about partial disable of optimizations > was brought up several times. tldr optimizations cannot be disabled > effectively. Pretty much all of them may cause trouble for the > verifier and all of them are often necessary for the verifier as well. > Please read this thread: > http://clang-developers.42468.n3.nabble.com/Disable-certain-llvm-optimizations-at-clang-frontend-tp4068601.html I am not enough of a compiler person to get the nuances of that discussion, but it seems that the last message[0] by Y Song seems to imply that you guys do want to fix such issues in LLVM, just not by disabling the optimisation, but at a later stage in the processing pipeline? -Toke [0] http://lists.llvm.org/pipermail/cfe-dev/2020-June/066015.html
On Wed, Sep 02, 2020 at 05:01:39PM +0200, Toke Høiland-Jørgensen wrote: > Alexei Starovoitov <alexei.starovoitov@gmail.com> writes: > > > On Wed, Sep 02, 2020 at 11:33:09AM +0200, Toke Høiland-Jørgensen wrote: > >> Yonghong Song <yhs@fb.com> writes: > >> > >> > On 9/1/20 1:07 PM, Andrii Nakryiko wrote: > >> >> On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: > >> >>> > >> >>> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. > >> >>> Compared to llvm 10, llvm 11 and 12 generates xor instruction which > >> >> > >> >> Does this mean that some perfectly working BPF programs will now fail > >> >> to verify on older kernels, if compiled with llvm 11 or llvm 12? If > >> > > >> > Right. > >> > > >> >> yes, is there something that one can do to prevent Clang from using > >> >> xor in such situations? > >> > > >> > The xor is generated by the combination of llvm simplifyCFG and > >> > instrCombine phase. > >> > > >> > The following is a hack to prevent compiler from generating xor's. > >> > >> Wait, so this means that we can no longer tell people to just use the > >> newest LLVM version - now we have to keep track of a minimum *and* > >> maximum LLVM version for each kernel version? > > > > No. The only way is forward. Everyone has to upgrade their llvm periodically. > > Right, great! But surely that implies that a regression such as that > described here, where a new LLVM version turns a previously-valid > program into one that no longer verifies is a bug, no? It's not a regression. Previous valid _compiled_ programs will load. Nothing guarantees that recompiled program will keep loading. Even if you keep compiler and source code constant the environment could change. That risk always existed in libbcc and in anything that compiles on the fly. A new version of bpftrace may suddenly start failing existing bpftrace scripts. No one wants this, of course, but we cannot guarantee 100%. > > >> Could we maybe try to not *keep* making it harder for people to use BPF? :/ > > > > Whom do you mean by "we" ? > > I mean "we as a community who would like BPF to be as useful as possible > to as many people as possible". Usability is a big part of this. Of course. I completely agree, but your previous statement said that somebody "is making it harder for people to use BPF"... and I asked whom did you point finger at. Sounds like you're saying that you are not a compiler person, so it's not your fault and some compiler person must be responsible? Well, we are all in the same boat and all are responsible for the outcome. > > >> As for the patch, sure, make the verifier smarter, but I also feel like > >> LLVM should be fixed to not suddenly emit such xor instructions... > > > > I don't think there is anything to be "fixed". It's not a bug form > > llvm developers point of view. At least I suspect that's the response > > you will get if you post the same sentence on llvm-dev mailing list. > > If you care to help, please bisect which llvm commit introduced this > > change. May be author (whoever that was) will have ideas how to > > pessimize it specifically for bpf backend. But I suspect they will > > refuse to do so. The discussion about partial disable of optimizations > > was brought up several times. tldr optimizations cannot be disabled > > effectively. Pretty much all of them may cause trouble for the > > verifier and all of them are often necessary for the verifier as well. > > Please read this thread: > > http://clang-developers.42468.n3.nabble.com/Disable-certain-llvm-optimizations-at-clang-frontend-tp4068601.html > > I am not enough of a compiler person to get the nuances of that > discussion, but it seems that the last message[0] by Y Song seems to > imply that you guys do want to fix such issues in LLVM, just not by > disabling the optimisation, but at a later stage in the processing > pipeline? Not really. The "fix such issues in LLVM" statement is missing the point. There is no _issue_ in LLVM and there is no _issue_ in the verifier. The word "fix" assigns the blame and implies a bug. The verifier is getting smarter. LLVM is getting smarter, but they follow different religions, so to speak. Reconciling the differences is what should happen. Inserting inline asm barriers at different stages of the compilation is a fragile hack. Both the verifier and the LLVM need to work towards each other. BPF programs are a pain to write. People keep fighting the verifier and fighting LLVM. Large progs are full of inline asm hacks (mostly written by humans) to please the verifier and force LLVM to do something that is against LLVM objectives. Yonghong is trying to come up with a set of heuristics to do this asm insertion automatically. It will help, for sure, but won't close every corner case. The verifier needs to get smarter too. Recognizing XORs in the verifier is the right thing to do. Missing XORs in older kernels is not a bug, but we might consider it a bug and backport this verifier feature to older kernels. LLVM vs verifier contest is outside of typical kernel bug vs feature classification of patches. I think we need to be creative here.
Yonghong Song wrote: > > > On 9/1/20 10:27 PM, John Fastabend wrote: > > Yonghong Song wrote: > >> > >> > >> On 9/1/20 1:07 PM, Andrii Nakryiko wrote: > >>> On Mon, Aug 24, 2020 at 11:47 PM Yonghong Song <yhs@fb.com> wrote: > >>>> > >>>> bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. > >>>> Compared to llvm 10, llvm 11 and 12 generates xor instruction which > >>> > >>> Does this mean that some perfectly working BPF programs will now fail > >>> to verify on older kernels, if compiled with llvm 11 or llvm 12? If > >> > >> Right. > >> > >>> yes, is there something that one can do to prevent Clang from using > >>> xor in such situations? > >> > >> The xor is generated by the combination of llvm simplifyCFG and > >> instrCombine phase. > > > > Another option would be to move it out of the isAsCheapAsAMove on the > > John, do you mean the following change? > > diff --git a/llvm/lib/Target/BPF/BPFInstrInfo.td > b/llvm/lib/Target/BPF/BPFInstrInfo.td > index 4298e2eaec04..7448a2499d40 100644 > --- a/llvm/lib/Target/BPF/BPFInstrInfo.td > +++ b/llvm/lib/Target/BPF/BPFInstrInfo.td > @@ -293,9 +293,9 @@ let isAsCheapAsAMove = 1 in { > defm AND : ALU<BPF_AND, "&=", and>; > defm SLL : ALU<BPF_LSH, "<<=", shl>; > defm SRL : ALU<BPF_RSH, ">>=", srl>; > - defm XOR : ALU<BPF_XOR, "^=", xor>; > defm SRA : ALU<BPF_ARSH, "s>>=", sra>; > } > + defm XOR : ALU<BPF_XOR, "^=", xor>; > defm MUL : ALU<BPF_MUL, "*=", mul>; > defm DIV : ALU<BPF_DIV, "/=", udiv>; > } > > Tried the above change with latest trunk. xor still generated :-( > I did not trace down to exact llvm optimization location for this > particular optimization instance. Agh I assumed that would work. I might have some time to mess around with it tomorrow. Now I'm just curious why that is being generated. Thanks for trying!
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index dd24503ab3d3..a08cabc0f683 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg, __update_reg_bounds(dst_reg); } +static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg, + struct bpf_reg_state *src_reg) +{ + bool src_known = tnum_subreg_is_const(src_reg->var_off); + bool dst_known = tnum_subreg_is_const(dst_reg->var_off); + struct tnum var32_off = tnum_subreg(dst_reg->var_off); + s32 smin_val = src_reg->s32_min_value; + + /* Assuming scalar64_min_max_xor will be called so it is safe + * to skip updating register for known case. + */ + if (src_known && dst_known) + return; + + /* We get both minimum and maximum from the var32_off. */ + dst_reg->u32_min_value = var32_off.value; + dst_reg->u32_max_value = var32_off.value | var32_off.mask; + + if (dst_reg->s32_min_value >= 0 && smin_val >= 0) { + /* XORing two positive sign numbers gives a positive, + * so safe to cast u32 result into s32. + */ + dst_reg->s32_min_value = dst_reg->u32_min_value; + dst_reg->s32_max_value = dst_reg->u32_max_value; + } else { + dst_reg->s32_min_value = S32_MIN; + dst_reg->s32_max_value = S32_MAX; + } +} + +static void scalar_min_max_xor(struct bpf_reg_state *dst_reg, + struct bpf_reg_state *src_reg) +{ + bool src_known = tnum_is_const(src_reg->var_off); + bool dst_known = tnum_is_const(dst_reg->var_off); + s64 smin_val = src_reg->smin_value; + + if (src_known && dst_known) { + /* dst_reg->var_off.value has been updated earlier */ + __mark_reg_known(dst_reg, dst_reg->var_off.value); + return; + } + + /* We get both minimum and maximum from the var_off. */ + dst_reg->umin_value = dst_reg->var_off.value; + dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask; + + if (dst_reg->smin_value >= 0 && smin_val >= 0) { + /* XORing two positive sign numbers gives a positive, + * so safe to cast u64 result into s64. + */ + dst_reg->smin_value = dst_reg->umin_value; + dst_reg->smax_value = dst_reg->umax_value; + } else { + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } + + __update_reg_bounds(dst_reg); +} + static void __scalar32_min_max_lsh(struct bpf_reg_state *dst_reg, u64 umin_val, u64 umax_val) { @@ -6109,6 +6170,11 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, scalar32_min_max_or(dst_reg, &src_reg); scalar_min_max_or(dst_reg, &src_reg); break; + case BPF_XOR: + dst_reg->var_off = tnum_xor(dst_reg->var_off, src_reg.var_off); + scalar32_min_max_xor(dst_reg, &src_reg); + scalar_min_max_xor(dst_reg, &src_reg); + break; case BPF_LSH: if (umax_val >= insn_bitness) { /* Shifts greater than 31 or 63 are undefined.
bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which is not handled properly in verifier. The following illustrates the problem: 16: (b4) w5 = 0 17: ... R5_w=inv0 ... ... 132: (a4) w5 ^= 1 133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... ... 37: (bc) w8 = w5 38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... ... 41: (bc) w3 = w8 42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... 45: (56) if w3 != 0x0 goto pc+1 ... R3_w=inv0 ... 46: (b7) r1 = 34 47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0) 47: (0f) r7 += r1 48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) 48: (b4) w9 = 0 49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0) 49: (69) r1 = *(u16 *)(r7 +0) invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) R7 offset is outside of the packet At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative value of w5. At insn 45, in reality the condition should be always false. But due to conservative value for w3, the verifier evaluates it could be true and this later leads to verifier failure complaining potential packet out-of-bound access. This patch implemented proper XOR support in verifier. In the above example, we have: 132: R5=invP0 132: (a4) w5 ^= 1 133: R5_w=invP1 ... 37: (bc) w8 = w5 ... 41: (bc) w3 = w8 42: R3_w=invP1 ... 45: (56) if w3 != 0x0 goto pc+1 47: R3_w=invP1 ... processed 353 insns ... and the verifier can verify the program successfully. Cc: John Fastabend <john.fastabend@gmail.com> Signed-off-by: Yonghong Song <yhs@fb.com> --- kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+)