- Linux-kselftest-mirror - lists.linaro.org

[PATCH 00/22] selftests/damon/sysfs.py: test all parameters

by SeongJae Park

sysfs.py tests if DAMON sysfs interface is passing the user-requested parameters to DAMON as expected. But only the default (minimum) parameters are being tested. This is partially because _damon_sysfs.py, which is the library for making the parameter requests, is not supporting the entire parameters. The internal DAMON status dump script (drgn_dump_damon_status.py) is also not dumping entire parameters. Extend the test coverage by updating parameters input and status dumping scripts to support all parameters, and writing additional tests using those. This increased test coverage actually found one real bug (https://lore.kernel.org/20250719181932.72944-1-sj@kernel.org). First seven patches (1-7) extend _damon_sysfs.py for all parameters setup. The eight patch (8) fixes _damon_sysfs.py to use correct max nr_acceses and age values for their type. Following three patches (9-11) extend drgn_dump_damon_status.py to dump full DAMON parameters. Following nine patches (12-20) refactor sysfs.py for general testing code reuse, and extend it for full parameters check. Finally, two patches (21 and 22) add test cases in sysfs.py for full parameters testing. SeongJae Park (22): selftests/damon/_damon_sysfs: support DAMOS watermarks setup selftests/damon/_damon_sysfs: support DAMOS filters setup selftests/damon/_damon_sysfs: support monitoring intervals goal setup selftests/damon/_damon_sysfs: support DAMOS quota weights setup selftests/damon/_damon_sysfs: support DAMOS quota goal nid setup selftests/damon/_damon_sysfs: support DAMOS action dests setup selftests/damon/_damon_sysfs: support DAMOS target_nid setup selftests/damon/_damon_sysfs: use 2**32 - 1 as max nr_accesses and age selftests/damon/drgn_dump_damon_status: dump damos->migrate_dests selftests/damon/drgn_dump_damon_status: dump ctx->ops.id selftests/damon/drgn_dump_damon_status: dump DAMOS filters selftests/damon/sysfs.py: generalize DAMOS Watermarks commit assertion selftests/damon/sysfs.py: generalize DamosQuota commit assertion selftests/damon/sysfs.py: test quota goal commitment selftests/damon/sysfs.py: test DAMOS destinations commitment selftests/damon/sysfs.py: generalize DAMOS schemes commit assertion selftests/damon/sysfs.py: test DAMOS filters commitment selftests/damon/sysfs.py: generalize DAMOS schemes commit assertion selftests/damon/sysfs.py: generalize monitoring attributes commit assertion selftests/damon/sysfs.py: generalize DAMON context commit assertion selftests/damon/sysfs.py: test non-default parameters runtime commit selftests/damon/sysfs.py: test runtime reduction of DAMON parameters tools/testing/selftests/damon/_damon_sysfs.py | 301 +++++++++++++++++- .../selftests/damon/drgn_dump_damon_status.py | 63 +++- tools/testing/selftests/damon/sysfs.py | 284 +++++++++++++---- 3 files changed, 568 insertions(+), 80 deletions(-) base-commit: fc8066077f44a4fd43f8fdb12bc238f8fbeaa3c5 -- 2.39.5

5 months, 1 week

2
24
0 0

[RESEND PATCH] selftests/pidfd: align stack to fix SP alignment exception

by Shuai Xue

The pidfd_test fails on the ARM64 platform with the following error: Bail out! pidfd_poll check for premature notification on child thread exec test: Failed When exception-trace is enabled, the kernel logs the details: #echo 1 > /proc/sys/debug/exception-trace #dmesg | tail -n 20 [48628.713023] pidfd_test[1082142]: unhandled exception: SP Alignment, ESR 0x000000009a000000, SP/PC alignment exception in pidfd_test[400000+4000] [48628.713049] CPU: 21 PID: 1082142 Comm: pidfd_test Kdump: loaded Tainted: G W E 6.6.71-3_rc1.al8.aarch64 #1 [48628.713051] Hardware name: AlibabaCloud AliServer-Xuanwu2.0AM-1UC1P-5B/AS1111MG1, BIOS 1.2.M1.AL.P.157.00 07/29/2023 [48628.713053] pstate: 60001800 (nZCv daif -PAN -UAO -TCO -DIT +SSBS BTYPE=-c) [48628.713055] pc : 0000000000402100 [48628.713056] lr : 0000ffff98288f9c [48628.713056] sp : 0000ffffde49daa8 [48628.713057] x29: 0000000000000000 x28: 0000000000000000 x27: 0000000000000000 [48628.713060] x26: 0000000000000000 x25: 0000000000000000 x24: 0000000000000000 [48628.713062] x23: 0000000000000000 x22: 0000000000000000 x21: 0000000000400e80 [48628.713065] x20: 0000000000000000 x19: 0000000000402650 x18: 0000000000000000 [48628.713067] x17: 00000000004200d8 x16: 0000ffff98288f40 x15: 0000ffffde49b92c [48628.713070] x14: 0000000000000000 x13: 0000000000000000 x12: 0000000000000000 [48628.713072] x11: 0000000000001011 x10: 0000000000402100 x9 : 0000000000000010 [48628.713074] x8 : 00000000000000dc x7 : 3861616239346564 x6 : 000000000000000a [48628.713077] x5 : 0000ffffde49daa8 x4 : 000000000000000a x3 : 0000ffffde49daa8 [48628.713079] x2 : 0000ffffde49dadc x1 : 0000ffffde49daa8 x0 : 0000000000000000 According to ARM ARM D1.3.10.2 SP alignment checking: > When the SP is used as the base address of a calculation, regardless of > any offset applied by the instruction, if bits [3:0] of the SP are not > 0b0000, there is a misaligned SP. To fix it, align the stack with 16 bytes. Signed-off-by: Shuai Xue <xueshuai(a)linux.alibaba.com> --- tools/testing/selftests/pidfd/pidfd_test.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tools/testing/selftests/pidfd/pidfd_test.c b/tools/testing/selftests/pidfd/pidfd_test.c index c081ae91313a..ec161a7c3ff9 100644 --- a/tools/testing/selftests/pidfd/pidfd_test.c +++ b/tools/testing/selftests/pidfd/pidfd_test.c @@ -33,7 +33,7 @@ static bool have_pidfd_send_signal; static pid_t pidfd_clone(int flags, int *pidfd, int (*fn)(void *)) { size_t stack_size = 1024; - char *stack[1024] = { 0 }; + char *stack[1024] __attribute__((aligned(16))) = {0}; #ifdef __ia64__ return __clone2(fn, stack, stack_size, flags | SIGCHLD, NULL, pidfd); -- 2.39.3

5 months, 1 week

3
6
0 0

[PATCH net-next] selftests: tc: Add generic erspan_opts matching support for tc-flower

by shuali＠redhat.com

From: Li Shuang <shuali(a)redhat.com> Add test cases to tc_flower.sh to validate generic matching on ERSPAN options. Both ERSPAN Type II and Type III are covered. Also add check_tc_erspan_support() to verify whether tc supports erspan_opts. Signed-off-by: Li Shuang <shuali(a)redhat.com> --- tools/testing/selftests/net/forwarding/lib.sh | 14 +++++ .../selftests/net/forwarding/tc_flower.sh | 52 ++++++++++++++++++- 2 files changed, 65 insertions(+), 1 deletion(-) diff --git a/tools/testing/selftests/net/forwarding/lib.sh b/tools/testing/selftests/net/forwarding/lib.sh index 9308b2f77fed..890b3374dacd 100644 --- a/tools/testing/selftests/net/forwarding/lib.sh +++ b/tools/testing/selftests/net/forwarding/lib.sh @@ -142,6 +142,20 @@ check_tc_version() fi } +check_tc_erspan_support() +{ + local dev=$1; shift + + tc filter add dev $dev ingress pref 1 handle 1 flower \ + erspan_opts 1:0:0:0 &> /dev/null + if [[ $? -ne 0 ]]; then + echo "SKIP: iproute2 too old; tc is missing erspan support" + return $ksft_skip + fi + tc filter del dev $dev ingress pref 1 handle 1 flower \ + erspan_opts 1:0:0:0 &> /dev/null +} + # Old versions of tc don't understand "mpls_uc" check_tc_mpls_support() { diff --git a/tools/testing/selftests/net/forwarding/tc_flower.sh b/tools/testing/selftests/net/forwarding/tc_flower.sh index b1daad19b01e..b58909a93112 100755 --- a/tools/testing/selftests/net/forwarding/tc_flower.sh +++ b/tools/testing/selftests/net/forwarding/tc_flower.sh @@ -6,7 +6,7 @@ ALL_TESTS="match_dst_mac_test match_src_mac_test match_dst_ip_test \ match_ip_tos_test match_indev_test match_ip_ttl_test match_mpls_label_test \ match_mpls_tc_test match_mpls_bos_test match_mpls_ttl_test \ - match_mpls_lse_test" + match_mpls_lse_test match_erspan_opts_test" NUM_NETIFS=2 source tc_common.sh source lib.sh @@ -676,6 +676,56 @@ match_mpls_lse_test() log_test "mpls lse match ($tcflags)" } +match_erspan_opts_test() +{ + RET=0 + + check_tc_erspan_support $h2 || return 0 + + # h1 erspan setup + tunnel_create erspan1 erspan 192.0.2.1 192.0.2.2 dev $h1 seq key 1001 \ + tos C ttl 64 erspan_ver 1 erspan 6789 # ERSPAN Type II + tunnel_create erspan2 erspan 192.0.2.1 192.0.2.2 dev $h1 seq key 1002 \ + tos C ttl 64 erspan_ver 2 erspan_dir egress erspan_hwid 63 \ + # ERSPAN Type III + ip link set dev erspan1 master v$h1 + ip link set dev erspan2 master v$h1 + # h2 erspan setup + ip link add ep-ex type erspan ttl 64 external # To collect tunnel info + ip link set ep-ex up + ip link set dev ep-ex master v$h2 + tc qdisc add dev ep-ex clsact + + # ERSPAN Type II [decap direction] + tc filter add dev ep-ex ingress protocol ip handle 101 flower \ + $tcflags enc_src_ip 192.0.2.1 enc_dst_ip 192.0.2.2 \ + enc_key_id 1001 erspan_opts 1:6789:0:0 \ + action drop + # ERSPAN Type III [decap direction] + tc filter add dev ep-ex ingress protocol ip handle 102 flower \ + $tcflags enc_src_ip 192.0.2.1 enc_dst_ip 192.0.2.2 \ + enc_key_id 1002 erspan_opts 2:0:1:63 action drop + + ep1mac=$(mac_get erspan1) + $MZ erspan1 -c 1 -p 64 -a $ep1mac -b $h2mac -t ip -q + tc_check_packets "dev ep-ex ingress" 101 1 + check_err $? "ERSPAN Type II" + + ep2mac=$(mac_get erspan2) + $MZ erspan2 -c 1 -p 64 -a $ep1mac -b $h2mac -t ip -q + tc_check_packets "dev ep-ex ingress" 102 1 + check_err $? "ERSPAN Type III" + + # h2 erspan cleanup + tc qdisc del dev ep-ex clsact + tunnel_destroy ep-ex + # h1 erspan cleanup + tunnel_destroy erspan2 # ERSPAN Type III + tunnel_destroy erspan1 # ERSPAN Type II + + log_test "erspan_opts match ($tcflags)" +} + setup_prepare() { h1=${NETIFS[p1]} -- 2.50.1

