Skip to contentSkip to conversation

fix mas_new_root()

PATCH NAK Wei Yang 2 participants 10 messages Oct 15, 2024 – Oct 16, 2024

Subsystems (3)
lore
Share & tools
lore

Wei Yang

author
#0 lore raw

cover fix mas_new_root()

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(-)
Signature · 1 line
2.34.1
author
#1 lore raw

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

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

CC Liam R. Howlett <[email protected]>
CC Sidhartha Kumar <[email protected]>
CC Lorenzo Stoakes <[email protected]>
---
 lib/maple_tree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
index 0aa9fa8fa7de..3a12866a4a89 100644
@@ -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);
Signature · 1 line
2.34.1
author
#2 lore raw

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

In reply to 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")
CC Liam R. Howlett <[email protected]>
CC Sidhartha Kumar <[email protected]>
CC Lorenzo Stoakes <[email protected]>
---
 lib/maple_tree.c | 9 ---------
 1 file changed, 9 deletions(-)
lib/maple_tree.c +0 -9
index 3a12866a4a89..5dfc589a8cde 100644
@@ -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);
 
Signature · 1 line
2.34.1
#3 lore raw

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

nack

Quoted 76 lines · 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")
CC Liam R. Howlett <[email protected]>
CC Sidhartha Kumar <[email protected]>
CC Lorenzo Stoakes <[email protected]>
---
 lib/maple_tree.c | 9 ---------
 1 file changed, 9 deletions(-)
lib/maple_tree.c +0 -9
index 3a12866a4a89..5dfc589a8cde 100644
@@ -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);
 
Signature · 1 line
2.34.1
#4 lore raw
In reply to Wei Yang
Quoted 2 lines · Wei Yang

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.

Quoted 11 lines

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(-)
Signature · 1 line
2.34.1
#5 lore raw
Quoted 8 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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.

Quoted 13 lines
Quoted 13 lines

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(-)
Signature · 1 line
2.34.1
author
#6 lore raw
Quoted 16 lines · Liam R. Howlett
Quoted 8 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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.

Quoted 8 lines

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?

Quoted 8 lines

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.

Quoted 6 lines

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?

Quoted 5 lines

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?

Quoted 13 lines
Quoted 13 lines
Quoted 13 lines

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(-)
Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang
Help you, Help me
#7 lore raw
Quoted 24 lines · Wei Yang
Quoted 23 lines · Liam R. Howlett
Quoted 8 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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.

Quoted 6 lines
Quoted 1 line

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.

Quoted 11 lines
Quoted 9 lines

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.

Quoted 10 lines
Quoted 7 lines

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.

Quoted 8 lines
Quoted 6 lines

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

author
#8 lore raw
Quoted 74 lines · Liam R. Howlett
Quoted 24 lines · Wei Yang
Quoted 23 lines · Liam R. Howlett
Quoted 8 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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.

Quoted 6 lines
Quoted 1 line

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.

Quoted 11 lines
Quoted 9 lines

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.

Quoted 10 lines
Quoted 7 lines

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.

Quoted 7 lines
Quoted 6 lines

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.

Quoted 6 lines
Quoted 1 line

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?

Quoted 2 lines

Thanks,
Liam

Signature · 2 lines
Wei Yang
Help you, Help me
author
#9 lore raw
In reply to Liam R. Howlett
Quoted 61 lines · Liam R. Howlett
Quoted 24 lines · Wei Yang
Quoted 23 lines · Liam R. Howlett
Quoted 8 lines · Liam R. Howlett
Quoted 2 lines · Wei Yang

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.

Quoted 6 lines
Quoted 1 line

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.

Quoted 11 lines
Quoted 9 lines

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.

Quoted 8 lines
Quoted 7 lines

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.

Quoted 6 lines
Quoted 2 lines

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()?

Quoted 15 lines
Quoted 8 lines
Quoted 6 lines

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

Signature · 2 lines
Wei Yang
Help you, Help me