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
  34 int mtree_insert_index(struct maple_tree *mt, 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 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 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 mtree_test_store_range(struct maple_tree *mt, unsigned long start,
  52                                 unsigned long end, void *ptr)
  53 {
  54         return mtree_store_range(mt, start, end, ptr, GFP_KERNEL);
  55 }
  56
  57 static int 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 mtree_test_insert_range(struct maple_tree *mt, unsigned long start,
  64                                 unsigned long end, void *ptr)
  65 {
  66         return mtree_insert_range(mt, start, end, ptr, GFP_KERNEL);
  67 }
  68
  69 static void *mtree_test_load(struct maple_tree *mt, unsigned long index)
  70 {
  71         return mtree_load(mt, index);
  72 }
  73
  74 static void *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 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 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 check_load(struct maple_tree *mt, unsigned long index,
 116                                 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 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 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 check_insert(struct maple_tree *mt, unsigned long index,
 158                 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 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
 177 void check_index_load(struct maple_tree *mt, unsigned long index)
 178 {
 179         return check_load(mt, index, xa_mk_value(index & LONG_MAX));
 180 }
 181
 182 static inline 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 check_rev_seq(struct maple_tree *mt, unsigned long max,
 198                 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 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 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 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 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 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 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 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 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 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         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         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         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 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         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         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         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 check_ranges(struct maple_tree *mt)
 946 {
 947         int i, val, val2;
 948         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 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 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 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 check_gap_combining(struct maple_tree *mt)
1371 {
1372         struct maple_enode *mn1, *mn2;
1373         void *entry;
1374         unsigned long singletons = 100;
1375         unsigned long *seq100;
1376         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         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         unsigned long seq2000[] = {
1405                 1152, 1151,
1406                 1100, 1200, 2,
1407         };
1408         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 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 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 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 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 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 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 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 check_mas_store_gfp(struct maple_tree *mt)
1713 {
1714
1715         struct maple_tree newmt;
1716         int i, nr_entries = 135;
1717         void *val;
1718         MA_STATE(mas, mt, 0, 0);
1719         MA_STATE(newmas, mt, 0, 0);
1720
1721         for (i = 0; i <= nr_entries; i++)
1722                 mtree_store_range(mt, i*10, i*10 + 5,
1723                                   xa_mk_value(i), GFP_KERNEL);
1724
1725         mt_set_non_kernel(99999);
1726         mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
1727         newmas.tree = &newmt;
1728         rcu_read_lock();
1729         mas_lock(&newmas);
1730         mas_reset(&newmas);
1731         mas_set(&mas, 0);
1732         mas_for_each(&mas, val, ULONG_MAX) {
1733                 newmas.index = mas.index;
1734                 newmas.last = mas.last;
1735                 mas_store_gfp(&newmas, val, GFP_KERNEL);
1736         }
1737         mas_unlock(&newmas);
1738         rcu_read_unlock();
1739         mt_validate(&newmt);
1740         mt_set_non_kernel(0);
1741         mtree_destroy(&newmt);
1742 }
1743
1744 #if defined(BENCH_FORK)
1745 static noinline void bench_forking(struct maple_tree *mt)
1746 {
1747
1748         struct maple_tree newmt;
1749         int i, nr_entries = 134, nr_fork = 80000;
1750         void *val;
1751         MA_STATE(mas, mt, 0, 0);
1752         MA_STATE(newmas, mt, 0, 0);
1753
1754         for (i = 0; i <= nr_entries; i++)
1755                 mtree_store_range(mt, i*10, i*10 + 5,
1756                                   xa_mk_value(i), GFP_KERNEL);
1757
1758         for (i = 0; i < nr_fork; i++) {
1759                 mt_set_non_kernel(99999);
1760                 mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
1761                 newmas.tree = &newmt;
1762                 mas_reset(&newmas);
1763                 mas_reset(&mas);
1764                 mas.index = 0;
1765                 mas.last = 0;
1766                 rcu_read_lock();
1767                 mas_lock(&newmas);
1768                 if (mas_expected_entries(&newmas, nr_entries)) {
1769                         printk("OOM!");
1770                         BUG_ON(1);
1771                 }
1772                 mas_for_each(&mas, val, ULONG_MAX) {
1773                         newmas.index = mas.index;
1774                         newmas.last = mas.last;
1775                         mas_store(&newmas, val);
1776                 }
1777                 mas_destroy(&newmas);
1778                 mas_unlock(&newmas);
1779                 rcu_read_unlock();
1780                 mt_validate(&newmt);
1781                 mt_set_non_kernel(0);
1782                 mtree_destroy(&newmt);
1783         }
1784 }
1785 #endif
1786
1787 static noinline void next_prev_test(struct maple_tree *mt)
1788 {
1789         int i, nr_entries;
1790         void *val;
1791         MA_STATE(mas, mt, 0, 0);
1792         struct maple_enode *mn;
1793         unsigned long *level2;
1794         unsigned long level2_64[] = {707, 1000, 710, 715, 720, 725};
1795         unsigned long level2_32[] = {1747, 2000, 1750, 1755, 1760, 1765};
1796
1797         if (MAPLE_32BIT) {
1798                 nr_entries = 500;
1799                 level2 = level2_32;
1800         } else {
1801                 nr_entries = 200;
1802                 level2 = level2_64;
1803         }
1804
1805         for (i = 0; i <= nr_entries; i++)
1806                 mtree_store_range(mt, i*10, i*10 + 5,
1807                                   xa_mk_value(i), GFP_KERNEL);
1808
1809         mas_lock(&mas);
1810         for (i = 0; i <= nr_entries / 2; i++) {
1811                 mas_next(&mas, 1000);
1812                 if (mas_is_none(&mas))
1813                         break;
1814
1815         }
1816         mas_reset(&mas);
1817         mas_set(&mas, 0);
1818         i = 0;
1819         mas_for_each(&mas, val, 1000) {
1820                 i++;
1821         }
1822
1823         mas_reset(&mas);
1824         mas_set(&mas, 0);
1825         i = 0;
1826         mas_for_each(&mas, val, 1000) {
1827                 mas_pause(&mas);
1828                 i++;
1829         }
1830
1831         /*
1832          * 680 - 685 = 0x61a00001930c
1833          * 686 - 689 = NULL;
1834          * 690 - 695 = 0x61a00001930c
1835          * Check simple next/prev
1836          */
1837         mas_set(&mas, 686);
1838         val = mas_walk(&mas);
1839         MT_BUG_ON(mt, val != NULL);
1840
1841         val = mas_next(&mas, 1000);
1842         MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
1843         MT_BUG_ON(mt, mas.index != 690);
1844         MT_BUG_ON(mt, mas.last != 695);
1845
1846         val = mas_prev(&mas, 0);
1847         MT_BUG_ON(mt, val != xa_mk_value(680 / 10));
1848         MT_BUG_ON(mt, mas.index != 680);
1849         MT_BUG_ON(mt, mas.last != 685);
1850
1851         val = mas_next(&mas, 1000);
1852         MT_BUG_ON(mt, val != xa_mk_value(690 / 10));
1853         MT_BUG_ON(mt, mas.index != 690);
1854         MT_BUG_ON(mt, mas.last != 695);
1855
1856         val = mas_next(&mas, 1000);
1857         MT_BUG_ON(mt, val != xa_mk_value(700 / 10));
1858         MT_BUG_ON(mt, mas.index != 700);
1859         MT_BUG_ON(mt, mas.last != 705);
1860
1861         /* Check across node boundaries of the tree */
1862         mas_set(&mas, 70);
1863         val = mas_walk(&mas);
1864         MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
1865         MT_BUG_ON(mt, mas.index != 70);
1866         MT_BUG_ON(mt, mas.last != 75);
1867
1868         val = mas_next(&mas, 1000);
1869         MT_BUG_ON(mt, val != xa_mk_value(80 / 10));
1870         MT_BUG_ON(mt, mas.index != 80);
1871         MT_BUG_ON(mt, mas.last != 85);
1872
1873         val = mas_prev(&mas, 70);
1874         MT_BUG_ON(mt, val != xa_mk_value(70 / 10));
1875         MT_BUG_ON(mt, mas.index != 70);
1876         MT_BUG_ON(mt, mas.last != 75);
1877
1878         /* Check across two levels of the tree */
1879         mas_reset(&mas);
1880         mas_set(&mas, level2[0]);
1881         val = mas_walk(&mas);
1882         MT_BUG_ON(mt, val != NULL);
1883         val = mas_next(&mas, level2[1]);
1884         MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
1885         MT_BUG_ON(mt, mas.index != level2[2]);
1886         MT_BUG_ON(mt, mas.last != level2[3]);
1887         mn = mas.node;
1888
1889         val = mas_next(&mas, level2[1]);
1890         MT_BUG_ON(mt, val != xa_mk_value(level2[4] / 10));
1891         MT_BUG_ON(mt, mas.index != level2[4]);
1892         MT_BUG_ON(mt, mas.last != level2[5]);
1893         MT_BUG_ON(mt, mn == mas.node);
1894
1895         val = mas_prev(&mas, 0);
1896         MT_BUG_ON(mt, val != xa_mk_value(level2[2] / 10));
1897         MT_BUG_ON(mt, mas.index != level2[2]);
1898         MT_BUG_ON(mt, mas.last != level2[3]);
1899
1900         /* Check running off the end and back on */
1901         mas_set(&mas, nr_entries * 10);
1902         val = mas_walk(&mas);
1903         MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
1904         MT_BUG_ON(mt, mas.index != (nr_entries * 10));
1905         MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
1906
1907         val = mas_next(&mas, ULONG_MAX);
1908         MT_BUG_ON(mt, val != NULL);
1909         MT_BUG_ON(mt, mas.index != ULONG_MAX);
1910         MT_BUG_ON(mt, mas.last != ULONG_MAX);
1911
1912         val = mas_prev(&mas, 0);
1913         MT_BUG_ON(mt, val != xa_mk_value(nr_entries));
1914         MT_BUG_ON(mt, mas.index != (nr_entries * 10));
1915         MT_BUG_ON(mt, mas.last != (nr_entries * 10 + 5));
1916
1917         /* Check running off the start and back on */
1918         mas_reset(&mas);
1919         mas_set(&mas, 10);
1920         val = mas_walk(&mas);
1921         MT_BUG_ON(mt, val != xa_mk_value(1));
1922         MT_BUG_ON(mt, mas.index != 10);
1923         MT_BUG_ON(mt, mas.last != 15);
1924
1925         val = mas_prev(&mas, 0);
1926         MT_BUG_ON(mt, val != xa_mk_value(0));
1927         MT_BUG_ON(mt, mas.index != 0);
1928         MT_BUG_ON(mt, mas.last != 5);
1929
1930         val = mas_prev(&mas, 0);
1931         MT_BUG_ON(mt, val != NULL);
1932         MT_BUG_ON(mt, mas.index != 0);
1933         MT_BUG_ON(mt, mas.last != 0);
1934
1935         mas.index = 0;
1936         mas.last = 5;
1937         mas_store(&mas, NULL);
1938         mas_reset(&mas);
1939         mas_set(&mas, 10);
1940         mas_walk(&mas);
1941
1942         val = mas_prev(&mas, 0);
1943         MT_BUG_ON(mt, val != NULL);
1944         MT_BUG_ON(mt, mas.index != 0);
1945         MT_BUG_ON(mt, mas.last != 0);
1946         mas_unlock(&mas);
1947
1948         mtree_destroy(mt);
1949
1950         mt_init(mt);
1951         mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL);
1952         mtree_store_range(mt, 5, 5, xa_mk_value(5), GFP_KERNEL);
1953         rcu_read_lock();
1954         mas_set(&mas, 5);
1955         val = mas_prev(&mas, 4);
1956         MT_BUG_ON(mt, val != NULL);
1957         rcu_read_unlock();
1958 }
1959
1960
1961
1962 /* Test spanning writes that require balancing right sibling or right cousin */
1963 static noinline void check_spanning_relatives(struct maple_tree *mt)
1964 {
1965
1966         unsigned long i, nr_entries = 1000;
1967
1968         for (i = 0; i <= nr_entries; i++)
1969                 mtree_store_range(mt, i*10, i*10 + 5,
1970                                   xa_mk_value(i), GFP_KERNEL);
1971
1972
1973         mtree_store_range(mt, 9365, 9955, NULL, GFP_KERNEL);
1974 }
1975
1976 static noinline void check_fuzzer(struct maple_tree *mt)
1977 {
1978         /*
1979          * 1. Causes a spanning rebalance of a single root node.
1980          * Fixed by setting the correct limit in mast_cp_to_nodes() when the
1981          * entire right side is consumed.
1982          */
1983         mtree_test_insert(mt, 88, (void *)0xb1);
1984         mtree_test_insert(mt, 84, (void *)0xa9);
1985         mtree_test_insert(mt, 2,  (void *)0x5);
1986         mtree_test_insert(mt, 4,  (void *)0x9);
1987         mtree_test_insert(mt, 14, (void *)0x1d);
1988         mtree_test_insert(mt, 7,  (void *)0xf);
1989         mtree_test_insert(mt, 12, (void *)0x19);
1990         mtree_test_insert(mt, 18, (void *)0x25);
1991         mtree_test_store_range(mt, 8, 18, (void *)0x11);
1992         mtree_destroy(mt);
1993
1994
1995         /*
1996          * 2. Cause a spanning rebalance of two nodes in root.
1997          * Fixed by setting mast->r->max correctly.
1998          */
1999         mt_init_flags(mt, 0);
2000         mtree_test_store(mt, 87, (void *)0xaf);
2001         mtree_test_store(mt, 0, (void *)0x1);
2002         mtree_test_load(mt, 4);
2003         mtree_test_insert(mt, 4, (void *)0x9);
2004         mtree_test_store(mt, 8, (void *)0x11);
2005         mtree_test_store(mt, 44, (void *)0x59);
2006         mtree_test_store(mt, 68, (void *)0x89);
2007         mtree_test_store(mt, 2, (void *)0x5);
2008         mtree_test_insert(mt, 43, (void *)0x57);
2009         mtree_test_insert(mt, 24, (void *)0x31);
2010         mtree_test_insert(mt, 844, (void *)0x699);
2011         mtree_test_store(mt, 84, (void *)0xa9);
2012         mtree_test_store(mt, 4, (void *)0x9);
2013         mtree_test_erase(mt, 4);
2014         mtree_test_load(mt, 5);
2015         mtree_test_erase(mt, 0);
2016         mtree_destroy(mt);
2017
2018         /*
2019          * 3. Cause a node overflow on copy
2020          * Fixed by using the correct check for node size in mas_wr_modify()
2021          * Also discovered issue with metadata setting.
2022          */
2023         mt_init_flags(mt, 0);
2024         mtree_test_store_range(mt, 0, ULONG_MAX, (void *)0x1);
2025         mtree_test_store(mt, 4, (void *)0x9);
2026         mtree_test_erase(mt, 5);
2027         mtree_test_erase(mt, 0);
2028         mtree_test_erase(mt, 4);
2029         mtree_test_store(mt, 5, (void *)0xb);
2030         mtree_test_erase(mt, 5);
2031         mtree_test_store(mt, 5, (void *)0xb);
2032         mtree_test_erase(mt, 5);
2033         mtree_test_erase(mt, 4);
2034         mtree_test_store(mt, 4, (void *)0x9);
2035         mtree_test_store(mt, 444, (void *)0x379);
2036         mtree_test_store(mt, 0, (void *)0x1);
2037         mtree_test_load(mt, 0);
2038         mtree_test_store(mt, 5, (void *)0xb);
2039         mtree_test_erase(mt, 0);
2040         mtree_destroy(mt);
2041
2042         /*
2043          * 4. spanning store failure due to writing incorrect pivot value at
2044          * last slot.
2045          * Fixed by setting mast->r->max correctly in mast_cp_to_nodes()
2046          *
2047          */
2048         mt_init_flags(mt, 0);
2049         mtree_test_insert(mt, 261, (void *)0x20b);
2050         mtree_test_store(mt, 516, (void *)0x409);
2051         mtree_test_store(mt, 6, (void *)0xd);
2052         mtree_test_insert(mt, 5, (void *)0xb);
2053         mtree_test_insert(mt, 1256, (void *)0x9d1);
2054         mtree_test_store(mt, 4, (void *)0x9);
2055         mtree_test_erase(mt, 1);
2056         mtree_test_store(mt, 56, (void *)0x71);
2057         mtree_test_insert(mt, 1, (void *)0x3);
2058         mtree_test_store(mt, 24, (void *)0x31);
2059         mtree_test_erase(mt, 1);
2060         mtree_test_insert(mt, 2263, (void *)0x11af);
2061         mtree_test_insert(mt, 446, (void *)0x37d);
2062         mtree_test_store_range(mt, 6, 45, (void *)0xd);
2063         mtree_test_store_range(mt, 3, 446, (void *)0x7);
2064         mtree_destroy(mt);
2065
2066         /*
2067          * 5. mas_wr_extend_null() may overflow slots.
2068          * Fix by checking against wr_mas->node_end.
2069          */
2070         mt_init_flags(mt, 0);
2071         mtree_test_store(mt, 48, (void *)0x61);
2072         mtree_test_store(mt, 3, (void *)0x7);
2073         mtree_test_load(mt, 0);
2074         mtree_test_store(mt, 88, (void *)0xb1);
2075         mtree_test_store(mt, 81, (void *)0xa3);
2076         mtree_test_insert(mt, 0, (void *)0x1);
2077         mtree_test_insert(mt, 8, (void *)0x11);
2078         mtree_test_insert(mt, 4, (void *)0x9);
2079         mtree_test_insert(mt, 2480, (void *)0x1361);
2080         mtree_test_insert(mt, ULONG_MAX,
2081                           (void *)0xffffffffffffffff);
2082         mtree_test_erase(mt, ULONG_MAX);
2083         mtree_destroy(mt);
2084
2085         /*
2086          * 6.  When reusing a node with an implied pivot and the node is
2087          * shrinking, old data would be left in the implied slot
2088          * Fixed by checking the last pivot for the mas->max and clear
2089          * accordingly.  This only affected the left-most node as that node is
2090          * the only one allowed to end in NULL.
2091          */
2092         mt_init_flags(mt, 0);
2093         mtree_test_erase(mt, 3);
2094         mtree_test_insert(mt, 22, (void *)0x2d);
2095         mtree_test_insert(mt, 15, (void *)0x1f);
2096         mtree_test_load(mt, 2);
2097         mtree_test_insert(mt, 1, (void *)0x3);
2098         mtree_test_insert(mt, 1, (void *)0x3);
2099         mtree_test_insert(mt, 5, (void *)0xb);
2100         mtree_test_erase(mt, 1);
2101         mtree_test_insert(mt, 1, (void *)0x3);
2102         mtree_test_insert(mt, 4, (void *)0x9);
2103         mtree_test_insert(mt, 1, (void *)0x3);
2104         mtree_test_erase(mt, 1);
2105         mtree_test_insert(mt, 2, (void *)0x5);
2106         mtree_test_insert(mt, 1, (void *)0x3);
2107         mtree_test_erase(mt, 3);
2108         mtree_test_insert(mt, 22, (void *)0x2d);
2109         mtree_test_insert(mt, 15, (void *)0x1f);
2110         mtree_test_insert(mt, 2, (void *)0x5);
2111         mtree_test_insert(mt, 1, (void *)0x3);
2112         mtree_test_insert(mt, 8, (void *)0x11);
2113         mtree_test_load(mt, 2);
2114         mtree_test_insert(mt, 1, (void *)0x3);
2115         mtree_test_insert(mt, 1, (void *)0x3);
2116         mtree_test_store(mt, 1, (void *)0x3);
2117         mtree_test_insert(mt, 5, (void *)0xb);
2118         mtree_test_erase(mt, 1);
2119         mtree_test_insert(mt, 1, (void *)0x3);
2120         mtree_test_insert(mt, 4, (void *)0x9);
2121         mtree_test_insert(mt, 1, (void *)0x3);
2122         mtree_test_erase(mt, 1);
2123         mtree_test_insert(mt, 2, (void *)0x5);
2124         mtree_test_insert(mt, 1, (void *)0x3);
2125         mtree_test_erase(mt, 3);
2126         mtree_test_insert(mt, 22, (void *)0x2d);
2127         mtree_test_insert(mt, 15, (void *)0x1f);
2128         mtree_test_insert(mt, 2, (void *)0x5);
2129         mtree_test_insert(mt, 1, (void *)0x3);
2130         mtree_test_insert(mt, 8, (void *)0x11);
2131         mtree_test_insert(mt, 12, (void *)0x19);
2132         mtree_test_erase(mt, 1);
2133         mtree_test_store_range(mt, 4, 62, (void *)0x9);
2134         mtree_test_erase(mt, 62);
2135         mtree_test_store_range(mt, 1, 0, (void *)0x3);
2136         mtree_test_insert(mt, 11, (void *)0x17);
2137         mtree_test_insert(mt, 3, (void *)0x7);
2138         mtree_test_insert(mt, 3, (void *)0x7);
2139         mtree_test_store(mt, 62, (void *)0x7d);
2140         mtree_test_erase(mt, 62);
2141         mtree_test_store_range(mt, 1, 15, (void *)0x3);
2142         mtree_test_erase(mt, 1);
2143         mtree_test_insert(mt, 22, (void *)0x2d);
2144         mtree_test_insert(mt, 12, (void *)0x19);
2145         mtree_test_erase(mt, 1);
2146         mtree_test_insert(mt, 3, (void *)0x7);
2147         mtree_test_store(mt, 62, (void *)0x7d);
2148         mtree_test_erase(mt, 62);
2149         mtree_test_insert(mt, 122, (void *)0xf5);
2150         mtree_test_store(mt, 3, (void *)0x7);
2151         mtree_test_insert(mt, 0, (void *)0x1);
2152         mtree_test_store_range(mt, 0, 1, (void *)0x1);
2153         mtree_test_insert(mt, 85, (void *)0xab);
2154         mtree_test_insert(mt, 72, (void *)0x91);
2155         mtree_test_insert(mt, 81, (void *)0xa3);
2156         mtree_test_insert(mt, 726, (void *)0x5ad);
2157         mtree_test_insert(mt, 0, (void *)0x1);
2158         mtree_test_insert(mt, 1, (void *)0x3);
2159         mtree_test_store(mt, 51, (void *)0x67);
2160         mtree_test_insert(mt, 611, (void *)0x4c7);
2161         mtree_test_insert(mt, 485, (void *)0x3cb);
2162         mtree_test_insert(mt, 1, (void *)0x3);
2163         mtree_test_erase(mt, 1);
2164         mtree_test_insert(mt, 0, (void *)0x1);
2165         mtree_test_insert(mt, 1, (void *)0x3);
2166         mtree_test_insert_range(mt, 26, 1, (void *)0x35);
2167         mtree_test_load(mt, 1);
2168         mtree_test_store_range(mt, 1, 22, (void *)0x3);
2169         mtree_test_insert(mt, 1, (void *)0x3);
2170         mtree_test_erase(mt, 1);
2171         mtree_test_load(mt, 53);
2172         mtree_test_load(mt, 1);
2173         mtree_test_store_range(mt, 1, 1, (void *)0x3);
2174         mtree_test_insert(mt, 222, (void *)0x1bd);
2175         mtree_test_insert(mt, 485, (void *)0x3cb);
2176         mtree_test_insert(mt, 1, (void *)0x3);
2177         mtree_test_erase(mt, 1);
2178         mtree_test_load(mt, 0);
2179         mtree_test_insert(mt, 21, (void *)0x2b);
2180         mtree_test_insert(mt, 3, (void *)0x7);
2181         mtree_test_store(mt, 621, (void *)0x4db);
2182         mtree_test_insert(mt, 0, (void *)0x1);
2183         mtree_test_erase(mt, 5);
2184         mtree_test_insert(mt, 1, (void *)0x3);
2185         mtree_test_store(mt, 62, (void *)0x7d);
2186         mtree_test_erase(mt, 62);
2187         mtree_test_store_range(mt, 1, 0, (void *)0x3);
2188         mtree_test_insert(mt, 22, (void *)0x2d);
2189         mtree_test_insert(mt, 12, (void *)0x19);
2190         mtree_test_erase(mt, 1);
2191         mtree_test_insert(mt, 1, (void *)0x3);
2192         mtree_test_store_range(mt, 4, 62, (void *)0x9);
2193         mtree_test_erase(mt, 62);
2194         mtree_test_erase(mt, 1);
2195         mtree_test_load(mt, 1);
2196         mtree_test_store_range(mt, 1, 22, (void *)0x3);
2197         mtree_test_insert(mt, 1, (void *)0x3);
2198         mtree_test_erase(mt, 1);
2199         mtree_test_load(mt, 53);
2200         mtree_test_load(mt, 1);
2201         mtree_test_store_range(mt, 1, 1, (void *)0x3);
2202         mtree_test_insert(mt, 222, (void *)0x1bd);
2203         mtree_test_insert(mt, 485, (void *)0x3cb);
2204         mtree_test_insert(mt, 1, (void *)0x3);
2205         mtree_test_erase(mt, 1);
2206         mtree_test_insert(mt, 1, (void *)0x3);
2207         mtree_test_load(mt, 0);
2208         mtree_test_load(mt, 0);
2209         mtree_destroy(mt);
2210
2211         /*
2212          * 7. Previous fix was incomplete, fix mas_resuse_node() clearing of old
2213          * data by overwriting it first - that way metadata is of no concern.
2214          */
2215         mt_init_flags(mt, 0);
2216         mtree_test_load(mt, 1);
2217         mtree_test_insert(mt, 102, (void *)0xcd);
2218         mtree_test_erase(mt, 2);
2219         mtree_test_erase(mt, 0);
2220         mtree_test_load(mt, 0);
2221         mtree_test_insert(mt, 4, (void *)0x9);
2222         mtree_test_insert(mt, 2, (void *)0x5);
2223         mtree_test_insert(mt, 110, (void *)0xdd);
2224         mtree_test_insert(mt, 1, (void *)0x3);
2225         mtree_test_insert_range(mt, 5, 0, (void *)0xb);
2226         mtree_test_erase(mt, 2);
2227         mtree_test_store(mt, 0, (void *)0x1);
2228         mtree_test_store(mt, 112, (void *)0xe1);
2229         mtree_test_insert(mt, 21, (void *)0x2b);
2230         mtree_test_store(mt, 1, (void *)0x3);
2231         mtree_test_insert_range(mt, 110, 2, (void *)0xdd);
2232         mtree_test_store(mt, 2, (void *)0x5);
2233         mtree_test_load(mt, 22);
2234         mtree_test_erase(mt, 2);
2235         mtree_test_store(mt, 210, (void *)0x1a5);
2236         mtree_test_store_range(mt, 0, 2, (void *)0x1);
2237         mtree_test_store(mt, 2, (void *)0x5);
2238         mtree_test_erase(mt, 2);
2239         mtree_test_erase(mt, 22);
2240         mtree_test_erase(mt, 1);
2241         mtree_test_erase(mt, 2);
2242         mtree_test_store(mt, 0, (void *)0x1);
2243         mtree_test_load(mt, 112);
2244         mtree_test_insert(mt, 2, (void *)0x5);
2245         mtree_test_erase(mt, 2);
2246         mtree_test_store(mt, 1, (void *)0x3);
2247         mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2248         mtree_test_erase(mt, 0);
2249         mtree_test_erase(mt, 2);
2250         mtree_test_store(mt, 2, (void *)0x5);
2251         mtree_test_erase(mt, 0);
2252         mtree_test_erase(mt, 2);
2253         mtree_test_store(mt, 0, (void *)0x1);
2254         mtree_test_store(mt, 0, (void *)0x1);
2255         mtree_test_erase(mt, 2);
2256         mtree_test_store(mt, 2, (void *)0x5);
2257         mtree_test_erase(mt, 2);
2258         mtree_test_insert(mt, 2, (void *)0x5);
2259         mtree_test_insert_range(mt, 1, 2, (void *)0x3);
2260         mtree_test_erase(mt, 0);
2261         mtree_test_erase(mt, 2);
2262         mtree_test_store(mt, 0, (void *)0x1);
2263         mtree_test_load(mt, 112);
2264         mtree_test_store_range(mt, 110, 12, (void *)0xdd);
2265         mtree_test_store(mt, 2, (void *)0x5);
2266         mtree_test_load(mt, 110);
2267         mtree_test_insert_range(mt, 4, 71, (void *)0x9);
2268         mtree_test_load(mt, 2);
2269         mtree_test_store(mt, 2, (void *)0x5);
2270         mtree_test_insert_range(mt, 11, 22, (void *)0x17);
2271         mtree_test_erase(mt, 12);
2272         mtree_test_store(mt, 2, (void *)0x5);
2273         mtree_test_load(mt, 22);
2274         mtree_destroy(mt);
2275
2276
2277         /*
2278          * 8.  When rebalancing or spanning_rebalance(), the max of the new node
2279          * may be set incorrectly to the final pivot and not the right max.
2280          * Fix by setting the left max to orig right max if the entire node is
2281          * consumed.
2282          */
2283         mt_init_flags(mt, 0);
2284         mtree_test_store(mt, 6, (void *)0xd);
2285         mtree_test_store(mt, 67, (void *)0x87);
2286         mtree_test_insert(mt, 15, (void *)0x1f);
2287         mtree_test_insert(mt, 6716, (void *)0x3479);
2288         mtree_test_store(mt, 61, (void *)0x7b);
2289         mtree_test_insert(mt, 13, (void *)0x1b);
2290         mtree_test_store(mt, 8, (void *)0x11);
2291         mtree_test_insert(mt, 1, (void *)0x3);
2292         mtree_test_load(mt, 0);
2293         mtree_test_erase(mt, 67167);
2294         mtree_test_insert_range(mt, 6, 7167, (void *)0xd);
2295         mtree_test_insert(mt, 6, (void *)0xd);
2296         mtree_test_erase(mt, 67);
2297         mtree_test_insert(mt, 1, (void *)0x3);
2298         mtree_test_erase(mt, 667167);
2299         mtree_test_insert(mt, 6, (void *)0xd);
2300         mtree_test_store(mt, 67, (void *)0x87);
2301         mtree_test_insert(mt, 5, (void *)0xb);
2302         mtree_test_erase(mt, 1);
2303         mtree_test_insert(mt, 6, (void *)0xd);
2304         mtree_test_erase(mt, 67);
2305         mtree_test_insert(mt, 15, (void *)0x1f);
2306         mtree_test_insert(mt, 67167, (void *)0x20cbf);
2307         mtree_test_insert(mt, 1, (void *)0x3);
2308         mtree_test_load(mt, 7);
2309         mtree_test_insert(mt, 16, (void *)0x21);
2310         mtree_test_insert(mt, 36, (void *)0x49);
2311         mtree_test_store(mt, 67, (void *)0x87);
2312         mtree_test_store(mt, 6, (void *)0xd);
2313         mtree_test_insert(mt, 367, (void *)0x2df);
2314         mtree_test_insert(mt, 115, (void *)0xe7);
2315         mtree_test_store(mt, 0, (void *)0x1);
2316         mtree_test_store_range(mt, 1, 3, (void *)0x3);
2317         mtree_test_store(mt, 1, (void *)0x3);
2318         mtree_test_erase(mt, 67167);
2319         mtree_test_insert_range(mt, 6, 47, (void *)0xd);
2320         mtree_test_store(mt, 1, (void *)0x3);
2321         mtree_test_insert_range(mt, 1, 67, (void *)0x3);
2322         mtree_test_load(mt, 67);
2323         mtree_test_insert(mt, 1, (void *)0x3);
2324         mtree_test_erase(mt, 67167);
2325         mtree_destroy(mt);
2326
2327         /*
2328          * 9. spanning store to the end of data caused an invalid metadata
2329          * length which resulted in a crash eventually.
2330          * Fix by checking if there is a value in pivot before incrementing the
2331          * metadata end in mab_mas_cp().  To ensure this doesn't happen again,
2332          * abstract the two locations this happens into a function called
2333          * mas_leaf_set_meta().
2334          */
2335         mt_init_flags(mt, 0);
2336         mtree_test_insert(mt, 21, (void *)0x2b);
2337         mtree_test_insert(mt, 12, (void *)0x19);
2338         mtree_test_insert(mt, 6, (void *)0xd);
2339         mtree_test_insert(mt, 8, (void *)0x11);
2340         mtree_test_insert(mt, 2, (void *)0x5);
2341         mtree_test_insert(mt, 91, (void *)0xb7);
2342         mtree_test_insert(mt, 18, (void *)0x25);
2343         mtree_test_insert(mt, 81, (void *)0xa3);
2344         mtree_test_store_range(mt, 0, 128, (void *)0x1);
2345         mtree_test_store(mt, 1, (void *)0x3);
2346         mtree_test_erase(mt, 8);
2347         mtree_test_insert(mt, 11, (void *)0x17);
2348         mtree_test_insert(mt, 8, (void *)0x11);
2349         mtree_test_insert(mt, 21, (void *)0x2b);
2350         mtree_test_insert(mt, 2, (void *)0x5);
2351         mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2352         mtree_test_erase(mt, ULONG_MAX - 10);
2353         mtree_test_store_range(mt, 0, 281, (void *)0x1);
2354         mtree_test_erase(mt, 2);
2355         mtree_test_insert(mt, 1211, (void *)0x977);
2356         mtree_test_insert(mt, 111, (void *)0xdf);
2357         mtree_test_insert(mt, 13, (void *)0x1b);
2358         mtree_test_insert(mt, 211, (void *)0x1a7);
2359         mtree_test_insert(mt, 11, (void *)0x17);
2360         mtree_test_insert(mt, 5, (void *)0xb);
2361         mtree_test_insert(mt, 1218, (void *)0x985);
2362         mtree_test_insert(mt, 61, (void *)0x7b);
2363         mtree_test_store(mt, 1, (void *)0x3);
2364         mtree_test_insert(mt, 121, (void *)0xf3);
2365         mtree_test_insert(mt, 8, (void *)0x11);
2366         mtree_test_insert(mt, 21, (void *)0x2b);
2367         mtree_test_insert(mt, 2, (void *)0x5);
2368         mtree_test_insert(mt, ULONG_MAX - 10, (void *)0xffffffffffffffeb);
2369         mtree_test_erase(mt, ULONG_MAX - 10);
2370 }
2371
2372 /* duplicate the tree with a specific gap */
2373 static noinline void check_dup_gaps(struct maple_tree *mt,
2374                                     unsigned long nr_entries, bool zero_start,
2375                                     unsigned long gap)
2376 {
2377         unsigned long i = 0;
2378         struct maple_tree newmt;
2379         int ret;
2380         void *tmp;
2381         MA_STATE(mas, mt, 0, 0);
2382         MA_STATE(newmas, &newmt, 0, 0);
2383
2384         if (!zero_start)
2385                 i = 1;
2386
2387         mt_zero_nr_tallocated();
2388         for (; i <= nr_entries; i++)
2389                 mtree_store_range(mt, i*10, (i+1)*10 - gap,
2390                                   xa_mk_value(i), GFP_KERNEL);
2391
2392         mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
2393         mt_set_non_kernel(99999);
2394         mas_lock(&newmas);
2395         ret = mas_expected_entries(&newmas, nr_entries);
2396         mt_set_non_kernel(0);
2397         MT_BUG_ON(mt, ret != 0);
2398
2399         rcu_read_lock();
2400         mas_for_each(&mas, tmp, ULONG_MAX) {
2401                 newmas.index = mas.index;
2402                 newmas.last = mas.last;
2403                 mas_store(&newmas, tmp);
2404         }
2405         rcu_read_unlock();
2406         mas_destroy(&newmas);
2407         mas_unlock(&newmas);
2408
2409         mtree_destroy(&newmt);
2410 }
2411
2412 /* Duplicate many sizes of trees.  Mainly to test expected entry values */
2413 static noinline void check_dup(struct maple_tree *mt)
2414 {
2415         int i;
2416         int big_start = 100010;
2417
2418         /* Check with a value at zero */
2419         for (i = 10; i < 1000; i++) {
2420                 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2421                 check_dup_gaps(mt, i, true, 5);
2422                 mtree_destroy(mt);
2423                 rcu_barrier();
2424         }
2425
2426         cond_resched();
2427         mt_cache_shrink();
2428         /* Check with a value at zero, no gap */
2429         for (i = 1000; i < 2000; i++) {
2430                 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2431                 check_dup_gaps(mt, i, true, 0);
2432                 mtree_destroy(mt);
2433                 rcu_barrier();
2434         }
2435
2436         cond_resched();
2437         mt_cache_shrink();
2438         /* Check with a value at zero and unreasonably large */
2439         for (i = big_start; i < big_start + 10; i++) {
2440                 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2441                 check_dup_gaps(mt, i, true, 5);
2442                 mtree_destroy(mt);
2443                 rcu_barrier();
2444         }
2445
2446         cond_resched();
2447         mt_cache_shrink();
2448         /* Small to medium size not starting at zero*/
2449         for (i = 200; i < 1000; i++) {
2450                 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2451                 check_dup_gaps(mt, i, false, 5);
2452                 mtree_destroy(mt);
2453                 rcu_barrier();
2454         }
2455
2456         cond_resched();
2457         mt_cache_shrink();
2458         /* Unreasonably large not starting at zero*/
2459         for (i = big_start; i < big_start + 10; i++) {
2460                 mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
2461                 check_dup_gaps(mt, i, false, 5);
2462                 mtree_destroy(mt);
2463                 rcu_barrier();
2464                 cond_resched();
2465                 mt_cache_shrink();
2466         }
2467
2468         /* Check non-allocation tree not starting at zero */
2469         for (i = 1500; i < 3000; i++) {
2470                 mt_init_flags(mt, 0);
2471                 check_dup_gaps(mt, i, false, 5);
2472                 mtree_destroy(mt);
2473                 rcu_barrier();
2474                 cond_resched();
2475                 if (i % 2 == 0)
2476                         mt_cache_shrink();
2477         }
2478
2479         mt_cache_shrink();
2480         /* Check non-allocation tree starting at zero */
2481         for (i = 200; i < 1000; i++) {
2482                 mt_init_flags(mt, 0);
2483                 check_dup_gaps(mt, i, true, 5);
2484                 mtree_destroy(mt);
2485                 rcu_barrier();
2486                 cond_resched();
2487         }
2488
2489         mt_cache_shrink();
2490         /* Unreasonably large */
2491         for (i = big_start + 5; i < big_start + 10; i++) {
2492                 mt_init_flags(mt, 0);
2493                 check_dup_gaps(mt, i, true, 5);
2494                 mtree_destroy(mt);
2495                 rcu_barrier();
2496                 mt_cache_shrink();
2497                 cond_resched();
2498         }
2499 }
2500
2501 static noinline void check_bnode_min_spanning(struct maple_tree *mt)
2502 {
2503         int i = 50;
2504         MA_STATE(mas, mt, 0, 0);
2505
2506         mt_set_non_kernel(9999);
2507         mas_lock(&mas);
2508         do {
2509                 mas_set_range(&mas, i*10, i*10+9);
2510                 mas_store(&mas, check_bnode_min_spanning);
2511         } while (i--);
2512
2513         mas_set_range(&mas, 240, 509);
2514         mas_store(&mas, NULL);
2515         mas_unlock(&mas);
2516         mas_destroy(&mas);
2517         mt_set_non_kernel(0);
2518 }
2519
2520 static DEFINE_MTREE(tree);
2521 static int maple_tree_seed(void)
2522 {
2523         unsigned long set[] = {5015, 5014, 5017, 25, 1000,
2524                                1001, 1002, 1003, 1005, 0,
2525                                5003, 5002};
2526         void *ptr = &set;
2527
2528         pr_info("\nTEST STARTING\n\n");
2529
2530         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2531         check_root_expand(&tree);
2532         mtree_destroy(&tree);
2533
2534 #if defined(BENCH_SLOT_STORE)
2535 #define BENCH
2536         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2537         bench_slot_store(&tree);
2538         mtree_destroy(&tree);
2539         goto skip;
2540 #endif
2541 #if defined(BENCH_NODE_STORE)
2542 #define BENCH
2543         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2544         bench_node_store(&tree);
2545         mtree_destroy(&tree);
2546         goto skip;
2547 #endif
2548 #if defined(BENCH_AWALK)
2549 #define BENCH
2550         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2551         bench_awalk(&tree);
2552         mtree_destroy(&tree);
2553         goto skip;
2554 #endif
2555 #if defined(BENCH_WALK)
2556 #define BENCH
2557         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2558         bench_walk(&tree);
2559         mtree_destroy(&tree);
2560         goto skip;
2561 #endif
2562 #if defined(BENCH_FORK)
2563 #define BENCH
2564         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2565         bench_forking(&tree);
2566         mtree_destroy(&tree);
2567         goto skip;
2568 #endif
2569 #if defined(BENCH_MT_FOR_EACH)
2570 #define BENCH
2571         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2572         bench_mt_for_each(&tree);
2573         mtree_destroy(&tree);
2574         goto skip;
2575 #endif
2576
2577         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2578         check_forking(&tree);
2579         mtree_destroy(&tree);
2580
2581         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2582         check_mas_store_gfp(&tree);
2583         mtree_destroy(&tree);
2584
2585         /* Test ranges (store and insert) */
2586         mt_init_flags(&tree, 0);
2587         check_ranges(&tree);
2588         mtree_destroy(&tree);
2589
2590 #if defined(CONFIG_64BIT)
2591         /* These tests have ranges outside of 4GB */
2592         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2593         check_alloc_range(&tree);
2594         mtree_destroy(&tree);
2595
2596         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2597         check_alloc_rev_range(&tree);
2598         mtree_destroy(&tree);
2599 #endif
2600
2601         mt_init_flags(&tree, 0);
2602
2603         check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
2604
2605         check_insert(&tree, set[9], &tree);     /* Insert 0 */
2606         check_load(&tree, set[9], &tree);       /* See if 0 -> &tree */
2607         check_load(&tree, set[0], NULL);       /* See if 5015 -> NULL */
2608
2609         check_insert(&tree, set[10], ptr);      /* Insert 5003 */
2610         check_load(&tree, set[9], &tree);       /* See if 0 -> &tree */
2611         check_load(&tree, set[11], NULL);       /* See if 5002 -> NULL */
2612         check_load(&tree, set[10], ptr);       /* See if 5003 -> ptr */
2613
2614         /* Clear out the tree */
2615         mtree_destroy(&tree);
2616
2617         /* Try to insert, insert a dup, and load back what was inserted. */
2618         mt_init_flags(&tree, 0);
2619         check_insert(&tree, set[0], &tree);     /* Insert 5015 */
2620         check_dup_insert(&tree, set[0], &tree); /* Insert 5015 again */
2621         check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
2622
2623         /*
2624          * Second set of tests try to load a value that doesn't exist, inserts
2625          * a second value, then loads the value again
2626          */
2627         check_load(&tree, set[1], NULL);        /* See if 5014 -> NULL */
2628         check_insert(&tree, set[1], ptr);       /* insert 5014 -> ptr */
2629         check_load(&tree, set[1], ptr);         /* See if 5014 -> ptr */
2630         check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
2631         /*
2632          * Tree currently contains:
2633          * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil)
2634          */
2635         check_insert(&tree, set[6], ptr);       /* insert 1002 -> ptr */
2636         check_insert(&tree, set[7], &tree);       /* insert 1003 -> &tree */
2637
2638         check_load(&tree, set[0], &tree);       /* See if 5015 -> &tree */
2639         check_load(&tree, set[1], ptr);         /* See if 5014 -> ptr */
2640         check_load(&tree, set[6], ptr);         /* See if 1002 -> ptr */
2641         check_load(&tree, set[7], &tree);       /* 1003 = &tree ? */
2642
2643         /* Clear out tree */
2644         mtree_destroy(&tree);
2645
2646         mt_init_flags(&tree, 0);
2647         /* Test inserting into a NULL hole. */
2648         check_insert(&tree, set[5], ptr);       /* insert 1001 -> ptr */
2649         check_insert(&tree, set[7], &tree);       /* insert 1003 -> &tree */
2650         check_insert(&tree, set[6], ptr);       /* insert 1002 -> ptr */
2651         check_load(&tree, set[5], ptr);         /* See if 1001 -> ptr */
2652         check_load(&tree, set[6], ptr);         /* See if 1002 -> ptr */
2653         check_load(&tree, set[7], &tree);       /* See if 1003 -> &tree */
2654
2655         /* Clear out the tree */
2656         mtree_destroy(&tree);
2657
2658         mt_init_flags(&tree, 0);
2659         /*
2660          *       set[] = {5015, 5014, 5017, 25, 1000,
2661          *                1001, 1002, 1003, 1005, 0,
2662          *                5003, 5002};
2663          */
2664
2665         check_insert(&tree, set[0], ptr); /* 5015 */
2666         check_insert(&tree, set[1], &tree); /* 5014 */
2667         check_insert(&tree, set[2], ptr); /* 5017 */
2668         check_insert(&tree, set[3], &tree); /* 25 */
2669         check_load(&tree, set[0], ptr);
2670         check_load(&tree, set[1], &tree);
2671         check_load(&tree, set[2], ptr);
2672         check_load(&tree, set[3], &tree);
2673         check_insert(&tree, set[4], ptr); /* 1000 < Should split. */
2674         check_load(&tree, set[0], ptr);
2675         check_load(&tree, set[1], &tree);
2676         check_load(&tree, set[2], ptr);
2677         check_load(&tree, set[3], &tree); /*25 */
2678         check_load(&tree, set[4], ptr);
2679         check_insert(&tree, set[5], &tree); /* 1001 */
2680         check_load(&tree, set[0], ptr);
2681         check_load(&tree, set[1], &tree);
2682         check_load(&tree, set[2], ptr);
2683         check_load(&tree, set[3], &tree);
2684         check_load(&tree, set[4], ptr);
2685         check_load(&tree, set[5], &tree);
2686         check_insert(&tree, set[6], ptr);
2687         check_load(&tree, set[0], ptr);
2688         check_load(&tree, set[1], &tree);
2689         check_load(&tree, set[2], ptr);
2690         check_load(&tree, set[3], &tree);
2691         check_load(&tree, set[4], ptr);
2692         check_load(&tree, set[5], &tree);
2693         check_load(&tree, set[6], ptr);
2694         check_insert(&tree, set[7], &tree);
2695         check_load(&tree, set[0], ptr);
2696         check_insert(&tree, set[8], ptr);
2697
2698         check_insert(&tree, set[9], &tree);
2699
2700         check_load(&tree, set[0], ptr);
2701         check_load(&tree, set[1], &tree);
2702         check_load(&tree, set[2], ptr);
2703         check_load(&tree, set[3], &tree);
2704         check_load(&tree, set[4], ptr);
2705         check_load(&tree, set[5], &tree);
2706         check_load(&tree, set[6], ptr);
2707         check_load(&tree, set[9], &tree);
2708         mtree_destroy(&tree);
2709
2710         mt_init_flags(&tree, 0);
2711         check_seq(&tree, 16, false);
2712         mtree_destroy(&tree);
2713
2714         mt_init_flags(&tree, 0);
2715         check_seq(&tree, 1000, true);
2716         mtree_destroy(&tree);
2717
2718         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2719         check_rev_seq(&tree, 1000, true);
2720         mtree_destroy(&tree);
2721
2722         check_lower_bound_split(&tree);
2723         check_upper_bound_split(&tree);
2724         check_mid_split(&tree);
2725
2726         mt_init_flags(&tree, 0);
2727         check_next_entry(&tree);
2728         check_find(&tree);
2729         check_find_2(&tree);
2730         mtree_destroy(&tree);
2731
2732         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2733         check_prev_entry(&tree);
2734         mtree_destroy(&tree);
2735
2736         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2737         check_gap_combining(&tree);
2738         mtree_destroy(&tree);
2739
2740         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2741         check_node_overwrite(&tree);
2742         mtree_destroy(&tree);
2743
2744         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2745         next_prev_test(&tree);
2746         mtree_destroy(&tree);
2747
2748         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2749         check_spanning_relatives(&tree);
2750         mtree_destroy(&tree);
2751
2752         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2753         check_rev_find(&tree);
2754         mtree_destroy(&tree);
2755
2756         mt_init_flags(&tree, 0);
2757         check_fuzzer(&tree);
2758         mtree_destroy(&tree);
2759
2760         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2761         check_dup(&tree);
2762         mtree_destroy(&tree);
2763
2764         mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
2765         check_bnode_min_spanning(&tree);
2766         mtree_destroy(&tree);
2767
2768 #if defined(BENCH)
2769 skip:
2770 #endif
2771         rcu_barrier();
2772         pr_info("maple_tree: %u of %u tests passed\n",
2773                         atomic_read(&maple_tree_tests_passed),
2774                         atomic_read(&maple_tree_tests_run));
2775         if (atomic_read(&maple_tree_tests_run) ==
2776             atomic_read(&maple_tree_tests_passed))
2777                 return 0;
2778
2779         return -EINVAL;
2780 }
2781
2782 static void maple_tree_harvest(void)
2783 {
2784
2785 }
2786
2787 module_init(maple_tree_seed);
2788 module_exit(maple_tree_harvest);
2789 MODULE_AUTHOR("Liam R. Howlett <Liam.Howlett@Oracle.com>");
2790 MODULE_LICENSE("GPL");