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_NONE);
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  *
2921  * Function     ENTRY   Start           Result          index & last
2922  * mas_prev()
2923  * - before index
2924  *                      Single entry tree at 0-0
2925  *                      ------------------------
2926  *                              if index > 0
2927  *              exists  MAS_START       MAS_ROOT        0
2928  *              exists  MAS_PAUSE       MAS_ROOT        0
2929  *              exists  MAS_NONE        MAS_ROOT        0
2930  *
2931  *                              if index == 0
2932  *              DNE     MAS_START       MAS_NONE        0
2933  *              DNE     MAS_PAUSE       MAS_NONE        0
2934  *              DNE     MAS_NONE        MAS_NONE        0
2935  *              DNE     MAS_ROOT        MAS_NONE        0
2936  *
2937  *                      Normal tree
2938  *                      -----------
2939  *              exists  MAS_START       active          range
2940  *              DNE     MAS_START       active          set to min
2941  *              exists  MAS_PAUSE       active          range
2942  *              DNE     MAS_PAUSE       active          set to min
2943  *              exists  MAS_NONE        active          range
2944  *              DNE     MAS_NONE        MAS_NONE        set to min
2945  *              any     MAS_ROOT        MAS_NONE        0
2946  *              exists  active          active          range
2947  *              DNE     active          active          last range
2948  *
2949  * Function     ENTRY   Start           Result          index & last
2950  * mas_find()
2951  *  - at index or next
2952  *                      Single entry tree at 0-0
2953  *                      ------------------------
2954  *                              if index >  0
2955  *              DNE     MAS_START       MAS_NONE        0
2956  *              DNE     MAS_PAUSE       MAS_NONE        0
2957  *              DNE     MAS_ROOT        MAS_NONE        0
2958  *              DNE     MAS_NONE        MAS_NONE        0
2959  *                              if index ==  0
2960  *              exists  MAS_START       MAS_ROOT        0
2961  *              exists  MAS_PAUSE       MAS_ROOT        0
2962  *              exists  MAS_NONE        MAS_ROOT        0
2963  *
2964  *                      Normal tree
2965  *                      -----------
2966  *              exists  MAS_START       active          range
2967  *              DNE     MAS_START       active          set to max
2968  *              exists  MAS_PAUSE       active          range
2969  *              DNE     MAS_PAUSE       active          set to max
2970  *              exists  MAS_NONE        active          range
2971  *              exists  active          active          range
2972  *              DNE     active          active          last range (max < last)
2973  *
2974  * Function     ENTRY   Start           Result          index & last
2975  * mas_find_rev()
2976  *  - at index or before
2977  *                      Single entry tree at 0-0
2978  *                      ------------------------
2979  *                              if index >  0
2980  *              exists  MAS_START       MAS_ROOT        0
2981  *              exists  MAS_PAUSE       MAS_ROOT        0
2982  *              exists  MAS_NONE        MAS_ROOT        0
2983  *                              if index ==  0
2984  *              DNE     MAS_START       MAS_NONE        0
2985  *              DNE     MAS_PAUSE       MAS_NONE        0
2986  *              DNE     MAS_NONE        MAS_NONE        0
2987  *              DNE     MAS_ROOT        MAS_NONE        0
2988  *
2989  *                      Normal tree
2990  *                      -----------
2991  *              exists  MAS_START       active          range
2992  *              DNE     MAS_START       active          set to min
2993  *              exists  MAS_PAUSE       active          range
2994  *              DNE     MAS_PAUSE       active          set to min
2995  *              exists  MAS_NONE        active          range
2996  *              exists  active          active          range
2997  *              DNE     active          active          last range (min > index)
2998  *
2999  * Function     ENTRY   Start           Result          index & last
3000  * mas_walk()
3001  * - Look up index
3002  *                      Single entry tree at 0-0
3003  *                      ------------------------
3004  *                              if index >  0
3005  *              DNE     MAS_START       MAS_ROOT        1 - oo
3006  *              DNE     MAS_PAUSE       MAS_ROOT        1 - oo
3007  *              DNE     MAS_NONE        MAS_ROOT        1 - oo
3008  *              DNE     MAS_ROOT        MAS_ROOT        1 - oo
3009  *                              if index ==  0
3010  *              exists  MAS_START       MAS_ROOT        0
3011  *              exists  MAS_PAUSE       MAS_ROOT        0
3012  *              exists  MAS_NONE        MAS_ROOT        0
3013  *              exists  MAS_ROOT        MAS_ROOT        0
3014  *
3015  *                      Normal tree
3016  *                      -----------
3017  *              exists  MAS_START       active          range
3018  *              DNE     MAS_START       active          range of NULL
3019  *              exists  MAS_PAUSE       active          range
3020  *              DNE     MAS_PAUSE       active          range of NULL
3021  *              exists  MAS_NONE        active          range
3022  *              DNE     MAS_NONE        active          range of NULL
3023  *              exists  active          active          range
3024  *              DNE     active          active          range of NULL
3025  */
3026
3027 #define mas_active(x)           (((x).node != MAS_ROOT) && \
3028                                  ((x).node != MAS_START) && \
3029                                  ((x).node != MAS_PAUSE) && \
3030                                  ((x).node != MAS_NONE))
3031 static noinline void __init check_state_handling(struct maple_tree *mt)
3032 {
3033         MA_STATE(mas, mt, 0, 0);
3034         void *entry, *ptr = (void *) 0x1234500;
3035         void *ptr2 = &ptr;
3036         void *ptr3 = &ptr2;
3037
3038         /* Check MAS_ROOT First */
3039         mtree_store_range(mt, 0, 0, ptr, GFP_KERNEL);
3040
3041         mas_lock(&mas);
3042         /* prev: Start -> none */
3043         entry = mas_prev(&mas, 0);
3044         MT_BUG_ON(mt, entry != NULL);
3045         MT_BUG_ON(mt, mas.node != MAS_NONE);
3046
3047         /* prev: Start -> root */
3048         mas_set(&mas, 10);
3049         entry = mas_prev(&mas, 0);
3050         MT_BUG_ON(mt, entry != ptr);
3051         MT_BUG_ON(mt, mas.index != 0);
3052         MT_BUG_ON(mt, mas.last != 0);
3053         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3054
3055         /* prev: pause -> root */
3056         mas_set(&mas, 10);
3057         mas_pause(&mas);
3058         entry = mas_prev(&mas, 0);
3059         MT_BUG_ON(mt, entry != ptr);
3060         MT_BUG_ON(mt, mas.index != 0);
3061         MT_BUG_ON(mt, mas.last != 0);
3062         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3063
3064         /* next: start -> none */
3065         mas_set(&mas, 0);
3066         entry = mas_next(&mas, ULONG_MAX);
3067         MT_BUG_ON(mt, mas.index != 1);
3068         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3069         MT_BUG_ON(mt, entry != NULL);
3070         MT_BUG_ON(mt, mas.node != MAS_NONE);
3071
3072         /* next: start -> none */
3073         mas_set(&mas, 10);
3074         entry = mas_next(&mas, ULONG_MAX);
3075         MT_BUG_ON(mt, mas.index != 1);
3076         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3077         MT_BUG_ON(mt, entry != NULL);
3078         MT_BUG_ON(mt, mas.node != MAS_NONE);
3079
3080         /* find: start -> root */
3081         mas_set(&mas, 0);
3082         entry = mas_find(&mas, ULONG_MAX);
3083         MT_BUG_ON(mt, entry != ptr);
3084         MT_BUG_ON(mt, mas.index != 0);
3085         MT_BUG_ON(mt, mas.last != 0);
3086         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3087
3088         /* find: root -> none */
3089         entry = mas_find(&mas, ULONG_MAX);
3090         MT_BUG_ON(mt, entry != NULL);
3091         MT_BUG_ON(mt, mas.index != 1);
3092         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3093         MT_BUG_ON(mt, mas.node != MAS_NONE);
3094
3095         /* find: none -> none */
3096         entry = mas_find(&mas, ULONG_MAX);
3097         MT_BUG_ON(mt, entry != NULL);
3098         MT_BUG_ON(mt, mas.index != 1);
3099         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3100         MT_BUG_ON(mt, mas.node != MAS_NONE);
3101
3102         /* find: start -> none */
3103         mas_set(&mas, 10);
3104         entry = mas_find(&mas, ULONG_MAX);
3105         MT_BUG_ON(mt, entry != NULL);
3106         MT_BUG_ON(mt, mas.index != 1);
3107         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3108         MT_BUG_ON(mt, mas.node != MAS_NONE);
3109
3110         /* find_rev: none -> root */
3111         entry = mas_find_rev(&mas, 0);
3112         MT_BUG_ON(mt, entry != ptr);
3113         MT_BUG_ON(mt, mas.index != 0);
3114         MT_BUG_ON(mt, mas.last != 0);
3115         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3116
3117         /* find_rev: start -> root */
3118         mas_set(&mas, 0);
3119         entry = mas_find_rev(&mas, 0);
3120         MT_BUG_ON(mt, entry != ptr);
3121         MT_BUG_ON(mt, mas.index != 0);
3122         MT_BUG_ON(mt, mas.last != 0);
3123         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3124
3125         /* find_rev: root -> none */
3126         entry = mas_find_rev(&mas, 0);
3127         MT_BUG_ON(mt, entry != NULL);
3128         MT_BUG_ON(mt, mas.index != 0);
3129         MT_BUG_ON(mt, mas.last != 0);
3130         MT_BUG_ON(mt, mas.node != MAS_NONE);
3131
3132         /* find_rev: none -> none */
3133         entry = mas_find_rev(&mas, 0);
3134         MT_BUG_ON(mt, entry != NULL);
3135         MT_BUG_ON(mt, mas.index != 0);
3136         MT_BUG_ON(mt, mas.last != 0);
3137         MT_BUG_ON(mt, mas.node != MAS_NONE);
3138
3139         /* find_rev: start -> root */
3140         mas_set(&mas, 10);
3141         entry = mas_find_rev(&mas, 0);
3142         MT_BUG_ON(mt, entry != ptr);
3143         MT_BUG_ON(mt, mas.index != 0);
3144         MT_BUG_ON(mt, mas.last != 0);
3145         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3146
3147         /* walk: start -> none */
3148         mas_set(&mas, 10);
3149         entry = mas_walk(&mas);
3150         MT_BUG_ON(mt, entry != NULL);
3151         MT_BUG_ON(mt, mas.index != 1);
3152         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3153         MT_BUG_ON(mt, mas.node != MAS_NONE);
3154
3155         /* walk: pause -> none*/
3156         mas_set(&mas, 10);
3157         mas_pause(&mas);
3158         entry = mas_walk(&mas);
3159         MT_BUG_ON(mt, entry != NULL);
3160         MT_BUG_ON(mt, mas.index != 1);
3161         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3162         MT_BUG_ON(mt, mas.node != MAS_NONE);
3163
3164         /* walk: none -> none */
3165         mas.index = mas.last = 10;
3166         entry = mas_walk(&mas);
3167         MT_BUG_ON(mt, entry != NULL);
3168         MT_BUG_ON(mt, mas.index != 1);
3169         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3170         MT_BUG_ON(mt, mas.node != MAS_NONE);
3171
3172         /* walk: none -> none */
3173         entry = mas_walk(&mas);
3174         MT_BUG_ON(mt, entry != NULL);
3175         MT_BUG_ON(mt, mas.index != 1);
3176         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3177         MT_BUG_ON(mt, mas.node != MAS_NONE);
3178
3179         /* walk: start -> root */
3180         mas_set(&mas, 0);
3181         entry = mas_walk(&mas);
3182         MT_BUG_ON(mt, entry != ptr);
3183         MT_BUG_ON(mt, mas.index != 0);
3184         MT_BUG_ON(mt, mas.last != 0);
3185         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3186
3187         /* walk: pause -> root */
3188         mas_set(&mas, 0);
3189         mas_pause(&mas);
3190         entry = mas_walk(&mas);
3191         MT_BUG_ON(mt, entry != ptr);
3192         MT_BUG_ON(mt, mas.index != 0);
3193         MT_BUG_ON(mt, mas.last != 0);
3194         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3195
3196         /* walk: none -> root */
3197         mas.node = MAS_NONE;
3198         entry = mas_walk(&mas);
3199         MT_BUG_ON(mt, entry != ptr);
3200         MT_BUG_ON(mt, mas.index != 0);
3201         MT_BUG_ON(mt, mas.last != 0);
3202         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3203
3204         /* walk: root -> root */
3205         entry = mas_walk(&mas);
3206         MT_BUG_ON(mt, entry != ptr);
3207         MT_BUG_ON(mt, mas.index != 0);
3208         MT_BUG_ON(mt, mas.last != 0);
3209         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3210
3211         /* walk: root -> none */
3212         mas_set(&mas, 10);
3213         entry = mas_walk(&mas);
3214         MT_BUG_ON(mt, entry != NULL);
3215         MT_BUG_ON(mt, mas.index != 1);
3216         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3217         MT_BUG_ON(mt, mas.node != MAS_NONE);
3218
3219         /* walk: none -> root */
3220         mas.index = mas.last = 0;
3221         entry = mas_walk(&mas);
3222         MT_BUG_ON(mt, entry != ptr);
3223         MT_BUG_ON(mt, mas.index != 0);
3224         MT_BUG_ON(mt, mas.last != 0);
3225         MT_BUG_ON(mt, mas.node != MAS_ROOT);
3226
3227         mas_unlock(&mas);
3228
3229         /* Check when there is an actual node */
3230         mtree_store_range(mt, 0, 0, NULL, GFP_KERNEL);
3231         mtree_store_range(mt, 0x1000, 0x1500, ptr, GFP_KERNEL);
3232         mtree_store_range(mt, 0x2000, 0x2500, ptr2, GFP_KERNEL);
3233         mtree_store_range(mt, 0x3000, 0x3500, ptr3, GFP_KERNEL);
3234
3235         mas_lock(&mas);
3236
3237         /* next: start ->active */
3238         mas_set(&mas, 0);
3239         entry = mas_next(&mas, ULONG_MAX);
3240         MT_BUG_ON(mt, entry != ptr);
3241         MT_BUG_ON(mt, mas.index != 0x1000);
3242         MT_BUG_ON(mt, mas.last != 0x1500);
3243         MT_BUG_ON(mt, !mas_active(mas));
3244
3245         /* next: pause ->active */
3246         mas_set(&mas, 0);
3247         mas_pause(&mas);
3248         entry = mas_next(&mas, ULONG_MAX);
3249         MT_BUG_ON(mt, entry != ptr);
3250         MT_BUG_ON(mt, mas.index != 0x1000);
3251         MT_BUG_ON(mt, mas.last != 0x1500);
3252         MT_BUG_ON(mt, !mas_active(mas));
3253
3254         /* next: none ->active */
3255         mas.index = mas.last = 0;
3256         mas.offset = 0;
3257         mas.node = MAS_NONE;
3258         entry = mas_next(&mas, ULONG_MAX);
3259         MT_BUG_ON(mt, entry != ptr);
3260         MT_BUG_ON(mt, mas.index != 0x1000);
3261         MT_BUG_ON(mt, mas.last != 0x1500);
3262         MT_BUG_ON(mt, !mas_active(mas));
3263
3264         /* next:active ->active */
3265         entry = mas_next(&mas, ULONG_MAX);
3266         MT_BUG_ON(mt, entry != ptr2);
3267         MT_BUG_ON(mt, mas.index != 0x2000);
3268         MT_BUG_ON(mt, mas.last != 0x2500);
3269         MT_BUG_ON(mt, !mas_active(mas));
3270
3271         /* next:active -> active out of range*/
3272         entry = mas_next(&mas, 0x2999);
3273         MT_BUG_ON(mt, entry != NULL);
3274         MT_BUG_ON(mt, mas.index != 0x2501);
3275         MT_BUG_ON(mt, mas.last != 0x2fff);
3276         MT_BUG_ON(mt, !mas_active(mas));
3277
3278         /* Continue after out of range*/
3279         entry = mas_next(&mas, ULONG_MAX);
3280         MT_BUG_ON(mt, entry != ptr3);
3281         MT_BUG_ON(mt, mas.index != 0x3000);
3282         MT_BUG_ON(mt, mas.last != 0x3500);
3283         MT_BUG_ON(mt, !mas_active(mas));
3284
3285         /* next:active -> active out of range*/
3286         entry = mas_next(&mas, ULONG_MAX);
3287         MT_BUG_ON(mt, entry != NULL);
3288         MT_BUG_ON(mt, mas.index != 0x3501);
3289         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3290         MT_BUG_ON(mt, !mas_active(mas));
3291
3292         /* next: none -> active, skip value at location */
3293         mas_set(&mas, 0);
3294         entry = mas_next(&mas, ULONG_MAX);
3295         mas.node = MAS_NONE;
3296         mas.offset = 0;
3297         entry = mas_next(&mas, ULONG_MAX);
3298         MT_BUG_ON(mt, entry != ptr2);
3299         MT_BUG_ON(mt, mas.index != 0x2000);
3300         MT_BUG_ON(mt, mas.last != 0x2500);
3301         MT_BUG_ON(mt, !mas_active(mas));
3302
3303         /* prev:active ->active */
3304         entry = mas_prev(&mas, 0);
3305         MT_BUG_ON(mt, entry != ptr);
3306         MT_BUG_ON(mt, mas.index != 0x1000);
3307         MT_BUG_ON(mt, mas.last != 0x1500);
3308         MT_BUG_ON(mt, !mas_active(mas));
3309
3310         /* prev:active -> active out of range*/
3311         entry = mas_prev(&mas, 0);
3312         MT_BUG_ON(mt, entry != NULL);
3313         MT_BUG_ON(mt, mas.index != 0);
3314         MT_BUG_ON(mt, mas.last != 0x0FFF);
3315         MT_BUG_ON(mt, !mas_active(mas));
3316
3317         /* prev: pause ->active */
3318         mas_set(&mas, 0x3600);
3319         entry = mas_prev(&mas, 0);
3320         MT_BUG_ON(mt, entry != ptr3);
3321         mas_pause(&mas);
3322         entry = mas_prev(&mas, 0);
3323         MT_BUG_ON(mt, entry != ptr2);
3324         MT_BUG_ON(mt, mas.index != 0x2000);
3325         MT_BUG_ON(mt, mas.last != 0x2500);
3326         MT_BUG_ON(mt, !mas_active(mas));
3327
3328         /* prev:active -> active out of range*/
3329         entry = mas_prev(&mas, 0x1600);
3330         MT_BUG_ON(mt, entry != NULL);
3331         MT_BUG_ON(mt, mas.index != 0x1501);
3332         MT_BUG_ON(mt, mas.last != 0x1FFF);
3333         MT_BUG_ON(mt, !mas_active(mas));
3334
3335         /* prev: active ->active, continue*/
3336         entry = mas_prev(&mas, 0);
3337         MT_BUG_ON(mt, entry != ptr);
3338         MT_BUG_ON(mt, mas.index != 0x1000);
3339         MT_BUG_ON(mt, mas.last != 0x1500);
3340         MT_BUG_ON(mt, !mas_active(mas));
3341
3342         /* find: start ->active */
3343         mas_set(&mas, 0);
3344         entry = mas_find(&mas, ULONG_MAX);
3345         MT_BUG_ON(mt, entry != ptr);
3346         MT_BUG_ON(mt, mas.index != 0x1000);
3347         MT_BUG_ON(mt, mas.last != 0x1500);
3348         MT_BUG_ON(mt, !mas_active(mas));
3349
3350         /* find: pause ->active */
3351         mas_set(&mas, 0);
3352         mas_pause(&mas);
3353         entry = mas_find(&mas, ULONG_MAX);
3354         MT_BUG_ON(mt, entry != ptr);
3355         MT_BUG_ON(mt, mas.index != 0x1000);
3356         MT_BUG_ON(mt, mas.last != 0x1500);
3357         MT_BUG_ON(mt, !mas_active(mas));
3358
3359         /* find: start ->active on value */;
3360         mas_set(&mas, 1200);
3361         entry = mas_find(&mas, ULONG_MAX);
3362         MT_BUG_ON(mt, entry != ptr);
3363         MT_BUG_ON(mt, mas.index != 0x1000);
3364         MT_BUG_ON(mt, mas.last != 0x1500);
3365         MT_BUG_ON(mt, !mas_active(mas));
3366
3367         /* find:active ->active */
3368         entry = mas_find(&mas, ULONG_MAX);
3369         MT_BUG_ON(mt, entry != ptr2);
3370         MT_BUG_ON(mt, mas.index != 0x2000);
3371         MT_BUG_ON(mt, mas.last != 0x2500);
3372         MT_BUG_ON(mt, !mas_active(mas));
3373
3374
3375         /* find:active -> active (NULL)*/
3376         entry = mas_find(&mas, 0x2700);
3377         MT_BUG_ON(mt, entry != NULL);
3378         MT_BUG_ON(mt, mas.index != 0x2501);
3379         MT_BUG_ON(mt, mas.last != 0x2FFF);
3380         MT_BUG_ON(mt, !mas_active(mas));
3381
3382         /* find: none ->active */
3383         entry = mas_find(&mas, 0x5000);
3384         MT_BUG_ON(mt, entry != ptr3);
3385         MT_BUG_ON(mt, mas.index != 0x3000);
3386         MT_BUG_ON(mt, mas.last != 0x3500);
3387         MT_BUG_ON(mt, !mas_active(mas));
3388
3389         /* find:active -> active (NULL) end*/
3390         entry = mas_find(&mas, ULONG_MAX);
3391         MT_BUG_ON(mt, entry != NULL);
3392         MT_BUG_ON(mt, mas.index != 0x3501);
3393         MT_BUG_ON(mt, mas.last != ULONG_MAX);
3394         MT_BUG_ON(mt, !mas_active(mas));
3395
3396         /* find_rev: active (END) ->active */
3397         entry = mas_find_rev(&mas, 0);
3398         MT_BUG_ON(mt, entry != ptr3);
3399         MT_BUG_ON(mt, mas.index != 0x3000);
3400         MT_BUG_ON(mt, mas.last != 0x3500);
3401         MT_BUG_ON(mt, !mas_active(mas));
3402
3403         /* find_rev:active ->active */
3404         entry = mas_find_rev(&mas, 0);
3405         MT_BUG_ON(mt, entry != ptr2);
3406         MT_BUG_ON(mt, mas.index != 0x2000);
3407         MT_BUG_ON(mt, mas.last != 0x2500);
3408         MT_BUG_ON(mt, !mas_active(mas));
3409
3410         /* find_rev: pause ->active */
3411         mas_pause(&mas);
3412         entry = mas_find_rev(&mas, 0);
3413         MT_BUG_ON(mt, entry != ptr);
3414         MT_BUG_ON(mt, mas.index != 0x1000);
3415         MT_BUG_ON(mt, mas.last != 0x1500);
3416         MT_BUG_ON(mt, !mas_active(mas));
3417
3418         /* find_rev:active -> active */
3419         entry = mas_find_rev(&mas, 0);
3420         MT_BUG_ON(mt, entry != NULL);
3421         MT_BUG_ON(mt, mas.index != 0);
3422         MT_BUG_ON(mt, mas.last != 0x0FFF);
3423         MT_BUG_ON(mt, !mas_active(mas));
3424
3425         /* find_rev: start ->active */
3426         mas_set(&mas, 0x1200);
3427         entry = mas_find_rev(&mas, 0);
3428         MT_BUG_ON(mt, entry != ptr);
3429         MT_BUG_ON(mt, mas.index != 0x1000);
3430         MT_BUG_ON(mt, mas.last != 0x1500);
3431         MT_BUG_ON(mt, !mas_active(mas));
3432
3433         /* mas_walk start ->active */
3434         mas_set(&mas, 0x1200);
3435         entry = mas_walk(&mas);
3436         MT_BUG_ON(mt, entry != ptr);
3437         MT_BUG_ON(mt, mas.index != 0x1000);
3438         MT_BUG_ON(mt, mas.last != 0x1500);
3439         MT_BUG_ON(mt, !mas_active(mas));
3440
3441         /* mas_walk start ->active */
3442         mas_set(&mas, 0x1600);
3443         entry = mas_walk(&mas);
3444         MT_BUG_ON(mt, entry != NULL);
3445         MT_BUG_ON(mt, mas.index != 0x1501);
3446         MT_BUG_ON(mt, mas.last != 0x1fff);
3447         MT_BUG_ON(mt, !mas_active(mas));
3448
3449         /* mas_walk pause ->active */
3450         mas_set(&mas, 0x1200);
3451         mas_pause(&mas);
3452         entry = mas_walk(&mas);
3453         MT_BUG_ON(mt, entry != ptr);
3454         MT_BUG_ON(mt, mas.index != 0x1000);
3455         MT_BUG_ON(mt, mas.last != 0x1500);
3456         MT_BUG_ON(mt, !mas_active(mas));
3457
3458         /* mas_walk pause -> active */
3459         mas_set(&mas, 0x1600);
3460         mas_pause(&mas);
3461         entry = mas_walk(&mas);
3462         MT_BUG_ON(mt, entry != NULL);
3463         MT_BUG_ON(mt, mas.index != 0x1501);
3464         MT_BUG_ON(mt, mas.last != 0x1fff);
3465         MT_BUG_ON(mt, !mas_active(mas));
3466
3467         /* mas_walk none -> active */
3468         mas_set(&mas, 0x1200);
3469         mas.node = MAS_NONE;
3470         entry = mas_walk(&mas);
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         /* mas_walk none -> active */
3477         mas_set(&mas, 0x1600);
3478         mas.node = MAS_NONE;
3479         entry = mas_walk(&mas);
3480         MT_BUG_ON(mt, entry != NULL);
3481         MT_BUG_ON(mt, mas.index != 0x1501);
3482         MT_BUG_ON(mt, mas.last != 0x1fff);
3483         MT_BUG_ON(mt, !mas_active(mas));
3484
3485         /* mas_walk active -> active */
3486         mas.index = 0x1200;
3487         mas.last = 0x1200;
3488         mas.offset = 0;
3489         entry = mas_walk(&mas);
3490         MT_BUG_ON(mt, entry != ptr);
3491         MT_BUG_ON(mt, mas.index != 0x1000);
3492         MT_BUG_ON(mt, mas.last != 0x1500);
3493         MT_BUG_ON(mt, !mas_active(mas));
3494
3495         /* mas_walk active -> active */
3496         mas.index = 0x1600;
3497         mas.last = 0x1600;
3498         entry = mas_walk(&mas);
3499         MT_BUG_ON(mt, entry != NULL);
3500         MT_BUG_ON(mt, mas.index != 0x1501);
3501         MT_BUG_ON(mt, mas.last != 0x1fff);
3502         MT_BUG_ON(mt, !mas_active(mas));
3503
3504         mas_unlock(&mas);
3505 }
3506
3507 static DEFINE_MTREE(tree);
3508 static int __init maple_tree_seed(void)
3509 {
3510         unsigned long set[] = { 5015, 5014, 5017, 25, 1000,
3511                                 1001, 1002, 1003, 1005, 0,
3512                                 5003, 5002};
3513         void *ptr = &set;
3514
3515         pr_info("\nTEST STARTING\n\n");
3516
3517         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3518         check_root_expand(&tree);
3519         mtree_destroy(&tree);
3520
3521 #if defined(BENCH_SLOT_STORE)
3522 #define BENCH
3523         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3524         bench_slot_store(&tree);
3525         mtree_destroy(&tree);
3526         goto skip;
3527 #endif
3528 #if defined(BENCH_NODE_STORE)
3529 #define BENCH
3530         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3531         bench_node_store(&tree);
3532         mtree_destroy(&tree);
3533         goto skip;
3534 #endif
3535 #if defined(BENCH_AWALK)
3536 #define BENCH
3537         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3538         bench_awalk(&tree);
3539         mtree_destroy(&tree);
3540         goto skip;
3541 #endif
3542 #if defined(BENCH_WALK)
3543 #define BENCH
3544         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3545         bench_walk(&tree);
3546         mtree_destroy(&tree);
3547         goto skip;
3548 #endif
3549 #if defined(BENCH_FORK)
3550 #define BENCH
3551         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3552         bench_forking(&tree);
3553         mtree_destroy(&tree);
3554         goto skip;
3555 #endif
3556 #if defined(BENCH_MT_FOR_EACH)
3557 #define BENCH
3558         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3559         bench_mt_for_each(&tree);
3560         mtree_destroy(&tree);
3561         goto skip;
3562 #endif
3563 #if defined(BENCH_MAS_FOR_EACH)
3564 #define BENCH
3565         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3566         bench_mas_for_each(&tree);
3567         mtree_destroy(&tree);
3568         goto skip;
3569 #endif
3570 #if defined(BENCH_MAS_PREV)
3571 #define BENCH
3572         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3573         bench_mas_prev(&tree);
3574         mtree_destroy(&tree);
3575         goto skip;
3576 #endif
3577
3578         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3579         check_iteration(&tree);
3580         mtree_destroy(&tree);
3581
3582         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3583         check_forking(&tree);
3584         mtree_destroy(&tree);
3585
3586         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3587         check_mas_store_gfp(&tree);
3588         mtree_destroy(&tree);
3589
3590         /* Test ranges (store and insert) */
3591         mt_init_flags(&tree, 0);
3592         check_ranges(&tree);
3593         mtree_destroy(&tree);
3594
3595 #if defined(CONFIG_64BIT)
3596         /* These tests have ranges outside of 4GB */
3597         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3598         check_alloc_range(&tree);
3599         mtree_destroy(&tree);
3600
3601         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3602         check_alloc_rev_range(&tree);
3603         mtree_destroy(&tree);
3604 #endif
3605
3606         mt_init_flags(&tree, 0);
3607
3608         check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
3609
3610         check_insert(&tree, set[9], &tree);     /* Insert 0 */
3611         check_load(&tree, set[9], &tree);       /* See if 0 -> &tree */
3612         check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
3613
3614         check_insert(&tree, set[10], ptr);      /* Insert 5003 */
3615         check_load(&tree, set[9], &tree);       /* See if 0 -> &tree */
3616         check_load(&tree, set[11], NULL);       /* See if 5002 -> NULL */
3617         check_load(&tree, set[10], ptr);       /* See if 5003 -> ptr */
3618
3619         /* Clear out the tree */
3620         mtree_destroy(&tree);
3621
3622         /* Try to insert, insert a dup, and load back what was inserted. */
3623         mt_init_flags(&tree, 0);
3624         check_insert(&tree, set[0], &tree);     /* Insert 5015 */
3625         check_dup_insert(&tree, set[0], &tree); /* Insert 5015 again */
3626         check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
3627
3628         /*
3629          * Second set of tests try to load a value that doesn't exist, inserts
3630          * a second value, then loads the value again
3631          */
3632         check_load(&tree, set[1], NULL);        /* See if 5014 -> NULL */
3633         check_insert(&tree, set[1], ptr);       /* insert 5014 -> ptr */
3634         check_load(&tree, set[1], ptr);         /* See if 5014 -> ptr */
3635         check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
3636         /*
3637          * Tree currently contains:
3638          * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil)
3639          */
3640         check_insert(&tree, set[6], ptr);       /* insert 1002 -> ptr */
3641         check_insert(&tree, set[7], &tree);       /* insert 1003 -> &tree */
3642
3643         check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
3644         check_load(&tree, set[1], ptr);         /* See if 5014 -> ptr */
3645         check_load(&tree, set[6], ptr);         /* See if 1002 -> ptr */
3646         check_load(&tree, set[7], &tree);       /* 1003 = &tree ? */
3647
3648         /* Clear out tree */
3649         mtree_destroy(&tree);
3650
3651         mt_init_flags(&tree, 0);
3652         /* Test inserting into a NULL hole. */
3653         check_insert(&tree, set[5], ptr);       /* insert 1001 -> ptr */
3654         check_insert(&tree, set[7], &tree);       /* insert 1003 -> &tree */
3655         check_insert(&tree, set[6], ptr);       /* insert 1002 -> ptr */
3656         check_load(&tree, set[5], ptr);         /* See if 1001 -> ptr */
3657         check_load(&tree, set[6], ptr);         /* See if 1002 -> ptr */
3658         check_load(&tree, set[7], &tree);       /* See if 1003 -> &tree */
3659
3660         /* Clear out the tree */
3661         mtree_destroy(&tree);
3662
3663         mt_init_flags(&tree, 0);
3664         /*
3665          *       set[] = {5015, 5014, 5017, 25, 1000,
3666          *                1001, 1002, 1003, 1005, 0,
3667          *                5003, 5002};
3668          */
3669
3670         check_insert(&tree, set[0], ptr); /* 5015 */
3671         check_insert(&tree, set[1], &tree); /* 5014 */
3672         check_insert(&tree, set[2], ptr); /* 5017 */
3673         check_insert(&tree, set[3], &tree); /* 25 */
3674         check_load(&tree, set[0], ptr);
3675         check_load(&tree, set[1], &tree);
3676         check_load(&tree, set[2], ptr);
3677         check_load(&tree, set[3], &tree);
3678         check_insert(&tree, set[4], ptr); /* 1000 < Should split. */
3679         check_load(&tree, set[0], ptr);
3680         check_load(&tree, set[1], &tree);
3681         check_load(&tree, set[2], ptr);
3682         check_load(&tree, set[3], &tree); /*25 */
3683         check_load(&tree, set[4], ptr);
3684         check_insert(&tree, set[5], &tree); /* 1001 */
3685         check_load(&tree, set[0], ptr);
3686         check_load(&tree, set[1], &tree);
3687         check_load(&tree, set[2], ptr);
3688         check_load(&tree, set[3], &tree);
3689         check_load(&tree, set[4], ptr);
3690         check_load(&tree, set[5], &tree);
3691         check_insert(&tree, set[6], ptr);
3692         check_load(&tree, set[0], ptr);
3693         check_load(&tree, set[1], &tree);
3694         check_load(&tree, set[2], ptr);
3695         check_load(&tree, set[3], &tree);
3696         check_load(&tree, set[4], ptr);
3697         check_load(&tree, set[5], &tree);
3698         check_load(&tree, set[6], ptr);
3699         check_insert(&tree, set[7], &tree);
3700         check_load(&tree, set[0], ptr);
3701         check_insert(&tree, set[8], ptr);
3702
3703         check_insert(&tree, set[9], &tree);
3704
3705         check_load(&tree, set[0], ptr);
3706         check_load(&tree, set[1], &tree);
3707         check_load(&tree, set[2], ptr);
3708         check_load(&tree, set[3], &tree);
3709         check_load(&tree, set[4], ptr);
3710         check_load(&tree, set[5], &tree);
3711         check_load(&tree, set[6], ptr);
3712         check_load(&tree, set[9], &tree);
3713         mtree_destroy(&tree);
3714
3715         mt_init_flags(&tree, 0);
3716         check_seq(&tree, 16, false);
3717         mtree_destroy(&tree);
3718
3719         mt_init_flags(&tree, 0);
3720         check_seq(&tree, 1000, true);
3721         mtree_destroy(&tree);
3722
3723         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3724         check_rev_seq(&tree, 1000, true);
3725         mtree_destroy(&tree);
3726
3727         check_lower_bound_split(&tree);
3728         check_upper_bound_split(&tree);
3729         check_mid_split(&tree);
3730
3731         mt_init_flags(&tree, 0);
3732         check_next_entry(&tree);
3733         check_find(&tree);
3734         check_find_2(&tree);
3735         mtree_destroy(&tree);
3736
3737         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3738         check_prev_entry(&tree);
3739         mtree_destroy(&tree);
3740
3741         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3742         check_gap_combining(&tree);
3743         mtree_destroy(&tree);
3744
3745         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3746         check_node_overwrite(&tree);
3747         mtree_destroy(&tree);
3748
3749         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3750         next_prev_test(&tree);
3751         mtree_destroy(&tree);
3752
3753         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3754         check_spanning_relatives(&tree);
3755         mtree_destroy(&tree);
3756
3757         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3758         check_rev_find(&tree);
3759         mtree_destroy(&tree);
3760
3761         mt_init_flags(&tree, 0);
3762         check_fuzzer(&tree);
3763         mtree_destroy(&tree);
3764
3765         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3766         check_dup(&tree);
3767         mtree_destroy(&tree);
3768
3769         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3770         check_bnode_min_spanning(&tree);
3771         mtree_destroy(&tree);
3772
3773         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3774         check_empty_area_window(&tree);
3775         mtree_destroy(&tree);
3776
3777         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3778         check_empty_area_fill(&tree);
3779         mtree_destroy(&tree);
3780
3781
3782         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
3783         check_state_handling(&tree);
3784         mtree_destroy(&tree);
3785
3786 #if defined(BENCH)
3787 skip:
3788 #endif
3789         rcu_barrier();
3790         pr_info("maple_tree: %u of %u tests passed\n",
3791                         atomic_read(&maple_tree_tests_passed),
3792                         atomic_read(&maple_tree_tests_run));
3793         if (atomic_read(&maple_tree_tests_run) ==
3794             atomic_read(&maple_tree_tests_passed))
3795                 return 0;
3796
3797         return -EINVAL;
3798 }
3799
3800 static void __exit maple_tree_harvest(void)
3801 {
3802
3803 }
3804
3805 module_init(maple_tree_seed);
3806 module_exit(maple_tree_harvest);
3807 MODULE_AUTHOR("Liam R. Howlett <Liam.Howlett@Oracle.com>");
3808 MODULE_LICENSE("GPL");