[PATCH 0/3] may miss to set node dead on destroy

[PATCH 0/3] may miss to set node dead on destroy

[Wei Yang]

Per my understanding, 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: may miss to set node dead on destroy
  maple_tree: restart walk on correct status
  maple_tree: assert retrieving new value on a tree with only root node

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

-- 
2.34.1

[PATCH 1/3] maple_tree: may miss to set node dead on destroy

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

This patch fixes this by setting the root dead before mt_destroy_walk().

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>
---
 lib/maple_tree.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 198c14dd3377..d31f0a2858f7 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5347,6 +5347,8 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
 {
 	struct maple_node *node = mte_to_node(enode);
 
+	mte_set_node_dead(enode);
+
 	if (mt_in_rcu(mt)) {
 		mt_destroy_walk(enode, mt, false);
 		call_rcu(&node->rcu, mt_free_walk);
-- 
2.34.1

[PATCH 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>
---
 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 d31f0a2858f7..e64ffa5b9970 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4899,7 +4899,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

[PATCH 3/3] maple_tree: assert retrieving new value on a tree with only root node

[Wei Yang]

Original code may get a stall value when overwriting the whole range on a
maple tree with only root node. The reason is we didn't set the only
root node dead during destroy.

Add a test case to verify this is not recreated.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 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: [PATCH 3/3] maple_tree: assert retrieving new value on a tree with only root node

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
> Original code may get a stall value when overwriting the whole range on a
                          ^^^^^- stale value.  I thought you were saying
			  it was stalling which did not make sense.

> maple tree with only root node. The reason is we didn't set the only
> root node dead during destroy.
> 
> Add a test case to verify this is not recreated.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
> ---
>  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: [PATCH 1/3] maple_tree: may miss to set node dead on destroy

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
> 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.
> 
> This patch fixes this by setting the root dead before mt_destroy_walk().
> 
> 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>
> ---
>  lib/maple_tree.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 198c14dd3377..d31f0a2858f7 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5347,6 +5347,8 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
>  {
>  	struct maple_node *node = mte_to_node(enode);
>  
> +	mte_set_node_dead(enode);
> +

This belongs in mt_destroy_walk().

>  	if (mt_in_rcu(mt)) {
>  		mt_destroy_walk(enode, mt, false);
>  		call_rcu(&node->rcu, mt_free_walk);
> -- 
> 2.34.1
> 

Re: [PATCH 2/3] maple_tree: restart walk on correct status

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
> 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 d31f0a2858f7..e64ffa5b9970 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4899,7 +4899,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
> 

Re: [PATCH 0/3] may miss to set node dead on destroy

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:

The subject of this patch set makes the issue sound much more sever than
it is.  It currently sounds like a memory leak or a UAF, which isn't the
case.

The root node may remain usable for the duration of the rcu window if
it's a leaf node.  The impact is pretty minor - you may see the old data
on calls that happen in the same rcu window - which is the case anyways.

You should also say maple_tree: in the subject since this is
going to linux-mm.  Not a really big deal since each patch in the series
specifies the maple tree.

> Per my understanding, 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: may miss to set node dead on destroy
>   maple_tree: restart walk on correct status
>   maple_tree: assert retrieving new value on a tree with only root node
> 
>  lib/maple_tree.c                 |  4 +++-
>  tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
>  2 files changed, 27 insertions(+), 1 deletion(-)
> 
> -- 
> 2.34.1
> 

Re: [PATCH 1/3] maple_tree: may miss to set node dead on destroy

[Wei Yang]

On Mon, Feb 10, 2025 at 09:19:46AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>> 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.
>> 
>> This patch fixes this by setting the root dead before mt_destroy_walk().
>> 
>> 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>
>> ---
>>  lib/maple_tree.c | 2 ++
>>  1 file changed, 2 insertions(+)
>> 
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 198c14dd3377..d31f0a2858f7 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -5347,6 +5347,8 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
>>  {
>>  	struct maple_node *node = mte_to_node(enode);
>>  
>> +	mte_set_node_dead(enode);
>> +
>
>This belongs in mt_destroy_walk().

You prefer a change like this?

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e64ffa5b9970..79f8632c61a3 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5288,6 +5288,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;
 	}
>
>>  	if (mt_in_rcu(mt)) {
>>  		mt_destroy_walk(enode, mt, false);
>>  		call_rcu(&node->rcu, mt_free_walk);
>> -- 
>> 2.34.1
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH 3/3] maple_tree: assert retrieving new value on a tree with only root node

[Wei Yang]

On Mon, Feb 10, 2025 at 09:18:53AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>> Original code may get a stall value when overwriting the whole range on a
>                          ^^^^^- stale value.  I thought you were saying
>			  it was stalling which did not make sense.
>

I want to say we don't get the new value as we expect.

How about:

Original code may not get the new value after overwriting the whole range on a
maple tree with only root node.

>> maple tree with only root node. The reason is we didn't set the only
>> root node dead during destroy.
>> 
>> Add a test case to verify this is not recreated.
>> 
>> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
>> ---
>>  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
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH 0/3] may miss to set node dead on destroy

[Wei Yang]

On Mon, Feb 10, 2025 at 09:31:28AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>
>The subject of this patch set makes the issue sound much more sever than
>it is.  It currently sounds like a memory leak or a UAF, which isn't the
>case.
>

Not intend to exaggerate the impact.

Is this one would be better?

  maple_tree: make sure each node is dead on destroy

>The root node may remain usable for the duration of the rcu window if
>it's a leaf node.  The impact is pretty minor - you may see the old data
>on calls that happen in the same rcu window - which is the case anyways.
>
>You should also say maple_tree: in the subject since this is
>going to linux-mm.  Not a really big deal since each patch in the series
>specifies the maple tree.
>

Thanks, will add it in next version.

>> Per my understanding, 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: may miss to set node dead on destroy
>>   maple_tree: restart walk on correct status
>>   maple_tree: assert retrieving new value on a tree with only root node
>> 
>>  lib/maple_tree.c                 |  4 +++-
>>  tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
>>  2 files changed, 27 insertions(+), 1 deletion(-)
>> 
>> -- 
>> 2.34.1
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH 1/3] maple_tree: may miss to set node dead on destroy

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250211 02:49]:
> On Mon, Feb 10, 2025 at 09:19:46AM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
> >> 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.
> >> 
> >> This patch fixes this by setting the root dead before mt_destroy_walk().
> >> 
> >> 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>
> >> ---
> >>  lib/maple_tree.c | 2 ++
> >>  1 file changed, 2 insertions(+)
> >> 
> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> >> index 198c14dd3377..d31f0a2858f7 100644
> >> --- a/lib/maple_tree.c
> >> +++ b/lib/maple_tree.c
> >> @@ -5347,6 +5347,8 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
> >>  {
> >>  	struct maple_node *node = mte_to_node(enode);
> >>  
> >> +	mte_set_node_dead(enode);
> >> +
> >
> >This belongs in mt_destroy_walk().
> 
> You prefer a change like this?

Yes.

> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index e64ffa5b9970..79f8632c61a3 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5288,6 +5288,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;
>  	}
> >
> >>  	if (mt_in_rcu(mt)) {
> >>  		mt_destroy_walk(enode, mt, false);
> >>  		call_rcu(&node->rcu, mt_free_walk);
> >> -- 
> >> 2.34.1
> >> 
> 
> -- 
> Wei Yang
> Help you, Help me

Re: [PATCH 3/3] maple_tree: assert retrieving new value on a tree with only root node

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250211 03:02]:
> On Mon, Feb 10, 2025 at 09:18:53AM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
> >> Original code may get a stall value when overwriting the whole range on a
> >                          ^^^^^- stale value.  I thought you were saying
> >			  it was stalling which did not make sense.
> >
> 
> I want to say we don't get the new value as we expect.
> 
> How about:
> 
> Original code may not get the new value after overwriting the whole range on a
> maple tree with only root node.

That's more clear than what you had before.  Usually you try to
concentrate on what you did, not what was there.

Ensure the new value is returned when overwriting a tree containing just
a leaf node.

> 
> >> maple tree with only root node. The reason is we didn't set the only
> >> root node dead during destroy.
> >> 
> >> Add a test case to verify this is not recreated.
> >> 
> >> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> >> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
> >> ---
> >>  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
> >> 
> 
> -- 
> Wei Yang
> Help you, Help me

Re: [PATCH 0/3] may miss to set node dead on destroy

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250211 03:11]:
> On Mon, Feb 10, 2025 at 09:31:28AM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
> >
> >The subject of this patch set makes the issue sound much more sever than
> >it is.  It currently sounds like a memory leak or a UAF, which isn't the
> >case.
> >
> 
> Not intend to exaggerate the impact.
> 
> Is this one would be better?
> 
>   maple_tree: make sure each node is dead on destroy

Not really, you are fixing two nodes, one isn't even to do with the
destry/dead node.  You are also not making sure each node is dead, but
fixing an issue with the leaf node.

maple_tree: Fix the replacement of a root leaf node ?

> 
> >The root node may remain usable for the duration of the rcu window if
> >it's a leaf node.  The impact is pretty minor - you may see the old data
> >on calls that happen in the same rcu window - which is the case anyways.
> >
> >You should also say maple_tree: in the subject since this is
> >going to linux-mm.  Not a really big deal since each patch in the series
> >specifies the maple tree.
> >
> 
> Thanks, will add it in next version.
> 
> >> Per my understanding, 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: may miss to set node dead on destroy
> >>   maple_tree: restart walk on correct status
> >>   maple_tree: assert retrieving new value on a tree with only root node
> >> 
> >>  lib/maple_tree.c                 |  4 +++-
> >>  tools/testing/radix-tree/maple.c | 24 ++++++++++++++++++++++++
> >>  2 files changed, 27 insertions(+), 1 deletion(-)
> >> 
> >> -- 
> >> 2.34.1
> >> 
> 
> -- 
> Wei Yang
> Help you, Help me

Re: [PATCH 1/3] maple_tree: may miss to set node dead on destroy

[Wei Yang]

On Tue, Feb 11, 2025 at 10:23:26AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250211 02:49]:
>> On Mon, Feb 10, 2025 at 09:19:46AM -0500, Liam R. Howlett wrote:
>> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>> >> 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.
>> >> 
>> >> This patch fixes this by setting the root dead before mt_destroy_walk().
>> >> 
>> >> 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>
>> >> ---
>> >>  lib/maple_tree.c | 2 ++
>> >>  1 file changed, 2 insertions(+)
>> >> 
>> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> >> index 198c14dd3377..d31f0a2858f7 100644
>> >> --- a/lib/maple_tree.c
>> >> +++ b/lib/maple_tree.c
>> >> @@ -5347,6 +5347,8 @@ static inline void mte_destroy_walk(struct maple_enode *enode,
>> >>  {
>> >>  	struct maple_node *node = mte_to_node(enode);
>> >>  
>> >> +	mte_set_node_dead(enode);
>> >> +
>> >
>> >This belongs in mt_destroy_walk().
>> 
>> You prefer a change like this?
>
>Yes.
>

Thanks, will adjust in v2.

>> 
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index e64ffa5b9970..79f8632c61a3 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -5288,6 +5288,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;
>>  	}
>> >
>> >>  	if (mt_in_rcu(mt)) {
>> >>  		mt_destroy_walk(enode, mt, false);
>> >>  		call_rcu(&node->rcu, mt_free_walk);
>> >> -- 
>> >> 2.34.1
>> >> 
>> 
>> -- 
>> Wei Yang
>> Help you, Help me

-- 
Wei Yang
Help you, Help me

Re: [PATCH 3/3] maple_tree: assert retrieving new value on a tree with only root node

[Wei Yang]

On Tue, Feb 11, 2025 at 10:25:27AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250211 03:02]:
>> On Mon, Feb 10, 2025 at 09:18:53AM -0500, Liam R. Howlett wrote:
>> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>> >> Original code may get a stall value when overwriting the whole range on a
>> >                          ^^^^^- stale value.  I thought you were saying
>> >			  it was stalling which did not make sense.
>> >
>> 
>> I want to say we don't get the new value as we expect.
>> 
>> How about:
>> 
>> Original code may not get the new value after overwriting the whole range on a
>> maple tree with only root node.
>
>That's more clear than what you had before.  Usually you try to
>concentrate on what you did, not what was there.

Thanks, I didn't notice it. Will pay attention to it.

>
>Ensure the new value is returned when overwriting a tree containing just
>a leaf node.
>
>> 
>> >> maple tree with only root node. The reason is we didn't set the only
>> >> root node dead during destroy.
>> >> 
>> >> Add a test case to verify this is not recreated.
>> >> 
>> >> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> >> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
>> >> ---
>> >>  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
>> >> 
>> 
>> -- 
>> Wei Yang
>> Help you, Help me

-- 
Wei Yang
Help you, Help me

Re: [PATCH 0/3] may miss to set node dead on destroy

[Wei Yang]

On Tue, Feb 11, 2025 at 10:28:53AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250211 03:11]:
>> On Mon, Feb 10, 2025 at 09:31:28AM -0500, Liam R. Howlett wrote:
>> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>> >
>> >The subject of this patch set makes the issue sound much more sever than
>> >it is.  It currently sounds like a memory leak or a UAF, which isn't the
>> >case.
>> >
>> 
>> Not intend to exaggerate the impact.
>> 
>> Is this one would be better?
>> 
>>   maple_tree: make sure each node is dead on destroy
>
>Not really, you are fixing two nodes, one isn't even to do with the
>destry/dead node.  You are also not making sure each node is dead, but
>fixing an issue with the leaf node.
>
>maple_tree: Fix the replacement of a root leaf node ?
>

