lib/textsearch: fix ts_bm resume offset, add tests, two small cleanups
Subsystems (2)
cover 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
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.
---
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(-)
lib/ts_bm.c +2 -1
@@ -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]];
Signature · 1 line
2.49.0.windows.1
Pablo Neira Ayuso
maintainerRe: [PATCH 1/4] lib/ts_bm: advance state->offset past the reported match
Quoted 6 lines · Bernard Ladenthin
bm_find()readsstate->offsetto decide where to resume, but never writes it back.textsearch_find()zeroesstate->offsetbefore the first call.textsearch_next()then relies on the algorithm having moved it past the match it just reported. With the "bm" algorithm everytextsearch_next()call restarts from the same place and re-reports the first match. A caller looping untilUINT_MAXnever terminates.
Yes, for a good reason.
Quoted 2 lines
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.
Quoted 6 lines
kmp_find()andfsm_find()both updatestate->offsetalready. This is an inconsistency between implementations of one interface, not a documented limitation of Boyer-Moore.Set
state->offsetto the end of the match and derive the return value from it, mirroringkmp_find().
Why? What do you get by setting state->offset?
What are you trying to fix?
Quoted 5 lines
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, andlib/textsearch.cdocuments 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?
Quoted 2 lines
xt_stringlets 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.
Quoted 10 lines
skb_find_text()also mentionstextsearch_next()in its kernel-doc. That comment has been stale since commit059a2440fd3c("net: Remove state argument fromskb_find_text()") movedts_stateinto 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.
You are not specifying any tree for this patches.
Quoted 21 lines
lib/ts_bm.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)lib/ts_bm.c +2
-1@@ -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]];Signature · 1 line
2.49.0.windows.1
Re: [PATCH 1/4] lib/ts_bm: advance state->offset past the reported match
Quoted 3 lines · Pablo Neira Ayuso
Quoted 1 line
A caller looping until
UINT_MAXnever terminates.Yes, for a good reason.
Thanks for the review. Let me start with the question I actually have.
One interface, three implementations. The same test, unchanged, run against each of them. kmp passes it, bm fails it. I cannot find where that difference is written down, and that is what I would like to understand.
Where I looked. include/linux/textsearch.h:20 describes the field as
* @offset: offset for next match
and lib/textsearch.c:72 says
* Subsequent occurrences can be found by calling textsearch_next()
* regardless of the linearity of the data.
Both are from 2005 and neither has changed. ts_bm.c does record one deviation from the other algorithms, in its file header, that a match spread over multiple blocks will be missed and that kmp should be used when that matters. It says nothing about repeating the same offset.
If what you mean is that the algorithm as Boyer and Moore published it stops at the first match and therefore defines no shift after one, that is true, and it may well be how this came about. kmp_find() faces the same question and answers it in two lines, and patch 1 is those same two lines:
kmp: state->offset = consumed + i + 1;
return state->offset - kmp->pattern_len;
bm: state->offset = consumed + shift + 1;
return state->offset - bm->patlen;So the question is not really about Boyer-Moore. It is about why two backends of one interface answer the same question differently, with nothing saying which answer is the intended one.
Quoted 2 lines
With bm, it reports offset 6, because it looks from right to left, this is how the original Boyer-Moore algorithm works.
I put that into a test case. The diff at the end adds it, parameterised like the others, so it makes the same claim about kmp and about bm. Applying it turns the suite red on purpose.
Patch 2 applies without patch 1 and does not touch lib/ts_bm.c, so this describes today's behaviour:
echo CONFIG_KUNIT=y > .kunitconfig
echo CONFIG_TEXTSEARCH_KUNIT_TEST=y >> .kunitconfig
./tools/testing/kunit/kunit.py run --arch=um \
--kunitconfig=.kunitconfig "textsearch.*"In the output below I cut the "at lib/tests/..." suffix so the lines fit, nothing else is changed:
============ ts_first_match_is_last_occurrence ============ [FAILED] kmp
# ts_first_match_is_last_occurrence: EXPECTATION FAILED
Expected pos == 6, but
pos == 2 (0x2) first match reported
[FAILED] bm
# ts_first_match_is_last_occurrence: EXPECTATION FAILED
Expected pos == 6, but
pos == 2 (0x2)first match reported
Both report 2, so the first match is the same for either algorithm. If that case asserts the wrong thing, please tell me what it should assert. The run also gives
# Totals: pass:17 fail:5 skip:0 total:22
Two of the five are that case, red by design. The other three are bm, in ts_next_advances, ts_next_finds_all and ts_blocks_iteration_terminates. Every kmp case passes.
Quoted 3 lines
Why? What do you get by setting
state->offset?What are you trying to fix?
I should be plain about the scope. Nothing in the tree calls textsearch_next(), and as far as I can tell nothing ever has. I checked the whole history with git log -S over 1.46 million commits back to 2.6.12-rc2, which covers the entire life of lib/textsearch.c. So this repairs no reported breakage, and I am not claiming otherwise.
What led me here is that lib/ts_bm.c has needed five correctness fixes in twenty-one years. In 2008 a pattern at the very start of the text was never found, "abc" in "abcdefg" returned nothing, and that had been true since 2005. In 2023 an iptables rule with --algo bm silently stopped matching, reported through bugzilla.netfilter.org #1390 and fixed by 6f67fbf8192d. Neither was caught by a test, because there were none.
That is why patch 2 exists, and it is the patch I care about most.
Which brings me to a basic question. Why has this code never had tests? I looked and found none, and git ls-tree agrees with me, but I may have missed them. If there are any, I would rather extend those than add a new file.
I ask because the suite does find two of those old bugs when they are put back on a current tree:
the 2008 one, shift = bm->patlen instead of bm->patlen - 1
ts_find_at_start red for bm, green for kmp
the 2023 one, revert 6f67fbf8192d
ts_blocks_match_within_block red for bm, green for kmp
Not all five, to be clear. The 2026 overflow it does not catch, because textsearch_prepare() rejects the zero length before the algorithm sees it. The two from 2006 I did not try to put back, the code around them has moved too far for that to mean anything.
Quoted 4 lines
Quoted 2 lines
Which algorithm a caller selected should not decide whether that works.
Why?
Because the promise is made at the interface, not per algorithm. lib/textsearch.c and include/linux/textsearch.h describe textsearch_next() without naming one, while lib/ts_bm.c lists its own deviation in its own header. And xt_string.c:56 hands conf->algo straight from userspace to textsearch_prepare(), so the caller cannot know in advance which of the two behaviours it will get.
Quoted 2 lines
Yes, and people that use it rely on the current behaviour, so you have to explain what you are aiming at fixing.
Nothing observable changes for them. The returned value is the same expression:
before: consumed + (shift - (bm->patlen - 1))
after: state->offset - bm->patlen,
with state->offset = consumed + shift + 1
Both are consumed + shift + 1 - bm->patlen. The patch only writes down the offset the return statement already implied. skb_find_text() keeps its ts_state on its own stack and uses only the return value, and xt_string reads only that return value, so no netfilter path can observe the write.
Quoted 1 line
You are not specifying any tree for this patches.
Sorry about that. get_maintainer.pl points at LIBRARY CODE for these files, so the series is aimed at Andrew Morton, and I should have said so in the subject. I will use a prefix on the next posting.
So my request is not that patch 1 be applied. It is that the difference be explained or written down. If bm is meant to be single shot, I will send a patch saying so in the same place the multi-block limitation is already stated, and drop patch 1. And if the Fixes: tag looks wrong for something nothing can reach today, I am happy to drop that too and let patch 1 stand as a follow-on to the tests.
The case below is not meant for merging. It is your sentence written as a test.
Thanks,
Bernard
---
lib/tests/textsearch_kunit.c +21 -0
@@ -302,6 +302,26 @@KUNIT_EXPECT_EQ (test,PTR_ERR (conf), -EINVAL ); } +/* +* Not part of the contract the other cases check, and not meant to be +* merged. It encodes the description that "bm" reports the last +* occurrence first, so that the claim can be run. It is parameterised +* like the rest, so it makes the same claim about kmp and about bm. +*/ +static void ts_first_match_is_last_occurrence (struct kunit *test) +{ +static const char text[] ="xxABxxABxx" ; +static const char pattern[] ="AB" ; +struct ts_config *conf =ts_conf_get (test, pattern); +struct ts_state state; +unsigned int pos; + + pos =textsearch_find_continuous (conf, &state, text,strlen (text)); +KUNIT_EXPECT_EQ_MSG (test, pos,6 ,"first match reported" ); + +textsearch_destroy (conf); +} +static struct kunit_case textsearch_test_cases[] = {KUNIT_CASE_PARAM (ts_find_middle, ts_algo_gen_params),KUNIT_CASE_PARAM (ts_find_at_start, ts_algo_gen_params),
@@ -313,6 +333,7 @@KUNIT_CASE_PARAM (ts_blocks_iteration_terminates, ts_algo_gen_params),KUNIT_CASE_PARAM (ts_get_pattern, ts_algo_gen_params),KUNIT_CASE_PARAM (ts_prepare_zero_len, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_first_match_is_last_occurrence, ts_algo_gen_params), {} };
Pablo Neira Ayuso
maintainerRe: [PATCH 1/4] lib/ts_bm: advance state->offset past the reported match
Hi,
First off, I cannot believe you wrote such a lengthy text... this can be only generated by LLM.
Quoted 66 lines · Bernard Ladenthin
Quoted 3 lines · Pablo Neira Ayuso
Quoted 1 line
A caller looping until
UINT_MAXnever terminates.Yes, for a good reason.
Thanks for the review. Let me start with the question I actually have.
One interface, three implementations. The same test, unchanged, run against each of them. kmp passes it, bm fails it. I cannot find where that difference is written down, and that is what I would like to understand.
Where I looked.
include/linux/textsearch.h:20describes the field as* @offset: offset for next match
and
lib/textsearch.c:72says* Subsequent occurrences can be found by calling
textsearch_next()
* regardless of the linearity of the data.Both are from 2005 and neither has changed.
ts_bm.cdoes record one deviation from the other algorithms, in its file header, that a match spread over multiple blocks will be missed and that kmp should be used when that matters. It says nothing about repeating the same offset.If what you mean is that the algorithm as Boyer and Moore published it stops at the first match and therefore defines no shift after one, that is true, and it may well be how this came about.
kmp_find()faces the same question and answers it in two lines, and patch 1 is those same two lines:kmp: state->offset = consumed + i + 1; return state->offset - kmp->pattern_len; bm: state->offset = consumed + shift + 1; return state->offset - bm->patlen;So the question is not really about Boyer-Moore. It is about why two backends of one interface answer the same question differently, with nothing saying which answer is the intended one.
Quoted 2 lines
With bm, it reports offset 6, because it looks from right to left, this is how the original Boyer-Moore algorithm works.
I put that into a test case. The diff at the end adds it, parameterised like the others, so it makes the same claim about kmp and about bm. Applying it turns the suite red on purpose.
Patch 2 applies without patch 1 and does not touch
lib/ts_bm.c, so this describes today's behaviour:echo CONFIG_KUNIT=y > .kunitconfig echo CONFIG_TEXTSEARCH_KUNIT_TEST=y >> .kunitconfig ./tools/testing/kunit/kunit.py run --arch=um \ --kunitconfig=.kunitconfig "textsearch.*"In the output below I cut the "at
lib/tests/..." suffix so the lines fit, nothing else is changed:============
ts_first_match_is_last_occurrence============ [FAILED] kmp# ts_first_match_is_last_occurrence: EXPECTATION FAILED Expected pos == 6, but pos == 2 (0x2)
Quoted 7 lines
first match reported
[FAILED] bm# ts_first_match_is_last_occurrence: EXPECTATION FAILED Expected pos == 6, but pos == 2 (0x2)first match reported
To my knowledge, **noone** uses this first_match_is_last_occurrent behaviour.
At least xt_string just return true on the first match.
So what's the point? Just "fix it" to make the new Kunit tests.
Or maybe this is being used by tc?
Quoted 27 lines
Both report 2, so the first match is the same for either algorithm. If that case asserts the wrong thing, please tell me what it should assert. The run also gives
# Totals: pass:17 fail:5 skip:0 total:22
Two of the five are that case, red by design. The other three are bm, in
ts_next_advances,ts_next_finds_allandts_blocks_iteration_terminates. Every kmp case passes.Quoted 3 lines
Why? What do you get by setting
state->offset?What are you trying to fix?
I should be plain about the scope. Nothing in the tree calls
textsearch_next(), and as far as I can tell nothing ever has. I checked the whole history with git log -S over 1.46 million commits back to 2.6.12-rc2, which covers the entire life oflib/textsearch.c. So this repairs no reported breakage, and I am not claiming otherwise.What led me here is that
lib/ts_bm.chas needed five correctness fixes in twenty-one years. In 2008 a pattern at the very start of the text was never found, "abc" in "abcdefg" returned nothing, and that had been true since 2005. In 2023 an iptables rule with --algo bm silently stopped matching, reported through bugzilla.netfilter.org #1390 and fixed by6f67fbf8192d. Neither was caught by a test, because there were none.
Quoted 3 lines
That is why patch 2 exists, and it is the patch I care about most.
Which brings me to a basic question. Why has this code never had tests?
There was no test infrastructure in the kernel tree for netdev at the time this was made.
Quoted 18 lines
I looked and found none, and git ls-tree agrees with me, but I may have missed them. If there are any, I would rather extend those than add a new file.
I ask because the suite does find two of those old bugs when they are put back on a current tree:
the 2008 one, shift =
bm->patleninstead ofbm->patlen- 1
ts_find_at_startred for bm, green for kmpthe 2023 one, revert
6f67fbf8192d
ts_blocks_match_within_blockred for bm, green for kmpNot all five, to be clear. The 2026 overflow it does not catch, because
textsearch_prepare()rejects the zero length before the algorithm sees it. The two from 2006 I did not try to put back, the code around them has moved too far for that to mean anything.
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines
Which algorithm a caller selected should not decide whether that works.
Why?
Because the promise is made at the interface, not per algorithm.
Yes, for correctness. But there is no users of this "find last occurrence" that I'm aware of?
Quoted 79 lines
lib/textsearch.candinclude/linux/textsearch.hdescribetextsearch_next()without naming one, whilelib/ts_bm.clists its own deviation in its own header. And xt_string.c:56 handsconf->algostraight from userspace totextsearch_prepare(), so the caller cannot know in advance which of the two behaviours it will get.Quoted 2 lines
Yes, and people that use it rely on the current behaviour, so you have to explain what you are aiming at fixing.
Nothing observable changes for them. The returned value is the same expression:
before: consumed + (shift - (
bm->patlen- 1))
after:state->offset-bm->patlen,with state->offset = consumed + shift + 1Both are consumed + shift + 1 -
bm->patlen. The patch only writes down the offset the return statement already implied.skb_find_text()keeps itsts_stateon its own stack and uses only the return value, andxt_stringreads only that return value, so no netfilter path can observe the write.Quoted 1 line
You are not specifying any tree for this patches.
Sorry about that. get_maintainer.pl points at LIBRARY CODE for these files, so the series is aimed at Andrew Morton, and I should have said so in the subject. I will use a prefix on the next posting.
So my request is not that patch 1 be applied. It is that the difference be explained or written down. If bm is meant to be single shot, I will send a patch saying so in the same place the multi-block limitation is already stated, and drop patch 1. And if the Fixes: tag looks wrong for something nothing can reach today, I am happy to drop that too and let patch 1 stand as a follow-on to the tests.
The case below is not meant for merging. It is your sentence written as a test.
Thanks,
Bernard---
lib/tests/textsearch_kunit.c +21
-0@@ -302,6 +302,26 @@KUNIT_EXPECT_EQ (test,PTR_ERR (conf), -EINVAL ); } +/* +* Not part of the contract the other cases check, and not meant to be +* merged. It encodes the description that "bm" reports the last +* occurrence first, so that the claim can be run. It is parameterised +* like the rest, so it makes the same claim about kmp and about bm. +*/ +static void ts_first_match_is_last_occurrence (struct kunit *test) +{ +static const char text[] ="xxABxxABxx" ; +static const char pattern[] ="AB" ; +struct ts_config *conf =ts_conf_get (test, pattern); +struct ts_state state; +unsigned int pos; + + pos =textsearch_find_continuous (conf, &state, text,strlen (text)); +KUNIT_EXPECT_EQ_MSG (test, pos,6 ,"first match reported" ); + +textsearch_destroy (conf); +} +static struct kunit_case textsearch_test_cases[] = {KUNIT_CASE_PARAM (ts_find_middle, ts_algo_gen_params),KUNIT_CASE_PARAM (ts_find_at_start, ts_algo_gen_params),@@ -313,6 +333,7 @@KUNIT_CASE_PARAM (ts_blocks_iteration_terminates, ts_algo_gen_params),KUNIT_CASE_PARAM (ts_get_pattern, ts_algo_gen_params),KUNIT_CASE_PARAM (ts_prepare_zero_len, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_first_match_is_last_occurrence, ts_algo_gen_params), {} };
PATCH 2/4 lib/tests: add KUnit tests for the textsearch infrastructure
In reply to Bernard Ladenthinlib/textsearch.c and the algorithms registered with it have had no test coverage since the infrastructure was added in 2005. Every bug found in lib/ts_bm.c since then was found by inspection, or by a user hitting it in production:
commit 3f330317ab49 ("[TEXTSEARCH]: Fix broken good shift array calculation in Boyer-Moore") commit 3ffaa8c7c0f8 ("[TEXTSEARCH]: Fix Boyer Moore initialization bug") commit aebb6a849cfe ("textsearch: fix Boyer-Moore text search bug")
commit 6f67fbf8192d ("lib/ts_bm: reset initial match offset for every block of text") commit 9003ec6f7f39 ("lib/ts_bm: fix integer overflow in pattern length calculation")
Add a KUnit suite that runs the same cases against every algorithm taking a plain byte-string pattern. All implementations are then held to the same interface contract. The cases cover matches at the start, middle and end of the text, the absence of a match, pattern accessors, rejection of zero-length patterns, and that textsearch_next() advances and eventually terminates.
Three of the five fixes listed above concern multi-block handling. The suite therefore also drives the algorithms through a get_next_block() that hands the text out in fixed-size chunks, the way skb_seq_read() does. Those cases check what has to hold for any block layout. A match contained in a single block is found. Every reported offset is a real match. Iteration makes progress and terminates. Matches spanning a block boundary are left alone, since ts_bm documents those as missed while ts_kmp finds them.
ts_fsm is not covered. fsm_init() consumes an array of struct ts_fsm_token rather than a byte string, so it cannot share these test vectors.
The loop in ts_next_advances is bounded. An algorithm that fails to advance then reports a failure instead of hanging the test run.
---
This is my first kernel submission. Corrections on anything I got wrong in the process are welcome.
lib/Kconfig.debug | 19 ++ lib/tests/Makefile | 1 + lib/tests/textsearch_kunit.c | 327 +++++++++++++++++++++++++++++++++++ 3 files changed, 347 insertions(+) create mode 100644 lib/tests/textsearch_kunit.c
lib/Kconfig.debug +19 -0
@@ -3531,6 +3531,25 @@ config GLOB_KUNIT_TEST If unsure, say N +config TEXTSEARCH_KUNIT_TEST + tristate "Textsearch infrastructure test" if !KUNIT_ALL_TESTS + depends on KUNIT + select TEXTSEARCH + select TEXTSEARCH_KMP + select TEXTSEARCH_BM + default KUNIT_ALL_TESTS + help + Enable this option to test the textsearch infrastructure at + runtime. + + This test suite exercises lib/textsearch.c together with the + string-pattern algorithms registered with it. The same cases are + run against every algorithm, checking the reported match offsets + and that repeated searches over one buffer make progress and + terminate. + + If unsure, say N + endif # RUNTIME_TESTING_MENU config ARCH_USE_MEMTEST
lib/tests/Makefile +1 -0
@@ -54,6 +54,7 @@ CFLAGS_stackinit_kunit.o += $(call cc-disable-warning, switch-unreachable) obj-$(CONFIG_STACKINIT_KUNIT_TEST) += stackinit_kunit.o obj-$(CONFIG_STRING_KUNIT_TEST) += string_kunit.o obj-$(CONFIG_STRING_HELPERS_KUNIT_TEST) += string_helpers_kunit.o +obj-$(CONFIG_TEXTSEARCH_KUNIT_TEST) += textsearch_kunit.o obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o obj-$(CONFIG_UTIL_MACROS_KUNIT) += util_macros_kunit.o obj-$(CONFIG_RATELIMIT_KUNIT_TEST) += test_ratelimit.o
lib/tests/textsearch_kunit.c new file +327 -0
327 lines not on this page · raw message
Signature · 1 line
2.49.0.windows.1
PATCH 3/4 textsearch: align ts_state.cb like skb->cb
In reply to Bernard Ladenthinstruct ts_state carries a 48-byte control buffer that callers cast to their own state structure. lib/textsearch.c casts it to struct ts_linear_state. net/core/skbuff.c casts it to struct skb_seq_state via TS_SKB_CB(). Both contain pointers and so need 8-byte alignment on 64-bit.
cb sits at offset 4, right after the unsigned int offset field, and struct ts_state itself has only 4-byte alignment. Any allocation aligned to 8 or more therefore places cb on a 4-mod-8 address. kmalloc() guarantees at least ARCH_KMALLOC_MINALIGN, which is 8 or larger, so a heap-allocated ts_state has a misaligned cb every time. For a stack-allocated one it depends on where the compiler happens to put it.
No in-tree caller is affected today. The only struct ts_state is a stack local in skb_find_text(). The cast is undefined behaviour regardless, and on architectures without efficient unaligned access it is a trap for whoever allocates one of these on the heap.
struct sk_buff already marks its cb[48] __aligned(8) for exactly this reason. Do the same here.
---
This is my first kernel submission. Corrections on anything I got wrong in the process are welcome.
include/linux/textsearch.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/textsearch.h +1 -1
@@ -23,7 +23,7 @@ struct ts_config;struct ts_state {unsigned int offset; -char cb[48 ]; +char cb[48 ]__aligned(8) ; };/**
Signature · 1 line
2.49.0.windows.1
PATCH 4/4 lib/ts_fsm: document that a match must consume the remaining data
In reply to Bernard Ladenthinfsm_find() reports a match only once the token chain has matched and the data is exhausted:
for (tok_idx = 0; tok_idx < fsm->ntokens; tok_idx++) { ... }
if (end_of_data())
goto found_match;
no_match:
return UINT_MAX;A chain of three specific tokens therefore matches the text "abc" but not "abcd". [TS_FSM_HEAD_IGNORE, a, b] does not find "ab" in "xxabyy". Searching for a pattern in the middle of the data needs TS_FSM_HEAD_IGNORE at the front and a TS_FSM_ANY token at the end. The latter short-circuits through "if (next == NULL) goto found_match".
The file header explains the head anchoring but says nothing about the tail, which makes the interface easy to misuse. Describe it.
This documents the behaviour as it stands. If the end-of-data requirement is not intended, the fix belongs in fsm_find() and this patch should be dropped in favour of that.
---
This is my first kernel submission. Corrections on anything I got wrong in the process are welcome.
lib/ts_fsm.c | 7 +++++++ 1 file changed, 7 insertions(+)
lib/ts_fsm.c +7 -0
@@ -18,6 +18,13 @@* is enabled by default and can be disabled by inserting * TS_FSM_HEAD_IGNORE as the first token in the chain. * +* A match is only reported once the data has been consumed as well: the +* token chain has to account for every remaining octet, not just for the +* pattern itself. A chain of three specific tokens therefore matches the +* text "abc" but not "abcd". To look for a pattern somewhere in the +* middle of the data, prepend a token with TS_FSM_HEAD_IGNORE and append +* one with TS_FSM_ANY, the latter matching whatever follows. +* * The runtime performance of the algorithm should be around O(n), * however while in strict mode the average runtime can be better. */
Signature · 1 line
2.49.0.windows.1