* [PATCH v1 0/2] maple_tree: fix RCU-mode destroy of trees without MT_FLAGS_ALLOC_RANGE
@ 2026-10-12 23:59 Nickolai Zeldovich
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
0 siblings, 2 replies; 3+ messages in thread
From: Nickolai Zeldovich @ 2026-10-12 23:59 UTC (permalink / raw)
To: Liam R. Howlett, Andrew Morton
Cc: Alice Ryhl, Andrew Ballance, Suren Baghdasaryan, maple-tree,
linux-mm, linux-kernel, stable, Nickolai Zeldovich
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH v1 1/2] maple_tree: restore per-node metadata clearing in mte_destroy_descend()
2026-10-12 23:59 [PATCH v1 0/2] maple_tree: fix RCU-mode destroy of trees without MT_FLAGS_ALLOC_RANGE Nickolai Zeldovich
@ 2026-10-12 23:59 ` Nickolai Zeldovich
2026-10-12 23:59 ` [PATCH v1 2/2] maple_tree: remove the late metadata clearing from mt_destroy_walk() Nickolai Zeldovich
1 sibling, 0 replies; 3+ messages in thread
From: Nickolai Zeldovich @ 2026-10-12 23:59 UTC (permalink / raw)
To: Liam R. Howlett, Andrew Morton
Cc: Alice Ryhl, Andrew Ballance, Suren Baghdasaryan, maple-tree,
linux-mm, linux-kernel, stable, Nickolai Zeldovich
The internal nodes of a tree without MT_FLAGS_ALLOC_RANGE are
maple_range_64 nodes, which keep their metadata (end, gap) in the bytes
of the last slot when that slot is unused. A node with 15 children
therefore holds the metadata {end = 14, gap = 0} in slot 15.
When such a tree is in RCU mode, mte_destroy_walk() only marks the nodes
dead with mt_destroy_walk(..., false) and leaves the freeing to the RCU
callback mt_free_walk(). After freeing the children of a node,
mt_free_walk() climbs to the parent and walks down the parent's next
slot if that slot is not NULL:
if ((offset < mt_slots[type]) &&
rcu_dereference_protected(slots[offset], ...))
slots = mte_dead_walk(&enode, offset);
In a 15-child parent it takes the metadata in slot 15 for a 16th child,
and mte_dead_walk() reads the node type at address 0x0e + 0x24. This
runs from the RCU softirq, so the kernel oopses on the zero page and
panics ("Fatal exception in interrupt"); the subtrees not yet freed are
leaked. It takes a 15-child node, other than the one the walk starts
from, at least two levels above the leaves, so a tree of height 4 or
more destroyed by mtree_destroy(), or a large subtree discarded by a
store (mas_new_root(), mas_mat_destroy()). No race is needed.
Commit 2e5b4921f8ef ("maple_tree: fix freeing of nodes in rcu mode")
fixed this by clearing the metadata of each node as
mte_destroy_descend() marks it dead, while the slots still hold encoded
pointers and mt_clear_meta() can tell metadata from a 16th child.
Commit 790e1fa86b34 ("maple_tree: add RCU lock checking to rcu callback
functions"), from the same series, converted mte_destroy_descend() from
the maple state to the tree and dropped that call, leaving only the
clearing of the start node at the end of mt_destroy_walk(). Since then
only the start node is covered.
Put the call back where the first of these commits had it, after the
node is marked dead. The RCU lock checking added by the second one is
kept.
No in-tree user hits this today: every tree used in RCU mode (the VMA
tree, sparse_irqs, the interval tree test, the DAMON KUnit test) has
MT_FLAGS_ALLOC_RANGE, whose maple_arange_64 nodes keep the metadata
outside the slots. The API allows RCU mode for any tree, though
(mt_init_flags(mt, MT_FLAGS_USE_RCU) or mt_set_in_rcu()).
The new test destroys an RCU-mode tree of 2768 ranges without
MT_FLAGS_ALLOC_RANGE, which on 64-bit has such a node. Without this
patch the userspace test suite (tools/testing/radix-tree/maple) crashes
in mte_dead_walk() called from mt_free_walk(), and an x86_64 or riscv64
kernel with CONFIG_TEST_MAPLE_TREE=y oopses at boot; with it both pass.
Found while formally verifying mt_free_walk() against the kernel binary.
Fixes: 790e1fa86b34 ("maple_tree: add RCU lock checking to rcu callback functions")
Cc: stable@vger.kernel.org # 6.1.x
Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
Notes:
Outside the test suite, the reproducer links lib/maple_tree.c into
tools/testing/radix-tree and stores [10i, 10i+5] ranges into a tree
created with only MT_FLAGS_USE_RCU until a node of the bad shape exists:
a maple_range_64 node below the root, two levels above the leaves, whose
slot 15 holds the metadata word 0xe. The first one appears after 2768
stores (height 4), which is where the count in the test comes from; the
count is specific to 64-bit, and on 32-bit the test is harmless. On
master, mtree_destroy() plus rcu_barrier() on that tree gives UBSan
"member access within misaligned address 0x00000000000e" in
mte_dead_walk() and a SIGSEGV in the RCU callback thread
(mt_free_walk() -> mte_dead_walk(offset = 15)); with this patch it
passes. With the new test but without the fix, a riscv64 defconfig kernel
with CONFIG_TEST_MAPLE_TREE=y oopses during boot with "Unable to handle
kernel NULL pointer dereference at virtual address 0000000000000032" in
mt_free_walk() (mte_dead_walk() inlined) and panics with "Fatal
exception in interrupt"; an x86_64 KASAN kernel reports a null-ptr-deref
in the range 0x30-0x37 at the same place.
A leak check that destroys trees of 1 to 5000 ranges with each
combination of MT_FLAGS_ALLOC_RANGE and MT_FLAGS_USE_RCU shows the same
allocation count before and after the series.
Another way to fix this is to have mt_free_walk() compare the offset
with the parent's slot_len, which mte_dead_leaves() sets on every dead
internal node, instead of testing the slot for NULL. I went with
restoring the clearing from 2e5b4921f8ef because the callback was
written around it and this keeps the callback unchanged; I can send the
other version if you prefer it.
lib/maple_tree.c | 1 +
lib/test_maple_tree.c | 17 +++++++++++++++++
2 files changed, 18 insertions(+)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1aba6cced713..fd7c3d20394c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4823,6 +4823,7 @@ static inline void __rcu **mte_destroy_descend(struct maple_enode **enode,
mte_set_node_dead(*enode);
node->type = type;
+ mt_clear_meta(mt, node, type);
node->piv_parent = prev;
node->parent_slot = offset;
offset = next_offset;
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index b9367c61e8b5..5d940bcfae34 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -3710,6 +3710,20 @@ static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
MT_BUG_ON(mt, ret != 1);
}
+/* Destroy a non-alloc tree of @nr ranges in RCU mode. */
+static noinline void __init check_rcu_destroy(struct maple_tree *mt,
+ unsigned long nr)
+{
+ unsigned long i;
+
+ mt_init_flags(mt, MT_FLAGS_USE_RCU);
+ for (i = 0; i < nr; i++)
+ MT_BUG_ON(mt, mtree_store_range(mt, i * 10, i * 10 + 5,
+ xa_mk_value(i), GFP_KERNEL));
+ mtree_destroy(mt);
+ rcu_barrier();
+}
+
static DEFINE_MTREE(tree);
static int __init maple_tree_seed(void)
{
@@ -3999,6 +4013,9 @@ static int __init maple_tree_seed(void)
alloc_cyclic_testing(&tree);
mtree_destroy(&tree);
+ /* 64-bit: a 15-child non-root node two levels above the leaves */
+ check_rcu_destroy(&tree, 2768);
+
#if defined(BENCH)
skip:
--
2.53.0
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH v1 2/2] maple_tree: remove the late metadata clearing from mt_destroy_walk()
2026-10-12 23:59 [PATCH v1 0/2] maple_tree: fix RCU-mode destroy of trees without MT_FLAGS_ALLOC_RANGE Nickolai Zeldovich
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 ` Nickolai Zeldovich
1 sibling, 0 replies; 3+ messages in thread
From: Nickolai Zeldovich @ 2026-10-12 23:59 UTC (permalink / raw)
To: Liam R. Howlett, Andrew Morton
Cc: Alice Ryhl, Andrew Ballance, Suren Baghdasaryan, maple-tree,
linux-mm, linux-kernel, stable, Nickolai Zeldovich
At the end of mt_destroy_walk(..., false), mt_clear_meta() clears the
metadata of the node the walk started from. By then mte_dead_leaves()
has replaced each child pointer in that node with the plain node
address, without the type bits. mt_clear_meta() decides whether slot 15
of a maple_range_64 node holds a child or metadata by looking for an
encoded node there, so for a node with 16 children it decides wrongly
and writes end = 0, gap = 0 over the first two bytes of the 16th child
pointer. On little-endian that clears bits 8-15 of the address (bits
0-7 are already zero, nodes being 256-byte aligned); on big-endian it
clears the top 16 bits.
mt_free_walk() then frees, or walks down, the corrupted address. On
little-endian that is a 256-byte aligned address up to 64KiB below the
real child: usually some other maple node, free or in use, possibly in
another tree, so the result is a double free or the freeing of a live
node, and the real child is leaked. It takes a tree without
MT_FLAGS_ALLOC_RANGE in RCU mode whose destroy starts at a full node:
any such tree whose root has 16 children, for example a tree of 127
ranges on 64-bit, when it is destroyed. No race is needed.
The clearing was added by commit 2e5b4921f8ef ("maple_tree: fix freeing
of nodes in rcu mode") together with the clearing of every node in
mte_destroy_descend(), which also covers the start node while its slots
are still encoded. With the previous patch restoring that, the late
call has nothing left to do except the damage above, so remove it. For
a leaf start node it was a no-op.
This depends on the previous patch: without it, nothing clears the
metadata of the start node and mt_free_walk() could take it for a child.
As with the previous patch, no in-tree user hits this today, since all
trees used in RCU mode have MT_FLAGS_ALLOC_RANGE, but the API allows it.
The new test destroys an RCU-mode tree of 127 ranges without
MT_FLAGS_ALLOC_RANGE, whose root is full on 64-bit. Without this patch
AddressSanitizer in the userspace test suite reports the bad free from
mt_free_walk(), as does KASAN in an x86_64 kernel with
CONFIG_TEST_MAPLE_TREE=y; with it both pass.
Found while formally verifying mt_destroy_walk() against the kernel
binary.
Fixes: 2e5b4921f8ef ("maple_tree: fix freeing of nodes in rcu mode")
Cc: stable@vger.kernel.org # 6.1.x
Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
Notes:
With the first patch alone, the reproducer still shows the damage: for
a tree of 120 ranges (root full, height 2), slot 15 of the root reads
...c04000 before mt_destroy_walk(root, false) and ...c00000 after it,
and AddressSanitizer then reports the free of ...c00000 from
mt_free_bulk() in mt_free_walk(). With both patches slot 15 is intact
and the free is clean. The 127 in the test is the largest such tree
before the root splits (64-bit).
If a version without the dependency on the first patch is wanted, for
instance for a separate backport, skipping the call when
node->slot_len == mt_slots[node->type] also fixes this, but the call is
redundant once the first patch is in, so removing it seemed simpler.
Both patches apply unchanged to mm-unstable and linux-next of
2026-10-12.
lib/maple_tree.c | 2 --
lib/test_maple_tree.c | 2 ++
2 files changed, 2 insertions(+), 2 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index fd7c3d20394c..870ab3281051 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4886,8 +4886,6 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
free_leaf:
if (free)
kfree(node);
- else
- mt_clear_meta(mt, node, node->type);
}
/*
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 5d940bcfae34..9d25b31e9b3c 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -4015,6 +4015,8 @@ static int __init maple_tree_seed(void)
/* 64-bit: a 15-child non-root node two levels above the leaves */
check_rcu_destroy(&tree, 2768);
+ /* 64-bit: a full root */
+ check_rcu_destroy(&tree, 127);
#if defined(BENCH)
--
2.53.0
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-10-12 23:59 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-10-12 23:59 [PATCH v1 0/2] maple_tree: fix RCU-mode destroy of trees without MT_FLAGS_ALLOC_RANGE Nickolai Zeldovich
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
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®