5 months, 1 week

3
2
0 0

[PATCH net v2 0/2] selftests: mptcp: connect: cover alt modes

by Matthieu Baerts (NGI0)

mptcp_connect.sh can be executed manually with "-m <MODE>" and "-C" to make sure everything works as expected when using "mmap" and "sendfile" modes instead of "poll", and with the MPTCP checksum support. These modes should be validated, but they are not when the selftests are executed via the kselftest helpers. It means that most CIs validating these selftests, like NIPA for the net development trees and LKFT for the stable ones, are not covering these modes. To fix that, new test programs have been added, simply calling mptcp_connect.sh with the right parameters. The first patch can be backported up to v5.6, and the second one up to v5.14. Signed-off-by: Matthieu Baerts (NGI0) <matttbe(a)kernel.org> --- Changes in v2: - force using a different prefix in the subtests to avoid having the same test names in all mptcp_connect*.sh selftests. - Link to v1: https://lore.kernel.org/r/20250714-net-mptcp-sft-connect-alt-v1-0-bf1c5abbe… --- Matthieu Baerts (NGI0) (2): selftests: mptcp: connect: also cover alt modes selftests: mptcp: connect: also cover checksum tools/testing/selftests/net/mptcp/Makefile | 3 ++- tools/testing/selftests/net/mptcp/mptcp_connect_checksum.sh | 5 +++++ tools/testing/selftests/net/mptcp/mptcp_connect_mmap.sh | 5 +++++ tools/testing/selftests/net/mptcp/mptcp_connect_sendfile.sh | 5 +++++ 4 files changed, 17 insertions(+), 1 deletion(-) --- base-commit: b640daa2822a39ff76e70200cb2b7b892b896dce change-id: 20250714-net-mptcp-sft-connect-alt-c1aaf073ef4e Best regards, -- Matthieu Baerts (NGI0) <matttbe(a)kernel.org>

5 months, 1 week

4
12
0 0

Re: [PATCH v3 5/7] perf test: Introduce storing logs for shell tests

by Ian Rogers

