Skip to contentSkip to conversation

bpf: Add kfuncs for read-only string operations

PATCH Superseded Viktor Malik 4 participants 9 messages Mar 24, 2025 – Apr 1, 2025

Subsystems (3)

v3 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

v3 cover bpf: Add kfuncs for read-only string operations

String operations are commonly used in programming and BPF programs are no exception. Since it is cumbersome to reimplement them over and over, this series introduce kfuncs which provide the most common operations. For now, we only limit ourselves to functions which do not copy memory since these usually introduce undefined behaviour in case the source/destination buffers overlap which would have to be prevented by the verifier.

The kernel already contains implementations for all of these, however, it is not possible to use them from BPF context. The main reason is that the verifier is not able to check that it is safe to access the entire string if the string size is not passed to the kfunc. Therefore, the unbounded variants of the operations are open-coded with __get_kernel_nofault used instead of plain dereference to make them safe.

On the contrary, safety of the bounded variants can be checked by the verifier so we reuse the kernel implementations which are sometimes highly optimized in assembly.

The last patch of the series adds a benchmark for comparing performance of the bounded and unbounded variants which shows that on architectures with optimized bounded string functions (e.g. strnlen on arm64), the performance benefit can be significant (140% for 4095B strings).

Changes in v3:
- Open-code unbounded variants with __get_kernel_nofault instead of dereference (suggested by Alexei).
- Use the __sz suffix for size parameters in bounded variants (suggested by Eduard and Alexei).
- Make tests more compact (suggested by Eduard).
- Add benchmark.

Viktor Malik (3):
bpf: Add kfuncs for read-only string operations selftests/bpf: Add tests for string kfuncs selftests/bpf: Add benchmark for bounded/unbounded string kfuncs

 kernel/bpf/helpers.c                          | 299 ++++++++++++++++++
 tools/testing/selftests/bpf/Makefile          |   2 +
 tools/testing/selftests/bpf/bench.c           |  21 ++
 .../bpf/benchs/bench_string_kfuncs.c          | 259 +++++++++++++++
 .../bpf/benchs/run_bench_string_kfuncs.sh     |  34 ++
 .../selftests/bpf/prog_tests/string_kfuncs.c  |  10 +
 .../selftests/bpf/progs/string_kfuncs.c       |  58 ++++
 .../selftests/bpf/progs/string_kfuncs_bench.c |  88 ++++++
 8 files changed, 771 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_string_kfuncs.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_string_kfuncs.sh
 create mode 100644 tools/testing/selftests/bpf/prog_tests/string_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/string_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/string_kfuncs_bench.c
Signature · 1 line
2.48.1
#1 lore raw

PATCH v3 1/3 bpf: Add kfuncs for read-only string operations

String operations are commonly used so this exposes the most common ones to BPF programs. For now, we limit ourselves to operations which do not copy memory around.

Unfortunately, most in-kernel implementations assume that strings are %NUL-terminated, which is not necessarily true, and therefore we cannot use them directly in BPF context. So, we use distinct approaches for bounded and unbounded variants of string operations:

- Unbounded variants are open-coded with using __get_kernel_nofault instead of plain dereference to make them safe.

- Bounded variants use params with the __sz suffix so safety is assured by the verifier and we can use the in-kernel (potentially optimized) functions.

---
 kernel/bpf/helpers.c | 299 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 299 insertions(+)
kernel/bpf/helpers.c +299 -0
index 5449756ba102..6f6af4289cd0 100644
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0-only
 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
  */
+#include "linux/uaccess.h"
 #include <linux/bpf.h>
 #include <linux/btf.h>
 #include <linux/bpf-cgroup.h>
@@ -3193,6 +3194,291 @@ __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag)
 	local_irq_restore(*flags__irq_flag);
 }
 
