* + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch
@ 2026-03-09 20:24 Andrew Morton
2026-03-09 20:35 ` Josh Law
0 siblings, 1 reply; 6+ messages in thread
From: Andrew Morton @ 2026-03-09 20:24 UTC (permalink / raw)
To: mm-commits, objecting, akpm
The patch titled
Subject: lib/ts_kmp: fix integer overflow in pattern length calculation
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via various
branches at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there most days
------------------------------------------------------
From: Josh Law <objecting@objecting.org>
Subject: lib/ts_kmp: fix integer overflow in pattern length calculation
Date: Sun, 8 Mar 2026 20:20:28 +0000
The ts_kmp algorithm stores its prefix_tbl[] table and pattern in a single
allocation sized from the pattern length. If the prefix_tbl[] size
calculation wraps, the resulting allocation can be too small and
subsequent pattern copies can overflow it.
Fix this by rejecting zero-length patterns and by using overflow helpers
before calculating the combined allocation size.
Link: https://lkml.kernel.org/r/20260308202028.2889285-2-objecting@objecting.org
Signed-off-by: Josh Law <objecting@objecting.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/ts_kmp.c | 18 ++++++++++++++++--
1 file changed, 16 insertions(+), 2 deletions(-)
--- a/lib/ts_kmp.c~lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation
+++ a/lib/ts_kmp.c
@@ -94,8 +94,22 @@ static struct ts_config *kmp_init(const
struct ts_config *conf;
struct ts_kmp *kmp;
int i;
- unsigned int prefix_tbl_len = len * sizeof(unsigned int);
- size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len;
+ unsigned int prefix_tbl_len;
+ size_t priv_size;
+
+ /* Zero-length patterns would make kmp_find() read beyond kmp->pattern. */
+ if (unlikely(!len))
+ return ERR_PTR(-EINVAL);
+
+ /*
+ * kmp->pattern is stored immediately after the prefix_tbl[] table.
+ * Reject lengths that would wrap while sizing either region.
+ */
+ if (unlikely(check_mul_overflow(len, sizeof(*kmp->prefix_tbl),
+ &prefix_tbl_len) ||
+ check_add_overflow(sizeof(*kmp), (size_t)len, &priv_size) ||
+ check_add_overflow(priv_size, prefix_tbl_len, &priv_size)))
+ return ERR_PTR(-EINVAL);
conf = alloc_ts_config(priv_size, gfp_mask);
if (IS_ERR(conf))
_
Patches currently in -mm which might be from objecting@objecting.org are
lib-maple_tree-fix-swapped-arguments-in-mas_safe_pivot-call.patch
lib-glob-fix-grammar-and-replace-non-inclusive-terminology.patch
lib-glob-add-explicit-include-for-exporth.patch
lib-glob-replace-bitwise-or-with-logical-operation-on-boolean.patch
lib-glob-clean-up-bool-abuse-in-pointer-arithmetic.patch
lib-uuid-fix-typo-reversion-to-revision-in-comment.patch
lib-inflate-fix-memory-leak-in-inflate_fixed-on-inflate_codes-failure.patch
lib-inflate-fix-memory-leak-in-inflate_dynamic-on-inflate_codes-failure.patch
lib-inflate-fix-grammar-in-comment-variable-to-variables.patch
lib-inflate-fix-typo-this-results-to-the-results-in-comment.patch
lib-bug-fix-inconsistent-capitalization-in-bug-message.patch
lib-bug-remove-unnecessary-variable-initializations.patch
lib-idr-fix-ida_find_first_range-missing-ids-across-chunk-boundaries.patch
lib-decompress_bunzip2-fix-32-bit-shift-undefined-behavior.patch
maintainers-add-josh-law-as-reviewer-for-library-code.patch
lib-bootconfig-fix-typo-budy-in-_xbc_exit-comment.patch
lib-ts_bm-fix-integer-overflow-in-pattern-length-calculation.patch
lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch
2026-03-09 20:24 + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch Andrew Morton
@ 2026-03-09 20:35 ` Josh Law
2026-03-09 20:43 ` Andrew Morton
0 siblings, 1 reply; 6+ messages in thread
From: Josh Law @ 2026-03-09 20:35 UTC (permalink / raw)
To: Andrew Morton; +Cc: mm-commits, objecting
9 Mar 2026 20:24:36 Andrew Morton <akpm@linux-foundation.org>:
>
> The patch titled
> Subject: lib/ts_kmp: fix integer overflow in pattern length calculation
> has been added to the -mm mm-nonmm-unstable branch. Its filename is
> lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch
>
> This patch will shortly appear at
> https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch
>
> This patch will later appear in the mm-nonmm-unstable branch at
> git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
>
> Before you just go and hit "reply", please:
> a) Consider who else should be cc'ed
> b) Prefer to cc a suitable mailing list as well
> c) Ideally: find the original patch on the mailing list and do a
> reply-to-all to that, adding suitable additional cc's
>
> *** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
>
> The -mm tree is included into linux-next via various
> branches at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
> and is updated there most days
>
> ------------------------------------------------------
> From: Josh Law <objecting@objecting.org>
> Subject: lib/ts_kmp: fix integer overflow in pattern length calculation
> Date: Sun, 8 Mar 2026 20:20:28 +0000
>
> The ts_kmp algorithm stores its prefix_tbl[] table and pattern in a single
> allocation sized from the pattern length. If the prefix_tbl[] size
> calculation wraps, the resulting allocation can be too small and
> subsequent pattern copies can overflow it.
>
> Fix this by rejecting zero-length patterns and by using overflow helpers
> before calculating the combined allocation size.
>
> Link: https://lkml.kernel.org/r/20260308202028.2889285-2-objecting@objecting.org
> Signed-off-by: Josh Law <objecting@objecting.org>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> ---
>
> lib/ts_kmp.c | 18 ++++++++++++++++--
> 1 file changed, 16 insertions(+), 2 deletions(-)
>
> --- a/lib/ts_kmp.c~lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation
> +++ a/lib/ts_kmp.c
> @@ -94,8 +94,22 @@ static struct ts_config *kmp_init(const
> struct ts_config *conf;
> struct ts_kmp *kmp;
> int i;
> - unsigned int prefix_tbl_len = len * sizeof(unsigned int);
> - size_t priv_size = sizeof(*kmp) + len + prefix_tbl_len;
> + unsigned int prefix_tbl_len;
> + size_t priv_size;
> +
> + /* Zero-length patterns would make kmp_find() read beyond kmp->pattern. */
> + if (unlikely(!len))
> + return ERR_PTR(-EINVAL);
> +
> + /*
> + * kmp->pattern is stored immediately after the prefix_tbl[] table.
> + * Reject lengths that would wrap while sizing either region.
> + */
> + if (unlikely(check_mul_overflow(len, sizeof(*kmp->prefix_tbl),
> + &prefix_tbl_len) ||
> + check_add_overflow(sizeof(*kmp), (size_t)len, &priv_size) ||
> + check_add_overflow(priv_size, prefix_tbl_len, &priv_size)))
> + return ERR_PTR(-EINVAL);
>
> conf = alloc_ts_config(priv_size, gfp_mask);
> if (IS_ERR(conf))
> _
>
> Patches currently in -mm which might be from objecting@objecting.org are
>
> lib-maple_tree-fix-swapped-arguments-in-mas_safe_pivot-call.patch
> lib-glob-fix-grammar-and-replace-non-inclusive-terminology.patch
> lib-glob-add-explicit-include-for-exporth.patch
> lib-glob-replace-bitwise-or-with-logical-operation-on-boolean.patch
> lib-glob-clean-up-bool-abuse-in-pointer-arithmetic.patch
> lib-uuid-fix-typo-reversion-to-revision-in-comment.patch
> lib-inflate-fix-memory-leak-in-inflate_fixed-on-inflate_codes-failure.patch
> lib-inflate-fix-memory-leak-in-inflate_dynamic-on-inflate_codes-failure.patch
> lib-inflate-fix-grammar-in-comment-variable-to-variables.patch
> lib-inflate-fix-typo-this-results-to-the-results-in-comment.patch
> lib-bug-fix-inconsistent-capitalization-in-bug-message.patch
> lib-bug-remove-unnecessary-variable-initializations.patch
> lib-idr-fix-ida_find_first_range-missing-ids-across-chunk-boundaries.patch
> lib-decompress_bunzip2-fix-32-bit-shift-undefined-behavior.patch
> maintainers-add-josh-law-as-reviewer-for-library-code.patch
> lib-bootconfig-fix-typo-budy-in-_xbc_exit-comment.patch
> lib-ts_bm-fix-integer-overflow-in-pattern-length-calculation.patch
> lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch
Do you think these patches require Cc: stable?
Idk the severity of the bug to you, the swapped arguments got Cc stable, overflow could cause some screwy bugs
V/R
Josh Law
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch
2026-03-09 20:35 ` Josh Law
@ 2026-03-09 20:43 ` Andrew Morton
2026-03-09 20:45 ` Josh Law
0 siblings, 1 reply; 6+ messages in thread
From: Andrew Morton @ 2026-03-09 20:43 UTC (permalink / raw)
To: Josh Law; +Cc: mm-commits, objecting
On Mon, 9 Mar 2026 20:35:07 +0000 Josh Law <hlcj1234567@gmail.com> wrote:
> Do you think these patches require Cc: stable?
> Idk the severity of the bug to you, the swapped arguments got Cc stable, overflow could cause some screwy bugs
Probably not - is there any reason to believe any callers will hit this?
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch
2026-03-09 20:43 ` Andrew Morton
@ 2026-03-09 20:45 ` Josh Law
2026-03-09 20:54 ` Josh Law
0 siblings, 1 reply; 6+ messages in thread
From: Josh Law @ 2026-03-09 20:45 UTC (permalink / raw)
To: Andrew Morton; +Cc: mm-commits, objecting
9 Mar 2026 20:43:11 Andrew Morton <akpm@linux-foundation.org>:
> On Mon, 9 Mar 2026 20:35:07 +0000 Josh Law <hlcj1234567@gmail.com> wrote:
>
>> Do you think these patches require Cc: stable?
>> Idk the severity of the bug to you, the swapped arguments got Cc stable, overflow could cause some screwy bugs
>
> Probably not - is there any reason to believe any callers will hit this?
I’ve been looking at the callers. While most are in-kernel constants, xt_string in Netfilter allows for dynamic patterns. Even if it's currently mitigated elsewhere, hardening the allocation logic in ts_bm and ts_kmp feels like a 'must-have' for stable trees to prevent future heap overflow vectors. Basically... Better safe than sorry!
V/R
Josh law
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch
2026-03-09 20:45 ` Josh Law
@ 2026-03-09 20:54 ` Josh Law
2026-03-09 21:47 ` Josh Law
0 siblings, 1 reply; 6+ messages in thread
From: Josh Law @ 2026-03-09 20:54 UTC (permalink / raw)
To: Andrew Morton; +Cc: mm-commits, objecting
9 Mar 2026 20:45:45 Josh Law <hlcj1234567@gmail.com>:
> 9 Mar 2026 20:43:11 Andrew Morton <akpm@linux-foundation.org>:
>
>> On Mon, 9 Mar 2026 20:35:07 +0000 Josh Law <hlcj1234567@gmail.com> wrote:
>>
>>> Do you think these patches require Cc: stable?
>>> Idk the severity of the bug to you, the swapped arguments got Cc stable, overflow could cause some screwy bugs
>>
>> Probably not - is there any reason to believe any callers will hit this?
>
> I’ve been looking at the callers. While most are in-kernel constants, xt_string in Netfilter allows for dynamic patterns. Even if it's currently mitigated elsewhere, hardening the allocation logic in ts_bm and ts_kmp feels like a 'must-have' for stable trees to prevent future heap overflow vectors. Basically... Better safe than sorry!
>
>
> V/R
>
>
>
> Josh law
Yeah, I now think Cc: stable is a need for both of the overflows, I am thinking about that 32 bit shift aswell, but that probably won't need it
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch
2026-03-09 20:54 ` Josh Law
@ 2026-03-09 21:47 ` Josh Law
0 siblings, 0 replies; 6+ messages in thread
From: Josh Law @ 2026-03-09 21:47 UTC (permalink / raw)
To: Andrew Morton; +Cc: mm-commits, objecting
9 Mar 2026 20:54:29 Josh Law <hlcj1234567@gmail.com>:
> 9 Mar 2026 20:45:45 Josh Law <hlcj1234567@gmail.com>:
>
>> 9 Mar 2026 20:43:11 Andrew Morton <akpm@linux-foundation.org>:
>>
>>> On Mon, 9 Mar 2026 20:35:07 +0000 Josh Law <hlcj1234567@gmail.com> wrote:
>>>
>>>> Do you think these patches require Cc: stable?
>>>> Idk the severity of the bug to you, the swapped arguments got Cc stable, overflow could cause some screwy bugs
>>>
>>> Probably not - is there any reason to believe any callers will hit this?
>>
>> I’ve been looking at the callers. While most are in-kernel constants, xt_string in Netfilter allows for dynamic patterns. Even if it's currently mitigated elsewhere, hardening the allocation logic in ts_bm and ts_kmp feels like a 'must-have' for stable trees to prevent future heap overflow vectors. Basically... Better safe than sorry!
>>
>>
>> V/R
>>
>>
>>
>> Josh law
>
> Yeah, I now think Cc: stable is a need for both of the overflows, I am thinking about that 32 bit shift aswell, but that probably won't need it
Cc: <stable@vger.kernel.org>
These patches (ts_bm and ts_kmp) fix a potential heap overflow. The pattern length calculation can wrap during a size_t addition, leading to an undersized allocation. Because the textsearch library is reachable from userspace via Netfilter's xt_string module, this is a security risk that should be backported to LTS kernels.
V/R
Josh law
(This is my final input :D)
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2026-03-09 21:47 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-03-09 20:24 + lib-ts_kmp-fix-integer-overflow-in-pattern-length-calculation.patch added to mm-nonmm-unstable branch Andrew Morton
2026-03-09 20:35 ` Josh Law
2026-03-09 20:43 ` Andrew Morton
2026-03-09 20:45 ` Josh Law
2026-03-09 20:54 ` Josh Law
2026-03-09 21:47 ` Josh Law
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.