maple_tree: reorganize testing to restore module testing

Along the development cycle, the testing code support for module/in-kernel
compiles was removed.  Restore this functionality by moving any internal
API tests to the userspace side, as well as threading tests.  Fix the
lockdep issues and add a way to reduce memory usage so the tests can
complete with KASAN + memleak detection.  Make the tests work on 32 bit
hosts where possible and detect 32 bit hosts in the radix test suite.

[akpm@linux-foundation.org: fix module export]
[akpm@linux-foundation.org: fix it some more]
[liam.howlett@oracle.com: fix compile warnings on 32bit build in check_find()]
  Link: https://lkml.kernel.org/r/20221107203816.1260327-1-Liam.Howlett@oracle.com
Link: https://lkml.kernel.org/r/20221028180415.3074673-1-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

5 files changed, 35792 insertions, 4 deletions

diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore
index c901d96dd013..49bccb90c35b 100644
--- a/tools/testing/radix-tree/.gitignore
+++ b/tools/testing/radix-tree/.gitignore
@@ -1,4 +1,5 @@
 # SPDX-License-Identifier: GPL-2.0-only
+generated/bit-length.h
 generated/map-shift.h
 idr.c
 idr-test
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 89d613e0505b..caf32a9b9608 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -18,9 +18,14 @@ endif
 ifeq ($(BUILD), 32)
 	CFLAGS += -m32
 	LDFLAGS += -m32
+LONG_BIT := 32
 endif
 
-targets: generated/map-shift.h $(TARGETS)
+ifndef LONG_BIT
+LONG_BIT := $(shell getconf LONG_BIT)
+endif
+
+targets: generated/map-shift.h generated/bit-length.h $(TARGETS)
 
 main:	$(OFILES)
 
@@ -34,11 +39,11 @@ maple: $(CORE_OFILES)
 multiorder: multiorder.o $(CORE_OFILES)
 
 clean:
-	$(RM) $(TARGETS) *.o radix-tree.c idr.c generated/map-shift.h
+	$(RM) $(TARGETS) *.o radix-tree.c idr.c generated/map-shift.h generated/bit-length.h
 
 vpath %.c ../../lib
 
-$(OFILES): Makefile *.h */*.h generated/map-shift.h \
+$(OFILES): Makefile *.h */*.h generated/map-shift.h generated/bit-length.h \
 	../../include/linux/*.h \
 	../../include/asm/*.h \
 	../../../include/linux/xarray.h \
@@ -61,3 +66,11 @@ generated/map-shift.h:
 		echo "#define XA_CHUNK_SHIFT $(SHIFT)" >		\
 				generated/map-shift.h;			\
 	fi
+
+generated/bit-length.h: FORCE
+	@if ! grep -qws CONFIG_$(LONG_BIT)BIT generated/bit-length.h; then   \
+		echo "Generating $@";                                        \
+		echo "#define CONFIG_$(LONG_BIT)BIT 1" > $@;                 \
+	fi
+
+FORCE: ;
diff --git a/tools/testing/radix-tree/generated/autoconf.h b/tools/testing/radix-tree/generated/autoconf.h
index e7da80350236..92dc474c349b 100644
--- a/tools/testing/radix-tree/generated/autoconf.h
+++ b/tools/testing/radix-tree/generated/autoconf.h
@@ -1,2 +1,2 @@
+#include "bit-length.h"
 #define CONFIG_XARRAY_MULTI 1
-#define CONFIG_64BIT 1
diff --git a/tools/testing/radix-tree/linux.c b/tools/testing/radix-tree/linux.c
index 2048d12c31df..d587a558997f 100644
--- a/tools/testing/radix-tree/linux.c
+++ b/tools/testing/radix-tree/linux.c
@@ -129,6 +129,10 @@ void kmem_cache_free_bulk(struct kmem_cache *cachep, size_t size, void **list)
 	pthread_mutex_unlock(&cachep->lock);
 }
 
+void kmem_cache_shrink(struct kmem_cache *cachep)
+{
+}
+
 int kmem_cache_alloc_bulk(struct kmem_cache *cachep, gfp_t gfp, size_t size,
 			  void **p)
 {
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 35082671928a..2e91973fbaa6 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -2,11 +2,17 @@
 /*
  * maple_tree.c: Userspace shim for maple tree test-suite
  * Copyright (c) 2018 Liam R. Howlett <Liam.Howlett@Oracle.com>
+ *
+ * Any tests that require internal knowledge of the tree or threads and other
+ * difficult to handle in kernel tests.
  */
 
 #define CONFIG_DEBUG_MAPLE_TREE
 #define CONFIG_MAPLE_SEARCH