+/* Kfuncs for string operations.
+ *
+ * Since strings are not necessarily %NUL-terminated, we cannot directly call
+ * in-kernel implementations. Instead, unbounded variants are open-coded with
+ * using __get_kernel_nofault instead of plain dereference to make them safe.
+ * Bounded variants use params with the __sz suffix so safety is assured by the
+ * verifier and we can use the in-kernel (potentially optimized) functions.
+ */
+
+/**
+ * bpf_strcmp - Compare two strings
+ * @cs: One string
+ * @ct: Another string
+ */
+__bpf_kfunc int bpf_strcmp(const char *cs, const char *ct)
+{
+	int i = 0, ret = 0;
+	char c1, c2;
+
+	pagefault_disable();
+	while (i++ < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&c1, cs++, char, cs_out);
+		__get_kernel_nofault(&c2, ct++, char, ct_out);
+		if (c1 != c2) {
+			ret = c1 < c2 ? -1 : 1;
+			goto out;
+		}
+		if (!c1)
+			goto out;
+	}
+cs_out:
+	ret = -1;
+	goto out;
+ct_out:
+	ret = 1;
+out:
+	pagefault_enable();
+	return ret;
+}
+
+/**
+ * bpf_strchr - Find the first occurrence of a character in a string
+ * @s: The string to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strchr(const char *s, int c)
+{
+	char *ret = NULL;
+	int i = 0;
+	char sc;
+
+	pagefault_disable();
+	while (i++ < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&sc, s, char, out);
+		if (sc == (char)c) {
+			ret = (char *)s;
+			break;
+		}
+		if (sc == '\0')
+			break;
+		s++;
+	}
+out:
+	pagefault_enable();
+	return ret;
+}
+
+/**
+ * bpf_strchrnul - Find and return a character in a string, or end of string
+ * @s: The string to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to first occurrence of 'c' in s. If c is not found, then
+ * return a pointer to the null byte at the end of s.
+ */
+__bpf_kfunc char *bpf_strchrnul(const char *s, int c)
+{
+	char *ret = NULL;
+	int i = 0;
+	char sc;
+
+	pagefault_disable();
+	while (i++ < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&sc, s, char, out);
+		if (sc == '\0' || sc == (char)c) {
+			ret = (char *)s;
+			break;
+		}
+		s++;
+	}
+out:
+	pagefault_enable();
+	return ret;
+}
+
+/**
+ * bpf_strnchr - Find a character in a length limited string
+ * @s: The string to be searched
+ * @s__sz: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strnchr(void *s, u32 s__sz, int c)
+{
+	return strnchr(s, s__sz, c);
+}
+
+/**
+ * bpf_strnchrnul - Find and return a character in a length limited string,
+ * or end of string
+ * @s: The string to be searched
+ * @s__sz: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to the first occurrence of 'c' in s. If c is not found,
+ * then return a pointer to the last character of the string.
+ */
+__bpf_kfunc char *bpf_strnchrnul(void *s, u32 s__sz, int c)
+{
+	return strnchrnul(s, s__sz, c);
+}
+
+/**
+ * bpf_strrchr - Find the last occurrence of a character in a string
+ * @s: The string to be searched
+ * @c: The character to search for
+ */
+__bpf_kfunc char *bpf_strrchr(const char *s, int c)
+{
+	char *ret = NULL;
+	int i = 0;
+	char sc;
+
+	pagefault_disable();
+	while (i++ < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&sc, s, char, out);
+		if (sc == '\0')
+			break;
+		if (sc == (char)c)
+			ret = (char *)s;
+		s++;
+	}
+out:
+	pagefault_enable();
+	return (char *)ret;
+}
+
+__bpf_kfunc size_t bpf_strlen(const char *s)
+{
+	int i = 0;
+	char c;
+
+	pagefault_disable();
+	while (i < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&c, s++, char, out);
+		if (c == '\0')
+			break;
+		i++;
+	}
+out:
+	pagefault_enable();
+	return i;
+}
+
+__bpf_kfunc size_t bpf_strnlen(void *s, u32 s__sz)
+{
+	return strnlen(s, s__sz);
+}
+
+/**
+ * bpf_strspn - Calculate the length of the initial substring of @s which only contain letters in @accept
+ * @s: The string to be searched
+ * @accept: The string to search for
+ */
+__bpf_kfunc size_t bpf_strspn(const char *s, const char *accept)
+{
+	int i = 0;
+	char c;
+
+	pagefault_disable();
+	while (i < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&c, s++, char, out);
+		if (c == '\0' || !bpf_strchr(accept, c))
+			break;
+		i++;
+	}
+out:
+	pagefault_enable();
+	return i;
+}
+
+/**
+ * strcspn - Calculate the length of the initial substring of @s which does not contain letters in @reject
+ * @s: The string to be searched
+ * @reject: The string to avoid
+ */
+__bpf_kfunc size_t bpf_strcspn(const char *s, const char *reject)
+{
+	int i = 0;
+	char c;
+
+	pagefault_disable();
+	while (i < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&c, s++, char, out);
+		if (c == '\0' || bpf_strchr(reject, c))
+			break;
+		i++;
+	}
+out:
+	pagefault_enable();
+	return i;
+}
+
+/**
+ * bpf_strpbrk - Find the first occurrence of a set of characters
+ * @cs: The string to be searched
+ * @ct: The characters to search for
+ */
+__bpf_kfunc char *bpf_strpbrk(const char *cs, const char *ct)
+{
+	char *ret = NULL;
+	int i = 0;
+	char c;
+
+	pagefault_disable();
+	while (i++ < XATTR_SIZE_MAX) {
+		__get_kernel_nofault(&c, cs, char, out);
+		if (c == '\0')
+			break;
+		if (bpf_strchr(ct, c)) {
+			ret = (char *)cs;
+			break;
+		}
+		cs++;
+	}
+out:
+	pagefault_enable();
+	return ret;
+}
+
+/**
+ * bpf_strstr - Find the first substring in a %NUL terminated string
+ * @s1: The string to be searched
+ * @s2: The string to search for
+ */
+__bpf_kfunc char *bpf_strstr(const char *s1, const char *s2)
+{
+	size_t l1, l2;
+
+	l2 = bpf_strlen(s2);
+	if (!l2)
+		return (char *)s1;
+	l1 = bpf_strlen(s1);
+	while (l1 >= l2) {
+		l1--;
+		if (!memcmp(s1, s2, l2))
+			return (char *)s1;
+		s1++;
+	}
+	return NULL;
+}
+
+/**
+ * bpf_strnstr - Find the first substring in a length-limited string
+ * @s1: The string to be searched
+ * @s1__sz: The size of @s1
+ * @s2: The string to search for
+ * @s2__sz: The size of @s2
+ */
+__bpf_kfunc char *bpf_strnstr(void *s1, u32 s1__sz, void *s2, u32 s2__sz)
+{
+	/* strnstr() uses strlen() to get the length of s2. Since this is not
+	 * safe in BPF context for non-%NUL-terminated strings, use strnlen
+	 * first to make it safe.
+	 */
+	if (strnlen(s2, s2__sz) == s2__sz)
+		return NULL;
+	return strnstr(s1, s2, s1__sz);
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -3293,6 +3579,19 @@ BTF_ID_FLAGS(func, bpf_iter_kmem_cache_next, KF_ITER_NEXT | KF_RET_NULL | KF_SLE
 BTF_ID_FLAGS(func, bpf_iter_kmem_cache_destroy, KF_ITER_DESTROY | KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_local_irq_save)
 BTF_ID_FLAGS(func, bpf_local_irq_restore)
+BTF_ID_FLAGS(func, bpf_strcmp);
+BTF_ID_FLAGS(func, bpf_strchr);
+BTF_ID_FLAGS(func, bpf_strchrnul);
+BTF_ID_FLAGS(func, bpf_strnchr);
+BTF_ID_FLAGS(func, bpf_strnchrnul);
+BTF_ID_FLAGS(func, bpf_strrchr);
+BTF_ID_FLAGS(func, bpf_strlen);
+BTF_ID_FLAGS(func, bpf_strnlen);
+BTF_ID_FLAGS(func, bpf_strspn);
+BTF_ID_FLAGS(func, bpf_strcspn);
+BTF_ID_FLAGS(func, bpf_strpbrk);
+BTF_ID_FLAGS(func, bpf_strstr);
+BTF_ID_FLAGS(func, bpf_strnstr);
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
Signature · 1 line
2.48.1
#6 lore raw

PATCH v3 2/3 selftests/bpf: Add tests for string kfuncs

In reply to Viktor Malik

The tests use the RUN_TESTS helper which executes BPF programs with BPF_PROG_TEST_RUN and check for the expected return value.

---
 .../selftests/bpf/prog_tests/string_kfuncs.c  | 10 ++++
 .../selftests/bpf/progs/string_kfuncs.c       | 58 +++++++++++++++++++
 2 files changed, 68 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/string_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/string_kfuncs.c
tools/testing/selftests/bpf/prog_tests/string_kfuncs.c new file +10 -0
new file mode 100644
index 000000000000..79dab172eb92
@@ -0,0 +1,10 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (C) 2025 Red Hat, Inc.*/
+#include <test_progs.h>
+#include "string_kfuncs.skel.h"
+
+void test_string_kfuncs(void)
+{
+	RUN_TESTS(string_kfuncs);
+}
+
tools/testing/selftests/bpf/progs/string_kfuncs.c new file +58 -0

58 lines not on this page · raw message

Signature · 1 line
2.48.1
#8 lore raw

PATCH v3 3/3 selftests/bpf: Add benchmark for bounded/unbounded string kfuncs

In reply to Viktor Malik

Add a new benchmark using the existing bench infrastructure which compares performance of bounded and unbounded string kfuncs added in the previous commits.

Running on x86_64 and arm64, the most significant difference is in the strlen/strnlen and strstr/strnstr comparisons on arm64:

    strlen/strnlen
    ==============
    strlen-1             0.453 ± 0.002M/s (drops 0.000 ± 0.000M/s)
    strnlen-1            0.470 ± 0.006M/s (drops 0.000 ± 0.000M/s)
    strlen-8             0.459 ± 0.011M/s (drops 0.000 ± 0.000M/s)
    strnlen-8            0.451 ± 0.006M/s (drops 0.000 ± 0.000M/s)
    strlen-64            0.439 ± 0.007M/s (drops 0.000 ± 0.000M/s)
    strnlen-64           0.455 ± 0.006M/s (drops 0.000 ± 0.000M/s)
    strlen-512           0.359 ± 0.006M/s (drops 0.000 ± 0.000M/s)
    strnlen-512          0.441 ± 0.007M/s (drops 0.000 ± 0.000M/s)
    strlen-2048          0.232 ± 0.003M/s (drops 0.000 ± 0.000M/s)
    strnlen-2048         0.403 ± 0.005M/s (drops 0.000 ± 0.000M/s)
    strlen-4095          0.151 ± 0.001M/s (drops 0.000 ± 0.000M/s)
    strnlen-4095         0.362 ± 0.005M/s (drops 0.000 ± 0.000M/s)

    strstr/strnstr
    ==============
    strstr-8             0.452 ± 0.005M/s (drops 0.000 ± 0.000M/s)
    strnstr-8            0.442 ± 0.006M/s (drops 0.000 ± 0.000M/s)
    strstr-64            0.390 ± 0.004M/s (drops 0.000 ± 0.000M/s)
    strnstr-64           0.400 ± 0.004M/s (drops 0.000 ± 0.000M/s)
    strstr-512           0.228 ± 0.003M/s (drops 0.000 ± 0.000M/s)
    strnstr-512          0.256 ± 0.002M/s (drops 0.000 ± 0.000M/s)
    strstr-2048          0.095 ± 0.001M/s (drops 0.000 ± 0.000M/s)
    strnstr-2048         0.113 ± 0.001M/s (drops 0.000 ± 0.000M/s)
    strstr-4095          0.052 ± 0.001M/s (drops 0.000 ± 0.000M/s)
    strnstr-4095         0.064 ± 0.001M/s (drops 0.000 ± 0.000M/s)

For strings longer than 64B, the unbounded variants are notably faster, having as much as 140% performance gain over the bounded variants (strncmp for strings of length 4095). The reason is that arm64 has an optimized implementation of strnlen in assembly which is also used inside strnstr.

On x86_64, which doesn't have any optimized string operations, there is still an observable difference in strlen/strnlen and strstr/strnstr, albeit much smaller than for arm64:

    strlen/strnlen
    ==============
    strlen-1             7.021 ± 0.036M/s (drops 0.000 ± 0.000M/s)
    strnlen-1            7.000 ± 0.038M/s (drops 0.000 ± 0.000M/s)
    strlen-8             6.837 ± 0.011M/s (drops 0.000 ± 0.000M/s)
    strnlen-8            6.832 ± 0.064M/s (drops 0.000 ± 0.000M/s)
    strlen-64            5.638 ± 0.026M/s (drops 0.000 ± 0.000M/s)
    strnlen-64           6.010 ± 0.034M/s (drops 0.000 ± 0.000M/s)
    strlen-512           3.322 ± 0.011M/s (drops 0.000 ± 0.000M/s)
    strnlen-512          3.449 ± 0.014M/s (drops 0.000 ± 0.000M/s)
    strlen-2048          1.390 ± 0.007M/s (drops 0.000 ± 0.000M/s)
    strnlen-2048         1.429 ± 0.003M/s (drops 0.000 ± 0.000M/s)
    strlen-4095          0.786 ± 0.003M/s (drops 0.000 ± 0.000M/s)
    strnlen-4095         0.803 ± 0.002M/s (drops 0.000 ± 0.000M/s)

    strstr/strnstr
    ==============
    strstr-8             6.031 ± 0.012M/s (drops 0.000 ± 0.000M/s)
    strnstr-8            6.322 ± 0.048M/s (drops 0.000 ± 0.000M/s)
    strstr-64            3.221 ± 0.054M/s (drops 0.000 ± 0.000M/s)
    strnstr-64           3.059 ± 0.025M/s (drops 0.000 ± 0.000M/s)
    strstr-512           0.734 ± 0.006M/s (drops 0.000 ± 0.000M/s)
    strnstr-512          0.849 ± 0.004M/s (drops 0.000 ± 0.000M/s)
    strstr-2048          0.220 ± 0.004M/s (drops 0.000 ± 0.000M/s)
    strnstr-2048         0.246 ± 0.002M/s (drops 0.000 ± 0.000M/s)
    strstr-4095          0.104 ± 0.000M/s (drops 0.000 ± 0.000M/s)
    strnstr-4095         0.122 ± 0.000M/s (drops 0.000 ± 0.000M/s)

The performance gain of the bounded variants on strings over 64B is 3%-6% for strlen/strnlen and 12%-18% for strstr/strnstr. The likely explanation is that the unbounded variants use __get_kernel_nofault instead of plain derefence which introduces some small overhead. This manifests mainly in the above functions as they iterate multiple strings (i.e. use __get_kernel_nofault more).

For the rest of the functions in the benchmark (strchr/strnchr and strchrnul/strnchrnul), the performance difference is negligable or within the bounds of a statistical error, with an exception of strchr/strnchr on arm64:

    strchr/strnchr
    ==============
    strchr-1             0.475 ± 0.010M/s (drops 0.000 ± 0.000M/s)
    strnchr-1            0.469 ± 0.008M/s (drops 0.000 ± 0.000M/s)
    strchr-8             0.448 ± 0.011M/s (drops 0.000 ± 0.000M/s)
    strnchr-8            0.472 ± 0.006M/s (drops 0.000 ± 0.000M/s)
    strchr-64            0.432 ± 0.010M/s (drops 0.000 ± 0.000M/s)
    strnchr-64           0.445 ± 0.008M/s (drops 0.000 ± 0.000M/s)
    strchr-512           0.308 ± 0.003M/s (drops 0.000 ± 0.000M/s)
    strnchr-512          0.330 ± 0.005M/s (drops 0.000 ± 0.000M/s)
    strchr-2048          0.156 ± 0.002M/s (drops 0.000 ± 0.000M/s)
    strnchr-2048         0.186 ± 0.003M/s (drops 0.000 ± 0.000M/s)
    strchr-4095          0.094 ± 0.001M/s (drops 0.000 ± 0.000M/s)
    strnchr-4095         0.115 ± 0.004M/s (drops 0.000 ± 0.000M/s)

Here, I'm not sure what the reason for the performance benefit is, possibly a combination of compiler optimizations and __get_kernel_nofault overhead.

---
 tools/testing/selftests/bpf/Makefile          |   2 +
 tools/testing/selftests/bpf/bench.c           |  21 ++
 .../bpf/benchs/bench_string_kfuncs.c          | 259 ++++++++++++++++++
 .../bpf/benchs/run_bench_string_kfuncs.sh     |  34 +++
 .../selftests/bpf/progs/string_kfuncs_bench.c |  88 ++++++
 5 files changed, 404 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_string_kfuncs.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_string_kfuncs.sh
 create mode 100644 tools/testing/selftests/bpf/progs/string_kfuncs_bench.c
tools/testing/selftests/bpf/Makefile +2 -0
index ca41d47d4ba6..d04f7e78c8ab 100644
@@ -813,6 +813,7 @@ $(OUTPUT)/bench_local_storage_create.o: $(OUTPUT)/bench_local_storage_create.ske
 $(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_string_kfuncs.o: $(OUTPUT)/string_kfuncs_bench.skel.h
 $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ)
 $(OUTPUT)/bench: LDLIBS += -lm
 $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -833,6 +834,7 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \
 		 $(OUTPUT)/bench_local_storage_create.o \
 		 $(OUTPUT)/bench_htab_mem.o \
 		 $(OUTPUT)/bench_bpf_crypto.o \
+		 $(OUTPUT)/bench_string_kfuncs.o \
 		 #
 	$(call msg,BINARY,,$@)
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
tools/testing/selftests/bpf/bench.c +21 -0
index 1bd403a5ef7b..5aa7f63436f6 100644
@@ -283,6 +283,7 @@ extern struct argp bench_local_storage_create_argp;
 extern struct argp bench_htab_mem_argp;
 extern struct argp bench_trigger_batch_argp;
 extern struct argp bench_crypto_argp;
+extern struct argp bench_string_kfuncs_argp;
 
 static const struct argp_child bench_parsers[] = {
 	{ &bench_ringbufs_argp, 0, "Ring buffers benchmark", 0 },
@@ -297,6 +298,7 @@ static const struct argp_child bench_parsers[] = {
 	{ &bench_htab_mem_argp, 0, "hash map memory benchmark", 0 },
 	{ &bench_trigger_batch_argp, 0, "BPF triggering benchmark", 0 },
 	{ &bench_crypto_argp, 0, "bpf crypto benchmark", 0 },
+	{ &bench_string_kfuncs_argp, 0, "string kfuncs benchmark", 0 },
 	{},
 };
 
@@ -550,6 +552,16 @@ extern const struct bench bench_htab_mem;
 extern const struct bench bench_crypto_encrypt;
 extern const struct bench bench_crypto_decrypt;
 
+/* string kfunc benchmarks */
+extern const struct bench bench_string_kfuncs_strlen;
+extern const struct bench bench_string_kfuncs_strnlen;
+extern const struct bench bench_string_kfuncs_strchr;
+extern const struct bench bench_string_kfuncs_strnchr;
+extern const struct bench bench_string_kfuncs_strchrnul;
+extern const struct bench bench_string_kfuncs_strnchrnul;
+extern const struct bench bench_string_kfuncs_strstr;
+extern const struct bench bench_string_kfuncs_strnstr;
+
 static const struct bench *benchs[] = {
 	&bench_count_global,
 	&bench_count_local,
@@ -609,6 +621,15 @@ static const struct bench *benchs[] = {
 	&bench_htab_mem,
 	&bench_crypto_encrypt,
 	&bench_crypto_decrypt,
+	/* string kfuncs */
+	&bench_string_kfuncs_strlen,
+	&bench_string_kfuncs_strnlen,
+	&bench_string_kfuncs_strchr,
+	&bench_string_kfuncs_strnchr,
+	&bench_string_kfuncs_strchrnul,
+	&bench_string_kfuncs_strnchrnul,
+	&bench_string_kfuncs_strstr,
+	&bench_string_kfuncs_strnstr,
 };
 
 static void find_benchmark(void)
tools/testing/selftests/bpf/benchs/bench_string_kfuncs.c new file +259 -0

259 lines not on this page · raw message

tools/testing/selftests/bpf/benchs/run_bench_string_kfuncs.sh new file +34 -0
new file mode 100755
index 000000000000..5e635681cd85
@@ -0,0 +1,34 @@
+#!/bin/bash
+# SPDX-License-Identifier: GPL-2.0
+
+source ./benchs/run_common.sh
+
+set -eufo pipefail
+
+header "strlen/strnlen"
+for s in 1 8 64 512 2048 4095; do
+	for b in strlen strnlen; do
+		summarize ${b}-${s} "$($RUN_BENCH --str-len=$s string-kfuncs-${b})"
+	done
+done
+
+header "strchr/strnchr"
+for s in 1 8 64 512 2048 4095; do
+	for b in strchr strnchr; do
+		summarize ${b}-${s} "$($RUN_BENCH --str-len=$s string-kfuncs-${b})"
+	done
+done
+
+header "strchrnul/strnchrnul"
+for s in 1 8 64 512 2048 4095; do
+	for b in strchrnul strnchrnul; do
+		summarize ${b}-${s} "$($RUN_BENCH --str-len=$s string-kfuncs-${b})"
+	done
+done
+
+header "strstr/strnstr"
+for s in 8 64 512 2048 4095; do
+	for b in strstr strnstr; do
+		summarize ${b}-${s} "$($RUN_BENCH --str-len=$s string-kfuncs-${b})"
+	done
+done
tools/testing/selftests/bpf/progs/string_kfuncs_bench.c new file +88 -0

88 lines not on this page · raw message

Signature · 1 line
2.48.1
#7 lore raw

Re: [PATCH bpf-next v3 2/3] selftests/bpf: Add tests for string kfuncs

In reply to Viktor Malik
Quoted 44 lines · Viktor Malik

The tests use the RUN_TESTS helper which executes BPF programs with BPF_PROG_TEST_RUN and check for the expected return value.

---
 .../selftests/bpf/prog_tests/string_kfuncs.c  | 10 ++++
 .../selftests/bpf/progs/string_kfuncs.c       | 58 +++++++++++++++++++
 2 files changed, 68 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/string_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/string_kfuncs.c
tools/testing/selftests/bpf/prog_tests/string_kfuncs.c new file +10 -0
new file mode 100644
index 000000000000..79dab172eb92
@@ -0,0 +1,10 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (C) 2025 Red Hat, Inc.*/
+#include <test_progs.h>
+#include "string_kfuncs.skel.h"
+
+void test_string_kfuncs(void)
+{
+	RUN_TESTS(string_kfuncs);
+}
+
tools/testing/selftests/bpf/progs/string_kfuncs.c new file +10 -0
new file mode 100644
index 000000000000..9fb1ed5ba1fa
@@ -0,0 +1,58 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (C) 2025 Red Hat, Inc.*/
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+int bpf_strcmp(const char *cs, const char *ct) __ksym;
+char *bpf_strchr(const char *s, int c) __ksym;
+char *bpf_strchrnul(const char *s, int c) __ksym;
+char *bpf_strnchr(void *s, u32 s__sz, int c) __ksym;

tools/testing/selftests/bpf/progs/string_kfuncs.c line 20

Quoted 10 lines
tools/testing/selftests/bpf/progs/string_kfuncs.c new file +10 -0
+char *bpf_strnchrnul(void *s, u32 s__sz, int c) __ksym;
+char *bpf_strrchr(const char *s, int c) __ksym;
+size_t bpf_strlen(const char *s) __ksym;
+size_t bpf_strnlen(void *s, u32 s__sz) __ksym;
+size_t bpf_strspn(const char *s, const char *accept) __ksym;
+size_t bpf_strcspn(const char *s, const char *reject) __ksym;
+char *bpf_strpbrk(const char *cs, const char *ct) __ksym;
+char *bpf_strstr(const char *s1, const char *s2) __ksym;
+char *bpf_strstr(const char *s1, const char *s2) __ksym;
+char *bpf_strnstr(void *s1, u32 s1__sz, void *s2, u32 s2__sz) __ksym;

hi,
I don't think above declarations are necessary, it should be all in vmlinux.h already

jirka

Quoted 41 lines
tools/testing/selftests/bpf/progs/string_kfuncs.c new file +38 -0
+
+char str1[] = "hello world";
+char str2[] = "hello";
+char str3[] = "world";
+char str4[] = "abc";
+char str5[] = "";
+
+#define __test(retval) SEC("syscall") __success __retval(retval)
+
+__test(0) int test_strcmp_eq(void *ctx) { return bpf_strcmp(str1, str1); }
+__test(1) int test_strcmp_neq(void *ctx) { return bpf_strcmp(str1, str2); }
+__test(1) int test_strchr_found(void *ctx) { return bpf_strchr(str1, 'e') - str1; }
+__test(11) int test_strchr_null(void *ctx) { return bpf_strchr(str1, '\0') - str1; }
+__test(0) u64 test_strchr_notfound(void *ctx) { return (u64)bpf_strchr(str1, 'x'); }
+__test(1) int test_strchrnul_found(void *ctx) { return bpf_strchrnul(str1, 'e') - str1; }
+__test(11) int test_strchrnul_notfound(void *ctx) { return bpf_strchrnul(str1, 'x') - str1; }
+__test(1) int test_strnchr_found(void *ctx) { return bpf_strnchr(str1, 5, 'e') - str1; }
+__test(11) int test_strnchr_null(void *ctx) { return bpf_strnchr(str1, 12, '\0') - str1; }
+__test(0) u64 test_strnchr_notfound(void *ctx) { return (u64)bpf_strnchr(str1, 5, 'w'); }
+__test(1) int test_strnchrnul_found(void *ctx) { return bpf_strnchrnul(str1, 5, 'e') - str1; }
+__test(11) int test_strnchrnul_notfound(void *ctx) { return bpf_strnchrnul(str1, 12, 'x') - str1; }
+__test(9) int test_strrchr_found(void *ctx) { return bpf_strrchr(str1, 'l') - str1; }
+__test(0) u64 test_strrchr_notfound(void *ctx) { return (u64)bpf_strrchr(str1, 'x'); }
+__test(11) size_t test_strlen(void *ctx) { return bpf_strlen(str1); }
+__test(11) size_t test_strnlen(void *ctx) { return bpf_strnlen(str1, 12); }
+__test(5) size_t test_strspn(void *ctx) { return bpf_strspn(str1, str2); }
+__test(2) size_t test_strcspn(void *ctx) { return bpf_strcspn(str1, str3); }
+__test(2) int test_strpbrk_found(void *ctx) { return bpf_strpbrk(str1, str3) - str1; }
+__test(0) u64 test_strpbrk_notfound(void *ctx) { return (u64)bpf_strpbrk(str1, str4); }
+__test(6) int test_strstr_found(void *ctx) { return bpf_strstr(str1, str3) - str1; }
+__test(0) u64 test_strstr_notfound(void *ctx) { return (u64)bpf_strstr(str1, str4); }
+__test(0) int test_strstr_empty(void *ctx) { return bpf_strstr(str1, str5) - str1; }
+__test(6) int test_strnstr_found(void *ctx) { return bpf_strnstr(str1, 12, str3, 6) - str1; }
+__test(0) u64 test_strnstr_unsafe(void *ctx) { return (u64)bpf_strnstr(str1, 5, str3, 5); }
+__test(0) u64 test_strnstr_notfound(void *ctx) { return (u64)bpf_strnstr(str1, 12, str4, 4); }
+__test(0) int test_strnstr_empty(void *ctx) { return bpf_strnstr(str1, 5, str5, 1) - str1; }
+
+char _license[] SEC("license") = "GPL";
Signature · 1 line
2.48.1
#2 lore raw
In reply to Viktor Malik
Quoted 28 lines · Viktor Malik

String operations are commonly used so this exposes the most common ones to BPF programs. For now, we limit ourselves to operations which do not copy memory around.

Unfortunately, most in-kernel implementations assume that strings are %NUL-terminated, which is not necessarily true, and therefore we cannot use them directly in BPF context. So, we use distinct approaches for bounded and unbounded variants of string operations:

- Unbounded variants are open-coded with using __get_kernel_nofault instead of plain dereference to make them safe.

- Bounded variants use params with the __sz suffix so safety is assured by the verifier and we can use the in-kernel (potentially optimized) functions.

---
 kernel/bpf/helpers.c | 299 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 299 insertions(+)
kernel/bpf/helpers.c +0 -0
index 5449756ba102..6f6af4289cd0 100644

kernel/bpf/helpers.c line 4

Quoted 4 lines
kernel/bpf/helpers.c +1 -0
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0-only
 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
  */
+#include "linux/uaccess.h"

<> should be used?

Quoted 20 lines
kernel/bpf/helpers.c +13 -0
 #include <linux/bpf.h>
 #include <linux/btf.h>
 #include <linux/bpf-cgroup.h>
@@ -3193,6 +3194,291 @@ __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag)
        local_irq_restore(*flags__irq_flag);
 }
 
+/* Kfuncs for string operations.
+ *
+ * Since strings are not necessarily %NUL-terminated, we cannot directly call
+ * in-kernel implementations. Instead, unbounded variants are open-coded with
+ * using __get_kernel_nofault instead of plain dereference to make them safe.
+ * Bounded variants use params with the __sz suffix so safety is assured by the
+ * verifier and we can use the in-kernel (potentially optimized) functions.
+ */
+
+/**
+ * bpf_strcmp - Compare two strings
+ * @cs: One string
+ * @ct: Another string

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3219

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+ */
+__bpf_kfunc int bpf_strcmp(const char *cs, const char *ct)
+{
+       int i = 0, ret = 0;
+       char c1, c2;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c1, cs++, char, cs_out);
+               __get_kernel_nofault(&c2, ct++, char, ct_out);

nit: should we avoid passing increment statements into macro? It's succinct and all, but we lose nothing by having cs++; ct++; at the end of while loop, no?

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+               if (c1 != c2) {
+                       ret = c1 < c2 ? -1 : 1;
+                       goto out;
+               }
+               if (!c1)
+                       goto out;

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3235

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       }
+cs_out:
+       ret = -1;
+       goto out;
+ct_out:
+       ret = 1;
+out:
+       pagefault_enable();
+       return ret;
+}

