mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Nickolai Zeldovich <nickolai@csail.mit.edu>
To: "Liam R. Howlett" <liam@infradead.org>,
	Andrew Morton <akpm@linux-foundation.org>
Cc: Alice Ryhl <aliceryhl@google.com>,
	Andrew Ballance <andrewjballance@gmail.com>,
	Suren Baghdasaryan <surenb@google.com>,
	maple-tree@lists.infradead.org, linux-mm@kvack.org,
	linux-kernel@vger.kernel.org, stable@vger.kernel.org,
	Nickolai Zeldovich <nickolai@csail.mit.edu>
Subject: [PATCH v1 0/2] maple_tree: fix RCU-mode destroy of trees without MT_FLAGS_ALLOC_RANGE
Date: Mon, 12 Oct 2026 19:59:16 -0400	[thread overview]
Message-ID: <20261012235918.773421-1-nickolai@csail.mit.edu> (raw)

Destroying a maple tree in RCU mode marks its nodes dead and leaves the
freeing to an RCU callback.  In a tree without MT_FLAGS_ALLOC_RANGE the
internal nodes keep their metadata in the last slot when it is unused,
and that path gets the two cases wrong:

1. mt_free_walk() takes the metadata of a 15-child node for a child and
   dereferences address 0x0e + 0x24 from the RCU softirq: oops, panic.
2. mt_destroy_walk() "clears the metadata" of a full start node after
   its slots were rewritten, which corrupts its last child pointer;
   mt_free_walk() then frees the wrong address (double free or freeing
   a live node) and leaks the real child.

Both come from the v6.3-rc6 RCU fixes: 2e5b4921f8ef cleared the metadata
of every node in mte_destroy_descend() and once more at the end of
mt_destroy_walk(); 790e1fa86b34 dropped the per-node call.  Patch 1
restores it; patch 2 removes the late call, which then only does harm.
Patch 2 depends on patch 1.  Both are deterministic, no race needed.

No in-tree user reaches either today: every tree used in RCU mode has
MT_FLAGS_ALLOC_RANGE.  The API allows RCU mode on any tree, though.

Found while formally verifying the maple tree destroy path against the
kernel binary.

Testing: each patch adds a case to lib/test_maple_tree.c that fails
without the fix (userspace suite: SIGSEGV, AddressSanitizer bad free;
kernel: oops at boot, KASAN report) and passes with it.  The userspace
maple suite passes; x86_64 and riscv defconfig builds with LLVM=1 have
no warnings, W=1 and sparse report nothing new for lib/maple_tree.o and
lib/test_maple_tree.o; x86_64 (also with KASAN) and riscv64 QEMU boots
with CONFIG_TEST_MAPLE_TREE=y pass the maple tree tests.

Nickolai Zeldovich (2):
  maple_tree: restore per-node metadata clearing in
    mte_destroy_descend()
  maple_tree: remove the late metadata clearing from mt_destroy_walk()

 lib/maple_tree.c      |  3 +--
 lib/test_maple_tree.c | 19 +++++++++++++++++++
 2 files changed, 20 insertions(+), 2 deletions(-)


base-commit: 24a19b953e2a3d0ea5a8c4951a0ab8f32720c907
-- 
2.53.0


             reply	other threads:[~2026-10-12 23:59 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-10-12 23:59 Nickolai Zeldovich [this message]
2026-10-12 23:59 ` [PATCH v1 1/2] maple_tree: restore per-node metadata clearing in mte_destroy_descend() Nickolai Zeldovich
2026-10-12 23:59 ` [PATCH v1 2/2] maple_tree: remove the late metadata clearing from mt_destroy_walk() Nickolai Zeldovich

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=20261012235918.773421-1-nickolai@csail.mit.edu \
    --to=nickolai@csail.mit.edu \
    --cc=akpm@linux-foundation.org \
    --cc=aliceryhl@google.com \
    --cc=andrewjballance@gmail.com \
    --cc=liam@infradead.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-mm@kvack.org \
    --cc=maple-tree@lists.infradead.org \
    --cc=stable@vger.kernel.org \
    --cc=surenb@google.com \
    /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

all inboxes | Powered by JetHome®