[Bloat] high speed packet and protocol processing in userspace?

[Bloat] high speed packet and protocol processing in userspace?

[Dave Taht]

Now that the big make-wifi-fast phase is complete, multicast is next.

I'm finding that I need to be delving into things that are happening
at sub-4ms intervals, and at high speeds (think: 802.11ac). While
flent can be used to drive such tests, actually taking apart the
packet captures has been something that I have generally fallen back
on things like wireshark, libpcap, and tcptrace to analyze.

Anyway, last month, after taking apart what I'd have to do to this code,
https://github.com/dtaht/airtime-pie-chart

to better be able to take apart multicast reception from multiple wifi
points, I ran away screaming. Then I started to look at new, cool
things, like ebpf - which would let me build histograms and so forth
in real time, and a variety of new efforts like fd.io, and so on, and
yet still is this semantic gap between "what I want", and "how to do
it".

So I'm *stumped* about a few things and I thought I'd ask the list.

A) How much overhead on a box or protocol can come from using raw
sockets and a ton of bpf?

Example: If I converted a daemon that currently uses classic means to
filter out packets, registering a udp port, turning on a multicast
group, listening on an address - and changed it to just basically
using a bpf filter to do all that instead) - how much is that going to
hurt, nowadays?

Is it faster to execute 17 bpf vm instructions on (nearly) every
packet, or to use all that old stuff?

bpf example for the babel protocol:

https://github.com/dtaht/libv6/blob/master/clients/tabalb/babel.bpf

(the crazy advantage of this idea is that I can better measure actual
packet loss, crc failures, wifi retries, etc, due to corruption,
across an entire wifi network)

B) Are there any means of easily abstracting deeper protocol
processing into a higher level grammar, better than tcpdump? I found
one tool, that I like conceptually - for deeply decoding a protocol -

https://github.com/grg/parser-gen/blob/master/README.parse-graphs.md

(which I got from the *excellent* paper:
http://yuba.stanford.edu/~nickm/papers/ancs48-gibb.pdf )

...but it just outputs verilog at the moment.

When I (as an example), look over the hand written parser for babeld's
(mere) 13 messages, I really, really want to be somewhere else. (and
it's a pretty good parser!)

That sort of processing does not seem amiable to a peg or bnf grammar
(but see above grammar and/or examples), and yet I'd really like to be
writing things that are provably correct and robust... that compile
down to something really efficient... quickly... with minimal
thought... that hopefully someone else has already written!

(babel's parser is *nothing* compared to looking at the mac80211 headers)

I've googled, and thunk, and maybe I'm merely asking the wrong
questions, and "the packet analysis tool to end all tools" already
exists?

C) Are vendors like mellonox or others doing network offloads parsing
bpf or ebpf directly yet?

-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

Re: [Bloat] high speed packet and protocol processing in userspace?

[Michael Richardson]

[-- Attachment #1: Type: text/plain, Size: 1391 bytes --]


Dave Taht <dave.taht@gmail.com> wrote:
    > Is it faster to execute 17 bpf vm instructions on (nearly) every
    > packet, or to use all that old stuff?

    > bpf example for the babel protocol:

I have no data for you.  Andrew McGregor might know more?
My understanding is that there is a JIT for ebpf.

    > B) Are there any means of easily abstracting deeper protocol processing
    > into a higher level grammar, better than tcpdump? I found one tool,
    > that I like conceptually - for deeply decoding a protocol -

tcpdump just exposes the libpcap compiler.  It has many annoying limitations.

    > I've googled, and thunk, and maybe I'm merely asking the wrong
    > questions, and "the packet analysis tool to end all tools" already
    > exists?

Yes, people have produced them, but they go nowhere because they are too
specialized, or too general.  The question is: are you trying to build a tcp
stack that punts packets at applications, or do "analysis" --- which I interpret
to mean to collect statistics.

    > C) Are vendors like mellonox or others doing network offloads parsing
    > bpf or ebpf directly yet?

I don't know.

--
]               Never tell me the odds!                 | ipv6 mesh networks [
]   Michael Richardson, Sandelman Software Works        | network architect  [
]     mcr@sandelman.ca  http://www.sandelman.ca/        |   ruby on rails    [


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: [Bloat] high speed packet and protocol processing in userspace?

[Eric Dumazet]

On Thu, 2017-03-16 at 11:52 -0400, Michael Richardson wrote:
> Dave Taht <dave.taht@gmail.com> wrote:
>     > Is it faster to execute 17 bpf vm instructions on (nearly) every
>     > packet, or to use all that old stuff?
> 
>     > bpf example for the babel protocol:
> 
> I have no data for you.  Andrew McGregor might know more?
> My understanding is that there is a JIT for ebpf.


