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

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 14 Nov 2019 15:55:51 +0100

Björn Töpel <[email-masked]> writes:

> On Thu, 14 Nov 2019 at 14:03, Daniel Borkmann <[email-masked]> wrote:
>>
>> On 11/14/19 1:31 PM, Toke Høiland-Jørgensen wrote:
>> > Björn Töpel <[email-masked]> writes:
>> >> From: Björn Töpel <[email-masked]>
>> >>
>> >> 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