Thanks, it looks more precise.

BTW, after addressing your current comments, could I send a v2?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 0/3] may miss to set node dead on destroy

[Wei Yang]

On Tue, Feb 11, 2025 at 10:28:53AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250211 03:11]:
>> On Mon, Feb 10, 2025 at 09:31:28AM -0500, Liam R. Howlett wrote:
>> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>> >
>> >The subject of this patch set makes the issue sound much more sever than
>> >it is.  It currently sounds like a memory leak or a UAF, which isn't the
>> >case.
>> >
>> 
>> Not intend to exaggerate the impact.
>> 
>> Is this one would be better?
>> 
>>   maple_tree: make sure each node is dead on destroy
>
>Not really, you are fixing two nodes, one isn't even to do with the
>destry/dead node.  You are also not making sure each node is dead, but
>fixing an issue with the leaf node.
>
>maple_tree: Fix the replacement of a root leaf node ?
>

One more question, would it be better to use this as the subject of patch 1?

-- 
Wei Yang
Help you, Help me

Re: [PATCH 0/3] may miss to set node dead on destroy

[Wei Yang]

On Wed, Feb 12, 2025 at 12:55:36AM +0000, Wei Yang wrote:
>On Tue, Feb 11, 2025 at 10:28:53AM -0500, Liam R. Howlett wrote:
>>* Wei Yang <richard.weiyang@gmail.com> [250211 03:11]:
>>> On Mon, Feb 10, 2025 at 09:31:28AM -0500, Liam R. Howlett wrote:
>>> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>>> >
>>> >The subject of this patch set makes the issue sound much more sever than
>>> >it is.  It currently sounds like a memory leak or a UAF, which isn't the
>>> >case.
>>> >
>>> 
>>> Not intend to exaggerate the impact.
>>> 
>>> Is this one would be better?
>>> 
>>>   maple_tree: make sure each node is dead on destroy
>>
>>Not really, you are fixing two nodes, one isn't even to do with the
>>destry/dead node.  You are also not making sure each node is dead, but
>>fixing an issue with the leaf node.
>>
>>maple_tree: Fix the replacement of a root leaf node ?
>>
>
>One more question, would it be better to use this as the subject of patch 1?
>