On Mon, Jul 21, 2025 at 6:27 AM Jakub Brnak <jbrnak(a)redhat.com> wrote: > > From: Veronika Molnarova <vmolnaro(a)redhat.com> > > Create temporary directories for storing log files for shell tests > that could help while debugging. The log files are necessary for > perftool testsuite test cases also. If the variable KEEP_TEST_LOGS > is set keep the logs, else delete them. Is there perhaps a kunit equivalent of log files so we could keep the implementations as similar as possible? Thanks, Ian > Signed-off-by: Michael Petlan <mpetlan(a)redhat.com> > Signed-off-by: Veronika Molnarova <vmolnaro(a)redhat.com> > Signed-off-by: Jakub Brnak <jbrnak(a)redhat.com> > --- > tools/perf/tests/builtin-test.c | 90 ++++++++++++++++++++++++++++++++ > tools/perf/tests/tests-scripts.c | 3 ++ > tools/perf/tests/tests-scripts.h | 1 + > 3 files changed, 94 insertions(+) > > diff --git a/tools/perf/tests/builtin-test.c b/tools/perf/tests/builtin-test.c > index 4e3d2f779b01..89b180798224 100644 > --- a/tools/perf/tests/builtin-test.c > +++ b/tools/perf/tests/builtin-test.c > @@ -6,6 +6,7 @@ > */ > #include <ctype.h> > #include <fcntl.h> > +#include <ftw.h> > #include <errno.h> > #ifdef HAVE_BACKTRACE_SUPPORT > #include <execinfo.h> > @@ -282,6 +283,86 @@ static bool test_exclusive(const struct test_suite *t, int test_case) > return t->test_cases[test_case].exclusive; > } > > +static int delete_file(const char *fpath, const struct stat *sb __maybe_unused, > + int typeflag, struct FTW *ftwbuf) > +{ > + int rv = -1; > + > + /* Stop traversal if going too deep */ > + if (ftwbuf->level > 5) { > + pr_err("Tree traversal reached level %d, stopping.", ftwbuf->level); > + return rv; > + } > + > + /* Remove only expected directories */ > + if (typeflag == FTW_D || typeflag == FTW_DP){ > + const char *dirname = fpath + ftwbuf->base; > + > + if (strcmp(dirname, "logs") && strcmp(dirname, "examples") && > + strcmp(dirname, "header_tar") && strncmp(dirname, "perf_", 5)) { > + pr_err("Unknown directory %s", dirname); > + return rv; > + } > + } > + > + /* Attempt to remove the file */ > + rv = remove(fpath); > + if (rv) > + pr_err("Failed to remove file: %s", fpath); > + > + return rv; > +} > + > +static bool create_logs(struct test_suite *t, int pass){ > + bool store_logs = t->priv && ((struct shell_info*)(t->priv))->store_logs; > + if (pass == 1 && (!test_exclusive(t, 0) || sequential || dont_fork)) { > + /* Sequential and non-exclusive tests run on the first pass. */ > + return store_logs; > + } > + else if (pass != 1 && test_exclusive(t, 0) && !sequential && !dont_fork) { > + /* Exclusive tests without sequential run on the second pass. */ > + return store_logs; > + } > + return false; > +} > + > +static char *setup_shell_logs(const char *name) > +{ > + char template[PATH_MAX]; > + char *temp_dir; > + > + if (snprintf(template, PATH_MAX, "/tmp/perf_test_%s.XXXXXX", name) < 0) { > + pr_err("Failed to create log dir template"); > + return NULL; /* Skip the testsuite */ > + } > + > + temp_dir = mkdtemp(template); > + if (temp_dir) { > + setenv("PERFSUITE_RUN_DIR", temp_dir, 1); > + return strdup(temp_dir); > + } > + else { > + pr_err("Failed to create the temporary directory"); > + } > + > + return NULL; /* Skip the testsuite */ > +} > + > +static void cleanup_shell_logs(char *dirname) > +{ > + char *keep_logs = getenv("PERFTEST_KEEP_LOGS"); > + > + /* Check if logs should be kept or do cleanup */ > + if (dirname) { > + if (!keep_logs || strcmp(keep_logs, "y") != 0) { > + nftw(dirname, delete_file, 8, FTW_DEPTH | FTW_PHYS); > + } > + free(dirname); > + } > + > + unsetenv("PERFSUITE_RUN_DIR"); > +} > + > static bool perf_test__matches(const char *desc, int suite_num, int argc, const char *argv[]) > { > int i; > @@ -626,6 +707,7 @@ static int __cmd_test(struct test_suite **suites, int argc, const char *argv[], > for (struct test_suite **t = suites; *t; t++, curr_suite++) { > int curr_test_case; > bool suite_matched = false; > + char *tmpdir = NULL; > > if (!perf_test__matches(test_description(*t, -1), curr_suite, argc, argv)) { > /* > @@ -655,6 +737,13 @@ static int __cmd_test(struct test_suite **suites, int argc, const char *argv[], > } > > for (unsigned int run = 0; run < runs_per_test; run++) { > + /* Setup temporary log directories for shell test suites */ > + if (create_logs(*t, pass)) { > + tmpdir = setup_shell_logs((*t)->desc); > + > + if (tmpdir == NULL) /* Couldn't create log dir, skip test suite */ > + ((struct shell_info*)((*t)->priv))->has_setup = FAILED_SETUP; > + } > test_suite__for_each_test_case(*t, curr_test_case) { > if (!suite_matched && > !perf_test__matches(test_description(*t, curr_test_case), > @@ -667,6 +756,7 @@ static int __cmd_test(struct test_suite **suites, int argc, const char *argv[], > goto err_out; > } > } > + cleanup_shell_logs(tmpdir); > } > if (!sequential) { > /* Parallel mode starts tests but doesn't finish them. Do that now. */ > diff --git a/tools/perf/tests/tests-scripts.c b/tools/perf/tests/tests-scripts.c > index d680a878800f..d4e382898a30 100644 > --- a/tools/perf/tests/tests-scripts.c > +++ b/tools/perf/tests/tests-scripts.c > @@ -251,6 +251,7 @@ static struct test_suite* prepare_test_suite(int dir_fd) > > test_info->base_path = strdup_check(dirpath); /* Absolute path to dir */ > test_info->has_setup = NO_SETUP; > + test_info->store_logs = false; > > test_suite->priv = test_info; > test_suite->desc = NULL; > @@ -427,6 +428,8 @@ static void append_suits_in_dir(int dir_fd, > continue; > } > > + /* Store logs for testsuite is sub-directories */ > + ((struct shell_info*)(test_suite->priv))->store_logs = true; > if (is_test_script(fd, SHELL_SETUP)) { /* Check for setup existance */ > char *desc = shell_test__description(fd, SHELL_SETUP); > test_suite->desc = desc; /* Set the suite name by the setup description */ > diff --git a/tools/perf/tests/tests-scripts.h b/tools/perf/tests/tests-scripts.h > index da4dcd26140c..41da0a175e4e 100644 > --- a/tools/perf/tests/tests-scripts.h > +++ b/tools/perf/tests/tests-scripts.h > @@ -16,6 +16,7 @@ enum shell_setup { > struct shell_info { > const char *base_path; > enum shell_setup has_setup; > + bool store_logs; > }; > > struct test_suite **create_script_test_suites(void); > -- > 2.50.1 >

5 months, 1 week

1
0
0 0

[PATCH v4 0/6] binder: Set up KUnit tests for alloc

by Tiffany Yang

