more test_progs...

more test_progs...

[David Miller]

I'm trying to get test_progs working in net-next on sparc, it can't
even load the first BPF program.  It's triggering this verifier
check:

static int check_pkt_ptr_alignment(const struct bpf_reg_state *reg,
                                   int off, int size)
{
        if (reg->id && size != 1) {
                verbose("Unknown alignment. Only byte-sized access allowed in packet access.\n");

Specifically (this is test_pkt_access.o of course):

libbpf: load bpf program failed: Permission denied
libbpf: -- BEGIN DUMP LOG ---
libbpf: 
0: (b7) r0 = 2
1: (61) r2 = *(u32 *)(r1 +80)

r2 = skb->data_end

2: (61) r1 = *(u32 *)(r1 +76)

r1 = skb->data

3: (bf) r4 = r1

r4 = skb->data

4: (07) r4 += 14

r4 += sizeof(struct ethhdr);

5: (2d) if r4 > r2 goto pc+37

if out of range, exit

 R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=14) R2=pkt_end R4=pkt(id=0,off=14,r=14) R10=fp

R1/R2/R4 analysis seems correct

6: (71) r5 = *(u8 *)(r1 +13)
7: (71) r3 = *(u8 *)(r1 +12)
8: (67) r3 <<= 8
9: (4f) r3 |= r5

Load eth->h_proto

10: (15) if r3 == 0xdd86 goto pc+9
 R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=14) R2=pkt_end R3=inv R4=pkt(id=0,off=14,r=14) R5=inv56 R10=fp

Hmmm, endianness looks wrong here.  "-target bpf" defaults to the
endianness of whatever cpu that llvm was built for, right?

Maybe I need to make even more adjustments to selftests/bpf/Makefile
handling of clang options...

Anyways this is checking for ipv6, if so goto insn 25

11: (55) if r3 != 0x8 goto pc+29
 R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=14) R2=pkt_end R3=inv,min_value=8,max_value=8 R4=pkt(id=0,off=14,r=14) R5=inv56 R10=fp

IPV4:

12: (bf) r3 = r1
13: (07) r3 += 34
14: (2d) if r3 > r2 goto pc+28

Make sure pkt + 34 is in range

 R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=34) R2=pkt_end R3=pkt(id=0,off=34,r=34) R4=pkt(id=0,off=14,r=34) R5=inv56 R10=fp
15: (b7) r3 = 3
16: (71) r5 = *(u8 *)(r4 +0)
17: (67) r5 <<= 2
18: (57) r5 &= 60
19: (05) goto pc+5

IPV6:

25: (bf) r4 = r1
26: (0f) r4 += r5
27: (07) r4 += 14
28: (15) if r4 == 0x0 goto pc+12
 R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=34) R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=14,r=0) R5=inv58,min_value=0,max_value=60 R10=fp
29: (bf) r5 = r4
30: (07) r5 += 20
31: (2d) if r5 > r2 goto pc+11
 R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=34) R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=14,r=34) R5=pkt(id=1,off=34,r=34) R10=fp
32: (0f) r1 += r3
33: (71) r1 = *(u8 *)(r1 +20)

Load ipv6 nexthdr

34: (57) r1 &= 255
35: (55) if r1 != 0x6 goto pc+7

if proto not TCP skip

 R0=imm2,min_value=2,max_value=2 R1=inv56,min_value=6,max_value=6 R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=14,r=34) R5=pkt(id=1,off=34,r=34) R10=fp
36: (07) r4 += 18
37: (2d) if r4 > r2 goto pc+5
 R0=imm2,min_value=2,max_value=2 R1=inv56,min_value=6,max_value=6 R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=32,r=34) R5=pkt(id=1,off=34,r=34) R10=fp
38: (b7) r0 = 0
39: (69) r1 = *(u16 *)(r4 +0)
Unknown alignment. Only byte-sized access allowed in packet access.

And this seems to load the urgent pointer as a u16 which is what the verifier rejects.

Oh I see, this is guarded by CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS.

How in the world is this supposed to work?

