Use the word-at-a-time character finder to skip haystack regions which cannot begin a match. For case-insensitive searches, check both ASCII case variants of the first needle byte.
At each candidate, use a direct fault-safe word matcher. When both strings have the same relative alignment, skip equal words and inspect locally loaded bytes only for mismatches and case folding. Keep needle-first access, fall back at the same byte after a word-load fault, and retain the extra needle-byte check at the search limit so fault and boundary behavior remain unchanged. Assisted-by: Codex:gpt-5.6-sol Signed-off-by: Leon Hwang <[email protected]> --- kernel/bpf/helpers.c | 142 +++++++++++++++++++++++++++++++++---------- 1 file changed, 111 insertions(+), 31 deletions(-) diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index af29acc90245..93d5fa409cd7 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -4281,11 +4281,90 @@ __bpf_kfunc int bpf_strcspn(const char *s__ign, const char *reject__ign) return __bpf_strspn(s__ign, reject__ign, true); } -static int __bpf_strnstr(const char *s1, const char *s2, size_t len, - bool ignore_case) +#define bpf_str_match_byte(byte1, byte2, ignore_case) \ +do { \ + char __c1 = (byte1); \ + char __c2 = (byte2); \ + \ + if (ignore_case) { \ + __c1 = tolower(__c1); \ + __c2 = tolower(__c2); \ + } \ + if (__c1 == '\0') \ + return -ENOENT; \ + if (__c1 != __c2) \ + return 0; \ +} while (0) + +static __always_inline int +bpf_str_match_at(const char *s1, const char *s2, size_t limit, bool ignore_case) { - char c1, c2; - int i, j; + const struct word_at_a_time constants = WORD_AT_A_TIME_CONSTANTS; + unsigned char byte1, byte2, *bytes1, *bytes2; + unsigned long word1, word2, data; + size_t pos = 0, word_end, i; + + if (IS_ENABLED(CONFIG_KMSAN) || + !IS_ALIGNED((unsigned long)s1 ^ (unsigned long)s2, sizeof(word1))) + goto byte_at_a_time; + + while (pos < limit && !IS_ALIGNED((unsigned long)(s1 + pos), sizeof(word1))) { + __get_kernel_nofault(&byte2, s2 + pos, unsigned char, err_out); + if (byte2 == '\0') + return 1; + __get_kernel_nofault(&byte1, s1 + pos, unsigned char, err_out); + bpf_str_match_byte(byte1, byte2, ignore_case); + pos++; + } + + word_end = pos + round_down(limit - pos, sizeof(word1)); + while (pos < word_end) { + __get_kernel_nofault(&word2, s2 + pos, unsigned long, byte_at_a_time); + if (has_zero(word2, &data, &constants)) + goto byte_at_a_time; + __get_kernel_nofault(&word1, s1 + pos, unsigned long, byte_at_a_time); + if (word1 == word2) { + pos += sizeof(word1); + continue; + } + + bytes1 = (unsigned char *)&word1; + bytes2 = (unsigned char *)&word2; + for (i = 0; i < sizeof(word1); i++) + bpf_str_match_byte(bytes1[i], bytes2[i], ignore_case); + pos += sizeof(word1); + } + +byte_at_a_time: + for (; pos < limit; pos++) { + __get_kernel_nofault(&byte2, s2 + pos, unsigned char, err_out); + if (byte2 == '\0') + return 1; + __get_kernel_nofault(&byte1, s1 + pos, unsigned char, err_out); + bpf_str_match_byte(byte1, byte2, ignore_case); + } + + if (limit == XATTR_SIZE_MAX) + return -E2BIG; + + /* + * Read one extra byte from s2 to cover the case when it is a suffix + * of the first limit bytes of s1. + */ + __get_kernel_nofault(&byte2, s2 + limit, unsigned char, err_out); + return byte2 == '\0' ? 1 : -ENOENT; + +err_out: + return -EFAULT; +} + +#undef bpf_str_match_byte + +static int __bpf_strnstr(const char *s1, const char *s2, size_t len, bool ignore_case) +{ + unsigned char first, candidate; + size_t pos = 0, limit; + int ret, offset; if (!copy_from_kernel_nofault_allowed(s1, 1) || !copy_from_kernel_nofault_allowed(s2, 1)) { @@ -4293,37 +4372,38 @@ static int __bpf_strnstr(const char *s1, const char *s2, size_t len, } guard(pagefault)(); - for (i = 0; i < XATTR_SIZE_MAX; i++) { - for (j = 0; i + j <= len && j < XATTR_SIZE_MAX; j++) { - __get_kernel_nofault(&c2, s2 + j, char, err_out); - if (c2 == '\0') - return i; - /* - * We allow reading an extra byte from s2 (note the - * `i + j <= len` above) to cover the case when s2 is - * a suffix of the first len chars of s1. - */ - if (i + j == len) - break; - __get_kernel_nofault(&c1, s1 + j, char, err_out); - - if (ignore_case) { - c1 = tolower(c1); - c2 = tolower(c2); - } + __get_kernel_nofault(&first, s2, unsigned char, err_out); + if (first == '\0') + return 0; - if (c1 == '\0') - return -ENOENT; - if (c1 != c2) - break; + while (pos < XATTR_SIZE_MAX && pos < len) { + limit = min_t(size_t, len - pos, XATTR_SIZE_MAX - pos); + offset = bpf_str_find(s1 + pos, limit, first, ignore_case, true); + if (offset < 0) { + if (offset == -ENOENT && limit == XATTR_SIZE_MAX - pos) + return -E2BIG; + return offset; } - if (j == XATTR_SIZE_MAX) - return -E2BIG; - if (i + j == len) + pos += offset; + + /* + * bpf_str_find() also returns the position of a terminating + * NUL. Distinguish it from a first-character match. + */ + __get_kernel_nofault(&candidate, s1 + pos, unsigned char, err_out); + if (candidate == '\0') return -ENOENT; - s1++; + + limit = min_t(size_t, len - pos, XATTR_SIZE_MAX); + ret = bpf_str_match_at(s1 + pos, s2, limit, ignore_case); + if (ret > 0) + return pos; + if (ret < 0) + return ret; + pos++; } - return -E2BIG; + return pos == XATTR_SIZE_MAX ? -E2BIG : -ENOENT; + err_out: return -EFAULT; } -- 2.55.0