Given valid values are only -1, 0, and 1, should we return -EFAULT when one or the other string can't be fetched?

Yes, users that don't care will treat -EFAULT as the first string is smaller than the second, but that's what you have anyways. But having -EFAULT is still useful, IMO. We can also return -E2BIG if we reach i == XATTR_SIZE_MAX situation, no?

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3245

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+
+/**
+ * bpf_strchr - Find the first occurrence of a character in a string
+ * @s: The string to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strchr(const char *s, int c)

if we do int -> char here, something breaks?

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3258

Quoted 13 lines
kernel/bpf/helpers.c +13 -0
+{
+       char *ret = NULL;
+       int i = 0;
+       char sc;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&sc, s, char, out);
+               if (sc == (char)c) {
+                       ret = (char *)s;
+                       break;
+               }
+               if (sc == '\0')

not very consistent with bpf_strcmp() implementation where you just did !c1 for the same. FWIW, when dealing with string characters I like sc == '\0' better, but regardless let's be consistent, at least.

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3260

Quoted 2 lines
kernel/bpf/helpers.c +2 -0
+                       break;
+               s++;

It's like bpf_strcmp and bpf_strchr were written by two different people, stylistically :)

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3233

Quoted 3 lines
kernel/bpf/helpers.c +3 -0
+       }
+out:
+       pagefault_enable();

how about we

DEFINE_LOCK_GUARD_0(pagefault, pagefault_disable(), pagefault_enable())

like we do for preempt_{disable,enable}() and simplify all the implementations significantly?

Quoted 9 lines
kernel/bpf/helpers.c +9 -0
+       return ret;
+}
+
+/**
+ * bpf_strchrnul - Find and return a character in a string, or end of string
+ * @s: The string to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to first occurrence of 'c' in s. If c is not found, then

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3282

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+ * return a pointer to the null byte at the end of s.
+ */
+__bpf_kfunc char *bpf_strchrnul(const char *s, int c)
+{
+       char *ret = NULL;
+       int i = 0;
+       char sc;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {

erm... for (i = 0; i < XATTR_SIZE_MAX; i++, s++) ?

what advantage does while() form provide? same question for lots of other functions. for() is meant for loops like this, no?

Quoted 12 lines
kernel/bpf/helpers.c +12 -0
+               __get_kernel_nofault(&sc, s, char, out);
+               if (sc == '\0' || sc == (char)c) {
+                       ret = (char *)s;
+                       break;
+               }
+               s++;
+       }
+out:
+       pagefault_enable();
+       return ret;
+}
+

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3304

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+/**
+ * bpf_strnchr - Find a character in a length limited string
+ * @s: The string to be searched
+ * @s__sz: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strnchr(void *s, u32 s__sz, int c)

I'm a bit on the fence here. I can see cases where s would be some string somewhere (not "trusted" by verifier, because I did BPF CO-RE based casts, etc). Also I can see how s__sz is non-const known at runtime only.

I think the performance argument is much less of a priority compared to the ability to use the helper in a much wider set of cases. WDYT? Maybe let's just have __get_kernel_nofault() for everything?

If performance is truly that important, we can later have an optimization in which we detect constant size and "guaranteed" lifetime and validity of s, and use optimized strnchr() implementation?

But I'd start with a safe and generic __get_kernel_nofault() way for sure.

Quoted 15 lines
kernel/bpf/helpers.c +15 -0
+{
+       return strnchr(s, s__sz, c);
+}
+
+/**
+ * bpf_strnchrnul - Find and return a character in a length limited string,
+ * or end of string
+ * @s: The string to be searched
+ * @s__sz: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to the first occurrence of 'c' in s. If c is not found,
+ * then return a pointer to the last character of the string.
+ */
+__bpf_kfunc char *bpf_strnchrnul(void *s, u32 s__sz, int c)

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3329

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+{
+       return strnchrnul(s, s__sz, c);
+}
+
+/**
+ * bpf_strrchr - Find the last occurrence of a character in a string
+ * @s: The string to be searched
+ * @c: The character to search for
+ */
+__bpf_kfunc char *bpf_strrchr(const char *s, int c)

