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 | return (1 << order) * chunk_size; |
24 | } |
25 | |
26 | __printf(2, 3) |
27 | static bool __timeout(unsigned long timeout, const char *fmt, ...) |
28 | { |
29 | va_list va; |
30 | |
31 | if (!signal_pending(current)) { |
32 | cond_resched(); |
33 | if (time_before(jiffies, timeout)) |
34 | return false; |
35 | } |
36 | |
37 | if (fmt) { |
38 | va_start(va, fmt); |
39 | vprintk(fmt, args: va); |
40 | va_end(va); |
41 | } |
42 | |
43 | return true; |
44 | } |
45 | |
46 | static void __dump_block(struct kunit *test, struct drm_buddy *mm, |
47 | struct drm_buddy_block *block, bool buddy) |
48 | { |
49 | 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 | } |
54 | |
55 | 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 | __dump_block(test, mm, block, buddy: false); |
61 | |
62 | buddy = drm_get_buddy(block); |
63 | if (buddy) |
64 | __dump_block(test, mm, block: buddy, buddy: true); |
65 | } |
66 | |
67 | 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 | int err = 0; |
75 | |
76 | block_state = drm_buddy_block_state(block); |
77 | |
78 | if (block_state != DRM_BUDDY_ALLOCATED && |
79 | block_state != DRM_BUDDY_FREE && block_state != DRM_BUDDY_SPLIT) { |
80 | kunit_err(test, "block state mismatch\n" ); |
81 | err = -EINVAL; |
82 | } |
83 | |
84 | block_size = drm_buddy_block_size(mm, block); |
85 | offset = drm_buddy_block_offset(block); |
86 | |
87 | if (block_size < mm->chunk_size) { |
88 | kunit_err(test, "block size smaller than min size\n" ); |
89 | err = -EINVAL; |
90 | } |
91 | |
92 | /* We can't use is_power_of_2() for a u64 on 32-bit systems. */ |
93 | if (block_size & (block_size - 1)) { |
94 | kunit_err(test, "block size not power of two\n" ); |
95 | err = -EINVAL; |
96 | } |
97 | |
98 | if (!IS_ALIGNED(block_size, mm->chunk_size)) { |
99 | kunit_err(test, "block size not aligned to min size\n" ); |
100 | err = -EINVAL; |
101 | } |
102 | |
103 | if (!IS_ALIGNED(offset, mm->chunk_size)) { |
104 | kunit_err(test, "block offset not aligned to min size\n" ); |
105 | err = -EINVAL; |
106 | } |
107 | |
108 | if (!IS_ALIGNED(offset, block_size)) { |
109 | kunit_err(test, "block offset not aligned to block size\n" ); |
110 | err = -EINVAL; |
111 | } |
112 | |
113 | buddy = drm_get_buddy(block); |
114 | |
115 | if (!buddy && block->parent) { |
116 | kunit_err(test, "buddy has gone fishing\n" ); |
117 | err = -EINVAL; |
118 | } |
119 | |
120 | if (buddy) { |
121 | if (drm_buddy_block_offset(block: buddy) != (offset ^ block_size)) { |
122 | kunit_err(test, "buddy has wrong offset\n" ); |
123 | err = -EINVAL; |
124 | } |
125 | |
126 | if (drm_buddy_block_size(mm, block: buddy) != block_size) { |
127 | kunit_err(test, "buddy size mismatch\n" ); |
128 | err = -EINVAL; |
129 | } |
130 | |
131 | if (drm_buddy_block_state(block: buddy) == block_state && |
132 | block_state == DRM_BUDDY_FREE) { |
133 | kunit_err(test, "block and its buddy are free\n" ); |
134 | err = -EINVAL; |
135 | } |
136 | } |
137 | |
138 | return err; |
139 | } |
140 | |
141 | 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 | int err = 0; |
148 | |
149 | block = NULL; |
150 | prev = NULL; |
151 | total = 0; |
152 | |
153 | list_for_each_entry(block, blocks, link) { |
154 | err = check_block(test, mm, block); |
155 | |
156 | if (!drm_buddy_block_is_allocated(block)) { |
157 | kunit_err(test, "block not allocated\n" ); |
158 | err = -EINVAL; |
159 | } |
160 | |
161 | if (is_contiguous && prev) { |
162 | u64 prev_block_size; |
163 | u64 prev_offset; |
164 | u64 offset; |
165 | |
166 | prev_offset = drm_buddy_block_offset(block: prev); |
167 | prev_block_size = drm_buddy_block_size(mm, block: prev); |
168 | offset = drm_buddy_block_offset(block); |
169 | |
170 | if (offset != (prev_offset + prev_block_size)) { |
171 | kunit_err(test, "block offset mismatch\n" ); |
172 | err = -EINVAL; |
173 | } |
174 | } |
175 | |
176 | if (err) |
177 | break; |
178 | |
179 | total += drm_buddy_block_size(mm, block); |
180 | prev = block; |
181 | } |
182 | |
183 | if (!err) { |
184 | if (total != expected_size) { |
185 | kunit_err(test, "size mismatch, expected=%llx, found=%llx\n" , |
186 | expected_size, total); |
187 | err = -EINVAL; |
188 | } |
189 | return err; |
190 | } |
191 | |
192 | if (prev) { |
193 | kunit_err(test, "prev block, dump:\n" ); |
194 | dump_block(test, mm, block: prev); |
195 | } |
196 | |
197 | kunit_err(test, "bad block, dump:\n" ); |
198 | dump_block(test, mm, block); |
199 | |
200 | return err; |
201 | } |
202 | |
203 | 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 | int err = 0; |
210 | |
211 | if (!mm->n_roots) { |
212 | kunit_err(test, "n_roots is zero\n" ); |
213 | return -EINVAL; |
214 | } |
215 | |
216 | if (mm->n_roots != hweight64(mm->size)) { |
217 | kunit_err(test, "n_roots mismatch, n_roots=%u, expected=%lu\n" , |
218 | mm->n_roots, hweight64(mm->size)); |
219 | return -EINVAL; |
220 | } |
221 | |
222 | root = NULL; |
223 | prev = NULL; |
224 | total = 0; |
225 | |
226 | for (i = 0; i < mm->n_roots; ++i) { |
227 | struct drm_buddy_block *block; |
228 | unsigned int order; |
229 | |
230 | root = mm->roots[i]; |
231 | if (!root) { |
232 | kunit_err(test, "root(%u) is NULL\n" , i); |
233 | err = -EINVAL; |
234 | break; |
235 | } |
236 | |
237 | err = check_block(test, mm, block: root); |
238 | |
239 | if (!drm_buddy_block_is_free(block: root)) { |
240 | kunit_err(test, "root not free\n" ); |
241 | err = -EINVAL; |
242 | } |
243 | |
244 | order = drm_buddy_block_order(block: root); |
245 | |
246 | if (!i) { |
247 | if (order != mm->max_order) { |
248 | kunit_err(test, "max order root missing\n" ); |
249 | err = -EINVAL; |
250 | } |
251 | } |
252 | |
253 | if (prev) { |
254 | u64 prev_block_size; |
255 | u64 prev_offset; |
256 | u64 offset; |
257 | |
258 | prev_offset = drm_buddy_block_offset(block: prev); |
259 | prev_block_size = drm_buddy_block_size(mm, block: prev); |
260 | offset = drm_buddy_block_offset(block: root); |
261 | |
262 | if (offset != (prev_offset + prev_block_size)) { |
263 | kunit_err(test, "root offset mismatch\n" ); |
264 | err = -EINVAL; |
265 | } |
266 | } |
267 | |
268 | block = list_first_entry_or_null(&mm->free_list[order], |
269 | struct drm_buddy_block, link); |
270 | if (block != root) { |
271 | kunit_err(test, "root mismatch at order=%u\n" , order); |
272 | err = -EINVAL; |
273 | } |
274 | |
275 | if (err) |
276 | break; |
277 | |
278 | prev = root; |
279 | total += drm_buddy_block_size(mm, block: root); |
280 | } |
281 | |
282 | if (!err) { |
283 | if (total != mm->size) { |
284 | kunit_err(test, "expected mm size=%llx, found=%llx\n" , |
285 | mm->size, total); |
286 | err = -EINVAL; |
287 | } |
288 | return err; |
289 | } |
290 | |
291 | if (prev) { |
292 | kunit_err(test, "prev root(%u), dump:\n" , i - 1); |
293 | dump_block(test, mm, block: prev); |
294 | } |
295 | |
296 | if (root) { |
297 | kunit_err(test, "bad root(%u), dump:\n" , i); |
298 | dump_block(test, mm, block: root); |
299 | } |
300 | |
301 | return err; |
302 | } |
303 | |
304 | static void mm_config(u64 *size, u64 *chunk_size) |
305 | { |
306 | DRM_RND_STATE(prng, random_seed); |
307 | u32 s, ms; |
308 | |
309 | /* Nothing fancy, just try to get an interesting bit pattern */ |
310 | |
311 | prandom_seed_state(state: &prng, seed: random_seed); |
312 | |
313 | /* Let size be a random number of pages up to 8 GB (2M pages) */ |
314 | s = 1 + drm_prandom_u32_max_state(ep_ro: (BIT(33 - 12)) - 1, state: &prng); |
315 | /* Let the chunk size be a random power of 2 less than size */ |
316 | ms = BIT(drm_prandom_u32_max_state(ilog2(s), &prng)); |
317 | /* Round size down to the chunk size */ |
318 | s &= -ms; |
319 | |
320 | /* Convert from pages to bytes */ |
321 | *chunk_size = (u64)ms << 12; |
322 | *size = (u64)s << 12; |
323 | } |
324 | |
325 | static void drm_test_buddy_alloc_pathological(struct kunit *test) |
326 | { |
327 | u64 mm_size, size, start = 0; |
328 | struct drm_buddy_block *block; |
329 | const int max_order = 3; |
330 | unsigned long flags = 0; |
331 | int order, top; |
332 | struct drm_buddy mm; |
333 | LIST_HEAD(blocks); |
334 | LIST_HEAD(holes); |
335 | 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 | mm_size = PAGE_SIZE << max_order; |
345 | KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE), |
346 | "buddy_init failed\n" ); |
347 | |
348 | KUNIT_EXPECT_EQ(test, mm.max_order, max_order); |
349 | |
350 | for (top = max_order; top; top--) { |
351 | /* Make room by freeing the largest allocated block */ |
352 | block = list_first_entry_or_null(&blocks, typeof(*block), link); |
353 | if (block) { |
354 | list_del(entry: &block->link); |
355 | drm_buddy_free_block(mm: &mm, block); |
356 | } |
357 | |
358 | for (order = top; order--;) { |
359 | size = get_size(order, PAGE_SIZE); |
360 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
367 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
368 | |
369 | list_move_tail(list: &block->link, head: &blocks); |
370 | } |
371 | |
372 | /* There should be one final page for this sub-allocation */ |
373 | size = get_size(order: 0, PAGE_SIZE); |
374 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
379 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
380 | |
381 | list_move_tail(list: &block->link, head: &holes); |
382 | |
383 | size = get_size(order: top, PAGE_SIZE); |
384 | 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 | drm_buddy_free_list(mm: &mm, objects: &holes); |
391 | |
392 | /* Nothing larger than blocks of chunk_size now available */ |
393 | for (order = 1; order <= max_order; order++) { |
394 | size = get_size(order, PAGE_SIZE); |
395 | 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 | list_splice_tail(list: &holes, head: &blocks); |
402 | drm_buddy_free_list(mm: &mm, objects: &blocks); |
403 | drm_buddy_fini(mm: &mm); |
404 | } |
405 | |
406 | static void drm_test_buddy_alloc_smoke(struct kunit *test) |
407 | { |
408 | u64 mm_size, chunk_size, start = 0; |
409 | unsigned long flags = 0; |
410 | struct drm_buddy mm; |
411 | int *order; |
412 | int i; |
413 | |
414 | DRM_RND_STATE(prng, random_seed); |
415 | TIMEOUT(end_time); |
416 | |
417 | mm_config(size: &mm_size, chunk_size: &chunk_size); |
418 | |
419 | KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, chunk_size), |
420 | "buddy_init failed\n" ); |
421 | |
422 | order = drm_random_order(count: mm.max_order + 1, state: &prng); |
423 | KUNIT_ASSERT_TRUE(test, order); |
424 | |
425 | for (i = 0; i <= mm.max_order; ++i) { |
426 | struct drm_buddy_block *block; |
427 | int max_order = order[i]; |
428 | bool timeout = false; |
429 | LIST_HEAD(blocks); |
430 | u64 total, size; |
431 | LIST_HEAD(tmp); |
432 | int order, err; |
433 | |
434 | 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 | size = get_size(order, chunk_size); |
443 | err = drm_buddy_alloc_blocks(mm: &mm, start, end: mm_size, size, min_page_size: size, blocks: &tmp, flags); |
444 | if (err) { |
445 | if (err == -ENOMEM) { |
446 | KUNIT_FAIL(test, "buddy_alloc hit -ENOMEM with order=%d\n" , |
447 | order); |
448 | } else { |
449 | if (order--) { |
450 | err = 0; |
451 | goto retry; |
452 | } |
453 | |
454 | KUNIT_FAIL(test, "buddy_alloc with order=%d failed\n" , |
455 | order); |
456 | } |
457 | |
458 | break; |
459 | } |
460 | |
461 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
462 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
463 | |
464 | list_move_tail(list: &block->link, head: &blocks); |
465 | KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_order(block), order, |
466 | "buddy_alloc order mismatch\n" ); |
467 | |
468 | total += drm_buddy_block_size(mm: &mm, block); |
469 | |
470 | if (__timeout(timeout: end_time, NULL)) { |
471 | timeout = true; |
472 | break; |
473 | } |
474 | } while (total < mm.size); |
475 | |
476 | if (!err) |
477 | err = check_blocks(test, mm: &mm, blocks: &blocks, expected_size: total, is_contiguous: false); |
478 | |
479 | drm_buddy_free_list(mm: &mm, objects: &blocks); |
480 | |
481 | if (!err) { |
482 | KUNIT_EXPECT_FALSE_MSG(test, check_mm(test, &mm), |
483 | "post-mm check failed\n" ); |
484 | } |
485 | |
486 | if (err || timeout) |
487 | break; |
488 | |
489 | cond_resched(); |
490 | } |
491 | |
492 | kfree(objp: order); |
493 | drm_buddy_fini(mm: &mm); |
494 | } |
495 | |
496 | static void drm_test_buddy_alloc_pessimistic(struct kunit *test) |
497 | { |
498 | u64 mm_size, size, start = 0; |
499 | struct drm_buddy_block *block, *bn; |
500 | const unsigned int max_order = 16; |
501 | unsigned long flags = 0; |
502 | struct drm_buddy mm; |
503 | unsigned int order; |
504 | LIST_HEAD(blocks); |
505 | 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 | mm_size = PAGE_SIZE << max_order; |
514 | KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE), |
515 | "buddy_init failed\n" ); |
516 | |
517 | KUNIT_EXPECT_EQ(test, mm.max_order, max_order); |
518 | |
519 | for (order = 0; order < max_order; order++) { |
520 | size = get_size(order, PAGE_SIZE); |
521 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
527 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
528 | |
529 | list_move_tail(list: &block->link, head: &blocks); |
530 | } |
531 | |
532 | /* And now the last remaining block available */ |
533 | size = get_size(order: 0, PAGE_SIZE); |
534 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
539 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
540 | |
541 | list_move_tail(list: &block->link, head: &blocks); |
542 | |
543 | /* Should be completely full! */ |
544 | for (order = max_order; order--;) { |
545 | size = get_size(order, PAGE_SIZE); |
546 | 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 | block = list_last_entry(&blocks, typeof(*block), link); |
552 | list_del(entry: &block->link); |
553 | drm_buddy_free_block(mm: &mm, block); |
554 | |
555 | /* As we free in increasing size, we make available larger blocks */ |
556 | order = 1; |
557 | list_for_each_entry_safe(block, bn, &blocks, link) { |
558 | list_del(entry: &block->link); |
559 | drm_buddy_free_block(mm: &mm, block); |
560 | |
561 | size = get_size(order, PAGE_SIZE); |
562 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
568 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
569 | |
570 | list_del(entry: &block->link); |
571 | drm_buddy_free_block(mm: &mm, block); |
572 | order++; |
573 | } |
574 | |
575 | /* To confirm, now the whole mm should be available */ |
576 | size = get_size(order: max_order, PAGE_SIZE); |
577 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
583 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
584 | |
585 | list_del(entry: &block->link); |
586 | drm_buddy_free_block(mm: &mm, block); |
587 | drm_buddy_free_list(mm: &mm, objects: &blocks); |
588 | drm_buddy_fini(mm: &mm); |
589 | } |
590 | |
591 | static void drm_test_buddy_alloc_optimistic(struct kunit *test) |
592 | { |
593 | u64 mm_size, size, start = 0; |
594 | struct drm_buddy_block *block; |
595 | unsigned long flags = 0; |
596 | const int max_order = 16; |
597 | struct drm_buddy mm; |
598 | LIST_HEAD(blocks); |
599 | 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 | mm_size = PAGE_SIZE * ((1 << (max_order + 1)) - 1); |
608 | |
609 | KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, PAGE_SIZE), |
610 | "buddy_init failed\n" ); |
611 | |
612 | KUNIT_EXPECT_EQ(test, mm.max_order, max_order); |
613 | |
614 | for (order = 0; order <= max_order; order++) { |
615 | size = get_size(order, PAGE_SIZE); |
616 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
622 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n" ); |
623 | |
624 | list_move_tail(list: &block->link, head: &blocks); |
625 | } |
626 | |
627 | /* Should be completely full! */ |
628 | size = get_size(order: 0, PAGE_SIZE); |
629 | 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 | drm_buddy_free_list(mm: &mm, objects: &blocks); |
634 | drm_buddy_fini(mm: &mm); |
635 | } |
636 | |
637 | static void drm_test_buddy_alloc_range(struct kunit *test) |
638 | { |
639 | 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 | LIST_HEAD(blocks); |
644 | |
645 | mm_config(size: &size, chunk_size: &chunk_size); |
646 | |
647 | KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, size, chunk_size), |
648 | "buddy_init failed" ); |
649 | |
650 | KUNIT_ASSERT_FALSE_MSG(test, check_mm(test, &mm), |
651 | "pre-mm check failed, abort!" ); |
652 | |
653 | rem = mm.size; |
654 | offset = 0; |
655 | |
656 | for_each_prime_number_from(page_num, 1, ULONG_MAX - 1) { |
657 | struct drm_buddy_block *block; |
658 | LIST_HEAD(tmp); |
659 | |
660 | size = min(page_num * mm.chunk_size, rem); |
661 | end = offset + size; |
662 | |
663 | 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 | block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link); |
669 | KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_range has no blocks\n" ); |
670 | |
671 | 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 | KUNIT_ASSERT_FALSE(test, check_blocks(test, &mm, &tmp, size, true)); |
676 | |
677 | list_splice_tail(list: &tmp, head: &blocks); |
678 | |
679 | offset += size; |
680 | |
681 | rem -= size; |
682 | if (!rem) |
683 | break; |
684 | |
685 | cond_resched(); |
686 | } |
687 | |
688 | drm_buddy_free_list(mm: &mm, objects: &blocks); |
689 | |
690 | KUNIT_EXPECT_FALSE_MSG(test, check_mm(test, &mm), "post-mm check failed\n" ); |
691 | |
692 | drm_buddy_fini(mm: &mm); |
693 | } |
694 | |
695 | static void drm_test_buddy_alloc_limit(struct kunit *test) |
696 | { |
697 | u64 size = U64_MAX, start = 0; |
698 | struct drm_buddy_block *block; |
699 | unsigned long flags = 0; |
700 | LIST_HEAD(allocated); |
701 | struct drm_buddy mm; |
702 | |
703 | KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, size, PAGE_SIZE)); |
704 | |
705 | 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 | size = mm.chunk_size << mm.max_order; |
710 | KUNIT_EXPECT_FALSE(test, drm_buddy_alloc_blocks(&mm, start, size, size, |
711 | PAGE_SIZE, &allocated, flags)); |
712 | |
713 | block = list_first_entry_or_null(&allocated, struct drm_buddy_block, link); |
714 | KUNIT_EXPECT_TRUE(test, block); |
715 | |
716 | 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 | 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 | drm_buddy_free_list(mm: &mm, objects: &allocated); |
727 | drm_buddy_fini(mm: &mm); |
728 | } |
729 | |
730 | static int drm_buddy_suite_init(struct kunit_suite *suite) |
731 | { |
732 | while (!random_seed) |
733 | random_seed = get_random_u32(); |
734 | |
735 | kunit_info(suite, "Testing DRM buddy manager, with random_seed=0x%x\n" , random_seed); |
736 | |
737 | 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" ); |
760 | |