From ac181cb5baf14e7b8b3d1d3b68f4947dde7a06c7 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Wed, 9 Dec 2020 19:26:20 -0500
Subject: [PATCH] maple_tree: Optimize mas_prev() path.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b5ce3027787c..5c104994e77a 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3579,6 +3579,8 @@ static inline void mas_prev_node(struct ma_state *mas, unsigned long limit)
 	enum maple_type mt;
 	int offset, level;
 	void **slots;
+	struct maple_node *node;
+	unsigned long *pivots;
 
 	if (mas_is_none(mas))
 		return;
@@ -3586,8 +3588,7 @@ static inline void mas_prev_node(struct ma_state *mas, unsigned long limit)
 	if (mte_is_root(mas->node))
 		goto no_entry;
 
-	offset = mte_parent_slot(mas->node);
-	start_piv = mas_safe_pivot(mas, offset);
+	start_piv = mas->index;
 restart_prev_node:
 	level = 0;
 	do {
@@ -3604,8 +3605,10 @@ restart_prev_node:
 
 	offset--;
 	mt = mte_node_type(mas->node);
-	slots = ma_slots(mas_mn(mas), mt);
-	mas->max = mas_safe_pivot(mas, offset);
+	node = mas_mn(mas);
+	slots = ma_slots(node, mt);
+	pivots = ma_pivots(node, mt);
+	mas->max = pivots[offset];
 	if (mas->max < limit)
 		goto no_entry;
 
@@ -3615,18 +3618,22 @@ restart_prev_node:
 		if (mas_dead_node(mas, start_piv))
 			goto restart_prev_node;
 		mt = mte_node_type(mas->node);
-		slots = ma_slots(mas_mn(mas), mt);
+		node = mas_mn(mas);
+		slots = ma_slots(node, mt);
+		pivots = ma_pivots(node, mt);
 		offset = mas_data_end(mas);
-		mas->max = mas_safe_pivot(mas, offset);
-		if (mas->max < limit)
-			goto no_entry;
+		if (offset < mt_pivots[mt]) {
+			mas->max = pivots[offset];
+			if (mas->max < limit)
+				goto no_entry;
+		}
 	}
 
 	mas->offset = offset;
-	mas->min = mas_safe_min(mas, ma_pivots(mas_mn(mas),
-					       mte_node_type(mas->node)),
-				offset);
 	mas->node = mas_slot(mas, slots, offset);
+	if (offset)
+		mas->min = pivots[offset - 1] + 1;
+
 	if (mas_dead_node(mas, start_piv))
 		goto restart_prev_node;
 	return;
@@ -3713,8 +3720,7 @@ no_entry:
 /*
  * prev node entry
  */
-static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long limit,
-		unsigned long *max)
+static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit)
 {
 	unsigned long pivot;
 	unsigned char offset;
@@ -3724,14 +3730,13 @@ static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long limit,
 	void **slots;
 
 	if (!mas->offset)
-		return false;
+		return NULL;
 
 	mn = mas_mn(mas);
 	mt = mte_node_type(mas->node);
 	offset = mas->offset - 1;
 	slots = ma_slots(mn, mt);
 	pivots = ma_pivots(mn, mt);
-
 	if (offset == mt_pivots[mt])
 		pivot = mas->max;
 	else
@@ -3742,10 +3747,11 @@ static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long limit,
 
 	mas->offset = offset;
 	if (!slots[offset])
-		return false;
+		return NULL;
 
-	*max = pivot;
-	return true;
+	mas->last = pivot;
+	mas->index = mas_safe_min(mas, pivots, offset);
+	return mas_slot(mas, slots, offset);
 }
 
 /*
@@ -3939,26 +3945,19 @@ next_node:
  */
 static inline void *_mas_prev(struct ma_state *mas, unsigned long limit)
 {
-	unsigned long max = mas->max;
-	unsigned long *pivots;
+	void *entry;
 
-	while (!mas_is_none(mas)) {
-		if (mas_prev_nentry(mas, limit, &max))
-			break;
+	while (likely(!mas_is_none(mas))) {
+		entry = mas_prev_nentry(mas, limit);
+		if (likely(entry))
+			return entry;
 
 		mas_prev_node(mas, limit);
 		mas->offset = mt_slot_count(mas->node);
 	}
 
-	if (mas_is_none(mas)) {
-		mas->index = mas->last = limit;
-		return NULL;
-	}
-
-	pivots = ma_pivots(mas_mn(mas), mte_node_type(mas->node));
-	mas->last = max;
-	mas->index = mas_safe_min(mas, pivots, mas->offset);
-	return mas_get_slot(mas, mas->offset);
+	mas->index = mas->last = limit;
+	return NULL;
 }
 
 /*
-- 
2.50.1