[PATCH 0/2] fix mas_new_root()

[PATCH 0/2] fix mas_new_root()

[Wei Yang]

When overwriting the whole range with NULL, current behavior is not correct.

Wei Yang (2):
  maple_tree: not necessary to check index/last again
  maple_tree: one single entry couldn't represent the whole range

 lib/maple_tree.c | 9 ---------
 1 file changed, 9 deletions(-)

-- 
2.34.1

[PATCH 1/2] maple_tree: not necessary to check index/last again

[Wei Yang]

Before calling mas_new_root(), the range has been checked.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes@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 0aa9fa8fa7de..3a12866a4a89 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3594,7 +3594,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
 	void __rcu **slots;
 	unsigned long *pivots;
 
-	if (!entry && !mas->index && mas->last == ULONG_MAX) {
+	if (!entry) {
 		mas->depth = 0;
 		mas_set_height(mas);
 		rcu_assign_pointer(mas->tree->ma_root, entry);
-- 
2.34.1

[PATCH 2/2] maple_tree: one single entry couldn't represent the whole range

[Wei Yang]

The current behavior of overwriting the whole range with NULL is not
correct.

For example, we store range [0, ULONG_MAX] to a new tree:

  mas_set_range(&ms, 0, ULONG_MAX);
  mas_store(&ms, NULL);
  mt_dump(mt, mt_dump_dec);

The dump result shows:

  maple_tree(0x7ffd9506e350) flags 7, height 1 root 0x61500000010e
  0-18446744073709551615: node 0x615000000100 depth 0 type 1 parent 0x7ffd9506e351 contents: (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil)
    0-18446744073709551615: (nil)

But if we do the store on a tree with value:

  mas_set_range(&ms, 5, ULONG_MAX);
  mas_store(&ms, NULL);
  mas_set_range(&ms, 0, ULONG_MAX);
  mas_store(&ms, NULL);
  mt_dump(mt, mt_dump_dec);

The dump result shows:

  maple_tree(0x7ffd9506e350) flags 3, height 0 root (nil)
  0: (nil)

We can see even we write the same range, these two trees are different.
The second tree only has an entry represent range [0, 0] instead of range
[0, ULONG_MAX], which is not correct.

The good news is it doesn't affect user, because mtree_load() still
return NULL for each index.

Let's create a node to represent the entire range even for NULL entry.

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: Sidhartha Kumar <sidhartha.kumar@oracle.com>
CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
---
 lib/maple_tree.c | 9 ---------
 1 file changed, 9 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3a12866a4a89..5dfc589a8cde 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3594,14 +3594,6 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
 	void __rcu **slots;
 	unsigned long *pivots;
 
-	if (!entry) {
-		mas->depth = 0;
-		mas_set_height(mas);
-		rcu_assign_pointer(mas->tree->ma_root, entry);
-		mas->status = ma_start;
-		goto done;
-	}
-
 	node = mas_pop_node(mas);
 	pivots = ma_pivots(node, type);
 	slots = ma_slots(node, type);
@@ -3614,7 +3606,6 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
 	mas_set_height(mas);
 	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
 
-done:
 	if (xa_is_node(root))
 		mte_destroy_walk(root, mas->tree);
 
-- 
2.34.1

Re: [PATCH 2/2] maple_tree: one single entry couldn't represent the whole range

[Liam R. Howlett]

nack

* Wei Yang <richard.weiyang@gmail.com> [241015 19:39]:
> The current behavior of overwriting the whole range with NULL is not
> correct.
> 
> For example, we store range [0, ULONG_MAX] to a new tree:
> 
>   mas_set_range(&ms, 0, ULONG_MAX);
>   mas_store(&ms, NULL);
>   mt_dump(mt, mt_dump_dec);
> 
> The dump result shows:
> 
>   maple_tree(0x7ffd9506e350) flags 7, height 1 root 0x61500000010e
>   0-18446744073709551615: node 0x615000000100 depth 0 type 1 parent 0x7ffd9506e351 contents: (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil)
>     0-18446744073709551615: (nil)
> 
> But if we do the store on a tree with value:
> 
>   mas_set_range(&ms, 5, ULONG_MAX);
>   mas_store(&ms, NULL);
>   mas_set_range(&ms, 0, ULONG_MAX);
>   mas_store(&ms, NULL);
>   mt_dump(mt, mt_dump_dec);
> 
> The dump result shows:
> 
>   maple_tree(0x7ffd9506e350) flags 3, height 0 root (nil)
>   0: (nil)
> 
> We can see even we write the same range, these two trees are different.
> The second tree only has an entry represent range [0, 0] instead of range
> [0, ULONG_MAX], which is not correct.
> 
> The good news is it doesn't affect user, because mtree_load() still
> return NULL for each index.
> 
> Let's create a node to represent the entire range even for NULL entry.
> 
> 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: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> ---
>  lib/maple_tree.c | 9 ---------
>  1 file changed, 9 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 3a12866a4a89..5dfc589a8cde 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3594,14 +3594,6 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
>  	void __rcu **slots;
>  	unsigned long *pivots;
>  
> -	if (!entry) {
> -		mas->depth = 0;
> -		mas_set_height(mas);
> -		rcu_assign_pointer(mas->tree->ma_root, entry);
> -		mas->status = ma_start;
> -		goto done;
> -	}
> -
>  	node = mas_pop_node(mas);
>  	pivots = ma_pivots(node, type);
>  	slots = ma_slots(node, type);
> @@ -3614,7 +3606,6 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)
>  	mas_set_height(mas);
>  	rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
>  
> -done:
>  	if (xa_is_node(root))
>  		mte_destroy_walk(root, mas->tree);
>  
> -- 
> 2.34.1
> 

Re: [PATCH 0/2] fix mas_new_root()

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241015 19:39]:
> When overwriting the whole range with NULL, current behavior is not correct.
> 

