drivers/gpu/drm/tests/drm_buddy_test.c

   1 // SPDX-License-Identifier: MIT
   2 /*
   3  * Copyright © 2019 Intel Corporation
   4  * Copyright © 2022 Maíra Canal <[email protected]>
   5  */
   6
   7 #include <kunit/test.h>
   8
   9 #include <linux/prime_numbers.h>
  10 #include <linux/sched/signal.h>
  11
  12 #include <drm/drm_buddy.h>
  13
  14 #include "../lib/drm_random.h"
  15
  16 #define TIMEOUT(name__)                                                         \
  17         unsigned long name__ = jiffies + MAX_SCHEDULE_TIMEOUT
  18
  19 static unsigned int random_seed;
  20
  21 static inline u64 get_size(int order, u64 chunk_size)
  22 {
  23         return (1 << order) * chunk_size;
  24 }
  25
  26 __printf(2, 3)
  27 static bool __timeout(unsigned long timeout, const char *fmt, ...)
  28 {
  29         va_list va;
  30
  31         if (!signal_pending(current)) {
  32                 cond_resched();
  33                 if (time_before(jiffies, timeout))
  34                         return false;
  35         }
  36
  37         if (fmt) {
  38                 va_start(va, fmt);
  39                 vprintk(fmt, va);
  40                 va_end(va);
  41         }
  42
  43         return true;
  44 }
  45
  46 static void __dump_block(struct kunit *test, struct drm_buddy *mm,
  47                          struct drm_buddy_block *block, bool buddy)
  48 {
  49         kunit_err(test, "block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%d buddy=%d\n",
  50                   block->header, drm_buddy_block_state(block),
  51                           drm_buddy_block_order(block), drm_buddy_block_offset(block),
  52                           drm_buddy_block_size(mm, block), !block->parent, buddy);
  53 }
  54
  55 static void dump_block(struct kunit *test, struct drm_buddy *mm,
  56                        struct drm_buddy_block *block)
  57 {
  58         struct drm_buddy_block *buddy;
  59
  60         __dump_block(test, mm, block, false);
  61
  62         buddy = drm_get_buddy(block);
  63         if (buddy)
  64                 __dump_block(test, mm, buddy, true);
  65 }
  66
  67 static int check_block(struct kunit *test, struct drm_buddy *mm,
  68                        struct drm_buddy_block *block)
  69 {
  70         struct drm_buddy_block *buddy;
  71         unsigned int block_state;
  72         u64 block_size;
  73         u64 offset;
  74         int err = 0;
  75
  76         block_state = drm_buddy_block_state(block);
  77
  78         if (block_state != DRM_BUDDY_ALLOCATED &&
  79             block_state != DRM_BUDDY_FREE && block_state != DRM_BUDDY_SPLIT) {
  80                 kunit_err(test, "block state mismatch\n");
  81                 err = -EINVAL;
  82         }
  83
  84         block_size = drm_buddy_block_size(mm, block);
  85         offset = drm_buddy_block_offset(block);
  86
  87         if (block_size < mm->chunk_size) {
  88                 kunit_err(test, "block size smaller than min size\n");
  89                 err = -EINVAL;
  90         }
  91
  92         /* We can't use is_power_of_2() for a u64 on 32-bit systems. */
  93         if (block_size & (block_size - 1)) {
  94                 kunit_err(test, "block size not power of two\n");
  95                 err = -EINVAL;
  96         }
  97
  98         if (!IS_ALIGNED(block_size, mm->chunk_size)) {
  99                 kunit_err(test, "block size not aligned to min size\n");
 100                 err = -EINVAL;
 101         }
 102
 103         if (!IS_ALIGNED(offset, mm->chunk_size)) {
 104                 kunit_err(test, "block offset not aligned to min size\n");
 105                 err = -EINVAL;
 106         }
 107
 108         if (!IS_ALIGNED(offset, block_size)) {
 109                 kunit_err(test, "block offset not aligned to block size\n");
 110                 err = -EINVAL;
 111         }
 112
 113         buddy = drm_get_buddy(block);
 114
 115         if (!buddy && block->parent) {
 116                 kunit_err(test, "buddy has gone fishing\n");
 117                 err = -EINVAL;
 118         }
 119
 120         if (buddy) {
 121                 if (drm_buddy_block_offset(buddy) != (offset ^ block_size)) {
 122                         kunit_err(test, "buddy has wrong offset\n");
 123                         err = -EINVAL;
 124                 }
 125
 126                 if (drm_buddy_block_size(mm, buddy) != block_size) {
 127                         kunit_err(test, "buddy size mismatch\n");
 128                         err = -EINVAL;
 129                 }
 130
 131                 if (drm_buddy_block_state(buddy) == block_state &&
 132                     block_state == DRM_BUDDY_FREE) {
 133                         kunit_err(test, "block and its buddy are free\n");
 134                         err = -EINVAL;
 135                 }
 136         }
 137
 138         return err;
 139 }
 140
 141 static int check_blocks(struct kunit *test, struct drm_buddy *mm,
 142                         struct list_head *blocks, u64 expected_size, bool is_contiguous)
 143 {
 144         struct drm_buddy_block *block;
 145         struct drm_buddy_block *prev;
 146         u64 total;
 147         int err = 0;
 148
 149         block = NULL;
 150         prev = NULL;
 151         total = 0;
 152
 153         list_for_each_entry(block, blocks, link) {
 154                 err = check_block(test, mm, block);
 155
 156                 if (!drm_buddy_block_is_allocated(block)) {
 157                         kunit_err(test, "block not allocated\n");
 158                         err = -EINVAL;
 159                 }
 160
 161                 if (is_contiguous && prev) {
 162                         u64 prev_block_size;
 163                         u64 prev_offset;
 164                         u64 offset;
 165
 166                         prev_offset = drm_buddy_block_offset(prev);
 167                         prev_block_size = drm_buddy_block_size(mm, prev);
 168                         offset = drm_buddy_block_offset(block);
 169
 170                         if (offset != (prev_offset + prev_block_size)) {
 171                                 kunit_err(test, "block offset mismatch\n");
 172                                 err = -EINVAL;
 173                         }
 174                 }
 175
 176                 if (err)
 177                         break;
 178
 179                 total += drm_buddy_block_size(mm, block);
 180                 prev = block;
 181         }
 182
 183         if (!err) {
 184                 if (total != expected_size) {
 185                         kunit_err(test, "size mismatch, expected=%llx, found=%llx\n",
 186                                   expected_size, total);
 187                         err = -EINVAL;
 188                 }
 189                 return err;
 190         }
 191
 192         if (prev) {
 193                 kunit_err(test, "prev block, dump:\n");
 194                 dump_block(test, mm, prev);
 195         }
 196
 197         kunit_err(test, "bad block, dump:\n");
 198         dump_block(test, mm, block);
 199
 200         return err;
 201 }
 202
 203 static int check_mm(struct kunit *test, struct drm_buddy *mm)
 204 {
 205         struct drm_buddy_block *root;
 206         struct drm_buddy_block *prev;
 207         unsigned int i;
 208         u64 total;
 209         int err = 0;
 210
 211         if (!mm->n_roots) {
 212                 kunit_err(test, "n_roots is zero\n");
 213                 return -EINVAL;
 214         }
 215
 216         if (mm->n_roots != hweight64(mm->size)) {
 217                 kunit_err(test, "n_roots mismatch, n_roots=%u, expected=%lu\n",
 218                           mm->n_roots, hweight64(mm->size));
 219                 return -EINVAL;
 220         }
 221
 222         root = NULL;
 223         prev = NULL;
 224         total = 0;
 225
 226         for (i = 0; i < mm->n_roots; ++i) {
 227                 struct drm_buddy_block *block;
 228                 unsigned int order;
 229
 230                 root = mm->roots[i];
 231                 if (!root) {
 232                         kunit_err(test, "root(%u) is NULL\n", i);
 233                         err = -EINVAL;
 234                         break;
 235                 }
 236
 237                 err = check_block(test, mm, root);
 238
 239                 if (!drm_buddy_block_is_free(root)) {
 240                         kunit_err(test, "root not free\n");
 241                         err = -EINVAL;
 242                 }
 243
 244                 order = drm_buddy_block_order(root);
 245
 246                 if (!i) {
 247                         if (order != mm->max_order) {
 248                                 kunit_err(test, "max order root missing\n");
 249                                 err = -EINVAL;
 250                         }
 251                 }
 252
 253                 if (prev) {
 254                         u64 prev_block_size;
 255                         u64 prev_offset;
 256                         u64 offset;
 257
 258                         prev_offset = drm_buddy_block_offset(prev);
 259                         prev_block_size = drm_buddy_block_size(mm, prev);
 260                         offset = drm_buddy_block_offset(root);
 261
 262                         if (offset != (prev_offset + prev_block_size)) {
 263                                 kunit_err(test, "root offset mismatch\n");
 264                                 err = -EINVAL;
 265                         }
 266                 }
 267
 268                 block = list_first_entry_or_null(&mm->free_list[order],
 269                                                  struct drm_buddy_block, link);
 270                 if (block != root) {
 271                         kunit_err(test, "root mismatch at order=%u\n", order);
 272                         err = -EINVAL;
 273                 }
 274
 275                 if (err)
 276                         break;
 277
 278                 prev = root;
 279                 total += drm_buddy_block_size(mm, root);
 280         }
 281
 282         if (!err) {
 283                 if (total != mm->size) {
 284                         kunit_err(test, "expected mm size=%llx, found=%llx\n",
 285                                   mm->size, total);
 286                         err = -EINVAL;
 287                 }
 288                 return err;
 289         }
 290
 291         if (prev) {
 292                 kunit_err(test, "prev root(%u), dump:\n", i - 1);
 293                 dump_block(test, mm, prev);
 294         }
 295
 296         if (root) {
 297                 kunit_err(test, "bad root(%u), dump:\n", i);
 298                 dump_block(test, mm, root);
 299         }
 300
 301         return err;
 302 }
 303
 304 static void mm_config(u64 *size, u64 *chunk_size)
 305 {
 306         DRM_RND_STATE(prng, random_seed);
 307         u32 s, ms;
 308
 309         /* Nothing fancy, just try to get an interesting bit pattern */
 310
 311         prandom_seed_state(&prng, random_seed);
 312
 313         /* Let size be a random number of pages up to 8 GB (2M pages) */
 314         s = 1 + drm_prandom_u32_max_state((BIT(33 - 12)) - 1, &prng);
 315         /* Let the chunk size be a random power of 2 less than size */
 316         ms = BIT(drm_prandom_u32_max_state(ilog2(s), &prng));
 317         /* Round size down to the chunk size */
 318         s &= -ms;
 319
 320         /* Convert from pages to bytes */
 321         *chunk_size = (u64)ms << 12;
 322         *size = (u64)s << 12;
 323 }
 324
 325 static void drm_test_buddy_alloc_pathological(struct kunit *test)
 326 {
 327         u64 mm_size, size, start = 0;
 328         struct drm_buddy_block *block;
 329         const int max_order = 3;
 330         unsigned long flags = 0;
 331         int order, top;
 332         struct drm_buddy mm;
 333         LIST_HEAD(blocks);
 334         LIST_HEAD(holes);
 335         LIST_HEAD(tmp);
 336
 337         /*
 338          * Create a pot-sized mm, then allocate one of each possible
 339          * order within. This should leave the mm with exactly one
 340          * page left. Free the largest block, then whittle down again.
 341          * Eventually we will have a fully 50% fragmented mm.
 342          */
 343
 344         mm_size = PAGE_SIZE << max_order;
 345         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE),
 346                                "buddy_init failed\n");
 347
 348         KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
 349
 350         for (top = max_order; top; top--) {
 351                 /* Make room by freeing the largest allocated block */
 352                 block = list_first_entry_or_null(&blocks, typeof(*block), link);
 353                 if (block) {
 354                         list_del(&block->link);
 355                         drm_buddy_free_block(&mm, block);
 356                 }
 357
 358                 for (order = top; order--;) {
 359                         size = get_size(order, PAGE_SIZE);
 360                         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start,
 361                                                                             mm_size, size, size,
 362                                                                                 &tmp, flags),
 363                                         "buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
 364                                         order, top);
 365
 366                         block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 367                         KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 368
 369                         list_move_tail(&block->link, &blocks);
 370                 }
 371
 372                 /* There should be one final page for this sub-allocation */
 373                 size = get_size(0, PAGE_SIZE);
 374                 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 375                                                                     size, size, &tmp, flags),
 376                                                            "buddy_alloc hit -ENOMEM for hole\n");
 377
 378                 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 379                 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 380
 381                 list_move_tail(&block->link, &holes);
 382
 383                 size = get_size(top, PAGE_SIZE);
 384                 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 385                                                                    size, size, &tmp, flags),
 386                                                           "buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",
 387                                                           top, max_order);
 388         }
 389
 390         drm_buddy_free_list(&mm, &holes);
 391
 392         /* Nothing larger than blocks of chunk_size now available */
 393         for (order = 1; order <= max_order; order++) {
 394                 size = get_size(order, PAGE_SIZE);
 395                 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 396                                                                    size, size, &tmp, flags),
 397                                                           "buddy_alloc unexpectedly succeeded at order %d, it should be full!",
 398                                                           order);
 399         }
 400
 401         list_splice_tail(&holes, &blocks);
 402         drm_buddy_free_list(&mm, &blocks);
 403         drm_buddy_fini(&mm);
 404 }
 405
 406 static void drm_test_buddy_alloc_smoke(struct kunit *test)
 407 {
 408         u64 mm_size, chunk_size, start = 0;
 409         unsigned long flags = 0;
 410         struct drm_buddy mm;
 411         int *order;
 412         int i;
 413
 414         DRM_RND_STATE(prng, random_seed);
 415         TIMEOUT(end_time);
 416
 417         mm_config(&mm_size, &chunk_size);
 418
 419         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, chunk_size),
 420                                "buddy_init failed\n");
 421
 422         order = drm_random_order(mm.max_order + 1, &prng);
 423         KUNIT_ASSERT_TRUE(test, order);
 424
 425         for (i = 0; i <= mm.max_order; ++i) {
 426                 struct drm_buddy_block *block;
 427                 int max_order = order[i];
 428                 bool timeout = false;
 429                 LIST_HEAD(blocks);
 430                 u64 total, size;
 431                 LIST_HEAD(tmp);
 432                 int order, err;
 433
 434                 KUNIT_ASSERT_FALSE_MSG(test, check_mm(test, &mm),
 435                                        "pre-mm check failed, abort\n");
 436
 437                 order = max_order;
 438                 total = 0;
 439
 440                 do {
 441 retry:
 442                         size = get_size(order, chunk_size);
 443                         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, size, &tmp, flags);
 444                         if (err) {
 445                                 if (err == -ENOMEM) {
 446                                         KUNIT_FAIL(test, "buddy_alloc hit -ENOMEM with order=%d\n",
 447                                                    order);
 448                                 } else {
 449                                         if (order--) {
 450                                                 err = 0;
 451                                                 goto retry;
 452                                         }
 453
 454                                         KUNIT_FAIL(test, "buddy_alloc with order=%d failed\n",
 455                                                    order);
 456                                 }
 457
 458                                 break;
 459                         }
 460
 461                         block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 462                         KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 463
 464                         list_move_tail(&block->link, &blocks);
 465                         KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_order(block), order,
 466                                             "buddy_alloc order mismatch\n");
 467
 468                         total += drm_buddy_block_size(&mm, block);
 469
 470                         if (__timeout(end_time, NULL)) {
 471                                 timeout = true;
 472                                 break;
 473                         }
 474                 } while (total < mm.size);
 475
 476                 if (!err)
 477                         err = check_blocks(test, &mm, &blocks, total, false);
 478
 479                 drm_buddy_free_list(&mm, &blocks);
 480
 481                 if (!err) {
 482                         KUNIT_EXPECT_FALSE_MSG(test, check_mm(test, &mm),
 483                                                "post-mm check failed\n");
 484                 }
 485
 486                 if (err || timeout)
 487                         break;
 488
 489                 cond_resched();
 490         }
 491
 492         kfree(order);
 493         drm_buddy_fini(&mm);
 494 }
 495
 496 static void drm_test_buddy_alloc_pessimistic(struct kunit *test)
 497 {
 498         u64 mm_size, size, start = 0;
 499         struct drm_buddy_block *block, *bn;
 500         const unsigned int max_order = 16;
 501         unsigned long flags = 0;
 502         struct drm_buddy mm;
 503         unsigned int order;
 504         LIST_HEAD(blocks);
 505         LIST_HEAD(tmp);
 506
 507         /*
 508          * Create a pot-sized mm, then allocate one of each possible
 509          * order within. This should leave the mm with exactly one
 510          * page left.
 511          */
 512
 513         mm_size = PAGE_SIZE << max_order;
 514         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE),
 515                                "buddy_init failed\n");
 516
 517         KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
 518
 519         for (order = 0; order < max_order; order++) {
 520                 size = get_size(order, PAGE_SIZE);
 521                 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 522                                                                     size, size, &tmp, flags),
 523                                                            "buddy_alloc hit -ENOMEM with order=%d\n",
 524                                                            order);
 525
 526                 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 527                 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 528
 529                 list_move_tail(&block->link, &blocks);
 530         }
 531
 532         /* And now the last remaining block available */
 533         size = get_size(0, PAGE_SIZE);
 534         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 535                                                             size, size, &tmp, flags),
 536                                                    "buddy_alloc hit -ENOMEM on final alloc\n");
 537
 538         block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 539         KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 540
 541         list_move_tail(&block->link, &blocks);
 542
 543         /* Should be completely full! */
 544         for (order = max_order; order--;) {
 545                 size = get_size(order, PAGE_SIZE);
 546                 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 547                                                                    size, size, &tmp, flags),
 548                                                           "buddy_alloc unexpectedly succeeded, it should be full!");
 549         }
 550
 551         block = list_last_entry(&blocks, typeof(*block), link);
 552         list_del(&block->link);
 553         drm_buddy_free_block(&mm, block);
 554
 555         /* As we free in increasing size, we make available larger blocks */
 556         order = 1;
 557         list_for_each_entry_safe(block, bn, &blocks, link) {
 558                 list_del(&block->link);
 559                 drm_buddy_free_block(&mm, block);
 560
 561                 size = get_size(order, PAGE_SIZE);
 562                 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 563                                                                     size, size, &tmp, flags),
 564                                                            "buddy_alloc hit -ENOMEM with order=%d\n",
 565                                                            order);
 566
 567                 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 568                 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 569
 570                 list_del(&block->link);
 571                 drm_buddy_free_block(&mm, block);
 572                 order++;
 573         }
 574
 575         /* To confirm, now the whole mm should be available */
 576         size = get_size(max_order, PAGE_SIZE);
 577         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 578                                                             size, size, &tmp, flags),
 579                                                    "buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
 580                                                    max_order);
 581
 582         block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 583         KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 584
 585         list_del(&block->link);
 586         drm_buddy_free_block(&mm, block);
 587         drm_buddy_free_list(&mm, &blocks);
 588         drm_buddy_fini(&mm);
 589 }
 590
 591 static void drm_test_buddy_alloc_optimistic(struct kunit *test)
 592 {
 593         u64 mm_size, size, start = 0;
 594         struct drm_buddy_block *block;
 595         unsigned long flags = 0;
 596         const int max_order = 16;
 597         struct drm_buddy mm;
 598         LIST_HEAD(blocks);
 599         LIST_HEAD(tmp);
 600         int order;
 601
 602         /*
 603          * Create a mm with one block of each order available, and
 604          * try to allocate them all.
 605          */
 606
 607         mm_size = PAGE_SIZE * ((1 << (max_order + 1)) - 1);
 608
 609         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE),
 610                                "buddy_init failed\n");
 611
 612         KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
 613
 614         for (order = 0; order <= max_order; order++) {
 615                 size = get_size(order, PAGE_SIZE);
 616                 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 617                                                                     size, size, &tmp, flags),
 618                                                            "buddy_alloc hit -ENOMEM with order=%d\n",
 619                                                            order);
 620
 621                 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 622                 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
 623
 624                 list_move_tail(&block->link, &blocks);
 625         }
 626
 627         /* Should be completely full! */
 628         size = get_size(0, PAGE_SIZE);
 629         KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
 630                                                            size, size, &tmp, flags),
 631                                                   "buddy_alloc unexpectedly succeeded, it should be full!");
 632
 633         drm_buddy_free_list(&mm, &blocks);
 634         drm_buddy_fini(&mm);
 635 }
 636
 637 static void drm_test_buddy_alloc_range(struct kunit *test)
 638 {
 639         unsigned long flags = DRM_BUDDY_RANGE_ALLOCATION;
 640         u64 offset, size, rem, chunk_size, end;
 641         unsigned long page_num;
 642         struct drm_buddy mm;
 643         LIST_HEAD(blocks);
 644
 645         mm_config(&size, &chunk_size);
 646
 647         KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, size, chunk_size),
 648                                "buddy_init failed");
 649
 650         KUNIT_ASSERT_FALSE_MSG(test, check_mm(test, &mm),
 651                                "pre-mm check failed, abort!");
 652
 653         rem = mm.size;
 654         offset = 0;
 655
 656         for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
 657                 struct drm_buddy_block *block;
 658                 LIST_HEAD(tmp);
 659
 660                 size = min(page_num * mm.chunk_size, rem);
 661                 end = offset + size;
 662
 663                 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, offset, end,
 664                                                                     size, mm.chunk_size,
 665                                                                         &tmp, flags),
 666                                 "alloc_range with offset=%llx, size=%llx failed\n", offset, size);
 667
 668                 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
 669                 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_range has no blocks\n");
 670
 671                 KUNIT_ASSERT_EQ_MSG(test, drm_buddy_block_offset(block), offset,
 672                                     "alloc_range start offset mismatch, found=%llx, expected=%llx\n",
 673                                                         drm_buddy_block_offset(block), offset);
 674
 675                 KUNIT_ASSERT_FALSE(test, check_blocks(test, &mm, &tmp, size, true));
 676
 677                 list_splice_tail(&tmp, &blocks);
 678
 679                 offset += size;
 680
 681                 rem -= size;
 682                 if (!rem)
 683                         break;
 684
 685                 cond_resched();
 686         }
 687
 688         drm_buddy_free_list(&mm, &blocks);
 689
 690         KUNIT_EXPECT_FALSE_MSG(test, check_mm(test, &mm), "post-mm check failed\n");
 691
 692         drm_buddy_fini(&mm);
 693 }
 694
 695 static void drm_test_buddy_alloc_limit(struct kunit *test)
 696 {
 697         u64 size = U64_MAX, start = 0;
 698         struct drm_buddy_block *block;
 699         unsigned long flags = 0;
 700         LIST_HEAD(allocated);
 701         struct drm_buddy mm;
 702
 703         KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, size, PAGE_SIZE));
 704
 705         KUNIT_EXPECT_EQ_MSG(test, mm.max_order, DRM_BUDDY_MAX_ORDER,
 706                             "mm.max_order(%d) != %d\n", mm.max_order,
 707                                                 DRM_BUDDY_MAX_ORDER);
 708
 709         size = mm.chunk_size << mm.max_order;
 710         KUNIT_EXPECT_FALSE(test, drm_buddy_alloc_blocks(&mm, start, size, size,
 711                                                         PAGE_SIZE, &allocated, flags));
 712
 713         block = list_first_entry_or_null(&allocated, struct drm_buddy_block, link);
 714         KUNIT_EXPECT_TRUE(test, block);
 715
 716         KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_order(block), mm.max_order,
 717                             "block order(%d) != %d\n",
 718                                                 drm_buddy_block_order(block), mm.max_order);
 719
 720         KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_size(&mm, block),
 721                             BIT_ULL(mm.max_order) * PAGE_SIZE,
 722                                                 "block size(%llu) != %llu\n",
 723                                                 drm_buddy_block_size(&mm, block),
 724                                                 BIT_ULL(mm.max_order) * PAGE_SIZE);
 725
 726         drm_buddy_free_list(&mm, &allocated);
 727         drm_buddy_fini(&mm);
 728 }
 729
 730 static int drm_buddy_suite_init(struct kunit_suite *suite)
 731 {
 732         while (!random_seed)
 733                 random_seed = get_random_u32();
 734
 735         kunit_info(suite, "Testing DRM buddy manager, with random_seed=0x%x\n", random_seed);
 736
 737         return 0;
 738 }
 739
 740 static struct kunit_case drm_buddy_tests[] = {
 741         KUNIT_CASE(drm_test_buddy_alloc_limit),
 742         KUNIT_CASE(drm_test_buddy_alloc_range),
 743         KUNIT_CASE(drm_test_buddy_alloc_optimistic),
 744         KUNIT_CASE(drm_test_buddy_alloc_pessimistic),
 745         KUNIT_CASE(drm_test_buddy_alloc_smoke),
 746         KUNIT_CASE(drm_test_buddy_alloc_pathological),
 747         {}
 748 };
 749
 750 static struct kunit_suite drm_buddy_test_suite = {
 751         .name = "drm_buddy",
 752         .suite_init = drm_buddy_suite_init,
 753         .test_cases = drm_buddy_tests,
 754 };
 755
 756 kunit_test_suite(drm_buddy_test_suite);
 757
 758 MODULE_AUTHOR("Intel Corporation");
 759 MODULE_LICENSE("GPL");