drivers/gpu/drm/selftests/test-drm_mm.c

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