[PATCH 1/2] maple_tree: fix alloc node fail issue

[PATCH 1/2] maple_tree: fix alloc node fail issue

[Liam R. Howlett]

From: Jiazi Li <jqqlijiazi@gmail.com>

In the following code, the second call to the mas_node_count will
return -ENOMEM:

	mas_node_count(mas, MAPLE_ALLOC_SLOTS + 1);
	mas_node_count(mas, MAPLE_ALLOC_SLOTS * 2 + 2);

This is because there may be some full maple_alloc node in current
maple state. Use full maple_alloc node will make max_req equal to 0.
And it leads to mt_alloc_bulk return 0.
As a result, mas_node_count set mas.node to MA_ERROR(-ENOMEM).

Find a non-full maple_alloc node, and if necessary, use this non-full
node in the next while loop.

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 634d49e39a02..fe5c6fab26c3 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1272,7 +1272,10 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
 
 		node->node_count += count;
 		allocated += count;
-		node = node->slot[0];
+		/* find a non-full node*/
+		do {
+			node = node->slot[0];
+		} while (unlikely(node->node_count == MAPLE_ALLOC_SLOTS));
 		requested -= count;
 	}
 	mas->alloc->total = allocated;
-- 
2.43.0

[PATCH 2/2] maple_tree: Add some alloc node test case

[Liam R. Howlett]

From: Jiazi Li <jqqlijiazi@gmail.com>

Add some maple_tree alloc node tese case.

Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 tools/testing/radix-tree/maple.c | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 11f1efdf83f9..b4b5fd9f294d 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -462,6 +462,28 @@ static noinline void __init check_new_node(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
 	mas_destroy(&mas);
 
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 2); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	mas.status = ma_start;
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2);
+	mas_destroy(&mas);
+
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 1); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1);
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 3 + 2); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	mas.status = ma_start;
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2);
+	mas_destroy(&mas);
+
 	mtree_unlock(mt);
 }
 
-- 
2.43.0

Re: [PATCH 2/2] maple_tree: Add some alloc node test case

[Wei Yang]

On Wed, Jun 26, 2024 at 12:06:31PM -0400, Liam R. Howlett wrote:
>From: Jiazi Li <jqqlijiazi@gmail.com>
>
>Add some maple_tree alloc node tese case.
>
>Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
>Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>---
> tools/testing/radix-tree/maple.c | 22 ++++++++++++++++++++++
> 1 file changed, 22 insertions(+)
>
>diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
>index 11f1efdf83f9..b4b5fd9f294d 100644
>--- a/tools/testing/radix-tree/maple.c
>+++ b/tools/testing/radix-tree/maple.c
>@@ -462,6 +462,28 @@ static noinline void __init check_new_node(struct maple_tree *mt)
> 	MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
> 	mas_destroy(&mas);
> 
>+	mas.node = MA_ERROR(-ENOMEM);
>+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
>+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */

I am not sure why mas_nomem() is here.

Without this one, we still can trigger the original bug.

>+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
>+	mas.node = MA_ERROR(-ENOMEM);
>+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 2); /* Request */
>+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
>+	mas.status = ma_start;
>+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2);
>+	mas_destroy(&mas);
>+
>+	mas.node = MA_ERROR(-ENOMEM);
>+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 1); /* Request */
>+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
>+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1);
>+	mas.node = MA_ERROR(-ENOMEM);
>+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 3 + 2); /* Request */
>+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
>+	mas.status = ma_start;
>+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2);
>+	mas_destroy(&mas);
>+
> 	mtree_unlock(mt);
> }
> 
>-- 
>2.43.0
>

-- 
Wei Yang
Help you, Help me

Re: [PATCH 2/2] maple_tree: Add some alloc node test case

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241010 21:18]:
> On Wed, Jun 26, 2024 at 12:06:31PM -0400, Liam R. Howlett wrote:
> >From: Jiazi Li <jqqlijiazi@gmail.com>
> >
> >Add some maple_tree alloc node tese case.
> >
> >Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> >Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
> >Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> >---
> > tools/testing/radix-tree/maple.c | 22 ++++++++++++++++++++++
> > 1 file changed, 22 insertions(+)
> >
> >diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> >index 11f1efdf83f9..b4b5fd9f294d 100644
> >--- a/tools/testing/radix-tree/maple.c
> >+++ b/tools/testing/radix-tree/maple.c
> >@@ -462,6 +462,28 @@ static noinline void __init check_new_node(struct maple_tree *mt)
> > 	MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
> > 	mas_destroy(&mas);
> > 
> >+	mas.node = MA_ERROR(-ENOMEM);
> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
> 
> I am not sure why mas_nomem() is here.
> 
> Without this one, we still can trigger the original bug.

