* Wei Yang <richard.weiyang@xxxxxxxxx> [241018 20:59]:
> On Fri, Oct 18, 2024 at 02:12:08PM -0400, Liam R. Howlett wrote:
> >* Liam R. Howlett <Liam.Howlett@xxxxxxxxxx> [241018 14:00]:
> >> * Liam R. Howlett <Liam.Howlett@xxxxxxxxxx> [241018 13:57]:
> >> > * Wei Yang <richard.weiyang@xxxxxxxxx> [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@xxxxxxxxx>
> >> > > CC: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> >> > > CC: Sidhartha Kumar <sidhartha.kumar@xxxxxxxxxx>
> >> > > CC: Lorenzo Stoakes <lorenzo.stoakes@xxxxxxxxxx>
> >> > >
> >> > > ---
> >> > > 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
>
