refine storing NULL
Subsystems (3)
v3 cover refine storing NULL
The original thread[1] thoughts it is a problem in mas_new_root(). But after discussion, this should be an improvement on storing NULL.
Patch 1/2 preparation for refine.
Patch 3 remove redundant check in mas_new_root().
Patch 4 refine mas_store_root() to improve memory efficiency and remove possible consecutive NULL slot.
Patch 5 adds a test for storing NULL.
[1]: https://lkml.kernel.org/r/[email protected]
v3:
patch 4 move the change into mas_store_root()
patch 5 move test into lib/test_maple_tree.c
Wei Yang (5):
maple_tree: print empty for an empty tree on mt_dump()
maple_tree: the return value of mas_root_expand() is not used
maple_tree: not necessary to check index/last again
maple_tree: refine mas_store_root() on storing NULL
maple_tree: add a test checking storing null
lib/maple_tree.c | 20 ++++++---- lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 103 insertions(+), 7 deletions(-)
Signature · 1 line
2.34.1
PATCH v3 1/5 maple_tree: print empty for an empty tree on mt_dump()
Currently for an empty tree, it would print:
maple_tree(0x7ffcd02c6ee0) flags 1, height 0 root (nil) 0: (nil)
This is a little misleading.
Let's print (empty) for an empty tree.
--- lib/maple_tree.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-)
lib/maple_tree.c +5 -3
@@ -7287,10 +7287,12 @@ void mt_dump(const struct maple_tree *mt, enum mt_dump_format format)pr_info ("maple_tree(%p) flags %X, height %u root %p\n" , mt, mt->ma_flags,mt_height (mt), entry); -if (!xa_is_node (entry)) -mt_dump_entry (entry,0 ,0 ,0 , format); -else if (entry) +if (xa_is_node (entry))mt_dump_node (mt, entry,0 ,mt_node_max (entry),0 , format); +else if (entry) +mt_dump_entry (entry,0 ,0 ,0 , format); +else +pr_info ("(empty)\n" ); }EXPORT_SYMBOL_GPL (mt_dump);
Signature · 1 line
2.34.1
PATCH v3 2/5 maple_tree: the return value of mas_root_expand() is not used
In reply to Wei YangNo user of the return value now, just remove it.
--- lib/maple_tree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
lib/maple_tree.c +2 -2
@@ -3398,7 +3398,7 @@ static noinline_for_kasan void mas_commit_b_node(struct ma_wr_state *wr_mas,* @mas: The maple state * @entry: The entry to store into the tree */ -static inline int mas_root_expand (struct ma_state *mas,void *entry) +static inline void mas_root_expand (struct ma_state *mas,void *entry) {void *contents =mas_root_locked (mas);enum maple_type type = maple_leaf_64;
@@ -3434,7 +3434,7 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry)ma_set_meta (node, maple_leaf_64,0 , slot);/* swap the new root into the tree */ rcu_assign_pointer (mas->tree->ma_root,mte_mk_root (mas->node)); -return slot; +return ; }static inline void mas_store_root (struct ma_state *mas,void *entry)
Signature · 1 line
2.34.1
PATCH v3 3/5 maple_tree: not necessary to check index/last again
In reply to Wei YangBefore calling mas_new_root(), the range has been checked.
--- lib/maple_tree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/maple_tree.c +1 -1
@@ -3662,7 +3662,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
Re: [PATCH v3 3/5] maple_tree: not necessary to check index/last again
Quoted 15 lines · Wei Yang
Before calling
mas_new_root(), the range has been checked.Signed-off-by Wei Yang <[email protected]>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 +0
-0
lib/maple_tree.c static inline void mas_new_root(struct ma_state *mas, void *entry) · line 3665
Quoted 5 lines
lib/maple_tree.c +1
-1@@ -3662,7 +3662,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) {
Probably good to catch anyone using this wrong with a WARN_ON_ONCE()? It also has the effect of documenting what is going on, which is always nice.
Sorry for not realising this earlier.
Quoted 6 lines
lib/maple_tree.c +0
-0mas->depth =0 ;mas_set_height (mas);rcu_assign_pointer (mas->tree->ma_root, entry);Signature · 1 line
2.34.1
Re: [PATCH v3 3/5] maple_tree: not necessary to check index/last again
Quoted 19 lines · Liam R. Howlett
Quoted 18 lines · Wei Yang
Before calling
mas_new_root(), the range has been checked.Signed-off-by Wei Yang <[email protected]>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 +0
-0@@ -3662,7 +3662,7 @@ static inline void mas_new_root(struct ma_state *mas, void *entry)void __rcu **slots;unsigned long *pivots;
Quoted 7 lines
lib/maple_tree.c static inline void mas_new_root(struct ma_state *mas, void *entry) · line 3665
Quoted 2 lines
lib/maple_tree.c +1
-1-if (!entry && !mas->index && mas->last ==ULONG_MAX ) { +if (!entry) {Probably good to catch anyone using this wrong with a
WARN_ON_ONCE()? It also has the effect of documenting what is going on, which is always nice.
Sure, will add a WARN_ON_ONCE().
Quoted 8 lines
Sorry for not realising this earlier.
Quoted 6 lines
lib/maple_tree.c +0
-0mas->depth =0 ;mas_set_height (mas);rcu_assign_pointer (mas->tree->ma_root, entry);Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
PATCH v3 4/5 maple_tree: refine mas_store_root() on storing NULL
In reply to Wei YangCurrently, when storing NULL on mas_store_root(), the behavior could be improved.
For example possible cases are:
* store NULL at any range result a new node
* store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL
* store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slot
This patch tries to improve in:
* memory efficient by setting to empty tree instead of using a node
* remove the possibility of consecutive NULL slot which will prohibit extended null in later operation
---
v3: move change into mas_store_root()
--- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)
lib/maple_tree.c +6 -1
@@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)static inline void mas_store_root (struct ma_state *mas,void *entry) { -if (likely ((mas->last !=0 ) || (mas->index !=0 ))) +if (!entry) { +void *contents =mas_root_locked (mas); + +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL ); + }else if (likely ((mas->last !=0 ) || (mas->index !=0 )))mas_root_expand (mas, entry);else if (((unsigned long ) (entry) &3 ) ==2 )
mas_root_expand(mas, entry);
Signature · 1 line
2.34.1
Re: [PATCH v3 4/5] maple_tree: refine mas_store_root() on storing NULL
Quoted 11 lines · Wei Yang
Currently, when storing NULL on
mas_store_root(), the behavior could be improved.For example possible cases are:
* store NULL at any range result a new node
* store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL
* store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slot
Quoted 6 lines
This patch tries to improve in:
* memory efficient by setting to empty tree instead of using a node
* remove the possibility of consecutive NULL slot which will prohibit extended null in later operation
I don't understand this. Do we actually store consecutive NULLs now?
This is a very odd change log for fixing an optimisation. Maybe start by explaining how we end up with a node with a single value now, then state how this code changes that?
Quoted 17 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>---
v3: move change intomas_store_root()--- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)lib/maple_tree.c +0
-0
lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3446
Quoted 9 lines
lib/maple_tree.c +5
-1@@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)static inline void mas_store_root (struct ma_state *mas,void *entry) { -if (likely ((mas->last !=0 ) || (mas->index !=0 ))) +if (!entry) { +void *contents =mas_root_locked (mas); + +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL );
You are changing what used to handle any range that wasn't 0 to handle storing NULL.
This seems really broken.
lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3447
Quoted 1 line
lib/maple_tree.c +1
-0+ }else if (likely ((mas->last !=0 ) || (mas->index !=0 )))
Isn't this exactly what you have above in the if statement?
Quoted 6 lines
lib/maple_tree.c +0
-0mas_root_expand (mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry);Signature · 1 line
2.34.1
Re: [PATCH v3 4/5] maple_tree: refine mas_store_root() on storing NULL
Quoted 55 lines · Liam R. Howlett
Quoted 11 lines · Wei Yang
Currently, when storing NULL on
mas_store_root(), the behavior could be improved.For example possible cases are:
* store NULL at any range result a new node
* store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL
* store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slotQuoted 6 lines
This patch tries to improve in:
* memory efficient by setting to empty tree instead of using a node
* remove the possibility of consecutive NULL slot which will prohibit extended null in later operation
I don't understand this. Do we actually store consecutive NULLs now?
This is a very odd change log for fixing an optimisation. Maybe start by explaining how we end up with a node with a single value now, then state how this code changes that?
Quoted 17 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>---
v3: move change intomas_store_root()--- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)lib/maple_tree.c +0
-0lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3446
Quoted 9 lines
lib/maple_tree.c +5
-1@@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)static inline void mas_store_root (struct ma_state *mas,void *entry) { -if (likely ((mas->last !=0 ) || (mas->index !=0 ))) +if (!entry) { +void *contents =mas_root_locked (mas); + +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL );You are changing what used to handle any range that wasn't 0 to handle storing NULL.
Quoted 5 lines
This seems really broken.
lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3447
Quoted 1 line
lib/maple_tree.c +1
-0+ }else if (likely ((mas->last !=0 ) || (mas->index !=0 )))Isn't this exactly what you have above in the if statement?
Oh, I see. It's the same as the line you deleted above.
Quoted 7 lines
Quoted 7 lines
lib/maple_tree.c +0
-0mas_root_expand (mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry);Signature · 1 line
2.34.1
Re: [PATCH v3 4/5] maple_tree: refine mas_store_root() on storing NULL
Quoted 56 lines · Liam R. Howlett
Quoted 55 lines · Liam R. Howlett
Quoted 11 lines · Wei Yang
Currently, when storing NULL on
mas_store_root(), the behavior could be improved.For example possible cases are:
* store NULL at any range result a new node
* store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL
* store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slotQuoted 6 lines
This patch tries to improve in:
* memory efficient by setting to empty tree instead of using a node
* remove the possibility of consecutive NULL slot which will prohibit extended null in later operation
I don't understand this. Do we actually store consecutive NULLs now?
This is a very odd change log for fixing an optimisation. Maybe start by explaining how we end up with a node with a single value now, then state how this code changes that?
Quoted 17 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>---
v3: move change intomas_store_root()--- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)lib/maple_tree.c +0
-0lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3446
Quoted 9 lines
lib/maple_tree.c +5
-1@@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)static inline void mas_store_root (struct ma_state *mas,void *entry) { -if (likely ((mas->last !=0 ) || (mas->index !=0 ))) +if (!entry) { +void *contents =mas_root_locked (mas); + +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL );You are changing what used to handle any range that wasn't 0 to handle storing NULL.
Quoted 1 line
Quoted 1 line
This seems really broken.
I understand now. You don't need to get the contents though
if (!mas->index && mas_is_ptr(mas)) will work
But it's probably faster to just assign the NULL and not check anything.
Quoted 14 lines
Quoted 4 lines
lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3447
Quoted 2 lines
lib/maple_tree.c +1
-0+ }else if (likely ((mas->last !=0 ) || (mas->index !=0 )))Isn't this exactly what you have above in the if statement?
Oh, I see. It's the same as the line you deleted above.
Quoted 7 lines
Quoted 7 lines
lib/maple_tree.c +0
-0mas_root_expand (mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry);Signature · 1 line
2.34.1
Re: [PATCH v3 4/5] maple_tree: refine mas_store_root() on storing NULL
Quoted 21 lines · Liam R. Howlett
Quoted 20 lines · Liam R. Howlett
Quoted 19 lines · Liam R. Howlett
Quoted 17 lines · Wei Yang
Currently, when storing NULL on
mas_store_root(), the behavior could be improved.For example possible cases are:
* store NULL at any range result a new node
* store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL
* store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slotThis patch tries to improve in:
* memory efficient by setting to empty tree instead of using a node
* remove the possibility of consecutive NULL slot which will prohibit extended null in later operation
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
I don't understand this. Do we actually store consecutive NULLs now?
This is a very odd change log for fixing an optimisation. Maybe start by explaining how we end up with a node with a single value now, then state how this code changes that?
Let me reply all at here.
We may have some cases to result in consecutive NULL slots now.
For example, we store NULL at range [3, 10] to an empty tree.
maple_tree(0x7fff2b797170) flags 5, height 1 root 0x615000000d0e
0-18446744073709551615: node 0x615000000d00 depth 0 type 1 parent 0x7fff2b797171 contents: (nil) 2 (nil) 10 (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 0x2
0-2: (nil)
3-10: (nil)
11-18446744073709551615: (nil)Or we first store an element to [0, 0] and then store NULL at range [2, 5]
maple_tree(0x7fff2b797170) flags 5, height 1 root 0x61500000150e
0-18446744073709551615: node 0x615000001500 depth 0 type 1 parent 0x7fff2b797171 contents: 0x7fff2b797000 0 (nil) 1 (nil) 5 (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 0x3
0: 0x7fff2b797000
1: (nil)
2-5: (nil)
6-18446744073709551615: (nil)These are the cases to be checked in new test cases in patch 5.
Maybe we can put this examples in change log for clarifying?
Quoted 30 lines
Quoted 30 lines
Quoted 30 lines
Quoted 17 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>---
v3: move change intomas_store_root()--- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)lib/maple_tree.c +0
-0lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3446
Quoted 9 lines
lib/maple_tree.c +5
-1@@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)static inline void mas_store_root (struct ma_state *mas,void *entry) { -if (likely ((mas->last !=0 ) || (mas->index !=0 ))) +if (!entry) { +void *contents =mas_root_locked (mas); + +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL );You are changing what used to handle any range that wasn't 0 to handle storing NULL.
Quoted 8 lines
Quoted 1 line
Quoted 1 line
This seems really broken.
I understand now. You don't need to get the contents though
if (!mas->index &&
mas_is_ptr(mas)) will workBut it's probably faster to just assign the NULL and not check anything.
We should at least check the new range cover [0, 0]. Otherwise it will overwrite it if it is originally a single entry tree.
This works fine:
if (!mas->index)
rcu_assign_pointer(mas->tree->ma_root, NULL);
I would change to this, if you are ok with it.
Quoted 14 lines
Quoted 14 lines
Quoted 4 lines
lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3447
Quoted 2 lines
lib/maple_tree.c +1
-0+ }else if (likely ((mas->last !=0 ) || (mas->index !=0 )))Isn't this exactly what you have above in the if statement?
Oh, I see. It's the same as the line you deleted above.
Quoted 7 lines
Quoted 7 lines
lib/maple_tree.c +0
-0mas_root_expand (mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry);Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH v3 4/5] maple_tree: refine mas_store_root() on storing NULL
Quoted 43 lines · Wei Yang
Quoted 21 lines · Liam R. Howlett
Quoted 20 lines · Liam R. Howlett
Quoted 19 lines · Liam R. Howlett
Quoted 17 lines · Wei Yang
Currently, when storing NULL on
mas_store_root(), the behavior could be improved.For example possible cases are:
* store NULL at any range result a new node
* store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL
* store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slotThis patch tries to improve in:
* memory efficient by setting to empty tree instead of using a node
* remove the possibility of consecutive NULL slot which will prohibit extended null in later operation
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
I don't understand this. Do we actually store consecutive NULLs now?
This is a very odd change log for fixing an optimisation. Maybe start by explaining how we end up with a node with a single value now, then state how this code changes that?
Let me reply all at here.
We may have some cases to result in consecutive NULL slots now.
For example, we store NULL at range [3, 10] to an empty tree.
maple_tree(0x7fff2b797170)flags 5, height 1 root0x615000000d0e
0-18446744073709551615: node0x615000000d00depth 0 type 1 parent0x7fff2b797171contents: (nil) 2 (nil) 10 (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) 00x20-2: (nil) 3-10: (nil) 11-18446744073709551615: (nil)Or we first store an element to [0, 0] and then store NULL at range [2, 5]
Quoted 8 lines
maple_tree(0x7fff2b797170)flags 5, height 1 root0x61500000150e
0-18446744073709551615: node0x615000001500depth 0 type 1 parent0x7fff2b797171contents:0x7fff2b7970000 (nil) 1 (nil) 5 (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 00x30: 0x7fff2b797000 1: (nil) 2-5: (nil) 6-18446744073709551615: (nil)These are the cases to be checked in new test cases in patch 5.
Oh. This needs to be backported.
Quoted 2 lines
Maybe we can put this examples in change log for clarifying?
No, state that mas_store_root() allows for multiple NULL entries by expanding root to store NULLs to an empty tree.
Quoted 43 lines
Quoted 31 lines
Quoted 31 lines
Quoted 31 lines
Quoted 18 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>---
v3: move change intomas_store_root()--- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)lib/maple_tree.c +0
-0lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3446
Quoted 9 lines
lib/maple_tree.c +5
-1@@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)static inline void mas_store_root (struct ma_state *mas,void *entry) { -if (likely ((mas->last !=0 ) || (mas->index !=0 ))) +if (!entry) { +void *contents =mas_root_locked (mas); + +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL );You are changing what used to handle any range that wasn't 0 to handle storing NULL.
Quoted 8 lines
Quoted 1 line
Quoted 1 line
This seems really broken.
I understand now. You don't need to get the contents though
if (!mas->index &&
mas_is_ptr(mas)) will workBut it's probably faster to just assign the NULL and not check anything.
We should at least check the new range cover [0, 0]. Otherwise it will overwrite it if it is originally a single entry tree.
Quoted 6 lines
This works fine:
if (!mas->index)
rcu_assign_pointer(mas->tree->ma_root, NULL);I would change to this, if you are ok with it.
This makes sense. Maybe we need a comment about what mas_store_root() means? That is, there is no root node and we are storing a value into the root - this function either assigns the pointer or expands into a node.
Then when people see the above, we can say either we are storing NULL to an existing NULL or overwriting an value at 0, so just write it if it's overwriting index 0.
Quoted 20 lines
Quoted 15 lines
Quoted 15 lines
Quoted 5 lines
lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3447
Quoted 3 lines
lib/maple_tree.c +1
-0+ }else if (likely ((mas->last !=0 ) || (mas->index !=0 )))Isn't this exactly what you have above in the if statement?
Oh, I see. It's the same as the line you deleted above.
Quoted 7 lines
Quoted 7 lines
lib/maple_tree.c +0
-0mas_root_expand (mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry);Signature · 1 line
2.34.1Signature · 2 lines
Wei Yang Help you, Help me
Re: [PATCH v3 4/5] maple_tree: refine mas_store_root() on storing NULL
Quoted 112 lines · Liam R. Howlett
Quoted 43 lines · Wei Yang
Quoted 21 lines · Liam R. Howlett
Quoted 20 lines · Liam R. Howlett
Quoted 19 lines · Liam R. Howlett
Quoted 17 lines · Wei Yang
Currently, when storing NULL on
mas_store_root(), the behavior could be improved.For example possible cases are:
* store NULL at any range result a new node
* store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL
* store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slotThis patch tries to improve in:
* memory efficient by setting to empty tree instead of using a node
* remove the possibility of consecutive NULL slot which will prohibit extended null in later operation
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
I don't understand this. Do we actually store consecutive NULLs now?
This is a very odd change log for fixing an optimisation. Maybe start by explaining how we end up with a node with a single value now, then state how this code changes that?
Let me reply all at here.
We may have some cases to result in consecutive NULL slots now.
For example, we store NULL at range [3, 10] to an empty tree.
maple_tree(0x7fff2b797170)flags 5, height 1 root0x615000000d0e
0-18446744073709551615: node0x615000000d00depth 0 type 1 parent0x7fff2b797171contents: (nil) 2 (nil) 10 (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) 00x20-2: (nil) 3-10: (nil) 11-18446744073709551615: (nil)Or we first store an element to [0, 0] and then store NULL at range [2, 5]
Quoted 8 lines
maple_tree(0x7fff2b797170)flags 5, height 1 root0x61500000150e
0-18446744073709551615: node0x615000001500depth 0 type 1 parent0x7fff2b797171contents:0x7fff2b7970000 (nil) 1 (nil) 5 (nil) 18446744073709551615 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 0 (nil) 00x30: 0x7fff2b797000 1: (nil) 2-5: (nil) 6-18446744073709551615: (nil)These are the cases to be checked in new test cases in patch 5.
Oh. This needs to be backported.
Quoted 2 lines
Maybe we can put this examples in change log for clarifying?
No, state that
mas_store_root()allows for multiple NULL entries by expanding root to store NULLs to an empty tree.Quoted 43 lines
Quoted 31 lines
Quoted 31 lines
Quoted 31 lines
Quoted 18 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>---
v3: move change intomas_store_root()--- lib/maple_tree.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-)lib/maple_tree.c +0
-0lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3446
Quoted 9 lines
lib/maple_tree.c +5
-1@@ -3439,7 +3439,11 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)static inline void mas_store_root (struct ma_state *mas,void *entry) { -if (likely ((mas->last !=0 ) || (mas->index !=0 ))) +if (!entry) { +void *contents =mas_root_locked (mas); + +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL );You are changing what used to handle any range that wasn't 0 to handle storing NULL.
Quoted 8 lines
Quoted 1 line
Quoted 1 line
This seems really broken.
I understand now. You don't need to get the contents though
if (!mas->index &&
mas_is_ptr(mas)) will workBut it's probably faster to just assign the NULL and not check anything.
We should at least check the new range cover [0, 0]. Otherwise it will overwrite it if it is originally a single entry tree.
Quoted 6 lines
This works fine:
if (!mas->index)
rcu_assign_pointer(mas->tree->ma_root, NULL);I would change to this, if you are ok with it.
Quoted 9 lines
This makes sense. Maybe we need a comment about what
mas_store_root()means? That is, there is no root node and we are storing a value into the root - this function either assigns the pointer or expands into a node.Then when people see the above, we can say either we are storing NULL to an existing NULL or overwriting an value at 0, so just write it if it's overwriting index 0.
I have spin another round.
If I miss or misunderstand you, just let me know.
Signature · 2 lines
Wei Yang Help you, Help me
PATCH v3 5/5 maple_tree: add a test checking storing null
In reply to Wei YangAdd a test to assert that, when storing null to am empty tree or a single entry tree it will not result into:
* a root node with range [0, ULONG_MAX] set to NULL
* a root node with consecutive slot set to NULL
---
v3: move test into lib/test_maple_tree.c
--- lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 90 insertions(+)
lib/test_maple_tree.c +90 -0
@@ -1387,6 +1387,92 @@ static noinline void __init check_prev_entry(struct maple_tree *mt)mas_unlock (&mas); } +static noinline void __init check_store_null(struct maple_tree *mt) +{ +MA_STATE (mas, mt,0 ,ULONG_MAX ); + +/* +* Store NULL at range [0, ULONG_MAX] to an empty tree should result +* in an empty tree +*/ +mt_init_flags (mt,MT_FLAGS_ALLOC_RANGE ); +mas_lock (&mas); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mas_unlock (&mas); +mtree_destroy (mt); + +/* +* Store NULL at any range to an empty tree should result in an empty +* tree +*/ +mt_init_flags (mt,MT_FLAGS_ALLOC_RANGE ); +mas_lock (&mas); +mas_set_range (&mas,3 ,10 ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mas_unlock (&mas); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a single entry tree should +* result in an empty tree +*/ +mt_init_flags (mt,MT_FLAGS_ALLOC_RANGE ); +mas_lock (&mas); +mas_set (&mas,0 ); +mas_store_gfp (&mas, &mas,GFP_KERNEL ); +mas_set_range (&mas,0 ,ULONG_MAX ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mas_unlock (&mas); +mtree_destroy (mt); + +/* +* Store NULL at range [0, n] to a single entry tree should +* result in an empty tree +*/ +mt_init_flags (mt,MT_FLAGS_ALLOC_RANGE ); +mas_lock (&mas); +mas_set (&mas,0 ); +mas_store_gfp (&mas, &mas,GFP_KERNEL ); +mas_set_range (&mas,0 ,5 ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mas_unlock (&mas); +mtree_destroy (mt); + +/* +* Store NULL at range [m, n] where m > 0 to a single entry tree +* should still be a single entry tree +*/ +mt_init_flags (mt,MT_FLAGS_ALLOC_RANGE ); +mas_lock (&mas); +mas_set (&mas,0 ); +mas_store_gfp (&mas, &mas,GFP_KERNEL ); +mas_set_range (&mas,2 ,5 ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt,mtree_empty (mt)); +MT_BUG_ON (mt,xa_is_node (mt->ma_root)); +mas_unlock (&mas); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a tree with node should +* result in an empty tree +*/ +mt_init_flags (mt,MT_FLAGS_ALLOC_RANGE ); +mas_lock (&mas); +mas_set_range (&mas,1 ,3 ); +mas_store_gfp (&mas, &mas,GFP_KERNEL ); +MT_BUG_ON (mt, !xa_is_node (mt->ma_root)); +mas_set_range (&mas,0 ,ULONG_MAX ); +mas_store_gfp (&mas,NULL ,GFP_KERNEL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mas_unlock (&mas); +mtree_destroy (mt); +} + static noinline void __init check_root_expand(struct maple_tree *mt) {MA_STATE (mas, mt,0 ,0 );
@@ -3710,6 +3796,10 @@ static int __init maple_tree_seed(void) goto skip;#endif +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE ); +check_store_null (&tree); +mtree_destroy (&tree); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE );check_root_expand (&tree);mtree_destroy (&tree);
Signature · 1 line
2.34.1
Quoted 11 lines · Wei Yang
The original thread[1] thoughts it is a problem in
mas_new_root(). But after discussion, this should be an improvement on storing NULL.Patch 1/2 preparation for refine.
Patch 3 remove redundant check in
mas_new_root().Patch 4 refine
mas_store_root()to improve memory efficiency and remove possible consecutive NULL slot.Patch 5 adds a test for storing NULL.
This series fails to apply to akpm/mm-unstable today.
What are you based off?
Quoted 21 lines
[1]: https://lkml.kernel.org/r/[email protected]
v3:
patch 4 move the change intomas_store_root()
patch 5 move test intolib/test_maple_tree.cWei Yang (5):
maple_tree: print empty for an empty tree onmt_dump()
maple_tree: the return value ofmas_root_expand()is not used
maple_tree: not necessary to check index/last again
maple_tree: refinemas_store_root()on storing NULL
maple_tree: add a test checking storing nulllib/maple_tree.c | 20 ++++++---- lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 103 insertions(+), 7 deletions(-)Signature · 1 line
2.34.1
Quoted 8 lines · Liam R. Howlett
Quoted 7 lines · Wei Yang
The original thread[1] thoughts it is a problem in
mas_new_root(). But after discussion, this should be an improvement on storing NULL.Patch 1/2 preparation for refine.
Patch 3 remove redundant check in
mas_new_root().
Quoted 9 lines
Quoted 4 lines
Patch 4 refine
mas_store_root()to improve memory efficiency and remove possible consecutive NULL slot.Patch 5 adds a test for storing NULL.
This series fails to apply to akpm/mm-unstable today.
What are you based off?
I based on yesterday's master
4d939780b705 2024-10-17 Merge tag 'mm-hotfixes-stable-2024-10-17-16-08' of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Do you prefer to based on latest akpm/mm-unstable in the following spin?
Quoted 21 lines
Quoted 21 lines
[1]: https://lkml.kernel.org/r/[email protected]
v3:
patch 4 move the change intomas_store_root()
patch 5 move test intolib/test_maple_tree.cWei Yang (5):
maple_tree: print empty for an empty tree onmt_dump()
maple_tree: the return value ofmas_root_expand()is not used
maple_tree: not necessary to check index/last again
maple_tree: refinemas_store_root()on storing NULL
maple_tree: add a test checking storing nulllib/maple_tree.c | 20 ++++++---- lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 103 insertions(+), 7 deletions(-)Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me