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

[Bernard Ladenthin <bernard.ladenthin@gmail.com>]

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