[PATCH v3 1/2] maple_tree: fix maple_range_64 crashes in RCU mode

[Dimitris Charisis]

This commit fixes two issues in maple_range_64 nodes under RCU mode. A
maple_range_64 node repurposes its last slot to hold metadata whenever
the node is not full. Both issues arise from mishandling that last slot.

More specifically the two fixes are:

1. Remove mt_clear_meta() function. mt_clear_meta() decides whether the
   last slot of a maple_range_64 node holds a child pointer or a
   struct maple_metadata with the check

        if (unlikely((mte_to_node(next) &&
                      mte_node_type(next))))
                return; /* no metadata, could be node */

   The check expects the pointer to be encoded.  But the only callsite
   of mt_clear_meta() is mt_destroy_walk() on the RCU destroy path, and
   by the time it runs, mte_dead_leaves() has overwritten every slot on
   a full node with a raw pointer, stripping the type information. Thus,
   the check above never returns early for a full node as it should. It
   falls through and then:
           meta->gap = 0;
           meta->end = 0;
   zeroes two bytes of a valid child pointer. Later, mt_free_walk()
   dereferences the corrupted pointer.

  Fix this by removing mt_clear_meta() along with its only callsite.
  mt_clear_meta() is only called for the root of each sub-tree destroyed
  under RCU. Descendant nodes retain their metadata until they are
  freed. RCU readers may use the metadata while traversing a node, but
  do not use cleared metadata to detect that a node has been removed.
  They detect a dead node via ma_dead_node().

2. Fix invalid memory access in mt_free_walk().  mt_free_walk() descends
   to the left-most unvisited "parent-of-a-leaf" node by checking the
   condition:

        if ((offset < mt_slots[type]) &&
            rcu_dereference_protected(slots[offset],
                                      lock_is_held(&rcu_callback_map)))
                slots = mte_dead_walk(&enode, offset);

   On a maple_range_64 node with MAPLE_RANGE64_SLOTS-1 children *all*
   slots are non-NULL. The first MAPLE_RANGE64_SLOTS-1  hold valid
   pointers to child nodes, and the last slot contains metadata. The
   above check therefore passes for all offsets, and mte_dead_walk()
   dereferences the metadata as if it were a node.

   To trigger this, a node at least two levels above the leaves has to
   have exactly MAPLE_RANGE64_SLOTS-1 valid pointers to other nodes.
   maple_arange_64 nodes cannot hit this since they store the metadata
   in a separate field.

   Fix this by bounding the descent with slot_len which holds the number
   of children of a dead node.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Fixes: 2e5b4921f8ef ("maple_tree: fix freeing of nodes in rcu mode")
Signed-off-by: Dimitris Charisis <dchar at cslab.ece.ntua.gr>
---
 lib/maple_tree.c | 43 +------------------------------------------
 1 file changed, 1 insertion(+), 42 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1aba6cced71307245cbbca26986e14e74b35a14f..0b0036c9f848929a7c9a26650ccd935c44aa1376 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -763,43 +763,6 @@ static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
 	meta->end = end;
 }
 
-/*
- * mt_clear_meta() - clear the metadata information of a node, if it exists
- * @mt: The maple tree
- * @mn: The maple node
- * @type: The maple node type
- */
-static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn,
-				  enum maple_type type)
-{
-	struct maple_metadata *meta;
-	unsigned long *pivots;
-	void __rcu **slots;
-	void *next;
-
-	switch (type) {
-	case maple_range_64:
-		pivots = mn->mr64.pivot;
-		if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) {
-			slots = mn->mr64.slot;
-			next = mt_slot_locked(mt, slots,
-					      MAPLE_RANGE64_SLOTS - 1);
-			if (unlikely((mte_to_node(next) &&
-				      mte_node_type(next))))
-				return; /* no metadata, could be node */
-		}
-		fallthrough;
-	case maple_arange_64:
-		meta = ma_meta(mn, type);
-		break;
-	default:
-		return;
-	}
-
-	meta->gap = 0;
-	meta->end = 0;
-}
-
 /*
  * ma_meta_end() - Get the data end of a node from the metadata
  * @mn: The maple node
@@ -4789,9 +4752,7 @@ 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)))
+		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));
@@ -4885,8 +4846,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);
 }
 
 /*

-- 
2.47.3