From d406ea81345072659002afbe8fce43b48ceb75aa Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Mon, 30 Nov 2020 15:27:00 -0500
Subject: [PATCH] maple_tree: Fix mas_prev() from skipping entries.

When searching backwards, if the node wasn't fully full then the pivot could
be zero and thus return there was no previous entry in the node.  Also set
mas.last/mas.index to ensure correct prev/next functions

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 904fc63be1197..65341848f944b 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3467,6 +3467,9 @@ restart_prev_node:
 	mt = mte_node_type(mas->node);
 	slots = ma_slots(mas_mn(mas), mt);
 	mas->max = mas_safe_pivot(mas, offset);
+	if (mas->max < limit)
+		goto no_entry;
+
 	while (level > 1) {
 		level--;
 		mas->node = mas_slot(mas, slots, offset);
@@ -3474,9 +3477,10 @@ restart_prev_node:
 			goto restart_prev_node;
 		mt = mte_node_type(mas->node);
 		slots = ma_slots(mas_mn(mas), mt);
-		offset = mt_slots[mt];
-		do {} while (!mas_get_slot(mas, --offset));
+		offset = mas_data_end(mas);
 		mas->max = mas_safe_pivot(mas, offset);
+		if (mas->max < limit)
+			goto no_entry;
 	}
 
 	mas->offset = offset;
@@ -3573,29 +3577,35 @@ no_entry:
 static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long limit,
 		unsigned long *max)
 {
-	unsigned long pivot = mas->max;
-	unsigned char slot = mas->offset;
-	void *entry;
+	unsigned long pivot;
+	unsigned char offset;
+	struct maple_node *mn;
+	enum maple_type mt;
+	unsigned long *pivots;
+	void **slots;
 
-	if (!slot)
+	if (!mas->offset)
 		return false;
 
-	slot--;
-	do {
-		pivot = mas_safe_pivot(mas, slot);
-		if (pivot < limit)
-			return false;
+	mn = mas_mn(mas);
+	mt = mte_node_type(mas->node);
+	offset = mas->offset - 1;
+	slots = ma_slots(mn, mt);
+	pivots = ma_pivots(mn, mt);
 
-		entry = mas_get_slot(mas, slot);
-		if (entry)
-			break;
-	} while (slot--);
+	if (offset == mt_pivots[mt])
+		pivot = mas->max;
+	else
+		pivot = pivots[offset];
 
-	if (!entry)
+	while ((offset && !slots[offset] && pivot >= limit) || !pivot)
+		pivot = pivots[--offset];
+
+	mas->offset = offset;
+	if (!slots[offset])
 		return false;
 
 	*max = pivot;
-	mas->offset = slot;
 	return true;
 }
 
@@ -3772,7 +3782,7 @@ static inline void *_mas_prev(struct ma_state *mas, unsigned long limit)
 	}
 
 	if (mas_is_none(mas)) {
-		mas->index = 0;
+		mas->index = mas->last = limit;
 		return NULL;
 	}
 
@@ -3791,8 +3801,10 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
 {
 	void *entry;
 
-	if (!mas->index) // Nothing comes before 0.
+	if (!mas->index) {// Nothing comes before 0.
+		mas->last = 0;
 		return NULL;
+	}
 
 	if (mas_is_none(mas))
 		mas->node = MAS_START;
@@ -3808,9 +3820,7 @@ void *mas_prev(struct ma_state *mas, unsigned long min)
 
 	do {
 		entry = _mas_prev(mas, min);
-		if (!mas_searchable(mas))
-			break;
-	} while (!entry);
+	} while (mas_searchable(mas) && !entry);
 
 	return entry;
 }
-- 
2.50.1