It will fill the maple state allocation.  Might not be needed but
doesn't hurt.

> 
> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
> >+	mas.node = MA_ERROR(-ENOMEM);
> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 2); /* Request */
> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
> >+	mas.status = ma_start;
> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2);
> >+	mas_destroy(&mas);
> >+
> >+	mas.node = MA_ERROR(-ENOMEM);
> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 1); /* Request */
> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1);
> >+	mas.node = MA_ERROR(-ENOMEM);
> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 3 + 2); /* Request */
> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
> >+	mas.status = ma_start;
> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2);
> >+	mas_destroy(&mas);
> >+
> > 	mtree_unlock(mt);
> > }
> > 
> >-- 
> >2.43.0
> >
> 
> -- 
> Wei Yang
> Help you, Help me

Re: [PATCH 2/2] maple_tree: Add some alloc node test case

[Wei Yang]

On Mon, Oct 14, 2024 at 09:15:07PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241010 21:18]:
>> On Wed, Jun 26, 2024 at 12:06:31PM -0400, Liam R. Howlett wrote:
>> >From: Jiazi Li <jqqlijiazi@gmail.com>
>> >
>> >Add some maple_tree alloc node tese case.
>> >
>> >Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>> >Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
>> >Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>> >---
>> > tools/testing/radix-tree/maple.c | 22 ++++++++++++++++++++++
>> > 1 file changed, 22 insertions(+)
>> >
>> >diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
>> >index 11f1efdf83f9..b4b5fd9f294d 100644
>> >--- a/tools/testing/radix-tree/maple.c
>> >+++ b/tools/testing/radix-tree/maple.c
>> >@@ -462,6 +462,28 @@ static noinline void __init check_new_node(struct maple_tree *mt)
>> > 	MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
>> > 	mas_destroy(&mas);
>> > 
>> >+	mas.node = MA_ERROR(-ENOMEM);
>> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
>> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
>> 
>> I am not sure why mas_nomem() is here.
>> 
>> Without this one, we still can trigger the original bug.
>
>It will fill the maple state allocation.  Might not be needed but
>doesn't hurt.
>

I took another look at it. We really need mas_nomem() here, since we call
mt_set_non_kernel(0) at the beginning of check_new_node(). 

So mas_node_count() just set the request count and mas_nomem() does the real
allocation.

Any reason to design test case like this?

>> 
>> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
>> >+	mas.node = MA_ERROR(-ENOMEM);
>> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 2); /* Request */
>> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
>> >+	mas.status = ma_start;
>> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 2);
>> >+	mas_destroy(&mas);
>> >+
>> >+	mas.node = MA_ERROR(-ENOMEM);
>> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 2 + 1); /* Request */
>> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
>> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 2 + 1);
>> >+	mas.node = MA_ERROR(-ENOMEM);
>> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS * 3 + 2); /* Request */
>> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
>> >+	mas.status = ma_start;
>> >+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS * 3 + 2);
>> >+	mas_destroy(&mas);
>> >+
>> > 	mtree_unlock(mt);
>> > }
>> > 
>> >-- 
>> >2.43.0
>> >
>> 
>> -- 
>> Wei Yang
>> Help you, Help me

-- 
Wei Yang
Help you, Help me

Re: [PATCH 2/2] maple_tree: Add some alloc node test case

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241015 09:31]:
> On Mon, Oct 14, 2024 at 09:15:07PM -0400, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [241010 21:18]:
> >> On Wed, Jun 26, 2024 at 12:06:31PM -0400, Liam R. Howlett wrote:
> >> >From: Jiazi Li <jqqlijiazi@gmail.com>
> >> >
> >> >Add some maple_tree alloc node tese case.
> >> >
> >> >Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> >> >Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
> >> >Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> >> >---
> >> > tools/testing/radix-tree/maple.c | 22 ++++++++++++++++++++++
> >> > 1 file changed, 22 insertions(+)
> >> >
> >> >diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> >> >index 11f1efdf83f9..b4b5fd9f294d 100644
> >> >--- a/tools/testing/radix-tree/maple.c
> >> >+++ b/tools/testing/radix-tree/maple.c
> >> >@@ -462,6 +462,28 @@ static noinline void __init check_new_node(struct maple_tree *mt)
> >> > 	MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
> >> > 	mas_destroy(&mas);
> >> > 
> >> >+	mas.node = MA_ERROR(-ENOMEM);
> >> >+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
> >> >+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
> >> 
> >> I am not sure why mas_nomem() is here.
> >> 
> >> Without this one, we still can trigger the original bug.
> >
> >It will fill the maple state allocation.  Might not be needed but
> >doesn't hurt.
> >
> 
> I took another look at it. We really need mas_nomem() here, since we call
> mt_set_non_kernel(0) at the beginning of check_new_node(). 
> 
> So mas_node_count() just set the request count and mas_nomem() does the real
> allocation.
> 
> Any reason to design test case like this?

