drm_buddy_test.c

  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#include <linux/sizes.h>
 12
 13#include <drm/drm_buddy.h>
 14
 15#include "../lib/drm_random.h"
 16
 17static unsigned int random_seed;
 18
 19static inline u64 get_size(int order, u64 chunk_size)
 20{
 21	return (1 << order) * chunk_size;
 22}
 23
 24static void drm_test_buddy_fragmentation_performance(struct kunit *test)
 25{
 26	struct drm_buddy_block *block, *tmp;
 27	int num_blocks, i, ret, count = 0;
 28	LIST_HEAD(allocated_blocks);
 29	unsigned long elapsed_ms;
 30	LIST_HEAD(reverse_list);
 31	LIST_HEAD(test_blocks);
 32	LIST_HEAD(clear_list);
 33	LIST_HEAD(dirty_list);
 34	LIST_HEAD(free_list);
 35	struct drm_buddy mm;
 36	u64 mm_size = SZ_4G;
 37	ktime_t start, end;
 38
 39	/*
 40	 * Allocation under severe fragmentation
 41	 *
 42	 * Create severe fragmentation by allocating the entire 4 GiB address space
 43	 * as tiny 8 KiB blocks but forcing a 64 KiB alignment. The resulting pattern
 44	 * leaves many scattered holes. Split the allocations into two groups and
 45	 * return them with different flags to block coalescing, then repeatedly
 46	 * allocate and free 64 KiB blocks while timing the loop. This stresses how
 47	 * quickly the allocator can satisfy larger, aligned requests from a pool of
 48	 * highly fragmented space.
 49	 */
 50	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, SZ_4K),
 51			       "buddy_init failed\n");
 52
 53	num_blocks = mm_size / SZ_64K;
 54
 55	start = ktime_get();
 56	/* Allocate with maximum fragmentation - 8K blocks with 64K alignment */
 57	for (i = 0; i < num_blocks; i++)
 58		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_64K,
 59								    &allocated_blocks, 0),
 60					"buddy_alloc hit an error size=%u\n", SZ_8K);
 61
 62	list_for_each_entry_safe(block, tmp, &allocated_blocks, link) {
 63		if (count % 4 == 0 || count % 4 == 3)
 64			list_move_tail(&block->link, &clear_list);
 65		else
 66			list_move_tail(&block->link, &dirty_list);
 67		count++;
 68	}
 69
 70	/* Free with different flags to ensure no coalescing */
 71	drm_buddy_free_list(&mm, &clear_list, DRM_BUDDY_CLEARED);
 72	drm_buddy_free_list(&mm, &dirty_list, 0);
 73
 74	for (i = 0; i < num_blocks; i++)
 75		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size, SZ_64K, SZ_64K,
 76								    &test_blocks, 0),
 77					"buddy_alloc hit an error size=%u\n", SZ_64K);
 78	drm_buddy_free_list(&mm, &test_blocks, 0);
 79
 80	end = ktime_get();
 81	elapsed_ms = ktime_to_ms(ktime_sub(end, start));
 82
 83	kunit_info(test, "Fragmented allocation took %lu ms\n", elapsed_ms);
 84
 85	drm_buddy_fini(&mm);
 86
 87	/*
 88	 * Reverse free order under fragmentation
 89	 *
 90	 * Construct a fragmented 4 GiB space by allocating every 8 KiB block with
 91	 * 64 KiB alignment, creating a dense scatter of small regions. Half of the
 92	 * blocks are selectively freed to form sparse gaps, while the remaining
 93	 * allocations are preserved, reordered in reverse, and released back with
 94	 * the cleared flag. This models a pathological reverse-ordered free pattern
 95	 * and measures how quickly the allocator can merge and reclaim space when
 96	 * deallocation occurs in the opposite order of allocation, exposing the
 97	 * cost difference between a linear freelist scan and an ordered tree lookup.
 98	 */
 99	ret = drm_buddy_init(&mm, mm_size, SZ_4K);