const char * return? we won't (well, shouldn't!) allow writing into it from the BPF program.

Quoted 45 lines
kernel/bpf/helpers.c +45 -0
+{
+       char *ret = NULL;
+       int i = 0;
+       char sc;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&sc, s, char, out);
+               if (sc == '\0')
+                       break;
+               if (sc == (char)c)
+                       ret = (char *)s;
+               s++;
+       }
+out:
+       pagefault_enable();
+       return (char *)ret;
+}
+
+__bpf_kfunc size_t bpf_strlen(const char *s)
+{
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0')
+                       break;
+               i++;
+       }
+out:
+       pagefault_enable();
+       return i;
+}
+
+__bpf_kfunc size_t bpf_strnlen(void *s, u32 s__sz)
+{
+       return strnlen(s, s__sz);
+}
+
+/**
+ * bpf_strspn - Calculate the length of the initial substring of @s which only contain letters in @accept
+ * @s: The string to be searched
+ * @accept: The string to search for

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3384

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+ */
+__bpf_kfunc size_t bpf_strspn(const char *s, const char *accept)
+{
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0' || !bpf_strchr(accept, c))

hm... so s is untrusted/unsafe, but accept is? How should verifier make a distinction? It's const char * in the signature, so what makes one more safe than the other?

Quoted 26 lines
kernel/bpf/helpers.c +26 -0
+                       break;
+               i++;
+       }
+out:
+       pagefault_enable();
+       return i;
+}
+
+/**
+ * strcspn - Calculate the length of the initial substring of @s which does not contain letters in @reject
+ * @s: The string to be searched
+ * @reject: The string to avoid
+ */
+__bpf_kfunc size_t bpf_strcspn(const char *s, const char *reject)
+{
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0' || bpf_strchr(reject, c))
+                       break;
+               i++;
+       }
+out:

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3420

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       pagefault_enable();
+       return i;
+}
+
+/**
+ * bpf_strpbrk - Find the first occurrence of a set of characters
+ * @cs: The string to be searched
+ * @ct: The characters to search for
+ */
+__bpf_kfunc char *bpf_strpbrk(const char *cs, const char *ct)

