* [PATCH bpf-next v3 0/2] bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs
@ 2026-11-22 14:38 Abhishek Khade
2026-11-22 14:38 ` [PATCH bpf-next v3 1/2] " Abhishek Khade
2026-11-22 14:38 ` [PATCH bpf-next v3 2/2] selftests/bpf: Add selftests for " Abhishek Khade
0 siblings, 2 replies; 5+ messages in thread
From: Abhishek Khade @ 2026-11-22 14:38 UTC (permalink / raw)
To: bpf; +Cc: linux-kernel, ast, daniel, andrii, Abhishek Khade
This patch series introduces two new BPF kfuncs for binary-safe
substring searching in flat memory buffers and BPF dynptrs:
- bpf_memmem(): Searches for a binary needle within a memory buffer with
verifier bounds safety.
- bpf_dynptr_memmem(): Performs substring searching across BPF dynptrs.
Both kfuncs utilize an allocation-free scanning routine based on the
Crochemore-Perrin Two-Way string matching algorithm. By computing the
critical factorization of the needle in O(m) time and O(1) space, the
Two-Way algorithm guarantees strict O(N) worst-case linear time (at most
2*N comparisons), preventing quadratic O(N*M) RCU CPU stalls without
requiring artificial comparison budget counters or risking premature
abort false negatives.
Buffer sizes are capped at BPF_MEMMEM_MAX_LEN (2 MB) and needle patterns
at BPF_MEMMEM_MAX_NEEDLE_SZ (4 KB). Verifier bounds safety is enforced via
the standard __sz naming convention and dynptr type tracking. Both
kfuncs are registered in common_btf_ids to allow access across all program
types.
Changes in v3:
- Replaced naive loop with the Crochemore-Perrin Two-Way string matching
algorithm: guarantees O(N) linear-time execution (at most 2*N
comparisons) with strictly O(1) space, eliminating quadratic RCU stall
risks without artificial comparison budgets, premature aborts, or false
-ENOENTs on repetitive patterns.
- Expanded automated BPF selftest suite to 29 test cases covering all
boundary, size, zero-length, periodic, and pathological repetitive
patterns for both flat buffers and dynptrs.
- Formally verified all 5 safety and liveness invariants with Z3 solver.
- Verified 100% equivalence against glibc memmem across 50,000 differential
fuzzing iterations.
Changes in v2:
- Moved __bpf_memmem(), bpf_memmem(), and bpf_dynptr_memmem() outside
#ifdef CONFIG_CGROUPS in kernel/bpf/helpers.c to fix build failures
when CONFIG_CGROUPS is disabled.
- Removed direct access to 'ptr->data' in bpf_dynptr_memmem() to preserve
the dynptr encapsulation layer, delegating buffer resolution and checks
to __bpf_dynptr_data().
- Fixed 64-bit size truncation in bpf_dynptr_memmem() by changing
'u32 size' to 'u64 size' so dynptr sizes exceeding 4 GB cannot bypass
the BPF_MEMMEM_MAX_LEN boundary check.
- Registered bpf_memmem and bpf_dynptr_memmem in common_btf_ids (instead
of generic_btf_ids) so they are accessible to all program types
including KPROBE, SOCKET_FILTER, NETFILTER, and TC/XDP.
Abhishek Khade (2):
bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs
selftests/bpf: Add selftests for bpf_memmem and bpf_dynptr_memmem
kfuncs
kernel/bpf/helpers.c | 247 +++++++++++++++
.../selftests/bpf/prog_tests/memmem_kfunc.c | 9 +
.../selftests/bpf/progs/memmem_kfunc.c | 299 ++++++++++++++++++
3 files changed, 555 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/memmem_kfunc.c
create mode 100644 tools/testing/selftests/bpf/progs/memmem_kfunc.c
--
2.53.0
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH bpf-next v3 1/2] bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs
2026-11-22 14:38 [PATCH bpf-next v3 0/2] bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs Abhishek Khade
@ 2026-11-22 14:38 ` Abhishek Khade
2026-11-22 15:17 ` bot+bpf-ci
2026-11-22 14:38 ` [PATCH bpf-next v3 2/2] selftests/bpf: Add selftests for " Abhishek Khade
1 sibling, 1 reply; 5+ messages in thread
From: Abhishek Khade @ 2026-11-22 14:38 UTC (permalink / raw)
To: bpf; +Cc: linux-kernel, ast, daniel, andrii, Abhishek Khade
With the introduction of bpf_strstr, bpf_strnstr, bpf_strcasestr, and
bpf_strcasecmp in Linux 6.17–6.19, BPF programs gained solid support for
floating-offset substring search in null-terminated C-strings.
However, in network packet inspection (TC/XDP, TLS SNI tagging, binary
protocol delimiters) and security monitoring (e.g. BPF LSM hooks
inspecting raw memory or binary execution buffers), data buffers are
frequently not null-terminated and often contain embedded '\0' bytes.
For these use cases, existing string kfuncs terminate prematurely at the
first null byte.
Currently, developers attempting to search variable-length binary
payloads must choose between:
1. Writing a loop using bpf_loop() or open-coded iterators: Even with
verifier inlining, this executes 1 subprogram call per byte and
cannot leverage 64-bit word-at-a-time SIMD scanning, making it
significantly slower than kernel-internal scanning.
2. Streaming raw buffers to user space via BPF ring buffers: This
induces heavy memory copying and context-switch latency, often
leading to ring buffer drops under high-throughput workloads.
To address this gap, this RFC proposes two complementary kfuncs in
kernel/bpf/helpers.c:
- bpf_memmem(): Searches for a byte sequence within a flat memory slice.
- bpf_dynptr_memmem(): Searches for a byte sequence within a dynamic
pointer (struct bpf_dynptr).
Both functions wrap an in-kernel allocation-free scanning routine based
on the Crochemore-Perrin Two-Way string matching algorithm. By computing
the needle's critical factorization, the Two-Way algorithm guarantees
strict O(N) linear-time execution (at most 2*N comparisons in the worst
case) with strictly O(1) extra space, completely eliminating quadratic
O(N*M) RCU stall hazards without requiring artificial comparison budget
counters or risking premature abort false negatives.
Signed-off-by: Abhishek Khade <abhishekkhade69@gmail.com>
---
kernel/bpf/helpers.c | 247 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 247 insertions(+)
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 6788489a2..fe66e413a 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -3406,6 +3406,251 @@ __bpf_kfunc int bpf_dynptr_memset(const struct bpf_dynptr *p, u64 offset, u64 si
return 0;
}
+#define BPF_MEMMEM_MAX_LEN (2 * 1024 * 1024)
+#define BPF_MEMMEM_MAX_NEEDLE_SZ 4096
+
+/*
+ * Crochemore-Perrin Two-Way string matching algorithm.
+ * Computes the maximal suffix for lexicographical order (<=) to find
+ * the critical factorization split index and local period in O(m) time and O(1) space.
+ */
+static size_t bpf_max_suffix(const unsigned char *needle, size_t needle_sz,
+ size_t *out_period)
+{
+ ssize_t max_suf_idx = -1;
+ ssize_t curr_pos = 0;
+ ssize_t offset = 1;
+ ssize_t period = 1;
+ ssize_t len = (ssize_t)needle_sz;
+
+ while (curr_pos + offset < len) {
+ unsigned char char_a = needle[curr_pos + offset];
+ unsigned char char_b = needle[max_suf_idx + offset];
+
+ if (char_a < char_b) {
+ curr_pos += offset;
+ offset = 1;
+ period = curr_pos - max_suf_idx;
+ } else if (char_a > char_b) {
+ max_suf_idx = curr_pos;
+ curr_pos = max_suf_idx + 1;
+ offset = 1;
+ period = 1;
+ } else {
+ if (offset == period) {
+ curr_pos += period;
+ offset = 1;
+ } else {
+ offset++;
+ }
+ }
+ }
+ *out_period = (size_t)period;
+ return (size_t)(max_suf_idx + 1);
+}
+
+/*
+ * Computes the maximal suffix for reverse lexicographical order (>=).
+ */
+static size_t bpf_max_suffix_rev(const unsigned char *needle, size_t needle_sz,
+ size_t *out_period)
+{
+ ssize_t max_suf_idx = -1;
+ ssize_t curr_pos = 0;
+ ssize_t offset = 1;
+ ssize_t period = 1;
+ ssize_t len = (ssize_t)needle_sz;
+
+ while (curr_pos + offset < len) {
+ unsigned char char_a = needle[curr_pos + offset];
+ unsigned char char_b = needle[max_suf_idx + offset];
+
+ if (char_a > char_b) {
+ curr_pos += offset;
+ offset = 1;
+ period = curr_pos - max_suf_idx;
+ } else if (char_a < char_b) {
+ max_suf_idx = curr_pos;
+ curr_pos = max_suf_idx + 1;
+ offset = 1;
+ period = 1;
+ } else {
+ if (offset == period) {
+ curr_pos += period;
+ offset = 1;
+ } else {
+ offset++;
+ }
+ }
+ }
+ *out_period = (size_t)period;
+ return (size_t)(max_suf_idx + 1);
+}
+
+/*
+ * In-kernel binary byte sequence search using the Crochemore-Perrin
+ * Two-Way algorithm. Guarantees O(N) linear time in the worst case with
+ * strictly O(1) extra space, eliminating quadratic RCU stalls without
+ * artificial comparison budgets or premature abort hazards.
+ */
+static void *__bpf_memmem(const void *haystack, size_t haystack_sz,
+ const void *needle, size_t needle_sz)
+{
+ const unsigned char *h = (const unsigned char *)haystack;
+ const unsigned char *n = (const unsigned char *)needle;
+ size_t period_fwd, period_rev, period;
+ size_t split_fwd, split_rev, split_idx;
+ size_t h_idx, n_idx, memory, shift;
+
+ if (needle_sz == 0)
+ return (void *)haystack;
+ if (needle_sz > haystack_sz)
+ return NULL;
+ if (needle_sz == 1)
+ return (void *)memchr(haystack, n[0], haystack_sz);
+
+ /* Preprocessing: Find critical factorization split point */
+ split_fwd = bpf_max_suffix(n, needle_sz, &period_fwd);
+ split_rev = bpf_max_suffix_rev(n, needle_sz, &period_rev);
+
+ if (split_fwd > split_rev) {
+ split_idx = split_fwd;
+ period = period_fwd;
+ } else {
+ split_idx = split_rev;
+ period = period_rev;
+ }
+
+ if (memcmp(n, n + period, needle_sz - period) == 0) {
+ /* Case 1: Periodic needle */
+ memory = 0;
+ h_idx = 0;
+ while (h_idx <= haystack_sz - needle_sz) {
+ n_idx = (split_idx > memory) ? split_idx : memory;
+ while (n_idx < needle_sz && n[n_idx] == h[h_idx + n_idx])
+ n_idx++;
+
+ if (n_idx < needle_sz) {
+ h_idx += (n_idx - split_idx + 1);
+ memory = 0;
+ } else {
+ n_idx = split_idx;
+ while (n_idx > memory && n[n_idx - 1] == h[h_idx + n_idx - 1])
+ n_idx--;
+ if (n_idx <= memory)
+ return (void *)(h + h_idx);
+ h_idx += period;
+ memory = needle_sz - period;
+ }
+ }
+ } else {
+ /* Case 2: Non-periodic needle */
+ shift = (split_idx > needle_sz - split_idx) ? split_idx : (needle_sz - split_idx);
+ shift++;
+ h_idx = 0;
+ while (h_idx <= haystack_sz - needle_sz) {
+ n_idx = split_idx;
+ while (n_idx < needle_sz && n[n_idx] == h[h_idx + n_idx])
+ n_idx++;
+
+ if (n_idx < needle_sz) {
+ h_idx += (n_idx - split_idx + 1);
+ } else {
+ n_idx = split_idx;
+ while (n_idx > 0 && n[n_idx - 1] == h[h_idx + n_idx - 1])
+ n_idx--;
+ if (n_idx == 0)
+ return (void *)(h + h_idx);
+ h_idx += shift;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+/**
+ * bpf_memmem - search for needle byte pattern in a flat memory buffer
+ * @haystack: pointer to haystack memory buffer
+ * @haystack__sz: size of haystack buffer in bytes
+ * @needle: pointer to byte pattern to search for
+ * @needle__sz: size of pattern in bytes
+ * @flags: reserved for future options (must be 0)
+ *
+ * Return:
+ * * >=0 - 0-based byte offset of match in haystack
+ * * %-ENOENT - needle was not found in haystack
+ * * %-EINVAL - invalid flags or parameters
+ * * %-E2BIG - haystack exceeds 2 MB or needle exceeds 4 KB
+ */
+__bpf_kfunc long bpf_memmem(const void *haystack, u32 haystack__sz,
+ const void *needle, u32 needle__sz,
+ u64 flags)
+{
+ const void *match;
+
+ if (flags)
+ return -EINVAL;
+ if (!haystack || !needle || needle__sz == 0 || haystack__sz == 0)
+ return -EINVAL;
+ if (needle__sz > haystack__sz)
+ return -EINVAL;
+ if (haystack__sz > BPF_MEMMEM_MAX_LEN || needle__sz > BPF_MEMMEM_MAX_NEEDLE_SZ)
+ return -E2BIG;
+
+ match = __bpf_memmem(haystack, haystack__sz, needle, needle__sz);
+ if (!match)
+ return -ENOENT;
+
+ return (long)((const char *)match - (const char *)haystack);
+}
+
+/**
+ * bpf_dynptr_memmem - search for needle within a dynamic pointer
+ * @haystack: pointer to dynptr representing the search buffer
+ * @needle: pointer to pattern to search for
+ * @needle__sz: size of pattern in bytes
+ * @flags: reserved for future options (must be 0)
+ *
+ * Return:
+ * * >=0 - 0-based byte offset of match in dynptr buffer
+ * * %-ENOENT - needle was not found
+ * * %-EINVAL - invalid flags, non-linear buffer, or parameters
+ * * %-E2BIG - dynptr buffer exceeds 2 MB or needle exceeds 4 KB
+ */
+__bpf_kfunc long bpf_dynptr_memmem(const struct bpf_dynptr *haystack,
+ const void *needle, u32 needle__sz,
+ u64 flags)
+{
+ struct bpf_dynptr_kern *ptr = (struct bpf_dynptr_kern *)haystack;
+ const void *data;
+ const void *match;
+ u64 size;
+
+ if (flags)
+ return -EINVAL;
+ if (!ptr || !needle || needle__sz == 0)
+ return -EINVAL;
+ if (needle__sz > BPF_MEMMEM_MAX_NEEDLE_SZ)
+ return -E2BIG;
+
+ size = __bpf_dynptr_size(ptr);
+ if (size > BPF_MEMMEM_MAX_LEN)
+ return -E2BIG;
+ if (size == 0 || needle__sz > size)
+ return -EINVAL;
+
+ data = __bpf_dynptr_data(ptr, size);
+ if (!data)
+ return -EINVAL;
+
+ match = __bpf_memmem(data, size, needle, needle__sz);
+ if (!match)
+ return -ENOENT;
+
+ return (long)((const char *)match - (const char *)data);
+}
+
__bpf_kfunc void *bpf_cast_to_kern_ctx(void *obj)
{
return obj;
@@ -5214,6 +5459,8 @@ BTF_ID_FLAGS(func, bpf_dynptr_size)
BTF_ID_FLAGS(func, bpf_dynptr_clone)
BTF_ID_FLAGS(func, bpf_dynptr_copy)
BTF_ID_FLAGS(func, bpf_dynptr_memset)
+BTF_ID_FLAGS(func, bpf_memmem)
+BTF_ID_FLAGS(func, bpf_dynptr_memmem)
#ifdef CONFIG_NET
BTF_ID_FLAGS(func, bpf_modify_return_test_tp)
#endif
--
2.53.0
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH bpf-next v3 2/2] selftests/bpf: Add selftests for bpf_memmem and bpf_dynptr_memmem kfuncs
2026-11-22 14:38 [PATCH bpf-next v3 0/2] bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs Abhishek Khade
2026-11-22 14:38 ` [PATCH bpf-next v3 1/2] " Abhishek Khade
@ 2026-11-22 14:38 ` Abhishek Khade
2026-11-22 15:17 ` bot+bpf-ci
1 sibling, 1 reply; 5+ messages in thread
From: Abhishek Khade @ 2026-11-22 14:38 UTC (permalink / raw)
To: bpf; +Cc: linux-kernel, ast, daniel, andrii, Abhishek Khade
Add automated BPF selftests validating in-kernel binary byte sequence
matching for bpf_memmem() and bpf_dynptr_memmem().
Covered test cases:
1. Binary pattern match across embedded null bytes (0x00).
2. Match at buffer start (offset 0).
3. Match at buffer end (haystack_sz - needle_sz).
4. Single-byte needle fastpath.
5. Non-matching pattern returning -ENOENT.
6. Multiple candidate occurrences returning the first match.
7. Overlapping candidate prefixes returning the correct match.
8. Exact match where needle equals haystack.
9. Needles larger than haystack returning -EINVAL.
10. Empty needle returning -EINVAL.
11. Invalid flags returning -EINVAL.
12. Oversized haystack (> 2 MB) returning -E2BIG.
13. Exact 2 MB boundary full scan.
14. Zero-length haystack returning -EINVAL.
15. Dynamic pointer (bpf_dynptr) searching across embedded nulls,
start, end, not found, size boundary, and error cases.
16. Periodic needle patterns validating Two-Way critical factorization.
17. Pathological repetitive prefix patterns validating linear-time immunity
without premature budget aborts.
Signed-off-by: Abhishek Khade <abhishekkhade69@gmail.com>
---
.../selftests/bpf/prog_tests/memmem_kfunc.c | 9 +
.../selftests/bpf/progs/memmem_kfunc.c | 299 ++++++++++++++++++
2 files changed, 308 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/memmem_kfunc.c
create mode 100644 tools/testing/selftests/bpf/progs/memmem_kfunc.c
diff --git a/tools/testing/selftests/bpf/prog_tests/memmem_kfunc.c b/tools/testing/selftests/bpf/prog_tests/memmem_kfunc.c
new file mode 100644
index 000000000..d27c9a2a2
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/memmem_kfunc.c
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2026 Abhishek Khade */
+#include <test_progs.h>
+#include "memmem_kfunc.skel.h"
+
+void test_memmem_kfunc(void)
+{
+ RUN_TESTS(memmem_kfunc);
+}
diff --git a/tools/testing/selftests/bpf/progs/memmem_kfunc.c b/tools/testing/selftests/bpf/progs/memmem_kfunc.c
new file mode 100644
index 000000000..eb8959068
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/memmem_kfunc.c
@@ -0,0 +1,299 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2026 Abhishek Khade */
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+#include "errno.h"
+
+char _license[] SEC("license") = "GPL";
+
+/* kfunc prototypes */
+long bpf_memmem(const void *haystack, u32 haystack__sz,
+ const void *needle, u32 needle__sz,
+ u64 flags) __ksym;
+
+long bpf_dynptr_memmem(const struct bpf_dynptr *haystack,
+ const void *needle, u32 needle__sz,
+ u64 flags) __ksym;
+
+static char bin_data[] = {
+ 0x16, 0x03, 0x01, 0x00, 0x02, 0xaa, 0xbb, 0x00, 0xff, 0x00, 0x55
+};
+
+static char needle_null[] = { 0x00, 0xff, 0x00 };
+static char needle_start[] = { 0x16, 0x03, 0x01 };
+static char needle_end[] = { 0x00, 0x55 };
+static char needle_single[] = { 0xaa };
+static char needle_notfound[] = { 0xde, 0xad };
+static char needle_repeat[] = { 0xaa, 0xbb, 0x00, 0xaa, 0xbb };
+static char needle_sub_repeat[] = { 0xaa, 0xbb };
+static char overlap_haystack[] = { 0xaa, 0xaa, 0xaa, 0xbb };
+static char overlap_needle[] = { 0xaa, 0xaa, 0xbb };
+static char periodic_buf[] = "abababac";
+static char periodic_needle[] = "ababac";
+static char rep_buf[] = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
+static char rep_needle[] = "aaaaaab";
+static char oversized_buf[2 * 1024 * 1024 + 1];
+
+/* 1. Flat memory buffer tests */
+
+SEC("syscall")
+__success __retval(7)
+int test_memmem_embedded_null(void *ctx)
+{
+ return bpf_memmem(bin_data, sizeof(bin_data),
+ needle_null, sizeof(needle_null), 0);
+}
+
+SEC("syscall")
+__success __retval(0)
+int test_memmem_start(void *ctx)
+{
+ return bpf_memmem(bin_data, sizeof(bin_data),
+ needle_start, sizeof(needle_start), 0);
+}
+
+SEC("syscall")
+__success __retval(9)
+int test_memmem_end(void *ctx)
+{
+ return bpf_memmem(bin_data, sizeof(bin_data),
+ needle_end, sizeof(needle_end), 0);
+}
+
+SEC("syscall")
+__success __retval(5)
+int test_memmem_single_byte(void *ctx)
+{
+ return bpf_memmem(bin_data, sizeof(bin_data),
+ needle_single, sizeof(needle_single), 0);
+}
+
+SEC("syscall")
+__success __retval(-ENOENT)
+int test_memmem_not_found(void *ctx)
+{
+ return bpf_memmem(bin_data, sizeof(bin_data),
+ needle_notfound, sizeof(needle_notfound), 0);
+}
+
+SEC("syscall")
+__success __retval(0)
+int test_memmem_first_occurrence(void *ctx)
+{
+ return bpf_memmem(needle_repeat, sizeof(needle_repeat),
+ needle_sub_repeat, sizeof(needle_sub_repeat), 0);
+}
+
+SEC("syscall")
+__success __retval(1)
+int test_memmem_overlapping_prefix(void *ctx)
+{
+ return bpf_memmem(overlap_haystack, sizeof(overlap_haystack),
+ overlap_needle, sizeof(overlap_needle), 0);
+}
+
+SEC("syscall")
+__success __retval(0)
+int test_memmem_exact_match(void *ctx)
+{
+ return bpf_memmem(needle_start, sizeof(needle_start),
+ needle_start, sizeof(needle_start), 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_memmem_needle_too_large(void *ctx)
+{
+ return bpf_memmem(needle_start, sizeof(needle_start),
+ bin_data, sizeof(bin_data), 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_memmem_empty_needle(void *ctx)
+{
+ return bpf_memmem(bin_data, sizeof(bin_data),
+ needle_start, 0, 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_memmem_invalid_flags(void *ctx)
+{
+ return bpf_memmem(bin_data, sizeof(bin_data),
+ needle_start, sizeof(needle_start), 1);
+}
+
+SEC("syscall")
+__success __retval(-E2BIG)
+int test_memmem_oversized_haystack(void *ctx)
+{
+ return bpf_memmem(oversized_buf, sizeof(oversized_buf),
+ needle_single, sizeof(needle_single), 0);
+}
+
+SEC("syscall")
+__success __retval(-ENOENT)
+int test_memmem_exact_2mb(void *ctx)
+{
+ return bpf_memmem(oversized_buf, 2 * 1024 * 1024,
+ needle_single, sizeof(needle_single), 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_memmem_zero_len_haystack(void *ctx)
+{
+ return bpf_memmem(bin_data, 0,
+ needle_single, sizeof(needle_single), 0);
+}
+
+SEC("syscall")
+__success __retval(2)
+int test_memmem_periodic_pattern(void *ctx)
+{
+ return bpf_memmem(periodic_buf, sizeof(periodic_buf) - 1,
+ periodic_needle, sizeof(periodic_needle) - 1, 0);
+}
+
+SEC("syscall")
+__success __retval(24)
+int test_memmem_repetitive_prefix(void *ctx)
+{
+ return bpf_memmem(rep_buf, sizeof(rep_buf) - 1,
+ rep_needle, sizeof(rep_needle) - 1, 0);
+}
+
+/* 2. Dynamic pointer (bpf_dynptr) tests */
+
+SEC("syscall")
+__success __retval(7)
+int test_dynptr_memmem_embedded_null(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)bin_data, sizeof(bin_data), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_null, sizeof(needle_null), 0);
+}
+
+SEC("syscall")
+__success __retval(0)
+int test_dynptr_memmem_start(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)bin_data, sizeof(bin_data), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_start, sizeof(needle_start), 0);
+}
+
+SEC("syscall")
+__success __retval(9)
+int test_dynptr_memmem_end(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)bin_data, sizeof(bin_data), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_end, sizeof(needle_end), 0);
+}
+
+SEC("syscall")
+__success __retval(0)
+int test_dynptr_memmem_exact_match(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)needle_start, sizeof(needle_start), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_start, sizeof(needle_start), 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_dynptr_memmem_needle_too_large(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)needle_start, sizeof(needle_start), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, bin_data, sizeof(bin_data), 0);
+}
+
+SEC("syscall")
+__success __retval(-ENOENT)
+int test_dynptr_memmem_not_found(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)bin_data, sizeof(bin_data), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_notfound, sizeof(needle_notfound), 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_dynptr_memmem_empty_needle(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)bin_data, sizeof(bin_data), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_start, 0, 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_dynptr_memmem_invalid_flags(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)bin_data, sizeof(bin_data), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_start, sizeof(needle_start), 1);
+}
+
+SEC("syscall")
+__success __retval(-E2BIG)
+int test_dynptr_memmem_oversized_haystack(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)oversized_buf, sizeof(oversized_buf), 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_single, sizeof(needle_single), 0);
+}
+
+SEC("syscall")
+__success __retval(-ENOENT)
+int test_dynptr_memmem_exact_2mb(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)oversized_buf, 2 * 1024 * 1024, 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_single, sizeof(needle_single), 0);
+}
+
+SEC("syscall")
+__success __retval(-EINVAL)
+int test_dynptr_memmem_zero_len_haystack(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)bin_data, 0, 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, needle_single, sizeof(needle_single), 0);
+}
+
+SEC("syscall")
+__success __retval(2)
+int test_dynptr_memmem_periodic_pattern(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)periodic_buf, sizeof(periodic_buf) - 1, 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, periodic_needle, sizeof(periodic_needle) - 1, 0);
+}
+
+SEC("syscall")
+__success __retval(24)
+int test_dynptr_memmem_repetitive_prefix(void *ctx)
+{
+ struct bpf_dynptr ptr;
+
+ bpf_dynptr_from_mem((void *)rep_buf, sizeof(rep_buf) - 1, 0, &ptr);
+ return bpf_dynptr_memmem(&ptr, rep_needle, sizeof(rep_needle) - 1, 0);
+}
--
2.53.0
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH bpf-next v3 2/2] selftests/bpf: Add selftests for bpf_memmem and bpf_dynptr_memmem kfuncs
2026-11-22 14:38 ` [PATCH bpf-next v3 2/2] selftests/bpf: Add selftests for " Abhishek Khade
@ 2026-11-22 15:17 ` bot+bpf-ci
0 siblings, 0 replies; 5+ messages in thread
From: bot+bpf-ci @ 2026-11-22 15:17 UTC (permalink / raw)
To: abhishekkhade69, bpf
Cc: linux-kernel, ast, daniel, andrii, abhishekkhade69, ast, andrii,
daniel, martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 3691 bytes --]
> selftests/bpf: Add selftests for bpf_memmem and bpf_dynptr_memmem kfuncs
TL;DR:
- Test issue: the "periodic" needle "ababac" appears to take the non-periodic
branch, so the periodic memory/shift logic goes untested
- Commit message overstates cases 16 and 17 (no timing or budget check)
> selftests/bpf: Add selftests for bpf_memmem and bpf_dynptr_memmem kfuncs
>
> Add automated BPF selftests validating in-kernel binary byte sequence
> matching for bpf_memmem() and bpf_dynptr_memmem().
> Covered test cases:
[ ... ]
> 16. Periodic needle patterns validating Two-Way critical factorization.
> 17. Pathological repetitive prefix patterns validating linear-time immunity
> without premature budget aborts.
> Signed-off-by: Abhishek Khade <abhishekkhade69@gmail.com>
This isn't a bug, but the list describes two cases as covering more than
the tests can show.
For item 16, the needle is periodic_needle = "ababac". Its shortest
period is its full length, 6. In __bpf_memmem(), bpf_max_suffix() returns
split 5 with period 1, and bpf_max_suffix_rev() returns split 0, so
split_idx = 5 and period = 1. memcmp("ababa", "babac", 5) is nonzero, so
the search takes the "Case 2: Non-periodic needle" branch. The expected
__retval(2) is what any correct substring search returns. The periodic
branch is actually reached by test_memmem_embedded_null, whose needle
{ 0x00, 0xff, 0x00 } has period 2.
For item 17, test_memmem_repetitive_prefix searches a 31-byte buffer for a
7-byte needle and checks only the offset (24). It does not measure time,
so a quadratic search would pass as well. The kfunc has no comparison
budget, so "without premature budget aborts" describes something this
series does not have.
Would it be more accurate to describe items 16 and 17 as correctness checks
on those inputs? Or could the periodic case use a needle that really is
periodic, for example "abab" or "aaa"? Could the changelog also say why
the cases were chosen instead of only listing them?
> diff --git a/tools/testing/selftests/bpf/progs/memmem_kfunc.c b/tools/testing/selftests/bpf/progs/memmem_kfunc.c
> new file mode 100644
> index 000000000000..eb895906811a
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/memmem_kfunc.c
> @@ -0,0 +1,299 @@
[ ... ]
> +static char periodic_buf[] = "abababac";
> +static char periodic_needle[] = "ababac";
[ ... ]
> +SEC("syscall")
> +__success __retval(2)
> +int test_memmem_periodic_pattern(void *ctx)
> +{
> + return bpf_memmem(periodic_buf, sizeof(periodic_buf) - 1,
> + periodic_needle, sizeof(periodic_needle) - 1, 0);
> +}
This isn't a bug, but is test_memmem_periodic_pattern() (and likewise
test_dynptr_memmem_periodic_pattern()) meant to exercise the periodic
branch of __bpf_memmem()?
As written, "ababac" takes the non-periodic branch: bpf_max_suffix() gives
split_idx = 5 with local period 1, and memcmp(n, n + 1, 5) ("ababa"
against "babac") differs, so the search returns 2 from the "Case 2:
Non-periodic needle" loop. Only needle_null ({0x00, 0xff, 0x00}: split 1,
period 2) reaches "Case 1: Periodic needle", and it matches on its first
full right-half comparison. So no test runs the
"h_idx += period; memory = needle_sz - period;" step or the
"n_idx = max(split_idx, memory)" restart with a nonzero memory.
Would a truly periodic needle that also forces a period shift, for example
"abab" searched in "bbababab" (expected 2), cover the memory logic of that
branch?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/45034767598
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH bpf-next v3 1/2] bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs
2026-11-22 14:38 ` [PATCH bpf-next v3 1/2] " Abhishek Khade
@ 2026-11-22 15:17 ` bot+bpf-ci
0 siblings, 0 replies; 5+ messages in thread
From: bot+bpf-ci @ 2026-11-22 15:17 UTC (permalink / raw)
To: abhishekkhade69, bpf
Cc: linux-kernel, ast, daniel, andrii, abhishekkhade69, ast, andrii,
daniel, martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 2783 bytes --]
> bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs
TL;DR: bpf_dynptr_memmem() may return -EINVAL for skb/xdp packets with
non-linear (frag) data, so packet searches can fail even when the needle is
present; the error is also ambiguous.
> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
[ ... ]
> +__bpf_kfunc long bpf_dynptr_memmem(const struct bpf_dynptr *haystack,
> + const void *needle, u32 needle__sz,
> + u64 flags)
> +{
[ ... ]
> + size = __bpf_dynptr_size(ptr);
> + if (size > BPF_MEMMEM_MAX_LEN)
> + return -E2BIG;
> + if (size == 0 || needle__sz > size)
> + return -EINVAL;
> +
> + data = __bpf_dynptr_data(ptr, size);
> + if (!data)
> + return -EINVAL;
Can this return -EINVAL for the packet inspection cases the commit message
describes?
__bpf_dynptr_data(ptr, size) is bpf_dynptr_slice(p, 0, NULL, size) with no
bounce buffer. For BPF_DYNPTR_TYPE_SKB that ends up in
skb_pointer_if_linear(), which returns NULL whenever size > skb_headlen(skb).
For BPF_DYNPTR_TYPE_XDP, bpf_xdp_pointer() returns NULL or an ERR_PTR when
the range crosses into frags or is larger than 0xffff. For
BPF_DYNPTR_TYPE_FILE, bpf_file_fetch_bytes() returns -EINVAL for a NULL
buffer, so it always fails.
A TC program calling bpf_dynptr_from_skb(skb, 0, &d) gets a dynptr covering
skb->len, and received skbs commonly keep most of their payload in page
frags. For a typical packet larger than the linear head, such as a TLS
ClientHello, the call fails even though the needle is present.
The neighbouring dynptr kfuncs handle non-linear data explicitly.
bpf_dynptr_memset() falls back to __bpf_dynptr_write() in chunks, and
bpf_dynptr_copy() falls back to __bpf_dynptr_read()/__bpf_dynptr_write().
The kernel-doc lists "non-linear buffer" under -EINVAL, but that code is
shared with invalid flags and invalid parameters (including needle__sz >
size). A program cannot tell "call bpf_skb_pull_data() and retry" from a
real argument error, nor from a packet that is simply shorter than the
needle, which arguably should be -ENOENT (bpf_strnstr() returns -ENOENT in
that case).
Should bpf_dynptr_memmem() search non-linear skb/xdp data, for example by
scanning slices with a needle_sz - 1 overlap, or at least return a distinct
error for the non-linear case? Should the commit message say that TC packet
payloads usually have to be linearized first?
> +
> + match = __bpf_memmem(data, size, needle, needle__sz);
> + if (!match)
> + return -ENOENT;
[ ... ]
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/45034767598
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2026-11-22 15:17 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-22 14:38 [PATCH bpf-next v3 0/2] bpf: Add bpf_memmem and bpf_dynptr_memmem kfuncs Abhishek Khade
2026-11-22 14:38 ` [PATCH bpf-next v3 1/2] " Abhishek Khade
2026-11-22 15:17 ` bot+bpf-ci
2026-11-22 14:38 ` [PATCH bpf-next v3 2/2] selftests/bpf: Add selftests for " Abhishek Khade
2026-11-22 15:17 ` bot+bpf-ci
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®