1 // SPDX-License-Identifier: MIT
3 * Copyright © 2019 Intel Corporation
6 #include <linux/prime_numbers.h>
8 #include "../i915_selftest.h"
9 #include "i915_random.h"
11 static void __igt_dump_block(struct i915_buddy_mm *mm,
12 struct i915_buddy_block *block,
15 pr_err("block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%s buddy=%s\n",
17 i915_buddy_block_state(block),
18 i915_buddy_block_order(block),
19 i915_buddy_block_offset(block),
20 i915_buddy_block_size(mm, block),
21 yesno(!block->parent),
25 static void igt_dump_block(struct i915_buddy_mm *mm,
26 struct i915_buddy_block *block)
28 struct i915_buddy_block *buddy;
30 __igt_dump_block(mm, block, false);
32 buddy = get_buddy(block);
34 __igt_dump_block(mm, buddy, true);
37 static int igt_check_block(struct i915_buddy_mm *mm,
38 struct i915_buddy_block *block)
40 struct i915_buddy_block *buddy;
41 unsigned int block_state;
46 block_state = i915_buddy_block_state(block);
48 if (block_state != I915_BUDDY_ALLOCATED &&
49 block_state != I915_BUDDY_FREE &&
50 block_state != I915_BUDDY_SPLIT) {
51 pr_err("block state mismatch\n");
55 block_size = i915_buddy_block_size(mm, block);
56 offset = i915_buddy_block_offset(block);
58 if (block_size < mm->chunk_size) {
59 pr_err("block size smaller than min size\n");
63 if (!is_power_of_2(block_size)) {
64 pr_err("block size not power of two\n");
68 if (!IS_ALIGNED(block_size, mm->chunk_size)) {
69 pr_err("block size not aligned to min size\n");
73 if (!IS_ALIGNED(offset, mm->chunk_size)) {
74 pr_err("block offset not aligned to min size\n");
78 if (!IS_ALIGNED(offset, block_size)) {
79 pr_err("block offset not aligned to block size\n");
83 buddy = get_buddy(block);
85 if (!buddy && block->parent) {
86 pr_err("buddy has gone fishing\n");
91 if (i915_buddy_block_offset(buddy) != (offset ^ block_size)) {
92 pr_err("buddy has wrong offset\n");
96 if (i915_buddy_block_size(mm, buddy) != block_size) {
97 pr_err("buddy size mismatch\n");
101 if (i915_buddy_block_state(buddy) == block_state &&
102 block_state == I915_BUDDY_FREE) {
103 pr_err("block and its buddy are free\n");
111 static int igt_check_blocks(struct i915_buddy_mm *mm,
112 struct list_head *blocks,
116 struct i915_buddy_block *block;
117 struct i915_buddy_block *prev;
125 list_for_each_entry(block, blocks, link) {
126 err = igt_check_block(mm, block);
128 if (!i915_buddy_block_is_allocated(block)) {
129 pr_err("block not allocated\n"),
133 if (is_contiguous && prev) {
138 prev_offset = i915_buddy_block_offset(prev);
139 prev_block_size = i915_buddy_block_size(mm, prev);
140 offset = i915_buddy_block_offset(block);
142 if (offset != (prev_offset + prev_block_size)) {
143 pr_err("block offset mismatch\n");
151 total += i915_buddy_block_size(mm, block);
156 if (total != expected_size) {
157 pr_err("size mismatch, expected=%llx, found=%llx\n",
158 expected_size, total);
165 pr_err("prev block, dump:\n");
166 igt_dump_block(mm, prev);
170 pr_err("bad block, dump:\n");
171 igt_dump_block(mm, block);
177 static int igt_check_mm(struct i915_buddy_mm *mm)
179 struct i915_buddy_block *root;
180 struct i915_buddy_block *prev;
186 pr_err("n_roots is zero\n");
190 if (mm->n_roots != hweight64(mm->size)) {
191 pr_err("n_roots mismatch, n_roots=%u, expected=%lu\n",
192 mm->n_roots, hweight64(mm->size));
200 for (i = 0; i < mm->n_roots; ++i) {
201 struct i915_buddy_block *block;
206 pr_err("root(%u) is NULL\n", i);
211 err = igt_check_block(mm, root);
213 if (!i915_buddy_block_is_free(root)) {
214 pr_err("root not free\n");
218 order = i915_buddy_block_order(root);
221 if (order != mm->max_order) {
222 pr_err("max order root missing\n");
232 prev_offset = i915_buddy_block_offset(prev);
233 prev_block_size = i915_buddy_block_size(mm, prev);
234 offset = i915_buddy_block_offset(root);
236 if (offset != (prev_offset + prev_block_size)) {
237 pr_err("root offset mismatch\n");
242 block = list_first_entry_or_null(&mm->free_list[order],
243 struct i915_buddy_block,
246 pr_err("root mismatch at order=%u\n", order);
254 total += i915_buddy_block_size(mm, root);
258 if (total != mm->size) {
259 pr_err("expected mm size=%llx, found=%llx\n", mm->size,
267 pr_err("prev root(%u), dump:\n", i - 1);
268 igt_dump_block(mm, prev);
272 pr_err("bad root(%u), dump:\n", i);
273 igt_dump_block(mm, root);
279 static void igt_mm_config(u64 *size, u64 *chunk_size)
281 I915_RND_STATE(prng);
284 /* Nothing fancy, just try to get an interesting bit pattern */
286 prandom_seed_state(&prng, i915_selftest.random_seed);
288 /* Let size be a random number of pages up to 8 GB (2M pages) */
289 s = 1 + i915_prandom_u32_max_state((BIT(33 - 12)) - 1, &prng);
290 /* Let the chunk size be a random power of 2 less than size */
291 ms = BIT(i915_prandom_u32_max_state(ilog2(s), &prng));
292 /* Round size down to the chunk size */
295 /* Convert from pages to bytes */
296 *chunk_size = (u64)ms << 12;
297 *size = (u64)s << 12;
300 static int igt_buddy_alloc_smoke(void *arg)
302 struct i915_buddy_mm mm;
303 IGT_TIMEOUT(end_time);
304 I915_RND_STATE(prng);
310 igt_mm_config(&mm_size, &chunk_size);
312 pr_info("buddy_init with size=%llx, chunk_size=%llx\n", mm_size, chunk_size);
314 err = i915_buddy_init(&mm, mm_size, chunk_size);
316 pr_err("buddy_init failed(%d)\n", err);
320 order = i915_random_order(mm.max_order + 1, &prng);
324 for (i = 0; i <= mm.max_order; ++i) {
325 struct i915_buddy_block *block;
326 int max_order = order[i];
327 bool timeout = false;
332 err = igt_check_mm(&mm);
334 pr_err("pre-mm check failed, abort\n");
338 pr_info("filling from max_order=%u\n", max_order);
345 block = i915_buddy_alloc(&mm, order);
347 err = PTR_ERR(block);
348 if (err == -ENOMEM) {
349 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
357 pr_err("buddy_alloc with order=%d failed(%d)\n",
364 list_add_tail(&block->link, &blocks);
366 if (i915_buddy_block_order(block) != order) {
367 pr_err("buddy_alloc order mismatch\n");
372 total += i915_buddy_block_size(&mm, block);
374 if (__igt_timeout(end_time, NULL)) {
378 } while (total < mm.size);
381 err = igt_check_blocks(&mm, &blocks, total, false);
383 i915_buddy_free_list(&mm, &blocks);
386 err = igt_check_mm(&mm);
388 pr_err("post-mm check failed\n");
402 i915_buddy_fini(&mm);
407 static int igt_buddy_alloc_pessimistic(void *arg)
409 const unsigned int max_order = 16;
410 struct i915_buddy_block *block, *bn;
411 struct i915_buddy_mm mm;
417 * Create a pot-sized mm, then allocate one of each possible
418 * order within. This should leave the mm with exactly one
422 err = i915_buddy_init(&mm, PAGE_SIZE << max_order, PAGE_SIZE);
424 pr_err("buddy_init failed(%d)\n", err);
427 GEM_BUG_ON(mm.max_order != max_order);
429 for (order = 0; order < max_order; order++) {
430 block = i915_buddy_alloc(&mm, order);
432 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
434 err = PTR_ERR(block);
438 list_add_tail(&block->link, &blocks);
441 /* And now the last remaining block available */
442 block = i915_buddy_alloc(&mm, 0);
444 pr_info("buddy_alloc hit -ENOMEM on final alloc\n");
445 err = PTR_ERR(block);
448 list_add_tail(&block->link, &blocks);
450 /* Should be completely full! */
451 for (order = max_order; order--; ) {
452 block = i915_buddy_alloc(&mm, order);
453 if (!IS_ERR(block)) {
454 pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
456 list_add_tail(&block->link, &blocks);
462 block = list_last_entry(&blocks, typeof(*block), link);
463 list_del(&block->link);
464 i915_buddy_free(&mm, block);
466 /* As we free in increasing size, we make available larger blocks */
468 list_for_each_entry_safe(block, bn, &blocks, link) {
469 list_del(&block->link);
470 i915_buddy_free(&mm, block);
472 block = i915_buddy_alloc(&mm, order);
474 pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
476 err = PTR_ERR(block);
479 i915_buddy_free(&mm, block);
483 /* To confirm, now the whole mm should be available */
484 block = i915_buddy_alloc(&mm, max_order);
486 pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
488 err = PTR_ERR(block);
491 i915_buddy_free(&mm, block);
494 i915_buddy_free_list(&mm, &blocks);
495 i915_buddy_fini(&mm);
499 static int igt_buddy_alloc_optimistic(void *arg)
501 const int max_order = 16;
502 struct i915_buddy_block *block;
503 struct i915_buddy_mm mm;
509 * Create a mm with one block of each order available, and
510 * try to allocate them all.
513 err = i915_buddy_init(&mm,
514 PAGE_SIZE * ((1 << (max_order + 1)) - 1),
517 pr_err("buddy_init failed(%d)\n", err);
520 GEM_BUG_ON(mm.max_order != max_order);
522 for (order = 0; order <= max_order; order++) {
523 block = i915_buddy_alloc(&mm, order);
525 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
527 err = PTR_ERR(block);
531 list_add_tail(&block->link, &blocks);
534 /* Should be completely full! */
535 block = i915_buddy_alloc(&mm, 0);
536 if (!IS_ERR(block)) {
537 pr_info("buddy_alloc unexpectedly succeeded, it should be full!");
538 list_add_tail(&block->link, &blocks);
544 i915_buddy_free_list(&mm, &blocks);
545 i915_buddy_fini(&mm);
549 static int igt_buddy_alloc_pathological(void *arg)
551 const int max_order = 16;
552 struct i915_buddy_block *block;
553 struct i915_buddy_mm mm;
560 * Create a pot-sized mm, then allocate one of each possible
561 * order within. This should leave the mm with exactly one
562 * page left. Free the largest block, then whittle down again.
563 * Eventually we will have a fully 50% fragmented mm.
566 err = i915_buddy_init(&mm, PAGE_SIZE << max_order, PAGE_SIZE);
568 pr_err("buddy_init failed(%d)\n", err);
571 GEM_BUG_ON(mm.max_order != max_order);
573 for (top = max_order; top; top--) {
574 /* Make room by freeing the largest allocated block */
575 block = list_first_entry_or_null(&blocks, typeof(*block), link);
577 list_del(&block->link);
578 i915_buddy_free(&mm, block);
581 for (order = top; order--; ) {
582 block = i915_buddy_alloc(&mm, order);
584 pr_info("buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
586 err = PTR_ERR(block);
589 list_add_tail(&block->link, &blocks);
592 /* There should be one final page for this sub-allocation */
593 block = i915_buddy_alloc(&mm, 0);
595 pr_info("buddy_alloc hit -ENOMEM for hole\n");
596 err = PTR_ERR(block);
599 list_add_tail(&block->link, &holes);
601 block = i915_buddy_alloc(&mm, top);
602 if (!IS_ERR(block)) {
603 pr_info("buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",
605 list_add_tail(&block->link, &blocks);
611 i915_buddy_free_list(&mm, &holes);
613 /* Nothing larger than blocks of chunk_size now available */
614 for (order = 1; order <= max_order; order++) {
615 block = i915_buddy_alloc(&mm, order);
616 if (!IS_ERR(block)) {
617 pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
619 list_add_tail(&block->link, &blocks);
626 list_splice_tail(&holes, &blocks);
627 i915_buddy_free_list(&mm, &blocks);
628 i915_buddy_fini(&mm);
632 static int igt_buddy_alloc_range(void *arg)
634 struct i915_buddy_mm mm;
635 unsigned long page_num;
643 igt_mm_config(&size, &chunk_size);
645 pr_info("buddy_init with size=%llx, chunk_size=%llx\n", size, chunk_size);
647 err = i915_buddy_init(&mm, size, chunk_size);
649 pr_err("buddy_init failed(%d)\n", err);
653 err = igt_check_mm(&mm);
655 pr_err("pre-mm check failed, abort, abort, abort!\n");
662 for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
663 struct i915_buddy_block *block;
666 size = min(page_num * mm.chunk_size, rem);
668 err = i915_buddy_alloc_range(&mm, &tmp, offset, size);
670 if (err == -ENOMEM) {
671 pr_info("alloc_range hit -ENOMEM with size=%llx\n",
674 pr_err("alloc_range with offset=%llx, size=%llx failed(%d)\n",
681 block = list_first_entry_or_null(&tmp,
682 struct i915_buddy_block,
685 pr_err("alloc_range has no blocks\n");
690 if (i915_buddy_block_offset(block) != offset) {
691 pr_err("alloc_range start offset mismatch, found=%llx, expected=%llx\n",
692 i915_buddy_block_offset(block), offset);
697 err = igt_check_blocks(&mm, &tmp, size, true);
699 list_splice_tail(&tmp, &blocks);
716 i915_buddy_free_list(&mm, &blocks);
719 err = igt_check_mm(&mm);
721 pr_err("post-mm check failed\n");
725 i915_buddy_fini(&mm);
730 int i915_buddy_mock_selftests(void)
732 static const struct i915_subtest tests[] = {
733 SUBTEST(igt_buddy_alloc_pessimistic),
734 SUBTEST(igt_buddy_alloc_optimistic),
735 SUBTEST(igt_buddy_alloc_pathological),
736 SUBTEST(igt_buddy_alloc_smoke),
737 SUBTEST(igt_buddy_alloc_range),
740 return i915_subtests(tests, NULL);