* Liam R. Howlett <Liam.Howlett@xxxxxxxxxx> [241020 18:00]:
> * Wei Yang <richard.weiyang@xxxxxxxxx> [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.
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.
>
> >
> > 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>
> > ---
> > 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
> >