wouldn't this be cs + bpf_strcspn(cs, ct)?

Quoted 31 lines
kernel/bpf/helpers.c +31 -0
+{
+       char *ret = NULL;
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, cs, char, out);
+               if (c == '\0')
+                       break;
+               if (bpf_strchr(ct, c)) {
+                       ret = (char *)cs;
+                       break;
+               }
+               cs++;
+       }
+out:
+       pagefault_enable();
+       return ret;
+}
+
+/**
+ * bpf_strstr - Find the first substring in a %NUL terminated string
+ * @s1: The string to be searched
+ * @s2: The string to search for
+ */
+__bpf_kfunc char *bpf_strstr(const char *s1, const char *s2)
+{
+       size_t l1, l2;
+
+       l2 = bpf_strlen(s2);

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3461

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       if (!l2)
+               return (char *)s1;
+       l1 = bpf_strlen(s1);
+       while (l1 >= l2) {
+               l1--;
+               if (!memcmp(s1, s2, l2))
+                       return (char *)s1;
+               s1++;
+       }
+       return NULL;

no __get_kernel_nofault() anymore?

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+}
+
+/**
+ * bpf_strnstr - Find the first substring in a length-limited string
+ * @s1: The string to be searched
+ * @s1__sz: The size of @s1
+ * @s2: The string to search for
+ * @s2__sz: The size of @s2
+ */
+__bpf_kfunc char *bpf_strnstr(void *s1, u32 s1__sz, void *s2, u32 s2__sz)

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3481

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+{
+       /* strnstr() uses strlen() to get the length of s2. Since this is not
+        * safe in BPF context for non-%NUL-terminated strings, use strnlen
+        * first to make it safe.
+        */
+       if (strnlen(s2, s2__sz) == s2__sz)
+               return NULL;
+       return strnstr(s1, s2, s1__sz);
+}
+

we have to assume that the string will change from under us, so any algorithm that does bpf_strlen/strlen/strnlen and then relies on that length to be true seems fishy...

pw-bot: cr

Quoted 26 lines
kernel/bpf/helpers.c +13 -1
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -3293,6 +3579,19 @@ BTF_ID_FLAGS(func, bpf_iter_kmem_cache_next, KF_ITER_NEXT | KF_RET_NULL | KF_SLE
 BTF_ID_FLAGS(func, bpf_iter_kmem_cache_destroy, KF_ITER_DESTROY | KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_local_irq_save)
 BTF_ID_FLAGS(func, bpf_local_irq_restore)
+BTF_ID_FLAGS(func, bpf_strcmp);
+BTF_ID_FLAGS(func, bpf_strchr);
+BTF_ID_FLAGS(func, bpf_strchrnul);
+BTF_ID_FLAGS(func, bpf_strnchr);
+BTF_ID_FLAGS(func, bpf_strnchrnul);
+BTF_ID_FLAGS(func, bpf_strrchr);
+BTF_ID_FLAGS(func, bpf_strlen);
+BTF_ID_FLAGS(func, bpf_strnlen);
+BTF_ID_FLAGS(func, bpf_strspn);
+BTF_ID_FLAGS(func, bpf_strcspn);
+BTF_ID_FLAGS(func, bpf_strpbrk);
+BTF_ID_FLAGS(func, bpf_strstr);
+BTF_ID_FLAGS(func, bpf_strnstr);
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
--

2.48.1

#3 lore raw
Quoted 24 lines · Andrii Nakryiko
Quoted 23 lines · Viktor Malik

String operations are commonly used so this exposes the most common ones to BPF programs. For now, we limit ourselves to operations which do not copy memory around.

Unfortunately, most in-kernel implementations assume that strings are %NUL-terminated, which is not necessarily true, and therefore we cannot use them directly in BPF context. So, we use distinct approaches for bounded and unbounded variants of string operations:

- Unbounded variants are open-coded with using __get_kernel_nofault instead of plain dereference to make them safe.

- Bounded variants use params with the __sz suffix so safety is assured by the verifier and we can use the in-kernel (potentially optimized) functions.

---
 kernel/bpf/helpers.c | 299 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 299 insertions(+)
Quoted 11 lines

kernel/bpf/helpers.c line 4

Quoted 9 lines
kernel/bpf/helpers.c +1 -0
index 5449756ba102..6f6af4289cd0 100644
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0-only
 /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
  */
+#include "linux/uaccess.h"

<> should be used?

Yes.

Quoted 27 lines
Quoted 27 lines
kernel/bpf/helpers.c +19 -0
 #include <linux/bpf.h>
 #include <linux/btf.h>
 #include <linux/bpf-cgroup.h>
@@ -3193,6 +3194,291 @@ __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag)
        local_irq_restore(*flags__irq_flag);
 }
 
+/* Kfuncs for string operations.
+ *
+ * Since strings are not necessarily %NUL-terminated, we cannot directly call
+ * in-kernel implementations. Instead, unbounded variants are open-coded with
+ * using __get_kernel_nofault instead of plain dereference to make them safe.
+ * Bounded variants use params with the __sz suffix so safety is assured by the
+ * verifier and we can use the in-kernel (potentially optimized) functions.
+ */
+
+/**
+ * bpf_strcmp - Compare two strings
+ * @cs: One string
+ * @ct: Another string
+ */
+__bpf_kfunc int bpf_strcmp(const char *cs, const char *ct)
+{
+       int i = 0, ret = 0;
+       char c1, c2;
+
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3219

Quoted 4 lines
kernel/bpf/helpers.c +4 -0
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c1, cs++, char, cs_out);
+               __get_kernel_nofault(&c2, ct++, char, ct_out);

nit: should we avoid passing increment statements into macro? It's succinct and all, but we lose nothing by having cs++; ct++; at the end of while loop, no?

