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

[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),
 	{}
 };