Merge tag 'io_uring-5.11-2021-01-16' of git://git.kernel.dk/linux-block
[linux/fpc-iii.git] / drivers / gpu / drm / i915 / selftests / i915_buddy.c
blob632b912b0bc9b870d0bb7796e18589003a73712c
1 // SPDX-License-Identifier: MIT
2 /*
3 * Copyright © 2019 Intel Corporation
4 */
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,
13 bool buddy)
15 pr_err("block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%s buddy=%s\n",
16 block->header,
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),
22 yesno(buddy));
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);
33 if (buddy)
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;
42 u64 block_size;
43 u64 offset;
44 int err = 0;
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");
52 err = -EINVAL;
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");
60 err = -EINVAL;
63 if (!is_power_of_2(block_size)) {
64 pr_err("block size not power of two\n");
65 err = -EINVAL;
68 if (!IS_ALIGNED(block_size, mm->chunk_size)) {
69 pr_err("block size not aligned to min size\n");
70 err = -EINVAL;
73 if (!IS_ALIGNED(offset, mm->chunk_size)) {
74 pr_err("block offset not aligned to min size\n");
75 err = -EINVAL;
78 if (!IS_ALIGNED(offset, block_size)) {
79 pr_err("block offset not aligned to block size\n");
80 err = -EINVAL;
83 buddy = get_buddy(block);
85 if (!buddy && block->parent) {
86 pr_err("buddy has gone fishing\n");
87 err = -EINVAL;
90 if (buddy) {
91 if (i915_buddy_block_offset(buddy) != (offset ^ block_size)) {
92 pr_err("buddy has wrong offset\n");
93 err = -EINVAL;
96 if (i915_buddy_block_size(mm, buddy) != block_size) {
97 pr_err("buddy size mismatch\n");
98 err = -EINVAL;
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");
104 err = -EINVAL;
108 return err;
111 static int igt_check_blocks(struct i915_buddy_mm *mm,
112 struct list_head *blocks,
113 u64 expected_size,
114 bool is_contiguous)
116 struct i915_buddy_block *block;
117 struct i915_buddy_block *prev;
118 u64 total;
119 int err = 0;
121 block = NULL;
122 prev = NULL;
123 total = 0;
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"),
130 err = -EINVAL;
133 if (is_contiguous && prev) {
134 u64 prev_block_size;
135 u64 prev_offset;
136 u64 offset;
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");
144 err = -EINVAL;
148 if (err)
149 break;
151 total += i915_buddy_block_size(mm, block);
152 prev = block;
155 if (!err) {
156 if (total != expected_size) {
157 pr_err("size mismatch, expected=%llx, found=%llx\n",
158 expected_size, total);
159 err = -EINVAL;
161 return err;
164 if (prev) {
165 pr_err("prev block, dump:\n");
166 igt_dump_block(mm, prev);
169 if (block) {
170 pr_err("bad block, dump:\n");
171 igt_dump_block(mm, block);
174 return err;
177 static int igt_check_mm(struct i915_buddy_mm *mm)
179 struct i915_buddy_block *root;
180 struct i915_buddy_block *prev;
181 unsigned int i;
182 u64 total;
183 int err = 0;
185 if (!mm->n_roots) {
186 pr_err("n_roots is zero\n");
187 return -EINVAL;
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));
193 return -EINVAL;
196 root = NULL;
197 prev = NULL;
198 total = 0;
200 for (i = 0; i < mm->n_roots; ++i) {
201 struct i915_buddy_block *block;
202 unsigned int order;
204 root = mm->roots[i];
205 if (!root) {
206 pr_err("root(%u) is NULL\n", i);
207 err = -EINVAL;
208 break;
211 err = igt_check_block(mm, root);
213 if (!i915_buddy_block_is_free(root)) {
214 pr_err("root not free\n");
215 err = -EINVAL;
218 order = i915_buddy_block_order(root);
220 if (!i) {
221 if (order != mm->max_order) {
222 pr_err("max order root missing\n");
223 err = -EINVAL;
227 if (prev) {
228 u64 prev_block_size;
229 u64 prev_offset;
230 u64 offset;
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");
238 err = -EINVAL;
242 block = list_first_entry_or_null(&mm->free_list[order],
243 struct i915_buddy_block,
244 link);
245 if (block != root) {
246 pr_err("root mismatch at order=%u\n", order);
247 err = -EINVAL;
250 if (err)
251 break;
253 prev = root;
254 total += i915_buddy_block_size(mm, root);
257 if (!err) {
258 if (total != mm->size) {
259 pr_err("expected mm size=%llx, found=%llx\n", mm->size,
260 total);
261 err = -EINVAL;
263 return err;
266 if (prev) {
267 pr_err("prev root(%u), dump:\n", i - 1);
268 igt_dump_block(mm, prev);
271 if (root) {
272 pr_err("bad root(%u), dump:\n", i);
273 igt_dump_block(mm, root);
276 return err;
279 static void igt_mm_config(u64 *size, u64 *chunk_size)
281 I915_RND_STATE(prng);
282 u32 s, ms;
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 */
293 s &= -ms;
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);
305 u64 chunk_size;
306 u64 mm_size;
307 int *order;
308 int err, i;
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);
315 if (err) {
316 pr_err("buddy_init failed(%d)\n", err);
317 return err;
320 order = i915_random_order(mm.max_order + 1, &prng);
321 if (!order)
322 goto out_fini;
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;
328 LIST_HEAD(blocks);
329 int order;
330 u64 total;
332 err = igt_check_mm(&mm);
333 if (err) {
334 pr_err("pre-mm check failed, abort\n");
335 break;
338 pr_info("filling from max_order=%u\n", max_order);
340 order = max_order;
341 total = 0;
343 do {
344 retry:
345 block = i915_buddy_alloc(&mm, order);
346 if (IS_ERR(block)) {
347 err = PTR_ERR(block);
348 if (err == -ENOMEM) {
349 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
350 order);
351 } else {
352 if (order--) {
353 err = 0;
354 goto retry;
357 pr_err("buddy_alloc with order=%d failed(%d)\n",
358 order, err);
361 break;
364 list_add_tail(&block->link, &blocks);
366 if (i915_buddy_block_order(block) != order) {
367 pr_err("buddy_alloc order mismatch\n");
368 err = -EINVAL;
369 break;
372 total += i915_buddy_block_size(&mm, block);
374 if (__igt_timeout(end_time, NULL)) {
375 timeout = true;
376 break;
378 } while (total < mm.size);
380 if (!err)
381 err = igt_check_blocks(&mm, &blocks, total, false);
383 i915_buddy_free_list(&mm, &blocks);
385 if (!err) {
386 err = igt_check_mm(&mm);
387 if (err)
388 pr_err("post-mm check failed\n");
391 if (err || timeout)
392 break;
394 cond_resched();
397 if (err == -ENOMEM)
398 err = 0;
400 kfree(order);
401 out_fini:
402 i915_buddy_fini(&mm);
404 return err;
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;
412 unsigned int order;
413 LIST_HEAD(blocks);
414 int err;
417 * Create a pot-sized mm, then allocate one of each possible
418 * order within. This should leave the mm with exactly one
419 * page left.
422 err = i915_buddy_init(&mm, PAGE_SIZE << max_order, PAGE_SIZE);
423 if (err) {
424 pr_err("buddy_init failed(%d)\n", err);
425 return 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);
431 if (IS_ERR(block)) {
432 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
433 order);
434 err = PTR_ERR(block);
435 goto err;
438 list_add_tail(&block->link, &blocks);
441 /* And now the last remaining block available */
442 block = i915_buddy_alloc(&mm, 0);
443 if (IS_ERR(block)) {
444 pr_info("buddy_alloc hit -ENOMEM on final alloc\n");
445 err = PTR_ERR(block);
446 goto err;
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!",
455 order);
456 list_add_tail(&block->link, &blocks);
457 err = -EINVAL;
458 goto err;
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 */
467 order = 1;
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);
473 if (IS_ERR(block)) {
474 pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
475 order);
476 err = PTR_ERR(block);
477 goto err;
479 i915_buddy_free(&mm, block);
480 order++;
483 /* To confirm, now the whole mm should be available */
484 block = i915_buddy_alloc(&mm, max_order);
485 if (IS_ERR(block)) {
486 pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
487 max_order);
488 err = PTR_ERR(block);
489 goto err;
491 i915_buddy_free(&mm, block);
493 err:
494 i915_buddy_free_list(&mm, &blocks);
495 i915_buddy_fini(&mm);
496 return err;
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;
504 LIST_HEAD(blocks);
505 int order;
506 int err;
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),
515 PAGE_SIZE);
516 if (err) {
517 pr_err("buddy_init failed(%d)\n", err);
518 return 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);
524 if (IS_ERR(block)) {
525 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
526 order);
527 err = PTR_ERR(block);
528 goto err;
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);
539 err = -EINVAL;
540 goto err;
543 err:
544 i915_buddy_free_list(&mm, &blocks);
545 i915_buddy_fini(&mm);
546 return err;
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;
554 LIST_HEAD(blocks);
555 LIST_HEAD(holes);
556 int order, top;
557 int err;
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);
567 if (err) {
568 pr_err("buddy_init failed(%d)\n", err);
569 return 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);
576 if (block) {
577 list_del(&block->link);
578 i915_buddy_free(&mm, block);
581 for (order = top; order--; ) {
582 block = i915_buddy_alloc(&mm, order);
583 if (IS_ERR(block)) {
584 pr_info("buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
585 order, top);
586 err = PTR_ERR(block);
587 goto err;
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);
594 if (IS_ERR(block)) {
595 pr_info("buddy_alloc hit -ENOMEM for hole\n");
596 err = PTR_ERR(block);
597 goto err;
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!",
604 top, max_order);
605 list_add_tail(&block->link, &blocks);
606 err = -EINVAL;
607 goto err;
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!",
618 order);
619 list_add_tail(&block->link, &blocks);
620 err = -EINVAL;
621 goto err;
625 err:
626 list_splice_tail(&holes, &blocks);
627 i915_buddy_free_list(&mm, &blocks);
628 i915_buddy_fini(&mm);
629 return err;
632 static int igt_buddy_alloc_range(void *arg)
634 struct i915_buddy_mm mm;
635 unsigned long page_num;
636 LIST_HEAD(blocks);
637 u64 chunk_size;
638 u64 offset;
639 u64 size;
640 u64 rem;
641 int err;
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);
648 if (err) {
649 pr_err("buddy_init failed(%d)\n", err);
650 return err;
653 err = igt_check_mm(&mm);
654 if (err) {
655 pr_err("pre-mm check failed, abort, abort, abort!\n");
656 goto err_fini;
659 rem = mm.size;
660 offset = 0;
662 for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
663 struct i915_buddy_block *block;
664 LIST_HEAD(tmp);
666 size = min(page_num * mm.chunk_size, rem);
668 err = i915_buddy_alloc_range(&mm, &tmp, offset, size);
669 if (err) {
670 if (err == -ENOMEM) {
671 pr_info("alloc_range hit -ENOMEM with size=%llx\n",
672 size);
673 } else {
674 pr_err("alloc_range with offset=%llx, size=%llx failed(%d)\n",
675 offset, size, err);
678 break;
681 block = list_first_entry_or_null(&tmp,
682 struct i915_buddy_block,
683 link);
684 if (!block) {
685 pr_err("alloc_range has no blocks\n");
686 err = -EINVAL;
687 break;
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);
693 err = -EINVAL;
696 if (!err)
697 err = igt_check_blocks(&mm, &tmp, size, true);
699 list_splice_tail(&tmp, &blocks);
701 if (err)
702 break;
704 offset += size;
706 rem -= size;
707 if (!rem)
708 break;
710 cond_resched();
713 if (err == -ENOMEM)
714 err = 0;
716 i915_buddy_free_list(&mm, &blocks);
718 if (!err) {
719 err = igt_check_mm(&mm);
720 if (err)
721 pr_err("post-mm check failed\n");
724 err_fini:
725 i915_buddy_fini(&mm);
727 return err;
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);