netdev - Re: [RFC PATCH bpf-next 2/4] bpf: introduce BPF dispatcher

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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 14 Nov 2019 15:55:51 +0100
From:   Toke Høiland-Jørgensen <toke@...hat.com>
To:     Björn Töpel <bjorn.topel@...il.com>,
        Daniel Borkmann <daniel@...earbox.net>
Cc:     Netdev <netdev@...r.kernel.org>,
        Alexei Starovoitov <ast@...nel.org>,
        Björn Töpel <bjorn.topel@...el.com>,
        bpf <bpf@...r.kernel.org>,
        Magnus Karlsson <magnus.karlsson@...il.com>,
        "Karlsson\, Magnus" <magnus.karlsson@...el.com>,
        Jonathan Lemon <jonathan.lemon@...il.com>
Subject: Re: [RFC PATCH bpf-next 2/4] bpf: introduce BPF dispatcher

Björn Töpel <bjorn.topel@...il.com> writes:

> On Thu, 14 Nov 2019 at 14:03, Daniel Borkmann <daniel@...earbox.net> wrote:
>>
>> On 11/14/19 1:31 PM, Toke Høiland-Jørgensen wrote:
>> > Björn Töpel <bjorn.topel@...il.com> writes:
>> >> From: Björn Töpel <bjorn.topel@...el.com>
>> >>
>> >> The BPF dispatcher builds on top of the BPF trampoline ideas;
>> >> Introduce bpf_arch_text_poke() and (re-)use the BPF JIT generate
>> >> code. The dispatcher builds a dispatch table for XDP programs, for
>> >> retpoline avoidance. The table is a simple binary search model, so
>> >> lookup is O(log n). Here, the dispatch table is limited to four
>> >> entries (for laziness reason -- only 1B relative jumps :-P). If the
>> >> dispatch table is full, it will fallback to the retpoline path.
>> >
>> > So it's O(log n) with n == 4? Have you compared the performance of just
>> > doing four linear compare-and-jumps? Seems to me it may not be that big
>> > of a difference for such a small N?
>>
>> Did you perform some microbenchmarks wrt search tree? Mainly wondering
>> since for code emission for switch/case statements, clang/gcc turns off
>> indirect calls entirely under retpoline, see [0] from back then.
>>
>
> As Toke stated, binsearch is not needed for 4 entries. I started out
> with 16 (and explicit ids instead of pointers), and there it made more
> sense. If folks think it's a good idea to move forward -- and with 4
> entries, it makes sense to make the code generator easier, or maybe
> based on static_calls like Ed did.

I don't really have anything to back it up, but my hunch is that only 4
entries will end up being a limit that people are going to end up
hitting. And since the performance falls off quite the cliff after
hitting that limit, I do fear that this is something we will hear about
quite emphatically :)

-Toke