eBPF - little-endian load instructions?

eBPF - little-endian load instructions?

[Johannes Berg]

Hi,

Looking at (e)BPF for wifi, I notice that everything is big endian in
loads from the frame - and wifi is all little endian.

Obviously, this can be worked around by doing byte-loads and swapping
in the program, but it'll be more efficient to not do that.

Do you think it's possible to add little-endian load instructions? Or
perhaps there should be a conversion function from BE to LE?

Thanks,
johannes

Re: eBPF - little-endian load instructions?

[Daniel Borkmann]

On 04/11/2017 12:38 PM, Johannes Berg wrote:
> Hi,
>
> Looking at (e)BPF for wifi, I notice that everything is big endian in
> loads from the frame - and wifi is all little endian.
>
> Obviously, this can be worked around by doing byte-loads and swapping
> in the program, but it'll be more efficient to not do that.
>
> Do you think it's possible to add little-endian load instructions? Or
> perhaps there should be a conversion function from BE to LE?

Are you working with an skb at that point in time in wifi? There are
3 different ways of accessing skb data, see [1] slide 7 - 10. The BPF
LD_ABS/IND instructions were carried over from cBPF and are the only
ones that convert to host endianess. It can be used in eBPF as well,
but there are more efficient ways like 'direct packet access' or
helpers such as bpf_skb_load_bytes() that load the raw buffers as-is,
which is probably what you want if I understand you correctly.

There are instructions to convert endianess, see __bpf_prog_run(), the
ALU_END_TO_BE, ALU_END_TO_LE labels for details. There's a BPF_ENDIAN()
macro used in the test suite and other places.

   [1] http://netdevconf.org/1.2/slides/oct7/07_advanced_programmability_and_recent_updates_with_tc_cls_bpf.pdf

Re: eBPF - little-endian load instructions?

[Johannes Berg]

> Are you working with an skb at that point in time in wifi? 

Yes.

> There are
> 3 different ways of accessing skb data, see [1] slide 7 - 10. The BPF
> LD_ABS/IND instructions were carried over from cBPF and are the only
> ones that convert to host endianess. It can be used in eBPF as well,
> but there are more efficient ways like 'direct packet access' or
> helpers such as bpf_skb_load_bytes() that load the raw buffers as-is,
> which is probably what you want if I understand you correctly.

Sounds like, yeah.

> There are instructions to convert endianess, see __bpf_prog_run(),
> the ALU_END_TO_BE, ALU_END_TO_LE labels for details. There's a
> BPF_ENDIAN() macro used in the test suite and other places.

Ok, thanks! :)

So sounds like I don't need anything special - should have a patch to
hook up the wifi stuff soon.

johannes

Re: eBPF - little-endian load instructions?

[Daniel Borkmann]

On 04/11/2017 01:15 PM, Johannes Berg wrote:
>
>> Are you working with an skb at that point in time in wifi?
>
> Yes.
>
>> There are
>> 3 different ways of accessing skb data, see [1] slide 7 - 10. The BPF
>> LD_ABS/IND instructions were carried over from cBPF and are the only
>> ones that convert to host endianess. It can be used in eBPF as well,
>> but there are more efficient ways like 'direct packet access' or
>> helpers such as bpf_skb_load_bytes() that load the raw buffers as-is,
>> which is probably what you want if I understand you correctly.
>
> Sounds like, yeah.
>
>> There are instructions to convert endianess, see __bpf_prog_run(),
>> the ALU_END_TO_BE, ALU_END_TO_LE labels for details. There's a
>> BPF_ENDIAN() macro used in the test suite and other places.
>
> Ok, thanks! :)
>
> So sounds like I don't need anything special - should have a patch to
> hook up the wifi stuff soon.

Yeah, you shouldn't need anything special. In case the wifi progs have
their own BPF program type, I wouldn't even add it to may_access_skb()
to not further encourage LD_ABS/IND usage. F.e. lwt BPF programs are not
hooked up there either.

Thanks,
Daniel

Re: eBPF - little-endian load instructions?

[Johannes Berg]

> Yeah, you shouldn't need anything special. 

I did add that, yes.

> In case the wifi progs have their own BPF program type, I wouldn't
> even add it to may_access_skb() to not further encourage LD_ABS/IND
> usage. F.e. lwt BPF programs are not hooked up there either.

