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

[Wei Yang <richard.weiyang@gmail.com>]

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