lib/test_maple_tree.c

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