From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt0-x22f.google.com (mail-qt0-x22f.google.com [IPv6:2607:f8b0:400d:c0d::22f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id A9DF83B29E for ; Thu, 16 Mar 2017 16:04:35 -0400 (EDT) Received: by mail-qt0-x22f.google.com with SMTP id r45so47355718qte.3 for ; Thu, 16 Mar 2017 13:04:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=Ma8I0FKyLgyNoVdFPozuHt6fM5wCHYKWxVN9OHBa484=; b=i+P/k3obxP6U6vyWXP8LYmGmcqd0n9kFuG8EOyi7MwgmB3t8VCCZiTBjwBCf909qBb onqm1/Cl07JDbXs4s7Es7/M3vouhQBX+DYnYHzSkyPKOyTh4mzOq8NROYnO5zOHj1rcD pnIs4QvM1J7zmjDaWlSdei3heEPp8tp8avR691BwAplfSYZfjfYYcNPmuh92bXk3I1LG sICHGEIXIuEhTXU67g9/qJD1eb5Ep8Rq8Q6/94OYIv4wt8itdGrefB/6HsOg2Z8Lm4uP 5UUMd4OxDGwD67BXw2V2qEfTnJhSv+C4gAwn7rrR+An9P8QKn1T8arm/H+I1tQnUtXyr vl8A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=Ma8I0FKyLgyNoVdFPozuHt6fM5wCHYKWxVN9OHBa484=; b=NarxP7N0D2xlPIQvCSqPnp8/AX4bHcIbE1HKARhhXebl9N8zBmBecqlgHog40Cz0ZX 80eTRUU9AYBwBFl2N143z0no0ruWXGI9D87OT7CDrcXcVSCf7bALDMPZeZoOnJraqBWu 4mlpfB2VPBX5G4q0bcqvH5+BROgx7T/pmQEMhpoSdESdICPVZNrvP/tMqsnKday+AvVi b1z39x+EQfqaPuJG2pHE72foI05QMwhf08j/p0fOu3lG9v1dgu1DAQuQG/aImaGvKoe6 LgLzY93VM/uzui542m9MpZNOos1GjV8vInYxVV5dTAUCrSyAOvu9ExPKeZTo9WBs7OYu mcAQ== X-Gm-Message-State: AFeK/H1IfvxGZzBCZOK/NbZgkHTWqE05F4m6iyBH3+Sl02YPuZ9jUgKjSR/dl6oL3xopHS8nK3fwlk0Ltlrvsg== X-Received: by 10.200.50.231 with SMTP id a36mr11176021qtb.156.1489694675027; Thu, 16 Mar 2017 13:04:35 -0700 (PDT) MIME-Version: 1.0 Received: by 10.12.142.132 with HTTP; Thu, 16 Mar 2017 13:04:34 -0700 (PDT) In-Reply-To: <18543.1489685534@obiwan.sandelman.ca> References: <27209.1489679549@obiwan.sandelman.ca> <1489681664.28631.221.camel@edumazet-glaptop3.roam.corp.google.com> <18543.1489685534@obiwan.sandelman.ca> From: Dave Taht Date: Thu, 16 Mar 2017 13:04:34 -0700 Message-ID: To: Michael Richardson Cc: bloat Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Bloat] high speed packet and protocol processing in userspace? X-BeenThere: bloat@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: General list for discussing Bufferbloat List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 16 Mar 2017 20:04:35 -0000 On Thu, Mar 16, 2017 at 10:32 AM, Michael Richardson wro= te: > > Dave Taht wrote: > > I'm *really* impressed by the level of tool support emerging for eb= pf, > > but it's still essentially writing assembly when I'd rather use an > > equivalent of bison or peg. If taking that massive step backwards i= s > > 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 =3D=3D 4; > ihl UINT 4 =3D=3D 5; /* length =3D=3D 5 : no options */ > typeOfService UINT 8; > totalLength UINT 16; > identification UINT 16; > flagReserved BIT 1 =3D=3D 0; > flagDontFragment BIT 1; > flagMoreFragments BIT 1 =3D=3D 0; /* last fragments only */ > fragmentOffset UINT 13 =3D=3D 0; /* first fragments only */ > timeToLive UINT 8; > protocol BIT 8 =3D=3D 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 th= is > into ) patricia-tree filters that ran in hardware at wirespeed. But, API= s > into ernels were hard to get accepted. > In the end, only people willing to pay for this were TLAs who wanted to r= un > regex's on traffic. Regex took lots of ram, but TLAs didn't buy many sock= ets. 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 airca= ps. 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 suspe= cted. > -- > ] Never tell me the odds! | ipv6 mesh netwo= rks [ > ] Michael Richardson, Sandelman Software Works | network archite= ct [ > ] mcr@sandelman.ca http://www.sandelman.ca/ | ruby on rails= [ > > > _______________________________________________ > Bloat mailing list > Bloat@lists.bufferbloat.net > https://lists.bufferbloat.net/listinfo/bloat > --=20 Dave T=C3=A4ht Let's go make home routers and wifi faster! With better software! http://blog.cerowrt.org