[PATCH bpf-next v2 0/2] bpf: Add kfuncs for read-only string operations

[PATCH bpf-next v2 0/2] bpf: Add kfuncs for read-only string operations

[Viktor Malik]

Kernel contains highly optimised implementation of traditional string
operations. Expose them as kfuncs to allow BPF programs leverage the
kernel implementation instead of needing to reimplement the operations.

These will be very helpful to bpftrace as it now needs to implement all
the string operations in LLVM IR.

v1 -> v2:
- use bpf_probe_read_kernel_str instead of bpf_probe_read_str in
  selftests as the latter cannot be used on some arches (s390x)

Viktor Malik (2):
  bpf: Add kfuncs for read-only string operations
  selftests/bpf: Add tests for string kfuncs

 kernel/bpf/helpers.c                          |  66 ++++++
 .../selftests/bpf/prog_tests/string_kfuncs.c  |  37 +++
 .../selftests/bpf/progs/test_string_kfuncs.c  | 215 ++++++++++++++++++
 3 files changed, 318 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/string_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_string_kfuncs.c

-- 
2.46.0

[PATCH bpf-next v2 1/2] bpf: Add kfuncs for read-only string operations

[Viktor Malik]

Kernel contains highly optimised implementation of traditional string
operations. Expose them as kfuncs to allow BPF programs leverage the
kernel implementation instead of needing to reimplement the operations.

For now, add kfuncs for all string operations which do not copy memory
around: strcmp, strchr, strrchr, strnchr, strstr, strnstr, strlen,
strnlen, strpbrk, strspn, strcspn. Do not add strncmp as it is already
exposed as a helper.

Signed-off-by: Viktor Malik <vmalik@redhat.com>
---
 kernel/bpf/helpers.c | 66 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 1a43d06eab28..daa19760d8c8 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -3004,6 +3004,61 @@ __bpf_kfunc int bpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user
 	return ret + 1;
 }
 