This is really strange.  You have changed the code to be wrong then
removed it..  The second patch removes what you changed in the first.

It doesn't look right today but what you have done is also not right.


> Wei Yang (2):
>   maple_tree: not necessary to check index/last again
>   maple_tree: one single entry couldn't represent the whole range
> 
>  lib/maple_tree.c | 9 ---------
>  1 file changed, 9 deletions(-)
> 
> -- 
> 2.34.1
> 
> 

Re: [PATCH 0/2] fix mas_new_root()

[Liam R. Howlett]

* Liam R. Howlett <Liam.Howlett@oracle.com> [241015 20:42]:
> * Wei Yang <richard.weiyang@gmail.com> [241015 19:39]:
> > When overwriting the whole range with NULL, current behavior is not correct.
> > 
> 
> This is really strange.  You have changed the code to be wrong then
> removed it..  The second patch removes what you changed in the first.
> 
> It doesn't look right today but what you have done is also not right.

Looking at this again, the code that you have changed is correct.

I actually think the bug is the other way around.  If we are
represnenting 0 - ULONG_MAX => NULL, then it's an empty tree and we
don't need a node to store that, and shouldn't.

It's also not really a bug, but a missed optimisation.  The ranges are
stored correctly, we just use too much memory in one case.

The dump isn't clear, but since we merge NULL entries, if there is a 0-0
-> NULL and 1-ULONG_MAX => NULL, then they will be one and the same.
You could change the dump code as part of your fix.

It's like the init of a tree (tree->ma_root = NULL).

Please don't submit multiple patches to fix the same thing like this, it
makes it look like you are trying to pad your patch count.  I'm guessing
you did this to keep them logically separate, but when you completely
drop the entire block of code that was changed in the second patch it
becomes a bit much (and hard to follow, I was trying to figure out what
branch you were working off because it didn't look like the patch would
apply to my branch).

Please submit a testcase with any suspected bugs. If it is not possible
to do the fix first, then do them at the same time.  I often write the
fix for a bug, then recreate the bug in a testcase and ensure that it
fails without my fix.

I am not sure the fixes tag is correct in the patch either, since so
much has changed around this.  You could test the older code to see once
you write a testcase.  But the bug is using a node to store 0-ULONG_MAX
=> NULL.

> 
> 
> > Wei Yang (2):
> >   maple_tree: not necessary to check index/last again
> >   maple_tree: one single entry couldn't represent the whole range
> > 
> >  lib/maple_tree.c | 9 ---------
> >  1 file changed, 9 deletions(-)
> > 
> > -- 
> > 2.34.1
> > 
> > 

Re: [PATCH 0/2] fix mas_new_root()

[Wei Yang]

