From 5fd59f330794ddc902b64abf1844f670a6f47fe7 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Fri, 17 Jul 2020 21:51:47 -0400
Subject: [PATCH] maple_tree: rework mas_awalk

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 92374037d4ad..f4e905a96741 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3450,121 +3450,74 @@ ascend:
 
 static inline bool _mas_awalk(struct ma_state *mas, unsigned long size)
 {
-	enum maple_type type;
-	unsigned long pivot, max, min;
-	unsigned char pivot_cnt, i;
+	enum maple_type type = mte_node_type(mas->node);
+	unsigned long pivot, min, gap;
+	unsigned char slot = 0, pivot_cnt = mt_pivots[type];
 	bool found = false;
 
-	min = mas->min;
-	max = mas->max;
-
-	type = mte_node_type(mas->node);
-	pivot_cnt = mt_pivots[type];
-
 	switch (type) {
+	default:
+		slot = mas_get_slot(mas);
 	case maple_leaf_64:
-		for (i = 0; i <= pivot_cnt; i++) {
-			unsigned long this_gap = 0;
-			void *entry = NULL;
-
-			pivot = _mas_get_safe_pivot(mas, i, type);
-
-			/* End of data in this leaf */
-			if (i && !pivot) {
-				if (min > mas->max)
-					break;
-				pivot = mas->max;
-			}
+		min = mas_get_safe_lower_bound(mas, slot);
+		for (; slot <= pivot_cnt; slot++) {
+			pivot = _mas_get_safe_pivot(mas, slot, type);
+			if (slot && !pivot)
+				break;
 
 			/* Not within lower bounds */
 			if (mas->index > pivot)
-				goto next;
+				goto next_slot;
 
-			entry = mas_get_rcu_slot(mas, i);
-			if (!mt_is_empty(entry))
-				goto next;
+			if (ma_is_leaf(type)) {
+				if (!mt_is_empty(mas_get_rcu_slot(mas, slot)))
+					goto next_slot;
 
-			this_gap = pivot - mas->index;
-			if (!this_gap) // No entry, pivot = index.
-				this_gap = 1;
+				gap = pivot - mas->index;
+				if (!gap) // No entry, pivot = index.
+					gap = 1;
 
-			/* out of upper bounds */
-			if (mas->last + size < pivot - this_gap) {
-				mas_set_err(mas, -EBUSY);
-				return true;
+				if (mas->last + size < pivot - gap) { // upper bound
+					mas_set_err(mas, -EBUSY);
+					return true;
+				}
+				if (mas->last < pivot - gap) // gap check
+					break;
+			} else {
+				gap = mte_get_gap(mas->node, slot);
 			}
-			/* Does not fit in this gap or node */
-			if (mas->last < pivot - this_gap)
-				goto ascend;
 
-			if (this_gap >= size) {
-				found = true;
-				break;
-			}
-next:
-			min = pivot + 1;
-		}
-		if (!found)
-			goto ascend; // leaf exhausted.
-		break;
-	default:
-		pivot = 0;
-		i = mas_get_slot(mas);
-		min = mas_get_safe_lower_bound(mas, i);
-		for (; i <= pivot_cnt; i++) {
-			unsigned long this_gap;
-			pivot = _mas_get_safe_pivot(mas, i, type);
-			if (i && !pivot)
-				goto ascend;
-
-			this_gap = mte_get_gap(mas->node, i);
-			if (size <= this_gap) {
-				if (mas->index <= pivot) {
-					max = pivot;
-					goto descend;
+			if (gap >= size) {
+				if (ma_is_leaf(type)) {
+					found = true;
+					break;
+				} else if (mas->index <= pivot) {
+					mas->node = mas_get_rcu_slot(mas, slot);
+					mas->min = min;
+					mas->max = pivot;
+					slot = 0;
+					break;
 				}
 			}
-
+next_slot:
 			min = pivot + 1;
 			if (mas->last < min) {
 				mas_set_err(mas, -EBUSY);
 				return true;
 			}
 		}
-		goto ascend; // exhausted internal node.
 		break;
 
-	case maple_dense:
-		// FIXME: find a line of nulls...
-		i = mas->index - mas->min;
+	case maple_dense: // placeholder.
+		slot = mas->index - mas->min;
 		found = true;
 		break;
 	}
 
-descend:
-
-	if (!ma_is_leaf(type)) { //descend
-		struct maple_enode *next;
-
-		next = mas_get_rcu_slot(mas, i);
-		mas->min = min;
-		mas->max = max;
-		if (!mt_is_empty(next)) {
-			mas->node = next;
-			i = 0;
-		} else {
-			found = true; // this is a non-leaf hole.
-		}
-	}
-
-	mas_set_slot(mas, i);
-	return found;
-
-ascend:
 	if (mte_is_root(mas->node))
 		found = true;
 
-	mas_set_slot(mas, i);
+	mas_set_slot(mas, slot);
 	return found;
 }
 
@@ -3574,7 +3527,7 @@ ascend:
  *
  */
 static inline bool _mas_range_walk(struct ma_state *mas,
-		unsigned long *range_min, unsigned long *range_max)
+				   unsigned long *range_min, unsigned long *range_max)
 {
 
 	void *entry = mas_start(mas);
-- 
2.50.1