Hello, binder_alloc_selftest provides a robust set of checks for the binder allocator, but it rarely runs because it must hook into a running binder process and block all other binder threads until it completes. The test itself is a good candidate for conversion to KUnit, and it can be further isolated from user processes by using a test-specific lru freelist instead of the global one. This series converts the selftest to KUnit to make it less burdensome to run and to set up a foundation for unit testing future binder_alloc changes. Thanks, Tiffany Tiffany Yang (6): binder: Fix selftest page indexing binder: Store lru freelist in binder_alloc kunit: test: Export kunit_attach_mm() binder: Scaffolding for binder_alloc KUnit tests binder: Convert binder_alloc selftests to KUnit binder: encapsulate individual alloc test cases drivers/android/Kconfig | 15 +- drivers/android/Makefile | 2 +- drivers/android/binder.c | 10 +- drivers/android/binder_alloc.c | 39 +- drivers/android/binder_alloc.h | 14 +- drivers/android/binder_alloc_selftest.c | 306 ----------- drivers/android/binder_internal.h | 4 + drivers/android/tests/.kunitconfig | 7 + drivers/android/tests/Makefile | 6 + drivers/android/tests/binder_alloc_kunit.c | 572 +++++++++++++++++++++ include/kunit/test.h | 12 + lib/kunit/user_alloc.c | 4 +- 12 files changed, 651 insertions(+), 340 deletions(-) delete mode 100644 drivers/android/binder_alloc_selftest.c create mode 100644 drivers/android/tests/.kunitconfig create mode 100644 drivers/android/tests/Makefile create mode 100644 drivers/android/tests/binder_alloc_kunit.c -- 2.50.0.727.gbf7dc18ff4-goog

5 months, 1 week

4
13
0 0

[PATCH] selftests/bpf: Add LPM trie microbenchmarks

by Matt Fleming

