Skip to contentSkip to conversation

bpf: add longest prefix match map

PATCH Superseded Daniel Mack 4 participants 6 messages Jan 14, 2017 – Jan 18, 2017

Subsystems (5)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 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, and 2/2 an extensive test suite.

Feedback is much appreciated.

Thanks,
Daniel

Changelog:

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 (1):
bpf: Add tests for the lpm trie map

 include/uapi/linux/bpf.h                   |   7 +
 kernel/bpf/Makefile                        |   2 +-
 kernel/bpf/lpm_trie.c                      | 493 +++++++++++++++++++++++++++++
 tools/testing/selftests/bpf/.gitignore     |   1 +
 tools/testing/selftests/bpf/Makefile       |   4 +-
 tools/testing/selftests/bpf/test_lpm_map.c | 358 +++++++++++++++++++++
 6 files changed, 862 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
#1 lore raw

PATCH v3 1/2 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.

---
 include/uapi/linux/bpf.h |   7 +
 kernel/bpf/Makefile      |   2 +-
 kernel/bpf/lpm_trie.c    | 493 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 501 insertions(+), 1 deletion(-)
 create mode 100644 kernel/bpf/lpm_trie.c
include/uapi/linux/bpf.h +7 -0
index 0eb0e87..d564277 100644
@@ -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
index 1276474..e1ce4f4 100644
@@ -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 +493 -0

493 lines not on this page · raw message

Signature · 1 line
2.9.3
#2 lore raw

Re: [PATCH v3 1/2] bpf: add a longest prefix match trie map implementation

kernel/bpf/lpm_trie.c line 403