On Tue, Oct 15, 2024 at 09:25:19PM -0400, Liam R. Howlett wrote:
>* Liam R. Howlett <Liam.Howlett@oracle.com> [241015 20:42]:
>> * Wei Yang <richard.weiyang@gmail.com> [241015 19:39]:
>> > When overwriting the whole range with NULL, current behavior is not correct.
>> > 
>> 
>> This is really strange.  You have changed the code to be wrong then
>> removed it..  The second patch removes what you changed in the first.
>> 
>> It doesn't look right today but what you have done is also not right.
>
>Looking at this again, the code that you have changed is correct.
>
>I actually think the bug is the other way around.  If we are
>represnenting 0 - ULONG_MAX => NULL, then it's an empty tree and we
>don't need a node to store that, and shouldn't.
>
>It's also not really a bug, but a missed optimisation.  The ranges are
>stored correctly, we just use too much memory in one case.
>
>The dump isn't clear, but since we merge NULL entries, if there is a 0-0
>-> NULL and 1-ULONG_MAX => NULL, then they will be one and the same.
>You could change the dump code as part of your fix.
>
>It's like the init of a tree (tree->ma_root = NULL).

Agree with your above statement, this depends how we want to handle this. The
change here is to make the behavior consistent.

Want to confirm with you: the fix in this patch is fine with your, right?

>
>Please don't submit multiple patches to fix the same thing like this, it
>makes it look like you are trying to pad your patch count.  I'm guessing
>you did this to keep them logically separate, but when you completely
>drop the entire block of code that was changed in the second patch it
>becomes a bit much (and hard to follow, I was trying to figure out what
>branch you were working off because it didn't look like the patch would
>apply to my branch).

Sure, will merge it.

>
>Please submit a testcase with any suspected bugs. If it is not possible
>to do the fix first, then do them at the same time.  I often write the
>fix for a bug, then recreate the bug in a testcase and ensure that it
>fails without my fix.
>

Since user won't detect the difference, so a case to see whether the root is a
node looks good to you?

>I am not sure the fixes tag is correct in the patch either, since so
>much has changed around this.  You could test the older code to see once
>you write a testcase.  But the bug is using a node to store 0-ULONG_MAX
>=> NULL.
>

So I should drop the fix tag?

>> 
>> 
>> > Wei Yang (2):
>> >   maple_tree: not necessary to check index/last again
>> >   maple_tree: one single entry couldn't represent the whole range
>> > 
>> >  lib/maple_tree.c | 9 ---------
>> >  1 file changed, 9 deletions(-)
>> > 
>> > -- 
>> > 2.34.1
>> > 
>> > 

-- 
Wei Yang
Help you, Help me

Re: [PATCH 0/2] fix mas_new_root()

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241015 22:18]:
> On Tue, Oct 15, 2024 at 09:25:19PM -0400, Liam R. Howlett wrote:
> >* Liam R. Howlett <Liam.Howlett@oracle.com> [241015 20:42]:
> >> * Wei Yang <richard.weiyang@gmail.com> [241015 19:39]:
> >> > When overwriting the whole range with NULL, current behavior is not correct.
> >> > 
> >> 
> >> This is really strange.  You have changed the code to be wrong then
> >> removed it..  The second patch removes what you changed in the first.
> >> 
> >> It doesn't look right today but what you have done is also not right.
> >
> >Looking at this again, the code that you have changed is correct.
> >
> >I actually think the bug is the other way around.  If we are
> >represnenting 0 - ULONG_MAX => NULL, then it's an empty tree and we
> >don't need a node to store that, and shouldn't.
> >
> >It's also not really a bug, but a missed optimisation.  The ranges are
> >stored correctly, we just use too much memory in one case.
> >
> >The dump isn't clear, but since we merge NULL entries, if there is a 0-0
> >-> NULL and 1-ULONG_MAX => NULL, then they will be one and the same.
> >You could change the dump code as part of your fix.
> >
> >It's like the init of a tree (tree->ma_root = NULL).
> 
> Agree with your above statement, this depends how we want to handle this. The
> change here is to make the behavior consistent.
> 
> Want to confirm with you: the fix in this patch is fine with your, right?

No, it's not fine.  You are removing an optimisation.  The issue is the
other side of things where a node is used to store a single range from 0
to ULONX_MAX pointing to NULL in a 256B node.

And, potentially, the debug dump of the tree should be more clear.

