[PATCH v3 0/3] simplify split calculation

[PATCH v3 0/3] 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: add a test case to check deficient node
Patch 3: validate deficient node except for root node

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

Wei Yang (3):
  maple_tree: simplify split calculation
  maple_tree: add a test check deficient node
  maple_tree: only root node could be deficient

 lib/maple_tree.c      | 25 +++++++------------------
 lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++
 2 files changed, 35 insertions(+), 18 deletions(-)

-- 
2.34.1

[PATCH v3 1/3] maple_tree: simplify split calculation

[Wei Yang]

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

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 v3 1/3] maple_tree: simplify split calculation

[Liam R. Howlett]

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

[PATCH v3 2/3] maple_tree: add a test check deficient node

[Wei Yang]

Add a test to assert when resulting a deficient node on splitting.

We can achieve this by build a tree with two nodes. With the left
node with consecutive data from 0 and leave some room for the final
insert to locate in left node. And the right node a full node to force
the split happens on the left node.

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>
---
 lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 704cb1093ae8..72bda304b595 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -1563,6 +1563,30 @@ static noinline void __init check_root_expand(struct maple_tree *mt)
 	mas_unlock(&mas);
 }
 
+static noinline void __init check_deficient_node(struct maple_tree *mt)
+{
+	MA_STATE(mas, mt, 0, 0);
+	int count;
+
+	mas_lock(&mas);
+	for (count = 0; count < 10; count++) {
+		mas_set(&mas, count);
+		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
+	}
+
+	for (count = 20; count < 39; count++) {
+		mas_set(&mas, count);
+		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
+	}
+
+	for (count = 10; count < 12; count++) {
+		mas_set(&mas, count);
+		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
+	}
+	mas_unlock(&mas);
+	mt_validate(mt);
+}
+
 static noinline void __init check_gap_combining(struct maple_tree *mt)
 {
 	struct maple_enode *mn1, *mn2;
@@ -3796,6 +3820,10 @@ static int __init maple_tree_seed(void)
 	goto skip;
 #endif
 
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	check_deficient_node(&tree);
+	mtree_destroy(&tree);
+
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
 	check_store_null(&tree);
 	mtree_destroy(&tree);
-- 
2.34.1

Re: [PATCH v3 2/3] maple_tree: add a test check deficient node

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241112 22:17]:
> Add a test to assert when resulting a deficient node on splitting.
> 
> We can achieve this by build a tree with two nodes. With the left
> node with consecutive data from 0 and leave some room for the final
> insert to locate in left node. And the right node a full node to force
> the split happens on the left node.
> 
> 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>

> ---
>  lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++
>  1 file changed, 28 insertions(+)
> 
> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> index 704cb1093ae8..72bda304b595 100644
> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -1563,6 +1563,30 @@ static noinline void __init check_root_expand(struct maple_tree *mt)
>  	mas_unlock(&mas);
>  }
>  
> +static noinline void __init check_deficient_node(struct maple_tree *mt)
> +{
> +	MA_STATE(mas, mt, 0, 0);
> +	int count;
> +
> +	mas_lock(&mas);
> +	for (count = 0; count < 10; count++) {
> +		mas_set(&mas, count);
> +		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
> +	}
> +
> +	for (count = 20; count < 39; count++) {
> +		mas_set(&mas, count);
> +		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
> +	}
> +
> +	for (count = 10; count < 12; count++) {
> +		mas_set(&mas, count);
> +		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
> +	}
> +	mas_unlock(&mas);
> +	mt_validate(mt);
> +}
> +
>  static noinline void __init check_gap_combining(struct maple_tree *mt)
>  {
>  	struct maple_enode *mn1, *mn2;
> @@ -3796,6 +3820,10 @@ static int __init maple_tree_seed(void)
>  	goto skip;
>  #endif
>  
> +	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
> +	check_deficient_node(&tree);
> +	mtree_destroy(&tree);
> +
>  	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
>  	check_store_null(&tree);
>  	mtree_destroy(&tree);
> -- 
> 2.34.1
> 

[PATCH v3 3/3] 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>
Reviewed-by: Liam R. Howlett <Liam.Howlett@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 v3 0/3] simplify split calculation

