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