Skip to content

RFC bpf: Optimize string kfuncs

Leon Hwang bpf linux-kselftest lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest6 patches 2 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/6bpf: Optimize string scan kfuncskernel/bpf/helpers.c+141 -392 replies
2/6bpf: Optimize string comparison kfuncskernel/bpf/helpers.c+57 -150 replies
3/6bpf: Optimize string span kfuncskernel/bpf/helpers.c+121 -540 replies
4/6bpf: Optimize string substring kfuncskernel/bpf/helpers.c+111 -310 replies
5/6selftests/bpf: Exercise word-at-a-time string kfuncstools/testing/selftests/bpf/progs/string_kfuncs_failure1.c tools/testing/selftests/bpf/progs/string_kfuncs_success.c+144 -00 replies
6/6selftests/bpf: Benchmark string kfuncstools/testing/selftests/bpf/Makefile tools/testing/selftests/bpf/bench.c tools/testing/selftests/bpf/bench.h +3 more+389 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [RFC PATCH bpf-next 0/6] bpf: Optimize string kfuncs

My friend Gray reported that bpf_strnstr() kfunc has poorer performance than his SWAR(SIMD Within A Register)-alike pure-bpf implementation [1].

I built his microbench, and ran it on a 16-cores 16GiB QEMU VM:

taskset -c 1 ./bpf_swar_benchmark
BPF HTTP Host search benchmark
kernel=7.2.0-rc4-00662-g771a7ae30d95 arch=amd64 repeat=100000 trials=9 warmup=1000

Scenario Bytes Byte ns/op SWAR ns/op Kfunc ns/op SWAR speedup Kfunc speedup

first           64        492.0        246.0         345.0        2.00x        1.43x
middle         512       2761.0        780.0        1193.0        3.54x        2.31x
late          1536      11801.0       2829.0        4469.0        4.17x        2.64x
absent        2048      19874.0       4557.0        7389.0        4.36x        2.69x

The result verified his report.

Then, with LLM assistance, I optimized all string kfuncs with word-at-a-time, include bpf_strnstr(). And, re-ran the microbench:

taskset -c 1 ./bpf_swar_benchmark
BPF HTTP Host search benchmark
kernel=7.2.0-rc4-00667-g707cce56283d arch=amd64 repeat=100000 trials=9 warmup=1000

Scenario Bytes Byte ns/op SWAR ns/op Kfunc ns/op SWAR speedup Kfunc speedup

first           64        487.0        245.0         261.0        1.99x        1.87x
middle         512       2827.0        781.0         352.0        3.62x        8.03x
late          1536      12127.0       2822.0         708.0        4.30x       17.13x
absent        2048      20463.0       4548.0         982.0        4.50x       20.84x

The optimized bpf_strnstr() kfunc was 10x faster than the original bpf_strnstr() kfunc.

Next, I (LLM) implemented the benchmarks for the 4 kinds of string kfuncs:

cd tools/testing/selftests/bpf
bash ./benchs/run_bench_bpf_str_kfuncs.sh
BPF string kfunc benchmark comparison
baseline kernel=7.2.0-rc4-00661-g4748a67f7111 arch=x86_64 repeat=100000 trials=9 warmup=1000 current kernel=7.2.0-rc4-00671-g239632cc49ee arch=x86_64 repeat=100000 trials=9 warmup=1000

scan (bpf_strnchr)
Scenario Bytes Baseline ns/op Current ns/op Speedup

first        64           174.0          179.0     0.97x
middle      512           489.0          241.0     2.03x
late       1536          1706.0          506.0     3.37x
absent     2048          2781.0          727.0     3.83x

comparison (bpf_strcmp)
Scenario Bytes Baseline ns/op Current ns/op Speedup

first        64           186.0          189.0     0.98x
middle      512           614.0          238.0     2.58x
late       1536          2234.0          458.0     4.88x
equal      2048          3663.0          634.0     5.78x

span (bpf_strcspn)
Scenario Bytes Baseline ns/op Current ns/op Speedup

first        64           179.0          195.0     0.92x
middle      512          1047.0          266.0     3.94x
late       1536          4489.0          482.0     9.31x
absent     2048          7468.0          661.0    11.30x

substring (bpf_strnstr)
Scenario Bytes Baseline ns/op Current ns/op Speedup

first        64           277.0          218.0     1.27x
middle      512          1115.0          296.0     3.77x
late       1536          4427.0          613.0     7.22x
absent     2048          7261.0          854.0     8.50x

The optimized kfuncs win most of the benchmarks.

For the implementation details, pls look into the first 4 patches.

The checkpatch.pl reports
"WARNING: Macros with flow control statements should be avoided" about those two macros. I will address it in the next revision.

Links:
[1] https://github.com/jschwinger233/bpf_swar_benchmark

Leon Hwang (6):
bpf: Optimize string scan kfuncs
bpf: Optimize string comparison kfuncs
bpf: Optimize string span kfuncs
bpf: Optimize string substring kfuncs selftests/bpf: Exercise word-at-a-time string kfuncs selftests/bpf: Benchmark string kfuncs

 kernel/bpf/helpers.c                          | 557 +++++++++++++-----
 tools/testing/selftests/bpf/Makefile          |   2 +
 tools/testing/selftests/bpf/bench.c           |  11 +
 tools/testing/selftests/bpf/bench.h           |   2 +
 .../bpf/benchs/bench_bpf_str_kfuncs.c         | 228 +++++++
 .../bpf/benchs/run_bench_bpf_str_kfuncs.sh    |  98 +++
 .../bpf/progs/bpf_str_kfuncs_bench.c          |  48 ++
 .../bpf/progs/string_kfuncs_failure1.c        |  58 ++
 .../bpf/progs/string_kfuncs_success.c         |  86 +++
 9 files changed, 957 insertions(+), 133 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_str_kfuncs.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_str_kfuncs.sh
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_str_kfuncs_bench.c

--
2.55.0