* [merged mm-hotfixes-stable] assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch removed from -mm tree
@ 2026-11-10 6:45 Andrew Morton
2026-11-17 13:22 ` David Hildenbrand (Arm)
0 siblings, 1 reply; 3+ messages in thread
From: Andrew Morton @ 2026-11-10 6:45 UTC (permalink / raw)
To: mm-commits, stable, jarkko, dhowells, 4ncienth, akpm
The quilt patch titled
Subject: assoc_array: discard shortcut when collapsing a leaf-only node
has been removed from the -mm tree. Its filename was
assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch
This patch was dropped because it was merged into the mm-hotfixes-stable branch
of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
------------------------------------------------------
From: Daehyeon Ko <4ncienth@gmail.com>
Subject: assoc_array: discard shortcut when collapsing a leaf-only node
Date: Fri, 25 Sep 2026 17:05:48 +0900
assoc_array_delete() can collapse a subtree into a node that contains only
leaves while retaining the shortcut that led to it. If that node later
fills, all_leaves_cluster_together replaces it with another shortcut. The
first shortcut then points directly to the second one.
assoc_array_apply_edit() publishes this topology and propagates branch
counts from the new child node. It skips the inner shortcut, encounters
the outer shortcut where it requires a node and triggers the BUG_ON().
Linux v7.2 and v6.12.105 are affected. The same root remains at the
base-commit below and in every supported stable branch checked down to
5.10. It requires CONFIG_KEYS, but no capability, user namespace or race.
A UID/GID 1000 process produced:
CONTROL_BEGIN mode=exact uid=1000 gid=1000
CONTROL_CapEff: 0000000000000000
kernel BUG at lib/assoc_array.c:1388!
Oops: invalid opcode: 0000 [#1] SMP KASAN NOPTI
CPU: 0 UID: 1000 PID: 154 Comm: exploit
RIP: assoc_array_apply_edit+0x4aa/0x690
Call Trace:
__key_link
__key_instantiate_and_link
__key_create_or_update
__do_sys_add_key
Kernel panic - not syncing: Fatal exception
When deletion produces a leaf-only node, bypass its preceding shortcut as
garbage collection already does. Retire the shortcut and old node
together after an RCU grace period; reused leaves keep their references
and the deleted leaf is still freed separately.
The exact trigger reached the BUG in 3/3 unmodified v7.2 KASAN boots and
completed cleanly in 3/3 fixed boots. Fixed v6.12.105 also passed 3/3. A
source reproducer is available privately on request.
Link: https://lore.kernel.org/20260925080548.2505640-1-4ncienth@gmail.com
Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
Signed-off-by: Daehyeon Ko <4ncienth@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Reviewed-by: Jarkko Sakkinen <jarkko@kernel.org>
Cc: David Howells <dhowells@redhat.com>
Cc: <stable@vger.kernel.org>
---
lib/assoc_array.c | 36 ++++++++++++++++++++++--------------
1 file changed, 22 insertions(+), 14 deletions(-)
--- a/lib/assoc_array.c~assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node
+++ a/lib/assoc_array.c
@@ -1210,8 +1210,22 @@ found_leaf:
goto enomem;
edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
- new_n0->back_pointer = node->back_pointer;
- new_n0->parent_slot = node->parent_slot;
+ /* A shortcut above a leaf-only node is redundant. Drop it as
+ * GC does so that a later split can't create two shortcuts in a row.
+ */
+ ptr = node->back_pointer;
+ if (assoc_array_ptr_is_shortcut(ptr)) {
+ struct assoc_array_shortcut *s =
+ assoc_array_ptr_to_shortcut(ptr);
+
+ new_n0->back_pointer = s->back_pointer;
+ new_n0->parent_slot = s->parent_slot;
+ edit->excised_subtree = ptr;
+ } else {
+ new_n0->back_pointer = ptr;
+ new_n0->parent_slot = node->parent_slot;
+ edit->excised_subtree = assoc_array_node_to_ptr(node);
+ }
new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
edit->adjust_count_on = new_n0;
@@ -1225,21 +1239,15 @@ found_leaf:
pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
- if (!node->back_pointer) {
+ if (!new_n0->back_pointer) {
edit->set[1].ptr = &array->root;
- } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
- BUG();
- } else if (assoc_array_ptr_is_node(node->back_pointer)) {
- struct assoc_array_node *p =
- assoc_array_ptr_to_node(node->back_pointer);
- edit->set[1].ptr = &p->slots[node->parent_slot];
- } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
- struct assoc_array_shortcut *s =
- assoc_array_ptr_to_shortcut(node->back_pointer);
- edit->set[1].ptr = &s->next_node;
+ } else {
+ struct assoc_array_node *p;
+
+ p = assoc_array_ptr_to_node(new_n0->back_pointer);
+ edit->set[1].ptr = &p->slots[new_n0->parent_slot];
}
edit->set[1].to = assoc_array_node_to_ptr(new_n0);
- edit->excised_subtree = assoc_array_node_to_ptr(node);
}
}
_
Patches currently in -mm which might be from 4ncienth@gmail.com are
iov_iter-validate-extracted-segment-for-bvec-alignment.patch
mm-hugetlb_cgroup-prevent-use-after-free-during-cgroup-offlining.patch
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [merged mm-hotfixes-stable] assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch removed from -mm tree
2026-11-10 6:45 [merged mm-hotfixes-stable] assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch removed from -mm tree Andrew Morton
@ 2026-11-17 13:22 ` David Hildenbrand (Arm)
2026-11-17 14:17 ` Jarkko Sakkinen
0 siblings, 1 reply; 3+ messages in thread
From: David Hildenbrand (Arm) @ 2026-11-17 13:22 UTC (permalink / raw)
To: Andrew Morton, mm-commits, stable, jarkko, dhowells, 4ncienth
On 11/10/26 07:45, Andrew Morton wrote:
> The quilt patch titled
> Subject: assoc_array: discard shortcut when collapsing a leaf-only node
> has been removed from the -mm tree. Its filename was
> assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch
>
> This patch was dropped because it was merged into the mm-hotfixes-stable branch
> of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
>
> ------------------------------------------------------
> From: Daehyeon Ko <4ncienth@gmail.com>
> Subject: assoc_array: discard shortcut when collapsing a leaf-only node
> Date: Fri, 25 Sep 2026 17:05:48 +0900
>
> assoc_array_delete() can collapse a subtree into a node that contains only
> leaves while retaining the shortcut that led to it. If that node later
> fills, all_leaves_cluster_together replaces it with another shortcut. The
> first shortcut then points directly to the second one.
>
> assoc_array_apply_edit() publishes this topology and propagates branch
> counts from the new child node. It skips the inner shortcut, encounters
> the outer shortcut where it requires a node and triggers the BUG_ON().
>
> Linux v7.2 and v6.12.105 are affected. The same root remains at the
> base-commit below and in every supported stable branch checked down to
> 5.10. It requires CONFIG_KEYS, but no capability, user namespace or race.
> A UID/GID 1000 process produced:
>
> CONTROL_BEGIN mode=exact uid=1000 gid=1000
> CONTROL_CapEff: 0000000000000000
> kernel BUG at lib/assoc_array.c:1388!
> Oops: invalid opcode: 0000 [#1] SMP KASAN NOPTI
> CPU: 0 UID: 1000 PID: 154 Comm: exploit
> RIP: assoc_array_apply_edit+0x4aa/0x690
> Call Trace:
> __key_link
> __key_instantiate_and_link
> __key_create_or_update
> __do_sys_add_key
> Kernel panic - not syncing: Fatal exception
>
> When deletion produces a leaf-only node, bypass its preceding shortcut as
> garbage collection already does. Retire the shortcut and old node
> together after an RCU grace period; reused leaves keep their references
> and the deleted leaf is still freed separately.
>
> The exact trigger reached the BUG in 3/3 unmodified v7.2 KASAN boots and
> completed cleanly in 3/3 fixed boots. Fixed v6.12.105 also passed 3/3. A
> source reproducer is available privately on request.
>
> Link: https://lore.kernel.org/20260925080548.2505640-1-4ncienth@gmail.com
> Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> Signed-off-by: Daehyeon Ko <4ncienth@gmail.com>
> Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> Reviewed-by: Jarkko Sakkinen <jarkko@kernel.org>
> Cc: David Howells <dhowells@redhat.com>
> Cc: <stable@vger.kernel.org>
> ---
>
> lib/assoc_array.c | 36 ++++++++++++++++++++++--------------
> 1 file changed, 22 insertions(+), 14 deletions(-)
>
> --- a/lib/assoc_array.c~assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node
> +++ a/lib/assoc_array.c
> @@ -1210,8 +1210,22 @@ found_leaf:
> goto enomem;
> edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
>
> - new_n0->back_pointer = node->back_pointer;
> - new_n0->parent_slot = node->parent_slot;
> + /* A shortcut above a leaf-only node is redundant. Drop it as
> + * GC does so that a later split can't create two shortcuts in a row.
> + */
> + ptr = node->back_pointer;
> + if (assoc_array_ptr_is_shortcut(ptr)) {
> + struct assoc_array_shortcut *s =
> + assoc_array_ptr_to_shortcut(ptr);
> +
> + new_n0->back_pointer = s->back_pointer;
> + new_n0->parent_slot = s->parent_slot;
> + edit->excised_subtree = ptr;
> + } else {
> + new_n0->back_pointer = ptr;
> + new_n0->parent_slot = node->parent_slot;
> + edit->excised_subtree = assoc_array_node_to_ptr(node);
> + }
> new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
> edit->adjust_count_on = new_n0;
>
> @@ -1225,21 +1239,15 @@ found_leaf:
> pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
> BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
>
> - if (!node->back_pointer) {
> + if (!new_n0->back_pointer) {
> edit->set[1].ptr = &array->root;
> - } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
> - BUG();
> - } else if (assoc_array_ptr_is_node(node->back_pointer)) {
> - struct assoc_array_node *p =
> - assoc_array_ptr_to_node(node->back_pointer);
> - edit->set[1].ptr = &p->slots[node->parent_slot];
> - } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
> - struct assoc_array_shortcut *s =
> - assoc_array_ptr_to_shortcut(node->back_pointer);
> - edit->set[1].ptr = &s->next_node;
> + } else {
> + struct assoc_array_node *p;
> +
> + p = assoc_array_ptr_to_node(new_n0->back_pointer);
> + edit->set[1].ptr = &p->slots[new_n0->parent_slot];
> }
> edit->set[1].to = assoc_array_node_to_ptr(new_n0);
> - edit->excised_subtree = assoc_array_node_to_ptr(node);
> }
> }
This causes conflicts with upstream. I suspect with Linus' cleanups part of
commit 666539eecdf4db623f5e3c3e55cf9f2dfad24aa4 (origin/master, origin/HEAD,
master, base)
Merge: 141b164bbe18 bbab563c5131
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date: Mon Nov 16 09:35:38 2026 -0800
Merge tag 'assoc-array-fixes-v2'
Clean up assoc_array library code
It's in akpm/mm-hotfixes-unstable, but is this really MM material?
Sounds more like nonmm stuff.
Anyhow, I'll drop this from now from mm-next as I couldn't easily figure out how
to resolve this (or if it is still required).
--
Cheers,
David
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [merged mm-hotfixes-stable] assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch removed from -mm tree
2026-11-17 13:22 ` David Hildenbrand (Arm)
@ 2026-11-17 14:17 ` Jarkko Sakkinen
0 siblings, 0 replies; 3+ messages in thread
From: Jarkko Sakkinen @ 2026-11-17 14:17 UTC (permalink / raw)
To: David Hildenbrand (Arm)
Cc: Andrew Morton, mm-commits, stable, dhowells, 4ncienth
On Tue, Nov 17, 2026 at 02:22:22PM +0100, David Hildenbrand (Arm) wrote:
> On 11/10/26 07:45, Andrew Morton wrote:
> > The quilt patch titled
> > Subject: assoc_array: discard shortcut when collapsing a leaf-only node
> > has been removed from the -mm tree. Its filename was
> > assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch
> >
> > This patch was dropped because it was merged into the mm-hotfixes-stable branch
> > of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
> >
> > ------------------------------------------------------
> > From: Daehyeon Ko <4ncienth@gmail.com>
> > Subject: assoc_array: discard shortcut when collapsing a leaf-only node
> > Date: Fri, 25 Sep 2026 17:05:48 +0900
> >
> > assoc_array_delete() can collapse a subtree into a node that contains only
> > leaves while retaining the shortcut that led to it. If that node later
> > fills, all_leaves_cluster_together replaces it with another shortcut. The
> > first shortcut then points directly to the second one.
> >
> > assoc_array_apply_edit() publishes this topology and propagates branch
> > counts from the new child node. It skips the inner shortcut, encounters
> > the outer shortcut where it requires a node and triggers the BUG_ON().
> >
> > Linux v7.2 and v6.12.105 are affected. The same root remains at the
> > base-commit below and in every supported stable branch checked down to
> > 5.10. It requires CONFIG_KEYS, but no capability, user namespace or race.
> > A UID/GID 1000 process produced:
> >
> > CONTROL_BEGIN mode=exact uid=1000 gid=1000
> > CONTROL_CapEff: 0000000000000000
> > kernel BUG at lib/assoc_array.c:1388!
> > Oops: invalid opcode: 0000 [#1] SMP KASAN NOPTI
> > CPU: 0 UID: 1000 PID: 154 Comm: exploit
> > RIP: assoc_array_apply_edit+0x4aa/0x690
> > Call Trace:
> > __key_link
> > __key_instantiate_and_link
> > __key_create_or_update
> > __do_sys_add_key
> > Kernel panic - not syncing: Fatal exception
> >
> > When deletion produces a leaf-only node, bypass its preceding shortcut as
> > garbage collection already does. Retire the shortcut and old node
> > together after an RCU grace period; reused leaves keep their references
> > and the deleted leaf is still freed separately.
> >
> > The exact trigger reached the BUG in 3/3 unmodified v7.2 KASAN boots and
> > completed cleanly in 3/3 fixed boots. Fixed v6.12.105 also passed 3/3. A
> > source reproducer is available privately on request.
> >
> > Link: https://lore.kernel.org/20260925080548.2505640-1-4ncienth@gmail.com
> > Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> > Signed-off-by: Daehyeon Ko <4ncienth@gmail.com>
> > Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
> > Reviewed-by: Jarkko Sakkinen <jarkko@kernel.org>
> > Cc: David Howells <dhowells@redhat.com>
> > Cc: <stable@vger.kernel.org>
> > ---
> >
> > lib/assoc_array.c | 36 ++++++++++++++++++++++--------------
> > 1 file changed, 22 insertions(+), 14 deletions(-)
> >
> > --- a/lib/assoc_array.c~assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node
> > +++ a/lib/assoc_array.c
> > @@ -1210,8 +1210,22 @@ found_leaf:
> > goto enomem;
> > edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
> >
> > - new_n0->back_pointer = node->back_pointer;
> > - new_n0->parent_slot = node->parent_slot;
> > + /* A shortcut above a leaf-only node is redundant. Drop it as
> > + * GC does so that a later split can't create two shortcuts in a row.
> > + */
> > + ptr = node->back_pointer;
> > + if (assoc_array_ptr_is_shortcut(ptr)) {
> > + struct assoc_array_shortcut *s =
> > + assoc_array_ptr_to_shortcut(ptr);
> > +
> > + new_n0->back_pointer = s->back_pointer;
> > + new_n0->parent_slot = s->parent_slot;
> > + edit->excised_subtree = ptr;
> > + } else {
> > + new_n0->back_pointer = ptr;
> > + new_n0->parent_slot = node->parent_slot;
> > + edit->excised_subtree = assoc_array_node_to_ptr(node);
> > + }
> > new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
> > edit->adjust_count_on = new_n0;
> >
> > @@ -1225,21 +1239,15 @@ found_leaf:
> > pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
> > BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
> >
> > - if (!node->back_pointer) {
> > + if (!new_n0->back_pointer) {
> > edit->set[1].ptr = &array->root;
> > - } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
> > - BUG();
> > - } else if (assoc_array_ptr_is_node(node->back_pointer)) {
> > - struct assoc_array_node *p =
> > - assoc_array_ptr_to_node(node->back_pointer);
> > - edit->set[1].ptr = &p->slots[node->parent_slot];
> > - } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
> > - struct assoc_array_shortcut *s =
> > - assoc_array_ptr_to_shortcut(node->back_pointer);
> > - edit->set[1].ptr = &s->next_node;
> > + } else {
> > + struct assoc_array_node *p;
> > +
> > + p = assoc_array_ptr_to_node(new_n0->back_pointer);
> > + edit->set[1].ptr = &p->slots[new_n0->parent_slot];
> > }
> > edit->set[1].to = assoc_array_node_to_ptr(new_n0);
> > - edit->excised_subtree = assoc_array_node_to_ptr(node);
> > }
> > }
>
> This causes conflicts with upstream. I suspect with Linus' cleanups part of
>
> commit 666539eecdf4db623f5e3c3e55cf9f2dfad24aa4 (origin/master, origin/HEAD,
> master, base)
> Merge: 141b164bbe18 bbab563c5131
> Author: Linus Torvalds <torvalds@linux-foundation.org>
> Date: Mon Nov 16 09:35:38 2026 -0800
>
> Merge tag 'assoc-array-fixes-v2'
>
> Clean up assoc_array library code
>
> It's in akpm/mm-hotfixes-unstable, but is this really MM material?
>
> Sounds more like nonmm stuff.
>
> Anyhow, I'll drop this from now from mm-next as I couldn't easily figure out how
> to resolve this (or if it is still required).
I think you're right, thanks.
I temporarily removed the commits from my next mirror branch.
I'll go through this with time and re-push them later.
>
> --
> Cheers,
>
> David
Br, Jarkko
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-11-17 14:17 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-10 6:45 [merged mm-hotfixes-stable] assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch removed from -mm tree Andrew Morton
2026-11-17 13:22 ` David Hildenbrand (Arm)
2026-11-17 14:17 ` Jarkko Sakkinen
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox