Linux kernel -stable discussions
 help / color / mirror / Atom feed
From: Jarkko Sakkinen <jarkko@kernel.org>
To: "David Hildenbrand (Arm)" <david@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>,
	mm-commits@vger.kernel.org, stable@vger.kernel.org,
	dhowells@redhat.com, 4ncienth@gmail.com
Subject: Re: [merged mm-hotfixes-stable] assoc_array-discard-shortcut-when-collapsing-a-leaf-only-node.patch removed from -mm tree
Date: Tue, 17 Nov 2026 16:17:23 +0200	[thread overview]
Message-ID: <avxh82yWCs_bQq_w@kernel.org> (raw)
In-Reply-To: <86f9796a-2d2f-4e5a-875c-d2714bd76c58@kernel.org>

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

      reply	other threads:[~2026-11-17 14:17 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
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 message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=avxh82yWCs_bQq_w@kernel.org \
    --to=jarkko@kernel.org \
    --cc=4ncienth@gmail.com \
    --cc=akpm@linux-foundation.org \
    --cc=david@kernel.org \
    --cc=dhowells@redhat.com \
    --cc=mm-commits@vger.kernel.org \
    --cc=stable@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox