1	// SPDX-License-Identifier: GPL-2.0+
2	/*
3	* test_maple_tree.c: Test the maple tree API
4	* Copyright (c) 2018-2022 Oracle Corporation
5	* Author: Liam R. Howlett <Liam.Howlett@Oracle.com>
6	*
7	* Any tests that only require the interface of the tree.
8	*/
9
10	#include <linux/maple_tree.h>
11	#include <linux/module.h>
12	#include <linux/rwsem.h>
13
14	#define MTREE_ALLOC_MAX 0x2000000000000Ul
15	#define CONFIG_MAPLE_SEARCH
16	#define MAPLE_32BIT (MAPLE_NODE_SLOTS > 31)
17
18	#ifndef CONFIG_DEBUG_MAPLE_TREE
19	#define mt_dump(mt, fmt) do {} while (0)
20	#define mt_validate(mt) do {} while (0)
21	#define mt_cache_shrink() do {} while (0)
22	#define mas_dump(mas) do {} while (0)
23	#define mas_wr_dump(mas) do {} while (0)
24	atomic_t maple_tree_tests_run;
25	atomic_t maple_tree_tests_passed;
26	#undef MT_BUG_ON
27
28	#define MT_BUG_ON(__tree, __x) do { \
29	atomic_inc(&maple_tree_tests_run); \
30	if (__x) { \
31	pr_info("BUG at %s:%d (%u)\n", \
32	__func__, __LINE__, __x); \
33	pr_info("Pass: %u Run:%u\n", \
34	atomic_read(&maple_tree_tests_passed), \
35	atomic_read(&maple_tree_tests_run)); \
36	} else { \
37	atomic_inc(&maple_tree_tests_passed); \
38	} \
39	} while (0)
40	#endif
41
42	/* #define BENCH_SLOT_STORE */
43	/* #define BENCH_NODE_STORE */
44	/* #define BENCH_AWALK */
45	/* #define BENCH_WALK */
46	/* #define BENCH_LOAD */
47	/* #define BENCH_MT_FOR_EACH */
48	/* #define BENCH_FORK */
49	/* #define BENCH_MAS_FOR_EACH */
50	/* #define BENCH_MAS_PREV */
51
52	#ifdef __KERNEL__
53	#define mt_set_non_kernel(x) do {} while (0)
54	#define mt_zero_nr_tallocated(x) do {} while (0)
55	#else
56	#define cond_resched() do {} while (0)
57	#endif
58
59	#define mas_is_none(x) ((x)->status == ma_none)
60	#define mas_is_overflow(x) ((x)->status == ma_overflow)
61	#define mas_is_underflow(x) ((x)->status == ma_underflow)
62
63	static int __init mtree_insert_index(struct maple_tree *mt,
64	unsigned long index, gfp_t gfp)
65	{
66	return mtree_insert(mt, index, entry: xa_mk_value(v: index & LONG_MAX), gfp);
67	}
68
69	static void __init mtree_erase_index(struct maple_tree *mt, unsigned long index)
70	{
71	MT_BUG_ON(mt, mtree_erase(mt, index) != xa_mk_value(index & LONG_MAX));
72	MT_BUG_ON(mt, mtree_load(mt, index) != NULL);
73	}
74
75	static int __init mtree_test_insert(struct maple_tree *mt, unsigned long index,
76	void *ptr)
77	{
78	return mtree_insert(mt, index, entry: ptr, GFP_KERNEL);
79	}
80
81	static int __init mtree_test_store_range(struct maple_tree *mt,
82	unsigned long start, unsigned long end, void *ptr)
83	{
84	return mtree_store_range(mt, first: start, last: end, entry: ptr, GFP_KERNEL);
85	}
86
87	static int __init mtree_test_store(struct maple_tree *mt, unsigned long start,
88	void *ptr)
89	{
90	return mtree_test_store_range(mt, start, end: start, ptr);
91	}
92
93	static int __init mtree_test_insert_range(struct maple_tree *mt,
94	unsigned long start, unsigned long end, void *ptr)
95	{
96	return mtree_insert_range(mt, first: start, last: end, entry: ptr, GFP_KERNEL);
97	}
98
99	static void __init *mtree_test_load(struct maple_tree *mt, unsigned long index)
100	{
101	return mtree_load(mt, index);
102	}
103
104	static void __init *mtree_test_erase(struct maple_tree *mt, unsigned long index)
105	{
106	return mtree_erase(mt, index);
107	}
108
109	#if defined(CONFIG_64BIT)
110	static noinline void __init check_mtree_alloc_range(struct maple_tree *mt,
111	unsigned long start, unsigned long end, unsigned long size,
112	unsigned long expected, int eret, void *ptr)
113	{
114
115	unsigned long result = expected + 1;
116	int ret;
117
118	ret = mtree_alloc_range(mt, startp: &result, entry: ptr, size, min: start, max: end,
119	GFP_KERNEL);
120	MT_BUG_ON(mt, ret != eret);
121	if (ret)
122	return;
123
124	MT_BUG_ON(mt, result != expected);
125	}
126
127	static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
128	unsigned long start, unsigned long end, unsigned long size,
129	unsigned long expected, int eret, void *ptr)
130	{
131
132	unsigned long result = expected + 1;
133	int ret;
134
135	ret = mtree_alloc_rrange(mt, startp: &result, entry: ptr, size, min: start, max: end,
136	GFP_KERNEL);
137	MT_BUG_ON(mt, ret != eret);
138	if (ret)
139	return;
140
141	MT_BUG_ON(mt, result != expected);
142	}
143	#endif
144
145	static noinline void __init check_load(struct maple_tree *mt,
146	unsigned long index, void *ptr)
147	{
148	void *ret = mtree_test_load(mt, index);
149
150	if (ret != ptr)
151	pr_err("Load %lu returned %p expect %p\n", index, ret, ptr);
152	MT_BUG_ON(mt, ret != ptr);
153	}
154
155	static noinline void __init check_store_range(struct maple_tree *mt,
156	unsigned long start, unsigned long end, void *ptr, int expected)
157	{
158	int ret = -EINVAL;
159	unsigned long i;
160
161	ret = mtree_test_store_range(mt, start, end, ptr);
162	MT_BUG_ON(mt, ret != expected);
163
164	if (ret)
165	return;
166
167	for (i = start; i <= end; i++)
168	check_load(mt, index: i, ptr);
169	}
170
171	static noinline void __init check_insert_range(struct maple_tree *mt,
172	unsigned long start, unsigned long end, void *ptr, int expected)
173	{
174	int ret = -EINVAL;
175	unsigned long i;
176
177	ret = mtree_test_insert_range(mt, start, end, ptr);
178	MT_BUG_ON(mt, ret != expected);
179
180	if (ret)
181	return;
182
183	for (i = start; i <= end; i++)
184	check_load(mt, index: i, ptr);
185	}
186
187	static noinline void __init check_insert(struct maple_tree *mt,
188	unsigned long index, void *ptr)
189	{
190	int ret = -EINVAL;
191
192	ret = mtree_test_insert(mt, index, ptr);
193	MT_BUG_ON(mt, ret != 0);
194	}
195
196	static noinline void __init check_dup_insert(struct maple_tree *mt,
197	unsigned long index, void *ptr)
198	{
199	int ret = -EINVAL;
200
201	ret = mtree_test_insert(mt, index, ptr);
202	MT_BUG_ON(mt, ret != -EEXIST);
203	}
204
205
206	static noinline void __init check_index_load(struct maple_tree *mt,
207	unsigned long index)
208	{
209	return check_load(mt, index, ptr: xa_mk_value(v: index & LONG_MAX));
210	}
211
212	static inline __init int not_empty(struct maple_node *node)
213	{
214	int i;
215
216	if (node->parent)
217	return 1;
218
219	for (i = 0; i < ARRAY_SIZE(node->slot); i++)
220	if (node->slot[i])
221	return 1;
222
223	return 0;
224	}
225
226
227	static noinline void __init check_rev_seq(struct maple_tree *mt,
228	unsigned long max, bool verbose)
229	{
230	unsigned long i = max, j;
231
232	MT_BUG_ON(mt, !mtree_empty(mt));
233
234	mt_zero_nr_tallocated();
235	while (i) {
236	MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
237	for (j = i; j <= max; j++)
238	check_index_load(mt, index: j);
239
240	check_load(mt, index: i - 1, NULL);
241	mt_set_in_rcu(mt);
242	MT_BUG_ON(mt, !mt_height(mt));
243	mt_clear_in_rcu(mt);
244	MT_BUG_ON(mt, !mt_height(mt));
245	i--;
246	}
247	check_load(mt, index: max + 1, NULL);
248
249	#ifndef __KERNEL__
250	if (verbose) {
251	rcu_barrier();
252	mt_dump(mt, mt_dump_dec);
253	pr_info(" %s test of 0-%lu %luK in %d active (%d total)\n",
254	__func__, max, mt_get_alloc_size()/1024, mt_nr_allocated(),
255	mt_nr_tallocated());
256	}
257	#endif
258	}
259
260	static noinline void __init check_seq(struct maple_tree *mt, unsigned long max,
261	bool verbose)
262	{
263	unsigned long i, j;
264
265	MT_BUG_ON(mt, !mtree_empty(mt));
266
267	mt_zero_nr_tallocated();
268	for (i = 0; i <= max; i++) {
269	MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL));
270	for (j = 0; j <= i; j++)
271	check_index_load(mt, index: j);
272
273	if (i)
274	MT_BUG_ON(mt, !mt_height(mt));
275	check_load(mt, index: i + 1, NULL);
276	}
277
278	#ifndef __KERNEL__
279	if (verbose) {
280	rcu_barrier();
281	mt_dump(mt, mt_dump_dec);
282	pr_info(" seq test of 0-%lu %luK in %d active (%d total)\n",
283	max, mt_get_alloc_size()/1024, mt_nr_allocated(),
284	mt_nr_tallocated());
285	}
286	#endif
287	}
288
289	static noinline void __init check_lb_not_empty(struct maple_tree *mt)
290	{
291	unsigned long i, j;
292	unsigned long huge = 4000UL * 1000 * 1000;
293
294
295	i = huge;
296	while (i > 4096) {
297	check_insert(mt, index: i, ptr: (void *) i);
298	for (j = huge; j >= i; j /= 2) {
299	check_load(mt, index: j-1, NULL);
300	check_load(mt, index: j, ptr: (void *) j);
301	check_load(mt, index: j+1, NULL);
302	}
303	i /= 2;
304	}
305	mtree_destroy(mt);
306	}
307
308	static noinline void __init check_lower_bound_split(struct maple_tree *mt)
309	{
310	MT_BUG_ON(mt, !mtree_empty(mt));
311	check_lb_not_empty(mt);
312	}
313
314	static noinline void __init check_upper_bound_split(struct maple_tree *mt)
315	{
316	unsigned long i, j;
317	unsigned long huge;
318
319	MT_BUG_ON(mt, !mtree_empty(mt));
320
321	if (MAPLE_32BIT)
322	huge = 2147483647UL;
323	else
324	huge = 4000UL * 1000 * 1000;
325
326	i = 4096;
327	while (i < huge) {
328	check_insert(mt, index: i, ptr: (void *) i);
329	for (j = i; j >= huge; j *= 2) {
330	check_load(mt, index: j-1, NULL);
331	check_load(mt, index: j, ptr: (void *) j);
332	check_load(mt, index: j+1, NULL);
333	}
334	i *= 2;
335	}
336	mtree_destroy(mt);
337	}
338
339	static noinline void __init check_mid_split(struct maple_tree *mt)
340	{
341	unsigned long huge = 8000UL * 1000 * 1000;
342
343	check_insert(mt, index: huge, ptr: (void *) huge);
344	check_insert(mt, index: 0, ptr: xa_mk_value(v: 0));
345	check_lb_not_empty(mt);
346	}
347
348	static noinline void __init check_rev_find(struct maple_tree *mt)
349	{
350	int i, nr_entries = 200;
351	void *val;
352	MA_STATE(mas, mt, 0, 0);
353
354	for (i = 0; i <= nr_entries; i++)
355	mtree_store_range(mt, first: i*10, last: i*10 + 5,
356	entry: xa_mk_value(v: i), GFP_KERNEL);
357
358	rcu_read_lock();
359	mas_set(mas: &mas, index: 1000);
360	val = mas_find_rev(mas: &mas, min: 1000);
361	MT_BUG_ON(mt, val != xa_mk_value(100));
362	val = mas_find_rev(mas: &mas, min: 1000);
363	MT_BUG_ON(mt, val != NULL);
364
365	mas_set(mas: &mas, index: 999);
366	val = mas_find_rev(mas: &mas, min: 997);
367	MT_BUG_ON(mt, val != NULL);
368
369	mas_set(mas: &mas, index: 1000);
370	val = mas_find_rev(mas: &mas, min: 900);
371	MT_BUG_ON(mt, val != xa_mk_value(100));
372	val = mas_find_rev(mas: &mas, min: 900);
373	MT_BUG_ON(mt, val != xa_mk_value(99));
374
375	mas_set(mas: &mas, index: 20);
376	val = mas_find_rev(mas: &mas, min: 0);
377	MT_BUG_ON(mt, val != xa_mk_value(2));
378	val = mas_find_rev(mas: &mas, min: 0);
379	MT_BUG_ON(mt, val != xa_mk_value(1));
380	val = mas_find_rev(mas: &mas, min: 0);
381	MT_BUG_ON(mt, val != xa_mk_value(0));
382	val = mas_find_rev(mas: &mas, min: 0);
383	MT_BUG_ON(mt, val != NULL);
384	rcu_read_unlock();
385	}
386
387	static noinline void __init check_find(struct maple_tree *mt)
388	{
389	unsigned long val = 0;
390	unsigned long count;
391	unsigned long max;
392	unsigned long top;
393	unsigned long last = 0, index = 0;
394	void *entry, *entry2;
395
396	MA_STATE(mas, mt, 0, 0);
397
398	/* Insert 0. */
399	MT_BUG_ON(mt, mtree_insert_index(mt, val++, GFP_KERNEL));
400
401	#if defined(CONFIG_64BIT)
402	top = 4398046511104UL;
403	#else
404	top = ULONG_MAX;
405	#endif
406
407	if (MAPLE_32BIT) {
408	count = 15;
409	} else {
410	count = 20;
411	}
412
413	for (int i = 0; i <= count; i++) {
414	if (val != 64)
415	MT_BUG_ON(mt, mtree_insert_index(mt, val, GFP_KERNEL));
416	else
417	MT_BUG_ON(mt, mtree_insert(mt, val,
418	XA_ZERO_ENTRY, GFP_KERNEL));
419
420	val <<= 2;
421	}
422
423	val = 0;
424	mas_set(mas: &mas, index: val);
425	mas_lock(&mas);
426	while ((entry = mas_find(mas: &mas, max: 268435456)) != NULL) {
427	if (val != 64)
428	MT_BUG_ON(mt, xa_mk_value(val) != entry);
429	else
430	MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
431
432	val <<= 2;
433	/* For zero check. */
434	if (!val)
435	val = 1;
436	}
437	mas_unlock(&mas);
438
439	val = 0;
440	mas_set(mas: &mas, index: val);
441	mas_lock(&mas);
442	mas_for_each(&mas, entry, ULONG_MAX) {
443	if (val != 64)
444	MT_BUG_ON(mt, xa_mk_value(val) != entry);
445	else
446	MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
447	val <<= 2;
448	/* For zero check. */
449	if (!val)
450	val = 1;
451	}
452	mas_unlock(&mas);
453
454	/* Test mas_pause */
455	val = 0;
456	mas_set(mas: &mas, index: val);
457	mas_lock(&mas);
458	mas_for_each(&mas, entry, ULONG_MAX) {
459	if (val != 64)
460	MT_BUG_ON(mt, xa_mk_value(val) != entry);
461	else
462	MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
463	val <<= 2;
464	/* For zero check. */
465	if (!val)
466	val = 1;
467
468	mas_pause(mas: &mas);
469	mas_unlock(&mas);
470	mas_lock(&mas);
471	}
472	mas_unlock(&mas);
473
474	val = 0;
475	max = 300; /* A value big enough to include XA_ZERO_ENTRY at 64. */
476	mt_for_each(mt, entry, index, max) {
477	MT_BUG_ON(mt, xa_mk_value(val) != entry);
478	val <<= 2;
479	if (val == 64) /* Skip zero entry. */
480	val <<= 2;
481	/* For zero check. */
482	if (!val)
483	val = 1;
484	}
485
486	val = 0;
487	max = 0;
488	index = 0;
489	MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
490	mt_for_each(mt, entry, index, ULONG_MAX) {
491	if (val == top)
492	MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
493	else
494	MT_BUG_ON(mt, xa_mk_value(val) != entry);
495
496	/* Workaround for 32bit */
497	if ((val << 2) < val)
498	val = ULONG_MAX;
499	else
500	val <<= 2;
501
502	if (val == 64) /* Skip zero entry. */
503	val <<= 2;
504	/* For zero check. */
505	if (!val)
506	val = 1;
507	max++;
508	MT_BUG_ON(mt, max > 25);
509	}
510	mtree_erase_index(mt, ULONG_MAX);
511
512	mas_reset(mas: &mas);
513	index = 17;
514	entry = mt_find(mt, index: &index, max: 512);
515	MT_BUG_ON(mt, xa_mk_value(256) != entry);
516
517	mas_reset(mas: &mas);
518	index = 17;
519	entry = mt_find(mt, index: &index, max: 20);
520	MT_BUG_ON(mt, entry != NULL);
521
522
523	/* Range check.. */
524	/* Insert ULONG_MAX */
525	MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL));
526
527	val = 0;
528	mas_set(mas: &mas, index: 0);
529	mas_lock(&mas);
530	mas_for_each(&mas, entry, ULONG_MAX) {
531	if (val == 64)
532	MT_BUG_ON(mt, entry != XA_ZERO_ENTRY);
533	else if (val == top)
534	MT_BUG_ON(mt, entry != xa_mk_value(LONG_MAX));
535	else
536	MT_BUG_ON(mt, xa_mk_value(val) != entry);
537
538	/* Workaround for 32bit */
539	if ((val << 2) < val)
540	val = ULONG_MAX;
541	else
542	val <<= 2;
543
544	/* For zero check. */
545	if (!val)
546	val = 1;
547	mas_pause(mas: &mas);
548	mas_unlock(&mas);
549	mas_lock(&mas);
550	}
551	mas_unlock(&mas);
552
553	mas_set(mas: &mas, index: 1048576);
554	mas_lock(&mas);
555	entry = mas_find(mas: &mas, max: 1048576);
556	mas_unlock(&mas);
557	MT_BUG_ON(mas.tree, entry == NULL);
558
559	/*
560	* Find last value.
561	* 1. get the expected value, leveraging the existence of an end entry
562	* 2. delete end entry
563	* 3. find the last value but searching for ULONG_MAX and then using
564	* prev
565	*/
566	/* First, get the expected result. */
567	mas_lock(&mas);
568	mas_reset(mas: &mas);
569	mas.index = ULONG_MAX; /* start at max.. */
570	entry = mas_find(mas: &mas, ULONG_MAX);
571	entry = mas_prev(mas: &mas, min: 0);
572	index = mas.index;
573	last = mas.last;
574
575	/* Erase the last entry. */
576	mas_reset(mas: &mas);
577	mas.index = ULONG_MAX;
578	mas.last = ULONG_MAX;
579	mas_erase(mas: &mas);
580
581	/* Get the previous value from MAS_START */
582	mas_reset(mas: &mas);
583	entry2 = mas_prev(mas: &mas, min: 0);
584
585	/* Check results. */
586	MT_BUG_ON(mt, entry != entry2);
587	MT_BUG_ON(mt, index != mas.index);
588	MT_BUG_ON(mt, last != mas.last);
589
590
591	mas.status = ma_none;
592	mas.index = ULONG_MAX;
593	mas.last = ULONG_MAX;
594	entry2 = mas_prev(mas: &mas, min: 0);
595	MT_BUG_ON(mt, entry != entry2);
596
597	mas_set(mas: &mas, index: 0);
598	MT_BUG_ON(mt, mas_prev(&mas, 0) != NULL);
599
600	mas_unlock(&mas);
601	mtree_destroy(mt);
602	}
603
604	static noinline void __init check_find_2(struct maple_tree *mt)
605	{
606	unsigned long i, j;
607	void *entry;
608
609	MA_STATE(mas, mt, 0, 0);
610	rcu_read_lock();
611	mas_for_each(&mas, entry, ULONG_MAX)
612	MT_BUG_ON(mt, true);
613	rcu_read_unlock();
614
615	for (i = 0; i < 256; i++) {
616	mtree_insert_index(mt, index: i, GFP_KERNEL);
617	j = 0;
618	mas_set(mas: &mas, index: 0);
619	rcu_read_lock();
620	mas_for_each(&mas, entry, ULONG_MAX) {
621	MT_BUG_ON(mt, entry != xa_mk_value(j));
622	j++;
623	}
624	rcu_read_unlock();
625	MT_BUG_ON(mt, j != i + 1);
626	}
627
628	for (i = 0; i < 256; i++) {
629	mtree_erase_index(mt, index: i);
630	j = i + 1;
631	mas_set(mas: &mas, index: 0);
632	rcu_read_lock();
633	mas_for_each(&mas, entry, ULONG_MAX) {
634	if (xa_is_zero(entry))
635	continue;
636
637	MT_BUG_ON(mt, entry != xa_mk_value(j));
638	j++;
639	}
640	rcu_read_unlock();
641	MT_BUG_ON(mt, j != 256);
642	}
643
644	/*MT_BUG_ON(mt, !mtree_empty(mt)); */
645	}
646
647
648	#if defined(CONFIG_64BIT)
649	static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
650	{
651	/*
652	* Generated by:
653	* cat /proc/self/maps | awk '{print $1}'|
654	* awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
655	*/
656
657	static const unsigned long range[] = {
658	/* Inclusive , Exclusive. */
659	0x565234af2000, 0x565234af4000,
660	0x565234af4000, 0x565234af9000,
661	0x565234af9000, 0x565234afb000,
662	0x565234afc000, 0x565234afd000,
663	0x565234afd000, 0x565234afe000,
664	0x565235def000, 0x565235e10000,
665	0x7f36d4bfd000, 0x7f36d4ee2000,
666	0x7f36d4ee2000, 0x7f36d4f04000,
667	0x7f36d4f04000, 0x7f36d504c000,
668	0x7f36d504c000, 0x7f36d5098000,
669	0x7f36d5098000, 0x7f36d5099000,
670	0x7f36d5099000, 0x7f36d509d000,
671	0x7f36d509d000, 0x7f36d509f000,
672	0x7f36d509f000, 0x7f36d50a5000,
673	0x7f36d50b9000, 0x7f36d50db000,
674	0x7f36d50db000, 0x7f36d50dc000,
675	0x7f36d50dc000, 0x7f36d50fa000,
676	0x7f36d50fa000, 0x7f36d5102000,
677	0x7f36d5102000, 0x7f36d5103000,
678	0x7f36d5103000, 0x7f36d5104000,
679	0x7f36d5104000, 0x7f36d5105000,
680	0x7fff5876b000, 0x7fff5878d000,
681	0x7fff5878e000, 0x7fff58791000,
682	0x7fff58791000, 0x7fff58793000,
683	};
684
685	static const unsigned long holes[] = {
686	/*
687	* Note: start of hole is INCLUSIVE
688	* end of hole is EXCLUSIVE
689	* (opposite of the above table.)
690	* Start of hole, end of hole, size of hole (+1)
691	*/
692	0x565234afb000, 0x565234afc000, 0x1000,
693	0x565234afe000, 0x565235def000, 0x12F1000,
694	0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
695	};
696
697	/*
698	* req_range consists of 4 values.
699	* 1. min index
700	* 2. max index
701	* 3. size
702	* 4. number that should be returned.
703	* 5. return value
704	*/
705	static const unsigned long req_range[] = {
706	0x565234af9000, /* Min */
707	0x7fff58791000, /* Max */
708	0x1000, /* Size */
709	0x7fff5878d << 12, /* First rev hole of size 0x1000 */
710	0, /* Return value success. */
711
712	0x0, /* Min */
713	0x565234AF0 << 12, /* Max */
714	0x3000, /* Size */
715	0x565234AEE << 12, /* max - 3. */
716	0, /* Return value success. */
717
718	0x0, /* Min */
719	-1, /* Max */
720	0x1000, /* Size */
721	562949953421311 << 12,/* First rev hole of size 0x1000 */
722	0, /* Return value success. */
723
724	0x0, /* Min */
725	0x7F36D5109 << 12, /* Max */
726	0x4000, /* Size */
727	0x7F36D5106 << 12, /* First rev hole of size 0x4000 */
728	0, /* Return value success. */
729
730	/* Ascend test. */
731	0x0,
732	34148798628 << 12,
733	19 << 12,
734	34148797418 << 12,
735	0x0,
736
737	/* Too big test. */
738	0x0,
739	18446744073709551615UL,
740	562915594369134UL << 12,
741	0x0,
742	-EBUSY,
743
744	/* Single space test. */
745	34148798725 << 12,
746	34148798725 << 12,
747	1 << 12,
748	34148798725 << 12,
749	0,
750	};
751
752	int i, range_count = ARRAY_SIZE(range);
753	int req_range_count = ARRAY_SIZE(req_range);
754	unsigned long min = 0;
755
756	MA_STATE(mas, mt, 0, 0);
757
758	mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
759	GFP_KERNEL);
760	#define DEBUG_REV_RANGE 0
761	for (i = 0; i < range_count; i += 2) {
762	/* Inclusive, Inclusive (with the -1) */
763
764	#if DEBUG_REV_RANGE
765	pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12,
766	(range[i + 1] >> 12) - 1);
767	#endif
768	check_insert_range(mt, start: range[i] >> 12, end: (range[i + 1] >> 12) - 1,
769	ptr: xa_mk_value(v: range[i] >> 12), expected: 0);
770	mt_validate(mt);
771	}
772
773
774	mas_lock(&mas);
775	for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
776	#if DEBUG_REV_RANGE
777	pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n",
778	min, holes[i+1]>>12, holes[i+2]>>12,
779	holes[i] >> 12);
780	#endif
781	MT_BUG_ON(mt, mas_empty_area_rev(&mas, min,
782	holes[i+1] >> 12,
783	holes[i+2] >> 12));
784	#if DEBUG_REV_RANGE
785	pr_debug("Found %lu %lu\n", mas.index, mas.last);
786	pr_debug("gap %lu %lu\n", (holes[i] >> 12),
787	(holes[i+1] >> 12));
788	#endif
789	MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12));
790	MT_BUG_ON(mt, mas.index != (holes[i+1] >> 12) - (holes[i+2] >> 12));
791	min = holes[i+1] >> 12;
792	mas_reset(mas: &mas);
793	}
794
795	mas_unlock(&mas);
796	for (i = 0; i < req_range_count; i += 5) {
797	#if DEBUG_REV_RANGE
798	pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
799	i, req_range[i] >> 12,
800	(req_range[i + 1] >> 12),
801	req_range[i+2] >> 12,
802	req_range[i+3] >> 12);
803	#endif
804	check_mtree_alloc_rrange(mt,
805	start: req_range[i] >> 12, /* start */
806	end: req_range[i+1] >> 12, /* end */
807	size: req_range[i+2] >> 12, /* size */
808	expected: req_range[i+3] >> 12, /* expected address */
809	eret: req_range[i+4], /* expected return */
810	ptr: xa_mk_value(v: req_range[i] >> 12)); /* pointer */
811	mt_validate(mt);
812	}
813
814	mt_set_non_kernel(1);
815	mtree_erase(mt, index: 34148798727); /* create a deleted range. */
816	mtree_erase(mt, index: 34148798725);
817	check_mtree_alloc_rrange(mt, start: 0, end: 34359052173, size: 210253414,
818	expected: 34148798725, eret: 0, ptr: mt);
819
820	mtree_destroy(mt);
821	}
822
823	static noinline void __init check_alloc_range(struct maple_tree *mt)
824	{
825	/*
826	* Generated by:
827	* cat /proc/self/maps|awk '{print $1}'|
828	* awk -F "-" '{printf "0x%s, 0x%s, ", $1, $2}'
829	*/
830
831	static const unsigned long range[] = {
832	/* Inclusive , Exclusive. */
833	0x565234af2000, 0x565234af4000,
834	0x565234af4000, 0x565234af9000,
835	0x565234af9000, 0x565234afb000,
836	0x565234afc000, 0x565234afd000,
837	0x565234afd000, 0x565234afe000,
838	0x565235def000, 0x565235e10000,
839	0x7f36d4bfd000, 0x7f36d4ee2000,
840	0x7f36d4ee2000, 0x7f36d4f04000,
841	0x7f36d4f04000, 0x7f36d504c000,
842	0x7f36d504c000, 0x7f36d5098000,
843	0x7f36d5098000, 0x7f36d5099000,
844	0x7f36d5099000, 0x7f36d509d000,
845	0x7f36d509d000, 0x7f36d509f000,
846	0x7f36d509f000, 0x7f36d50a5000,
847	0x7f36d50b9000, 0x7f36d50db000,
848	0x7f36d50db000, 0x7f36d50dc000,
849	0x7f36d50dc000, 0x7f36d50fa000,
850	0x7f36d50fa000, 0x7f36d5102000,
851	0x7f36d5102000, 0x7f36d5103000,
852	0x7f36d5103000, 0x7f36d5104000,
853	0x7f36d5104000, 0x7f36d5105000,
854	0x7fff5876b000, 0x7fff5878d000,
855	0x7fff5878e000, 0x7fff58791000,
856	0x7fff58791000, 0x7fff58793000,
857	};
858	static const unsigned long holes[] = {
859	/* Start of hole, end of hole, size of hole (+1) */
860	0x565234afb000, 0x565234afc000, 0x1000,
861	0x565234afe000, 0x565235def000, 0x12F1000,
862	0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000,
863	};
864
865	/*
866	* req_range consists of 4 values.
867	* 1. min index
868	* 2. max index
869	* 3. size
870	* 4. number that should be returned.
871	* 5. return value
872	*/
873	static const unsigned long req_range[] = {
874	0x565234af9000, /* Min */
875	0x7fff58791000, /* Max */
876	0x1000, /* Size */
877	0x565234afb000, /* First hole in our data of size 1000. */
878	0, /* Return value success. */
879
880	0x0, /* Min */
881	0x7fff58791000, /* Max */
882	0x1F00, /* Size */
883	0x0, /* First hole in our data of size 2000. */
884	0, /* Return value success. */
885
886	/* Test ascend. */
887	34148797436 << 12, /* Min */
888	0x7fff587AF000, /* Max */
889	0x3000, /* Size */
890	34148798629 << 12, /* Expected location */
891	0, /* Return value success. */
892
893	/* Test failing. */
894	34148798623 << 12, /* Min */
895	34148798683 << 12, /* Max */
896	0x15000, /* Size */
897	0, /* Expected location */
898	-EBUSY, /* Return value failed. */
899
900	/* Test filling entire gap. */
901	34148798623 << 12, /* Min */
902	0x7fff587AF000, /* Max */
903	0x10000, /* Size */
904	34148798632 << 12, /* Expected location */
905	0, /* Return value success. */
906
907	/* Test walking off the end of root. */
908	0, /* Min */
909	-1, /* Max */
910	-1, /* Size */
911	0, /* Expected location */
912	-EBUSY, /* Return value failure. */
913
914	/* Test looking for too large a hole across entire range. */
915	0, /* Min */
916	-1, /* Max */
917	4503599618982063UL << 12, /* Size */
918	34359052178 << 12, /* Expected location */
919	-EBUSY, /* Return failure. */
920
921	/* Test a single entry */
922	34148798648 << 12, /* Min */
923	34148798648 << 12, /* Max */
924	4096, /* Size of 1 */
925	34148798648 << 12, /* Location is the same as min/max */
926	0, /* Success */
927	};
928	int i, range_count = ARRAY_SIZE(range);
929	int req_range_count = ARRAY_SIZE(req_range);
930	unsigned long min = 0x565234af2000;
931	MA_STATE(mas, mt, 0, 0);
932
933	mtree_store_range(mt, MTREE_ALLOC_MAX, ULONG_MAX, XA_ZERO_ENTRY,
934	GFP_KERNEL);
935	for (i = 0; i < range_count; i += 2) {
936	#define DEBUG_ALLOC_RANGE 0
937	#if DEBUG_ALLOC_RANGE
938	pr_debug("\tInsert %lu-%lu\n", range[i] >> 12,
939	(range[i + 1] >> 12) - 1);
940	mt_dump(mt, mt_dump_hex);
941	#endif
942	check_insert_range(mt, start: range[i] >> 12, end: (range[i + 1] >> 12) - 1,
943	ptr: xa_mk_value(v: range[i] >> 12), expected: 0);
944	mt_validate(mt);
945	}
946
947
948
949	mas_lock(&mas);
950	for (i = 0; i < ARRAY_SIZE(holes); i += 3) {
951
952	#if DEBUG_ALLOC_RANGE
953	pr_debug("\tGet empty %lu-%lu size %lu (%lx-%lx)\n", min >> 12,
954	holes[i+1] >> 12, holes[i+2] >> 12,
955	min, holes[i+1]);
956	#endif
957	MT_BUG_ON(mt, mas_empty_area(&mas, min >> 12,
958	holes[i+1] >> 12,
959	holes[i+2] >> 12));
960	MT_BUG_ON(mt, mas.index != holes[i] >> 12);
961	min = holes[i+1];
962	mas_reset(mas: &mas);
963	}
964	mas_unlock(&mas);
965	for (i = 0; i < req_range_count; i += 5) {
966	#if DEBUG_ALLOC_RANGE
967	pr_debug("\tTest %d: %lu-%lu size %lu expected %lu (%lu-%lu)\n",
968	i/5, req_range[i] >> 12, req_range[i + 1] >> 12,
969	req_range[i + 2] >> 12, req_range[i + 3] >> 12,
970	req_range[i], req_range[i+1]);
971	#endif
972	check_mtree_alloc_range(mt,
973	start: req_range[i] >> 12, /* start */
974	end: req_range[i+1] >> 12, /* end */
975	size: req_range[i+2] >> 12, /* size */
976	expected: req_range[i+3] >> 12, /* expected address */
977	eret: req_range[i+4], /* expected return */
978	ptr: xa_mk_value(v: req_range[i] >> 12)); /* pointer */
979	mt_validate(mt);
980	#if DEBUG_ALLOC_RANGE
981	mt_dump(mt, mt_dump_hex);
982	#endif
983	}
984
985	mtree_destroy(mt);
986	}
987	#endif
988
989	static noinline void __init check_ranges(struct maple_tree *mt)
990	{
991	int i, val, val2;
992	static const unsigned long r[] = {
993	10, 15,
994	20, 25,
995	17, 22, /* Overlaps previous range. */
996	9, 1000, /* Huge. */
997	100, 200,
998	45, 168,
999	118, 128,
1000	};
1001
1002	MT_BUG_ON(mt, !mtree_empty(mt));
1003	check_insert_range(mt, start: r[0], end: r[1], ptr: xa_mk_value(v: r[0]), expected: 0);
1004	check_insert_range(mt, start: r[2], end: r[3], ptr: xa_mk_value(v: r[2]), expected: 0);
1005	check_insert_range(mt, start: r[4], end: r[5], ptr: xa_mk_value(v: r[4]), expected: -EEXIST);
1006	MT_BUG_ON(mt, !mt_height(mt));
1007	/* Store */
1008	check_store_range(mt, start: r[4], end: r[5], ptr: xa_mk_value(v: r[4]), expected: 0);
1009	check_store_range(mt, start: r[6], end: r[7], ptr: xa_mk_value(v: r[6]), expected: 0);
1010	check_store_range(mt, start: r[8], end: r[9], ptr: xa_mk_value(v: r[8]), expected: 0);
1011	MT_BUG_ON(mt, !mt_height(mt));
1012	mtree_destroy(mt);
1013	MT_BUG_ON(mt, mt_height(mt));
1014
1015	check_seq(mt, max: 50, verbose: false);
1016	mt_set_non_kernel(4);
1017	check_store_range(mt, start: 5, end: 47, ptr: xa_mk_value(v: 47), expected: 0);
1018	MT_BUG_ON(mt, !mt_height(mt));
1019	mtree_destroy(mt);
1020
1021	/* Create tree of 1-100 */
1022	check_seq(mt, max: 100, verbose: false);
1023	/* Store 45-168 */
1024	mt_set_non_kernel(10);
1025	check_store_range(mt, start: r[10], end: r[11], ptr: xa_mk_value(v: r[10]), expected: 0);
1026	MT_BUG_ON(mt, !mt_height(mt));
1027	mtree_destroy(mt);
1028
1029	/* Create tree of 1-200 */
1030	check_seq(mt, max: 200, verbose: false);
1031	/* Store 45-168 */
1032	check_store_range(mt, start: r[10], end: r[11], ptr: xa_mk_value(v: r[10]), expected: 0);
1033	MT_BUG_ON(mt, !mt_height(mt));
1034	mtree_destroy(mt);
1035
1036	check_seq(mt, max: 30, verbose: false);
1037	check_store_range(mt, start: 6, end: 18, ptr: xa_mk_value(v: 6), expected: 0);
1038	MT_BUG_ON(mt, !mt_height(mt));
1039	mtree_destroy(mt);
1040
1041	/* Overwrite across multiple levels. */
1042	/* Create tree of 1-400 */
1043	check_seq(mt, max: 400, verbose: false);
1044	mt_set_non_kernel(50);
1045	/* Store 118-128 */
1046	check_store_range(mt, start: r[12], end: r[13], ptr: xa_mk_value(v: r[12]), expected: 0);
1047	mt_set_non_kernel(50);
1048	mtree_test_erase(mt, index: 140);
1049	mtree_test_erase(mt, index: 141);
1050	mtree_test_erase(mt, index: 142);
1051	mtree_test_erase(mt, index: 143);
1052	mtree_test_erase(mt, index: 130);
1053	mtree_test_erase(mt, index: 131);
1054	mtree_test_erase(mt, index: 132);
1055	mtree_test_erase(mt, index: 133);
1056	mtree_test_erase(mt, index: 134);
1057	mtree_test_erase(mt, index: 135);
1058	check_load(mt, index: r[12], ptr: xa_mk_value(v: r[12]));
1059	check_load(mt, index: r[13], ptr: xa_mk_value(v: r[12]));
1060	check_load(mt, index: r[13] - 1, ptr: xa_mk_value(v: r[12]));
1061	check_load(mt, index: r[13] + 1, ptr: xa_mk_value(v: r[13] + 1));
1062	check_load(mt, index: 135, NULL);
1063	check_load(mt, index: 140, NULL);
1064	mt_set_non_kernel(0);
1065	MT_BUG_ON(mt, !mt_height(mt));
1066	mtree_destroy(mt);
1067
1068
1069
1070	/* Overwrite multiple levels at the end of the tree (slot 7) */
1071	mt_set_non_kernel(50);
1072	check_seq(mt, max: 400, verbose: false);
1073	check_store_range(mt, start: 353, end: 361, ptr: xa_mk_value(v: 353), expected: 0);
1074	check_store_range(mt, start: 347, end: 352, ptr: xa_mk_value(v: 347), expected: 0);
1075
1076	check_load(mt, index: 346, ptr: xa_mk_value(v: 346));
1077	for (i = 347; i <= 352; i++)
1078	check_load(mt, index: i, ptr: xa_mk_value(v: 347));
1079	for (i = 353; i <= 361; i++)
1080	check_load(mt, index: i, ptr: xa_mk_value(v: 353));
1081	check_load(mt, index: 362, ptr: xa_mk_value(v: 362));
1082	mt_set_non_kernel(0);
1083	MT_BUG_ON(mt, !mt_height(mt));
1084	mtree_destroy(mt);
1085
1086	mt_set_non_kernel(50);
1087	check_seq(mt, max: 400, verbose: false);
1088	check_store_range(mt, start: 352, end: 364, NULL, expected: 0);
1089	check_store_range(mt, start: 351, end: 363, ptr: xa_mk_value(v: 352), expected: 0);
1090	check_load(mt, index: 350, ptr: xa_mk_value(v: 350));
1091	check_load(mt, index: 351, ptr: xa_mk_value(v: 352));
1092	for (i = 352; i <= 363; i++)
1093	check_load(mt, index: i, ptr: xa_mk_value(v: 352));
1094	check_load(mt, index: 364, NULL);
1095	check_load(mt, index: 365, ptr: xa_mk_value(v: 365));
1096	mt_set_non_kernel(0);
1097	MT_BUG_ON(mt, !mt_height(mt));
1098	mtree_destroy(mt);
1099
1100	mt_set_non_kernel(5);
1101	check_seq(mt, max: 400, verbose: false);
1102	check_store_range(mt, start: 352, end: 364, NULL, expected: 0);
1103	check_store_range(mt, start: 351, end: 364, ptr: xa_mk_value(v: 352), expected: 0);
1104	check_load(mt, index: 350, ptr: xa_mk_value(v: 350));
1105	check_load(mt, index: 351, ptr: xa_mk_value(v: 352));
1106	for (i = 352; i <= 364; i++)
1107	check_load(mt, index: i, ptr: xa_mk_value(v: 352));
1108	check_load(mt, index: 365, ptr: xa_mk_value(v: 365));
1109	mt_set_non_kernel(0);
1110	MT_BUG_ON(mt, !mt_height(mt));
1111	mtree_destroy(mt);
1112
1113
1114	mt_set_non_kernel(50);
1115	check_seq(mt, max: 400, verbose: false);
1116	check_store_range(mt, start: 362, end: 367, ptr: xa_mk_value(v: 362), expected: 0);
1117	check_store_range(mt, start: 353, end: 361, ptr: xa_mk_value(v: 353), expected: 0);
1118	mt_set_non_kernel(0);
1119	mt_validate(mt);
1120	MT_BUG_ON(mt, !mt_height(mt));
1121	mtree_destroy(mt);
1122	/*
1123	* Interesting cases:
1124	* 1. Overwrite the end of a node and end in the first entry of the next
1125	* node.
1126	* 2. Split a single range
1127	* 3. Overwrite the start of a range
1128	* 4. Overwrite the end of a range
1129	* 5. Overwrite the entire range
1130	* 6. Overwrite a range that causes multiple parent nodes to be
1131	* combined
1132	* 7. Overwrite a range that causes multiple parent nodes and part of
1133	* root to be combined
1134	* 8. Overwrite the whole tree
1135	* 9. Try to overwrite the zero entry of an alloc tree.
1136	* 10. Write a range larger than a nodes current pivot
1137	*/
1138
1139	mt_set_non_kernel(50);
1140	for (i = 0; i <= 500; i++) {
1141	val = i*5;
1142	val2 = (i+1)*5;
1143	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1144	}
1145	check_store_range(mt, start: 2400, end: 2400, ptr: xa_mk_value(v: 2400), expected: 0);
1146	check_store_range(mt, start: 2411, end: 2411, ptr: xa_mk_value(v: 2411), expected: 0);
1147	check_store_range(mt, start: 2412, end: 2412, ptr: xa_mk_value(v: 2412), expected: 0);
1148	check_store_range(mt, start: 2396, end: 2400, ptr: xa_mk_value(v: 4052020), expected: 0);
1149	check_store_range(mt, start: 2402, end: 2402, ptr: xa_mk_value(v: 2402), expected: 0);
1150	mtree_destroy(mt);
1151	mt_set_non_kernel(0);
1152
1153	mt_set_non_kernel(50);
1154	for (i = 0; i <= 500; i++) {
1155	val = i*5;
1156	val2 = (i+1)*5;
1157	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1158	}
1159	check_store_range(mt, start: 2422, end: 2422, ptr: xa_mk_value(v: 2422), expected: 0);
1160	check_store_range(mt, start: 2424, end: 2424, ptr: xa_mk_value(v: 2424), expected: 0);
1161	check_store_range(mt, start: 2425, end: 2425, ptr: xa_mk_value(v: 2), expected: 0);
1162	check_store_range(mt, start: 2460, end: 2470, NULL, expected: 0);
1163	check_store_range(mt, start: 2435, end: 2460, ptr: xa_mk_value(v: 2435), expected: 0);
1164	check_store_range(mt, start: 2461, end: 2470, ptr: xa_mk_value(v: 2461), expected: 0);
1165	mt_set_non_kernel(0);
1166	MT_BUG_ON(mt, !mt_height(mt));
1167	mtree_destroy(mt);
1168
1169	/* Check in-place modifications */
1170	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1171	/* Append to the start of last range */
1172	mt_set_non_kernel(50);
1173	for (i = 0; i <= 500; i++) {
1174	val = i * 5 + 1;
1175	val2 = val + 4;
1176	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1177	}
1178
1179	/* Append to the last range without touching any boundaries */
1180	for (i = 0; i < 10; i++) {
1181	val = val2 + 5;
1182	val2 = val + 4;
1183	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1184	}
1185
1186	/* Append to the end of last range */
1187	val = val2;
1188	for (i = 0; i < 10; i++) {
1189	val += 5;
1190	MT_BUG_ON(mt, mtree_test_store_range(mt, val, ULONG_MAX,
1191	xa_mk_value(val)) != 0);
1192	}
1193
1194	/* Overwriting the range and over a part of the next range */
1195	for (i = 10; i < 30; i += 2) {
1196	val = i * 5 + 1;
1197	val2 = val + 5;
1198	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1199	}
1200
1201	/* Overwriting a part of the range and over the next range */
1202	for (i = 50; i < 70; i += 2) {
1203	val2 = i * 5;
1204	val = val2 - 5;
1205	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1206	}
1207
1208	/*
1209	* Expand the range, only partially overwriting the previous and
1210	* next ranges
1211	*/
1212	for (i = 100; i < 130; i += 3) {
1213	val = i * 5 - 5;
1214	val2 = i * 5 + 1;
1215	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1216	}
1217
1218	/*
1219	* Expand the range, only partially overwriting the previous and
1220	* next ranges, in RCU mode
1221	*/
1222	mt_set_in_rcu(mt);
1223	for (i = 150; i < 180; i += 3) {
1224	val = i * 5 - 5;
1225	val2 = i * 5 + 1;
1226	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1227	}
1228
1229	MT_BUG_ON(mt, !mt_height(mt));
1230	mt_validate(mt);
1231	mt_set_non_kernel(0);
1232	mtree_destroy(mt);
1233
1234	/* Test rebalance gaps */
1235	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1236	mt_set_non_kernel(50);
1237	for (i = 0; i <= 50; i++) {
1238	val = i*10;
1239	val2 = (i+1)*10;
1240	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1241	}
1242	check_store_range(mt, start: 161, end: 161, ptr: xa_mk_value(v: 161), expected: 0);
1243	check_store_range(mt, start: 162, end: 162, ptr: xa_mk_value(v: 162), expected: 0);
1244	check_store_range(mt, start: 163, end: 163, ptr: xa_mk_value(v: 163), expected: 0);
1245	check_store_range(mt, start: 240, end: 249, NULL, expected: 0);
1246	mtree_erase(mt, index: 200);
1247	mtree_erase(mt, index: 210);
1248	mtree_erase(mt, index: 220);
1249	mtree_erase(mt, index: 230);
1250	mt_set_non_kernel(0);
1251	MT_BUG_ON(mt, !mt_height(mt));
1252	mtree_destroy(mt);
1253
1254	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1255	for (i = 0; i <= 500; i++) {
1256	val = i*10;
1257	val2 = (i+1)*10;
1258	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1259	}
1260	check_store_range(mt, start: 4600, end: 4959, ptr: xa_mk_value(v: 1), expected: 0);
1261	mt_validate(mt);
1262	MT_BUG_ON(mt, !mt_height(mt));
1263	mtree_destroy(mt);
1264
1265	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1266	for (i = 0; i <= 500; i++) {
1267	val = i*10;
1268	val2 = (i+1)*10;
1269	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1270	}
1271	check_store_range(mt, start: 4811, end: 4811, ptr: xa_mk_value(v: 4811), expected: 0);
1272	check_store_range(mt, start: 4812, end: 4812, ptr: xa_mk_value(v: 4812), expected: 0);
1273	check_store_range(mt, start: 4861, end: 4861, ptr: xa_mk_value(v: 4861), expected: 0);
1274	check_store_range(mt, start: 4862, end: 4862, ptr: xa_mk_value(v: 4862), expected: 0);
1275	check_store_range(mt, start: 4842, end: 4849, NULL, expected: 0);
1276	mt_validate(mt);
1277	MT_BUG_ON(mt, !mt_height(mt));
1278	mtree_destroy(mt);
1279
1280	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1281	for (i = 0; i <= 1300; i++) {
1282	val = i*10;
1283	val2 = (i+1)*10;
1284	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1285	MT_BUG_ON(mt, mt_height(mt) >= 4);
1286	}
1287	/* Cause a 3 child split all the way up the tree. */
1288	for (i = 5; i < 215; i += 10)
1289	check_store_range(mt, start: 11450 + i, end: 11450 + i + 1, NULL, expected: 0);
1290	for (i = 5; i < 65; i += 10)
1291	check_store_range(mt, start: 11770 + i, end: 11770 + i + 1, NULL, expected: 0);
1292
1293	MT_BUG_ON(mt, mt_height(mt) >= 4);
1294	for (i = 5; i < 45; i += 10)
1295	check_store_range(mt, start: 11700 + i, end: 11700 + i + 1, NULL, expected: 0);
1296	if (!MAPLE_32BIT)
1297	MT_BUG_ON(mt, mt_height(mt) < 4);
1298	mtree_destroy(mt);
1299
1300
1301	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1302	for (i = 0; i <= 1200; i++) {
1303	val = i*10;
1304	val2 = (i+1)*10;
1305	check_store_range(mt, start: val, end: val2, ptr: xa_mk_value(v: val), expected: 0);
1306	MT_BUG_ON(mt, mt_height(mt) >= 4);
1307	}
1308	/* Fill parents and leaves before split. */
1309	for (i = 5; i < 455; i += 10)
1310	check_store_range(mt, start: 7800 + i, end: 7800 + i + 1, NULL, expected: 0);
1311
1312	for (i = 1; i < 16; i++)
1313	check_store_range(mt, start: 8185 + i, end: 8185 + i + 1,
1314	ptr: xa_mk_value(v: 8185+i), expected: 0);
1315	MT_BUG_ON(mt, mt_height(mt) >= 4);
1316	/* triple split across multiple levels. */
1317	check_store_range(mt, start: 8184, end: 8184, ptr: xa_mk_value(v: 8184), expected: 0);
1318	if (!MAPLE_32BIT)
1319	MT_BUG_ON(mt, mt_height(mt) != 4);
1320	}
1321
1322	static noinline void __init check_next_entry(struct maple_tree *mt)
1323	{
1324	void *entry = NULL;
1325	unsigned long limit = 30, i = 0;
1326	MA_STATE(mas, mt, i, i);
1327
1328	MT_BUG_ON(mt, !mtree_empty(mt));
1329
1330	check_seq(mt, max: limit, verbose: false);
1331	rcu_read_lock();
1332
1333	/* Check the first one and get ma_state in the correct state. */
1334	MT_BUG_ON(mt, mas_walk(&mas) != xa_mk_value(i++));
1335	for ( ; i <= limit + 1; i++) {
1336	entry = mas_next(mas: &mas, max: limit);
1337	if (i > limit)
1338	MT_BUG_ON(mt, entry != NULL);
1339	else
1340	MT_BUG_ON(mt, xa_mk_value(i) != entry);
1341	}
1342	rcu_read_unlock();
1343	mtree_destroy(mt);
1344	}
1345
1346	static noinline void __init check_prev_entry(struct maple_tree *mt)
1347	{
1348	unsigned long index = 16;
1349	void *value;
1350	int i;
1351
1352	MA_STATE(mas, mt, index, index);
1353
1354	MT_BUG_ON(mt, !mtree_empty(mt));
1355	check_seq(mt, max: 30, verbose: false);
1356
1357	rcu_read_lock();
1358	value = mas_find(mas: &mas, ULONG_MAX);
1359	MT_BUG_ON(mt, value != xa_mk_value(index));
1360	value = mas_prev(mas: &mas, min: 0);
1361	MT_BUG_ON(mt, value != xa_mk_value(index - 1));
1362	rcu_read_unlock();
1363	mtree_destroy(mt);
1364
1365	/* Check limits on prev */
1366	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1367	mas_lock(&mas);
1368	for (i = 0; i <= index; i++) {
1369	mas_set_range(mas: &mas, start: i*10, last: i*10+5);
1370	mas_store_gfp(mas: &mas, entry: xa_mk_value(v: i), GFP_KERNEL);
1371	}
1372
1373	mas_set(mas: &mas, index: 20);
1374	value = mas_walk(mas: &mas);
1375	MT_BUG_ON(mt, value != xa_mk_value(2));
1376
1377	value = mas_prev(mas: &mas, min: 19);
1378	MT_BUG_ON(mt, value != NULL);
1379
1380	mas_set(mas: &mas, index: 80);
1381	value = mas_walk(mas: &mas);
1382	MT_BUG_ON(mt, value != xa_mk_value(8));
1383
1384	value = mas_prev(mas: &mas, min: 76);
1385	MT_BUG_ON(mt, value != NULL);
1386
1387	mas_unlock(&mas);
1388	}
1389
1390	static noinline void __init check_root_expand(struct maple_tree *mt)
1391	{
1392	MA_STATE(mas, mt, 0, 0);
1393	void *ptr;
1394
1395
1396	mas_lock(&mas);
1397	mas_set(mas: &mas, index: 3);
1398	ptr = mas_walk(mas: &mas);
1399	MT_BUG_ON(mt, mas.index != 0);
1400	MT_BUG_ON(mt, ptr != NULL);
1401	MT_BUG_ON(mt, mas.index != 0);
1402	MT_BUG_ON(mt, mas.last != ULONG_MAX);
1403
1404	ptr = &check_prev_entry;
1405	mas_set(mas: &mas, index: 1);
1406	mas_store_gfp(mas: &mas, entry: ptr, GFP_KERNEL);
1407
1408	mas_set(mas: &mas, index: 0);
1409	ptr = mas_walk(mas: &mas);
1410	MT_BUG_ON(mt, ptr != NULL);
1411
1412	mas_set(mas: &mas, index: 1);
1413	ptr = mas_walk(mas: &mas);
1414	MT_BUG_ON(mt, ptr != &check_prev_entry);
1415
1416	mas_set(mas: &mas, index: 2);
1417	ptr = mas_walk(mas: &mas);
1418	MT_BUG_ON(mt, ptr != NULL);
1419	mas_unlock(&mas);
1420	mtree_destroy(mt);
1421
1422
1423	mt_init_flags(mt, flags: 0);
1424	mas_lock(&mas);
1425
1426	mas_set(mas: &mas, index: 0);
1427	ptr = &check_prev_entry;
1428	mas_store_gfp(mas: &mas, entry: ptr, GFP_KERNEL);
1429
1430	mas_set(mas: &mas, index: 5);
1431	ptr = mas_walk(mas: &mas);
1432	MT_BUG_ON(mt, ptr != NULL);
1433	MT_BUG_ON(mt, mas.index != 1);
1434	MT_BUG_ON(mt, mas.last != ULONG_MAX);
1435
1436	mas_set_range(mas: &mas, start: 0, last: 100);
1437	ptr = mas_walk(mas: &mas);
1438	MT_BUG_ON(mt, ptr != &check_prev_entry);
1439	MT_BUG_ON(mt, mas.last != 0);
1440	mas_unlock(&mas);
1441	mtree_destroy(mt);
1442
1443	mt_init_flags(mt, flags: 0);
1444	mas_lock(&mas);
1445
1446	mas_set(mas: &mas, index: 0);
1447	ptr = (void *)((unsigned long) check_prev_entry | 1UL);
1448	mas_store_gfp(mas: &mas, entry: ptr, GFP_KERNEL);
1449	ptr = mas_next(mas: &mas, ULONG_MAX);
1450	MT_BUG_ON(mt, ptr != NULL);
1451	MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));
1452
1453	mas_set(mas: &mas, index: 1);
1454	ptr = mas_prev(mas: &mas, min: 0);
1455	MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1456	MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 1UL));
1457
1458	mas_unlock(&mas);
1459
1460	mtree_destroy(mt);
1461
1462	mt_init_flags(mt, flags: 0);
1463	mas_lock(&mas);
1464	mas_set(mas: &mas, index: 0);
1465	ptr = (void *)((unsigned long) check_prev_entry | 2UL);
1466	mas_store_gfp(mas: &mas, entry: ptr, GFP_KERNEL);
1467	ptr = mas_next(mas: &mas, ULONG_MAX);
1468	MT_BUG_ON(mt, ptr != NULL);
1469	MT_BUG_ON(mt, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));
1470
1471	mas_set(mas: &mas, index: 1);
1472	ptr = mas_prev(mas: &mas, min: 0);
1473	MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1474	MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 2UL));
1475
1476
1477	mas_unlock(&mas);
1478	}
1479
1480	static noinline void __init check_gap_combining(struct maple_tree *mt)
1481	{
1482	struct maple_enode *mn1, *mn2;
1483	void *entry;
1484	unsigned long singletons = 100;
1485	static const unsigned long *seq100;
1486	static const unsigned long seq100_64[] = {
1487	/* 0-5 */
1488	74, 75, 76,
1489	50, 100, 2,
1490
1491	/* 6-12 */
1492	44, 45, 46, 43,
1493	20, 50, 3,
1494
1495	/* 13-20*/
1496	80, 81, 82,
1497	76, 2, 79, 85, 4,
1498	};
1499
1500	static const unsigned long seq100_32[] = {
1501	/* 0-5 */
1502	61, 62, 63,
1503	50, 100, 2,
1504
1505	/* 6-12 */
1506	31, 32, 33, 30,
1507	20, 50, 3,
1508
1509	/* 13-20*/
1510	80, 81, 82,
1511	76, 2, 79, 85, 4,
1512	};
1513
1514	static const unsigned long seq2000[] = {
1515	1152, 1151,
1516	1100, 1200, 2,
1517	};
1518	static const unsigned long seq400[] = {
1519	286, 318,
1520	256, 260, 266, 270, 275, 280, 290, 398,
1521	286, 310,
1522	};
1523
1524	unsigned long index;
1525
1526	MA_STATE(mas, mt, 0, 0);
1527
1528	if (MAPLE_32BIT)
1529	seq100 = seq100_32;
1530	else
1531	seq100 = seq100_64;
1532
1533	index = seq100[0];
1534	mas_set(mas: &mas, index);
1535	MT_BUG_ON(mt, !mtree_empty(mt));
1536	check_seq(mt, max: singletons, verbose: false); /* create 100 singletons. */
1537
1538	mt_set_non_kernel(1);
1539	mtree_test_erase(mt, index: seq100[2]);
1540	check_load(mt, index: seq100[2], NULL);
1541	mtree_test_erase(mt, index: seq100[1]);
1542	check_load(mt, index: seq100[1], NULL);
1543
1544	rcu_read_lock();
1545	entry = mas_find(mas: &mas, ULONG_MAX);
1546	MT_BUG_ON(mt, entry != xa_mk_value(index));
1547	mn1 = mas.node;
1548	mas_next(mas: &mas, ULONG_MAX);
1549	entry = mas_next(mas: &mas, ULONG_MAX);
1550	MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1551	mn2 = mas.node;
1552	MT_BUG_ON(mt, mn1 == mn2); /* test the test. */
1553
1554	/*
1555	* At this point, there is a gap of 2 at index + 1 between seq100[3] and
1556	* seq100[4]. Search for the gap.
1557	*/
1558	mt_set_non_kernel(1);
1559	mas_reset(mas: &mas);
1560	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[3], seq100[4],
1561	seq100[5]));
1562	MT_BUG_ON(mt, mas.index != index + 1);
1563	rcu_read_unlock();
1564
1565	mtree_test_erase(mt, index: seq100[6]);
1566	check_load(mt, index: seq100[6], NULL);
1567	mtree_test_erase(mt, index: seq100[7]);
1568	check_load(mt, index: seq100[7], NULL);
1569	mtree_test_erase(mt, index: seq100[8]);
1570	index = seq100[9];
1571
1572	rcu_read_lock();
1573	mas.index = index;
1574	mas.last = index;
1575	mas_reset(mas: &mas);
1576	entry = mas_find(mas: &mas, ULONG_MAX);
1577	MT_BUG_ON(mt, entry != xa_mk_value(index));
1578	mn1 = mas.node;
1579	entry = mas_next(mas: &mas, ULONG_MAX);
1580	MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1581	mas_next(mas: &mas, ULONG_MAX); /* go to the next entry. */
1582	mn2 = mas.node;
1583	MT_BUG_ON(mt, mn1 == mn2); /* test the next entry is in the next node. */
1584
1585	/*
1586	* At this point, there is a gap of 3 at seq100[6]. Find it by
1587	* searching 20 - 50 for size 3.
1588	*/
1589	mas_reset(mas: &mas);
1590	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[10], seq100[11],
1591	seq100[12]));
1592	MT_BUG_ON(mt, mas.index != seq100[6]);
1593	rcu_read_unlock();
1594
1595	mt_set_non_kernel(1);
1596	mtree_store(mt, index: seq100[13], NULL, GFP_KERNEL);
1597	check_load(mt, index: seq100[13], NULL);
1598	check_load(mt, index: seq100[14], ptr: xa_mk_value(v: seq100[14]));
1599	mtree_store(mt, index: seq100[14], NULL, GFP_KERNEL);
1600	check_load(mt, index: seq100[13], NULL);
1601	check_load(mt, index: seq100[14], NULL);
1602
1603	mas_reset(mas: &mas);
1604	rcu_read_lock();
1605	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[15],
1606	seq100[17]));
1607	MT_BUG_ON(mt, mas.index != seq100[13]);
1608	mt_validate(mt);
1609	rcu_read_unlock();
1610
1611	/*
1612	* *DEPRECATED: no retries anymore* Test retry entry in the start of a
1613	* gap.
1614	*/
1615	mt_set_non_kernel(2);
1616	mtree_test_store_range(mt, start: seq100[18], end: seq100[14], NULL);
1617	mtree_test_erase(mt, index: seq100[15]);
1618	mas_reset(mas: &mas);
1619	rcu_read_lock();
1620	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[19],
1621	seq100[20]));
1622	rcu_read_unlock();
1623	MT_BUG_ON(mt, mas.index != seq100[18]);
1624	mt_validate(mt);
1625	mtree_destroy(mt);
1626
1627	/* seq 2000 tests are for multi-level tree gaps */
1628	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1629	check_seq(mt, max: 2000, verbose: false);
1630	mt_set_non_kernel(1);
1631	mtree_test_erase(mt, index: seq2000[0]);
1632	mtree_test_erase(mt, index: seq2000[1]);
1633
1634	mt_set_non_kernel(2);
1635	mas_reset(mas: &mas);
1636	rcu_read_lock();
1637	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq2000[2], seq2000[3],
1638	seq2000[4]));
1639	MT_BUG_ON(mt, mas.index != seq2000[1]);
1640	rcu_read_unlock();
1641	mt_validate(mt);
1642	mtree_destroy(mt);
1643
1644	/* seq 400 tests rebalancing over two levels. */
1645	mt_set_non_kernel(99);
1646	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1647	check_seq(mt, max: 400, verbose: false);
1648	mtree_test_store_range(mt, start: seq400[0], end: seq400[1], NULL);
1649	mt_set_non_kernel(0);
1650	mtree_destroy(mt);
1651
1652	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1653	check_seq(mt, max: 400, verbose: false);
1654	mt_set_non_kernel(50);
1655	mtree_test_store_range(mt, start: seq400[2], end: seq400[9],
1656	ptr: xa_mk_value(v: seq400[2]));
1657	mtree_test_store_range(mt, start: seq400[3], end: seq400[9],
1658	ptr: xa_mk_value(v: seq400[3]));
1659	mtree_test_store_range(mt, start: seq400[4], end: seq400[9],
1660	ptr: xa_mk_value(v: seq400[4]));
1661	mtree_test_store_range(mt, start: seq400[5], end: seq400[9],
1662	ptr: xa_mk_value(v: seq400[5]));
1663	mtree_test_store_range(mt, start: seq400[0], end: seq400[9],
1664	ptr: xa_mk_value(v: seq400[0]));
1665	mtree_test_store_range(mt, start: seq400[6], end: seq400[9],
1666	ptr: xa_mk_value(v: seq400[6]));
1667	mtree_test_store_range(mt, start: seq400[7], end: seq400[9],
1668	ptr: xa_mk_value(v: seq400[7]));
1669	mtree_test_store_range(mt, start: seq400[8], end: seq400[9],
1670	ptr: xa_mk_value(v: seq400[8]));
1671	mtree_test_store_range(mt, start: seq400[10], end: seq400[11],
1672	ptr: xa_mk_value(v: seq400[10]));
1673	mt_validate(mt);
1674	mt_set_non_kernel(0);
1675	mtree_destroy(mt);
1676	}
1677	static noinline void __init check_node_overwrite(struct maple_tree *mt)
1678	{
1679	int i, max = 4000;
1680
1681	for (i = 0; i < max; i++)
1682	mtree_test_store_range(mt, start: i*100, end: i*100 + 50, ptr: xa_mk_value(v: i*100));
1683
1684	mtree_test_store_range(mt, start: 319951, end: 367950, NULL);
1685	/*mt_dump(mt, mt_dump_dec); */
1686	mt_validate(mt);
1687	}
1688
1689	#if defined(BENCH_SLOT_STORE)
1690	static noinline void __init bench_slot_store(struct maple_tree *mt)
1691	{
1692	int i, brk = 105, max = 1040, brk_start = 100, count = 20000000;
1693
1694	for (i = 0; i < max; i += 10)
1695	mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1696
1697	for (i = 0; i < count; i++) {
1698	mtree_store_range(mt, brk, brk, NULL, GFP_KERNEL);
1699	mtree_store_range(mt, brk_start, brk, xa_mk_value(brk),
1700	GFP_KERNEL);
1701	}
1702	}
1703	#endif
1704
1705	#if defined(BENCH_NODE_STORE)
1706	static noinline void __init bench_node_store(struct maple_tree *mt)
1707	{
1708	int i, overwrite = 76, max = 240, count = 20000000;
1709
1710	for (i = 0; i < max; i += 10)
1711	mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1712
1713	for (i = 0; i < count; i++) {
1714	mtree_store_range(mt, overwrite, overwrite + 15,
1715	xa_mk_value(overwrite), GFP_KERNEL);
1716
1717	overwrite += 5;
1718	if (overwrite >= 135)
1719	overwrite = 76;
1720	}
1721	}
1722	#endif
1723
1724	#if defined(BENCH_AWALK)
1725	static noinline void __init bench_awalk(struct maple_tree *mt)
1726	{
1727	int i, max = 2500, count = 50000000;
1728	MA_STATE(mas, mt, 1470, 1470);
1729
1730	for (i = 0; i < max; i += 10)
1731	mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1732
1733	mtree_store_range(mt, 1470, 1475, NULL, GFP_KERNEL);
1734
1735	for (i = 0; i < count; i++) {
1736	mas_empty_area_rev(&mas, 0, 2000, 10);
1737	mas_reset(&mas);
1738	}
1739	}
1740	#endif
1741	#if defined(BENCH_WALK)
1742	static noinline void __init bench_walk(struct maple_tree *mt)
1743	{
1744	int i, max = 2500, count = 550000000;
1745	MA_STATE(mas, mt, 1470, 1470);
1746
1747	for (i = 0; i < max; i += 10)
1748	mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1749
1750	for (i = 0; i < count; i++) {
1751	mas_walk(&mas);
1752	mas_reset(&mas);
1753	}
1754
1755	}
1756	#endif
1757
1758	#if defined(BENCH_LOAD)
1759	static noinline void __init bench_load(struct maple_tree *mt)
1760	{
1761	int i, max = 2500, count = 550000000;
1762
1763	for (i = 0; i < max; i += 10)
1764	mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1765
1766	for (i = 0; i < count; i++)
1767	mtree_load(mt, 1470);
1768	}
1769	#endif
1770
1771	#if defined(BENCH_MT_FOR_EACH)
1772	static noinline void __init bench_mt_for_each(struct maple_tree *mt)
1773	{
1774	int i, count = 1000000;
1775	unsigned long max = 2500, index = 0;
1776	void *entry;
1777
1778	for (i = 0; i < max; i += 5)
1779	mtree_store_range(mt, i, i + 4, xa_mk_value(i), GFP_KERNEL);
1780
1781	for (i = 0; i < count; i++) {
1782	unsigned long j = 0;
1783
1784	mt_for_each(mt, entry, index, max) {
1785	MT_BUG_ON(mt, entry != xa_mk_value(j));
1786	j += 5;
1787	}
1788
1789	index = 0;
1790	}
1791
1792	}
1793	#endif
1794
1795	#if defined(BENCH_MAS_FOR_EACH)
1796	static noinline void __init bench_mas_for_each(struct maple_tree *mt)
1797	{
1798	int i, count = 1000000;
1799	unsigned long max = 2500;
1800	void *entry;
1801	MA_STATE(mas, mt, 0, 0);
1802
1803	for (i = 0; i < max; i += 5) {
1804	int gap = 4;
1805
1806	if (i % 30 == 0)
1807	gap = 3;
1808	mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1809	}
1810
1811	rcu_read_lock();
1812	for (i = 0; i < count; i++) {
1813	unsigned long j = 0;
1814
1815	mas_for_each(&mas, entry, max) {
1816	MT_BUG_ON(mt, entry != xa_mk_value(j));
1817	j += 5;
1818	}
1819	mas_set(&mas, 0);
1820	}
1821	rcu_read_unlock();
1822
1823	}
1824	#endif
1825	#if defined(BENCH_MAS_PREV)
1826	static noinline void __init bench_mas_prev(struct maple_tree *mt)
1827	{
1828	int i, count = 1000000;
1829	unsigned long max = 2500;
1830	void *entry;
1831	MA_STATE(mas, mt, 0, 0);
1832
1833	for (i = 0; i < max; i += 5) {
1834	int gap = 4;
1835
1836	if (i % 30 == 0)
1837	gap = 3;
1838	mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1839	}
1840
1841	rcu_read_lock();
1842	for (i = 0; i < count; i++) {
1843	unsigned long j = 2495;
1844
1845	mas_set(&mas, ULONG_MAX);
1846	while ((entry = mas_prev(&mas, 0)) != NULL) {
1847	MT_BUG_ON(mt, entry != xa_mk_value(j));
1848	j -= 5;
1849	}
1850	}
1851	rcu_read_unlock();
1852
1853	}
1854	#endif
1855	/* check_forking - simulate the kernel forking sequence with the tree. */
1856	static noinline void __init check_forking(void)
1857	{
1858	struct maple_tree mt, newmt;
1859	int i, nr_entries = 134, ret;
1860	void *val;
1861	MA_STATE(mas, &mt, 0, 0);
1862	MA_STATE(newmas, &newmt, 0, 0);
1863	struct rw_semaphore mt_lock, newmt_lock;
1864
1865	init_rwsem(&mt_lock);
1866	init_rwsem(&newmt_lock);
1867
1868	mt_init_flags(mt: &mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
1869	mt_set_external_lock(&mt, &mt_lock);
1870
1871	mt_init_flags(mt: &newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
1872	mt_set_external_lock(&newmt, &newmt_lock);
1873
1874	down_write(sem: &mt_lock);
1875	for (i = 0; i <= nr_entries; i++) {
1876	mas_set_range(mas: &mas, start: i*10, last: i*10 + 5);
1877	mas_store_gfp(mas: &mas, entry: xa_mk_value(v: i), GFP_KERNEL);
1878	}
1879
1880	down_write_nested(sem: &newmt_lock, SINGLE_DEPTH_NESTING);
1881	ret = __mt_dup(mt: &mt, new: &newmt, GFP_KERNEL);
1882	if (ret) {
1883	pr_err("OOM!");
1884	BUG_ON(1);
1885	}
1886
1887	mas_set(mas: &newmas, index: 0);
1888	mas_for_each(&newmas, val, ULONG_MAX)
1889	mas_store(mas: &newmas, entry: val);
1890
1891	mas_destroy(mas: &newmas);
1892	mas_destroy(mas: &mas);
1893	mt_validate(mt: &newmt);
1894	__mt_destroy(mt: &newmt);
1895	__mt_destroy(mt: &mt);
1896	up_write(sem: &newmt_lock);
1897	up_write(sem: &mt_lock);
1898	}
1899
1900	static noinline void __init check_iteration(struct maple_tree *mt)
1901	{
1902	int i, nr_entries = 125;
1903	void *val;
1904	MA_STATE(mas, mt, 0, 0);
1905
1906	for (i = 0; i <= nr_entries; i++)
1907	mtree_store_range(mt, first: i * 10, last: i * 10 + 9,
1908	entry: xa_mk_value(v: i), GFP_KERNEL);
1909
1910	mt_set_non_kernel(99999);
1911
1912	i = 0;
1913	mas_lock(&mas);
1914	mas_for_each(&mas, val, 925) {
1915	MT_BUG_ON(mt, mas.index != i * 10);
1916	MT_BUG_ON(mt, mas.last != i * 10 + 9);
1917	/* Overwrite end of entry 92 */
1918	if (i == 92) {
1919	mas.index = 925;
1920	mas.last = 929;
1921	mas_store(mas: &mas, entry: val);
1922	}
1923	i++;
1924	}
1925	/* Ensure mas_find() gets the next value */
1926	val = mas_find(mas: &mas, ULONG_MAX);
1927	MT_BUG_ON(mt, val != xa_mk_value(i));
1928
1929	mas_set(mas: &mas, index: 0);
1930	i = 0;
1931	mas_for_each(&mas, val, 785) {
1932	MT_BUG_ON(mt, mas.index != i * 10);
1933	MT_BUG_ON(mt, mas.last != i * 10 + 9);
1934	/* Overwrite start of entry 78 */
1935	if (i == 78) {
1936	mas.index = 780;
1937	mas.last = 785;
1938	mas_store(mas: &mas, entry: val);
1939	} else {
1940	i++;
1941	}
1942	}
1943	val = mas_find(mas: &mas, ULONG_MAX);
1944	MT_BUG_ON(mt, val != xa_mk_value(i));
1945
1946	mas_set(mas: &mas, index: 0);
1947	i = 0;
1948	mas_for_each(&mas, val, 765) {
1949	MT_BUG_ON(mt, mas.index != i * 10);
1950	MT_BUG_ON(mt, mas.last != i * 10 + 9);
1951	/* Overwrite end of entry 76 and advance to the end */
1952	if (i == 76) {
1953	mas.index = 760;
1954	mas.last = 765;
1955	mas_store(mas: &mas, entry: val);
1956	}
1957	i++;
1958	}
1959	/* Make sure the next find returns the one after 765, 766-769 */
1960	val = mas_find(mas: &mas, ULONG_MAX);
1961	MT_BUG_ON(mt, val != xa_mk_value(76));
1962	mas_unlock(&mas);
1963	mas_destroy(mas: &mas);
1964	mt_set_non_kernel(0);
1965	}
1966
1967	static noinline void __init check_mas_store_gfp(struct maple_tree *mt)
1968	{
1969
1970	struct maple_tree newmt;
1971	int i, nr_entries = 135;
1972	void *val;
1973	MA_STATE(mas, mt, 0, 0);
1974	MA_STATE(newmas, mt, 0, 0);
1975
1976	for (i = 0; i <= nr_entries; i++)
1977	mtree_store_range(mt, first: i*10, last: i*10 + 5,
1978	entry: xa_mk_value(v: i), GFP_KERNEL);
1979
1980	mt_set_non_kernel(99999);
1981	mt_init_flags(mt: &newmt, MT_FLAGS_ALLOC_RANGE);
1982	newmas.tree = &newmt;
1983	rcu_read_lock();
1984	mas_lock(&newmas);
1985	mas_reset(mas: &newmas);
1986	mas_set(mas: &mas, index: 0);
1987	mas_for_each(&mas, val, ULONG_MAX) {
1988	newmas.index = mas.index;
1989	newmas.last = mas.last;
1990	mas_store_gfp(mas: &newmas, entry: val, GFP_KERNEL);
1991	}
1992	mas_unlock(&newmas);
1993	rcu_read_unlock();
1994	mt_validate(mt: &newmt);
1995	mt_set_non_kernel(0);
1996	mtree_destroy(mt: &newmt);
1997	}
1998
1999	#if defined(BENCH_FORK)
2000	static noinline void __init bench_forking(void)
2001	{
2002	struct maple_tree mt, newmt;
2003	int i, nr_entries = 134, nr_fork = 80000, ret;
2004	void *val;
2005	MA_STATE(mas, &mt, 0, 0);
2006	MA_STATE(newmas, &newmt, 0, 0);
2007	struct rw_semaphore mt_lock, newmt_lock;
2008
2009	init_rwsem(&mt_lock);
2010	init_rwsem(&newmt_lock);
2011
2012	mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
2013	mt_set_external_lock(&mt, &mt_lock);
2014
2015	down_write(&mt_lock);
2016	for (i = 0; i <= nr_entries; i++) {
2017	mas_set_range(&mas, i*10, i*10 + 5);
2018	mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
2019	}
2020
2021	for (i = 0; i < nr_fork; i++) {
2022	mt_init_flags(&newmt,
2023	MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
2024	mt_set_external_lock(&newmt, &newmt_lock);
2025
2026	down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING);
2027	ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
2028	if (ret) {
2029	pr_err("OOM!");
2030	BUG_ON(1);
2031	}
2032
2033	mas_set(&newmas, 0);
2034	mas_for_each(&newmas, val, ULONG_MAX)
2035	mas_store(&newmas, val);
2036
2037	mas_destroy(&newmas);
2038	mt_validate(&newmt);
2039	__mt_destroy(&newmt);
2040	up_write(&newmt_lock);
2041	}
2042	mas_destroy(&mas);
2043	__mt_destroy(&mt);
2044	up_write(&mt_lock);
2045	}
2046	#endif
2047
2048	static noinline void __init next_prev_test(struct maple_tree *mt)
2049	{
2050	int i, nr_entries;
2051	void *val;
2052	MA_STATE(mas, mt, 0, 0);
2053	struct maple_enode *mn;
2054	static const unsigned long *level2;
2055	static const unsigned long level2_64[] = { 707, 1000, 710, 715, 720,
2056	725};
2057	static const unsigned long level2_32[] = { 1747, 2000, 1750, 1755,
2058	1760, 1765};
2059	unsigned long last_index;
2060
2061	if (MAPLE_32BIT) {
2062	nr_entries = 500;
2063	level2 = level2_32;
2064	last_index = 0x138e;
2065	} else {
2066	nr_entries = 200;
2067	level2 = level2_64;
2068	last_index = 0x7d6;
2069	}
2070
2071	for (i = 0; i <= nr_entries; i++)
2072	mtree_store_range(mt, first: i*10, last: i*10 + 5,
2073	entry: xa_mk_value(v: i), GFP_KERNEL);
2074
2075	mas_lock(&mas);
2076	for (i = 0; i <= nr_entries / 2; i++) {
2077	mas_next(mas: &mas, max: 1000);
2078	if (mas_is_none(&mas))
2079	break;
2080
2081	}
2082	mas_reset(mas: &mas);
2083	mas_set(mas: &mas, index: 0);
2084	i = 0;
2085	mas_for_each(&mas, val, 1000) {
2086	i++;
2087	}
2088
2089	mas_reset(mas: &mas);
2090	mas_set(mas: &mas, index: 0);
2091	i = 0;
2092	mas_for_each(&mas, val, 1000) {
2093	mas_pause(mas: &mas);
2094	i++;
2095	}
2096
2097	/*
2098	* 680 - 685 = 0x61a00001930c
2099	* 686 - 689 = NULL;
2100	* 690 - 695 = 0x61a00001930c
2101	* Check simple next/prev
2102	*/
2103	mas_set(mas: &mas, index: 686);
2104	val = mas_walk(mas: &mas);
2105	MT_BUG_ON(mt, val != NULL);
2106
2107	val = mas_next(mas: &mas, max: 1000);
2108	MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2109	MT_BUG_ON(mt, mas.index != 690);
2110	MT_BUG_ON(mt, mas.last != 695);
2111
2112	val = mas_prev(mas: &mas, min: 0);
2113	MT_BUG_ON(mt, val != xa_mk_value(680 / 10));
2114	MT_BUG_ON(mt, mas.index != 680);
2115	MT_BUG_ON(mt, mas.last != 685);
2116
2117	val = mas_next(mas: &mas, max: 1000);
2118	MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2119	MT_BUG_ON(mt, mas.index != 690);
2120	MT_BUG_ON(mt, mas.last != 695);
2121
2122	val = mas_next(mas: &mas, max: 1000);
2123	MT_BUG_ON(mt, val != xa_mk_value(700 / 10));
2124	MT_BUG_ON(mt, mas.index != 700);
2125	MT_BUG_ON(mt, mas.last != 705);
2126
2127	/* Check across node boundaries of the tree */
2128	mas_set(mas: &mas, index: 70);
2129	val = mas_walk(mas: &mas);
2130	MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2131	MT_BUG_ON(mt, mas.index != 70);
2132	MT_BUG_ON(mt, mas.last != 75);
2133
2134	val = mas_next(mas: &mas, max: 1000);
2135	MT_BUG_ON(mt, val != xa_mk_value(80 / 10));
2136	MT_BUG_ON(mt, mas.index != 80);
2137	MT_BUG_ON(mt, mas.last != 85);
2138
2139	val = mas_prev(mas: &mas, min: 70);
2140	MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2141	MT_BUG_ON(mt, mas.index != 70);
2142	MT_BUG_ON(mt, mas.last != 75);
2143
2144	/* Check across two levels of the tree */
2145	mas_reset(mas: &mas);
2146	mas_set(mas: &mas, index: level2[0]);
2147	val = mas_walk(mas: &mas);
2148	MT_BUG_ON(mt, val != NULL);
2149	val = mas_next(mas: &mas, max: level2[1]);
2150	MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2151	MT_BUG_ON(mt, mas.index != level2[2]);
2152	MT_BUG_ON(mt, mas.last != level2[3]);
2153	mn = mas.node;
2154
2155	val = mas_next(mas: &mas, max: level2[1]);
2156	MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10));
2157	MT_BUG_ON(mt, mas.index != level2[4]);
2158	MT_BUG_ON(mt, mas.last != level2[5]);
2159	MT_BUG_ON(mt, mn == mas.node);
2160
2161	val = mas_prev(mas: &mas, min: 0);
2162	MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2163	MT_BUG_ON(mt, mas.index != level2[2]);
2164	MT_BUG_ON(mt, mas.last != level2[3]);
2165
2166	/* Check running off the end and back on */
2167	mas_set(mas: &mas, index: nr_entries * 10);
2168	val = mas_walk(mas: &mas);
2169	MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2170	MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2171	MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2172
2173	val = mas_next(mas: &mas, ULONG_MAX);
2174	MT_BUG_ON(mt, val != NULL);
2175	MT_BUG_ON(mt, mas.index != last_index);
2176	MT_BUG_ON(mt, mas.last != ULONG_MAX);
2177
2178	val = mas_prev(mas: &mas, min: 0);
2179	MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2180	MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2181	MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2182
2183	/* Check running off the start and back on */
2184	mas_reset(mas: &mas);
2185	mas_set(mas: &mas, index: 10);
2186	val = mas_walk(mas: &mas);
2187	MT_BUG_ON(mt, val != xa_mk_value(1));
2188	MT_BUG_ON(mt, mas.index != 10);
2189	MT_BUG_ON(mt, mas.last != 15);
2190
2191	val = mas_prev(mas: &mas, min: 0);
2192	MT_BUG_ON(mt, val != xa_mk_value(0));
2193	MT_BUG_ON(mt, mas.index != 0);
2194	MT_BUG_ON(mt, mas.last != 5);
2195
2196	val = mas_prev(mas: &mas, min: 0);
2197	MT_BUG_ON(mt, val != NULL);
2198	MT_BUG_ON(mt, mas.index != 0);
2199	MT_BUG_ON(mt, mas.last != 5);
2200	MT_BUG_ON(mt, !mas_is_underflow(&mas));
2201
2202	mas.index = 0;
2203	mas.last = 5;
2204	mas_store(mas: &mas, NULL);
2205	mas_reset(mas: &mas);
2206	mas_set(mas: &mas, index: 10);
2207	mas_walk(mas: &mas);
2208
2209	val = mas_prev(mas: &mas, min: 0);
2210	MT_BUG_ON(mt, val != NULL);
2211	MT_BUG_ON(mt, mas.index != 0);
2212	MT_BUG_ON(mt, mas.last != 9);
2213	mas_unlock(&mas);
2214
2215	mtree_destroy(mt);
2216
2217	mt_init(mt);
2218	mtree_store_range(mt, first: 0, last: 0, entry: xa_mk_value(v: 0), GFP_KERNEL);
2219	mtree_store_range(mt, first: 5, last: 5, entry: xa_mk_value(v: 5), GFP_KERNEL);
2220	rcu_read_lock();
2221	mas_set(mas: &mas, index: 5);
2222	val = mas_prev(mas: &mas, min: 4);
2223	MT_BUG_ON(mt, val != NULL);
2224	rcu_read_unlock();
2225	}
2226
2227
2228
2229	/* Test spanning writes that require balancing right sibling or right cousin */
2230	static noinline void __init check_spanning_relatives(struct maple_tree *mt)
2231	{
2232
2233	unsigned long i, nr_entries = 1000;
2234
2235	for (i = 0; i <= nr_entries; i++)
2236	mtree_store_range(mt, first: i*10, last: i*10 + 5,
2237	entry: xa_mk_value(v: i), GFP_KERNEL);
2238
2239
2240	mtree_store_range(mt, first: 9365, last: 9955, NULL, GFP_KERNEL);
2241	}
2242
2243	static noinline void __init check_fuzzer(struct maple_tree *mt)
2244	{
2245	/*
2246	* 1. Causes a spanning rebalance of a single root node.
2247	* Fixed by setting the correct limit in mast_cp_to_nodes() when the
2248	* entire right side is consumed.
2249	*/
2250	mtree_test_insert(mt, index: 88, ptr: (void *)0xb1);
2251	mtree_test_insert(mt, index: 84, ptr: (void *)0xa9);
2252	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2253	mtree_test_insert(mt, index: 4, ptr: (void *)0x9);
2254	mtree_test_insert(mt, index: 14, ptr: (void *)0x1d);
2255	mtree_test_insert(mt, index: 7, ptr: (void *)0xf);
2256	mtree_test_insert(mt, index: 12, ptr: (void *)0x19);
2257	mtree_test_insert(mt, index: 18, ptr: (void *)0x25);
2258	mtree_test_store_range(mt, start: 8, end: 18, ptr: (void *)0x11);
2259	mtree_destroy(mt);
2260
2261
2262	/*
2263	* 2. Cause a spanning rebalance of two nodes in root.
2264	* Fixed by setting mast->r->max correctly.
2265	*/
2266	mt_init_flags(mt, flags: 0);
2267	mtree_test_store(mt, start: 87, ptr: (void *)0xaf);
2268	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2269	mtree_test_load(mt, index: 4);
2270	mtree_test_insert(mt, index: 4, ptr: (void *)0x9);
2271	mtree_test_store(mt, start: 8, ptr: (void *)0x11);
2272	mtree_test_store(mt, start: 44, ptr: (void *)0x59);
2273	mtree_test_store(mt, start: 68, ptr: (void *)0x89);
2274	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2275	mtree_test_insert(mt, index: 43, ptr: (void *)0x57);
2276	mtree_test_insert(mt, index: 24, ptr: (void *)0x31);
2277	mtree_test_insert(mt, index: 844, ptr: (void *)0x699);
2278	mtree_test_store(mt, start: 84, ptr: (void *)0xa9);
2279	mtree_test_store(mt, start: 4, ptr: (void *)0x9);
2280	mtree_test_erase(mt, index: 4);
2281	mtree_test_load(mt, index: 5);
2282	mtree_test_erase(mt, index: 0);
2283	mtree_destroy(mt);
2284
2285	/*
2286	* 3. Cause a node overflow on copy
2287	* Fixed by using the correct check for node size in mas_wr_modify()
2288	* Also discovered issue with metadata setting.
2289	*/
2290	mt_init_flags(mt, flags: 0);
2291	mtree_test_store_range(mt, start: 0, ULONG_MAX, ptr: (void *)0x1);
2292	mtree_test_store(mt, start: 4, ptr: (void *)0x9);
2293	mtree_test_erase(mt, index: 5);
2294	mtree_test_erase(mt, index: 0);
2295	mtree_test_erase(mt, index: 4);
2296	mtree_test_store(mt, start: 5, ptr: (void *)0xb);
2297	mtree_test_erase(mt, index: 5);
2298	mtree_test_store(mt, start: 5, ptr: (void *)0xb);
2299	mtree_test_erase(mt, index: 5);
2300	mtree_test_erase(mt, index: 4);
2301	mtree_test_store(mt, start: 4, ptr: (void *)0x9);
2302	mtree_test_store(mt, start: 444, ptr: (void *)0x379);
2303	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2304	mtree_test_load(mt, index: 0);
2305	mtree_test_store(mt, start: 5, ptr: (void *)0xb);
2306	mtree_test_erase(mt, index: 0);
2307	mtree_destroy(mt);
2308
2309	/*
2310	* 4. spanning store failure due to writing incorrect pivot value at
2311	* last slot.
2312	* Fixed by setting mast->r->max correctly in mast_cp_to_nodes()
2313	*
2314	*/
2315	mt_init_flags(mt, flags: 0);
2316	mtree_test_insert(mt, index: 261, ptr: (void *)0x20b);
2317	mtree_test_store(mt, start: 516, ptr: (void *)0x409);
2318	mtree_test_store(mt, start: 6, ptr: (void *)0xd);
2319	mtree_test_insert(mt, index: 5, ptr: (void *)0xb);
2320	mtree_test_insert(mt, index: 1256, ptr: (void *)0x9d1);
2321	mtree_test_store(mt, start: 4, ptr: (void *)0x9);
2322	mtree_test_erase(mt, index: 1);
2323	mtree_test_store(mt, start: 56, ptr: (void *)0x71);
2324	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2325	mtree_test_store(mt, start: 24, ptr: (void *)0x31);
2326	mtree_test_erase(mt, index: 1);
2327	mtree_test_insert(mt, index: 2263, ptr: (void *)0x11af);
2328	mtree_test_insert(mt, index: 446, ptr: (void *)0x37d);
2329	mtree_test_store_range(mt, start: 6, end: 45, ptr: (void *)0xd);
2330	mtree_test_store_range(mt, start: 3, end: 446, ptr: (void *)0x7);
2331	mtree_destroy(mt);
2332
2333	/*
2334	* 5. mas_wr_extend_null() may overflow slots.
2335	* Fix by checking against wr_mas->node_end.
2336	*/
2337	mt_init_flags(mt, flags: 0);
2338	mtree_test_store(mt, start: 48, ptr: (void *)0x61);
2339	mtree_test_store(mt, start: 3, ptr: (void *)0x7);
2340	mtree_test_load(mt, index: 0);
2341	mtree_test_store(mt, start: 88, ptr: (void *)0xb1);
2342	mtree_test_store(mt, start: 81, ptr: (void *)0xa3);
2343	mtree_test_insert(mt, index: 0, ptr: (void *)0x1);
2344	mtree_test_insert(mt, index: 8, ptr: (void *)0x11);
2345	mtree_test_insert(mt, index: 4, ptr: (void *)0x9);
2346	mtree_test_insert(mt, index: 2480, ptr: (void *)0x1361);
2347	mtree_test_insert(mt, ULONG_MAX,
2348	ptr: (void *)0xffffffffffffffff);
2349	mtree_test_erase(mt, ULONG_MAX);
2350	mtree_destroy(mt);
2351
2352	/*
2353	* 6. When reusing a node with an implied pivot and the node is
2354	* shrinking, old data would be left in the implied slot
2355	* Fixed by checking the last pivot for the mas->max and clear
2356	* accordingly. This only affected the left-most node as that node is
2357	* the only one allowed to end in NULL.
2358	*/
2359	mt_init_flags(mt, flags: 0);
2360	mtree_test_erase(mt, index: 3);
2361	mtree_test_insert(mt, index: 22, ptr: (void *)0x2d);
2362	mtree_test_insert(mt, index: 15, ptr: (void *)0x1f);
2363	mtree_test_load(mt, index: 2);
2364	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2365	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2366	mtree_test_insert(mt, index: 5, ptr: (void *)0xb);
2367	mtree_test_erase(mt, index: 1);
2368	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2369	mtree_test_insert(mt, index: 4, ptr: (void *)0x9);
2370	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2371	mtree_test_erase(mt, index: 1);
2372	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2373	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2374	mtree_test_erase(mt, index: 3);
2375	mtree_test_insert(mt, index: 22, ptr: (void *)0x2d);
2376	mtree_test_insert(mt, index: 15, ptr: (void *)0x1f);
2377	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2378	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2379	mtree_test_insert(mt, index: 8, ptr: (void *)0x11);
2380	mtree_test_load(mt, index: 2);
2381	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2382	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2383	mtree_test_store(mt, start: 1, ptr: (void *)0x3);
2384	mtree_test_insert(mt, index: 5, ptr: (void *)0xb);
2385	mtree_test_erase(mt, index: 1);
2386	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2387	mtree_test_insert(mt, index: 4, ptr: (void *)0x9);
2388	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2389	mtree_test_erase(mt, index: 1);
2390	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2391	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2392	mtree_test_erase(mt, index: 3);
2393	mtree_test_insert(mt, index: 22, ptr: (void *)0x2d);
2394	mtree_test_insert(mt, index: 15, ptr: (void *)0x1f);
2395	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2396	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2397	mtree_test_insert(mt, index: 8, ptr: (void *)0x11);
2398	mtree_test_insert(mt, index: 12, ptr: (void *)0x19);
2399	mtree_test_erase(mt, index: 1);
2400	mtree_test_store_range(mt, start: 4, end: 62, ptr: (void *)0x9);
2401	mtree_test_erase(mt, index: 62);
2402	mtree_test_store_range(mt, start: 1, end: 0, ptr: (void *)0x3);
2403	mtree_test_insert(mt, index: 11, ptr: (void *)0x17);
2404	mtree_test_insert(mt, index: 3, ptr: (void *)0x7);
2405	mtree_test_insert(mt, index: 3, ptr: (void *)0x7);
2406	mtree_test_store(mt, start: 62, ptr: (void *)0x7d);
2407	mtree_test_erase(mt, index: 62);
2408	mtree_test_store_range(mt, start: 1, end: 15, ptr: (void *)0x3);
2409	mtree_test_erase(mt, index: 1);
2410	mtree_test_insert(mt, index: 22, ptr: (void *)0x2d);
2411	mtree_test_insert(mt, index: 12, ptr: (void *)0x19);
2412	mtree_test_erase(mt, index: 1);
2413	mtree_test_insert(mt, index: 3, ptr: (void *)0x7);
2414	mtree_test_store(mt, start: 62, ptr: (void *)0x7d);
2415	mtree_test_erase(mt, index: 62);
2416	mtree_test_insert(mt, index: 122, ptr: (void *)0xf5);
2417	mtree_test_store(mt, start: 3, ptr: (void *)0x7);
2418	mtree_test_insert(mt, index: 0, ptr: (void *)0x1);
2419	mtree_test_store_range(mt, start: 0, end: 1, ptr: (void *)0x1);
2420	mtree_test_insert(mt, index: 85, ptr: (void *)0xab);
2421	mtree_test_insert(mt, index: 72, ptr: (void *)0x91);
2422	mtree_test_insert(mt, index: 81, ptr: (void *)0xa3);
2423	mtree_test_insert(mt, index: 726, ptr: (void *)0x5ad);
2424	mtree_test_insert(mt, index: 0, ptr: (void *)0x1);
2425	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2426	mtree_test_store(mt, start: 51, ptr: (void *)0x67);
2427	mtree_test_insert(mt, index: 611, ptr: (void *)0x4c7);
2428	mtree_test_insert(mt, index: 485, ptr: (void *)0x3cb);
2429	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2430	mtree_test_erase(mt, index: 1);
2431	mtree_test_insert(mt, index: 0, ptr: (void *)0x1);
2432	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2433	mtree_test_insert_range(mt, start: 26, end: 1, ptr: (void *)0x35);
2434	mtree_test_load(mt, index: 1);
2435	mtree_test_store_range(mt, start: 1, end: 22, ptr: (void *)0x3);
2436	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2437	mtree_test_erase(mt, index: 1);
2438	mtree_test_load(mt, index: 53);
2439	mtree_test_load(mt, index: 1);
2440	mtree_test_store_range(mt, start: 1, end: 1, ptr: (void *)0x3);
2441	mtree_test_insert(mt, index: 222, ptr: (void *)0x1bd);
2442	mtree_test_insert(mt, index: 485, ptr: (void *)0x3cb);
2443	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2444	mtree_test_erase(mt, index: 1);
2445	mtree_test_load(mt, index: 0);
2446	mtree_test_insert(mt, index: 21, ptr: (void *)0x2b);
2447	mtree_test_insert(mt, index: 3, ptr: (void *)0x7);
2448	mtree_test_store(mt, start: 621, ptr: (void *)0x4db);
2449	mtree_test_insert(mt, index: 0, ptr: (void *)0x1);
2450	mtree_test_erase(mt, index: 5);
2451	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2452	mtree_test_store(mt, start: 62, ptr: (void *)0x7d);
2453	mtree_test_erase(mt, index: 62);
2454	mtree_test_store_range(mt, start: 1, end: 0, ptr: (void *)0x3);
2455	mtree_test_insert(mt, index: 22, ptr: (void *)0x2d);
2456	mtree_test_insert(mt, index: 12, ptr: (void *)0x19);
2457	mtree_test_erase(mt, index: 1);
2458	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2459	mtree_test_store_range(mt, start: 4, end: 62, ptr: (void *)0x9);
2460	mtree_test_erase(mt, index: 62);
2461	mtree_test_erase(mt, index: 1);
2462	mtree_test_load(mt, index: 1);
2463	mtree_test_store_range(mt, start: 1, end: 22, ptr: (void *)0x3);
2464	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2465	mtree_test_erase(mt, index: 1);
2466	mtree_test_load(mt, index: 53);
2467	mtree_test_load(mt, index: 1);
2468	mtree_test_store_range(mt, start: 1, end: 1, ptr: (void *)0x3);
2469	mtree_test_insert(mt, index: 222, ptr: (void *)0x1bd);
2470	mtree_test_insert(mt, index: 485, ptr: (void *)0x3cb);
2471	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2472	mtree_test_erase(mt, index: 1);
2473	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2474	mtree_test_load(mt, index: 0);
2475	mtree_test_load(mt, index: 0);
2476	mtree_destroy(mt);
2477
2478	/*
2479	* 7. Previous fix was incomplete, fix mas_resuse_node() clearing of old
2480	* data by overwriting it first - that way metadata is of no concern.
2481	*/
2482	mt_init_flags(mt, flags: 0);
2483	mtree_test_load(mt, index: 1);
2484	mtree_test_insert(mt, index: 102, ptr: (void *)0xcd);
2485	mtree_test_erase(mt, index: 2);
2486	mtree_test_erase(mt, index: 0);
2487	mtree_test_load(mt, index: 0);
2488	mtree_test_insert(mt, index: 4, ptr: (void *)0x9);
2489	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2490	mtree_test_insert(mt, index: 110, ptr: (void *)0xdd);
2491	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2492	mtree_test_insert_range(mt, start: 5, end: 0, ptr: (void *)0xb);
2493	mtree_test_erase(mt, index: 2);
2494	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2495	mtree_test_store(mt, start: 112, ptr: (void *)0xe1);
2496	mtree_test_insert(mt, index: 21, ptr: (void *)0x2b);
2497	mtree_test_store(mt, start: 1, ptr: (void *)0x3);
2498	mtree_test_insert_range(mt, start: 110, end: 2, ptr: (void *)0xdd);
2499	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2500	mtree_test_load(mt, index: 22);
2501	mtree_test_erase(mt, index: 2);
2502	mtree_test_store(mt, start: 210, ptr: (void *)0x1a5);
2503	mtree_test_store_range(mt, start: 0, end: 2, ptr: (void *)0x1);
2504	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2505	mtree_test_erase(mt, index: 2);
2506	mtree_test_erase(mt, index: 22);
2507	mtree_test_erase(mt, index: 1);
2508	mtree_test_erase(mt, index: 2);
2509	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2510	mtree_test_load(mt, index: 112);
2511	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2512	mtree_test_erase(mt, index: 2);
2513	mtree_test_store(mt, start: 1, ptr: (void *)0x3);
2514	mtree_test_insert_range(mt, start: 1, end: 2, ptr: (void *)0x3);
2515	mtree_test_erase(mt, index: 0);
2516	mtree_test_erase(mt, index: 2);
2517	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2518	mtree_test_erase(mt, index: 0);
2519	mtree_test_erase(mt, index: 2);
2520	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2521	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2522	mtree_test_erase(mt, index: 2);
2523	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2524	mtree_test_erase(mt, index: 2);
2525	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2526	mtree_test_insert_range(mt, start: 1, end: 2, ptr: (void *)0x3);
2527	mtree_test_erase(mt, index: 0);
2528	mtree_test_erase(mt, index: 2);
2529	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2530	mtree_test_load(mt, index: 112);
2531	mtree_test_store_range(mt, start: 110, end: 12, ptr: (void *)0xdd);
2532	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2533	mtree_test_load(mt, index: 110);
2534	mtree_test_insert_range(mt, start: 4, end: 71, ptr: (void *)0x9);
2535	mtree_test_load(mt, index: 2);
2536	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2537	mtree_test_insert_range(mt, start: 11, end: 22, ptr: (void *)0x17);
2538	mtree_test_erase(mt, index: 12);
2539	mtree_test_store(mt, start: 2, ptr: (void *)0x5);
2540	mtree_test_load(mt, index: 22);
2541	mtree_destroy(mt);
2542
2543
2544	/*
2545	* 8. When rebalancing or spanning_rebalance(), the max of the new node
2546	* may be set incorrectly to the final pivot and not the right max.
2547	* Fix by setting the left max to orig right max if the entire node is
2548	* consumed.
2549	*/
2550	mt_init_flags(mt, flags: 0);
2551	mtree_test_store(mt, start: 6, ptr: (void *)0xd);
2552	mtree_test_store(mt, start: 67, ptr: (void *)0x87);
2553	mtree_test_insert(mt, index: 15, ptr: (void *)0x1f);
2554	mtree_test_insert(mt, index: 6716, ptr: (void *)0x3479);
2555	mtree_test_store(mt, start: 61, ptr: (void *)0x7b);
2556	mtree_test_insert(mt, index: 13, ptr: (void *)0x1b);
2557	mtree_test_store(mt, start: 8, ptr: (void *)0x11);
2558	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2559	mtree_test_load(mt, index: 0);
2560	mtree_test_erase(mt, index: 67167);
2561	mtree_test_insert_range(mt, start: 6, end: 7167, ptr: (void *)0xd);
2562	mtree_test_insert(mt, index: 6, ptr: (void *)0xd);
2563	mtree_test_erase(mt, index: 67);
2564	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2565	mtree_test_erase(mt, index: 667167);
2566	mtree_test_insert(mt, index: 6, ptr: (void *)0xd);
2567	mtree_test_store(mt, start: 67, ptr: (void *)0x87);
2568	mtree_test_insert(mt, index: 5, ptr: (void *)0xb);
2569	mtree_test_erase(mt, index: 1);
2570	mtree_test_insert(mt, index: 6, ptr: (void *)0xd);
2571	mtree_test_erase(mt, index: 67);
2572	mtree_test_insert(mt, index: 15, ptr: (void *)0x1f);
2573	mtree_test_insert(mt, index: 67167, ptr: (void *)0x20cbf);
2574	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2575	mtree_test_load(mt, index: 7);
2576	mtree_test_insert(mt, index: 16, ptr: (void *)0x21);
2577	mtree_test_insert(mt, index: 36, ptr: (void *)0x49);
2578	mtree_test_store(mt, start: 67, ptr: (void *)0x87);
2579	mtree_test_store(mt, start: 6, ptr: (void *)0xd);
2580	mtree_test_insert(mt, index: 367, ptr: (void *)0x2df);
2581	mtree_test_insert(mt, index: 115, ptr: (void *)0xe7);
2582	mtree_test_store(mt, start: 0, ptr: (void *)0x1);
2583	mtree_test_store_range(mt, start: 1, end: 3, ptr: (void *)0x3);
2584	mtree_test_store(mt, start: 1, ptr: (void *)0x3);
2585	mtree_test_erase(mt, index: 67167);
2586	mtree_test_insert_range(mt, start: 6, end: 47, ptr: (void *)0xd);
2587	mtree_test_store(mt, start: 1, ptr: (void *)0x3);
2588	mtree_test_insert_range(mt, start: 1, end: 67, ptr: (void *)0x3);
2589	mtree_test_load(mt, index: 67);
2590	mtree_test_insert(mt, index: 1, ptr: (void *)0x3);
2591	mtree_test_erase(mt, index: 67167);
2592	mtree_destroy(mt);
2593
2594	/*
2595	* 9. spanning store to the end of data caused an invalid metadata
2596	* length which resulted in a crash eventually.
2597	* Fix by checking if there is a value in pivot before incrementing the
2598	* metadata end in mab_mas_cp(). To ensure this doesn't happen again,
2599	* abstract the two locations this happens into a function called
2600	* mas_leaf_set_meta().
2601	*/
2602	mt_init_flags(mt, flags: 0);
2603	mtree_test_insert(mt, index: 21, ptr: (void *)0x2b);
2604	mtree_test_insert(mt, index: 12, ptr: (void *)0x19);
2605	mtree_test_insert(mt, index: 6, ptr: (void *)0xd);
2606	mtree_test_insert(mt, index: 8, ptr: (void *)0x11);
2607	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2608	mtree_test_insert(mt, index: 91, ptr: (void *)0xb7);
2609	mtree_test_insert(mt, index: 18, ptr: (void *)0x25);
2610	mtree_test_insert(mt, index: 81, ptr: (void *)0xa3);
2611	mtree_test_store_range(mt, start: 0, end: 128, ptr: (void *)0x1);
2612	mtree_test_store(mt, start: 1, ptr: (void *)0x3);
2613	mtree_test_erase(mt, index: 8);
2614	mtree_test_insert(mt, index: 11, ptr: (void *)0x17);
2615	mtree_test_insert(mt, index: 8, ptr: (void *)0x11);
2616	mtree_test_insert(mt, index: 21, ptr: (void *)0x2b);
2617	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2618	mtree_test_insert(mt, ULONG_MAX - 10, ptr: (void *)0xffffffffffffffeb);
2619	mtree_test_erase(mt, ULONG_MAX - 10);
2620	mtree_test_store_range(mt, start: 0, end: 281, ptr: (void *)0x1);
2621	mtree_test_erase(mt, index: 2);
2622	mtree_test_insert(mt, index: 1211, ptr: (void *)0x977);
2623	mtree_test_insert(mt, index: 111, ptr: (void *)0xdf);
2624	mtree_test_insert(mt, index: 13, ptr: (void *)0x1b);
2625	mtree_test_insert(mt, index: 211, ptr: (void *)0x1a7);
2626	mtree_test_insert(mt, index: 11, ptr: (void *)0x17);
2627	mtree_test_insert(mt, index: 5, ptr: (void *)0xb);
2628	mtree_test_insert(mt, index: 1218, ptr: (void *)0x985);
2629	mtree_test_insert(mt, index: 61, ptr: (void *)0x7b);
2630	mtree_test_store(mt, start: 1, ptr: (void *)0x3);
2631	mtree_test_insert(mt, index: 121, ptr: (void *)0xf3);
2632	mtree_test_insert(mt, index: 8, ptr: (void *)0x11);
2633	mtree_test_insert(mt, index: 21, ptr: (void *)0x2b);
2634	mtree_test_insert(mt, index: 2, ptr: (void *)0x5);
2635	mtree_test_insert(mt, ULONG_MAX - 10, ptr: (void *)0xffffffffffffffeb);
2636	mtree_test_erase(mt, ULONG_MAX - 10);
2637	}
2638
2639	/* duplicate the tree with a specific gap */
2640	static noinline void __init check_dup_gaps(struct maple_tree *mt,
2641	unsigned long nr_entries, bool zero_start,
2642	unsigned long gap)
2643	{
2644	unsigned long i = 0;
2645	struct maple_tree newmt;
2646	int ret;
2647	void *tmp;
2648	MA_STATE(mas, mt, 0, 0);
2649	MA_STATE(newmas, &newmt, 0, 0);
2650	struct rw_semaphore newmt_lock;
2651
2652	init_rwsem(&newmt_lock);
2653	mt_set_external_lock(&newmt, &newmt_lock);
2654
2655	if (!zero_start)
2656	i = 1;
2657
2658	mt_zero_nr_tallocated();
2659	for (; i <= nr_entries; i++)
2660	mtree_store_range(mt, first: i*10, last: (i+1)*10 - gap,
2661	entry: xa_mk_value(v: i), GFP_KERNEL);
2662
2663	mt_init_flags(mt: &newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
2664	mt_set_non_kernel(99999);
2665	down_write(sem: &newmt_lock);
2666	ret = mas_expected_entries(mas: &newmas, nr_entries);
2667	mt_set_non_kernel(0);
2668	MT_BUG_ON(mt, ret != 0);
2669
2670	rcu_read_lock();
2671	mas_for_each(&mas, tmp, ULONG_MAX) {
2672	newmas.index = mas.index;
2673	newmas.last = mas.last;
2674	mas_store(mas: &newmas, entry: tmp);
2675	}
2676	rcu_read_unlock();
2677	mas_destroy(mas: &newmas);
2678
2679	__mt_destroy(mt: &newmt);
2680	up_write(sem: &newmt_lock);
2681	}
2682
2683	/* Duplicate many sizes of trees. Mainly to test expected entry values */
2684	static noinline void __init check_dup(struct maple_tree *mt)
2685	{
2686	int i;
2687	int big_start = 100010;
2688
2689	/* Check with a value at zero */
2690	for (i = 10; i < 1000; i++) {
2691	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2692	check_dup_gaps(mt, nr_entries: i, zero_start: true, gap: 5);
2693	mtree_destroy(mt);
2694	rcu_barrier();
2695	}
2696
2697	cond_resched();
2698	mt_cache_shrink();
2699	/* Check with a value at zero, no gap */
2700	for (i = 1000; i < 2000; i++) {
2701	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2702	check_dup_gaps(mt, nr_entries: i, zero_start: true, gap: 0);
2703	mtree_destroy(mt);
2704	rcu_barrier();
2705	}
2706
2707	cond_resched();
2708	mt_cache_shrink();
2709	/* Check with a value at zero and unreasonably large */
2710	for (i = big_start; i < big_start + 10; i++) {
2711	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2712	check_dup_gaps(mt, nr_entries: i, zero_start: true, gap: 5);
2713	mtree_destroy(mt);
2714	rcu_barrier();
2715	}
2716
2717	cond_resched();
2718	mt_cache_shrink();
2719	/* Small to medium size not starting at zero*/
2720	for (i = 200; i < 1000; i++) {
2721	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2722	check_dup_gaps(mt, nr_entries: i, zero_start: false, gap: 5);
2723	mtree_destroy(mt);
2724	rcu_barrier();
2725	}
2726
2727	cond_resched();
2728	mt_cache_shrink();
2729	/* Unreasonably large not starting at zero*/
2730	for (i = big_start; i < big_start + 10; i++) {
2731	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2732	check_dup_gaps(mt, nr_entries: i, zero_start: false, gap: 5);
2733	mtree_destroy(mt);
2734	rcu_barrier();
2735	cond_resched();
2736	mt_cache_shrink();
2737	}
2738
2739	/* Check non-allocation tree not starting at zero */
2740	for (i = 1500; i < 3000; i++) {
2741	mt_init_flags(mt, flags: 0);
2742	check_dup_gaps(mt, nr_entries: i, zero_start: false, gap: 5);
2743	mtree_destroy(mt);
2744	rcu_barrier();
2745	cond_resched();
2746	if (i % 2 == 0)
2747	mt_cache_shrink();
2748	}
2749
2750	mt_cache_shrink();
2751	/* Check non-allocation tree starting at zero */
2752	for (i = 200; i < 1000; i++) {
2753	mt_init_flags(mt, flags: 0);
2754	check_dup_gaps(mt, nr_entries: i, zero_start: true, gap: 5);
2755	mtree_destroy(mt);
2756	rcu_barrier();
2757	cond_resched();
2758	}
2759
2760	mt_cache_shrink();
2761	/* Unreasonably large */
2762	for (i = big_start + 5; i < big_start + 10; i++) {
2763	mt_init_flags(mt, flags: 0);
2764	check_dup_gaps(mt, nr_entries: i, zero_start: true, gap: 5);
2765	mtree_destroy(mt);
2766	rcu_barrier();
2767	mt_cache_shrink();
2768	cond_resched();
2769	}
2770	}
2771
2772	static noinline void __init check_bnode_min_spanning(struct maple_tree *mt)
2773	{
2774	int i = 50;
2775	MA_STATE(mas, mt, 0, 0);
2776
2777	mt_set_non_kernel(9999);
2778	mas_lock(&mas);
2779	do {
2780	mas_set_range(mas: &mas, start: i*10, last: i*10+9);
2781	mas_store(mas: &mas, entry: check_bnode_min_spanning);
2782	} while (i--);
2783
2784	mas_set_range(mas: &mas, start: 240, last: 509);
2785	mas_store(mas: &mas, NULL);
2786	mas_unlock(&mas);
2787	mas_destroy(mas: &mas);
2788	mt_set_non_kernel(0);
2789	}
2790
2791	static noinline void __init check_empty_area_window(struct maple_tree *mt)
2792	{
2793	unsigned long i, nr_entries = 20;
2794	MA_STATE(mas, mt, 0, 0);
2795
2796	for (i = 1; i <= nr_entries; i++)
2797	mtree_store_range(mt, first: i*10, last: i*10 + 9,
2798	entry: xa_mk_value(v: i), GFP_KERNEL);
2799
2800	/* Create another hole besides the one at 0 */
2801	mtree_store_range(mt, first: 160, last: 169, NULL, GFP_KERNEL);
2802
2803	/* Check lower bounds that don't fit */
2804	rcu_read_lock();
2805	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 10) != -EBUSY);
2806
2807	mas_reset(mas: &mas);
2808	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 6, 90, 5) != -EBUSY);
2809
2810	/* Check lower bound that does fit */
2811	mas_reset(mas: &mas);
2812	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 5) != 0);
2813	MT_BUG_ON(mt, mas.index != 5);
2814	MT_BUG_ON(mt, mas.last != 9);
2815	rcu_read_unlock();
2816
2817	/* Check one gap that doesn't fit and one that does */
2818	rcu_read_lock();
2819	mas_reset(mas: &mas);
2820	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 217, 9) != 0);
2821	MT_BUG_ON(mt, mas.index != 161);
2822	MT_BUG_ON(mt, mas.last != 169);
2823
2824	/* Check one gap that does fit above the min */
2825	mas_reset(mas: &mas);
2826	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 3) != 0);
2827	MT_BUG_ON(mt, mas.index != 216);
2828	MT_BUG_ON(mt, mas.last != 218);
2829
2830	/* Check size that doesn't fit any gap */
2831	mas_reset(mas: &mas);
2832	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 16) != -EBUSY);
2833
2834	/*
2835	* Check size that doesn't fit the lower end of the window but
2836	* does fit the gap
2837	*/
2838	mas_reset(mas: &mas);
2839	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 167, 200, 4) != -EBUSY);
2840
2841	/*
2842	* Check size that doesn't fit the upper end of the window but
2843	* does fit the gap
2844	*/
2845	mas_reset(mas: &mas);
2846	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 162, 4) != -EBUSY);
2847
2848	/* Check mas_empty_area forward */
2849	mas_reset(mas: &mas);
2850	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 9) != 0);
2851	MT_BUG_ON(mt, mas.index != 0);
2852	MT_BUG_ON(mt, mas.last != 8);
2853
2854	mas_reset(mas: &mas);
2855	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 4) != 0);
2856	MT_BUG_ON(mt, mas.index != 0);
2857	MT_BUG_ON(mt, mas.last != 3);
2858
2859	mas_reset(mas: &mas);
2860	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 11) != -EBUSY);
2861
2862	mas_reset(mas: &mas);
2863	MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
2864
2865	mas_reset(mas: &mas);
2866	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
2867
2868	mas_reset(mas: &mas);
2869	mas_empty_area(mas: &mas, min: 100, max: 165, size: 3);
2870
2871	mas_reset(mas: &mas);
2872	MT_BUG_ON(mt, mas_empty_area(&mas, 100, 163, 6) != -EBUSY);
2873	rcu_read_unlock();
2874	}
2875
2876	static noinline void __init check_empty_area_fill(struct maple_tree *mt)
2877	{
2878	const unsigned long max = 0x25D78000;
2879	unsigned long size;
2880	int loop, shift;
2881	MA_STATE(mas, mt, 0, 0);
2882
2883	mt_set_non_kernel(99999);
2884	for (shift = 12; shift <= 16; shift++) {
2885	loop = 5000;
2886	size = 1 << shift;
2887	while (loop--) {
2888	mas_set(mas: &mas, index: 0);
2889	mas_lock(&mas);
2890	MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != 0);
2891	MT_BUG_ON(mt, mas.last != mas.index + size - 1);
2892	mas_store_gfp(mas: &mas, entry: (void *)size, GFP_KERNEL);
2893	mas_unlock(&mas);
2894	mas_reset(mas: &mas);
2895	}
2896	}
2897
2898	/* No space left. */
2899	size = 0x1000;
2900	rcu_read_lock();
2901	MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != -EBUSY);
2902	rcu_read_unlock();
2903
2904	/* Fill a depth 3 node to the maximum */
2905	for (unsigned long i = 629440511; i <= 629440800; i += 6)
2906	mtree_store_range(mt, first: i, last: i + 5, entry: (void *)i, GFP_KERNEL);
2907	/* Make space in the second-last depth 4 node */
2908	mtree_erase(mt, index: 631668735);
2909	/* Make space in the last depth 4 node */
2910	mtree_erase(mt, index: 629506047);
2911	mas_reset(mas: &mas);
2912	/* Search from just after the gap in the second-last depth 4 */
2913	rcu_read_lock();
2914	MT_BUG_ON(mt, mas_empty_area(&mas, 629506048, 690000000, 0x5000) != 0);
2915	rcu_read_unlock();
2916	mt_set_non_kernel(0);
2917	}
2918
2919	/*
2920	* Check MAS_START, MAS_PAUSE, active (implied), and MAS_NONE transitions.
2921	*
2922	* The table below shows the single entry tree (0-0 pointer) and normal tree
2923	* with nodes.
2924	*
2925	* Function ENTRY Start Result index & last
2926	* ┬ ┬ ┬ ┬ ┬
2927	* │ │ │ │ └─ the final range
2928	* │ │ │ └─ The node value after execution
2929	* │ │ └─ The node value before execution
2930	* │ └─ If the entry exists or does not exists (DNE)
2931	* └─ The function name
2932	*
2933	* Function ENTRY Start Result index & last
2934	* mas_next()
2935	* - after last
2936	* Single entry tree at 0-0
2937	* ------------------------
2938	* DNE MAS_START MAS_NONE 1 - oo
2939	* DNE MAS_PAUSE MAS_NONE 1 - oo
2940	* DNE MAS_ROOT MAS_NONE 1 - oo
2941	* when index = 0
2942	* DNE MAS_NONE MAS_ROOT 0
2943	* when index > 0
2944	* DNE MAS_NONE MAS_NONE 1 - oo
2945	*
2946	* Normal tree
2947	* -----------
2948	* exists MAS_START active range
2949	* DNE MAS_START active set to last range
2950	* exists MAS_PAUSE active range
2951	* DNE MAS_PAUSE active set to last range
2952	* exists MAS_NONE active range
2953	* exists active active range
2954	* DNE active active set to last range
2955	* ERANGE active MAS_OVERFLOW last range
2956	*
2957	* Function ENTRY Start Result index & last
2958	* mas_prev()
2959	* - before index
2960	* Single entry tree at 0-0
2961	* ------------------------
2962	* if index > 0
2963	* exists MAS_START MAS_ROOT 0
2964	* exists MAS_PAUSE MAS_ROOT 0
2965	* exists MAS_NONE MAS_ROOT 0
2966	*
2967	* if index == 0
2968	* DNE MAS_START MAS_NONE 0
2969	* DNE MAS_PAUSE MAS_NONE 0
2970	* DNE MAS_NONE MAS_NONE 0
2971	* DNE MAS_ROOT MAS_NONE 0
2972	*
2973	* Normal tree
2974	* -----------
2975	* exists MAS_START active range
2976	* DNE MAS_START active set to min
2977	* exists MAS_PAUSE active range
2978	* DNE MAS_PAUSE active set to min
2979	* exists MAS_NONE active range
2980	* DNE MAS_NONE MAS_NONE set to min
2981	* any MAS_ROOT MAS_NONE 0
2982	* exists active active range
2983	* DNE active active last range
2984	* ERANGE active MAS_UNDERFLOW last range
2985	*
2986	* Function ENTRY Start Result index & last
2987	* mas_find()
2988	* - at index or next
2989	* Single entry tree at 0-0
2990	* ------------------------
2991	* if index > 0
2992	* DNE MAS_START MAS_NONE 0
2993	* DNE MAS_PAUSE MAS_NONE 0
2994	* DNE MAS_ROOT MAS_NONE 0
2995	* DNE MAS_NONE MAS_NONE 1
2996	* if index == 0
2997	* exists MAS_START MAS_ROOT 0
2998	* exists MAS_PAUSE MAS_ROOT 0
2999	* exists MAS_NONE MAS_ROOT 0
3000	*
3001	* Normal tree
3002	* -----------
3003	* exists MAS_START active range
3004	* DNE MAS_START active set to max
3005	* exists MAS_PAUSE active range
3006	* DNE MAS_PAUSE active set to max
3007	* exists MAS_NONE active range (start at last)
3008	* exists active active range
3009	* DNE active active last range (max < last)
3010	*
3011	* Function ENTRY Start Result index & last
3012	* mas_find_rev()
3013	* - at index or before
3014	* Single entry tree at 0-0
3015	* ------------------------
3016	* if index > 0
3017	* exists MAS_START MAS_ROOT 0
3018	* exists MAS_PAUSE MAS_ROOT 0
3019	* exists MAS_NONE MAS_ROOT 0
3020	* if index == 0
3021	* DNE MAS_START MAS_NONE 0
3022	* DNE MAS_PAUSE MAS_NONE 0
3023	* DNE MAS_NONE MAS_NONE 0
3024	* DNE MAS_ROOT MAS_NONE 0
3025	*
3026	* Normal tree
3027	* -----------
3028	* exists MAS_START active range
3029	* DNE MAS_START active set to min
3030	* exists MAS_PAUSE active range
3031	* DNE MAS_PAUSE active set to min
3032	* exists MAS_NONE active range (start at index)
3033	* exists active active range
3034	* DNE active active last range (min > index)
3035	*
3036	* Function ENTRY Start Result index & last
3037	* mas_walk()
3038	* - Look up index
3039	* Single entry tree at 0-0
3040	* ------------------------
3041	* if index > 0
3042	* DNE MAS_START MAS_ROOT 1 - oo
3043	* DNE MAS_PAUSE MAS_ROOT 1 - oo
3044	* DNE MAS_NONE MAS_ROOT 1 - oo
3045	* DNE MAS_ROOT MAS_ROOT 1 - oo
3046	* if index == 0
3047	* exists MAS_START MAS_ROOT 0
3048	* exists MAS_PAUSE MAS_ROOT 0
3049	* exists MAS_NONE MAS_ROOT 0
3050	* exists MAS_ROOT MAS_ROOT 0
3051	*
3052	* Normal tree
3053	* -----------
3054	* exists MAS_START active range
3055	* DNE MAS_START active range of NULL
3056	* exists MAS_PAUSE active range
3057	* DNE MAS_PAUSE active range of NULL
3058	* exists MAS_NONE active range
3059	* DNE MAS_NONE active range of NULL
3060	* exists active active range
3061	* DNE active active range of NULL
3062	*/
3063
3064	static noinline void __init check_state_handling(struct maple_tree *mt)
3065	{
3066	MA_STATE(mas, mt, 0, 0);
3067	void *entry, *ptr = (void *) 0x1234500;
3068	void *ptr2 = &ptr;
3069	void *ptr3 = &ptr2;
3070
3071	/* Check MAS_ROOT First */
3072	mtree_store_range(mt, first: 0, last: 0, entry: ptr, GFP_KERNEL);
3073
3074	mas_lock(&mas);
3075	/* prev: Start -> underflow*/
3076	entry = mas_prev(mas: &mas, min: 0);
3077	MT_BUG_ON(mt, entry != NULL);
3078	MT_BUG_ON(mt, mas.status != ma_underflow);
3079
3080	/* prev: Start -> root */
3081	mas_set(mas: &mas, index: 10);
3082	entry = mas_prev(mas: &mas, min: 0);
3083	MT_BUG_ON(mt, entry != ptr);
3084	MT_BUG_ON(mt, mas.index != 0);
3085	MT_BUG_ON(mt, mas.last != 0);
3086	MT_BUG_ON(mt, mas.status != ma_root);
3087
3088	/* prev: pause -> root */
3089	mas_set(mas: &mas, index: 10);
3090	mas_pause(mas: &mas);
3091	entry = mas_prev(mas: &mas, min: 0);
3092	MT_BUG_ON(mt, entry != ptr);
3093	MT_BUG_ON(mt, mas.index != 0);
3094	MT_BUG_ON(mt, mas.last != 0);
3095	MT_BUG_ON(mt, mas.status != ma_root);
3096
3097	/* next: start -> none */
3098	mas_set(mas: &mas, index: 0);
3099	entry = mas_next(mas: &mas, ULONG_MAX);
3100	MT_BUG_ON(mt, mas.index != 1);
3101	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3102	MT_BUG_ON(mt, entry != NULL);
3103	MT_BUG_ON(mt, mas.status != ma_none);
3104
3105	/* next: start -> none*/
3106	mas_set(mas: &mas, index: 10);
3107	entry = mas_next(mas: &mas, ULONG_MAX);
3108	MT_BUG_ON(mt, mas.index != 1);
3109	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3110	MT_BUG_ON(mt, entry != NULL);
3111	MT_BUG_ON(mt, mas.status != ma_none);
3112
3113	/* find: start -> root */
3114	mas_set(mas: &mas, index: 0);
3115	entry = mas_find(mas: &mas, ULONG_MAX);
3116	MT_BUG_ON(mt, entry != ptr);
3117	MT_BUG_ON(mt, mas.index != 0);
3118	MT_BUG_ON(mt, mas.last != 0);
3119	MT_BUG_ON(mt, mas.status != ma_root);
3120
3121	/* find: root -> none */
3122	entry = mas_find(mas: &mas, ULONG_MAX);
3123	MT_BUG_ON(mt, entry != NULL);
3124	MT_BUG_ON(mt, mas.index != 1);
3125	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3126	MT_BUG_ON(mt, mas.status != ma_none);
3127
3128	/* find: none -> none */
3129	entry = mas_find(mas: &mas, ULONG_MAX);
3130	MT_BUG_ON(mt, entry != NULL);
3131	MT_BUG_ON(mt, mas.index != 1);
3132	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3133	MT_BUG_ON(mt, mas.status != ma_none);
3134
3135	/* find: start -> none */
3136	mas_set(mas: &mas, index: 10);
3137	entry = mas_find(mas: &mas, ULONG_MAX);
3138	MT_BUG_ON(mt, entry != NULL);
3139	MT_BUG_ON(mt, mas.index != 1);
3140	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3141	MT_BUG_ON(mt, mas.status != ma_none);
3142
3143	/* find_rev: none -> root */
3144	entry = mas_find_rev(mas: &mas, min: 0);
3145	MT_BUG_ON(mt, entry != ptr);
3146	MT_BUG_ON(mt, mas.index != 0);
3147	MT_BUG_ON(mt, mas.last != 0);
3148	MT_BUG_ON(mt, mas.status != ma_root);
3149
3150	/* find_rev: start -> root */
3151	mas_set(mas: &mas, index: 0);
3152	entry = mas_find_rev(mas: &mas, min: 0);
3153	MT_BUG_ON(mt, entry != ptr);
3154	MT_BUG_ON(mt, mas.index != 0);
3155	MT_BUG_ON(mt, mas.last != 0);
3156	MT_BUG_ON(mt, mas.status != ma_root);
3157
3158	/* find_rev: root -> none */
3159	entry = mas_find_rev(mas: &mas, min: 0);
3160	MT_BUG_ON(mt, entry != NULL);
3161	MT_BUG_ON(mt, mas.index != 0);
3162	MT_BUG_ON(mt, mas.last != 0);
3163	MT_BUG_ON(mt, mas.status != ma_none);
3164
3165	/* find_rev: none -> none */
3166	entry = mas_find_rev(mas: &mas, min: 0);
3167	MT_BUG_ON(mt, entry != NULL);
3168	MT_BUG_ON(mt, mas.index != 0);
3169	MT_BUG_ON(mt, mas.last != 0);
3170	MT_BUG_ON(mt, mas.status != ma_none);
3171
3172	/* find_rev: start -> root */
3173	mas_set(mas: &mas, index: 10);
3174	entry = mas_find_rev(mas: &mas, min: 0);
3175	MT_BUG_ON(mt, entry != ptr);
3176	MT_BUG_ON(mt, mas.index != 0);
3177	MT_BUG_ON(mt, mas.last != 0);
3178	MT_BUG_ON(mt, mas.status != ma_root);
3179
3180	/* walk: start -> none */
3181	mas_set(mas: &mas, index: 10);
3182	entry = mas_walk(mas: &mas);
3183	MT_BUG_ON(mt, entry != NULL);
3184	MT_BUG_ON(mt, mas.index != 1);
3185	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3186	MT_BUG_ON(mt, mas.status != ma_none);
3187
3188	/* walk: pause -> none*/
3189	mas_set(mas: &mas, index: 10);
3190	mas_pause(mas: &mas);
3191	entry = mas_walk(mas: &mas);
3192	MT_BUG_ON(mt, entry != NULL);
3193	MT_BUG_ON(mt, mas.index != 1);
3194	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3195	MT_BUG_ON(mt, mas.status != ma_none);
3196
3197	/* walk: none -> none */
3198	mas.index = mas.last = 10;
3199	entry = mas_walk(mas: &mas);
3200	MT_BUG_ON(mt, entry != NULL);
3201	MT_BUG_ON(mt, mas.index != 1);
3202	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3203	MT_BUG_ON(mt, mas.status != ma_none);
3204
3205	/* walk: none -> none */
3206	entry = mas_walk(mas: &mas);
3207	MT_BUG_ON(mt, entry != NULL);
3208	MT_BUG_ON(mt, mas.index != 1);
3209	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3210	MT_BUG_ON(mt, mas.status != ma_none);
3211
3212	/* walk: start -> root */
3213	mas_set(mas: &mas, index: 0);
3214	entry = mas_walk(mas: &mas);
3215	MT_BUG_ON(mt, entry != ptr);
3216	MT_BUG_ON(mt, mas.index != 0);
3217	MT_BUG_ON(mt, mas.last != 0);
3218	MT_BUG_ON(mt, mas.status != ma_root);
3219
3220	/* walk: pause -> root */
3221	mas_set(mas: &mas, index: 0);
3222	mas_pause(mas: &mas);
3223	entry = mas_walk(mas: &mas);
3224	MT_BUG_ON(mt, entry != ptr);
3225	MT_BUG_ON(mt, mas.index != 0);
3226	MT_BUG_ON(mt, mas.last != 0);
3227	MT_BUG_ON(mt, mas.status != ma_root);
3228
3229	/* walk: none -> root */
3230	mas.status = ma_none;
3231	entry = mas_walk(mas: &mas);
3232	MT_BUG_ON(mt, entry != ptr);
3233	MT_BUG_ON(mt, mas.index != 0);
3234	MT_BUG_ON(mt, mas.last != 0);
3235	MT_BUG_ON(mt, mas.status != ma_root);
3236
3237	/* walk: root -> root */
3238	entry = mas_walk(mas: &mas);
3239	MT_BUG_ON(mt, entry != ptr);
3240	MT_BUG_ON(mt, mas.index != 0);
3241	MT_BUG_ON(mt, mas.last != 0);
3242	MT_BUG_ON(mt, mas.status != ma_root);
3243
3244	/* walk: root -> none */
3245	mas_set(mas: &mas, index: 10);
3246	entry = mas_walk(mas: &mas);
3247	MT_BUG_ON(mt, entry != NULL);
3248	MT_BUG_ON(mt, mas.index != 1);
3249	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3250	MT_BUG_ON(mt, mas.status != ma_none);
3251
3252	/* walk: none -> root */
3253	mas.index = mas.last = 0;
3254	entry = mas_walk(mas: &mas);
3255	MT_BUG_ON(mt, entry != ptr);
3256	MT_BUG_ON(mt, mas.index != 0);
3257	MT_BUG_ON(mt, mas.last != 0);
3258	MT_BUG_ON(mt, mas.status != ma_root);
3259
3260	mas_unlock(&mas);
3261
3262	/* Check when there is an actual node */
3263	mtree_store_range(mt, first: 0, last: 0, NULL, GFP_KERNEL);
3264	mtree_store_range(mt, first: 0x1000, last: 0x1500, entry: ptr, GFP_KERNEL);
3265	mtree_store_range(mt, first: 0x2000, last: 0x2500, entry: ptr2, GFP_KERNEL);
3266	mtree_store_range(mt, first: 0x3000, last: 0x3500, entry: ptr3, GFP_KERNEL);
3267
3268	mas_lock(&mas);
3269
3270	/* next: start ->active */
3271	mas_set(mas: &mas, index: 0);
3272	entry = mas_next(mas: &mas, ULONG_MAX);
3273	MT_BUG_ON(mt, entry != ptr);
3274	MT_BUG_ON(mt, mas.index != 0x1000);
3275	MT_BUG_ON(mt, mas.last != 0x1500);
3276	MT_BUG_ON(mt, !mas_is_active(&mas));
3277
3278	/* next: pause ->active */
3279	mas_set(mas: &mas, index: 0);
3280	mas_pause(mas: &mas);
3281	entry = mas_next(mas: &mas, ULONG_MAX);
3282	MT_BUG_ON(mt, entry != ptr);
3283	MT_BUG_ON(mt, mas.index != 0x1000);
3284	MT_BUG_ON(mt, mas.last != 0x1500);
3285	MT_BUG_ON(mt, !mas_is_active(&mas));
3286
3287	/* next: none ->active */
3288	mas.index = mas.last = 0;
3289	mas.offset = 0;
3290	mas.status = ma_none;
3291	entry = mas_next(mas: &mas, ULONG_MAX);
3292	MT_BUG_ON(mt, entry != ptr);
3293	MT_BUG_ON(mt, mas.index != 0x1000);
3294	MT_BUG_ON(mt, mas.last != 0x1500);
3295	MT_BUG_ON(mt, !mas_is_active(&mas));
3296
3297	/* next:active ->active (spanning limit) */
3298	entry = mas_next(mas: &mas, max: 0x2100);
3299	MT_BUG_ON(mt, entry != ptr2);
3300	MT_BUG_ON(mt, mas.index != 0x2000);
3301	MT_BUG_ON(mt, mas.last != 0x2500);
3302	MT_BUG_ON(mt, !mas_is_active(&mas));
3303
3304	/* next:active -> overflow (limit reached) beyond data */
3305	entry = mas_next(mas: &mas, max: 0x2999);
3306	MT_BUG_ON(mt, entry != NULL);
3307	MT_BUG_ON(mt, mas.index != 0x2501);
3308	MT_BUG_ON(mt, mas.last != 0x2fff);
3309	MT_BUG_ON(mt, !mas_is_overflow(&mas));
3310
3311	/* next:overflow -> active (limit changed) */
3312	entry = mas_next(mas: &mas, ULONG_MAX);
3313	MT_BUG_ON(mt, entry != ptr3);
3314	MT_BUG_ON(mt, mas.index != 0x3000);
3315	MT_BUG_ON(mt, mas.last != 0x3500);
3316	MT_BUG_ON(mt, !mas_is_active(&mas));
3317
3318	/* next:active -> overflow (limit reached) */
3319	entry = mas_next(mas: &mas, ULONG_MAX);
3320	MT_BUG_ON(mt, entry != NULL);
3321	MT_BUG_ON(mt, mas.index != 0x3501);
3322	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3323	MT_BUG_ON(mt, !mas_is_overflow(&mas));
3324
3325	/* next:overflow -> overflow */
3326	entry = mas_next(mas: &mas, ULONG_MAX);
3327	MT_BUG_ON(mt, entry != NULL);
3328	MT_BUG_ON(mt, mas.index != 0x3501);
3329	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3330	MT_BUG_ON(mt, !mas_is_overflow(&mas));
3331
3332	/* prev:overflow -> active */
3333	entry = mas_prev(mas: &mas, min: 0);
3334	MT_BUG_ON(mt, entry != ptr3);
3335	MT_BUG_ON(mt, mas.index != 0x3000);
3336	MT_BUG_ON(mt, mas.last != 0x3500);
3337	MT_BUG_ON(mt, !mas_is_active(&mas));
3338
3339	/* next: none -> active, skip value at location */
3340	mas_set(mas: &mas, index: 0);
3341	entry = mas_next(mas: &mas, ULONG_MAX);
3342	mas.status = ma_none;
3343	mas.offset = 0;
3344	entry = mas_next(mas: &mas, ULONG_MAX);
3345	MT_BUG_ON(mt, entry != ptr2);
3346	MT_BUG_ON(mt, mas.index != 0x2000);
3347	MT_BUG_ON(mt, mas.last != 0x2500);
3348	MT_BUG_ON(mt, !mas_is_active(&mas));
3349
3350	/* prev:active ->active */
3351	entry = mas_prev(mas: &mas, min: 0);
3352	MT_BUG_ON(mt, entry != ptr);
3353	MT_BUG_ON(mt, mas.index != 0x1000);
3354	MT_BUG_ON(mt, mas.last != 0x1500);
3355	MT_BUG_ON(mt, !mas_is_active(&mas));
3356
3357	/* prev:active -> underflow (span limit) */
3358	mas_next(mas: &mas, ULONG_MAX);
3359	entry = mas_prev(mas: &mas, min: 0x1200);
3360	MT_BUG_ON(mt, entry != ptr);
3361	MT_BUG_ON(mt, mas.index != 0x1000);
3362	MT_BUG_ON(mt, mas.last != 0x1500);
3363	MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */
3364	entry = mas_prev(mas: &mas, min: 0x1200); /* underflow */
3365	MT_BUG_ON(mt, entry != NULL);
3366	MT_BUG_ON(mt, mas.index != 0x1000);
3367	MT_BUG_ON(mt, mas.last != 0x1500);
3368	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3369
3370	/* prev:underflow -> underflow (lower limit) spanning end range */
3371	entry = mas_prev(mas: &mas, min: 0x0100);
3372	MT_BUG_ON(mt, entry != NULL);
3373	MT_BUG_ON(mt, mas.index != 0);
3374	MT_BUG_ON(mt, mas.last != 0x0FFF);
3375	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3376
3377	/* prev:underflow -> underflow */
3378	entry = mas_prev(mas: &mas, min: 0);
3379	MT_BUG_ON(mt, entry != NULL);
3380	MT_BUG_ON(mt, mas.index != 0);
3381	MT_BUG_ON(mt, mas.last != 0x0FFF);
3382	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3383
3384	/* prev:underflow -> underflow */
3385	entry = mas_prev(mas: &mas, min: 0);
3386	MT_BUG_ON(mt, entry != NULL);
3387	MT_BUG_ON(mt, mas.index != 0);
3388	MT_BUG_ON(mt, mas.last != 0x0FFF);
3389	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3390
3391	/* next:underflow -> active */
3392	entry = mas_next(mas: &mas, ULONG_MAX);
3393	MT_BUG_ON(mt, entry != ptr);
3394	MT_BUG_ON(mt, mas.index != 0x1000);
3395	MT_BUG_ON(mt, mas.last != 0x1500);
3396	MT_BUG_ON(mt, !mas_is_active(&mas));
3397
3398	/* prev:first value -> underflow */
3399	entry = mas_prev(mas: &mas, min: 0x1000);
3400	MT_BUG_ON(mt, entry != NULL);
3401	MT_BUG_ON(mt, mas.index != 0x1000);
3402	MT_BUG_ON(mt, mas.last != 0x1500);
3403	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3404
3405	/* find:underflow -> first value */
3406	entry = mas_find(mas: &mas, ULONG_MAX);
3407	MT_BUG_ON(mt, entry != ptr);
3408	MT_BUG_ON(mt, mas.index != 0x1000);
3409	MT_BUG_ON(mt, mas.last != 0x1500);
3410	MT_BUG_ON(mt, !mas_is_active(&mas));
3411
3412	/* prev: pause ->active */
3413	mas_set(mas: &mas, index: 0x3600);
3414	entry = mas_prev(mas: &mas, min: 0);
3415	MT_BUG_ON(mt, entry != ptr3);
3416	mas_pause(mas: &mas);
3417	entry = mas_prev(mas: &mas, min: 0);
3418	MT_BUG_ON(mt, entry != ptr2);
3419	MT_BUG_ON(mt, mas.index != 0x2000);
3420	MT_BUG_ON(mt, mas.last != 0x2500);
3421	MT_BUG_ON(mt, !mas_is_active(&mas));
3422
3423	/* prev:active -> underflow spanning min */
3424	entry = mas_prev(mas: &mas, min: 0x1600);
3425	MT_BUG_ON(mt, entry != NULL);
3426	MT_BUG_ON(mt, mas.index != 0x1501);
3427	MT_BUG_ON(mt, mas.last != 0x1FFF);
3428	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3429
3430	/* prev: active ->active, continue */
3431	entry = mas_prev(mas: &mas, min: 0);
3432	MT_BUG_ON(mt, entry != ptr);
3433	MT_BUG_ON(mt, mas.index != 0x1000);
3434	MT_BUG_ON(mt, mas.last != 0x1500);
3435	MT_BUG_ON(mt, !mas_is_active(&mas));
3436
3437	/* find: start ->active */
3438	mas_set(mas: &mas, index: 0);
3439	entry = mas_find(mas: &mas, ULONG_MAX);
3440	MT_BUG_ON(mt, entry != ptr);
3441	MT_BUG_ON(mt, mas.index != 0x1000);
3442	MT_BUG_ON(mt, mas.last != 0x1500);
3443	MT_BUG_ON(mt, !mas_is_active(&mas));
3444
3445	/* find: pause ->active */
3446	mas_set(mas: &mas, index: 0);
3447	mas_pause(mas: &mas);
3448	entry = mas_find(mas: &mas, ULONG_MAX);
3449	MT_BUG_ON(mt, entry != ptr);
3450	MT_BUG_ON(mt, mas.index != 0x1000);
3451	MT_BUG_ON(mt, mas.last != 0x1500);
3452	MT_BUG_ON(mt, !mas_is_active(&mas));
3453
3454	/* find: start ->active on value */;
3455	mas_set(mas: &mas, index: 1200);
3456	entry = mas_find(mas: &mas, ULONG_MAX);
3457	MT_BUG_ON(mt, entry != ptr);
3458	MT_BUG_ON(mt, mas.index != 0x1000);
3459	MT_BUG_ON(mt, mas.last != 0x1500);
3460	MT_BUG_ON(mt, !mas_is_active(&mas));
3461
3462	/* find:active ->active */
3463	entry = mas_find(mas: &mas, ULONG_MAX);
3464	MT_BUG_ON(mt, entry != ptr2);
3465	MT_BUG_ON(mt, mas.index != 0x2000);
3466	MT_BUG_ON(mt, mas.last != 0x2500);
3467	MT_BUG_ON(mt, !mas_is_active(&mas));
3468
3469
3470	/* find:active -> active (NULL)*/
3471	entry = mas_find(mas: &mas, max: 0x2700);
3472	MT_BUG_ON(mt, entry != NULL);
3473	MT_BUG_ON(mt, mas.index != 0x2501);
3474	MT_BUG_ON(mt, mas.last != 0x2FFF);
3475	MAS_BUG_ON(&mas, !mas_is_active(&mas));
3476
3477	/* find: overflow ->active */
3478	entry = mas_find(mas: &mas, max: 0x5000);
3479	MT_BUG_ON(mt, entry != ptr3);
3480	MT_BUG_ON(mt, mas.index != 0x3000);
3481	MT_BUG_ON(mt, mas.last != 0x3500);
3482	MT_BUG_ON(mt, !mas_is_active(&mas));
3483
3484	/* find:active -> active (NULL) end*/
3485	entry = mas_find(mas: &mas, ULONG_MAX);
3486	MT_BUG_ON(mt, entry != NULL);
3487	MT_BUG_ON(mt, mas.index != 0x3501);
3488	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3489	MAS_BUG_ON(&mas, !mas_is_active(&mas));
3490
3491	/* find_rev: active (END) ->active */
3492	entry = mas_find_rev(mas: &mas, min: 0);
3493	MT_BUG_ON(mt, entry != ptr3);
3494	MT_BUG_ON(mt, mas.index != 0x3000);
3495	MT_BUG_ON(mt, mas.last != 0x3500);
3496	MT_BUG_ON(mt, !mas_is_active(&mas));
3497
3498	/* find_rev:active ->active */
3499	entry = mas_find_rev(mas: &mas, min: 0);
3500	MT_BUG_ON(mt, entry != ptr2);
3501	MT_BUG_ON(mt, mas.index != 0x2000);
3502	MT_BUG_ON(mt, mas.last != 0x2500);
3503	MT_BUG_ON(mt, !mas_is_active(&mas));
3504
3505	/* find_rev: pause ->active */
3506	mas_pause(mas: &mas);
3507	entry = mas_find_rev(mas: &mas, min: 0);
3508	MT_BUG_ON(mt, entry != ptr);
3509	MT_BUG_ON(mt, mas.index != 0x1000);
3510	MT_BUG_ON(mt, mas.last != 0x1500);
3511	MT_BUG_ON(mt, !mas_is_active(&mas));
3512
3513	/* find_rev:active -> underflow */
3514	entry = mas_find_rev(mas: &mas, min: 0);
3515	MT_BUG_ON(mt, entry != NULL);
3516	MT_BUG_ON(mt, mas.index != 0);
3517	MT_BUG_ON(mt, mas.last != 0x0FFF);
3518	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3519
3520	/* find_rev: start ->active */
3521	mas_set(mas: &mas, index: 0x1200);
3522	entry = mas_find_rev(mas: &mas, min: 0);
3523	MT_BUG_ON(mt, entry != ptr);
3524	MT_BUG_ON(mt, mas.index != 0x1000);
3525	MT_BUG_ON(mt, mas.last != 0x1500);
3526	MT_BUG_ON(mt, !mas_is_active(&mas));
3527
3528	/* mas_walk start ->active */
3529	mas_set(mas: &mas, index: 0x1200);
3530	entry = mas_walk(mas: &mas);
3531	MT_BUG_ON(mt, entry != ptr);
3532	MT_BUG_ON(mt, mas.index != 0x1000);
3533	MT_BUG_ON(mt, mas.last != 0x1500);
3534	MT_BUG_ON(mt, !mas_is_active(&mas));
3535
3536	/* mas_walk start ->active */
3537	mas_set(mas: &mas, index: 0x1600);
3538	entry = mas_walk(mas: &mas);
3539	MT_BUG_ON(mt, entry != NULL);
3540	MT_BUG_ON(mt, mas.index != 0x1501);
3541	MT_BUG_ON(mt, mas.last != 0x1fff);
3542	MT_BUG_ON(mt, !mas_is_active(&mas));
3543
3544	/* mas_walk pause ->active */
3545	mas_set(mas: &mas, index: 0x1200);
3546	mas_pause(mas: &mas);
3547	entry = mas_walk(mas: &mas);
3548	MT_BUG_ON(mt, entry != ptr);
3549	MT_BUG_ON(mt, mas.index != 0x1000);
3550	MT_BUG_ON(mt, mas.last != 0x1500);
3551	MT_BUG_ON(mt, !mas_is_active(&mas));
3552
3553	/* mas_walk pause -> active */
3554	mas_set(mas: &mas, index: 0x1600);
3555	mas_pause(mas: &mas);
3556	entry = mas_walk(mas: &mas);
3557	MT_BUG_ON(mt, entry != NULL);
3558	MT_BUG_ON(mt, mas.index != 0x1501);
3559	MT_BUG_ON(mt, mas.last != 0x1fff);
3560	MT_BUG_ON(mt, !mas_is_active(&mas));
3561
3562	/* mas_walk none -> active */
3563	mas_set(mas: &mas, index: 0x1200);
3564	mas.status = ma_none;
3565	entry = mas_walk(mas: &mas);
3566	MT_BUG_ON(mt, entry != ptr);
3567	MT_BUG_ON(mt, mas.index != 0x1000);
3568	MT_BUG_ON(mt, mas.last != 0x1500);
3569	MT_BUG_ON(mt, !mas_is_active(&mas));
3570
3571	/* mas_walk none -> active */
3572	mas_set(mas: &mas, index: 0x1600);
3573	mas.status = ma_none;
3574	entry = mas_walk(mas: &mas);
3575	MT_BUG_ON(mt, entry != NULL);
3576	MT_BUG_ON(mt, mas.index != 0x1501);
3577	MT_BUG_ON(mt, mas.last != 0x1fff);
3578	MT_BUG_ON(mt, !mas_is_active(&mas));
3579
3580	/* mas_walk active -> active */
3581	mas.index = 0x1200;
3582	mas.last = 0x1200;
3583	mas.offset = 0;
3584	entry = mas_walk(mas: &mas);
3585	MT_BUG_ON(mt, entry != ptr);
3586	MT_BUG_ON(mt, mas.index != 0x1000);
3587	MT_BUG_ON(mt, mas.last != 0x1500);
3588	MT_BUG_ON(mt, !mas_is_active(&mas));
3589
3590	/* mas_walk active -> active */
3591	mas.index = 0x1600;
3592	mas.last = 0x1600;
3593	entry = mas_walk(mas: &mas);
3594	MT_BUG_ON(mt, entry != NULL);
3595	MT_BUG_ON(mt, mas.index != 0x1501);
3596	MT_BUG_ON(mt, mas.last != 0x1fff);
3597	MT_BUG_ON(mt, !mas_is_active(&mas));
3598
3599	mas_unlock(&mas);
3600	}
3601
3602	static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
3603	{
3604	unsigned long location;
3605	unsigned long next;
3606	int ret = 0;
3607	MA_STATE(mas, mt, 0, 0);
3608
3609	next = 0;
3610	mtree_lock(mt);
3611	for (int i = 0; i < 100; i++) {
3612	mas_alloc_cyclic(mas: &mas, startp: &location, entry: mt, range_lo: 2, ULONG_MAX, next: &next, GFP_KERNEL);
3613	MAS_BUG_ON(&mas, i != location - 2);
3614	MAS_BUG_ON(&mas, mas.index != location);
3615	MAS_BUG_ON(&mas, mas.last != location);
3616	MAS_BUG_ON(&mas, i != next - 3);
3617	}
3618
3619	mtree_unlock(mt);
3620	mtree_destroy(mt);
3621	next = 0;
3622	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
3623	for (int i = 0; i < 100; i++) {
3624	mtree_alloc_cyclic(mt, startp: &location, entry: mt, range_lo: 2, ULONG_MAX, next: &next, GFP_KERNEL);
3625	MT_BUG_ON(mt, i != location - 2);
3626	MT_BUG_ON(mt, i != next - 3);
3627	MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3628	}
3629
3630	mtree_destroy(mt);
3631	/* Overflow test */
3632	next = ULONG_MAX - 1;
3633	ret = mtree_alloc_cyclic(mt, startp: &location, entry: mt, range_lo: 2, ULONG_MAX, next: &next, GFP_KERNEL);
3634	MT_BUG_ON(mt, ret != 0);
3635	ret = mtree_alloc_cyclic(mt, startp: &location, entry: mt, range_lo: 2, ULONG_MAX, next: &next, GFP_KERNEL);
3636	MT_BUG_ON(mt, ret != 0);
3637	ret = mtree_alloc_cyclic(mt, startp: &location, entry: mt, range_lo: 2, ULONG_MAX, next: &next, GFP_KERNEL);
3638	MT_BUG_ON(mt, ret != 1);
3639	}
3640
3641	static DEFINE_MTREE(tree);
3642	static int __init maple_tree_seed(void)
3643	{
3644	unsigned long set[] = { 5015, 5014, 5017, 25, 1000,
3645	1001, 1002, 1003, 1005, 0,
3646	5003, 5002};
3647	void *ptr = &set;
3648
3649	pr_info("\nTEST STARTING\n\n");
3650
3651	#if defined(BENCH_SLOT_STORE)
3652	#define BENCH
3653	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3654	bench_slot_store(&tree);
3655	mtree_destroy(&tree);
3656	goto skip;
3657	#endif
3658	#if defined(BENCH_NODE_STORE)
3659	#define BENCH
3660	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3661	bench_node_store(&tree);
3662	mtree_destroy(&tree);
3663	goto skip;
3664	#endif
3665	#if defined(BENCH_AWALK)
3666	#define BENCH
3667	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3668	bench_awalk(&tree);
3669	mtree_destroy(&tree);
3670	goto skip;
3671	#endif
3672	#if defined(BENCH_WALK)
3673	#define BENCH
3674	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3675	bench_walk(&tree);
3676	mtree_destroy(&tree);
3677	goto skip;
3678	#endif
3679	#if defined(BENCH_LOAD)
3680	#define BENCH
3681	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3682	bench_load(&tree);
3683	mtree_destroy(&tree);
3684	goto skip;
3685	#endif
3686	#if defined(BENCH_FORK)
3687	#define BENCH
3688	bench_forking();
3689	goto skip;
3690	#endif
3691	#if defined(BENCH_MT_FOR_EACH)
3692	#define BENCH
3693	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3694	bench_mt_for_each(&tree);
3695	mtree_destroy(&tree);
3696	goto skip;
3697	#endif
3698	#if defined(BENCH_MAS_FOR_EACH)
3699	#define BENCH
3700	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3701	bench_mas_for_each(&tree);
3702	mtree_destroy(&tree);
3703	goto skip;
3704	#endif
3705	#if defined(BENCH_MAS_PREV)
3706	#define BENCH
3707	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3708	bench_mas_prev(&tree);
3709	mtree_destroy(&tree);
3710	goto skip;
3711	#endif
3712
3713	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3714	check_root_expand(mt: &tree);
3715	mtree_destroy(mt: &tree);
3716
3717	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3718	check_iteration(mt: &tree);
3719	mtree_destroy(mt: &tree);
3720
3721	check_forking();
3722
3723	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3724	check_mas_store_gfp(mt: &tree);
3725	mtree_destroy(mt: &tree);
3726
3727	/* Test ranges (store and insert) */
3728	mt_init_flags(mt: &tree, flags: 0);
3729	check_ranges(mt: &tree);
3730	mtree_destroy(mt: &tree);
3731
3732	#if defined(CONFIG_64BIT)
3733	/* These tests have ranges outside of 4GB */
3734	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3735	check_alloc_range(mt: &tree);
3736	mtree_destroy(mt: &tree);
3737
3738	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3739	check_alloc_rev_range(mt: &tree);
3740	mtree_destroy(mt: &tree);
3741	#endif
3742
3743	mt_init_flags(mt: &tree, flags: 0);
3744
3745	check_load(mt: &tree, index: set[0], NULL); /* See if 5015 -> NULL */
3746
3747	check_insert(mt: &tree, index: set[9], ptr: &tree); /* Insert 0 */
3748	check_load(mt: &tree, index: set[9], ptr: &tree); /* See if 0 -> &tree */
3749	check_load(mt: &tree, index: set[0], NULL); /* See if 5015 -> NULL */
3750
3751	check_insert(mt: &tree, index: set[10], ptr); /* Insert 5003 */
3752	check_load(mt: &tree, index: set[9], ptr: &tree); /* See if 0 -> &tree */
3753	check_load(mt: &tree, index: set[11], NULL); /* See if 5002 -> NULL */
3754	check_load(mt: &tree, index: set[10], ptr); /* See if 5003 -> ptr */
3755
3756	/* Clear out the tree */
3757	mtree_destroy(mt: &tree);
3758
3759	/* Try to insert, insert a dup, and load back what was inserted. */
3760	mt_init_flags(mt: &tree, flags: 0);
3761	check_insert(mt: &tree, index: set[0], ptr: &tree); /* Insert 5015 */
3762	check_dup_insert(mt: &tree, index: set[0], ptr: &tree); /* Insert 5015 again */
3763	check_load(mt: &tree, index: set[0], ptr: &tree); /* See if 5015 -> &tree */
3764
3765	/*
3766	* Second set of tests try to load a value that doesn't exist, inserts
3767	* a second value, then loads the value again
3768	*/
3769	check_load(mt: &tree, index: set[1], NULL); /* See if 5014 -> NULL */
3770	check_insert(mt: &tree, index: set[1], ptr); /* insert 5014 -> ptr */
3771	check_load(mt: &tree, index: set[1], ptr); /* See if 5014 -> ptr */
3772	check_load(mt: &tree, index: set[0], ptr: &tree); /* See if 5015 -> &tree */
3773	/*
3774	* Tree currently contains:
3775	* p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil)
3776	*/
3777	check_insert(mt: &tree, index: set[6], ptr); /* insert 1002 -> ptr */
3778	check_insert(mt: &tree, index: set[7], ptr: &tree); /* insert 1003 -> &tree */
3779
3780	check_load(mt: &tree, index: set[0], ptr: &tree); /* See if 5015 -> &tree */
3781	check_load(mt: &tree, index: set[1], ptr); /* See if 5014 -> ptr */
3782	check_load(mt: &tree, index: set[6], ptr); /* See if 1002 -> ptr */
3783	check_load(mt: &tree, index: set[7], ptr: &tree); /* 1003 = &tree ? */
3784
3785	/* Clear out tree */
3786	mtree_destroy(mt: &tree);
3787
3788	mt_init_flags(mt: &tree, flags: 0);
3789	/* Test inserting into a NULL hole. */
3790	check_insert(mt: &tree, index: set[5], ptr); /* insert 1001 -> ptr */
3791	check_insert(mt: &tree, index: set[7], ptr: &tree); /* insert 1003 -> &tree */
3792	check_insert(mt: &tree, index: set[6], ptr); /* insert 1002 -> ptr */
3793	check_load(mt: &tree, index: set[5], ptr); /* See if 1001 -> ptr */
3794	check_load(mt: &tree, index: set[6], ptr); /* See if 1002 -> ptr */
3795	check_load(mt: &tree, index: set[7], ptr: &tree); /* See if 1003 -> &tree */
3796
3797	/* Clear out the tree */
3798	mtree_destroy(mt: &tree);
3799
3800	mt_init_flags(mt: &tree, flags: 0);
3801	/*
3802	* set[] = {5015, 5014, 5017, 25, 1000,
3803	* 1001, 1002, 1003, 1005, 0,
3804	* 5003, 5002};
3805	*/
3806
3807	check_insert(mt: &tree, index: set[0], ptr); /* 5015 */
3808	check_insert(mt: &tree, index: set[1], ptr: &tree); /* 5014 */
3809	check_insert(mt: &tree, index: set[2], ptr); /* 5017 */
3810	check_insert(mt: &tree, index: set[3], ptr: &tree); /* 25 */
3811	check_load(mt: &tree, index: set[0], ptr);
3812	check_load(mt: &tree, index: set[1], ptr: &tree);
3813	check_load(mt: &tree, index: set[2], ptr);
3814	check_load(mt: &tree, index: set[3], ptr: &tree);
3815	check_insert(mt: &tree, index: set[4], ptr); /* 1000 < Should split. */
3816	check_load(mt: &tree, index: set[0], ptr);
3817	check_load(mt: &tree, index: set[1], ptr: &tree);
3818	check_load(mt: &tree, index: set[2], ptr);
3819	check_load(mt: &tree, index: set[3], ptr: &tree); /*25 */
3820	check_load(mt: &tree, index: set[4], ptr);
3821	check_insert(mt: &tree, index: set[5], ptr: &tree); /* 1001 */
3822	check_load(mt: &tree, index: set[0], ptr);
3823	check_load(mt: &tree, index: set[1], ptr: &tree);
3824	check_load(mt: &tree, index: set[2], ptr);
3825	check_load(mt: &tree, index: set[3], ptr: &tree);
3826	check_load(mt: &tree, index: set[4], ptr);
3827	check_load(mt: &tree, index: set[5], ptr: &tree);
3828	check_insert(mt: &tree, index: set[6], ptr);
3829	check_load(mt: &tree, index: set[0], ptr);
3830	check_load(mt: &tree, index: set[1], ptr: &tree);
3831	check_load(mt: &tree, index: set[2], ptr);
3832	check_load(mt: &tree, index: set[3], ptr: &tree);
3833	check_load(mt: &tree, index: set[4], ptr);
3834	check_load(mt: &tree, index: set[5], ptr: &tree);
3835	check_load(mt: &tree, index: set[6], ptr);
3836	check_insert(mt: &tree, index: set[7], ptr: &tree);
3837	check_load(mt: &tree, index: set[0], ptr);
3838	check_insert(mt: &tree, index: set[8], ptr);
3839
3840	check_insert(mt: &tree, index: set[9], ptr: &tree);
3841
3842	check_load(mt: &tree, index: set[0], ptr);
3843	check_load(mt: &tree, index: set[1], ptr: &tree);
3844	check_load(mt: &tree, index: set[2], ptr);
3845	check_load(mt: &tree, index: set[3], ptr: &tree);
3846	check_load(mt: &tree, index: set[4], ptr);
3847	check_load(mt: &tree, index: set[5], ptr: &tree);
3848	check_load(mt: &tree, index: set[6], ptr);
3849	check_load(mt: &tree, index: set[9], ptr: &tree);
3850	mtree_destroy(mt: &tree);
3851
3852	mt_init_flags(mt: &tree, flags: 0);
3853	check_seq(mt: &tree, max: 16, verbose: false);
3854	mtree_destroy(mt: &tree);
3855
3856	mt_init_flags(mt: &tree, flags: 0);
3857	check_seq(mt: &tree, max: 1000, verbose: true);
3858	mtree_destroy(mt: &tree);
3859
3860	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3861	check_rev_seq(mt: &tree, max: 1000, verbose: true);
3862	mtree_destroy(mt: &tree);
3863
3864	check_lower_bound_split(mt: &tree);
3865	check_upper_bound_split(mt: &tree);
3866	check_mid_split(mt: &tree);
3867
3868	mt_init_flags(mt: &tree, flags: 0);
3869	check_next_entry(mt: &tree);
3870	check_find(mt: &tree);
3871	check_find_2(mt: &tree);
3872	mtree_destroy(mt: &tree);
3873
3874	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3875	check_prev_entry(mt: &tree);
3876	mtree_destroy(mt: &tree);
3877
3878	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3879	check_gap_combining(mt: &tree);
3880	mtree_destroy(mt: &tree);
3881
3882	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3883	check_node_overwrite(mt: &tree);
3884	mtree_destroy(mt: &tree);
3885
3886	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3887	next_prev_test(mt: &tree);
3888	mtree_destroy(mt: &tree);
3889
3890	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3891	check_spanning_relatives(mt: &tree);
3892	mtree_destroy(mt: &tree);
3893
3894	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3895	check_rev_find(mt: &tree);
3896	mtree_destroy(mt: &tree);
3897
3898	mt_init_flags(mt: &tree, flags: 0);
3899	check_fuzzer(mt: &tree);
3900	mtree_destroy(mt: &tree);
3901
3902	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3903	check_dup(mt: &tree);
3904	mtree_destroy(mt: &tree);
3905
3906	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3907	check_bnode_min_spanning(mt: &tree);
3908	mtree_destroy(mt: &tree);
3909
3910	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3911	check_empty_area_window(mt: &tree);
3912	mtree_destroy(mt: &tree);
3913
3914	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3915	check_empty_area_fill(mt: &tree);
3916	mtree_destroy(mt: &tree);
3917
3918	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3919	check_state_handling(mt: &tree);
3920	mtree_destroy(mt: &tree);
3921
3922	mt_init_flags(mt: &tree, MT_FLAGS_ALLOC_RANGE);
3923	alloc_cyclic_testing(mt: &tree);
3924	mtree_destroy(mt: &tree);
3925
3926
3927	#if defined(BENCH)
3928	skip:
3929	#endif
3930	rcu_barrier();
3931	pr_info("maple_tree: %u of %u tests passed\n",
3932	atomic_read(&maple_tree_tests_passed),
3933	atomic_read(&maple_tree_tests_run));
3934	if (atomic_read(v: &maple_tree_tests_run) ==
3935	atomic_read(v: &maple_tree_tests_passed))
3936	return 0;
3937
3938	return -EINVAL;
3939	}
3940
3941	static void __exit maple_tree_harvest(void)
3942	{
3943
3944	}
3945
3946	module_init(maple_tree_seed);
3947	module_exit(maple_tree_harvest);
3948	MODULE_AUTHOR("Liam R. Howlett <Liam.Howlett@Oracle.com>");
3949	MODULE_LICENSE("GPL");
3950