Quoted 13 lines · Daniel Mack
kernel/bpf/lpm_trie.c new file +13 -0
+static struct bpf_map *trie_alloc(union bpf_attr *attr)
+{
+	size_t cost, cost_per_node;
+	struct lpm_trie *trie;
+	int ret;
+
+	/* check sanity of attributes */
+	if (attr->max_entries == 0 ||
+	    attr->map_flags != BPF_F_NO_PREALLOC ||
+	    attr->key_size < sizeof(struct bpf_lpm_trie_key) + 1   ||
+	    attr->key_size > sizeof(struct bpf_lpm_trie_key) + 256 ||
+	    attr->value_size == 0)
+		return ERR_PTR(-EINVAL);

could you also make it root only for now ?
Like we did for lru map:

        if (lru && !capable(CAP_SYS_ADMIN))
                /* LRU implementation is much complicated than other
                 * maps.  Hence, limit to CAP_SYS_ADMIN for now.
                 */
                return ERR_PTR(-EPERM);

trie is not that complicated, but I think socket_filters (the only unpriv prog type today) can live a release or two without ability to use it.

In patch 2/2 there are some comments not in networking style:
+ /*
+ * Perform longest prefix-match on @key/@n_bits. That is,

As far as performance it has to be measured from datapath. Like create tc+cls_bpf prog that does a dozen of trie lookups, attach it to veth or tap and use samples/pktgen/pktgen_bench_xmit_mode_netif_receive.sh to send traffic into it.
Like: samples/bpf/test_cls_bpf.sh does.

Another alternative is to extend samples/bpf/map_perf_test It has perf tests for most map types today (including lru) and trie would be natural addition there.
I would prefer this latter option.

Thanks!

#3 lore raw

Re: [PATCH v3 1/2] bpf: add a longest prefix match trie map implementation

Hi

Quoted 4 lines · Alexei Starovoitov

Another alternative is to extend samples/bpf/map_perf_test It has perf tests for most map types today (including lru) and trie would be natural addition there.
I would prefer this latter option.

I hooked into gettid() and installed a simple kprobe bpf program that searches for an entry in an lpm trie. The bpf program does either 0, 1, 8, or 32 lookups in a row (always the same element). The trie has size 0, 1, or 8192. The data is below. The results vary by roughly 5% on every run.

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).

https://gist.github.com/dvdhrm/4c90e61a1c39746d5c55ab9e0e29315e

Thanks
David

Trie-size: 0
#Lookups: 0

    0:lpm_perf kmalloc 9,230,321 events per sec
    -> 6.5us / syscall

Trie-size: 1
#Lookups: 1

    0:lpm_perf kmalloc 7,224,508 events per sec
    -> 8.3us / syscall

Trie-size: 1
#Lookups: 8

    0:lpm_perf kmalloc 4,152,740 events per sec
    -> 14.4us / syscall

Trie-size: 1
#Lookups: 32

    0:lpm_perf kmalloc 1,713,415 events per sec
    -> 35.0us / syscall

Trie-size: 8192
#Lookups: 1

    0:lpm_perf kmalloc 4,369,138 events per sec
    -> 13.7us / syscall

Trie-size: 8192
#Lookups: 8
0:lpm_perf kmalloc 943,849 events per sec
-> 63.6us / syscall

Trie-size: 8192
#Lookups: 32
0:lpm_perf kmalloc 271,737 events per sec
-> 220.8us / syscall

#4 lore raw

Re: [PATCH v3 1/2] bpf: add a longest prefix match trie map implementation

Quoted 14 lines · David Herrmann

Hi

Quoted 4 lines · Alexei Starovoitov

Another alternative is to extend samples/bpf/map_perf_test It has perf tests for most map types today (including lru) and trie would be natural addition there.
I would prefer this latter option.

I hooked into gettid() and installed a simple kprobe bpf program that searches for an entry in an lpm trie. The bpf program does either 0, 1, 8, or 32 lookups in a row (always the same element). The trie has size 0, 1, or 8192. The data is below. The results vary by roughly 5% on every run.

Quoted 4 lines

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).

thanks. please add them to commit log.

Quoted 1 line

https://gist.github.com/dvdhrm/4c90e61a1c39746d5c55ab9e0e29315e

looks good. please add it as an extra patch to this set. and add
#pragma clang loop unroll(full)
before
+ for (i = 0; i < 8; ++i)
+ bpf_map_lookup_elem(&lpm_trie_map_alloc, &key);
to make sure it's unrolled regardless of the version of llvm.

Quoted 30 lines

Trie-size: 0
#Lookups: 0

    0:lpm_perf kmalloc 9,230,321 events per sec
    -> 6.5us / syscall

Trie-size: 1
#Lookups: 1

    0:lpm_perf kmalloc 7,224,508 events per sec
    -> 8.3us / syscall

Trie-size: 1
#Lookups: 8

    0:lpm_perf kmalloc 4,152,740 events per sec
    -> 14.4us / syscall

Trie-size: 1
#Lookups: 32

    0:lpm_perf kmalloc 1,713,415 events per sec
    -> 35.0us / syscall

Trie-size: 8192
#Lookups: 1

    0:lpm_perf kmalloc 4,369,138 events per sec
    -> 13.7us / syscall

Trie-size: 8192
#Lookups: 8
0:lpm_perf kmalloc 943,849 events per sec
-> 63.6us / syscall

Quoted 4 lines

Trie-size: 8192
#Lookups: 32
0:lpm_perf kmalloc 271,737 events per sec
-> 220.8us / syscall

so it's the same lookup done 32-times per each syscall. Since the latency of single lookup in 8 vs 32 experiments are pretty close, it means that the 32 lookup numbers amortize the cost of syscall pretty well and no need to go higher. So I would use 32 as a loop count in stress_lpm_trie_map_alloc()

Thanks!

#5 lore raw

PATCH v3 2/2 bpf: Add tests for the lpm trie map

In reply to 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.

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
index 071431b..d3b1c9b 100644
@@ -1,3 +1,4 @@
 test_verifier
 test_maps
 test_lru_map
+test_lpm_map
tools/testing/selftests/bpf/Makefile +2 -2
index 7a5f245..064a3e5 100644
@@ -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