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