ebpf is pretty fast.

> 
>     > B) Are there any means of easily abstracting deeper protocol processing
>     > into a higher level grammar, better than tcpdump? I found one tool,
>     > that I like conceptually - for deeply decoding a protocol -
> 
> tcpdump just exposes the libpcap compiler.  It has many annoying limitations.
> 
>     > I've googled, and thunk, and maybe I'm merely asking the wrong
>     > questions, and "the packet analysis tool to end all tools" already
>     > exists?
> 
> Yes, people have produced them, but they go nowhere because they are too
> specialized, or too general.  The question is: are you trying to build a tcp
> stack that punts packets at applications, or do "analysis" --- which I interpret
> to mean to collect statistics.

Note that you can use C to write your parser, then use LLVM to generate
native eBPF code.


> 
>     > C) Are vendors like mellonox or others doing network offloads parsing
>     > bpf or ebpf directly yet?
> 
> I don't know.

Netronome is (kind of)
drivers/net/ethernet/netronome/nfp

Re: [Bloat] high speed packet and protocol processing in userspace?

[Dave Taht]

On Thu, Mar 16, 2017 at 9:27 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Thu, 2017-03-16 at 11:52 -0400, Michael Richardson wrote:
>> Dave Taht <dave.taht@gmail.com> wrote:
>>     > Is it faster to execute 17 bpf vm instructions on (nearly) every
>>     > packet, or to use all that old stuff?
>>
>>     > bpf example for the babel protocol:
>>
>> I have no data for you.  Andrew McGregor might know more?
>> My understanding is that there is a JIT for ebpf.
>
>
> ebpf is pretty fast.
>
>>
>>     > B) Are there any means of easily abstracting deeper protocol processing
>>     > into a higher level grammar, better than tcpdump? I found one tool,
>>     > that I like conceptually - for deeply decoding a protocol -
>>
>> tcpdump just exposes the libpcap compiler.  It has many annoying limitations.
>>
>>     > I've googled, and thunk, and maybe I'm merely asking the wrong
>>     > questions, and "the packet analysis tool to end all tools" already
>>     > exists?
>>
>> Yes, people have produced them, but they go nowhere because they are too
>> specialized, or too general.  The question is: are you trying to build a tcp
>> stack that punts packets at applications, or do "analysis" --- which I interpret
>> to mean to collect statistics.

Yes and no. Being able to toss "rawer" captures into a database and be
able to sanely query against it was the goal of capturing multiple
"views" of a wifi network.

Another goal was to be able to write a solid packet parser for any
given protocol I used babel as my example, but, say, http2....

People are perpetually using the ip6 match in tcpdump, when that's incorrect.

> Note that you can use C to write your parser, then use LLVM to generate
> native eBPF code.

Ideally I wanted to be able to express that like this:

https://github.com/grg/parser-gen/blob/master/examples/headers-enterprise.txt

Preprocess it, then use llvm to compile it down to bpf.

I'm *really* impressed by the level of tool support emerging for ebpf,
but it's still essentially writing assembly when I'd rather use an
equivalent of bison or peg. If taking that massive step backwards is
the right thing, to build that tool (if none exists)... well... ok.

>
>
>>
>>     > C) Are vendors like mellonox or others doing network offloads parsing
>>     > bpf or ebpf directly yet?
>>
>> I don't know.
>
> Netronome is (kind of)
> drivers/net/ethernet/netronome/nfp

Cool.  Looks like I'd have to hold a bufferbloat.net bake sale to get
one of those to play with, tho.

>
>



-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

Re: [Bloat] high speed packet and protocol processing in userspace?

[Michael Richardson]

