Yonghong Song wrote: > > > On 2/4/20 11:55 AM, John Fastabend wrote: > > Alexei Starovoitov wrote: > >> On Fri, Jan 31, 2020 at 9:16 AM John Fastabend <john.fastabend@xxxxxxxxx> wrote: > >>> > >>> Also don't mind to build pseudo instruction here for signed extension > >>> but its not clear to me why we are getting different instruction > >>> selections? Its not clear to me why sext is being chosen in your case? [...] > >> zext is there both cases and it will be optimized with your llvm patch. > >> So please send it. Don't delay :) > > > > LLVM patch here, https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D73985&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=DA8e1B5r073vIqRrFz7MRA&m=VnK0SKxGnw_yzWjaO-cZFrmlZB9p86L4me-mWE_vDto&s=jwDJuAEdJ23HVcvIILvkfxvTNSe_cgHQFn_MpXssfXc&e= > > > > With updated LLVM I can pass selftests with above fix and additional patch > > below to get tighter bounds on 32bit registers. So going forward I think > > we need to review and assuming it looks good commit above llvm patch and > > then go forward with this series. > > Thanks. The llvm patch looks sane, but after applying the patch, I hit > several selftest failures. For example, strobemeta_nounroll1.o. > > The following is a brief analysis of the verifier state: > > 184: > R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0; > 0xffffffff00000001)) > R7=inv0 > > 184: (bc) w7 = w0 > 185: > R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0; > 0xffffffff00000001)) > R7_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0x1)) > > 185: (67) r7 <<= 32 > 186: > R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0; > 0xffffffff00000001)) > R7_w=inv(id=0,umax_value=4294967296,var_off=(0x0; 0x100000000)) > > 186: (77) r7 >>= 32 > 187: > R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0; > 0xffffffff00000001)) > R7_w=inv(id=0,umax_value=1,var_off=(0x0; 0x1)) > > You can see after left and right shift, we got a better R7 umax_value=1. > Without the left and right shift, eventually verifier complains. > > Can we make uname_value=1 at insn 'w7 = w0'? > Currently, we cannot do this due to the logic in coerce_reg_to_size(). > It looks correct to me to ignore the top mask as we know the upper 32bit > will be discarded. > > I have implemented in my previous patch to deal with signed compares. > The following is the patch to fix this particular issue: [...] > > With the above patch, there is still one more issue in test_seg6_loop.o, > which is related to llvm code generation, w.r.t. our strange 32bit > packet begin and packet end. > > The following patch is generated: > > 2: (61) r1 = *(u32 *)(r6 +76) > 3: R1_w=pkt(id=0,off=0,r=0,imm=0) R2_w=pkt_end(id=0,off=0,imm=0) > R6_w=ctx(id=0,off=0,imm=0) R10=fp0 > ; cursor = (void *)(long)skb->data; > 3: (bc) w8 = w1 > 4: R1_w=pkt(id=0,off=0,r=0,imm=0) R2_w=pkt_end(id=0,off=0,imm=0) > R6_w=ctx(id=0,off=0,imm=0) > R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0 > ; if ((void *)ipver + sizeof(*ipver) > data_end) > 4: (bf) r3 = r8 > > In the above r1 is packet pointer and after the assignment, it becomes a > scalar and will lead later verification failure. > > Without the patch, we generates: > 1: R1=ctx(id=0,off=0,imm=0) R6_w=ctx(id=0,off=0,imm=0) R10=fp0 > ; data_end = (void *)(long)skb->data_end; > 1: (61) r1 = *(u32 *)(r6 +80) > 2: R1_w=pkt_end(id=0,off=0,imm=0) R6_w=ctx(id=0,off=0,imm=0) R10=fp0 > ; cursor = (void *)(long)skb->data; > 2: (61) r8 = *(u32 *)(r6 +76) > 3: R1_w=pkt_end(id=0,off=0,imm=0) R6_w=ctx(id=0,off=0,imm=0) > R8_w=pkt(id=0,off=0,r=0,imm=0) R10=fp0 > ; if ((void *)ipver + sizeof(*ipver) > data_end) > 3: (bf) r2 = r8 > 4: R1_w=pkt_end(id=0,off=0,imm=0) R2_w=pkt(id=0,off=0,r=0,imm=0) > R6_w=ctx(id=0,off=0,imm=0) R8_w=pkt(id=0,off=0,r=0,imm=0) R10=fp0 > 4: (07) r2 += 1 > 5: R1_w=pkt_end(id=0,off=0,imm=0) R2_w=pkt(id=0,off=1,r=0,imm=0) > R6_w=ctx(id=0,off=0,imm=0) R8_w=pkt(id=0,off=0,r=0,imm=0) R10=fp0 > > r2 keeps as a packet pointer, so we don't have issues later. > > Not sure how we could fix this in llvm as llvm does not really have idea > the above w1 in w8 = w1 is a packet pointer. > OK thanks for analysis. I have this on my stack as well but need to check its correct still, diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 320e2df..3072dba7 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2804,8 +2804,11 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size) reg->umax_value = mask; } reg->smin_value = reg->umin_value; - if (reg->smax_value < 0 || reg->smax_value > reg->umax_value) + if (reg->smax_value < 0 || reg->smax_value > reg->umax_value) { reg->smax_value = reg->umax_value; + } else { + reg->umax_value = reg->smax_value; + } } this helps but still hitting above issue with the packet pointer as you pointed out. I'll sort out how we can fix this. Somewhat related we have a similar issue we hit fairly consistently I've been meaning to sort out where the cmp happens on a different register then is used in the call, for example something like this pseudocode r8 = r2 if r8 > blah goto +label r1 = dest_ptr r1 += r2 r2 = size r3 = ptr call #some_call and the verifier aborts because r8 was verified instead of r2. The working plan was to walk back in the def-use chain and sort it out but tbd. .John
