bpf: add longest prefix match map
Subsystems (5)
v4 cover bpf: add longest prefix match map
This patch set adds a longest prefix match algorithm that can be used to match IP addresses to a stored set of ranges. It is exposed as a bpf map type.
Internally, data is stored in an unbalanced tree of nodes that has a maximum height of n, where n is the prefixlen the trie was created with.
Note that this has nothing to do with fib or fib6 and is in no way meant to replace or share code with it. It's rather a much simpler implementation that is specifically written with bpf maps in mind.
Patch 1/2 adds the implementation, 2/2 an extensive test suite and 3/3 has benchmarking code for the new trie type.
Feedback is much appreciated.
Thanks,
Daniel
Changelog:
v3 -> v4:
* David added a 3rd patch that augments map_perf_test for LPM trie benchmarks
* Limit allocation of maps of this new type to CAP_SYS_ADMIN for now, as requested by Alexei
* Add a stub .map_delete_elem so the core does not stumble over a NULL pointer when the syscall is invoked
* Tests for non-power-of-2 prefix lengths were added
* More comment style fixes
v2 -> v3:
* Store both the key match data and the caller provided value in the same byte array attached to a node. This avoids double allocations
* Bring back node->flags to distinguish between 'real' and intermediate nodes
* Fix comment style and some typos
v1 -> v2:
* Turn spin lock into raw spinlock
* Lock with irqsave options during trie_update_elem()
* Return -ENOMEM properly from trie_alloc()
* Force attr->flags == BPF_F_NO_PREALLOC during creation
* Set trie->map.pages after creation to account for map memory
* Allow arbitrary value sizes
* Removed node->flags and denode intermediate nodes through node->value == NULL instead
rfc -> v1:
* Add __rcu pointer annotations to make sparse happy
* Fold _lpm_trie_find_target_node() into its only caller
* Fix some minor documentation issues
Daniel Mack (1):
bpf: add a longest prefix match trie map implementation
David Herrmann (2):
bpf: Add tests for the lpm trie map
samples/bpf: add lpm-trie benchmark
include/uapi/linux/bpf.h | 7 + kernel/bpf/Makefile | 2 +- kernel/bpf/lpm_trie.c | 503 +++++++++++++++++++++++++++++ samples/bpf/map_perf_test_kern.c | 30 ++ samples/bpf/map_perf_test_user.c | 49 +++ tools/testing/selftests/bpf/.gitignore | 1 + tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/test_lpm_map.c | 358 ++++++++++++++++++++ 8 files changed, 951 insertions(+), 3 deletions(-) create mode 100644 kernel/bpf/lpm_trie.c create mode 100644 tools/testing/selftests/bpf/test_lpm_map.c
Signature · 1 line
2.9.3
PATCH v4 2/3 bpf: Add tests for the lpm trie map
From: David Herrmann <[email protected]>
The first part of this program runs randomized tests against the lpm-bpf-map. It implements a "Trivial Longest Prefix Match" (tlpm) based on simple, linear, single linked lists. The implementation should be pretty straightforward.
Based on tlpm, this inserts randomized data into bpf-lpm-maps and verifies the trie-based bpf-map implementation behaves the same way as tlpm.
The second part uses 'real world' IPv4 and IPv6 addresses and tests the trie with those.
--- tools/testing/selftests/bpf/.gitignore | 1 + tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/test_lpm_map.c | 358 +++++++++++++++++++++++++++++ 3 files changed, 361 insertions(+), 2 deletions(-) create mode 100644 tools/testing/selftests/bpf/test_lpm_map.c
tools/testing/selftests/bpf/.gitignore +1 -0
@@ -1,3 +1,4 @@ test_verifier test_maps test_lru_map +test_lpm_map
tools/testing/selftests/bpf/Makefile +2 -2
@@ -1,8 +1,8 @@ CFLAGS += -Wall -O2 -I../../../../usr/include -test_objs = test_verifier test_maps test_lru_map +test_objs = test_verifier test_maps test_lru_map test_lpm_map -TEST_PROGS := test_verifier test_maps test_lru_map test_kmod.sh +TEST_PROGS := test_verifier test_maps test_lru_map test_lpm_map test_kmod.sh TEST_FILES := $(test_objs) all: $(test_objs)
tools/testing/selftests/bpf/test_lpm_map.c new file +358 -0
358 lines not on this page · raw message
Signature · 1 line
2.9.3
PATCH v4 3/3 samples/bpf: add lpm-trie benchmark
In reply to Daniel MackFrom: David Herrmann <[email protected]>
Extend the map_perf_test_{user,kern}.c infrastructure to stress test lpm-trie lookups. We hook into the kprobe on sys_gettid() and measure the latency depending on trie size and lookup count.
On my Intel Haswell i7-6400U, a single gettid() syscall with an empty bpf program takes roughly 6.5us on my system. Lookups in empty tries take ~1.8us on first try, ~0.9us on retries. Lookups in tries with 8192 entries take ~7.1us (on the first _and_ any subsequent try).
--- samples/bpf/map_perf_test_kern.c | 30 ++++++++++++++++++++++++ samples/bpf/map_perf_test_user.c | 49 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 79 insertions(+)
samples/bpf/map_perf_test_kern.c +30 -0
@@ -57,6 +57,14 @@ struct bpf_map_def SEC("maps") percpu_hash_map_alloc = { .map_flags = BPF_F_NO_PREALLOC, }; +struct bpf_map_def SEC("maps") lpm_trie_map_alloc = { + .type = BPF_MAP_TYPE_LPM_TRIE, + .key_size = 8, + .value_size = sizeof(long), + .max_entries = 10000, + .map_flags = BPF_F_NO_PREALLOC, +}; + SEC("kprobe/sys_getuid")int stress_hmap (struct pt_regs *ctx) {
@@ -135,5 +143,27 @@ int stress_percpu_lru_hmap_alloc(struct pt_regs *ctx)return 0 ; } +SEC("kprobe/sys_gettid") +int stress_lpm_trie_map_alloc (struct pt_regs *ctx) +{ +union { +u32 b32[2 ]; +u8 b8[8 ]; + } key; +unsigned int i; + + key.b32[0 ] =32 ; + key.b8[4 ] =192 ; + key.b8[5 ] =168 ; + key.b8[6 ] =0 ; + key.b8[7 ] =1 ; + +#pragma clang loop unroll(full) +for (i =0 ; i <32 ; ++i) +bpf_map_lookup_elem (&lpm_trie_map_alloc, &key); + +return 0 ; +} + char _license[] SEC("license") = "GPL"; u32 _version SEC("version") = LINUX_VERSION_CODE;
samples/bpf/map_perf_test_user.c +49 -0
79 lines not on this page · raw message
Signature · 1 line
2.9.3
PATCH v4 1/3 bpf: add a longest prefix match trie map implementation
In reply to Daniel MackThis 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.
--- include/uapi/linux/bpf.h | 7 + kernel/bpf/Makefile | 2 +- kernel/bpf/lpm_trie.c | 503 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 511 insertions(+), 1 deletion(-) create mode 100644 kernel/bpf/lpm_trie.c
include/uapi/linux/bpf.h +7 -0
@@ -63,6 +63,12 @@ struct bpf_insn {__s32 imm;/* signed immediate constant */ }; +/* Key of an a BPF_MAP_TYPE_LPM_TRIE entry */ +struct bpf_lpm_trie_key { +__u32 prefixlen;/* up to 32 for AF_INET, 128 for AF_INET6 */ +__u8 data[0 ];/* Arbitrary size */ +}; +/* BPF syscall commands, see bpf(2) man-page for details. */ enum bpf_cmd {BPF_MAP_CREATE ,
@@ -89,6 +95,7 @@ enum bpf_map_type {BPF_MAP_TYPE_CGROUP_ARRAY ,BPF_MAP_TYPE_LRU_HASH ,BPF_MAP_TYPE_LRU_PERCPU_HASH , + BPF_MAP_TYPE_LPM_TRIE, }; enum bpf_prog_type {
kernel/bpf/Makefile +1 -1
@@ -1,7 +1,7 @@ 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 +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
kernel/bpf/lpm_trie.c new file +503 -0
503 lines not on this page · raw message
Signature · 1 line
2.9.3
Re: [PATCH v4 1/3] bpf: add a longest prefix match trie map implementation
Quoted 7 lines · Daniel Mack
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.
Quoted 8 lines
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 auint64_t.The code carries more information about the internal implementation.
Signed-off-by Daniel Mack <[email protected]>Reviewed-by David Herrmann <[email protected]>
Looks great to me.
Re: [PATCH v4 2/3] bpf: Add tests for the lpm trie map
In reply to Daniel MackQuoted 11 lines · Daniel Mack
From: David Herrmann <[email protected]>
The first part of this program runs randomized tests against the lpm-bpf-map. It implements a "Trivial Longest Prefix Match" (tlpm) based on simple, linear, single linked lists. The implementation should be pretty straightforward.
Based on tlpm, this inserts randomized data into bpf-lpm-maps and verifies the trie-based bpf-map implementation behaves the same way as tlpm.
Quoted 5 lines
The second part uses 'real world' IPv4 and IPv6 addresses and tests the trie with those.
Signed-off-by David Herrmann <[email protected]>Signed-off-by Daniel Mack <[email protected]>
Re: [PATCH v4 3/3] samples/bpf: add lpm-trie benchmark
In reply to Daniel MackQuoted 6 lines · Daniel Mack
From: David Herrmann <[email protected]>
Extend the map_perf_test_{user,kern}.c infrastructure to stress test lpm-trie lookups. We hook into the kprobe on
sys_gettid()and measure the latency depending on trie size and lookup count.
Quoted 7 lines
On my Intel Haswell i7-6400U, a single
gettid()syscall with an empty bpf program takes roughly 6.5us on my system. Lookups in empty tries take ~1.8us on first try, ~0.9us on retries. Lookups in tries with 8192 entries take ~7.1us (on the first _and_ any subsequent try).Signed-off-by David Herrmann <[email protected]>Reviewed-by Daniel Mack <[email protected]>
Thank you for all the hard work you've put into these patches. All looks great to me.
Daniel Borkmann
maintainerRe: [PATCH v4 1/3] bpf: add a longest prefix match trie map implementation
In reply to Daniel MackOn 01/21/2017 05:26 PM, Daniel Mack wrote:
[...]
kernel/bpf/lpm_trie.c line 265
Quoted 6 lines
kernel/bpf/lpm_trie.c new file +6
-0+/* Called from syscall or from eBPF program */ +static int trie_update_elem (struct bpf_map *map, +void *_key,void *value,u64 flags) +{ + struct lpm_trie *trie = container_of(map, struct lpm_trie, map); +struct lpm_trie_node *node, *im_node, *new_node =NULL ;
im_node is uninitialized here ...
Quoted 10 lines
kernel/bpf/lpm_trie.c new file +10
-0+struct lpm_trie_node __rcu **slot; +struct bpf_lpm_trie_key *key = _key; +unsigned long irq_flags; +unsigned int next_bit; +size_t matchlen =0 ; +int ret =0 ; + +if (unlikely (flags >BPF_EXIST )) +return -EINVAL ; +
kernel/bpf/lpm_trie.c line 285
Quoted 10 lines
kernel/bpf/lpm_trie.c new file +10
-0+if (key->prefixlen > trie->max_prefixlen) +return -EINVAL ; + +raw_spin_lock_irqsave (&trie->lock, irq_flags); + +/* Allocate and fill a new node */ + +if (trie->n_entries == trie->map.max_entries) { + ret = -ENOSPC ; + goto out;
... and here we go to out path with ret as non-zero ...
Quoted 7 lines
kernel/bpf/lpm_trie.c new file +7
-0+ } + + new_node =lpm_trie_node_alloc (trie, value); +if (!new_node) { + ret = -ENOMEM ; + goto out; + }
[...]
kernel/bpf/lpm_trie.c line 383
Quoted 8 lines
kernel/bpf/lpm_trie.c new file +8
-0+ +out: +if (ret) { +if (new_node) + trie->n_entries--; + +kfree (new_node); +kfree (im_node);
... which does kfree() in im_node here.
Quoted 6 lines
kernel/bpf/lpm_trie.c new file +6
-0+ } + +raw_spin_unlock_irqrestore (&trie->lock, irq_flags); + +return ret; +}
Re: [PATCH v4 1/3] bpf: add a longest prefix match trie map implementation
Quoted 42 lines · Daniel Borkmann
On 01/21/2017 05:26 PM, Daniel Mack wrote:
[...]kernel/bpf/lpm_trie.c line 265
Quoted 6 lines
kernel/bpf/lpm_trie.c new file +6
-0+/* Called from syscall or from eBPF program */ +static int trie_update_elem (struct bpf_map *map, +void *_key,void *value,u64 flags) +{ + struct lpm_trie *trie = container_of(map, struct lpm_trie, map); +struct lpm_trie_node *node, *im_node, *new_node =NULL ;
im_nodeis uninitialized here ...Quoted 10 lines
kernel/bpf/lpm_trie.c new file +10
-0+struct lpm_trie_node __rcu **slot; +struct bpf_lpm_trie_key *key = _key; +unsigned long irq_flags; +unsigned int next_bit; +size_t matchlen =0 ; +int ret =0 ; + +if (unlikely (flags >BPF_EXIST )) +return -EINVAL ; +kernel/bpf/lpm_trie.c line 285
Quoted 10 lines
kernel/bpf/lpm_trie.c new file +10
-0+if (key->prefixlen > trie->max_prefixlen) +return -EINVAL ; + +raw_spin_lock_irqsave (&trie->lock, irq_flags); + +/* Allocate and fill a new node */ + +if (trie->n_entries == trie->map.max_entries) { + ret = -ENOSPC ; + goto out;... and here we go to out path with ret as non-zero ...
Quoted 7 lines
kernel/bpf/lpm_trie.c new file +7
-0+ } + + new_node =lpm_trie_node_alloc (trie, value); +if (!new_node) { + ret = -ENOMEM ; + goto out; + }[...]
Quoted 10 lines
kernel/bpf/lpm_trie.c line 383
Quoted 8 lines
kernel/bpf/lpm_trie.c new file +8
-0+ +out: +if (ret) { +if (new_node) + trie->n_entries--; + +kfree (new_node); +kfree (im_node);... which does
kfree()inim_nodehere.
Oops. Nice catch! gcc was too stupid to recognize that :)
Thanks, I'll repost a v5 with Alexei's Acked-by later today.
Daniel
David Miller
maintainerFrom: Daniel Mack <[email protected]>
Date: Sat, 21 Jan 2017 17:26:10 +0100
Quoted 8 lines
This patch set adds a longest prefix match algorithm that can be used to match IP addresses to a stored set of ranges. It is exposed as a bpf map type.
Internally, data is stored in an unbalanced tree of nodes that has a maximum height of n, where n is the prefixlen the trie was created with.
Quoted 8 lines
Note that this has nothing to do with fib or fib6 and is in no way meant to replace or share code with it. It's rather a much simpler implementation that is specifically written with bpf maps in mind.
Patch 1/2 adds the implementation, 2/2 an extensive test suite and 3/3 has benchmarking code for the new trie type.
Feedback is much appreciated.
Series applied, thank you.