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

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

[Leon Hwang]

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

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

[Leon Hwang]

Use aligned nofault word loads for the strchr, strrchr, and strlen
kfunc families. Align once, hoist the full-word boundary, and use
word-at-a-time masks to skip irrelevant words or locate the first
matching or NUL byte.

Factor the common unaligned-byte, aligned-word, and byte-fallback
plumbing into an expansion macro. Keep algorithm-specific actions expanded
at each call site.

Allow the shared finder to match both ASCII case variants so the
case-insensitive substring kfuncs can use the same word-at-a-time scan.

If a word load faults, retry from the same address byte-at-a-time. Keep
the byte path under KMSAN to avoid reading uninitialized storage beyond
the terminator, and preserve the existing limits and error semantics.

Assisted-by: Codex:gpt-5.6-sol
Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 kernel/bpf/helpers.c | 180 +++++++++++++++++++++++++++++++++----------
 1 file changed, 141 insertions(+), 39 deletions(-)

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 88b38db47de9..36075c683166 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -30,6 +30,8 @@
 #include <linux/irq_work.h>
 #include <linux/buildid.h>
 
+#include <asm/word-at-a-time.h>
+
 #include "../../lib/kstrtox.h"
 
 /* If kernel subsystem is allowing eBPF programs to call this function,
@@ -3727,6 +3729,95 @@ __bpf_kfunc void __bpf_trap(void)
  * __get_kernel_nofault instead of plain dereference to make them safe.
  */
 
