[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 at oracle.com> [241018 14:00]:
>> * Liam R. Howlett <Liam.Howlett at oracle.com> [241018 13:57]:
>> > * Wei Yang <richard.weiyang at 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 at gmail.com>
>> > > CC: Liam R. Howlett <Liam.Howlett at Oracle.com>
>> > > CC: Sidhartha Kumar <sidhartha.kumar at oracle.com>
>> > > CC: Lorenzo Stoakes <lorenzo.stoakes at 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