On Fri, Dec 30, 2016 at 12:25 PM, David Miller <da...@davemloft.net> wrote: > From: Daniel Mack <dan...@zonque.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!
