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@xxxxxxxxx>
> >> Signed-off-by: Yonghong Song <yhs@xxxxxx>
> >> ---
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@xxxxxxxxx>
> >> 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);
> >> +}
