[PATCH v5 0/5] refine storing null

[PATCH v5 0/5] refine storing null

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

[1]: https://lkml.kernel.org/r/20241015233909.23592-1-richard.weiyang@gmail.com

v5:
  rebase on akpm mm-unstable
  fix a build warning on xa_is_node() in patch 5

v4:
  patch 3 add a WARN_ON_ONCE()
  patch 4 add a comment and simplify the logic a little

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      | 29 ++++++++++----
 lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 112 insertions(+), 7 deletions(-)

-- 
2.34.1

[PATCH v5 1/5] maple_tree: print empty for an empty tree on mt_dump()

[Wei Yang]

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.

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>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 38aa8abf8eb8..523355fb2bbe 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7273,10 +7273,12 @@ void mt_dump(const struct maple_tree *mt, enum mt_dump_format format)
 
 	pr_info("maple_tree(" PTR_FMT ") flags %X, height %u root " PTR_FMT "\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);
 
-- 
2.34.1

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

[Wei Yang]

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

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>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 523355fb2bbe..071d3055f1fa 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3408,7 +3408,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;
@@ -3444,7 +3444,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)
-- 
2.34.1

[PATCH v5 3/5] 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>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

---
v4: add WARN_ON_ONCE() to check mis-usage.
---
 lib/maple_tree.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 071d3055f1fa..4900f182e99d 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3670,7 +3670,9 @@ 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) {
+	WARN_ON_ONCE(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 v5 4/5] maple_tree: refine mas_store_root() on storing NULL

[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
  * it allows for multiple NULL entries by expanding root
    to store NULLs to an empty tree

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

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>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

---
v3: move change into mas_store_root()
v4: add a comment and simplify the logic a little
    adjust the change log a little
---
 lib/maple_tree.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4900f182e99d..d0ae808f3a14 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3447,9 +3447,20 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
 	return;
 }
 
+/*
+ * mas_store_root() - Storing value into root.
+ * @mas: The maple state
+ * @entry: The entry to store.
+ *
+ * There is no root node now and we are storing a value into the root - this
+ * function either assigns the pointer or expands into a node.
+ */
 static inline void mas_store_root(struct ma_state *mas, void *entry)
 {
-	if (likely((mas->last != 0) || (mas->index != 0)))
+	if (!entry) {
+		if (!mas->index)
+			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);
-- 
2.34.1

Re: [PATCH v5 4/5] maple_tree: refine mas_store_root() on storing NULL

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241031 19:17]:
> Currently, when storing NULL on mas_store_root(), the behavior could be
> improved.

Storing NULLs over the entire tree may result in a node being used to
store a single range.  Further stores of NULL may cause the node and
tree to be corrupt and cause incorrect behaviour.  Fixing the store to
the root null fixes the issue by ensuring that a range of 0 - ULONG_MAX
results in an empty tree.

Users of the tree may experience incorrect values returned if the tree
was expanded to store values, then overwritten by all NULLS, then
continued to store NULLs over the empty area.

> 
> 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
>   * it allows for multiple NULL entries by expanding root
>     to store NULLs to an empty tree
> 
> 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
> 
> 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>
> Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

Please add stable to Cc list, and fixes tag.  This needs to be
backported, probably to v6.1

> 
> ---
> v3: move change into mas_store_root()
> v4: add a comment and simplify the logic a little
>     adjust the change log a little
> ---
>  lib/maple_tree.c | 13 ++++++++++++-
>  1 file changed, 12 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 4900f182e99d..d0ae808f3a14 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -3447,9 +3447,20 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry)
>  	return;
>  }
>  
> +/*
> + * mas_store_root() - Storing value into root.
> + * @mas: The maple state
> + * @entry: The entry to store.
> + *
> + * There is no root node now and we are storing a value into the root - this
> + * function either assigns the pointer or expands into a node.
> + */
>  static inline void mas_store_root(struct ma_state *mas, void *entry)
>  {
> -	if (likely((mas->last != 0) || (mas->index != 0)))
> +	if (!entry) {
> +		if (!mas->index)
> +			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);
> -- 
> 2.34.1
> 

Re: [PATCH v5 4/5] maple_tree: refine mas_store_root() on storing NULL

[Andrew Morton]

On Fri, 1 Nov 2024 10:59:24 -0400 "Liam R. Howlett" <Liam.Howlett@oracle.com> wrote:

> * Wei Yang <richard.weiyang@gmail.com> [241031 19:17]:
> > Currently, when storing NULL on mas_store_root(), the behavior could be
> > improved.
> 
> Storing NULLs over the entire tree may result in a node being used to
> store a single range.  Further stores of NULL may cause the node and
> tree to be corrupt and cause incorrect behaviour.  Fixing the store to
> the root null fixes the issue by ensuring that a range of 0 - ULONG_MAX
> results in an empty tree.
> 
> Users of the tree may experience incorrect values returned if the tree
> was expanded to store values, then overwritten by all NULLS, then
> continued to store NULLs over the empty area.

I pasted that into the changelog.

> > 
> > 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
> >   * it allows for multiple NULL entries by expanding root
> >     to store NULLs to an empty tree
> > 
> > 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
> > 
> > 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>
> > Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
> 
> Please add stable to Cc list, and fixes tag.  This needs to be
> backported, probably to v6.1

I added

Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Cc: <stable@vger.kernel.org>

[PATCH v5 5/5] maple_tree: add a test checking storing null

[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

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>
Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

---
v3: move test into lib/test_maple_tree.c
v5: fix a build warning on xa_is_node()
---
 lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 31561e0e1a0d..6f76093170bb 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -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(mas_root(&mas)));
+	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(mas_root(&mas)));
+	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);
-- 
2.34.1

