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

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 <[email protected]>
---
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