drivers/gpu/drm/i915/selftests/i915_buddy.c

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