From nobody Mon Aug 24 04:17:55 2026 Received: from mail-wm1-f44.google.com (mail-wm1-f44.google.com [209.85.128.44]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E3CF2391E5F for ; Sun, 16 Aug 2026 17:06:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.44 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900013; cv=none; b=Rh3r+BTGzC6J+g5f/DqXCLI/zLrKsNwDKftHXa6jiykQOzo4ej5N/SgJCyZZOcmVOHLcY4NFGukJW3ZM8HS6nqzRtuDv/ETPqRtS84DsKS8cSRcnDKIOtV6J0uqjz70whuGPFw7jGDkEXLF0r6Affjz3IY4oKOPaaU9+1NdSXvs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900013; c=relaxed/simple; bh=jXdBmOJ0ziF4vZ8k3JfSRKjfviukl/lYqgcx3OeIMlw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Sg10TajNGEiAZSc11gUMIJ6RWmGL8OD/5muOmKztKAZ7NE0rrRvUT4DTMdah8t/se0usY5yvc0xSUnpA1s1NQmQVKw970d4x6gGLDH1U2wju/jyNYcDSYxx0MYWkrgIOn1PAAgudciu4op73/iiFUQhtqGKqT0Ql+K/ZuSt0ek8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=I/0S5dqA; arc=none smtp.client-ip=209.85.128.44 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="I/0S5dqA" Received: by mail-wm1-f44.google.com with SMTP id 5b1f17b1804b1-4953e04ef16so28735595e9.2 for ; Sun, 16 Aug 2026 10:06:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786900010; x=1787504810; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=U1Ixo7fgt6nx2xcmQkKup8mBmE03cs139sFvFDg9BSQ=; b=I/0S5dqAWIgVhNlPc/+CUf19zqcBoJ96R911lWn1uONFv0rSMrEl4Kr/K8oUOm1ASE DPNLO4+tMk3+tSMU85tvmWydlKrFtXr9mGEdNCHNecI02vOnZ+W+Ha0GxKhJrcQeCwwQ ekm7GkNvXKid5iX8M9soIMEzpOaum+cvls7ghBn77D5MB+lVq9iq15IM80i9XPx0mXql 3I/QbeE8jCf35r2gy6pwiPfwLSv+Rt0ZwCpcGCB4tCo1+kvcQbd3+u/ZwkD8Csy/uei0 nUXFphNCEbVVQkSTNAxvFu8mx+rrzCAii/iV0YrAMdx0IwLbk9tnCvnDdNJBYbnErK15 Lf8A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786900010; x=1787504810; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=U1Ixo7fgt6nx2xcmQkKup8mBmE03cs139sFvFDg9BSQ=; b=WOncjHA9Jg4ZnaI8k86anZtJNTjciSMGbJ3XJDS4PLmbSiV4gauPQ4DEzOs2sdKq4W bMk2GH9y/0I0K2YWIJoq/XQTy93G8KhWJFJ4MGC2VamXAjB6EqQM5xKeIrgTKHADO9XM PkY6wqTNPm+CINuqXeuAc4U6ww/04UpoZCG+3EbrWaxfmPrdPWcijqhWD123p0vpo6CG GMk6EhK8kJNSYvDq50Q19mDW1ZwpvIEX9OqO8l+ALUOPo07GwH3FuyGwQnIxAB+12d+k ItDCfMZF/6zr0Xw6NPPfKEZ052Hd1SLNdiX2PUzcDF1pyrh0u0UpaIT022a3rJgm9Y4z sOfQ== X-Gm-Message-State: AOJu0YxU56nJmY/QN82dZZkkgs2maLcYOXXje6AlaumMP3lmfmAXvaDi a07FtmF3rfk1QwlUNznZ57ccSCYgxlGSu4ykvA7Ywxz9iO/BATAUFcxW X-Gm-Gg: AR+sD13drlXwWrGo9PHruvJJ3m6DI38IjGWuxYG2zauHgmP3ogQB7SxmoN6RUkhSVVg 34Ib0Zn3VpQTTnLSuBjN4KRgshWQ2xb+pKLnkMYjg6zMUcDf4Uxu8QF58PNhVXI7wkGJCov2e+B Ge/80mGFM6ZqZuGxPiZbNsKNDI4GYfn6U3EQqOXGNNbKniAV5JQFOvYUr778Bql6P3FkV5YsHhn v2YB7xfQQl7UbQRlDoZJ0Bu9M/R+wU05oua1dX6VqiSZTiONNDYuf3GJ1JUCEJD9MaYfymqmYJL Q1r96Hj34JKYBiO6wHo6fi4qk+t5dx2CH2WZFn1Zd9TE3OvKRlJmCQ7Ui+048hUyYv5OBrQJVXC cT/dnqrYObcv++z7BGNseLkN3ECbd+d3SRw7Eo0lG3oy2ilYtw8zbTteXzO9gJHFcvpeketfVmX ISLTEmMQBKQRlcxSKyzSk3VhOiE13pCLRpAXoV0gqPLDRW2WDyiZye8MeSKGng5T1oQO8xcS3ws Uqjz/uKWA2Ub00lZF4IfXpI6ZRDs7VV2quwGYxhFwe/Ztj8AZIB1V6+E6DFVXLHSop5aewMxNVj /xoUU0A/MX4fPD02nndBs5jF/mbJoMQskhKMAH2hqhf1vrTyYA== X-Received: by 2002:a05:600c:3545:b0:499:79b9:e220 with SMTP id 5b1f17b1804b1-49987958779mr270559505e9.10.1786900010082; Sun, 16 Aug 2026 10:06:50 -0700 (PDT) Received: from localhost.localdomain (p54a14b85.dip0.t-ipconnect.de. [84.161.75.133]) by smtp.gmail.com with ESMTPSA id 5b1f17b1804b1-4999618acafsm55671335e9.14.2026.08.16.10.06.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 16 Aug 2026 10:06:49 -0700 (PDT) From: Bernard Ladenthin To: akpm@linux-foundation.org Cc: linux-kernel@vger.kernel.org, pablo@netfilter.org, fw@strlen.de, netfilter-devel@vger.kernel.org, kunit-dev@googlegroups.com, davem@davemloft.net, Bernard Ladenthin Subject: [PATCH 1/4] lib/ts_bm: advance state->offset past the reported match Date: Sun, 16 Aug 2026 19:05:37 +0200 Message-ID: <20260816170541.3384-2-bernard.ladenthin@gmail.com> X-Mailer: git-send-email 2.49.0.windows.1 In-Reply-To: <20260816170541.3384-1-bernard.ladenthin@gmail.com> References: <20260816170541.3384-1-bernard.ladenthin@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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 infrastru= cture strike #2") Signed-off-by: Bernard Ladenthin --- 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, struc= t ts_state *state) if (i =3D=3D bm->patlen) { /* London calling... */ DEBUGP("found!\n"); - return consumed + (shift-(bm->patlen-1)); + state->offset =3D consumed + shift + 1; + return state->offset - bm->patlen; } =20 bs =3D bm->bad_shift[text[shift-i]]; --=20 2.49.0.windows.1 From nobody Mon Aug 24 04:17:55 2026 Received: from mail-wm1-f52.google.com (mail-wm1-f52.google.com [209.85.128.52]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CDC9339794B for ; Sun, 16 Aug 2026 17:06:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.52 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900018; cv=none; b=nhVqKNPsGVWa6PmR8iTZUWQ2UPFgdAHXpBxSg7b5OVEw0EcmK6HkLQr16EmJmusP83RRkB2gSmHXdiZt8woCJsMx/ei/4HcNpP/N0UqZ/y4kDQWUzYK7GiB2plHT6f15g0Vg57NLlSMH3oEEW57dVvdgbMseUifvm7LP1ZT58bo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900018; c=relaxed/simple; bh=8qNZFThDXTxE9NVGLl+9G6+Cxvg4naDwuzb6SLiQuLI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=UJUdR/S6gsejV/dpQ9gHFDVUiq9OEKrvaDQWZq2f79zyNFlxDKAhjQKd+B7WW0PuTCQEsBEGDvYRdc9hHjW1dn1GjUi1H59q689AhDYlYMIsLPyxHZ+8CFW0Bp/tEUOEbb7cBPfgh9e0Pq4NAbY8WbN+Z9rZInn3D7W7AFmiDIo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=fzthR3dV; arc=none smtp.client-ip=209.85.128.52 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="fzthR3dV" Received: by mail-wm1-f52.google.com with SMTP id 5b1f17b1804b1-49558ce01afso19860285e9.1 for ; Sun, 16 Aug 2026 10:06:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786900015; x=1787504815; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=DuxZwIcZAysRXAH+nqg9/bm9jSLM6Ud0irjYjttvIoA=; b=fzthR3dVk9U3y091A60F0Uqa32RnnaFYOL2tYceOYODk7VRFf0UCUjyeMLokhQ4Q+B iuAG5LvmH/ATF33anQ1YGU67njKr+s2/TZVbcxtzdlOU1fbyzwIe4d+VnoXuBY1aEVha PuqgMHBo1GG9BQRNpZtfHoC0B54WspLtzoSfZIiujcCASH71/OSsGXYjuZXPQJ8lJ5pD gy/aaS7uuqNaDQxRxfN5yxkeK47r2MFzQSdpwAu7MbfLJfSqvHDKeED2+baUcoebdFrK viJUFurCLGTOId48wgzamAvnTvwqvijW8w++w36ciN38z0ByMMbQCsyjf+HIsXmZpdzu HsAw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786900015; x=1787504815; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=DuxZwIcZAysRXAH+nqg9/bm9jSLM6Ud0irjYjttvIoA=; b=oqZNEsQeQcRxSidtXkOUuYwt9xbfHRRItDwCMYc9r7xiZ0kVm5eLcy82c+CWpH8GpQ ncOPNc/YLeoEumOfkv9yknUBxx/Qa634jCX7T+zHkyt3ACjYnQlYxg4FkCtieUgI9c5r TAp04z3p7dKw6LmNRHWJQeKdgOMRU51X1v+ZS2IDQZ6SelIGyKXU5BuvxAOYxSwzuGGp 57diMYnzXObKVP3LARjUajrAcydxRalWImJoVvh/sNlJn8ZTxdvgMgQ8+i+apcc8UvfL r11KSICIeEC8vsAKNNlCW8SkvjlB2uSundOWJ4/IsZyl1h13obRfVOs6pAaIb1bw8sBN iMGw== X-Gm-Message-State: AOJu0YxU8Q6LNVn3LOLdO5K/CDzz2wUIZkdFZJ0P9a8S5Qre1bb3lytm grwbW5v5Xz1jI6474RTPOgoiwhAbt6B29WQKHTYRJl4oNrHKZh8SUllD X-Gm-Gg: AR+sD10t143SHG7R94MqrcbUBj1tIZ4Mra4FEcp1HkxZlqGx0eoMyPEf1RhtmrEE/65 rFM5m4WArEOAQwlDoSrUultIIY6qfkdQBXcG4QzQzkIr+M8jwFWj8UaUPlP2rv2Chjf6yBC4OwT rWa0P0w0ab4tBkiCpAGZ020rtjZlbCCPeUUVVLj+OwjltN+BtYJA14E6ydtKe/6paQIViHWya54 Q3RyNQTHFNIAXYWi/i6atKPFe4cz0oSyZTGtORNWJ1blxr68EzXc+BAWbQCksCDNV7H/m4CKnpr Cyuzb+pBb5F69AwGqDXGNKcVZ3IkjHiXeOlszJF+QZfEbFbRTu1wPBANqDIe2sxD2xrt1UlAYQs 6HWqjCSKMuzNzhNQ6BX3QLl1vl1PIALAp8uIFhLbuw0E/Agz+7TV7NiCX52RNFx8ky0G7dH9nIG 6H68RllfDbOZnhEeDn+d7dKMetUli+azoLZkUUYHCiu1eqG/EXEH2YIaX92Ly/9YBShQ9yAkuUc TM9x267mGf8j8/Wym9aBvjr8IlNZrKPGGQuSuuNhaYj4+ZcPucsWf9RjJpD4jEtw9slaTtjuud3 ax1fJY+QcvF0wvH0+I+Vk1SjTY/g+vbhPp+TgfQ= X-Received: by 2002:a05:600c:8218:b0:499:593b:a15b with SMTP id 5b1f17b1804b1-499879357cemr334789675e9.1.1786900014893; Sun, 16 Aug 2026 10:06:54 -0700 (PDT) Received: from localhost.localdomain (p54a14b85.dip0.t-ipconnect.de. [84.161.75.133]) by smtp.gmail.com with ESMTPSA id 5b1f17b1804b1-4999618acafsm55671335e9.14.2026.08.16.10.06.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 16 Aug 2026 10:06:54 -0700 (PDT) From: Bernard Ladenthin To: akpm@linux-foundation.org Cc: linux-kernel@vger.kernel.org, pablo@netfilter.org, fw@strlen.de, netfilter-devel@vger.kernel.org, kunit-dev@googlegroups.com, davem@davemloft.net, Bernard Ladenthin Subject: [PATCH 2/4] lib/tests: add KUnit tests for the textsearch infrastructure Date: Sun, 16 Aug 2026 19:05:38 +0200 Message-ID: <20260816170541.3384-3-bernard.ladenthin@gmail.com> X-Mailer: git-send-email 2.49.0.windows.1 In-Reply-To: <20260816170541.3384-1-bernard.ladenthin@gmail.com> References: <20260816170541.3384-1-bernard.ladenthin@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" lib/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 calculati= on 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 blo= ck of text") commit 9003ec6f7f39 ("lib/ts_bm: fix integer overflow in pattern length c= alculation") 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. Signed-off-by: Bernard Ladenthin --- 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 diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 1244dcac2294..783cf6bf1469 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -3531,6 +3531,25 @@ config GLOB_KUNIT_TEST =20 If unsure, say N =20 +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 =20 config ARCH_USE_MEMTEST diff --git a/lib/tests/Makefile b/lib/tests/Makefile index 4ead57602eac..a2d0390c18d4 100644 --- a/lib/tests/Makefile +++ b/lib/tests/Makefile @@ -54,6 +54,7 @@ CFLAGS_stackinit_kunit.o +=3D $(call cc-disable-warning, = switch-unreachable) obj-$(CONFIG_STACKINIT_KUNIT_TEST) +=3D stackinit_kunit.o obj-$(CONFIG_STRING_KUNIT_TEST) +=3D string_kunit.o obj-$(CONFIG_STRING_HELPERS_KUNIT_TEST) +=3D string_helpers_kunit.o +obj-$(CONFIG_TEXTSEARCH_KUNIT_TEST) +=3D textsearch_kunit.o obj-$(CONFIG_USERCOPY_KUNIT_TEST) +=3D usercopy_kunit.o obj-$(CONFIG_UTIL_MACROS_KUNIT) +=3D util_macros_kunit.o obj-$(CONFIG_RATELIMIT_KUNIT_TEST) +=3D test_ratelimit.o diff --git a/lib/tests/textsearch_kunit.c b/lib/tests/textsearch_kunit.c new file mode 100644 index 000000000000..b8a79240366d --- /dev/null +++ b/lib/tests/textsearch_kunit.c @@ -0,0 +1,327 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * KUnit tests for the textsearch infrastructure. + * + * The cases below are run against every string-pattern algorithm register= ed + * with lib/textsearch.c, so that all implementations are held to the same + * interface contract. + * + * ts_fsm is deliberately not covered: fsm_init() consumes an array of + * struct ts_fsm_token rather than a plain byte string, so it cannot share + * these test vectors. + */ + +#include +#include +#include +#include +#include +#include + +static const char * const ts_algo_names[] =3D { "kmp", "bm" }; + +static void ts_algo_desc(const char * const *algo, char *desc) +{ + strscpy(desc, *algo, KUNIT_PARAM_DESC_SIZE); +} + +KUNIT_ARRAY_PARAM(ts_algo, ts_algo_names, ts_algo_desc); + +/* + * Build a configuration for the algorithm under test. Skips the case rath= er + * than failing it when the algorithm is not registered, so that a kernel + * built without, say, CONFIG_TEXTSEARCH_BM still reports cleanly. + */ +static struct ts_config *ts_conf_get(struct kunit *test, const char *patte= rn) +{ + const char *algo =3D *(const char * const *)test->param_value; + struct ts_config *conf; + + conf =3D textsearch_prepare(algo, pattern, strlen(pattern), + GFP_KERNEL, TS_AUTOLOAD); + if (IS_ERR(conf)) + kunit_skip(test, "algorithm \"%s\" not registered (%pe)", + algo, conf); + + return conf; +} + +static void ts_find_middle(struct kunit *test) +{ + static const char text[] =3D "We dance the funky chicken"; + static const char pattern[] =3D "chicken"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + struct ts_state state; + + KUNIT_EXPECT_EQ(test, + textsearch_find_continuous(conf, &state, text, + strlen(text)), + strlen(text) - strlen(pattern)); + + textsearch_destroy(conf); +} + +static void ts_find_at_start(struct kunit *test) +{ + static const char text[] =3D "abcdefg"; + static const char pattern[] =3D "abc"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + struct ts_state state; + + KUNIT_EXPECT_EQ(test, + textsearch_find_continuous(conf, &state, text, + strlen(text)), + 0); + + textsearch_destroy(conf); +} + +static void ts_find_at_end(struct kunit *test) +{ + static const char text[] =3D "abcdefg"; + static const char pattern[] =3D "efg"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + struct ts_state state; + + KUNIT_EXPECT_EQ(test, + textsearch_find_continuous(conf, &state, text, + strlen(text)), + 4); + + textsearch_destroy(conf); +} + +static void ts_find_no_match(struct kunit *test) +{ + static const char text[] =3D "abcdefg"; + static const char pattern[] =3D "xyz"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + struct ts_state state; + + KUNIT_EXPECT_EQ(test, + textsearch_find_continuous(conf, &state, text, + strlen(text)), + UINT_MAX); + + textsearch_destroy(conf); +} + +/* + * textsearch_find() resets state->offset and textsearch_next() relies on = the + * algorithm having advanced it past the match it just reported. An algori= thm + * that leaves state->offset alone reports the same position forever. + */ +static void ts_next_advances(struct kunit *test) +{ + static const char text[] =3D "aaaa"; + static const char pattern[] =3D "aa"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + unsigned int pos, prev; + struct ts_state state; + int i; + + pos =3D textsearch_find_continuous(conf, &state, text, strlen(text)); + KUNIT_ASSERT_EQ(test, pos, 0); + + /* Bounded so that a non-advancing algorithm fails instead of hanging. */ + for (i =3D 0; i < 8; i++) { + prev =3D pos; + + pos =3D textsearch_next(conf, &state); + if (pos =3D=3D UINT_MAX) + break; + + KUNIT_ASSERT_GT_MSG(test, pos, prev, + "textsearch_next() reported %u after %u; it must advance past the = previous match", + pos, prev); + } + + KUNIT_EXPECT_EQ_MSG(test, pos, UINT_MAX, + "search did not terminate within 8 iterations"); + + textsearch_destroy(conf); +} + +/* The full set of matches must be reported exactly once, in order. */ +static void ts_next_finds_all(struct kunit *test) +{ + static const char text[] =3D "xxABxxABxx"; + static const char pattern[] =3D "AB"; + static const unsigned int expect[] =3D { 2, 6 }; + struct ts_config *conf =3D ts_conf_get(test, pattern); + struct ts_state state; + unsigned int pos; + int i; + + pos =3D textsearch_find_continuous(conf, &state, text, strlen(text)); + + for (i =3D 0; i < ARRAY_SIZE(expect); i++) { + KUNIT_ASSERT_EQ_MSG(test, pos, expect[i], + "match %d: expected offset %u, got %u", + i, expect[i], pos); + pos =3D textsearch_next(conf, &state); + } + + KUNIT_EXPECT_EQ_MSG(test, pos, UINT_MAX, + "expected exactly %zu matches", ARRAY_SIZE(expect)); + + textsearch_destroy(conf); +} + +/* + * A block source that hands the text out in fixed-size chunks, so that the + * algorithms are driven the way a non-linear skb drives them. Boundaries = sit + * at multiples of @chunk, mirroring skb_seq_read(). + */ +struct ts_chunk_state { + const char *data; + unsigned int len; + unsigned int chunk; +}; + +static unsigned int ts_get_chunk(unsigned int consumed, const u8 **dst, + struct ts_config *conf, + struct ts_state *state) +{ + struct ts_chunk_state *cs =3D (struct ts_chunk_state *)state->cb; + unsigned int end; + + if (consumed >=3D cs->len) + return 0; + + end =3D (consumed / cs->chunk + 1) * cs->chunk; + if (end > cs->len) + end =3D cs->len; + + *dst =3D (const u8 *)cs->data + consumed; + return end - consumed; +} + +static unsigned int ts_find_chunked(struct ts_config *conf, + struct ts_state *state, const char *text, + unsigned int len, unsigned int chunk) +{ + struct ts_chunk_state *cs =3D (struct ts_chunk_state *)state->cb; + + BUILD_BUG_ON(sizeof(struct ts_chunk_state) > sizeof(state->cb)); + + conf->get_next_block =3D ts_get_chunk; + cs->data =3D text; + cs->len =3D len; + cs->chunk =3D chunk; + + return textsearch_find(conf, state); +} + +/* + * A match that lies entirely inside one block must be found no matter how= the + * text is split up. Matches spanning a block boundary are deliberately not + * covered: ts_bm documents those as missed, ts_kmp finds them. + */ +static void ts_blocks_match_within_block(struct kunit *test) +{ + static const char text[] =3D "xxxxABCDxxxx"; + static const char pattern[] =3D "ABCD"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + struct ts_state state; + + /* chunk 4 puts "ABCD" exactly in the second block */ + KUNIT_EXPECT_EQ_MSG(test, + ts_find_chunked(conf, &state, text, + strlen(text), 4), + 4, "match inside a single block must be found"); + + /* one block for the whole text must agree with the chunked run */ + KUNIT_EXPECT_EQ(test, + ts_find_chunked(conf, &state, text, strlen(text), + strlen(text)), + 4); + + textsearch_destroy(conf); +} + +/* Iterating over a chunked buffer must terminate and must make progress. = */ +static void ts_blocks_iteration_terminates(struct kunit *test) +{ + static const char text[] =3D "abababababab"; + static const char pattern[] =3D "ab"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + unsigned int chunk, pos, prev; + struct ts_state state; + int i; + + for (chunk =3D 1; chunk <=3D strlen(text); chunk++) { + pos =3D ts_find_chunked(conf, &state, text, strlen(text), chunk); + + for (i =3D 0; i < 32 && pos !=3D UINT_MAX; i++) { + KUNIT_ASSERT_LE_MSG(test, pos + strlen(pattern), + strlen(text), + "chunk %u: reported match at %u runs past the text", + chunk, pos); + KUNIT_ASSERT_MEMEQ_MSG(test, text + pos, pattern, + strlen(pattern), + "chunk %u: offset %u is not a real match", + chunk, pos); + prev =3D pos; + pos =3D textsearch_next(conf, &state); + if (pos =3D=3D UINT_MAX) + break; + KUNIT_ASSERT_GT_MSG(test, pos, prev, + "chunk %u: reported %u after %u", + chunk, pos, prev); + } + + KUNIT_EXPECT_EQ_MSG(test, pos, UINT_MAX, + "chunk %u: search did not terminate", chunk); + } + + textsearch_destroy(conf); +} + +static void ts_get_pattern(struct kunit *test) +{ + static const char pattern[] =3D "chicken"; + struct ts_config *conf =3D ts_conf_get(test, pattern); + + KUNIT_EXPECT_EQ(test, textsearch_get_pattern_len(conf), + strlen(pattern)); + KUNIT_EXPECT_MEMEQ(test, textsearch_get_pattern(conf), pattern, + strlen(pattern)); + + textsearch_destroy(conf); +} + +/* textsearch_prepare() documents -EINVAL for a zero-length pattern. */ +static void ts_prepare_zero_len(struct kunit *test) +{ + const char *algo =3D *(const char * const *)test->param_value; + struct ts_config *conf; + + conf =3D textsearch_prepare(algo, "", 0, GFP_KERNEL, TS_AUTOLOAD); + KUNIT_ASSERT_TRUE(test, IS_ERR(conf)); + KUNIT_EXPECT_EQ(test, PTR_ERR(conf), -EINVAL); +} + +static struct kunit_case textsearch_test_cases[] =3D { + KUNIT_CASE_PARAM(ts_find_middle, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_find_at_start, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_find_at_end, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_find_no_match, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_next_advances, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_next_finds_all, ts_algo_gen_params), + KUNIT_CASE_PARAM(ts_blocks_match_within_block, ts_algo_gen_params), + 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), + {} +}; + +static struct kunit_suite textsearch_test_suite =3D { + .name =3D "textsearch", + .test_cases =3D textsearch_test_cases, +}; + +kunit_test_suite(textsearch_test_suite); + +MODULE_DESCRIPTION("KUnit tests for the textsearch infrastructure"); +MODULE_LICENSE("GPL"); --=20 2.49.0.windows.1 From nobody Mon Aug 24 04:17:55 2026 Received: from mail-wm1-f47.google.com (mail-wm1-f47.google.com [209.85.128.47]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C05133A1A23 for ; Sun, 16 Aug 2026 17:07:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900024; cv=none; b=baG+LJpJ9tXA+LEV5Be6g1iXF+4rK7yAt9xelbVI7Mfc6Wl2yN5fobE/Ik9RLooK6UzwYDA1dK7d9I8M92/MYZbvDb/aKhncy0IN/dtNmZ7kfNYfy5IUPG4fqJs852qejGeOMFMGoTVN7akaC68BzEl0hpcvikfDiK22u3NvIiA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900024; c=relaxed/simple; bh=UjKZbgfnH1XMHC6xC5BUOWE08XCJYVIJ9QrIeEmUvZI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=O/yPWBIyjmyhaTySdL1ncWPOl+yv65JTmEuagPdP7re+apiBP+YU0UbGJACnjyunLMuSZe0VIU7/nB7wcJfrqbA/E87RgJbYUR/XV6sFXyGnBk62Kk6xTNJWdoEuT0Kixir+oujUcuLNPE5ZuTwNwnXjlB+Trkz2H7KXf63dUOE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=om0R+S7v; arc=none smtp.client-ip=209.85.128.47 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="om0R+S7v" Received: by mail-wm1-f47.google.com with SMTP id 5b1f17b1804b1-4956869750eso17583055e9.2 for ; Sun, 16 Aug 2026 10:07:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786900021; x=1787504821; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=HVcyBope6DGMi/80lpE9C+i3r+YlYpBjseKIjfNL3rQ=; b=om0R+S7v5h63SVYRNsYOkpVe9ssIC8V3cXmzJx9kngHNEJzXQ0O8Uk26corHOJBoMO yUCS7YQn8ngL1UtQC0LcpObHmJbZQWXtYCaDJUtAi+/fU6VQKhfwGr7rS+cdLCY2Dbb+ lyQjGAvUwet1e6/+395kQcuDmqQV7NwyvtPopMS//l5ze7mqkmNXu+R0dDjCGR1qxwmd ia8LSPxwgKiuV3Otctvq/6ZQ/6mtq00skbEnUZrnzxkBYfZ7UZj+wBHrHtYiKMeOTSPO USIIMVUcVWzCZ/PgonoS3I4LGn3bSQZYmWAgqcF0L1iIGkwCZRiyL8+tlH7re2DAiF02 WytA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786900021; x=1787504821; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=HVcyBope6DGMi/80lpE9C+i3r+YlYpBjseKIjfNL3rQ=; b=dRwsAMaV3vgHcAf97xKCPd0SjlnixjpkJTv9pQpE0UlS8BEkT0OACGDGnvYF/Swo7N KBj87mjJU+QWLYZoUBgdBrPP9jmilL7Ke7IqOmRv4V5YYiEZu+/u0HeAwiyj7O3wnptU gXkusDuERTaxaQSgxS1CmtgvCNpEnUIuwJvvJNnyIneHOTgTTPfOeJ9+HEdEhC5RfWlT dq1sz9xp1aJ4cpUl8oiMQfk/6iehzHly1bfxNam7YG4bcoUf983pUSEpYUPTzbcOiLUw QaRXAu/rq+L8gC6mBhE6SQjptzfkOgZPqNLzsD+5IkxNJvzCRI/ANHjQ9J/flhd5VMg9 DD7g== X-Gm-Message-State: AOJu0YyIBr8LPJNipKaThUQHLdL39xY1wLAg1xTZ4AzEoLNwxYpwRnme rWRzGgTP0CZ33i6RSLLJtzdWo0Xb9Nfmp/CLPTSZYnfkn5PIt6lWKTYC X-Gm-Gg: AR+sD10ms48MuMg2tPxbJlnD8rD/9XrYCnVmd4VfMOfg45y6T3zQl+LfJGMt9zzhqCB 5M59A24foZgzw6IIaDGiM6zw/Egm5nI76jFrCbPDNLQ+Jg6iDGVI9BOnz9IqohDi/KsdvvCPP3x yBNhP1bF4KJozeZBbwhw9jeP3Yo+jRAvZ7TORSu9X6UJn/CgzSFgyOcJ1aN5g1oyv3XmzrQhyov psF9dxZTDPZBq0jRaPAt1TgbsKt2sn0+1I/yUMDaxhHN0L7yNs1ZQZ4bb+bFt5q/FtvddSI+yOp T9Q/Bz8B+Qr4Sv/CWgBYsJRRjBvRVuV1izgljvWSfaZaTT4CLXqL3ZsiWeRqdHufJID1tXzA9Ca 0K0qV45Z7CaP7JeAmJpdWuZUHJ4mH4W8yvXCXtemULLKuHEmFmTYxcK6lpKaVyN5pRNqrYx6KdO ttTunTt08+Ma+SDJkQZ0Vi5OYg3O3kgbYhuQBjwrquih51KydjVFPYpXObrtLXt9MwyWj2BzvaV TyDtEe8ZYZamgcHPF7FoOlXdzM/iuy59PeJqb56djkUK4djupQevzjRNxahwWVWyYw3bmKCCIvt p01upPjSIKQitIw2WFaNA4/P0RnmReDL27lZtpY= X-Received: by 2002:a05:600c:3485:b0:499:8758:8cb4 with SMTP id 5b1f17b1804b1-49987935eecmr314132475e9.5.1786900020748; Sun, 16 Aug 2026 10:07:00 -0700 (PDT) Received: from localhost.localdomain (p54a14b85.dip0.t-ipconnect.de. [84.161.75.133]) by smtp.gmail.com with ESMTPSA id 5b1f17b1804b1-4999618acafsm55671335e9.14.2026.08.16.10.07.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 16 Aug 2026 10:07:00 -0700 (PDT) From: Bernard Ladenthin To: akpm@linux-foundation.org Cc: linux-kernel@vger.kernel.org, pablo@netfilter.org, fw@strlen.de, netfilter-devel@vger.kernel.org, kunit-dev@googlegroups.com, davem@davemloft.net, Bernard Ladenthin Subject: [PATCH 3/4] textsearch: align ts_state.cb like skb->cb Date: Sun, 16 Aug 2026 19:05:39 +0200 Message-ID: <20260816170541.3384-4-bernard.ladenthin@gmail.com> X-Mailer: git-send-email 2.49.0.windows.1 In-Reply-To: <20260816170541.3384-1-bernard.ladenthin@gmail.com> References: <20260816170541.3384-1-bernard.ladenthin@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" struct 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. Signed-off-by: Bernard Ladenthin --- 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(-) diff --git a/include/linux/textsearch.h b/include/linux/textsearch.h index 4933777404d6..e117f9c9de59 100644 --- a/include/linux/textsearch.h +++ b/include/linux/textsearch.h @@ -23,7 +23,7 @@ struct ts_config; struct ts_state { unsigned int offset; - char cb[48]; + char cb[48] __aligned(8); }; =20 /** --=20 2.49.0.windows.1 From nobody Mon Aug 24 04:17:55 2026 Received: from mail-wm1-f46.google.com (mail-wm1-f46.google.com [209.85.128.46]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 56F783A8753 for ; Sun, 16 Aug 2026 17:07:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900026; cv=none; b=Z5FRVX7pFvAQZ0NVeWDn7V6MfjDK0UnnvhEi+cyIOHeDQcTbPopevbo4Xi0vOLQAlZr3FSwggLvazXH30bZV6b8QhqPfhVe0O47Q6ZhP2V+hHotNM53ehArZ7+L5wJU7ifnv83BP2kdM/AowSgQpunFRgkTK0nQMjLZz1MCEwhI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786900026; c=relaxed/simple; bh=gxV4kQ+OCvgh/Dml0PD7+RUVFmfyn0qzpnWoEaFYUHc=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=fV0flHlMCP5xOG1JXjyvBgo76DWK0ZRwKpPLxib51hHdJzrZLUYQpnr1XT4U6uZmu+nxXSF2aObzIGjLXUWbLmbvRtUT9x31LiOUU/XhUPbhJPenfbQlTcng+5qTw6vfvthRzZ0ZNp058FW1nMqAculV7DAAby35iL+xkeyWW+Q= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=PrBiQKJA; arc=none smtp.client-ip=209.85.128.46 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="PrBiQKJA" Received: by mail-wm1-f46.google.com with SMTP id 5b1f17b1804b1-4998b5a63e2so18994555e9.1 for ; Sun, 16 Aug 2026 10:07:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1786900023; x=1787504823; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to:content-type; bh=ADy21TiCO8lIm8cjutcu3wh44q8LK9FtOZhFKac1cq8=; b=PrBiQKJAusXaH5q6tA+c4lXbXKI2onxlRcGg7V6WM+LLG4eaD5BcLStlREPVBghGaR avuO2drhkRlP+gFINM64qNeaRALQ6YXBaxfdQILb0V9AHMLRkPZt3zCe+IhEeBNb/atC wuQ5HO1SboTXLpVNewSPQCyXLdSzeWdzgbZy/gMzMQlc+xV7wBpYqlmzfosvmuTVLexI FjALWs8yRC/NvScwN6tLH86Ty0GS68hkD6hZPbCk+Ws/REKD18uWRnibBxdWVxVlUOuZ YgeJsEViQ14VWIhxh5rXrtg1TZqRPDYd2qQBaGnV6V38yuvYjA3gIDLdzeOKi+qdVtfn e0ow== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1786900023; x=1787504823; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to:content-type; bh=ADy21TiCO8lIm8cjutcu3wh44q8LK9FtOZhFKac1cq8=; b=J6RQFz3ZYDTJ5faUgxyqnbxLDsiVfGSbH0CWQ/0cZgpMPNWqQgyFFBe8VGo9z8SKeM XwhfCLT9DSZWvDNvYYuwCXu87aJdBoPsFWmvUFjVg3kGOIeLtcvaVPuVK2V4k8jHjwiL /rJcBbYRtNkTEihNUXwd8AzcWPqLkXEpuR7QvafLIx/nOCfXEVEgqgK/DETpOmW5jqfq bEV7BVERcocrqQNpWTAh/NyJepN0qhwtglZpoyadAdRqHJqLccBRl7UdIHGhWYokUSJe v/8OVNCP3K1T5uA6ZtBrWhc+oEAycij62mbgDaoIWqPRaUNRCV5X8WVBzCwmoF4v5c87 pKOg== X-Gm-Message-State: AOJu0Yy7hHjGV37NVA/Efd090PHfp6hEPktvIm5IwbDFY7AZpw7vGseL t1Jw8/MJKyimHuQ45ulCCx7fxsuQbnppKdKxEAlI2xeKR0VNvmyGuaaL X-Gm-Gg: AR+sD13PA/ddAqKUx9v6X1CFSmAba4cFWnHXWMkpt5MtnljL0zAiyUvwiIm+mkX2lNQ fI8tSSoQqiwSjUZOJ4zYsgJmJ5gz1v6H2EfWtJjpMuUgFjjkOL9AsMtjbV/ZTNyEmWyYgxpYmKV hRL7Bm49Wmchfw+uJ7+eUuPmgZ+neUW+nenayLX6DwOVRbNRaYjD+uxHgN43Hjcgu1CtWCymRHB weFH1xy9mFvqnIpaHHwtp89IzpVsOr9oYzUHE6hQNUB8xYzk5xoY2D8nYhA4Ulqk7DIPdiJS4xV yKfjUumV9545zCZgZy19rm5ulY/nO8UFHcsSk6cM/9nmlyorU65VDy+FrrWy3PGMpTocyJqe3Aw j2MfDHWdVuUiqFfFyQZIczMDzFptzVoX1Ii7DvbDDoUfXZiikmJq8kHkhI9IXQrQl8n5hoA3O2b mQ0RLSQBKRmE6K/rLc8mTMRV9G42icKHjDi7dDCaHJ9BFHgBF23Y6aDE55PQU164fB15Xl8uZUE dbBQ5B2B9uGNQU58hJoIUbXmxad5LvKQsh8uXiATNLVDDX0NEZvMYvTmio6uvwH5iEyqcvlLMNC JlUyA/UJk7DEA6rtSbuVqDD1jCcnRzWsE97/dFY= X-Received: by 2002:a05:600c:6289:b0:499:84fe:ca8c with SMTP id 5b1f17b1804b1-499879332e1mr265118815e9.5.1786900023344; Sun, 16 Aug 2026 10:07:03 -0700 (PDT) Received: from localhost.localdomain (p54a14b85.dip0.t-ipconnect.de. [84.161.75.133]) by smtp.gmail.com with ESMTPSA id 5b1f17b1804b1-4999618acafsm55671335e9.14.2026.08.16.10.07.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 16 Aug 2026 10:07:03 -0700 (PDT) From: Bernard Ladenthin To: akpm@linux-foundation.org Cc: linux-kernel@vger.kernel.org, pablo@netfilter.org, fw@strlen.de, netfilter-devel@vger.kernel.org, kunit-dev@googlegroups.com, davem@davemloft.net, Bernard Ladenthin Subject: [PATCH 4/4] lib/ts_fsm: document that a match must consume the remaining data Date: Sun, 16 Aug 2026 19:05:40 +0200 Message-ID: <20260816170541.3384-5-bernard.ladenthin@gmail.com> X-Mailer: git-send-email 2.49.0.windows.1 In-Reply-To: <20260816170541.3384-1-bernard.ladenthin@gmail.com> References: <20260816170541.3384-1-bernard.ladenthin@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" fsm_find() reports a match only once the token chain has matched and the data is exhausted: for (tok_idx =3D 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 =3D=3D 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. Signed-off-by: Bernard Ladenthin --- 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(+) diff --git a/lib/ts_fsm.c b/lib/ts_fsm.c index 053615f4fcd7..ceec6295505c 100644 --- a/lib/ts_fsm.c +++ b/lib/ts_fsm.c @@ -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. */ --=20 2.49.0.windows.1