Line data Source code
1 : // SPDX-License-Identifier: MIT
2 : /*
3 : * Copyright © 2019 Intel Corporation
4 : * 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 :
12 : #include <drm/drm_buddy.h>
13 :
14 : #include "../lib/drm_random.h"
15 :
16 : #define TIMEOUT(name__) \
17 : unsigned long name__ = jiffies + MAX_SCHEDULE_TIMEOUT
18 :
19 : static unsigned int random_seed;
20 :
21 : static inline u64 get_size(int order, u64 chunk_size)
22 : {
23 9770 : return (1 << order) * chunk_size;
24 : }
25 :
26 : __printf(2, 3)
27 9615 : static bool __timeout(unsigned long timeout, const char *fmt, ...)
28 : {
29 : va_list va;
30 :
31 9615 : if (!signal_pending(current)) {
32 9615 : cond_resched();
33 9615 : if (time_before(jiffies, timeout))
34 : return false;
35 : }
36 :
37 0 : if (fmt) {
38 0 : va_start(va, fmt);
39 0 : vprintk(fmt, va);
40 0 : va_end(va);
41 : }
42 :
43 : return true;
44 : }
45 :
46 0 : static void __dump_block(struct kunit *test, struct drm_buddy *mm,
47 : struct drm_buddy_block *block, bool buddy)
48 : {
49 0 : kunit_err(test, "block info: header=%llx, state=%u, order=%d, offset=%llx size=%llx root=%d buddy=%d\n",
50 : block->header, drm_buddy_block_state(block),
51 : drm_buddy_block_order(block), drm_buddy_block_offset(block),
52 : drm_buddy_block_size(mm, block), !block->parent, buddy);
53 0 : }
54 :
55 0 : static void dump_block(struct kunit *test, struct drm_buddy *mm,
56 : struct drm_buddy_block *block)
57 : {
58 : struct drm_buddy_block *buddy;
59 :
60 0 : __dump_block(test, mm, block, false);
61 :
62 0 : buddy = drm_get_buddy(block);
63 0 : if (buddy)
64 0 : __dump_block(test, mm, buddy, true);
65 0 : }
66 :
67 10135 : static int check_block(struct kunit *test, struct drm_buddy *mm,
68 : struct drm_buddy_block *block)
69 : {
70 : struct drm_buddy_block *buddy;
71 : unsigned int block_state;
72 : u64 block_size;
73 : u64 offset;
74 10135 : int err = 0;
75 :
76 20270 : block_state = drm_buddy_block_state(block);
77 :
78 20270 : if (block_state != DRM_BUDDY_ALLOCATED &&
79 10135 : block_state != DRM_BUDDY_FREE && block_state != DRM_BUDDY_SPLIT) {
80 0 : kunit_err(test, "block state mismatch\n");
81 0 : err = -EINVAL;
82 : }
83 :
84 20270 : block_size = drm_buddy_block_size(mm, block);
85 20270 : offset = drm_buddy_block_offset(block);
86 :
87 10135 : if (block_size < mm->chunk_size) {
88 0 : kunit_err(test, "block size smaller than min size\n");
89 0 : err = -EINVAL;
90 : }
91 :
92 10135 : if (!is_power_of_2(block_size)) {
93 0 : kunit_err(test, "block size not power of two\n");
94 0 : err = -EINVAL;
95 : }
96 :
97 10135 : if (!IS_ALIGNED(block_size, mm->chunk_size)) {
98 0 : kunit_err(test, "block size not aligned to min size\n");
99 0 : err = -EINVAL;
100 : }
101 :
102 10135 : if (!IS_ALIGNED(offset, mm->chunk_size)) {
103 0 : kunit_err(test, "block offset not aligned to min size\n");
104 0 : err = -EINVAL;
105 : }
106 :
107 10135 : if (!IS_ALIGNED(offset, block_size)) {
108 0 : kunit_err(test, "block offset not aligned to block size\n");
109 0 : err = -EINVAL;
110 : }
111 :
112 10135 : buddy = drm_get_buddy(block);
113 :
114 10135 : if (!buddy && block->parent) {
115 0 : kunit_err(test, "buddy has gone fishing\n");
116 0 : err = -EINVAL;
117 : }
118 :
119 10135 : if (buddy) {
120 19682 : if (drm_buddy_block_offset(buddy) != (offset ^ block_size)) {
121 0 : kunit_err(test, "buddy has wrong offset\n");
122 0 : err = -EINVAL;
123 : }
124 :
125 19682 : if (drm_buddy_block_size(mm, buddy) != block_size) {
126 0 : kunit_err(test, "buddy size mismatch\n");
127 0 : err = -EINVAL;
128 : }
129 :
130 19682 : if (drm_buddy_block_state(buddy) == block_state &&
131 : block_state == DRM_BUDDY_FREE) {
132 0 : kunit_err(test, "block and its buddy are free\n");
133 0 : err = -EINVAL;
134 : }
135 : }
136 :
137 10135 : return err;
138 : }
139 :
140 63 : static int check_blocks(struct kunit *test, struct drm_buddy *mm,
141 : struct list_head *blocks, u64 expected_size, bool is_contiguous)
142 : {
143 : struct drm_buddy_block *block;
144 : struct drm_buddy_block *prev;
145 : u64 total;
146 63 : int err = 0;
147 :
148 63 : block = NULL;
149 63 : prev = NULL;
150 63 : total = 0;
151 :
152 9974 : list_for_each_entry(block, blocks, link) {
153 9911 : err = check_block(test, mm, block);
154 :
155 9911 : if (!drm_buddy_block_is_allocated(block)) {
156 0 : kunit_err(test, "block not allocated\n");
157 0 : err = -EINVAL;
158 : }
159 :
160 9911 : if (is_contiguous && prev) {
161 : u64 prev_block_size;
162 : u64 prev_offset;
163 : u64 offset;
164 :
165 492 : prev_offset = drm_buddy_block_offset(prev);
166 492 : prev_block_size = drm_buddy_block_size(mm, prev);
167 492 : offset = drm_buddy_block_offset(block);
168 :
169 246 : if (offset != (prev_offset + prev_block_size)) {
170 0 : kunit_err(test, "block offset mismatch\n");
171 0 : err = -EINVAL;
172 : }
173 : }
174 :
175 9911 : if (err)
176 : break;
177 :
178 19822 : total += drm_buddy_block_size(mm, block);
179 9911 : prev = block;
180 : }
181 :
182 63 : if (!err) {
183 63 : if (total != expected_size) {
184 0 : kunit_err(test, "size mismatch, expected=%llx, found=%llx\n",
185 : expected_size, total);
186 0 : err = -EINVAL;
187 : }
188 : return err;
189 : }
190 :
191 0 : if (prev) {
192 0 : kunit_err(test, "prev block, dump:\n");
193 0 : dump_block(test, mm, prev);
194 : }
195 :
196 0 : kunit_err(test, "bad block, dump:\n");
197 0 : dump_block(test, mm, block);
198 :
199 0 : return err;
200 : }
201 :
202 28 : static int check_mm(struct kunit *test, struct drm_buddy *mm)
203 : {
204 : struct drm_buddy_block *root;
205 : struct drm_buddy_block *prev;
206 : unsigned int i;
207 : u64 total;
208 28 : int err = 0;
209 :
210 28 : if (!mm->n_roots) {
211 0 : kunit_err(test, "n_roots is zero\n");
212 0 : return -EINVAL;
213 : }
214 :
215 56 : if (mm->n_roots != hweight64(mm->size)) {
216 0 : kunit_err(test, "n_roots mismatch, n_roots=%u, expected=%lu\n",
217 : mm->n_roots, hweight64(mm->size));
218 0 : return -EINVAL;
219 : }
220 :
221 : root = NULL;
222 : prev = NULL;
223 : total = 0;
224 :
225 224 : for (i = 0; i < mm->n_roots; ++i) {
226 : struct drm_buddy_block *block;
227 : unsigned int order;
228 :
229 224 : root = mm->roots[i];
230 224 : if (!root) {
231 0 : kunit_err(test, "root(%u) is NULL\n", i);
232 0 : err = -EINVAL;
233 0 : break;
234 : }
235 :
236 224 : err = check_block(test, mm, root);
237 :
238 224 : if (!drm_buddy_block_is_free(root)) {
239 0 : kunit_err(test, "root not free\n");
240 0 : err = -EINVAL;
241 : }
242 :
243 448 : order = drm_buddy_block_order(root);
244 :
245 224 : if (!i) {
246 28 : if (order != mm->max_order) {
247 0 : kunit_err(test, "max order root missing\n");
248 0 : err = -EINVAL;
249 : }
250 : }
251 :
252 224 : if (prev) {
253 : u64 prev_block_size;
254 : u64 prev_offset;
255 : u64 offset;
256 :
257 392 : prev_offset = drm_buddy_block_offset(prev);
258 392 : prev_block_size = drm_buddy_block_size(mm, prev);
259 392 : offset = drm_buddy_block_offset(root);
260 :
261 196 : if (offset != (prev_offset + prev_block_size)) {
262 0 : kunit_err(test, "root offset mismatch\n");
263 0 : err = -EINVAL;
264 : }
265 : }
266 :
267 224 : block = list_first_entry_or_null(&mm->free_list[order],
268 : struct drm_buddy_block, link);
269 224 : if (block != root) {
270 0 : kunit_err(test, "root mismatch at order=%u\n", order);
271 0 : err = -EINVAL;
272 : }
273 :
274 224 : if (err)
275 : break;
276 :
277 224 : prev = root;
278 448 : total += drm_buddy_block_size(mm, root);
279 : }
280 :
281 28 : if (!err) {
282 28 : if (total != mm->size) {
283 0 : kunit_err(test, "expected mm size=%llx, found=%llx\n",
284 : mm->size, total);
285 0 : err = -EINVAL;
286 : }
287 : return err;
288 : }
289 :
290 0 : if (prev) {
291 0 : kunit_err(test, "prev root(%u), dump:\n", i - 1);
292 0 : dump_block(test, mm, prev);
293 : }
294 :
295 0 : if (root) {
296 0 : kunit_err(test, "bad root(%u), dump:\n", i);
297 0 : dump_block(test, mm, root);
298 : }
299 :
300 : return err;
301 : }
302 :
303 2 : static void mm_config(u64 *size, u64 *chunk_size)
304 : {
305 2 : DRM_RND_STATE(prng, random_seed);
306 : u32 s, ms;
307 :
308 : /* Nothing fancy, just try to get an interesting bit pattern */
309 :
310 2 : prandom_seed_state(&prng, random_seed);
311 :
312 : /* Let size be a random number of pages up to 8 GB (2M pages) */
313 2 : s = 1 + drm_prandom_u32_max_state((BIT(33 - 12)) - 1, &prng);
314 : /* Let the chunk size be a random power of 2 less than size */
315 4 : ms = BIT(drm_prandom_u32_max_state(ilog2(s), &prng));
316 : /* Round size down to the chunk size */
317 2 : s &= -ms;
318 :
319 : /* Convert from pages to bytes */
320 2 : *chunk_size = (u64)ms << 12;
321 2 : *size = (u64)s << 12;
322 2 : }
323 :
324 1 : static void drm_test_buddy_alloc_pathological(struct kunit *test)
325 : {
326 1 : u64 mm_size, size, start = 0;
327 : struct drm_buddy_block *block;
328 1 : const int max_order = 3;
329 1 : unsigned long flags = 0;
330 : int order, top;
331 : struct drm_buddy mm;
332 1 : LIST_HEAD(blocks);
333 1 : LIST_HEAD(holes);
334 1 : LIST_HEAD(tmp);
335 :
336 : /*
337 : * Create a pot-sized mm, then allocate one of each possible
338 : * order within. This should leave the mm with exactly one
339 : * page left. Free the largest block, then whittle down again.
340 : * Eventually we will have a fully 50% fragmented mm.
341 : */
342 :
343 1 : mm_size = PAGE_SIZE << max_order;
344 1 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE),
345 : "buddy_init failed\n");
346 :
347 1 : KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
348 :
349 3 : for (top = max_order; top; top--) {
350 : /* Make room by freeing the largest allocated block */
351 3 : block = list_first_entry_or_null(&blocks, typeof(*block), link);
352 3 : if (block) {
353 4 : list_del(&block->link);
354 2 : drm_buddy_free_block(&mm, block);
355 : }
356 :
357 9 : for (order = top; order--;) {
358 6 : size = get_size(order, PAGE_SIZE);
359 6 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start,
360 : mm_size, size, size,
361 : &tmp, flags),
362 : "buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
363 : order, top);
364 :
365 6 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
366 6 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
367 :
368 6 : list_move_tail(&block->link, &blocks);
369 : }
370 :
371 : /* There should be one final page for this sub-allocation */
372 3 : size = get_size(0, PAGE_SIZE);
373 3 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
374 : size, size, &tmp, flags),
375 : "buddy_alloc hit -ENOMEM for hole\n");
376 :
377 3 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
378 3 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
379 :
380 6 : list_move_tail(&block->link, &holes);
381 :
382 3 : size = get_size(top, PAGE_SIZE);
383 3 : KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
384 : size, size, &tmp, flags),
385 : "buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",
386 : top, max_order);
387 : }
388 :
389 1 : drm_buddy_free_list(&mm, &holes);
390 :
391 : /* Nothing larger than blocks of chunk_size now available */
392 4 : for (order = 1; order <= max_order; order++) {
393 3 : size = get_size(order, PAGE_SIZE);
394 3 : KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
395 : size, size, &tmp, flags),
396 : "buddy_alloc unexpectedly succeeded at order %d, it should be full!",
397 : order);
398 : }
399 :
400 1 : list_splice_tail(&holes, &blocks);
401 1 : drm_buddy_free_list(&mm, &blocks);
402 1 : drm_buddy_fini(&mm);
403 1 : }
404 :
405 1 : static void drm_test_buddy_alloc_smoke(struct kunit *test)
406 : {
407 1 : u64 mm_size, chunk_size, start = 0;
408 1 : unsigned long flags = 0;
409 : struct drm_buddy mm;
410 : int *order;
411 : int i;
412 :
413 1 : DRM_RND_STATE(prng, random_seed);
414 1 : TIMEOUT(end_time);
415 :
416 1 : mm_config(&mm_size, &chunk_size);
417 :
418 1 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, chunk_size),
419 : "buddy_init failed\n");
420 :
421 1 : order = drm_random_order(mm.max_order + 1, &prng);
422 1 : KUNIT_ASSERT_TRUE(test, order);
423 :
424 13 : for (i = 0; i <= mm.max_order; ++i) {
425 : struct drm_buddy_block *block;
426 13 : int max_order = order[i];
427 13 : bool timeout = false;
428 13 : LIST_HEAD(blocks);
429 : u64 total, size;
430 13 : LIST_HEAD(tmp);
431 : int order, err;
432 :
433 13 : KUNIT_ASSERT_FALSE_MSG(test, check_mm(test, &mm),
434 : "pre-mm check failed, abort\n");
435 :
436 : order = max_order;
437 : total = 0;
438 :
439 : do {
440 : retry:
441 19386 : size = get_size(order, chunk_size);
442 9693 : err = drm_buddy_alloc_blocks(&mm, start, mm_size, size, size, &tmp, flags);
443 9693 : if (err) {
444 78 : if (err == -ENOMEM) {
445 0 : KUNIT_FAIL(test, "buddy_alloc hit -ENOMEM with order=%d\n",
446 : order);
447 : } else {
448 78 : if (order--) {
449 : err = 0;
450 : goto retry;
451 : }
452 :
453 0 : KUNIT_FAIL(test, "buddy_alloc with order=%d failed\n",
454 : order);
455 : }
456 :
457 : break;
458 : }
459 :
460 9615 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
461 9615 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
462 :
463 19230 : list_move_tail(&block->link, &blocks);
464 19230 : KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_order(block), order,
465 : "buddy_alloc order mismatch\n");
466 :
467 19230 : total += drm_buddy_block_size(&mm, block);
468 :
469 9615 : if (__timeout(end_time, NULL)) {
470 : timeout = true;
471 : break;
472 : }
473 9615 : } while (total < mm.size);
474 :
475 13 : if (!err)
476 13 : err = check_blocks(test, &mm, &blocks, total, false);
477 :
478 13 : drm_buddy_free_list(&mm, &blocks);
479 :
480 13 : if (!err) {
481 13 : KUNIT_EXPECT_FALSE_MSG(test, check_mm(test, &mm),
482 : "post-mm check failed\n");
483 : }
484 :
485 13 : if (err || timeout)
486 : break;
487 :
488 13 : cond_resched();
489 : }
490 :
491 1 : kfree(order);
492 1 : drm_buddy_fini(&mm);
493 1 : }
494 :
495 1 : static void drm_test_buddy_alloc_pessimistic(struct kunit *test)
496 : {
497 1 : u64 mm_size, size, start = 0;
498 : struct drm_buddy_block *block, *bn;
499 1 : const unsigned int max_order = 16;
500 1 : unsigned long flags = 0;
501 : struct drm_buddy mm;
502 : unsigned int order;
503 1 : LIST_HEAD(blocks);
504 1 : LIST_HEAD(tmp);
505 :
506 : /*
507 : * Create a pot-sized mm, then allocate one of each possible
508 : * order within. This should leave the mm with exactly one
509 : * page left.
510 : */
511 :
512 1 : mm_size = PAGE_SIZE << max_order;
513 1 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE),
514 : "buddy_init failed\n");
515 :
516 1 : KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
517 :
518 16 : for (order = 0; order < max_order; order++) {
519 32 : size = get_size(order, PAGE_SIZE);
520 16 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
521 : size, size, &tmp, flags),
522 : "buddy_alloc hit -ENOMEM with order=%d\n",
523 : order);
524 :
525 16 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
526 16 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
527 :
528 32 : list_move_tail(&block->link, &blocks);
529 : }
530 :
531 : /* And now the last remaining block available */
532 1 : size = get_size(0, PAGE_SIZE);
533 1 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
534 : size, size, &tmp, flags),
535 : "buddy_alloc hit -ENOMEM on final alloc\n");
536 :
537 1 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
538 1 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
539 :
540 2 : list_move_tail(&block->link, &blocks);
541 :
542 : /* Should be completely full! */
543 18 : for (order = max_order; order--;) {
544 32 : size = get_size(order, PAGE_SIZE);
545 16 : KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
546 : size, size, &tmp, flags),
547 : "buddy_alloc unexpectedly succeeded, it should be full!");
548 : }
549 :
550 1 : block = list_last_entry(&blocks, typeof(*block), link);
551 2 : list_del(&block->link);
552 1 : drm_buddy_free_block(&mm, block);
553 :
554 : /* As we free in increasing size, we make available larger blocks */
555 1 : order = 1;
556 17 : list_for_each_entry_safe(block, bn, &blocks, link) {
557 32 : list_del(&block->link);
558 16 : drm_buddy_free_block(&mm, block);
559 :
560 32 : size = get_size(order, PAGE_SIZE);
561 16 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
562 : size, size, &tmp, flags),
563 : "buddy_alloc hit -ENOMEM with order=%d\n",
564 : order);
565 :
566 16 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
567 16 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
568 :
569 32 : list_del(&block->link);
570 16 : drm_buddy_free_block(&mm, block);
571 16 : order++;
572 : }
573 :
574 : /* To confirm, now the whole mm should be available */
575 1 : size = get_size(max_order, PAGE_SIZE);
576 1 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
577 : size, size, &tmp, flags),
578 : "buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
579 : max_order);
580 :
581 1 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
582 1 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
583 :
584 2 : list_del(&block->link);
585 1 : drm_buddy_free_block(&mm, block);
586 1 : drm_buddy_free_list(&mm, &blocks);
587 1 : drm_buddy_fini(&mm);
588 1 : }
589 :
590 1 : static void drm_test_buddy_alloc_optimistic(struct kunit *test)
591 : {
592 1 : u64 mm_size, size, start = 0;
593 : struct drm_buddy_block *block;
594 1 : unsigned long flags = 0;
595 1 : const int max_order = 16;
596 : struct drm_buddy mm;
597 1 : LIST_HEAD(blocks);
598 1 : LIST_HEAD(tmp);
599 : int order;
600 :
601 : /*
602 : * Create a mm with one block of each order available, and
603 : * try to allocate them all.
604 : */
605 :
606 1 : mm_size = PAGE_SIZE * ((1 << (max_order + 1)) - 1);
607 :
608 1 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE),
609 : "buddy_init failed\n");
610 :
611 1 : KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
612 :
613 17 : for (order = 0; order <= max_order; order++) {
614 17 : size = get_size(order, PAGE_SIZE);
615 17 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
616 : size, size, &tmp, flags),
617 : "buddy_alloc hit -ENOMEM with order=%d\n",
618 : order);
619 :
620 17 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
621 17 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
622 :
623 34 : list_move_tail(&block->link, &blocks);
624 : }
625 :
626 : /* Should be completely full! */
627 1 : size = get_size(0, PAGE_SIZE);
628 1 : KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
629 : size, size, &tmp, flags),
630 : "buddy_alloc unexpectedly succeeded, it should be full!");
631 :
632 1 : drm_buddy_free_list(&mm, &blocks);
633 1 : drm_buddy_fini(&mm);
634 1 : }
635 :
636 1 : static void drm_test_buddy_alloc_range(struct kunit *test)
637 : {
638 1 : unsigned long flags = DRM_BUDDY_RANGE_ALLOCATION;
639 : u64 offset, size, rem, chunk_size, end;
640 : unsigned long page_num;
641 : struct drm_buddy mm;
642 1 : LIST_HEAD(blocks);
643 :
644 1 : mm_config(&size, &chunk_size);
645 :
646 1 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, size, chunk_size),
647 : "buddy_init failed");
648 :
649 1 : KUNIT_ASSERT_FALSE_MSG(test, check_mm(test, &mm),
650 : "pre-mm check failed, abort!");
651 :
652 1 : rem = mm.size;
653 1 : offset = 0;
654 :
655 50 : for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) {
656 : struct drm_buddy_block *block;
657 50 : LIST_HEAD(tmp);
658 :
659 50 : size = min(page_num * mm.chunk_size, rem);
660 50 : end = offset + size;
661 :
662 50 : KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, offset, end,
663 : size, mm.chunk_size,
664 : &tmp, flags),
665 : "alloc_range with offset=%llx, size=%llx failed\n", offset, size);
666 :
667 50 : block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
668 50 : KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_range has no blocks\n");
669 :
670 100 : KUNIT_ASSERT_EQ_MSG(test, drm_buddy_block_offset(block), offset,
671 : "alloc_range start offset mismatch, found=%llx, expected=%llx\n",
672 : drm_buddy_block_offset(block), offset);
673 :
674 50 : KUNIT_ASSERT_FALSE(test, check_blocks(test, &mm, &tmp, size, true));
675 :
676 50 : list_splice_tail(&tmp, &blocks);
677 :
678 50 : offset += size;
679 :
680 50 : rem -= size;
681 50 : if (!rem)
682 : break;
683 :
684 49 : cond_resched();
685 : }
686 :
687 1 : drm_buddy_free_list(&mm, &blocks);
688 :
689 1 : KUNIT_EXPECT_FALSE_MSG(test, check_mm(test, &mm), "post-mm check failed\n");
690 :
691 1 : drm_buddy_fini(&mm);
692 1 : }
693 :
694 1 : static void drm_test_buddy_alloc_limit(struct kunit *test)
695 : {
696 1 : u64 size = U64_MAX, start = 0;
697 : struct drm_buddy_block *block;
698 1 : unsigned long flags = 0;
699 1 : LIST_HEAD(allocated);
700 : struct drm_buddy mm;
701 :
702 1 : KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, size, PAGE_SIZE));
703 :
704 1 : KUNIT_EXPECT_EQ_MSG(test, mm.max_order, DRM_BUDDY_MAX_ORDER,
705 : "mm.max_order(%d) != %d\n", mm.max_order,
706 : DRM_BUDDY_MAX_ORDER);
707 :
708 1 : size = mm.chunk_size << mm.max_order;
709 1 : KUNIT_EXPECT_FALSE(test, drm_buddy_alloc_blocks(&mm, start, size, size,
710 : PAGE_SIZE, &allocated, flags));
711 :
712 1 : block = list_first_entry_or_null(&allocated, struct drm_buddy_block, link);
713 1 : KUNIT_EXPECT_TRUE(test, block);
714 :
715 2 : KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_order(block), mm.max_order,
716 : "block order(%d) != %d\n",
717 : drm_buddy_block_order(block), mm.max_order);
718 :
719 2 : KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_size(&mm, block),
720 : BIT_ULL(mm.max_order) * PAGE_SIZE,
721 : "block size(%llu) != %llu\n",
722 : drm_buddy_block_size(&mm, block),
723 : BIT_ULL(mm.max_order) * PAGE_SIZE);
724 :
725 1 : drm_buddy_free_list(&mm, &allocated);
726 1 : drm_buddy_fini(&mm);
727 1 : }
728 :
729 1 : static int drm_buddy_suite_init(struct kunit_suite *suite)
730 : {
731 3 : while (!random_seed)
732 1 : random_seed = get_random_u32();
733 :
734 1 : kunit_info(suite, "Testing DRM buddy manager, with random_seed=0x%x\n", random_seed);
735 :
736 1 : return 0;
737 : }
738 :
739 : static struct kunit_case drm_buddy_tests[] = {
740 : KUNIT_CASE(drm_test_buddy_alloc_limit),
741 : KUNIT_CASE(drm_test_buddy_alloc_range),
742 : KUNIT_CASE(drm_test_buddy_alloc_optimistic),
743 : KUNIT_CASE(drm_test_buddy_alloc_pessimistic),
744 : KUNIT_CASE(drm_test_buddy_alloc_smoke),
745 : KUNIT_CASE(drm_test_buddy_alloc_pathological),
746 : {}
747 : };
748 :
749 : static struct kunit_suite drm_buddy_test_suite = {
750 : .name = "drm_buddy",
751 : .suite_init = drm_buddy_suite_init,
752 : .test_cases = drm_buddy_tests,
753 : };
754 :
755 : kunit_test_suite(drm_buddy_test_suite);
756 :
757 : MODULE_AUTHOR("Intel Corporation");
758 : MODULE_LICENSE("GPL");
|
