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