Re: [PATCH v5 5/5] maple_tree: add a test checking storing null

[Andrew Morton]

On Thu, 31 Oct 2024 23:16:27 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:

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

I don't get it.

> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -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);
> +
>
> ...
>
> +	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
> ...
>

mas_root() is private to lib/maple_tree.c.  I'll do this for now:

--- a/lib/test_maple_tree.c~maple_tree-add-a-test-checking-storing-null-fix
+++ a/lib/test_maple_tree.c
@@ -1453,7 +1453,7 @@ static noinline void __init check_store_
 	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(mas_root(&mas)));
+//	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
 	mas_unlock(&mas);
 	mtree_destroy(mt);
 
@@ -1465,7 +1465,7 @@ static noinline void __init check_store_
 	mas_lock(&mas);
 	mas_set_range(&mas, 1, 3);
 	mas_store_gfp(&mas, &mas, GFP_KERNEL);
-	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
+//	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
 	mas_set_range(&mas, 0, ULONG_MAX);
 	mas_store_gfp(&mas, NULL, GFP_KERNEL);
 	MT_BUG_ON(mt, !mtree_empty(mt));
_

Re: [PATCH v5 5/5] maple_tree: add a test checking storing null

[Wei Yang]

On Thu, Oct 31, 2024 at 08:37:57PM -0700, Andrew Morton wrote:
>On Thu, 31 Oct 2024 23:16:27 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
>
>> 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
>> 
>
>I don't get it.
>

For example, if we store NULL to [3, 10] currently, we will have a root node
like this.

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)

Slot 0, 1 is consecutively set to NULL. This is not expected.

>> --- a/lib/test_maple_tree.c
>> +++ b/lib/test_maple_tree.c
>> @@ -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);
>> +
>>
>> ...
>>
>> +	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
>> ...
>>
>
>mas_root() is private to lib/maple_tree.c.  I'll do this for now:

Oh, thanks.

>
>--- a/lib/test_maple_tree.c~maple_tree-add-a-test-checking-storing-null-fix
>+++ a/lib/test_maple_tree.c
>@@ -1453,7 +1453,7 @@ static noinline void __init check_store_
> 	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(mas_root(&mas)));
>+//	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
> 	mas_unlock(&mas);
> 	mtree_destroy(mt);
> 
>@@ -1465,7 +1465,7 @@ static noinline void __init check_store_
> 	mas_lock(&mas);
> 	mas_set_range(&mas, 1, 3);
> 	mas_store_gfp(&mas, &mas, GFP_KERNEL);
>-	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
>+//	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
> 	mas_set_range(&mas, 0, ULONG_MAX);
> 	mas_store_gfp(&mas, NULL, GFP_KERNEL);
> 	MT_BUG_ON(mt, !mtree_empty(mt));
>_

-- 
Wei Yang
Help you, Help me

Re: [PATCH v5 0/5] refine storing null

[Andrew Morton]

On Thu, 31 Oct 2024 23:16:22 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:

> The original thread[1] thoughts it is a problem in mas_new_root(). But after
> discussion, this should be an improvement on storing NULL.

I hate to be a bureaucrat, but that isn't a very satisfying [0/N].

> 
> [1]: https://lkml.kernel.org/r/20241015233909.23592-1-richard.weiyang@gmail.com

From here I extracted "When overwriting the whole range with NULL,
current behavior is not correct", but that's still very thin.  What is
incorrect about it and what is the impact of all of this to Linux users?

Re: [PATCH v5 0/5] refine storing null

[Liam R. Howlett]

* Andrew Morton <akpm@linux-foundation.org> [241101 09:54]:
> On Thu, 31 Oct 2024 23:16:22 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
> 
> > The original thread[1] thoughts it is a problem in mas_new_root(). But after
> > discussion, this should be an improvement on storing NULL.
> 
> I hate to be a bureaucrat, but that isn't a very satisfying [0/N].
> 
> > 
> > [1]: https://lkml.kernel.org/r/20241015233909.23592-1-richard.weiyang@gmail.com
> 
> From here I extracted "When overwriting the whole range with NULL,
> current behavior is not correct", but that's still very thin.  What is
> incorrect about it and what is the impact of all of this to Linux users?
> 

