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