[-- Attachment #1: Type: text/plain, Size: 2115 bytes --]


Dave Taht <dave.taht@gmail.com> wrote:
    > I'm *really* impressed by the level of tool support emerging for ebpf,
    > but it's still essentially writing assembly when I'd rather use an
    > equivalent of bison or peg. If taking that massive step backwards is
    > the right thing, to build that tool (if none exists)... well... ok.

years ago, I worked in the NPU space, and we created the language that I
think you wanted.  It was described here:

https://www.ietf.org/archive/id/draft-nossik-pax-pdl-00.txt

IPv4 patterns filters looked like this:

PATTERN  IP_v4_Hdr_For_ICMP {
  version UINT 4 == 4;
  ihl UINT 4 == 5;            /* length == 5 : no options */
  typeOfService UINT 8;
  totalLength UINT 16;
  identification UINT 16;
  flagReserved BIT 1 == 0;
  flagDontFragment BIT 1;
  flagMoreFragments BIT 1 == 0;    /* last fragments only */
  fragmentOffset UINT 13 == 0;    /* first fragments only */
  timeToLive UINT 8;
  protocol BIT 8 == IPPROTO_ICMP;                 /* ICMP */
  headerChecksum BIT 16;
  sourceAddress BIT 32;
  destinationAddress BIT 32
}

You could compile the patterns, and then instantiate fields at runtime if you
needed to.  (i.e: add constraints).  Also merge patterns to select (a) or (b)
in constant time (but not constant memory usage)

Solidum (for whom I worked at the time) had a compiler that would turn this
into ) patricia-tree filters that ran in hardware at wirespeed.  But, APIs
into ernels were hard to get accepted.
In the end, only people willing to pay for this were TLAs who wanted to run
regex's on traffic. Regex took lots of ram, but TLAs didn't buy many sockets.
I would love to be able to recycle the compiler as open source; it could
easily spit out EBPF, but generating assembly directly might be faster
actually.  The Patricia tree is basically jmp base+nextbyteofpacket., but
stored more compactly.

--
]               Never tell me the odds!                 | ipv6 mesh networks [
]   Michael Richardson, Sandelman Software Works        | network architect  [
]     mcr@sandelman.ca  http://www.sandelman.ca/        |   ruby on rails    [


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: [Bloat] high speed packet and protocol processing in userspace?

[Dave Taht]

On Thu, Mar 16, 2017 at 10:32 AM, Michael Richardson <mcr@sandelman.ca> wrote:
>
> Dave Taht <dave.taht@gmail.com> wrote:
>     > I'm *really* impressed by the level of tool support emerging for ebpf,
>     > but it's still essentially writing assembly when I'd rather use an
>     > equivalent of bison or peg. If taking that massive step backwards is
>     > the right thing, to build that tool (if none exists)... well... ok.
>
> years ago, I worked in the NPU space, and we created the language that I
> think you wanted.  It was described here:
>
> https://www.ietf.org/archive/id/draft-nossik-pax-pdl-00.txt
>
> IPv4 patterns filters looked like this:
>
> PATTERN  IP_v4_Hdr_For_ICMP {
>   version UINT 4 == 4;
>   ihl UINT 4 == 5;            /* length == 5 : no options */
>   typeOfService UINT 8;
>   totalLength UINT 16;
>   identification UINT 16;
>   flagReserved BIT 1 == 0;
>   flagDontFragment BIT 1;
>   flagMoreFragments BIT 1 == 0;    /* last fragments only */
>   fragmentOffset UINT 13 == 0;    /* first fragments only */
>   timeToLive UINT 8;
>   protocol BIT 8 == IPPROTO_ICMP;                 /* ICMP */
>   headerChecksum BIT 16;
>   sourceAddress BIT 32;
>   destinationAddress BIT 32
> }
>
> You could compile the patterns, and then instantiate fields at runtime if you
> needed to.  (i.e: add constraints).  Also merge patterns to select (a) or (b)
> in constant time (but not constant memory usage)

Yes, that is more or less what I wanted. And in 1998!?

> Solidum (for whom I worked at the time) had a compiler that would turn this
> into ) patricia-tree filters that ran in hardware at wirespeed.  But, APIs
> into ernels were hard to get accepted.
> In the end, only people willing to pay for this were TLAs who wanted to run
> regex's on traffic. Regex took lots of ram, but TLAs didn't buy many sockets.

I think regexes are flexible but crazy for high speed packet
processing of formally defined protocols that essentially only make
forward progress.

the chip design people must have had tools like this for decades now,
but not OS and app design folk. :sigh:

> I would love to be able to recycle the compiler as open source; it could
> easily spit out EBPF, but generating assembly directly might be faster
> actually.  The Patricia tree is basically jmp base+nextbyteofpacket., but
> stored more compactly.

Well, ebpf as a target would make it most useful at the moment,
followed by pure C (processing a packet), followed by verilog. Still
have the code?

I'm tempted to take apart the first tool mentioned to see if it could
be made to (in addition to verilog) output c, then bpf, but I had
really rather expected this to have been a solved problem. And it
seemed to have been! in 1998! wow

... but, like everyone else, I go around painfully writing custom pcap
filters for everything. It's begun to really, really hurt when I do
that.

I need to also note that I don't care about tcp - we have plenty of
tools for that -  in working with the airtime-pie-chart I discovered
it was filtering out all the multicast beacons, and all the other
related "below layer 1" wifi traffic, probes, crypto etc - in addition
to the failures in nd and dhcp and babel I was looking at.

