[PATCH 2/2] maple_tree: fix invalid memory access in mt_free_walk()

[Dimitris Charisis]

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

A maple_range_64 node has MAPLE_RANGE64_SLOTS slots. When it's not full,
the last slot carries a struct maple_metadata holding the offset of the
last valid slot. So on a 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")
Signed-off-by: Dimitris Charisis <dchar@xxxxxxxxxxxxxxxxx>
---
 lib/maple_tree.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e86eee43aa0ada6963995cd74495d9344f6ccd06..0b0036c9f848929a7c9a26650ccd935c44aa1376 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4752,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));

-- 
2.47.3