| Message ID | 20241113031616.10530-2-richard.weiyang@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | simplify split calculation | expand |
* Wei Yang <richard.weiyang@gmail.com> [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@gmail.com> > CC: Liam R. Howlett <Liam.Howlett@Oracle.com> > CC: Sidhartha Kumar <sidhartha.kumar@oracle.com> > CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com> > Cc: <stable@vger.kernel.org> > Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com> > --- > 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 >
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
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@gmail.com> CC: Liam R. Howlett <Liam.Howlett@Oracle.com> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com> Cc: <stable@vger.kernel.org> --- 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(-)