779 lines · c
1// SPDX-License-Identifier: MIT2/*3 * Copyright © 2019 Intel Corporation4 * Copyright © 2022 Maíra Canal <mairacanal@riseup.net>5 */6 7#include <kunit/test.h>8 9#include <linux/prime_numbers.h>10#include <linux/sched/signal.h>11#include <linux/sizes.h>12 13#include <drm/drm_buddy.h>14 15#include "../lib/drm_random.h"16 17static unsigned int random_seed;18 19static inline u64 get_size(int order, u64 chunk_size)20{21 return (1 << order) * chunk_size;22}23 24static void drm_test_buddy_alloc_range_bias(struct kunit *test)25{26 u32 mm_size, size, ps, bias_size, bias_start, bias_end, bias_rem;27 DRM_RND_STATE(prng, random_seed);28 unsigned int i, count, *order;29 struct drm_buddy_block *block;30 unsigned long flags;31 struct drm_buddy mm;32 LIST_HEAD(allocated);33 34 bias_size = SZ_1M;35 ps = roundup_pow_of_two(prandom_u32_state(&prng) % bias_size);36 ps = max(SZ_4K, ps);37 mm_size = (SZ_8M-1) & ~(ps-1); /* Multiple roots */38 39 kunit_info(test, "mm_size=%u, ps=%u\n", mm_size, ps);40 41 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, ps),42 "buddy_init failed\n");43 44 count = mm_size / bias_size;45 order = drm_random_order(count, &prng);46 KUNIT_EXPECT_TRUE(test, order);47 48 /*49 * Idea is to split the address space into uniform bias ranges, and then50 * in some random order allocate within each bias, using various51 * patterns within. This should detect if allocations leak out from a52 * given bias, for example.53 */54 55 for (i = 0; i < count; i++) {56 LIST_HEAD(tmp);57 u32 size;58 59 bias_start = order[i] * bias_size;60 bias_end = bias_start + bias_size;61 bias_rem = bias_size;62 63 /* internal round_up too big */64 KUNIT_ASSERT_TRUE_MSG(test,65 drm_buddy_alloc_blocks(&mm, bias_start,66 bias_end, bias_size + ps, bias_size,67 &allocated,68 DRM_BUDDY_RANGE_ALLOCATION),69 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",70 bias_start, bias_end, bias_size, bias_size);71 72 /* size too big */73 KUNIT_ASSERT_TRUE_MSG(test,74 drm_buddy_alloc_blocks(&mm, bias_start,75 bias_end, bias_size + ps, ps,76 &allocated,77 DRM_BUDDY_RANGE_ALLOCATION),78 "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",79 bias_start, bias_end, bias_size + ps, ps);80 81 /* bias range too small for size */82 KUNIT_ASSERT_TRUE_MSG(test,83 drm_buddy_alloc_blocks(&mm, bias_start + ps,84 bias_end, bias_size, ps,85 &allocated,86 DRM_BUDDY_RANGE_ALLOCATION),87 "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",88 bias_start + ps, bias_end, bias_size, ps);89 90 /* bias misaligned */91 KUNIT_ASSERT_TRUE_MSG(test,92 drm_buddy_alloc_blocks(&mm, bias_start + ps,93 bias_end - ps,94 bias_size >> 1, bias_size >> 1,95 &allocated,96 DRM_BUDDY_RANGE_ALLOCATION),97 "buddy_alloc h didn't fail with bias(%x-%x), size=%u, ps=%u\n",98 bias_start + ps, bias_end - ps, bias_size >> 1, bias_size >> 1);99 100 /* single big page */101 KUNIT_ASSERT_FALSE_MSG(test,102 drm_buddy_alloc_blocks(&mm, bias_start,103 bias_end, bias_size, bias_size,104 &tmp,105 DRM_BUDDY_RANGE_ALLOCATION),106 "buddy_alloc i failed with bias(%x-%x), size=%u, ps=%u\n",107 bias_start, bias_end, bias_size, bias_size);108 drm_buddy_free_list(&mm, &tmp, 0);109 110 /* single page with internal round_up */111 KUNIT_ASSERT_FALSE_MSG(test,112 drm_buddy_alloc_blocks(&mm, bias_start,113 bias_end, ps, bias_size,114 &tmp,115 DRM_BUDDY_RANGE_ALLOCATION),116 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",117 bias_start, bias_end, ps, bias_size);118 drm_buddy_free_list(&mm, &tmp, 0);119 120 /* random size within */121 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);122 if (size)123 KUNIT_ASSERT_FALSE_MSG(test,124 drm_buddy_alloc_blocks(&mm, bias_start,125 bias_end, size, ps,126 &tmp,127 DRM_BUDDY_RANGE_ALLOCATION),128 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",129 bias_start, bias_end, size, ps);130 131 bias_rem -= size;132 /* too big for current avail */133 KUNIT_ASSERT_TRUE_MSG(test,134 drm_buddy_alloc_blocks(&mm, bias_start,135 bias_end, bias_rem + ps, ps,136 &allocated,137 DRM_BUDDY_RANGE_ALLOCATION),138 "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",139 bias_start, bias_end, bias_rem + ps, ps);140 141 if (bias_rem) {142 /* random fill of the remainder */143 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);144 size = max(size, ps);145 146 KUNIT_ASSERT_FALSE_MSG(test,147 drm_buddy_alloc_blocks(&mm, bias_start,148 bias_end, size, ps,149 &allocated,150 DRM_BUDDY_RANGE_ALLOCATION),151 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",152 bias_start, bias_end, size, ps);153 /*154 * Intentionally allow some space to be left155 * unallocated, and ideally not always on the bias156 * boundaries.157 */158 drm_buddy_free_list(&mm, &tmp, 0);159 } else {160 list_splice_tail(&tmp, &allocated);161 }162 }163 164 kfree(order);165 drm_buddy_free_list(&mm, &allocated, 0);166 drm_buddy_fini(&mm);167 168 /*169 * Something more free-form. Idea is to pick a random starting bias170 * range within the address space and then start filling it up. Also171 * randomly grow the bias range in both directions as we go along. This172 * should give us bias start/end which is not always uniform like above,173 * and in some cases will require the allocator to jump over already174 * allocated nodes in the middle of the address space.175 */176 177 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, ps),178 "buddy_init failed\n");179 180 bias_start = round_up(prandom_u32_state(&prng) % (mm_size - ps), ps);181 bias_end = round_up(bias_start + prandom_u32_state(&prng) % (mm_size - bias_start), ps);182 bias_end = max(bias_end, bias_start + ps);183 bias_rem = bias_end - bias_start;184 185 do {186 u32 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);187 188 KUNIT_ASSERT_FALSE_MSG(test,189 drm_buddy_alloc_blocks(&mm, bias_start,190 bias_end, size, ps,191 &allocated,192 DRM_BUDDY_RANGE_ALLOCATION),193 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",194 bias_start, bias_end, size, ps);195 bias_rem -= size;196 197 /*198 * Try to randomly grow the bias range in both directions, or199 * only one, or perhaps don't grow at all.200 */201 do {202 u32 old_bias_start = bias_start;203 u32 old_bias_end = bias_end;204 205 if (bias_start)206 bias_start -= round_up(prandom_u32_state(&prng) % bias_start, ps);207 if (bias_end != mm_size)208 bias_end += round_up(prandom_u32_state(&prng) % (mm_size - bias_end), ps);209 210 bias_rem += old_bias_start - bias_start;211 bias_rem += bias_end - old_bias_end;212 } while (!bias_rem && (bias_start || bias_end != mm_size));213 } while (bias_rem);214 215 KUNIT_ASSERT_EQ(test, bias_start, 0);216 KUNIT_ASSERT_EQ(test, bias_end, mm_size);217 KUNIT_ASSERT_TRUE_MSG(test,218 drm_buddy_alloc_blocks(&mm, bias_start, bias_end,219 ps, ps,220 &allocated,221 DRM_BUDDY_RANGE_ALLOCATION),222 "buddy_alloc passed with bias(%x-%x), size=%u\n",223 bias_start, bias_end, ps);224 225 drm_buddy_free_list(&mm, &allocated, 0);226 drm_buddy_fini(&mm);227 228 /*229 * Allocate cleared blocks in the bias range when the DRM buddy's clear avail is230 * zero. This will validate the bias range allocation in scenarios like system boot231 * when no cleared blocks are available and exercise the fallback path too. The resulting232 * blocks should always be dirty.233 */234 235 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, ps),236 "buddy_init failed\n");237 238 bias_start = round_up(prandom_u32_state(&prng) % (mm_size - ps), ps);239 bias_end = round_up(bias_start + prandom_u32_state(&prng) % (mm_size - bias_start), ps);240 bias_end = max(bias_end, bias_start + ps);241 bias_rem = bias_end - bias_start;242 243 flags = DRM_BUDDY_CLEAR_ALLOCATION | DRM_BUDDY_RANGE_ALLOCATION;244 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);245 246 KUNIT_ASSERT_FALSE_MSG(test,247 drm_buddy_alloc_blocks(&mm, bias_start,248 bias_end, size, ps,249 &allocated,250 flags),251 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",252 bias_start, bias_end, size, ps);253 254 list_for_each_entry(block, &allocated, link)255 KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), false);256 257 drm_buddy_free_list(&mm, &allocated, 0);258 drm_buddy_fini(&mm);259}260 261static void drm_test_buddy_alloc_clear(struct kunit *test)262{263 unsigned long n_pages, total, i = 0;264 DRM_RND_STATE(prng, random_seed);265 const unsigned long ps = SZ_4K;266 struct drm_buddy_block *block;267 const int max_order = 12;268 LIST_HEAD(allocated);269 struct drm_buddy mm;270 unsigned int order;271 u32 mm_size, size;272 LIST_HEAD(dirty);273 LIST_HEAD(clean);274 275 mm_size = SZ_4K << max_order;276 KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));277 278 KUNIT_EXPECT_EQ(test, mm.max_order, max_order);279 280 /*281 * Idea is to allocate and free some random portion of the address space,282 * returning those pages as non-dirty and randomly alternate between283 * requesting dirty and non-dirty pages (not going over the limit284 * we freed as non-dirty), putting that into two separate lists.285 * Loop over both lists at the end checking that the dirty list286 * is indeed all dirty pages and vice versa. Free it all again,287 * keeping the dirty/clear status.288 */289 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,290 5 * ps, ps, &allocated,291 DRM_BUDDY_TOPDOWN_ALLOCATION),292 "buddy_alloc hit an error size=%lu\n", 5 * ps);293 drm_buddy_free_list(&mm, &allocated, DRM_BUDDY_CLEARED);294 295 n_pages = 10;296 do {297 unsigned long flags;298 struct list_head *list;299 int slot = i % 2;300 301 if (slot == 0) {302 list = &dirty;303 flags = 0;304 } else {305 list = &clean;306 flags = DRM_BUDDY_CLEAR_ALLOCATION;307 }308 309 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,310 ps, ps, list,311 flags),312 "buddy_alloc hit an error size=%lu\n", ps);313 } while (++i < n_pages);314 315 list_for_each_entry(block, &clean, link)316 KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), true);317 318 list_for_each_entry(block, &dirty, link)319 KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), false);320 321 drm_buddy_free_list(&mm, &clean, DRM_BUDDY_CLEARED);322 323 /*324 * Trying to go over the clear limit for some allocation.325 * The allocation should never fail with reasonable page-size.326 */327 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,328 10 * ps, ps, &clean,329 DRM_BUDDY_CLEAR_ALLOCATION),330 "buddy_alloc hit an error size=%lu\n", 10 * ps);331 332 drm_buddy_free_list(&mm, &clean, DRM_BUDDY_CLEARED);333 drm_buddy_free_list(&mm, &dirty, 0);334 drm_buddy_fini(&mm);335 336 KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));337 338 /*339 * Create a new mm. Intentionally fragment the address space by creating340 * two alternating lists. Free both lists, one as dirty the other as clean.341 * Try to allocate double the previous size with matching min_page_size. The342 * allocation should never fail as it calls the force_merge. Also check that343 * the page is always dirty after force_merge. Free the page as dirty, then344 * repeat the whole thing, increment the order until we hit the max_order.345 */346 347 i = 0;348 n_pages = mm_size / ps;349 do {350 struct list_head *list;351 int slot = i % 2;352 353 if (slot == 0)354 list = &dirty;355 else356 list = &clean;357 358 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,359 ps, ps, list, 0),360 "buddy_alloc hit an error size=%lu\n", ps);361 } while (++i < n_pages);362 363 drm_buddy_free_list(&mm, &clean, DRM_BUDDY_CLEARED);364 drm_buddy_free_list(&mm, &dirty, 0);365 366 order = 1;367 do {368 size = SZ_4K << order;369 370 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,371 size, size, &allocated,372 DRM_BUDDY_CLEAR_ALLOCATION),373 "buddy_alloc hit an error size=%u\n", size);374 total = 0;375 list_for_each_entry(block, &allocated, link) {376 if (size != mm_size)377 KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), false);378 total += drm_buddy_block_size(&mm, block);379 }380 KUNIT_EXPECT_EQ(test, total, size);381 382 drm_buddy_free_list(&mm, &allocated, 0);383 } while (++order <= max_order);384 385 drm_buddy_fini(&mm);386 387 /*388 * Create a new mm with a non power-of-two size. Allocate a random size, free as389 * cleared and then call fini. This will ensure the multi-root force merge during390 * fini.391 */392 mm_size = 12 * SZ_4K;393 size = max(round_up(prandom_u32_state(&prng) % mm_size, ps), ps);394 KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));395 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,396 size, ps, &allocated,397 DRM_BUDDY_TOPDOWN_ALLOCATION),398 "buddy_alloc hit an error size=%u\n", size);399 drm_buddy_free_list(&mm, &allocated, DRM_BUDDY_CLEARED);400 drm_buddy_fini(&mm);401}402 403static void drm_test_buddy_alloc_contiguous(struct kunit *test)404{405 const unsigned long ps = SZ_4K, mm_size = 16 * 3 * SZ_4K;406 unsigned long i, n_pages, total;407 struct drm_buddy_block *block;408 struct drm_buddy mm;409 LIST_HEAD(left);410 LIST_HEAD(middle);411 LIST_HEAD(right);412 LIST_HEAD(allocated);413 414 KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));415 416 /*417 * Idea is to fragment the address space by alternating block418 * allocations between three different lists; one for left, middle and419 * right. We can then free a list to simulate fragmentation. In420 * particular we want to exercise the DRM_BUDDY_CONTIGUOUS_ALLOCATION,421 * including the try_harder path.422 */423 424 i = 0;425 n_pages = mm_size / ps;426 do {427 struct list_head *list;428 int slot = i % 3;429 430 if (slot == 0)431 list = &left;432 else if (slot == 1)433 list = &middle;434 else435 list = &right;436 KUNIT_ASSERT_FALSE_MSG(test,437 drm_buddy_alloc_blocks(&mm, 0, mm_size,438 ps, ps, list, 0),439 "buddy_alloc hit an error size=%lu\n",440 ps);441 } while (++i < n_pages);442 443 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,444 3 * ps, ps, &allocated,445 DRM_BUDDY_CONTIGUOUS_ALLOCATION),446 "buddy_alloc didn't error size=%lu\n", 3 * ps);447 448 drm_buddy_free_list(&mm, &middle, 0);449 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,450 3 * ps, ps, &allocated,451 DRM_BUDDY_CONTIGUOUS_ALLOCATION),452 "buddy_alloc didn't error size=%lu\n", 3 * ps);453 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,454 2 * ps, ps, &allocated,455 DRM_BUDDY_CONTIGUOUS_ALLOCATION),456 "buddy_alloc didn't error size=%lu\n", 2 * ps);457 458 drm_buddy_free_list(&mm, &right, 0);459 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,460 3 * ps, ps, &allocated,461 DRM_BUDDY_CONTIGUOUS_ALLOCATION),462 "buddy_alloc didn't error size=%lu\n", 3 * ps);463 /*464 * At this point we should have enough contiguous space for 2 blocks,465 * however they are never buddies (since we freed middle and right) so466 * will require the try_harder logic to find them.467 */468 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,469 2 * ps, ps, &allocated,470 DRM_BUDDY_CONTIGUOUS_ALLOCATION),471 "buddy_alloc hit an error size=%lu\n", 2 * ps);472 473 drm_buddy_free_list(&mm, &left, 0);474 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,475 3 * ps, ps, &allocated,476 DRM_BUDDY_CONTIGUOUS_ALLOCATION),477 "buddy_alloc hit an error size=%lu\n", 3 * ps);478 479 total = 0;480 list_for_each_entry(block, &allocated, link)481 total += drm_buddy_block_size(&mm, block);482 483 KUNIT_ASSERT_EQ(test, total, ps * 2 + ps * 3);484 485 drm_buddy_free_list(&mm, &allocated, 0);486 drm_buddy_fini(&mm);487}488 489static void drm_test_buddy_alloc_pathological(struct kunit *test)490{491 u64 mm_size, size, start = 0;492 struct drm_buddy_block *block;493 const int max_order = 3;494 unsigned long flags = 0;495 int order, top;496 struct drm_buddy mm;497 LIST_HEAD(blocks);498 LIST_HEAD(holes);499 LIST_HEAD(tmp);500 501 /*502 * Create a pot-sized mm, then allocate one of each possible503 * order within. This should leave the mm with exactly one504 * page left. Free the largest block, then whittle down again.505 * Eventually we will have a fully 50% fragmented mm.506 */507 508 mm_size = SZ_4K << max_order;509 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, SZ_4K),510 "buddy_init failed\n");511 512 KUNIT_EXPECT_EQ(test, mm.max_order, max_order);513 514 for (top = max_order; top; top--) {515 /* Make room by freeing the largest allocated block */516 block = list_first_entry_or_null(&blocks, typeof(*block), link);517 if (block) {518 list_del(&block->link);519 drm_buddy_free_block(&mm, block);520 }521 522 for (order = top; order--;) {523 size = get_size(order, mm.chunk_size);524 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start,525 mm_size, size, size,526 &tmp, flags),527 "buddy_alloc hit -ENOMEM with order=%d, top=%d\n",528 order, top);529 530 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);531 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");532 533 list_move_tail(&block->link, &blocks);534 }535 536 /* There should be one final page for this sub-allocation */537 size = get_size(0, mm.chunk_size);538 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,539 size, size, &tmp, flags),540 "buddy_alloc hit -ENOMEM for hole\n");541 542 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);543 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");544 545 list_move_tail(&block->link, &holes);546 547 size = get_size(top, mm.chunk_size);548 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,549 size, size, &tmp, flags),550 "buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",551 top, max_order);552 }553 554 drm_buddy_free_list(&mm, &holes, 0);555 556 /* Nothing larger than blocks of chunk_size now available */557 for (order = 1; order <= max_order; order++) {558 size = get_size(order, mm.chunk_size);559 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,560 size, size, &tmp, flags),561 "buddy_alloc unexpectedly succeeded at order %d, it should be full!",562 order);563 }564 565 list_splice_tail(&holes, &blocks);566 drm_buddy_free_list(&mm, &blocks, 0);567 drm_buddy_fini(&mm);568}569 570static void drm_test_buddy_alloc_pessimistic(struct kunit *test)571{572 u64 mm_size, size, start = 0;573 struct drm_buddy_block *block, *bn;574 const unsigned int max_order = 16;575 unsigned long flags = 0;576 struct drm_buddy mm;577 unsigned int order;578 LIST_HEAD(blocks);579 LIST_HEAD(tmp);580 581 /*582 * Create a pot-sized mm, then allocate one of each possible583 * order within. This should leave the mm with exactly one584 * page left.585 */586 587 mm_size = SZ_4K << max_order;588 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, SZ_4K),589 "buddy_init failed\n");590 591 KUNIT_EXPECT_EQ(test, mm.max_order, max_order);592 593 for (order = 0; order < max_order; order++) {594 size = get_size(order, mm.chunk_size);595 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,596 size, size, &tmp, flags),597 "buddy_alloc hit -ENOMEM with order=%d\n",598 order);599 600 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);601 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");602 603 list_move_tail(&block->link, &blocks);604 }605 606 /* And now the last remaining block available */607 size = get_size(0, mm.chunk_size);608 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,609 size, size, &tmp, flags),610 "buddy_alloc hit -ENOMEM on final alloc\n");611 612 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);613 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");614 615 list_move_tail(&block->link, &blocks);616 617 /* Should be completely full! */618 for (order = max_order; order--;) {619 size = get_size(order, mm.chunk_size);620 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,621 size, size, &tmp, flags),622 "buddy_alloc unexpectedly succeeded, it should be full!");623 }624 625 block = list_last_entry(&blocks, typeof(*block), link);626 list_del(&block->link);627 drm_buddy_free_block(&mm, block);628 629 /* As we free in increasing size, we make available larger blocks */630 order = 1;631 list_for_each_entry_safe(block, bn, &blocks, link) {632 list_del(&block->link);633 drm_buddy_free_block(&mm, block);634 635 size = get_size(order, mm.chunk_size);636 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,637 size, size, &tmp, flags),638 "buddy_alloc hit -ENOMEM with order=%d\n",639 order);640 641 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);642 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");643 644 list_del(&block->link);645 drm_buddy_free_block(&mm, block);646 order++;647 }648 649 /* To confirm, now the whole mm should be available */650 size = get_size(max_order, mm.chunk_size);651 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,652 size, size, &tmp, flags),653 "buddy_alloc (realloc) hit -ENOMEM with order=%d\n",654 max_order);655 656 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);657 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");658 659 list_del(&block->link);660 drm_buddy_free_block(&mm, block);661 drm_buddy_free_list(&mm, &blocks, 0);662 drm_buddy_fini(&mm);663}664 665static void drm_test_buddy_alloc_optimistic(struct kunit *test)666{667 u64 mm_size, size, start = 0;668 struct drm_buddy_block *block;669 unsigned long flags = 0;670 const int max_order = 16;671 struct drm_buddy mm;672 LIST_HEAD(blocks);673 LIST_HEAD(tmp);674 int order;675 676 /*677 * Create a mm with one block of each order available, and678 * try to allocate them all.679 */680 681 mm_size = SZ_4K * ((1 << (max_order + 1)) - 1);682 683 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, SZ_4K),684 "buddy_init failed\n");685 686 KUNIT_EXPECT_EQ(test, mm.max_order, max_order);687 688 for (order = 0; order <= max_order; order++) {689 size = get_size(order, mm.chunk_size);690 KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,691 size, size, &tmp, flags),692 "buddy_alloc hit -ENOMEM with order=%d\n",693 order);694 695 block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);696 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");697 698 list_move_tail(&block->link, &blocks);699 }700 701 /* Should be completely full! */702 size = get_size(0, mm.chunk_size);703 KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,704 size, size, &tmp, flags),705 "buddy_alloc unexpectedly succeeded, it should be full!");706 707 drm_buddy_free_list(&mm, &blocks, 0);708 drm_buddy_fini(&mm);709}710 711static void drm_test_buddy_alloc_limit(struct kunit *test)712{713 u64 size = U64_MAX, start = 0;714 struct drm_buddy_block *block;715 unsigned long flags = 0;716 LIST_HEAD(allocated);717 struct drm_buddy mm;718 719 KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, size, SZ_4K));720 721 KUNIT_EXPECT_EQ_MSG(test, mm.max_order, DRM_BUDDY_MAX_ORDER,722 "mm.max_order(%d) != %d\n", mm.max_order,723 DRM_BUDDY_MAX_ORDER);724 725 size = mm.chunk_size << mm.max_order;726 KUNIT_EXPECT_FALSE(test, drm_buddy_alloc_blocks(&mm, start, size, size,727 mm.chunk_size, &allocated, flags));728 729 block = list_first_entry_or_null(&allocated, struct drm_buddy_block, link);730 KUNIT_EXPECT_TRUE(test, block);731 732 KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_order(block), mm.max_order,733 "block order(%d) != %d\n",734 drm_buddy_block_order(block), mm.max_order);735 736 KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_size(&mm, block),737 BIT_ULL(mm.max_order) * mm.chunk_size,738 "block size(%llu) != %llu\n",739 drm_buddy_block_size(&mm, block),740 BIT_ULL(mm.max_order) * mm.chunk_size);741 742 drm_buddy_free_list(&mm, &allocated, 0);743 drm_buddy_fini(&mm);744}745 746static int drm_buddy_suite_init(struct kunit_suite *suite)747{748 while (!random_seed)749 random_seed = get_random_u32();750 751 kunit_info(suite, "Testing DRM buddy manager, with random_seed=0x%x\n",752 random_seed);753 754 return 0;755}756 757static struct kunit_case drm_buddy_tests[] = {758 KUNIT_CASE(drm_test_buddy_alloc_limit),759 KUNIT_CASE(drm_test_buddy_alloc_optimistic),760 KUNIT_CASE(drm_test_buddy_alloc_pessimistic),761 KUNIT_CASE(drm_test_buddy_alloc_pathological),762 KUNIT_CASE(drm_test_buddy_alloc_contiguous),763 KUNIT_CASE(drm_test_buddy_alloc_clear),764 KUNIT_CASE(drm_test_buddy_alloc_range_bias),765 {}766};767 768static struct kunit_suite drm_buddy_test_suite = {769 .name = "drm_buddy",770 .suite_init = drm_buddy_suite_init,771 .test_cases = drm_buddy_tests,772};773 774kunit_test_suite(drm_buddy_test_suite);775 776MODULE_AUTHOR("Intel Corporation");777MODULE_DESCRIPTION("Kunit test for drm_buddy functions");778MODULE_LICENSE("GPL");779