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
next 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®