linux-kernel - Re: [PATCH bpf-next v3] 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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <67bc8bbb-9fad-4eb6-86d3-71098358e071@kernel.org>
Date: Wed, 13 Aug 2025 18:59:36 +0200
From: Jesper Dangaard Brouer <hawk@...nel.org>
To: Alexei Starovoitov <alexei.starovoitov@...il.com>,
 Matt Fleming <matt@...dmodwrite.com>
Cc: Alexei Starovoitov <ast@...nel.org>,
 Daniel Borkmann <daniel@...earbox.net>, Andrii Nakryiko <andrii@...nel.org>,
 Eduard Zingerman <eddyz87@...il.com>, Shuah Khan <shuah@...nel.org>,
 kernel-team <kernel-team@...udflare.com>,
 "open list:KERNEL SELFTEST FRAMEWORK" <linux-kselftest@...r.kernel.org>,
 LKML <linux-kernel@...r.kernel.org>, bpf <bpf@...r.kernel.org>,
 Martin KaFai Lau <martin.lau@...nel.org>,
 Yonghong Song <yonghong.song@...ux.dev>,
 Network Development <netdev@...r.kernel.org>,
 Matt Fleming <mfleming@...udflare.com>
Subject: Re: [PATCH bpf-next v3] selftests/bpf: Add LPM trie microbenchmarks



On 28/07/2025 16.34, Alexei Starovoitov 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..522e1cbef490
>> --- /dev/null
>> +++ b/tools/testing/selftests/bpf/progs/lpm_trie_bench.c
[...]
>> +
>> +static void gen_random_key(struct trie_key *key)
>> +{
>> +       key->prefixlen = prefixlen;
>> +       key->data = bpf_get_prandom_u32() % nr_entries;
> bpf_get_prandom_u32() is not free
> and modulo operation isn't free either.
> The benchmark includes their time.
> It's ok to have it, but add a mode where the bench
> tests linear lookup/update too with simple key.data++

I've extended this bench with a "noop" and "baseline" benchmark[1].

  [1] 
https://lore.kernel.org/all/175509897596.2755384.18413775753563966331.stgit@firesoul/

This allowed us to measure and deduce that the:
   bpf_get_prandom_u32() % nr_entries

Takes 14.1 nanosec for doing the rand + modulo.

The "noop" test shows harness overhead is 13.402 ns/op
and on-top the "baseline" shows randomness takes 27.529 ns/op.

--Jesper