FAILED: patch "[PATCH] maple_tree: simplify split calculation" failed to apply to 6.1-stable tree

PATCH [email protected] 2 participants 3 messages Feb 11, 2025 – Feb 13, 2025

Subsystems (3)

Stable branch Library code Maple tree

lore

Share & tools

lore

[email protected]

author maintainer

2025-02-11 09:48 UTC #0 lore raw

The patch below does not apply to the 6.1-stable tree.
If someone wants it applied there, or to any other stable or longterm tree, then please email the backport, including the original git commit id to <[email protected]>.

To reproduce the conflict and resubmit, you may use the following commands:

git fetch https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ linux-6.1.y
git checkout FETCH_HEAD
git cherry-pick -x 4f6a6bed0bfef4b966f076f33eb4f5547226056a
# <resolve conflicts, build, test, etc.>
git commit -s
git send-email --to '<[email protected]>' --in-reply-to '2025021128-repeater-percolate-6131@gregkh' --subject-prefix 'PATCH 6.1.y' HEAD^..

Possible dependencies:

thanks,

greg k-h

------------------ original commit in Linus's tree ------------------

From 4f6a6bed0bfef4b966f076f33eb4f5547226056a Mon Sep 17 00:00:00 2001
From: Wei Yang <[email protected]>
Date: Wed, 13 Nov 2024 03:16:14 +0000
Subject: [PATCH] maple_tree: simplify split calculation

Patch series "simplify split calculation", v3.

This patch (of 3):

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.

[[email protected]: rephrase the change log]

Link https://lkml.kernel.org/r/[email protected] open here

Fixes 54a611b60590 ("Maple Tree: add new data structure")

Signed-off-by Wei Yang <[email protected]>

Reviewed-by Liam R. Howlett <[email protected]>

Cc Sidhartha Kumar <[email protected]>

Cc Lorenzo Stoakes <[email protected]>

Cc <[email protected]>

Signed-off-by Andrew Morton <[email protected]>

lib/maple_tree.c +6 ~~-17~~

index fe7f9e1f5bbb..ca8ae1e1cc0a 100644
@@ -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

Wei Yang

2025-02-11 14:03 UTC #1 lore raw

Quoted 8 lines · On Tue, Feb 11, 2025 at 10:48:28AM +0100, [email protected] wrote:

The patch below does not apply to the 6.1-stable tree.
If someone wants it applied there, or to any other stable or longterm tree, then please email the backport, including the original git commit id to <[email protected]>.
To reproduce the conflict and resubmit, you may use the following commands:

Quoted 9 lines

git fetch https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ linux-6.1.y
git checkout FETCH_HEAD
git cherry-pick -x 4f6a6bed0bfef4b966f076f33eb4f5547226056a
# <resolve conflicts, build, test, etc.>
git commit -s
git send-email --to '<[email protected]>' --in-reply-to '2025021128-repeater-percolate-6131@gregkh' --subject-prefix 'PATCH 6.1.y' HEAD^..
Possible dependencies:

Hi, Greg

commit 5729e06c819184b7ba40869c1ad53e1a463040b2

Author: Liam R. Howlett <[email protected]>
Date:   Thu May 18 10:55:10 2023 -0400

maple_tree: fix static analyser cppcheck issue

This commit reorder the comparison and leads to the conflict.

If you pick up this one first and then pick up 4f6a6bed0bfef4b966f0, there is no complain.

What do I suppose to do? Re-send these two patches? or merge then into one?

Quoted 5 lines

thanks,
greg k-h

Signature · 2 lines

Wei Yang
Help you, Help me

Greg KH

author maintainer

2025-02-13 13:10 UTC #2 lore raw

Quoted 25 lines · Wei Yang

Quoted 8 lines · On Tue, Feb 11, 2025 at 10:48:28AM +0100, [email protected] wrote:
The patch below does not apply to the 6.1-stable tree.
If someone wants it applied there, or to any other stable or longterm tree, then please email the backport, including the original git commit id to <[email protected]>.
To reproduce the conflict and resubmit, you may use the following commands:
Quoted 9 lines
git fetch https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/ linux-6.1.y
git checkout FETCH_HEAD
git cherry-pick -x 4f6a6bed0bfef4b966f076f33eb4f5547226056a
# <resolve conflicts, build, test, etc.>
git commit -s
git send-email --to '<[email protected]>' --in-reply-to '2025021128-repeater-percolate-6131@gregkh' --subject-prefix 'PATCH 6.1.y' HEAD^..
Possible dependencies:
Hi, Greg
commit 5729e06c819184b7ba40869c1ad53e1a463040b2
Author: Liam R. Howlett <[email protected]>
Date:   Thu May 18 10:55:10 2023 -0400

Quoted 8 lines

maple_tree: fix static analyser cppcheck issue
This commit reorder the comparison and leads to the conflict.
If you pick up this one first and then pick up 4f6a6bed0bfef4b966f0, there is no complain.
What do I suppose to do? Re-send these two patches? or merge then into one?

I took the above one first and then this one applied just fine, so nothing else for you to have to do at all, thanks!

greg k-h