+__bpf_kfunc int bpf_strcmp(const char *cs, const char *ct)
+{
+	return strcmp(cs, ct);
+}
+
+__bpf_kfunc char *bpf_strchr(const char *s, int c)
+{
+	return strchr(s, c);
+}
+
+__bpf_kfunc char *bpf_strrchr(const char *s, int c)
+{
+	return strrchr(s, c);
+}
+
+__bpf_kfunc char *bpf_strnchr(const char *s, size_t count, int c)
+{
+	return strnchr(s, count, c);
+}
+
+__bpf_kfunc char *bpf_strstr(const char *s1, const char *s2)
+{
+	return strstr(s1, s2);
+}
+
+__bpf_kfunc char *bpf_strnstr(const char *s1, const char *s2, size_t len)
+{
+	return strnstr(s1, s2, len);
+}
+
+__bpf_kfunc size_t bpf_strlen(const char *s)
+{
+	return strlen(s);
+}
+
+__bpf_kfunc size_t bpf_strnlen(const char *s, size_t count)
+{
+	return strnlen(s, count);
+}
+
+__bpf_kfunc char *bpf_strpbrk(const char *cs, const char *ct)
+{
+	return strpbrk(cs, ct);
+}
+
+__bpf_kfunc size_t bpf_strspn(const char *s, const char *accept)
+{
+	return strspn(s, accept);
+}
+
+__bpf_kfunc size_t bpf_strcspn(const char *s, const char *reject)
+{
+	return strcspn(s, reject);
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(generic_btf_ids)
@@ -3090,6 +3145,17 @@ BTF_ID_FLAGS(func, bpf_iter_bits_new, KF_ITER_NEW)
 BTF_ID_FLAGS(func, bpf_iter_bits_next, KF_ITER_NEXT | KF_RET_NULL)
 BTF_ID_FLAGS(func, bpf_iter_bits_destroy, KF_ITER_DESTROY)
 BTF_ID_FLAGS(func, bpf_copy_from_user_str, KF_SLEEPABLE)
+BTF_ID_FLAGS(func, bpf_strcmp)
+BTF_ID_FLAGS(func, bpf_strchr)
+BTF_ID_FLAGS(func, bpf_strrchr)
+BTF_ID_FLAGS(func, bpf_strnchr)
+BTF_ID_FLAGS(func, bpf_strstr)
+BTF_ID_FLAGS(func, bpf_strnstr)
+BTF_ID_FLAGS(func, bpf_strlen)
+BTF_ID_FLAGS(func, bpf_strnlen)
+BTF_ID_FLAGS(func, bpf_strpbrk)
+BTF_ID_FLAGS(func, bpf_strspn)
+BTF_ID_FLAGS(func, bpf_strcspn)
 BTF_KFUNCS_END(common_btf_ids)
 
 static const struct btf_kfunc_id_set common_kfunc_set = {
-- 
2.46.0

[PATCH bpf-next v2 2/2] selftests/bpf: Add tests for string kfuncs

[Viktor Malik]

The tests attach to `raw_tp/bpf_testmod_test_write_bare` triggerred by
`trigger_module_test_write` which writes the string "aaa..." of the
given size.

Signed-off-by: Viktor Malik <vmalik@redhat.com>
---
 .../selftests/bpf/prog_tests/string_kfuncs.c  |  37 +++
 .../selftests/bpf/progs/test_string_kfuncs.c  | 215 ++++++++++++++++++
 2 files changed, 252 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/string_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_string_kfuncs.c

diff --git a/tools/testing/selftests/bpf/prog_tests/string_kfuncs.c b/tools/testing/selftests/bpf/prog_tests/string_kfuncs.c
new file mode 100644
index 000000000000..4fe28a4ee6ad
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/string_kfuncs.c
@@ -0,0 +1,37 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <test_progs.h>
+#include "test_string_kfuncs.skel.h"
+
+void test_string_kfuncs(void)
+{
+	const int WRITE_SZ = 10;
+	struct test_string_kfuncs *skel;
+	struct test_string_kfuncs__bss *bss;
+
+	skel = test_string_kfuncs__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "test_string_kfuncs__open_end_load"))
+		return;
+
+	bss = skel->bss;
+
+	if (!ASSERT_OK(test_string_kfuncs__attach(skel), "test_string_kfuncs__attach"))
+		goto end;
+
+	ASSERT_OK(trigger_module_test_write(WRITE_SZ), "trigger_write");
+
+	ASSERT_EQ(bss->strcmp_check, 1, "test_strcmp");
+	ASSERT_EQ(bss->strchr_check, 1, "test_strchr");
+	ASSERT_EQ(bss->strrchr_check, 1, "test_strrchr");
+	ASSERT_EQ(bss->strnchr_check, 1, "test_strnchr");
+	ASSERT_EQ(bss->strstr_check, 1, "test_strstr");
+	ASSERT_EQ(bss->strnstr_check, 1, "test_strstr");
+	ASSERT_EQ(bss->strlen_check, 1, "test_strlen");
+	ASSERT_EQ(bss->strnlen_check, 1, "test_strnlen");
+	ASSERT_EQ(bss->strpbrk_check, 1, "test_strpbrk");
+	ASSERT_EQ(bss->strspn_check, 1, "test_strspn");
+	ASSERT_EQ(bss->strcspn_check, 1, "test_strspn");
+
+end:
+	test_string_kfuncs__destroy(skel);
+}
diff --git a/tools/testing/selftests/bpf/progs/test_string_kfuncs.c b/tools/testing/selftests/bpf/progs/test_string_kfuncs.c
new file mode 100644
index 000000000000..3cfe80b1941b
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/test_string_kfuncs.c
@@ -0,0 +1,215 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include "vmlinux.h"
+#include <bpf/bpf_core_read.h>
+#include <bpf/bpf_tracing.h>
+#include "../bpf_testmod/bpf_testmod.h"
+
+#define BUFSZ 10
+
+int bpf_strcmp(const char *cs, const char *ct) __ksym;
+char *bpf_strchr(const char *s, int c) __ksym;
+char *bpf_strrchr(const char *s, int c) __ksym;
+char *bpf_strnchr(const char *s, size_t count, int c) __ksym;
+char *bpf_strstr(const char *s1, const char *s2) __ksym;
+char *bpf_strnstr(const char *s1, const char *s2, size_t len) __ksym;
+size_t bpf_strlen(const char *) __ksym;
+size_t bpf_strnlen(const char *s, size_t count) __ksym;
+char *bpf_strpbrk(const char *cs, const char *ct) __ksym;
+size_t bpf_strspn(const char *s, const char *accept) __ksym;
+size_t bpf_strcspn(const char *s, const char *reject) __ksym;
+
+__u32 strcmp_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strcmp,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+	char expected[] = "aaaaaaaaa";
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strcmp(buf, expected) == 0)
+		strcmp_check = 1;
+
+	return 0;
+}
+
+__u32 strchr_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strchr,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strchr(buf, 'a') == buf)
+		strchr_check = 1;
+
+	return 0;
+}
+
+__u32 strrchr_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strrchr,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strrchr(buf, 'a') == &buf[8])
+		strrchr_check = 1;
+
+	return 0;
+}
+
+__u32 strnchr_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strnchr,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strnchr(buf, 1, 'a') == buf)
+		strnchr_check = 1;
+
+	return 0;
+}
+
+__u32 strstr_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strstr,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+	char substr[] = "aaa";
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strstr(buf, substr) == buf)
+		strstr_check = 1;
+
+	return 0;
+}
+
+__u32 strnstr_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strnstr,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+	char substr[] = "aaa";
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strnstr(buf, substr, 3) == buf)
+		strnstr_check = 1;
+
+	return 0;
+}
+
+__u32 strlen_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strlen,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strlen(buf) == 9)
+		strlen_check = 1;
+
+	return 0;
+}
+
+__u32 strnlen_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strnlen,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strnlen(buf, 5) == 5)
+		strnlen_check = 1;
+
+	return 0;
+}
+
+__u32 strpbrk_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strpbrk,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+	char accept[] = "abc";
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strpbrk(buf, accept) == buf)
+		strpbrk_check = 1;
+
+	return 0;
+}
+
+__u32 strspn_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strspn,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+	char accept[] = "abc";
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strspn(buf, accept) == 9)
+		strspn_check = 1;
+
+	return 0;
+}
+
+__u32 strcspn_check = 0;
+
+SEC("raw_tp/bpf_testmod_test_write_bare")
+int BPF_PROG(test_strcspn,
+	     struct task_struct *task, struct bpf_testmod_test_write_ctx *write_ctx)
+{
+	char buf[BUFSZ], *buf_ptr;
+	char reject[] = "abc";
+
+	buf_ptr = BPF_PROBE_READ(write_ctx, buf);
+	bpf_probe_read_kernel_str(buf, sizeof(buf), buf_ptr);
+
+	if (bpf_strcspn(buf, reject) == 0)
+		strcspn_check = 1;
+
+	return 0;
+}
+
+char LICENSE[] SEC("license") = "GPL";
-- 
2.46.0

