Björn Töpel <bjorn.topel@xxxxxxxxx> writes: > On Thu, 14 Nov 2019 at 14:03, Daniel Borkmann <daniel@xxxxxxxxxxxxx> wrote: >> >> On 11/14/19 1:31 PM, Toke Høiland-Jørgensen wrote: >> > Björn Töpel <bjorn.topel@xxxxxxxxx> writes: >> >> From: Björn Töpel <bjorn.topel@xxxxxxxxx> >> >> >> >> 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
