selftests/bpf: Add LPM trie microbenchmarks
Subsystems (3)
PATCH v2 1/1 selftests/bpf: Add LPM trie microbenchmarks
From: Matt Fleming <[email protected]>
Add benchmarks for the standard set of operations: lookup, update, delete. Also, include a benchmark for trie_free() which is known to have terrible performance for maps with many entries.
Benchmarks operate on tries without gaps in the key range, i.e. each test begins with a trie with valid keys in the range [0, nr_entries). This is intended to cause maximum branching when traversing the trie.
All measurements are recorded inside the kernel to remove syscall overhead.
Most benchmarks run an XDP program to generate stats but free needs to collect latencies using fentry/fexit on map_free_deferred() because it's not possible to use fentry directly on lpm_trie.c since commit c83508da5620 ("bpf: Avoid deadlock caused by nested kprobe and fentry bpf programs") and there's no way to create/destroy a map from within an XDP program.
Here is example output from an AMD EPYC 9684X 96-Core machine for each of the benchmarks using a trie with 10K entries and a 32-bit prefix length, e.g.
$ ./bench lpm-trie-$op \ --prefix_len=32 \ --producers=1 \ --nr_entries=10000
lookup: throughput 7.423 ± 0.023 M ops/s ( 7.423M ops/prod), latency 134.710 ns/op
update: throughput 2.643 ± 0.015 M ops/s ( 2.643M ops/prod), latency 378.310 ns/op
delete: throughput 0.712 ± 0.008 M ops/s ( 0.712M ops/prod), latency 1405.152 ns/op
free: throughput 0.574 ± 0.003 K ops/s ( 0.574K ops/prod), latency 1.743 ms/op---
Changes in v2:
- Add Jesper's Tested-by and Revewied-by tags
- Remove use of atomic_*() in favour of __sync_add_and_fetch()
- Use a file-local 'deleted_entries' in the DELETE op benchmark and add a comment explaining why non-atomic accesses are safe.
- Bump 'hits' with the number of bpf_loop() loops actually executed
tools/testing/selftests/bpf/Makefile | 2 + tools/testing/selftests/bpf/bench.c | 10 + tools/testing/selftests/bpf/bench.h | 1 + .../selftests/bpf/benchs/bench_lpm_trie_map.c | 337 ++++++++++++++++++ .../selftests/bpf/progs/lpm_trie_bench.c | 171 +++++++++ .../selftests/bpf/progs/lpm_trie_map.c | 19 + 6 files changed, 540 insertions(+) create mode 100644 tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c create mode 100644 tools/testing/selftests/bpf/progs/lpm_trie_bench.c create mode 100644 tools/testing/selftests/bpf/progs/lpm_trie_map.c
tools/testing/selftests/bpf/Makefile +2 -0
@@ -815,6 +815,7 @@ $(OUTPUT)/bench_bpf_hashmap_lookup.o: $(OUTPUT)/bpf_hashmap_lookup.skel.h $(OUTPUT)/bench_htab_mem.o: $(OUTPUT)/htab_mem_bench.skel.h $(OUTPUT)/bench_bpf_crypto.o: $(OUTPUT)/crypto_bench.skel.h $(OUTPUT)/bench_sockmap.o: $(OUTPUT)/bench_sockmap_prog.skel.h +$(OUTPUT)/bench_lpm_trie_map.o: $(OUTPUT)/lpm_trie_bench.skel.h $(OUTPUT)/lpm_trie_map.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -836,6 +837,7 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_htab_mem.o \ $(OUTPUT)/bench_bpf_crypto.o \ $(OUTPUT)/bench_sockmap.o \ + $(OUTPUT)/bench_lpm_trie_map.o \ # $(call msg,BINARY,,$@) $(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
tools/testing/selftests/bpf/bench.c +10 -0
@@ -284,6 +284,7 @@ extern struct argp bench_htab_mem_argp;extern struct argp bench_trigger_batch_argp;extern struct argp bench_crypto_argp;extern struct argp bench_sockmap_argp; +extern struct argp bench_lpm_trie_map_argp;static const struct argp_child bench_parsers[] = { { &bench_ringbufs_argp,0 ,"Ring buffers benchmark" ,0 },
@@ -299,6 +300,7 @@ static const struct argp_child bench_parsers[] = { { &bench_trigger_batch_argp, 0, "BPF triggering benchmark", 0 }, { &bench_crypto_argp, 0, "bpf crypto benchmark", 0 }, { &bench_sockmap_argp, 0, "bpf sockmap benchmark", 0 }, + { &bench_lpm_trie_map_argp, 0, "LPM trie map benchmark", 0 }, {}, };
@@ -558,6 +560,10 @@ extern const struct bench bench_htab_mem;extern const struct bench bench_crypto_encrypt;extern const struct bench bench_crypto_decrypt;extern const struct bench bench_sockmap; +extern const struct bench bench_lpm_trie_lookup; +extern const struct bench bench_lpm_trie_update; +extern const struct bench bench_lpm_trie_delete; +extern const struct bench bench_lpm_trie_free;static const struct bench *benchs[] = { &bench_count_global,
@@ -625,6 +631,10 @@ static const struct bench *benchs[] = { &bench_crypto_encrypt, &bench_crypto_decrypt, &bench_sockmap, + &bench_lpm_trie_lookup, + &bench_lpm_trie_update, + &bench_lpm_trie_delete, + &bench_lpm_trie_free, };static void find_benchmark (void )
tools/testing/selftests/bpf/bench.h +1 -0
@@ -46,6 +46,7 @@ struct bench_res {unsigned long gp_ns;unsigned long gp_ct;unsigned int stime; +unsigned long duration_ns; };struct bench {
tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c new file +337 -0
337 lines not on this page · raw message
tools/testing/selftests/bpf/progs/lpm_trie_bench.c new file +171 -0
171 lines not on this page · raw message
tools/testing/selftests/bpf/progs/lpm_trie_map.c new file +19 -0
@@ -0,0 +1,19 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_tracing.h> + +#define MAX_ENTRIES 100000000 + +struct trie_key { +__u32 prefixlen; +__u32 data; +}; + +struct { + __uint(type, BPF_MAP_TYPE_LPM_TRIE); + __type(key, struct trie_key); + __type(value, __u32); + __uint(map_flags, BPF_F_NO_PREALLOC); + __uint(max_entries, MAX_ENTRIES); +} trie_free_map SEC(".maps");
Signature · 1 line
2.34.1