Skip to contentSkip to conversation

bpf: Add kfuncs for read-only string operations

PATCH Superseded Viktor Malik 2 participants 7 messages Sep 26, 2024 – Sep 27, 2024

Subsystems (3)

v2 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

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

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
Signature · 1 line
2.46.0
#1 lore raw

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

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.

---
 kernel/bpf/helpers.c | 66 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)
kernel/bpf/helpers.c +66 -0
index 1a43d06eab28..daa19760d8c8 100644
@@ -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 = {
Signature · 1 line
2.46.0
#2 lore raw

PATCH v2 2/2 selftests/bpf: Add tests for string kfuncs

In reply to 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.

---
 .../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
tools/testing/selftests/bpf/prog_tests/string_kfuncs.c new file +37 -0
new file mode 100644
index 000000000000..4fe28a4ee6ad
@@ -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);
+}
tools/testing/selftests/bpf/progs/test_string_kfuncs.c new file +215 -0

215 lines not on this page · raw message

Signature · 1 line
2.46.0
maintainer
#5 lore raw
In reply to Viktor Malik
Quoted 6 lines · 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.

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.

[...]

maintainer
#3 lore raw

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

In reply to Viktor Malik
Quoted 6 lines · 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.

---

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.

[...]

#6 lore raw
In reply to Eduard Zingerman
Quoted 15 lines · Eduard Zingerman
Quoted 6 lines · 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.

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

Quoted 6 lines

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

Quoted 3 lines

[...]

#4 lore raw

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

In reply to Eduard Zingerman
Quoted 49 lines · Eduard Zingerman
Quoted 6 lines · 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.

---

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
Quoted 4 lines

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

Quoted 3 lines

[...]