From 8e23ed66548d777e8a857651bc9ddd8c8d1141a9 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Thu, 16 Jul 2020 23:24:04 -0400
Subject: [PATCH] maple_tree: combine_separate reduction with copy out to nodes

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index ff4ab65bfc43..9f1ca66f9778 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2028,6 +2028,41 @@ 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_cp_to_nodes(struct maple_subtree_state *mast,
+				    struct maple_enode *left,
+				    struct maple_enode *middle,
+				    struct maple_enode *right,
+				    unsigned char split,
+				    unsigned char mid_split)
+{
+	mast->l->node = left;
+	mast->m->node = middle;
+	mast->r->node = right;
+
+	mast->l->min = mast->orig_l->min;
+	mast->l->max = mast->bn->pivot[split];
+	mab_mas_cp(mast->bn, 0, split, mast->l, 0);
+	mast->r->max = mast->l->max;
+
+	if (middle) {
+		mab_mas_cp(mast->bn, 1 + split, mid_split, mast->m, 0);
+		mast->m->min = mast->bn->pivot[split] + 1;
+		mast->m->max = mast->bn->pivot[mid_split];
+		split = mid_split;
+	}
+
+	if (right) {
+		mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, mast->r, 0);
+		mast->r->min = mast->bn->pivot[split] + 1;
+		mast->r->max = mast->bn->pivot[mast->bn->b_end];
+	}
+}
+
+/*
+ * Copy in the original left side of the tree into the combined data set in the
+ * maple subtree state big node.
+ */
 static inline void mast_combine_cp_left(struct maple_subtree_state *mast)
 {
 	unsigned char l_slot = mas_get_slot(mast->orig_l);
@@ -2037,6 +2072,10 @@ static inline void mast_combine_cp_left(struct maple_subtree_state *mast)
 
 	mas_mab_cp(mast->orig_l, 0, l_slot - 1, mast->bn, 0);
 }
+/*
+ * Copy in the original right side of the tree into the combined data set in
+ * the maple subtree state big node.
+ */
 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)
@@ -2046,6 +2085,17 @@ static inline void mast_combine_cp_right(struct maple_subtree_state *mast)
 		   mas_data_end(mast->orig_r), mast->bn, mast->bn->b_end);
 	mast->orig_r->last = mast->orig_r->max;
 }
+
+/* Check if the maple subtree state has enough data in the big node to create at
+ * least one sufficient node
+ */
+static inline bool mast_sufficient(struct maple_subtree_state *mast)
+{
+	if (mast->bn->b_end > mt_min_slot_cnt(mast->orig_l->node))
+		return true;
+
+	return false;
+}
 /* Private
  *
  * mas_combine_separate() - Follow the tree upwards from @l_mas and @r_mas for
@@ -2092,30 +2142,9 @@ static inline int mas_combine_separate(struct ma_state *mas,
 		mast->bn->type = mte_node_type(mast->orig_l->node);
 		split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle,
 					&mid_split);
-
 		mast_set_split_parents(mast, left, right, split);
 
-		/* Copy data from mast->bn to new nodes */
-		l_mas.node = left;
-		m_mas.node = middle;
-		r_mas.node = right;
-		l_mas.min = mast->orig_l->min;
-		mab_mas_cp(mast->bn, 0, split, &l_mas, 0);
-		l_mas.max = mast->bn->pivot[split];
-		r_mas.max = l_mas.max;
-
-		if (middle) {
-			mab_mas_cp(mast->bn, 1 + split, mid_split, &m_mas, 0);
-			m_mas.min = mast->bn->pivot[split] + 1;
-			m_mas.max = mast->bn->pivot[mid_split];
-			split = mid_split;
-		}
-
-		if (right) {
-			mab_mas_cp(mast->bn, 1 + split, mast->bn->b_end, &r_mas, 0);
-			r_mas.min = mast->bn->pivot[split] + 1;
-			r_mas.max = mast->bn->pivot[mast->bn->b_end];
-		}
+		mast_cp_to_nodes(mast, left, middle, right, split, mid_split);
 
 		/* Copy data from next level in the tree to mast->bn from next iteration */
 		memset(mast->bn, 0, sizeof(struct maple_big_node));
@@ -2139,10 +2168,10 @@ static inline int mas_combine_separate(struct ma_state *mas,
 		mast_consume(mast);
 		mast->orig_l->last = mast->orig_l->max;
 
-		if (mast->bn->b_end > mt_min_slot_cnt(mast->orig_l->node))
+		if(mast_sufficient(mast))
 			continue;
 
-		// Ensure there is enough data for the next loop.
+		// Try to get enough data for the next iteration.
 		if (!mast_rebalance_from_siblings(mast))
 			if (!mast_rebalance_from_cousins(mast))
 				break;
-- 
2.50.1