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