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