From d936a37d019c36f8e50f79c1416dd68bc633a7fe Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Mon, 24 Feb 2020 10:14:18 -0500
Subject: [PATCH] maple_tree: Rework node split calculation for better non-leaf
 node split usage.

When calculating where to split non-leaf nodes, assume the minimum span
is 8 in each entry, so 8*8.  This still needs work as we could figure
out the level from a leaf and keep going up in the minimum span to
better utilize more levels of the tree.

There is also the issue of the right-most entry (ULONG_MAX) which ends
up wasting a slot in the linear allocation case.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 098ac9ac05c5..314b16fa5e39 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1364,10 +1364,21 @@ static inline unsigned char mas_append_calc_split(struct ma_state *mas,
 	unsigned long range = mas->max - mas->min;
 	unsigned long half;
 	unsigned long piv = 0;
+	unsigned long min_range = 8;
 	enum maple_type mas_type = mte_node_type(mas->node);
 
-	if (mas_type == maple_arange_64)
+	if (mas_type == maple_arange_64) {
 		max = 5;
+		ret = 5;
+	}
+
+	if (!ma_is_leaf(mas_type)) {
+		min_range *= max;
+		if (mas->max == ULONG_MAX) {
+			max--;
+			ret--;
+		}
+	}
 
 	if (!active) {
 		if (ma_is_leaf(mas_type))
@@ -1375,33 +1386,26 @@ static inline unsigned char mas_append_calc_split(struct ma_state *mas,
 		return max - 2;
 	}
 
-	//if (mas->min == 0)
-	//	max = 7;
-
 	half = max / 2;
-	if (ma_is_leaf(mas_type)) {
-		if (range <= 8UL)
-			return ret;
-
-		for (slot = 0; slot <= mt_pivots[mas_type]; slot++) {
-			piv = mas_get_safe_pivot(mas, slot);
+	if (range <= min_range)
+		return ret;
 
-			if (!piv && slot)
-				return ret;
+	for (slot = 0; slot <= mt_pivots[mas_type]; slot++) {
+		piv = mas_get_safe_pivot(mas, slot);
 
-			range = piv - mas->min;
-			if (range >= 8) {
-				if (slot > half)
-					ret = slot;
-				else
-					ret = half;
-				goto done;
-			}
+		if (!piv && slot)
+			return ret;
 
+		range = piv - mas->min;
+		if (range >= min_range) {
+			if (slot > half)
+				ret = (max > slot ? slot : max);
+			else
+				ret = half;
+			goto done;
 		}
-	}
 
-	return half;
+	}
 
 done:
 	if (ret < max && (piv == ULONG_MAX))
-- 
2.50.1