[RESEND Patch v2 0/3] maple_tree: Fix the replacement of a root leaf node

[RESEND Patch v2 0/3] maple_tree: Fix the replacement of a root leaf node

[Wei Yang]

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.

Patch 1 fixes this.

When adding a test case, I found we always get the new value even we leave the
old root node not dead. It turns out we always re-walk the tree in mas_walk().
It looks like a typo on the status check of mas_walk().

Patch 2 fixes this.

Patch 3 add a test case to assert retrieving new value when overwriting the
whole range to a tree with only root node.

Wei Yang (3):
  maple_tree: Fix mt_destroy_walk() on root leaf node
  maple_tree: restart walk on correct status
  maple_tree: assert retrieving new value on a tree containing just a
    leaf node

 lib/maple_tree.c                 |  3 ++-
 tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
 2 files changed, 26 insertions(+), 1 deletion(-)

-- 
2.34.1

[RESEND Patch v2 1/3] maple_tree: Fix mt_destroy_walk() on root leaf node

[Wei Yang]

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

Re: [RESEND Patch v2 1/3] maple_tree: Fix mt_destroy_walk() on root leaf node

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250407 19:14]:
> 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>

Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

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

[RESEND Patch v2 2/3] maple_tree: restart walk on correct status

[Wei Yang]

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

[RESEND Patch v2 3/3] maple_tree: assert retrieving new value on a tree containing just a leaf node

[Wei Yang]

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

Re: [RESEND Patch v2 3/3] maple_tree: assert retrieving new value on a tree containing just a leaf node

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250407 19:14]:
> 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>

Reviewed-by: 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
>