bpf: add a longest prefix match trie map implementation
authorDaniel Mack <daniel@zonque.org>
Sat, 21 Jan 2017 16:26:11 +0000 (17:26 +0100)
committerDavid S. Miller <davem@davemloft.net>
Mon, 23 Jan 2017 21:10:38 +0000 (16:10 -0500)
commitb95a5c4db09bc7c253636cb84dc9b12c577fd5a0
treea8c872a2412680a6a670d10d3d16df68b4587272
parent10eeb5e645b5332b24986a554046f6c9cc2c22d4
bpf: add a longest prefix match trie map implementation

This trie implements a longest prefix match algorithm that can be used
to match IP addresses to a stored set of ranges.

Internally, data is stored in an unbalanced trie of nodes that has a
maximum height of n, where n is the prefixlen the trie was created
with.

Tries may be created with prefix lengths that are multiples of 8, in
the range from 8 to 2048. The key used for lookup and update operations
is a struct bpf_lpm_trie_key, and the value is a uint64_t.

The code carries more information about the internal implementation.

Signed-off-by: Daniel Mack <daniel@zonque.org>
Reviewed-by: David Herrmann <dh.herrmann@gmail.com>
Acked-by: Alexei Starovoitov <ast@kernel.org>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/uapi/linux/bpf.h
kernel/bpf/Makefile
kernel/bpf/lpm_trie.c [new file with mode: 0644]