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

   1 // SPDX-License-Identifier: MIT
   2 /*
   3  * Copyright © 2019 Intel Corporation
   4  */
   5
   6 #define pr_fmt(fmt) "drm_buddy: " fmt
   7
   8 #include <linux/module.h>
   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 TESTS "drm_buddy_selftests.h"
  17 #include "drm_selftest.h"
  18
  19 #define IGT_TIMEOUT(name__) \
  20         unsigned long name__ = jiffies + MAX_SCHEDULE_TIMEOUT
  21
  22 static unsigned int random_seed;
  23
  24 static inline u64 get_size(int order, u64 chunk_size)
  25 {
  26         return (1 << order) * chunk_size;
  27 }
  28
  29 __printf(2, 3)
  30 static bool __igt_timeout(unsigned long timeout, const char *fmt, ...)
  31 {
  32         va_list va;
  33
  34         if (!signal_pending(current)) {
  35                 cond_resched();
  36                 if (time_before(jiffies, timeout))
  37                         return false;
  38         }
  39
  40         if (fmt) {
  41                 va_start(va, fmt);
  42                 vprintk(fmt, va);
  43                 va_end(va);
  44         }
  45
  46         return true;
  47 }
  48
  49 static inline const char *yesno(bool v)
  50 {
  51         return v ? "yes" : "no";
  52 }
  53
  54 static void __igt_dump_block(struct drm_buddy *mm,
  55                              struct drm_buddy_block *block,
  56                              bool buddy)
  57 {
  58         pr_err("block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%s buddy=%s\n",
  59                block->header,
  60                drm_buddy_block_state(block),
  61                drm_buddy_block_order(block),
  62                drm_buddy_block_offset(block),
  63                drm_buddy_block_size(mm, block),
  64                yesno(!block->parent),
  65                yesno(buddy));
  66 }
  67
  68 static void igt_dump_block(struct drm_buddy *mm,
  69                            struct drm_buddy_block *block)
  70 {
  71         struct drm_buddy_block *buddy;
  72
  73         __igt_dump_block(mm, block, false);
  74
  75         buddy = drm_get_buddy(block);
  76         if (buddy)
  77                 __igt_dump_block(mm, buddy, true);
  78 }
  79
  80 static int igt_check_block(struct drm_buddy *mm,
  81                            struct drm_buddy_block *block)
  82 {
  83         struct drm_buddy_block *buddy;
  84         unsigned int block_state;
  85         u64 block_size;
  86         u64 offset;
  87         int err = 0;
  88
  89         block_state = drm_buddy_block_state(block);
  90
  91         if (block_state != DRM_BUDDY_ALLOCATED &&
  92             block_state != DRM_BUDDY_FREE &&
  93             block_state != DRM_BUDDY_SPLIT) {
  94                 pr_err("block state mismatch\n");
  95                 err = -EINVAL;
  96         }
  97
  98         block_size = drm_buddy_block_size(mm, block);
  99         offset = drm_buddy_block_offset(block);
 100
 101         if (block_size < mm->chunk_size) {
 102                 pr_err("block size smaller than min size\n");
 103                 err = -EINVAL;
 104         }
 105
 106         if (!is_power_of_2(block_size)) {
 107                 pr_err("block size not power of two\n");
 108                 err = -EINVAL;
 109         }
 110
 111         if (!IS_ALIGNED(block_size, mm->chunk_size)) {
 112                 pr_err("block size not aligned to min size\n");
 113                 err = -EINVAL;
 114         }
 115
 116         if (!IS_ALIGNED(offset, mm->chunk_size)) {
 117                 pr_err("block offset not aligned to min size\n");
 118                 err = -EINVAL;
 119         }
 120
 121         if (!IS_ALIGNED(offset, block_size)) {
 122                 pr_err("block offset not aligned to block size\n");
 123                 err = -EINVAL;
 124         }
 125
 126         buddy = drm_get_buddy(block);
 127
 128         if (!buddy && block->parent) {
 129                 pr_err("buddy has gone fishing\n");
 130                 err = -EINVAL;
 131         }
 132
 133         if (buddy) {
 134                 if (drm_buddy_block_offset(buddy) != (offset ^ block_size)) {
 135                         pr_err("buddy has wrong offset\n");
 136                         err = -EINVAL;
 137                 }
 138
 139                 if (drm_buddy_block_size(mm, buddy) != block_size) {
 140                         pr_err("buddy size mismatch\n");
 141                         err = -EINVAL;
 142                 }
 143
 144                 if (drm_buddy_block_state(buddy) == block_state &&
 145                     block_state == DRM_BUDDY_FREE) {
 146                         pr_err("block and its buddy are free\n");
 147                         err = -EINVAL;
 148                 }
 149         }
 150
 151         return err;
 152 }
 153
 154 static int igt_check_blocks(struct drm_buddy *mm,
 155                             struct list_head *blocks,
 156                             u64 expected_size,
 157                             bool is_contiguous)
 158 {
 159         struct drm_buddy_block *block;
 160         struct drm_buddy_block *prev;
 161         u64 total;
 162         int err = 0;
 163
 164         block = NULL;
 165         prev = NULL;
 166         total = 0;
 167
 168         list_for_each_entry(block, blocks, link) {
 169                 err = igt_check_block(mm, block);
 170
 171                 if (!drm_buddy_block_is_allocated(block)) {
 172                         pr_err("block not allocated\n"),
 173                                err = -EINVAL;
 174                 }
 175
 176                 if (is_contiguous && prev) {
 177                         u64 prev_block_size;
 178                         u64 prev_offset;
 179                         u64 offset;
 180
 181                         prev_offset = drm_buddy_block_offset(prev);
 182                         prev_block_size = drm_buddy_block_size(mm, prev);
 183                         offset = drm_buddy_block_offset(block);
 184
 185                         if (offset != (prev_offset + prev_block_size)) {
 186                                 pr_err("block offset mismatch\n");
 187                                 err = -EINVAL;
 188                         }
 189                 }
 190
 191                 if (err)
 192                         break;
 193
 194                 total += drm_buddy_block_size(mm, block);
 195                 prev = block;
 196         }
 197
 198         if (!err) {
 199                 if (total != expected_size) {
 200                         pr_err("size mismatch, expected=%llx, found=%llx\n",
 201                                expected_size, total);
 202                         err = -EINVAL;
 203                 }
 204                 return err;
 205         }
 206
 207         if (prev) {
 208                 pr_err("prev block, dump:\n");
 209                 igt_dump_block(mm, prev);
 210         }
 211
 212         pr_err("bad block, dump:\n");
 213         igt_dump_block(mm, block);
 214
 215         return err;
 216 }
 217
 218 static int igt_check_mm(struct drm_buddy *mm)
 219 {
 220         struct drm_buddy_block *root;
 221         struct drm_buddy_block *prev;
 222         unsigned int i;
 223         u64 total;
 224         int err = 0;
 225
 226         if (!mm->n_roots) {
 227                 pr_err("n_roots is zero\n");
 228                 return -EINVAL;
 229         }
 230
 231         if (mm->n_roots != hweight64(mm->size)) {
 232                 pr_err("n_roots mismatch, n_roots=%u, expected=%lu\n",
 233                        mm->n_roots, hweight64(mm->size));
 234                 return -EINVAL;
 235         }
 236
 237         root = NULL;
 238         prev = NULL;
 239         total = 0;
 240
 241         for (i = 0; i < mm->n_roots; ++i) {
 242                 struct drm_buddy_block *block;
 243                 unsigned int order;
 244
 245                 root = mm->roots[i];
 246                 if (!root) {
 247                         pr_err("root(%u) is NULL\n", i);
 248                         err = -EINVAL;
 249                         break;
 250                 }
 251
 252                 err = igt_check_block(mm, root);
 253
 254                 if (!drm_buddy_block_is_free(root)) {
 255                         pr_err("root not free\n");
 256                         err = -EINVAL;
 257                 }
 258
 259                 order = drm_buddy_block_order(root);
 260
 261                 if (!i) {
 262                         if (order != mm->max_order) {
 263                                 pr_err("max order root missing\n");
 264                                 err = -EINVAL;
 265                         }
 266                 }
 267
 268                 if (prev) {
 269                         u64 prev_block_size;
 270                         u64 prev_offset;
 271                         u64 offset;
 272
 273                         prev_offset = drm_buddy_block_offset(prev);
 274                         prev_block_size = drm_buddy_block_size(mm, prev);
 275                         offset = drm_buddy_block_offset(root);
 276
 277                         if (offset != (prev_offset + prev_block_size)) {
 278                                 pr_err("root offset mismatch\n");
 279                                 err = -EINVAL;
 280                         }
 281                 }
 282
 283                 block = list_first_entry_or_null(&mm->free_list[order],
 284                                                  struct drm_buddy_block,
 285                                                  link);
 286                 if (block != root) {
 287                         pr_err("root mismatch at order=%u\n", order);
 288                         err = -EINVAL;
 289                 }
 290
 291                 if (err)
 292                         break;
 293
 294                 prev = root;
 295                 total += drm_buddy_block_size(mm, root);
 296         }
 297
 298         if (!err) {
 299                 if (total != mm->size) {
 300                         pr_err("expected mm size=%llx, found=%llx\n", mm->size,
 301                                total);
 302                         err = -EINVAL;
 303                 }
 304                 return err;
 305         }
 306
 307         if (prev) {
 308                 pr_err("prev root(%u), dump:\n", i - 1);
 309                 igt_dump_block(mm, prev);
 310         }
 311
 312         if (root) {
 313                 pr_err("bad root(%u), dump:\n", i);
 314                 igt_dump_block(mm, root);
 315         }
 316
 317         return err;
 318 }
 319
 320 static void igt_mm_config(u64 *size, u64 *chunk_size)
 321 {
 322         DRM_RND_STATE(prng, random_seed);
 323         u32 s, ms;
 324
 325         /* Nothing fancy, just try to get an interesting bit pattern */
 326
 327         prandom_seed_state(&prng, random_seed);
 328
 329         /* Let size be a random number of pages up to 8 GB (2M pages) */
 330         s = 1 + drm_prandom_u32_max_state((BIT(33 - 12)) - 1, &prng);
 331         /* Let the chunk size be a random power of 2 less than size */
 332         ms = BIT(drm_prandom_u32_max_state(ilog2(s), &prng));
 333         /* Round size down to the chunk size */
 334         s &= -ms;
 335
 336         /* Convert from pages to bytes */
 337         *chunk_size = (u64)ms << 12;
 338         *size = (u64)s << 12;
 339 }
 340
 341 static int igt_buddy_alloc_pathological(void *arg)
 342 {
 343         u64 mm_size, size, min_page_size, start = 0;
 344         struct drm_buddy_block *block;
 345         const int max_order = 3;
 346         unsigned long flags = 0;
 347         int order, top, err;
 348         struct drm_buddy mm;
 349         LIST_HEAD(blocks);
 350         LIST_HEAD(holes);
 351         LIST_HEAD(tmp);
 352
 353         /*
 354          * Create a pot-sized mm, then allocate one of each possible
 355          * order within. This should leave the mm with exactly one
 356          * page left. Free the largest block, then whittle down again.
 357          * Eventually we will have a fully 50% fragmented mm.
 358          */
 359
 360         mm_size = PAGE_SIZE << max_order;
 361         err = drm_buddy_init(&mm, mm_size, PAGE_SIZE);
 362         if (err) {
 363                 pr_err("buddy_init failed(%d)\n", err);
 364                 return err;
 365         }
 366         BUG_ON(mm.max_order != max_order);
 367
 368         for (top = max_order; top; top--) {
 369                 /* Make room by freeing the largest allocated block */
 370                 block = list_first_entry_or_null(&blocks, typeof(*block), link);
 371                 if (block) {
 372                         list_del(&block->link);
 373                         drm_buddy_free_block(&mm, block);
 374                 }
 375
 376                 for (order = top; order--; ) {
 377                         size = min_page_size = get_size(order, PAGE_SIZE);
 378                         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size,
 379                                                      min_page_size, &tmp, flags);
 380                         if (err) {
 381                                 pr_info("buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
 382                                         order, top);
 383                                 goto err;
 384                         }
 385
 386                         block = list_first_entry_or_null(&tmp,
 387                                                          struct drm_buddy_block,
 388                                                          link);
 389                         if (!block) {
 390                                 pr_err("alloc_blocks has no blocks\n");
 391                                 err = -EINVAL;
 392                                 goto err;
 393                         }
 394
 395                         list_move_tail(&block->link, &blocks);
 396                 }
 397
 398                 /* There should be one final page for this sub-allocation */
 399                 size = min_page_size = get_size(0, PAGE_SIZE);
 400                 err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 401                 if (err) {
 402                         pr_info("buddy_alloc hit -ENOMEM for hole\n");
 403                         goto err;
 404                 }
 405
 406                 block = list_first_entry_or_null(&tmp,
 407                                                  struct drm_buddy_block,
 408                                                  link);
 409                 if (!block) {
 410                         pr_err("alloc_blocks has no blocks\n");
 411                         err = -EINVAL;
 412                         goto err;
 413                 }
 414
 415                 list_move_tail(&block->link, &holes);
 416
 417                 size = min_page_size = get_size(top, PAGE_SIZE);
 418                 err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 419                 if (!err) {
 420                         pr_info("buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",
 421                                 top, max_order);
 422                         block = list_first_entry_or_null(&tmp,
 423                                                          struct drm_buddy_block,
 424                                                          link);
 425                         if (!block) {
 426                                 pr_err("alloc_blocks has no blocks\n");
 427                                 err = -EINVAL;
 428                                 goto err;
 429                         }
 430
 431                         list_move_tail(&block->link, &blocks);
 432                         err = -EINVAL;
 433                         goto err;
 434                 }
 435         }
 436
 437         drm_buddy_free_list(&mm, &holes);
 438
 439         /* Nothing larger than blocks of chunk_size now available */
 440         for (order = 1; order <= max_order; order++) {
 441                 size = min_page_size = get_size(order, PAGE_SIZE);
 442                 err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 443                 if (!err) {
 444                         pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
 445                                 order);
 446                         block = list_first_entry_or_null(&tmp,
 447                                                          struct drm_buddy_block,
 448                                                          link);
 449                         if (!block) {
 450                                 pr_err("alloc_blocks has no blocks\n");
 451                                 err = -EINVAL;
 452                                 goto err;
 453                         }
 454
 455                         list_move_tail(&block->link, &blocks);
 456                         err = -EINVAL;
 457                         goto err;
 458                 }
 459         }
 460
 461         if (err)
 462                 err = 0;
 463
 464 err:
 465         list_splice_tail(&holes, &blocks);
 466         drm_buddy_free_list(&mm, &blocks);
 467         drm_buddy_fini(&mm);
 468         return err;
 469 }
 470
 471 static int igt_buddy_alloc_smoke(void *arg)
 472 {
 473         u64 mm_size, min_page_size, chunk_size, start = 0;
 474         unsigned long flags = 0;
 475         struct drm_buddy mm;
 476         int *order;
 477         int err, i;
 478
 479         DRM_RND_STATE(prng, random_seed);
 480         IGT_TIMEOUT(end_time);
 481
 482         igt_mm_config(&mm_size, &chunk_size);
 483
 484         err = drm_buddy_init(&mm, mm_size, chunk_size);
 485         if (err) {
 486                 pr_err("buddy_init failed(%d)\n", err);
 487                 return err;
 488         }
 489
 490         order = drm_random_order(mm.max_order + 1, &prng);
 491         if (!order) {
 492                 err = -ENOMEM;
 493                 goto out_fini;
 494         }
 495
 496         for (i = 0; i <= mm.max_order; ++i) {
 497                 struct drm_buddy_block *block;
 498                 int max_order = order[i];
 499                 bool timeout = false;
 500                 LIST_HEAD(blocks);
 501                 u64 total, size;
 502                 LIST_HEAD(tmp);
 503                 int order;
 504
 505                 err = igt_check_mm(&mm);
 506                 if (err) {
 507                         pr_err("pre-mm check failed, abort\n");
 508                         break;
 509                 }
 510
 511                 order = max_order;
 512                 total = 0;
 513
 514                 do {
 515 retry:
 516                         size = min_page_size = get_size(order, chunk_size);
 517                         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size,
 518                                                      min_page_size, &tmp, flags);
 519                         if (err) {
 520                                 if (err == -ENOMEM) {
 521                                         pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
 522                                                 order);
 523                                 } else {
 524                                         if (order--) {
 525                                                 err = 0;
 526                                                 goto retry;
 527                                         }
 528
 529                                         pr_err("buddy_alloc with order=%d failed(%d)\n",
 530                                                order, err);
 531                                 }
 532
 533                                 break;
 534                         }
 535
 536                         block = list_first_entry_or_null(&tmp,
 537                                                          struct drm_buddy_block,
 538                                                          link);
 539                         if (!block) {
 540                                 pr_err("alloc_blocks has no blocks\n");
 541                                 err = -EINVAL;
 542                                 break;
 543                         }
 544
 545                         list_move_tail(&block->link, &blocks);
 546
 547                         if (drm_buddy_block_order(block) != order) {
 548                                 pr_err("buddy_alloc order mismatch\n");
 549                                 err = -EINVAL;
 550                                 break;
 551                         }
 552
 553                         total += drm_buddy_block_size(&mm, block);
 554
 555                         if (__igt_timeout(end_time, NULL)) {
 556                                 timeout = true;
 557                                 break;
 558                         }
 559                 } while (total < mm.size);
 560
 561                 if (!err)
 562                         err = igt_check_blocks(&mm, &blocks, total, false);
 563
 564                 drm_buddy_free_list(&mm, &blocks);
 565
 566                 if (!err) {
 567                         err = igt_check_mm(&mm);
 568                         if (err)
 569                                 pr_err("post-mm check failed\n");
 570                 }
 571
 572                 if (err || timeout)
 573                         break;
 574
 575                 cond_resched();
 576         }
 577
 578         if (err == -ENOMEM)
 579                 err = 0;
 580
 581         kfree(order);
 582 out_fini:
 583         drm_buddy_fini(&mm);
 584
 585         return err;
 586 }
 587
 588 static int igt_buddy_alloc_pessimistic(void *arg)
 589 {
 590         u64 mm_size, size, min_page_size, start = 0;
 591         struct drm_buddy_block *block, *bn;
 592         const unsigned int max_order = 16;
 593         unsigned long flags = 0;
 594         struct drm_buddy mm;
 595         unsigned int order;
 596         LIST_HEAD(blocks);
 597         LIST_HEAD(tmp);
 598         int err;
 599
 600         /*
 601          * Create a pot-sized mm, then allocate one of each possible
 602          * order within. This should leave the mm with exactly one
 603          * page left.
 604          */
 605
 606         mm_size = PAGE_SIZE << max_order;
 607         err = drm_buddy_init(&mm, mm_size, PAGE_SIZE);
 608         if (err) {
 609                 pr_err("buddy_init failed(%d)\n", err);
 610                 return err;
 611         }
 612         BUG_ON(mm.max_order != max_order);
 613
 614         for (order = 0; order < max_order; order++) {
 615                 size = min_page_size = get_size(order, PAGE_SIZE);
 616                 err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 617                 if (err) {
 618                         pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
 619                                 order);
 620                         goto err;
 621                 }
 622
 623                 block = list_first_entry_or_null(&tmp,
 624                                                  struct drm_buddy_block,
 625                                                  link);
 626                 if (!block) {
 627                         pr_err("alloc_blocks has no blocks\n");
 628                         err = -EINVAL;
 629                         goto err;
 630                 }
 631
 632                 list_move_tail(&block->link, &blocks);
 633         }
 634
 635         /* And now the last remaining block available */
 636         size = min_page_size = get_size(0, PAGE_SIZE);
 637         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 638         if (err) {
 639                 pr_info("buddy_alloc hit -ENOMEM on final alloc\n");
 640                 goto err;
 641         }
 642
 643         block = list_first_entry_or_null(&tmp,
 644                                          struct drm_buddy_block,
 645                                          link);
 646         if (!block) {
 647                 pr_err("alloc_blocks has no blocks\n");
 648                 err = -EINVAL;
 649                 goto err;
 650         }
 651
 652         list_move_tail(&block->link, &blocks);
 653
 654         /* Should be completely full! */
 655         for (order = max_order; order--; ) {
 656                 size = min_page_size = get_size(order, PAGE_SIZE);
 657                 err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 658                 if (!err) {
 659                         pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
 660                                 order);
 661                         block = list_first_entry_or_null(&tmp,
 662                                                          struct drm_buddy_block,
 663                                                          link);
 664                         if (!block) {
 665                                 pr_err("alloc_blocks has no blocks\n");
 666                                 err = -EINVAL;
 667                                 goto err;
 668                         }
 669
 670                         list_move_tail(&block->link, &blocks);
 671                         err = -EINVAL;
 672                         goto err;
 673                 }
 674         }
 675
 676         block = list_last_entry(&blocks, typeof(*block), link);
 677         list_del(&block->link);
 678         drm_buddy_free_block(&mm, block);
 679
 680         /* As we free in increasing size, we make available larger blocks */
 681         order = 1;
 682         list_for_each_entry_safe(block, bn, &blocks, link) {
 683                 list_del(&block->link);
 684                 drm_buddy_free_block(&mm, block);
 685
 686                 size = min_page_size = get_size(order, PAGE_SIZE);
 687                 err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 688                 if (err) {
 689                         pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
 690                                 order);
 691                         goto err;
 692                 }
 693
 694                 block = list_first_entry_or_null(&tmp,
 695                                                  struct drm_buddy_block,
 696                                                  link);
 697                 if (!block) {
 698                         pr_err("alloc_blocks has no blocks\n");
 699                         err = -EINVAL;
 700                         goto err;
 701                 }
 702
 703                 list_del(&block->link);
 704                 drm_buddy_free_block(&mm, block);
 705                 order++;
 706         }
 707
 708         /* To confirm, now the whole mm should be available */
 709         size = min_page_size = get_size(max_order, PAGE_SIZE);
 710         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 711         if (err) {
 712                 pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
 713                         max_order);
 714                 goto err;
 715         }
 716
 717         block = list_first_entry_or_null(&tmp,
 718                                          struct drm_buddy_block,
 719                                          link);
 720         if (!block) {
 721                 pr_err("alloc_blocks has no blocks\n");
 722                 err = -EINVAL;
 723                 goto err;
 724         }
 725
 726         list_del(&block->link);
 727         drm_buddy_free_block(&mm, block);
 728
 729 err:
 730         drm_buddy_free_list(&mm, &blocks);
 731         drm_buddy_fini(&mm);
 732         return err;
 733 }
 734
 735 static int igt_buddy_alloc_optimistic(void *arg)
 736 {
 737         u64 mm_size, size, min_page_size, start = 0;
 738         struct drm_buddy_block *block;
 739         unsigned long flags = 0;
 740         const int max_order = 16;
 741         struct drm_buddy mm;
 742         LIST_HEAD(blocks);
 743         LIST_HEAD(tmp);
 744         int order, err;
 745
 746         /*
 747          * Create a mm with one block of each order available, and
 748          * try to allocate them all.
 749          */
 750
 751         mm_size = PAGE_SIZE * ((1 << (max_order + 1)) - 1);
 752         err = drm_buddy_init(&mm,
 753                              mm_size,
 754                              PAGE_SIZE);
 755         if (err) {
 756                 pr_err("buddy_init failed(%d)\n", err);
 757                 return err;
 758         }
 759
 760         BUG_ON(mm.max_order != max_order);
 761
 762         for (order = 0; order <= max_order; order++) {
 763                 size = min_page_size = get_size(order, PAGE_SIZE);
 764                 err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 765                 if (err) {
 766                         pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
 767                                 order);
 768                         goto err;
 769                 }
 770
 771                 block = list_first_entry_or_null(&tmp,
 772                                                  struct drm_buddy_block,
 773                                                  link);
 774                 if (!block) {
 775                         pr_err("alloc_blocks has no blocks\n");
 776                         err = -EINVAL;
 777                         goto err;
 778                 }
 779
 780                 list_move_tail(&block->link, &blocks);
 781         }
 782
 783         /* Should be completely full! */
 784         size = min_page_size = get_size(0, PAGE_SIZE);
 785         err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, min_page_size, &tmp, flags);
 786         if (!err) {
 787                 pr_info("buddy_alloc unexpectedly succeeded, it should be full!");
 788                 block = list_first_entry_or_null(&tmp,
 789                                                  struct drm_buddy_block,
 790                                                  link);
 791                 if (!block) {
 792                         pr_err("alloc_blocks has no blocks\n");
 793                         err = -EINVAL;
 794                         goto err;
 795                 }
 796
 797                 list_move_tail(&block->link, &blocks);
 798                 err = -EINVAL;
 799                 goto err;
 800         } else {
 801                 err = 0;
 802         }
 803
 804 err:
 805         drm_buddy_free_list(&mm, &blocks);
 806         drm_buddy_fini(&mm);
 807         return err;
 808 }
 809
 810 static int igt_buddy_alloc_range(void *arg)
 811 {
 812         unsigned long flags = DRM_BUDDY_RANGE_ALLOCATION;
 813         u64 offset, size, rem, chunk_size, end;
 814         unsigned long page_num;
 815         struct drm_buddy mm;
 816         LIST_HEAD(blocks);
 817         int err;
 818
 819         igt_mm_config(&size, &chunk_size);
 820
 821         err = drm_buddy_init(&mm, size, chunk_size);
 822         if (err) {
 823                 pr_err("buddy_init failed(%d)\n", err);
 824                 return err;
 825         }
 826
 827         err = igt_check_mm(&mm);
 828         if (err) {
 829                 pr_err("pre-mm check failed, abort, abort, abort!\n");
 830                 goto err_fini;
 831         }
 832
 833         rem = mm.size;
 834         offset = 0;
 835
 836         for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
 837                 struct drm_buddy_block *block;
 838                 LIST_HEAD(tmp);
 839
 840                 size = min(page_num * mm.chunk_size, rem);
 841                 end = offset + size;
 842
 843                 err = drm_buddy_alloc_blocks(&mm, offset, end, size, mm.chunk_size, &tmp, flags);
 844                 if (err) {
 845                         if (err == -ENOMEM) {
 846                                 pr_info("alloc_range hit -ENOMEM with size=%llx\n",
 847                                         size);
 848                         } else {
 849                                 pr_err("alloc_range with offset=%llx, size=%llx failed(%d)\n",
 850                                        offset, size, err);
 851                         }
 852
 853                         break;
 854                 }
 855
 856                 block = list_first_entry_or_null(&tmp,
 857                                                  struct drm_buddy_block,
 858                                                  link);
 859                 if (!block) {
 860                         pr_err("alloc_range has no blocks\n");
 861                         err = -EINVAL;
 862                         break;
 863                 }
 864
 865                 if (drm_buddy_block_offset(block) != offset) {
 866                         pr_err("alloc_range start offset mismatch, found=%llx, expected=%llx\n",
 867                                drm_buddy_block_offset(block), offset);
 868                         err = -EINVAL;
 869                 }
 870
 871                 if (!err)
 872                         err = igt_check_blocks(&mm, &tmp, size, true);
 873
 874                 list_splice_tail(&tmp, &blocks);
 875
 876                 if (err)
 877                         break;
 878
 879                 offset += size;
 880
 881                 rem -= size;
 882                 if (!rem)
 883                         break;
 884
 885                 cond_resched();
 886         }
 887
 888         if (err == -ENOMEM)
 889                 err = 0;
 890
 891         drm_buddy_free_list(&mm, &blocks);
 892
 893         if (!err) {
 894                 err = igt_check_mm(&mm);
 895                 if (err)
 896                         pr_err("post-mm check failed\n");
 897         }
 898
 899 err_fini:
 900         drm_buddy_fini(&mm);
 901
 902         return err;
 903 }
 904
 905 static int igt_buddy_alloc_limit(void *arg)
 906 {
 907         u64 size = U64_MAX, start = 0;
 908         struct drm_buddy_block *block;
 909         unsigned long flags = 0;
 910         LIST_HEAD(allocated);
 911         struct drm_buddy mm;
 912         int err;
 913
 914         err = drm_buddy_init(&mm, size, PAGE_SIZE);
 915         if (err)
 916                 return err;
 917
 918         if (mm.max_order != DRM_BUDDY_MAX_ORDER) {
 919                 pr_err("mm.max_order(%d) != %d\n",
 920                        mm.max_order, DRM_BUDDY_MAX_ORDER);
 921                 err = -EINVAL;
 922                 goto out_fini;
 923         }
 924
 925         size = mm.chunk_size << mm.max_order;
 926         err = drm_buddy_alloc_blocks(&mm, start, size, size,
 927                                      PAGE_SIZE, &allocated, flags);
 928
 929         if (unlikely(err))
 930                 goto out_free;
 931
 932         block = list_first_entry_or_null(&allocated,
 933                                          struct drm_buddy_block,
 934                                          link);
 935
 936         if (!block) {
 937                 err = -EINVAL;
 938                 goto out_fini;
 939         }
 940
 941         if (drm_buddy_block_order(block) != mm.max_order) {
 942                 pr_err("block order(%d) != %d\n",
 943                        drm_buddy_block_order(block), mm.max_order);
 944                 err = -EINVAL;
 945                 goto out_free;
 946         }
 947
 948         if (drm_buddy_block_size(&mm, block) !=
 949             BIT_ULL(mm.max_order) * PAGE_SIZE) {
 950                 pr_err("block size(%llu) != %llu\n",
 951                        drm_buddy_block_size(&mm, block),
 952                        BIT_ULL(mm.max_order) * PAGE_SIZE);
 953                 err = -EINVAL;
 954                 goto out_free;
 955         }
 956
 957 out_free:
 958         drm_buddy_free_list(&mm, &allocated);
 959 out_fini:
 960         drm_buddy_fini(&mm);
 961         return err;
 962 }
 963
 964 static int igt_sanitycheck(void *ignored)
 965 {
 966         pr_info("%s - ok!\n", __func__);
 967         return 0;
 968 }
 969
 970 #include "drm_selftest.c"
 971
 972 static int __init test_drm_buddy_init(void)
 973 {
 974         int err;
 975
 976         while (!random_seed)
 977                 random_seed = get_random_int();
 978
 979         pr_info("Testing DRM buddy manager (struct drm_buddy), with random_seed=0x%x\n",
 980                 random_seed);
 981         err = run_selftests(selftests, ARRAY_SIZE(selftests), NULL);
 982
 983         return err > 0 ? 0 : err;
 984 }
 985
 986 static void __exit test_drm_buddy_exit(void)
 987 {
 988 }
 989
 990 module_init(test_drm_buddy_init);
 991 module_exit(test_drm_buddy_exit);
 992
 993 MODULE_AUTHOR("Intel Corporation");
 994 MODULE_LICENSE("GPL");