1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Test cases for the drm_mm range manager 4 * 5 * Copyright (c) 2022 Arthur Grillo <arthur.grillo@usp.br> 6 */ 7 8 #include <kunit/test.h> 9 10 #include <linux/prime_numbers.h> 11 #include <linux/slab.h> 12 #include <linux/random.h> 13 #include <linux/vmalloc.h> 14 #include <linux/ktime.h> 15 16 #include <drm/drm_mm.h> 17 18 #include "../lib/drm_random.h" 19 20 static unsigned int random_seed; 21 static unsigned int max_iterations = 8192; 22 static unsigned int max_prime = 128; 23 24 enum { 25 BEST, 26 BOTTOMUP, 27 TOPDOWN, 28 EVICT, 29 }; 30 31 static const struct insert_mode { 32 const char *name; 33 enum drm_mm_insert_mode mode; 34 } insert_modes[] = { 35 [BEST] = { "best", DRM_MM_INSERT_BEST }, 36 [BOTTOMUP] = { "bottom-up", DRM_MM_INSERT_LOW }, 37 [TOPDOWN] = { "top-down", DRM_MM_INSERT_HIGH }, 38 [EVICT] = { "evict", DRM_MM_INSERT_EVICT }, 39 {} 40 }, evict_modes[] = { 41 { "bottom-up", DRM_MM_INSERT_LOW }, 42 { "top-down", DRM_MM_INSERT_HIGH }, 43 {} 44 }; 45 46 static bool assert_no_holes(struct kunit *test, const struct drm_mm *mm) 47 { 48 struct drm_mm_node *hole; 49 u64 hole_start, __always_unused hole_end; 50 unsigned long count; 51 52 count = 0; 53 drm_mm_for_each_hole(hole, mm, hole_start, hole_end) 54 count++; 55 if (count) { 56 KUNIT_FAIL(test, 57 "Expected to find no holes (after reserve), found %lu instead\n", count); 58 return false; 59 } 60 61 drm_mm_for_each_node(hole, mm) { 62 if (drm_mm_hole_follows(hole)) { 63 KUNIT_FAIL(test, "Hole follows node, expected none!\n"); 64 return false; 65 } 66 } 67 68 return true; 69 } 70 71 static bool assert_one_hole(struct kunit *test, const struct drm_mm *mm, u64 start, u64 end) 72 { 73 struct drm_mm_node *hole; 74 u64 hole_start, hole_end; 75 unsigned long count; 76 bool ok = true; 77 78 if (end <= start) 79 return true; 80 81 count = 0; 82 drm_mm_for_each_hole(hole, mm, hole_start, hole_end) { 83 if (start != hole_start || end != hole_end) { 84 if (ok) 85 KUNIT_FAIL(test, 86 "empty mm has incorrect hole, found (%llx, %llx), expect (%llx, %llx)\n", 87 hole_start, hole_end, start, end); 88 ok = false; 89 } 90 count++; 91 } 92 if (count != 1) { 93 KUNIT_FAIL(test, "Expected to find one hole, found %lu instead\n", count); 94 ok = false; 95 } 96 97 return ok; 98 } 99 100 static bool assert_continuous(struct kunit *test, const struct drm_mm *mm, u64 size) 101 { 102 struct drm_mm_node *node, *check, *found; 103 unsigned long n; 104 u64 addr; 105 106 if (!assert_no_holes(test, mm)) 107 return false; 108 109 n = 0; 110 addr = 0; 111 drm_mm_for_each_node(node, mm) { 112 if (node->start != addr) { 113 KUNIT_FAIL(test, "node[%ld] list out of order, expected %llx found %llx\n", 114 n, addr, node->start); 115 return false; 116 } 117 118 if (node->size != size) { 119 KUNIT_FAIL(test, "node[%ld].size incorrect, expected %llx, found %llx\n", 120 n, size, node->size); 121 return false; 122 } 123 124 if (drm_mm_hole_follows(node)) { 125 KUNIT_FAIL(test, "node[%ld] is followed by a hole!\n", n); 126 return false; 127 } 128 129 found = NULL; 130 drm_mm_for_each_node_in_range(check, mm, addr, addr + size) { 131 if (node != check) { 132 KUNIT_FAIL(test, 133 "lookup return wrong node, expected start %llx, found %llx\n", 134 node->start, check->start); 135 return false; 136 } 137 found = check; 138 } 139 if (!found) { 140 KUNIT_FAIL(test, "lookup failed for node %llx + %llx\n", addr, size); 141 return false; 142 } 143 144 addr += size; 145 n++; 146 } 147 148 return true; 149 } 150 151 static u64 misalignment(struct drm_mm_node *node, u64 alignment) 152 { 153 u64 rem; 154 155 if (!alignment) 156 return 0; 157 158 div64_u64_rem(node->start, alignment, &rem); 159 return rem; 160 } 161 162 static bool assert_node(struct kunit *test, struct drm_mm_node *node, struct drm_mm *mm, 163 u64 size, u64 alignment, unsigned long color) 164 { 165 bool ok = true; 166 167 if (!drm_mm_node_allocated(node) || node->mm != mm) { 168 KUNIT_FAIL(test, "node not allocated\n"); 169 ok = false; 170 } 171 172 if (node->size != size) { 173 KUNIT_FAIL(test, "node has wrong size, found %llu, expected %llu\n", 174 node->size, size); 175 ok = false; 176 } 177 178 if (misalignment(node, alignment)) { 179 KUNIT_FAIL(test, 180 "node is misaligned, start %llx rem %llu, expected alignment %llu\n", 181 node->start, misalignment(node, alignment), alignment); 182 ok = false; 183 } 184 185 if (node->color != color) { 186 KUNIT_FAIL(test, "node has wrong color, found %lu, expected %lu\n", 187 node->color, color); 188 ok = false; 189 } 190 191 return ok; 192 } 193 194 static void igt_mm_init(struct kunit *test) 195 { 196 const unsigned int size = 4096; 197 struct drm_mm mm; 198 struct drm_mm_node tmp; 199 200 /* Start with some simple checks on initialising the struct drm_mm */ 201 memset(&mm, 0, sizeof(mm)); 202 KUNIT_ASSERT_FALSE_MSG(test, drm_mm_initialized(&mm), 203 "zeroed mm claims to be initialized\n"); 204 205 memset(&mm, 0xff, sizeof(mm)); 206 drm_mm_init(&mm, 0, size); 207 if (!drm_mm_initialized(&mm)) { 208 KUNIT_FAIL(test, "mm claims not to be initialized\n"); 209 goto out; 210 } 211 212 if (!drm_mm_clean(&mm)) { 213 KUNIT_FAIL(test, "mm not empty on creation\n"); 214 goto out; 215 } 216 217 /* After creation, it should all be one massive hole */ 218 if (!assert_one_hole(test, &mm, 0, size)) { 219 KUNIT_FAIL(test, ""); 220 goto out; 221 } 222 223 memset(&tmp, 0, sizeof(tmp)); 224 tmp.start = 0; 225 tmp.size = size; 226 if (drm_mm_reserve_node(&mm, &tmp)) { 227 KUNIT_FAIL(test, "failed to reserve whole drm_mm\n"); 228 goto out; 229 } 230 231 /* After filling the range entirely, there should be no holes */ 232 if (!assert_no_holes(test, &mm)) { 233 KUNIT_FAIL(test, ""); 234 goto out; 235 } 236 237 /* And then after emptying it again, the massive hole should be back */ 238 drm_mm_remove_node(&tmp); 239 if (!assert_one_hole(test, &mm, 0, size)) { 240 KUNIT_FAIL(test, ""); 241 goto out; 242 } 243 244 out: 245 drm_mm_takedown(&mm); 246 } 247 248 static void igt_mm_debug(struct kunit *test) 249 { 250 struct drm_mm mm; 251 struct drm_mm_node nodes[2]; 252 253 /* Create a small drm_mm with a couple of nodes and a few holes, and 254 * check that the debug iterator doesn't explode over a trivial drm_mm. 255 */ 256 257 drm_mm_init(&mm, 0, 4096); 258 259 memset(nodes, 0, sizeof(nodes)); 260 nodes[0].start = 512; 261 nodes[0].size = 1024; 262 KUNIT_ASSERT_FALSE_MSG(test, drm_mm_reserve_node(&mm, &nodes[0]), 263 "failed to reserve node[0] {start=%lld, size=%lld)\n", 264 nodes[0].start, nodes[0].size); 265 266 nodes[1].size = 1024; 267 nodes[1].start = 4096 - 512 - nodes[1].size; 268 KUNIT_ASSERT_FALSE_MSG(test, drm_mm_reserve_node(&mm, &nodes[1]), 269 "failed to reserve node[0] {start=%lld, size=%lld)\n", 270 nodes[0].start, nodes[0].size); 271 } 272 273 static struct drm_mm_node *set_node(struct drm_mm_node *node, 274 u64 start, u64 size) 275 { 276 node->start = start; 277 node->size = size; 278 return node; 279 } 280 281 static bool expect_reserve_fail(struct kunit *test, struct drm_mm *mm, struct drm_mm_node *node) 282 { 283 int err; 284 285 err = drm_mm_reserve_node(mm, node); 286 if (likely(err == -ENOSPC)) 287 return true; 288 289 if (!err) { 290 KUNIT_FAIL(test, "impossible reserve succeeded, node %llu + %llu\n", 291 node->start, node->size); 292 drm_mm_remove_node(node); 293 } else { 294 KUNIT_FAIL(test, 295 "impossible reserve failed with wrong error %d [expected %d], node %llu + %llu\n", 296 err, -ENOSPC, node->start, node->size); 297 } 298 return false; 299 } 300 301 static bool check_reserve_boundaries(struct kunit *test, struct drm_mm *mm, 302 unsigned int count, 303 u64 size) 304 { 305 const struct boundary { 306 u64 start, size; 307 const char *name; 308 } boundaries[] = { 309 #define B(st, sz) { (st), (sz), "{ " #st ", " #sz "}" } 310 B(0, 0), 311 B(-size, 0), 312 B(size, 0), 313 B(size * count, 0), 314 B(-size, size), 315 B(-size, -size), 316 B(-size, 2 * size), 317 B(0, -size), 318 B(size, -size), 319 B(count * size, size), 320 B(count * size, -size), 321 B(count * size, count * size), 322 B(count * size, -count * size), 323 B(count * size, -(count + 1) * size), 324 B((count + 1) * size, size), 325 B((count + 1) * size, -size), 326 B((count + 1) * size, -2 * size), 327 #undef B 328 }; 329 struct drm_mm_node tmp = {}; 330 int n; 331 332 for (n = 0; n < ARRAY_SIZE(boundaries); n++) { 333 if (!expect_reserve_fail(test, mm, set_node(&tmp, boundaries[n].start, 334 boundaries[n].size))) { 335 KUNIT_FAIL(test, "boundary[%d:%s] failed, count=%u, size=%lld\n", 336 n, boundaries[n].name, count, size); 337 return false; 338 } 339 } 340 341 return true; 342 } 343 344 static int __igt_reserve(struct kunit *test, unsigned int count, u64 size) 345 { 346 DRM_RND_STATE(prng, random_seed); 347 struct drm_mm mm; 348 struct drm_mm_node tmp, *nodes, *node, *next; 349 unsigned int *order, n, m, o = 0; 350 int ret, err; 351 352 /* For exercising drm_mm_reserve_node(struct kunit *test, ), we want to check that 353 * reservations outside of the drm_mm range are rejected, and to 354 * overlapping and otherwise already occupied ranges. Afterwards, 355 * the tree and nodes should be intact. 356 */ 357 358 DRM_MM_BUG_ON(!count); 359 DRM_MM_BUG_ON(!size); 360 361 ret = -ENOMEM; 362 order = drm_random_order(count, &prng); 363 if (!order) 364 goto err; 365 366 nodes = vzalloc(array_size(count, sizeof(*nodes))); 367 KUNIT_ASSERT_TRUE(test, nodes); 368 369 ret = -EINVAL; 370 drm_mm_init(&mm, 0, count * size); 371 372 if (!check_reserve_boundaries(test, &mm, count, size)) 373 goto out; 374 375 for (n = 0; n < count; n++) { 376 nodes[n].start = order[n] * size; 377 nodes[n].size = size; 378 379 err = drm_mm_reserve_node(&mm, &nodes[n]); 380 if (err) { 381 KUNIT_FAIL(test, "reserve failed, step %d, start %llu\n", 382 n, nodes[n].start); 383 ret = err; 384 goto out; 385 } 386 387 if (!drm_mm_node_allocated(&nodes[n])) { 388 KUNIT_FAIL(test, "reserved node not allocated! step %d, start %llu\n", 389 n, nodes[n].start); 390 goto out; 391 } 392 393 if (!expect_reserve_fail(test, &mm, &nodes[n])) 394 goto out; 395 } 396 397 /* After random insertion the nodes should be in order */ 398 if (!assert_continuous(test, &mm, size)) 399 goto out; 400 401 /* Repeated use should then fail */ 402 drm_random_reorder(order, count, &prng); 403 for (n = 0; n < count; n++) { 404 if (!expect_reserve_fail(test, &mm, set_node(&tmp, order[n] * size, 1))) 405 goto out; 406 407 /* Remove and reinsert should work */ 408 drm_mm_remove_node(&nodes[order[n]]); 409 err = drm_mm_reserve_node(&mm, &nodes[order[n]]); 410 if (err) { 411 KUNIT_FAIL(test, "reserve failed, step %d, start %llu\n", 412 n, nodes[n].start); 413 ret = err; 414 goto out; 415 } 416 } 417 418 if (!assert_continuous(test, &mm, size)) 419 goto out; 420 421 /* Overlapping use should then fail */ 422 for (n = 0; n < count; n++) { 423 if (!expect_reserve_fail(test, &mm, set_node(&tmp, 0, size * count))) 424 goto out; 425 } 426 for (n = 0; n < count; n++) { 427 if (!expect_reserve_fail(test, &mm, set_node(&tmp, size * n, size * (count - n)))) 428 goto out; 429 } 430 431 /* Remove several, reinsert, check full */ 432 for_each_prime_number(n, min(max_prime, count)) { 433 for (m = 0; m < n; m++) { 434 node = &nodes[order[(o + m) % count]]; 435 drm_mm_remove_node(node); 436 } 437 438 for (m = 0; m < n; m++) { 439 node = &nodes[order[(o + m) % count]]; 440 err = drm_mm_reserve_node(&mm, node); 441 if (err) { 442 KUNIT_FAIL(test, "reserve failed, step %d/%d, start %llu\n", 443 m, n, node->start); 444 ret = err; 445 goto out; 446 } 447 } 448 449 o += n; 450 451 if (!assert_continuous(test, &mm, size)) 452 goto out; 453 } 454 455 ret = 0; 456 out: 457 drm_mm_for_each_node_safe(node, next, &mm) 458 drm_mm_remove_node(node); 459 drm_mm_takedown(&mm); 460 vfree(nodes); 461 kfree(order); 462 err: 463 return ret; 464 } 465 466 static void igt_mm_reserve(struct kunit *test) 467 { 468 const unsigned int count = min_t(unsigned int, BIT(10), max_iterations); 469 int n; 470 471 for_each_prime_number_from(n, 1, 54) { 472 u64 size = BIT_ULL(n); 473 474 KUNIT_ASSERT_FALSE(test, __igt_reserve(test, count, size - 1)); 475 KUNIT_ASSERT_FALSE(test, __igt_reserve(test, count, size)); 476 KUNIT_ASSERT_FALSE(test, __igt_reserve(test, count, size + 1)); 477 478 cond_resched(); 479 } 480 } 481 482 static bool expect_insert(struct kunit *test, struct drm_mm *mm, 483 struct drm_mm_node *node, u64 size, u64 alignment, unsigned long color, 484 const struct insert_mode *mode) 485 { 486 int err; 487 488 err = drm_mm_insert_node_generic(mm, node, 489 size, alignment, color, 490 mode->mode); 491 if (err) { 492 KUNIT_FAIL(test, 493 "insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n", 494 size, alignment, color, mode->name, err); 495 return false; 496 } 497 498 if (!assert_node(test, node, mm, size, alignment, color)) { 499 drm_mm_remove_node(node); 500 return false; 501 } 502 503 return true; 504 } 505 506 static bool expect_insert_fail(struct kunit *test, struct drm_mm *mm, u64 size) 507 { 508 struct drm_mm_node tmp = {}; 509 int err; 510 511 err = drm_mm_insert_node(mm, &tmp, size); 512 if (likely(err == -ENOSPC)) 513 return true; 514 515 if (!err) { 516 KUNIT_FAIL(test, "impossible insert succeeded, node %llu + %llu\n", 517 tmp.start, tmp.size); 518 drm_mm_remove_node(&tmp); 519 } else { 520 KUNIT_FAIL(test, 521 "impossible insert failed with wrong error %d [expected %d], size %llu\n", 522 err, -ENOSPC, size); 523 } 524 return false; 525 } 526 527 static int __igt_insert(struct kunit *test, unsigned int count, u64 size, bool replace) 528 { 529 DRM_RND_STATE(prng, random_seed); 530 const struct insert_mode *mode; 531 struct drm_mm mm; 532 struct drm_mm_node *nodes, *node, *next; 533 unsigned int *order, n, m, o = 0; 534 int ret; 535 536 /* Fill a range with lots of nodes, check it doesn't fail too early */ 537 538 DRM_MM_BUG_ON(!count); 539 DRM_MM_BUG_ON(!size); 540 541 ret = -ENOMEM; 542 nodes = vmalloc(array_size(count, sizeof(*nodes))); 543 KUNIT_ASSERT_TRUE(test, nodes); 544 545 order = drm_random_order(count, &prng); 546 if (!order) 547 goto err_nodes; 548 549 ret = -EINVAL; 550 drm_mm_init(&mm, 0, count * size); 551 552 for (mode = insert_modes; mode->name; mode++) { 553 for (n = 0; n < count; n++) { 554 struct drm_mm_node tmp; 555 556 node = replace ? &tmp : &nodes[n]; 557 memset(node, 0, sizeof(*node)); 558 if (!expect_insert(test, &mm, node, size, 0, n, mode)) { 559 KUNIT_FAIL(test, "%s insert failed, size %llu step %d\n", 560 mode->name, size, n); 561 goto out; 562 } 563 564 if (replace) { 565 drm_mm_replace_node(&tmp, &nodes[n]); 566 if (drm_mm_node_allocated(&tmp)) { 567 KUNIT_FAIL(test, 568 "replaced old-node still allocated! step %d\n", 569 n); 570 goto out; 571 } 572 573 if (!assert_node(test, &nodes[n], &mm, size, 0, n)) { 574 KUNIT_FAIL(test, 575 "replaced node did not inherit parameters, size %llu step %d\n", 576 size, n); 577 goto out; 578 } 579 580 if (tmp.start != nodes[n].start) { 581 KUNIT_FAIL(test, 582 "replaced node mismatch location expected [%llx + %llx], found [%llx + %llx]\n", 583 tmp.start, size, nodes[n].start, nodes[n].size); 584 goto out; 585 } 586 } 587 } 588 589 /* After random insertion the nodes should be in order */ 590 if (!assert_continuous(test, &mm, size)) 591 goto out; 592 593 /* Repeated use should then fail */ 594 if (!expect_insert_fail(test, &mm, size)) 595 goto out; 596 597 /* Remove one and reinsert, as the only hole it should refill itself */ 598 for (n = 0; n < count; n++) { 599 u64 addr = nodes[n].start; 600 601 drm_mm_remove_node(&nodes[n]); 602 if (!expect_insert(test, &mm, &nodes[n], size, 0, n, mode)) { 603 KUNIT_FAIL(test, "%s reinsert failed, size %llu step %d\n", 604 mode->name, size, n); 605 goto out; 606 } 607 608 if (nodes[n].start != addr) { 609 KUNIT_FAIL(test, 610 "%s reinsert node moved, step %d, expected %llx, found %llx\n", 611 mode->name, n, addr, nodes[n].start); 612 goto out; 613 } 614 615 if (!assert_continuous(test, &mm, size)) 616 goto out; 617 } 618 619 /* Remove several, reinsert, check full */ 620 for_each_prime_number(n, min(max_prime, count)) { 621 for (m = 0; m < n; m++) { 622 node = &nodes[order[(o + m) % count]]; 623 drm_mm_remove_node(node); 624 } 625 626 for (m = 0; m < n; m++) { 627 node = &nodes[order[(o + m) % count]]; 628 if (!expect_insert(test, &mm, node, size, 0, n, mode)) { 629 KUNIT_FAIL(test, 630 "%s multiple reinsert failed, size %llu step %d\n", 631 mode->name, size, n); 632 goto out; 633 } 634 } 635 636 o += n; 637 638 if (!assert_continuous(test, &mm, size)) 639 goto out; 640 641 if (!expect_insert_fail(test, &mm, size)) 642 goto out; 643 } 644 645 drm_mm_for_each_node_safe(node, next, &mm) 646 drm_mm_remove_node(node); 647 DRM_MM_BUG_ON(!drm_mm_clean(&mm)); 648 649 cond_resched(); 650 } 651 652 ret = 0; 653 out: 654 drm_mm_for_each_node_safe(node, next, &mm) 655 drm_mm_remove_node(node); 656 drm_mm_takedown(&mm); 657 kfree(order); 658 err_nodes: 659 vfree(nodes); 660 return ret; 661 } 662 663 static void igt_mm_insert(struct kunit *test) 664 { 665 const unsigned int count = min_t(unsigned int, BIT(10), max_iterations); 666 unsigned int n; 667 668 for_each_prime_number_from(n, 1, 54) { 669 u64 size = BIT_ULL(n); 670 671 KUNIT_ASSERT_FALSE(test, __igt_insert(test, count, size - 1, false)); 672 KUNIT_ASSERT_FALSE(test, __igt_insert(test, count, size, false)); 673 KUNIT_ASSERT_FALSE(test, __igt_insert(test, count, size + 1, false)); 674 675 cond_resched(); 676 } 677 } 678 679 static void igt_mm_replace(struct kunit *test) 680 { 681 const unsigned int count = min_t(unsigned int, BIT(10), max_iterations); 682 unsigned int n; 683 684 /* Reuse igt_insert to exercise replacement by inserting a dummy node, 685 * then replacing it with the intended node. We want to check that 686 * the tree is intact and all the information we need is carried 687 * across to the target node. 688 */ 689 690 for_each_prime_number_from(n, 1, 54) { 691 u64 size = BIT_ULL(n); 692 693 KUNIT_ASSERT_FALSE(test, __igt_insert(test, count, size - 1, true)); 694 KUNIT_ASSERT_FALSE(test, __igt_insert(test, count, size, true)); 695 KUNIT_ASSERT_FALSE(test, __igt_insert(test, count, size + 1, true)); 696 697 cond_resched(); 698 } 699 } 700 701 static bool expect_insert_in_range(struct kunit *test, struct drm_mm *mm, struct drm_mm_node *node, 702 u64 size, u64 alignment, unsigned long color, 703 u64 range_start, u64 range_end, const struct insert_mode *mode) 704 { 705 int err; 706 707 err = drm_mm_insert_node_in_range(mm, node, 708 size, alignment, color, 709 range_start, range_end, 710 mode->mode); 711 if (err) { 712 KUNIT_FAIL(test, 713 "insert (size=%llu, alignment=%llu, color=%lu, mode=%s) nto range [%llx, %llx] failed with err=%d\n", 714 size, alignment, color, mode->name, 715 range_start, range_end, err); 716 return false; 717 } 718 719 if (!assert_node(test, node, mm, size, alignment, color)) { 720 drm_mm_remove_node(node); 721 return false; 722 } 723 724 return true; 725 } 726 727 static bool expect_insert_in_range_fail(struct kunit *test, struct drm_mm *mm, 728 u64 size, u64 range_start, u64 range_end) 729 { 730 struct drm_mm_node tmp = {}; 731 int err; 732 733 err = drm_mm_insert_node_in_range(mm, &tmp, size, 0, 0, range_start, range_end, 734 0); 735 if (likely(err == -ENOSPC)) 736 return true; 737 738 if (!err) { 739 KUNIT_FAIL(test, 740 "impossible insert succeeded, node %llx + %llu, range [%llx, %llx]\n", 741 tmp.start, tmp.size, range_start, range_end); 742 drm_mm_remove_node(&tmp); 743 } else { 744 KUNIT_FAIL(test, 745 "impossible insert failed with wrong error %d [expected %d], size %llu, range [%llx, %llx]\n", 746 err, -ENOSPC, size, range_start, range_end); 747 } 748 749 return false; 750 } 751 752 static bool assert_contiguous_in_range(struct kunit *test, struct drm_mm *mm, 753 u64 size, u64 start, u64 end) 754 { 755 struct drm_mm_node *node; 756 unsigned int n; 757 758 if (!expect_insert_in_range_fail(test, mm, size, start, end)) 759 return false; 760 761 n = div64_u64(start + size - 1, size); 762 drm_mm_for_each_node(node, mm) { 763 if (node->start < start || node->start + node->size > end) { 764 KUNIT_FAIL(test, 765 "node %d out of range, address [%llx + %llu], range [%llx, %llx]\n", 766 n, node->start, node->start + node->size, start, end); 767 return false; 768 } 769 770 if (node->start != n * size) { 771 KUNIT_FAIL(test, "node %d out of order, expected start %llx, found %llx\n", 772 n, n * size, node->start); 773 return false; 774 } 775 776 if (node->size != size) { 777 KUNIT_FAIL(test, "node %d has wrong size, expected size %llx, found %llx\n", 778 n, size, node->size); 779 return false; 780 } 781 782 if (drm_mm_hole_follows(node) && drm_mm_hole_node_end(node) < end) { 783 KUNIT_FAIL(test, "node %d is followed by a hole!\n", n); 784 return false; 785 } 786 787 n++; 788 } 789 790 if (start > 0) { 791 node = __drm_mm_interval_first(mm, 0, start - 1); 792 if (drm_mm_node_allocated(node)) { 793 KUNIT_FAIL(test, "node before start: node=%llx+%llu, start=%llx\n", 794 node->start, node->size, start); 795 return false; 796 } 797 } 798 799 if (end < U64_MAX) { 800 node = __drm_mm_interval_first(mm, end, U64_MAX); 801 if (drm_mm_node_allocated(node)) { 802 KUNIT_FAIL(test, "node after end: node=%llx+%llu, end=%llx\n", 803 node->start, node->size, end); 804 return false; 805 } 806 } 807 808 return true; 809 } 810 811 static int __igt_insert_range(struct kunit *test, unsigned int count, u64 size, u64 start, u64 end) 812 { 813 const struct insert_mode *mode; 814 struct drm_mm mm; 815 struct drm_mm_node *nodes, *node, *next; 816 unsigned int n, start_n, end_n; 817 int ret; 818 819 DRM_MM_BUG_ON(!count); 820 DRM_MM_BUG_ON(!size); 821 DRM_MM_BUG_ON(end <= start); 822 823 /* Very similar to __igt_insert(struct kunit *test, ), but now instead of populating the 824 * full range of the drm_mm, we try to fill a small portion of it. 825 */ 826 827 ret = -ENOMEM; 828 nodes = vzalloc(array_size(count, sizeof(*nodes))); 829 KUNIT_ASSERT_TRUE(test, nodes); 830 831 ret = -EINVAL; 832 drm_mm_init(&mm, 0, count * size); 833 834 start_n = div64_u64(start + size - 1, size); 835 end_n = div64_u64(end - size, size); 836 837 for (mode = insert_modes; mode->name; mode++) { 838 for (n = start_n; n <= end_n; n++) { 839 if (!expect_insert_in_range(test, &mm, &nodes[n], size, size, n, 840 start, end, mode)) { 841 KUNIT_FAIL(test, 842 "%s insert failed, size %llu, step %d [%d, %d], range [%llx, %llx]\n", 843 mode->name, size, n, start_n, end_n, start, end); 844 goto out; 845 } 846 } 847 848 if (!assert_contiguous_in_range(test, &mm, size, start, end)) { 849 KUNIT_FAIL(test, 850 "%s: range [%llx, %llx] not full after initialisation, size=%llu\n", 851 mode->name, start, end, size); 852 goto out; 853 } 854 855 /* Remove one and reinsert, it should refill itself */ 856 for (n = start_n; n <= end_n; n++) { 857 u64 addr = nodes[n].start; 858 859 drm_mm_remove_node(&nodes[n]); 860 if (!expect_insert_in_range(test, &mm, &nodes[n], size, size, n, 861 start, end, mode)) { 862 KUNIT_FAIL(test, "%s reinsert failed, step %d\n", mode->name, n); 863 goto out; 864 } 865 866 if (nodes[n].start != addr) { 867 KUNIT_FAIL(test, 868 "%s reinsert node moved, step %d, expected %llx, found %llx\n", 869 mode->name, n, addr, nodes[n].start); 870 goto out; 871 } 872 } 873 874 if (!assert_contiguous_in_range(test, &mm, size, start, end)) { 875 KUNIT_FAIL(test, 876 "%s: range [%llx, %llx] not full after reinsertion, size=%llu\n", 877 mode->name, start, end, size); 878 goto out; 879 } 880 881 drm_mm_for_each_node_safe(node, next, &mm) 882 drm_mm_remove_node(node); 883 DRM_MM_BUG_ON(!drm_mm_clean(&mm)); 884 885 cond_resched(); 886 } 887 888 ret = 0; 889 out: 890 drm_mm_for_each_node_safe(node, next, &mm) 891 drm_mm_remove_node(node); 892 drm_mm_takedown(&mm); 893 vfree(nodes); 894 return ret; 895 } 896 897 static int insert_outside_range(struct kunit *test) 898 { 899 struct drm_mm mm; 900 const unsigned int start = 1024; 901 const unsigned int end = 2048; 902 const unsigned int size = end - start; 903 904 drm_mm_init(&mm, start, size); 905 906 if (!expect_insert_in_range_fail(test, &mm, 1, 0, start)) 907 return -EINVAL; 908 909 if (!expect_insert_in_range_fail(test, &mm, size, 910 start - size / 2, start + (size + 1) / 2)) 911 return -EINVAL; 912 913 if (!expect_insert_in_range_fail(test, &mm, size, 914 end - (size + 1) / 2, end + size / 2)) 915 return -EINVAL; 916 917 if (!expect_insert_in_range_fail(test, &mm, 1, end, end + size)) 918 return -EINVAL; 919 920 drm_mm_takedown(&mm); 921 return 0; 922 } 923 924 static void igt_mm_insert_range(struct kunit *test) 925 { 926 const unsigned int count = min_t(unsigned int, BIT(13), max_iterations); 927 unsigned int n; 928 929 /* Check that requests outside the bounds of drm_mm are rejected. */ 930 KUNIT_ASSERT_FALSE(test, insert_outside_range(test)); 931 932 for_each_prime_number_from(n, 1, 50) { 933 const u64 size = BIT_ULL(n); 934 const u64 max = count * size; 935 936 KUNIT_ASSERT_FALSE(test, __igt_insert_range(test, count, size, 0, max)); 937 KUNIT_ASSERT_FALSE(test, __igt_insert_range(test, count, size, 1, max)); 938 KUNIT_ASSERT_FALSE(test, __igt_insert_range(test, count, size, 0, max - 1)); 939 KUNIT_ASSERT_FALSE(test, __igt_insert_range(test, count, size, 0, max / 2)); 940 KUNIT_ASSERT_FALSE(test, __igt_insert_range(test, count, size, max / 2, max / 2)); 941 KUNIT_ASSERT_FALSE(test, __igt_insert_range(test, count, size, 942 max / 4 + 1, 3 * max / 4 - 1)); 943 944 cond_resched(); 945 } 946 } 947 948 static int prepare_igt_frag(struct kunit *test, struct drm_mm *mm, 949 struct drm_mm_node *nodes, unsigned int num_insert, 950 const struct insert_mode *mode) 951 { 952 unsigned int size = 4096; 953 unsigned int i; 954 955 for (i = 0; i < num_insert; i++) { 956 if (!expect_insert(test, mm, &nodes[i], size, 0, i, mode) != 0) { 957 KUNIT_FAIL(test, "%s insert failed\n", mode->name); 958 return -EINVAL; 959 } 960 } 961 962 /* introduce fragmentation by freeing every other node */ 963 for (i = 0; i < num_insert; i++) { 964 if (i % 2 == 0) 965 drm_mm_remove_node(&nodes[i]); 966 } 967 968 return 0; 969 } 970 971 static u64 get_insert_time(struct kunit *test, struct drm_mm *mm, 972 unsigned int num_insert, struct drm_mm_node *nodes, 973 const struct insert_mode *mode) 974 { 975 unsigned int size = 8192; 976 ktime_t start; 977 unsigned int i; 978 979 start = ktime_get(); 980 for (i = 0; i < num_insert; i++) { 981 if (!expect_insert(test, mm, &nodes[i], size, 0, i, mode) != 0) { 982 KUNIT_FAIL(test, "%s insert failed\n", mode->name); 983 return 0; 984 } 985 } 986 987 return ktime_to_ns(ktime_sub(ktime_get(), start)); 988 } 989 990 static void igt_mm_frag(struct kunit *test) 991 { 992 struct drm_mm mm; 993 const struct insert_mode *mode; 994 struct drm_mm_node *nodes, *node, *next; 995 unsigned int insert_size = 10000; 996 unsigned int scale_factor = 4; 997 998 /* We need 4 * insert_size nodes to hold intermediate allocated 999 * drm_mm nodes. 1000 * 1 times for prepare_igt_frag(struct kunit *test, ) 1001 * 1 times for get_insert_time(struct kunit *test, ) 1002 * 2 times for get_insert_time(struct kunit *test, ) 1003 */ 1004 nodes = vzalloc(array_size(insert_size * 4, sizeof(*nodes))); 1005 KUNIT_ASSERT_TRUE(test, nodes); 1006 1007 /* For BOTTOMUP and TOPDOWN, we first fragment the 1008 * address space using prepare_igt_frag(struct kunit *test, ) and then try to verify 1009 * that insertions scale quadratically from 10k to 20k insertions 1010 */ 1011 drm_mm_init(&mm, 1, U64_MAX - 2); 1012 for (mode = insert_modes; mode->name; mode++) { 1013 u64 insert_time1, insert_time2; 1014 1015 if (mode->mode != DRM_MM_INSERT_LOW && 1016 mode->mode != DRM_MM_INSERT_HIGH) 1017 continue; 1018 1019 if (prepare_igt_frag(test, &mm, nodes, insert_size, mode)) 1020 goto err; 1021 1022 insert_time1 = get_insert_time(test, &mm, insert_size, 1023 nodes + insert_size, mode); 1024 if (insert_time1 == 0) 1025 goto err; 1026 1027 insert_time2 = get_insert_time(test, &mm, (insert_size * 2), 1028 nodes + insert_size * 2, mode); 1029 if (insert_time2 == 0) 1030 goto err; 1031 1032 kunit_info(test, "%s fragmented insert of %u and %u insertions took %llu and %llu nsecs\n", 1033 mode->name, insert_size, insert_size * 2, insert_time1, insert_time2); 1034 1035 if (insert_time2 > (scale_factor * insert_time1)) { 1036 KUNIT_FAIL(test, "%s fragmented insert took %llu nsecs more\n", 1037 mode->name, insert_time2 - (scale_factor * insert_time1)); 1038 goto err; 1039 } 1040 1041 drm_mm_for_each_node_safe(node, next, &mm) 1042 drm_mm_remove_node(node); 1043 } 1044 1045 err: 1046 drm_mm_for_each_node_safe(node, next, &mm) 1047 drm_mm_remove_node(node); 1048 drm_mm_takedown(&mm); 1049 vfree(nodes); 1050 } 1051 1052 static void igt_mm_align(struct kunit *test) 1053 { 1054 const struct insert_mode *mode; 1055 const unsigned int max_count = min(8192u, max_prime); 1056 struct drm_mm mm; 1057 struct drm_mm_node *nodes, *node, *next; 1058 unsigned int prime; 1059 1060 /* For each of the possible insertion modes, we pick a few 1061 * arbitrary alignments and check that the inserted node 1062 * meets our requirements. 1063 */ 1064 1065 nodes = vzalloc(array_size(max_count, sizeof(*nodes))); 1066 KUNIT_ASSERT_TRUE(test, nodes); 1067 1068 drm_mm_init(&mm, 1, U64_MAX - 2); 1069 1070 for (mode = insert_modes; mode->name; mode++) { 1071 unsigned int i = 0; 1072 1073 for_each_prime_number_from(prime, 1, max_count) { 1074 u64 size = next_prime_number(prime); 1075 1076 if (!expect_insert(test, &mm, &nodes[i], size, prime, i, mode)) { 1077 KUNIT_FAIL(test, "%s insert failed with alignment=%d", 1078 mode->name, prime); 1079 goto out; 1080 } 1081 1082 i++; 1083 } 1084 1085 drm_mm_for_each_node_safe(node, next, &mm) 1086 drm_mm_remove_node(node); 1087 DRM_MM_BUG_ON(!drm_mm_clean(&mm)); 1088 1089 cond_resched(); 1090 } 1091 1092 out: 1093 drm_mm_for_each_node_safe(node, next, &mm) 1094 drm_mm_remove_node(node); 1095 drm_mm_takedown(&mm); 1096 vfree(nodes); 1097 } 1098 1099 static void igt_align_pot(struct kunit *test, int max) 1100 { 1101 struct drm_mm mm; 1102 struct drm_mm_node *node, *next; 1103 int bit; 1104 1105 /* Check that we can align to the full u64 address space */ 1106 1107 drm_mm_init(&mm, 1, U64_MAX - 2); 1108 1109 for (bit = max - 1; bit; bit--) { 1110 u64 align, size; 1111 1112 node = kzalloc(sizeof(*node), GFP_KERNEL); 1113 if (!node) { 1114 KUNIT_FAIL(test, "failed to allocate node"); 1115 goto out; 1116 } 1117 1118 align = BIT_ULL(bit); 1119 size = BIT_ULL(bit - 1) + 1; 1120 if (!expect_insert(test, &mm, node, size, align, bit, &insert_modes[0])) { 1121 KUNIT_FAIL(test, "insert failed with alignment=%llx [%d]", align, bit); 1122 goto out; 1123 } 1124 1125 cond_resched(); 1126 } 1127 1128 out: 1129 drm_mm_for_each_node_safe(node, next, &mm) { 1130 drm_mm_remove_node(node); 1131 kfree(node); 1132 } 1133 drm_mm_takedown(&mm); 1134 } 1135 1136 static void igt_mm_align32(struct kunit *test) 1137 { 1138 igt_align_pot(test, 32); 1139 } 1140 1141 static void igt_mm_align64(struct kunit *test) 1142 { 1143 igt_align_pot(test, 64); 1144 } 1145 1146 static void show_scan(struct kunit *test, const struct drm_mm_scan *scan) 1147 { 1148 kunit_info(test, "scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n", 1149 scan->hit_start, scan->hit_end, scan->size, scan->alignment, scan->color); 1150 } 1151 1152 static void show_holes(struct kunit *test, const struct drm_mm *mm, int count) 1153 { 1154 u64 hole_start, hole_end; 1155 struct drm_mm_node *hole; 1156 1157 drm_mm_for_each_hole(hole, mm, hole_start, hole_end) { 1158 struct drm_mm_node *next = list_next_entry(hole, node_list); 1159 const char *node1 = NULL, *node2 = NULL; 1160 1161 if (drm_mm_node_allocated(hole)) 1162 node1 = kasprintf(GFP_KERNEL, "[%llx + %lld, color=%ld], ", 1163 hole->start, hole->size, hole->color); 1164 1165 if (drm_mm_node_allocated(next)) 1166 node2 = kasprintf(GFP_KERNEL, ", [%llx + %lld, color=%ld]", 1167 next->start, next->size, next->color); 1168 1169 kunit_info(test, "%sHole [%llx - %llx, size %lld]%s\n", node1, 1170 hole_start, hole_end, hole_end - hole_start, node2); 1171 1172 kfree(node2); 1173 kfree(node1); 1174 1175 if (!--count) 1176 break; 1177 } 1178 } 1179 1180 struct evict_node { 1181 struct drm_mm_node node; 1182 struct list_head link; 1183 }; 1184 1185 static bool evict_nodes(struct kunit *test, struct drm_mm_scan *scan, 1186 struct evict_node *nodes, unsigned int *order, unsigned int count, 1187 bool use_color, struct list_head *evict_list) 1188 { 1189 struct evict_node *e, *en; 1190 unsigned int i; 1191 1192 for (i = 0; i < count; i++) { 1193 e = &nodes[order ? order[i] : i]; 1194 list_add(&e->link, evict_list); 1195 if (drm_mm_scan_add_block(scan, &e->node)) 1196 break; 1197 } 1198 list_for_each_entry_safe(e, en, evict_list, link) { 1199 if (!drm_mm_scan_remove_block(scan, &e->node)) 1200 list_del(&e->link); 1201 } 1202 if (list_empty(evict_list)) { 1203 KUNIT_FAIL(test, 1204 "Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n", 1205 scan->size, count, scan->alignment, scan->color); 1206 return false; 1207 } 1208 1209 list_for_each_entry(e, evict_list, link) 1210 drm_mm_remove_node(&e->node); 1211 1212 if (use_color) { 1213 struct drm_mm_node *node; 1214 1215 while ((node = drm_mm_scan_color_evict(scan))) { 1216 e = container_of(node, typeof(*e), node); 1217 drm_mm_remove_node(&e->node); 1218 list_add(&e->link, evict_list); 1219 } 1220 } else { 1221 if (drm_mm_scan_color_evict(scan)) { 1222 KUNIT_FAIL(test, 1223 "drm_mm_scan_color_evict unexpectedly reported overlapping nodes!\n"); 1224 return false; 1225 } 1226 } 1227 1228 return true; 1229 } 1230 1231 static bool evict_nothing(struct kunit *test, struct drm_mm *mm, 1232 unsigned int total_size, struct evict_node *nodes) 1233 { 1234 struct drm_mm_scan scan; 1235 LIST_HEAD(evict_list); 1236 struct evict_node *e; 1237 struct drm_mm_node *node; 1238 unsigned int n; 1239 1240 drm_mm_scan_init(&scan, mm, 1, 0, 0, 0); 1241 for (n = 0; n < total_size; n++) { 1242 e = &nodes[n]; 1243 list_add(&e->link, &evict_list); 1244 drm_mm_scan_add_block(&scan, &e->node); 1245 } 1246 list_for_each_entry(e, &evict_list, link) 1247 drm_mm_scan_remove_block(&scan, &e->node); 1248 1249 for (n = 0; n < total_size; n++) { 1250 e = &nodes[n]; 1251 1252 if (!drm_mm_node_allocated(&e->node)) { 1253 KUNIT_FAIL(test, "node[%d] no longer allocated!\n", n); 1254 return false; 1255 } 1256 1257 e->link.next = NULL; 1258 } 1259 1260 drm_mm_for_each_node(node, mm) { 1261 e = container_of(node, typeof(*e), node); 1262 e->link.next = &e->link; 1263 } 1264 1265 for (n = 0; n < total_size; n++) { 1266 e = &nodes[n]; 1267 1268 if (!e->link.next) { 1269 KUNIT_FAIL(test, "node[%d] no longer connected!\n", n); 1270 return false; 1271 } 1272 } 1273 1274 return assert_continuous(test, mm, nodes[0].node.size); 1275 } 1276 1277 static bool evict_everything(struct kunit *test, struct drm_mm *mm, 1278 unsigned int total_size, struct evict_node *nodes) 1279 { 1280 struct drm_mm_scan scan; 1281 LIST_HEAD(evict_list); 1282 struct evict_node *e; 1283 unsigned int n; 1284 int err; 1285 1286 drm_mm_scan_init(&scan, mm, total_size, 0, 0, 0); 1287 for (n = 0; n < total_size; n++) { 1288 e = &nodes[n]; 1289 list_add(&e->link, &evict_list); 1290 if (drm_mm_scan_add_block(&scan, &e->node)) 1291 break; 1292 } 1293 1294 err = 0; 1295 list_for_each_entry(e, &evict_list, link) { 1296 if (!drm_mm_scan_remove_block(&scan, &e->node)) { 1297 if (!err) { 1298 KUNIT_FAIL(test, "Node %lld not marked for eviction!\n", 1299 e->node.start); 1300 err = -EINVAL; 1301 } 1302 } 1303 } 1304 if (err) 1305 return false; 1306 1307 list_for_each_entry(e, &evict_list, link) 1308 drm_mm_remove_node(&e->node); 1309 1310 if (!assert_one_hole(test, mm, 0, total_size)) 1311 return false; 1312 1313 list_for_each_entry(e, &evict_list, link) { 1314 err = drm_mm_reserve_node(mm, &e->node); 1315 if (err) { 1316 KUNIT_FAIL(test, "Failed to reinsert node after eviction: start=%llx\n", 1317 e->node.start); 1318 return false; 1319 } 1320 } 1321 1322 return assert_continuous(test, mm, nodes[0].node.size); 1323 } 1324 1325 static int evict_something(struct kunit *test, struct drm_mm *mm, 1326 u64 range_start, u64 range_end, struct evict_node *nodes, 1327 unsigned int *order, unsigned int count, unsigned int size, 1328 unsigned int alignment, const struct insert_mode *mode) 1329 { 1330 struct drm_mm_scan scan; 1331 LIST_HEAD(evict_list); 1332 struct evict_node *e; 1333 struct drm_mm_node tmp; 1334 int err; 1335 1336 drm_mm_scan_init_with_range(&scan, mm, size, alignment, 0, range_start, 1337 range_end, mode->mode); 1338 if (!evict_nodes(test, &scan, nodes, order, count, false, &evict_list)) 1339 return -EINVAL; 1340 1341 memset(&tmp, 0, sizeof(tmp)); 1342 err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, 0, 1343 DRM_MM_INSERT_EVICT); 1344 if (err) { 1345 KUNIT_FAIL(test, "Failed to insert into eviction hole: size=%d, align=%d\n", 1346 size, alignment); 1347 show_scan(test, &scan); 1348 show_holes(test, mm, 3); 1349 return err; 1350 } 1351 1352 if (tmp.start < range_start || tmp.start + tmp.size > range_end) { 1353 KUNIT_FAIL(test, 1354 "Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n", 1355 tmp.start, tmp.size, range_start, range_end); 1356 err = -EINVAL; 1357 } 1358 1359 if (!assert_node(test, &tmp, mm, size, alignment, 0) || 1360 drm_mm_hole_follows(&tmp)) { 1361 KUNIT_FAIL(test, 1362 "Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n", 1363 tmp.size, size, alignment, misalignment(&tmp, alignment), 1364 tmp.start, drm_mm_hole_follows(&tmp)); 1365 err = -EINVAL; 1366 } 1367 1368 drm_mm_remove_node(&tmp); 1369 if (err) 1370 return err; 1371 1372 list_for_each_entry(e, &evict_list, link) { 1373 err = drm_mm_reserve_node(mm, &e->node); 1374 if (err) { 1375 KUNIT_FAIL(test, "Failed to reinsert node after eviction: start=%llx\n", 1376 e->node.start); 1377 return err; 1378 } 1379 } 1380 1381 if (!assert_continuous(test, mm, nodes[0].node.size)) { 1382 KUNIT_FAIL(test, "range is no longer continuous\n"); 1383 return -EINVAL; 1384 } 1385 1386 return 0; 1387 } 1388 1389 static void igt_mm_evict(struct kunit *test) 1390 { 1391 DRM_RND_STATE(prng, random_seed); 1392 const unsigned int size = 8192; 1393 const struct insert_mode *mode; 1394 struct drm_mm mm; 1395 struct evict_node *nodes; 1396 struct drm_mm_node *node, *next; 1397 unsigned int *order, n; 1398 1399 /* Here we populate a full drm_mm and then try and insert a new node 1400 * by evicting other nodes in a random order. The drm_mm_scan should 1401 * pick the first matching hole it finds from the random list. We 1402 * repeat that for different allocation strategies, alignments and 1403 * sizes to try and stress the hole finder. 1404 */ 1405 1406 nodes = vzalloc(array_size(size, sizeof(*nodes))); 1407 KUNIT_ASSERT_TRUE(test, nodes); 1408 1409 order = drm_random_order(size, &prng); 1410 if (!order) 1411 goto err_nodes; 1412 1413 drm_mm_init(&mm, 0, size); 1414 for (n = 0; n < size; n++) { 1415 if (drm_mm_insert_node(&mm, &nodes[n].node, 1)) { 1416 KUNIT_FAIL(test, "insert failed, step %d\n", n); 1417 goto out; 1418 } 1419 } 1420 1421 /* First check that using the scanner doesn't break the mm */ 1422 if (!evict_nothing(test, &mm, size, nodes)) { 1423 KUNIT_FAIL(test, "evict_nothing() failed\n"); 1424 goto out; 1425 } 1426 if (!evict_everything(test, &mm, size, nodes)) { 1427 KUNIT_FAIL(test, "evict_everything() failed\n"); 1428 goto out; 1429 } 1430 1431 for (mode = evict_modes; mode->name; mode++) { 1432 for (n = 1; n <= size; n <<= 1) { 1433 drm_random_reorder(order, size, &prng); 1434 if (evict_something(test, &mm, 0, U64_MAX, nodes, order, size, n, 1, 1435 mode)) { 1436 KUNIT_FAIL(test, "%s evict_something(size=%u) failed\n", 1437 mode->name, n); 1438 goto out; 1439 } 1440 } 1441 1442 for (n = 1; n < size; n <<= 1) { 1443 drm_random_reorder(order, size, &prng); 1444 if (evict_something(test, &mm, 0, U64_MAX, nodes, order, size, 1445 size / 2, n, mode)) { 1446 KUNIT_FAIL(test, 1447 "%s evict_something(size=%u, alignment=%u) failed\n", 1448 mode->name, size / 2, n); 1449 goto out; 1450 } 1451 } 1452 1453 for_each_prime_number_from(n, 1, min(size, max_prime)) { 1454 unsigned int nsize = (size - n + 1) / 2; 1455 1456 DRM_MM_BUG_ON(!nsize); 1457 1458 drm_random_reorder(order, size, &prng); 1459 if (evict_something(test, &mm, 0, U64_MAX, nodes, order, size, 1460 nsize, n, mode)) { 1461 KUNIT_FAIL(test, 1462 "%s evict_something(size=%u, alignment=%u) failed\n", 1463 mode->name, nsize, n); 1464 goto out; 1465 } 1466 } 1467 1468 cond_resched(); 1469 } 1470 1471 out: 1472 drm_mm_for_each_node_safe(node, next, &mm) 1473 drm_mm_remove_node(node); 1474 drm_mm_takedown(&mm); 1475 kfree(order); 1476 err_nodes: 1477 vfree(nodes); 1478 } 1479 1480 static void igt_mm_evict_range(struct kunit *test) 1481 { 1482 DRM_RND_STATE(prng, random_seed); 1483 const unsigned int size = 8192; 1484 const unsigned int range_size = size / 2; 1485 const unsigned int range_start = size / 4; 1486 const unsigned int range_end = range_start + range_size; 1487 const struct insert_mode *mode; 1488 struct drm_mm mm; 1489 struct evict_node *nodes; 1490 struct drm_mm_node *node, *next; 1491 unsigned int *order, n; 1492 1493 /* Like igt_evict() but now we are limiting the search to a 1494 * small portion of the full drm_mm. 1495 */ 1496 1497 nodes = vzalloc(array_size(size, sizeof(*nodes))); 1498 KUNIT_ASSERT_TRUE(test, nodes); 1499 1500 order = drm_random_order(size, &prng); 1501 if (!order) 1502 goto err_nodes; 1503 1504 drm_mm_init(&mm, 0, size); 1505 for (n = 0; n < size; n++) { 1506 if (drm_mm_insert_node(&mm, &nodes[n].node, 1)) { 1507 KUNIT_FAIL(test, "insert failed, step %d\n", n); 1508 goto out; 1509 } 1510 } 1511 1512 for (mode = evict_modes; mode->name; mode++) { 1513 for (n = 1; n <= range_size; n <<= 1) { 1514 drm_random_reorder(order, size, &prng); 1515 if (evict_something(test, &mm, range_start, range_end, nodes, 1516 order, size, n, 1, mode)) { 1517 KUNIT_FAIL(test, 1518 "%s evict_something(size=%u) failed with range [%u, %u]\n", 1519 mode->name, n, range_start, range_end); 1520 goto out; 1521 } 1522 } 1523 1524 for (n = 1; n <= range_size; n <<= 1) { 1525 drm_random_reorder(order, size, &prng); 1526 if (evict_something(test, &mm, range_start, range_end, nodes, 1527 order, size, range_size / 2, n, mode)) { 1528 KUNIT_FAIL(test, 1529 "%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n", 1530 mode->name, range_size / 2, n, range_start, range_end); 1531 goto out; 1532 } 1533 } 1534 1535 for_each_prime_number_from(n, 1, min(range_size, max_prime)) { 1536 unsigned int nsize = (range_size - n + 1) / 2; 1537 1538 DRM_MM_BUG_ON(!nsize); 1539 1540 drm_random_reorder(order, size, &prng); 1541 if (evict_something(test, &mm, range_start, range_end, nodes, 1542 order, size, nsize, n, mode)) { 1543 KUNIT_FAIL(test, 1544 "%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n", 1545 mode->name, nsize, n, range_start, range_end); 1546 goto out; 1547 } 1548 } 1549 1550 cond_resched(); 1551 } 1552 1553 out: 1554 drm_mm_for_each_node_safe(node, next, &mm) 1555 drm_mm_remove_node(node); 1556 drm_mm_takedown(&mm); 1557 kfree(order); 1558 err_nodes: 1559 vfree(nodes); 1560 } 1561 1562 static unsigned int node_index(const struct drm_mm_node *node) 1563 { 1564 return div64_u64(node->start, node->size); 1565 } 1566 1567 static void igt_mm_topdown(struct kunit *test) 1568 { 1569 const struct insert_mode *topdown = &insert_modes[TOPDOWN]; 1570 1571 DRM_RND_STATE(prng, random_seed); 1572 const unsigned int count = 8192; 1573 unsigned int size; 1574 unsigned long *bitmap; 1575 struct drm_mm mm; 1576 struct drm_mm_node *nodes, *node, *next; 1577 unsigned int *order, n, m, o = 0; 1578 1579 /* When allocating top-down, we expect to be returned a node 1580 * from a suitable hole at the top of the drm_mm. We check that 1581 * the returned node does match the highest available slot. 1582 */ 1583 1584 nodes = vzalloc(array_size(count, sizeof(*nodes))); 1585 KUNIT_ASSERT_TRUE(test, nodes); 1586 1587 bitmap = bitmap_zalloc(count, GFP_KERNEL); 1588 if (!bitmap) 1589 goto err_nodes; 1590 1591 order = drm_random_order(count, &prng); 1592 if (!order) 1593 goto err_bitmap; 1594 1595 for (size = 1; size <= 64; size <<= 1) { 1596 drm_mm_init(&mm, 0, size * count); 1597 for (n = 0; n < count; n++) { 1598 if (!expect_insert(test, &mm, &nodes[n], size, 0, n, topdown)) { 1599 KUNIT_FAIL(test, "insert failed, size %u step %d\n", size, n); 1600 goto out; 1601 } 1602 1603 if (drm_mm_hole_follows(&nodes[n])) { 1604 KUNIT_FAIL(test, 1605 "hole after topdown insert %d, start=%llx\n, size=%u", 1606 n, nodes[n].start, size); 1607 goto out; 1608 } 1609 1610 if (!assert_one_hole(test, &mm, 0, size * (count - n - 1))) 1611 goto out; 1612 } 1613 1614 if (!assert_continuous(test, &mm, size)) 1615 goto out; 1616 1617 drm_random_reorder(order, count, &prng); 1618 for_each_prime_number_from(n, 1, min(count, max_prime)) { 1619 for (m = 0; m < n; m++) { 1620 node = &nodes[order[(o + m) % count]]; 1621 drm_mm_remove_node(node); 1622 __set_bit(node_index(node), bitmap); 1623 } 1624 1625 for (m = 0; m < n; m++) { 1626 unsigned int last; 1627 1628 node = &nodes[order[(o + m) % count]]; 1629 if (!expect_insert(test, &mm, node, size, 0, 0, topdown)) { 1630 KUNIT_FAIL(test, "insert failed, step %d/%d\n", m, n); 1631 goto out; 1632 } 1633 1634 if (drm_mm_hole_follows(node)) { 1635 KUNIT_FAIL(test, 1636 "hole after topdown insert %d/%d, start=%llx\n", 1637 m, n, node->start); 1638 goto out; 1639 } 1640 1641 last = find_last_bit(bitmap, count); 1642 if (node_index(node) != last) { 1643 KUNIT_FAIL(test, 1644 "node %d/%d, size %d, not inserted into upmost hole, expected %d, found %d\n", 1645 m, n, size, last, node_index(node)); 1646 goto out; 1647 } 1648 1649 __clear_bit(last, bitmap); 1650 } 1651 1652 DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count); 1653 1654 o += n; 1655 } 1656 1657 drm_mm_for_each_node_safe(node, next, &mm) 1658 drm_mm_remove_node(node); 1659 DRM_MM_BUG_ON(!drm_mm_clean(&mm)); 1660 cond_resched(); 1661 } 1662 1663 out: 1664 drm_mm_for_each_node_safe(node, next, &mm) 1665 drm_mm_remove_node(node); 1666 drm_mm_takedown(&mm); 1667 kfree(order); 1668 err_bitmap: 1669 bitmap_free(bitmap); 1670 err_nodes: 1671 vfree(nodes); 1672 } 1673 1674 static void igt_mm_bottomup(struct kunit *test) 1675 { 1676 const struct insert_mode *bottomup = &insert_modes[BOTTOMUP]; 1677 1678 DRM_RND_STATE(prng, random_seed); 1679 const unsigned int count = 8192; 1680 unsigned int size; 1681 unsigned long *bitmap; 1682 struct drm_mm mm; 1683 struct drm_mm_node *nodes, *node, *next; 1684 unsigned int *order, n, m, o = 0; 1685 1686 /* Like igt_topdown, but instead of searching for the last hole, 1687 * we search for the first. 1688 */ 1689 1690 nodes = vzalloc(array_size(count, sizeof(*nodes))); 1691 KUNIT_ASSERT_TRUE(test, nodes); 1692 1693 bitmap = bitmap_zalloc(count, GFP_KERNEL); 1694 if (!bitmap) 1695 goto err_nodes; 1696 1697 order = drm_random_order(count, &prng); 1698 if (!order) 1699 goto err_bitmap; 1700 1701 for (size = 1; size <= 64; size <<= 1) { 1702 drm_mm_init(&mm, 0, size * count); 1703 for (n = 0; n < count; n++) { 1704 if (!expect_insert(test, &mm, &nodes[n], size, 0, n, bottomup)) { 1705 KUNIT_FAIL(test, 1706 "bottomup insert failed, size %u step %d\n", size, n); 1707 goto out; 1708 } 1709 1710 if (!assert_one_hole(test, &mm, size * (n + 1), size * count)) 1711 goto out; 1712 } 1713 1714 if (!assert_continuous(test, &mm, size)) 1715 goto out; 1716 1717 drm_random_reorder(order, count, &prng); 1718 for_each_prime_number_from(n, 1, min(count, max_prime)) { 1719 for (m = 0; m < n; m++) { 1720 node = &nodes[order[(o + m) % count]]; 1721 drm_mm_remove_node(node); 1722 __set_bit(node_index(node), bitmap); 1723 } 1724 1725 for (m = 0; m < n; m++) { 1726 unsigned int first; 1727 1728 node = &nodes[order[(o + m) % count]]; 1729 if (!expect_insert(test, &mm, node, size, 0, 0, bottomup)) { 1730 KUNIT_FAIL(test, "insert failed, step %d/%d\n", m, n); 1731 goto out; 1732 } 1733 1734 first = find_first_bit(bitmap, count); 1735 if (node_index(node) != first) { 1736 KUNIT_FAIL(test, 1737 "node %d/%d not inserted into bottom hole, expected %d, found %d\n", 1738 m, n, first, node_index(node)); 1739 goto out; 1740 } 1741 __clear_bit(first, bitmap); 1742 } 1743 1744 DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count); 1745 1746 o += n; 1747 } 1748 1749 drm_mm_for_each_node_safe(node, next, &mm) 1750 drm_mm_remove_node(node); 1751 DRM_MM_BUG_ON(!drm_mm_clean(&mm)); 1752 cond_resched(); 1753 } 1754 1755 out: 1756 drm_mm_for_each_node_safe(node, next, &mm) 1757 drm_mm_remove_node(node); 1758 drm_mm_takedown(&mm); 1759 kfree(order); 1760 err_bitmap: 1761 bitmap_free(bitmap); 1762 err_nodes: 1763 vfree(nodes); 1764 } 1765 1766 static void __igt_once(struct kunit *test, unsigned int mode) 1767 { 1768 struct drm_mm mm; 1769 struct drm_mm_node rsvd_lo, rsvd_hi, node; 1770 1771 drm_mm_init(&mm, 0, 7); 1772 1773 memset(&rsvd_lo, 0, sizeof(rsvd_lo)); 1774 rsvd_lo.start = 1; 1775 rsvd_lo.size = 1; 1776 if (drm_mm_reserve_node(&mm, &rsvd_lo)) { 1777 KUNIT_FAIL(test, "Could not reserve low node\n"); 1778 goto err; 1779 } 1780 1781 memset(&rsvd_hi, 0, sizeof(rsvd_hi)); 1782 rsvd_hi.start = 5; 1783 rsvd_hi.size = 1; 1784 if (drm_mm_reserve_node(&mm, &rsvd_hi)) { 1785 KUNIT_FAIL(test, "Could not reserve low node\n"); 1786 goto err_lo; 1787 } 1788 1789 if (!drm_mm_hole_follows(&rsvd_lo) || !drm_mm_hole_follows(&rsvd_hi)) { 1790 KUNIT_FAIL(test, "Expected a hole after lo and high nodes!\n"); 1791 goto err_hi; 1792 } 1793 1794 memset(&node, 0, sizeof(node)); 1795 if (drm_mm_insert_node_generic(&mm, &node, 2, 0, 0, mode)) { 1796 KUNIT_FAIL(test, "Could not insert the node into the available hole!\n"); 1797 goto err_hi; 1798 } 1799 1800 drm_mm_remove_node(&node); 1801 err_hi: 1802 drm_mm_remove_node(&rsvd_hi); 1803 err_lo: 1804 drm_mm_remove_node(&rsvd_lo); 1805 err: 1806 drm_mm_takedown(&mm); 1807 } 1808 1809 static void igt_mm_lowest(struct kunit *test) 1810 { 1811 __igt_once(test, DRM_MM_INSERT_LOW); 1812 } 1813 1814 static void igt_mm_highest(struct kunit *test) 1815 { 1816 __igt_once(test, DRM_MM_INSERT_HIGH); 1817 } 1818 1819 static void separate_adjacent_colors(const struct drm_mm_node *node, 1820 unsigned long color, u64 *start, u64 *end) 1821 { 1822 if (drm_mm_node_allocated(node) && node->color != color) 1823 ++*start; 1824 1825 node = list_next_entry(node, node_list); 1826 if (drm_mm_node_allocated(node) && node->color != color) 1827 --*end; 1828 } 1829 1830 static bool colors_abutt(struct kunit *test, const struct drm_mm_node *node) 1831 { 1832 if (!drm_mm_hole_follows(node) && 1833 drm_mm_node_allocated(list_next_entry(node, node_list))) { 1834 KUNIT_FAIL(test, "colors abutt; %ld [%llx + %llx] is next to %ld [%llx + %llx]!\n", 1835 node->color, node->start, node->size, 1836 list_next_entry(node, node_list)->color, 1837 list_next_entry(node, node_list)->start, 1838 list_next_entry(node, node_list)->size); 1839 return true; 1840 } 1841 1842 return false; 1843 } 1844 1845 static void igt_mm_color(struct kunit *test) 1846 { 1847 const unsigned int count = min(4096u, max_iterations); 1848 const struct insert_mode *mode; 1849 struct drm_mm mm; 1850 struct drm_mm_node *node, *nn; 1851 unsigned int n; 1852 1853 /* Color adjustment complicates everything. First we just check 1854 * that when we insert a node we apply any color_adjustment callback. 1855 * The callback we use should ensure that there is a gap between 1856 * any two nodes, and so after each insertion we check that those 1857 * holes are inserted and that they are preserved. 1858 */ 1859 1860 drm_mm_init(&mm, 0, U64_MAX); 1861 1862 for (n = 1; n <= count; n++) { 1863 node = kzalloc(sizeof(*node), GFP_KERNEL); 1864 if (!node) 1865 goto out; 1866 1867 if (!expect_insert(test, &mm, node, n, 0, n, &insert_modes[0])) { 1868 KUNIT_FAIL(test, "insert failed, step %d\n", n); 1869 kfree(node); 1870 goto out; 1871 } 1872 } 1873 1874 drm_mm_for_each_node_safe(node, nn, &mm) { 1875 if (node->color != node->size) { 1876 KUNIT_FAIL(test, "invalid color stored: expected %lld, found %ld\n", 1877 node->size, node->color); 1878 1879 goto out; 1880 } 1881 1882 drm_mm_remove_node(node); 1883 kfree(node); 1884 } 1885 1886 /* Now, let's start experimenting with applying a color callback */ 1887 mm.color_adjust = separate_adjacent_colors; 1888 for (mode = insert_modes; mode->name; mode++) { 1889 u64 last; 1890 1891 node = kzalloc(sizeof(*node), GFP_KERNEL); 1892 if (!node) 1893 goto out; 1894 1895 node->size = 1 + 2 * count; 1896 node->color = node->size; 1897 1898 if (drm_mm_reserve_node(&mm, node)) { 1899 KUNIT_FAIL(test, "initial reserve failed!\n"); 1900 goto out; 1901 } 1902 1903 last = node->start + node->size; 1904 1905 for (n = 1; n <= count; n++) { 1906 int rem; 1907 1908 node = kzalloc(sizeof(*node), GFP_KERNEL); 1909 if (!node) 1910 goto out; 1911 1912 node->start = last; 1913 node->size = n + count; 1914 node->color = node->size; 1915 1916 if (drm_mm_reserve_node(&mm, node) != -ENOSPC) { 1917 KUNIT_FAIL(test, "reserve %d did not report color overlap!", n); 1918 goto out; 1919 } 1920 1921 node->start += n + 1; 1922 rem = misalignment(node, n + count); 1923 node->start += n + count - rem; 1924 1925 if (drm_mm_reserve_node(&mm, node)) { 1926 KUNIT_FAIL(test, "reserve %d failed", n); 1927 goto out; 1928 } 1929 1930 last = node->start + node->size; 1931 } 1932 1933 for (n = 1; n <= count; n++) { 1934 node = kzalloc(sizeof(*node), GFP_KERNEL); 1935 if (!node) 1936 goto out; 1937 1938 if (!expect_insert(test, &mm, node, n, n, n, mode)) { 1939 KUNIT_FAIL(test, "%s insert failed, step %d\n", mode->name, n); 1940 kfree(node); 1941 goto out; 1942 } 1943 } 1944 1945 drm_mm_for_each_node_safe(node, nn, &mm) { 1946 u64 rem; 1947 1948 if (node->color != node->size) { 1949 KUNIT_FAIL(test, 1950 "%s invalid color stored: expected %lld, found %ld\n", 1951 mode->name, node->size, node->color); 1952 1953 goto out; 1954 } 1955 1956 if (colors_abutt(test, node)) 1957 goto out; 1958 1959 div64_u64_rem(node->start, node->size, &rem); 1960 if (rem) { 1961 KUNIT_FAIL(test, 1962 "%s colored node misaligned, start=%llx expected alignment=%lld [rem=%lld]\n", 1963 mode->name, node->start, node->size, rem); 1964 goto out; 1965 } 1966 1967 drm_mm_remove_node(node); 1968 kfree(node); 1969 } 1970 1971 cond_resched(); 1972 } 1973 1974 out: 1975 drm_mm_for_each_node_safe(node, nn, &mm) { 1976 drm_mm_remove_node(node); 1977 kfree(node); 1978 } 1979 drm_mm_takedown(&mm); 1980 } 1981 1982 static int evict_color(struct kunit *test, struct drm_mm *mm, u64 range_start, 1983 u64 range_end, struct evict_node *nodes, unsigned int *order, 1984 unsigned int count, unsigned int size, unsigned int alignment, 1985 unsigned long color, const struct insert_mode *mode) 1986 { 1987 struct drm_mm_scan scan; 1988 LIST_HEAD(evict_list); 1989 struct evict_node *e; 1990 struct drm_mm_node tmp; 1991 int err; 1992 1993 drm_mm_scan_init_with_range(&scan, mm, size, alignment, color, range_start, 1994 range_end, mode->mode); 1995 if (!evict_nodes(test, &scan, nodes, order, count, true, &evict_list)) 1996 return -EINVAL; 1997 1998 memset(&tmp, 0, sizeof(tmp)); 1999 err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, color, 2000 DRM_MM_INSERT_EVICT); 2001 if (err) { 2002 KUNIT_FAIL(test, 2003 "Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n", 2004 size, alignment, color, err); 2005 show_scan(test, &scan); 2006 show_holes(test, mm, 3); 2007 return err; 2008 } 2009 2010 if (tmp.start < range_start || tmp.start + tmp.size > range_end) { 2011 KUNIT_FAIL(test, 2012 "Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n", 2013 tmp.start, tmp.size, range_start, range_end); 2014 err = -EINVAL; 2015 } 2016 2017 if (colors_abutt(test, &tmp)) 2018 err = -EINVAL; 2019 2020 if (!assert_node(test, &tmp, mm, size, alignment, color)) { 2021 KUNIT_FAIL(test, 2022 "Inserted did not fit the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx\n", 2023 tmp.size, size, alignment, misalignment(&tmp, alignment), tmp.start); 2024 err = -EINVAL; 2025 } 2026 2027 drm_mm_remove_node(&tmp); 2028 if (err) 2029 return err; 2030 2031 list_for_each_entry(e, &evict_list, link) { 2032 err = drm_mm_reserve_node(mm, &e->node); 2033 if (err) { 2034 KUNIT_FAIL(test, "Failed to reinsert node after eviction: start=%llx\n", 2035 e->node.start); 2036 return err; 2037 } 2038 } 2039 2040 cond_resched(); 2041 return 0; 2042 } 2043 2044 static void igt_mm_color_evict(struct kunit *test) 2045 { 2046 DRM_RND_STATE(prng, random_seed); 2047 const unsigned int total_size = min(8192u, max_iterations); 2048 const struct insert_mode *mode; 2049 unsigned long color = 0; 2050 struct drm_mm mm; 2051 struct evict_node *nodes; 2052 struct drm_mm_node *node, *next; 2053 unsigned int *order, n; 2054 2055 /* Check that the drm_mm_scan also honours color adjustment when 2056 * choosing its victims to create a hole. Our color_adjust does not 2057 * allow two nodes to be placed together without an intervening hole 2058 * enlarging the set of victims that must be evicted. 2059 */ 2060 2061 nodes = vzalloc(array_size(total_size, sizeof(*nodes))); 2062 KUNIT_ASSERT_TRUE(test, nodes); 2063 2064 order = drm_random_order(total_size, &prng); 2065 if (!order) 2066 goto err_nodes; 2067 2068 drm_mm_init(&mm, 0, 2 * total_size - 1); 2069 mm.color_adjust = separate_adjacent_colors; 2070 for (n = 0; n < total_size; n++) { 2071 if (!expect_insert(test, &mm, &nodes[n].node, 2072 1, 0, color++, 2073 &insert_modes[0])) { 2074 KUNIT_FAIL(test, "insert failed, step %d\n", n); 2075 goto out; 2076 } 2077 } 2078 2079 for (mode = evict_modes; mode->name; mode++) { 2080 for (n = 1; n <= total_size; n <<= 1) { 2081 drm_random_reorder(order, total_size, &prng); 2082 if (evict_color(test, &mm, 0, U64_MAX, nodes, order, total_size, 2083 n, 1, color++, mode)) { 2084 KUNIT_FAIL(test, "%s evict_color(size=%u) failed\n", mode->name, n); 2085 goto out; 2086 } 2087 } 2088 2089 for (n = 1; n < total_size; n <<= 1) { 2090 drm_random_reorder(order, total_size, &prng); 2091 if (evict_color(test, &mm, 0, U64_MAX, nodes, order, total_size, 2092 total_size / 2, n, color++, mode)) { 2093 KUNIT_FAIL(test, "%s evict_color(size=%u, alignment=%u) failed\n", 2094 mode->name, total_size / 2, n); 2095 goto out; 2096 } 2097 } 2098 2099 for_each_prime_number_from(n, 1, min(total_size, max_prime)) { 2100 unsigned int nsize = (total_size - n + 1) / 2; 2101 2102 DRM_MM_BUG_ON(!nsize); 2103 2104 drm_random_reorder(order, total_size, &prng); 2105 if (evict_color(test, &mm, 0, U64_MAX, nodes, order, total_size, 2106 nsize, n, color++, mode)) { 2107 KUNIT_FAIL(test, "%s evict_color(size=%u, alignment=%u) failed\n", 2108 mode->name, nsize, n); 2109 goto out; 2110 } 2111 } 2112 2113 cond_resched(); 2114 } 2115 2116 out: 2117 drm_mm_for_each_node_safe(node, next, &mm) 2118 drm_mm_remove_node(node); 2119 drm_mm_takedown(&mm); 2120 kfree(order); 2121 err_nodes: 2122 vfree(nodes); 2123 } 2124 2125 static void igt_mm_color_evict_range(struct kunit *test) 2126 { 2127 DRM_RND_STATE(prng, random_seed); 2128 const unsigned int total_size = 8192; 2129 const unsigned int range_size = total_size / 2; 2130 const unsigned int range_start = total_size / 4; 2131 const unsigned int range_end = range_start + range_size; 2132 const struct insert_mode *mode; 2133 unsigned long color = 0; 2134 struct drm_mm mm; 2135 struct evict_node *nodes; 2136 struct drm_mm_node *node, *next; 2137 unsigned int *order, n; 2138 2139 /* Like igt_color_evict(), but limited to small portion of the full 2140 * drm_mm range. 2141 */ 2142 2143 nodes = vzalloc(array_size(total_size, sizeof(*nodes))); 2144 KUNIT_ASSERT_TRUE(test, nodes); 2145 2146 order = drm_random_order(total_size, &prng); 2147 if (!order) 2148 goto err_nodes; 2149 2150 drm_mm_init(&mm, 0, 2 * total_size - 1); 2151 mm.color_adjust = separate_adjacent_colors; 2152 for (n = 0; n < total_size; n++) { 2153 if (!expect_insert(test, &mm, &nodes[n].node, 2154 1, 0, color++, 2155 &insert_modes[0])) { 2156 KUNIT_FAIL(test, "insert failed, step %d\n", n); 2157 goto out; 2158 } 2159 } 2160 2161 for (mode = evict_modes; mode->name; mode++) { 2162 for (n = 1; n <= range_size; n <<= 1) { 2163 drm_random_reorder(order, range_size, &prng); 2164 if (evict_color(test, &mm, range_start, range_end, nodes, order, 2165 total_size, n, 1, color++, mode)) { 2166 KUNIT_FAIL(test, 2167 "%s evict_color(size=%u) failed for range [%x, %x]\n", 2168 mode->name, n, range_start, range_end); 2169 goto out; 2170 } 2171 } 2172 2173 for (n = 1; n < range_size; n <<= 1) { 2174 drm_random_reorder(order, total_size, &prng); 2175 if (evict_color(test, &mm, range_start, range_end, nodes, order, 2176 total_size, range_size / 2, n, color++, mode)) { 2177 KUNIT_FAIL(test, 2178 "%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n", 2179 mode->name, total_size / 2, n, range_start, range_end); 2180 goto out; 2181 } 2182 } 2183 2184 for_each_prime_number_from(n, 1, min(range_size, max_prime)) { 2185 unsigned int nsize = (range_size - n + 1) / 2; 2186 2187 DRM_MM_BUG_ON(!nsize); 2188 2189 drm_random_reorder(order, total_size, &prng); 2190 if (evict_color(test, &mm, range_start, range_end, nodes, order, 2191 total_size, nsize, n, color++, mode)) { 2192 KUNIT_FAIL(test, 2193 "%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n", 2194 mode->name, nsize, n, range_start, range_end); 2195 goto out; 2196 } 2197 } 2198 2199 cond_resched(); 2200 } 2201 2202 out: 2203 drm_mm_for_each_node_safe(node, next, &mm) 2204 drm_mm_remove_node(node); 2205 drm_mm_takedown(&mm); 2206 kfree(order); 2207 err_nodes: 2208 vfree(nodes); 2209 } 2210 2211 static int drm_mm_init_test(struct kunit *test) 2212 { 2213 while (!random_seed) 2214 random_seed = get_random_int(); 2215 2216 return 0; 2217 } 2218 2219 module_param(random_seed, uint, 0400); 2220 module_param(max_iterations, uint, 0400); 2221 module_param(max_prime, uint, 0400); 2222 2223 static struct kunit_case drm_mm_tests[] = { 2224 KUNIT_CASE(igt_mm_init), 2225 KUNIT_CASE(igt_mm_debug), 2226 KUNIT_CASE(igt_mm_reserve), 2227 KUNIT_CASE(igt_mm_insert), 2228 KUNIT_CASE(igt_mm_replace), 2229 KUNIT_CASE(igt_mm_insert_range), 2230 KUNIT_CASE(igt_mm_frag), 2231 KUNIT_CASE(igt_mm_align), 2232 KUNIT_CASE(igt_mm_align32), 2233 KUNIT_CASE(igt_mm_align64), 2234 KUNIT_CASE(igt_mm_evict), 2235 KUNIT_CASE(igt_mm_evict_range), 2236 KUNIT_CASE(igt_mm_topdown), 2237 KUNIT_CASE(igt_mm_bottomup), 2238 KUNIT_CASE(igt_mm_lowest), 2239 KUNIT_CASE(igt_mm_highest), 2240 KUNIT_CASE(igt_mm_color), 2241 KUNIT_CASE(igt_mm_color_evict), 2242 KUNIT_CASE(igt_mm_color_evict_range), 2243 {} 2244 }; 2245 2246 static struct kunit_suite drm_mm_test_suite = { 2247 .name = "drm_mm", 2248 .init = drm_mm_init_test, 2249 .test_cases = drm_mm_tests, 2250 }; 2251 2252 kunit_test_suite(drm_mm_test_suite); 2253 2254 MODULE_AUTHOR("Intel Corporation"); 2255 MODULE_LICENSE("GPL"); 2256