[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 at 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