That's probably a good idea. It shouldn't be a problem having those increments at the end of the loop so let me update it.

Quoted 21 lines
Quoted 7 lines
kernel/bpf/helpers.c +6 -0
+               if (c1 != c2) {
+                       ret = c1 < c2 ? -1 : 1;
+                       goto out;
+               }
+               if (!c1)
+                       goto out;

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3235

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       }
+cs_out:
+       ret = -1;
+       goto out;
+ct_out:
+       ret = 1;
+out:
+       pagefault_enable();
+       return ret;
+}

Given valid values are only -1, 0, and 1, should we return -EFAULT when one or the other string can't be fetched?

Quoted 4 lines

Yes, users that don't care will treat -EFAULT as the first string is smaller than the second, but that's what you have anyways. But having -EFAULT is still useful, IMO. We can also return -E2BIG if we reach i == XATTR_SIZE_MAX situation, no?

I was a bit hesitant to make the semantics of bpf_strcmp different from strcmp. But the truth is that returning errors here may bring some value so if people are ok with that, I have no problem implementing your proposal.

But in such a case, I'd suggest that we do the same for the rest of the string kfuncs, too. That is, return -EINVAL if __get_kernel_nofault fails and -E2BIG if the string is longer than XATTR_SIZE_MAX, possibly wrapped in PTR_ERR when the kfunc returns a pointer. What do you think?

Quoted 13 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3245

Quoted 11 lines
kernel/bpf/helpers.c +10 -0
+
+/**
+ * bpf_strchr - Find the first occurrence of a character in a string
+ * @s: The string to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strchr(const char *s, int c)

if we do int -> char here, something breaks?

No, it shouldn't. IIUC the int comes from the original prototype of libc strchr and it's there solely for legacy purposes. Let's change it to char.

Quoted 20 lines
Quoted 4 lines
kernel/bpf/helpers.c +3 -0
+{
+       char *ret = NULL;
+       int i = 0;

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3258

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       char sc;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&sc, s, char, out);
+               if (sc == (char)c) {
+                       ret = (char *)s;
+                       break;
+               }
+               if (sc == '\0')

not very consistent with bpf_strcmp() implementation where you just did !c1 for the same. FWIW, when dealing with string characters I like sc == '\0' better, but regardless let's be consistent, at least.

Quoted 5 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3260

Quoted 2 lines
kernel/bpf/helpers.c +2 -0
+                       break;
+               s++;

It's like bpf_strcmp and bpf_strchr were written by two different people, stylistically :)

Yeah, the main reason here is that I've taken the implementations from lib/string.c so that's where these differences come from. But the truth is that the BPF kfuncs required quite a lot of changes so it's better to rewrite them even further and make them consistent among themselves. I'll have a look into it.

Quoted 11 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3233

Quoted 4 lines
kernel/bpf/helpers.c +3 -0
+       }
+out:
+       pagefault_enable();

how about we

DEFINE_LOCK_GUARD_0(pagefault, pagefault_disable(), pagefault_enable())

like we do for preempt_{disable,enable}() and simplify all the implementations significantly?

That's neat, I didn't know it. It will a bit more tricky to use here as __get_kernel_nofault still requires a label but we should at least be able to get rid of pagefault_{disable,enable}() in each function.

Quoted 23 lines
Quoted 10 lines
kernel/bpf/helpers.c +9 -0
+       return ret;
+}
+
+/**
+ * bpf_strchrnul - Find and return a character in a string, or end of string
+ * @s: The string to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to first occurrence of 'c' in s. If c is not found, then

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3282

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+ * return a pointer to the null byte at the end of s.
+ */
+__bpf_kfunc char *bpf_strchrnul(const char *s, int c)
+{
+       char *ret = NULL;
+       int i = 0;
+       char sc;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {

erm... for (i = 0; i < XATTR_SIZE_MAX; i++, s++) ?

Quoted 2 lines

what advantage does while() form provide? same question for lots of other functions. for() is meant for loops like this, no?

Yes, obviously for() is better here, I'll use it.

Quoted 33 lines
Quoted 13 lines
kernel/bpf/helpers.c +12 -0
+               __get_kernel_nofault(&sc, s, char, out);
+               if (sc == '\0' || sc == (char)c) {
+                       ret = (char *)s;
+                       break;
+               }
+               s++;
+       }
+out:
+       pagefault_enable();
+       return ret;
+}
+

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3304

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+/**
+ * bpf_strnchr - Find a character in a length limited string
+ * @s: The string to be searched
+ * @s__sz: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strnchr(void *s, u32 s__sz, int c)

I'm a bit on the fence here. I can see cases where s would be some string somewhere (not "trusted" by verifier, because I did BPF CO-RE based casts, etc). Also I can see how s__sz is non-const known at runtime only.

I think the performance argument is much less of a priority compared to the ability to use the helper in a much wider set of cases. WDYT? Maybe let's just have __get_kernel_nofault() for everything?

Quoted 6 lines

If performance is truly that important, we can later have an optimization in which we detect constant size and "guaranteed" lifetime and validity of s, and use optimized strnchr() implementation?

But I'd start with a safe and generic __get_kernel_nofault() way for sure.

Ok, that makes sense. I didn't realize that with this prototype, we're eliminating a number of uses-cases and I agree that it's more important than performance.

Also it turned out that the bounded string functions are seldom optimized on arches and therefore the performance benefit is minimal (the only real case is strnlen on few arches like arm64).

So let's turn everything to generic __get_kernel_nofault variants for now. We can think about optimization later, it would be much better if we could detect situations when the kernel implementaion can be used even for the unbounded functions. There, the performance gain would be seen on much more functions.

Quoted 21 lines
Quoted 21 lines
kernel/bpf/helpers.c +20 -0
+{
+       return strnchr(s, s__sz, c);
+}
+
+/**
+ * bpf_strnchrnul - Find and return a character in a length limited string,
+ * or end of string
+ * @s: The string to be searched
+ * @s__sz: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Returns pointer to the first occurrence of 'c' in s. If c is not found,
+ * then return a pointer to the last character of the string.
+ */
+__bpf_kfunc char *bpf_strnchrnul(void *s, u32 s__sz, int c)
+{
+       return strnchrnul(s, s__sz, c);
+}
+
+/**
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3329

Quoted 5 lines
kernel/bpf/helpers.c +5 -0
+ * bpf_strrchr - Find the last occurrence of a character in a string
+ * @s: The string to be searched
+ * @c: The character to search for
+ */
+__bpf_kfunc char *bpf_strrchr(const char *s, int c)

const char * return? we won't (well, shouldn't!) allow writing into it from the BPF program.

Yes, agreed.

Quoted 52 lines
Quoted 52 lines
kernel/bpf/helpers.c +51 -0
+{
+       char *ret = NULL;
+       int i = 0;
+       char sc;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&sc, s, char, out);
+               if (sc == '\0')
+                       break;
+               if (sc == (char)c)
+                       ret = (char *)s;
+               s++;
+       }
+out:
+       pagefault_enable();
+       return (char *)ret;
+}
+
+__bpf_kfunc size_t bpf_strlen(const char *s)
+{
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0')
+                       break;
+               i++;
+       }
+out:
+       pagefault_enable();
+       return i;
+}
+
+__bpf_kfunc size_t bpf_strnlen(void *s, u32 s__sz)
+{
+       return strnlen(s, s__sz);
+}
+
+/**
+ * bpf_strspn - Calculate the length of the initial substring of @s which only contain letters in @accept
+ * @s: The string to be searched
+ * @accept: The string to search for
+ */
+__bpf_kfunc size_t bpf_strspn(const char *s, const char *accept)
+{
+       int i = 0;
+       char c;
+
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3384

Quoted 4 lines
kernel/bpf/helpers.c +4 -0
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0' || !bpf_strchr(accept, c))

hm... so s is untrusted/unsafe, but accept is? How should verifier make a distinction? It's const char * in the signature, so what makes one more safe than the other?

accept is untrusted as well, that's why bpf_strchr is used instead of strchr. Or am I missing something?

Quoted 31 lines
Quoted 31 lines
kernel/bpf/helpers.c +30 -0
+                       break;
+               i++;
+       }
+out:
+       pagefault_enable();
+       return i;
+}
+
+/**
+ * strcspn - Calculate the length of the initial substring of @s which does not contain letters in @reject
+ * @s: The string to be searched
+ * @reject: The string to avoid
+ */
+__bpf_kfunc size_t bpf_strcspn(const char *s, const char *reject)
+{
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0' || bpf_strchr(reject, c))
+                       break;
+               i++;
+       }
+out:
+       pagefault_enable();
+       return i;
+}
+
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3420

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+/**
+ * bpf_strpbrk - Find the first occurrence of a set of characters
+ * @cs: The string to be searched
+ * @ct: The characters to search for
+ */
+__bpf_kfunc char *bpf_strpbrk(const char *cs, const char *ct)

wouldn't this be cs + bpf_strcspn(cs, ct)?

That's IMO correct, unless bpf_strcspn(cs, ct) == strlen(cs). Then it's NULL. But it's still a nicer implementation.

