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

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

[Jesper Dangaard Brouer]

On 18/07/2025 17.05, Matt Fleming wrote:
> From: Matt Fleming <mfleming@cloudflare.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@cloudflare.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@kernel.org>

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

Reviewed-by: Jesper Dangaard Brouer <hawk@kernel.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

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

[Matt Fleming]

On Sat, Jul 19, 2025 at 2:15 PM Jesper Dangaard Brouer <hawk@kernel.org> wrote:
>
> On 18/07/2025 17.05, Matt Fleming wrote:
>
> > [...]
> > 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` ?

Actually, we can side step this problem completely by consistently
using __sync_fetch_and_add() for duration_ns and hits and removing the
atomic operations for DELETE, which doesn't need atomicity anyway
since only a single producer can run.

I'll send a v2.

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

[Yonghong Song]

On 7/21/25 6:01 AM, Matt Fleming wrote:
> On Sat, Jul 19, 2025 at 2:15 PM Jesper Dangaard Brouer <hawk@kernel.org> wrote:
>> On 18/07/2025 17.05, Matt Fleming wrote:
>>
>>> [...]
>>> 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` ?
> Actually, we can side step this problem completely by consistently
> using __sync_fetch_and_add() for duration_ns and hits and removing the
> atomic operations for DELETE, which doesn't need atomicity anyway
> since only a single producer can run.

__sync_fetch_and_add() and __atomic_add_fetch() have the same
semantics. So indeed tt would be good to just use one of them.

>
> I'll send a v2.