On Tue, Nov 12, 2024 at 09:46:20AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@xxxxxxxxx> [241109 08:45]:
>> We have been too smart to calculate split value.
>>
>> The purpose of current calculation is to avoid having a range less than
>> the slot count. But this seems to push too hard to suffer from jitter
>> problem.
>>
>> Considering this only matters if the range is less than the slot count,
>> so the real world implications of the calculation will be negligible. So
>> we decide to simplify the calculation of split.
>>
>> Also current code may lead to deficient node, the condition to check
>> should be (b_end - split - 1 > slot_min). After this change, this one is
>> gone together.
>
>This comment is difficult to understand.
>
>Maybe something like:
>The current calculation for splitting nodes tries to enforce a minimum
>span on the leaf nodes. This code is complex and never worked correctly
>to begin with, due to the min value being passed as 0 for all leaves.
>
>The calculation should just split the data as equally as possible
>between the new nodes. Note that b_end will be one more than the data,
>so the left side is still favoured in the calculation.
>
>The current code may also lead to a deficient node by not leaving enough
>data for the right side of the split. This issue is also addressed with
>the split calculation change.
>
Thanks, this looks much better :-)
>>
>> Signed-off-by: Wei Yang <richard.weiyang@xxxxxxxxx>
>
>Fixes: ?
>Cc: stable ?
>
Will add this.
BTW, as this is a fix, do you think the test case in patch 2 of v1 is still
necessary?
>> CC: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
>> CC: Sidhartha Kumar <sidhartha.kumar@xxxxxxxxxx>
>> CC: Lorenzo Stoakes <lorenzo.stoakes@xxxxxxxxxx>
>>
>> ---
>> v2:
>> instead of fixing deficient split, simplify the calculation
>> ---
>> lib/maple_tree.c | 23 ++++++-----------------
>> 1 file changed, 6 insertions(+), 17 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index d0ae808f3a14..4f2950a1c38d 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -1863,11 +1863,11 @@ static inline int mab_no_null_split(struct maple_big_node *b_node,
>> * Return: The first split location. The middle split is set in @mid_split.
>> */
>> static inline int mab_calc_split(struct ma_state *mas,
>> - struct maple_big_node *bn, unsigned char *mid_split, unsigned long min)
>> + struct maple_big_node *bn, unsigned char *mid_split)
>> {
>> unsigned char b_end = bn->b_end;
>> int split = b_end / 2; /* Assume equal split. */
>> - unsigned char slot_min, slot_count = mt_slots[bn->type];
>> + unsigned char slot_count = mt_slots[bn->type];
>>
>> /*
>> * To support gap tracking, all NULL entries are kept together and a node cannot
>> @@ -1900,18 +1900,7 @@ static inline int mab_calc_split(struct ma_state *mas,
>> split = b_end / 3;
>> *mid_split = split * 2;
>> } else {
>> - slot_min = mt_min_slots[bn->type];
>> -
>> *mid_split = 0;
>> - /*
>> - * Avoid having a range less than the slot count unless it
>> - * causes one node to be deficient.
>> - * NOTE: mt_min_slots is 1 based, b_end and split are zero.
>> - */
>> - while ((split < slot_count - 1) &&
>> - ((bn->pivot[split] - min) < slot_count - 1) &&
>> - (b_end - split > slot_min))
>> - split++;
>> }
>>
>> /* Avoid ending a node on a NULL entry */
>> @@ -2377,7 +2366,7 @@ static inline struct maple_enode
>> static inline unsigned char mas_mab_to_node(struct ma_state *mas,
>> struct maple_big_node *b_node, struct maple_enode **left,
>> struct maple_enode **right, struct maple_enode **middle,
>> - unsigned char *mid_split, unsigned long min)
>> + unsigned char *mid_split)
>> {
>> unsigned char split = 0;
>> unsigned char slot_count = mt_slots[b_node->type];
>> @@ -2390,7 +2379,7 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas,
>> if (b_node->b_end < slot_count) {
>> split = b_node->b_end;
>> } else {
>> - split = mab_calc_split(mas, b_node, mid_split, min);
>> + split = mab_calc_split(mas, b_node, mid_split);
>> *right = mas_new_ma_node(mas, b_node);
>> }
>>
>> @@ -2877,7 +2866,7 @@ static void mas_spanning_rebalance(struct ma_state *mas,
>> mast->bn->b_end--;
>> mast->bn->type = mte_node_type(mast->orig_l->node);
>> split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,
>> - &mid_split, mast->orig_l->min);
>> + &mid_split);
>> mast_set_split_parents(mast, left, middle, right, split,
>> mid_split);
>> mast_cp_to_nodes(mast, left, middle, right, split, mid_split);
>> @@ -3365,7 +3354,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);
>> 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