Quoted 36 lines
Quoted 36 lines
kernel/bpf/helpers.c +35 -0
+{
+       char *ret = NULL;
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, cs, char, out);
+               if (c == '\0')
+                       break;
+               if (bpf_strchr(ct, c)) {
+                       ret = (char *)cs;
+                       break;
+               }
+               cs++;
+       }
+out:
+       pagefault_enable();
+       return ret;
+}
+
+/**
+ * bpf_strstr - Find the first substring in a %NUL terminated string
+ * @s1: The string to be searched
+ * @s2: The string to search for
+ */
+__bpf_kfunc char *bpf_strstr(const char *s1, const char *s2)
+{
+       size_t l1, l2;
+
+       l2 = bpf_strlen(s2);
+       if (!l2)
+               return (char *)s1;
+       l1 = bpf_strlen(s1);
+       while (l1 >= l2) {
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3461

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+               l1--;
+               if (!memcmp(s1, s2, l2))
+                       return (char *)s1;
+               s1++;
+       }
+       return NULL;

no __get_kernel_nofault() anymore?

It's hidden inside bpf_strlen.

But I assume that the same as below applies (string possibly changing in between the bpf_strlen and memcmp calls) so we'll need a different implementation.

Quoted 17 lines
Quoted 17 lines
kernel/bpf/helpers.c +16 -0
+}
+
+/**
+ * bpf_strnstr - Find the first substring in a length-limited string
+ * @s1: The string to be searched
+ * @s1__sz: The size of @s1
+ * @s2: The string to search for
+ * @s2__sz: The size of @s2
+ */
+__bpf_kfunc char *bpf_strnstr(void *s1, u32 s1__sz, void *s2, u32 s2__sz)
+{
+       /* strnstr() uses strlen() to get the length of s2. Since this is not
+        * safe in BPF context for non-%NUL-terminated strings, use strnlen
+        * first to make it safe.
+        */
+       if (strnlen(s2, s2__sz) == s2__sz)
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3481

Quoted 4 lines
kernel/bpf/helpers.c +4 -0
+               return NULL;
+       return strnstr(s1, s2, s1__sz);
+}
+

we have to assume that the string will change from under us, so any algorithm that does bpf_strlen/strlen/strnlen and then relies on that length to be true seems fishy...

Hm, that's a good point, I didn't consider that. I'll think about a better implementation for bpf_strstr and bpf_strnstr.

Thanks a lot for the thourough review! I'll post v4 soon.

Viktor

Quoted 30 lines

pw-bot: cr

Quoted 26 lines
kernel/bpf/helpers.c +13 -1
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -3293,6 +3579,19 @@ BTF_ID_FLAGS(func, bpf_iter_kmem_cache_next, KF_ITER_NEXT | KF_RET_NULL | KF_SLE
 BTF_ID_FLAGS(func, bpf_iter_kmem_cache_destroy, KF_ITER_DESTROY | KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_local_irq_save)
 BTF_ID_FLAGS(func, bpf_local_irq_restore)
+BTF_ID_FLAGS(func, bpf_strcmp);
+BTF_ID_FLAGS(func, bpf_strchr);
+BTF_ID_FLAGS(func, bpf_strchrnul);
+BTF_ID_FLAGS(func, bpf_strnchr);
+BTF_ID_FLAGS(func, bpf_strnchrnul);
+BTF_ID_FLAGS(func, bpf_strrchr);
+BTF_ID_FLAGS(func, bpf_strlen);
+BTF_ID_FLAGS(func, bpf_strnlen);
+BTF_ID_FLAGS(func, bpf_strspn);
+BTF_ID_FLAGS(func, bpf_strcspn);
+BTF_ID_FLAGS(func, bpf_strpbrk);
+BTF_ID_FLAGS(func, bpf_strstr);
+BTF_ID_FLAGS(func, bpf_strnstr);
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
--

2.48.1

#4 lore raw
Quoted 26 lines · Viktor Malik
Quoted 24 lines · Andrii Nakryiko
Quoted 23 lines · Viktor Malik

String operations are commonly used so this exposes the most common ones to BPF programs. For now, we limit ourselves to operations which do not copy memory around.

Unfortunately, most in-kernel implementations assume that strings are %NUL-terminated, which is not necessarily true, and therefore we cannot use them directly in BPF context. So, we use distinct approaches for bounded and unbounded variants of string operations:

- Unbounded variants are open-coded with using __get_kernel_nofault instead of plain dereference to make them safe.

- Bounded variants use params with the __sz suffix so safety is assured by the verifier and we can use the in-kernel (potentially optimized) functions.

---
 kernel/bpf/helpers.c | 299 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 299 insertions(+)

[...]

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
kernel/bpf/helpers.c +5 -0
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c1, cs++, char, cs_out);
+               __get_kernel_nofault(&c2, ct++, char, ct_out);
Quoted 6 lines
Quoted 3 lines

nit: should we avoid passing increment statements into macro? It's succinct and all, but we lose nothing by having cs++; ct++; at the end of while loop, no?

That's probably a good idea. It shouldn't be a problem having those increments at the end of the loop so let me update it.

ok, thanks

Quoted 27 lines
Quoted 22 lines
Quoted 8 lines
kernel/bpf/helpers.c +6 -0
+               if (c1 != c2) {
+                       ret = c1 < c2 ? -1 : 1;
+                       goto out;
+               }
+               if (!c1)
+                       goto out;

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3235

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       }
+cs_out:
+       ret = -1;
+       goto out;
+ct_out:
+       ret = 1;
+out:
+       pagefault_enable();
+       return ret;
+}

Given valid values are only -1, 0, and 1, should we return -EFAULT when one or the other string can't be fetched?

Quoted 4 lines

Yes, users that don't care will treat -EFAULT as the first string is smaller than the second, but that's what you have anyways. But having -EFAULT is still useful, IMO. We can also return -E2BIG if we reach i == XATTR_SIZE_MAX situation, no?

Quoted 7 lines

I was a bit hesitant to make the semantics of bpf_strcmp different from strcmp. But the truth is that returning errors here may bring some value so if people are ok with that, I have no problem implementing your proposal.

But in such a case, I'd suggest that we do the same for the rest of the string kfuncs, too. That is, return -EINVAL if __get_kernel_nofault

-EFAULT, not -EINVAL

Quoted 2 lines

fails and -E2BIG if the string is longer than XATTR_SIZE_MAX, possibly wrapped in PTR_ERR when the kfunc returns a pointer. What do you think?

yep, makes sense. Unlike strcmp() and others, we do have an extra conditions as you mentioned (memory read faulting, too long/unbounded strings, etc), so I'd prefer if users were able to tell error condition from trustworthy result, yep

Quoted 15 lines
Quoted 14 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3245

Quoted 12 lines
kernel/bpf/helpers.c +10 -0
+
+/**
+ * bpf_strchr - Find the first occurrence of a character in a string
+ * @s: The string to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strchr(const char *s, int c)

if we do int -> char here, something breaks?

Quoted 4 lines

No, it shouldn't. IIUC the int comes from the original prototype of libc strchr and it's there solely for legacy purposes. Let's change it to char.

+1, I always found that int c in glibc confusing

Quoted 39 lines
Quoted 20 lines
Quoted 4 lines
kernel/bpf/helpers.c +3 -0
+{
+       char *ret = NULL;
+       int i = 0;

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3258

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+       char sc;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&sc, s, char, out);
+               if (sc == (char)c) {
+                       ret = (char *)s;
+                       break;
+               }
+               if (sc == '\0')

not very consistent with bpf_strcmp() implementation where you just did !c1 for the same. FWIW, when dealing with string characters I like sc == '\0' better, but regardless let's be consistent, at least.

Quoted 5 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+                       break;
+               s++;

It's like bpf_strcmp and bpf_strchr were written by two different people, stylistically :)

Yeah, the main reason here is that I've taken the implementations from lib/string.c so that's where these differences come from. But the truth is that the BPF kfuncs required quite a lot of changes so it's better to rewrite them even further and make them consistent among themselves. I'll have a look into it.

Quoted 7 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3233

Quoted 4 lines
kernel/bpf/helpers.c +3 -0
+       }
+out:
+       pagefault_enable();

how about we

Quoted 8 lines
Quoted 4 lines

DEFINE_LOCK_GUARD_0(pagefault, pagefault_disable(), pagefault_enable())

like we do for preempt_{disable,enable}() and simplify all the implementations significantly?

That's neat, I didn't know it. It will a bit more tricky to use here as __get_kernel_nofault still requires a label but we should at least be able to get rid of pagefault_{disable,enable}() in each function.

yep, we'll have:

err_out:

    return -EFAULT;

But the rest will be a clean loop and no pagefault_disable() clean ups, distracting from the main logic

[...]

Quoted 35 lines
Quoted 20 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3304

Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+/**
+ * bpf_strnchr - Find a character in a length limited string
+ * @s: The string to be searched
+ * @s__sz: The number of characters to be searched
+ * @c: The character to search for
+ *
+ * Note that the %NUL-terminator is considered part of the string, and can
+ * be searched for.
+ */
+__bpf_kfunc char *bpf_strnchr(void *s, u32 s__sz, int c)

I'm a bit on the fence here. I can see cases where s would be some string somewhere (not "trusted" by verifier, because I did BPF CO-RE based casts, etc). Also I can see how s__sz is non-const known at runtime only.

I think the performance argument is much less of a priority compared to the ability to use the helper in a much wider set of cases. WDYT? Maybe let's just have __get_kernel_nofault() for everything?

