netdev - Re: [PATCH] selftests/bpf: Add LPM trie microbenchmarks

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-ID: <81cd8749-6212-4fcf-8e1a-5eba5a8e2a73@kernel.org>
Date: Sat, 19 Jul 2025 15:15:06 +0200
From: Jesper Dangaard Brouer <hawk@...nel.org>
To: Matt Fleming <matt@...dmodwrite.com>, Alexei Starovoitov
 <ast@...nel.org>, Daniel Borkmann <daniel@...earbox.net>,
 Andrii Nakryiko <andrii@...nel.org>, Eduard Zingerman <eddyz87@...il.com>,
 Martin KaFai Lau <martin.lau@...nel.org>
Cc: Shuah Khan <shuah@...nel.org>, kernel-team@...udflare.com,
 linux-kselftest@...r.kernel.org, linux-kernel@...r.kernel.org,
 bpf@...r.kernel.org, Matt Fleming <mfleming@...udflare.com>,
 Yonghong Song <yonghong.song@...ux.dev>, Netdev <netdev@...r.kernel.org>
Subject: Re: [PATCH] selftests/bpf: Add LPM trie microbenchmarks



On 18/07/2025 17.05, Matt Fleming wrote:
> From: Matt Fleming <mfleming@...udflare.com>
> 
> 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
> 
> Signed-off-by: Matt Fleming <mfleming@...udflare.com>
> ---
>   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 | 345 ++++++++++++++++++
>   .../selftests/bpf/progs/lpm_trie_bench.c      | 175 +++++++++
>   .../selftests/bpf/progs/lpm_trie_map.c        |  19 +
>   6 files changed, 552 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
> 

I've already tested + reviewed this and different version of this 
benchmark during internal development.  Thanks to Matt for working on this.

Tested-by: Jesper Dangaard Brouer <hawk@...nel.org>

You can add my reviewed by when we resolve below comment.

Reviewed-by: Jesper Dangaard Brouer <hawk@...nel.org>


> [...]
> diff --git a/tools/testing/selftests/bpf/progs/lpm_trie_bench.c b/tools/testing/selftests/bpf/progs/lpm_trie_bench.c
> new file mode 100644
> index 000000000000..c335718cc240
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/lpm_trie_bench.c
> @@ -0,0 +1,175 @@
[...]
> +
> +static __always_inline void atomic_inc(long *cnt)
> +{
> +	__atomic_add_fetch(cnt, 1, __ATOMIC_SEQ_CST);
> +}
> +
> +static __always_inline long atomic_swap(long *cnt, long val)
> +{
> +	return __atomic_exchange_n(cnt, val, __ATOMIC_SEQ_CST);
> +}

For userspace includes we have similar defines in bench.h.
Except they use __ATOMIC_RELAXED and here __ATOMIC_SEQ_CST.
Which is the correct to use?

For BPF kernel-side do selftests have another header file that define
these `atomic_inc` and `atomic_swap` ?

--Jesper