Re: [PATCH bpf-next v3 1/3] bpf: Add kfuncs for read-only string operations

[Viktor Malik <vmalik@redhat.com>]

On 3/28/25 23:48, Andrii Nakryiko wrote:
> On Mon, Mar 24, 2025 at 5:04 AM Viktor Malik <vmalik@redhat.com> wrote:
>>
>> 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.
>>
>> Suggested-by: Alexei Starovoitov <ast@kernel.org>
>> Signed-off-by: Viktor Malik <vmalik@redhat.com>
>> ---
>>  kernel/bpf/helpers.c | 299 +++++++++++++++++++++++++++++++++++++++++++
>>  1 file changed, 299 insertions(+)
>>
>> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
>> index 5449756ba102..6f6af4289cd0 100644
>> --- a/kernel/bpf/helpers.c
>> +++ b/kernel/bpf/helpers.c
>> @@ -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.

> 
>>  #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);
> 
> 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.

> 
>> +               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;
>> +}
> 
> 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?

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?

> 
>> +
>> +/**
>> + * 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.

> 
>> +{
>> +       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.
> 
>> +                       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.

> 
>> +       }
>> +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.

> 
>> +       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) {
> 
> 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?

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

> 
>> +               __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)
> 
> 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.

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.

> 
>> +{
>> +       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)
> 
> `const char *` return? we won't (well, shouldn't!) allow writing into
> it from the BPF program.

Yes, agreed.

> 
>> +{
>> +       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))
> 
> 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?

> 
>> +                       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)
> 
> 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.

> 
>> +{
>> +       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;
> 
> 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.

> 
>> +}
>> +
>> +/**
>> + * 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);
>> +}
>> +
> 
> 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

> 
> pw-bot: cr
> 
>>  __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
>>
>