100	KUNIT_ASSERT_EQ(test, ret, 0);
101
102	start = ktime_get();
103	/* Allocate maximum fragmentation */
104	for (i = 0; i < num_blocks; i++)
105		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_64K,
106								    &allocated_blocks, 0),
107					"buddy_alloc hit an error size=%u\n", SZ_8K);
108
109	list_for_each_entry_safe(block, tmp, &allocated_blocks, link) {
110		if (count % 2 == 0)
111			list_move_tail(&block->link, &free_list);
112		count++;
113	}
114	drm_buddy_free_list(&mm, &free_list, DRM_BUDDY_CLEARED);
115
116	list_for_each_entry_safe_reverse(block, tmp, &allocated_blocks, link)
117		list_move(&block->link, &reverse_list);
118	drm_buddy_free_list(&mm, &reverse_list, DRM_BUDDY_CLEARED);
119
120	end = ktime_get();
121	elapsed_ms = ktime_to_ms(ktime_sub(end, start));
122
123	kunit_info(test, "Reverse-ordered free took %lu ms\n", elapsed_ms);
124
125	drm_buddy_fini(&mm);
126}
127
128static void drm_test_buddy_alloc_range_bias(struct kunit *test)
129{
130	u32 mm_size, size, ps, bias_size, bias_start, bias_end, bias_rem;
131	DRM_RND_STATE(prng, random_seed);
132	unsigned int i, count, *order;
133	struct drm_buddy_block *block;
134	unsigned long flags;
135	struct drm_buddy mm;
136	LIST_HEAD(allocated);
137
138	bias_size = SZ_1M;
139	ps = roundup_pow_of_two(prandom_u32_state(&prng) % bias_size);
140	ps = max(SZ_4K, ps);
141	mm_size = (SZ_8M-1) & ~(ps-1); /* Multiple roots */
142
143	kunit_info(test, "mm_size=%u, ps=%u\n", mm_size, ps);
144
145	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, ps),
146			       "buddy_init failed\n");
147
148	count = mm_size / bias_size;
149	order = drm_random_order(count, &prng);
150	KUNIT_EXPECT_TRUE(test, order);
151
152	/*
153	 * Idea is to split the address space into uniform bias ranges, and then
154	 * in some random order allocate within each bias, using various
155	 * patterns within. This should detect if allocations leak out from a
156	 * given bias, for example.
157	 */
158
159	for (i = 0; i < count; i++) {
160		LIST_HEAD(tmp);
161		u32 size;
162
163		bias_start = order[i] * bias_size;
164		bias_end = bias_start + bias_size;
165		bias_rem = bias_size;
166
167		/* internal round_up too big */
168		KUNIT_ASSERT_TRUE_MSG(test,
169				      drm_buddy_alloc_blocks(&mm, bias_start,
170							     bias_end, bias_size + ps, bias_size,
171							     &allocated,
172							     DRM_BUDDY_RANGE_ALLOCATION),
173				      "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",
174				      bias_start, bias_end, bias_size, bias_size);
175
176		/* size too big */
177		KUNIT_ASSERT_TRUE_MSG(test,
178				      drm_buddy_alloc_blocks(&mm, bias_start,
179							     bias_end, bias_size + ps, ps,
180							     &allocated,
181							     DRM_BUDDY_RANGE_ALLOCATION),
182				      "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",
183				      bias_start, bias_end, bias_size + ps, ps);
184
185		/* bias range too small for size */
186		KUNIT_ASSERT_TRUE_MSG(test,
187				      drm_buddy_alloc_blocks(&mm, bias_start + ps,
188							     bias_end, bias_size, ps,
189							     &allocated,
190							     DRM_BUDDY_RANGE_ALLOCATION),
191				      "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",
192				      bias_start + ps, bias_end, bias_size, ps);
193
194		/* bias misaligned */
195		KUNIT_ASSERT_TRUE_MSG(test,
196				      drm_buddy_alloc_blocks(&mm, bias_start + ps,
197							     bias_end - ps,
198							     bias_size >> 1, bias_size >> 1,
199							     &allocated,
200							     DRM_BUDDY_RANGE_ALLOCATION),
201				      "buddy_alloc h didn't fail with bias(%x-%x), size=%u, ps=%u\n",
202				      bias_start + ps, bias_end - ps, bias_size >> 1, bias_size >> 1);
203
204		/* single big page */
205		KUNIT_ASSERT_FALSE_MSG(test,
206				       drm_buddy_alloc_blocks(&mm, bias_start,
207							      bias_end, bias_size, bias_size,
208							      &tmp,
209							      DRM_BUDDY_RANGE_ALLOCATION),
210				       "buddy_alloc i failed with bias(%x-%x), size=%u, ps=%u\n",
211				       bias_start, bias_end, bias_size, bias_size);
212		drm_buddy_free_list(&mm, &tmp, 0);
213
214		/* single page with internal round_up */
215		KUNIT_ASSERT_FALSE_MSG(test,
216				       drm_buddy_alloc_blocks(&mm, bias_start,
217							      bias_end, ps, bias_size,
218							      &tmp,
219							      DRM_BUDDY_RANGE_ALLOCATION),
220				       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",
221				       bias_start, bias_end, ps, bias_size);
222		drm_buddy_free_list(&mm, &tmp, 0);
223
224		/* random size within */
225		size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);
226		if (size)
227			KUNIT_ASSERT_FALSE_MSG(test,
228					       drm_buddy_alloc_blocks(&mm, bias_start,
229								      bias_end, size, ps,
230								      &tmp,
231								      DRM_BUDDY_RANGE_ALLOCATION),
232					       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",
233					       bias_start, bias_end, size, ps);
234
235		bias_rem -= size;
236		/* too big for current avail */
237		KUNIT_ASSERT_TRUE_MSG(test,
238				      drm_buddy_alloc_blocks(&mm, bias_start,
239							     bias_end, bias_rem + ps, ps,
240							     &allocated,
241							     DRM_BUDDY_RANGE_ALLOCATION),
242				      "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n",
243				      bias_start, bias_end, bias_rem + ps, ps);
244
245		if (bias_rem) {
246			/* random fill of the remainder */
247			size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);
248			size = max(size, ps);
249
250			KUNIT_ASSERT_FALSE_MSG(test,
251					       drm_buddy_alloc_blocks(&mm, bias_start,
252								      bias_end, size, ps,
253								      &allocated,
254								      DRM_BUDDY_RANGE_ALLOCATION),
255					       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",
256					       bias_start, bias_end, size, ps);
257			/*
258			 * Intentionally allow some space to be left
259			 * unallocated, and ideally not always on the bias
260			 * boundaries.
261			 */
262			drm_buddy_free_list(&mm, &tmp, 0);
263		} else {
264			list_splice_tail(&tmp, &allocated);
265		}
266	}
267
268	kfree(order);
269	drm_buddy_free_list(&mm, &allocated, 0);
270	drm_buddy_fini(&mm);
271
272	/*
273	 * Something more free-form. Idea is to pick a random starting bias
274	 * range within the address space and then start filling it up. Also
275	 * randomly grow the bias range in both directions as we go along. This
276	 * should give us bias start/end which is not always uniform like above,
277	 * and in some cases will require the allocator to jump over already
278	 * allocated nodes in the middle of the address space.
279	 */
280
281	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, ps),
282			       "buddy_init failed\n");
283
284	bias_start = round_up(prandom_u32_state(&prng) % (mm_size - ps), ps);
285	bias_end = round_up(bias_start + prandom_u32_state(&prng) % (mm_size - bias_start), ps);
286	bias_end = max(bias_end, bias_start + ps);
287	bias_rem = bias_end - bias_start;
288
289	do {
290		u32 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);
291
292		KUNIT_ASSERT_FALSE_MSG(test,
293				       drm_buddy_alloc_blocks(&mm, bias_start,
294							      bias_end, size, ps,
295							      &allocated,
296							      DRM_BUDDY_RANGE_ALLOCATION),
297				       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",
298				       bias_start, bias_end, size, ps);
299		bias_rem -= size;
300
301		/*
302		 * Try to randomly grow the bias range in both directions, or
303		 * only one, or perhaps don't grow at all.
304		 */
305		do {
306			u32 old_bias_start = bias_start;
307			u32 old_bias_end = bias_end;
308
309			if (bias_start)
310				bias_start -= round_up(prandom_u32_state(&prng) % bias_start, ps);
311			if (bias_end != mm_size)
312				bias_end += round_up(prandom_u32_state(&prng) % (mm_size - bias_end), ps);
313
314			bias_rem += old_bias_start - bias_start;
315			bias_rem += bias_end - old_bias_end;
316		} while (!bias_rem && (bias_start || bias_end != mm_size));
317	} while (bias_rem);
318
319	KUNIT_ASSERT_EQ(test, bias_start, 0);
320	KUNIT_ASSERT_EQ(test, bias_end, mm_size);
321	KUNIT_ASSERT_TRUE_MSG(test,
322			      drm_buddy_alloc_blocks(&mm, bias_start, bias_end,
323						     ps, ps,
324						     &allocated,
325						     DRM_BUDDY_RANGE_ALLOCATION),
326			      "buddy_alloc passed with bias(%x-%x), size=%u\n",
327			      bias_start, bias_end, ps);
328
329	drm_buddy_free_list(&mm, &allocated, 0);
330	drm_buddy_fini(&mm);
331
332	/*
333	 * Allocate cleared blocks in the bias range when the DRM buddy's clear avail is
334	 * zero. This will validate the bias range allocation in scenarios like system boot
335	 * when no cleared blocks are available and exercise the fallback path too. The resulting
336	 * blocks should always be dirty.
337	 */
338
339	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, ps),
340			       "buddy_init failed\n");
341
342	bias_start = round_up(prandom_u32_state(&prng) % (mm_size - ps), ps);
343	bias_end = round_up(bias_start + prandom_u32_state(&prng) % (mm_size - bias_start), ps);
344	bias_end = max(bias_end, bias_start + ps);
345	bias_rem = bias_end - bias_start;
346
347	flags = DRM_BUDDY_CLEAR_ALLOCATION | DRM_BUDDY_RANGE_ALLOCATION;
348	size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps);
349
350	KUNIT_ASSERT_FALSE_MSG(test,
351			       drm_buddy_alloc_blocks(&mm, bias_start,
352						      bias_end, size, ps,
353						      &allocated,
354						      flags),
355			       "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n",
356			       bias_start, bias_end, size, ps);
357
358	list_for_each_entry(block, &allocated, link)
359		KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), false);
360
361	drm_buddy_free_list(&mm, &allocated, 0);
362	drm_buddy_fini(&mm);
363}
364
365static void drm_test_buddy_alloc_clear(struct kunit *test)
366{
367	unsigned long n_pages, total, i = 0;
368	const unsigned long ps = SZ_4K;
369	struct drm_buddy_block *block;
370	const int max_order = 12;
371	LIST_HEAD(allocated);
372	struct drm_buddy mm;
373	unsigned int order;
374	u32 mm_size, size;
375	LIST_HEAD(dirty);
376	LIST_HEAD(clean);
377
378	mm_size = SZ_4K << max_order;
379	KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));
380
381	KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
382
383	/*
384	 * Idea is to allocate and free some random portion of the address space,
385	 * returning those pages as non-dirty and randomly alternate between
386	 * requesting dirty and non-dirty pages (not going over the limit
387	 * we freed as non-dirty), putting that into two separate lists.
388	 * Loop over both lists at the end checking that the dirty list
389	 * is indeed all dirty pages and vice versa. Free it all again,
390	 * keeping the dirty/clear status.
391	 */
392	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
393							    5 * ps, ps, &allocated,
394							    DRM_BUDDY_TOPDOWN_ALLOCATION),
395				"buddy_alloc hit an error size=%lu\n", 5 * ps);
396	drm_buddy_free_list(&mm, &allocated, DRM_BUDDY_CLEARED);
397
398	n_pages = 10;
399	do {
400		unsigned long flags;
401		struct list_head *list;
402		int slot = i % 2;
403
404		if (slot == 0) {
405			list = &dirty;
406			flags = 0;
407		} else {
408			list = &clean;
409			flags = DRM_BUDDY_CLEAR_ALLOCATION;
410		}
411
412		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
413								    ps, ps, list,
414								    flags),
415					"buddy_alloc hit an error size=%lu\n", ps);
416	} while (++i < n_pages);
417
418	list_for_each_entry(block, &clean, link)
419		KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), true);
420
421	list_for_each_entry(block, &dirty, link)
422		KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), false);
423
424	drm_buddy_free_list(&mm, &clean, DRM_BUDDY_CLEARED);
425
426	/*
427	 * Trying to go over the clear limit for some allocation.
428	 * The allocation should never fail with reasonable page-size.
429	 */
430	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
431							    10 * ps, ps, &clean,
432							    DRM_BUDDY_CLEAR_ALLOCATION),
433				"buddy_alloc hit an error size=%lu\n", 10 * ps);
434
435	drm_buddy_free_list(&mm, &clean, DRM_BUDDY_CLEARED);
436	drm_buddy_free_list(&mm, &dirty, 0);
437	drm_buddy_fini(&mm);
438
439	KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));
440
441	/*
442	 * Create a new mm. Intentionally fragment the address space by creating
443	 * two alternating lists. Free both lists, one as dirty the other as clean.
444	 * Try to allocate double the previous size with matching min_page_size. The
445	 * allocation should never fail as it calls the force_merge. Also check that
446	 * the page is always dirty after force_merge. Free the page as dirty, then
447	 * repeat the whole thing, increment the order until we hit the max_order.
448	 */
449
450	i = 0;
451	n_pages = mm_size / ps;
452	do {
453		struct list_head *list;
454		int slot = i % 2;
455
456		if (slot == 0)
457			list = &dirty;
458		else
459			list = &clean;
460
461		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
462								    ps, ps, list, 0),
463					"buddy_alloc hit an error size=%lu\n", ps);
464	} while (++i < n_pages);
465
466	drm_buddy_free_list(&mm, &clean, DRM_BUDDY_CLEARED);
467	drm_buddy_free_list(&mm, &dirty, 0);
468
469	order = 1;
470	do {
471		size = SZ_4K << order;
472
473		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
474								    size, size, &allocated,
475								    DRM_BUDDY_CLEAR_ALLOCATION),
476					"buddy_alloc hit an error size=%u\n", size);
477		total = 0;
478		list_for_each_entry(block, &allocated, link) {
479			if (size != mm_size)
480				KUNIT_EXPECT_EQ(test, drm_buddy_block_is_clear(block), false);
481			total += drm_buddy_block_size(&mm, block);
482		}
483		KUNIT_EXPECT_EQ(test, total, size);
484
485		drm_buddy_free_list(&mm, &allocated, 0);
486	} while (++order <= max_order);
487
488	drm_buddy_fini(&mm);
489
490	/*
491	 * Create a new mm with a non power-of-two size. Allocate a random size from each
492	 * root, free as cleared and then call fini. This will ensure the multi-root
493	 * force merge during fini.
494	 */
495	mm_size = (SZ_4K << max_order) + (SZ_4K << (max_order - 2));
496
497	KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));
498	KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
499	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, SZ_4K << max_order,
500							    4 * ps, ps, &allocated,
501							    DRM_BUDDY_RANGE_ALLOCATION),
502				"buddy_alloc hit an error size=%lu\n", 4 * ps);
503	drm_buddy_free_list(&mm, &allocated, DRM_BUDDY_CLEARED);
504	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, SZ_4K << max_order,
505							    2 * ps, ps, &allocated,
506							    DRM_BUDDY_CLEAR_ALLOCATION),
507				"buddy_alloc hit an error size=%lu\n", 2 * ps);
508	drm_buddy_free_list(&mm, &allocated, DRM_BUDDY_CLEARED);
509	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, SZ_4K << max_order, mm_size,
510							    ps, ps, &allocated,
511							    DRM_BUDDY_RANGE_ALLOCATION),
512				"buddy_alloc hit an error size=%lu\n", ps);
513	drm_buddy_free_list(&mm, &allocated, DRM_BUDDY_CLEARED);
514	drm_buddy_fini(&mm);
515}
516
517static void drm_test_buddy_alloc_contiguous(struct kunit *test)
518{
519	const unsigned long ps = SZ_4K, mm_size = 16 * 3 * SZ_4K;
520	unsigned long i, n_pages, total;
521	struct drm_buddy_block *block;
522	struct drm_buddy mm;
523	LIST_HEAD(left);
524	LIST_HEAD(middle);
525	LIST_HEAD(right);
526	LIST_HEAD(allocated);
527
528	KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, mm_size, ps));
529
530	/*
531	 * Idea is to fragment the address space by alternating block
532	 * allocations between three different lists; one for left, middle and
533	 * right. We can then free a list to simulate fragmentation. In
534	 * particular we want to exercise the DRM_BUDDY_CONTIGUOUS_ALLOCATION,
535	 * including the try_harder path.
536	 */
537
538	i = 0;
539	n_pages = mm_size / ps;
540	do {
541		struct list_head *list;
542		int slot = i % 3;
543
544		if (slot == 0)
545			list = &left;
546		else if (slot == 1)
547			list = &middle;
548		else
549			list = &right;
550		KUNIT_ASSERT_FALSE_MSG(test,
551				       drm_buddy_alloc_blocks(&mm, 0, mm_size,
552							      ps, ps, list, 0),
553				       "buddy_alloc hit an error size=%lu\n",
554				       ps);
555	} while (++i < n_pages);
556
557	KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
558							   3 * ps, ps, &allocated,
559							   DRM_BUDDY_CONTIGUOUS_ALLOCATION),
560			       "buddy_alloc didn't error size=%lu\n", 3 * ps);
561
562	drm_buddy_free_list(&mm, &middle, 0);
563	KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
564							   3 * ps, ps, &allocated,
565							   DRM_BUDDY_CONTIGUOUS_ALLOCATION),
566			       "buddy_alloc didn't error size=%lu\n", 3 * ps);
567	KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
568							   2 * ps, ps, &allocated,
569							   DRM_BUDDY_CONTIGUOUS_ALLOCATION),
570			       "buddy_alloc didn't error size=%lu\n", 2 * ps);
571
572	drm_buddy_free_list(&mm, &right, 0);
573	KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
574							   3 * ps, ps, &allocated,
575							   DRM_BUDDY_CONTIGUOUS_ALLOCATION),
576			       "buddy_alloc didn't error size=%lu\n", 3 * ps);
577	/*
578	 * At this point we should have enough contiguous space for 2 blocks,
579	 * however they are never buddies (since we freed middle and right) so
580	 * will require the try_harder logic to find them.
581	 */
582	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
583							    2 * ps, ps, &allocated,
584							    DRM_BUDDY_CONTIGUOUS_ALLOCATION),
585			       "buddy_alloc hit an error size=%lu\n", 2 * ps);
586
587	drm_buddy_free_list(&mm, &left, 0);
588	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, 0, mm_size,
589							    3 * ps, ps, &allocated,
590							    DRM_BUDDY_CONTIGUOUS_ALLOCATION),
591			       "buddy_alloc hit an error size=%lu\n", 3 * ps);
592
593	total = 0;
594	list_for_each_entry(block, &allocated, link)
595		total += drm_buddy_block_size(&mm, block);
596
597	KUNIT_ASSERT_EQ(test, total, ps * 2 + ps * 3);
598
599	drm_buddy_free_list(&mm, &allocated, 0);
600	drm_buddy_fini(&mm);
601}
602
603static void drm_test_buddy_alloc_pathological(struct kunit *test)
604{
605	u64 mm_size, size, start = 0;
606	struct drm_buddy_block *block;
607	const int max_order = 3;
608	unsigned long flags = 0;
609	int order, top;
610	struct drm_buddy mm;
611	LIST_HEAD(blocks);
612	LIST_HEAD(holes);
613	LIST_HEAD(tmp);
614
615	/*
616	 * Create a pot-sized mm, then allocate one of each possible
617	 * order within. This should leave the mm with exactly one
618	 * page left. Free the largest block, then whittle down again.
619	 * Eventually we will have a fully 50% fragmented mm.
620	 */
621
622	mm_size = SZ_4K << max_order;
623	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, SZ_4K),
624			       "buddy_init failed\n");
625
626	KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
627
628	for (top = max_order; top; top--) {
629		/* Make room by freeing the largest allocated block */
630		block = list_first_entry_or_null(&blocks, typeof(*block), link);
631		if (block) {
632			list_del(&block->link);
633			drm_buddy_free_block(&mm, block);
634		}
635
636		for (order = top; order--;) {
637			size = get_size(order, mm.chunk_size);
638			KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start,
639									    mm_size, size, size,
640										&tmp, flags),
641					"buddy_alloc hit -ENOMEM with order=%d, top=%d\n",
642					order, top);
643
644			block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
645			KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
646
647			list_move_tail(&block->link, &blocks);
648		}
649
650		/* There should be one final page for this sub-allocation */
651		size = get_size(0, mm.chunk_size);
652		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
653								    size, size, &tmp, flags),
654							   "buddy_alloc hit -ENOMEM for hole\n");
655
656		block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
657		KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
658
659		list_move_tail(&block->link, &holes);
660
661		size = get_size(top, mm.chunk_size);
662		KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
663								   size, size, &tmp, flags),
664							  "buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!",
665							  top, max_order);
666	}
667
668	drm_buddy_free_list(&mm, &holes, 0);
669
670	/* Nothing larger than blocks of chunk_size now available */
671	for (order = 1; order <= max_order; order++) {
672		size = get_size(order, mm.chunk_size);
673		KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
674								   size, size, &tmp, flags),
675							  "buddy_alloc unexpectedly succeeded at order %d, it should be full!",
676							  order);
677	}
678
679	list_splice_tail(&holes, &blocks);
680	drm_buddy_free_list(&mm, &blocks, 0);
681	drm_buddy_fini(&mm);
682}
683
684static void drm_test_buddy_alloc_pessimistic(struct kunit *test)
685{
686	u64 mm_size, size, start = 0;
687	struct drm_buddy_block *block, *bn;
688	const unsigned int max_order = 16;
689	unsigned long flags = 0;
690	struct drm_buddy mm;
691	unsigned int order;
692	LIST_HEAD(blocks);
693	LIST_HEAD(tmp);
694
695	/*
696	 * Create a pot-sized mm, then allocate one of each possible
697	 * order within. This should leave the mm with exactly one
698	 * page left.
699	 */
700
701	mm_size = SZ_4K << max_order;
702	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, SZ_4K),
703			       "buddy_init failed\n");
704
705	KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
706
707	for (order = 0; order < max_order; order++) {
708		size = get_size(order, mm.chunk_size);
709		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
710								    size, size, &tmp, flags),
711							   "buddy_alloc hit -ENOMEM with order=%d\n",
712							   order);
713
714		block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
715		KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
716
717		list_move_tail(&block->link, &blocks);
718	}
719
720	/* And now the last remaining block available */
721	size = get_size(0, mm.chunk_size);
722	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
723							    size, size, &tmp, flags),
724						   "buddy_alloc hit -ENOMEM on final alloc\n");
725
726	block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
727	KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
728
729	list_move_tail(&block->link, &blocks);
730
731	/* Should be completely full! */
732	for (order = max_order; order--;) {
733		size = get_size(order, mm.chunk_size);
734		KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
735								   size, size, &tmp, flags),
736							  "buddy_alloc unexpectedly succeeded, it should be full!");
737	}
738
739	block = list_last_entry(&blocks, typeof(*block), link);
740	list_del(&block->link);
741	drm_buddy_free_block(&mm, block);
742
743	/* As we free in increasing size, we make available larger blocks */
744	order = 1;
745	list_for_each_entry_safe(block, bn, &blocks, link) {
746		list_del(&block->link);
747		drm_buddy_free_block(&mm, block);
748
749		size = get_size(order, mm.chunk_size);
750		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
751								    size, size, &tmp, flags),
752							   "buddy_alloc hit -ENOMEM with order=%d\n",
753							   order);
754
755		block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
756		KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
757
758		list_del(&block->link);
759		drm_buddy_free_block(&mm, block);
760		order++;
761	}
762
763	/* To confirm, now the whole mm should be available */
764	size = get_size(max_order, mm.chunk_size);
765	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
766							    size, size, &tmp, flags),
767						   "buddy_alloc (realloc) hit -ENOMEM with order=%d\n",
768						   max_order);
769
770	block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
771	KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
772
773	list_del(&block->link);
774	drm_buddy_free_block(&mm, block);
775	drm_buddy_free_list(&mm, &blocks, 0);
776	drm_buddy_fini(&mm);
777}
778
779static void drm_test_buddy_alloc_optimistic(struct kunit *test)
780{
781	u64 mm_size, size, start = 0;
782	struct drm_buddy_block *block;
783	unsigned long flags = 0;
784	const int max_order = 16;
785	struct drm_buddy mm;
786	LIST_HEAD(blocks);
787	LIST_HEAD(tmp);
788	int order;
789
790	/*
791	 * Create a mm with one block of each order available, and
792	 * try to allocate them all.
793	 */
794
795	mm_size = SZ_4K * ((1 << (max_order + 1)) - 1);
796
797	KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_init(&mm, mm_size, SZ_4K),
798			       "buddy_init failed\n");
799
800	KUNIT_EXPECT_EQ(test, mm.max_order, max_order);
801
802	for (order = 0; order <= max_order; order++) {
803		size = get_size(order, mm.chunk_size);
804		KUNIT_ASSERT_FALSE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
805								    size, size, &tmp, flags),
806							   "buddy_alloc hit -ENOMEM with order=%d\n",
807							   order);
808
809		block = list_first_entry_or_null(&tmp, struct drm_buddy_block, link);
810		KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n");
811
812		list_move_tail(&block->link, &blocks);
813	}
814
815	/* Should be completely full! */
816	size = get_size(0, mm.chunk_size);
817	KUNIT_ASSERT_TRUE_MSG(test, drm_buddy_alloc_blocks(&mm, start, mm_size,
818							   size, size, &tmp, flags),
819						  "buddy_alloc unexpectedly succeeded, it should be full!");
820
821	drm_buddy_free_list(&mm, &blocks, 0);
822	drm_buddy_fini(&mm);
823}
824
825static void drm_test_buddy_alloc_limit(struct kunit *test)
826{
827	u64 size = U64_MAX, start = 0;
828	struct drm_buddy_block *block;
829	unsigned long flags = 0;
830	LIST_HEAD(allocated);
831	struct drm_buddy mm;
832
833	KUNIT_EXPECT_FALSE(test, drm_buddy_init(&mm, size, SZ_4K));
834
835	KUNIT_EXPECT_EQ_MSG(test, mm.max_order, DRM_BUDDY_MAX_ORDER,
836			    "mm.max_order(%d) != %d\n", mm.max_order,
837						DRM_BUDDY_MAX_ORDER);
838
839	size = mm.chunk_size << mm.max_order;
840	KUNIT_EXPECT_FALSE(test, drm_buddy_alloc_blocks(&mm, start, size, size,
841							mm.chunk_size, &allocated, flags));
842
843	block = list_first_entry_or_null(&allocated, struct drm_buddy_block, link);
844	KUNIT_EXPECT_TRUE(test, block);
845
846	KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_order(block), mm.max_order,
847			    "block order(%d) != %d\n",
848						drm_buddy_block_order(block), mm.max_order);
849
850	KUNIT_EXPECT_EQ_MSG(test, drm_buddy_block_size(&mm, block),
851			    BIT_ULL(mm.max_order) * mm.chunk_size,
852						"block size(%llu) != %llu\n",
853						drm_buddy_block_size(&mm, block),
854						BIT_ULL(mm.max_order) * mm.chunk_size);
855
856	drm_buddy_free_list(&mm, &allocated, 0);
857	drm_buddy_fini(&mm);
858}
859
860static int drm_buddy_suite_init(struct kunit_suite *suite)
861{
862	while (!random_seed)
863		random_seed = get_random_u32();
864
865	kunit_info(suite, "Testing DRM buddy manager, with random_seed=0x%x\n",
866		   random_seed);
867
868	return 0;
869}
870
871static struct kunit_case drm_buddy_tests[] = {
872	KUNIT_CASE(drm_test_buddy_alloc_limit),
873	KUNIT_CASE(drm_test_buddy_alloc_optimistic),
874	KUNIT_CASE(drm_test_buddy_alloc_pessimistic),
875	KUNIT_CASE(drm_test_buddy_alloc_pathological),
876	KUNIT_CASE(drm_test_buddy_alloc_contiguous),
877	KUNIT_CASE(drm_test_buddy_alloc_clear),
878	KUNIT_CASE(drm_test_buddy_alloc_range_bias),
879	KUNIT_CASE(drm_test_buddy_fragmentation_performance),
880	{}
881};
882
883static struct kunit_suite drm_buddy_test_suite = {
884	.name = "drm_buddy",
885	.suite_init = drm_buddy_suite_init,
886	.test_cases = drm_buddy_tests,
887};
888
889kunit_test_suite(drm_buddy_test_suite);
890
891MODULE_AUTHOR("Intel Corporation");
892MODULE_DESCRIPTION("Kunit test for drm_buddy functions");
893MODULE_LICENSE("GPL");