test_maple_tree.c

   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)
  24atomic_t maple_tree_tests_run;
  25atomic_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
  63static int __init mtree_insert_index(struct maple_tree *mt,
  64				     unsigned long index, gfp_t gfp)
  65{
  66	return mtree_insert(mt, index, xa_mk_value(index & LONG_MAX), gfp);
  67}
  68
  69static 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
  75static int __init mtree_test_insert(struct maple_tree *mt, unsigned long index,
  76				void *ptr)
  77{
  78	return mtree_insert(mt, index, ptr, GFP_KERNEL);
  79}
  80
  81static 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, start, end, ptr, GFP_KERNEL);
  85}
  86
  87static int __init mtree_test_store(struct maple_tree *mt, unsigned long start,
  88				void *ptr)
  89{
  90	return mtree_test_store_range(mt, start, start, ptr);
  91}
  92
  93static 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, start, end, ptr, GFP_KERNEL);
  97}
  98
  99static void __init *mtree_test_load(struct maple_tree *mt, unsigned long index)
 100{
 101	return mtree_load(mt, index);
 102}
 103
 104static 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)
 110static 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, &result, ptr, size, start, 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
 127static 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, &result, ptr, size, start, 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
 145static 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
 155static 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, i, ptr);
 169}
 170
 171static 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, i, ptr);
 185}
 186
 187static 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
 196static 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
 206static noinline void __init check_index_load(struct maple_tree *mt,
 207					     unsigned long index)
 208{
 209	return check_load(mt, index, xa_mk_value(index & LONG_MAX));
 210}
 211
 212static 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
 227static 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, j);
 239
 240		check_load(mt, 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, 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
 260static 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, j);
 272
 273		if (i)
 274			MT_BUG_ON(mt, !mt_height(mt));
 275		check_load(mt, 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
 289static 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, i, (void *) i);
 298		for (j = huge; j >= i; j /= 2) {
 299			check_load(mt, j-1, NULL);
 300			check_load(mt, j, (void *) j);
 301			check_load(mt, j+1, NULL);
 302		}
 303		i /= 2;
 304	}
 305	mtree_destroy(mt);
 306}
 307
 308static 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
 314static 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, i, (void *) i);
 329		for (j = i; j >= huge; j *= 2) {
 330			check_load(mt, j-1, NULL);
 331			check_load(mt, j, (void *) j);
 332			check_load(mt, j+1, NULL);
 333		}
 334		i *= 2;
 335	}
 336	mtree_destroy(mt);
 337}
 338
 339static noinline void __init check_mid_split(struct maple_tree *mt)
 340{
 341	unsigned long huge = 8000UL * 1000 * 1000;
 342
 343	check_insert(mt, huge, (void *) huge);
 344	check_insert(mt, 0, xa_mk_value(0));
 345	check_lb_not_empty(mt);
 346}
 347
 348static 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, i*10, i*10 + 5,
 356				  xa_mk_value(i), GFP_KERNEL);
 357
 358	rcu_read_lock();
 359	mas_set(&mas, 1000);
 360	val = mas_find_rev(&mas, 1000);
 361	MT_BUG_ON(mt, val != xa_mk_value(100));
 362	val = mas_find_rev(&mas, 1000);
 363	MT_BUG_ON(mt, val != NULL);
 364
 365	mas_set(&mas, 999);
 366	val = mas_find_rev(&mas, 997);
 367	MT_BUG_ON(mt, val != NULL);
 368
 369	mas_set(&mas, 1000);
 370	val = mas_find_rev(&mas, 900);
 371	MT_BUG_ON(mt, val != xa_mk_value(100));
 372	val = mas_find_rev(&mas, 900);
 373	MT_BUG_ON(mt, val != xa_mk_value(99));
 374
 375	mas_set(&mas, 20);
 376	val = mas_find_rev(&mas, 0);
 377	MT_BUG_ON(mt, val != xa_mk_value(2));
 378	val = mas_find_rev(&mas, 0);
 379	MT_BUG_ON(mt, val != xa_mk_value(1));
 380	val = mas_find_rev(&mas, 0);
 381	MT_BUG_ON(mt, val != xa_mk_value(0));
 382	val = mas_find_rev(&mas, 0);
 383	MT_BUG_ON(mt, val != NULL);
 384	rcu_read_unlock();
 385}
 386
 387static 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, val);
 425	mas_lock(&mas);
 426	while ((entry = mas_find(&mas, 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, 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, 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);
 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);
 513	index = 17;
 514	entry = mt_find(mt, &index, 512);
 515	MT_BUG_ON(mt, xa_mk_value(256) != entry);
 516
 517	mas_reset(&mas);
 518	index = 17;
 519	entry = mt_find(mt, &index, 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, 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);
 548		mas_unlock(&mas);
 549		mas_lock(&mas);
 550	}
 551	mas_unlock(&mas);
 552
 553	mas_set(&mas, 1048576);
 554	mas_lock(&mas);
 555	entry = mas_find(&mas, 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);
 569	mas.index = ULONG_MAX; /* start at max.. */
 570	entry = mas_find(&mas, ULONG_MAX);
 571	entry = mas_prev(&mas, 0);
 572	index = mas.index;
 573	last = mas.last;
 574
 575	/* Erase the last entry. */
 576	mas_reset(&mas);
 577	mas.index = ULONG_MAX;
 578	mas.last = ULONG_MAX;
 579	mas_erase(&mas);
 580
 581	/* Get the previous value from MAS_START */
 582	mas_reset(&mas);
 583	entry2 = mas_prev(&mas, 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, 0);
 595	MT_BUG_ON(mt, entry != entry2);
 596
 597	mas_set(&mas, 0);
 598	MT_BUG_ON(mt, mas_prev(&mas, 0) != NULL);
 599
 600	mas_unlock(&mas);
 601	mtree_destroy(mt);
 602}
 603
 604static 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, i, GFP_KERNEL);
 617		j = 0;
 618		mas_set(&mas, 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, i);
 630		j = i + 1;
 631		mas_set(&mas, 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)
 649static 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, range[i] >> 12, (range[i + 1] >> 12) - 1,
 769				xa_mk_value(range[i] >> 12), 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);
 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				req_range[i]   >> 12, /* start */
 806				req_range[i+1] >> 12, /* end */
 807				req_range[i+2] >> 12, /* size */
 808				req_range[i+3] >> 12, /* expected address */
 809				req_range[i+4],       /* expected return */
 810				xa_mk_value(req_range[i] >> 12)); /* pointer */
 811		mt_validate(mt);
 812	}
 813
 814	mt_set_non_kernel(1);
 815	mtree_erase(mt, 34148798727); /* create a deleted range. */
 816	mtree_erase(mt, 34148798725);
 817	check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414,
 818			34148798725, 0, mt);
 819
 820	mtree_destroy(mt);
 821}
 822
 823static 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, range[i] >> 12, (range[i + 1] >> 12) - 1,
 943				xa_mk_value(range[i] >> 12), 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);
 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				req_range[i]   >> 12, /* start */
 974				req_range[i+1] >> 12, /* end */
 975				req_range[i+2] >> 12, /* size */
 976				req_range[i+3] >> 12, /* expected address */
 977				req_range[i+4],       /* expected return */
 978				xa_mk_value(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
 989static 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, r[0], r[1], xa_mk_value(r[0]), 0);
