[PATCH v3 0/5] refine storing NULL

[PATCH v3 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

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

-- 
2.34.1

[PATCH v3 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>
---
 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 20990ecba2dd..ec746aca2510 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -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);
 
-- 
2.34.1

[PATCH v3 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>
---
 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 ec746aca2510..cbbaaf60efa9 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -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)
-- 
2.34.1

[PATCH v3 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>
---
 lib/maple_tree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index cbbaaf60efa9..db8b89487c98 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -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);
-- 
2.34.1

Re: [PATCH v3 3/5] maple_tree: not necessary to check index/last again

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
> 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>
> ---
>  lib/maple_tree.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index cbbaaf60efa9..db8b89487c98 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -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.

>  		mas->depth = 0;
>  		mas_set_height(mas);
>  		rcu_assign_pointer(mas->tree->ma_root, entry);
> -- 
> 2.34.1
> 

Re: [PATCH v3 3/5] maple_tree: not necessary to check index/last again

[Wei Yang]

On Fri, Oct 18, 2024 at 01:43:18PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
>> 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>
>> ---
>>  lib/maple_tree.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>> 
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index cbbaaf60efa9..db8b89487c98 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -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.
>

Sure, will add a WARN_ON_ONCE().

>Sorry for not realising this earlier.
>
>>  		mas->depth = 0;
>>  		mas_set_height(mas);
>>  		rcu_assign_pointer(mas->tree->ma_root, entry);
>> -- 
>> 2.34.1
>> 

-- 
Wei Yang
Help you, Help me

[PATCH v3 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

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>

---
v3: move change into mas_store_root()
---
 lib/maple_tree.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index db8b89487c98..03fbee9880eb 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -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);
-- 
2.34.1

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

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
> 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
> 
> 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?

> 
> 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>
> 
> ---
> v3: move change into mas_store_root()
> ---
>  lib/maple_tree.c | 6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index db8b89487c98..03fbee9880eb 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -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.

> +	} else if (likely((mas->last != 0) || (mas->index != 0)))

Isn't this exactly what you have above in the if statement?

>  		mas_root_expand(mas, entry);
>  	else if (((unsigned long) (entry) & 3) == 2)
>  		mas_root_expand(mas, entry);
> -- 
> 2.34.1
> 

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

[Liam R. Howlett]

* Liam R. Howlett <Liam.Howlett@oracle.com> [241018 13:57]:
> * Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
> > 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
> > 
> > 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?
> 
> > 
> > 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>
> > 
> > ---
> > v3: move change into mas_store_root()
> > ---
> >  lib/maple_tree.c | 6 +++++-
> >  1 file changed, 5 insertions(+), 1 deletion(-)
> > 
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index db8b89487c98..03fbee9880eb 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -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.
> 
> > +	} 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.

> 
> >  		mas_root_expand(mas, entry);
> >  	else if (((unsigned long) (entry) & 3) == 2)
> >  		mas_root_expand(mas, entry);
> > -- 
> > 2.34.1
> > 

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

[Liam R. Howlett]

* Liam R. Howlett <Liam.Howlett@oracle.com> [241018 14:00]:
> * Liam R. Howlett <Liam.Howlett@oracle.com> [241018 13:57]:
> > * Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
> > > 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
> > > 
> > > 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?
> > 
> > > 
> > > 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>
> > > 
> > > ---
> > > v3: move change into mas_store_root()
> > > ---
> > >  lib/maple_tree.c | 6 +++++-
> > >  1 file changed, 5 insertions(+), 1 deletion(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index db8b89487c98..03fbee9880eb 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -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.

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.

> > 
> > > +	} 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.
> 
> > 
> > >  		mas_root_expand(mas, entry);
> > >  	else if (((unsigned long) (entry) & 3) == 2)
> > >  		mas_root_expand(mas, entry);
> > > -- 
> > > 2.34.1
> > > 

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

[Wei Yang]

On Fri, Oct 18, 2024 at 02:12:08PM -0400, Liam R. Howlett wrote:
>* Liam R. Howlett <Liam.Howlett@oracle.com> [241018 14:00]:
>> * Liam R. Howlett <Liam.Howlett@oracle.com> [241018 13:57]:
>> > * Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
>> > > 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
>> > > 
>> > > 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?
>> > 

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?