Liam,

Are you ok with this and can I send a v2?

>-- 
>Wei Yang
>Help you, Help me

-- 
Wei Yang
Help you, Help me

Re: [PATCH 0/3] may miss to set node dead on destroy

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [250304 07:07]:
> On Wed, Feb 12, 2025 at 12:55:36AM +0000, Wei Yang wrote:
> >On Tue, Feb 11, 2025 at 10:28:53AM -0500, Liam R. Howlett wrote:
> >>* Wei Yang <richard.weiyang@gmail.com> [250211 03:11]:
> >>> On Mon, Feb 10, 2025 at 09:31:28AM -0500, Liam R. Howlett wrote:
> >>> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
> >>> >
> >>> >The subject of this patch set makes the issue sound much more sever than
> >>> >it is.  It currently sounds like a memory leak or a UAF, which isn't the
> >>> >case.
> >>> >
> >>> 
> >>> Not intend to exaggerate the impact.
> >>> 
> >>> Is this one would be better?
> >>> 
> >>>   maple_tree: make sure each node is dead on destroy
> >>
> >>Not really, you are fixing two nodes, one isn't even to do with the
> >>destry/dead node.  You are also not making sure each node is dead, but
> >>fixing an issue with the leaf node.
> >>
> >>maple_tree: Fix the replacement of a root leaf node ?
> >>
> >
> >One more question, would it be better to use this as the subject of patch 1?

