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.
Maybe we can put this examples in change log for clarifying?
>> > >
>> > > 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.
>> >
>> > > + } 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
