Skip to contentSkip to conversation

maple_tree: Fix mt_destroy_walk() on root leaf node

PATCH In review Liam R. Howlett 2 participants 3 messages Jun 24, 2025 – Jun 25, 2025

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

PATCH 1/2 maple_tree: Fix mt_destroy_walk() on root leaf node

From: Wei Yang <[email protected]>

On destroy, we should set each node dead. But current code miss this when the maple tree has only the root node.

The reason is mt_destroy_walk() leverage mte_destroy_descend() to set node dead, but this is skipped since the only root node is a leaf.

Fixes this by setting the node dead if it is a leaf.

Fixes 54a611b60590 ("Maple Tree: add new data structure")
CC Liam R. Howlett <[email protected]>
---
 lib/maple_tree.c | 1 +
 1 file changed, 1 insertion(+)
lib/maple_tree.c +1 -0
index 6b0fc6ebbe363..85d17d943753d 100644
@@ -5319,6 +5319,7 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
 	struct maple_enode *start;
 
 	if (mte_is_leaf(enode)) {
+		mte_set_node_dead(enode);
 		node->type = mte_node_type(enode);
 		goto free_leaf;
 	}
Signature · 1 line
2.47.2
#1 lore raw

PATCH 2/2 maple_tree: assert retrieving new value on a tree containing just a leaf node

From: Wei Yang <[email protected]>

Original code may not get the new value after overwriting the whole range on a maple tree containing just a leaf node. The reason is we didn't set the only root node dead during destroy.

Add a test case to ensure the new value is returned when overwriting a tree containing just a leaf node.

---
 tools/testing/radix-tree/maple.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
tools/testing/radix-tree/maple.c +26 -0
index 172700fb7784d..2f6dcdc7a38f6 100644
@@ -35257,6 +35257,32 @@ static noinline void __init check_rcu_simulated(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_prev(&mas_reader, 0) != xa_mk_value(val));
 	rcu_read_unlock();
 
+	/* Clear out tree & create one with only root node */
+	mtree_destroy(mt);
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_USE_RCU);
+	mas_pause(&mas_writer);
+	mas_lock(&mas_writer);
+	for (i = 0; i <= 5; i++) {
+		mas_writer.index = i * 10;
+		mas_writer.last = i * 10 + 5;
+		mas_store_gfp(&mas_writer, xa_mk_value(i), GFP_KERNEL);
+	}
+	mas_unlock(&mas_writer);
+	target = 10;
+	val = 20;
+	mas_set(&mas_reader, target);
+	rcu_read_lock();
+	MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
+	MT_BUG_ON(mt, mte_is_leaf(mas_reader.node) != true);
+
+	/* Overwrite the whole range */
+	mas_lock(&mas_writer);
+	mas_set_range(&mas_writer, 0, ULONG_MAX);
+	mas_store_gfp(&mas_writer, xa_mk_value(val), GFP_KERNEL);
+	mas_unlock(&mas_writer);
+	MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(val));
+	rcu_read_unlock();
+
 	rcu_unregister_thread();
 }
 
Signature · 1 line
2.47.2
Reviewed-by on v1 1/2
#2 lore raw
In reply to Liam R. Howlett
Quoted 25 lines · Liam R. Howlett

From: Wei Yang <[email protected]>

On destroy, we should set each node dead. But current code miss this when the maple tree has only the root node.

The reason is mt_destroy_walk() leverage mte_destroy_descend() to set node dead, but this is skipped since the only root node is a leaf.

Fixes this by setting the node dead if it is a leaf.

Fixes 54a611b60590 ("Maple Tree: add new data structure")
CC Liam R. Howlett <[email protected]>
---
  lib/maple_tree.c | 1 +
  1 file changed, 1 insertion(+)
lib/maple_tree.c +0 -0
index 6b0fc6ebbe363..85d17d943753d 100644

lib/maple_tree.c static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, · line 5325

Quoted 7 lines
lib/maple_tree.c +1 -0
@@ -5319,6 +5319,7 @@ static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
  	struct maple_enode *start;
 
  	if (mte_is_leaf(enode)) {
+		mte_set_node_dead(enode);
  		node->type = mte_node_type(enode);
  		goto free_leaf;
  	}

FWIW I have been reading the maple tree code and this looks good to me.