Re: [PATCH bpf-next v2 0/2] bpf: Add kfuncs for read-only string operations

[Eduard Zingerman]

On Thu, 2024-09-26 at 09:29 +0200, Viktor Malik wrote:
> Kernel contains highly optimised implementation of traditional string
> operations. Expose them as kfuncs to allow BPF programs leverage the
> kernel implementation instead of needing to reimplement the operations.
> 
> These will be very helpful to bpftrace as it now needs to implement all
> the string operations in LLVM IR.

Note that existing string related helpers take a pointer to a string
and it's maximal length, namely:
- bpf_strtol
- bpf_strtoul
- bpf_snprintf_btf
- bpf_strncmp

The unbounded variants that are being exposed in this patch-set
(like strcmp) are only safe to use if string is guaranteed to be null terminated.
Verifier does not check this property at the moment (idk how easy/hard
such analysis might be).

I'd suggest not to expose unbounded variants of string functions.

[...]

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

[Eduard Zingerman]

On Thu, 2024-09-26 at 09:29 +0200, Viktor Malik wrote:
> The tests attach to `raw_tp/bpf_testmod_test_write_bare` triggerred by
> `trigger_module_test_write` which writes the string "aaa..." of the
> given size.
> 
> Signed-off-by: Viktor Malik <vmalik@redhat.com>
> ---

I thought about making these tests more terse as follows:

--- 8< ----------------------------------

// SPDX-License-Identifier: GPL-2.0

#include <linux/bpf.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;

static char *abc = "abc";

#define __test(retval) SEC("raw_tp") __success __retval(retval)

__test(2) int test_strcmp(void *ctx) { return bpf_strcmp(abc, "abd"); }
__test(1) int test_strchr(void *ctx) { return bpf_strchr(abc, 'b') - abc; }

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

---------------------------------- >8 ---

(plus registration in tools/testing/selftests/bpf/prog_tests/verifier.c)

However, this does not pass verification with the following error:

    VERIFIER LOG:
    =============
    arg#0 reference type('UNKNOWN ') size cannot be determined: -22
    0: R1=ctx() R10=fp0
    ; __test(2) int test_strcmp(void *ctx) { return bpf_strcmp(abc, "abd"); } @ verifier_str.c:15
    0: (18) r1 = 0xffff8881019533dc       ; R1_w=map_value(map=.rodata.str1.1,ks=4,vs=8,off=4)
    2: (18) r2 = 0xffff8881019533d8       ; R2_w=map_value(map=.rodata.str1.1,ks=4,vs=8)
    4: (85) call bpf_strcmp#64714
    write into map forbidden, value_size=8 off=4 size=1
    processed 3 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
    =============
    #503/1   verifier_str/test_strcmp:FAIL

