* [Patch v2 1/3] maple_tree: Fix mt_destroy_walk() on root leaf node
2025-03-05 0:46 [Patch v2 0/3] maple_tree: Fix the replacement of a root leaf node Wei Yang
@ 2025-03-05 0:46 ` Wei Yang
2025-03-05 0:46 ` [Patch v2 2/3] maple_tree: restart walk on correct status Wei Yang
2025-03-05 0:46 ` [Patch v2 3/3] maple_tree: assert retrieving new value on a tree containing just a leaf node Wei Yang
2 siblings, 0 replies; 4+ messages in thread
From: Wei Yang @ 2025-03-05 0:46 UTC (permalink / raw)
To: akpm, Liam.Howlett
Cc: maple-tree, linux-mm, Wei Yang, Liam R . Howlett, stable
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")
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
Cc: <stable@vger.kernel.org>
---
v2:
* move the operation into mt_destroy_walk()
* adjust the title accordingly
---
lib/maple_tree.c | 1 +
1 file changed, 1 insertion(+)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4bd5a5be1440..0696e8d1c4e9 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5284,6 +5284,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;
}
--
2.34.1
^ permalink raw reply [flat|nested] 4+ messages in thread* [Patch v2 2/3] maple_tree: restart walk on correct status
2025-03-05 0:46 [Patch v2 0/3] maple_tree: Fix the replacement of a root leaf node Wei Yang
2025-03-05 0:46 ` [Patch v2 1/3] maple_tree: Fix mt_destroy_walk() on " Wei Yang
@ 2025-03-05 0:46 ` Wei Yang
2025-03-05 0:46 ` [Patch v2 3/3] maple_tree: assert retrieving new value on a tree containing just a leaf node Wei Yang
2 siblings, 0 replies; 4+ messages in thread
From: Wei Yang @ 2025-03-05 0:46 UTC (permalink / raw)
To: akpm, Liam.Howlett
Cc: maple-tree, linux-mm, Wei Yang, Liam R . Howlett, stable
Commit a8091f039c1e ("maple_tree: add MAS_UNDERFLOW and MAS_OVERFLOW
states") adds more status during maple tree walk. But it introduce a
typo on the status check during walk.
It expects to mean neither active nor start, we would restart the walk,
while current code means we would always restart the walk.
Fixes: a8091f039c1e ("maple_tree: add MAS_UNDERFLOW and MAS_OVERFLOW states")
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
CC: <stable@vger.kernel.org>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
lib/maple_tree.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0696e8d1c4e9..81970b3a6af7 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4895,7 +4895,7 @@ void *mas_walk(struct ma_state *mas)
{
void *entry;
- if (!mas_is_active(mas) || !mas_is_start(mas))
+ if (!mas_is_active(mas) && !mas_is_start(mas))
mas->status = ma_start;
retry:
entry = mas_state_walk(mas);
--
2.34.1
^ permalink raw reply [flat|nested] 4+ messages in thread* [Patch v2 3/3] maple_tree: assert retrieving new value on a tree containing just a leaf node
2025-03-05 0:46 [Patch v2 0/3] maple_tree: Fix the replacement of a root leaf node Wei Yang
2025-03-05 0:46 ` [Patch v2 1/3] maple_tree: Fix mt_destroy_walk() on " Wei Yang
2025-03-05 0:46 ` [Patch v2 2/3] maple_tree: restart walk on correct status Wei Yang
@ 2025-03-05 0:46 ` Wei Yang
2 siblings, 0 replies; 4+ messages in thread
From: Wei Yang @ 2025-03-05 0:46 UTC (permalink / raw)
To: akpm, Liam.Howlett; +Cc: maple-tree, linux-mm, Wei Yang, Liam R . Howlett
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.
Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
v2: adjust the changelog according to Liam's suggestion
---
tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
1 file changed, 24 insertions(+)
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index bc30050227fd..1e293e4d856d 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35256,6 +35256,30 @@ 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 */
+ mas_lock(&mas_writer);
+ mas_set_range(&mas_writer, 0, ULONG_MAX);
+ mas_store_gfp(&mas_writer, NULL, GFP_KERNEL);
+ mas_set_range(&mas_writer, 0, 0);
+ 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;
+ mas_set_range(&mas_reader, target, target);
+ rcu_read_lock();
+ MT_BUG_ON(mt, mas_walk(&mas_reader) != xa_mk_value(target/10));
+
+ /* 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();
}
--
2.34.1
^ permalink raw reply [flat|nested] 4+ messages in thread