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