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

[Leon Hwang <leon.hwang@linux.dev>]

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