[PATCH 0/4] lib/textsearch: fix ts_bm resume offset, add tests, two small cleanups

[Bernard Ladenthin]

lib/ts_bm.c never updates state->offset. With the "bm" algorithm
textsearch_next() reports the first match over and over, and a caller
looping until UINT_MAX does not terminate. kmp_find() and fsm_find() both
update it. This is an inconsistency between implementations of one
interface, not a documented limitation of Boyer-Moore. It has been there
since ts_bm was added in 2005.

Patch 1 fixes it. Patch 2 adds the KUnit coverage that would have caught
it. lib/textsearch.c has had no tests since it was merged in 2005, and
every bug found in ts_bm.c since was found by inspection or by a user
running into it. The fix comes first, so the tree is never left with a
failing test.

Patches 3 and 4 turned up while writing the tests. Both are independent
and can be dropped without affecting the rest.

3 struct ts_state.cb is cast to structures containing pointers but is
not aligned for them, unlike skb->cb. Latent today, since the only
in-tree ts_state is a stack local.

4 ts_fsm only reports a match once the data is exhausted, which the file
header does not mention. Documentation only.

A related patch was turned down in 2017 with "There are no users of this
functionality. Once you add one, you can submit this patch alongside of
it." [1]. That is what patch 2 does. The tests are the first in-tree caller
of textsearch_next(). Patch 1 is not marked for stable, since no in-tree
code was affected before this series.

Testing. The suite is 20 cases, 10 against each of the two algorithms, and
passes. Without patch 1, ts_next_advances, ts_next_finds_all and
ts_blocks_iteration_terminates fail for "bm". It ran under UML and on a
real x86_64 kernel in QEMU, with CONFIG_KASAN=y and again with
CONFIG_KMSAN=y (clang), while driving packets through iptables -m string.
No sanitizer reports in either.

textsearch has no MAINTAINERS entry. get_maintainer.pl routes patches 1, 2
and 4 to LIBRARY CODE. include/linux/textsearch.h, touched by patch 3, is
covered by no entry at all. Netfilter is on Cc as the only in-tree user,
kunit-dev for the new suite. lib/tests/textsearch_kunit.c would want a
MAINTAINERS entry of its own, but that means naming a maintainer for
textsearch, which I did not want to do unilaterally.

The kernel-doc of skb_find_text() still tells callers to use
textsearch_next(), which has been impossible since commit 059a2440fd3c
("net: Remove state argument from skb_find_text()"). A fix was posted and
acked in 2017 [2] but never applied. That is a net/ change and will be sent
separately.

This is my first kernel submission. Corrections on anything I got wrong in
the process are welcome.

[1] https://lore.kernel.org/all/20170207.105320.456...@davemloft.net/
[2] https://lore.kernel.org/all/20170208084455.GA1878@salvia/

Bernard Ladenthin (4):
lib/ts_bm: advance state->offset past the reported match
lib/tests: add KUnit tests for the textsearch infrastructure
textsearch: align ts_state.cb like skb->cb
lib/ts_fsm: document that a match must consume the remaining data

include/linux/textsearch.h | 2 +-
lib/Kconfig.debug | 19 ++
lib/tests/Makefile | 1 +
lib/tests/textsearch_kunit.c | 327 +++++++++++++++++++++++++++++++++++
lib/ts_bm.c | 3 +-
lib/ts_fsm.c | 7 +
6 files changed, 357 insertions(+), 2 deletions(-)
create mode 100644 lib/tests/textsearch_kunit.c


base-commit: 075b74841bd0065a3bda3440873c747938e69b68
--
2.49.0.windows.1

[Bernard Ladenthin]

bm_find() reads state->offset to decide where to resume, but never writes
it back. textsearch_find() zeroes state->offset before the first call.
textsearch_next() then relies on the algorithm having moved it past the
match it just reported. With the "bm" algorithm every textsearch_next()
call restarts from the same place and re-reports the first match. A caller
looping until UINT_MAX never terminates.

Searching "xxABxxABxx" for "AB" reports offset 2 on every call. The match
at offset 6 is never reached. kmp_find() and fsm_find() both update
state->offset already. This is an inconsistency between implementations of

one interface, not a documented limitation of Boyer-Moore.

Set state->offset to the end of the match and derive the return value from
it, mirroring kmp_find().

