All of lore.kernel.org
 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: 4+ 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]
2026-11-17 17:06     ` Andrew Morton

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 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.