From bdbe9f6045d7111ff2a880bbb92d850f020397b6 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Thu, 16 Jul 2020 23:07:31 -0400
Subject: [PATCH] maple_tree: combine_separate reduction with parents and
 cp_left/cp_right

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c | 50 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 35 insertions(+), 15 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 5f9d20c5e3e1..ff4ab65bfc43 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -114,6 +114,7 @@ struct maple_subtree_state {
 	struct ma_state *orig_l;	/* Original left side of subtree */
 	struct ma_state *orig_r;	/* Original rigth side of subtree */
 	struct ma_state *l;		/* New left side of subtree */
+	struct ma_state *m;		/* New middle of subtree (rare) */
 	struct ma_state *r;		/* New right side of subtree */
 	struct ma_topiary *free;	/* nodes to be freed */
 	struct ma_topiary *destroy;	/* Nodes to be destroyed (walked and freed) */
@@ -1967,6 +1968,17 @@ static inline void mas_set_split_parent(struct ma_state *mas,
 	(*slot)++;
 }
 
+static inline void mast_set_split_parents(struct maple_subtree_state *mast,
+					  struct maple_enode *left,
+					  struct maple_enode *right,
+					  unsigned char split)
+{
+	unsigned char slot = mas_get_slot(mast->l);
+
+	mas_set_split_parent(mast->l, left, right, &slot, split);
+	mas_set_split_parent(mast->m, left, right, &slot, split);
+	mas_set_split_parent(mast->r, left, right, &slot, split);
+}
 static inline void mas_wmb_replace(struct ma_state *mas,
 				   struct ma_topiary *free,
 				   struct ma_topiary *destroy)
@@ -2016,6 +2028,24 @@ static inline bool mast_new_root(struct maple_subtree_state *mast,
 	mas_dup_state(mast->orig_l, mast->l);
 	return true;
 }
+static inline void mast_combine_cp_left(struct maple_subtree_state *mast)
+{
+	unsigned char l_slot = mas_get_slot(mast->orig_l);
+
+	if (!l_slot)
+		return;
+
+	mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);
+}
+static inline void mast_combine_cp_right(struct maple_subtree_state *mast)
+{
+	if (mast->bn->pivot[mast->bn->b_end - 1] >= mast->orig_r->max)
+		return;
+
+	mas_mab_cp(mast->orig_r, mas_get_slot(mast->orig_r) + 1,
+		   mas_data_end(mast->orig_r), mast->bn, mast->bn->b_end);
+	mast->orig_r->last = mast->orig_r->max;
+}
 /* Private
  *
  * mas_combine_separate() - Follow the tree upwards from @l_mas and @r_mas for
@@ -2037,7 +2067,7 @@ static inline int mas_combine_separate(struct ma_state *mas,
 				       struct maple_subtree_state *mast, unsigned char count)
 {
 	unsigned char split, mid_split;
-	unsigned char slot = 0, l_slot = 0;
+	unsigned char slot = 0;
 	struct maple_enode *left = NULL, *middle = NULL, *right = NULL;
 
 	MA_STATE(l_mas, mas->tree, mas->index, mas->index);
@@ -2047,6 +2077,7 @@ static inline int mas_combine_separate(struct ma_state *mas,
 	MA_TOPIARY(destroy, mas->tree);
 
 	mast->l = &l_mas;
+	mast->m = &m_mas;
 	mast->r = &r_mas;
 	mast->free = &free;
 	mast->destroy = &destroy;
@@ -2062,11 +2093,7 @@ static inline int mas_combine_separate(struct ma_state *mas,
 		split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,
 					&mid_split);
 
-		/* Set parents from previous run */
-		slot = mas_get_slot(&l_mas);
-		mas_set_split_parent(&l_mas, left, right, &slot, split);
-		mas_set_split_parent(&m_mas, left, right, &slot, split);
-		mas_set_split_parent(&r_mas, left, right, &slot, split);
+		mast_set_split_parents(mast, left, right, split);
 
 		/* Copy data from mast->bn to new nodes */
 		l_mas.node = left;
@@ -2098,11 +2125,9 @@ static inline int mas_combine_separate(struct ma_state *mas,
 			goto new_root;
 
 		mast_ascend_free(mast);
-		l_slot = mas_get_slot(mast->orig_l);
 
 		mast->bn->b_end = 0;
-		if (l_slot)
-			mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);
+		mast_combine_cp_left(mast);
 
 		mas_set_slot(&l_mas, mast->bn->b_end);
 		mab_set_b_end(mast->bn, &l_mas, left);
@@ -2110,12 +2135,7 @@ static inline int mas_combine_separate(struct ma_state *mas,
 		mab_set_b_end(mast->bn, &r_mas, right);
 
 		// Copy anything necessary out of the right node.
-		if (mast->bn->pivot[mast->bn->b_end - 1] < mast->orig_r->max) {
-			mas_mab_cp(mast->orig_r, mas_get_slot(mast->orig_r) + 1,
-				   mas_data_end(mast->orig_r), mast->bn,
-				   mast->bn->b_end);
-			mast->orig_r->last = mast->orig_r->max;
-		}
+		mast_combine_cp_right(mast);
 		mast_consume(mast);
 		mast->orig_l->last = mast->orig_l->max;
 
-- 
2.50.1