[PATCH v2 0/2] simplify split calculation

[PATCH v2 0/2] simplify split calculation

[Wei Yang]

In version 1 [1], we found current split would result into deficient node.

By discussion, current implementation would lead to jitter problem. Since this
is a rare case in real world, we decide to simplify the split calculation.

Patch 1: simplify split calculation
Patch 2: validate deficient node except for root node

[1]: https://lkml.kernel.org/r/20241020024628.22469-1-richard.weiyang@gmail.com

Wei Yang (2):
  maple_tree: simplify split calculation
  maple_tree: only root node could be deficient

 lib/maple_tree.c | 25 +++++++------------------
 1 file changed, 7 insertions(+), 18 deletions(-)

-- 
2.34.1

[PATCH v2 1/2] maple_tree: simplify split calculation

[Wei Yang]

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.

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>

---
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

Re: [PATCH v2 1/2] maple_tree: simplify split calculation

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [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.

> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>

Fixes: ?
Cc: stable ?

> CC: Liam R. Howlett <Liam.Howlett@Oracle.com>
> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
> 
> ---
> 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
> 

Re: [PATCH v2 1/2] maple_tree: simplify split calculation

[Wei Yang]

On Tue, Nov 12, 2024 at 09:46:20AM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [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@gmail.com>
>
>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@Oracle.com>
>> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com>
>> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com>
>> 
>> ---
>> 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

Re: [PATCH v2 1/2] maple_tree: simplify split calculation

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241112 20:15]:
> On Tue, Nov 12, 2024 at 09:46:20AM -0500, Liam R. Howlett wrote:
> >* Wei Yang <richard.weiyang@gmail.com> [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@gmail.com>
> >
> >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?

Yes, please include it.

I keep all test cases from fixed bugs or added features.  This way we
know that the bug doesn't return in another unrelated change.  The
testcases continuously grow, but they are always useful.

Thanks,
Liam

[PATCH v2 2/2] maple_tree: only root node could be deficient

[Wei Yang]

Each level's right most node should have (max == ULONG_MAX). This means
current validation skips the right most node on each level.

Only the root node may be below the minimum data threshold.

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>

---
v2:
  adjust the change log
---
 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 4f2950a1c38d..667326717f35 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -7585,7 +7585,7 @@ void mt_validate(struct maple_tree *mt)
 		MAS_WARN_ON(&mas, mte_dead_node(mas.node));
 		end = mas_data_end(&mas);
 		if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) &&
-				(mas.max != ULONG_MAX))) {
+				(!mte_is_root(mas.node)))) {
 			pr_err("Invalid size %u of " PTR_FMT "\n",
 			       end, mas_mn(&mas));
 		}
-- 
2.34.1

Re: [PATCH v2 2/2] maple_tree: only root node could be deficient

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241109 08:45]:
> Each level's right most node should have (max == ULONG_MAX). This means
> current validation skips the right most node on each level.
> 
> Only the root node may be below the minimum data threshold.
> 
> 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>

Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

> 
> ---
> v2:
>   adjust the change log

Thanks

> ---
>  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 4f2950a1c38d..667326717f35 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -7585,7 +7585,7 @@ void mt_validate(struct maple_tree *mt)
>  		MAS_WARN_ON(&mas, mte_dead_node(mas.node));
>  		end = mas_data_end(&mas);
>  		if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) &&
> -				(mas.max != ULONG_MAX))) {
> +				(!mte_is_root(mas.node)))) {
>  			pr_err("Invalid size %u of " PTR_FMT "\n",
>  			       end, mas_mn(&mas));
>  		}
> -- 
> 2.34.1
>