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

[Pablo Neira Ayuso <pablo@netfilter.org>]

Hi,

First off, I cannot believe you wrote such a lengthy text... this can
be only generated by LLM.

On Mon, Sep 07, 2026 at 12:19:54AM +0200, Bernard Ladenthin wrote:
> 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

To my knowledge, **noone** uses this first_match_is_last_occurrent
behaviour.

At least xt_string just return true on the first match.

So what's the point? Just "fix it" to make the new Kunit tests.

Or maybe this is being used by tc?

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

There was no test infrastructure in the kernel tree for netdev at the
time this was made.

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

Yes, for correctness. But there is no users of this "find last
occurrence" that I'm aware of?

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