refine storing NULL
Subsystems (4)
v2 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_root_expand() 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]
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_root_expand() on storing NULL
maple_tree: add a test checking storing null
lib/maple_tree.c | 32 +++++++++++--- tools/testing/radix-tree/maple.c | 73 ++++++++++++++++++++++++++++++++ 2 files changed, 99 insertions(+), 6 deletions(-)
Signature · 1 line
2.34.1
PATCH v2 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
@@ -7204,10 +7204,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 v2 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
@@ -3326,7 +3326,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;
@@ -3362,7 +3362,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 v2 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
@@ -3591,7 +3591,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
PATCH v2 4/5 maple_tree: refine mas_root_expand() on storing NULL
In reply to Wei YangCurrently, when storing NULL on mas_root_expand(), 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
--- lib/maple_tree.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+)
lib/maple_tree.c +18 -0
@@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)unsigned long *pivots;int slot =0 ; +if (!entry) { +/* +* We come here in two cases: +* 1. This is an empty tree +* 2. This is a single entry tree with range [0, 0] +* +* If this is an empty tree, the result should still be an +* empty tree no matter what the range is. +* +* If this is a single entry tree, we should set it to an +* empty tree if the range cover [0, 0]. Otherwise, we don't +* need to change it. +*/ +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL ); +return ; + } + node =mas_pop_node (mas); pivots =ma_pivots (node, type); slots =ma_slots (node, type);
Signature · 1 line
2.34.1
Re: [PATCH v2 4/5] maple_tree: refine mas_root_expand() on storing NULL
Quoted 41 lines · Wei Yang
Currently, when storing NULL on
mas_root_expand(), 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 operationSigned-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 | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+)lib/maple_tree.c +8
-0@@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)unsigned long *pivots;int slot =0 ; +if (!entry) { +/* +* We come here in two cases: +* 1. This is an empty tree +* 2. This is a single entry tree with range [0, 0] +* +* If this is an empty tree, the result should still be an +* empty tree no matter what the range is.
lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3355
Quoted 10 lines
lib/maple_tree.c +10
-0+* +* If this is a single entry tree, we should set it to an +* empty tree if the range cover [0, 0]. Otherwise, we don't +* need to change it. +*/ +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL ); +return ; + } +
This fix should be done in mas_store_root(), which will probably reduce or remove your lengthy comment.
mas_root_expand() should... expand the root, and this isn't what is happening now.
Quoted 6 lines
lib/maple_tree.c +0
-0node =mas_pop_node (mas); pivots =ma_pivots (node, type); slots =ma_slots (node, type);Signature · 1 line
2.34.1
Re: [PATCH v2 4/5] maple_tree: refine mas_root_expand() on storing NULL
Quoted 56 lines · Liam R. Howlett
Quoted 41 lines · Wei Yang
Currently, when storing NULL on
mas_root_expand(), 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 operationSigned-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 | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+)lib/maple_tree.c +8
-0@@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)unsigned long *pivots;int slot =0 ; +if (!entry) { +/* +* We come here in two cases: +* 1. This is an empty tree +* 2. This is a single entry tree with range [0, 0] +* +* If this is an empty tree, the result should still be an +* empty tree no matter what the range is. lib/maple_tree.c static inline void mas_root_expand(struct ma_state *mas, void *entry) · line 3355
Quoted 10 lines
lib/maple_tree.c +10
-0+* +* If this is a single entry tree, we should set it to an +* empty tree if the range cover [0, 0]. Otherwise, we don't +* need to change it. +*/ +if (!mas->index && contents) +rcu_assign_pointer (mas->tree->ma_root,NULL ); +return ; + } +This fix should be done in
mas_store_root(), which will probably reduce or remove your lengthy comment.
Quoted 3 lines
mas_root_expand()should... expand the root, and this isn't what is happening now.
Right, will move it.
Thanks
Quoted 6 lines
Quoted 6 lines
lib/maple_tree.c +0
-0node =mas_pop_node (mas); pivots =ma_pivots (node, type); slots =ma_slots (node, type);Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me
PATCH v2 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
--- tools/testing/radix-tree/maple.c | 73 ++++++++++++++++++++++++++++++++ 1 file changed, 73 insertions(+)
tools/testing/radix-tree/maple.c +73 -0
@@ -35867,6 +35867,75 @@ static noinline void __init check_locky(struct maple_tree *mt)mt_clear_in_rcu (mt); } +static noinline void __init check_store_null(struct maple_tree *mt) +{ +MA_STATE (ms, mt,0 ,ULONG_MAX ); + +mt_set_non_kernel (10 ); + +/* +* Store NULL at range [0, ULONG_MAX] to an empty tree should result +* in an empty tree +*/ +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at any range to an empty tree should result in an empty +* tree +*/ +mas_set_range (&ms,3 ,10 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a single entry tree should +* result in an empty tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,ULONG_MAX ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, n] to a single entry tree should +* result in an empty tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,5 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [m, n] where m > 0 to a single entry tree +* should still be a single entry tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,2 ,5 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt,mtree_empty (mt)); +MT_BUG_ON (mt,xa_is_node (mt->ma_root)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a tree with node should +* result in an empty tree +*/ +mas_set_range (&ms,1 ,3 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,ULONG_MAX ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); +} +/* * Compares two nodes except for the addresses stored in the nodes. * Returns zero if they are the same, otherwise returns non-zero.
@@ -36344,6 +36413,10 @@ void farmer_tests(void) node->parent =ma_parent_ptr (node);ma_free_rcu (node); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE ); +check_store_null (&tree); +mtree_destroy (&tree); +/* Check things that will make lockdep angry */ mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE );check_locky (&tree);
Signature · 1 line
2.34.1
Re: [PATCH v2 5/5] maple_tree: add a test checking storing null
Quoted 5 lines · Wei Yang
Add 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
Is there any reason this isn't in lib/test_maple_tree.c ?
Does it need internal interfaces at all?
Quoted 103 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- tools/testing/radix-tree/maple.c | 73 ++++++++++++++++++++++++++++++++ 1 file changed, 73 insertions(+)tools/testing/radix-tree/maple.c +73
-0@@ -35867,6 +35867,75 @@ static noinline void __init check_locky(struct maple_tree *mt)mt_clear_in_rcu (mt); } +static noinline void __init check_store_null(struct maple_tree *mt) +{ +MA_STATE (ms, mt,0 ,ULONG_MAX ); + +mt_set_non_kernel (10 ); + +/* +* Store NULL at range [0, ULONG_MAX] to an empty tree should result +* in an empty tree +*/ +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at any range to an empty tree should result in an empty +* tree +*/ +mas_set_range (&ms,3 ,10 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a single entry tree should +* result in an empty tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,ULONG_MAX ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, n] to a single entry tree should +* result in an empty tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,5 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [m, n] where m > 0 to a single entry tree +* should still be a single entry tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,2 ,5 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt,mtree_empty (mt)); +MT_BUG_ON (mt,xa_is_node (mt->ma_root)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a tree with node should +* result in an empty tree +*/ +mas_set_range (&ms,1 ,3 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,ULONG_MAX ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); +} +/* * Compares two nodes except for the addresses stored in the nodes. * Returns zero if they are the same, otherwise returns non-zero. @@ -36344,6 +36413,10 @@ void farmer_tests(void) node->parent =ma_parent_ptr (node);ma_free_rcu (node); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE ); +check_store_null (&tree); +mtree_destroy (&tree); +/* Check things that will make lockdep angry */ mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE );check_locky (&tree);Signature · 1 line
2.34.1
Re: [PATCH v2 5/5] maple_tree: add a test checking storing null
Quoted 10 lines · Liam R. Howlett
Quoted 5 lines · Wei Yang
Add 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 NULLIs there any reason this isn't in
lib/test_maple_tree.c?Does it need internal interfaces at all?
Sorry, I didn't notice this requirement.
Will move into test_maple_tree.c
Quoted 104 lines
Quoted 104 lines
Signed-off-by Wei Yang <[email protected]>CC Liam R. Howlett <[email protected]>CC Sidhartha Kumar <[email protected]>CC Lorenzo Stoakes <[email protected]>--- tools/testing/radix-tree/maple.c | 73 ++++++++++++++++++++++++++++++++ 1 file changed, 73 insertions(+)tools/testing/radix-tree/maple.c +73
-0@@ -35867,6 +35867,75 @@ static noinline void __init check_locky(struct maple_tree *mt)mt_clear_in_rcu (mt); } +static noinline void __init check_store_null(struct maple_tree *mt) +{ +MA_STATE (ms, mt,0 ,ULONG_MAX ); + +mt_set_non_kernel (10 ); + +/* +* Store NULL at range [0, ULONG_MAX] to an empty tree should result +* in an empty tree +*/ +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at any range to an empty tree should result in an empty +* tree +*/ +mas_set_range (&ms,3 ,10 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a single entry tree should +* result in an empty tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,ULONG_MAX ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, n] to a single entry tree should +* result in an empty tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,5 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); + +/* +* Store NULL at range [m, n] where m > 0 to a single entry tree +* should still be a single entry tree +*/ +mas_set (&ms,0 ); +mas_store (&ms, &ms); +mas_set_range (&ms,2 ,5 ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt,mtree_empty (mt)); +MT_BUG_ON (mt,xa_is_node (mt->ma_root)); +mtree_destroy (mt); + +/* +* Store NULL at range [0, ULONG_MAX] to a tree with node should +* result in an empty tree +*/ +mas_set_range (&ms,1 ,3 ); +mas_store (&ms, &ms); +mas_set_range (&ms,0 ,ULONG_MAX ); +mas_store (&ms,NULL ); +MT_BUG_ON (mt, !mtree_empty (mt)); +mtree_destroy (mt); +} +/* * Compares two nodes except for the addresses stored in the nodes. * Returns zero if they are the same, otherwise returns non-zero. @@ -36344,6 +36413,10 @@ void farmer_tests(void) node->parent =ma_parent_ptr (node);ma_free_rcu (node); +mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE ); +check_store_null (&tree); +mtree_destroy (&tree); +/* Check things that will make lockdep angry */ mt_init_flags (&tree,MT_FLAGS_ALLOC_RANGE );check_locky (&tree);Signature · 1 line
2.34.1
Signature · 2 lines
Wei Yang Help you, Help me