From d9d01b5eeebf50cf792fb8fd87405c402b40f682 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Date: Wed, 6 May 2020 14:04:47 -0400
Subject: [PATCH] maple_tree: Skip multiple deletes in split calculation.

When splitting, do not split within consecutive NULL entries.  Doing so
would cause separated gaps.

Also reset mas->node before walking in two other places which could
potentially cause issue.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
---
 lib/maple_tree.c      |  9 +++++++-
 lib/test_maple_tree.c | 50 +++++++++++++++++++++++++++++++++++++++----
 2 files changed, 54 insertions(+), 5 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index f2125125c91b..88a04fec52ef 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1505,11 +1505,16 @@ static inline unsigned char mas_append_calc_split(struct ma_state *mas,
 
 done:
 	if (ret < max) {
+		bool null = false;
 		if (piv == ULONG_MAX)
 			ret++;
 
+		if (mt_is_empty(mas_get_rcu_slot(mas, ret)))
+		    null = true;
+
 		while((ret < max) && // Skip deletes and retries.
-		      (piv == mas_get_safe_pivot(mas, ret + 1)))
+		      ((piv == mas_get_safe_pivot(mas, ret + 1)) ||
+		       (null && mt_is_empty(mas_get_rcu_slot(mas, ret + 1)))))
 		      ret++;
 	}
 
@@ -4064,6 +4069,7 @@ static inline void mas_rebalance(struct ma_state *mas)
 	mas_rebalance_gaps(mas);
 	if (mas_is_err(mas))
 		return;
+	mas->node = MAS_START;
 	_mas_walk(mas); // return to the updated location in the tree.
 }
 
@@ -4486,6 +4492,7 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index)
 		return 0;
 
 	mas->index = index;
+	mas->node = MAS_START;
 	_mas_walk(mas);
 	return 1;
 }
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 4a6f3aa53afa..20b91a01e80f 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -22233,6 +22233,31 @@ SNULL, 140249682087935, 140249710600191,
 STORE, 140249652703232, 140249682087935,
 STORE, 140249682087936, 140249710600191,
 	};
+	unsigned long set26[] = {
+STORE, 140737488347136, 140737488351231,
+STORE, 140729464770560, 140737488351231,
+SNULL, 140729464774655, 140737488351231,
+STORE, 140729464770560, 140729464774655,
+STORE, 140729464639488, 140729464774655,
+STORE, 4194304, 5066751,
+STORE, 7159808, 7172095,
+STORE, 7172096, 7180287,
+STORE, 140729465114624, 140729465118719,
+STORE, 140729465102336, 140729465114623,
+STORE, 30867456, 30875647,
+STORE, 30867456, 31010815,
+STORE, 140109040988160, 140109042671615,
+STORE, 140109040959488, 140109040988159,
+STORE, 140109040943104, 140109040959487,
+ERASE, 140109040943104, 140109040959487,
+STORE, 140109040840704, 140109040959487,
+ERASE, 140109040840704, 140109040959487,
+STORE, 140109040951296, 140109040959487,
+ERASE, 140109040951296, 140109040959487,
+STORE, 140109040955392, 140109040959487,
+ERASE, 140109040955392, 140109040959487,
+	};
+
 	int cnt = 0;
 	void *ptr = NULL;
 	MA_STATE(mas, mt, 0, 0);
@@ -22413,12 +22438,14 @@ STORE, 140249682087936, 140249710600191,
 	mt_validate(mt);
 	ptr = mtree_load(mt, 140551363362816);
 	MT_BUG_ON(mt, ptr == mtree_load(mt, 140551363420159));
+	mt_set_non_kernel(0);
 	mtree_destroy(mt);
 
 	mt_set_non_kernel(99);
 	mtree_init(mt, MAPLE_ALLOC_RANGE);
 	check_erase2_testset(mt, set23, ARRAY_SIZE(set23));
 	rcu_barrier();
+	mt_set_non_kernel(0);
 	mt_validate(mt);
 	mtree_destroy(mt);
 
@@ -22427,16 +22454,30 @@ STORE, 140249682087936, 140249710600191,
 	mtree_init(mt, MAPLE_ALLOC_RANGE);
 	check_erase2_testset(mt, set24, ARRAY_SIZE(set24));
 	rcu_barrier();
+	mt_set_non_kernel(0);
 	mt_validate(mt);
 	mtree_destroy(mt);
 
-
 	mt_set_non_kernel(99);
 	mtree_init(mt, MAPLE_ALLOC_RANGE);
 	check_erase2_testset(mt, set25, ARRAY_SIZE(set25));
 	rcu_barrier();
+	mt_set_non_kernel(0);
 	mt_validate(mt);
 	mtree_destroy(mt);
+
+	// Split on NULL followed by delete - causes gap issues.
+	mt_set_non_kernel(99);
+	mas_reset(&mas);
+	mtree_init(mt, MAPLE_ALLOC_RANGE);
+	check_erase2_testset(mt, set26, ARRAY_SIZE(set26));
+	rcu_barrier();
+	mas_get_unmapped_area_rev(&mas, 4096, 140109042671616, 409600);
+	MT_BUG_ON(mt, mas.index != 140109040549888);
+	mt_set_non_kernel(0);
+	mt_validate(mt);
+	mtree_destroy(mt);
+	exit(0);
 }
 
 static noinline void check_alloc_rev_range(struct maple_tree *mt)
@@ -23065,15 +23106,15 @@ static noinline void check_gap_combining(struct maple_tree *mt)
 	rcu_read_unlock();
 	mt_validate(mt);
 	mtree_destroy(mt);
-#if 0
+
 	mt_set_non_kernel(99);
 	mtree_init(mt, MAPLE_ALLOC_RANGE);
 	check_seq(mt, 400, false);
 	mtree_test_store_range(mt, 376, 391, NULL);
 	mt_dump(mt);
-	mt_set_non_kernel(1);
+	mt_set_non_kernel(0);
 	mtree_destroy(mt);
-#endif
+
 	mtree_init(mt, MAPLE_ALLOC_RANGE);
 	check_seq(mt, 400, false);
 	mt_set_non_kernel(50);
@@ -23249,6 +23290,7 @@ static int maple_tree_seed(void)
 
 	mtree_init(&tree, MAPLE_ALLOC_RANGE);
 	check_prev_entry(&tree);
+
 	mtree_init(&tree, 0);
 	check_erase2_sets(&tree);
 	mtree_destroy(&tree);
-- 
2.50.1