[PATCH 0/3] maple_tree: fix two bugs when freeing RCU-mode trees

[PATCH 0/3] maple_tree: fix two bugs when freeing RCU-mode trees

[Florian Schmaus]

Destroying a non-allocation maple tree with MT_FLAGS_USE_RCU defers freeing
its nodes to mt_free_walk(). There are two independent bugs on that path,
both caused by the metadata that a maple_range_64 node may keep in its last
slot:

 1. mt_free_walk() takes the metadata of a node with 15 children for a
    child node and dereferences it.
    Reproduced with: 2768 ranges / height 4

 2. mt_destroy_walk() takes the last child of a full node for metadata
    and corrupts its pointer, so mt_free_walk() frees a bogus address.
    Reproduced with: 120 ranges / a full root

Patch 3 adds a regression test for both cases to lib/test_maple_tree.c.

Testing: on x86_64, in the userspace test harness
(tools/testing/radix-tree) built with ASan and UBSan, the new test fails at
120 ranges without patch 2 and at 2768 ranges without patch 1. With the
whole series, all maple tree tests pass. The full suite also passes on
s390x (big-endian) under qemu-user.

No in-tree user is known to hit either bug, because all in-tree RCU-mode
trees (mm_mt, sparse_irqs) are allocation trees, whose nodes keep the
metadata in a separate field.

We identified these issues on a CHERI [1, 2] system, which provides
fine-grained memory protection through architectural capabilities. Our
CHERI Linux port uses plain RCU-mode maple trees for CHERI-based temporal
safety via revocation and destroys them after every revocation sweep, which
exercises a path that in-tree users do not reach. Unlike traditional
MMU-based protection, under which zeroing the low bytes of a node pointer
silently yields another "valid" address, CHERI invalidated the damaged
pointer: the partial write cleared its capability tag. Consequently, the
kernel trapped at the next use of that pointer, and the bounds of the
faulting capability, exactly one maple node, pointed to a corrupted maple
node pointer. We then reproduced both bugs without CHERI on x86 with the
userspace test harness under ASan.

1: https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
2: https://codasip.com/solutions/riscv-processor-safety-security/cheri/

Signed-off-by: Florian Schmaus <florian.schmaus@codasip.com>
---
Florian Schmaus (3):
      maple_tree: do not descend into metadata in mt_free_walk()
      maple_tree: do not clear the metadata of a full dead node
      maple_tree: add a test for destroying RCU-mode trees

 lib/maple_tree.c      | 19 +++++++++++++++----
 lib/test_maple_tree.c | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 47 insertions(+), 4 deletions(-)
---
base-commit: 4056b3c9d3c92ea45955641dbafeb9b960e146ef
change-id: 20261015-maple-tree-fix-slab-corruption-d1f098521d15

Best regards,
--  
Florian Schmaus <florian.schmaus@codasip.com>

[PATCH 1/3] maple_tree: do not descend into metadata in mt_free_walk()

[Florian Schmaus]

mt_free_walk() frees the nodes of a dead RCU-mode tree from an RCU
callback. After freeing the children of a node, it continues with the
next slot of the parent if that slot is non-NULL. A maple_range_64 node
with fewer children than slots keeps its metadata in the last slot. If
the parent has exactly MAPLE_RANGE64_SLOTS - 1 children, the walk takes
the metadata (end = 14, i.e. 0xe) for a node and dereferences it.

mt_destroy_walk() already skips such slots by checking for a node pointer,
and mt_clear_meta() clears the metadata of the start node only. The bug is
therefore hit by the walk over a parent other than the start node, which
needs a tree of height 4 or more. Storing 2768 disjoint ranges into an
MT_FLAGS_USE_RCU tree and then calling mtree_destroy() and rcu_barrier()
in the userspace test harness gives:

  lib/maple_tree.c:4755:27: runtime error: member access within
  misaligned address 0x00000000000e for type 'struct maple_node'

Fix this by only descending into the slots that hold children.
mt_destroy_walk() has already stored the number of children of each dead
node in slot_len, so compare the offset against the slot_len of the
parent. The slot value itself cannot tell a child from metadata here:
mte_dead_leaves() has replaced the children with plain node pointers,
whose low byte is zero, and on big-endian the metadata is stored in the
high bytes of the slot, so its low byte is zero as well.

As the check no longer loads the slot, the rcu_dereference_protected()
with lock_is_held(&rcu_callback_map) is no longer needed there. slot_len
is a plain field that mt_destroy_walk() sets before call_rcu(), and
mt_free_walk() already reads it without annotation elsewhere. When the
walk descends, mte_dead_walk() still loads the slot with
rcu_dereference_protected().

Allocation trees, such as mm_mt, are not affected because their
maple_arange_64 nodes keep the metadata in a separate field.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Florian Schmaus <florian.schmaus@codasip.com>
---
 lib/maple_tree.c | 9 ++++++---
 1 file changed, 6 insertions(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1aba6cced713..e5c0eeda0bd7 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4789,9 +4789,12 @@ static void mt_free_walk(struct rcu_head *head)
 
 		type = mte_node_type(enode);
 		slots = ma_slots(mte_to_node(enode), type);
-		if ((offset < mt_slots[type]) &&
-		    rcu_dereference_protected(slots[offset],
-					      lock_is_held(&rcu_callback_map)))
+		/*
+		 * Only the first slot_len slots of the parent hold children.
+		 * A maple_range_64 node with fewer children keeps its metadata
+		 * in the last slot, which must not be taken for a node.
+		 */
+		if (offset < mte_to_node(enode)->slot_len)
 			slots = mte_dead_walk(&enode, offset);
 		node = mte_to_node(enode);
 	} while ((node != start) || (node->slot_len < offset));

