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
__igt_dump_block(struct i915_buddy_mm * mm,struct i915_buddy_block * block,bool buddy)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
igt_dump_block(struct i915_buddy_mm * mm,struct i915_buddy_block * block)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
igt_check_block(struct i915_buddy_mm * mm,struct i915_buddy_block * block)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
igt_check_blocks(struct i915_buddy_mm * mm,struct list_head * blocks,u64 expected_size,bool is_contiguous)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
igt_check_mm(struct i915_buddy_mm * mm)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
igt_mm_config(u64 * size,u64 * chunk_size)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
igt_buddy_alloc_smoke(void * arg)298 static int igt_buddy_alloc_smoke(void *arg)
299 {
300 struct i915_buddy_mm mm;
301 int max_order;
302 u64 chunk_size;
303 u64 mm_size;
304 int err;
305
306 igt_mm_config(&mm_size, &chunk_size);
307
308 pr_info("buddy_init with size=%llx, chunk_size=%llx\n", mm_size, chunk_size);
309
310 err = i915_buddy_init(&mm, mm_size, chunk_size);
311 if (err) {
312 pr_err("buddy_init failed(%d)\n", err);
313 return err;
314 }
315
316 for (max_order = mm.max_order; max_order >= 0; max_order--) {
317 struct i915_buddy_block *block;
318 int order;
319 LIST_HEAD(blocks);
320 u64 total;
321
322 err = igt_check_mm(&mm);
323 if (err) {
324 pr_err("pre-mm check failed, abort\n");
325 break;
326 }
327
328 pr_info("filling from max_order=%u\n", max_order);
329
330 order = max_order;
331 total = 0;
332
333 do {
334 retry:
335 block = i915_buddy_alloc(&mm, order);
336 if (IS_ERR(block)) {
337 err = PTR_ERR(block);
338 if (err == -ENOMEM) {
339 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
340 order);
341 } else {
342 if (order--) {
343 err = 0;
344 goto retry;
345 }
346
347 pr_err("buddy_alloc with order=%d failed(%d)\n",
348 order, err);
349 }
350
351 break;
352 }
353
354 list_add_tail(&block->link, &blocks);
355
356 if (i915_buddy_block_order(block) != order) {
357 pr_err("buddy_alloc order mismatch\n");
358 err = -EINVAL;
359 break;
360 }
361
362 total += i915_buddy_block_size(&mm, block);
363 } while (total < mm.size);
364
365 if (!err)
366 err = igt_check_blocks(&mm, &blocks, total, false);
367
368 i915_buddy_free_list(&mm, &blocks);
369
370 if (!err) {
371 err = igt_check_mm(&mm);
372 if (err)
373 pr_err("post-mm check failed\n");
374 }
375
376 if (err)
377 break;
378 }
379
380 if (err == -ENOMEM)
381 err = 0;
382
383 i915_buddy_fini(&mm);
384
385 return err;
386 }
387
igt_buddy_alloc_pessimistic(void * arg)388 static int igt_buddy_alloc_pessimistic(void *arg)
389 {
390 const unsigned int max_order = 16;
391 struct i915_buddy_block *block, *bn;
392 struct i915_buddy_mm mm;
393 unsigned int order;
394 LIST_HEAD(blocks);
395 int err;
396
397 /*
398 * Create a pot-sized mm, then allocate one of each possible
399 * order within. This should leave the mm with exactly one
400 * page left.
401 */
402
403 err = i915_buddy_init(&mm, PAGE_SIZE << max_order, PAGE_SIZE);
404 if (err) {
405 pr_err("buddy_init failed(%d)\n", err);
406 return err;
407 }
408 GEM_BUG_ON(mm.max_order != max_order);
409
410 for (order = 0; order < max_order; order++) {
411 block = i915_buddy_alloc(&mm, order);
412 if (IS_ERR(block)) {
413 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
414 order);
415 err = PTR_ERR(block);
416 goto err;
417 }
418
419 list_add_tail(&block->link, &blocks);
420 }
421
422 /* And now the last remaining block available */
423 block = i915_buddy_alloc(&mm, 0);
424 if (IS_ERR(block)) {
425 pr_info("buddy_alloc hit -ENOMEM on final alloc\n");
426 err = PTR_ERR(block);
427 goto err;
428 }
429 list_add_tail(&block->link, &blocks);
430
431 /* Should be completely full! */
432 for (order = max_order; order--; ) {
433 block = i915_buddy_alloc(&mm, order);
434 if (!IS_ERR(block)) {
435 pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
436 order);
437 list_add_tail(&block->link, &blocks);
438 err = -EINVAL;
439 goto err;
440 }
441 }
442
443 block = list_last_entry(&blocks, typeof(*block), link);
444 list_del(&block->link);
445 i915_buddy_free(&mm, block);
446
447 /* As we free in increasing size, we make available larger blocks */
448 order = 1;
449 list_for_each_entry_safe(block, bn, &blocks, link) {
450 list_del(&block->link);
451 i915_buddy_free(&mm, block);
452
453 block = i915_buddy_alloc(&mm, order);
454 if (IS_ERR(block)) {
455 pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
456 order);
457 err = PTR_ERR(block);
458 goto err;
459 }
460 i915_buddy_free(&mm, block);
461 order++;
462 }
463
464 /* To confirm, now the whole mm should be available */
465 block = i915_buddy_alloc(&mm, max_order);
466 if (IS_ERR(block)) {
467 pr_info("buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
468 max_order);
469 err = PTR_ERR(block);
470 goto err;
471 }
472 i915_buddy_free(&mm, block);
473
474 err:
475 i915_buddy_free_list(&mm, &blocks);
476 i915_buddy_fini(&mm);
477 return err;
478 }
479
igt_buddy_alloc_optimistic(void * arg)480 static int igt_buddy_alloc_optimistic(void *arg)
481 {
482 const int max_order = 16;
483 struct i915_buddy_block *block;
484 struct i915_buddy_mm mm;
485 LIST_HEAD(blocks);
486 int order;
487 int err;
488
489 /*
490 * Create a mm with one block of each order available, and
491 * try to allocate them all.
492 */
493
494 err = i915_buddy_init(&mm,
495 PAGE_SIZE * ((1 << (max_order + 1)) - 1),
496 PAGE_SIZE);
497 if (err) {
498 pr_err("buddy_init failed(%d)\n", err);
499 return err;
500 }
501 GEM_BUG_ON(mm.max_order != max_order);
502
503 for (order = 0; order <= max_order; order++) {
504 block = i915_buddy_alloc(&mm, order);
505 if (IS_ERR(block)) {
506 pr_info("buddy_alloc hit -ENOMEM with order=%d\n",
507 order);
508 err = PTR_ERR(block);
509 goto err;
510 }
511
512 list_add_tail(&block->link, &blocks);
513 }
514
515 /* Should be completely full! */
516 block = i915_buddy_alloc(&mm, 0);
517 if (!IS_ERR(block)) {
518 pr_info("buddy_alloc unexpectedly succeeded, it should be full!");
519 list_add_tail(&block->link, &blocks);
520 err = -EINVAL;
521 goto err;
522 }
523
524 err:
525 i915_buddy_free_list(&mm, &blocks);
526 i915_buddy_fini(&mm);
527 return err;
528 }
529
igt_buddy_alloc_pathological(void * arg)530 static int igt_buddy_alloc_pathological(void *arg)
531 {
532 const int max_order = 16;
533 struct i915_buddy_block *block;
534 struct i915_buddy_mm mm;
535 LIST_HEAD(blocks);
536 LIST_HEAD(holes);
537 int order, top;
538 int err;
539
540 /*
541 * Create a pot-sized mm, then allocate one of each possible
542 * order within. This should leave the mm with exactly one
543 * page left. Free the largest block, then whittle down again.
544 * Eventually we will have a fully 50% fragmented mm.
545 */
546
547 err = i915_buddy_init(&mm, PAGE_SIZE << max_order, PAGE_SIZE);
548 if (err) {
549 pr_err("buddy_init failed(%d)\n", err);
550 return err;
551 }
552 GEM_BUG_ON(mm.max_order != max_order);
553
554 for (top = max_order; top; top--) {
555 /* Make room by freeing the largest allocated block */
556 block = list_first_entry_or_null(&blocks, typeof(*block), link);
557 if (block) {
558 list_del(&block->link);
559 i915_buddy_free(&mm, block);
560 }
561
562 for (order = top; order--; ) {
563 block = i915_buddy_alloc(&mm, order);
564 if (IS_ERR(block)) {
565 pr_info("buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
566 order, top);
567 err = PTR_ERR(block);
568 goto err;
569 }
570 list_add_tail(&block->link, &blocks);
571 }
572
573 /* There should be one final page for this sub-allocation */
574 block = i915_buddy_alloc(&mm, 0);
575 if (IS_ERR(block)) {
576 pr_info("buddy_alloc hit -ENOMEM for hole\n");
577 err = PTR_ERR(block);
578 goto err;
579 }
580 list_add_tail(&block->link, &holes);
581
582 block = i915_buddy_alloc(&mm, top);
583 if (!IS_ERR(block)) {
584 pr_info("buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",
585 top, max_order);
586 list_add_tail(&block->link, &blocks);
587 err = -EINVAL;
588 goto err;
589 }
590 }
591
592 i915_buddy_free_list(&mm, &holes);
593
594 /* Nothing larger than blocks of chunk_size now available */
595 for (order = 1; order <= max_order; order++) {
596 block = i915_buddy_alloc(&mm, order);
597 if (!IS_ERR(block)) {
598 pr_info("buddy_alloc unexpectedly succeeded at order %d, it should be full!",
599 order);
600 list_add_tail(&block->link, &blocks);
601 err = -EINVAL;
602 goto err;
603 }
604 }
605
606 err:
607 list_splice_tail(&holes, &blocks);
608 i915_buddy_free_list(&mm, &blocks);
609 i915_buddy_fini(&mm);
610 return err;
611 }
612
igt_buddy_alloc_range(void * arg)613 static int igt_buddy_alloc_range(void *arg)
614 {
615 struct i915_buddy_mm mm;
616 unsigned long page_num;
617 LIST_HEAD(blocks);
618 u64 chunk_size;
619 u64 offset;
620 u64 size;
621 u64 rem;
622 int err;
623
624 igt_mm_config(&size, &chunk_size);
625
626 pr_info("buddy_init with size=%llx, chunk_size=%llx\n", size, chunk_size);
627
628 err = i915_buddy_init(&mm, size, chunk_size);
629 if (err) {
630 pr_err("buddy_init failed(%d)\n", err);
631 return err;
632 }
633
634 err = igt_check_mm(&mm);
635 if (err) {
636 pr_err("pre-mm check failed, abort, abort, abort!\n");
637 goto err_fini;
638 }
639
640 rem = mm.size;
641 offset = 0;
642
643 for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
644 struct i915_buddy_block *block;
645 LIST_HEAD(tmp);
646
647 size = min(page_num * mm.chunk_size, rem);
648
649 err = i915_buddy_alloc_range(&mm, &tmp, offset, size);
650 if (err) {
651 if (err == -ENOMEM) {
652 pr_info("alloc_range hit -ENOMEM with size=%llx\n",
653 size);
654 } else {
655 pr_err("alloc_range with offset=%llx, size=%llx failed(%d)\n",
656 offset, size, err);
657 }
658
659 break;
660 }
661
662 block = list_first_entry_or_null(&tmp,
663 struct i915_buddy_block,
664 link);
665 if (!block) {
666 pr_err("alloc_range has no blocks\n");
667 err = -EINVAL;
668 break;
669 }
670
671 if (i915_buddy_block_offset(block) != offset) {
672 pr_err("alloc_range start offset mismatch, found=%llx, expected=%llx\n",
673 i915_buddy_block_offset(block), offset);
674 err = -EINVAL;
675 }
676
677 if (!err)
678 err = igt_check_blocks(&mm, &tmp, size, true);
679
680 list_splice_tail(&tmp, &blocks);
681
682 if (err)
683 break;
684
685 offset += size;
686
687 rem -= size;
688 if (!rem)
689 break;
690 }
691
692 if (err == -ENOMEM)
693 err = 0;
694
695 i915_buddy_free_list(&mm, &blocks);
696
697 if (!err) {
698 err = igt_check_mm(&mm);
699 if (err)
700 pr_err("post-mm check failed\n");
701 }
702
703 err_fini:
704 i915_buddy_fini(&mm);
705
706 return err;
707 }
708
i915_buddy_mock_selftests(void)709 int i915_buddy_mock_selftests(void)
710 {
711 static const struct i915_subtest tests[] = {
712 SUBTEST(igt_buddy_alloc_pessimistic),
713 SUBTEST(igt_buddy_alloc_optimistic),
714 SUBTEST(igt_buddy_alloc_pathological),
715 SUBTEST(igt_buddy_alloc_smoke),
716 SUBTEST(igt_buddy_alloc_range),
717 };
718
719 return i915_subtests(tests, NULL);
720 }
721