Note that each string literal in the BPF program is in fact a pointer
to a read-only map. Hence in current form these new functions are not
very ergonomic. I think verifier should be extended to check 'const'
qualifiers for the kfuncs and allowing access in such cases.

[...]

Re: [PATCH bpf-next v2 0/2] bpf: Add kfuncs for read-only string operations

[Viktor Malik]

On 9/27/24 03:37, Eduard Zingerman wrote:
> On Thu, 2024-09-26 at 09:29 +0200, Viktor Malik wrote:
>> Kernel contains highly optimised implementation of traditional string
>> operations. Expose them as kfuncs to allow BPF programs leverage the
>> kernel implementation instead of needing to reimplement the operations.
>>
>> These will be very helpful to bpftrace as it now needs to implement all
>> the string operations in LLVM IR.
> 
> Note that existing string related helpers take a pointer to a string
> and it's maximal length, namely:
> - bpf_strtol
> - bpf_strtoul
> - bpf_snprintf_btf
> - bpf_strncmp
> 
> The unbounded variants that are being exposed in this patch-set
> (like strcmp) are only safe to use if string is guaranteed to be null terminated.
> Verifier does not check this property at the moment (idk how easy/hard
> such analysis might be).
> 
> I'd suggest not to expose unbounded variants of string functions.

That's a great point, thanks. Let me remove the unbounded variants for
now, until we add the null-byte check to the verifier. The bounded
variants will still be useful to bpftrace so I'd love to have them added.

Viktor

> 
> [...]
> 

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

[Viktor Malik]

On 9/27/24 03:57, Eduard Zingerman wrote:
> On Thu, 2024-09-26 at 09:29 +0200, Viktor Malik wrote:
>> The tests attach to `raw_tp/bpf_testmod_test_write_bare` triggerred by
>> `trigger_module_test_write` which writes the string "aaa..." of the
>> given size.
>>
>> Signed-off-by: Viktor Malik <vmalik@redhat.com>
>> ---
> 
> I thought about making these tests more terse as follows:
> 
> --- 8< ----------------------------------
> 
> // SPDX-License-Identifier: GPL-2.0
> 
> #include <linux/bpf.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;
> 
> static char *abc = "abc";
> 
> #define __test(retval) SEC("raw_tp") __success __retval(retval)
> 
> __test(2) int test_strcmp(void *ctx) { return bpf_strcmp(abc, "abd"); }
> __test(1) int test_strchr(void *ctx) { return bpf_strchr(abc, 'b') - abc; }
> 
> char _license[] SEC("license") = "GPL";
> 
> ---------------------------------- >8 ---
> 
> (plus registration in tools/testing/selftests/bpf/prog_tests/verifier.c)
> 
> However, this does not pass verification with the following error:
> 
>     VERIFIER LOG:
>     =============
>     arg#0 reference type('UNKNOWN ') size cannot be determined: -22
>     0: R1=ctx() R10=fp0
>     ; __test(2) int test_strcmp(void *ctx) { return bpf_strcmp(abc, "abd"); } @ verifier_str.c:15
>     0: (18) r1 = 0xffff8881019533dc       ; R1_w=map_value(map=.rodata.str1.1,ks=4,vs=8,off=4)
>     2: (18) r2 = 0xffff8881019533d8       ; R2_w=map_value(map=.rodata.str1.1,ks=4,vs=8)
>     4: (85) call bpf_strcmp#64714
>     write into map forbidden, value_size=8 off=4 size=1
>     processed 3 insns (limit 1000000) max_states_per_insn 0 total_states 0 peak_states 0 mark_read 0
>     =============
>     #503/1   verifier_str/test_strcmp:FAIL
> 
> Note that each string literal in the BPF program is in fact a pointer
> to a read-only map. Hence in current form these new functions are not
> very ergonomic. I think verifier should be extended to check 'const'
> qualifiers for the kfuncs and allowing access in such cases.

Yeah, I noticed the same problem when I was trying to come with shorter
tests. Teaching verifier to allow passing pointers to read-only maps to
these kfuncs is certainly a good thing, I'll have a look into it.

On the other hand, bpftrace stores string literals on stack so these
kfuncs would be useful to us straight away.

Viktor

> 
> [...]
>