the amount of that stuff was significant - 12% typically where I am,
I've seen +40% - and now that I know where to look, perhaps I'll find
more, and why....

And I'd been eyeball-filtering it out for a long time when looking at aircaps.

And regrettably very little - except the IEEE specifications - defines
what the correct behaviors for all that is.

So I turned over a rock and found a nightmare in wifi I hadn't deeply suspected.


> --
> ]               Never tell me the odds!                 | ipv6 mesh networks [
> ]   Michael Richardson, Sandelman Software Works        | network architect  [
> ]     mcr@sandelman.ca  http://www.sandelman.ca/        |   ruby on rails    [
>
>
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat
>



-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

Re: [Bloat] high speed packet and protocol processing in userspace?

[Jesper Dangaard Brouer]

On Thu, 16 Mar 2017 09:27:44 -0700 Eric Dumazet <eric.dumazet@gmail.com> wrote:
> On Thu, 2017-03-16 at 11:52 -0400, Michael Richardson wrote:
> > Dave Taht <dave.taht@gmail.com> wrote:  
> >     > Is it faster to execute 17 bpf vm instructions on (nearly) every
> >     > packet, or to use all that old stuff?  
> > 
> > My understanding is that there is a JIT for ebpf.  
>
> ebpf is pretty fast.

To Dave what kind of arch are you running on?
AFAIK you were running on MIPS right?
Just checked the kernel tree and I was surprised to see a bpf JIT for mips:

$ ls -1 arch/mips/net/bpf_jit*
arch/mips/net/bpf_jit_asm.S
arch/mips/net/bpf_jit.c
arch/mips/net/bpf_jit.h

But I don't know what state it is in (Markos?)


> >     > B) Are there any means of easily abstracting deeper protocol processing
> >     > into a higher level grammar, better than tcpdump? I found one tool,
> >     > that I like conceptually - for deeply decoding a protocol -  
> > 
> > tcpdump just exposes the libpcap compiler.  It has many annoying limitations.
> >   
> >     > I've googled, and thunk, and maybe I'm merely asking the wrong
> >     > questions, and "the packet analysis tool to end all tools" already
> >     > exists?  
> > 
> > Yes, people have produced them, but they go nowhere because they
> > are too specialized, or too general.  The question is: are you
> > trying to build a tcp stack that punts packets at applications, or
> > do "analysis" --- which I interpret to mean to collect statistics.  

The main point for getting performance out of eBPF is to avoid writing
a generic framework that need to handle everything.  The point is only
to emit the instructions you need for your specific use-case.

You should think about eBPF as a programmable policy (that we don't
need/want to add to the kernel code and maintain forever) See this talk:
 https://github.com/iovisor/bpf-docs/blob/master/XDP_Inside_and_Out.pdf

> Note that you can use C to write your parser, then use LLVM to
> generate native eBPF code.

Yes, that is how I use eBPF, writing restricted-C that LLVM compiles
into eBPF code.  You can look at examples in the kernel git tree under
samples/bpf/

I've tried to make it easier to get started working with the LLVM setup by:

(1) providing example code that compiles outside kernel tree:
  https://github.com/netoptimizer/prototype-kernel/tree/master/kernel/samples/bpf

(2) started documenting howto use eBPF:
  https://prototype-kernel.readthedocs.io/en/latest/bpf/index.html

(3) Giving a talk on howto use it:
  http://people.netfilter.org/hawk/presentations/OpenSourceDays2017/
  https://opensourcedays.org/business/talk?speaker_id=84

-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Principal Kernel Engineer at Red Hat
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [Bloat] high speed packet and protocol processing in userspace?

[Daniel Borkmann]

On 03/17/2017 10:02 AM, Jesper Dangaard Brouer wrote:
> On Thu, 16 Mar 2017 09:27:44 -0700 Eric Dumazet <eric.dumazet@gmail.com> wrote:
>> On Thu, 2017-03-16 at 11:52 -0400, Michael Richardson wrote:
>>> Dave Taht <dave.taht@gmail.com> wrote:
>>>      > Is it faster to execute 17 bpf vm instructions on (nearly) every
>>>      > packet, or to use all that old stuff?
>>>
>>> My understanding is that there is a JIT for ebpf.
>>
>> ebpf is pretty fast.
>
> To Dave what kind of arch are you running on?
> AFAIK you were running on MIPS right?
> Just checked the kernel tree and I was surprised to see a bpf JIT for mips:
>
> $ ls -1 arch/mips/net/bpf_jit*
> arch/mips/net/bpf_jit_asm.S
> arch/mips/net/bpf_jit.c
> arch/mips/net/bpf_jit.h
>
> But I don't know what state it is in (Markos?)

