From e31418c7d01c3bd43059a1e8d2c9704d6ab324b5 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Fri, 15 Feb 2019 16:27:03 -0500
Subject: [PATCH] maple_tree: Rework walk.

Make walk more efficient by avoiding duplicate fetches of slot and pivots.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3859870d88c3..3f0aeee47063 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1279,66 +1279,60 @@ done:
 	return ret;
 }
 
-static inline struct maple_node *mas_search_slots(struct ma_state *mas,
-		unsigned long val, enum maple_type type)
+static inline bool _mas_walk(struct ma_state *mas)
 {
-	int i;
-	unsigned char pivot_cnt = mt_pivots[type];
-	unsigned long pivot = 0;
+	enum maple_type type;
+	struct maple_node *next;
+	unsigned long pivot_cnt, pivot, max, min, i;
 
-	if (!pivot_cnt) {
-		i = val - mas->min;
-		if (mas->min)
-			i--;
-		goto linear_node;
-	}
+	mas->node = mas_start(mas);
 
-	for (i = 0; i < pivot_cnt; i++) {
-		pivot = _ma_get_pivot(mas->node, i, type);
-		if (i != 0 && pivot == 0) {
-			ma_set_slot(mas, MAPLE_NODE_SLOTS);
-			return NULL;
-		}
+	while (true) {
+		type = mt_node_type(mas->node);
+		pivot_cnt = mt_pivots[type];
+		min = mas->min;
+		max = mas->max;
 
-		if (val <= pivot)
-			break;
-	}
+		if (pivot_cnt) {
+			pivot = 0;
+			for (i = 0; i < pivot_cnt; i++) {
+				pivot = _ma_get_pivot(mas->node, i, type);
+				if (i != 0 && pivot == 0) {
+					ma_set_slot(mas, MAPLE_NODE_SLOTS);
+					return NULL;
+				}
 
-	if (i == pivot_cnt - 1) {
-		if (val > pivot)
-			i++;
-	}
+				if (mas->index <= pivot) {
+					max = pivot;
+					break;
+				}
+				min = pivot;
+			}
 
-linear_node:
-	ma_set_slot(mas, i);
-	return _ma_get_rcu_slot(mas->node, i, type);
-}
-static inline bool mas_traverse(struct ma_state *mas, struct maple_node *next,
-		enum maple_type type)
-{
-	unsigned char slot;
+			if (i == pivot_cnt - 1) {
+				if (mas->index > pivot)
+					i++;
+			}
+		} else {
+			// Linear node.
+			i = mas->index - mas->min;
+			if (mas->min)
+				i--;
+		}
 
-	if (type < maple_range_16)
-		return false;
-	slot = ma_get_slot(mas);
-	mas_update_limits(mas, slot, type);
-	mas->node = next;
-	return true;
-}
+		ma_set_slot(mas, i);
+		if (type < maple_range_16) // Leaf.
+			return true;
 
-static inline bool _mas_walk(struct ma_state *mas)
-{
-	mas->node = mas_start(mas);
-	enum maple_type type;
-	struct maple_node *next;
-	do {
-		type = mt_node_type(mas->node);
-		next = mas_search_slots(mas, mas->index, type);
-		if (!next)
+		next = _ma_get_rcu_slot(mas->node, i, type);
+		if (!next) // Not found.
 			return type < maple_range_16;
-	} while (mas_traverse(mas, next, type));
 
-	return true;
+		// Traverse.
+		mas->max = max;
+		mas->min = min;
+		mas->node = next;
+	}
 }
 
 static inline void ma_insert(struct ma_state *mas, void *entry)
-- 
2.50.1