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