There are two types of testing that we do: ones that can call internal
functions to poke at stuff (like this one), and ones that can't which is
more like what users can do (lives in lib/test_maple_tree.c).

Both are important as this checks what we think will happen while the
other tests the integration of all our work together.

As for this particular test, the two parts work together most of the
time, but if we run out of memory then we need to test them in parts to
make sure both are doing what we think.

It also means that we can easily set up tests for scenarios that are
harder to synthesize using the external api - but they can happen.  I'm
not sure if this is the case for this test, but there were tests already
setting the allocations into certain positions and this is now just
another one of those tests.

I hope this helps explain some more of the testing work here as it is
extremely important.  I'm very pleased to have this setup to recreate
issues for both fixing issues and ensuring they do not return -
especially on large refactoring, new features or algorithms.

Thanks,
Liam

Re: [PATCH 1/2] maple_tree: fix alloc node fail issue

[Wei Yang]

On Wed, Jun 26, 2024 at 12:06:30PM -0400, Liam R. Howlett wrote:
>From: Jiazi Li <jqqlijiazi@gmail.com>
>
>In the following code, the second call to the mas_node_count will
>return -ENOMEM:
>
>	mas_node_count(mas, MAPLE_ALLOC_SLOTS + 1);
>	mas_node_count(mas, MAPLE_ALLOC_SLOTS * 2 + 2);
>
>This is because there may be some full maple_alloc node in current
>maple state. Use full maple_alloc node will make max_req equal to 0.
>And it leads to mt_alloc_bulk return 0.
>As a result, mas_node_count set mas.node to MA_ERROR(-ENOMEM).
>
>Find a non-full maple_alloc node, and if necessary, use this non-full
>node in the next while loop.
>
>Fixes: 54a611b60590 ("Maple Tree: add new data structure")
>Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
>Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

Reviewed-by: Wei Yang <richard.weiyang@gmail.com>


This looks good to me.

I don't see it is in the master. Not sure this is missed.

-- 
Wei Yang
Help you, Help me

Re: [PATCH 1/2] maple_tree: fix alloc node fail issue

[Liam R. Howlett]

Andrew,

I think these two were missed.  Can you please pick them up?

Thanks,
Liam

* Liam R. Howlett <Liam.Howlett@oracle.com> [240626 12:06]:
> From: Jiazi Li <jqqlijiazi@gmail.com>
> 
> In the following code, the second call to the mas_node_count will
> return -ENOMEM:
> 
> 	mas_node_count(mas, MAPLE_ALLOC_SLOTS + 1);
> 	mas_node_count(mas, MAPLE_ALLOC_SLOTS * 2 + 2);
> 
> This is because there may be some full maple_alloc node in current
> maple state. Use full maple_alloc node will make max_req equal to 0.
> And it leads to mt_alloc_bulk return 0.
> As a result, mas_node_count set mas.node to MA_ERROR(-ENOMEM).
> 
> Find a non-full maple_alloc node, and if necessary, use this non-full
> node in the next while loop.
> 
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> Suggested-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> Signed-off-by: Jiazi Li <jqqlijiazi@gmail.com>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> ---
>  lib/maple_tree.c | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 634d49e39a02..fe5c6fab26c3 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1272,7 +1272,10 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
>  
>  		node->node_count += count;
>  		allocated += count;
> -		node = node->slot[0];
> +		/* find a non-full node*/
> +		do {
> +			node = node->slot[0];
> +		} while (unlikely(node->node_count == MAPLE_ALLOC_SLOTS));
>  		requested -= count;
>  	}
>  	mas->alloc->total = allocated;
> -- 
> 2.43.0
>