]> git.baikalelectronics.ru Git - kernel.git/commit
bpf, lpm: make longest_prefix_match() faster
authorEric Dumazet <edumazet@google.com>
Thu, 22 Nov 2018 05:39:52 +0000 (21:39 -0800)
committerDaniel Borkmann <daniel@iogearbox.net>
Thu, 22 Nov 2018 09:35:13 +0000 (10:35 +0100)
commit1193a704fcd18a6495129a15072681f6e27206d7
treea105ed36362e91dede6e6d145e215c9fb9ea4007
parent5909e24f4ca5c78f3900e256b3804528ffc6fe3e
bpf, lpm: make longest_prefix_match() faster

At LPC 2018 in Vancouver, Vlad Dumitrescu mentioned that longest_prefix_match()
has a high cost [1].

One reason for that cost is a loop handling one byte at a time.

We can handle more bytes at a time, if enough attention is paid
to endianness.

I was able to remove ~55 % of longest_prefix_match() cpu costs.

[1] https://linuxplumbersconf.org/event/2/contributions/88/attachments/76/87/lpc-bpf-2018-shaping.pdf

Signed-off-by: Eric Dumazet <edumazet@google.com>
Cc: Vlad Dumitrescu <vladum@google.com>
Cc: Alexei Starovoitov <ast@kernel.org>
Cc: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
kernel/bpf/lpm_trie.c