netdev - Re: [PATCH v1 0/2] bpf: add longest prefix match map

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

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!