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