You are not fixing the replacement of the root leaf node, you are fixing
the free path of the old root leaf node.

The fix is in mt_destroy_walk(), I usually try to have the function name
in the first line too..

maple_tree: Fix mt_destroy_walk() on root leaf node


> >
> 
> Liam,
> 
> Are you ok with this and can I send a v2?

Pleas send v2.


Thanks,
Liam

Re: [PATCH 0/3] may miss to set node dead on destroy

[Wei Yang]

On Tue, Mar 04, 2025 at 09:45:16AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [250304 07:07]:
>> On Wed, Feb 12, 2025 at 12:55:36AM +0000, Wei Yang wrote:
>> >On Tue, Feb 11, 2025 at 10:28:53AM -0500, Liam R. Howlett wrote:
>> >>* Wei Yang <richard.weiyang@gmail.com> [250211 03:11]:
>> >>> On Mon, Feb 10, 2025 at 09:31:28AM -0500, Liam R. Howlett wrote:
>> >>> >* Wei Yang <richard.weiyang@gmail.com> [250207 20:26]:
>> >>> >
>> >>> >The subject of this patch set makes the issue sound much more sever than
>> >>> >it is.  It currently sounds like a memory leak or a UAF, which isn't the
>> >>> >case.
>> >>> >
>> >>> 
>> >>> Not intend to exaggerate the impact.
>> >>> 
>> >>> Is this one would be better?
>> >>> 
>> >>>   maple_tree: make sure each node is dead on destroy
>> >>
>> >>Not really, you are fixing two nodes, one isn't even to do with the
>> >>destry/dead node.  You are also not making sure each node is dead, but
>> >>fixing an issue with the leaf node.
>> >>
>> >>maple_tree: Fix the replacement of a root leaf node ?
>> >>
>> >
>> >One more question, would it be better to use this as the subject of patch 1?
>
>You are not fixing the replacement of the root leaf node, you are fixing
>the free path of the old root leaf node.
>
>The fix is in mt_destroy_walk(), I usually try to have the function name
>in the first line too..
>
>maple_tree: Fix mt_destroy_walk() on root leaf node
>

Thanks, this is better.

>
>> >
>> 
>> Liam,
>> 
>> Are you ok with this and can I send a v2?
>
>Pleas send v2.
>
>
>Thanks,
>Liam

-- 
Wei Yang
Help you, Help me