An empty tree is represented by having the tree point to NULL directly.
An empty tree indicates the entire range (0-ULONG_MAX) is NULL.

A store operation into an existing node that causes 0 - ULONG_MAX to be
equal to NULL may not be restored to an empty state - a node is used to
store the single range instead.  This is wasteful and different from the
initial setup of the tree.

Once the tree is using a single node to store 0 - ULONG_MAX, problems
may arise when storing more values into a tree with the unexpected state
of 0 - ULONG being a single range in a node.

User visible issues may mean a corrupt tree and incorrect storage of
information within the tree.  This would be limited to users who create
and then empty a tree by overwriting all values, then try to store more
NULLs into the empty tree.

I cannot come up with an example of any user doing this (users usually
destroy the tree and generally don't keep trying to store NULLs over
NULLs), but patch 4/5 "maple_tree: refine mas_store_root() on storing
NULL" should be backported just in case.

I said patch 4/5 needed to be backported in v3 [1], but stable didn't
get added to the Cc list and I missed it on review of v4.  I added to
the confusion by stating in an earlier version that it did not need to
be backported [2].  At the time the issue of corrupting the node wasn't
in the description. It should go back to v6.1.

I will be more clear in my communication on Cc'ing stable in the future.
The description of 4/5 is inadequate and I'll respond there as well.

[1] https://lore.kernel.org/all/jo4wjti235pqmzd6qaziexzjsavt53vmtyzyvw4htrcwpuxf4n@ctyucxk5avrc/
[2] https://lore.kernel.org/all/ia7qdjv5c5hmg6yds3tz2x5to5u65k47ssgudiayxjqrowu4fm@i5la2j7kpe5k/

Thanks,
Liam

Re: [PATCH v5 0/5] refine storing null

[Wei Yang]

On Fri, Nov 01, 2024 at 10:52:42AM -0400, Liam R. Howlett wrote:
>* Andrew Morton <akpm@linux-foundation.org> [241101 09:54]:
>> On Thu, 31 Oct 2024 23:16:22 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
>> 
>> > The original thread[1] thoughts it is a problem in mas_new_root(). But after
>> > discussion, this should be an improvement on storing NULL.
>> 
>> I hate to be a bureaucrat, but that isn't a very satisfying [0/N].
>> 
>> > 
>> > [1]: https://lkml.kernel.org/r/20241015233909.23592-1-richard.weiyang@gmail.com
>> 
>> From here I extracted "When overwriting the whole range with NULL,
>> current behavior is not correct", but that's still very thin.  What is
>> incorrect about it and what is the impact of all of this to Linux users?
>> 
>
>An empty tree is represented by having the tree point to NULL directly.
>An empty tree indicates the entire range (0-ULONG_MAX) is NULL.
>
>A store operation into an existing node that causes 0 - ULONG_MAX to be
>equal to NULL may not be restored to an empty state - a node is used to
>store the single range instead.  This is wasteful and different from the
>initial setup of the tree.
>
>Once the tree is using a single node to store 0 - ULONG_MAX, problems
>may arise when storing more values into a tree with the unexpected state
>of 0 - ULONG being a single range in a node.
>
>User visible issues may mean a corrupt tree and incorrect storage of
>information within the tree.  This would be limited to users who create
>and then empty a tree by overwriting all values, then try to store more
>NULLs into the empty tree.

Thanks for the detailed explanation.

>
>I cannot come up with an example of any user doing this (users usually
>destroy the tree and generally don't keep trying to store NULLs over
>NULLs), but patch 4/5 "maple_tree: refine mas_store_root() on storing
>NULL" should be backported just in case.
>
>I said patch 4/5 needed to be backported in v3 [1], but stable didn't
>get added to the Cc list and I missed it on review of v4.  I added to
>the confusion by stating in an earlier version that it did not need to
>be backported [2].  At the time the issue of corrupting the node wasn't
>in the description. It should go back to v6.1.
>
>I will be more clear in my communication on Cc'ing stable in the future.
>The description of 4/5 is inadequate and I'll respond there as well.

I will be more careful for this next time.

>
>[1] https://lore.kernel.org/all/jo4wjti235pqmzd6qaziexzjsavt53vmtyzyvw4htrcwpuxf4n@ctyucxk5avrc/
>[2] https://lore.kernel.org/all/ia7qdjv5c5hmg6yds3tz2x5to5u65k47ssgudiayxjqrowu4fm@i5la2j7kpe5k/
>
>Thanks,
>Liam

-- 
Wei Yang
Help you, Help me