Re: more test_progs...

[Daniel Borkmann]

On 04/25/2017 06:52 PM, David Miller wrote:
[...]
> Load eth->h_proto
>
> 10: (15) if r3 == 0xdd86 goto pc+9
>   R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=14) R2=pkt_end R3=inv R4=pkt(id=0,off=14,r=14) R5=inv56 R10=fp
>
> Hmmm, endianness looks wrong here.  "-target bpf" defaults to the
> endianness of whatever cpu that llvm was built for, right?

Hmm, would it show the right endianess when you compile
with "-target bpfeb"?

My understanding is that "-target bpf" defaults to host
cpu's endianess, and since you likely built clang/llvm
directly on sparc, it should also all run on target
endianness anyway (so no potential mixup when compiling
f.e. bpfeb on x86_64).

Re: more test_progs...

[Alexei Starovoitov]

On 4/25/17 9:52 AM, David Miller wrote:
>
> 10: (15) if r3 == 0xdd86 goto pc+9
>  R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=14) R2=pkt_end R3=inv R4=pkt(id=0,off=14,r=14) R5=inv56 R10=fp
>
> Hmmm, endianness looks wrong here.  "-target bpf" defaults to the
> endianness of whatever cpu that llvm was built for, right?

yeah. so here the code comes from:
         } else if (eth->h_proto == _htons(ETH_P_IPV6)) {

and in the beginning of that .c file:
#define _htons __builtin_bswap16
^^^ that's the bug.
It should have been nop for sparc.
We cannot use htons() from system header, since it uses x86 inline asm.

>  R0=imm2,min_value=2,max_value=2 R1=inv56,min_value=6,max_value=6 R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=14,r=34) R5=pkt(id=1,off=34,r=34) R10=fp
> 36: (07) r4 += 18
> 37: (2d) if r4 > r2 goto pc+5
>  R0=imm2,min_value=2,max_value=2 R1=inv56,min_value=6,max_value=6 R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=32,r=34) R5=pkt(id=1,off=34,r=34) R10=fp
> 38: (b7) r0 = 0
> 39: (69) r1 = *(u16 *)(r4 +0)
> Unknown alignment. Only byte-sized access allowed in packet access.
>
> And this seems to load the urgent pointer as a u16 which is what the verifier rejects.
>
> Oh I see, this is guarded by CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS.

yes. exactly.
Your analysis is correct and offending 16-bit load is this C code:
                 if (tcp->urg_ptr == 123)

the parsing code before that line deals with variable length ip header:
                 tcp = (struct tcphdr *)((void *)(iph) + ihl_len);

and at that point verifier cannot track the alignment of the pointer
anymore. It knows 'iph' alignment, but as soon as some variable is added
to it cannot assume good alignment anymore and from there on it
allows >1 byte accesses only on HAVE_EFFICIENT_UNALIGNED_ACCESS
architectures.
That's the 'if' that you found:
  'if (reg->id && size != 1) {'

ref->id > 0 means that some variable was added to ptr_to_packet.

