lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAADnVQJ63TVkzA+2dUzmdywuMXo5TcwR0WmM0VC++7SShzKrdw@mail.gmail.com> Date: Sat, 31 Dec 2016 14:31:36 -0800 From: Alexei Starovoitov <alexei.starovoitov@...il.com> To: David Miller <davem@...emloft.net> Cc: Daniel Mack <daniel@...que.org>, Alexei Starovoitov <ast@...com>, dh.herrmann@...il.com, Daniel Borkmann <daniel@...earbox.net>, "netdev@...r.kernel.org" <netdev@...r.kernel.org> Subject: Re: [PATCH v1 0/2] bpf: add longest prefix match map On Fri, Dec 30, 2016 at 12:25 PM, David Miller <davem@...emloft.net> wrote: > From: Daniel Mack <daniel@...que.org> > Date: Thu, 29 Dec 2016 18:28:53 +0100 > >> This patch set adds a longest prefix match algorithm that can be used >> to match IP addresses to a stored set of ranges. It is exposed as a >> bpf map type. >> >> Internally, data is stored in an unbalanced tree of nodes that has a >> maximum height of n, where n is the prefixlen the trie was created >> with. >> >> Not that this has nothing to do with fib or fib6 and is in no way meant >> to replace or share code with it. It's rather a much simpler >> implementation that is specifically written with bpf maps in mind. >> >> Patch 1/2 adds the implementation, and 2/2 an extensive test suite. >> >> Feedback is much appreciated. > > I'll give Alexei and Daniel time to provide feedback on this series. I did a quick glance over and, in general, I'm very much in favor. Will do a proper review Jan 3rd when I'm back from pto. Daniel, could you provide performance numbers for lookups per second for different key lengths with almost empty and almost full 100k+ lpm rules? And the rate of updates per second? I guess your use case is more traditional 32 or 128 bit lpm whereas I'd like to use it as 64-bit lpm. Would be good to add few tests with non-power of 8 key length (it seems to me they should be supported by the algo). Thank you for working on it!
Powered by blists - more mailing lists