Interesting, ok. I still need to hook up get_func_proto though to
actually be able to access that.

johannes

Re: eBPF - little-endian load instructions?

[Johannes Berg]

On Tue, 2017-04-11 at 13:06 +0200, Daniel Borkmann wrote:
> 
> There are instructions to convert endianess, see __bpf_prog_run(),
> the ALU_END_TO_BE, ALU_END_TO_LE labels for details. There's a
> BPF_ENDIAN() macro used in the test suite and other places.

Are these hooked up to llvm intrinsics or so? If not, can I do that
through some kind of inline asm statement?

In the samples, I only see people doing

#define _htonl __builtin_bswap32

but I'm not even completely convinced that's correct, since it assumes
a little-endian host?

johannes

Re: eBPF - little-endian load instructions?

[Alexei Starovoitov]

On Wed, Apr 12, 2017 at 03:02:00PM +0200, Johannes Berg wrote:
> On Tue, 2017-04-11 at 13:06 +0200, Daniel Borkmann wrote:
> > 
> > There are instructions to convert endianess, see __bpf_prog_run(),
> > the ALU_END_TO_BE, ALU_END_TO_LE labels for details. There's a
> > BPF_ENDIAN() macro used in the test suite and other places.
> 
> Are these hooked up to llvm intrinsics or so? If not, can I do that
> through some kind of inline asm statement?

llvm doesn't support bpf inline asm yet.

> In the samples, I only see people doing
> 
> #define _htonl __builtin_bswap32
> 
> but I'm not even completely convinced that's correct, since it assumes
> a little-endian host?

oh well, time to face the music.

In llvm backend I did:
// bswap16, bswap32, bswap64
class BSWAP<bits<32> SizeOp, string OpcodeStr, list<dag> Pattern>
...
  let op = 0xd;     // BPF_END
  let BPFSrc = 1;   // BPF_TO_BE (TODO: use BPF_TO_LE for big-endian target)
  let BPFClass = 4; // BPF_ALU

so __builtin_bswap32() is not a normal bswap. It's only doing bswap
if the compiled program running on little endian arch.
The plan was to fix it up for -march=bpfeb target (hence the comment above),
but it turned out that such __builtin_bswap32 matches perfectly to _htonl()
semantics, so I left it as-is even for -march=bpfeb.

On little endian:
ld_abs_W = *(u32*) + real bswap32
__builtin_bswap32() == bpf_to_be insn = real bswap32

On big endian:
ld_abs_W = *(u32*)
__builtin_bswap32() == bpf_to_be insn = nop

