* Wei Yang <richard.weiyang@xxxxxxxxx> [241112 22:17]:
> 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.
>
> [liam: rephrase the change log]
>
> Fixes: 54a611b60590 ("Maple Tree: add new data structure")
> 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>
> Cc: <stable@xxxxxxxxxxxxxxx>
>
Reviewed-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
> ---
> v3:
> * Liam helps rephrase the change log
> * add fix tag and cc stable
> ---
> 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
>
