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 misalinged, 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         drm_mm_for_each_node_in_range(node, mm, 0, start) {
 843                 if (node) {
 844                         pr_err("node before start: node=%llx+%llu, start=%llx\n",
 845                                node->start, node->size, start);
 846                         return false;
 847                 }
 848         }
 849
 850         drm_mm_for_each_node_in_range(node, mm, end, U64_MAX) {
 851                 if (node) {
 852                         pr_err("node after end: node=%llx+%llu, end=%llx\n",
 853                                node->start, node->size, end);
 854                         return false;
 855                 }
 856         }
 857
 858         return true;
 859 }
 860
 861 static int __igt_insert_range(unsigned int count, u64 size, u64 start, u64 end)
 862 {
 863         const struct insert_mode *mode;
 864         struct drm_mm mm;
 865         struct drm_mm_node *nodes, *node, *next;
 866         unsigned int n, start_n, end_n;
 867         int ret;
 868
 869         DRM_MM_BUG_ON(!count);
 870         DRM_MM_BUG_ON(!size);
 871         DRM_MM_BUG_ON(end <= start);
 872
 873         /* Very similar to __igt_insert(), but now instead of populating the
 874          * full range of the drm_mm, we try to fill a small portion of it.
 875          */
 876
 877         ret = -ENOMEM;
 878         nodes = vzalloc(count * sizeof(*nodes));
 879         if (!nodes)
 880                 goto err;
 881
 882         ret = -EINVAL;
 883         drm_mm_init(&mm, 0, count * size);
 884
 885         start_n = div64_u64(start + size - 1, size);
 886         end_n = div64_u64(end - size, size);
 887
 888         for (mode = insert_modes; mode->name; mode++) {
 889                 for (n = start_n; n <= end_n; n++) {
 890                         if (!expect_insert_in_range(&mm, &nodes[n],
 891                                                     size, size, n,
 892                                                     start, end, mode)) {
 893                                 pr_err("%s insert failed, size %llu, step %d [%d, %d], range [%llx, %llx]\n",
 894                                        mode->name, size, n,
 895                                        start_n, end_n,
 896                                        start, end);
 897                                 goto out;
 898                         }
 899                 }
 900
 901                 if (!assert_contiguous_in_range(&mm, size, start, end)) {
 902                         pr_err("%s: range [%llx, %llx] not full after initialisation, size=%llu\n",
 903                                mode->name, start, end, size);
 904                         goto out;
 905                 }
 906
 907                 /* Remove one and reinsert, it should refill itself */
 908                 for (n = start_n; n <= end_n; n++) {
 909                         u64 addr = nodes[n].start;
 910
 911                         drm_mm_remove_node(&nodes[n]);
 912                         if (!expect_insert_in_range(&mm, &nodes[n],
 913                                                     size, size, n,
 914                                                     start, end, mode)) {
 915                                 pr_err("%s reinsert failed, step %d\n", mode->name, n);
 916                                 goto out;
 917                         }
 918
 919                         if (nodes[n].start != addr) {
 920                                 pr_err("%s reinsert node moved, step %d, expected %llx, found %llx\n",
 921                                        mode->name, n, addr, nodes[n].start);
 922                                 goto out;
 923                         }
 924                 }
 925
 926                 if (!assert_contiguous_in_range(&mm, size, start, end)) {
 927                         pr_err("%s: range [%llx, %llx] not full after reinsertion, size=%llu\n",
 928                                mode->name, start, end, size);
 929                         goto out;
 930                 }
 931
 932                 drm_mm_for_each_node_safe(node, next, &mm)
 933                         drm_mm_remove_node(node);
 934                 DRM_MM_BUG_ON(!drm_mm_clean(&mm));
 935         }
 936
 937         ret = 0;
 938 out:
 939         drm_mm_for_each_node_safe(node, next, &mm)
 940                 drm_mm_remove_node(node);
 941         drm_mm_takedown(&mm);
 942         vfree(nodes);
 943 err:
 944         return ret;
 945 }
 946
 947 static int insert_outside_range(void)
 948 {
 949         struct drm_mm mm;
 950         const unsigned int start = 1024;
 951         const unsigned int end = 2048;
 952         const unsigned int size = end - start;
 953
 954         drm_mm_init(&mm, start, size);
 955
 956         if (!expect_insert_in_range_fail(&mm, 1, 0, start))
 957                 return -EINVAL;
 958
 959         if (!expect_insert_in_range_fail(&mm, size,
 960                                          start - size/2, start + (size+1)/2))
 961                 return -EINVAL;
 962
 963         if (!expect_insert_in_range_fail(&mm, size,
 964                                          end - (size+1)/2, end + size/2))
 965                 return -EINVAL;
 966
 967         if (!expect_insert_in_range_fail(&mm, 1, end, end + size))
 968                 return -EINVAL;
 969
 970         drm_mm_takedown(&mm);
 971         return 0;
 972 }
 973
 974 static int igt_insert_range(void *ignored)
 975 {
 976         const unsigned int count = min_t(unsigned int, BIT(13), max_iterations);
 977         unsigned int n;
 978         int ret;
 979
 980         /* Check that requests outside the bounds of drm_mm are rejected. */
 981         ret = insert_outside_range();
 982         if (ret)
 983                 return ret;
 984
 985         for_each_prime_number_from(n, 1, 50) {
 986                 const u64 size = BIT_ULL(n);
 987                 const u64 max = count * size;
 988
 989                 ret = __igt_insert_range(count, size, 0, max);
 990                 if (ret)
 991                         return ret;
 992
 993                 ret = __igt_insert_range(count, size, 1, max);
 994                 if (ret)
 995                         return ret;
 996
 997                 ret = __igt_insert_range(count, size, 0, max - 1);
 998                 if (ret)
 999                         return ret;
1000
1001                 ret = __igt_insert_range(count, size, 0, max/2);
1002                 if (ret)
1003                         return ret;
1004
1005                 ret = __igt_insert_range(count, size, max/2, max);
1006                 if (ret)
1007                         return ret;
1008
1009                 ret = __igt_insert_range(count, size, max/4+1, 3*max/4-1);
1010                 if (ret)
1011                         return ret;
1012         }
1013
1014         return 0;
1015 }
1016
1017 static int igt_align(void *ignored)
1018 {
1019         const struct insert_mode *mode;
1020         const unsigned int max_count = min(8192u, max_prime);
1021         struct drm_mm mm;
1022         struct drm_mm_node *nodes, *node, *next;
1023         unsigned int prime;
1024         int ret = -EINVAL;
1025
1026         /* For each of the possible insertion modes, we pick a few
1027          * arbitrary alignments and check that the inserted node
1028          * meets our requirements.
1029          */
1030
1031         nodes = vzalloc(max_count * sizeof(*nodes));
1032         if (!nodes)
1033                 goto err;
1034
1035         drm_mm_init(&mm, 1, U64_MAX - 2);
1036
1037         for (mode = insert_modes; mode->name; mode++) {
1038                 unsigned int i = 0;
1039
1040                 for_each_prime_number_from(prime, 1, max_count) {
1041                         u64 size = next_prime_number(prime);
1042
1043                         if (!expect_insert(&mm, &nodes[i],
1044                                            size, prime, i,
1045                                            mode)) {
1046                                 pr_err("%s insert failed with alignment=%d",
1047                                        mode->name, prime);
1048                                 goto out;
1049                         }
1050
1051                         i++;
1052                 }
1053
1054                 drm_mm_for_each_node_safe(node, next, &mm)
1055                         drm_mm_remove_node(node);
1056                 DRM_MM_BUG_ON(!drm_mm_clean(&mm));
1057         }
1058
1059         ret = 0;
1060 out:
1061         drm_mm_for_each_node_safe(node, next, &mm)
1062                 drm_mm_remove_node(node);
1063         drm_mm_takedown(&mm);
1064         vfree(nodes);
1065 err:
1066         return ret;
1067 }
1068
1069 static int igt_align_pot(int max)
1070 {
1071         struct drm_mm mm;
1072         struct drm_mm_node *node, *next;
1073         int bit;
1074         int ret = -EINVAL;
1075
1076         /* Check that we can align to the full u64 address space */
1077
1078         drm_mm_init(&mm, 1, U64_MAX - 2);
1079
1080         for (bit = max - 1; bit; bit--) {
1081                 u64 align, size;
1082
1083                 node = kzalloc(sizeof(*node), GFP_KERNEL);
1084                 if (!node) {
1085                         ret = -ENOMEM;
1086                         goto out;
1087                 }
1088
1089                 align = BIT_ULL(bit);
1090                 size = BIT_ULL(bit-1) + 1;
1091                 if (!expect_insert(&mm, node,
1092                                    size, align, bit,
1093                                    &insert_modes[0])) {
1094                         pr_err("insert failed with alignment=%llx [%d]",
1095                                align, bit);
1096                         goto out;
1097                 }
1098         }
1099
1100         ret = 0;
1101 out:
1102         drm_mm_for_each_node_safe(node, next, &mm) {
1103                 drm_mm_remove_node(node);
1104                 kfree(node);
1105         }
1106         drm_mm_takedown(&mm);
1107         return ret;
1108 }
1109
1110 static int igt_align32(void *ignored)
1111 {
1112         return igt_align_pot(32);
1113 }
1114
1115 static int igt_align64(void *ignored)
1116 {
1117         return igt_align_pot(64);
1118 }
1119
1120 static void show_scan(const struct drm_mm_scan *scan)
1121 {
1122         pr_info("scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n",
1123                 scan->hit_start, scan->hit_end,
1124                 scan->size, scan->alignment, scan->color);
1125 }
1126
1127 static void show_holes(const struct drm_mm *mm, int count)
1128 {
1129         u64 hole_start, hole_end;
1130         struct drm_mm_node *hole;
1131
1132         drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
1133                 struct drm_mm_node *next = list_next_entry(hole, node_list);
1134                 const char *node1 = NULL, *node2 = NULL;
1135
1136                 if (hole->allocated)
1137                         node1 = kasprintf(GFP_KERNEL,
1138                                           "[%llx + %lld, color=%ld], ",
1139                                           hole->start, hole->size, hole->color);
1140
1141                 if (next->allocated)
1142                         node2 = kasprintf(GFP_KERNEL,
1143                                           ", [%llx + %lld, color=%ld]",
1144                                           next->start, next->size, next->color);
1145
1146                 pr_info("%sHole [%llx - %llx, size %lld]%s\n",
1147                         node1,
1148                         hole_start, hole_end, hole_end - hole_start,
1149                         node2);
1150
1151                 kfree(node2);
1152                 kfree(node1);
1153
1154                 if (!--count)
1155                         break;
1156         }
1157 }
1158
1159 struct evict_node {
1160         struct drm_mm_node node;
1161         struct list_head link;
1162 };
1163
1164 static bool evict_nodes(struct drm_mm_scan *scan,
1165                         struct evict_node *nodes,
1166                         unsigned int *order,
1167                         unsigned int count,
1168                         bool use_color,
1169                         struct list_head *evict_list)
1170 {
1171         struct evict_node *e, *en;
1172         unsigned int i;
1173
1174         for (i = 0; i < count; i++) {
1175                 e = &nodes[order ? order[i] : i];
1176                 list_add(&e->link, evict_list);
1177                 if (drm_mm_scan_add_block(scan, &e->node))
1178                         break;
1179         }
1180         list_for_each_entry_safe(e, en, evict_list, link) {
1181                 if (!drm_mm_scan_remove_block(scan, &e->node))
1182                         list_del(&e->link);
1183         }
1184         if (list_empty(evict_list)) {
1185                 pr_err("Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n",
1186                        scan->size, count, scan->alignment, scan->color);
1187                 return false;
1188         }
1189
1190         list_for_each_entry(e, evict_list, link)
1191                 drm_mm_remove_node(&e->node);
1192
1193         if (use_color) {
1194                 struct drm_mm_node *node;
1195
1196                 while ((node = drm_mm_scan_color_evict(scan))) {
1197                         e = container_of(node, typeof(*e), node);
1198                         drm_mm_remove_node(&e->node);
1199                         list_add(&e->link, evict_list);
1200                 }
1201         } else {
1202                 if (drm_mm_scan_color_evict(scan)) {
1203                         pr_err("drm_mm_scan_color_evict unexpectedly reported overlapping nodes!\n");
1204                         return false;
1205                 }
1206         }
1207
1208         return true;
1209 }
1210
1211 static bool evict_nothing(struct drm_mm *mm,
1212                           unsigned int total_size,
1213                           struct evict_node *nodes)
1214 {
1215         struct drm_mm_scan scan;
1216         LIST_HEAD(evict_list);
1217         struct evict_node *e;
1218         struct drm_mm_node *node;
1219         unsigned int n;
1220
1221         drm_mm_scan_init(&scan, mm, 1, 0, 0, 0);
1222         for (n = 0; n < total_size; n++) {
1223                 e = &nodes[n];
1224                 list_add(&e->link, &evict_list);
1225                 drm_mm_scan_add_block(&scan, &e->node);
1226         }
1227         list_for_each_entry(e, &evict_list, link)
1228                 drm_mm_scan_remove_block(&scan, &e->node);
1229
1230         for (n = 0; n < total_size; n++) {
1231                 e = &nodes[n];
1232
1233                 if (!drm_mm_node_allocated(&e->node)) {
1234                         pr_err("node[%d] no longer allocated!\n", n);
1235                         return false;
1236                 }
1237
1238                 e->link.next = NULL;
1239         }
1240
1241         drm_mm_for_each_node(node, mm) {
1242                 e = container_of(node, typeof(*e), node);
1243                 e->link.next = &e->link;
1244         }
1245
1246         for (n = 0; n < total_size; n++) {
1247                 e = &nodes[n];
1248
1249                 if (!e->link.next) {
1250                         pr_err("node[%d] no longer connected!\n", n);
1251                         return false;
1252                 }
1253         }
1254
1255         return assert_continuous(mm, nodes[0].node.size);
1256 }
1257
1258 static bool evict_everything(struct drm_mm *mm,
1259                              unsigned int total_size,
1260                              struct evict_node *nodes)
1261 {
1262         struct drm_mm_scan scan;
1263         LIST_HEAD(evict_list);
1264         struct evict_node *e;
1265         unsigned int n;
1266         int err;
1267
1268         drm_mm_scan_init(&scan, mm, total_size, 0, 0, 0);
1269         for (n = 0; n < total_size; n++) {
1270                 e = &nodes[n];
1271                 list_add(&e->link, &evict_list);
1272                 if (drm_mm_scan_add_block(&scan, &e->node))
1273                         break;
1274         }
1275
1276         err = 0;
1277         list_for_each_entry(e, &evict_list, link) {
1278                 if (!drm_mm_scan_remove_block(&scan, &e->node)) {
1279                         if (!err) {
1280                                 pr_err("Node %lld not marked for eviction!\n",
1281                                        e->node.start);
1282                                 err = -EINVAL;
1283                         }
1284                 }
1285         }
1286         if (err)
1287                 return false;
1288
1289         list_for_each_entry(e, &evict_list, link)
1290                 drm_mm_remove_node(&e->node);
1291
1292         if (!assert_one_hole(mm, 0, total_size))
1293                 return false;
1294
1295         list_for_each_entry(e, &evict_list, link) {
1296                 err = drm_mm_reserve_node(mm, &e->node);
1297                 if (err) {
1298                         pr_err("Failed to reinsert node after eviction: start=%llx\n",
1299                                e->node.start);
1300                         return false;
1301                 }
1302         }
1303
1304         return assert_continuous(mm, nodes[0].node.size);
1305 }
1306
1307 static int evict_something(struct drm_mm *mm,
1308                            u64 range_start, u64 range_end,
1309                            struct evict_node *nodes,
1310                            unsigned int *order,
1311                            unsigned int count,
1312                            unsigned int size,
1313                            unsigned int alignment,
1314                            const struct insert_mode *mode)
1315 {
1316         struct drm_mm_scan scan;
1317         LIST_HEAD(evict_list);
1318         struct evict_node *e;
1319         struct drm_mm_node tmp;
1320         int err;
1321
1322         drm_mm_scan_init_with_range(&scan, mm,
1323                                     size, alignment, 0,
1324                                     range_start, range_end,
1325                                     mode->mode);
1326         if (!evict_nodes(&scan,
1327                          nodes, order, count, false,
1328                          &evict_list))
1329                 return -EINVAL;
1330
1331         memset(&tmp, 0, sizeof(tmp));
1332         err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, 0,
1333                                          DRM_MM_INSERT_EVICT);
1334         if (err) {
1335                 pr_err("Failed to insert into eviction hole: size=%d, align=%d\n",
1336                        size, alignment);
1337                 show_scan(&scan);
1338                 show_holes(mm, 3);
1339                 return err;
1340         }
1341
1342         if (tmp.start < range_start || tmp.start + tmp.size > range_end) {
1343                 pr_err("Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
1344                        tmp.start, tmp.size, range_start, range_end);
1345                 err = -EINVAL;
1346         }
1347
1348         if (!assert_node(&tmp, mm, size, alignment, 0) ||
1349             drm_mm_hole_follows(&tmp)) {
1350                 pr_err("Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n",
1351                        tmp.size, size,
1352                        alignment, misalignment(&tmp, alignment),
1353                        tmp.start, drm_mm_hole_follows(&tmp));
1354                 err = -EINVAL;
1355         }
1356
1357         drm_mm_remove_node(&tmp);
1358         if (err)
1359                 return err;
1360
1361         list_for_each_entry(e, &evict_list, link) {
1362                 err = drm_mm_reserve_node(mm, &e->node);
1363                 if (err) {
1364                         pr_err("Failed to reinsert node after eviction: start=%llx\n",
1365                                e->node.start);
1366                         return err;
1367                 }
1368         }
1369
1370         if (!assert_continuous(mm, nodes[0].node.size)) {
1371                 pr_err("range is no longer continuous\n");
1372                 return -EINVAL;
1373         }
1374
1375         return 0;
1376 }
1377
1378 static int igt_evict(void *ignored)
1379 {
1380         DRM_RND_STATE(prng, random_seed);
1381         const unsigned int size = 8192;
1382         const struct insert_mode *mode;
1383         struct drm_mm mm;
1384         struct evict_node *nodes;
1385         struct drm_mm_node *node, *next;
1386         unsigned int *order, n;
1387         int ret, err;
1388
1389         /* Here we populate a full drm_mm and then try and insert a new node
1390          * by evicting other nodes in a random order. The drm_mm_scan should
1391          * pick the first matching hole it finds from the random list. We
1392          * repeat that for different allocation strategies, alignments and
1393          * sizes to try and stress the hole finder.
1394          */
1395
1396         ret = -ENOMEM;
1397         nodes = vzalloc(size * sizeof(*nodes));
1398         if (!nodes)
1399                 goto err;
1400
1401         order = drm_random_order(size, &prng);
1402         if (!order)
1403                 goto err_nodes;
1404
1405         ret = -EINVAL;
1406         drm_mm_init(&mm, 0, size);
1407         for (n = 0; n < size; n++) {
1408                 err = drm_mm_insert_node(&mm, &nodes[n].node, 1);
1409                 if (err) {
1410                         pr_err("insert failed, step %d\n", n);
1411                         ret = err;
1412                         goto out;
1413                 }
1414         }
1415
1416         /* First check that using the scanner doesn't break the mm */
1417         if (!evict_nothing(&mm, size, nodes)) {
1418                 pr_err("evict_nothing() failed\n");
1419                 goto out;
1420         }
1421         if (!evict_everything(&mm, size, nodes)) {
1422                 pr_err("evict_everything() failed\n");
1423                 goto out;
1424         }
1425
1426         for (mode = evict_modes; mode->name; mode++) {
1427                 for (n = 1; n <= size; n <<= 1) {
1428                         drm_random_reorder(order, size, &prng);
1429                         err = evict_something(&mm, 0, U64_MAX,
1430                                               nodes, order, size,
1431                                               n, 1,
1432                                               mode);
1433                         if (err) {
1434                                 pr_err("%s evict_something(size=%u) failed\n",
1435                                        mode->name, n);
1436                                 ret = err;
1437                                 goto out;
1438                         }
1439                 }
1440
1441                 for (n = 1; n < size; n <<= 1) {
1442                         drm_random_reorder(order, size, &prng);
1443                         err = evict_something(&mm, 0, U64_MAX,
1444                                               nodes, order, size,
1445                                               size/2, n,
1446                                               mode);
1447                         if (err) {
1448                                 pr_err("%s evict_something(size=%u, alignment=%u) failed\n",
1449                                        mode->name, size/2, n);
1450                                 ret = err;
1451                                 goto out;
1452                         }
1453                 }
1454
1455                 for_each_prime_number_from(n, 1, min(size, max_prime)) {
1456                         unsigned int nsize = (size - n + 1) / 2;
1457
1458                         DRM_MM_BUG_ON(!nsize);
1459
1460                         drm_random_reorder(order, size, &prng);
1461                         err = evict_something(&mm, 0, U64_MAX,
1462                                               nodes, order, size,
1463                                               nsize, n,
1464                                               mode);
1465                         if (err) {
1466                                 pr_err("%s evict_something(size=%u, alignment=%u) failed\n",
1467                                        mode->name, nsize, n);
1468                                 ret = err;
1469                                 goto out;
1470                         }
1471                 }
1472         }
1473
1474         ret = 0;
1475 out:
1476         drm_mm_for_each_node_safe(node, next, &mm)
1477                 drm_mm_remove_node(node);
1478         drm_mm_takedown(&mm);
1479         kfree(order);
1480 err_nodes:
1481         vfree(nodes);
1482 err:
1483         return ret;
1484 }
1485
1486 static int igt_evict_range(void *ignored)
1487 {
1488         DRM_RND_STATE(prng, random_seed);
1489         const unsigned int size = 8192;
1490         const unsigned int range_size = size / 2;
1491         const unsigned int range_start = size / 4;
1492         const unsigned int range_end = range_start + range_size;
1493         const struct insert_mode *mode;
1494         struct drm_mm mm;
1495         struct evict_node *nodes;
1496         struct drm_mm_node *node, *next;
1497         unsigned int *order, n;
1498         int ret, err;
1499
1500         /* Like igt_evict() but now we are limiting the search to a
1501          * small portion of the full drm_mm.
1502          */
1503
1504         ret = -ENOMEM;
1505         nodes = vzalloc(size * sizeof(*nodes));
1506         if (!nodes)
1507                 goto err;
1508
1509         order = drm_random_order(size, &prng);
1510         if (!order)
1511                 goto err_nodes;
1512
1513         ret = -EINVAL;
1514         drm_mm_init(&mm, 0, size);
1515         for (n = 0; n < size; n++) {
1516                 err = drm_mm_insert_node(&mm, &nodes[n].node, 1);
1517                 if (err) {
1518                         pr_err("insert failed, step %d\n", n);
1519                         ret = err;
1520                         goto out;
1521                 }
1522         }
1523
1524         for (mode = evict_modes; mode->name; mode++) {
1525                 for (n = 1; n <= range_size; n <<= 1) {
1526                         drm_random_reorder(order, size, &prng);
1527                         err = evict_something(&mm, range_start, range_end,
1528                                               nodes, order, size,
1529                                               n, 1,
1530                                               mode);
1531                         if (err) {
1532                                 pr_err("%s evict_something(size=%u) failed with range [%u, %u]\n",
1533                                        mode->name, n, range_start, range_end);
1534                                 goto out;
1535                         }
1536                 }
1537
1538                 for (n = 1; n <= range_size; n <<= 1) {
1539                         drm_random_reorder(order, size, &prng);
1540                         err = evict_something(&mm, range_start, range_end,
1541                                               nodes, order, size,
1542                                               range_size/2, n,
1543                                               mode);
1544                         if (err) {
1545                                 pr_err("%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
1546                                        mode->name, range_size/2, n, range_start, range_end);
1547                                 goto out;
1548                         }
1549                 }
1550
1551                 for_each_prime_number_from(n, 1, min(range_size, max_prime)) {
1552                         unsigned int nsize = (range_size - n + 1) / 2;
1553
1554                         DRM_MM_BUG_ON(!nsize);
1555
1556                         drm_random_reorder(order, size, &prng);
1557                         err = evict_something(&mm, range_start, range_end,
1558                                               nodes, order, size,
1559                                               nsize, n,
1560                                               mode);
1561                         if (err) {
1562                                 pr_err("%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
1563                                        mode->name, nsize, n, range_start, range_end);
1564                                 goto out;
1565                         }
1566                 }
1567         }
1568
1569         ret = 0;
1570 out:
1571         drm_mm_for_each_node_safe(node, next, &mm)
1572                 drm_mm_remove_node(node);
1573         drm_mm_takedown(&mm);
1574         kfree(order);
1575 err_nodes:
1576         vfree(nodes);
1577 err:
1578         return ret;
1579 }
1580
1581 static unsigned int node_index(const struct drm_mm_node *node)
1582 {
1583         return div64_u64(node->start, node->size);
1584 }
1585
1586 static int igt_topdown(void *ignored)
1587 {
1588         const struct insert_mode *topdown = &insert_modes[TOPDOWN];
1589         DRM_RND_STATE(prng, random_seed);
1590         const unsigned int count = 8192;
1591         unsigned int size;
1592         unsigned long *bitmap = NULL;
1593         struct drm_mm mm;
1594         struct drm_mm_node *nodes, *node, *next;
1595         unsigned int *order, n, m, o = 0;
1596         int ret;
1597
1598         /* When allocating top-down, we expect to be returned a node
1599          * from a suitable hole at the top of the drm_mm. We check that
1600          * the returned node does match the highest available slot.
1601          */
1602
1603         ret = -ENOMEM;
1604         nodes = vzalloc(count * sizeof(*nodes));
1605         if (!nodes)
1606                 goto err;
1607
1608         bitmap = kzalloc(count / BITS_PER_LONG * sizeof(unsigned long),
1609                          GFP_TEMPORARY);
1610         if (!bitmap)
1611                 goto err_nodes;
1612
1613         order = drm_random_order(count, &prng);
1614         if (!order)
1615                 goto err_bitmap;
1616
1617         ret = -EINVAL;
1618         for (size = 1; size <= 64; size <<= 1) {
1619                 drm_mm_init(&mm, 0, size*count);
1620                 for (n = 0; n < count; n++) {
1621                         if (!expect_insert(&mm, &nodes[n],
1622                                            size, 0, n,
1623                                            topdown)) {
1624                                 pr_err("insert failed, size %u step %d\n", size, n);
1625                                 goto out;
1626                         }
1627
1628                         if (drm_mm_hole_follows(&nodes[n])) {
1629                                 pr_err("hole after topdown insert %d, start=%llx\n, size=%u",
1630                                        n, nodes[n].start, size);
1631                                 goto out;
1632                         }
1633
1634                         if (!assert_one_hole(&mm, 0, size*(count - n - 1)))
1635                                 goto out;
1636                 }
1637
1638                 if (!assert_continuous(&mm, size))
1639                         goto out;
1640
1641                 drm_random_reorder(order, count, &prng);
1642                 for_each_prime_number_from(n, 1, min(count, max_prime)) {
1643                         for (m = 0; m < n; m++) {
1644                                 node = &nodes[order[(o + m) % count]];
1645                                 drm_mm_remove_node(node);
1646                                 __set_bit(node_index(node), bitmap);
1647                         }
1648
1649                         for (m = 0; m < n; m++) {
1650                                 unsigned int last;
1651
1652                                 node = &nodes[order[(o + m) % count]];
1653                                 if (!expect_insert(&mm, node,
1654                                                    size, 0, 0,
1655                                                    topdown)) {
1656                                         pr_err("insert failed, step %d/%d\n", m, n);
1657                                         goto out;
1658                                 }
1659
1660                                 if (drm_mm_hole_follows(node)) {
1661                                         pr_err("hole after topdown insert %d/%d, start=%llx\n",
1662                                                m, n, node->start);
1663                                         goto out;
1664                                 }
1665
1666                                 last = find_last_bit(bitmap, count);
1667                                 if (node_index(node) != last) {
1668                                         pr_err("node %d/%d, size %d, not inserted into upmost hole, expected %d, found %d\n",
1669                                                m, n, size, last, node_index(node));
1670                                         goto out;
1671                                 }
1672
1673                                 __clear_bit(last, bitmap);
1674                         }
1675
1676                         DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count);
1677
1678                         o += n;
1679                 }
1680
1681                 drm_mm_for_each_node_safe(node, next, &mm)
1682                         drm_mm_remove_node(node);
1683                 DRM_MM_BUG_ON(!drm_mm_clean(&mm));
1684         }
1685
1686         ret = 0;
1687 out:
1688         drm_mm_for_each_node_safe(node, next, &mm)
1689                 drm_mm_remove_node(node);
1690         drm_mm_takedown(&mm);
1691         kfree(order);
1692 err_bitmap:
1693         kfree(bitmap);
1694 err_nodes:
1695         vfree(nodes);
1696 err:
1697         return ret;
1698 }
1699
1700 static int igt_bottomup(void *ignored)
1701 {
1702         const struct insert_mode *bottomup = &insert_modes[BOTTOMUP];
1703         DRM_RND_STATE(prng, random_seed);
1704         const unsigned int count = 8192;
1705         unsigned int size;
1706         unsigned long *bitmap;
1707         struct drm_mm mm;
1708         struct drm_mm_node *nodes, *node, *next;
1709         unsigned int *order, n, m, o = 0;
1710         int ret;
1711
1712         /* Like igt_topdown, but instead of searching for the last hole,
1713          * we search for the first.
1714          */
1715
1716         ret = -ENOMEM;
1717         nodes = vzalloc(count * sizeof(*nodes));
1718         if (!nodes)
1719                 goto err;
1720
1721         bitmap = kzalloc(count / BITS_PER_LONG * sizeof(unsigned long),
1722                          GFP_TEMPORARY);
1723         if (!bitmap)
1724                 goto err_nodes;
1725
1726         order = drm_random_order(count, &prng);
1727         if (!order)
1728                 goto err_bitmap;
1729
1730         ret = -EINVAL;
1731         for (size = 1; size <= 64; size <<= 1) {
1732                 drm_mm_init(&mm, 0, size*count);
1733                 for (n = 0; n < count; n++) {
1734                         if (!expect_insert(&mm, &nodes[n],
1735                                            size, 0, n,
1736                                            bottomup)) {
1737                                 pr_err("bottomup insert failed, size %u step %d\n", size, n);
1738                                 goto out;
1739                         }
1740
1741                         if (!assert_one_hole(&mm, size*(n + 1), size*count))
1742                                 goto out;
1743                 }
1744
1745                 if (!assert_continuous(&mm, size))
1746                         goto out;
1747
1748                 drm_random_reorder(order, count, &prng);
1749                 for_each_prime_number_from(n, 1, min(count, max_prime)) {
1750                         for (m = 0; m < n; m++) {
1751                                 node = &nodes[order[(o + m) % count]];
1752                                 drm_mm_remove_node(node);
1753                                 __set_bit(node_index(node), bitmap);
1754                         }
1755
1756                         for (m = 0; m < n; m++) {
1757                                 unsigned int first;
1758
1759                                 node = &nodes[order[(o + m) % count]];
1760                                 if (!expect_insert(&mm, node,
1761                                                    size, 0, 0,
1762                                                    bottomup)) {
1763                                         pr_err("insert failed, step %d/%d\n", m, n);
1764                                         goto out;
1765                                 }
1766
1767                                 first = find_first_bit(bitmap, count);
1768                                 if (node_index(node) != first) {
1769                                         pr_err("node %d/%d not inserted into bottom hole, expected %d, found %d\n",
1770                                                m, n, first, node_index(node));
1771                                         goto out;
1772                                 }
1773                                 __clear_bit(first, bitmap);
1774                         }
1775
1776                         DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count);
1777
1778                         o += n;
1779                 }
1780
1781                 drm_mm_for_each_node_safe(node, next, &mm)
1782                         drm_mm_remove_node(node);
1783                 DRM_MM_BUG_ON(!drm_mm_clean(&mm));
1784         }
1785
1786         ret = 0;
1787 out:
1788         drm_mm_for_each_node_safe(node, next, &mm)
1789                 drm_mm_remove_node(node);
1790         drm_mm_takedown(&mm);
1791         kfree(order);
1792 err_bitmap:
1793         kfree(bitmap);
1794 err_nodes:
1795         vfree(nodes);
1796 err:
1797         return ret;
1798 }
1799
1800 static void separate_adjacent_colors(const struct drm_mm_node *node,
1801                                      unsigned long color,
1802                                      u64 *start,
1803                                      u64 *end)
1804 {
1805         if (node->allocated && node->color != color)
1806                 ++*start;
1807
1808         node = list_next_entry(node, node_list);
1809         if (node->allocated && node->color != color)
1810                 --*end;
1811 }
1812
1813 static bool colors_abutt(const struct drm_mm_node *node)
1814 {
1815         if (!drm_mm_hole_follows(node) &&
1816             list_next_entry(node, node_list)->allocated) {
1817                 pr_err("colors abutt; %ld [%llx + %llx] is next to %ld [%llx + %llx]!\n",
1818                        node->color, node->start, node->size,
1819                        list_next_entry(node, node_list)->color,
1820                        list_next_entry(node, node_list)->start,
1821                        list_next_entry(node, node_list)->size);
1822                 return true;
1823         }
1824
1825         return false;
1826 }
1827
1828 static int igt_color(void *ignored)
1829 {
1830         const unsigned int count = min(4096u, max_iterations);
1831         const struct insert_mode *mode;
1832         struct drm_mm mm;
1833         struct drm_mm_node *node, *nn;
1834         unsigned int n;
1835         int ret = -EINVAL, err;
1836
1837         /* Color adjustment complicates everything. First we just check
1838          * that when we insert a node we apply any color_adjustment callback.
1839          * The callback we use should ensure that there is a gap between
1840          * any two nodes, and so after each insertion we check that those
1841          * holes are inserted and that they are preserved.
1842          */
1843
1844         drm_mm_init(&mm, 0, U64_MAX);
1845
1846         for (n = 1; n <= count; n++) {
1847                 node = kzalloc(sizeof(*node), GFP_KERNEL);
1848                 if (!node) {
1849                         ret = -ENOMEM;
1850                         goto out;
1851                 }
1852
1853                 if (!expect_insert(&mm, node,
1854                                    n, 0, n,
1855                                    &insert_modes[0])) {
1856                         pr_err("insert failed, step %d\n", n);
1857                         kfree(node);
1858                         goto out;
1859                 }
1860         }
1861
1862         drm_mm_for_each_node_safe(node, nn, &mm) {
1863                 if (node->color != node->size) {
1864                         pr_err("invalid color stored: expected %lld, found %ld\n",
1865                                node->size, node->color);
1866
1867                         goto out;
1868                 }
1869
1870                 drm_mm_remove_node(node);
1871                 kfree(node);
1872         }
1873
1874         /* Now, let's start experimenting with applying a color callback */
1875         mm.color_adjust = separate_adjacent_colors;
1876         for (mode = insert_modes; mode->name; mode++) {
1877                 u64 last;
1878
1879                 node = kzalloc(sizeof(*node), GFP_KERNEL);
1880                 if (!node) {
1881                         ret = -ENOMEM;
1882                         goto out;
1883                 }
1884
1885                 node->size = 1 + 2*count;
1886                 node->color = node->size;
1887
1888                 err = drm_mm_reserve_node(&mm, node);
1889                 if (err) {
1890                         pr_err("initial reserve failed!\n");
1891                         ret = err;
1892                         goto out;
1893                 }
1894
1895                 last = node->start + node->size;
1896
1897                 for (n = 1; n <= count; n++) {
1898                         int rem;
1899
1900                         node = kzalloc(sizeof(*node), GFP_KERNEL);
1901                         if (!node) {
1902                                 ret = -ENOMEM;
1903                                 goto out;
1904                         }
1905
1906                         node->start = last;
1907                         node->size = n + count;
1908                         node->color = node->size;
1909
1910                         err = drm_mm_reserve_node(&mm, node);
1911                         if (err != -ENOSPC) {
1912                                 pr_err("reserve %d did not report color overlap! err=%d\n",
1913                                        n, err);
1914                                 goto out;
1915                         }
1916
1917                         node->start += n + 1;
1918                         rem = misalignment(node, n + count);
1919                         node->start += n + count - rem;
1920
1921                         err = drm_mm_reserve_node(&mm, node);
1922                         if (err) {
1923                                 pr_err("reserve %d failed, err=%d\n", n, err);
1924                                 ret = err;
1925                                 goto out;
1926                         }
1927
1928                         last = node->start + node->size;
1929                 }
1930
1931                 for (n = 1; n <= count; n++) {
1932                         node = kzalloc(sizeof(*node), GFP_KERNEL);
1933                         if (!node) {
1934                                 ret = -ENOMEM;
1935                                 goto out;
1936                         }
1937
1938                         if (!expect_insert(&mm, node,
1939                                            n, n, n,
1940                                            mode)) {
1941                                 pr_err("%s insert failed, step %d\n",
1942                                        mode->name, n);
1943                                 kfree(node);
1944                                 goto out;
1945                         }
1946                 }
1947
1948                 drm_mm_for_each_node_safe(node, nn, &mm) {
1949                         u64 rem;
1950
1951                         if (node->color != node->size) {
1952                                 pr_err("%s invalid color stored: expected %lld, found %ld\n",
1953                                        mode->name, node->size, node->color);
1954
1955                                 goto out;
1956                         }
1957
1958                         if (colors_abutt(node))
1959                                 goto out;
1960
1961                         div64_u64_rem(node->start, node->size, &rem);
1962                         if (rem) {
1963                                 pr_err("%s colored node misaligned, start=%llx expected alignment=%lld [rem=%lld]\n",
1964                                        mode->name, node->start, node->size, rem);
1965                                 goto out;
1966                         }
1967
1968                         drm_mm_remove_node(node);
1969                         kfree(node);
1970                 }
1971         }
1972
1973         ret = 0;
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         return ret;
1981 }
1982
1983 static int evict_color(struct drm_mm *mm,
1984                        u64 range_start, u64 range_end,
1985                        struct evict_node *nodes,
1986                        unsigned int *order,
1987                        unsigned int count,
1988                        unsigned int size,
1989                        unsigned int alignment,
1990                        unsigned long color,
1991                        const struct insert_mode *mode)
1992 {
1993         struct drm_mm_scan scan;
1994         LIST_HEAD(evict_list);
1995         struct evict_node *e;
1996         struct drm_mm_node tmp;
1997         int err;
1998
1999         drm_mm_scan_init_with_range(&scan, mm,
2000                                     size, alignment, color,
2001                                     range_start, range_end,
2002                                     mode->mode);
2003         if (!evict_nodes(&scan,
2004                          nodes, order, count, true,
2005                          &evict_list))
2006                 return -EINVAL;
2007
2008         memset(&tmp, 0, sizeof(tmp));
2009         err = drm_mm_insert_node_generic(mm, &tmp, size, alignment, color,
2010                                          DRM_MM_INSERT_EVICT);
2011         if (err) {
2012                 pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n",
2013                        size, alignment, color, err);
2014                 show_scan(&scan);
2015                 show_holes(mm, 3);
2016                 return err;
2017         }
2018
2019         if (tmp.start < range_start || tmp.start + tmp.size > range_end) {
2020                 pr_err("Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
2021                        tmp.start, tmp.size, range_start, range_end);
2022                 err = -EINVAL;
2023         }
2024
2025         if (colors_abutt(&tmp))
2026                 err = -EINVAL;
2027
2028         if (!assert_node(&tmp, mm, size, alignment, color)) {
2029                 pr_err("Inserted did not fit the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx\n",
2030                        tmp.size, size,
2031                        alignment, misalignment(&tmp, alignment), tmp.start);
2032                 err = -EINVAL;
2033         }
2034
2035         drm_mm_remove_node(&tmp);
2036         if (err)
2037                 return err;
2038
2039         list_for_each_entry(e, &evict_list, link) {
2040                 err = drm_mm_reserve_node(mm, &e->node);
2041                 if (err) {
2042                         pr_err("Failed to reinsert node after eviction: start=%llx\n",
2043                                e->node.start);
2044                         return err;
2045                 }
2046         }
2047
2048         return 0;
2049 }
2050
2051 static int igt_color_evict(void *ignored)
2052 {
2053         DRM_RND_STATE(prng, random_seed);
2054         const unsigned int total_size = min(8192u, max_iterations);
2055         const struct insert_mode *mode;
2056         unsigned long color = 0;
2057         struct drm_mm mm;
2058         struct evict_node *nodes;
2059         struct drm_mm_node *node, *next;
2060         unsigned int *order, n;
2061         int ret, err;
2062
2063         /* Check that the drm_mm_scan also honours color adjustment when
2064          * choosing its victims to create a hole. Our color_adjust does not
2065          * allow two nodes to be placed together without an intervening hole
2066          * enlarging the set of victims that must be evicted.
2067          */
2068
2069         ret = -ENOMEM;
2070         nodes = vzalloc(total_size * sizeof(*nodes));
2071         if (!nodes)
2072                 goto err;
2073
2074         order = drm_random_order(total_size, &prng);
2075         if (!order)
2076                 goto err_nodes;
2077
2078         ret = -EINVAL;
2079         drm_mm_init(&mm, 0, 2*total_size - 1);
2080         mm.color_adjust = separate_adjacent_colors;
2081         for (n = 0; n < total_size; n++) {
2082                 if (!expect_insert(&mm, &nodes[n].node,
2083                                    1, 0, color++,
2084                                    &insert_modes[0])) {
2085                         pr_err("insert failed, step %d\n", n);
2086                         goto out;
2087                 }
2088         }
2089
2090         for (mode = evict_modes; mode->name; mode++) {
2091                 for (n = 1; n <= total_size; n <<= 1) {
2092                         drm_random_reorder(order, total_size, &prng);
2093                         err = evict_color(&mm, 0, U64_MAX,
2094                                           nodes, order, total_size,
2095                                           n, 1, color++,
2096                                           mode);
2097                         if (err) {
2098                                 pr_err("%s evict_color(size=%u) failed\n",
2099                                        mode->name, n);
2100                                 goto out;
2101                         }
2102                 }
2103
2104                 for (n = 1; n < total_size; n <<= 1) {
2105                         drm_random_reorder(order, total_size, &prng);
2106                         err = evict_color(&mm, 0, U64_MAX,
2107                                           nodes, order, total_size,
2108                                           total_size/2, n, color++,
2109                                           mode);
2110                         if (err) {
2111                                 pr_err("%s evict_color(size=%u, alignment=%u) failed\n",
2112                                        mode->name, total_size/2, n);
2113                                 goto out;
2114                         }
2115                 }
2116
2117                 for_each_prime_number_from(n, 1, min(total_size, max_prime)) {
2118                         unsigned int nsize = (total_size - n + 1) / 2;
2119
2120                         DRM_MM_BUG_ON(!nsize);
2121
2122                         drm_random_reorder(order, total_size, &prng);
2123                         err = evict_color(&mm, 0, U64_MAX,
2124                                           nodes, order, total_size,
2125                                           nsize, n, color++,
2126                                           mode);
2127                         if (err) {
2128                                 pr_err("%s evict_color(size=%u, alignment=%u) failed\n",
2129                                        mode->name, nsize, n);
2130                                 goto out;
2131                         }
2132                 }
2133         }
2134
2135         ret = 0;
2136 out:
2137         if (ret)
2138                 show_mm(&mm);
2139         drm_mm_for_each_node_safe(node, next, &mm)
2140                 drm_mm_remove_node(node);
2141         drm_mm_takedown(&mm);
2142         kfree(order);
2143 err_nodes:
2144         vfree(nodes);
2145 err:
2146         return ret;
2147 }
2148
2149 static int igt_color_evict_range(void *ignored)
2150 {
2151         DRM_RND_STATE(prng, random_seed);
2152         const unsigned int total_size = 8192;
2153         const unsigned int range_size = total_size / 2;
2154         const unsigned int range_start = total_size / 4;
2155         const unsigned int range_end = range_start + range_size;
2156         const struct insert_mode *mode;
2157         unsigned long color = 0;
2158         struct drm_mm mm;
2159         struct evict_node *nodes;
2160         struct drm_mm_node *node, *next;
2161         unsigned int *order, n;
2162         int ret, err;
2163
2164         /* Like igt_color_evict(), but limited to small portion of the full
2165          * drm_mm range.
2166          */
2167
2168         ret = -ENOMEM;
2169         nodes = vzalloc(total_size * sizeof(*nodes));
2170         if (!nodes)
2171                 goto err;
2172
2173         order = drm_random_order(total_size, &prng);
2174         if (!order)
2175                 goto err_nodes;
2176
2177         ret = -EINVAL;
2178         drm_mm_init(&mm, 0, 2*total_size - 1);
2179         mm.color_adjust = separate_adjacent_colors;
2180         for (n = 0; n < total_size; n++) {
2181                 if (!expect_insert(&mm, &nodes[n].node,
2182                                    1, 0, color++,
2183                                    &insert_modes[0])) {
2184                         pr_err("insert failed, step %d\n", n);
2185                         goto out;
2186                 }
2187         }
2188
2189         for (mode = evict_modes; mode->name; mode++) {
2190                 for (n = 1; n <= range_size; n <<= 1) {
2191                         drm_random_reorder(order, range_size, &prng);
2192                         err = evict_color(&mm, range_start, range_end,
2193                                           nodes, order, total_size,
2194                                           n, 1, color++,
2195                                           mode);
2196                         if (err) {
2197                                 pr_err("%s evict_color(size=%u) failed for range [%x, %x]\n",
2198                                        mode->name, n, range_start, range_end);
2199                                 goto out;
2200                         }
2201                 }
2202
2203                 for (n = 1; n < range_size; n <<= 1) {
2204                         drm_random_reorder(order, total_size, &prng);
2205                         err = evict_color(&mm, range_start, range_end,
2206                                           nodes, order, total_size,
2207                                           range_size/2, n, color++,
2208                                           mode);
2209                         if (err) {
2210                                 pr_err("%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
2211                                        mode->name, total_size/2, n, range_start, range_end);
2212                                 goto out;
2213                         }
2214                 }
2215
2216                 for_each_prime_number_from(n, 1, min(range_size, max_prime)) {
2217                         unsigned int nsize = (range_size - n + 1) / 2;
2218
2219                         DRM_MM_BUG_ON(!nsize);
2220
2221                         drm_random_reorder(order, total_size, &prng);
2222                         err = evict_color(&mm, range_start, range_end,
2223                                           nodes, order, total_size,
2224                                           nsize, n, color++,
2225                                           mode);
2226                         if (err) {
2227                                 pr_err("%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
2228                                        mode->name, nsize, n, range_start, range_end);
2229                                 goto out;
2230                         }
2231                 }
2232         }
2233
2234         ret = 0;
2235 out:
2236         if (ret)
2237                 show_mm(&mm);
2238         drm_mm_for_each_node_safe(node, next, &mm)
2239                 drm_mm_remove_node(node);
2240         drm_mm_takedown(&mm);
2241         kfree(order);
2242 err_nodes:
2243         vfree(nodes);
2244 err:
2245         return ret;
2246 }
2247
2248 #include "drm_selftest.c"
2249
2250 static int __init test_drm_mm_init(void)
2251 {
2252         int err;
2253
2254         while (!random_seed)
2255                 random_seed = get_random_int();
2256
2257         pr_info("Testing DRM range manger (struct drm_mm), with random_seed=0x%x max_iterations=%u max_prime=%u\n",
2258                 random_seed, max_iterations, max_prime);
2259         err = run_selftests(selftests, ARRAY_SIZE(selftests), NULL);
2260
2261         return err > 0 ? 0 : err;
2262 }
2263
2264 static void __exit test_drm_mm_exit(void)
2265 {
2266 }
2267
2268 module_init(test_drm_mm_init);
2269 module_exit(test_drm_mm_exit);
2270
2271 module_param(random_seed, uint, 0400);
2272 module_param(max_iterations, uint, 0400);
2273 module_param(max_prime, uint, 0400);
2274
2275 MODULE_AUTHOR("Intel Corporation");
2276 MODULE_LICENSE("GPL");