so in samples/bpf/*.c:
load_word() + _htonl()(__builtin_bswap32) has the same semantics
for both little and big endian archs, hence all networking sample code in
samples/bpf/*_kern.c works fine.

imo the whole thing is crazy ugly. llvm doesn't have 'htonl' equivalent builtin,
so builtin_bswap was the closest I could use to generate bpf_to_[bl]e insn.

To solve this properly I think we need two things:
. proper bswap32 insn in BPF
. extend llvm with bpf_to_be/le builtins
Both are not trivial amount of work.

Re: eBPF - little-endian load instructions?

[Johannes Berg]

On Wed, 2017-04-12 at 09:58 -0700, Alexei Starovoitov wrote:
> 
> > Are these hooked up to llvm intrinsics or so? If not, can I do that
> > through some kind of inline asm statement?
> 
> llvm doesn't support bpf inline asm yet.

Ok.

> > In the samples, I only see people doing
> > 
> > #define _htonl __builtin_bswap32
> > 
> > but I'm not even completely convinced that's correct, since it
> > assumes
> > a little-endian host?
> 
> oh well, time to face the music.
> 
> In llvm backend I did:
> // bswap16, bswap32, bswap64
> class BSWAP<bits<32> SizeOp, string OpcodeStr, list<dag> Pattern>
> ...
>   let op = 0xd;     // BPF_END
>   let BPFSrc = 1;   // BPF_TO_BE (TODO: use BPF_TO_LE for big-endian
> target)
>   let BPFClass = 4; // BPF_ALU
> 
> so __builtin_bswap32() is not a normal bswap. It's only doing bswap
> if the compiled program running on little endian arch.
> The plan was to fix it up for -march=bpfeb target (hence the comment
> above), but it turned out that such __builtin_bswap32 matches
> perfectly to _htonl() semantics, so I left it as-is even for
> -march=bpfeb.
> 
> On little endian:
> ld_abs_W = *(u32*) + real bswap32
> __builtin_bswap32() == bpf_to_be insn = real bswap32
> 
> On big endian:
> ld_abs_W = *(u32*)
> __builtin_bswap32() == bpf_to_be insn = nop
> 
> so in samples/bpf/*.c:
> load_word() + _htonl()(__builtin_bswap32) has the same semantics
> for both little and big endian archs, hence all networking sample
> code in
> samples/bpf/*_kern.c works fine.
> 
> imo the whole thing is crazy ugly. llvm doesn't have 'htonl'
> equivalent builtin, so builtin_bswap was the closest I could use to
> generate bpf_to_[bl]e insn.
> 

Awkward. How can this even be fixed without breaking all the existing
code?

I assume the BPF machine is intended to be endian-independent, which is
really the problem - normally you'd either
	#define be32_to_cpu bswap32
or
	#define be32_to_cpu(x) (x)
depending on the build architecture, I guess.

> To solve this properly I think we need two things:
> . proper bswap32 insn in BPF

Not sure you need that - what for? Normally this doesn't really get used directly, I think? At least I don't really see a good reason for using it directly. And reimplementing that now would break existing C code.

> . extend llvm with bpf_to_be/le builtins
> Both are not trivial amount of work.

It seems that perhaps the best way to solve this would be to actually
implement inline assembly. Then, existing C code that relies on the
(broken) bswap32 semantics can actually continue to work, if that
built-in isn't touched, and one could then implement the various
cpu_to_be32 and friends as inline assembly?

That would make it invisible to the LLVM optimiser though, so perhaps
not the best idea either.

johannes

Re: eBPF - little-endian load instructions?

[Alexei Starovoitov]

On Wed, Apr 12, 2017 at 09:38:39PM +0200, Johannes Berg wrote:
> On Wed, 2017-04-12 at 09:58 -0700, Alexei Starovoitov wrote:
> > 
> > > Are these hooked up to llvm intrinsics or so? If not, can I do that
> > > through some kind of inline asm statement?
> > 
> > llvm doesn't support bpf inline asm yet.
> 
> Ok.
> 
> > > In the samples, I only see people doing
> > > 
> > > #define _htonl __builtin_bswap32
> > > 
> > > but I'm not even completely convinced that's correct, since it
> > > assumes
> > > a little-endian host?
> > 
> > oh well, time to face the music.
> > 
> > In llvm backend I did:
> > // bswap16, bswap32, bswap64
> > class BSWAP<bits<32> SizeOp, string OpcodeStr, list<dag> Pattern>
> > ...
> >   let op = 0xd;     // BPF_END
> >   let BPFSrc = 1;   // BPF_TO_BE (TODO: use BPF_TO_LE for big-endian
> > target)
> >   let BPFClass = 4; // BPF_ALU
> > 
> > so __builtin_bswap32() is not a normal bswap. It's only doing bswap
> > if the compiled program running on little endian arch.
> > The plan was to fix it up for -march=bpfeb target (hence the comment
> > above), but it turned out that such __builtin_bswap32 matches
> > perfectly to _htonl() semantics, so I left it as-is even for
> > -march=bpfeb.
> > 
> > On little endian:
> > ld_abs_W = *(u32*) + real bswap32
> > __builtin_bswap32() == bpf_to_be insn = real bswap32
> > 
> > On big endian:
> > ld_abs_W = *(u32*)
> > __builtin_bswap32() == bpf_to_be insn = nop
> > 
> > so in samples/bpf/*.c:
> > load_word() + _htonl()(__builtin_bswap32) has the same semantics
> > for both little and big endian archs, hence all networking sample
> > code in
> > samples/bpf/*_kern.c works fine.
> > 
> > imo the whole thing is crazy ugly. llvm doesn't have 'htonl'
> > equivalent builtin, so builtin_bswap was the closest I could use to
> > generate bpf_to_[bl]e insn.
> > 
> 
> Awkward. How can this even be fixed without breaking all the existing
> code?

it's really llvm bug that i need fix. It's plain broken
to generate what effectively is nop insn for march=bpfeb
My only excuse that when that code was written llvm had only march=bpfel.
bpfeb was added much later.

> I assume the BPF machine is intended to be endian-independent, which is
> really the problem - normally you'd either
> 	#define be32_to_cpu bswap32
> or
> 	#define be32_to_cpu(x) (x)
> depending on the build architecture, I guess.

yeah. that's what we should have in bpf_helpers.h

> > To solve this properly I think we need two things:
> > . proper bswap32 insn in BPF
> 
> Not sure you need that - what for? Normally this doesn't really get used directly, I think? At least I don't really see a good reason for using it directly. And reimplementing that now would break existing C code.

I think bswap is only used in crypto and things like crypto.
In the kernel it's 802.15.4 mac.
ntoh is enough for any networking code,
so I guess we can live without real bswap insn.

> > . extend llvm with bpf_to_be/le builtins
> > Both are not trivial amount of work.
> 
> It seems that perhaps the best way to solve this would be to actually
> implement inline assembly. Then, existing C code that relies on the
> (broken) bswap32 semantics can actually continue to work, if that
> built-in isn't touched, and one could then implement the various
> cpu_to_be32 and friends as inline assembly?
> 
> That would make it invisible to the LLVM optimiser though, so perhaps
> not the best idea either.

In llvm the inline asm is actually visible to optimizer (unlike gcc),
so it can be ok-ish.
Inline asm needs to be done anyway.

Re: eBPF - little-endian load instructions?

[Johannes Berg]

On Wed, 2017-04-12 at 20:08 -0700, Alexei Starovoitov wrote:

> it's really llvm bug that i need fix. It's plain broken
> to generate what effectively is nop insn for march=bpfeb
> My only excuse that when that code was written llvm had only
> march=bpfel.
> bpfeb was added much later.

So I'm confused now. Is bpf intended to be endian-independent or not?
It sounded at first like it was, even if I have a hard time imagining
how that would even work.

> > 	#define be32_to_cpu bswap32
> > or
> > 	#define be32_to_cpu(x) (x)
> > depending on the build architecture, I guess.
> 
> yeah. that's what we should have in bpf_helpers.h

But that sounds more like it isn't.

> ntoh is enough for any networking code,
> so I guess we can live without real bswap insn.

Well, my reason for asking this is that wireless actually as a little-
endian wire protocol, unlike other network stuff :)
(Even at a bit level it's defined to transfer the LSB first, but that
doesn't really get visible at the level of the CPU that can only
address bytes.)

johannes

Re: eBPF - little-endian load instructions?

[Alexei Starovoitov]

On Thu, Apr 13, 2017 at 07:58:45AM +0200, Johannes Berg wrote:
> On Wed, 2017-04-12 at 20:08 -0700, Alexei Starovoitov wrote:
> 
> > it's really llvm bug that i need fix. It's plain broken
> > to generate what effectively is nop insn for march=bpfeb
> > My only excuse that when that code was written llvm had only
> > march=bpfel.
> > bpfeb was added much later.
> 
> So I'm confused now. Is bpf intended to be endian-independent or not?
> It sounded at first like it was, even if I have a hard time imagining
> how that would even work.

bpf takes endianness of the cpu it runs on.
if we said that bpf 32-bit load insn is little endian, it would have screwed up
all big-endian archs and the other way around.
For both classic and extended the corresponding struct sock_filter and bpf_insn
are encoded in target cpu endianness.
The front-end (clang) needs to run in target endianness as well otherwise
the bcc tracing scripts will be accessing garbage.
In other words you cannot take either classic or extended bpf program
generated for x86 and run it on big-endian. Though you can compile on x86
and run on Arm. Hence two targets for llvm -march=bpfeb and -march=bpfel
If you compile for -march=bpfeb and try to load on x86, the instruction stream
will be rejected by the verifier in early stages, since branch insns and
all immediate values will be wrong.

Re: eBPF - little-endian load instructions?

[Johannes Berg]

On Fri, 2017-04-14 at 11:42 -0700, Alexei Starovoitov wrote:

> bpf takes endianness of the cpu it runs on.

Ok, so then things are actually not as difficult as I thought.

> if we said that bpf 32-bit load insn is little endian, it would have
> screwed up all big-endian archs and the other way around.

Right.

But then basically we do only need to have builtins for endian
conversion, and #define them appropriately, as done anywhere else.

Perhaps we want to eventually be able to take advantage of "other-
endian" loads the CPU may have through the JIT, but getting it correct
first would be good :)

Either way though, it could be done with something like inline
assembly.

johannes