That sucks for sparc, of course. I don't have good suggestions for
workaround other than marking tcphdr as packed :(
 From code efficiency point of view it still will be faster than
LD_ABS insn.
Another idea is to try to track that ihl_len variable is also
somehow multiple of 4, but it will be quite complicated on
the verifier side in its existing architecture and maybe? worth
waiting until the verifier has proper dataflow analysis.

Re: more test_progs...

[Daniel Borkmann]

On 04/26/2017 05:42 AM, Alexei Starovoitov wrote:
> On 4/25/17 9:52 AM, David Miller wrote:
>>
>> 10: (15) if r3 == 0xdd86 goto pc+9
>>  R0=imm2,min_value=2,max_value=2 R1=pkt(id=0,off=0,r=14) R2=pkt_end R3=inv R4=pkt(id=0,off=14,r=14) R5=inv56 R10=fp
>>
>> Hmmm, endianness looks wrong here.  "-target bpf" defaults to the
>> endianness of whatever cpu that llvm was built for, right?
>
> yeah. so here the code comes from:
>          } else if (eth->h_proto == _htons(ETH_P_IPV6)) {
>
> and in the beginning of that .c file:
> #define _htons __builtin_bswap16
> ^^^ that's the bug.
> It should have been nop for sparc.
> We cannot use htons() from system header, since it uses x86 inline asm.

Ahh yes, you're right! Wouldn't it be much easier for the above
case to just include <asm/byteorder.h> and use __constant_htons()?
(In fact, all htons() users in this file are constants.)

>>  R0=imm2,min_value=2,max_value=2 R1=inv56,min_value=6,max_value=6 R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=14,r=34) R5=pkt(id=1,off=34,r=34) R10=fp
>> 36: (07) r4 += 18
>> 37: (2d) if r4 > r2 goto pc+5
>>  R0=imm2,min_value=2,max_value=2 R1=inv56,min_value=6,max_value=6 R2=pkt_end R3=imm3,min_value=3,max_value=3 R4=pkt(id=1,off=32,r=34) R5=pkt(id=1,off=34,r=34) R10=fp
>> 38: (b7) r0 = 0
>> 39: (69) r1 = *(u16 *)(r4 +0)
>> Unknown alignment. Only byte-sized access allowed in packet access.
>>
>> And this seems to load the urgent pointer as a u16 which is what the verifier rejects.
>>
>> Oh I see, this is guarded by CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS.
>
> yes. exactly.
> Your analysis is correct and offending 16-bit load is this C code:
>                  if (tcp->urg_ptr == 123)
>
> the parsing code before that line deals with variable length ip header:
>                  tcp = (struct tcphdr *)((void *)(iph) + ihl_len);
>
> and at that point verifier cannot track the alignment of the pointer
> anymore. It knows 'iph' alignment, but as soon as some variable is added
> to it cannot assume good alignment anymore and from there on it
> allows >1 byte accesses only on HAVE_EFFICIENT_UNALIGNED_ACCESS
> architectures.
> That's the 'if' that you found:
>   'if (reg->id && size != 1) {'
>
> ref->id > 0 means that some variable was added to ptr_to_packet.
>
> That sucks for sparc, of course. I don't have good suggestions for
> workaround other than marking tcphdr as packed :(
>  From code efficiency point of view it still will be faster than
> LD_ABS insn.

Plus, ld_abs would also only work on skbs right now, and would
need JIT support for XDP. But it's also cumbersome to use with
f.e. IPv6, etc, so should not be encouraged, imo.

One other option for !HAVE_EFFICIENT_UNALIGNED_ACCESS archs could
be to provide a bpf_skb_load_bytes() helper equivalent for XDP,
where you eventually do the memcpy() inside. We could see to inline
the helper itself to optimize it slightly.

> Another idea is to try to track that ihl_len variable is also
> somehow multiple of 4, but it will be quite complicated on
> the verifier side in its existing architecture and maybe? worth
> waiting until the verifier has proper dataflow analysis.

Re: more test_progs...

[David Miller]

From: Daniel Borkmann <daniel@iogearbox.net>
Date: Wed, 26 Apr 2017 10:14:42 +0200

> On 04/26/2017 05:42 AM, Alexei Starovoitov wrote:
>> That sucks for sparc, of course. I don't have good suggestions for
>> workaround other than marking tcphdr as packed :(
>>  From code efficiency point of view it still will be faster than
>> LD_ABS insn.
> 
> Plus, ld_abs would also only work on skbs right now, and would
> need JIT support for XDP. But it's also cumbersome to use with
> f.e. IPv6, etc, so should not be encouraged, imo.
> 
> One other option for !HAVE_EFFICIENT_UNALIGNED_ACCESS archs could
> be to provide a bpf_skb_load_bytes() helper equivalent for XDP,
> where you eventually do the memcpy() inside. We could see to inline
> the helper itself to optimize it slightly.

We have to do something that works transparently and always,
regardless of whether HAVE_EFFICIENT_UNALIGNED_ACCESS is in
play or not.

And no, marking objects with __packed is not the answer.

What's happening right now is completely unacceptable.

Re: more test_progs...

[Alexei Starovoitov]

On 4/26/17 7:55 AM, David Miller wrote:
> From: Daniel Borkmann <daniel@iogearbox.net>
> Date: Wed, 26 Apr 2017 10:14:42 +0200
>
>> On 04/26/2017 05:42 AM, Alexei Starovoitov wrote:
>>> That sucks for sparc, of course. I don't have good suggestions for
>>> workaround other than marking tcphdr as packed :(
>>>  From code efficiency point of view it still will be faster than
>>> LD_ABS insn.
>>
>> Plus, ld_abs would also only work on skbs right now, and would
>> need JIT support for XDP. But it's also cumbersome to use with
>> f.e. IPv6, etc, so should not be encouraged, imo.
>>
>> One other option for !HAVE_EFFICIENT_UNALIGNED_ACCESS archs could
>> be to provide a bpf_skb_load_bytes() helper equivalent for XDP,
>> where you eventually do the memcpy() inside. We could see to inline
>> the helper itself to optimize it slightly.
>
> We have to do something that works transparently and always,
> regardless of whether HAVE_EFFICIENT_UNALIGNED_ACCESS is in
> play or not.
>
> And no, marking objects with __packed is not the answer.

I'm not suggesting to mark everything as __packed.
Why the following is not the answer?
index fd1e0832d409..c215dffd7189 100644
--- a/tools/testing/selftests/bpf/test_pkt_access.c
+++ b/tools/testing/selftests/bpf/test_pkt_access.c
@@ -19,13 +19,52 @@
  #define barrier() __asm__ __volatile__("": : :"memory")
  int _version SEC("version") = 1;

+struct __tcphdr {
+       __u16  source;
...
+       __u16  window;
+       __u16 check;
+       __u16  urg_ptr;
+}
+#if defined(__sparc__) || defined(__s390__)
+__packed
+#endif
+;
  SEC("test1")
  int process(struct __sk_buff *skb)
  {
         void *data_end = (void *)(long)skb->data_end;
         void *data = (void *)(long)skb->data;
         struct ethhdr *eth = (struct ethhdr *)(data);
-       struct tcphdr *tcp = NULL;
+       struct __tcphdr *tcp = NULL;
         __u8 proto = 255;

It's only needed for test_pkt_access.c test,
since it's being fancy and doing iph->ihl * 4.

Also such tcp->urg_ptr access into packed struct is more efficient
after JITing then sparc's own load_half_unaligned in asm, since it's
done inline and doesn't need a call.

Note that such tcphdr workaround is not necessary for more
real programs: test_l4lb.c and test_xdp.c, since they do:
if (iph->ihl != 5)
    return drop;

Another idea:
x64, arm64, ppc have efficient unaligned.
s390 and mips64 have special instructions to do unaligned
access efficiently and we can make verifier convert unknown-align
load/stores into special internal load/stores, so they can be
executed differently by interpreter and by JITs.
Does sparc64 have some special instructions like that?

Re: more test_progs...

[David Miller]

From: Alexei Starovoitov <ast@fb.com>
Date: Wed, 26 Apr 2017 16:49:35 -0700

> It's only needed for test_pkt_access.c test,
> since it's being fancy and doing iph->ihl * 4.

It is going to be a common idiom in anything looking at
transport headers, no?

> Also such tcp->urg_ptr access into packed struct is more efficient
> after JITing then sparc's own load_half_unaligned in asm, since it's
> done inline and doesn't need a call.
> 
> Note that such tcphdr workaround is not necessary for more
> real programs: test_l4lb.c and test_xdp.c, since they do:
> if (iph->ihl != 5)
>    return drop;

Hmmm...

> Does sparc64 have some special instructions like that?

Unfortunately not.

I think we need to seriously consider tracking "Pointer
incremented by power of 2 N" and stuff like that.

I know it's not easy, but it is necessary.

Having stuff like the packed thing above is just a completely
unnecessary detail to expose to users writing these programs.