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)
commit8d75839b843ae0ef8d9db97ed05b493e687e6b75
treea105ed36362e91dede6e6d145e215c9fb9ea4007
parente4b0c94bd24cf8c992919233a2a4e350cd15cde2
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