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