No in-tree code called textsearch_next() before this series. The KUnit
tests added in the following patch are the first. The function is exported
though, and lib/textsearch.c documents it as the way to fetch subsequent
occurrences "regardless of the linearity of the data". Which algorithm a
caller selected should not decide whether that works. xt_string lets
userspace pick the algorithm, so "bm" is a live choice.

skb_find_text() also mentions textsearch_next() in its kernel-doc. That
comment has been stale since commit 059a2440fd3c ("net: Remove state
argument from skb_find_text()") moved ts_state into the function's own
scope. It is not evidence of a working caller.

Fixes: 8082e4ed0a61 ("[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2")
Signed-off-by: Bernard Ladenthin <bernard....@gmail.com>
---

This is my first kernel submission. Corrections on anything I got wrong in
the process are welcome.

lib/ts_bm.c | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/ts_bm.c b/lib/ts_bm.c
index 676105e84005..eacc49e64c56 100644
--- a/lib/ts_bm.c
+++ b/lib/ts_bm.c
@@ -98,7 +98,8 @@ static unsigned int bm_find(struct ts_config *conf, struct ts_state *state)
if (i == bm->patlen) {
/* London calling... */
DEBUGP("found!\n");
- return consumed + (shift-(bm->patlen-1));
+ state->offset = consumed + shift + 1;
+ return state->offset - bm->patlen;
}

bs = bm->bad_shift[text[shift-i]];
--
2.49.0.windows.1

[Bernard Ladenthin]

lib/textsearch.c and the algorithms registered with it have had no test
coverage since the infrastructure was added in 2005. Every bug found in
lib/ts_bm.c since then was found by inspection, or by a user hitting it in
production:

commit 3f330317ab49 ("[TEXTSEARCH]: Fix broken good shift array calculation in Boyer-Moore")
commit 3ffaa8c7c0f8 ("[TEXTSEARCH]: Fix Boyer Moore initialization bug")
commit aebb6a849cfe ("textsearch: fix Boyer-Moore text search bug")
commit 6f67fbf8192d ("lib/ts_bm: reset initial match offset for every block of text")
commit 9003ec6f7f39 ("lib/ts_bm: fix integer overflow in pattern length calculation")

Add a KUnit suite that runs the same cases against every algorithm taking
a plain byte-string pattern. All implementations are then held to the same
interface contract. The cases cover matches at the start, middle and end
of the text, the absence of a match, pattern accessors, rejection of
zero-length patterns, and that textsearch_next() advances and eventually
terminates.

Three of the five fixes listed above concern multi-block handling. The
suite therefore also drives the algorithms through a get_next_block() that
hands the text out in fixed-size chunks, the way skb_seq_read() does.
Those cases check what has to hold for any block layout. A match contained
in a single block is found. Every reported offset is a real match.
Iteration makes progress and terminates. Matches spanning a block boundary
are left alone, since ts_bm documents those as missed while ts_kmp finds
them.

ts_fsm is not covered. fsm_init() consumes an array of struct ts_fsm_token
rather than a byte string, so it cannot share these test vectors.

The loop in ts_next_advances is bounded. An algorithm that fails to
advance then reports a failure instead of hanging the test run.

Signed-off-by: Bernard Ladenthin <bernard....@gmail.com>
---

This is my first kernel submission. Corrections on anything I got wrong in
the process are welcome.

lib/Kconfig.debug | 19 ++
lib/tests/Makefile | 1 +
lib/tests/textsearch_kunit.c | 327 +++++++++++++++++++++++++++++++++++

3 files changed, 347 insertions(+)
create mode 100644 lib/tests/textsearch_kunit.c

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 1244dcac2294..783cf6bf1469 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -3531,6 +3531,25 @@ config GLOB_KUNIT_TEST

If unsure, say N

+config TEXTSEARCH_KUNIT_TEST
+ tristate "Textsearch infrastructure test" if !KUNIT_ALL_TESTS
+ depends on KUNIT
+ select TEXTSEARCH
+ select TEXTSEARCH_KMP
+ select TEXTSEARCH_BM
+ default KUNIT_ALL_TESTS
+ help
+ Enable this option to test the textsearch infrastructure at
+ runtime.
+
+ This test suite exercises lib/textsearch.c together with the
+ string-pattern algorithms registered with it. The same cases are
+ run against every algorithm, checking the reported match offsets
+ and that repeated searches over one buffer make progress and
+ terminate.
+
+ If unsure, say N
+
endif # RUNTIME_TESTING_MENU

config ARCH_USE_MEMTEST
diff --git a/lib/tests/Makefile b/lib/tests/Makefile
index 4ead57602eac..a2d0390c18d4 100644
--- a/lib/tests/Makefile
+++ b/lib/tests/Makefile
@@ -54,6 +54,7 @@ CFLAGS_stackinit_kunit.o += $(call cc-disable-warning, switch-unreachable)
obj-$(CONFIG_STACKINIT_KUNIT_TEST) += stackinit_kunit.o
obj-$(CONFIG_STRING_KUNIT_TEST) += string_kunit.o
obj-$(CONFIG_STRING_HELPERS_KUNIT_TEST) += string_helpers_kunit.o
+obj-$(CONFIG_TEXTSEARCH_KUNIT_TEST) += textsearch_kunit.o
obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o
obj-$(CONFIG_UTIL_MACROS_KUNIT) += util_macros_kunit.o
obj-$(CONFIG_RATELIMIT_KUNIT_TEST) += test_ratelimit.o
diff --git a/lib/tests/textsearch_kunit.c b/lib/tests/textsearch_kunit.c
new file mode 100644
index 000000000000..b8a79240366d
--- /dev/null
+++ b/lib/tests/textsearch_kunit.c
@@ -0,0 +1,327 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * KUnit tests for the textsearch infrastructure.
+ *
+ * The cases below are run against every string-pattern algorithm registered
+ * with lib/textsearch.c, so that all implementations are held to the same
+ * interface contract.
+ *
+ * ts_fsm is deliberately not covered: fsm_init() consumes an array of
+ * struct ts_fsm_token rather than a plain byte string, so it cannot share
+ * these test vectors.
+ */
+
+#include <kunit/test.h>
+#include <linux/err.h>
+#include <linux/kernel.h>
+#include <linux/slab.h>
+#include <linux/string.h>
+#include <linux/textsearch.h>
+
+static const char * const ts_algo_names[] = { "kmp", "bm" };
+
+static void ts_algo_desc(const char * const *algo, char *desc)
+{
+ strscpy(desc, *algo, KUNIT_PARAM_DESC_SIZE);
+}
+
+KUNIT_ARRAY_PARAM(ts_algo, ts_algo_names, ts_algo_desc);
+
+/*
+ * Build a configuration for the algorithm under test. Skips the case rather
+ * than failing it when the algorithm is not registered, so that a kernel
+ * built without, say, CONFIG_TEXTSEARCH_BM still reports cleanly.
+ */
+static struct ts_config *ts_conf_get(struct kunit *test, const char *pattern)
+{
+ const char *algo = *(const char * const *)test->param_value;
+ struct ts_config *conf;
+
+ conf = textsearch_prepare(algo, pattern, strlen(pattern),
+ GFP_KERNEL, TS_AUTOLOAD);
+ if (IS_ERR(conf))
+ kunit_skip(test, "algorithm \"%s\" not registered (%pe)",
+ algo, conf);
+
+ return conf;
+}
+
+static void ts_find_middle(struct kunit *test)
+{
+ static const char text[] = "We dance the funky chicken";
+ static const char pattern[] = "chicken";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ struct ts_state state;
+
+ KUNIT_EXPECT_EQ(test,
+ textsearch_find_continuous(conf, &state, text,
+ strlen(text)),
+ strlen(text) - strlen(pattern));
+
+ textsearch_destroy(conf);
+}
+
+static void ts_find_at_start(struct kunit *test)
+{
+ static const char text[] = "abcdefg";
+ static const char pattern[] = "abc";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ struct ts_state state;
+
+ KUNIT_EXPECT_EQ(test,
+ textsearch_find_continuous(conf, &state, text,
+ strlen(text)),
+ 0);
+
+ textsearch_destroy(conf);
+}
+
+static void ts_find_at_end(struct kunit *test)
+{
+ static const char text[] = "abcdefg";
+ static const char pattern[] = "efg";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ struct ts_state state;
+
+ KUNIT_EXPECT_EQ(test,
+ textsearch_find_continuous(conf, &state, text,
+ strlen(text)),
+ 4);
+
+ textsearch_destroy(conf);
+}
+
+static void ts_find_no_match(struct kunit *test)
+{
+ static const char text[] = "abcdefg";
+ static const char pattern[] = "xyz";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ struct ts_state state;
+
+ KUNIT_EXPECT_EQ(test,
+ textsearch_find_continuous(conf, &state, text,
+ strlen(text)),
+ UINT_MAX);
+
+ textsearch_destroy(conf);
+}
+
+/*
+ * textsearch_find() resets state->offset and textsearch_next() relies on the
+ * algorithm having advanced it past the match it just reported. An algorithm
+ * that leaves state->offset alone reports the same position forever.
+ */
+static void ts_next_advances(struct kunit *test)
+{
+ static const char text[] = "aaaa";
+ static const char pattern[] = "aa";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ unsigned int pos, prev;
+ struct ts_state state;
+ int i;
+
+ pos = textsearch_find_continuous(conf, &state, text, strlen(text));
+ KUNIT_ASSERT_EQ(test, pos, 0);
+
+ /* Bounded so that a non-advancing algorithm fails instead of hanging. */
+ for (i = 0; i < 8; i++) {
+ prev = pos;
+
+ pos = textsearch_next(conf, &state);
+ if (pos == UINT_MAX)
+ break;
+
+ KUNIT_ASSERT_GT_MSG(test, pos, prev,
+ "textsearch_next() reported %u after %u; it must advance past the previous match",
+ pos, prev);
+ }
+
+ KUNIT_EXPECT_EQ_MSG(test, pos, UINT_MAX,
+ "search did not terminate within 8 iterations");
+
+ textsearch_destroy(conf);
+}
+
+/* The full set of matches must be reported exactly once, in order. */
+static void ts_next_finds_all(struct kunit *test)
+{
+ static const char text[] = "xxABxxABxx";
+ static const char pattern[] = "AB";
+ static const unsigned int expect[] = { 2, 6 };
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ struct ts_state state;
+ unsigned int pos;
+ int i;
+
+ pos = textsearch_find_continuous(conf, &state, text, strlen(text));
+
+ for (i = 0; i < ARRAY_SIZE(expect); i++) {
+ KUNIT_ASSERT_EQ_MSG(test, pos, expect[i],
+ "match %d: expected offset %u, got %u",
+ i, expect[i], pos);
+ pos = textsearch_next(conf, &state);
+ }
+
+ KUNIT_EXPECT_EQ_MSG(test, pos, UINT_MAX,
+ "expected exactly %zu matches", ARRAY_SIZE(expect));
+
+ textsearch_destroy(conf);
+}
+
+/*
+ * A block source that hands the text out in fixed-size chunks, so that the
+ * algorithms are driven the way a non-linear skb drives them. Boundaries sit
+ * at multiples of @chunk, mirroring skb_seq_read().
+ */
+struct ts_chunk_state {
+ const char *data;
+ unsigned int len;
+ unsigned int chunk;
+};
+
+static unsigned int ts_get_chunk(unsigned int consumed, const u8 **dst,
+ struct ts_config *conf,
+ struct ts_state *state)
+{
+ struct ts_chunk_state *cs = (struct ts_chunk_state *)state->cb;
+ unsigned int end;
+
+ if (consumed >= cs->len)
+ return 0;
+
+ end = (consumed / cs->chunk + 1) * cs->chunk;
+ if (end > cs->len)
+ end = cs->len;
+
+ *dst = (const u8 *)cs->data + consumed;
+ return end - consumed;
+}
+
+static unsigned int ts_find_chunked(struct ts_config *conf,
+ struct ts_state *state, const char *text,
+ unsigned int len, unsigned int chunk)
+{
+ struct ts_chunk_state *cs = (struct ts_chunk_state *)state->cb;
+
+ BUILD_BUG_ON(sizeof(struct ts_chunk_state) > sizeof(state->cb));
+
+ conf->get_next_block = ts_get_chunk;
+ cs->data = text;
+ cs->len = len;
+ cs->chunk = chunk;
+
+ return textsearch_find(conf, state);
+}
+
+/*
+ * A match that lies entirely inside one block must be found no matter how the
+ * text is split up. Matches spanning a block boundary are deliberately not
+ * covered: ts_bm documents those as missed, ts_kmp finds them.
+ */
+static void ts_blocks_match_within_block(struct kunit *test)
+{
+ static const char text[] = "xxxxABCDxxxx";
+ static const char pattern[] = "ABCD";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ struct ts_state state;
+
+ /* chunk 4 puts "ABCD" exactly in the second block */
+ KUNIT_EXPECT_EQ_MSG(test,
+ ts_find_chunked(conf, &state, text,
+ strlen(text), 4),
+ 4, "match inside a single block must be found");
+
+ /* one block for the whole text must agree with the chunked run */
+ KUNIT_EXPECT_EQ(test,
+ ts_find_chunked(conf, &state, text, strlen(text),
+ strlen(text)),
+ 4);
+
+ textsearch_destroy(conf);
+}
+
+/* Iterating over a chunked buffer must terminate and must make progress. */
+static void ts_blocks_iteration_terminates(struct kunit *test)
+{
+ static const char text[] = "abababababab";
+ static const char pattern[] = "ab";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+ unsigned int chunk, pos, prev;
+ struct ts_state state;
+ int i;
+
+ for (chunk = 1; chunk <= strlen(text); chunk++) {
+ pos = ts_find_chunked(conf, &state, text, strlen(text), chunk);
+
+ for (i = 0; i < 32 && pos != UINT_MAX; i++) {
+ KUNIT_ASSERT_LE_MSG(test, pos + strlen(pattern),
+ strlen(text),
+ "chunk %u: reported match at %u runs past the text",
+ chunk, pos);
+ KUNIT_ASSERT_MEMEQ_MSG(test, text + pos, pattern,
+ strlen(pattern),
+ "chunk %u: offset %u is not a real match",
+ chunk, pos);
+ prev = pos;
+ pos = textsearch_next(conf, &state);
+ if (pos == UINT_MAX)
+ break;
+ KUNIT_ASSERT_GT_MSG(test, pos, prev,
+ "chunk %u: reported %u after %u",
+ chunk, pos, prev);
+ }
+
+ KUNIT_EXPECT_EQ_MSG(test, pos, UINT_MAX,
+ "chunk %u: search did not terminate", chunk);
+ }
+
+ textsearch_destroy(conf);
+}
+
+static void ts_get_pattern(struct kunit *test)
+{
+ static const char pattern[] = "chicken";
+ struct ts_config *conf = ts_conf_get(test, pattern);
+
+ KUNIT_EXPECT_EQ(test, textsearch_get_pattern_len(conf),
+ strlen(pattern));
+ KUNIT_EXPECT_MEMEQ(test, textsearch_get_pattern(conf), pattern,
+ strlen(pattern));
+
+ textsearch_destroy(conf);
+}
+
+/* textsearch_prepare() documents -EINVAL for a zero-length pattern. */
+static void ts_prepare_zero_len(struct kunit *test)
+{
+ const char *algo = *(const char * const *)test->param_value;
+ struct ts_config *conf;
+
+ conf = textsearch_prepare(algo, "", 0, GFP_KERNEL, TS_AUTOLOAD);
+ KUNIT_ASSERT_TRUE(test, IS_ERR(conf));
+ KUNIT_EXPECT_EQ(test, PTR_ERR(conf), -EINVAL);
+}
+
+static struct kunit_case textsearch_test_cases[] = {
+ KUNIT_CASE_PARAM(ts_find_middle, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_find_at_start, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_find_at_end, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_find_no_match, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_next_advances, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_next_finds_all, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_blocks_match_within_block, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_blocks_iteration_terminates, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_get_pattern, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_prepare_zero_len, ts_algo_gen_params),
+ {}
+};
+
+static struct kunit_suite textsearch_test_suite = {
+ .name = "textsearch",
+ .test_cases = textsearch_test_cases,
+};
+
+kunit_test_suite(textsearch_test_suite);
+
+MODULE_DESCRIPTION("KUnit tests for the textsearch infrastructure");
+MODULE_LICENSE("GPL");
--
2.49.0.windows.1

[Bernard Ladenthin]

struct ts_state carries a 48-byte control buffer that callers cast to
their own state structure. lib/textsearch.c casts it to struct
ts_linear_state. net/core/skbuff.c casts it to struct skb_seq_state via
TS_SKB_CB(). Both contain pointers and so need 8-byte alignment on 64-bit.

cb sits at offset 4, right after the unsigned int offset field, and struct
ts_state itself has only 4-byte alignment. Any allocation aligned to 8 or
more therefore places cb on a 4-mod-8 address. kmalloc() guarantees at
least ARCH_KMALLOC_MINALIGN, which is 8 or larger, so a heap-allocated
ts_state has a misaligned cb every time. For a stack-allocated one it
depends on where the compiler happens to put it.

No in-tree caller is affected today. The only struct ts_state is a stack
local in skb_find_text(). The cast is undefined behaviour regardless, and
on architectures without efficient unaligned access it is a trap for
whoever allocates one of these on the heap.

struct sk_buff already marks its cb[48] __aligned(8) for exactly this
reason. Do the same here.

Signed-off-by: Bernard Ladenthin <bernard....@gmail.com>
---

This is my first kernel submission. Corrections on anything I got wrong in
the process are welcome.

include/linux/textsearch.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/textsearch.h b/include/linux/textsearch.h
index 4933777404d6..e117f9c9de59 100644
--- a/include/linux/textsearch.h
+++ b/include/linux/textsearch.h
@@ -23,7 +23,7 @@ struct ts_config;
struct ts_state
{
unsigned int offset;
- char cb[48];
+ char cb[48] __aligned(8);
};

/**
--
2.49.0.windows.1

[Bernard Ladenthin]

fsm_find() reports a match only once the token chain has matched and the
data is exhausted:

for (tok_idx = 0; tok_idx < fsm->ntokens; tok_idx++) { ... }

if (end_of_data())
goto found_match;
no_match:
return UINT_MAX;

A chain of three specific tokens therefore matches the text "abc" but not
"abcd". [TS_FSM_HEAD_IGNORE, a, b] does not find "ab" in "xxabyy".
Searching for a pattern in the middle of the data needs TS_FSM_HEAD_IGNORE
at the front and a TS_FSM_ANY token at the end. The latter short-circuits
through "if (next == NULL) goto found_match".

The file header explains the head anchoring but says nothing about the
tail, which makes the interface easy to misuse. Describe it.

This documents the behaviour as it stands. If the end-of-data requirement
is not intended, the fix belongs in fsm_find() and this patch should be
dropped in favour of that.

Signed-off-by: Bernard Ladenthin <bernard....@gmail.com>
---

This is my first kernel submission. Corrections on anything I got wrong in
the process are welcome.

lib/ts_fsm.c | 7 +++++++
1 file changed, 7 insertions(+)

diff --git a/lib/ts_fsm.c b/lib/ts_fsm.c
index 053615f4fcd7..ceec6295505c 100644
--- a/lib/ts_fsm.c
+++ b/lib/ts_fsm.c
@@ -18,6 +18,13 @@
* is enabled by default and can be disabled by inserting
* TS_FSM_HEAD_IGNORE as the first token in the chain.
*
+ * A match is only reported once the data has been consumed as well: the
+ * token chain has to account for every remaining octet, not just for the
+ * pattern itself. A chain of three specific tokens therefore matches the
+ * text "abc" but not "abcd". To look for a pattern somewhere in the
+ * middle of the data, prepend a token with TS_FSM_HEAD_IGNORE and append
+ * one with TS_FSM_ANY, the latter matching whatever follows.
+ *
* The runtime performance of the algorithm should be around O(n),
* however while in strict mode the average runtime can be better.
*/
--
2.49.0.windows.1

[Pablo Neira Ayuso]

On Sun, Aug 16, 2026 at 07:05:37PM +0200, Bernard Ladenthin wrote:
> bm_find() reads state->offset to decide where to resume, but never writes
> it back. textsearch_find() zeroes state->offset before the first call.
> textsearch_next() then relies on the algorithm having moved it past the
> match it just reported. With the "bm" algorithm every textsearch_next()
> call restarts from the same place and re-reports the first match. A caller
> looping until UINT_MAX never terminates.

Yes, for a good reason.

> Searching "xxABxxABxx" for "AB" reports offset 2 on every call. The match
> at offset 6 is never reached.

With bm, it reports offset 6, because it looks from right to left,
this is how the original Boyer-Moore algorithm works.

> kmp_find() and fsm_find() both update state->offset already. This is
> an inconsistency between implementations of one interface, not a
> documented limitation of Boyer-Moore.
>
> Set state->offset to the end of the match and derive the return value from
> it, mirroring kmp_find().

Why? What do you get by setting state->offset?

What are you trying to fix?

> No in-tree code called textsearch_next() before this series. The KUnit
> tests added in the following patch are the first. The function is exported
> though, and lib/textsearch.c documents it as the way to fetch subsequent
> occurrences "regardless of the linearity of the data". Which algorithm a
> caller selected should not decide whether that works.

Why?

> xt_string lets userspace pick the algorithm, so "bm" is a live
> choice.

Yes, and people that use it rely on the current behaviour, so you have
to explain what you are aiming at fixing.

> skb_find_text() also mentions textsearch_next() in its kernel-doc. That
> comment has been stale since commit 059a2440fd3c ("net: Remove state
> argument from skb_find_text()") moved ts_state into the function's own
> scope. It is not evidence of a working caller.
>
> Fixes: 8082e4ed0a61 ("[LIB]: Boyer-Moore extension for textsearch infrastructure strike #2")
> Signed-off-by: Bernard Ladenthin <bernard....@gmail.com>
> ---
> This is my first kernel submission. Corrections on anything I got wrong in
> the process are welcome.

You are not specifying any tree for this patches.

[Bernard Ladenthin]

On Sun, Aug 16, 2026 at 10:37:51PM +0200, Pablo Neira Ayuso wrote:
> > A caller looping until UINT_MAX never terminates.
>
> Yes, for a good reason.

Thanks for the review. Let me start with the question I actually have.

One interface, three implementations. The same test, unchanged, run
against each of them. kmp passes it, bm fails it. I cannot find where
that difference is written down, and that is what I would like to
understand.

Where I looked. include/linux/textsearch.h:20 describes the field as

* @offset: offset for next match

and lib/textsearch.c:72 says

* Subsequent occurrences can be found by calling textsearch_next()
* regardless of the linearity of the data.

Both are from 2005 and neither has changed. ts_bm.c does record one
deviation from the other algorithms, in its file header, that a match
spread over multiple blocks will be missed and that kmp should be used
when that matters. It says nothing about repeating the same offset.

If what you mean is that the algorithm as Boyer and Moore published it
stops at the first match and therefore defines no shift after one, that
is true, and it may well be how this came about. kmp_find() faces the
same question and answers it in two lines, and patch 1 is those same two
lines:

kmp: state->offset = consumed + i + 1;
return state->offset - kmp->pattern_len;

bm: state->offset = consumed + shift + 1;

return state->offset - bm->patlen;

So the question is not really about Boyer-Moore. It is about why two
backends of one interface answer the same question differently, with
nothing saying which answer is the intended one.

> With bm, it reports offset 6, because it looks from right to left,
> this is how the original Boyer-Moore algorithm works.

I put that into a test case. The diff at the end adds it,
parameterised like the others, so it makes the same claim about kmp and
about bm. Applying it turns the suite red on purpose.

Patch 2 applies without patch 1 and does not touch lib/ts_bm.c, so this
describes today's behaviour:

echo CONFIG_KUNIT=y > .kunitconfig
echo CONFIG_TEXTSEARCH_KUNIT_TEST=y >> .kunitconfig
./tools/testing/kunit/kunit.py run --arch=um \
--kunitconfig=.kunitconfig "textsearch.*"

In the output below I cut the "at lib/tests/..." suffix so the lines
fit, nothing else is changed:

============ ts_first_match_is_last_occurrence ============
[FAILED] kmp
# ts_first_match_is_last_occurrence: EXPECTATION FAILED
Expected pos == 6, but
pos == 2 (0x2)

first match reported
[FAILED] bm
# ts_first_match_is_last_occurrence: EXPECTATION FAILED
Expected pos == 6, but
pos == 2 (0x2)

first match reported

Both report 2, so the first match is the same for either algorithm. If
that case asserts the wrong thing, please tell me what it should assert.
The run also gives

# Totals: pass:17 fail:5 skip:0 total:22

Two of the five are that case, red by design. The other three are bm, in
ts_next_advances, ts_next_finds_all and ts_blocks_iteration_terminates.
Every kmp case passes.

> Why? What do you get by setting state->offset?
>
> What are you trying to fix?

I should be plain about the scope. Nothing in the tree calls
textsearch_next(), and as far as I can tell nothing ever has. I checked
the whole history with git log -S over 1.46 million commits back to
2.6.12-rc2, which covers the entire life of lib/textsearch.c. So this
repairs no reported breakage, and I am not claiming otherwise.

What led me here is that lib/ts_bm.c has needed five correctness fixes
in twenty-one years. In 2008 a pattern at the very start of the text was
never found, "abc" in "abcdefg" returned nothing, and that had been true
since 2005. In 2023 an iptables rule with --algo bm silently stopped
matching, reported through bugzilla.netfilter.org #1390 and fixed by
6f67fbf8192d. Neither was caught by a test, because there were none.

That is why patch 2 exists, and it is the patch I care about most.

Which brings me to a basic question. Why has this code never had tests?
I looked and found none, and git ls-tree agrees with me, but I may have
missed them. If there are any, I would rather extend those than add a
new file.

I ask because the suite does find two of those old bugs when they are
put back on a current tree:

the 2008 one, shift = bm->patlen instead of bm->patlen - 1
ts_find_at_start red for bm, green for kmp

the 2023 one, revert 6f67fbf8192d
ts_blocks_match_within_block red for bm, green for kmp

Not all five, to be clear. The 2026 overflow it does not catch, because
textsearch_prepare() rejects the zero length before the algorithm sees
it. The two from 2006 I did not try to put back, the code around them
has moved too far for that to mean anything.

> > Which algorithm a caller selected should not decide whether that
> > works.
>
> Why?

Because the promise is made at the interface, not per algorithm.
lib/textsearch.c and include/linux/textsearch.h describe
textsearch_next() without naming one, while lib/ts_bm.c lists its own
deviation in its own header. And xt_string.c:56 hands conf->algo
straight from userspace to textsearch_prepare(), so the caller cannot
know in advance which of the two behaviours it will get.

> Yes, and people that use it rely on the current behaviour, so you have
> to explain what you are aiming at fixing.

Nothing observable changes for them. The returned value is the same
expression:

before: consumed + (shift - (bm->patlen - 1))
after: state->offset - bm->patlen,
with state->offset = consumed + shift + 1

Both are consumed + shift + 1 - bm->patlen. The patch only writes down
the offset the return statement already implied. skb_find_text() keeps
its ts_state on its own stack and uses only the return value, and
xt_string reads only that return value, so no netfilter path can observe
the write.

> You are not specifying any tree for this patches.

Sorry about that. get_maintainer.pl points at LIBRARY CODE for these
files, so the series is aimed at Andrew Morton, and I should have said
so in the subject. I will use a prefix on the next posting.

So my request is not that patch 1 be applied. It is that the difference
be explained or written down. If bm is meant to be single shot, I will
send a patch saying so in the same place the multi-block limitation is
already stated, and drop patch 1. And if the Fixes: tag looks wrong for
something nothing can reach today, I am happy to drop that too and let
patch 1 stand as a follow-on to the tests.

The case below is not meant for merging. It is your sentence written
as a test.

Thanks,
Bernard

---
--- a/lib/tests/textsearch_kunit.c
+++ b/lib/tests/textsearch_kunit.c
@@ -302,6 +302,26 @@
KUNIT_EXPECT_EQ(test, PTR_ERR(conf), -EINVAL);
}

+/*
+ * Not part of the contract the other cases check, and not meant to be
+ * merged. It encodes the description that "bm" reports the last
+ * occurrence first, so that the claim can be run. It is parameterised
+ * like the rest, so it makes the same claim about kmp and about bm.
+ */
+static void ts_first_match_is_last_occurrence(struct kunit *test)

+{
+ static const char text[] = "xxABxxABxx";
+ static const char pattern[] = "AB";

+ struct ts_config *conf = ts_conf_get(test, pattern);
+ struct ts_state state;
+ unsigned int pos;
+

+ pos = textsearch_find_continuous(conf, &state, text, strlen(text));

+ KUNIT_EXPECT_EQ_MSG(test, pos, 6, "first match reported");

+
+ textsearch_destroy(conf);
+}
+

static struct kunit_case textsearch_test_cases[] = {
KUNIT_CASE_PARAM(ts_find_middle, ts_algo_gen_params),
KUNIT_CASE_PARAM(ts_find_at_start, ts_algo_gen_params),
@@ -313,6 +333,7 @@
KUNIT_CASE_PARAM(ts_blocks_iteration_terminates, ts_algo_gen_params),
KUNIT_CASE_PARAM(ts_get_pattern, ts_algo_gen_params),
KUNIT_CASE_PARAM(ts_prepare_zero_len, ts_algo_gen_params),
+ KUNIT_CASE_PARAM(ts_first_match_is_last_occurrence, ts_algo_gen_params),
{}
};