Quoted 6 lines

If performance is truly that important, we can later have an optimization in which we detect constant size and "guaranteed" lifetime and validity of s, and use optimized strnchr() implementation?

But I'd start with a safe and generic __get_kernel_nofault() way for sure.

Ok, that makes sense. I didn't realize that with this prototype, we're eliminating a number of uses-cases and I agree that it's more important than performance.

Also it turned out that the bounded string functions are seldom optimized on arches and therefore the performance benefit is minimal (the only real case is strnlen on few arches like arm64).

Quoted 5 lines

So let's turn everything to generic __get_kernel_nofault variants for now. We can think about optimization later, it would be much better if we could detect situations when the kernel implementaion can be used even for the unbounded functions. There, the performance gain would be seen on much more functions.

Let's leave it for the future, I suspect string routine performance will never be a real performance concert, as it will normally be a small part of otherwise much more expensive custom logic in BPF program. But we'll have an option to optimize, and that's all that matters. Generality beats performance for these APIs, though, so let's generalize first.

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
kernel/bpf/helpers.c +4 -0
+{
+       return strnchr(s, s__sz, c);
+}
+

[...]

Quoted 19 lines
Quoted 10 lines
Quoted 10 lines
kernel/bpf/helpers.c +10 -0
+/**
+ * bpf_strspn - Calculate the length of the initial substring of @s which only contain letters in @accept
+ * @s: The string to be searched
+ * @accept: The string to search for
+ */
+__bpf_kfunc size_t bpf_strspn(const char *s, const char *accept)
+{
+       int i = 0;
+       char c;
+
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3384

Quoted 4 lines
kernel/bpf/helpers.c +4 -0
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0' || !bpf_strchr(accept, c))

hm... so s is untrusted/unsafe, but accept is? How should verifier make a distinction? It's const char * in the signature, so what makes one more safe than the other?

Quoted 2 lines

accept is untrusted as well, that's why bpf_strchr is used instead of strchr. Or am I missing something?

I'm just asking how should verifier know this just looking at the prototype:

__bpf_kfunc size_t bpf_strspn(const char *s, const char *accept)

?

For the next revision, let's add a bunch more "negative cases", passing known-bad pointers/strings and checking -EFAULT and -E2BIG. These are very generic APIs, let's test this thoroughly: user instead of kernel pointers, unbounded/too long strings, just plain invalid pointers, etc.

Quoted 41 lines
Quoted 32 lines
Quoted 32 lines
kernel/bpf/helpers.c +30 -0
+                       break;
+               i++;
+       }
+out:
+       pagefault_enable();
+       return i;
+}
+
+/**
+ * strcspn - Calculate the length of the initial substring of @s which does not contain letters in @reject
+ * @s: The string to be searched
+ * @reject: The string to avoid
+ */
+__bpf_kfunc size_t bpf_strcspn(const char *s, const char *reject)
+{
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, s++, char, out);
+               if (c == '\0' || bpf_strchr(reject, c))
+                       break;
+               i++;
+       }
+out:
+       pagefault_enable();
+       return i;
+}
+
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3420

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+/**
+ * bpf_strpbrk - Find the first occurrence of a set of characters
+ * @cs: The string to be searched
+ * @ct: The characters to search for
+ */
+__bpf_kfunc char *bpf_strpbrk(const char *cs, const char *ct)

wouldn't this be cs + bpf_strcspn(cs, ct)?

Quoted 2 lines

That's IMO correct, unless bpf_strcspn(cs, ct) == strlen(cs). Then it's NULL. But it's still a nicer implementation.

ah, strlen() is problematic (though we can have __bpf_strcspn() returning both size_t and the actual character (as out parameter), to distinguish these situations, don't know. It will be more obvious while implementing if that makes sense or not (all those algorithms are pretty straightforward, so code reuse isn't really a big concern from my POV)

Quoted 46 lines
Quoted 37 lines
Quoted 37 lines
kernel/bpf/helpers.c +35 -0
+{
+       char *ret = NULL;
+       int i = 0;
+       char c;
+
+       pagefault_disable();
+       while (i++ < XATTR_SIZE_MAX) {
+               __get_kernel_nofault(&c, cs, char, out);
+               if (c == '\0')
+                       break;
+               if (bpf_strchr(ct, c)) {
+                       ret = (char *)cs;
+                       break;
+               }
+               cs++;
+       }
+out:
+       pagefault_enable();
+       return ret;
+}
+
+/**
+ * bpf_strstr - Find the first substring in a %NUL terminated string
+ * @s1: The string to be searched
+ * @s2: The string to search for
+ */
+__bpf_kfunc char *bpf_strstr(const char *s1, const char *s2)
+{
+       size_t l1, l2;
+
+       l2 = bpf_strlen(s2);
+       if (!l2)
+               return (char *)s1;
+       l1 = bpf_strlen(s1);
+       while (l1 >= l2) {
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3461

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+               l1--;
+               if (!memcmp(s1, s2, l2))
+                       return (char *)s1;
+               s1++;
+       }
+       return NULL;

no __get_kernel_nofault() anymore?

Quoted 6 lines

It's hidden inside bpf_strlen.

But I assume that the same as below applies (string possibly changing in between the bpf_strlen and memcmp calls) so we'll need a different implementation.

yep, assume the worst. The result might be invalid due to race (as in, we can report that string is found at position X, but a few nanoseconds later that's not true anymore), that's fine. But we shouldn't crash, loop forever, etc. As long as the result is correct in a non-changing string situation, we should be fine.

Quoted 26 lines
Quoted 17 lines
Quoted 17 lines
kernel/bpf/helpers.c +16 -0
+}
+
+/**
+ * bpf_strnstr - Find the first substring in a length-limited string
+ * @s1: The string to be searched
+ * @s1__sz: The size of @s1
+ * @s2: The string to search for
+ * @s2__sz: The size of @s2
+ */
+__bpf_kfunc char *bpf_strnstr(void *s1, u32 s1__sz, void *s2, u32 s2__sz)
+{
+       /* strnstr() uses strlen() to get the length of s2. Since this is not
+        * safe in BPF context for non-%NUL-terminated strings, use strnlen
+        * first to make it safe.
+        */
+       if (strnlen(s2, s2__sz) == s2__sz)
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3481

Quoted 4 lines
kernel/bpf/helpers.c +4 -0
+               return NULL;
+       return strnstr(s1, s2, s1__sz);
+}
+

we have to assume that the string will change from under us, so any algorithm that does bpf_strlen/strlen/strnlen and then relies on that length to be true seems fishy...

Quoted 5 lines

Hm, that's a good point, I didn't consider that. I'll think about a better implementation for bpf_strstr and bpf_strnstr.

Thanks a lot for the thourough review! I'll post v4 soon.

thanks, let's be a bit more paranoid and add some negative tests while at it

Quoted 33 lines

Viktor

Quoted 30 lines

pw-bot: cr

Quoted 26 lines

__bpf_kfunc_end_defs();

BTF_KFUNCS_START(generic_btf_ids)

kernel/bpf/helpers.c +13 -1
@@ -3293,6 +3579,19 @@ BTF_ID_FLAGS(func, bpf_iter_kmem_cache_next, KF_ITER_NEXT | KF_RET_NULL | KF_SLE
 BTF_ID_FLAGS(func, bpf_iter_kmem_cache_destroy, KF_ITER_DESTROY | KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_local_irq_save)
 BTF_ID_FLAGS(func, bpf_local_irq_restore)
+BTF_ID_FLAGS(func, bpf_strcmp);
+BTF_ID_FLAGS(func, bpf_strchr);
+BTF_ID_FLAGS(func, bpf_strchrnul);
+BTF_ID_FLAGS(func, bpf_strnchr);
+BTF_ID_FLAGS(func, bpf_strnchrnul);
+BTF_ID_FLAGS(func, bpf_strrchr);
+BTF_ID_FLAGS(func, bpf_strlen);
+BTF_ID_FLAGS(func, bpf_strnlen);
+BTF_ID_FLAGS(func, bpf_strspn);
+BTF_ID_FLAGS(func, bpf_strcspn);
+BTF_ID_FLAGS(func, bpf_strpbrk);
+BTF_ID_FLAGS(func, bpf_strstr);
+BTF_ID_FLAGS(func, bpf_strnstr);
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
--

2.48.1

#5 lore raw
Quoted 17 lines · Andrii Nakryiko
Quoted 8 lines
Quoted 8 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_local_irq_restore(unsigned long *flags__irq_flag) · line 3233

Quoted 5 lines
kernel/bpf/helpers.c +3 -0
+       }
+out:
+       pagefault_enable();

how about we

Quoted 8 lines
Quoted 4 lines

DEFINE_LOCK_GUARD_0(pagefault, pagefault_disable(), pagefault_enable())

like we do for preempt_{disable,enable}() and simplify all the implementations significantly?

That's neat, I didn't know it. It will a bit more tricky to use here as __get_kernel_nofault still requires a label but we should at least be able to get rid of pagefault_{disable,enable}() in each function.

Quoted 7 lines

yep, we'll have:

err_out:

    return -EFAULT;

But the rest will be a clean loop and no pagefault_disable() clean ups, distracting from the main logic

Just a word of caution...
Please double check that both gcc and clang generate proper cleanup code when asm goto is used.