From: Matt Fleming <mfleming(a)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(a)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 diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile index 910d8d6402ef..10a5f1d0fa41 100644 --- a/tools/testing/selftests/bpf/Makefile +++ b/tools/testing/selftests/bpf/Makefile @@ -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 $@ diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c index ddd73d06a1eb..fd15f60fd5a8 100644 --- a/tools/testing/selftests/bpf/bench.c +++ b/tools/testing/selftests/bpf/bench.c @@ -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) diff --git a/tools/testing/selftests/bpf/bench.h b/tools/testing/selftests/bpf/bench.h index 005c401b3e22..bea323820ffb 100644 --- a/tools/testing/selftests/bpf/bench.h +++ b/tools/testing/selftests/bpf/bench.h @@ -46,6 +46,7 @@ struct bench_res { unsigned long gp_ns; unsigned long gp_ct; unsigned int stime; + unsigned long duration_ns; }; struct bench { diff --git a/tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c b/tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c new file mode 100644 index 000000000000..ddd7d3669e70 --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c @@ -0,0 +1,345 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Cloudflare */ + +/* + * All of these benchmarks operate on tries with keys in the range + * [0, args.nr_entries), i.e. there are no gaps or partially filled + * branches of the trie for any key < args.nr_entries. + * + * This gives an idea of worst-case behaviour. + */ + +#include <argp.h> +#include <linux/time64.h> +#include <linux/if_ether.h> +#include "lpm_trie_bench.skel.h" +#include "lpm_trie_map.skel.h" +#include "bench.h" +#include "testing_helpers.h" + +static struct ctx { + struct lpm_trie_bench *bench; +} ctx; + +static struct { + __u32 nr_entries; + __u32 prefixlen; +} args = { + .nr_entries = 10000, + .prefixlen = 32, +}; + +enum { + ARG_NR_ENTRIES = 9000, + ARG_PREFIX_LEN, +}; + +static const struct argp_option opts[] = { + { "nr_entries", ARG_NR_ENTRIES, "NR_ENTRIES", 0, + "Number of unique entries in the LPM trie" }, + { "prefix_len", ARG_PREFIX_LEN, "PREFIX_LEN", 0, + "Number of prefix bits to use in the LPM trie" }, + {}, +}; + +static error_t lpm_parse_arg(int key, char *arg, struct argp_state *state) +{ + long ret; + + switch (key) { + case ARG_NR_ENTRIES: + ret = strtol(arg, NULL, 10); + if (ret < 1 || ret > UINT_MAX) { + fprintf(stderr, "Invalid nr_entries count."); + argp_usage(state); + } + args.nr_entries = ret; + break; + case ARG_PREFIX_LEN: + ret = strtol(arg, NULL, 10); + if (ret < 1 || ret > UINT_MAX) { + fprintf(stderr, "Invalid prefix_len value."); + argp_usage(state); + } + args.prefixlen = ret; + break; + default: + return ARGP_ERR_UNKNOWN; + } + return 0; +} + +const struct argp bench_lpm_trie_map_argp = { + .options = opts, + .parser = lpm_parse_arg, +}; + +static void __lpm_validate(void) +{ + if (env.consumer_cnt != 0) { + fprintf(stderr, "benchmark doesn't support consumer!\n"); + exit(1); + } + + if ((1UL << args.prefixlen) < args.nr_entries) { + fprintf(stderr, "prefix_len value too small for nr_entries!\n"); + exit(1); + }; +} + +enum { OP_LOOKUP = 1, OP_UPDATE, OP_DELETE, OP_FREE }; + +static void lpm_delete_validate(void) +{ + __lpm_validate(); + + if (env.producer_cnt != 1) { + fprintf(stderr, + "lpm-trie-delete requires a single producer!\n"); + exit(1); + } +} + +static void lpm_free_validate(void) +{ + __lpm_validate(); + + if (env.producer_cnt != 1) { + fprintf(stderr, "lpm-trie-free requires a single producer!\n"); + exit(1); + } +} + +static void fill_map(int map_fd) +{ + int i, err; + + for (i = 0; i < args.nr_entries; i++) { + struct trie_key { + __u32 prefixlen; + __u32 data; + } key = { args.prefixlen, i }; + __u32 val = 1; + + err = bpf_map_update_elem(map_fd, &key, &val, BPF_NOEXIST); + if (err) { + fprintf(stderr, "failed to add key %d to map: %d\n", + key.data, -err); + exit(1); + } + } +} + +static void __lpm_setup(void) +{ + ctx.bench = lpm_trie_bench__open_and_load(); + if (!ctx.bench) { + fprintf(stderr, "failed to open skeleton\n"); + exit(1); + } + + ctx.bench->bss->nr_entries = args.nr_entries; + ctx.bench->bss->prefixlen = args.prefixlen; + + if (lpm_trie_bench__attach(ctx.bench)) { + fprintf(stderr, "failed to attach skeleton\n"); + exit(1); + } +} + +static void lpm_setup(void) +{ + int fd; + + __lpm_setup(); + + fd = bpf_map__fd(ctx.bench->maps.trie_map); + fill_map(fd); +} + +static void lpm_lookup_setup(void) +{ + lpm_setup(); + + ctx.bench->bss->op = OP_LOOKUP; +} + +static void lpm_update_setup(void) +{ + lpm_setup(); + + ctx.bench->bss->op = OP_UPDATE; +} + +static void lpm_delete_setup(void) +{ + lpm_setup(); + + ctx.bench->bss->op = OP_DELETE; +} + +static void lpm_free_setup(void) +{ + __lpm_setup(); + ctx.bench->bss->op = OP_FREE; +} + +static void lpm_measure(struct bench_res *res) +{ + res->hits = atomic_swap(&ctx.bench->bss->hits, 0); + res->duration_ns = atomic_swap(&ctx.bench->bss->duration_ns, 0); +} + +/* For LOOKUP, UPDATE, and DELETE */ +static void *lpm_producer(void *unused __always_unused) +{ + int err; + char in[ETH_HLEN]; /* unused */ + + LIBBPF_OPTS(bpf_test_run_opts, opts, .data_in = in, + .data_size_in = sizeof(in), .repeat = 1, ); + + while (true) { + int fd = bpf_program__fd(ctx.bench->progs.run_bench); + err = bpf_prog_test_run_opts(fd, &opts); + if (err) { + fprintf(stderr, "failed to run BPF prog: %d\n", err); + exit(1); + } + + if (opts.retval < 0) { + fprintf(stderr, "BPF prog returned error: %d\n", + opts.retval); + exit(1); + } + + if (ctx.bench->bss->op == OP_DELETE && opts.retval == 1) { + /* trie_map needs to be refilled */ + fill_map(bpf_map__fd(ctx.bench->maps.trie_map)); + } + } + + return NULL; +} + +static void *lpm_free_producer(void *unused __always_unused) +{ + while (true) { + struct lpm_trie_map *skel; + + skel = lpm_trie_map__open_and_load(); + if (!skel) { + fprintf(stderr, "failed to open skeleton\n"); + exit(1); + } + + fill_map(bpf_map__fd(skel->maps.trie_free_map)); + lpm_trie_map__destroy(skel); + } + + return NULL; +} + +static __always_inline double duration_ms(struct bench_res *res) +{ + if (!res->hits) + return 0.0; + + return res->duration_ns / res->hits / NSEC_PER_MSEC; +} + +static void free_ops_report_progress(int iter, struct bench_res *res, + long delta_ns) +{ + double hits_per_sec, hits_per_prod; + double rate_divisor = 1000.0; + char rate = 'K'; + + hits_per_sec = res->hits / (res->duration_ns / (double)NSEC_PER_SEC) / + rate_divisor; + hits_per_prod = hits_per_sec / env.producer_cnt; + + printf("Iter %3d (%7.3lfus): ", iter, + (delta_ns - NSEC_PER_SEC) / 1000.0); + printf("hits %8.3lf%c/s (%7.3lf%c/prod)\n", hits_per_sec, rate, + hits_per_prod, rate); +} + +static void free_ops_report_final(struct bench_res res[], int res_cnt) +{ + double hits_mean = 0.0, hits_stddev = 0.0; + double lat_divisor = 1000000.0; + double rate_divisor = 1000.0; + const char *unit = "ms"; + double latency = 0.0; + char rate = 'K'; + int i; + + for (i = 0; i < res_cnt; i++) { + double val = res[i].hits / rate_divisor / + (res[i].duration_ns / (double)NSEC_PER_SEC); + hits_mean += val / (0.0 + res_cnt); + latency += res[i].duration_ns / res[i].hits / (0.0 + res_cnt); + } + + if (res_cnt > 1) { + for (i = 0; i < res_cnt; i++) { + double val = + res[i].hits / rate_divisor / + (res[i].duration_ns / (double)NSEC_PER_SEC); + hits_stddev += (hits_mean - val) * (hits_mean - val) / + (res_cnt - 1.0); + } + + hits_stddev = sqrt(hits_stddev); + } + printf("Summary: throughput %8.3lf \u00B1 %5.3lf %c ops/s (%7.3lf%c ops/prod), ", + hits_mean, hits_stddev, rate, hits_mean / env.producer_cnt, + rate); + printf("latency %8.3lf %s/op\n", + latency / lat_divisor / env.producer_cnt, unit); +} + +const struct bench bench_lpm_trie_lookup = { + .name = "lpm-trie-lookup", + .argp = &bench_lpm_trie_map_argp, + .validate = __lpm_validate, + .setup = lpm_lookup_setup, + .producer_thread = lpm_producer, + .measure = lpm_measure, + .report_progress = ops_report_progress, + .report_final = ops_report_final, +}; + +const struct bench bench_lpm_trie_update = { + .name = "lpm-trie-update", + .argp = &bench_lpm_trie_map_argp, + .validate = __lpm_validate, + .setup = lpm_update_setup, + .producer_thread = lpm_producer, + .measure = lpm_measure, + .report_progress = ops_report_progress, + .report_final = ops_report_final, +}; + +const struct bench bench_lpm_trie_delete = { + .name = "lpm-trie-delete", + .argp = &bench_lpm_trie_map_argp, + .validate = lpm_delete_validate, + .setup = lpm_delete_setup, + .producer_thread = lpm_producer, + .measure = lpm_measure, + .report_progress = ops_report_progress, + .report_final = ops_report_final, +}; + +const struct bench bench_lpm_trie_free = { + .name = "lpm-trie-free", + .argp = &bench_lpm_trie_map_argp, + .validate = lpm_free_validate, + .setup = lpm_free_setup, + .producer_thread = lpm_free_producer, + .measure = lpm_measure, + .report_progress = free_ops_report_progress, + .report_final = free_ops_report_final, +}; 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 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Cloudflare */ + +#include <vmlinux.h> +#include <bpf/bpf_tracing.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_core_read.h> +#include "bpf_misc.h" + +#define BPF_OBJ_NAME_LEN 16U +#define MAX_ENTRIES 100000000 +#define NR_LOOPS 10000 + +struct trie_key { + __u32 prefixlen; + __u32 data; +}; + +char _license[] SEC("license") = "GPL"; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 512); + __type(key, struct bpf_map *); + __type(value, __u64); +} latency_free_start SEC(".maps"); + +/* Filled by userspace. See fill_map() in bench_lpm_trie_map.c */ +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_map SEC(".maps"); + +long hits; +long duration_ns; + +/* Configured from userspace */ +__u64 nr_entries; +__u32 prefixlen; +__u8 op; + +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); +} + +SEC("fentry/bpf_map_free_deferred") +int BPF_PROG(trie_free_entry, struct work_struct *work) +{ + struct bpf_map *map = container_of(work, struct bpf_map, work); + const char *name; + u32 map_type; + __u64 val; + + map_type = BPF_CORE_READ(map, map_type); + if (map_type != BPF_MAP_TYPE_LPM_TRIE) + return 0; + + /* + * Ideally we'd have access to the map ID but that's already + * freed before we enter trie_free(). + */ + name = BPF_CORE_READ(map, name); + if (bpf_strncmp(name, BPF_OBJ_NAME_LEN, "trie_free_map")) + return 0; + + val = bpf_ktime_get_ns(); + bpf_map_update_elem(&latency_free_start, &map, &val, BPF_ANY); + + return 0; +} + +SEC("fexit/bpf_map_free_deferred") +int BPF_PROG(trie_free_exit, struct work_struct *work) +{ + struct bpf_map *map = container_of(work, struct bpf_map, work); + __u64 *val; + + val = bpf_map_lookup_elem(&latency_free_start, &map); + if (val) { + __sync_add_and_fetch(&duration_ns, bpf_ktime_get_ns() - *val); + atomic_inc(&hits); + bpf_map_delete_elem(&latency_free_start, &map); + } + + return 0; +} + +static void gen_random_key(struct trie_key *key) +{ + key->prefixlen = prefixlen; + key->data = bpf_get_prandom_u32() % nr_entries; +} + +static int lookup(__u32 index, __u32 *unused) +{ + struct trie_key key; + + gen_random_key(&key); + bpf_map_lookup_elem(&trie_map, &key); + return 0; +} + +static int update(__u32 index, __u32 *unused) +{ + struct trie_key key; + u32 val = bpf_get_prandom_u32(); + + gen_random_key(&key); + bpf_map_update_elem(&trie_map, &key, &val, BPF_EXIST); + return 0; +} + +long deleted_entries; +long refill; + +static int delete (__u32 index, __u32 *unused) +{ + struct trie_key key = { + .data = deleted_entries, + .prefixlen = prefixlen, + }; + + bpf_map_delete_elem(&trie_map, &key); + atomic_inc(&deleted_entries); + + /* Do we need to refill the map? */ + if (deleted_entries >= nr_entries) { + atomic_swap(&refill, 1); + atomic_swap(&deleted_entries, 0); + return 1; + } + + return 0; +} + +SEC("xdp") +int BPF_PROG(run_bench) +{ + u64 start, delta; + bool need_refill = false; + + start = bpf_ktime_get_ns(); + + switch (op) { + case 1: + bpf_loop(NR_LOOPS, lookup, NULL, 0); + break; + case 2: + bpf_loop(NR_LOOPS, update, NULL, 0); + break; + case 3: + bpf_loop(NR_LOOPS, delete, NULL, 0); + need_refill = atomic_swap(&refill, 0); + break; + default: + bpf_printk("invalid benchmark operation\n"); + return -1; + } + + delta = bpf_ktime_get_ns() - start; + + __sync_add_and_fetch(&hits, NR_LOOPS); + __sync_add_and_fetch(&duration_ns, delta); + + return need_refill; +} diff --git a/tools/testing/selftests/bpf/progs/lpm_trie_map.c b/tools/testing/selftests/bpf/progs/lpm_trie_map.c new file mode 100644 index 000000000000..2ab43e2cd6c6 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/lpm_trie_map.c @@ -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"); -- 2.34.1

5 months, 1 week

3
4
0 0

[PATCH bpf-next v2] selftests/bpf: Add LPM trie microbenchmarks

by Matt Fleming

From: Matt Fleming <mfleming(a)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 Tested-by: Jesper Dangaard Brouer <hawk(a)kernel.org> Reviewed-by: Jesper Dangaard Brouer <hawk(a)kernel.org> Signed-off-by: Matt Fleming <mfleming(a)cloudflare.com> --- 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 diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile index 910d8d6402ef..10a5f1d0fa41 100644 --- a/tools/testing/selftests/bpf/Makefile +++ b/tools/testing/selftests/bpf/Makefile @@ -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 $@ diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c index ddd73d06a1eb..fd15f60fd5a8 100644 --- a/tools/testing/selftests/bpf/bench.c +++ b/tools/testing/selftests/bpf/bench.c @@ -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) diff --git a/tools/testing/selftests/bpf/bench.h b/tools/testing/selftests/bpf/bench.h index 005c401b3e22..bea323820ffb 100644 --- a/tools/testing/selftests/bpf/bench.h +++ b/tools/testing/selftests/bpf/bench.h @@ -46,6 +46,7 @@ struct bench_res { unsigned long gp_ns; unsigned long gp_ct; unsigned int stime; + unsigned long duration_ns; }; struct bench { diff --git a/tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c b/tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c new file mode 100644 index 000000000000..435b5c7ceee9 --- /dev/null +++ b/tools/testing/selftests/bpf/benchs/bench_lpm_trie_map.c @@ -0,0 +1,337 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Cloudflare */ + +/* + * All of these benchmarks operate on tries with keys in the range + * [0, args.nr_entries), i.e. there are no gaps or partially filled + * branches of the trie for any key < args.nr_entries. + * + * This gives an idea of worst-case behaviour. + */ + +#include <argp.h> +#include <linux/time64.h> +#include <linux/if_ether.h> +#include "lpm_trie_bench.skel.h" +#include "lpm_trie_map.skel.h" +#include "bench.h" +#include "testing_helpers.h" + +static struct ctx { + struct lpm_trie_bench *bench; +} ctx; + +static struct { + __u32 nr_entries; + __u32 prefixlen; +} args = { + .nr_entries = 10000, + .prefixlen = 32, +}; + +enum { + ARG_NR_ENTRIES = 9000, + ARG_PREFIX_LEN, +}; + +static const struct argp_option opts[] = { + { "nr_entries", ARG_NR_ENTRIES, "NR_ENTRIES", 0, + "Number of unique entries in the LPM trie" }, + { "prefix_len", ARG_PREFIX_LEN, "PREFIX_LEN", 0, + "Number of prefix bits to use in the LPM trie" }, + {}, +}; + +static error_t lpm_parse_arg(int key, char *arg, struct argp_state *state) +{ + long ret; + + switch (key) { + case ARG_NR_ENTRIES: + ret = strtol(arg, NULL, 10); + if (ret < 1 || ret > UINT_MAX) { + fprintf(stderr, "Invalid nr_entries count."); + argp_usage(state); + } + args.nr_entries = ret; + break; + case ARG_PREFIX_LEN: + ret = strtol(arg, NULL, 10); + if (ret < 1 || ret > UINT_MAX) { + fprintf(stderr, "Invalid prefix_len value."); + argp_usage(state); + } + args.prefixlen = ret; + break; + default: + return ARGP_ERR_UNKNOWN; + } + return 0; +} + +const struct argp bench_lpm_trie_map_argp = { + .options = opts, + .parser = lpm_parse_arg, +}; + +static void __lpm_validate(void) +{ + if (env.consumer_cnt != 0) { + fprintf(stderr, "benchmark doesn't support consumer!\n"); + exit(1); + } + + if ((1UL << args.prefixlen) < args.nr_entries) { + fprintf(stderr, "prefix_len value too small for nr_entries!\n"); + exit(1); + }; +} + +enum { OP_LOOKUP = 1, OP_UPDATE, OP_DELETE, OP_FREE }; + +static void lpm_delete_validate(void) +{ + __lpm_validate(); + + if (env.producer_cnt != 1) { + fprintf(stderr, + "lpm-trie-delete requires a single producer!\n"); + exit(1); + } +} + +static void lpm_free_validate(void) +{ + __lpm_validate(); + + if (env.producer_cnt != 1) { + fprintf(stderr, "lpm-trie-free requires a single producer!\n"); + exit(1); + } +} + +static void fill_map(int map_fd) +{ + int i, err; + + for (i = 0; i < args.nr_entries; i++) { + struct trie_key { + __u32 prefixlen; + __u32 data; + } key = { args.prefixlen, i }; + __u32 val = 1; + + err = bpf_map_update_elem(map_fd, &key, &val, BPF_NOEXIST); + if (err) { + fprintf(stderr, "failed to add key %d to map: %d\n", + key.data, -err); + exit(1); + } + } +} + +static void __lpm_setup(void) +{ + ctx.bench = lpm_trie_bench__open_and_load(); + if (!ctx.bench) { + fprintf(stderr, "failed to open skeleton\n"); + exit(1); + } + + ctx.bench->bss->nr_entries = args.nr_entries; + ctx.bench->bss->prefixlen = args.prefixlen; + + if (lpm_trie_bench__attach(ctx.bench)) { + fprintf(stderr, "failed to attach skeleton\n"); + exit(1); + } +} + +static void lpm_setup(void) +{ + int fd; + + __lpm_setup(); + + fd = bpf_map__fd(ctx.bench->maps.trie_map); + fill_map(fd); +} + +static void lpm_lookup_setup(void) +{ + lpm_setup(); + + ctx.bench->bss->op = OP_LOOKUP; +} + +static void lpm_update_setup(void) +{ + lpm_setup(); + + ctx.bench->bss->op = OP_UPDATE; +} + +static void lpm_delete_setup(void) +{ + lpm_setup(); + + ctx.bench->bss->op = OP_DELETE; +} + +static void lpm_free_setup(void) +{ + __lpm_setup(); + ctx.bench->bss->op = OP_FREE; +} + +static void lpm_measure(struct bench_res *res) +{ + res->hits = atomic_swap(&ctx.bench->bss->hits, 0); + res->duration_ns = atomic_swap(&ctx.bench->bss->duration_ns, 0); +} + +/* For LOOKUP, UPDATE, and DELETE */ +static void *lpm_producer(void *unused __always_unused) +{ + int err; + char in[ETH_HLEN]; /* unused */ + + LIBBPF_OPTS(bpf_test_run_opts, opts, .data_in = in, + .data_size_in = sizeof(in), .repeat = 1, ); + + while (true) { + int fd = bpf_program__fd(ctx.bench->progs.run_bench); + err = bpf_prog_test_run_opts(fd, &opts); + if (err) { + fprintf(stderr, "failed to run BPF prog: %d\n", err); + exit(1); + } + + if (opts.retval < 0) { + fprintf(stderr, "BPF prog returned error: %d\n", + opts.retval); + exit(1); + } + + if (ctx.bench->bss->op == OP_DELETE && opts.retval == 1) { + /* trie_map needs to be refilled */ + fill_map(bpf_map__fd(ctx.bench->maps.trie_map)); + } + } + + return NULL; +} + +static void *lpm_free_producer(void *unused __always_unused) +{ + while (true) { + struct lpm_trie_map *skel; + + skel = lpm_trie_map__open_and_load(); + if (!skel) { + fprintf(stderr, "failed to open skeleton\n"); + exit(1); + } + + fill_map(bpf_map__fd(skel->maps.trie_free_map)); + lpm_trie_map__destroy(skel); + } + + return NULL; +} + +static void free_ops_report_progress(int iter, struct bench_res *res, + long delta_ns) +{ + double hits_per_sec, hits_per_prod; + double rate_divisor = 1000.0; + char rate = 'K'; + + hits_per_sec = res->hits / (res->duration_ns / (double)NSEC_PER_SEC) / + rate_divisor; + hits_per_prod = hits_per_sec / env.producer_cnt; + + printf("Iter %3d (%7.3lfus): ", iter, + (delta_ns - NSEC_PER_SEC) / 1000.0); + printf("hits %8.3lf%c/s (%7.3lf%c/prod)\n", hits_per_sec, rate, + hits_per_prod, rate); +} + +static void free_ops_report_final(struct bench_res res[], int res_cnt) +{ + double hits_mean = 0.0, hits_stddev = 0.0; + double lat_divisor = 1000000.0; + double rate_divisor = 1000.0; + const char *unit = "ms"; + double latency = 0.0; + char rate = 'K'; + int i; + + for (i = 0; i < res_cnt; i++) { + double val = res[i].hits / rate_divisor / + (res[i].duration_ns / (double)NSEC_PER_SEC); + hits_mean += val / (0.0 + res_cnt); + latency += res[i].duration_ns / res[i].hits / (0.0 + res_cnt); + } + + if (res_cnt > 1) { + for (i = 0; i < res_cnt; i++) { + double val = + res[i].hits / rate_divisor / + (res[i].duration_ns / (double)NSEC_PER_SEC); + hits_stddev += (hits_mean - val) * (hits_mean - val) / + (res_cnt - 1.0); + } + + hits_stddev = sqrt(hits_stddev); + } + printf("Summary: throughput %8.3lf \u00B1 %5.3lf %c ops/s (%7.3lf%c ops/prod), ", + hits_mean, hits_stddev, rate, hits_mean / env.producer_cnt, + rate); + printf("latency %8.3lf %s/op\n", + latency / lat_divisor / env.producer_cnt, unit); +} + +const struct bench bench_lpm_trie_lookup = { + .name = "lpm-trie-lookup", + .argp = &bench_lpm_trie_map_argp, + .validate = __lpm_validate, + .setup = lpm_lookup_setup, + .producer_thread = lpm_producer, + .measure = lpm_measure, + .report_progress = ops_report_progress, + .report_final = ops_report_final, +}; + +const struct bench bench_lpm_trie_update = { + .name = "lpm-trie-update", + .argp = &bench_lpm_trie_map_argp, + .validate = __lpm_validate, + .setup = lpm_update_setup, + .producer_thread = lpm_producer, + .measure = lpm_measure, + .report_progress = ops_report_progress, + .report_final = ops_report_final, +}; + +const struct bench bench_lpm_trie_delete = { + .name = "lpm-trie-delete", + .argp = &bench_lpm_trie_map_argp, + .validate = lpm_delete_validate, + .setup = lpm_delete_setup, + .producer_thread = lpm_producer, + .measure = lpm_measure, + .report_progress = ops_report_progress, + .report_final = ops_report_final, +}; + +const struct bench bench_lpm_trie_free = { + .name = "lpm-trie-free", + .argp = &bench_lpm_trie_map_argp, + .validate = lpm_free_validate, + .setup = lpm_free_setup, + .producer_thread = lpm_free_producer, + .measure = lpm_measure, + .report_progress = free_ops_report_progress, + .report_final = free_ops_report_final, +}; 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..1a138e21e156 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/lpm_trie_bench.c @@ -0,0 +1,171 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2025 Cloudflare */ + +#include <vmlinux.h> +#include <bpf/bpf_tracing.h> +#include <bpf/bpf_helpers.h> +#include <bpf/bpf_core_read.h> +#include "bpf_misc.h" + +#define BPF_OBJ_NAME_LEN 16U +#define MAX_ENTRIES 100000000 +#define NR_LOOPS 10000 + +struct trie_key { + __u32 prefixlen; + __u32 data; +}; + +char _license[] SEC("license") = "GPL"; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 512); + __type(key, struct bpf_map *); + __type(value, __u64); +} latency_free_start SEC(".maps"); + +/* Filled by userspace. See fill_map() in bench_lpm_trie_map.c */ +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_map SEC(".maps"); + +long hits; +long duration_ns; + +/* Configured from userspace */ +__u32 nr_entries; +__u32 prefixlen; +__u8 op; + +SEC("fentry/bpf_map_free_deferred") +int BPF_PROG(trie_free_entry, struct work_struct *work) +{ + struct bpf_map *map = container_of(work, struct bpf_map, work); + const char *name; + u32 map_type; + __u64 val; + + map_type = BPF_CORE_READ(map, map_type); + if (map_type != BPF_MAP_TYPE_LPM_TRIE) + return 0; + + /* + * Ideally we'd have access to the map ID but that's already + * freed before we enter trie_free(). + */ + name = BPF_CORE_READ(map, name); + if (bpf_strncmp(name, BPF_OBJ_NAME_LEN, "trie_free_map")) + return 0; + + val = bpf_ktime_get_ns(); + bpf_map_update_elem(&latency_free_start, &map, &val, BPF_ANY); + + return 0; +} + +SEC("fexit/bpf_map_free_deferred") +int BPF_PROG(trie_free_exit, struct work_struct *work) +{ + struct bpf_map *map = container_of(work, struct bpf_map, work); + __u64 *val; + + val = bpf_map_lookup_elem(&latency_free_start, &map); + if (val) { + __sync_add_and_fetch(&duration_ns, bpf_ktime_get_ns() - *val); + __sync_add_and_fetch(&hits, 1); + bpf_map_delete_elem(&latency_free_start, &map); + } + + return 0; +} + +static void gen_random_key(struct trie_key *key) +{ + key->prefixlen = prefixlen; + key->data = bpf_get_prandom_u32() % nr_entries; +} + +static int lookup(__u32 index, __u32 *unused) +{ + struct trie_key key; + + gen_random_key(&key); + bpf_map_lookup_elem(&trie_map, &key); + return 0; +} + +static int update(__u32 index, __u32 *unused) +{ + struct trie_key key; + u32 val = bpf_get_prandom_u32(); + + gen_random_key(&key); + bpf_map_update_elem(&trie_map, &key, &val, BPF_EXIST); + return 0; +} + +static __u32 deleted_entries; + +static int delete (__u32 index, bool *need_refill) +{ + struct trie_key key = { + .data = deleted_entries, + .prefixlen = prefixlen, + }; + + bpf_map_delete_elem(&trie_map, &key); + + /* Do we need to refill the map? */ + if (++deleted_entries == nr_entries) { + /* + * Atomicity isn't required because DELETE only supports + * one producer running concurrently. What we need is a + * way to track how many entries have been deleted from + * the trie between consecutive invocations of the BPF + * prog because a single bpf_loop() call might not + * delete all entries, e.g. when NR_LOOPS < nr_entries. + */ + deleted_entries = 0; + *need_refill = true; + return 1; + } + + return 0; +} + +SEC("xdp") +int BPF_PROG(run_bench) +{ + bool need_refill = false; + u64 start, delta; + int loops; + + start = bpf_ktime_get_ns(); + + switch (op) { + case 1: + loops = bpf_loop(NR_LOOPS, lookup, NULL, 0); + break; + case 2: + loops = bpf_loop(NR_LOOPS, update, NULL, 0); + break; + case 3: + loops = bpf_loop(NR_LOOPS, delete, &need_refill, 0); + break; + default: + bpf_printk("invalid benchmark operation\n"); + return -1; + } + + delta = bpf_ktime_get_ns() - start; + + __sync_add_and_fetch(&duration_ns, delta); + __sync_add_and_fetch(&hits, loops); + + return need_refill; +} diff --git a/tools/testing/selftests/bpf/progs/lpm_trie_map.c b/tools/testing/selftests/bpf/progs/lpm_trie_map.c new file mode 100644 index 000000000000..2ab43e2cd6c6 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/lpm_trie_map.c @@ -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"); -- 2.34.1

5 months, 1 week

1
0
0 0

[PATCH nf-next v4 0/2] Add IPIP flowtable SW acceleratio

by Lorenzo Bianconi

Introduce SW acceleration for IPIP tunnels in the netfilter flowtable infrastructure. --- Changes in v4: - Use the hash value of the saddr, daddr and protocol of outer IP header as encapsulation id. - Link to v3: https://lore.kernel.org/r/20250703-nf-flowtable-ipip-v3-0-880afd319b9f@kern… Changes in v3: - Add outer IP header sanity checks - target nf-next tree instead of net-next - Link to v2: https://lore.kernel.org/r/20250627-nf-flowtable-ipip-v2-0-c713003ce75b@kern… Changes in v2: - Introduce IPIP flowtable selftest - Link to v1: https://lore.kernel.org/r/20250623-nf-flowtable-ipip-v1-1-2853596e3941@kern… --- Lorenzo Bianconi (2): net: netfilter: Add IPIP flowtable SW acceleration selftests: netfilter: nft_flowtable.sh: Add IPIP flowtable selftest include/linux/netdevice.h | 1 + net/ipv4/ipip.c | 25 +++++++++++ net/netfilter/nf_flow_table_ip.c | 48 +++++++++++++++++++++- net/netfilter/nft_flow_offload.c | 1 + .../selftests/net/netfilter/nft_flowtable.sh | 40 ++++++++++++++++++ 5 files changed, 113 insertions(+), 2 deletions(-) --- base-commit: d61f6cb6f6ef3c70d2ccc0d9c85c508cb8017da9 change-id: 20250623-nf-flowtable-ipip-1b3d7b08d067 Best regards, -- Lorenzo Bianconi <lorenzo(a)kernel.org>

5 months, 1 week

2
7
0 0

[PATCH v2 0/2] rust: minor idiomatic fixes to doctest generator

by Tamir Duberstein

Please see individual commit messages. Signed-off-by: Tamir Duberstein <tamird(a)gmail.com> --- Changes in v2: - rustfmt. - Alice's RB. - Add second patch to emit information in panic rather than separately to stderr. - Link to v1: https://lore.kernel.org/r/20250527-idiomatic-match-slice-v1-1-34b0b1d1d58c@… --- Tamir Duberstein (2): rust: replace length checks with match rust: emit path candidates in panic message scripts/rustdoc_test_gen.rs | 33 +++++++++++++++++---------------- 1 file changed, 17 insertions(+), 16 deletions(-) --- base-commit: 1ce98bb2bb30713ec4374ef11ead0d7d3e856766 change-id: 20250527-idiomatic-match-slice-26a79d100e4d Best regards, -- Tamir Duberstein <tamird(a)gmail.com>

5 months, 1 week

2
8
0 0

2025

2024

2023

2022

2021

2020

2019

2018

2017

Linux-kselftest-mirror