> 
> >
> >Please don't submit multiple patches to fix the same thing like this, it
> >makes it look like you are trying to pad your patch count.  I'm guessing
> >you did this to keep them logically separate, but when you completely
> >drop the entire block of code that was changed in the second patch it
> >becomes a bit much (and hard to follow, I was trying to figure out what
> >branch you were working off because it didn't look like the patch would
> >apply to my branch).
> 
> Sure, will merge it.

Merge changes like this in the future, but the second patch in this
series is wrong.

> 
> >
> >Please submit a testcase with any suspected bugs. If it is not possible
> >to do the fix first, then do them at the same time.  I often write the
> >fix for a bug, then recreate the bug in a testcase and ensure that it
> >fails without my fix.
> >
> 
> Since user won't detect the difference, so a case to see whether the root is a
> node looks good to you?

Write a test to find out if the resulting 0 - ULONG_MAX store of NULL
results in a node.  If it is in a node, then the test should fail.

> 
> >I am not sure the fixes tag is correct in the patch either, since so
> >much has changed around this.  You could test the older code to see once
> >you write a testcase.  But the bug is using a node to store 0-ULONG_MAX
> >=> NULL.
> >
> 
> So I should drop the fix tag?

Yes, it's not a bug/problem - it's just inefficient use of space when
someone tries to store 0 - ULONG_MAX, so there really isn't a reason to
backport.

Thanks,
Liam

Re: [PATCH 0/2] fix mas_new_root()

[Wei Yang]

On Tue, Oct 15, 2024 at 10:32:41PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241015 22:18]:
>> On Tue, Oct 15, 2024 at 09:25:19PM -0400, Liam R. Howlett wrote:
>> >* Liam R. Howlett <Liam.Howlett@oracle.com> [241015 20:42]:
>> >> * Wei Yang <richard.weiyang@gmail.com> [241015 19:39]:
>> >> > When overwriting the whole range with NULL, current behavior is not correct.
>> >> > 
>> >> 
>> >> This is really strange.  You have changed the code to be wrong then
>> >> removed it..  The second patch removes what you changed in the first.
>> >> 
>> >> It doesn't look right today but what you have done is also not right.
>> >
>> >Looking at this again, the code that you have changed is correct.
>> >
>> >I actually think the bug is the other way around.  If we are
>> >represnenting 0 - ULONG_MAX => NULL, then it's an empty tree and we
>> >don't need a node to store that, and shouldn't.
>> >
>> >It's also not really a bug, but a missed optimisation.  The ranges are
>> >stored correctly, we just use too much memory in one case.
>> >
>> >The dump isn't clear, but since we merge NULL entries, if there is a 0-0
>> >-> NULL and 1-ULONG_MAX => NULL, then they will be one and the same.
>> >You could change the dump code as part of your fix.
>> >
>> >It's like the init of a tree (tree->ma_root = NULL).
>> 
>> Agree with your above statement, this depends how we want to handle this. The
>> change here is to make the behavior consistent.
>> 
>> Want to confirm with you: the fix in this patch is fine with your, right?
>
>No, it's not fine.  You are removing an optimisation.  The issue is the
>other side of things where a node is used to store a single range from 0
>to ULONX_MAX pointing to NULL in a 256B node.
>
>And, potentially, the debug dump of the tree should be more clear.
>
>> 
>> >
>> >Please don't submit multiple patches to fix the same thing like this, it
>> >makes it look like you are trying to pad your patch count.  I'm guessing
>> >you did this to keep them logically separate, but when you completely
>> >drop the entire block of code that was changed in the second patch it
>> >becomes a bit much (and hard to follow, I was trying to figure out what
>> >branch you were working off because it didn't look like the patch would
>> >apply to my branch).
>> 
>> Sure, will merge it.
>
>Merge changes like this in the future, but the second patch in this
>series is wrong.
>
>> 
>> >
>> >Please submit a testcase with any suspected bugs. If it is not possible
>> >to do the fix first, then do them at the same time.  I often write the
>> >fix for a bug, then recreate the bug in a testcase and ensure that it
>> >fails without my fix.
>> >
>> 
>> Since user won't detect the difference, so a case to see whether the root is a
>> node looks good to you?
>
>Write a test to find out if the resulting 0 - ULONG_MAX store of NULL
>results in a node.  If it is in a node, then the test should fail.
>
>> 
>> >I am not sure the fixes tag is correct in the patch either, since so
>> >much has changed around this.  You could test the older code to see once
>> >you write a testcase.  But the bug is using a node to store 0-ULONG_MAX
>> >=> NULL.
>> >
>> 
>> So I should drop the fix tag?
>
>Yes, it's not a bug/problem - it's just inefficient use of space when
>someone tries to store 0 - ULONG_MAX, so there really isn't a reason to
>backport.
>