+/* Abstract the common unaligned-byte, aligned-word, and byte-fallback scan. */
+#define bpf_str_for_each_word(s, limit, pos, word, byte, byte_label,	\
+			      byte_action, word_action, err_label)	\
+do {									\
+	__label__ byte_label;						\
+	size_t __word_end;						\
+									\
+	if (IS_ENABLED(CONFIG_KMSAN))					\
+		goto byte_label;					\
+									\
+	for (; (pos) < (limit) &&					\
+	       !IS_ALIGNED((unsigned long)((s) + (pos)), sizeof(word));	\
+	     (pos)++) {							\
+		__get_kernel_nofault(&(byte), (s) + (pos),		\
+				     unsigned char, err_label);		\
+		byte_action;						\
+	}								\
+									\
+	__word_end = (pos) + round_down((limit) - (pos), sizeof(word));	\
+	for (; (pos) < __word_end; (pos) += sizeof(word)) {		\
+		__get_kernel_nofault(&(word), (s) + (pos),		\
+				     unsigned long, byte_label);	\
+		word_action;						\
+	}								\
+									\
+byte_label:								\
+	for (; (pos) < (limit); (pos)++) {				\
+		__get_kernel_nofault(&(byte), (s) + (pos),		\
+				     unsigned char, err_label);		\
+		byte_action;						\
+	}								\
+} while (0)
+
+static __always_inline int bpf_str_find(const char *s, size_t limit, unsigned char c,
+					bool ignore_case, bool nul_is_match)
+{
+	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
+	const unsigned char match_c = ignore_case ? tolower(c) : c;
+	const unsigned char alt_c = ignore_case && islower(match_c) ?
+				    toupper(match_c) : match_c;
+	const unsigned long repeated_c = REPEAT_BYTE(match_c);
+	const unsigned long repeated_alt = REPEAT_BYTE(alt_c);
+	unsigned long word, zero_data, char_data, alt_data;
+	unsigned long zero_at, char_at, alt_at;
+	const bool has_alt = alt_c != match_c;
+	unsigned char sc;
+	size_t pos = 0;
+
+	bpf_str_for_each_word(s, limit, pos, word, sc, byte_at_a_time, ({
+		if (sc == match_c || (has_alt && sc == alt_c))
+			return pos;
+		if (sc == '\0')
+			return nul_is_match ? pos : -ENOENT;
+	}), ({
+		zero_at = has_zero(word, &zero_data, &constants);
+		char_at = has_zero(word ^ repeated_c, &char_data, &constants);
+		alt_at = has_alt ? has_zero(word ^ repeated_alt, &alt_data, &constants) : 0;
+		if (!zero_at && !char_at && !alt_at)
+			continue;
+
+		if (zero_at) {
+			zero_data = prep_zero_mask(word, zero_data, &constants);
+			zero_at = find_zero(create_zero_mask(zero_data));
+		} else {
+			zero_at = sizeof(word);
+		}
+		if (char_at) {
+			char_data = prep_zero_mask(word ^ repeated_c, char_data, &constants);
+			char_at = find_zero(create_zero_mask(char_data));
+		} else {
+			char_at = sizeof(word);
+		}
+		if (alt_at) {
+			alt_data = prep_zero_mask(word ^ repeated_alt, alt_data, &constants);
+			alt_at = find_zero(create_zero_mask(alt_data));
+			char_at = min(char_at, alt_at);
+		}
+
+		if (char_at <= zero_at)
+			return pos + char_at;
+		return nul_is_match ? pos + zero_at : -ENOENT;
+	}), err_out);
+
+	return pos == XATTR_SIZE_MAX ? -E2BIG : -ENOENT;
+
+err_out:
+	return -EFAULT;
+}
+
 static int __bpf_strncasecmp(const char *s1, const char *s2, bool ignore_case, size_t len)
 {
 	char c1, c2;
@@ -3830,24 +3921,14 @@ __bpf_kfunc int bpf_strncasecmp(const char *s1__ign, const char *s2__ign, size_t
  */
 __bpf_kfunc int bpf_strnchr(const char *s__ign, size_t count, char c)
 {
-	char sc;
-	int i;
+	size_t limit;
 
 	if (!copy_from_kernel_nofault_allowed(s__ign, 1))
 		return -ERANGE;
 
+	limit = min_t(size_t, count, XATTR_SIZE_MAX);
 	guard(pagefault)();
-	for (i = 0; i < count && i < XATTR_SIZE_MAX; i++) {
-		__get_kernel_nofault(&sc, s__ign, char, err_out);
-		if (sc == c)
-			return i;
-		if (sc == '\0')
-			return -ENOENT;
-		s__ign++;
-	}
-	return i == XATTR_SIZE_MAX ? -E2BIG : -ENOENT;
-err_out:
-	return -EFAULT;
+	return bpf_str_find(s__ign, limit, (unsigned char)c, false, false);
 }
 
 /**
@@ -3884,22 +3965,11 @@ __bpf_kfunc int bpf_strchr(const char *s__ign, char c)
  */
 __bpf_kfunc int bpf_strchrnul(const char *s__ign, char c)
 {
-	char sc;
-	int i;
-
 	if (!copy_from_kernel_nofault_allowed(s__ign, 1))
 		return -ERANGE;
 
 	guard(pagefault)();
-	for (i = 0; i < XATTR_SIZE_MAX; i++) {
-		__get_kernel_nofault(&sc, s__ign, char, err_out);
-		if (sc == '\0' || sc == c)
-			return i;
-		s__ign++;
-	}
-	return -E2BIG;
-err_out:
-	return -EFAULT;
+	return bpf_str_find(s__ign, XATTR_SIZE_MAX, (unsigned char)c, false, true);
 }
 
 /**
@@ -3916,22 +3986,44 @@ __bpf_kfunc int bpf_strchrnul(const char *s__ign, char c)
  */
 __bpf_kfunc int bpf_strrchr(const char *s__ign, int c)
 {
+	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
+	const unsigned char uc = (unsigned char)(char)c;
+	const unsigned long repeated_c = REPEAT_BYTE(uc);
+	const bool char_matches = c == (char)c;
+	unsigned char byte, *bytes;
+	unsigned long word, data;
+	size_t pos = 0, i;
 	char sc;
-	int i, last = -ENOENT;
+	int last = -ENOENT;
 
 	if (!copy_from_kernel_nofault_allowed(s__ign, 1))
 		return -ERANGE;
 
 	guard(pagefault)();
-	for (i = 0; i < XATTR_SIZE_MAX; i++) {
-		__get_kernel_nofault(&sc, s__ign, char, err_out);
+
+	bpf_str_for_each_word(s__ign, XATTR_SIZE_MAX, pos, word, byte, byte_at_a_time, ({
+		sc = byte;
 		if (sc == c)
-			last = i;
+			last = pos;
 		if (sc == '\0')
 			return last;
-		s__ign++;
-	}
+	}), ({
+		if (!has_zero(word, &data, &constants) &&
+		    (!char_matches || !has_zero(word ^ repeated_c, &data, &constants)))
+			continue;
+
+		bytes = (unsigned char *)&word;
+		for (i = 0; i < sizeof(word); i++) {
+			sc = bytes[i];
+			if (sc == c)
+				last = pos + i;
+			if (sc == '\0')
+				return last;
+		}
+	}), err_out);
+
 	return -E2BIG;
+
 err_out:
 	return -EFAULT;
 }
@@ -3949,20 +4041,30 @@ __bpf_kfunc int bpf_strrchr(const char *s__ign, int c)
  */
 __bpf_kfunc int bpf_strnlen(const char *s__ign, size_t count)
 {
-	char c;
-	int i;
+	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
+	unsigned long word, data;
+	size_t limit, pos = 0;
+	unsigned char c;
 
 	if (!copy_from_kernel_nofault_allowed(s__ign, 1))
 		return -ERANGE;
 
+	limit = min_t(size_t, count, XATTR_SIZE_MAX);
 	guard(pagefault)();
-	for (i = 0; i < count && i < XATTR_SIZE_MAX; i++) {
-		__get_kernel_nofault(&c, s__ign, char, err_out);
+
+	bpf_str_for_each_word(s__ign, limit, pos, word, c, byte_at_a_time, ({
 		if (c == '\0')
-			return i;
-		s__ign++;
-	}
-	return i == XATTR_SIZE_MAX ? -E2BIG : i;
+			return pos;
+	}), ({
+		if (!has_zero(word, &data, &constants))
+			continue;
+
+		data = prep_zero_mask(word, data, &constants);
+		return pos + find_zero(create_zero_mask(data));
+	}), err_out);
+
+	return pos == XATTR_SIZE_MAX ? -E2BIG : pos;
+
 err_out:
 	return -EFAULT;
 }
-- 
2.55.0

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

[Leon Hwang]

Use aligned nofault word loads for the strcmp and strcasecmp kfunc
families when both operands have the same relative alignment. Skip
identical NUL-free words directly and inspect locally loaded bytes only
for mismatches and case folding.

Reuse the string scan expansion macro for alignment, word bounds, and
byte fallback while keeping the comparison actions expanded at the call
site.

Keep byte-at-a-time access for differently aligned operands, KMSAN, and
word-load faults. This preserves comparison order and the existing error
semantics.

Assisted-by: Codex:gpt-5.6-sol
Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 kernel/bpf/helpers.c | 72 +++++++++++++++++++++++++++++++++++---------
 1 file changed, 57 insertions(+), 15 deletions(-)

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 36075c683166..406aca61789a 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -3818,32 +3818,74 @@ static __always_inline int bpf_str_find(const char *s, size_t limit, unsigned ch
 	return -EFAULT;
 }
 
+static __always_inline bool
+bpf_str_cmp_byte(unsigned char byte1, unsigned char byte2, bool ignore_case, int *ret)
+{
+	char c1 = byte1, c2 = byte2;
+
+	if (ignore_case) {
+		c1 = tolower(c1);
+		c2 = tolower(c2);
+	}
+	if (c1 != c2) {
+		*ret = c1 < c2 ? -1 : 1;
+		return true;
+	}
+	if (c1 == '\0') {
+		*ret = 0;
+		return true;
+	}
+	return false;
+}
+
 static int __bpf_strncasecmp(const char *s1, const char *s2, bool ignore_case, size_t len)
 {
-	char c1, c2;
-	int i;
+	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
+	unsigned char byte1, byte2, *bytes1, *bytes2;
+	unsigned long word1, word2, data;
+	size_t limit, pos = 0, i;
+	int ret;
 
 	if (!copy_from_kernel_nofault_allowed(s1, 1) ||
 	    !copy_from_kernel_nofault_allowed(s2, 1)) {
 		return -ERANGE;
 	}
 
+	limit = min_t(size_t, len, XATTR_SIZE_MAX);
 	guard(pagefault)();
-	for (i = 0; i < len && i < XATTR_SIZE_MAX; i++) {
-		__get_kernel_nofault(&c1, s1, char, err_out);
-		__get_kernel_nofault(&c2, s2, char, err_out);
-		if (ignore_case) {
-			c1 = tolower(c1);
-			c2 = tolower(c2);
+
+	if (!IS_ALIGNED((unsigned long)s1 ^ (unsigned long)s2, sizeof(word1))) {
+		for (; pos < limit; pos++) {
+			__get_kernel_nofault(&byte1, s1 + pos, unsigned char, err_out);
+			__get_kernel_nofault(&byte2, s2 + pos, unsigned char, err_out);
+			if (bpf_str_cmp_byte(byte1, byte2, ignore_case, &ret))
+				return ret;
 		}
-		if (c1 != c2)
-			return c1 < c2 ? -1 : 1;
-		if (c1 == '\0')
-			return 0;
-		s1++;
-		s2++;
+		return pos == XATTR_SIZE_MAX ? -E2BIG : 0;
 	}
-	return i == XATTR_SIZE_MAX ? -E2BIG : 0;
+
+	bpf_str_for_each_word(s1, limit, pos, word1, byte1, byte_at_a_time, ({
+		__get_kernel_nofault(&byte2, s2 + pos, unsigned char, err_out);
+		if (bpf_str_cmp_byte(byte1, byte2, ignore_case, &ret))
+			return ret;
+	}), ({
+		__get_kernel_nofault(&word2, s2 + pos, unsigned long, byte_at_a_time);
+		if (word1 == word2) {
+			if (has_zero(word1, &data, &constants))
+				return 0;
+			continue;
+		}
+
+		bytes1 = (unsigned char *)&word1;
+		bytes2 = (unsigned char *)&word2;
+		for (i = 0; i < sizeof(word1); i++) {
+			if (bpf_str_cmp_byte(bytes1[i], bytes2[i], ignore_case, &ret))
+				return ret;
+		}
+	}), err_out);
+
+	return pos == XATTR_SIZE_MAX ? -E2BIG : 0;
+
 err_out:
 	return -EFAULT;
 }
-- 
2.55.0

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

[Leon Hwang]

Share a direct implementation between bpf_strspn() and bpf_strcspn().
Read the source string a word at a time and cache set membership in a
lazily populated 256-bit bitmap, so each required accept or reject byte
is nofault-loaded at most once.

Use the word-at-a-time character finder after discovering a singleton
reject set. This avoids inspecting individual source bytes for common
bpf_strcspn() delimiters.

Keep set loading lazy, retry from the same byte after a word-load fault,
and retain the existing NUL, EFAULT, and E2BIG ordering.

Assisted-by: Codex:gpt-5.6-sol
Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 kernel/bpf/helpers.c | 175 ++++++++++++++++++++++++++++++-------------
 1 file changed, 121 insertions(+), 54 deletions(-)

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 406aca61789a..af29acc90245 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -4126,6 +4126,125 @@ __bpf_kfunc int bpf_strlen(const char *s__ign)
 	return bpf_strnlen(s__ign, XATTR_SIZE_MAX);
 }
 
+static __always_inline bool
+bpf_str_set_contains(const unsigned long *set_bits, unsigned char c)
+{
+	return set_bits[c / BITS_PER_LONG] & BIT(c % BITS_PER_LONG);
+}
+
+static __always_inline int
+bpf_str_set_lookup(const char *set, unsigned long *set_bits, size_t *set_pos, bool *set_complete,
+		   unsigned char *set_first, unsigned char c)
+{
+	unsigned char set_c;
+
+	if (bpf_str_set_contains(set_bits, c))
+		return 1;
+	if (*set_complete)
+		return 0;
+
+	while (*set_pos < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&set_c, set + *set_pos, unsigned char, err_out);
+		if (set_c == '\0') {
+			*set_complete = true;
+			return 0;
+		}
+
+		if (*set_pos == 0)
+			*set_first = set_c;
+		set_bits[set_c / BITS_PER_LONG] |= BIT(set_c % BITS_PER_LONG);
+		(*set_pos)++;
+		if (set_c == c)
+			return 1;
+	}
+	return -E2BIG;
+
+err_out:
+	return -EFAULT;
+}
+
+static __always_inline int
+bpf_strcspn_single(const char *s, size_t pos, unsigned char reject)
+{
+	int ret;
+
+	ret = bpf_str_find(s + pos, XATTR_SIZE_MAX - pos, reject, false, true);
+	if (ret >= 0)
+		return pos + ret;
+	return ret == -ENOENT ? -E2BIG : ret;
+}
+
+static int __bpf_strspn(const char *s, const char *set, bool reject)
+{
+	unsigned long set_bits[256 / BITS_PER_LONG] = {};
+	size_t pos = 0, word_end, i, set_pos = 0;
+	unsigned char c, set_first = 0, *bytes;
+	bool set_complete = false;
+	unsigned long word;
+	int ret;
+
+	if (!copy_from_kernel_nofault_allowed(s, 1) ||
+	    !copy_from_kernel_nofault_allowed(set, 1))
+		return -ERANGE;
+
+	guard(pagefault)();
+
+	if (IS_ENABLED(CONFIG_KMSAN))
+		goto byte_at_a_time;
+
+	while (!IS_ALIGNED((unsigned long)(s + pos), sizeof(word))) {
+		__get_kernel_nofault(&c, s + pos, unsigned char, err_out);
+		if (c == '\0')
+			return pos;
+		ret = bpf_str_set_lookup(set, set_bits, &set_pos, &set_complete, &set_first, c);
+		if (ret < 0)
+			return ret;
+		if (ret == reject)
+			return pos;
+		pos++;
+		if (reject && set_complete && set_pos == 1)
+			return bpf_strcspn_single(s, pos, set_first);
+	}
+
+	word_end = pos + round_down(XATTR_SIZE_MAX - pos, sizeof(word));
+	while (pos < word_end) {
+		__get_kernel_nofault(&word, s + pos, unsigned long, byte_at_a_time);
+		bytes = (unsigned char *)&word;
+		for (i = 0; i < sizeof(word); i++) {
+			c = bytes[i];
+			if (c == '\0')
+				return pos + i;
+			ret = bpf_str_set_lookup(set, set_bits, &set_pos, &set_complete,
+						 &set_first, c);
+			if (ret < 0)
+				return ret;
+			if (ret == reject)
+				return pos + i;
+			if (reject && set_complete && set_pos == 1)
+				return bpf_strcspn_single(s, pos + i + 1, set_first);
+		}
+		pos += sizeof(word);
+	}
+
+byte_at_a_time:
+	for (; pos < XATTR_SIZE_MAX; pos++) {
+		__get_kernel_nofault(&c, s + pos, unsigned char, err_out);
+		if (c == '\0')
+			return pos;
+		ret = bpf_str_set_lookup(set, set_bits, &set_pos, &set_complete, &set_first, c);
+		if (ret < 0)
+			return ret;
+		if (ret == reject)
+			return pos;
+		if (reject && set_complete && set_pos == 1)
+			return bpf_strcspn_single(s, pos + 1, set_first);
+	}
+	return -E2BIG;
+
+err_out:
+	return -EFAULT;
+}
+
 /**
  * bpf_strspn - Calculate the length of the initial substring of @s__ign which
  *              only contains letters in @accept__ign
@@ -4141,33 +4260,7 @@ __bpf_kfunc int bpf_strlen(const char *s__ign)
  */
 __bpf_kfunc int bpf_strspn(const char *s__ign, const char *accept__ign)
 {
-	char cs, ca;
-	int i, j;
-
-	if (!copy_from_kernel_nofault_allowed(s__ign, 1) ||
-	    !copy_from_kernel_nofault_allowed(accept__ign, 1)) {
-		return -ERANGE;
-	}
-
-	guard(pagefault)();
-	for (i = 0; i < XATTR_SIZE_MAX; i++) {
-		__get_kernel_nofault(&cs, s__ign, char, err_out);
-		if (cs == '\0')
-			return i;
-		for (j = 0; j < XATTR_SIZE_MAX; j++) {
-			__get_kernel_nofault(&ca, accept__ign + j, char, err_out);
-			if (cs == ca || ca == '\0')
-				break;
-		}
-		if (j == XATTR_SIZE_MAX)
-			return -E2BIG;
-		if (ca == '\0')
-			return i;
-		s__ign++;
-	}
-	return -E2BIG;
-err_out:
-	return -EFAULT;
+	return __bpf_strspn(s__ign, accept__ign, false);
 }
 
 /**
@@ -4185,33 +4278,7 @@ __bpf_kfunc int bpf_strspn(const char *s__ign, const char *accept__ign)
  */
 __bpf_kfunc int bpf_strcspn(const char *s__ign, const char *reject__ign)
 {
-	char cs, cr;
-	int i, j;
-
-	if (!copy_from_kernel_nofault_allowed(s__ign, 1) ||
-	    !copy_from_kernel_nofault_allowed(reject__ign, 1)) {
-		return -ERANGE;
-	}
-
-	guard(pagefault)();
-	for (i = 0; i < XATTR_SIZE_MAX; i++) {
-		__get_kernel_nofault(&cs, s__ign, char, err_out);
-		if (cs == '\0')
-			return i;
-		for (j = 0; j < XATTR_SIZE_MAX; j++) {
-			__get_kernel_nofault(&cr, reject__ign + j, char, err_out);
-			if (cs == cr || cr == '\0')
-				break;
-		}
-		if (j == XATTR_SIZE_MAX)
-			return -E2BIG;
-		if (cr != '\0')
-			return i;
-		s__ign++;
-	}
-	return -E2BIG;
-err_out:
-	return -EFAULT;
+	return __bpf_strspn(s__ign, reject__ign, true);
 }
 
 static int __bpf_strnstr(const char *s1, const char *s2, size_t len,
-- 
2.55.0

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

[Leon Hwang]

Use the word-at-a-time character finder to skip haystack regions which
cannot begin a match. For case-insensitive searches, check both ASCII
case variants of the first needle byte.

At each candidate, use a direct fault-safe word matcher. When both
strings have the same relative alignment, skip equal words and inspect
locally loaded bytes only for mismatches and case folding.

Keep needle-first access, fall back at the same byte after a word-load
fault, and retain the extra needle-byte check at the search limit so
fault and boundary behavior remain unchanged.

Assisted-by: Codex:gpt-5.6-sol
Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 kernel/bpf/helpers.c | 142 +++++++++++++++++++++++++++++++++----------
 1 file changed, 111 insertions(+), 31 deletions(-)

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index af29acc90245..93d5fa409cd7 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -4281,11 +4281,90 @@ __bpf_kfunc int bpf_strcspn(const char *s__ign, const char *reject__ign)
 	return __bpf_strspn(s__ign, reject__ign, true);
 }
 
-static int __bpf_strnstr(const char *s1, const char *s2, size_t len,
-			 bool ignore_case)
+#define bpf_str_match_byte(byte1, byte2, ignore_case)	\
+do {							\
+	char __c1 = (byte1);				\
+	char __c2 = (byte2);				\
+							\
+	if (ignore_case) {				\
+		__c1 = tolower(__c1);			\
+		__c2 = tolower(__c2);			\
+	}						\
+	if (__c1 == '\0')				\
+		return -ENOENT;				\
+	if (__c1 != __c2)				\
+		return 0;				\
+} while (0)
+
+static __always_inline int
+bpf_str_match_at(const char *s1, const char *s2, size_t limit, bool ignore_case)
 {
-	char c1, c2;
-	int i, j;
+	const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS;
+	unsigned char byte1, byte2, *bytes1, *bytes2;
+	unsigned long word1, word2, data;
+	size_t pos = 0, word_end, i;
+
+	if (IS_ENABLED(CONFIG_KMSAN) ||
+	    !IS_ALIGNED((unsigned long)s1 ^ (unsigned long)s2, sizeof(word1)))
+		goto byte_at_a_time;
+
+	while (pos < limit && !IS_ALIGNED((unsigned long)(s1 + pos), sizeof(word1))) {
+		__get_kernel_nofault(&byte2, s2 + pos, unsigned char, err_out);
+		if (byte2 == '\0')
+			return 1;
+		__get_kernel_nofault(&byte1, s1 + pos, unsigned char, err_out);
+		bpf_str_match_byte(byte1, byte2, ignore_case);
+		pos++;
+	}
+
+	word_end = pos + round_down(limit - pos, sizeof(word1));
+	while (pos < word_end) {
+		__get_kernel_nofault(&word2, s2 + pos, unsigned long, byte_at_a_time);
+		if (has_zero(word2, &data, &constants))
+			goto byte_at_a_time;
+		__get_kernel_nofault(&word1, s1 + pos, unsigned long, byte_at_a_time);
+		if (word1 == word2) {
+			pos += sizeof(word1);
+			continue;
+		}
+
+		bytes1 = (unsigned char *)&word1;
+		bytes2 = (unsigned char *)&word2;
+		for (i = 0; i < sizeof(word1); i++)
+			bpf_str_match_byte(bytes1[i], bytes2[i], ignore_case);
+		pos += sizeof(word1);
+	}
+
+byte_at_a_time:
+	for (; pos < limit; pos++) {
+		__get_kernel_nofault(&byte2, s2 + pos, unsigned char, err_out);
+		if (byte2 == '\0')
+			return 1;
+		__get_kernel_nofault(&byte1, s1 + pos, unsigned char, err_out);
+		bpf_str_match_byte(byte1, byte2, ignore_case);
+	}
+
+	if (limit == XATTR_SIZE_MAX)
+		return -E2BIG;
+
+	/*
+	 * Read one extra byte from s2 to cover the case when it is a suffix
+	 * of the first limit bytes of s1.
+	 */
+	__get_kernel_nofault(&byte2, s2 + limit, unsigned char, err_out);
+	return byte2 == '\0' ? 1 : -ENOENT;
+
+err_out:
+	return -EFAULT;
+}
+
+#undef bpf_str_match_byte
+
+static int __bpf_strnstr(const char *s1, const char *s2, size_t len, bool ignore_case)
+{
+	unsigned char first, candidate;
+	size_t pos = 0, limit;
+	int ret, offset;
 
 	if (!copy_from_kernel_nofault_allowed(s1, 1) ||
 	    !copy_from_kernel_nofault_allowed(s2, 1)) {
@@ -4293,37 +4372,38 @@ static int __bpf_strnstr(const char *s1, const char *s2, size_t len,
 	}
 
 	guard(pagefault)();
-	for (i = 0; i < XATTR_SIZE_MAX; i++) {
-		for (j = 0; i + j <= len && j < XATTR_SIZE_MAX; j++) {
-			__get_kernel_nofault(&c2, s2 + j, char, err_out);
-			if (c2 == '\0')
-				return i;
-			/*
-			 * We allow reading an extra byte from s2 (note the
-			 * `i + j <= len` above) to cover the case when s2 is
-			 * a suffix of the first len chars of s1.
-			 */
-			if (i + j == len)
-				break;
-			__get_kernel_nofault(&c1, s1 + j, char, err_out);
-
-			if (ignore_case) {
-				c1 = tolower(c1);
-				c2 = tolower(c2);
-			}
+	__get_kernel_nofault(&first, s2, unsigned char, err_out);
+	if (first == '\0')
+		return 0;
 
-			if (c1 == '\0')
-				return -ENOENT;
-			if (c1 != c2)
-				break;
+	while (pos < XATTR_SIZE_MAX && pos < len) {
+		limit = min_t(size_t, len - pos, XATTR_SIZE_MAX - pos);
+		offset = bpf_str_find(s1 + pos, limit, first, ignore_case, true);
+		if (offset < 0) {
+			if (offset == -ENOENT && limit == XATTR_SIZE_MAX - pos)
+				return -E2BIG;
+			return offset;
 		}
-		if (j == XATTR_SIZE_MAX)
-			return -E2BIG;
-		if (i + j == len)
+		pos += offset;
+
+		/*
+		 * bpf_str_find() also returns the position of a terminating
+		 * NUL. Distinguish it from a first-character match.
+		 */
+		__get_kernel_nofault(&candidate, s1 + pos, unsigned char, err_out);
+		if (candidate == '\0')
 			return -ENOENT;
-		s1++;
+
+		limit = min_t(size_t, len - pos, XATTR_SIZE_MAX);
+		ret = bpf_str_match_at(s1 + pos, s2, limit, ignore_case);
+		if (ret > 0)
+			return pos;
+		if (ret < 0)
+			return ret;
+		pos++;
 	}
-	return -E2BIG;
+	return pos == XATTR_SIZE_MAX ? -E2BIG : -ENOENT;
+
 err_out:
 	return -EFAULT;
 }
-- 
2.55.0

[RFC PATCH bpf-next 5/6] selftests/bpf: Exercise word-at-a-time string kfuncs

[Leon Hwang]

Add functional coverage for aligned and unaligned strings across
the scan, comparison, span, and substring families. Cover matches and
mismatches beyond the first word as well as the length-limited substring
suffix rule.

Use aligned invalid kernel addresses to exercise a failed
word-sized nofault load and its byte-sized retry.

Assisted-by: Codex:gpt-5.6-sol
Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 .../bpf/progs/string_kfuncs_failure1.c        | 58 +++++++++++++
 .../bpf/progs/string_kfuncs_success.c         | 86 +++++++++++++++++++
 2 files changed, 144 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c b/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c
index bddc4e8579d2..05f93c7cd07c 100644
--- a/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c
+++ b/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c
@@ -8,6 +8,7 @@
 
 char *user_ptr = (char *)1;
 char *invalid_kern_ptr = (char *)-1;
+char *invalid_aligned_kern_ptr = (char *)-8;
 
 /*
  * When passing userspace pointers, the error code differs based on arch:
@@ -108,4 +109,61 @@ SEC("syscall") __retval(-EFAULT) int test_strnstr_pagefault2(void *ctx) { return
 SEC("syscall") __retval(-EFAULT) int test_strncasestr_pagefault1(void *ctx) { return bpf_strncasestr(invalid_kern_ptr, "hello", 1); }
 SEC("syscall") __retval(-EFAULT) int test_strncasestr_pagefault2(void *ctx) { return bpf_strncasestr("hello", invalid_kern_ptr, 1); }
 
+/* Exercise word-load faults and the byte retry at the same address. */
+SEC("syscall")
+__retval(-EFAULT)
+int test_strncasecmp_word_pagefault(void *ctx)
+{
+	return bpf_strncasecmp(invalid_aligned_kern_ptr, "12345678", 8);
+}
+
+SEC("syscall")
+__retval(-EFAULT)
+int test_strnchr_word_pagefault(void *ctx)
+{
+	return bpf_strnchr(invalid_aligned_kern_ptr, 8, 'a');
+}
+
+SEC("syscall")
+__retval(-EFAULT)
+int test_strrchr_word_pagefault(void *ctx)
+{
+	return bpf_strrchr(invalid_aligned_kern_ptr, 'a');
+}
+
+SEC("syscall")
+__retval(-EFAULT)
+int test_strnlen_word_pagefault(void *ctx)
+{
+	return bpf_strnlen(invalid_aligned_kern_ptr, 8);
+}
+
+SEC("syscall")
+__retval(-EFAULT)
+int test_strspn_word_pagefault(void *ctx)
+{
+	return bpf_strspn(invalid_aligned_kern_ptr, "a");
+}
+
+SEC("syscall")
+__retval(-EFAULT)
+int test_strspn_set_word_pagefault(void *ctx)
+{
+	return bpf_strspn("a", invalid_aligned_kern_ptr);
+}
+
+SEC("syscall")
+__retval(-EFAULT)
+int test_strnstr_word_pagefault1(void *ctx)
+{
+	return bpf_strnstr(invalid_aligned_kern_ptr, "12345678", 8);
+}
+
+SEC("syscall")
+__retval(-EFAULT)
+int test_strnstr_word_pagefault2(void *ctx)
+{
+	return bpf_strnstr("12345678", invalid_aligned_kern_ptr, 8);
+}
+
 char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/string_kfuncs_success.c b/tools/testing/selftests/bpf/progs/string_kfuncs_success.c
index f65b1226a81a..ec72410e17a1 100644
--- a/tools/testing/selftests/bpf/progs/string_kfuncs_success.c
+++ b/tools/testing/selftests/bpf/progs/string_kfuncs_success.c
@@ -6,6 +6,11 @@
 #include "errno.h"
 
 char str[] = "hello world";
+char aligned_str[] __aligned(8) = "0123456789abcdef0123456789ABCDEF";
+char unaligned_str[] __aligned(8) = "_0123456789abcdef0123456789ABCDEF";
+char scan_order[] __aligned(8) = { 'a', 'H', '\0', 'H', 'x', 'x', 'x', 'x' };
+char compare_order1[] __aligned(8) = { 'a', 'b', '\0', 'x', 'x', 'x', 'x', 'x' };
+char compare_order2[] __aligned(8) = { 'a', 'b', '\0', 'y', 'y', 'y', 'y', 'y' };
 
 #define __test(retval) SEC("syscall") __success __retval(retval)
 
@@ -60,4 +65,85 @@ __test(-ENOENT) int test_strncasestr_notfound2(void *ctx) { return bpf_strncases
 __test(-ENOENT) int test_strncasestr_notfound3(void *ctx) { return bpf_strncasestr("", "a", 0); }
 __test(0) int test_strncasestr_empty(void *ctx) { return bpf_strncasestr(str, "", 1); }
 
+/* Exercise aligned word loads, mask ordering, and unaligned prefixes. */
+__test(30) int test_strnchr_word(void *ctx) { return bpf_strnchr(aligned_str, 32, 'E'); }
+
+__test(1) int test_strnchr_word_before_null(void *ctx)
+{
+	return bpf_strnchr(scan_order, sizeof(scan_order), 'H');
+}
+
+__test(-ENOENT) int test_strnchr_word_after_null(void *ctx)
+{
+	return bpf_strnchr(scan_order, sizeof(scan_order), 'x');
+}
+
+__test(2) int test_strchrnul_word_after_null(void *ctx)
+{
+	return bpf_strchrnul(scan_order, 'x');
+}
+
+__test(1) int test_strrchr_word_after_null(void *ctx)
+{
+	return bpf_strrchr(scan_order, 'H');
+}
+
+__test(2) int test_strnlen_word_null(void *ctx)
+{
+	return bpf_strnlen(scan_order, sizeof(scan_order));
+}
+
+__test(32) int test_strlen_word(void *ctx) { return bpf_strlen(aligned_str); }
+
+__test(0) int test_strcmp_word(void *ctx) { return bpf_strcmp(aligned_str, unaligned_str + 1); }
+
+__test(0) int test_strcmp_word_after_null(void *ctx)
+{
+	return bpf_strcmp(compare_order1, compare_order2);
+}
+
+__test(-1) int test_strcmp_word_mismatch(void *ctx)
+{
+	return bpf_strcmp(aligned_str, "0123456789abcdef1123456789abcdef");
+}
+
+__test(32) int test_strspn_word(void *ctx)
+{
+	return bpf_strspn(aligned_str, "0123456789abcdefABCDEF");
+}
+
+__test(0) int test_strspn_word_set_after_null(void *ctx)
+{
+	return bpf_strspn("xx", scan_order);
+}
+
+__test(30) int test_strcspn_word(void *ctx) { return bpf_strcspn(unaligned_str + 1, "E"); }
+
+__test(16) int test_strstr_word(void *ctx) { return bpf_strstr(aligned_str, "0123456789ABCDEF"); }
+
+__test(16) int test_strstr_unaligned(void *ctx)
+{
+	return bpf_strstr(unaligned_str + 1, "0123456789ABCDEF");
+}
+
+__test(15) int test_strcasestr_word(void *ctx)
+{
+	return bpf_strcasestr(aligned_str, "F0123456789ABCDEF");
+}
+
+__test(0) int test_strnstr_word_suffix(void *ctx)
+{
+	return bpf_strnstr(aligned_str, "0123456789abcdef", 16);
+}
+
+__test(-ENOENT) int test_strnstr_word_truncated(void *ctx)
+{
+	return bpf_strnstr(aligned_str, "0123456789abcdef0", 16);
+}
+
+__test(0) int test_strnstr_word_after_null(void *ctx)
+{
+	return bpf_strnstr(compare_order1, compare_order2, sizeof(compare_order1));
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.55.0

[RFC PATCH bpf-next 6/6] selftests/bpf: Benchmark string kfuncs

[Leon Hwang]

Add a kfunc-only benchmark covering one representative from each string
family: bpf_strnchr(), bpf_strcmp(), bpf_strcspn(), and bpf_strnstr().

Userspace populates aligned .data buffers once per scenario, before the
timed program runs. Each BPF program reads those buffers and calls the
selected kfunc directly.

Run the programs through BPF_PROG_TEST_RUN with first, middle, late, and
terminal scenarios, and report median kernel execution times. Always run
the complete matrix with fixed repetitions, trials, and warmup settings.

Extend the generic benchmark framework with a synchronous run callback
and register the string kfunc benchmark with it. This keeps the finite
trial matrix out of the producer and consumer timing loop.

Have the runner save its first result as a temporary baseline and compare
subsequent runs against it, reporting baseline and current timings with
their speedup.

Assisted-by: Codex:gpt-5.6-sol
Signed-off-by: Leon Hwang <leon.hwang@linux.dev>
---
 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 ++++
 6 files changed, 389 insertions(+)
 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

diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile
index 55d394438705..e1e9d7ae7cb7 100644
--- a/tools/testing/selftests/bpf/Makefile
+++ b/tools/testing/selftests/bpf/Makefile
@@ -977,6 +977,7 @@ $(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_bpf_nop.o: $(OUTPUT)/bpf_nop_bench.skel.h bench_bpf_timing.h
 $(OUTPUT)/bench_xdp_lb.o: $(OUTPUT)/xdp_lb_bench.skel.h bench_bpf_timing.h
+$(OUTPUT)/bench_bpf_str_kfuncs.o: $(OUTPUT)/bpf_str_kfuncs_bench.skel.h
 $(OUTPUT)/bench_bpf_timing.o: bench_bpf_timing.h
 $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ)
 $(OUTPUT)/bench: LDLIBS += -lm
@@ -1003,6 +1004,7 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \
 		 $(OUTPUT)/bench_bpf_timing.o \
 		 $(OUTPUT)/bench_bpf_nop.o \
 		 $(OUTPUT)/bench_xdp_lb.o \
+		 $(OUTPUT)/bench_bpf_str_kfuncs.o \
 		 $(OUTPUT)/usdt_1.o \
 		 $(OUTPUT)/usdt_2.o \
 		 #
diff --git a/tools/testing/selftests/bpf/bench.c b/tools/testing/selftests/bpf/bench.c
index 3d9d2cd7764b..c355f824b8ba 100644
--- a/tools/testing/selftests/bpf/bench.c
+++ b/tools/testing/selftests/bpf/bench.c
@@ -582,6 +582,7 @@ extern const struct bench bench_lpm_trie_delete;
 extern const struct bench bench_lpm_trie_free;
 extern const struct bench bench_bpf_nop;
 extern const struct bench bench_xdp_lb;
+extern const struct bench bench_bpf_str_kfuncs;
 
 static const struct bench *benchs[] = {
 	&bench_count_global,
@@ -665,6 +666,7 @@ static const struct bench *benchs[] = {
 	&bench_lpm_trie_free,
 	&bench_bpf_nop,
 	&bench_xdp_lb,
+	&bench_bpf_str_kfuncs,
 };
 
 static void find_benchmark(void)
@@ -791,6 +793,15 @@ int main(int argc, char **argv)
 	find_benchmark();
 	parse_cmdline_args_final(argc, argv);
 
+	if (bench->run) {
+		if (bench->validate)
+			bench->validate();
+		if (bench->setup)
+			bench->setup();
+		bench->run();
+		return 0;
+	}
+
 	setup_benchmark();
 
 	setup_timer();
diff --git a/tools/testing/selftests/bpf/bench.h b/tools/testing/selftests/bpf/bench.h
index 89a3fc72f70e..9351b472d5e4 100644
--- a/tools/testing/selftests/bpf/bench.h
+++ b/tools/testing/selftests/bpf/bench.h
@@ -55,6 +55,8 @@ struct bench {
 	const struct argp *argp;
 	void (*validate)(void);
 	void (*setup)(void);
+	/* Run a synchronous benchmark without producer or consumer threads. */
+	void (*run)(void);
 	void *(*producer_thread)(void *ctx);
 	void *(*consumer_thread)(void *ctx);
 	void (*measure)(struct bench_res* res);
diff --git a/tools/testing/selftests/bpf/benchs/bench_bpf_str_kfuncs.c b/tools/testing/selftests/bpf/benchs/bench_bpf_str_kfuncs.c
new file mode 100644
index 000000000000..12139054bed5
--- /dev/null
+++ b/tools/testing/selftests/bpf/benchs/bench_bpf_str_kfuncs.c
@@ -0,0 +1,228 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/utsname.h>
+
+#include "bench.h"
+#include "bpf_str_kfuncs_bench.skel.h"
+
+#define STR_BENCH_CAP		2048
+#define STR_BENCH_SCENARIOS	4
+#define STR_BENCH_REPEAT	100000
+#define STR_BENCH_TRIALS	9
+#define STR_BENCH_WARMUP	1000
+
+enum benchmark_kind {
+	BENCH_SCAN,
+	BENCH_COMPARISON,
+	BENCH_SPAN,
+	BENCH_SUBSTRING,
+	BENCH_COUNT,
+};
+
+struct scenario {
+	const char *name;
+	unsigned char payload[STR_BENCH_CAP];
+	size_t length;
+	int position;
+	__u32 want;
+};
+
+struct sample {
+	double ns_per_op;
+};
+
+struct benchmark {
+	const char *name;
+	const char *kfunc;
+	struct bpf_program *prog;
+	struct bpf_str_kfuncs_bench *skel;
+	enum benchmark_kind kind;
+};
+
+struct scenario_spec {
+	const char *name;
+	size_t length;
+	int position;
+};
+
+static const struct scenario_spec scenario_specs[STR_BENCH_SCENARIOS] = {
+	{ "first",  64,   0    },
+	{ "middle", 512,  240  },
+	{ "late",   1536, 1200 },
+	{ "absent", 2048, -1   },
+};
+
+static const char substring_needle[] = "Host: benchmark.example.com";
+static const unsigned char dummy_packet[64];
+
+static void make_scenario(enum benchmark_kind kind, struct scenario *scenario,
+			  const struct scenario_spec *spec)
+{
+	scenario->name = spec->name;
+	scenario->length = spec->length;
+	scenario->position = spec->position;
+
+	switch (kind) {
+	case BENCH_SCAN:
+		memset(scenario->payload, 'x', scenario->length);
+		if (spec->position >= 0)
+			scenario->payload[spec->position] = 'H';
+		scenario->want = spec->position < 0 ? (__u32)-ENOENT : spec->position;
+		break;
+	case BENCH_COMPARISON:
+		scenario->name = spec->position < 0 ? "equal" : spec->name;
+		memset(scenario->payload, 'a', scenario->length);
+		scenario->want = spec->position < 0 ? 0 : (__u32)-1;
+		break;
+	case BENCH_SPAN:
+		memset(scenario->payload, 'a', scenario->length);
+		if (spec->position >= 0)
+			scenario->payload[spec->position] = ':';
+		scenario->want = spec->position < 0 ? scenario->length : spec->position;
+		break;
+	case BENCH_SUBSTRING:
+		memset(scenario->payload, 'x', scenario->length);
+		if (spec->position >= 0)
+			memcpy(scenario->payload + spec->position, substring_needle,
+			       sizeof(substring_needle) - 1);
+		scenario->want = spec->position < 0 ? (__u32)-ENOENT : spec->position;
+		break;
+	case BENCH_COUNT:
+		break;
+	}
+}
+
+static void prepare_program_input(const struct benchmark *benchmark,
+				  const struct scenario *scenario)
+{
+	unsigned char *lhs = (unsigned char *)benchmark->skel->data->buffers.lhs.words;
+	unsigned char *rhs = (unsigned char *)benchmark->skel->data->buffers.rhs.words;
+
+	memcpy(lhs, scenario->payload, scenario->length);
+	lhs[scenario->length] = '\0';
+
+	if (benchmark->kind == BENCH_COMPARISON) {
+		memcpy(rhs, scenario->payload, scenario->length);
+		if (scenario->position >= 0)
+			rhs[scenario->position] = 'b';
+		rhs[scenario->length] = '\0';
+	}
+
+	benchmark->skel->data->payload_length = scenario->length;
+}
+
+static void run_program(const struct benchmark *benchmark, const struct scenario *scenario,
+			int repeat, struct sample *sample)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, topts);
+	int err;
+
+	topts.data_in = dummy_packet;
+	topts.data_size_in = sizeof(dummy_packet);
+	topts.repeat = repeat;
+	err = bpf_prog_test_run_opts(bpf_program__fd(benchmark->prog), &topts);
+	if (err || topts.retval != scenario->want) {
+		fprintf(stderr, "%s/%s failed: err=%d retval=%u want=%u\n",
+			benchmark->name, scenario->name, err, topts.retval, scenario->want);
+		exit(1);
+	}
+	if (sample)
+		sample->ns_per_op = topts.duration;
+}
+
+static int compare_samples(const void *a, const void *b)
+{
+	const struct sample *sa = a;
+	const struct sample *sb = b;
+
+	if (sa->ns_per_op < sb->ns_per_op)
+		return -1;
+	if (sa->ns_per_op > sb->ns_per_op)
+		return 1;
+	return 0;
+}
+
+static void benchmark_scenario(const struct benchmark *benchmark, const struct scenario *scenario)
+{
+	struct sample samples[STR_BENCH_TRIALS];
+	int i;
+
+	prepare_program_input(benchmark, scenario);
+	run_program(benchmark, scenario, STR_BENCH_WARMUP, NULL);
+	for (i = 0; i < STR_BENCH_TRIALS; i++)
+		run_program(benchmark, scenario, STR_BENCH_REPEAT, &samples[i]);
+
+	qsort(samples, STR_BENCH_TRIALS, sizeof(*samples), compare_samples);
+	printf("%-9s %5zu %13.1f\n", scenario->name, scenario->length,
+	       samples[STR_BENCH_TRIALS / 2].ns_per_op);
+}
+
+static void str_kfuncs_run(void)
+{
+	struct benchmark benchmarks[BENCH_COUNT];
+	struct bpf_str_kfuncs_bench *skel;
+	struct scenario scenario;
+	struct utsname uts = {};
+	int i, j;
+
+	setup_libbpf();
+	skel = bpf_str_kfuncs_bench__open_and_load();
+	if (!skel) {
+		fprintf(stderr, "Failed to load BPF skeleton\n");
+		exit(1);
+	}
+
+	benchmarks[BENCH_SCAN] = (struct benchmark) {
+		.name = "scan",
+		.kfunc = "bpf_strnchr",
+		.prog = skel->progs.scan_kfunc,
+		.skel = skel,
+		.kind = BENCH_SCAN,
+	};
+	benchmarks[BENCH_COMPARISON] = (struct benchmark) {
+		.name = "comparison",
+		.kfunc = "bpf_strcmp",
+		.prog = skel->progs.compare_kfunc,
+		.skel = skel,
+		.kind = BENCH_COMPARISON,
+	};
+	benchmarks[BENCH_SPAN] = (struct benchmark) {
+		.name = "span",
+		.kfunc = "bpf_strcspn",
+		.prog = skel->progs.span_kfunc,
+		.skel = skel,
+		.kind = BENCH_SPAN,
+	};
+	benchmarks[BENCH_SUBSTRING] = (struct benchmark) {
+		.name = "substring",
+		.kfunc = "bpf_strnstr",
+		.prog = skel->progs.substring_kfunc,
+		.skel = skel,
+		.kind = BENCH_SUBSTRING,
+	};
+
+	uname(&uts);
+	printf("BPF string kfunc benchmark\n");
+	printf("kernel=%s arch=%s repeat=%d trials=%d warmup=%d\n",
+	       uts.release, uts.machine, STR_BENCH_REPEAT, STR_BENCH_TRIALS, STR_BENCH_WARMUP);
+
+	for (i = 0; i < BENCH_COUNT; i++) {
+		printf("\n%s (%s)\n", benchmarks[i].name, benchmarks[i].kfunc);
+		printf("%-9s %5s %13s\n", "Scenario", "Bytes", "Kfunc ns/op");
+
+		for (j = 0; j < STR_BENCH_SCENARIOS; j++) {
+			make_scenario(benchmarks[i].kind, &scenario, &scenario_specs[j]);
+			benchmark_scenario(&benchmarks[i], &scenario);
+		}
+	}
+
+	bpf_str_kfuncs_bench__destroy(skel);
+}
+
+const struct bench bench_bpf_str_kfuncs = {
+	.name = "bpf-str-kfuncs",
+	.run = str_kfuncs_run,
+};
diff --git a/tools/testing/selftests/bpf/benchs/run_bench_bpf_str_kfuncs.sh b/tools/testing/selftests/bpf/benchs/run_bench_bpf_str_kfuncs.sh
new file mode 100755
index 000000000000..4787176e7717
--- /dev/null
+++ b/tools/testing/selftests/bpf/benchs/run_bench_bpf_str_kfuncs.sh
@@ -0,0 +1,98 @@
+#!/bin/bash
+# SPDX-License-Identifier: GPL-2.0
+
+set -euo pipefail
+
+cpu=${CPU:-1}
+report=${REPORT:-bench_bpf_str_kfuncs.tmp}
+
+if [[ -z "$report" ]]; then
+	echo "Report file must not be empty" >&2
+	exit 2
+fi
+
+tmp=$(mktemp "${report}.tmp.XXXXXX")
+trap 'rm -f "$tmp"' EXIT
+
+sudo taskset -c "$cpu" ./bench bpf-str-kfuncs "$@" > "$tmp"
+
+if [[ ! -e "$report" ]]; then
+	mv "$tmp" "$report"
+	trap - EXIT
+	cat "$report"
+	printf '\nSaved baseline report to %s\n' "$report"
+	exit
+fi
+
+awk '
+function fail(message)
+{
+	print "Invalid benchmark comparison: " message > "/dev/stderr"
+	failed = 1
+	exit 1
+}
+
+FNR == 1 {
+	file++
+	kind = ""
+}
+
+$1 ~ /^kernel=/ {
+	if (file == 1) {
+		baseline_kernel = $0
+		baseline_params = $2 " " $3 " " $4 " " $5
+	} else {
+		current_kernel = $0
+		current_params = $2 " " $3 " " $4 " " $5
+		if (baseline_params != current_params)
+			fail("architecture or run parameters differ")
+		print "BPF string kfunc benchmark comparison"
+		print "baseline " baseline_kernel
+		print "current  " current_kernel
+	}
+	next
+}
+
+$0 ~ /^[[:alpha:]]+ \(bpf_[[:alnum:]_]+\)$/ {
+	kind = $1
+	kfunc = $2
+	gsub(/[()]/, "", kfunc)
+	next
+}
+
+$1 ~ /^(first|middle|late|absent|equal)$/ && $2 ~ /^[0-9]+$/ {
+	key = kind SUBSEP $1
+	if (!kind)
+		fail("result row without benchmark name")
+
+	if (file == 1) {
+		baseline[key] = $3
+		baseline_bytes[key] = $2
+		baseline_count++
+	} else {
+		if (!(key in baseline))
+			fail("baseline is missing " kind "/" $1)
+		if (baseline_bytes[key] != $2)
+			fail("byte count differs for " kind "/" $1)
+		if (kind != last_kind) {
+			last_kind = kind
+			printf "\n%s (%s)\n", kind, kfunc
+			printf "%-9s %5s %15s %14s %9s\n", "Scenario",
+			       "Bytes", "Baseline ns/op", "Current ns/op",
+			       "Speedup"
+		}
+		printf "%-9s %5d %15.1f %14.1f %8.2fx\n",
+		       $1, $2, baseline[key], $3, baseline[key] / $3
+		current_count++
+	}
+}
+
+END {
+	if (failed)
+		exit 1
+	if (!baseline_kernel || !current_kernel)
+		fail("missing benchmark metadata")
+	if (baseline_count != current_count)
+		fail("different number of result rows")
+}
+' "$report" "$tmp"
diff --git a/tools/testing/selftests/bpf/progs/bpf_str_kfuncs_bench.c b/tools/testing/selftests/bpf/progs/bpf_str_kfuncs_bench.c
new file mode 100644
index 000000000000..44a40e42cafa
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/bpf_str_kfuncs_bench.c
@@ -0,0 +1,48 @@
+// SPDX-License-Identifier: GPL-2.0
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+#define STR_BENCH_CAP 2048
+
+static const char span_reject[] __aligned(8) = ":";
+static const char substring_needle[] __aligned(8) =
+	"Host: benchmark.example.com";
+
+/* Populated by userspace once per scenario, outside the timed program run. */
+struct {
+	struct {
+		__u64 words[(STR_BENCH_CAP + sizeof(__u64)) / sizeof(__u64)];
+	} lhs;
+	struct {
+		__u64 words[(STR_BENCH_CAP + sizeof(__u64)) / sizeof(__u64)];
+	} rhs;
+} buffers SEC(".data");
+
+__u32 payload_length SEC(".data");
+
+SEC("tc")
+int scan_kfunc(struct __sk_buff *skb)
+{
+	return bpf_strnchr((const char *)buffers.lhs.words, payload_length, 'H');
+}
+
+SEC("tc")
+int compare_kfunc(struct __sk_buff *skb)
+{
+	return bpf_strcmp((const char *)buffers.lhs.words, (const char *)buffers.rhs.words);
+}
+
+SEC("tc")
+int span_kfunc(struct __sk_buff *skb)
+{
+	return bpf_strcspn((const char *)buffers.lhs.words, span_reject);
+}
+
+SEC("tc")
+int substring_kfunc(struct __sk_buff *skb)
+{
+	return bpf_strnstr((const char *)buffers.lhs.words, substring_needle, payload_length);
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.55.0

Re: [RFC PATCH bpf-next 5/6] selftests/bpf: Exercise word-at-a-time string kfuncs

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Tests intended to exercise word-load page faults fail to reach the word-at-a-time code paths due to unaligned arguments or byte-load implementations.
--

--- Patch [5]: [RFC PATCH bpf-next 5/6] selftests/bpf: Exercise word-at-a-time string kfuncs ---
commit dc0a0a05e577e233a4ad33ac1ebb0ed2f4f840c1
Author: Leon Hwang <leon.hwang@linux.dev>

selftests/bpf: Exercise word-at-a-time string kfuncs
    
This commit adds functional coverage for aligned and unaligned strings
across the scan, comparison, span, and substring families. It also adds tests
using aligned invalid kernel addresses to exercise failed word-sized nofault
loads and their byte-sized retries.

> diff --git a/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c b/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c
> index bddc4e8579d24..05f93c7cd07cd 100644
> --- a/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c
> +++ b/tools/testing/selftests/bpf/progs/string_kfuncs_failure1.c

[ ... ]

> @@ -108,4 +109,61 @@ SEC("syscall") __retval(-EFAULT) int test_strnstr_pagefault2(void *ctx) { return
>  SEC("syscall") __retval(-EFAULT) int test_strncasestr_pagefault1(void *ctx) { return bpf_strncasestr(invalid_kern_ptr, "hello", 1); }
>  SEC("syscall") __retval(-EFAULT) int test_strncasestr_pagefault2(void *ctx) { return bpf_strncasestr("hello", invalid_kern_ptr, 1); }
>  
> +/* Exercise word-load faults and the byte retry at the same address. */
> +SEC("syscall")
> +__retval(-EFAULT)
> +int test_strncasecmp_word_pagefault(void *ctx)
> +{
> +	return bpf_strncasecmp(invalid_aligned_kern_ptr, "12345678", 8);

[Severity: Medium]
Will this actually exercise the word-load fault logic?

Since "12345678" is a string literal, it may not be aligned. If it is
relatively misaligned, __bpf_strncasecmp falls back to a byte-by-byte loop,
which would mean this test misses the intended word-load fault test entirely
and only tests the byte-load path.

> +}

[ ... ]

> +SEC("syscall")
> +__retval(-EFAULT)
> +int test_strspn_set_word_pagefault(void *ctx)
> +{
> +	return bpf_strspn("a", invalid_aligned_kern_ptr);

[Severity: Medium]
Does this test reach the word-at-a-time code path?

It looks like bpf_strspn processes the 'accept' set using strictly 1-byte
loads. By passing the invalid pointer as the set, the test will fault on
a byte-load, bypassing the word-load logic it is intended to test.

> +}

[ ... ]

> +SEC("syscall")
> +__retval(-EFAULT)
> +int test_strnstr_word_pagefault2(void *ctx)
> +{
> +	return bpf_strnstr("12345678", invalid_aligned_kern_ptr, 8);

[Severity: Medium]
Will this fault on a word-load?

Looking at bpf_strnstr(), it unconditionally reads the first character of the
second argument using a 1-byte load. If invalid_aligned_kern_ptr is passed
here, it will fault on the initial byte-load before any word-load occurs.

> +}
> +
>  char _license[] SEC("license") = "GPL";

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260728145727.45153-1-leon.hwang@linux.dev?part=5