[Liam R. Howlett]

* Wei Yang <richard.weiyang@gmail.com> [241112 22:17]:
> In version 1 [1], we found current split would result into deficient node.
> 
> By discussion, current implementation would lead to jitter problem.

I don't recall it leading to a jitter, I was concerned about that but I
don't think this leads to jitter.


> Since this
> is a rare case in real world, we decide to simplify the split calculation.
> 
> Patch 1: simplify split calculation
> Patch 2: add a test case to check deficient node
> Patch 3: validate deficient node except for root node
> 
> [1]: https://lkml.kernel.org/r/20241020024628.22469-1-richard.weiyang@gmail.com
> 
> Wei Yang (3):
>   maple_tree: simplify split calculation
>   maple_tree: add a test check deficient node
>   maple_tree: only root node could be deficient
> 
>  lib/maple_tree.c      | 25 +++++++------------------
>  lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++
>  2 files changed, 35 insertions(+), 18 deletions(-)
> 
> -- 
> 2.34.1
> 

Re: [PATCH v3 0/3] simplify split calculation

[Wei Yang]

On Wed, Nov 13, 2024 at 01:39:37PM -0500, Liam R. Howlett wrote:
>* Wei Yang <richard.weiyang@gmail.com> [241112 22:17]:
>> In version 1 [1], we found current split would result into deficient node.
>> 
>> By discussion, current implementation would lead to jitter problem.
>
>I don't recall it leading to a jitter, I was concerned about that but I
>don't think this leads to jitter.
>

Sorry for my misunderstanding.

>
>> Since this
>> is a rare case in real world, we decide to simplify the split calculation.
>> 
>> Patch 1: simplify split calculation
>> Patch 2: add a test case to check deficient node
>> Patch 3: validate deficient node except for root node
>> 
>> [1]: https://lkml.kernel.org/r/20241020024628.22469-1-richard.weiyang@gmail.com
>> 
>> Wei Yang (3):
>>   maple_tree: simplify split calculation
>>   maple_tree: add a test check deficient node
>>   maple_tree: only root node could be deficient
>> 
>>  lib/maple_tree.c      | 25 +++++++------------------
>>  lib/test_maple_tree.c | 28 ++++++++++++++++++++++++++++
>>  2 files changed, 35 insertions(+), 18 deletions(-)
>> 
>> -- 
>> 2.34.1
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH v3 0/3] simplify split calculation

[Andrew Morton]

On Wed, 13 Nov 2024 03:16:13 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:

> 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: add a test case to check deficient node
> Patch 3: validate deficient node except for root node
> 
> [1]: https://lkml.kernel.org/r/20241020024628.22469-1-richard.weiyang@gmail.com

There's nothing here which is really useful as a [0/n] overview.

Why is [1/3] being proposed for -stable?  The changelog doesn't
describe what benefit such a backport would provide to -stable users.

Re: [PATCH v3 0/3] simplify split calculation

[Liam R. Howlett]

* Andrew Morton <akpm@linux-foundation.org> [241129 23:31]:
> On Wed, 13 Nov 2024 03:16:13 +0000 Wei Yang <richard.weiyang@gmail.com> wrote:
> 
> > 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: add a test case to check deficient node
> > Patch 3: validate deficient node except for root node
> > 
> > [1]: https://lkml.kernel.org/r/20241020024628.22469-1-richard.weiyang@gmail.com
> 
> There's nothing here which is really useful as a [0/n] overview.
> 
> Why is [1/3] being proposed for -stable?  The changelog doesn't
> describe what benefit such a backport would provide to -stable users.
> 

The split calculation may cause an insufficient node in rare cases.
This could cause issues down the line for the tree during merging
operations, which would lead to wasted space at best and stability
issues at worse.  Although we haven't seen an insufficient node occur
(or at least not cause issues), it seems prudent to backport the fix to
remove the risk.

The benefit is to remove risk from tree operations by ensuring the nodes
remain in a known good (and well tested) state.

Does that seem reasonable?  I'd be happy to hear any guidance you can
provide for such issues and if you think it is worth sending to stable.

Thanks,
Liam