Ok, I see your preference.

So current behavior of this is not expected, right?

  mas_set_range(mas, 0, ULONG_MAX)
  mas_store(mas, NULL)

This operation to an empty tree will create a node now.

Looks like a problem?

>Thanks,
>Liam

-- 
Wei Yang
Help you, Help me

Re: [PATCH 0/2] fix mas_new_root()

[Wei Yang]

On Tue, Oct 15, 2024 at 10:32:41PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241015 22:18]:
>> On Tue, Oct 15, 2024 at 09:25:19PM -0400, Liam R. Howlett wrote:
>> >* Liam R. Howlett <Liam.Howlett@oracle.com> [241015 20:42]:
>> >> * Wei Yang <richard.weiyang@gmail.com> [241015 19:39]:
>> >> > When overwriting the whole range with NULL, current behavior is not correct.
>> >> > 
>> >> 
>> >> This is really strange.  You have changed the code to be wrong then
>> >> removed it..  The second patch removes what you changed in the first.
>> >> 
>> >> It doesn't look right today but what you have done is also not right.
>> >
>> >Looking at this again, the code that you have changed is correct.
>> >
>> >I actually think the bug is the other way around.  If we are
>> >represnenting 0 - ULONG_MAX => NULL, then it's an empty tree and we
>> >don't need a node to store that, and shouldn't.
>> >
>> >It's also not really a bug, but a missed optimisation.  The ranges are
>> >stored correctly, we just use too much memory in one case.
>> >
>> >The dump isn't clear, but since we merge NULL entries, if there is a 0-0
>> >-> NULL and 1-ULONG_MAX => NULL, then they will be one and the same.
>> >You could change the dump code as part of your fix.
>> >
>> >It's like the init of a tree (tree->ma_root = NULL).
>> 
>> Agree with your above statement, this depends how we want to handle this. The
>> change here is to make the behavior consistent.
>> 
>> Want to confirm with you: the fix in this patch is fine with your, right?
>
>No, it's not fine.  You are removing an optimisation.  The issue is the
>other side of things where a node is used to store a single range from 0
>to ULONX_MAX pointing to NULL in a 256B node.
>
>And, potentially, the debug dump of the tree should be more clear.
>
>> 
>> >
>> >Please don't submit multiple patches to fix the same thing like this, it
>> >makes it look like you are trying to pad your patch count.  I'm guessing
>> >you did this to keep them logically separate, but when you completely
>> >drop the entire block of code that was changed in the second patch it
>> >becomes a bit much (and hard to follow, I was trying to figure out what
>> >branch you were working off because it didn't look like the patch would
>> >apply to my branch).
>> 
>> Sure, will merge it.
>
>Merge changes like this in the future, but the second patch in this
>series is wrong.
>
>> 
>> >
>> >Please submit a testcase with any suspected bugs. If it is not possible
>> >to do the fix first, then do them at the same time.  I often write the
>> >fix for a bug, then recreate the bug in a testcase and ensure that it
>> >fails without my fix.
>> >
>> 
>> Since user won't detect the difference, so a case to see whether the root is a
>> node looks good to you?
>
>Write a test to find out if the resulting 0 - ULONG_MAX store of NULL
>results in a node.  If it is in a node, then the test should fail.
>

Want to confirm:

Store [0, ULONG_MAX] of NULL should result an empty tree or an single entry
represent [0, 0] as current mas_new_root()?

>> 
>> >I am not sure the fixes tag is correct in the patch either, since so
>> >much has changed around this.  You could test the older code to see once
>> >you write a testcase.  But the bug is using a node to store 0-ULONG_MAX
>> >=> NULL.
>> >
>> 
>> So I should drop the fix tag?
>
>Yes, it's not a bug/problem - it's just inefficient use of space when
>someone tries to store 0 - ULONG_MAX, so there really isn't a reason to
>backport.
>
>Thanks,
>Liam

-- 
Wei Yang
Help you, Help me