* 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);@@ -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);@@ -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);
- Usually correct, mab_mas_cp in the above call overwrites
-- 2.34.1