[PATCH 3/4] maple_tree: use the correct min to calculate split

[Wei Yang]

On Tue, Oct 29, 2024 at 01:49:28PM -0400, Liam R. Howlett wrote:
>* Liam R. Howlett <Liam.Howlett at oracle.com> [241020 18:00]:
>> * Wei Yang <richard.weiyang at gmail.com> [241019 22:46]:
>> > The check in mab_calc_split() is to make sure the gap between
>> > [0, split] won't be too small. But we don't pass the correct min.
>> > 
>> > First we may encounter a pivot[split] smaller than min. For example:
>> > 
>> >        mt_init_flags(mt, 0);
>> >        for (count = 0; count <= 240; count++) {
>> >                mas_set(&mas, count);
>> >                mas_store(&mas, xa_mk_value(count));
>> >        }
>> > 
>> > On splitting root for storing 240, the pivot[split] is smaller than min.
>> > This result a huge (pivot[split] - min).
>> 
>> This is fine.
>> 
>> There is an open work item to make it more accurate at higher levels,
>> but it's not a problem as it is.
>> 
>> Each level upwards needs a better 'minimum span', meaning that the node
>> should have at least mas.min - mas.min + level * something.
>> 
>> It works today for leaves, somewhat.
>> 
>> > 
>> > Second prev_l_mas.min is not initialized for the first iteration. This
>> > means on splitting leaf node, this value is mostly taking no effect.
>> 
>> No, it is set to 0.  Not initialized would cause random data loss.
>> 
>> See MA_STATE() in the header.
>> 
>> > 
>> > Since we are now calculating the split of mas->node, we should use the
>> > mas->min instead of prev_l_mas.min.
>> 
>> This sounds reasonable, but considering what this number is used for, I
>> don't see how it is working as well as it is today.  I will need to look
>> deeper into this.
>
>
>On examination of what is happening here, the only way this makes a
>difference during the testcases is if we have a node with 16 entries,
>we'll put 8 in the left today and 9 in the left after this change.
>
>This only matters if the range is less than the slot count, so the real
>world implications of the change will be negligible, if anything.
>

Yes, maybe it only effect when there are all singleton.

>I honestly think I'm trying to be too smart here, especially at the
>leaves.  We should just set mid_split = 0; in that complex statement and
>drop the min argument all together.  It hasn't made a difference besides
>the number of instructions executed.
>

I have tried to remove those lines, so we got split = b_end / 2 and 
mid_split = 0. Tests all passed and kernel runs. (I guess in the real world,
it behaves the same, since (bn->pivot[split] - min) is always bigger than 15.)

Since we call mab_calc_split() when b_end >= slot_count == 16, it means we
get split == 16/2 == 8. So the new left|right node has data 9|8, this is
friendly to jitter problem. 

>> 
>> > 
>> > 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>
>> > ---
>> >  lib/maple_tree.c | 2 +-
>> >  1 file changed, 1 insertion(+), 1 deletion(-)
>> > 
>> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> > index 894dc5e9436e..c2d4b188646c 100644
>> > --- a/lib/maple_tree.c
>> > +++ b/lib/maple_tree.c
>> > @@ -3357,7 +3357,7 @@ static void mas_split(struct ma_state *mas, struct maple_big_node *b_node)
>> >  		if (mas_push_data(mas, height, &mast, false))
>> >  			break;
>> >  
>> > -		split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min);
>> > +		split = mab_calc_split(mas, b_node, &mid_split, mas->min);
>> >  		mast_split_data(&mast, mas, split);
>> >  		/*
>> >  		 * Usually correct, mab_mas_cp in the above call overwrites
>> > -- 
>> > 2.34.1
>> > 

-- 
Wei Yang
Help you, Help me