Skip to content

lib/textsearch: fix ts_bm resume offset, add tests, two small cleanups

Bernard Ladenthin lkml netfilter-devel 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest4 patches 3 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/4lib/ts_bm: advance state->offset past the reported matchlib/ts_bm.c+2 -13 replies
2/4lib/tests: add KUnit tests for the textsearch infrastructurelib/Kconfig.debug lib/tests/Makefile lib/tests/textsearch_kunit.c+347 -00 replies
3/4textsearch: align ts_state.cb like skb->cbinclude/linux/textsearch.h+1 -10 replies
4/4lib/ts_fsm: document that a match must consume the remaining datalib/ts_fsm.c+7 -00 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

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

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

Signature · 1 line
2.49.0.windows.1