-- 
2.55.0

[PATCH 2/3] maple_tree: do not clear the metadata of a full dead node

[Florian Schmaus]

When an RCU-mode tree that is not an allocation tree is destroyed, or a
subtree of such a tree is replaced by a spanning store, mt_destroy_walk()
runs with free == false and the nodes are freed later by mt_free_walk().
mte_dead_leaves() replaces the slots of each dead node with plain node
pointers, which lack the type bits of an encoded node. Afterwards,
mt_clear_meta() clears the metadata of the start node.

A maple_range_64 node keeps its metadata in the last slot, unless that
slot holds a child. mt_clear_meta() recognizes a child only by its type
bits. For a full node (16 children), it therefore takes the last child
for metadata and zeroes two bytes of the pointer (the low bytes on
little-endian). mt_free_walk() then frees the resulting address, which
usually points into another node, live or already freed, and corrupts
the slab.

Storing 120 disjoint ranges into an MT_FLAGS_USE_RCU tree (a full root
of height 2) and then calling mtree_destroy() and rcu_barrier() in the
userspace test harness under ASan gives:

  ERROR: AddressSanitizer: heap-buffer-overflow on address 0x7c64552f0000
  WRITE of size 256 at 0x7c64552f0000 thread T1
    #3 kmem_cache_free_bulk ../shared/linux.c:149
    #4 mt_free_bulk ../shared/../../../lib/maple_tree.c:144
    #5 mt_free_walk ../shared/../../../lib/maple_tree.c:4784

A full maple_range_64 node has no metadata, so do not clear it.

Allocation trees, such as mm_mt, are not affected because their
maple_arange_64 nodes keep the metadata in a separate field.

Fixes: 2e5b4921f8ef ("maple_tree: fix freeing of nodes in rcu mode")
Signed-off-by: Florian Schmaus <florian.schmaus@codasip.com>
---
 lib/maple_tree.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e5c0eeda0bd7..05546aa53871 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4886,9 +4886,17 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
 		mt_free_bulk(node->slot_len, slots);
 
 free_leaf:
+	/*
+	 * A full maple_range_64 node has no metadata: its last slot holds a
+	 * child.  mt_clear_meta() cannot tell, because mte_dead_leaves() has
+	 * stripped the type bits from the child pointers, and would zero part
+	 * of that child pointer.  slot_len, the child count returned by
+	 * mte_dead_leaves(), says whether the node is full.
+	 */
 	if (free)
 		kfree(node);
-	else
+	else if (node->type != maple_range_64 ||
+		 node->slot_len < MAPLE_RANGE64_SLOTS)
 		mt_clear_meta(mt, node, node->type);
 }
 

-- 
2.55.0

[PATCH 3/3] maple_tree: add a test for destroying RCU-mode trees

[Florian Schmaus]

Destroying an RCU-mode tree that is not an allocation tree defers freeing
its nodes to mt_free_walk(). This path had two bugs, both caused by the
metadata that a maple_range_64 node may keep in its last slot:

- mt_destroy_walk() took the last child of a full node for metadata and
  corrupted it.
- mt_free_walk() took the metadata of a node with 15 children for a child
  and dereferenced it.

Add check_rcu_destroy(), which builds RCU-mode trees with 120 ranges
(a full root) and 2768 ranges (height 4, where a non-root internal node
has 15 children), then destroys them and waits for the RCU callbacks.

The second case crashes without its fix. The first one corrupts memory
silently and needs KASAN, or ASan in the userspace test harness, to be
detected.

Signed-off-by: Florian Schmaus <florian.schmaus@codasip.com>
---
 lib/test_maple_tree.c | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index b9367c61e8b5..aea62269810b 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -286,6 +286,36 @@ static noinline void __init check_seq(struct maple_tree *mt, unsigned long max,
 #endif
 }
 
+/*
+ * Destroy RCU-mode trees that are not allocation trees, so that the nodes are
+ * freed by mt_free_walk() from an RCU callback.  With the ranges and gaps
+ * stored below, the sizes give the tree shapes (on 64-bit) that used to break
+ * this path:
+ *
+ * - 120 ranges: a full root.  mt_destroy_walk() took its last child for
+ *   metadata and zeroed part of the child pointer.
+ * - 2768 ranges: height 4, and a non-root internal node has 15 children.
+ *   mt_free_walk() took the metadata in its last slot for a child.
+ *
+ * Without its fix, the first case corrupts memory silently and is only
+ * detected with KASAN, or with ASan in the userspace test harness.
+ */
+static noinline void __init check_rcu_destroy(struct maple_tree *mt)
+{
+	unsigned long sizes[] = { 120, 2768 };
+	unsigned long i, j;
+
+	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
+		mt_init_flags(mt, MT_FLAGS_USE_RCU);
+		for (j = 0; j < sizes[i]; j++)
+			MT_BUG_ON(mt, mtree_store_range(mt, j * 10, j * 10 + 5,
+							xa_mk_value(j),
+							GFP_KERNEL));
+		mtree_destroy(mt);
+		rcu_barrier();
+	}
+}
+
 static noinline void __init check_lb_not_empty(struct maple_tree *mt)
 {
 	unsigned long i, j;
@@ -3804,6 +3834,8 @@ static int __init maple_tree_seed(void)
 	check_mas_store_gfp(&tree);
 	mtree_destroy(&tree);
 
+	check_rcu_destroy(&tree);
+
 	/* Test ranges (store and insert) */
 	mt_init_flags(&tree, 0);
 	check_ranges(&tree);

-- 
2.55.0