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