1004	check_insert_range(mt, r[2], r[3], xa_mk_value(r[2]), 0);
1005	check_insert_range(mt, r[4], r[5], xa_mk_value(r[4]), -EEXIST);
1006	MT_BUG_ON(mt, !mt_height(mt));
1007	/* Store */
1008	check_store_range(mt, r[4], r[5], xa_mk_value(r[4]), 0);
1009	check_store_range(mt, r[6], r[7], xa_mk_value(r[6]), 0);
1010	check_store_range(mt, r[8], r[9], xa_mk_value(r[8]), 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, 50, false);
1016	mt_set_non_kernel(4);
1017	check_store_range(mt, 5, 47,  xa_mk_value(47), 0);
1018	MT_BUG_ON(mt, !mt_height(mt));
1019	mtree_destroy(mt);
1020
1021	/* Create tree of 1-100 */
1022	check_seq(mt, 100, false);
1023	/* Store 45-168 */
1024	mt_set_non_kernel(10);
1025	check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
1026	MT_BUG_ON(mt, !mt_height(mt));
1027	mtree_destroy(mt);
1028
1029	/* Create tree of 1-200 */
1030	check_seq(mt, 200, false);
1031	/* Store 45-168 */
1032	check_store_range(mt, r[10], r[11], xa_mk_value(r[10]), 0);
1033	MT_BUG_ON(mt, !mt_height(mt));
1034	mtree_destroy(mt);
1035
1036	check_seq(mt, 30, false);
1037	check_store_range(mt, 6, 18, xa_mk_value(6), 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, 400, false);
1044	mt_set_non_kernel(50);
1045	/* Store 118-128 */
1046	check_store_range(mt, r[12], r[13], xa_mk_value(r[12]), 0);
1047	mt_set_non_kernel(50);
1048	mtree_test_erase(mt, 140);
1049	mtree_test_erase(mt, 141);
1050	mtree_test_erase(mt, 142);
1051	mtree_test_erase(mt, 143);
1052	mtree_test_erase(mt, 130);
1053	mtree_test_erase(mt, 131);
1054	mtree_test_erase(mt, 132);
1055	mtree_test_erase(mt, 133);
1056	mtree_test_erase(mt, 134);
1057	mtree_test_erase(mt, 135);
1058	check_load(mt, r[12], xa_mk_value(r[12]));
1059	check_load(mt, r[13], xa_mk_value(r[12]));
1060	check_load(mt, r[13] - 1, xa_mk_value(r[12]));
1061	check_load(mt, r[13] + 1, xa_mk_value(r[13] + 1));
1062	check_load(mt, 135, NULL);
1063	check_load(mt, 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, 400, false);
1073	check_store_range(mt, 353, 361, xa_mk_value(353), 0);
1074	check_store_range(mt, 347, 352, xa_mk_value(347), 0);
1075
1076	check_load(mt, 346, xa_mk_value(346));
1077	for (i = 347; i <= 352; i++)
1078		check_load(mt, i, xa_mk_value(347));
1079	for (i = 353; i <= 361; i++)
1080		check_load(mt, i, xa_mk_value(353));
1081	check_load(mt, 362, xa_mk_value(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, 400, false);
1088	check_store_range(mt, 352, 364, NULL, 0);
1089	check_store_range(mt, 351, 363, xa_mk_value(352), 0);
1090	check_load(mt, 350, xa_mk_value(350));
1091	check_load(mt, 351, xa_mk_value(352));
1092	for (i = 352; i <= 363; i++)
1093		check_load(mt, i, xa_mk_value(352));
1094	check_load(mt, 364, NULL);
1095	check_load(mt, 365, xa_mk_value(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, 400, false);
1102	check_store_range(mt, 352, 364, NULL, 0);
1103	check_store_range(mt, 351, 364, xa_mk_value(352), 0);
1104	check_load(mt, 350, xa_mk_value(350));
1105	check_load(mt, 351, xa_mk_value(352));
1106	for (i = 352; i <= 364; i++)
1107		check_load(mt, i, xa_mk_value(352));
1108	check_load(mt, 365, xa_mk_value(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, 400, false);
1116	check_store_range(mt, 362, 367, xa_mk_value(362), 0);
1117	check_store_range(mt, 353, 361, xa_mk_value(353), 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, val, val2, xa_mk_value(val), 0);
1144	}
1145	check_store_range(mt, 2400, 2400, xa_mk_value(2400), 0);
1146	check_store_range(mt, 2411, 2411, xa_mk_value(2411), 0);
1147	check_store_range(mt, 2412, 2412, xa_mk_value(2412), 0);
1148	check_store_range(mt, 2396, 2400, xa_mk_value(4052020), 0);
1149	check_store_range(mt, 2402, 2402, xa_mk_value(2402), 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, val, val2, xa_mk_value(val), 0);
1158	}
1159	check_store_range(mt, 2422, 2422, xa_mk_value(2422), 0);
1160	check_store_range(mt, 2424, 2424, xa_mk_value(2424), 0);
1161	check_store_range(mt, 2425, 2425, xa_mk_value(2), 0);
1162	check_store_range(mt, 2460, 2470, NULL, 0);
1163	check_store_range(mt, 2435, 2460, xa_mk_value(2435), 0);
1164	check_store_range(mt, 2461, 2470, xa_mk_value(2461), 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, val, val2, xa_mk_value(val), 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, val, val2, xa_mk_value(val), 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, val, val2, xa_mk_value(val), 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, val, val2, xa_mk_value(val), 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, val, val2, xa_mk_value(val), 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, val, val2, xa_mk_value(val), 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, val, val2, xa_mk_value(val), 0);
1241	}
1242	check_store_range(mt, 161, 161, xa_mk_value(161), 0);
1243	check_store_range(mt, 162, 162, xa_mk_value(162), 0);
1244	check_store_range(mt, 163, 163, xa_mk_value(163), 0);
1245	check_store_range(mt, 240, 249, NULL, 0);
1246	mtree_erase(mt, 200);
1247	mtree_erase(mt, 210);
1248	mtree_erase(mt, 220);
1249	mtree_erase(mt, 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, val, val2, xa_mk_value(val), 0);
1259	}
1260	check_store_range(mt, 4600, 4959, xa_mk_value(1), 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, val, val2, xa_mk_value(val), 0);
1270	}
1271	check_store_range(mt, 4811, 4811, xa_mk_value(4811), 0);
1272	check_store_range(mt, 4812, 4812, xa_mk_value(4812), 0);
1273	check_store_range(mt, 4861, 4861, xa_mk_value(4861), 0);
1274	check_store_range(mt, 4862, 4862, xa_mk_value(4862), 0);
1275	check_store_range(mt, 4842, 4849, NULL, 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, val, val2, xa_mk_value(val), 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, 11450 + i, 11450 + i + 1, NULL, 0);
1290	for (i = 5; i < 65; i += 10)
1291		check_store_range(mt, 11770 + i, 11770 + i + 1, NULL, 0);
1292
1293	MT_BUG_ON(mt, mt_height(mt) >= 4);
1294	for (i = 5; i < 45; i += 10)
1295		check_store_range(mt, 11700 + i, 11700 + i + 1, NULL, 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, val, val2, xa_mk_value(val), 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, 7800 + i, 7800 + i + 1, NULL, 0);
1311
1312	for (i = 1; i < 16; i++)
1313		check_store_range(mt, 8185 + i, 8185 + i + 1,
1314				  xa_mk_value(8185+i), 0);
1315	MT_BUG_ON(mt, mt_height(mt) >= 4);
1316	/* triple split across multiple levels. */
1317	check_store_range(mt, 8184, 8184, xa_mk_value(8184), 0);
1318	if (!MAPLE_32BIT)
1319		MT_BUG_ON(mt, mt_height(mt) != 4);
1320}
1321
1322static 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, limit, 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, 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
1346static 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, 30, false);
1356
1357	rcu_read_lock();
1358	value = mas_find(&mas, ULONG_MAX);
1359	MT_BUG_ON(mt, value != xa_mk_value(index));
1360	value = mas_prev(&mas, 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, i*10, i*10+5);
1370		mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
1371	}
1372
1373	mas_set(&mas, 20);
1374	value = mas_walk(&mas);
1375	MT_BUG_ON(mt, value != xa_mk_value(2));
1376
1377	value = mas_prev(&mas, 19);
1378	MT_BUG_ON(mt, value != NULL);
1379
1380	mas_set(&mas, 80);
1381	value = mas_walk(&mas);
1382	MT_BUG_ON(mt, value != xa_mk_value(8));
1383
1384	value = mas_prev(&mas, 76);
1385	MT_BUG_ON(mt, value != NULL);
1386
1387	mas_unlock(&mas);
1388}
1389
1390static noinline void __init check_store_null(struct maple_tree *mt)
1391{
1392	MA_STATE(mas, mt, 0, ULONG_MAX);
1393
1394	/*
1395	 * Store NULL at range [0, ULONG_MAX] to an empty tree should result
1396	 * in an empty tree
1397	 */
1398	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1399	mas_lock(&mas);
1400	mas_store_gfp(&mas, NULL, GFP_KERNEL);
1401	MT_BUG_ON(mt, !mtree_empty(mt));
1402	mas_unlock(&mas);
1403	mtree_destroy(mt);
1404
1405	/*
1406	 * Store NULL at any range to an empty tree should result in an empty
1407	 * tree
1408	 */
1409	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1410	mas_lock(&mas);
1411	mas_set_range(&mas, 3, 10);
1412	mas_store_gfp(&mas, NULL, GFP_KERNEL);
1413	MT_BUG_ON(mt, !mtree_empty(mt));
1414	mas_unlock(&mas);
1415	mtree_destroy(mt);
1416
1417	/*
1418	 * Store NULL at range [0, ULONG_MAX] to a single entry tree should
1419	 * result in an empty tree
1420	 */
1421	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1422	mas_lock(&mas);
1423	mas_set(&mas, 0);
1424	mas_store_gfp(&mas, &mas, GFP_KERNEL);
1425	mas_set_range(&mas, 0, ULONG_MAX);
1426	mas_store_gfp(&mas, NULL, GFP_KERNEL);
1427	MT_BUG_ON(mt, !mtree_empty(mt));
1428	mas_unlock(&mas);
1429	mtree_destroy(mt);
1430
1431	/*
1432	 * Store NULL at range [0, n] to a single entry tree should
1433	 * result in an empty tree
1434	 */
1435	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1436	mas_lock(&mas);
1437	mas_set(&mas, 0);
1438	mas_store_gfp(&mas, &mas, GFP_KERNEL);
1439	mas_set_range(&mas, 0, 5);
1440	mas_store_gfp(&mas, NULL, GFP_KERNEL);
1441	MT_BUG_ON(mt, !mtree_empty(mt));
1442	mas_unlock(&mas);
1443	mtree_destroy(mt);
1444
1445	/*
1446	 * Store NULL at range [m, n] where m > 0 to a single entry tree
1447	 * should still be a single entry tree
1448	 */
1449	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1450	mas_lock(&mas);
1451	mas_set(&mas, 0);
1452	mas_store_gfp(&mas, &mas, GFP_KERNEL);
1453	mas_set_range(&mas, 2, 5);
1454	mas_store_gfp(&mas, NULL, GFP_KERNEL);
1455	MT_BUG_ON(mt, mtree_empty(mt));
1456//	MT_BUG_ON(mt, xa_is_node(mas_root(&mas)));
1457	mas_unlock(&mas);
1458	mtree_destroy(mt);
1459
1460	/*
1461	 * Store NULL at range [0, ULONG_MAX] to a tree with node should
1462	 * result in an empty tree
1463	 */
1464	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1465	mas_lock(&mas);
1466	mas_set_range(&mas, 1, 3);
1467	mas_store_gfp(&mas, &mas, GFP_KERNEL);
1468//	MT_BUG_ON(mt, !xa_is_node(mas_root(&mas)));
1469	mas_set_range(&mas, 0, ULONG_MAX);
1470	mas_store_gfp(&mas, NULL, GFP_KERNEL);
1471	MT_BUG_ON(mt, !mtree_empty(mt));
1472	mas_unlock(&mas);
1473	mtree_destroy(mt);
1474}
1475
1476static noinline void __init check_root_expand(struct maple_tree *mt)
1477{
1478	MA_STATE(mas, mt, 0, 0);
1479	void *ptr;
1480
1481
1482	mas_lock(&mas);
1483	mas_set(&mas, 3);
1484	ptr = mas_walk(&mas);
1485	MT_BUG_ON(mt, mas.index != 0);
1486	MT_BUG_ON(mt, ptr != NULL);
1487	MT_BUG_ON(mt, mas.index != 0);
1488	MT_BUG_ON(mt, mas.last != ULONG_MAX);
1489
1490	ptr = &check_prev_entry;
1491	mas_set(&mas, 1);
1492	mas_store_gfp(&mas, ptr, GFP_KERNEL);
1493
1494	mas_set(&mas, 0);
1495	ptr = mas_walk(&mas);
1496	MT_BUG_ON(mt, ptr != NULL);
1497
1498	mas_set(&mas, 1);
1499	ptr = mas_walk(&mas);
1500	MT_BUG_ON(mt, ptr != &check_prev_entry);
1501
1502	mas_set(&mas, 2);
1503	ptr = mas_walk(&mas);
1504	MT_BUG_ON(mt, ptr != NULL);
1505	mas_unlock(&mas);
1506	mtree_destroy(mt);
1507
1508
1509	mt_init_flags(mt, 0);
1510	mas_lock(&mas);
1511
1512	mas_set(&mas, 0);
1513	ptr = &check_prev_entry;
1514	mas_store_gfp(&mas, ptr, GFP_KERNEL);
1515
1516	mas_set(&mas, 5);
1517	ptr = mas_walk(&mas);
1518	MT_BUG_ON(mt, ptr != NULL);
1519	MT_BUG_ON(mt, mas.index != 1);
1520	MT_BUG_ON(mt, mas.last != ULONG_MAX);
1521
1522	mas_set_range(&mas, 0, 100);
1523	ptr = mas_walk(&mas);
1524	MT_BUG_ON(mt, ptr != &check_prev_entry);
1525	MT_BUG_ON(mt, mas.last != 0);
1526	mas_unlock(&mas);
1527	mtree_destroy(mt);
1528
1529	mt_init_flags(mt, 0);
1530	mas_lock(&mas);
1531
1532	mas_set(&mas, 0);
1533	ptr = (void *)((unsigned long) check_prev_entry | 1UL);
1534	mas_store_gfp(&mas, ptr, GFP_KERNEL);
1535	ptr = mas_next(&mas, ULONG_MAX);
1536	MT_BUG_ON(mt, ptr != NULL);
1537	MT_BUG_ON(mt, (mas.index != 1) && (mas.last != ULONG_MAX));
1538
1539	mas_set(&mas, 1);
1540	ptr = mas_prev(&mas, 0);
1541	MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1542	MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 1UL));
1543
1544	mas_unlock(&mas);
1545
1546	mtree_destroy(mt);
1547
1548	mt_init_flags(mt, 0);
1549	mas_lock(&mas);
1550	mas_set(&mas, 0);
1551	ptr = (void *)((unsigned long) check_prev_entry | 2UL);
1552	mas_store_gfp(&mas, ptr, GFP_KERNEL);
1553	ptr = mas_next(&mas, ULONG_MAX);
1554	MT_BUG_ON(mt, ptr != NULL);
1555	MT_BUG_ON(mt, (mas.index != ULONG_MAX) && (mas.last != ULONG_MAX));
1556
1557	mas_set(&mas, 1);
1558	ptr = mas_prev(&mas, 0);
1559	MT_BUG_ON(mt, (mas.index != 0) && (mas.last != 0));
1560	MT_BUG_ON(mt, ptr != (void *)((unsigned long) check_prev_entry | 2UL));
1561
1562
1563	mas_unlock(&mas);
1564}
1565
1566static noinline void __init check_deficient_node(struct maple_tree *mt)
1567{
1568	MA_STATE(mas, mt, 0, 0);
1569	int count;
1570
1571	mas_lock(&mas);
1572	for (count = 0; count < 10; count++) {
1573		mas_set(&mas, count);
1574		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
1575	}
1576
1577	for (count = 20; count < 39; count++) {
1578		mas_set(&mas, count);
1579		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
1580	}
1581
1582	for (count = 10; count < 12; count++) {
1583		mas_set(&mas, count);
1584		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
1585	}
1586	mas_unlock(&mas);
1587	mt_validate(mt);
1588}
1589
1590static noinline void __init check_gap_combining(struct maple_tree *mt)
1591{
1592	struct maple_enode *mn1, *mn2;
1593	void *entry;
1594	unsigned long singletons = 100;
1595	static const unsigned long *seq100;
1596	static const unsigned long seq100_64[] = {
1597		/* 0-5 */
1598		74, 75, 76,
1599		50, 100, 2,
1600
1601		/* 6-12 */
1602		44, 45, 46, 43,
1603		20, 50, 3,
1604
1605		/* 13-20*/
1606		80, 81, 82,
1607		76, 2, 79, 85, 4,
1608	};
1609
1610	static const unsigned long seq100_32[] = {
1611		/* 0-5 */
1612		61, 62, 63,
1613		50, 100, 2,
1614
1615		/* 6-12 */
1616		31, 32, 33, 30,
1617		20, 50, 3,
1618
1619		/* 13-20*/
1620		80, 81, 82,
1621		76, 2, 79, 85, 4,
1622	};
1623
1624	static const unsigned long seq2000[] = {
1625		1152, 1151,
1626		1100, 1200, 2,
1627	};
1628	static const unsigned long seq400[] = {
1629		286, 318,
1630		256, 260, 266, 270, 275, 280, 290, 398,
1631		286, 310,
1632	};
1633
1634	unsigned long index;
1635
1636	MA_STATE(mas, mt, 0, 0);
1637
1638	if (MAPLE_32BIT)
1639		seq100 = seq100_32;
1640	else
1641		seq100 = seq100_64;
1642
1643	index = seq100[0];
1644	mas_set(&mas, index);
1645	MT_BUG_ON(mt, !mtree_empty(mt));
1646	check_seq(mt, singletons, false); /* create 100 singletons. */
1647
1648	mt_set_non_kernel(1);
1649	mtree_test_erase(mt, seq100[2]);
1650	check_load(mt, seq100[2], NULL);
1651	mtree_test_erase(mt, seq100[1]);
1652	check_load(mt, seq100[1], NULL);
1653
1654	rcu_read_lock();
1655	entry = mas_find(&mas, ULONG_MAX);
1656	MT_BUG_ON(mt, entry != xa_mk_value(index));
1657	mn1 = mas.node;
1658	mas_next(&mas, ULONG_MAX);
1659	entry = mas_next(&mas, ULONG_MAX);
1660	MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1661	mn2 = mas.node;
1662	MT_BUG_ON(mt, mn1 == mn2); /* test the test. */
1663
1664	/*
1665	 * At this point, there is a gap of 2 at index + 1 between seq100[3] and
1666	 * seq100[4]. Search for the gap.
1667	 */
1668	mt_set_non_kernel(1);
1669	mas_reset(&mas);
1670	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[3], seq100[4],
1671					     seq100[5]));
1672	MT_BUG_ON(mt, mas.index != index + 1);
1673	rcu_read_unlock();
1674
1675	mtree_test_erase(mt, seq100[6]);
1676	check_load(mt, seq100[6], NULL);
1677	mtree_test_erase(mt, seq100[7]);
1678	check_load(mt, seq100[7], NULL);
1679	mtree_test_erase(mt, seq100[8]);
1680	index = seq100[9];
1681
1682	rcu_read_lock();
1683	mas.index = index;
1684	mas.last = index;
1685	mas_reset(&mas);
1686	entry = mas_find(&mas, ULONG_MAX);
1687	MT_BUG_ON(mt, entry != xa_mk_value(index));
1688	mn1 = mas.node;
1689	entry = mas_next(&mas, ULONG_MAX);
1690	MT_BUG_ON(mt, entry != xa_mk_value(index + 4));
1691	mas_next(&mas, ULONG_MAX); /* go to the next entry. */
1692	mn2 = mas.node;
1693	MT_BUG_ON(mt, mn1 == mn2); /* test the next entry is in the next node. */
1694
1695	/*
1696	 * At this point, there is a gap of 3 at seq100[6].  Find it by
1697	 * searching 20 - 50 for size 3.
1698	 */
1699	mas_reset(&mas);
1700	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[10], seq100[11],
1701					     seq100[12]));
1702	MT_BUG_ON(mt, mas.index != seq100[6]);
1703	rcu_read_unlock();
1704
1705	mt_set_non_kernel(1);
1706	mtree_store(mt, seq100[13], NULL, GFP_KERNEL);
1707	check_load(mt, seq100[13], NULL);
1708	check_load(mt, seq100[14], xa_mk_value(seq100[14]));
1709	mtree_store(mt, seq100[14], NULL, GFP_KERNEL);
1710	check_load(mt, seq100[13], NULL);
1711	check_load(mt, seq100[14], NULL);
1712
1713	mas_reset(&mas);
1714	rcu_read_lock();
1715	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[15],
1716					     seq100[17]));
1717	MT_BUG_ON(mt, mas.index != seq100[13]);
1718	mt_validate(mt);
1719	rcu_read_unlock();
1720
1721	/*
1722	 * *DEPRECATED: no retries anymore* Test retry entry in the start of a
1723	 * gap.
1724	 */
1725	mt_set_non_kernel(2);
1726	mtree_test_store_range(mt, seq100[18], seq100[14], NULL);
1727	mtree_test_erase(mt, seq100[15]);
1728	mas_reset(&mas);
1729	rcu_read_lock();
1730	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq100[16], seq100[19],
1731					     seq100[20]));
1732	rcu_read_unlock();
1733	MT_BUG_ON(mt, mas.index != seq100[18]);
1734	mt_validate(mt);
1735	mtree_destroy(mt);
1736
1737	/* seq 2000 tests are for multi-level tree gaps */
1738	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1739	check_seq(mt, 2000, false);
1740	mt_set_non_kernel(1);
1741	mtree_test_erase(mt, seq2000[0]);
1742	mtree_test_erase(mt, seq2000[1]);
1743
1744	mt_set_non_kernel(2);
1745	mas_reset(&mas);
1746	rcu_read_lock();
1747	MT_BUG_ON(mt, mas_empty_area_rev(&mas, seq2000[2], seq2000[3],
1748					     seq2000[4]));
1749	MT_BUG_ON(mt, mas.index != seq2000[1]);
1750	rcu_read_unlock();
1751	mt_validate(mt);
1752	mtree_destroy(mt);
1753
1754	/* seq 400 tests rebalancing over two levels. */
1755	mt_set_non_kernel(99);
1756	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1757	check_seq(mt, 400, false);
1758	mtree_test_store_range(mt, seq400[0], seq400[1], NULL);
1759	mt_set_non_kernel(0);
1760	mtree_destroy(mt);
1761
1762	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
1763	check_seq(mt, 400, false);
1764	mt_set_non_kernel(50);
1765	mtree_test_store_range(mt, seq400[2], seq400[9],
1766			       xa_mk_value(seq400[2]));
1767	mtree_test_store_range(mt, seq400[3], seq400[9],
1768			       xa_mk_value(seq400[3]));
1769	mtree_test_store_range(mt, seq400[4], seq400[9],
1770			       xa_mk_value(seq400[4]));
1771	mtree_test_store_range(mt, seq400[5], seq400[9],
1772			       xa_mk_value(seq400[5]));
1773	mtree_test_store_range(mt, seq400[0], seq400[9],
1774			       xa_mk_value(seq400[0]));
1775	mtree_test_store_range(mt, seq400[6], seq400[9],
1776			       xa_mk_value(seq400[6]));
1777	mtree_test_store_range(mt, seq400[7], seq400[9],
1778			       xa_mk_value(seq400[7]));
1779	mtree_test_store_range(mt, seq400[8], seq400[9],
1780			       xa_mk_value(seq400[8]));
1781	mtree_test_store_range(mt, seq400[10], seq400[11],
1782			       xa_mk_value(seq400[10]));
1783	mt_validate(mt);
1784	mt_set_non_kernel(0);
1785	mtree_destroy(mt);
1786}
1787static noinline void __init check_node_overwrite(struct maple_tree *mt)
1788{
1789	int i, max = 4000;
1790
1791	for (i = 0; i < max; i++)
1792		mtree_test_store_range(mt, i*100, i*100 + 50, xa_mk_value(i*100));
1793
1794	mtree_test_store_range(mt, 319951, 367950, NULL);
1795	/*mt_dump(mt, mt_dump_dec); */
1796	mt_validate(mt);
1797}
1798
1799#if defined(BENCH_SLOT_STORE)
1800static noinline void __init bench_slot_store(struct maple_tree *mt)
1801{
1802	int i, brk = 105, max = 1040, brk_start = 100, count = 20000000;
1803
1804	for (i = 0; i < max; i += 10)
1805		mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1806
1807	for (i = 0; i < count; i++) {
1808		mtree_store_range(mt, brk, brk, NULL, GFP_KERNEL);
1809		mtree_store_range(mt, brk_start, brk, xa_mk_value(brk),
1810				  GFP_KERNEL);
1811	}
1812}
1813#endif
1814
1815#if defined(BENCH_NODE_STORE)
1816static noinline void __init bench_node_store(struct maple_tree *mt)
1817{
1818	int i, overwrite = 76, max = 240, count = 20000000;
1819
1820	for (i = 0; i < max; i += 10)
1821		mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1822
1823	for (i = 0; i < count; i++) {
1824		mtree_store_range(mt, overwrite,  overwrite + 15,
1825				  xa_mk_value(overwrite), GFP_KERNEL);
1826
1827		overwrite += 5;
1828		if (overwrite >= 135)
1829			overwrite = 76;
1830	}
1831}
1832#endif
1833
1834#if defined(BENCH_AWALK)
1835static noinline void __init bench_awalk(struct maple_tree *mt)
1836{
1837	int i, max = 2500, count = 50000000;
1838	MA_STATE(mas, mt, 1470, 1470);
1839
1840	for (i = 0; i < max; i += 10)
1841		mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1842
1843	mtree_store_range(mt, 1470, 1475, NULL, GFP_KERNEL);
1844
1845	for (i = 0; i < count; i++) {
1846		mas_empty_area_rev(&mas, 0, 2000, 10);
1847		mas_reset(&mas);
1848	}
1849}
1850#endif
1851#if defined(BENCH_WALK)
1852static noinline void __init bench_walk(struct maple_tree *mt)
1853{
1854	int i, max = 2500, count = 550000000;
1855	MA_STATE(mas, mt, 1470, 1470);
1856
1857	for (i = 0; i < max; i += 10)
1858		mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1859
1860	for (i = 0; i < count; i++) {
1861		mas_walk(&mas);
1862		mas_reset(&mas);
1863	}
1864
1865}
1866#endif
1867
1868#if defined(BENCH_LOAD)
1869static noinline void __init bench_load(struct maple_tree *mt)
1870{
1871	int i, max = 2500, count = 550000000;
1872
1873	for (i = 0; i < max; i += 10)
1874		mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
1875
1876	for (i = 0; i < count; i++)
1877		mtree_load(mt, 1470);
1878}
1879#endif
1880
1881#if defined(BENCH_MT_FOR_EACH)
1882static noinline void __init bench_mt_for_each(struct maple_tree *mt)
1883{
1884	int i, count = 1000000;
1885	unsigned long max = 2500, index = 0;
1886	void *entry;
1887
1888	for (i = 0; i < max; i += 5)
1889		mtree_store_range(mt, i, i + 4, xa_mk_value(i), GFP_KERNEL);
1890
1891	for (i = 0; i < count; i++) {
1892		unsigned long j = 0;
1893
1894		mt_for_each(mt, entry, index, max) {
1895			MT_BUG_ON(mt, entry != xa_mk_value(j));
1896			j += 5;
1897		}
1898
1899		index = 0;
1900	}
1901
1902}
1903#endif
1904
1905#if defined(BENCH_MAS_FOR_EACH)
1906static noinline void __init bench_mas_for_each(struct maple_tree *mt)
1907{
1908	int i, count = 1000000;
1909	unsigned long max = 2500;
1910	void *entry;
1911	MA_STATE(mas, mt, 0, 0);
1912
1913	for (i = 0; i < max; i += 5) {
1914		int gap = 4;
1915
1916		if (i % 30 == 0)
1917			gap = 3;
1918		mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1919	}
1920
1921	rcu_read_lock();
1922	for (i = 0; i < count; i++) {
1923		unsigned long j = 0;
1924
1925		mas_for_each(&mas, entry, max) {
1926			MT_BUG_ON(mt, entry != xa_mk_value(j));
1927			j += 5;
1928		}
1929		mas_set(&mas, 0);
1930	}
1931	rcu_read_unlock();
1932
1933}
1934#endif
1935#if defined(BENCH_MAS_PREV)
1936static noinline void __init bench_mas_prev(struct maple_tree *mt)
1937{
1938	int i, count = 1000000;
1939	unsigned long max = 2500;
1940	void *entry;
1941	MA_STATE(mas, mt, 0, 0);
1942
1943	for (i = 0; i < max; i += 5) {
1944		int gap = 4;
1945
1946		if (i % 30 == 0)
1947			gap = 3;
1948		mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
1949	}
1950
1951	rcu_read_lock();
1952	for (i = 0; i < count; i++) {
1953		unsigned long j = 2495;
1954
1955		mas_set(&mas, ULONG_MAX);
1956		while ((entry = mas_prev(&mas, 0)) != NULL) {
1957			MT_BUG_ON(mt, entry != xa_mk_value(j));
1958			j -= 5;
1959		}
1960	}
1961	rcu_read_unlock();
1962
1963}
1964#endif
1965/* check_forking - simulate the kernel forking sequence with the tree. */
1966static noinline void __init check_forking(void)
1967{
1968	struct maple_tree mt, newmt;
1969	int i, nr_entries = 134, ret;
1970	void *val;
1971	MA_STATE(mas, &mt, 0, 0);
1972	MA_STATE(newmas, &newmt, 0, 0);
1973	struct rw_semaphore mt_lock, newmt_lock;
1974
1975	init_rwsem(&mt_lock);
1976	init_rwsem(&newmt_lock);
1977
1978	mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
1979	mt_set_external_lock(&mt, &mt_lock);
1980
1981	mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
1982	mt_set_external_lock(&newmt, &newmt_lock);
1983
1984	down_write(&mt_lock);
1985	for (i = 0; i <= nr_entries; i++) {
1986		mas_set_range(&mas, i*10, i*10 + 5);
1987		mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
1988	}
1989
1990	down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING);
1991	ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
1992	if (ret) {
1993		pr_err("OOM!");
1994		BUG_ON(1);
1995	}
1996
1997	mas_set(&newmas, 0);
1998	mas_for_each(&newmas, val, ULONG_MAX)
1999		mas_store(&newmas, val);
2000
2001	mas_destroy(&newmas);
2002	mas_destroy(&mas);
2003	mt_validate(&newmt);
2004	__mt_destroy(&newmt);
2005	__mt_destroy(&mt);
2006	up_write(&newmt_lock);
2007	up_write(&mt_lock);
2008}
2009
2010static noinline void __init check_iteration(struct maple_tree *mt)
2011{
2012	int i, nr_entries = 125;
2013	void *val;
2014	MA_STATE(mas, mt, 0, 0);
2015
2016	for (i = 0; i <= nr_entries; i++)
2017		mtree_store_range(mt, i * 10, i * 10 + 9,
2018				  xa_mk_value(i), GFP_KERNEL);
2019
2020	mt_set_non_kernel(99999);
2021
2022	i = 0;
2023	mas_lock(&mas);
2024	mas_for_each(&mas, val, 925) {
2025		MT_BUG_ON(mt, mas.index != i * 10);
2026		MT_BUG_ON(mt, mas.last != i * 10 + 9);
2027		/* Overwrite end of entry 92 */
2028		if (i == 92) {
2029			mas.index = 925;
2030			mas.last = 929;
2031			mas_store(&mas, val);
2032		}
2033		i++;
2034	}
2035	/* Ensure mas_find() gets the next value */
2036	val = mas_find(&mas, ULONG_MAX);
2037	MT_BUG_ON(mt, val != xa_mk_value(i));
2038
2039	mas_set(&mas, 0);
2040	i = 0;
2041	mas_for_each(&mas, val, 785) {
2042		MT_BUG_ON(mt, mas.index != i * 10);
2043		MT_BUG_ON(mt, mas.last != i * 10 + 9);
2044		/* Overwrite start of entry 78 */
2045		if (i == 78) {
2046			mas.index = 780;
2047			mas.last = 785;
2048			mas_store(&mas, val);
2049		} else {
2050			i++;
2051		}
2052	}
2053	val = mas_find(&mas, ULONG_MAX);
2054	MT_BUG_ON(mt, val != xa_mk_value(i));
2055
2056	mas_set(&mas, 0);
2057	i = 0;
2058	mas_for_each(&mas, val, 765) {
2059		MT_BUG_ON(mt, mas.index != i * 10);
2060		MT_BUG_ON(mt, mas.last != i * 10 + 9);
2061		/* Overwrite end of entry 76 and advance to the end */
2062		if (i == 76) {
2063			mas.index = 760;
2064			mas.last = 765;
2065			mas_store(&mas, val);
2066		}
2067		i++;
2068	}
2069	/* Make sure the next find returns the one after 765, 766-769 */
2070	val = mas_find(&mas, ULONG_MAX);
2071	MT_BUG_ON(mt, val != xa_mk_value(76));
2072	mas_unlock(&mas);
2073	mas_destroy(&mas);
2074	mt_set_non_kernel(0);
2075}
2076
2077static noinline void __init check_mas_store_gfp(struct maple_tree *mt)
2078{
2079
2080	struct maple_tree newmt;
2081	int i, nr_entries = 135;
2082	void *val;
2083	MA_STATE(mas, mt, 0, 0);
2084	MA_STATE(newmas, mt, 0, 0);
2085
2086	for (i = 0; i <= nr_entries; i++)
2087		mtree_store_range(mt, i*10, i*10 + 5,
2088				  xa_mk_value(i), GFP_KERNEL);
2089
2090	mt_set_non_kernel(99999);
2091	mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
2092	newmas.tree = &newmt;
2093	rcu_read_lock();
2094	mas_lock(&newmas);
2095	mas_reset(&newmas);
2096	mas_set(&mas, 0);
2097	mas_for_each(&mas, val, ULONG_MAX) {
2098		newmas.index = mas.index;
2099		newmas.last = mas.last;
2100		mas_store_gfp(&newmas, val, GFP_KERNEL);
2101	}
2102	mas_unlock(&newmas);
2103	rcu_read_unlock();
2104	mt_validate(&newmt);
2105	mt_set_non_kernel(0);
2106	mtree_destroy(&newmt);
2107}
2108
2109#if defined(BENCH_FORK)
2110static noinline void __init bench_forking(void)
2111{
2112	struct maple_tree mt, newmt;
2113	int i, nr_entries = 134, nr_fork = 80000, ret;
2114	void *val;
2115	MA_STATE(mas, &mt, 0, 0);
2116	MA_STATE(newmas, &newmt, 0, 0);
2117	struct rw_semaphore mt_lock, newmt_lock;
2118
2119	init_rwsem(&mt_lock);
2120	init_rwsem(&newmt_lock);
2121
2122	mt_init_flags(&mt, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
2123	mt_set_external_lock(&mt, &mt_lock);
2124
2125	down_write(&mt_lock);
2126	for (i = 0; i <= nr_entries; i++) {
2127		mas_set_range(&mas, i*10, i*10 + 5);
2128		mas_store_gfp(&mas, xa_mk_value(i), GFP_KERNEL);
2129	}
2130
2131	for (i = 0; i < nr_fork; i++) {
2132		mt_init_flags(&newmt,
2133			      MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN);
2134		mt_set_external_lock(&newmt, &newmt_lock);
2135
2136		down_write_nested(&newmt_lock, SINGLE_DEPTH_NESTING);
2137		ret = __mt_dup(&mt, &newmt, GFP_KERNEL);
2138		if (ret) {
2139			pr_err("OOM!");
2140			BUG_ON(1);
2141		}
2142
2143		mas_set(&newmas, 0);
2144		mas_for_each(&newmas, val, ULONG_MAX)
2145			mas_store(&newmas, val);
2146
2147		mas_destroy(&newmas);
2148		mt_validate(&newmt);
2149		__mt_destroy(&newmt);
2150		up_write(&newmt_lock);
2151	}
2152	mas_destroy(&mas);
2153	__mt_destroy(&mt);
2154	up_write(&mt_lock);
2155}
2156#endif
2157
2158static noinline void __init next_prev_test(struct maple_tree *mt)
2159{
2160	int i, nr_entries;
2161	void *val;
2162	MA_STATE(mas, mt, 0, 0);
2163	struct maple_enode *mn;
2164	static const unsigned long *level2;
2165	static const unsigned long level2_64[] = { 707, 1000, 710, 715, 720,
2166						   725};
2167	static const unsigned long level2_32[] = { 1747, 2000, 1750, 1755,
2168						   1760, 1765};
2169	unsigned long last_index;
2170
2171	if (MAPLE_32BIT) {
2172		nr_entries = 500;
2173		level2 = level2_32;
2174		last_index = 0x138e;
2175	} else {
2176		nr_entries = 200;
2177		level2 = level2_64;
2178		last_index = 0x7d6;
2179	}
2180
2181	for (i = 0; i <= nr_entries; i++)
2182		mtree_store_range(mt, i*10, i*10 + 5,
2183				  xa_mk_value(i), GFP_KERNEL);
2184
2185	mas_lock(&mas);
2186	for (i = 0; i <= nr_entries / 2; i++) {
2187		mas_next(&mas, 1000);
2188		if (mas_is_none(&mas))
2189			break;
2190
2191	}
2192	mas_reset(&mas);
2193	mas_set(&mas, 0);
2194	i = 0;
2195	mas_for_each(&mas, val, 1000) {
2196		i++;
2197	}
2198
2199	mas_reset(&mas);
2200	mas_set(&mas, 0);
2201	i = 0;
2202	mas_for_each(&mas, val, 1000) {
2203		mas_pause(&mas);
2204		i++;
2205	}
2206
2207	/*
2208	 * 680 - 685 = 0x61a00001930c
2209	 * 686 - 689 = NULL;
2210	 * 690 - 695 = 0x61a00001930c
2211	 * Check simple next/prev
2212	 */
2213	mas_set(&mas, 686);
2214	val = mas_walk(&mas);
2215	MT_BUG_ON(mt, val != NULL);
2216
2217	val = mas_next(&mas, 1000);
2218	MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2219	MT_BUG_ON(mt, mas.index != 690);
2220	MT_BUG_ON(mt, mas.last != 695);
2221
2222	val = mas_prev(&mas, 0);
2223	MT_BUG_ON(mt, val != xa_mk_value(680 / 10));
2224	MT_BUG_ON(mt, mas.index != 680);
2225	MT_BUG_ON(mt, mas.last != 685);
2226
2227	val = mas_next(&mas, 1000);
2228	MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
2229	MT_BUG_ON(mt, mas.index != 690);
2230	MT_BUG_ON(mt, mas.last != 695);
2231
2232	val = mas_next(&mas, 1000);
2233	MT_BUG_ON(mt, val != xa_mk_value(700 / 10));
2234	MT_BUG_ON(mt, mas.index != 700);
2235	MT_BUG_ON(mt, mas.last != 705);
2236
2237	/* Check across node boundaries of the tree */
2238	mas_set(&mas, 70);
2239	val = mas_walk(&mas);
2240	MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2241	MT_BUG_ON(mt, mas.index != 70);
2242	MT_BUG_ON(mt, mas.last != 75);
2243
2244	val = mas_next(&mas, 1000);
2245	MT_BUG_ON(mt, val != xa_mk_value(80 / 10));
2246	MT_BUG_ON(mt, mas.index != 80);
2247	MT_BUG_ON(mt, mas.last != 85);
2248
2249	val = mas_prev(&mas, 70);
2250	MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
2251	MT_BUG_ON(mt, mas.index != 70);
2252	MT_BUG_ON(mt, mas.last != 75);
2253
2254	/* Check across two levels of the tree */
2255	mas_reset(&mas);
2256	mas_set(&mas, level2[0]);
2257	val = mas_walk(&mas);
2258	MT_BUG_ON(mt, val != NULL);
2259	val = mas_next(&mas, level2[1]);
2260	MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2261	MT_BUG_ON(mt, mas.index != level2[2]);
2262	MT_BUG_ON(mt, mas.last != level2[3]);
2263	mn = mas.node;
2264
2265	val = mas_next(&mas, level2[1]);
2266	MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10));
2267	MT_BUG_ON(mt, mas.index != level2[4]);
2268	MT_BUG_ON(mt, mas.last != level2[5]);
2269	MT_BUG_ON(mt, mn == mas.node);
2270
2271	val = mas_prev(&mas, 0);
2272	MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
2273	MT_BUG_ON(mt, mas.index != level2[2]);
2274	MT_BUG_ON(mt, mas.last != level2[3]);
2275
2276	/* Check running off the end and back on */
2277	mas_set(&mas, nr_entries * 10);
2278	val = mas_walk(&mas);
2279	MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2280	MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2281	MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2282
2283	val = mas_next(&mas, ULONG_MAX);
2284	MT_BUG_ON(mt, val != NULL);
2285	MT_BUG_ON(mt, mas.index != last_index);
2286	MT_BUG_ON(mt, mas.last != ULONG_MAX);
2287
2288	val = mas_prev(&mas, 0);
2289	MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
2290	MT_BUG_ON(mt, mas.index != (nr_entries * 10));
2291	MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
2292
2293	/* Check running off the start and back on */
2294	mas_reset(&mas);
2295	mas_set(&mas, 10);
2296	val = mas_walk(&mas);
2297	MT_BUG_ON(mt, val != xa_mk_value(1));
2298	MT_BUG_ON(mt, mas.index != 10);
2299	MT_BUG_ON(mt, mas.last != 15);
2300
2301	val = mas_prev(&mas, 0);
2302	MT_BUG_ON(mt, val != xa_mk_value(0));
2303	MT_BUG_ON(mt, mas.index != 0);
2304	MT_BUG_ON(mt, mas.last != 5);
2305
2306	val = mas_prev(&mas, 0);
2307	MT_BUG_ON(mt, val != NULL);
2308	MT_BUG_ON(mt, mas.index != 0);
2309	MT_BUG_ON(mt, mas.last != 5);
2310	MT_BUG_ON(mt, !mas_is_underflow(&mas));
2311
2312	mas.index = 0;
2313	mas.last = 5;
2314	mas_store(&mas, NULL);
2315	mas_reset(&mas);
2316	mas_set(&mas, 10);
2317	mas_walk(&mas);
2318
2319	val = mas_prev(&mas, 0);
2320	MT_BUG_ON(mt, val != NULL);
2321	MT_BUG_ON(mt, mas.index != 0);
2322	MT_BUG_ON(mt, mas.last != 9);
2323	mas_unlock(&mas);
2324
2325	mtree_destroy(mt);
2326
2327	mt_init(mt);
2328	mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL);
2329	mtree_store_range(mt, 5, 5, xa_mk_value(5), GFP_KERNEL);
2330	rcu_read_lock();
2331	mas_set(&mas, 5);
2332	val = mas_prev(&mas, 4);
2333	MT_BUG_ON(mt, val != NULL);
2334	rcu_read_unlock();
2335}
2336
2337
2338
2339/* Test spanning writes that require balancing right sibling or right cousin */
2340static noinline void __init check_spanning_relatives(struct maple_tree *mt)
2341{
2342
2343	unsigned long i, nr_entries = 1000;
2344
2345	for (i = 0; i <= nr_entries; i++)
2346		mtree_store_range(mt, i*10, i*10 + 5,
2347				  xa_mk_value(i), GFP_KERNEL);
2348
2349
2350	mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL);
2351}
2352
2353static noinline void __init check_fuzzer(struct maple_tree *mt)
2354{
2355	/*
2356	 * 1. Causes a spanning rebalance of a single root node.
2357	 * Fixed by setting the correct limit in mast_cp_to_nodes() when the
2358	 * entire right side is consumed.
2359	 */
2360	mtree_test_insert(mt, 88, (void *)0xb1);
2361	mtree_test_insert(mt, 84, (void *)0xa9);
2362	mtree_test_insert(mt, 2,  (void *)0x5);
2363	mtree_test_insert(mt, 4,  (void *)0x9);
2364	mtree_test_insert(mt, 14, (void *)0x1d);
2365	mtree_test_insert(mt, 7,  (void *)0xf);
2366	mtree_test_insert(mt, 12, (void *)0x19);
2367	mtree_test_insert(mt, 18, (void *)0x25);
2368	mtree_test_store_range(mt, 8, 18, (void *)0x11);
2369	mtree_destroy(mt);
2370
2371
2372	/*
2373	 * 2. Cause a spanning rebalance of two nodes in root.
2374	 * Fixed by setting mast->r->max correctly.
2375	 */
2376	mt_init_flags(mt, 0);
2377	mtree_test_store(mt, 87, (void *)0xaf);
2378	mtree_test_store(mt, 0, (void *)0x1);
2379	mtree_test_load(mt, 4);
2380	mtree_test_insert(mt, 4, (void *)0x9);
2381	mtree_test_store(mt, 8, (void *)0x11);
2382	mtree_test_store(mt, 44, (void *)0x59);
2383	mtree_test_store(mt, 68, (void *)0x89);
2384	mtree_test_store(mt, 2, (void *)0x5);
2385	mtree_test_insert(mt, 43, (void *)0x57);
2386	mtree_test_insert(mt, 24, (void *)0x31);
2387	mtree_test_insert(mt, 844, (void *)0x699);
2388	mtree_test_store(mt, 84, (void *)0xa9);
2389	mtree_test_store(mt, 4, (void *)0x9);
2390	mtree_test_erase(mt, 4);
2391	mtree_test_load(mt, 5);
2392	mtree_test_erase(mt, 0);
2393	mtree_destroy(mt);
2394
2395	/*
2396	 * 3. Cause a node overflow on copy
2397	 * Fixed by using the correct check for node size in mas_wr_modify()
2398	 * Also discovered issue with metadata setting.
2399	 */
2400	mt_init_flags(mt, 0);
2401	mtree_test_store_range(mt, 0, ULONG_MAX, (void *)0x1);
2402	mtree_test_store(mt, 4, (void *)0x9);
2403	mtree_test_erase(mt, 5);
2404	mtree_test_erase(mt, 0);
2405	mtree_test_erase(mt, 4);
2406	mtree_test_store(mt, 5, (void *)0xb);
2407	mtree_test_erase(mt, 5);
2408	mtree_test_store(mt, 5, (void *)0xb);
2409	mtree_test_erase(mt, 5);
2410	mtree_test_erase(mt, 4);
2411	mtree_test_store(mt, 4, (void *)0x9);
2412	mtree_test_store(mt, 444, (void *)0x379);
2413	mtree_test_store(mt, 0, (void *)0x1);
2414	mtree_test_load(mt, 0);
2415	mtree_test_store(mt, 5, (void *)0xb);
2416	mtree_test_erase(mt, 0);
2417	mtree_destroy(mt);
2418
2419	/*
2420	 * 4. spanning store failure due to writing incorrect pivot value at
2421	 * last slot.
2422	 * Fixed by setting mast->r->max correctly in mast_cp_to_nodes()
2423	 *
2424	 */
2425	mt_init_flags(mt, 0);
2426	mtree_test_insert(mt, 261, (void *)0x20b);
2427	mtree_test_store(mt, 516, (void *)0x409);
2428	mtree_test_store(mt, 6, (void *)0xd);
2429	mtree_test_insert(mt, 5, (void *)0xb);
2430	mtree_test_insert(mt, 1256, (void *)0x9d1);
2431	mtree_test_store(mt, 4, (void *)0x9);
2432	mtree_test_erase(mt, 1);
2433	mtree_test_store(mt, 56, (void *)0x71);
2434	mtree_test_insert(mt, 1, (void *)0x3);
2435	mtree_test_store(mt, 24, (void *)0x31);
2436	mtree_test_erase(mt, 1);
2437	mtree_test_insert(mt, 2263, (void *)0x11af);
2438	mtree_test_insert(mt, 446, (void *)0x37d);
2439	mtree_test_store_range(mt, 6, 45, (void *)0xd);
2440	mtree_test_store_range(mt, 3, 446, (void *)0x7);
2441	mtree_destroy(mt);
2442
2443	/*
2444	 * 5. mas_wr_extend_null() may overflow slots.
2445	 * Fix by checking against wr_mas->node_end.
2446	 */
2447	mt_init_flags(mt, 0);
2448	mtree_test_store(mt, 48, (void *)0x61);
2449	mtree_test_store(mt, 3, (void *)0x7);
2450	mtree_test_load(mt, 0);
2451	mtree_test_store(mt, 88, (void *)0xb1);
2452	mtree_test_store(mt, 81, (void *)0xa3);
2453	mtree_test_insert(mt, 0, (void *)0x1);
2454	mtree_test_insert(mt, 8, (void *)0x11);
2455	mtree_test_insert(mt, 4, (void *)0x9);
2456	mtree_test_insert(mt, 2480, (void *)0x1361);
2457	mtree_test_insert(mt, ULONG_MAX,
2458			  (void *)0xffffffffffffffff);
2459	mtree_test_erase(mt, ULONG_MAX);
2460	mtree_destroy(mt);
2461
2462	/*
2463	 * 6.  When reusing a node with an implied pivot and the node is
2464	 * shrinking, old data would be left in the implied slot
2465	 * Fixed by checking the last pivot for the mas->max and clear
2466	 * accordingly.  This only affected the left-most node as that node is
2467	 * the only one allowed to end in NULL.
2468	 */
2469	mt_init_flags(mt, 0);
2470	mtree_test_erase(mt, 3);
2471	mtree_test_insert(mt, 22, (void *)0x2d);
2472	mtree_test_insert(mt, 15, (void *)0x1f);
2473	mtree_test_load(mt, 2);
2474	mtree_test_insert(mt, 1, (void *)0x3);
2475	mtree_test_insert(mt, 1, (void *)0x3);
2476	mtree_test_insert(mt, 5, (void *)0xb);
2477	mtree_test_erase(mt, 1);
2478	mtree_test_insert(mt, 1, (void *)0x3);
2479	mtree_test_insert(mt, 4, (void *)0x9);
2480	mtree_test_insert(mt, 1, (void *)0x3);
2481	mtree_test_erase(mt, 1);
2482	mtree_test_insert(mt, 2, (void *)0x5);
2483	mtree_test_insert(mt, 1, (void *)0x3);
2484	mtree_test_erase(mt, 3);
2485	mtree_test_insert(mt, 22, (void *)0x2d);
2486	mtree_test_insert(mt, 15, (void *)0x1f);
2487	mtree_test_insert(mt, 2, (void *)0x5);
2488	mtree_test_insert(mt, 1, (void *)0x3);
2489	mtree_test_insert(mt, 8, (void *)0x11);
2490	mtree_test_load(mt, 2);
2491	mtree_test_insert(mt, 1, (void *)0x3);
2492	mtree_test_insert(mt, 1, (void *)0x3);
2493	mtree_test_store(mt, 1, (void *)0x3);
2494	mtree_test_insert(mt, 5, (void *)0xb);
2495	mtree_test_erase(mt, 1);
2496	mtree_test_insert(mt, 1, (void *)0x3);
2497	mtree_test_insert(mt, 4, (void *)0x9);
2498	mtree_test_insert(mt, 1, (void *)0x3);
2499	mtree_test_erase(mt, 1);
2500	mtree_test_insert(mt, 2, (void *)0x5);
2501	mtree_test_insert(mt, 1, (void *)0x3);
2502	mtree_test_erase(mt, 3);
2503	mtree_test_insert(mt, 22, (void *)0x2d);
2504	mtree_test_insert(mt, 15, (void *)0x1f);
2505	mtree_test_insert(mt, 2, (void *)0x5);
2506	mtree_test_insert(mt, 1, (void *)0x3);
2507	mtree_test_insert(mt, 8, (void *)0x11);
2508	mtree_test_insert(mt, 12, (void *)0x19);
2509	mtree_test_erase(mt, 1);
2510	mtree_test_store_range(mt, 4, 62, (void *)0x9);
2511	mtree_test_erase(mt, 62);
2512	mtree_test_store_range(mt, 1, 0, (void *)0x3);
2513	mtree_test_insert(mt, 11, (void *)0x17);
2514	mtree_test_insert(mt, 3, (void *)0x7);
2515	mtree_test_insert(mt, 3, (void *)0x7);
2516	mtree_test_store(mt, 62, (void *)0x7d);
2517	mtree_test_erase(mt, 62);
2518	mtree_test_store_range(mt, 1, 15, (void *)0x3);
2519	mtree_test_erase(mt, 1);
2520	mtree_test_insert(mt, 22, (void *)0x2d);
2521	mtree_test_insert(mt, 12, (void *)0x19);
2522	mtree_test_erase(mt, 1);
2523	mtree_test_insert(mt, 3, (void *)0x7);
2524	mtree_test_store(mt, 62, (void *)0x7d);
2525	mtree_test_erase(mt, 62);
2526	mtree_test_insert(mt, 122, (void *)0xf5);
2527	mtree_test_store(mt, 3, (void *)0x7);
2528	mtree_test_insert(mt, 0, (void *)0x1);
2529	mtree_test_store_range(mt, 0, 1, (void *)0x1);
2530	mtree_test_insert(mt, 85, (void *)0xab);
2531	mtree_test_insert(mt, 72, (void *)0x91);
2532	mtree_test_insert(mt, 81, (void *)0xa3);
2533	mtree_test_insert(mt, 726, (void *)0x5ad);
2534	mtree_test_insert(mt, 0, (void *)0x1);
2535	mtree_test_insert(mt, 1, (void *)0x3);
2536	mtree_test_store(mt, 51, (void *)0x67);
2537	mtree_test_insert(mt, 611, (void *)0x4c7);
2538	mtree_test_insert(mt, 485, (void *)0x3cb);
2539	mtree_test_insert(mt, 1, (void *)0x3);
2540	mtree_test_erase(mt, 1);
2541	mtree_test_insert(mt, 0, (void *)0x1);
2542	mtree_test_insert(mt, 1, (void *)0x3);
2543	mtree_test_insert_range(mt, 26, 1, (void *)0x35);
2544	mtree_test_load(mt, 1);
2545	mtree_test_store_range(mt, 1, 22, (void *)0x3);
2546	mtree_test_insert(mt, 1, (void *)0x3);
2547	mtree_test_erase(mt, 1);
2548	mtree_test_load(mt, 53);
2549	mtree_test_load(mt, 1);
2550	mtree_test_store_range(mt, 1, 1, (void *)0x3);
2551	mtree_test_insert(mt, 222, (void *)0x1bd);
2552	mtree_test_insert(mt, 485, (void *)0x3cb);
2553	mtree_test_insert(mt, 1, (void *)0x3);
2554	mtree_test_erase(mt, 1);
2555	mtree_test_load(mt, 0);
2556	mtree_test_insert(mt, 21, (void *)0x2b);
2557	mtree_test_insert(mt, 3, (void *)0x7);
2558	mtree_test_store(mt, 621, (void *)0x4db);
2559	mtree_test_insert(mt, 0, (void *)0x1);
2560	mtree_test_erase(mt, 5);
2561	mtree_test_insert(mt, 1, (void *)0x3);
2562	mtree_test_store(mt, 62, (void *)0x7d);
2563	mtree_test_erase(mt, 62);
2564	mtree_test_store_range(mt, 1, 0, (void *)0x3);
2565	mtree_test_insert(mt, 22, (void *)0x2d);
2566	mtree_test_insert(mt, 12, (void *)0x19);
2567	mtree_test_erase(mt, 1);
2568	mtree_test_insert(mt, 1, (void *)0x3);
2569	mtree_test_store_range(mt, 4, 62, (void *)0x9);
2570	mtree_test_erase(mt, 62);
2571	mtree_test_erase(mt, 1);
2572	mtree_test_load(mt, 1);
2573	mtree_test_store_range(mt, 1, 22, (void *)0x3);
2574	mtree_test_insert(mt, 1, (void *)0x3);
2575	mtree_test_erase(mt, 1);
2576	mtree_test_load(mt, 53);
2577	mtree_test_load(mt, 1);
2578	mtree_test_store_range(mt, 1, 1, (void *)0x3);
2579	mtree_test_insert(mt, 222, (void *)0x1bd);
2580	mtree_test_insert(mt, 485, (void *)0x3cb);
2581	mtree_test_insert(mt, 1, (void *)0x3);
2582	mtree_test_erase(mt, 1);
2583	mtree_test_insert(mt, 1, (void *)0x3);
2584	mtree_test_load(mt, 0);
2585	mtree_test_load(mt, 0);
2586	mtree_destroy(mt);
2587
2588	/*
2589	 * 7. Previous fix was incomplete, fix mas_resuse_node() clearing of old
2590	 * data by overwriting it first - that way metadata is of no concern.
2591	 */
2592	mt_init_flags(mt, 0);
2593	mtree_test_load(mt, 1);
2594	mtree_test_insert(mt, 102, (void *)0xcd);
2595	mtree_test_erase(mt, 2);
2596	mtree_test_erase(mt, 0);
2597	mtree_test_load(mt, 0);
2598	mtree_test_insert(mt, 4, (void *)0x9);
2599	mtree_test_insert(mt, 2, (void *)0x5);
2600	mtree_test_insert(mt, 110, (void *)0xdd);
2601	mtree_test_insert(mt, 1, (void *)0x3);
2602	mtree_test_insert_range(mt, 5, 0, (void *)0xb);
2603	mtree_test_erase(mt, 2);
2604	mtree_test_store(mt, 0, (void *)0x1);
2605	mtree_test_store(mt, 112, (void *)0xe1);
2606	mtree_test_insert(mt, 21, (void *)0x2b);
2607	mtree_test_store(mt, 1, (void *)0x3);
2608	mtree_test_insert_range(mt, 110, 2, (void *)0xdd);
2609	mtree_test_store(mt, 2, (void *)0x5);
2610	mtree_test_load(mt, 22);
2611	mtree_test_erase(mt, 2);
2612	mtree_test_store(mt, 210, (void *)0x1a5);
2613	mtree_test_store_range(mt, 0, 2, (void *)0x1);
2614	mtree_test_store(mt, 2, (void *)0x5);
2615	mtree_test_erase(mt, 2);
2616	mtree_test_erase(mt, 22);
2617	mtree_test_erase(mt, 1);
2618	mtree_test_erase(mt, 2);
2619	mtree_test_store(mt, 0, (void *)0x1);
2620	mtree_test_load(mt, 112);
2621	mtree_test_insert(mt, 2, (void *)0x5);
2622	mtree_test_erase(mt, 2);
2623	mtree_test_store(mt, 1, (void *)0x3);
2624	mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2625	mtree_test_erase(mt, 0);
2626	mtree_test_erase(mt, 2);
2627	mtree_test_store(mt, 2, (void *)0x5);
2628	mtree_test_erase(mt, 0);
2629	mtree_test_erase(mt, 2);
2630	mtree_test_store(mt, 0, (void *)0x1);
2631	mtree_test_store(mt, 0, (void *)0x1);
2632	mtree_test_erase(mt, 2);
2633	mtree_test_store(mt, 2, (void *)0x5);
2634	mtree_test_erase(mt, 2);
2635	mtree_test_insert(mt, 2, (void *)0x5);
2636	mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2637	mtree_test_erase(mt, 0);
2638	mtree_test_erase(mt, 2);
2639	mtree_test_store(mt, 0, (void *)0x1);
2640	mtree_test_load(mt, 112);
2641	mtree_test_store_range(mt, 110, 12, (void *)0xdd);
2642	mtree_test_store(mt, 2, (void *)0x5);
2643	mtree_test_load(mt, 110);
2644	mtree_test_insert_range(mt, 4, 71, (void *)0x9);
2645	mtree_test_load(mt, 2);
2646	mtree_test_store(mt, 2, (void *)0x5);
2647	mtree_test_insert_range(mt, 11, 22, (void *)0x17);
2648	mtree_test_erase(mt, 12);
2649	mtree_test_store(mt, 2, (void *)0x5);
2650	mtree_test_load(mt, 22);
2651	mtree_destroy(mt);
2652
2653
2654	/*
2655	 * 8.  When rebalancing or spanning_rebalance(), the max of the new node
2656	 * may be set incorrectly to the final pivot and not the right max.
2657	 * Fix by setting the left max to orig right max if the entire node is
2658	 * consumed.
2659	 */
2660	mt_init_flags(mt, 0);
2661	mtree_test_store(mt, 6, (void *)0xd);
2662	mtree_test_store(mt, 67, (void *)0x87);
2663	mtree_test_insert(mt, 15, (void *)0x1f);
2664	mtree_test_insert(mt, 6716, (void *)0x3479);
2665	mtree_test_store(mt, 61, (void *)0x7b);
2666	mtree_test_insert(mt, 13, (void *)0x1b);
2667	mtree_test_store(mt, 8, (void *)0x11);
2668	mtree_test_insert(mt, 1, (void *)0x3);
2669	mtree_test_load(mt, 0);
2670	mtree_test_erase(mt, 67167);
2671	mtree_test_insert_range(mt, 6, 7167, (void *)0xd);
2672	mtree_test_insert(mt, 6, (void *)0xd);
2673	mtree_test_erase(mt, 67);
2674	mtree_test_insert(mt, 1, (void *)0x3);
2675	mtree_test_erase(mt, 667167);
2676	mtree_test_insert(mt, 6, (void *)0xd);
2677	mtree_test_store(mt, 67, (void *)0x87);
2678	mtree_test_insert(mt, 5, (void *)0xb);
2679	mtree_test_erase(mt, 1);
2680	mtree_test_insert(mt, 6, (void *)0xd);
2681	mtree_test_erase(mt, 67);
2682	mtree_test_insert(mt, 15, (void *)0x1f);
2683	mtree_test_insert(mt, 67167, (void *)0x20cbf);
2684	mtree_test_insert(mt, 1, (void *)0x3);
2685	mtree_test_load(mt, 7);
2686	mtree_test_insert(mt, 16, (void *)0x21);
2687	mtree_test_insert(mt, 36, (void *)0x49);
2688	mtree_test_store(mt, 67, (void *)0x87);
2689	mtree_test_store(mt, 6, (void *)0xd);
2690	mtree_test_insert(mt, 367, (void *)0x2df);
2691	mtree_test_insert(mt, 115, (void *)0xe7);
2692	mtree_test_store(mt, 0, (void *)0x1);
2693	mtree_test_store_range(mt, 1, 3, (void *)0x3);
2694	mtree_test_store(mt, 1, (void *)0x3);
2695	mtree_test_erase(mt, 67167);
2696	mtree_test_insert_range(mt, 6, 47, (void *)0xd);
2697	mtree_test_store(mt, 1, (void *)0x3);
2698	mtree_test_insert_range(mt, 1, 67, (void *)0x3);
2699	mtree_test_load(mt, 67);
2700	mtree_test_insert(mt, 1, (void *)0x3);
2701	mtree_test_erase(mt, 67167);
2702	mtree_destroy(mt);
2703
2704	/*
2705	 * 9. spanning store to the end of data caused an invalid metadata
2706	 * length which resulted in a crash eventually.
2707	 * Fix by checking if there is a value in pivot before incrementing the
2708	 * metadata end in mab_mas_cp().  To ensure this doesn't happen again,
2709	 * abstract the two locations this happens into a function called
2710	 * mas_leaf_set_meta().
2711	 */
2712	mt_init_flags(mt, 0);
2713	mtree_test_insert(mt, 21, (void *)0x2b);
2714	mtree_test_insert(mt, 12, (void *)0x19);
2715	mtree_test_insert(mt, 6, (void *)0xd);
2716	mtree_test_insert(mt, 8, (void *)0x11);
2717	mtree_test_insert(mt, 2, (void *)0x5);
2718	mtree_test_insert(mt, 91, (void *)0xb7);
2719	mtree_test_insert(mt, 18, (void *)0x25);
2720	mtree_test_insert(mt, 81, (void *)0xa3);
2721	mtree_test_store_range(mt, 0, 128, (void *)0x1);
2722	mtree_test_store(mt, 1, (void *)0x3);
2723	mtree_test_erase(mt, 8);
2724	mtree_test_insert(mt, 11, (void *)0x17);
2725	mtree_test_insert(mt, 8, (void *)0x11);
2726	mtree_test_insert(mt, 21, (void *)0x2b);
2727	mtree_test_insert(mt, 2, (void *)0x5);
2728	mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2729	mtree_test_erase(mt, ULONG_MAX - 10);
2730	mtree_test_store_range(mt, 0, 281, (void *)0x1);
2731	mtree_test_erase(mt, 2);
2732	mtree_test_insert(mt, 1211, (void *)0x977);
2733	mtree_test_insert(mt, 111, (void *)0xdf);
2734	mtree_test_insert(mt, 13, (void *)0x1b);
2735	mtree_test_insert(mt, 211, (void *)0x1a7);
2736	mtree_test_insert(mt, 11, (void *)0x17);
2737	mtree_test_insert(mt, 5, (void *)0xb);
2738	mtree_test_insert(mt, 1218, (void *)0x985);
2739	mtree_test_insert(mt, 61, (void *)0x7b);
2740	mtree_test_store(mt, 1, (void *)0x3);
2741	mtree_test_insert(mt, 121, (void *)0xf3);
2742	mtree_test_insert(mt, 8, (void *)0x11);
2743	mtree_test_insert(mt, 21, (void *)0x2b);
2744	mtree_test_insert(mt, 2, (void *)0x5);
2745	mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2746	mtree_test_erase(mt, ULONG_MAX - 10);
2747}
2748
2749static noinline void __init check_bnode_min_spanning(struct maple_tree *mt)
2750{
2751	int i = 50;
2752	MA_STATE(mas, mt, 0, 0);
2753
2754	mt_set_non_kernel(9999);
2755	mas_lock(&mas);
2756	do {
2757		mas_set_range(&mas, i*10, i*10+9);
2758		mas_store(&mas, check_bnode_min_spanning);
2759	} while (i--);
2760
2761	mas_set_range(&mas, 240, 509);
2762	mas_store(&mas, NULL);
2763	mas_unlock(&mas);
2764	mas_destroy(&mas);
2765	mt_set_non_kernel(0);
2766}
2767
2768static noinline void __init check_empty_area_window(struct maple_tree *mt)
2769{
2770	unsigned long i, nr_entries = 20;
2771	MA_STATE(mas, mt, 0, 0);
2772
2773	for (i = 1; i <= nr_entries; i++)
2774		mtree_store_range(mt, i*10, i*10 + 9,
2775				  xa_mk_value(i), GFP_KERNEL);
2776
2777	/* Create another hole besides the one at 0 */
2778	mtree_store_range(mt, 160, 169, NULL, GFP_KERNEL);
2779
2780	/* Check lower bounds that don't fit */
2781	rcu_read_lock();
2782	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 10) != -EBUSY);
2783
2784	mas_reset(&mas);
2785	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 6, 90, 5) != -EBUSY);
2786
2787	/* Check lower bound that does fit */
2788	mas_reset(&mas);
2789	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 5) != 0);
2790	MT_BUG_ON(mt, mas.index != 5);
2791	MT_BUG_ON(mt, mas.last != 9);
2792	rcu_read_unlock();
2793
2794	/* Check one gap that doesn't fit and one that does */
2795	rcu_read_lock();
2796	mas_reset(&mas);
2797	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 217, 9) != 0);
2798	MT_BUG_ON(mt, mas.index != 161);
2799	MT_BUG_ON(mt, mas.last != 169);
2800
2801	/* Check one gap that does fit above the min */
2802	mas_reset(&mas);
2803	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 3) != 0);
2804	MT_BUG_ON(mt, mas.index != 216);
2805	MT_BUG_ON(mt, mas.last != 218);
2806
2807	/* Check size that doesn't fit any gap */
2808	mas_reset(&mas);
2809	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 16) != -EBUSY);
2810
2811	/*
2812	 * Check size that doesn't fit the lower end of the window but
2813	 * does fit the gap
2814	 */
2815	mas_reset(&mas);
2816	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 167, 200, 4) != -EBUSY);
2817
2818	/*
2819	 * Check size that doesn't fit the upper end of the window but
2820	 * does fit the gap
2821	 */
2822	mas_reset(&mas);
2823	MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 162, 4) != -EBUSY);
2824
2825	/* Check mas_empty_area forward */
2826	mas_reset(&mas);
2827	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 9) != 0);
2828	MT_BUG_ON(mt, mas.index != 0);
2829	MT_BUG_ON(mt, mas.last != 8);
2830
2831	mas_reset(&mas);
2832	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 4) != 0);
2833	MT_BUG_ON(mt, mas.index != 0);
2834	MT_BUG_ON(mt, mas.last != 3);
2835
2836	mas_reset(&mas);
2837	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 11) != -EBUSY);
2838
2839	mas_reset(&mas);
2840	MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY);
2841
2842	mas_reset(&mas);
2843	MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EINVAL);
2844
2845	mas_reset(&mas);
2846	mas_empty_area(&mas, 100, 165, 3);
2847
2848	mas_reset(&mas);
2849	MT_BUG_ON(mt, mas_empty_area(&mas, 100, 163, 6) != -EBUSY);
2850	rcu_read_unlock();
2851}
2852
2853static noinline void __init check_empty_area_fill(struct maple_tree *mt)
2854{
2855	const unsigned long max = 0x25D78000;
2856	unsigned long size;
2857	int loop, shift;
2858	MA_STATE(mas, mt, 0, 0);
2859
2860	mt_set_non_kernel(99999);
2861	for (shift = 12; shift <= 16; shift++) {
2862		loop = 5000;
2863		size = 1 << shift;
2864		while (loop--) {
2865			mas_set(&mas, 0);
2866			mas_lock(&mas);
2867			MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != 0);
2868			MT_BUG_ON(mt, mas.last != mas.index + size - 1);
2869			mas_store_gfp(&mas, (void *)size, GFP_KERNEL);
2870			mas_unlock(&mas);
2871			mas_reset(&mas);
2872		}
2873	}
2874
2875	/* No space left. */
2876	size = 0x1000;
2877	rcu_read_lock();
2878	MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != -EBUSY);
2879	rcu_read_unlock();
2880
2881	/* Fill a depth 3 node to the maximum */
2882	for (unsigned long i = 629440511; i <= 629440800; i += 6)
2883		mtree_store_range(mt, i, i + 5, (void *)i, GFP_KERNEL);
2884	/* Make space in the second-last depth 4 node */
2885	mtree_erase(mt, 631668735);
2886	/* Make space in the last depth 4 node */
2887	mtree_erase(mt, 629506047);
2888	mas_reset(&mas);
2889	/* Search from just after the gap in the second-last depth 4 */
2890	rcu_read_lock();
2891	MT_BUG_ON(mt, mas_empty_area(&mas, 629506048, 690000000, 0x5000) != 0);
2892	rcu_read_unlock();
2893	mt_set_non_kernel(0);
2894}
2895
2896/*
2897 * Check MAS_START, MAS_PAUSE, active (implied), and MAS_NONE transitions.
2898 *
2899 * The table below shows the single entry tree (0-0 pointer) and normal tree
2900 * with nodes.
2901 *
2902 * Function	ENTRY	Start		Result		index & last
2903 *     ┬          ┬       ┬               ┬                ┬
2904 *     │          │       │               │                └─ the final range
2905 *     │          │       │               └─ The node value after execution
2906 *     │          │       └─ The node value before execution
2907 *     │          └─ If the entry exists or does not exists (DNE)
2908 *     └─ The function name
2909 *
2910 * Function	ENTRY	Start		Result		index & last
2911 * mas_next()
2912 *  - after last
2913 *			Single entry tree at 0-0
2914 *			------------------------
2915 *		DNE	MAS_START	MAS_NONE	1 - oo
2916 *		DNE	MAS_PAUSE	MAS_NONE	1 - oo
2917 *		DNE	MAS_ROOT	MAS_NONE	1 - oo
2918 *			when index = 0
2919 *		DNE	MAS_NONE	MAS_ROOT	0
2920 *			when index > 0
2921 *		DNE	MAS_NONE	MAS_NONE	1 - oo
2922 *
2923 *			Normal tree
2924 *			-----------
2925 *		exists	MAS_START	active		range
2926 *		DNE	MAS_START	active		set to last range
2927 *		exists	MAS_PAUSE	active		range
2928 *		DNE	MAS_PAUSE	active		set to last range
2929 *		exists	MAS_NONE	active		range
2930 *		exists	active		active		range
2931 *		DNE	active		active		set to last range
2932 *		ERANGE	active		MAS_OVERFLOW	last range
2933 *
2934 * Function	ENTRY	Start		Result		index & last
2935 * mas_prev()
2936 * - before index
2937 *			Single entry tree at 0-0
2938 *			------------------------
2939 *				if index > 0
2940 *		exists	MAS_START	MAS_ROOT	0
2941 *		exists	MAS_PAUSE	MAS_ROOT	0
2942 *		exists	MAS_NONE	MAS_ROOT	0
2943 *
2944 *				if index == 0
2945 *		DNE	MAS_START	MAS_NONE	0
2946 *		DNE	MAS_PAUSE	MAS_NONE	0
2947 *		DNE	MAS_NONE	MAS_NONE	0
2948 *		DNE	MAS_ROOT	MAS_NONE	0
2949 *
2950 *			Normal tree
2951 *			-----------
2952 *		exists	MAS_START	active		range
2953 *		DNE	MAS_START	active		set to min
2954 *		exists	MAS_PAUSE	active		range
2955 *		DNE	MAS_PAUSE	active		set to min
2956 *		exists	MAS_NONE	active		range
2957 *		DNE	MAS_NONE	MAS_NONE	set to min
2958 *		any	MAS_ROOT	MAS_NONE	0
2959 *		exists	active		active		range
2960 *		DNE	active		active		last range
2961 *		ERANGE	active		MAS_UNDERFLOW	last range
2962 *
2963 * Function	ENTRY	Start		Result		index & last
2964 * mas_find()
2965 *  - at index or next
2966 *			Single entry tree at 0-0
2967 *			------------------------
2968 *				if index >  0
2969 *		DNE	MAS_START	MAS_NONE	0
2970 *		DNE	MAS_PAUSE	MAS_NONE	0
2971 *		DNE	MAS_ROOT	MAS_NONE	0
2972 *		DNE	MAS_NONE	MAS_NONE	1
2973 *				if index ==  0
2974 *		exists	MAS_START	MAS_ROOT	0
2975 *		exists	MAS_PAUSE	MAS_ROOT	0
2976 *		exists	MAS_NONE	MAS_ROOT	0
2977 *
2978 *			Normal tree
2979 *			-----------
2980 *		exists	MAS_START	active		range
2981 *		DNE	MAS_START	active		set to max
2982 *		exists	MAS_PAUSE	active		range
2983 *		DNE	MAS_PAUSE	active		set to max
2984 *		exists	MAS_NONE	active		range (start at last)
2985 *		exists	active		active		range
2986 *		DNE	active		active		last range (max < last)
2987 *
2988 * Function	ENTRY	Start		Result		index & last
2989 * mas_find_rev()
2990 *  - at index or before
2991 *			Single entry tree at 0-0
2992 *			------------------------
2993 *				if index >  0
2994 *		exists	MAS_START	MAS_ROOT	0
2995 *		exists	MAS_PAUSE	MAS_ROOT	0
2996 *		exists	MAS_NONE	MAS_ROOT	0
2997 *				if index ==  0
2998 *		DNE	MAS_START	MAS_NONE	0
2999 *		DNE	MAS_PAUSE	MAS_NONE	0
3000 *		DNE	MAS_NONE	MAS_NONE	0
3001 *		DNE	MAS_ROOT	MAS_NONE	0
3002 *
3003 *			Normal tree
3004 *			-----------
3005 *		exists	MAS_START	active		range
3006 *		DNE	MAS_START	active		set to min
3007 *		exists	MAS_PAUSE	active		range
3008 *		DNE	MAS_PAUSE	active		set to min
3009 *		exists	MAS_NONE	active		range (start at index)
3010 *		exists	active		active		range
3011 *		DNE	active		active		last range (min > index)
3012 *
3013 * Function	ENTRY	Start		Result		index & last
3014 * mas_walk()
3015 * - Look up index
3016 *			Single entry tree at 0-0
3017 *			------------------------
3018 *				if index >  0
3019 *		DNE	MAS_START	MAS_ROOT	1 - oo
3020 *		DNE	MAS_PAUSE	MAS_ROOT	1 - oo
3021 *		DNE	MAS_NONE	MAS_ROOT	1 - oo
3022 *		DNE	MAS_ROOT	MAS_ROOT	1 - oo
3023 *				if index ==  0
3024 *		exists	MAS_START	MAS_ROOT	0
3025 *		exists	MAS_PAUSE	MAS_ROOT	0
3026 *		exists	MAS_NONE	MAS_ROOT	0
3027 *		exists	MAS_ROOT	MAS_ROOT	0
3028 *
3029 *			Normal tree
3030 *			-----------
3031 *		exists	MAS_START	active		range
3032 *		DNE	MAS_START	active		range of NULL
3033 *		exists	MAS_PAUSE	active		range
3034 *		DNE	MAS_PAUSE	active		range of NULL
3035 *		exists	MAS_NONE	active		range
3036 *		DNE	MAS_NONE	active		range of NULL
3037 *		exists	active		active		range
3038 *		DNE	active		active		range of NULL
3039 */
3040
3041static noinline void __init check_state_handling(struct maple_tree *mt)
3042{
3043	MA_STATE(mas, mt, 0, 0);
3044	void *entry, *ptr = (void *) 0x1234500;
3045	void *ptr2 = &ptr;
3046	void *ptr3 = &ptr2;
3047	unsigned long index;
3048
3049	/* Check MAS_ROOT First */
3050	mtree_store_range(mt, 0, 0, ptr, GFP_KERNEL);
3051
3052	mas_lock(&mas);
3053	/* prev: Start -> underflow*/
3054	entry = mas_prev(&mas, 0);
3055	MT_BUG_ON(mt, entry != NULL);
3056	MT_BUG_ON(mt, mas.status != ma_underflow);
3057
3058	/* prev: Start -> root */
3059	mas_set(&mas, 10);
3060	entry = mas_prev(&mas, 0);
3061	MT_BUG_ON(mt, entry != ptr);
3062	MT_BUG_ON(mt, mas.index != 0);
3063	MT_BUG_ON(mt, mas.last != 0);
3064	MT_BUG_ON(mt, mas.status != ma_root);
3065
3066	/* prev: pause -> root */
3067	mas_set(&mas, 10);
3068	mas_pause(&mas);
3069	entry = mas_prev(&mas, 0);
3070	MT_BUG_ON(mt, entry != ptr);
3071	MT_BUG_ON(mt, mas.index != 0);
3072	MT_BUG_ON(mt, mas.last != 0);
3073	MT_BUG_ON(mt, mas.status != ma_root);
3074
3075	/* next: start -> none */
3076	mas_set(&mas, 0);
3077	entry = mas_next(&mas, ULONG_MAX);
3078	MT_BUG_ON(mt, mas.index != 1);
3079	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3080	MT_BUG_ON(mt, entry != NULL);
3081	MT_BUG_ON(mt, mas.status != ma_none);
3082
3083	/* next: start -> none*/
3084	mas_set(&mas, 10);
3085	entry = mas_next(&mas, ULONG_MAX);
3086	MT_BUG_ON(mt, mas.index != 1);
3087	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3088	MT_BUG_ON(mt, entry != NULL);
3089	MT_BUG_ON(mt, mas.status != ma_none);
3090
3091	/* find: start -> root */
3092	mas_set(&mas, 0);
3093	entry = mas_find(&mas, ULONG_MAX);
3094	MT_BUG_ON(mt, entry != ptr);
3095	MT_BUG_ON(mt, mas.index != 0);
3096	MT_BUG_ON(mt, mas.last != 0);
3097	MT_BUG_ON(mt, mas.status != ma_root);
3098
3099	/* find: root -> none */
3100	entry = mas_find(&mas, ULONG_MAX);
3101	MT_BUG_ON(mt, entry != NULL);
3102	MT_BUG_ON(mt, mas.index != 1);
3103	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3104	MT_BUG_ON(mt, mas.status != ma_none);
3105
3106	/* find: none -> none */
3107	entry = mas_find(&mas, ULONG_MAX);
3108	MT_BUG_ON(mt, entry != NULL);
3109	MT_BUG_ON(mt, mas.index != 1);
3110	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3111	MT_BUG_ON(mt, mas.status != ma_none);
3112
3113	/* find: start -> none */
3114	mas_set(&mas, 10);
3115	entry = mas_find(&mas, ULONG_MAX);
3116	MT_BUG_ON(mt, entry != NULL);
3117	MT_BUG_ON(mt, mas.index != 1);
3118	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3119	MT_BUG_ON(mt, mas.status != ma_none);
3120
3121	/* find_rev: none -> root */
3122	entry = mas_find_rev(&mas, 0);
3123	MT_BUG_ON(mt, entry != ptr);
3124	MT_BUG_ON(mt, mas.index != 0);
3125	MT_BUG_ON(mt, mas.last != 0);
3126	MT_BUG_ON(mt, mas.status != ma_root);
3127
3128	/* find_rev: start -> root */
3129	mas_set(&mas, 0);
3130	entry = mas_find_rev(&mas, 0);
3131	MT_BUG_ON(mt, entry != ptr);
3132	MT_BUG_ON(mt, mas.index != 0);
3133	MT_BUG_ON(mt, mas.last != 0);
3134	MT_BUG_ON(mt, mas.status != ma_root);
3135
3136	/* find_rev: root -> none */
3137	entry = mas_find_rev(&mas, 0);
3138	MT_BUG_ON(mt, entry != NULL);
3139	MT_BUG_ON(mt, mas.index != 0);
3140	MT_BUG_ON(mt, mas.last != 0);
3141	MT_BUG_ON(mt, mas.status != ma_none);
3142
3143	/* find_rev: none -> none */
3144	entry = mas_find_rev(&mas, 0);
3145	MT_BUG_ON(mt, entry != NULL);
3146	MT_BUG_ON(mt, mas.index != 0);
3147	MT_BUG_ON(mt, mas.last != 0);
3148	MT_BUG_ON(mt, mas.status != ma_none);
3149
3150	/* find_rev: start -> root */
3151	mas_set(&mas, 10);
3152	entry = mas_find_rev(&mas, 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	/* walk: start -> none */
3159	mas_set(&mas, 10);
3160	entry = mas_walk(&mas);
3161	MT_BUG_ON(mt, entry != NULL);
3162	MT_BUG_ON(mt, mas.index != 1);
3163	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3164	MT_BUG_ON(mt, mas.status != ma_none);
3165
3166	/* walk: pause -> none*/
3167	mas_set(&mas, 10);
3168	mas_pause(&mas);
3169	entry = mas_walk(&mas);
3170	MT_BUG_ON(mt, entry != NULL);
3171	MT_BUG_ON(mt, mas.index != 1);
3172	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3173	MT_BUG_ON(mt, mas.status != ma_none);
3174
3175	/* walk: none -> none */
3176	mas.index = mas.last = 10;
3177	entry = mas_walk(&mas);
3178	MT_BUG_ON(mt, entry != NULL);
3179	MT_BUG_ON(mt, mas.index != 1);
3180	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3181	MT_BUG_ON(mt, mas.status != ma_none);
3182
3183	/* walk: none -> none */
3184	entry = mas_walk(&mas);
3185	MT_BUG_ON(mt, entry != NULL);
3186	MT_BUG_ON(mt, mas.index != 1);
3187	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3188	MT_BUG_ON(mt, mas.status != ma_none);
3189
3190	/* walk: start -> root */
3191	mas_set(&mas, 0);
3192	entry = mas_walk(&mas);
3193	MT_BUG_ON(mt, entry != ptr);
3194	MT_BUG_ON(mt, mas.index != 0);
3195	MT_BUG_ON(mt, mas.last != 0);
3196	MT_BUG_ON(mt, mas.status != ma_root);
3197
3198	/* walk: pause -> root */
3199	mas_set(&mas, 0);
3200	mas_pause(&mas);
3201	entry = mas_walk(&mas);
3202	MT_BUG_ON(mt, entry != ptr);
3203	MT_BUG_ON(mt, mas.index != 0);
3204	MT_BUG_ON(mt, mas.last != 0);
3205	MT_BUG_ON(mt, mas.status != ma_root);
3206
3207	/* walk: none -> root */
3208	mas.status = ma_none;
3209	entry = mas_walk(&mas);
3210	MT_BUG_ON(mt, entry != ptr);
3211	MT_BUG_ON(mt, mas.index != 0);
3212	MT_BUG_ON(mt, mas.last != 0);
3213	MT_BUG_ON(mt, mas.status != ma_root);
3214
3215	/* walk: root -> root */
3216	entry = mas_walk(&mas);
3217	MT_BUG_ON(mt, entry != ptr);
3218	MT_BUG_ON(mt, mas.index != 0);
3219	MT_BUG_ON(mt, mas.last != 0);
3220	MT_BUG_ON(mt, mas.status != ma_root);
3221
3222	/* walk: root -> none */
3223	mas_set(&mas, 10);
3224	entry = mas_walk(&mas);
3225	MT_BUG_ON(mt, entry != NULL);
3226	MT_BUG_ON(mt, mas.index != 1);
3227	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3228	MT_BUG_ON(mt, mas.status != ma_none);
3229
3230	/* walk: none -> root */
3231	mas.index = mas.last = 0;
3232	entry = mas_walk(&mas);
3233	MT_BUG_ON(mt, entry != ptr);
3234	MT_BUG_ON(mt, mas.index != 0);
3235	MT_BUG_ON(mt, mas.last != 0);
3236	MT_BUG_ON(mt, mas.status != ma_root);
3237
3238	mas_unlock(&mas);
3239
3240	/* Check when there is an actual node */
3241	mtree_store_range(mt, 0, 0, NULL, GFP_KERNEL);
3242	mtree_store_range(mt, 0x1000, 0x1500, ptr, GFP_KERNEL);
3243	mtree_store_range(mt, 0x2000, 0x2500, ptr2, GFP_KERNEL);
3244	mtree_store_range(mt, 0x3000, 0x3500, ptr3, GFP_KERNEL);
3245
3246	mas_lock(&mas);
3247
3248	/* next: start ->active */
3249	mas_set(&mas, 0);
3250	entry = mas_next(&mas, ULONG_MAX);
3251	MT_BUG_ON(mt, entry != ptr);
3252	MT_BUG_ON(mt, mas.index != 0x1000);
3253	MT_BUG_ON(mt, mas.last != 0x1500);
3254	MT_BUG_ON(mt, !mas_is_active(&mas));
3255
3256	/* next: pause ->active */
3257	mas_set(&mas, 0);
3258	mas_pause(&mas);
3259	entry = mas_next(&mas, ULONG_MAX);
3260	MT_BUG_ON(mt, entry != ptr);
3261	MT_BUG_ON(mt, mas.index != 0x1000);
3262	MT_BUG_ON(mt, mas.last != 0x1500);
3263	MT_BUG_ON(mt, !mas_is_active(&mas));
3264
3265	/* next: none ->active */
3266	mas.index = mas.last = 0;
3267	mas.offset = 0;
3268	mas.status = ma_none;
3269	entry = mas_next(&mas, ULONG_MAX);
3270	MT_BUG_ON(mt, entry != ptr);
3271	MT_BUG_ON(mt, mas.index != 0x1000);
3272	MT_BUG_ON(mt, mas.last != 0x1500);
3273	MT_BUG_ON(mt, !mas_is_active(&mas));
3274
3275	/* next:active ->active (spanning limit) */
3276	entry = mas_next(&mas, 0x2100);
3277	MT_BUG_ON(mt, entry != ptr2);
3278	MT_BUG_ON(mt, mas.index != 0x2000);
3279	MT_BUG_ON(mt, mas.last != 0x2500);
3280	MT_BUG_ON(mt, !mas_is_active(&mas));
3281
3282	/* next:active -> overflow (limit reached) beyond data */
3283	entry = mas_next(&mas, 0x2999);
3284	MT_BUG_ON(mt, entry != NULL);
3285	MT_BUG_ON(mt, mas.index != 0x2501);
3286	MT_BUG_ON(mt, mas.last != 0x2fff);
3287	MT_BUG_ON(mt, !mas_is_overflow(&mas));
3288
3289	/* next:overflow -> active (limit changed) */
3290	entry = mas_next(&mas, ULONG_MAX);
3291	MT_BUG_ON(mt, entry != ptr3);
3292	MT_BUG_ON(mt, mas.index != 0x3000);
3293	MT_BUG_ON(mt, mas.last != 0x3500);
3294	MT_BUG_ON(mt, !mas_is_active(&mas));
3295
3296	/* next:active ->  overflow (limit reached) */
3297	entry = mas_next(&mas, ULONG_MAX);
3298	MT_BUG_ON(mt, entry != NULL);
3299	MT_BUG_ON(mt, mas.index != 0x3501);
3300	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3301	MT_BUG_ON(mt, !mas_is_overflow(&mas));
3302
3303	/* next:overflow -> overflow  */
3304	entry = mas_next(&mas, ULONG_MAX);
3305	MT_BUG_ON(mt, entry != NULL);
3306	MT_BUG_ON(mt, mas.index != 0x3501);
3307	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3308	MT_BUG_ON(mt, !mas_is_overflow(&mas));
3309
3310	/* prev:overflow -> active  */
3311	entry = mas_prev(&mas, 0);
3312	MT_BUG_ON(mt, entry != ptr3);
3313	MT_BUG_ON(mt, mas.index != 0x3000);
3314	MT_BUG_ON(mt, mas.last != 0x3500);
3315	MT_BUG_ON(mt, !mas_is_active(&mas));
3316
3317	/* next: none -> active, skip value at location */
3318	mas_set(&mas, 0);
3319	entry = mas_next(&mas, ULONG_MAX);
3320	mas.status = ma_none;
3321	mas.offset = 0;
3322	entry = mas_next(&mas, ULONG_MAX);
3323	MT_BUG_ON(mt, entry != ptr2);
3324	MT_BUG_ON(mt, mas.index != 0x2000);
3325	MT_BUG_ON(mt, mas.last != 0x2500);
3326	MT_BUG_ON(mt, !mas_is_active(&mas));
3327
3328	/* prev:active ->active */
3329	entry = mas_prev(&mas, 0);
3330	MT_BUG_ON(mt, entry != ptr);
3331	MT_BUG_ON(mt, mas.index != 0x1000);
3332	MT_BUG_ON(mt, mas.last != 0x1500);
3333	MT_BUG_ON(mt, !mas_is_active(&mas));
3334
3335	/* prev:active -> underflow (span limit) */
3336	mas_next(&mas, ULONG_MAX);
3337	entry = mas_prev(&mas, 0x1200);
3338	MT_BUG_ON(mt, entry != ptr);
3339	MT_BUG_ON(mt, mas.index != 0x1000);
3340	MT_BUG_ON(mt, mas.last != 0x1500);
3341	MT_BUG_ON(mt, !mas_is_active(&mas)); /* spanning limit */
3342	entry = mas_prev(&mas, 0x1200); /* underflow */
3343	MT_BUG_ON(mt, entry != NULL);
3344	MT_BUG_ON(mt, mas.index != 0x1000);
3345	MT_BUG_ON(mt, mas.last != 0x1500);
3346	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3347
3348	/* prev:underflow -> underflow (lower limit) spanning end range */
3349	entry = mas_prev(&mas, 0x0100);
3350	MT_BUG_ON(mt, entry != NULL);
3351	MT_BUG_ON(mt, mas.index != 0);
3352	MT_BUG_ON(mt, mas.last != 0x0FFF);
3353	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3354
3355	/* prev:underflow -> underflow */
3356	entry = mas_prev(&mas, 0);
3357	MT_BUG_ON(mt, entry != NULL);
3358	MT_BUG_ON(mt, mas.index != 0);
3359	MT_BUG_ON(mt, mas.last != 0x0FFF);
3360	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3361
3362	/* prev:underflow -> underflow */
3363	entry = mas_prev(&mas, 0);
3364	MT_BUG_ON(mt, entry != NULL);
3365	MT_BUG_ON(mt, mas.index != 0);
3366	MT_BUG_ON(mt, mas.last != 0x0FFF);
3367	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3368
3369	/* next:underflow -> active */
3370	entry = mas_next(&mas, ULONG_MAX);
3371	MT_BUG_ON(mt, entry != ptr);
3372	MT_BUG_ON(mt, mas.index != 0x1000);
3373	MT_BUG_ON(mt, mas.last != 0x1500);
3374	MT_BUG_ON(mt, !mas_is_active(&mas));
3375
3376	/* prev:first value -> underflow */
3377	entry = mas_prev(&mas, 0x1000);
3378	MT_BUG_ON(mt, entry != NULL);
3379	MT_BUG_ON(mt, mas.index != 0x1000);
3380	MT_BUG_ON(mt, mas.last != 0x1500);
3381	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3382
3383	/* find:underflow -> first value */
3384	entry = mas_find(&mas, ULONG_MAX);
3385	MT_BUG_ON(mt, entry != ptr);
3386	MT_BUG_ON(mt, mas.index != 0x1000);
3387	MT_BUG_ON(mt, mas.last != 0x1500);
3388	MT_BUG_ON(mt, !mas_is_active(&mas));
3389
3390	/* prev: pause ->active */
3391	mas_set(&mas, 0x3600);
3392	entry = mas_prev(&mas, 0);
3393	MT_BUG_ON(mt, entry != ptr3);
3394	mas_pause(&mas);
3395	entry = mas_prev(&mas, 0);
3396	MT_BUG_ON(mt, entry != ptr2);
3397	MT_BUG_ON(mt, mas.index != 0x2000);
3398	MT_BUG_ON(mt, mas.last != 0x2500);
3399	MT_BUG_ON(mt, !mas_is_active(&mas));
3400
3401	/* prev:active -> underflow spanning min */
3402	entry = mas_prev(&mas, 0x1600);
3403	MT_BUG_ON(mt, entry != NULL);
3404	MT_BUG_ON(mt, mas.index != 0x1501);
3405	MT_BUG_ON(mt, mas.last != 0x1FFF);
3406	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3407
3408	/* prev: active ->active, continue */
3409	entry = mas_prev(&mas, 0);
3410	MT_BUG_ON(mt, entry != ptr);
3411	MT_BUG_ON(mt, mas.index != 0x1000);
3412	MT_BUG_ON(mt, mas.last != 0x1500);
3413	MT_BUG_ON(mt, !mas_is_active(&mas));
3414
3415	/* find: start ->active */
3416	mas_set(&mas, 0);
3417	entry = mas_find(&mas, ULONG_MAX);
3418	MT_BUG_ON(mt, entry != ptr);
3419	MT_BUG_ON(mt, mas.index != 0x1000);
3420	MT_BUG_ON(mt, mas.last != 0x1500);
3421	MT_BUG_ON(mt, !mas_is_active(&mas));
3422
3423	/* find: pause ->active */
3424	mas_set(&mas, 0);
3425	mas_pause(&mas);
3426	entry = mas_find(&mas, ULONG_MAX);
3427	MT_BUG_ON(mt, entry != ptr);
3428	MT_BUG_ON(mt, mas.index != 0x1000);
3429	MT_BUG_ON(mt, mas.last != 0x1500);
3430	MT_BUG_ON(mt, !mas_is_active(&mas));
3431
3432	/* find: start ->active on value */
3433	mas_set(&mas, 1200);
3434	entry = mas_find(&mas, ULONG_MAX);
3435	MT_BUG_ON(mt, entry != ptr);
3436	MT_BUG_ON(mt, mas.index != 0x1000);
3437	MT_BUG_ON(mt, mas.last != 0x1500);
3438	MT_BUG_ON(mt, !mas_is_active(&mas));
3439
3440	/* find:active ->active */
3441	entry = mas_find(&mas, ULONG_MAX);
3442	MT_BUG_ON(mt, entry != ptr2);
3443	MT_BUG_ON(mt, mas.index != 0x2000);
3444	MT_BUG_ON(mt, mas.last != 0x2500);
3445	MT_BUG_ON(mt, !mas_is_active(&mas));
3446
3447
3448	/* find:active -> active (NULL)*/
3449	entry = mas_find(&mas, 0x2700);
3450	MT_BUG_ON(mt, entry != NULL);
3451	MT_BUG_ON(mt, mas.index != 0x2501);
3452	MT_BUG_ON(mt, mas.last != 0x2FFF);
3453	MAS_BUG_ON(&mas, !mas_is_active(&mas));
3454
3455	/* find: overflow ->active */
3456	entry = mas_find(&mas, 0x5000);
3457	MT_BUG_ON(mt, entry != ptr3);
3458	MT_BUG_ON(mt, mas.index != 0x3000);
3459	MT_BUG_ON(mt, mas.last != 0x3500);
3460	MT_BUG_ON(mt, !mas_is_active(&mas));
3461
3462	/* find:active -> active (NULL) end*/
3463	entry = mas_find(&mas, ULONG_MAX);
3464	MT_BUG_ON(mt, entry != NULL);
3465	MT_BUG_ON(mt, mas.index != 0x3501);
3466	MT_BUG_ON(mt, mas.last != ULONG_MAX);
3467	MAS_BUG_ON(&mas, !mas_is_active(&mas));
3468
3469	/* find_rev: active (END) ->active */
3470	entry = mas_find_rev(&mas, 0);
3471	MT_BUG_ON(mt, entry != ptr3);
3472	MT_BUG_ON(mt, mas.index != 0x3000);
3473	MT_BUG_ON(mt, mas.last != 0x3500);
3474	MT_BUG_ON(mt, !mas_is_active(&mas));
3475
3476	/* find_rev:active ->active */
3477	entry = mas_find_rev(&mas, 0);
3478	MT_BUG_ON(mt, entry != ptr2);
3479	MT_BUG_ON(mt, mas.index != 0x2000);
3480	MT_BUG_ON(mt, mas.last != 0x2500);
3481	MT_BUG_ON(mt, !mas_is_active(&mas));
3482
3483	/* find_rev: pause ->active */
3484	mas_pause(&mas);
3485	entry = mas_find_rev(&mas, 0);
3486	MT_BUG_ON(mt, entry != ptr);
3487	MT_BUG_ON(mt, mas.index != 0x1000);
3488	MT_BUG_ON(mt, mas.last != 0x1500);
3489	MT_BUG_ON(mt, !mas_is_active(&mas));
3490
3491	/* find_rev:active -> underflow */
3492	entry = mas_find_rev(&mas, 0);
3493	MT_BUG_ON(mt, entry != NULL);
3494	MT_BUG_ON(mt, mas.index != 0);
3495	MT_BUG_ON(mt, mas.last != 0x0FFF);
3496	MT_BUG_ON(mt, !mas_is_underflow(&mas));
3497
3498	/* find_rev: start ->active */
3499	mas_set(&mas, 0x1200);
3500	entry = mas_find_rev(&mas, 0);
3501	MT_BUG_ON(mt, entry != ptr);
3502	MT_BUG_ON(mt, mas.index != 0x1000);
3503	MT_BUG_ON(mt, mas.last != 0x1500);
3504	MT_BUG_ON(mt, !mas_is_active(&mas));
3505
3506	/* mas_walk start ->active */
3507	mas_set(&mas, 0x1200);
3508	entry = mas_walk(&mas);
3509	MT_BUG_ON(mt, entry != ptr);
3510	MT_BUG_ON(mt, mas.index != 0x1000);
3511	MT_BUG_ON(mt, mas.last != 0x1500);
3512	MT_BUG_ON(mt, !mas_is_active(&mas));
3513
3514	/* mas_walk start ->active */
3515	mas_set(&mas, 0x1600);
3516	entry = mas_walk(&mas);
3517	MT_BUG_ON(mt, entry != NULL);
3518	MT_BUG_ON(mt, mas.index != 0x1501);
3519	MT_BUG_ON(mt, mas.last != 0x1fff);
3520	MT_BUG_ON(mt, !mas_is_active(&mas));
3521
3522	/* mas_walk pause ->active */
3523	mas_set(&mas, 0x1200);
3524	mas_pause(&mas);
3525	entry = mas_walk(&mas);
3526	MT_BUG_ON(mt, entry != ptr);
3527	MT_BUG_ON(mt, mas.index != 0x1000);
3528	MT_BUG_ON(mt, mas.last != 0x1500);
3529	MT_BUG_ON(mt, !mas_is_active(&mas));
3530
3531	/* mas_walk pause -> active */
3532	mas_set(&mas, 0x1600);
3533	mas_pause(&mas);
3534	entry = mas_walk(&mas);
3535	MT_BUG_ON(mt, entry != NULL);
3536	MT_BUG_ON(mt, mas.index != 0x1501);
3537	MT_BUG_ON(mt, mas.last != 0x1fff);
3538	MT_BUG_ON(mt, !mas_is_active(&mas));
3539
3540	/* mas_walk none -> active */
3541	mas_set(&mas, 0x1200);
3542	mas.status = ma_none;
3543	entry = mas_walk(&mas);
3544	MT_BUG_ON(mt, entry != ptr);
3545	MT_BUG_ON(mt, mas.index != 0x1000);
3546	MT_BUG_ON(mt, mas.last != 0x1500);
3547	MT_BUG_ON(mt, !mas_is_active(&mas));
3548
3549	/* mas_walk none -> active */
3550	mas_set(&mas, 0x1600);
3551	mas.status = ma_none;
3552	entry = mas_walk(&mas);
3553	MT_BUG_ON(mt, entry != NULL);
3554	MT_BUG_ON(mt, mas.index != 0x1501);
3555	MT_BUG_ON(mt, mas.last != 0x1fff);
3556	MT_BUG_ON(mt, !mas_is_active(&mas));
3557
3558	/* mas_walk active -> active */
3559	mas.index = 0x1200;
3560	mas.last = 0x1200;
3561	mas.offset = 0;
3562	entry = mas_walk(&mas);
3563	MT_BUG_ON(mt, entry != ptr);
3564	MT_BUG_ON(mt, mas.index != 0x1000);
3565	MT_BUG_ON(mt, mas.last != 0x1500);
3566	MT_BUG_ON(mt, !mas_is_active(&mas));
3567
3568	/* mas_walk active -> active */
3569	mas.index = 0x1600;
3570	mas.last = 0x1600;
3571	entry = mas_walk(&mas);
3572	MT_BUG_ON(mt, entry != NULL);
3573	MT_BUG_ON(mt, mas.index != 0x1501);
3574	MT_BUG_ON(mt, mas.last != 0x1fff);
3575	MT_BUG_ON(mt, !mas_is_active(&mas));
3576
3577	mas_unlock(&mas);
3578	mtree_destroy(mt);
3579
3580	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
3581	mas_lock(&mas);
3582	for (int count = 0; count < 30; count++) {
3583		mas_set(&mas, count);
3584		mas_store_gfp(&mas, xa_mk_value(count), GFP_KERNEL);
3585	}
3586
3587	/* Ensure mas_find works with MA_UNDERFLOW */
3588	mas_set(&mas, 0);
3589	entry = mas_walk(&mas);
3590	mas_set(&mas, 0);
3591	mas_prev(&mas, 0);
3592	MT_BUG_ON(mt, mas.status != ma_underflow);
3593	MT_BUG_ON(mt, mas_find(&mas, ULONG_MAX) != entry);
3594
3595	/* Restore active on mas_next */
3596	entry = mas_next(&mas, ULONG_MAX);
3597	index = mas.index;
3598	mas_prev(&mas, index);
3599	MT_BUG_ON(mt, mas.status != ma_underflow);
3600	MT_BUG_ON(mt, mas_next(&mas, ULONG_MAX) != entry);
3601
3602	/* Ensure overflow -> active works */
3603	mas_prev(&mas, 0);
3604	mas_next(&mas, index - 1);
3605	MT_BUG_ON(mt, mas.status != ma_overflow);
3606	MT_BUG_ON(mt, mas_next(&mas, ULONG_MAX) != entry);
3607
3608	mas_unlock(&mas);
3609}
3610
3611static noinline void __init alloc_cyclic_testing(struct maple_tree *mt)
3612{
3613	unsigned long location;
3614	unsigned long next;
3615	int ret = 0;
3616	MA_STATE(mas, mt, 0, 0);
3617
3618	next = 0;
3619	mtree_lock(mt);
3620	for (int i = 0; i < 100; i++) {
3621		mas_alloc_cyclic(&mas, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3622		MAS_BUG_ON(&mas, i != location - 2);
3623		MAS_BUG_ON(&mas, mas.index != location);
3624		MAS_BUG_ON(&mas, mas.last != location);
3625		MAS_BUG_ON(&mas, i != next - 3);
3626	}
3627
3628	mtree_unlock(mt);
3629	mtree_destroy(mt);
3630	next = 0;
3631	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
3632	for (int i = 0; i < 100; i++) {
3633		mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3634		MT_BUG_ON(mt, i != location - 2);
3635		MT_BUG_ON(mt, i != next - 3);
3636		MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3637	}
3638
3639	mtree_destroy(mt);
3640
3641	/*
3642	 * Issue with reverse search was discovered
3643	 * https://lore.kernel.org/all/20241216060600.287B4C4CED0@smtp.kernel.org/
3644	 * Exhausting the allocation area and forcing the search to wrap needs a
3645	 * mas_reset() in mas_alloc_cyclic().
3646	 */
3647	next = 0;
3648	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
3649	for (int i = 0; i < 1023; i++) {
3650		mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL);
3651		MT_BUG_ON(mt, i != location - 2);
3652		MT_BUG_ON(mt, i != next - 3);
3653		MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3654	}
3655	mtree_erase(mt, 123);
3656	MT_BUG_ON(mt, mtree_load(mt, 123) != NULL);
3657	mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL);
3658	MT_BUG_ON(mt, 123 != location);
3659	MT_BUG_ON(mt, 124 != next);
3660	MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3661	mtree_erase(mt, 100);
3662	mtree_alloc_cyclic(mt, &location, mt, 2, 1024, &next, GFP_KERNEL);
3663	MT_BUG_ON(mt, 100 != location);
3664	MT_BUG_ON(mt, 101 != next);
3665	MT_BUG_ON(mt, mtree_load(mt, location) != mt);
3666	mtree_destroy(mt);
3667
3668	/* Overflow test */
3669	next = ULONG_MAX - 1;
3670	ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3671	MT_BUG_ON(mt, ret != 0);
3672	ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3673	MT_BUG_ON(mt, ret != 0);
3674	ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL);
3675	MT_BUG_ON(mt, ret != 1);
3676}
3677
3678static DEFINE_MTREE(tree);
3679static int __init maple_tree_seed(void)
3680{
3681	unsigned long set[] = { 5015, 5014, 5017, 25, 1000,
3682				1001, 1002, 1003, 1005, 0,
3683				5003, 5002};
3684	void *ptr = &set;
3685
3686	pr_info("\nTEST STARTING\n\n");
3687
3688#if defined(BENCH_SLOT_STORE)
3689#define BENCH
3690	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3691	bench_slot_store(&tree);
3692	mtree_destroy(&tree);
3693	goto skip;
3694#endif
3695#if defined(BENCH_NODE_STORE)
3696#define BENCH
3697	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3698	bench_node_store(&tree);
3699	mtree_destroy(&tree);
3700	goto skip;
3701#endif
3702#if defined(BENCH_AWALK)
3703#define BENCH
3704	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3705	bench_awalk(&tree);
3706	mtree_destroy(&tree);
3707	goto skip;
3708#endif
3709#if defined(BENCH_WALK)
3710#define BENCH
3711	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3712	bench_walk(&tree);
3713	mtree_destroy(&tree);
3714	goto skip;
3715#endif
3716#if defined(BENCH_LOAD)
3717#define BENCH
3718	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3719	bench_load(&tree);
3720	mtree_destroy(&tree);
3721	goto skip;
3722#endif
3723#if defined(BENCH_FORK)
3724#define BENCH
3725	bench_forking();
3726	goto skip;
3727#endif
3728#if defined(BENCH_MT_FOR_EACH)
3729#define BENCH
3730	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3731	bench_mt_for_each(&tree);
3732	mtree_destroy(&tree);
3733	goto skip;
3734#endif
3735#if defined(BENCH_MAS_FOR_EACH)
3736#define BENCH
3737	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3738	bench_mas_for_each(&tree);
3739	mtree_destroy(&tree);
3740	goto skip;
3741#endif
3742#if defined(BENCH_MAS_PREV)
3743#define BENCH
3744	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3745	bench_mas_prev(&tree);
3746	mtree_destroy(&tree);
3747	goto skip;
3748#endif
3749
3750	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3751	check_deficient_node(&tree);
3752	mtree_destroy(&tree);
3753
3754	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3755	check_store_null(&tree);
3756	mtree_destroy(&tree);
3757
3758	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3759	check_root_expand(&tree);
3760	mtree_destroy(&tree);
3761
3762	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3763	check_iteration(&tree);
3764	mtree_destroy(&tree);
3765
3766	check_forking();
3767
3768	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3769	check_mas_store_gfp(&tree);
3770	mtree_destroy(&tree);
3771
3772	/* Test ranges (store and insert) */
3773	mt_init_flags(&tree, 0);
3774	check_ranges(&tree);
3775	mtree_destroy(&tree);
3776
3777#if defined(CONFIG_64BIT)
3778	/* These tests have ranges outside of 4GB */
3779	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3780	check_alloc_range(&tree);
3781	mtree_destroy(&tree);
3782
3783	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3784	check_alloc_rev_range(&tree);
3785	mtree_destroy(&tree);
3786#endif
3787
3788	mt_init_flags(&tree, 0);
3789
3790	check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
3791
3792	check_insert(&tree, set[9], &tree);     /* Insert 0 */
3793	check_load(&tree, set[9], &tree);       /* See if 0 -> &tree */
3794	check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
3795
3796	check_insert(&tree, set[10], ptr);      /* Insert 5003 */
3797	check_load(&tree, set[9], &tree);       /* See if 0 -> &tree */
3798	check_load(&tree, set[11], NULL);       /* See if 5002 -> NULL */
3799	check_load(&tree, set[10], ptr);       /* See if 5003 -> ptr */
3800
3801	/* Clear out the tree */
3802	mtree_destroy(&tree);
3803
3804	/* Try to insert, insert a dup, and load back what was inserted. */
3805	mt_init_flags(&tree, 0);
3806	check_insert(&tree, set[0], &tree);     /* Insert 5015 */
3807	check_dup_insert(&tree, set[0], &tree); /* Insert 5015 again */
3808	check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
3809
3810	/*
3811	 * Second set of tests try to load a value that doesn't exist, inserts
3812	 * a second value, then loads the value again
3813	 */
3814	check_load(&tree, set[1], NULL);        /* See if 5014 -> NULL */
3815	check_insert(&tree, set[1], ptr);       /* insert 5014 -> ptr */
3816	check_load(&tree, set[1], ptr);         /* See if 5014 -> ptr */
3817	check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
3818	/*
3819	 * Tree currently contains:
3820	 * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil)
3821	 */
3822	check_insert(&tree, set[6], ptr);       /* insert 1002 -> ptr */
3823	check_insert(&tree, set[7], &tree);       /* insert 1003 -> &tree */
3824
3825	check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
3826	check_load(&tree, set[1], ptr);         /* See if 5014 -> ptr */
3827	check_load(&tree, set[6], ptr);         /* See if 1002 -> ptr */
3828	check_load(&tree, set[7], &tree);       /* 1003 = &tree ? */
3829
3830	/* Clear out tree */
3831	mtree_destroy(&tree);
3832
3833	mt_init_flags(&tree, 0);
3834	/* Test inserting into a NULL hole. */
3835	check_insert(&tree, set[5], ptr);       /* insert 1001 -> ptr */
3836	check_insert(&tree, set[7], &tree);       /* insert 1003 -> &tree */
3837	check_insert(&tree, set[6], ptr);       /* insert 1002 -> ptr */
3838	check_load(&tree, set[5], ptr);         /* See if 1001 -> ptr */
3839	check_load(&tree, set[6], ptr);         /* See if 1002 -> ptr */
3840	check_load(&tree, set[7], &tree);       /* See if 1003 -> &tree */
3841
3842	/* Clear out the tree */
3843	mtree_destroy(&tree);
3844
3845	mt_init_flags(&tree, 0);
3846	/*
3847	 *       set[] = {5015, 5014, 5017, 25, 1000,
3848	 *                1001, 1002, 1003, 1005, 0,
3849	 *                5003, 5002};
3850	 */
3851
3852	check_insert(&tree, set[0], ptr); /* 5015 */
3853	check_insert(&tree, set[1], &tree); /* 5014 */
3854	check_insert(&tree, set[2], ptr); /* 5017 */
3855	check_insert(&tree, set[3], &tree); /* 25 */
3856	check_load(&tree, set[0], ptr);
3857	check_load(&tree, set[1], &tree);
3858	check_load(&tree, set[2], ptr);
3859	check_load(&tree, set[3], &tree);
3860	check_insert(&tree, set[4], ptr); /* 1000 < Should split. */
3861	check_load(&tree, set[0], ptr);
3862	check_load(&tree, set[1], &tree);
3863	check_load(&tree, set[2], ptr);
3864	check_load(&tree, set[3], &tree); /*25 */
3865	check_load(&tree, set[4], ptr);
3866	check_insert(&tree, set[5], &tree); /* 1001 */
3867	check_load(&tree, set[0], ptr);
3868	check_load(&tree, set[1], &tree);
3869	check_load(&tree, set[2], ptr);
3870	check_load(&tree, set[3], &tree);
3871	check_load(&tree, set[4], ptr);
3872	check_load(&tree, set[5], &tree);
3873	check_insert(&tree, set[6], ptr);
3874	check_load(&tree, set[0], ptr);
3875	check_load(&tree, set[1], &tree);
3876	check_load(&tree, set[2], ptr);
3877	check_load(&tree, set[3], &tree);
3878	check_load(&tree, set[4], ptr);
3879	check_load(&tree, set[5], &tree);
3880	check_load(&tree, set[6], ptr);
3881	check_insert(&tree, set[7], &tree);
3882	check_load(&tree, set[0], ptr);
3883	check_insert(&tree, set[8], ptr);
3884
3885	check_insert(&tree, set[9], &tree);
3886
3887	check_load(&tree, set[0], ptr);
3888	check_load(&tree, set[1], &tree);
3889	check_load(&tree, set[2], ptr);
3890	check_load(&tree, set[3], &tree);
3891	check_load(&tree, set[4], ptr);
3892	check_load(&tree, set[5], &tree);
3893	check_load(&tree, set[6], ptr);
3894	check_load(&tree, set[9], &tree);
3895	mtree_destroy(&tree);
3896
3897	mt_init_flags(&tree, 0);
3898	check_seq(&tree, 16, false);
3899	mtree_destroy(&tree);
3900
3901	mt_init_flags(&tree, 0);
3902	check_seq(&tree, 1000, true);
3903	mtree_destroy(&tree);
3904
3905	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3906	check_rev_seq(&tree, 1000, true);
3907	mtree_destroy(&tree);
3908
3909	check_lower_bound_split(&tree);
3910	check_upper_bound_split(&tree);
3911	check_mid_split(&tree);
3912
3913	mt_init_flags(&tree, 0);
3914	check_next_entry(&tree);
3915	check_find(&tree);
3916	check_find_2(&tree);
3917	mtree_destroy(&tree);
3918
3919	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3920	check_prev_entry(&tree);
3921	mtree_destroy(&tree);
3922
3923	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3924	check_gap_combining(&tree);
3925	mtree_destroy(&tree);
3926
3927	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3928	check_node_overwrite(&tree);
3929	mtree_destroy(&tree);
3930
3931	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3932	next_prev_test(&tree);
3933	mtree_destroy(&tree);
3934
3935	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3936	check_spanning_relatives(&tree);
3937	mtree_destroy(&tree);
3938
3939	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3940	check_rev_find(&tree);
3941	mtree_destroy(&tree);
3942
3943	mt_init_flags(&tree, 0);
3944	check_fuzzer(&tree);
3945	mtree_destroy(&tree);
3946
3947	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3948	check_bnode_min_spanning(&tree);
3949	mtree_destroy(&tree);
3950
3951	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3952	check_empty_area_window(&tree);
3953	mtree_destroy(&tree);
3954
3955	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3956	check_empty_area_fill(&tree);
3957	mtree_destroy(&tree);
3958
3959	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3960	check_state_handling(&tree);
3961	mtree_destroy(&tree);
3962
3963	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3964	alloc_cyclic_testing(&tree);
3965	mtree_destroy(&tree);
3966
3967
3968#if defined(BENCH)
3969skip:
3970#endif
3971	rcu_barrier();
3972	pr_info("maple_tree: %u of %u tests passed\n",
3973			atomic_read(&maple_tree_tests_passed),
3974			atomic_read(&maple_tree_tests_run));
3975	if (atomic_read(&maple_tree_tests_run) ==
3976	    atomic_read(&maple_tree_tests_passed))
3977		return 0;
3978
3979	return -EINVAL;
3980}
3981
3982static void __exit maple_tree_harvest(void)
3983{
3984
3985}
3986
3987module_init(maple_tree_seed);
3988module_exit(maple_tree_harvest);
3989MODULE_AUTHOR("Liam R. Howlett <Liam.Howlett@Oracle.com>");
3990MODULE_DESCRIPTION("maple tree API test module");
3991MODULE_LICENSE("GPL");