bpf: Add kfuncs for read-only string operations
Subsystems (3)
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.
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
PATCH 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
@@ -3004,6 +3004,61 @@ __bpf_kfunc int bpf_copy_from_user_str(void *dst, u32 dst__sz, const void __userreturn 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
Quoted 20 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.
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 <[email protected]>--- kernel/bpf/helpers.c | 66 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+)kernel/bpf/helpers.c +0
-0
kernel/bpf/helpers.c __bpf_kfunc int bpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user · line 3007
Quoted 4 lines
kernel/bpf/helpers.c +1
-0@@ -3004,6 +3004,61 @@ __bpf_kfunc int bpf_copy_from_user_str(void *dst, u32 dst__sz, const void __userreturn ret +1 ; } +__bpf_kfunc int bpf_strcmp(const char *cs, const char *ct)
I don't think this will work as you hope it will work. I suspect BPF verifier thinks you are asking to a pointer to a singular char (1-byte memory, basically), and expects kfunc to not access beyond that single byte. Which is not what you are doing, so it's a violation of declared kfunc contract.
We do have support to pass constant string pointers that are known at verification time (see bpf_strncmp() and also is_kfunc_arg_const_str() for kfunc-like equivalent), but I don't think that's what you want here.
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
pw-bot: cr
Quoted 78 lines
kernel/bpf/helpers.c +65
-1+{ +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
Eduard Zingerman
maintainerOn Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have 'is_kfunc_arg_mem_size()' that checks for __sz suffix, e.g. used for bpf_copy_from_user_str():
/**
* bpf_copy_from_user_str() - Copy a string from an unsafe user address
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.
* ...
*/__bpf_kfunc int bpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)
However, this suffix won't work for strnstr because of the arguments order.
[...]
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user address
Quoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with __get_kernel_nofault() instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faults and __get_kernel_nofault is an efficient mechanism to do that. It's just an annotated load. No extra overhead.
So readonly kfuncs can look like:
bpf_str...(const char *src)
while kfuncs that need a destination buffer will look like:
bpf_str...(void *dst, u32 dst__sz, ...)
bpf_strcpy(), strncpy, strlcpy shouldn't be introduced though.
but bpf_strscpy_pad(void *dst, u32 dst__sz, const char *src) would be good to have.
And it will be just as fast as strscpy_pad().
Quoted 26 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Quoted 8 lines
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faults
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Quoted 14 lines
and
__get_kernel_nofaultis an efficient mechanism to do that. It's just an annotated load. No extra overhead.So readonly kfuncs can look like:
bpf_str...(const char *src)while kfuncs that need a destination buffer will look like:
bpf_str...(void *dst, u32dst__sz, ...)
bpf_strcpy(), strncpy, strlcpy shouldn't be introduced though.but
bpf_strscpy_pad(void *dst, u32 dst__sz, const char *src)would be good to have.
And it will be just as fast asstrscpy_pad().
Quoted 38 lines · Andrii Nakryiko
Quoted 26 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Quoted 8 lines
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faults
Quoted 3 lines
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Just checking s[0] and s[N-1] is not enough, obviously, and especially, since the logic won't know where nul byte is, so N is unknown. I meant to that all of str* kfuncs will be reading all bytes via __get_kernel_nofault() until they find \0.
It can be optimized to 8 byte access.
The open coding (aka copy-paste) is unfortunate, of course.
Quoted 41 lines · Alexei Starovoitov
Quoted 38 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faults
Quoted 8 lines
Quoted 3 lines
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Just checking s[0] and s[N-1] is not enough, obviously, and especially, since the logic won't know where nul byte is, so N is unknown. I meant to that all of str* kfuncs will be reading all bytes via
__get_kernel_nofault()until they find \0.
Ah, ok, I see what you mean now.
Quoted 2 lines
It can be optimized to 8 byte access.
The open coding (aka copy-paste) is unfortunate, of course.
Yep, this sucks.
Quoted 52 lines · Andrii Nakryiko
Quoted 41 lines · Alexei Starovoitov
Quoted 38 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faultsQuoted 8 lines
Quoted 3 lines
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Just checking s[0] and s[N-1] is not enough, obviously, and especially, since the logic won't know where nul byte is, so N is unknown. I meant to that all of str* kfuncs will be reading all bytes via
__get_kernel_nofault()until they find \0.
Quoted 6 lines
Ah, ok, I see what you mean now.
Quoted 2 lines
It can be optimized to 8 byte access.
The open coding (aka copy-paste) is unfortunate, of course.Yep, this sucks.
Yeah, that's quite annoying. I really wanted to avoid doing that. Also, we won't be able to use arch-optimized versions of the functions.
Just to make sure I understand things correctly - can we do what Eduard suggested and add explicit sizes for all arguments using the __sz suffix? So something like:
const char *bpf_strnstr(const char *s1, u32 s1__sz, const char *s2, u32 s2__sz);
Or that would still not be sufficient b/c the strings may still be unsafe and we need an additional safety check (using __get_kernel_nofault suggested by Alexei)?
Quoted 61 lines · Viktor Malik
Quoted 52 lines · Andrii Nakryiko
Quoted 41 lines · Alexei Starovoitov
Quoted 38 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faultsQuoted 8 lines
Quoted 3 lines
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Just checking s[0] and s[N-1] is not enough, obviously, and especially, since the logic won't know where nul byte is, so N is unknown. I meant to that all of str* kfuncs will be reading all bytes via
__get_kernel_nofault()until they find \0.Quoted 6 lines
Ah, ok, I see what you mean now.
Quoted 2 lines
It can be optimized to 8 byte access.
The open coding (aka copy-paste) is unfortunate, of course.Yep, this sucks.
Quoted 8 lines
Yeah, that's quite annoying. I really wanted to avoid doing that. Also, we won't be able to use arch-optimized versions of the functions.
Just to make sure I understand things correctly - can we do what Eduard suggested and add explicit sizes for all arguments using the
__szsuffix? So something like:const char *bpf_strnstr(const char *s1, u32 s1__sz, const char *s2, u32 s2__sz);
That's ok-ish, but you probably want:
const char *bpf_strnstr(void *s1, u32 s1__sz, void *s2, u32 s2__sz);
and then to call strnstr() you still need to strnlen(s2, s2__sz).
But a more general question... how always passing size will work for bpftrace ? Does it always know the upper bound of storage where strings are stored?
I would think __get_kernel_nofault() approach is user friendlier.
Quoted 73 lines · Alexei Starovoitov
Quoted 61 lines · Viktor Malik
Quoted 52 lines · Andrii Nakryiko
Quoted 41 lines · Alexei Starovoitov
Quoted 38 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faultsQuoted 8 lines
Quoted 3 lines
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Just checking s[0] and s[N-1] is not enough, obviously, and especially, since the logic won't know where nul byte is, so N is unknown. I meant to that all of str* kfuncs will be reading all bytes via
__get_kernel_nofault()until they find \0.Quoted 6 lines
Ah, ok, I see what you mean now.
Quoted 2 lines
It can be optimized to 8 byte access.
The open coding (aka copy-paste) is unfortunate, of course.Yep, this sucks.
Quoted 8 lines
Yeah, that's quite annoying. I really wanted to avoid doing that. Also, we won't be able to use arch-optimized versions of the functions.
Just to make sure I understand things correctly - can we do what Eduard suggested and add explicit sizes for all arguments using the
__szsuffix? So something like:const char *bpf_strnstr(const char *s1, u32 s1__sz, const char *s2, u32 s2__sz);That's ok-ish, but you probably want:
Quoted 7 lines
const char *bpf_strnstr(void *s1, u32
s1__sz, void *s2, u32s2__sz);and then to call
strnstr()you still need tostrnlen(s2, s2__sz).But a more general question... how always passing size will work for bpftrace ? Does it always know the upper bound of storage where strings are stored?
Yes, it does. The strings must be read via the str() call (which internally calls bpf_probe_read_str) and there's an upper bound on the size of each string.
Quoted 1 line
I would think
__get_kernel_nofault()approach is user friendlier.
That's probably true but isn't there still the problem that strings are not necessarily null-terminated? And in such case, unbounded string functions may not terminate which is not allowed in BPF?
Quoted 79 lines · Viktor Malik
Quoted 77 lines · Alexei Starovoitov
Quoted 61 lines · Viktor Malik
Quoted 52 lines · Andrii Nakryiko
Quoted 41 lines · Alexei Starovoitov
Quoted 38 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faultsQuoted 8 lines
Quoted 3 lines
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Just checking s[0] and s[N-1] is not enough, obviously, and especially, since the logic won't know where nul byte is, so N is unknown. I meant to that all of str* kfuncs will be reading all bytes via
__get_kernel_nofault()until they find \0.Quoted 6 lines
Ah, ok, I see what you mean now.
Quoted 2 lines
It can be optimized to 8 byte access.
The open coding (aka copy-paste) is unfortunate, of course.Yep, this sucks.
Quoted 8 lines
Yeah, that's quite annoying. I really wanted to avoid doing that. Also, we won't be able to use arch-optimized versions of the functions.
Just to make sure I understand things correctly - can we do what Eduard suggested and add explicit sizes for all arguments using the
__szsuffix? So something like:const char *bpf_strnstr(const char *s1, u32 s1__sz, const char *s2, u32 s2__sz);That's ok-ish, but you probably want:
const char *bpf_strnstr(void *s1, u32
s1__sz, void *s2, u32s2__sz);and then to call
strnstr()you still need tostrnlen(s2, s2__sz).
Quoted 7 lines
Quoted 3 lines
But a more general question... how always passing size will work for bpftrace ? Does it always know the upper bound of storage where strings are stored?
Yes, it does. The strings must be read via the
str()call (which internally callsbpf_probe_read_str) and there's an upper bound on the size of each string.
which sounds like a bpftrace current limitation and not something to depend on from kfunc design pov.
Wouldn't you want strings to be arbitrary length?
Quoted 5 lines
Quoted 1 line
I would think
__get_kernel_nofault()approach is user friendlier.That's probably true but isn't there still the problem that strings are not necessarily null-terminated? And in such case, unbounded string functions may not terminate which is not allowed in BPF?
kfuncs that are searching for nul via loop with __get_kernel_nofault() would certainly need an upper bound.
Something like PATH_MAX (4k) or XATTR_SIZE_MAX (64k)
would cover 99.99% of use cases.
Quoted 84 lines · Alexei Starovoitov
Quoted 83 lines · Viktor Malik
Quoted 80 lines · Alexei Starovoitov
Quoted 61 lines · Viktor Malik
Quoted 52 lines · Andrii Nakryiko
Quoted 41 lines · Alexei Starovoitov
Quoted 38 lines · Andrii Nakryiko
Quoted 34 lines · Alexei Starovoitov
Quoted 13 lines · Eduard Zingerman
On Mon, 2024-09-30 at 15:00 -0700, Andrii Nakryiko wrote:
[...]
Quoted 2 lines
Right now, the only way to pass dynamically sized anything is through dynptr, AFAIU.
But we do have '
is_kfunc_arg_mem_size()' that checks for__szsuffix, e.g. used forbpf_copy_from_user_str():/**
*bpf_copy_from_user_str()- Copy a string from an unsafe user addressQuoted 8 lines
* @dst: Destination address, in kernel space. This buffer must be * at least @dst__sz bytes long. * @dst__sz: Maximum number of bytes to copy, includes the trailing NUL.* ...
*/__bpf_kfuncintbpf_copy_from_user_str(void *dst, u32 dst__sz, const void __user *unsafe_ptr__ign, u64 flags)However, this suffix won't work for strnstr because of the arguments order.
Stating the obvious... we don't need to keep the order exactly the same.
Regarding all of these kfuncs... as Andrii pointed out 'const char *s' means that the verifier will check that 's' points to a valid byte. I think we can do a hybrid static + dynamic safety scheme here. All of the kfunc signatures can stay the same, but we'd have to open code all string helpers with
__get_kernel_nofault()instead of direct memory access.
Since the first byte is guaranteed to be valid by the verifier we only need to make sure that the s+N bytes won't cause page faultsQuoted 8 lines
Quoted 3 lines
You mean to just check that s[N-1] can be read? Given a large enough N, couldn't it be that some page between s[0] and s[N-1] still can be unmapped, defeating this check?
Just checking s[0] and s[N-1] is not enough, obviously, and especially, since the logic won't know where nul byte is, so N is unknown. I meant to that all of str* kfuncs will be reading all bytes via
__get_kernel_nofault()until they find \0.Quoted 6 lines
Ah, ok, I see what you mean now.
Quoted 2 lines
It can be optimized to 8 byte access.
The open coding (aka copy-paste) is unfortunate, of course.Yep, this sucks.
Quoted 8 lines
Yeah, that's quite annoying. I really wanted to avoid doing that. Also, we won't be able to use arch-optimized versions of the functions.
Just to make sure I understand things correctly - can we do what Eduard suggested and add explicit sizes for all arguments using the
__szsuffix? So something like:const char *bpf_strnstr(const char *s1, u32 s1__sz, const char *s2, u32 s2__sz);That's ok-ish, but you probably want:
const char *bpf_strnstr(void *s1, u32
s1__sz, void *s2, u32s2__sz);and then to call
strnstr()you still need tostrnlen(s2, s2__sz).But a more general question... how always passing size will work for bpftrace ? Does it always know the upper bound of storage where strings are stored?
Quoted 7 lines
Quoted 3 lines
Yes, it does. The strings must be read via the
str()call (which internally callsbpf_probe_read_str) and there's an upper bound on the size of each string.which sounds like a bpftrace current limitation and not something to depend on from kfunc design pov.
Wouldn't you want strings to be arbitrary length?
Sure, there's just a lot of work to be done on that front...
But I agree, it shouldn't be a limitation for the kfuncs. I just wanted to point out that if we agreed to only create kfuncs for bounded functions, bpftrace use-case would be (at least for the moment) covered.
Anyways, it seems to me that both the bounded and the unbounded versions have their place. Would it be ok with you to open-code just the unbounded ones and call in-kernel implementations for the bounded ones? Or would you prefer to have everything unified (i.e. open-coded)?
Also, just out of curiosity, what are the ways to create/obtain strings of unbounded length in BPF programs? Arguments of BTF-enabled program types (like fentry)? Any other examples? Because IIUC, when you read strings from kernel/userspace memory using bpf_probe_read_str, you always need to specify the size.
Quoted 11 lines
Quoted 6 lines
Quoted 2 lines
I would think
__get_kernel_nofault()approach is user friendlier.That's probably true but isn't there still the problem that strings are not necessarily null-terminated? And in such case, unbounded string functions may not terminate which is not allowed in BPF?
kfuncs that are searching for nul via loop with
__get_kernel_nofault()would certainly need an upper bound.
Something likePATH_MAX(4k) orXATTR_SIZE_MAX(64k)
would cover 99.99% of use cases.
Right, makes sense.
Thanks!
Viktor
Quoted 1 line
Quoted 4 lines · Viktor Malik
Anyways, it seems to me that both the bounded and the unbounded versions have their place. Would it be ok with you to open-code just the unbounded ones and call in-kernel implementations for the bounded ones?
Right. Open coding unbounded ones is not a lot of code. We can copy paste from arch/x86/boot/string.c and replace pointer deref with __get_kernel_nofault().
No need to be fancy.
The bounded ones should call into in-kernel bits that are optimized in asm.
Documenting the difference in performance between bounded vs unbounded should be part of the patch.
Quoted 5 lines
Also, just out of curiosity, what are the ways to create/obtain strings of unbounded length in BPF programs? Arguments of BTF-enabled program types (like fentry)? Any other examples? Because IIUC, when you read strings from kernel/userspace memory using
bpf_probe_read_str, you always need to specify the size.
The main use case is argv/env processing in bpf-lsm programs. These strings are nul terminated and can be very large. Attackers use multi megabyte env vars to hide things.
Folks push them into ringbuf and strstr() in user space as a workaround. Unbounded bpf_strstr() kfunc would be handy.
Viktor,
Are you still planning to work on string kfuncs ?
I think we more or less converged on requirements. So only a small matter of programming is left ? :)
If you're busy with other things we can take over.
Quoted 30 lines · Alexei Starovoitov
Quoted 4 lines · Viktor Malik
Anyways, it seems to me that both the bounded and the unbounded versions have their place. Would it be ok with you to open-code just the unbounded ones and call in-kernel implementations for the bounded ones?
Right. Open coding unbounded ones is not a lot of code. We can copy paste from
arch/x86/boot/string.cand replace pointer deref with__get_kernel_nofault().
No need to be fancy.The bounded ones should call into in-kernel bits that are optimized in asm.
Documenting the difference in performance between bounded vs unbounded should be part of the patch.
Quoted 5 lines
Also, just out of curiosity, what are the ways to create/obtain strings of unbounded length in BPF programs? Arguments of BTF-enabled program types (like fentry)? Any other examples? Because IIUC, when you read strings from kernel/userspace memory using
bpf_probe_read_str, you always need to specify the size.The main use case is argv/env processing in bpf-lsm programs. These strings are nul terminated and can be very large. Attackers use multi megabyte env vars to hide things.
Folks push them into ringbuf and
strstr()in user space as a workaround. Unboundedbpf_strstr()kfunc would be handy.
Quoted 8 lines · Alexei Starovoitov
Viktor,
Are you still planning to work on string kfuncs ?
I think we more or less converged on requirements. So only a small matter of programming is left ? :)
If you're busy with other things we can take over.
Hi Alexei,
this slipped off my radar due to other priorities recently but I should be able to get to it in the upcoming weeks. As you say, it shouldn't be much work so I hope to get back with a v2 soon.
Thanks for poking me :)
Viktor
Quoted 34 lines
Quoted 30 lines · Alexei Starovoitov
Quoted 4 lines · Viktor Malik
Anyways, it seems to me that both the bounded and the unbounded versions have their place. Would it be ok with you to open-code just the unbounded ones and call in-kernel implementations for the bounded ones?
Right. Open coding unbounded ones is not a lot of code. We can copy paste from
arch/x86/boot/string.cand replace pointer deref with__get_kernel_nofault().
No need to be fancy.The bounded ones should call into in-kernel bits that are optimized in asm.
Documenting the difference in performance between bounded vs unbounded should be part of the patch.
Quoted 5 lines
Also, just out of curiosity, what are the ways to create/obtain strings of unbounded length in BPF programs? Arguments of BTF-enabled program types (like fentry)? Any other examples? Because IIUC, when you read strings from kernel/userspace memory using
bpf_probe_read_str, you always need to specify the size.The main use case is argv/env processing in bpf-lsm programs. These strings are nul terminated and can be very large. Attackers use multi megabyte env vars to hide things.
Folks push them into ringbuf and
strstr()in user space as a workaround. Unboundedbpf_strstr()kfunc would be handy.
Quoted 9 lines · Viktor Malik
Quoted 7 lines · Alexei Starovoitov
Viktor,
Are you still planning to work on string kfuncs ?
I think we more or less converged on requirements. So only a small matter of programming is left ? :)
Quoted 7 lines
Quoted 1 line
If you're busy with other things we can take over.
Hi Alexei,
this slipped off my radar due to other priorities recently but I should be able to get to it in the upcoming weeks. As you say, it shouldn't be much work so I hope to get back with a v2 soon.
Great. Thanks!
PATCH 2/2 selftests/bpf: Add tests for string kfuncs
In reply to Viktor MalikThe 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
@@ -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