+#define MAPLE_32BIT (MAPLE_NODE_SLOTS > 31)
 #include "test.h"
+#include <stdlib.h>
+#include <time.h>
 
 #define module_init(x)
 #define module_exit(x)
@@ -18,6 +24,35717 @@
 #undef CONFIG_DEBUG_MAPLE_TREE
 #include "../../../lib/test_maple_tree.c"
 
+#define RCU_RANGE_COUNT 1000
+#define RCU_MT_BUG_ON(test, y) {if (y) { test->stop = true; } MT_BUG_ON(test->mt, y); }
+
+struct rcu_test_struct2 {
+	struct maple_tree *mt;
+
+	bool start;
+	bool stop;
+	unsigned int thread_count;
+
+	unsigned int seen_toggle;
+	unsigned int seen_added;
+	unsigned int seen_modified;
+	unsigned int seen_deleted;
+	int pause;
+
+	unsigned long index[RCU_RANGE_COUNT];
+	unsigned long last[RCU_RANGE_COUNT];
+};
+
+struct rcu_reader_struct {
+	unsigned int id;
+	int mod;
+	int del;
+	int flip;
+	int add;
+	int next;
+	struct rcu_test_struct2 *test;
+};
+
+/*
+ * check_new_node() - Check the creation of new nodes and error path
+ * verification.
+ */
+static noinline void check_new_node(struct maple_tree *mt)
+{
+
+	struct maple_node *mn, *mn2, *mn3;
+	struct maple_alloc *smn;
+	struct maple_node *nodes[100];
+	int i, j, total;
+
+	MA_STATE(mas, mt, 0, 0);
+
+	/* Try allocating 3 nodes */
+	mtree_lock(mt);
+	mt_set_non_kernel(0);
+	/* request 3 nodes to be allocated. */
+	mas_node_count(&mas, 3);
+	/* Allocation request of 3. */
+	MT_BUG_ON(mt, mas_alloc_req(&mas) != 3);
+	/* Allocate failed. */
+	MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
+	MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+
+	MT_BUG_ON(mt, mas_allocated(&mas) != 3);
+	mn = mas_pop_node(&mas);
+	MT_BUG_ON(mt, not_empty(mn));
+	MT_BUG_ON(mt, mn == NULL);
+	MT_BUG_ON(mt, mas.alloc == NULL);
+	MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
+	mas_push_node(&mas, mn);
+	mas_nomem(&mas, GFP_KERNEL); /* free */
+	mtree_unlock(mt);
+
+
+	/* Try allocating 1 node, then 2 more */
+	mtree_lock(mt);
+	/* Set allocation request to 1. */
+	mas_set_alloc_req(&mas, 1);
+	/* Check Allocation request of 1. */
+	MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
+	mas_set_err(&mas, -ENOMEM);
+	/* Validate allocation request. */
+	MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+	/* Eat the requested node. */
+	mn = mas_pop_node(&mas);
+	MT_BUG_ON(mt, not_empty(mn));
+	MT_BUG_ON(mt, mn == NULL);
+	MT_BUG_ON(mt, mn->slot[0] != NULL);
+	MT_BUG_ON(mt, mn->slot[1] != NULL);
+	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+
+	ma_free_rcu(mn);
+	mas.node = MAS_START;
+	mas_nomem(&mas, GFP_KERNEL);
+	/* Allocate 3 nodes, will fail. */
+	mas_node_count(&mas, 3);
+	/* Drop the lock and allocate 3 nodes. */
+	mas_nomem(&mas, GFP_KERNEL);
+	/* Ensure 3 are allocated. */
+	MT_BUG_ON(mt, mas_allocated(&mas) != 3);
+	/* Allocation request of 0. */
+	MT_BUG_ON(mt, mas_alloc_req(&mas) != 0);
+
+	MT_BUG_ON(mt, mas.alloc == NULL);
+	MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
+	MT_BUG_ON(mt, mas.alloc->slot[1] == NULL);
+	/* Ensure we counted 3. */
+	MT_BUG_ON(mt, mas_allocated(&mas) != 3);
+	/* Free. */
+	mas_nomem(&mas, GFP_KERNEL);
+
+	/* Set allocation request to 1. */
+	mas_set_alloc_req(&mas, 1);
+	MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
+	mas_set_err(&mas, -ENOMEM);
+	/* Validate allocation request. */
+	MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+	MT_BUG_ON(mt, mas_allocated(&mas) != 1);
+	/* Check the node is only one node. */
+	mn = mas_pop_node(&mas);
+	MT_BUG_ON(mt, not_empty(mn));
+	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+	MT_BUG_ON(mt, mn == NULL);
+	MT_BUG_ON(mt, mn->slot[0] != NULL);
+	MT_BUG_ON(mt, mn->slot[1] != NULL);
+	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+	mas_push_node(&mas, mn);
+	MT_BUG_ON(mt, mas_allocated(&mas) != 1);
+	MT_BUG_ON(mt, mas.alloc->node_count);
+
+	mas_set_alloc_req(&mas, 2); /* request 2 more. */
+	MT_BUG_ON(mt, mas_alloc_req(&mas) != 2);
+	mas_set_err(&mas, -ENOMEM);
+	MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+	MT_BUG_ON(mt, mas_allocated(&mas) != 3);
+	MT_BUG_ON(mt, mas.alloc == NULL);
+	MT_BUG_ON(mt, mas.alloc->slot[0] == NULL);
+	MT_BUG_ON(mt, mas.alloc->slot[1] == NULL);
+	for (i = 2; i >= 0; i--) {
+		mn = mas_pop_node(&mas);
+		MT_BUG_ON(mt, mas_allocated(&mas) != i);
+		MT_BUG_ON(mt, !mn);
+		MT_BUG_ON(mt, not_empty(mn));
+		ma_free_rcu(mn);
+	}
+
+	total = 64;
+	mas_set_alloc_req(&mas, total); /* request 2 more. */
+	MT_BUG_ON(mt, mas_alloc_req(&mas) != total);
+	mas_set_err(&mas, -ENOMEM);
+	MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+	for (i = total; i > 0; i--) {
+		unsigned int e = 0; /* expected node_count */
+
+		if (!MAPLE_32BIT) {
+			if (i >= 35)
+				e = i - 35;
+			else if (i >= 5)
+				e = i - 5;
+			else if (i >= 2)
+				e = i - 2;
+		} else {
+			if (i >= 4)
+				e = i - 4;
+			else if (i == 3)
+				e = i - 2;
+			else
+				e = 0;
+		}
+
+		MT_BUG_ON(mt, mas.alloc->node_count != e);
+		mn = mas_pop_node(&mas);
+		MT_BUG_ON(mt, not_empty(mn));
+		MT_BUG_ON(mt, mas_allocated(&mas) != i - 1);
+		MT_BUG_ON(mt, !mn);
+		ma_free_rcu(mn);
+	}
+
+	total = 100;
+	for (i = 1; i < total; i++) {
+		mas_set_alloc_req(&mas, i);
+		mas_set_err(&mas, -ENOMEM);
+		MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+		for (j = i; j > 0; j--) {
+			mn = mas_pop_node(&mas);
+			MT_BUG_ON(mt, mas_allocated(&mas) != j - 1);
+			MT_BUG_ON(mt, !mn);
+			MT_BUG_ON(mt, not_empty(mn));
+			mas_push_node(&mas, mn);
+			MT_BUG_ON(mt, mas_allocated(&mas) != j);
+			mn = mas_pop_node(&mas);
+			MT_BUG_ON(mt, not_empty(mn));
+			MT_BUG_ON(mt, mas_allocated(&mas) != j - 1);
+			ma_free_rcu(mn);
+		}
+		MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+
+		mas_set_alloc_req(&mas, i);
+		mas_set_err(&mas, -ENOMEM);
+		MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+		for (j = 0; j <= i/2; j++) {
+			MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
+			nodes[j] = mas_pop_node(&mas);
+			MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
+		}
+
+		while (j) {
+			j--;
+			mas_push_node(&mas, nodes[j]);
+			MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
+		}
+		MT_BUG_ON(mt, mas_allocated(&mas) != i);
+		for (j = 0; j <= i/2; j++) {
+			MT_BUG_ON(mt, mas_allocated(&mas) != i - j);
+			mn = mas_pop_node(&mas);
+			MT_BUG_ON(mt, not_empty(mn));
+			ma_free_rcu(mn);
+			MT_BUG_ON(mt, mas_allocated(&mas) != i - j - 1);
+		}
+		MT_BUG_ON(mt, mas_nomem(&mas, GFP_KERNEL));
+
+	}
+
+	/* Set allocation request. */
+	total = 500;
+	mas_node_count(&mas, total);
+	/* Drop the lock and allocate the nodes. */
+	mas_nomem(&mas, GFP_KERNEL);
+	MT_BUG_ON(mt, !mas.alloc);
+	i = 1;
+	smn = mas.alloc;
+	while (i < total) {
+		for (j = 0; j < MAPLE_ALLOC_SLOTS; j++) {
+			i++;
+			MT_BUG_ON(mt, !smn->slot[j]);
+			if (i == total)
+				break;
+		}
+		smn = smn->slot[0]; /* next. */
+	}
+	MT_BUG_ON(mt, mas_allocated(&mas) != total);
+	mas_nomem(&mas, GFP_KERNEL); /* Free. */
+
+	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+	for (i = 1; i < 128; i++) {
+		mas_node_count(&mas, i); /* Request */
+		mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+		MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */
+		for (j = i; j > 0; j--) { /*Free the requests */
+			mn = mas_pop_node(&mas); /* get the next node. */
+			MT_BUG_ON(mt, mn == NULL);
+			MT_BUG_ON(mt, not_empty(mn));
+			ma_free_rcu(mn);
+		}
+		MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+	}
+
+	for (i = 1; i < MAPLE_NODE_MASK + 1; i++) {
+		MA_STATE(mas2, mt, 0, 0);
+		mas_node_count(&mas, i); /* Request */
+		mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+		MT_BUG_ON(mt, mas_allocated(&mas) != i); /* check request filled */
+		for (j = 1; j <= i; j++) { /* Move the allocations to mas2 */
+			mn = mas_pop_node(&mas); /* get the next node. */
+			MT_BUG_ON(mt, mn == NULL);
+			MT_BUG_ON(mt, not_empty(mn));
+			mas_push_node(&mas2, mn);
+			MT_BUG_ON(mt, mas_allocated(&mas2) != j);
+		}
+		MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+		MT_BUG_ON(mt, mas_allocated(&mas2) != i);
+
+		for (j = i; j > 0; j--) { /*Free the requests */
+			MT_BUG_ON(mt, mas_allocated(&mas2) != j);
+			mn = mas_pop_node(&mas2); /* get the next node. */
+			MT_BUG_ON(mt, mn == NULL);
+			MT_BUG_ON(mt, not_empty(mn));
+			ma_free_rcu(mn);
+		}
+		MT_BUG_ON(mt, mas_allocated(&mas2) != 0);
+	}
+
+
+	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 1); /* Request */
+	MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
+	MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
+	MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS - 1);
+
+	mn = mas_pop_node(&mas); /* get the next node. */
+	MT_BUG_ON(mt, mn == NULL);
+	MT_BUG_ON(mt, not_empty(mn));
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS);
+	MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS - 2);
+
+	mas_push_node(&mas, mn);
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
+	MT_BUG_ON(mt, mas.alloc->node_count != MAPLE_ALLOC_SLOTS - 1);
+
+	/* Check the limit of pop/push/pop */
+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS + 2); /* Request */
+	MT_BUG_ON(mt, mas_alloc_req(&mas) != 1);
+	MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM));
+	MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL));
+	MT_BUG_ON(mt, mas_alloc_req(&mas));
+	MT_BUG_ON(mt, mas.alloc->node_count);
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2);
+	mn = mas_pop_node(&mas);
+	MT_BUG_ON(mt, not_empty(mn));
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 1);
+	MT_BUG_ON(mt, mas.alloc->node_count  != MAPLE_ALLOC_SLOTS - 1);
+	mas_push_node(&mas, mn);
+	MT_BUG_ON(mt, mas.alloc->node_count);
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS + 2);
+	mn = mas_pop_node(&mas);
+	MT_BUG_ON(mt, not_empty(mn));
+	ma_free_rcu(mn);
+	for (i = 1; i <= MAPLE_ALLOC_SLOTS + 1; i++) {
+		mn = mas_pop_node(&mas);
+		MT_BUG_ON(mt, not_empty(mn));
+		ma_free_rcu(mn);
+	}
+	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+
+
+	for (i = 3; i < MAPLE_NODE_MASK * 3; i++) {
+		mas.node = MA_ERROR(-ENOMEM);
+		mas_node_count(&mas, i); /* Request */
+		mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+		mn = mas_pop_node(&mas); /* get the next node. */
+		mas_push_node(&mas, mn); /* put it back */
+		mas_destroy(&mas);
+
+		mas.node = MA_ERROR(-ENOMEM);
+		mas_node_count(&mas, i); /* Request */
+		mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+		mn = mas_pop_node(&mas); /* get the next node. */
+		mn2 = mas_pop_node(&mas); /* get the next node. */
+		mas_push_node(&mas, mn); /* put them back */
+		mas_push_node(&mas, mn2);
+		mas_destroy(&mas);
+
+		mas.node = MA_ERROR(-ENOMEM);
+		mas_node_count(&mas, i); /* Request */
+		mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+		mn = mas_pop_node(&mas); /* get the next node. */
+		mn2 = mas_pop_node(&mas); /* get the next node. */
+		mn3 = mas_pop_node(&mas); /* get the next node. */
+		mas_push_node(&mas, mn); /* put them back */
+		mas_push_node(&mas, mn2);
+		mas_push_node(&mas, mn3);
+		mas_destroy(&mas);
+
+		mas.node = MA_ERROR(-ENOMEM);
+		mas_node_count(&mas, i); /* Request */
+		mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+		mn = mas_pop_node(&mas); /* get the next node. */
+		ma_free_rcu(mn);
+		mas_destroy(&mas);
+
+		mas.node = MA_ERROR(-ENOMEM);
+		mas_node_count(&mas, i); /* Request */
+		mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+		mn = mas_pop_node(&mas); /* get the next node. */
+		ma_free_rcu(mn);
+		mn = mas_pop_node(&mas); /* get the next node. */
+		ma_free_rcu(mn);
+		mn = mas_pop_node(&mas); /* get the next node. */
+		ma_free_rcu(mn);
+		mas_destroy(&mas);
+	}
+
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, 5); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	MT_BUG_ON(mt, mas_allocated(&mas) != 5);
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, 10); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	mas.node = MAS_START;
+	MT_BUG_ON(mt, mas_allocated(&mas) != 10);
+	mas_destroy(&mas);
+
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, MAPLE_ALLOC_SLOTS - 1); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	MT_BUG_ON(mt, mas_allocated(&mas) != MAPLE_ALLOC_SLOTS - 1);
+	mas.node = MA_ERROR(-ENOMEM);
+	mas_node_count(&mas, 10 + MAPLE_ALLOC_SLOTS - 1); /* Request */
+	mas_nomem(&mas, GFP_KERNEL); /* Fill request */
+	mas.node = MAS_START;
+	MT_BUG_ON(mt, mas_allocated(&mas) != 10 + MAPLE_ALLOC_SLOTS - 1);
+	mas_destroy(&mas);
+
+	mtree_unlock(mt);
+}
+
+/*
+ * Check erasing including RCU.
+ */
+static noinline void check_erase(struct maple_tree *mt, unsigned long index,
+		void *ptr)
+{
+	MT_BUG_ON(mt, mtree_test_erase(mt, index) != ptr);
+}
+
+#define erase_check_load(mt, i) check_load(mt, set[i], entry[i%2])
+#define erase_check_insert(mt, i) check_insert(mt, set[i], entry[i%2])
+#define erase_check_erase(mt, i) check_erase(mt, set[i], entry[i%2])
+
+static noinline void check_erase_testset(struct maple_tree *mt)
+{
+	unsigned long set[] = { 5015, 5014, 5017, 25, 1000,
+				1001, 1002, 1003, 1005, 0,
+				6003, 6002, 6008, 6012, 6015,
+				7003, 7002, 7008, 7012, 7015,
+				8003, 8002, 8008, 8012, 8015,
+				9003, 9002, 9008, 9012, 9015,
+				10003, 10002, 10008, 10012, 10015,
+				11003, 11002, 11008, 11012, 11015,
+				12003, 12002, 12008, 12012, 12015,
+				13003, 13002, 13008, 13012, 13015,
+				14003, 14002, 14008, 14012, 14015,
+				15003, 15002, 15008, 15012, 15015,
+			      };
+
+
+	void *ptr = &set;
+	void *entry[2] = { ptr, mt };
+	void *root_node;
+
+
+	rcu_register_thread();
+	mt_set_in_rcu(mt);
+	for (int i = 0; i < 4; i++)
+		erase_check_insert(mt, i);
+	for (int i = 0; i < 4; i++)
+		erase_check_load(mt, i);
+
+	mt_set_non_kernel(2);
+	erase_check_erase(mt, 1);
+	erase_check_load(mt, 0);
+	check_load(mt, set[1], NULL);
+	for (int i = 2; i < 4; i++)
+		erase_check_load(mt, i);
+
+
+	erase_check_erase(mt, 2);
+	erase_check_load(mt, 0);
+	check_load(mt, set[1], NULL);
+	check_load(mt, set[2], NULL);
+
+	erase_check_insert(mt, 1);
+	erase_check_insert(mt, 2);
+
+	for (int i = 0; i < 4; i++)
+		erase_check_load(mt, i);
+
+	/* Check erase and load without an allocation. */
+	erase_check_load(mt, 3);
+	erase_check_erase(mt, 1);
+	erase_check_load(mt, 0);
+	check_load(mt, set[1], NULL);
+	for (int i = 2; i < 4; i++)
+		erase_check_load(mt, i);
+
+	/*
+	 * Set the newly erased node.  This will produce a different allocated
+	 * node to avoid busy slots.
+	 */
+	root_node = mt->ma_root;
+	erase_check_insert(mt, 1);
+
+	erase_check_load(mt, 0);
+	check_load(mt, 5016, NULL);
+	erase_check_load(mt, 1);
+	check_load(mt, 5013, NULL);
+	erase_check_load(mt, 2);
+	check_load(mt, 5018, NULL);
+	erase_check_load(mt, 3);
+
+	erase_check_erase(mt, 2); /* erase 5017 to check append */
+	erase_check_load(mt, 0);
+	check_load(mt, 5016, NULL);
+	erase_check_load(mt, 1);
+	check_load(mt, 5013, NULL);
+	check_load(mt, set[2], NULL);
+	check_load(mt, 5018, NULL);
+
+	erase_check_load(mt, 3);
+
+	root_node = mt->ma_root;
+	erase_check_insert(mt, 2);
+
+	erase_check_load(mt, 0);
+	check_load(mt, 5016, NULL);
+	erase_check_load(mt, 1);
+	check_load(mt, 5013, NULL);
+	erase_check_load(mt, 2);
+	check_load(mt, 5018, NULL);
+	erase_check_load(mt, 3);
+
+	mt_set_non_kernel(1);
+	erase_check_erase(mt, 2); /* erase 5017 to check append */
+	erase_check_load(mt, 0);
+	check_load(mt, 5016, NULL);
+	check_load(mt, set[2], NULL);
+	erase_check_erase(mt, 0); /* erase 5015 to check append */
+	check_load(mt, set[0], NULL);
+	check_load(mt, 5016, NULL);
+	erase_check_insert(mt, 4); /* 1000 < Should not split. */
+	check_load(mt, set[0], NULL);
+	check_load(mt, 5016, NULL);
+	erase_check_load(mt, 1);
+	check_load(mt, 5013, NULL);
+	check_load(mt, set[2], NULL);
+	check_load(mt, 5018, NULL);
+	erase_check_load(mt, 4);
+	check_load(mt, 999, NULL);
+	check_load(mt, 1001, NULL);
+	erase_check_load(mt, 4);
+	if (mt_in_rcu(mt))
+		MT_BUG_ON(mt, root_node == mt->ma_root);
+	else
+		MT_BUG_ON(mt, root_node != mt->ma_root);
+
+	/* Should not have split. */
+	MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root));
+
+
+	/* Coalesce testing */
+	erase_check_insert(mt, 0);
+	erase_check_insert(mt, 2);
+
+	for (int i = 5; i < 25; i++) {
+		erase_check_insert(mt, i);
+		for (int j = i; j >= 0; j--)
+			erase_check_load(mt, j);
+	}
+
+	erase_check_erase(mt, 14); /*6015 */
+	for (int i = 0; i < 25; i++) {
+		if (i == 14)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+	erase_check_erase(mt, 16); /*7002 */
+	for (int i = 0; i < 25; i++) {
+		if (i == 16 || i == 14)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+
+	mt_set_non_kernel(1);
+	erase_check_erase(mt, 13); /*6012 */
+	for (int i = 0; i < 25; i++) {
+		if (i == 16 || i == 14 || i == 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	erase_check_erase(mt, 15); /*7003 */
+	for (int i = 0; i < 25; i++) {
+		if (i <= 16 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	mt_set_non_kernel(2);
+	erase_check_erase(mt, 17); /*7008 *should* cause coalesce. */
+	for (int i = 0; i < 25; i++) {
+		if (i <= 17 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	erase_check_erase(mt, 18); /*7012 */
+	for (int i = 0; i < 25; i++) {
+		if (i <= 18 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	mt_set_non_kernel(2);
+	erase_check_erase(mt, 19); /*7015 */
+	for (int i = 0; i < 25; i++) {
+		if (i <= 19 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	erase_check_erase(mt, 20); /*8003 */
+	for (int i = 0; i < 25; i++) {
+		if (i <= 20 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	erase_check_erase(mt, 21); /*8002 */
+	for (int i = 0; i < 25; i++) {
+		if (i <= 21 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	mt_set_non_kernel(2);
+	erase_check_erase(mt, 22); /*8008 */
+	for (int i = 0; i < 25; i++) {
+		if (i <= 22 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+	for (int i = 23; i < 25; i++)
+		erase_check_erase(mt, i);
+
+	for (int i = 0; i < 25; i++) {
+		if (i <= 25 && i >= 13)
+			check_load(mt, set[i], NULL);
+		else
+			erase_check_load(mt, i);
+	}
+
+	/* Shrinking tree test. */
+
+	for (int i = 13; i < ARRAY_SIZE(set); i++)
+		erase_check_insert(mt, i);
+
+	mt_set_non_kernel(99);
+	for (int i = 18; i < ARRAY_SIZE(set); i++) {
+		erase_check_erase(mt, i);
+		for (int j = 0; j < ARRAY_SIZE(set); j++) {
+			if (j < 18 || j > i)
+				erase_check_load(mt, j);
+			else
+				check_load(mt, set[j], NULL);
+		}
+	}
+	mt_set_non_kernel(35);
+	for (int i = 0; i < 18; i++) {
+		erase_check_erase(mt, i);
+		for (int j = 0; j < ARRAY_SIZE(set); j++) {
+			if (j < 18 && j > i)
+				erase_check_load(mt, j);
+			else
+				check_load(mt, set[j], NULL);
+		}
+	}
+	erase_check_insert(mt, 8);
+	erase_check_insert(mt, 9);
+	erase_check_erase(mt, 8);
+	rcu_unregister_thread();
+}
+
+/* End of erase testing */
+
+/* VM Generated Crashes - uses its own tree walk for verification */
+#define erase_check_store_range(mt, a, i, ptr) mtree_test_store_range(mt, \
+						a[(i)], a[(i + 1)], ptr)
+#define STORE 1
+#define SNULL 2
+#define ERASE 3
+#define ec_type_str(x) \
+	(((x) == STORE) ? \
+	  "STORE" : \
+		  (((x) == SNULL) ? \
+		  "SNULL" : "ERASE") \
+	)
+#define check_erase2_debug 0
+
+/* Calculate the overwritten entries. */
+int mas_ce2_over_count(struct ma_state *mas_start, struct ma_state *mas_end,
+		      void *s_entry, unsigned long s_min,
+		      void *e_entry, unsigned long e_max,
+		      unsigned long *set, int i, bool null_entry)
+{
+	int count = 0, span = 0;
+	unsigned long retry = 0;
+	void *entry;
+	struct ma_state tmp;
+
+
+	/* count slots */
+	memcpy(&tmp, mas_start, sizeof(tmp));
+	entry = mas_next(&tmp, mas_end->last);
+	while (entry) {
+		BUG_ON(retry > 50); /* stop infinite retry on testing. */
+		if (xa_is_zero(s_entry)) {
+			retry++;
+			continue;
+		}
+		count++;
+		span++;
+		entry = mas_next(&tmp, mas_end->last);
+	}
+
+	if (null_entry) {
+		/* Check splitting end. */
+		if (e_entry && (e_max > mas_end->last))
+			count--;
+
+		/* check overwrite of entire start */
+		if (s_entry && (s_min == mas_start->index))
+			count++;
+	} else { /* !null_entry (store) */
+		bool esplit = e_max > mas_end->last;
+		bool ssplit = s_min != mas_start->index;
+
+		if (s_entry && e_entry) {
+			if (esplit && ssplit)
+				count--;
+			else if (ssplit)
+				count--;
+			else if (esplit) {
+				if (span)
+					count--;
+			}
+		} else if (s_entry && !e_entry) {
+			if (ssplit)
+				count--;
+		} else if (!s_entry && e_entry) {
+			if (esplit)
+				count--;
+			count--;
+		} else {
+			count--;
+		}
+	}
+	return count;
+}
+
+/*
+ * mas_node_walk() - Walk a maple node to offset of the index.
+ * @mas: The maple state
+ * @type: The maple node type
+ * @*range_min: Pointer to store the minimum range of the offset
+ * @*range_max: Pointer to store the maximum range of the offset
+ *
+ * The offset will be stored in the maple state.
+ *
+ */
+static inline void mas_node_walk(struct ma_state *mas, struct maple_node *node,
+			 enum maple_type type, unsigned long *range_min,
+			 unsigned long *range_max)
+
+{
+	unsigned long *pivots;
+	unsigned char count;
+	unsigned long prev, max;
+	unsigned char offset;
+	unsigned long index;
+
+	if (unlikely(ma_is_dense(type))) {
+		(*range_max) = (*range_min) = mas->index;
+		if (unlikely(ma_dead_node(node)))
+			return;
+
+		mas->offset = mas->index = mas->min;
+		return;
+	}
+
+	pivots = ma_pivots(node, type);
+	max = pivots[0];
+	if (unlikely(ma_dead_node(node)))
+		return;
+
+	offset = 0;
+	prev = mas->min;
+	index = mas->index;
+	if (unlikely(index <= max))
+		goto offset_zero;
+
+	count = mt_pivots[type];
+	while (++offset < count) {
+		prev = max;
+		max = pivots[offset];
+		if (unlikely(ma_dead_node(node)))
+			return;
+
+		if (index <= max)
+			goto offset_found;
+		else if (unlikely(!max))
+			goto mas_max;
+	}
+
+	prev = max;
+mas_max:
+	max = mas->max;
+offset_found:
+	prev++;
+offset_zero:
+	mas->offset = offset;
+	if (ma_is_leaf(type)) {
+		*range_max = max;
+		*range_min = prev;
+	} else {
+		mas->max = max;
+		mas->min = prev;
+	}
+}
+
+/*
+ * mas_descend_walk(): Locates a value and sets the mas->node and slot
+ * accordingly.  range_min and range_max are set to the range which the entry is
+ * valid.
+ * @mas: The maple state
+ * @*range_min: A pointer to store the minimum of the range
+ * @*range_max: A pointer to store the maximum of the range
+ *
+ * Check mas->node is still valid on return of any value.
+ *
+ * Return: true if pointing to a valid node and offset.  False otherwise.
+ */
+static inline bool mas_descend_walk(struct ma_state *mas,
+			unsigned long *range_min, unsigned long *range_max)
+{
+	struct maple_enode *next;
+	struct maple_node *node;
+	enum maple_type type;
+
+	next = mas->node;
+	while (true) {
+		node = mte_to_node(next);
+		type = mte_node_type(next);
+		mas_node_walk(mas, node, type, range_min, range_max);
+		next = mas_slot(mas, ma_slots(node, type), mas->offset);
+		if (unlikely(ma_dead_node(node)))
+			return false;
+
+		if (unlikely(ma_is_leaf(type)))
+			return true;
+
+		/* Descend. */
+		mas->node = next;
+	}
+	return false;
+}
+
+/*
+ * mas_tree_walk() - Walk to @mas->index and set the range values.
+ * @mas: The maple state.
+ * @*range_min: The minimum range to be set.
+ * @*range_max: The maximum range to be set.
+ *
+ * Ranges are only valid if there is a valid entry at @mas->index.
+ *
+ * Return: True if a value exists, false otherwise.
+ */
+static inline bool mas_tree_walk(struct ma_state *mas, unsigned long *range_min,
+				 unsigned long *range_max)
+{
+	bool ret;
+
+retry:
+	ret = false;
+	mas_start(mas);
+	if (mas_is_none(mas))
+		goto not_found;
+
+	if (mas_is_ptr(mas)) {
+		*range_min = *range_max = 0;
+		if (!mas->index)
+			return true;
+
+		goto not_found;
+	}
+
+	ret = mas_descend_walk(mas, range_min, range_max);
+	if (unlikely(mte_dead_node(mas->node))) {
+		mas->node = MAS_START;
+		goto retry;
+	}
+
+	return ret;
+
+not_found:
+	mas->offset = MAPLE_NODE_SLOTS;
+	return false;
+}
+
+static inline void *mas_range_load(struct ma_state *mas,
+	   unsigned long *range_min, unsigned long *range_max)
+
+{
+	void *entry = NULL;
+	unsigned long index = mas->index;
+
+	if (mas_is_none(mas) || mas_is_paused(mas))
+		mas->node = MAS_START;
+retry:
+	if (mas_tree_walk(mas, range_min, range_max))
+		if (unlikely(mas->node == MAS_ROOT))
+			return mas_root(mas);
+
+	if (likely(mas->offset != MAPLE_NODE_SLOTS))
+		entry = mas_get_slot(mas, mas->offset);
+
+	if (mas_dead_node(mas, index))
+		goto retry;
+
+	return entry;
+}
+
+#if defined(CONFIG_64BIT)
+static noinline void check_erase2_testset(struct maple_tree *mt,
+		unsigned long *set, unsigned long size)
+{
+	int entry_count = 0;
+	int check = 0;
+	void *foo;
+	unsigned long addr = 0;
+	void *s_entry = NULL, *e_entry = NULL;
+
+	MA_STATE(mas, mt, 0, 0);
+
+	for (int i = 0; i < size; i += 3) {
+		unsigned long s_min, s_max;
+		unsigned long e_min, e_max;
+		void *value = NULL;
+
+		MA_STATE(mas_start, mt, set[i+1], set[i+1]);
+		MA_STATE(mas_end, mt, set[i+2], set[i+2]);
+		mt_set_non_kernel(127);
+#if check_erase2_debug
+		pr_err("%s: %d %s %lu - %lu\n", __func__, i,
+				ec_type_str(set[i]),
+				set[i+1], set[i+2]);
+#endif
+		s_entry = mas_range_load(&mas_start, &s_min, &s_max);
+		e_entry = mas_range_load(&mas_end, &e_min, &e_max);
+
+		switch (set[i]) {
+		case SNULL:
+			if ((s_min == set[i+1]) && (s_max == set[i+2])) {
+				if (s_entry)
+					entry_count--;
+			} else if ((s_min != set[i+1]) && (s_max != set[i+2])) {
+				entry_count++;
+			} else if ((mas_start.node != mas_end.node) ||
+			   (mas_start.offset != mas_end.offset)) {
+				entry_count -=
+				   mas_ce2_over_count(&mas_start, &mas_end,
+						    s_