The JIT is for cBPF right now, but Cavium guys mentioned on netdev
recently that they're going to implement an eBPF JIT for mips 64.

You can see current cBPF and eBPF JITs that are supported by the
kernel via:

$ git grep BPF_JIT | grep select
arch/arm/Kconfig:	select HAVE_CBPF_JIT
arch/arm64/Kconfig:	select HAVE_EBPF_JIT
arch/mips/Kconfig:	select HAVE_CBPF_JIT if !CPU_MICROMIPS
arch/powerpc/Kconfig:	select HAVE_CBPF_JIT if !PPC64
arch/powerpc/Kconfig:	select HAVE_EBPF_JIT if PPC64
arch/s390/Kconfig:	select HAVE_EBPF_JIT if PACK_STACK && HAVE_MARCH_Z196_FEATURES
arch/sparc/Kconfig:	select HAVE_CBPF_JIT
arch/x86/Kconfig:	select HAVE_EBPF_JIT			if X86_64

[...]
> The main point for getting performance out of eBPF is to avoid writing
> a generic framework that need to handle everything.  The point is only
> to emit the instructions you need for your specific use-case.
>
> You should think about eBPF as a programmable policy (that we don't
> need/want to add to the kernel code and maintain forever) See this talk:
>   https://github.com/iovisor/bpf-docs/blob/master/XDP_Inside_and_Out.pdf
>
>> Note that you can use C to write your parser, then use LLVM to
>> generate native eBPF code.
>
> Yes, that is how I use eBPF, writing restricted-C that LLVM compiles
> into eBPF code.  You can look at examples in the kernel git tree under
> samples/bpf/

Another, perhaps more complex project for eBPF in combination with
tc + sched_clsact + cls_bpf in da (direct-action) mode can be found
under: https://github.com/cilium/cilium (see bpf/ folder for the C
code that LLVM compiles down to eBPF if you're curious).

Cheers,
Daniel

Re: [Bloat] high speed packet and protocol processing in userspace?

[Jesper Dangaard Brouer]

On Fri, 17 Mar 2017 13:10:32 +0100
Daniel Borkmann <daniel@iogearbox.net> wrote:

> On 03/17/2017 10:02 AM, Jesper Dangaard Brouer wrote:
> > On Thu, 16 Mar 2017 09:27:44 -0700 Eric Dumazet <eric.dumazet@gmail.com> wrote:  
> >> On Thu, 2017-03-16 at 11:52 -0400, Michael Richardson wrote:  
> >>> Dave Taht <dave.taht@gmail.com> wrote:  
> >>>      > Is it faster to execute 17 bpf vm instructions on (nearly) every
> >>>      > packet, or to use all that old stuff?  
> >>>
> >>> My understanding is that there is a JIT for ebpf.  
> >>
> >> ebpf is pretty fast.  
> >
> > To Dave what kind of arch are you running on?
> > AFAIK you were running on MIPS right?
> > Just checked the kernel tree and I was surprised to see a bpf JIT for mips:
> >
> > $ ls -1 arch/mips/net/bpf_jit*
> > arch/mips/net/bpf_jit_asm.S
> > arch/mips/net/bpf_jit.c
> > arch/mips/net/bpf_jit.h
> >
> > But I don't know what state it is in (Markos?)  
> 
> The JIT is for cBPF right now, but Cavium guys mentioned on netdev
> recently that they're going to implement an eBPF JIT for mips 64.
> 
> You can see current cBPF and eBPF JITs that are supported by the
> kernel via:
> 
> $ git grep BPF_JIT | grep select
> arch/arm/Kconfig:	select HAVE_CBPF_JIT
> arch/arm64/Kconfig:	select HAVE_EBPF_JIT
> arch/mips/Kconfig:	select HAVE_CBPF_JIT if !CPU_MICROMIPS
> arch/powerpc/Kconfig:	select HAVE_CBPF_JIT if !PPC64
> arch/powerpc/Kconfig:	select HAVE_EBPF_JIT if PPC64
> arch/s390/Kconfig:	select HAVE_EBPF_JIT if PACK_STACK && HAVE_MARCH_Z196_FEATURES
> arch/sparc/Kconfig:	select HAVE_CBPF_JIT
> arch/x86/Kconfig:	select HAVE_EBPF_JIT			if X86_64

Thanks Daniel, this is very useful information. Doc this:
 https://github.com/netoptimizer/prototype-kernel/commit/ff51c31123de1220

-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Principal Kernel Engineer at Red Hat
  LinkedIn: http://www.linkedin.com/in/brouer