>> > > 
>> > > 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>
>> > > 
>> > > ---
>> > > v3: move change into mas_store_root()
>> > > ---
>> > >  lib/maple_tree.c | 6 +++++-
>> > >  1 file changed, 5 insertions(+), 1 deletion(-)
>> > > 
>> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> > > index db8b89487c98..03fbee9880eb 100644
>> > > --- a/lib/maple_tree.c
>> > > +++ b/lib/maple_tree.c
>> > > @@ -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.
>
>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.
>

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.

>> > 
>> > > +	} 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.
>> 
>> > 
>> > >  		mas_root_expand(mas, entry);
>> > >  	else if (((unsigned long) (entry) & 3) == 2)
>> > >  		mas_root_expand(mas, entry);
>> > > -- 
>> > > 2.34.1
>> > > 

-- 
Wei Yang
Help you, Help me

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

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241018 20:59]:
> On Fri, Oct 18, 2024 at 02:12:08PM -0400, Liam R. Howlett wrote:
> >* Liam R. Howlett <Liam.Howlett@oracle.com> [241018 14:00]:
> >> * Liam R. Howlett <Liam.Howlett@oracle.com> [241018 13:57]:
> >> > * Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
> >> > > 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
> >> > > 
> >> > > 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?
> >> > 
> 
> 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.

Oh.  This needs to be backported.

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


> 
> >> > > 
> >> > > 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>
> >> > > 
> >> > > ---
> >> > > v3: move change into mas_store_root()
> >> > > ---
> >> > >  lib/maple_tree.c | 6 +++++-
> >> > >  1 file changed, 5 insertions(+), 1 deletion(-)
> >> > > 
> >> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> >> > > index db8b89487c98..03fbee9880eb 100644
> >> > > --- a/lib/maple_tree.c
> >> > > +++ b/lib/maple_tree.c
> >> > > @@ -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.
> >
> >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.
> >
> 
> 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.

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.

> 
> >> > 
> >> > > +	} 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.
> >> 
> >> > 
> >> > >  		mas_root_expand(mas, entry);
> >> > >  	else if (((unsigned long) (entry) & 3) == 2)
> >> > >  		mas_root_expand(mas, entry);
> >> > > -- 
> >> > > 2.34.1
> >> > > 
> 
> -- 
> Wei Yang
> Help you, Help me
> 

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

[Wei Yang]

On Fri, Oct 18, 2024 at 09:55:53PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241018 20:59]:
>> On Fri, Oct 18, 2024 at 02:12:08PM -0400, Liam R. Howlett wrote:
>> >* Liam R. Howlett <Liam.Howlett@oracle.com> [241018 14:00]:
>> >> * Liam R. Howlett <Liam.Howlett@oracle.com> [241018 13:57]:
>> >> > * Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
>> >> > > 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
>> >> > > 
>> >> > > 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?
>> >> > 
>> 
>> 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.
>
>Oh.  This needs to be backported.
>
>> 
>> 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.
>
>
>> 
>> >> > > 
>> >> > > 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>
>> >> > > 
>> >> > > ---
>> >> > > v3: move change into mas_store_root()
>> >> > > ---
>> >> > >  lib/maple_tree.c | 6 +++++-
>> >> > >  1 file changed, 5 insertions(+), 1 deletion(-)
>> >> > > 
>> >> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> >> > > index db8b89487c98..03fbee9880eb 100644
>> >> > > --- a/lib/maple_tree.c
>> >> > > +++ b/lib/maple_tree.c
>> >> > > @@ -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.
>> >
>> >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.
>> >
>> 
>> 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.
>
>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.

-- 
Wei Yang
Help you, Help me

[PATCH v3 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>

---
v3: move test into lib/test_maple_tree.c
---
 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..2ef72f6c6d1b 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(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);
-- 
2.34.1

Re: [PATCH v3 0/5] refine storing NULL

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
> 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?

>                                                                                                                                                                                                              
> [1]: https://lkml.kernel.org/r/20241015233909.23592-1-richard.weiyang@gmail.com
> 
> 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(-)
> 
> -- 
> 2.34.1
> 

Re: [PATCH v3 0/5] refine storing NULL

[Wei Yang]

On Fri, Oct 18, 2024 at 02:03:55PM -0400, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241017 22:40]:
>> 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?
>

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?

>>                                                                                                                                                                                                              
>> [1]: https://lkml.kernel.org/r/20241015233909.23592-1-richard.weiyang@gmail.com
>> 
>> 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(-)
>> 
>> -- 
>> 2.34.1
>> 

-- 
Wei Yang
Help you, Help me