On Fri, Oct 18, 2024 at 09:55:53PM -0400, Liam R. Howlett wrote:
>* 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.
>
I have spin another round.
If I miss or misunderstand you, just let me know.
--
Wei Yang
Help you, Help me
