Eric Lee / smarc-fsl-linux-kernel | Embedian Git Server

b95a5c4db bpf: add a longest prefix match trie map implementation ... Browse Code »

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
Reviewed-by: David Herrmann
Acked-by: Alexei Starovoitov
Signed-off-by: David S. Miller

Daniel Mack
2017-01-24 05:10:38 +0800

Makefile 293 Bytes

edit raw blame history

1 2 3 4 5 6 7 8

obj-y := core.o

obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o
obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o
ifeq ($(CONFIG_PERF_EVENTS),y)
obj-$(CONFIG_BPF_SYSCALL) += stackmap.o
endif
obj-$(CONFIG_CGROUP_BPF) += cgroup.o