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

[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.45609559819874123.davem@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

[PATCH 1/4] lib/ts_bm: advance state->offset past the reported match

[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.ladenthin@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

[PATCH 2/4] lib/tests: add KUnit tests for the textsearch infrastructure

[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.ladenthin@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

[PATCH 3/4] textsearch: align ts_state.cb like skb->cb

[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.ladenthin@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

[PATCH 4/4] lib/ts_fsm: document that a match must consume the remaining data

[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.ladenthin@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

Re: [PATCH 1/4] lib/ts_bm: advance state->offset past the reported match

[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.ladenthin@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.

> 
>  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
>