Loading...
Note: File does not exist in v3.1.
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
11static void __igt_dump_block(struct i915_buddy_mm *mm,
12 struct i915_buddy_block *block,
13 bool buddy)
14{
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));
23}
24
25static void igt_dump_block(struct i915_buddy_mm *mm,
26 struct i915_buddy_block *block)
27{
28 struct i915_buddy_block *buddy;
29
30 __igt_dump_block(mm, block, false);
31
32 buddy = get_buddy(block);
33 if (buddy)
34 __igt_dump_block(mm, buddy, true);
35}
36
37static int igt_check_block(struct i915_buddy_mm *mm,
38 struct i915_buddy_block *block)
39{
40 struct i915_buddy_block *buddy;
41 unsigned int block_state;
42 u64 block_size;
43 u64 offset;
44 int err = 0;
45
46 block_state = i915_buddy_block_state(block);
47
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;
53 }
54
55 block_size = i915_buddy_block_size(mm, block);
56 offset = i915_buddy_block_offset(block);
57
58 if (block_size < mm->chunk_size) {
59 pr_err("block size smaller than min size\n");
60 err = -EINVAL;
61 }
62
63 if (!is_power_of_2(block_size)) {
64 pr_err("block size not power of two\n");
65 err = -EINVAL;
66 }
67
68 if (!IS_ALIGNED(block_size, mm->chunk_size)) {
69 pr_err("block size not aligned to min size\n");
70 err = -EINVAL;
71 }
72
73 if (!IS_ALIGNED(offset, mm->chunk_size)) {
74 pr_err("block offset not aligned to min size\n");
75 err = -EINVAL;
76 }
77
78 if (!IS_ALIGNED(offset, block_size)) {
79 pr_err("block offset not aligned to block size\n");
80 err = -EINVAL;
81 }
82
83 buddy = get_buddy(block);
84
85 if (!buddy && block->parent) {
86 pr_err("buddy has gone fishing\n");
87 err = -EINVAL;
88 }
89
90 if (buddy) {
91 if (i915_buddy_block_offset(buddy) != (offset ^ block_size)) {
92 pr_err("buddy has wrong offset\n");
93 err = -EINVAL;
94 }
95
96 if (i915_buddy_block_size(mm, buddy) != block_size) {
97 pr_err("buddy size mismatch\n");
98 err = -EINVAL;
99 }
100
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;
105 }
106 }
107
108 return err;
109}
110
111static int igt_check_blocks(struct i915_buddy_mm *mm,
112 struct list_head *blocks,
113 u64 expected_size,
114 bool is_contiguous)
115{
116 struct i915_buddy_block *block;
117 struct i915_buddy_block *prev;
118 u64 total;
119 int err = 0;
120
121 block = NULL;
122 prev = NULL;
123 total = 0;
124
125 list_for_each_entry(block, blocks, link) {
126 err = igt_check_block(mm, block);
127
128 if (!i915_buddy_block_is_allocated(block)) {
129 pr_err("block not allocated\n"),
130 err = -EINVAL;
131 }
132
133 if (is_contiguous && prev) {
134 u64 prev_block_size;
135 u64 prev_offset;
136 u64 offset;
137
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);
141
142 if (offset != (prev_offset + prev_block_size)) {
143 pr_err("block offset mismatch\n");
144 err = -EINVAL;
145 }
146 }
147
148 if (err)
149 break;
150
151 total += i915_buddy_block_size(mm, block);
152 prev = block;
153 }
154
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;
160 }
161 return err;
162 }
163
164 if (prev) {
165 pr_err("prev block, dump:\n");
166 igt_dump_block(mm, prev);
167 }
168
169 if (block) {
170 pr_err("bad block, dump:\n");
171 igt_dump_block(mm, block);
172 }
173
174 return err;
175}
176
177static int igt_check_mm(struct i915_buddy_mm *mm)
178{
179 struct i915_buddy_block *root;
180 struct i915_buddy_block *prev;
181 unsigned int i;
182 u64 total;
183 int err = 0;
184
185 if (!mm->n_roots) {
186 pr_err("n_roots is zero\n");
187 return -EINVAL;
188 }
189
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;
194 }
195
196 root = NULL;
197 prev = NULL;
198 total = 0;
199
200 for (i = 0; i < mm->n_roots; ++i) {
201 struct i915_buddy_block *block;
202 unsigned int order;
203
204 root = mm->roots[i];
205 if (!root) {
206 pr_err("root(%u) is NULL\n", i);
207 err = -EINVAL;
208 break;
209 }
210
211 err = igt_check_block(mm, root);
212
213 if (!i915_buddy_block_is_free(root)) {
214 pr_err("root not free\n");
215 err = -EINVAL;
216 }
217
218 order = i915_buddy_block_order(root);
219
220 if (!i) {
221 if (order != mm->max_order) {
222 pr_err("max order root missing\n");
223 err = -EINVAL;
224 }
225 }
226
227 if (prev) {
228 u64 prev_block_size;
229 u64 prev_offset;
230 u64 offset;
231
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);
235
236 if (offset != (prev_offset + prev_block_size)) {
237 pr_err("root offset mismatch\n");
238 err = -EINVAL;
239 }
240 }
241
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;
248 }
249
250 if (err)
251 break;
252
253 prev = root;
254 total += i915_buddy_block_size(mm, root);
255 }
256
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;
262 }
263 return err;
264 }
265
266 if (prev) {
267 pr_err("prev root(%u), dump:\n", i - 1);
268 igt_dump_block(mm, prev);
269 }
270
271 if (root) {
272 pr_err("bad root(%u), dump:\n", i);
273 igt_dump_block(mm, root);
274 }
275
276 return err;
277}
278
279static void igt_mm_config(u64 *size, u64 *chunk_size)
280{
281 I915_RND_STATE(prng);
282 u32 s, ms;
283
284 /* Nothing fancy, just try to get an interesting bit pattern */
285
286 prandom_seed_state(&prng, i915_selftest.random_seed);
287
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;
294
295 /* Convert from pages to bytes */
296 *chunk_size = (u64)ms << 12;
297 *size = (u64)s << 12;
298}
299
300static int igt_buddy_alloc_smoke(void *arg)
301{
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;
309
310 igt_mm_config(&mm_size, &chunk_size);
311
312 pr_info("buddy_init with size=%llx, chunk_size=%llx\n", mm_size, chunk_size);
313
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;
318 }
319
320 order = i915_random_order(mm.max_order + 1, &prng);
321 if (!order)
322 goto out_fini;
323
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;
331
332 err = igt_check_mm(&mm);
333 if (err) {
334 pr_err("pre-mm check failed, abort\n");
335 break;
336 }
337
338 pr_info("filling from max_order=%u\n", max_order);
339
340 order = max_order;
341 total = 0;
342
343 do {
344retry:
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;
355 }
356
357 pr_err("buddy_alloc with order=%d failed(%d)\n",
358 order, err);
359 }
360
361 break;
362 }
363
364 list_add_tail(&block->link, &blocks);
365
366 if (i915_buddy_block_order(block) != order) {
367 pr_err("buddy_alloc order mismatch\n");
368 err = -EINVAL;
369 break;
370 }
371
372 total += i915_buddy_block_size(&mm, block);
373
374 if (__igt_timeout(end_time, NULL)) {
375 timeout = true;
376 break;
377 }
378 } while (total < mm.size);
379
380 if (!err)
381 err = igt_check_blocks(&mm, &blocks, total, false);
382
383 i915_buddy_free_list(&mm, &blocks);
384
385 if (!err) {
386 err = igt_check_mm(&mm);
387 if (err)
388 pr_err("post-mm check failed\n");
389 }
390
391 if (err || timeout)
392 break;
393
394 cond_resched();
395 }
396
397 if (err == -ENOMEM)
398 err = 0;
399
400 kfree(order);
401out_fini:
402 i915_buddy_fini(&mm);
403
404 return err;
405}
406
407static int igt_buddy_alloc_pessimistic(void *arg)
408{
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;
415
416 /*
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.
420 */
421
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;
426 }
427 GEM_BUG_ON(mm.max_order != max_order);
428
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;
436 }
437
438 list_add_tail(&block->link, &blocks);
439 }
440
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;
447 }
448 list_add_tail(&block->link, &blocks);
449
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;
459 }
460 }
461
462 block = list_last_entry(&blocks, typeof(*block), link);
463 list_del(&block->link);
464 i915_buddy_free(&mm, block);
465
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);
471
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;
478 }
479 i915_buddy_free(&mm, block);
480 order++;
481 }
482
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;
490 }
491 i915_buddy_free(&mm, block);
492
493err:
494 i915_buddy_free_list(&mm, &blocks);
495 i915_buddy_fini(&mm);
496 return err;
497}
498
499static int igt_buddy_alloc_optimistic(void *arg)
500{
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;
507
508 /*
509 * Create a mm with one block of each order available, and
510 * try to allocate them all.
511 */
512
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;
519 }
520 GEM_BUG_ON(mm.max_order != max_order);
521
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;
529 }
530
531 list_add_tail(&block->link, &blocks);
532 }
533
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;
541 }
542
543err:
544 i915_buddy_free_list(&mm, &blocks);
545 i915_buddy_fini(&mm);
546 return err;
547}
548
549static int igt_buddy_alloc_pathological(void *arg)
550{
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;
558
559 /*
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.
564 */
565
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;
570 }
571 GEM_BUG_ON(mm.max_order != max_order);
572
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);
579 }
580
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;
588 }
589 list_add_tail(&block->link, &blocks);
590 }
591
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;
598 }
599 list_add_tail(&block->link, &holes);
600
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;
608 }
609 }
610
611 i915_buddy_free_list(&mm, &holes);
612
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;
622 }
623 }
624
625err:
626 list_splice_tail(&holes, &blocks);
627 i915_buddy_free_list(&mm, &blocks);
628 i915_buddy_fini(&mm);
629 return err;
630}
631
632static int igt_buddy_alloc_range(void *arg)
633{
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;
642
643 igt_mm_config(&size, &chunk_size);
644
645 pr_info("buddy_init with size=%llx, chunk_size=%llx\n", size, chunk_size);
646
647 err = i915_buddy_init(&mm, size, chunk_size);
648 if (err) {
649 pr_err("buddy_init failed(%d)\n", err);
650 return err;
651 }
652
653 err = igt_check_mm(&mm);
654 if (err) {
655 pr_err("pre-mm check failed, abort, abort, abort!\n");
656 goto err_fini;
657 }
658
659 rem = mm.size;
660 offset = 0;
661
662 for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
663 struct i915_buddy_block *block;
664 LIST_HEAD(tmp);
665
666 size = min(page_num * mm.chunk_size, rem);
667
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);
676 }
677
678 break;
679 }
680
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;
688 }
689
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;
694 }
695
696 if (!err)
697 err = igt_check_blocks(&mm, &tmp, size, true);
698
699 list_splice_tail(&tmp, &blocks);
700
701 if (err)
702 break;
703
704 offset += size;
705
706 rem -= size;
707 if (!rem)
708 break;
709
710 cond_resched();
711 }
712
713 if (err == -ENOMEM)
714 err = 0;
715
716 i915_buddy_free_list(&mm, &blocks);
717
718 if (!err) {
719 err = igt_check_mm(&mm);
720 if (err)
721 pr_err("post-mm check failed\n");
722 }
723
724err_fini:
725 i915_buddy_fini(&mm);
726
727 return err;
728}
729
730int i915_buddy_mock_selftests(void)
731{
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),
738 };
739
740 return i915_subtests(tests, NULL);
741}