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