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