Skip to contentSkip to conversation

refine storing NULL

PATCH Superseded Wei Yang 2 participants 10 messages Oct 17, 2024

Subsystems (4)

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Wei Yang

author
#0 lore raw

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
author
#1 lore raw

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.

CC Liam R. Howlett <[email protected]>
CC Sidhartha Kumar <[email protected]>
CC Lorenzo Stoakes <[email protected]>
---
 lib/maple_tree.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)
lib/maple_tree.c +5 -3
index db3de0b9aa9a..63a969d581f2 100644
@@ -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
author
#2 lore raw

PATCH v2 2/5 maple_tree: the return value of mas_root_expand() is not used

In reply to Wei Yang

No user of the return value now, just remove it.

CC Liam R. Howlett <[email protected]>
CC Sidhartha Kumar <[email protected]>
CC Lorenzo Stoakes <[email protected]>
---
 lib/maple_tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
lib/maple_tree.c +2 -2
index 63a969d581f2..ff9d972dba4d 100644
@@ -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
author
#3 lore raw

PATCH v2 3/5 maple_tree: not necessary to check index/last again

In reply to Wei Yang

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 ff9d972dba4d..a90c29156fe2 100644
@@ -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
author
#4 lore raw

PATCH v2 4/5 maple_tree: refine mas_root_expand() on storing NULL

In reply to 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 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

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 +18 -0
index a90c29156fe2..15d2124acc36 100644
@@ -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
#5 lore raw

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 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

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
index a90c29156fe2..15d2124acc36 100644
@@ -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 -0
 	node = mas_pop_node(mas);
 	pivots = ma_pivots(node, type);
 	slots = ma_slots(node, type);
Signature · 1 line
2.34.1
author
#6 lore raw

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 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

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
index a90c29156fe2..15d2124acc36 100644
@@ -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 -0
 	node = 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
author
#7 lore raw

PATCH v2 5/5 maple_tree: add a test checking storing null

In reply to 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

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
index 5fde09999be4..fbb08f151b01 100644
@@ -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
#8 lore raw

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
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
index 5fde09999be4..fbb08f151b01 100644
@@ -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
author
#9 lore raw

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 NULL

Is 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
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
index 5fde09999be4..fbb08f151b01 100644
@@ -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