1	// SPDX-License-Identifier: GPL-2.0-only
2	/*
3	* Test cases for the drm_mm range manager
4	*
5	* Copyright (c) 2022 Arthur Grillo <arthur.grillo@usp.br>
6	*/
7
8	#include <kunit/test.h>
9
10	#include <linux/prime_numbers.h>
11	#include <linux/slab.h>
12	#include <linux/random.h>
13	#include <linux/vmalloc.h>
14	#include <linux/ktime.h>
15
16	#include <drm/drm_mm.h>
17
18	#include "../lib/drm_random.h"
19
20	static unsigned int random_seed;
21	static unsigned int max_iterations = 8192;
22	static unsigned int max_prime = 128;
23
24	enum {
25	BEST,
26	BOTTOMUP,
27	TOPDOWN,
28	EVICT,
29	};
30
31	static const struct insert_mode {
32	const char *name;
33	enum drm_mm_insert_mode mode;
34	} insert_modes[] = {
35	[BEST] = { .name: "best", .mode: DRM_MM_INSERT_BEST },
36	[BOTTOMUP] = { .name: "bottom-up", .mode: DRM_MM_INSERT_LOW },
37	[TOPDOWN] = { .name: "top-down", .mode: DRM_MM_INSERT_HIGH },
38	[EVICT] = { .name: "evict", .mode: DRM_MM_INSERT_EVICT },
39	{}
40	}, evict_modes[] = {
41	{ "bottom-up", DRM_MM_INSERT_LOW },
42	{ "top-down", DRM_MM_INSERT_HIGH },
43	{}
44	};
45
46	static bool assert_no_holes(struct kunit *test, const struct drm_mm *mm)
47	{
48	struct drm_mm_node *hole;
49	u64 hole_start, __always_unused hole_end;
50	unsigned long count;
51
52	count = 0;
53	drm_mm_for_each_hole(hole, mm, hole_start, hole_end)
54	count++;
55	if (count) {
56	KUNIT_FAIL(test,
57	"Expected to find no holes (after reserve), found %lu instead\n", count);
58	return false;
59	}
60
61	drm_mm_for_each_node(hole, mm) {
62	if (drm_mm_hole_follows(node: hole)) {
63	KUNIT_FAIL(test, "Hole follows node, expected none!\n");
64	return false;
65	}
66	}
67
68	return true;
69	}
70
71	static bool assert_one_hole(struct kunit *test, const struct drm_mm *mm, u64 start, u64 end)
72	{
73	struct drm_mm_node *hole;
74	u64 hole_start, hole_end;
75	unsigned long count;
76	bool ok = true;
77
78	if (end <= start)
79	return true;
80
81	count = 0;
82	drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
83	if (start != hole_start || end != hole_end) {
84	if (ok)
85	KUNIT_FAIL(test,
86	"empty mm has incorrect hole, found (%llx, %llx), expect (%llx, %llx)\n",
87	hole_start, hole_end, start, end);
88	ok = false;
89	}
90	count++;
91	}
92	if (count != 1) {
93	KUNIT_FAIL(test, "Expected to find one hole, found %lu instead\n", count);
94	ok = false;
95	}
96
97	return ok;
98	}
99
100	static bool assert_continuous(struct kunit *test, const struct drm_mm *mm, u64 size)
101	{
102	struct drm_mm_node *node, *check, *found;
103	unsigned long n;
104	u64 addr;
105
106	if (!assert_no_holes(test, mm))
107	return false;
108
109	n = 0;
110	addr = 0;
111	drm_mm_for_each_node(node, mm) {
112	if (node->start != addr) {
113	KUNIT_FAIL(test, "node[%ld] list out of order, expected %llx found %llx\n",
114	n, addr, node->start);
115	return false;
116	}
117
118	if (node->size != size) {
119	KUNIT_FAIL(test, "node[%ld].size incorrect, expected %llx, found %llx\n",
120	n, size, node->size);
121	return false;
122	}
123
124	if (drm_mm_hole_follows(node)) {
125	KUNIT_FAIL(test, "node[%ld] is followed by a hole!\n", n);
126	return false;
127	}
128
129	found = NULL;
130	drm_mm_for_each_node_in_range(check, mm, addr, addr + size) {
131	if (node != check) {
132	KUNIT_FAIL(test,
133	"lookup return wrong node, expected start %llx, found %llx\n",
134	node->start, check->start);
135	return false;
136	}
137	found = check;
138	}
139	if (!found) {
140	KUNIT_FAIL(test, "lookup failed for node %llx + %llx\n", addr, size);
141	return false;
142	}
143
144	addr += size;
145	n++;
146	}
147
148	return true;
149	}
150
151	static u64 misalignment(struct drm_mm_node *node, u64 alignment)
152	{
153	u64 rem;
154
155	if (!alignment)
156	return 0;
157
158	div64_u64_rem(dividend: node->start, divisor: alignment, remainder: &rem);
159	return rem;
160	}
161
162	static bool assert_node(struct kunit *test, struct drm_mm_node *node, struct drm_mm *mm,
163	u64 size, u64 alignment, unsigned long color)
164	{
165	bool ok = true;
166
167	if (!drm_mm_node_allocated(node) || node->mm != mm) {
168	KUNIT_FAIL(test, "node not allocated\n");
169	ok = false;
170	}
171
172	if (node->size != size) {
173	KUNIT_FAIL(test, "node has wrong size, found %llu, expected %llu\n",
174	node->size, size);
175	ok = false;
176	}
177
178	if (misalignment(node, alignment)) {
179	KUNIT_FAIL(test,
180	"node is misaligned, start %llx rem %llu, expected alignment %llu\n",
181	node->start, misalignment(node, alignment), alignment);
182	ok = false;
183	}
184
185	if (node->color != color) {
186	KUNIT_FAIL(test, "node has wrong color, found %lu, expected %lu\n",
187	node->color, color);
188	ok = false;
189	}
190
191	return ok;
192	}
193
194	static void drm_test_mm_init(struct kunit *test)
195	{
196	const unsigned int size = 4096;
197	struct drm_mm mm;
198	struct drm_mm_node tmp;
199
200	/* Start with some simple checks on initialising the struct drm_mm */
201	memset(&mm, 0, sizeof(mm));
202	KUNIT_ASSERT_FALSE_MSG(test, drm_mm_initialized(&mm),
203	"zeroed mm claims to be initialized\n");
204
205	memset(&mm, 0xff, sizeof(mm));
206	drm_mm_init(mm: &mm, start: 0, size);
207	if (!drm_mm_initialized(mm: &mm)) {
208	KUNIT_FAIL(test, "mm claims not to be initialized\n");
209	goto out;
210	}
211
212	if (!drm_mm_clean(mm: &mm)) {
213	KUNIT_FAIL(test, "mm not empty on creation\n");
214	goto out;
215	}
216
217	/* After creation, it should all be one massive hole */
218	if (!assert_one_hole(test, mm: &mm, start: 0, end: size)) {
219	KUNIT_FAIL(test, "");
220	goto out;
221	}
222
223	memset(&tmp, 0, sizeof(tmp));
224	tmp.start = 0;
225	tmp.size = size;
226	if (drm_mm_reserve_node(mm: &mm, node: &tmp)) {
227	KUNIT_FAIL(test, "failed to reserve whole drm_mm\n");
228	goto out;
229	}
230
231	/* After filling the range entirely, there should be no holes */
232	if (!assert_no_holes(test, mm: &mm)) {
233	KUNIT_FAIL(test, "");
234	goto out;
235	}
236
237	/* And then after emptying it again, the massive hole should be back */
238	drm_mm_remove_node(node: &tmp);
239	if (!assert_one_hole(test, mm: &mm, start: 0, end: size)) {
240	KUNIT_FAIL(test, "");
241	goto out;
242	}
243
244	out:
245	drm_mm_takedown(mm: &mm);
246	}
247
248	static void drm_test_mm_debug(struct kunit *test)
249	{
250	struct drm_mm mm;
251	struct drm_mm_node nodes[2];
252
253	/* Create a small drm_mm with a couple of nodes and a few holes, and
254	* check that the debug iterator doesn't explode over a trivial drm_mm.
255	*/
256
257	drm_mm_init(mm: &mm, start: 0, size: 4096);
258
259	memset(nodes, 0, sizeof(nodes));
260	nodes[0].start = 512;
261	nodes[0].size = 1024;
262	KUNIT_ASSERT_FALSE_MSG(test, drm_mm_reserve_node(&mm, &nodes[0]),
263	"failed to reserve node[0] {start=%lld, size=%lld)\n",
264	nodes[0].start, nodes[0].size);
265
266	nodes[1].size = 1024;
267	nodes[1].start = 4096 - 512 - nodes[1].size;
268	KUNIT_ASSERT_FALSE_MSG(test, drm_mm_reserve_node(&mm, &nodes[1]),
269	"failed to reserve node[0] {start=%lld, size=%lld)\n",
270	nodes[0].start, nodes[0].size);
271	}
272
273	static struct drm_mm_node *set_node(struct drm_mm_node *node,
274	u64 start, u64 size)
275	{
276	node->start = start;
277	node->size = size;
278	return node;
279	}
280
281	static bool expect_reserve_fail(struct kunit *test, struct drm_mm *mm, struct drm_mm_node *node)
282	{
283	int err;
284
285	err = drm_mm_reserve_node(mm, node);
286	if (likely(err == -ENOSPC))
287	return true;
288
289	if (!err) {
290	KUNIT_FAIL(test, "impossible reserve succeeded, node %llu + %llu\n",
291	node->start, node->size);
292	drm_mm_remove_node(node);
293	} else {
294	KUNIT_FAIL(test,
295	"impossible reserve failed with wrong error %d [expected %d], node %llu + %llu\n",
296	err, -ENOSPC, node->start, node->size);
297	}
298	return false;
299	}
300
301	static bool noinline_for_stack check_reserve_boundaries(struct kunit *test, struct drm_mm *mm,
302	unsigned int count,
303	u64 size)
304	{
305	const struct boundary {
306	u64 start, size;
307	const char *name;
308	} boundaries[] = {
309	#define B(st, sz) { (st), (sz), "{ " #st ", " #sz "}" }
310	B(0, 0),
311	B(-size, 0),
312	B(size, 0),
313	B(size * count, 0),
314	B(-size, size),
315	B(-size, -size),
316	B(-size, 2 * size),
317	B(0, -size),
318	B(size, -size),
319	B(count * size, size),
320	B(count * size, -size),
321	B(count * size, count * size),
322	B(count * size, -count * size),
323	B(count * size, -(count + 1) * size),
324	B((count + 1) * size, size),
325	B((count + 1) * size, -size),
326	B((count + 1) * size, -2 * size),
327	#undef B
328	};
329	struct drm_mm_node tmp = {};
330	int n;
331
332	for (n = 0; n < ARRAY_SIZE(boundaries); n++) {
333	if (!expect_reserve_fail(test, mm, node: set_node(node: &tmp, start: boundaries[n].start,
334	size: boundaries[n].size))) {
335	KUNIT_FAIL(test, "boundary[%d:%s] failed, count=%u, size=%lld\n",
336	n, boundaries[n].name, count, size);
337	return false;
338	}
339	}
340
341	return true;
342	}
343
344	static int __drm_test_mm_reserve(struct kunit *test, unsigned int count, u64 size)
345	{
346	DRM_RND_STATE(prng, random_seed);
347	struct drm_mm mm;
348	struct drm_mm_node tmp, *nodes, *node, *next;
349	unsigned int *order, n, m, o = 0;
350	int ret, err;
351
352	/* For exercising drm_mm_reserve_node(), we want to check that
353	* reservations outside of the drm_mm range are rejected, and to
354	* overlapping and otherwise already occupied ranges. Afterwards,
355	* the tree and nodes should be intact.
356	*/
357
358	DRM_MM_BUG_ON(!count);
359	DRM_MM_BUG_ON(!size);
360
361	ret = -ENOMEM;
362	order = drm_random_order(count, state: &prng);
363	if (!order)
364	goto err;
365
366	nodes = vzalloc(array_size(count, sizeof(*nodes)));
367	KUNIT_ASSERT_TRUE(test, nodes);
368
369	ret = -EINVAL;
370	drm_mm_init(mm: &mm, start: 0, size: count * size);
371
372	if (!check_reserve_boundaries(test, mm: &mm, count, size))
373	goto out;
374
375	for (n = 0; n < count; n++) {
376	nodes[n].start = order[n] * size;
377	nodes[n].size = size;
378
379	err = drm_mm_reserve_node(mm: &mm, node: &nodes[n]);
380	if (err) {
381	KUNIT_FAIL(test, "reserve failed, step %d, start %llu\n",
382	n, nodes[n].start);
383	ret = err;
384	goto out;
385	}
386
387	if (!drm_mm_node_allocated(node: &nodes[n])) {
388	KUNIT_FAIL(test, "reserved node not allocated! step %d, start %llu\n",
389	n, nodes[n].start);
390	goto out;
391	}
392
393	if (!expect_reserve_fail(test, mm: &mm, node: &nodes[n]))
394	goto out;
395	}
396
397	/* After random insertion the nodes should be in order */
398	if (!assert_continuous(test, mm: &mm, size))
399	goto out;
400
401	/* Repeated use should then fail */
402	drm_random_reorder(order, count, state: &prng);
403	for (n = 0; n < count; n++) {
404	if (!expect_reserve_fail(test, mm: &mm, node: set_node(node: &tmp, start: order[n] * size, size: 1)))
405	goto out;
406
407	/* Remove and reinsert should work */
408	drm_mm_remove_node(node: &nodes[order[n]]);
409	err = drm_mm_reserve_node(mm: &mm, node: &nodes[order[n]]);
410	if (err) {
411	KUNIT_FAIL(test, "reserve failed, step %d, start %llu\n",
412	n, nodes[n].start);
413	ret = err;
414	goto out;
415	}
416	}
417
418	if (!assert_continuous(test, mm: &mm, size))
419	goto out;
420
421	/* Overlapping use should then fail */
422	for (n = 0; n < count; n++) {
423	if (!expect_reserve_fail(test, mm: &mm, node: set_node(node: &tmp, start: 0, size: size * count)))
424	goto out;
425	}
426	for (n = 0; n < count; n++) {
427	if (!expect_reserve_fail(test, mm: &mm, node: set_node(node: &tmp, start: size * n, size: size * (count - n))))
428	goto out;
429	}
430
431	/* Remove several, reinsert, check full */
432	for_each_prime_number(n, min(max_prime, count)) {
433	for (m = 0; m < n; m++) {
434	node = &nodes[order[(o + m) % count]];
435	drm_mm_remove_node(node);
436	}
437
438	for (m = 0; m < n; m++) {
439	node = &nodes[order[(o + m) % count]];
440	err = drm_mm_reserve_node(mm: &mm, node);
441	if (err) {
442	KUNIT_FAIL(test, "reserve failed, step %d/%d, start %llu\n",
443	m, n, node->start);
444	ret = err;
445	goto out;
446	}
447	}
448
449	o += n;
450
451	if (!assert_continuous(test, mm: &mm, size))
452	goto out;
453	}
454
455	ret = 0;
456	out:
457	drm_mm_for_each_node_safe(node, next, &mm)
458	drm_mm_remove_node(node);
459	drm_mm_takedown(mm: &mm);
460	vfree(addr: nodes);
461	kfree(objp: order);
462	err:
463	return ret;
464	}
465
466	static void drm_test_mm_reserve(struct kunit *test)
467	{
468	const unsigned int count = min_t(unsigned int, BIT(10), max_iterations);
469	int n;
470
471	for_each_prime_number_from(n, 1, 54) {
472	u64 size = BIT_ULL(n);
473
474	KUNIT_ASSERT_FALSE(test, __drm_test_mm_reserve(test, count, size - 1));
475	KUNIT_ASSERT_FALSE(test, __drm_test_mm_reserve(test, count, size));
476	KUNIT_ASSERT_FALSE(test, __drm_test_mm_reserve(test, count, size + 1));
477
478	cond_resched();
479	}
480	}
481
482	static bool expect_insert(struct kunit *test, struct drm_mm *mm,
483	struct drm_mm_node *node, u64 size, u64 alignment, unsigned long color,
484	const struct insert_mode *mode)
485	{
486	int err;
487
488	err = drm_mm_insert_node_generic(mm, node,
489	size, alignment, color,
490	mode: mode->mode);
491	if (err) {
492	KUNIT_FAIL(test,
493	"insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n",
494	size, alignment, color, mode->name, err);
495	return false;
496	}
497
498	if (!assert_node(test, node, mm, size, alignment, color)) {
499	drm_mm_remove_node(node);
500	return false;
501	}
502
503	return true;
504	}
505
506	static bool expect_insert_fail(struct kunit *test, struct drm_mm *mm, u64 size)
507	{
508	struct drm_mm_node tmp = {};
509	int err;
510
511	err = drm_mm_insert_node(mm, node: &tmp, size);
512	if (likely(err == -ENOSPC))
513	return true;
514
515	if (!err) {
516	KUNIT_FAIL(test, "impossible insert succeeded, node %llu + %llu\n",
517	tmp.start, tmp.size);
518	drm_mm_remove_node(node: &tmp);
519	} else {
520	KUNIT_FAIL(test,
521	"impossible insert failed with wrong error %d [expected %d], size %llu\n",
522	err, -ENOSPC, size);
523	}
524	return false;
525	}
526
527	static int __drm_test_mm_insert(struct kunit *test, unsigned int count, u64 size, bool replace)
528	{
529	DRM_RND_STATE(prng, random_seed);
530	const struct insert_mode *mode;
531	struct drm_mm mm;
532	struct drm_mm_node *nodes, *node, *next;
533	unsigned int *order, n, m, o = 0;
534	int ret;
535
536	/* Fill a range with lots of nodes, check it doesn't fail too early */
537
538	DRM_MM_BUG_ON(!count);
539	DRM_MM_BUG_ON(!size);
540
541	ret = -ENOMEM;
542	nodes = vmalloc(array_size(count, sizeof(*nodes)));
543	KUNIT_ASSERT_TRUE(test, nodes);
544
545	order = drm_random_order(count, state: &prng);
546	if (!order)
547	goto err_nodes;
548
549	ret = -EINVAL;
550	drm_mm_init(mm: &mm, start: 0, size: count * size);
551
552	for (mode = insert_modes; mode->name; mode++) {
553	for (n = 0; n < count; n++) {
554	struct drm_mm_node tmp;
555
556	node = replace ? &tmp : &nodes[n];
557	memset(node, 0, sizeof(*node));
558	if (!expect_insert(test, mm: &mm, node, size, alignment: 0, color: n, mode)) {
559	KUNIT_FAIL(test, "%s insert failed, size %llu step %d\n",
560	mode->name, size, n);
561	goto out;
562	}
563
564	if (replace) {
565	drm_mm_replace_node(old: &tmp, new: &nodes[n]);
566	if (drm_mm_node_allocated(node: &tmp)) {
567	KUNIT_FAIL(test,
568	"replaced old-node still allocated! step %d\n",
569	n);
570	goto out;
571	}
572
573	if (!assert_node(test, node: &nodes[n], mm: &mm, size, alignment: 0, color: n)) {
574	KUNIT_FAIL(test,
575	"replaced node did not inherit parameters, size %llu step %d\n",
576	size, n);
577	goto out;
578	}
579
580	if (tmp.start != nodes[n].start) {
581	KUNIT_FAIL(test,
582	"replaced node mismatch location expected [%llx + %llx], found [%llx + %llx]\n",
583	tmp.start, size, nodes[n].start, nodes[n].size);
584	goto out;
585	}
586	}
587	}
588
589	/* After random insertion the nodes should be in order */
590	if (!assert_continuous(test, mm: &mm, size))
591	goto out;
592
593	/* Repeated use should then fail */
594	if (!expect_insert_fail(test, mm: &mm, size))
595	goto out;
596
597	/* Remove one and reinsert, as the only hole it should refill itself */
598	for (n = 0; n < count; n++) {
599	u64 addr = nodes[n].start;
600
601	drm_mm_remove_node(node: &nodes[n]);
602	if (!expect_insert(test, mm: &mm, node: &nodes[n], size, alignment: 0, color: n, mode)) {
603	KUNIT_FAIL(test, "%s reinsert failed, size %llu step %d\n",
604	mode->name, size, n);
605	goto out;
606	}
607
608	if (nodes[n].start != addr) {
609	KUNIT_FAIL(test,
610	"%s reinsert node moved, step %d, expected %llx, found %llx\n",
611	mode->name, n, addr, nodes[n].start);
612	goto out;
613	}
614
615	if (!assert_continuous(test, mm: &mm, size))
616	goto out;
617	}
618
619	/* Remove several, reinsert, check full */
620	for_each_prime_number(n, min(max_prime, count)) {
621	for (m = 0; m < n; m++) {
622	node = &nodes[order[(o + m) % count]];
623	drm_mm_remove_node(node);
624	}
625
626	for (m = 0; m < n; m++) {
627	node = &nodes[order[(o + m) % count]];
628	if (!expect_insert(test, mm: &mm, node, size, alignment: 0, color: n, mode)) {
629	KUNIT_FAIL(test,
630	"%s multiple reinsert failed, size %llu step %d\n",
631	mode->name, size, n);
632	goto out;
633	}
634	}
635
636	o += n;
637
638	if (!assert_continuous(test, mm: &mm, size))
639	goto out;
640
641	if (!expect_insert_fail(test, mm: &mm, size))
642	goto out;
643	}
644
645	drm_mm_for_each_node_safe(node, next, &mm)
646	drm_mm_remove_node(node);
647	DRM_MM_BUG_ON(!drm_mm_clean(&mm));
648
649	cond_resched();
650	}
651
652	ret = 0;
653	out:
654	drm_mm_for_each_node_safe(node, next, &mm)
655	drm_mm_remove_node(node);
656	drm_mm_takedown(mm: &mm);
657	kfree(objp: order);
658	err_nodes:
659	vfree(addr: nodes);
660	return ret;
661	}
662
663	static void drm_test_mm_insert(struct kunit *test)
664	{
665	const unsigned int count = min_t(unsigned int, BIT(10), max_iterations);
666	unsigned int n;
667
668	for_each_prime_number_from(n, 1, 54) {
669	u64 size = BIT_ULL(n);
670
671	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert(test, count, size - 1, false));
672	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert(test, count, size, false));
673	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert(test, count, size + 1, false));
674
675	cond_resched();
676	}
677	}
678
679	static void drm_test_mm_replace(struct kunit *test)
680	{
681	const unsigned int count = min_t(unsigned int, BIT(10), max_iterations);
682	unsigned int n;
683
684	/* Reuse __drm_test_mm_insert to exercise replacement by inserting a dummy node,
685	* then replacing it with the intended node. We want to check that
686	* the tree is intact and all the information we need is carried
687	* across to the target node.
688	*/
689
690	for_each_prime_number_from(n, 1, 54) {
691	u64 size = BIT_ULL(n);
692
693	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert(test, count, size - 1, true));
694	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert(test, count, size, true));
695	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert(test, count, size + 1, true));
696
697	cond_resched();
698	}
699	}
700
701	static bool expect_insert_in_range(struct kunit *test, struct drm_mm *mm, struct drm_mm_node *node,
702	u64 size, u64 alignment, unsigned long color,
703	u64 range_start, u64 range_end, const struct insert_mode *mode)
704	{
705	int err;
706
707	err = drm_mm_insert_node_in_range(mm, node,
708	size, alignment, color,
709	start: range_start, end: range_end,
710	mode: mode->mode);
711	if (err) {
712	KUNIT_FAIL(test,
713	"insert (size=%llu, alignment=%llu, color=%lu, mode=%s) nto range [%llx, %llx] failed with err=%d\n",
714	size, alignment, color, mode->name,
715	range_start, range_end, err);
716	return false;
717	}
718
719	if (!assert_node(test, node, mm, size, alignment, color)) {
720	drm_mm_remove_node(node);
721	return false;
722	}
723
724	return true;
725	}
726
727	static bool expect_insert_in_range_fail(struct kunit *test, struct drm_mm *mm,
728	u64 size, u64 range_start, u64 range_end)
729	{
730	struct drm_mm_node tmp = {};
731	int err;
732
733	err = drm_mm_insert_node_in_range(mm, node: &tmp, size, alignment: 0, color: 0, start: range_start, end: range_end,
734	mode: 0);
735	if (likely(err == -ENOSPC))
736	return true;
737
738	if (!err) {
739	KUNIT_FAIL(test,
740	"impossible insert succeeded, node %llx + %llu, range [%llx, %llx]\n",
741	tmp.start, tmp.size, range_start, range_end);
742	drm_mm_remove_node(node: &tmp);
743	} else {
744	KUNIT_FAIL(test,
745	"impossible insert failed with wrong error %d [expected %d], size %llu, range [%llx, %llx]\n",
746	err, -ENOSPC, size, range_start, range_end);
747	}
748
749	return false;
750	}
751
752	static bool assert_contiguous_in_range(struct kunit *test, struct drm_mm *mm,
753	u64 size, u64 start, u64 end)
754	{
755	struct drm_mm_node *node;
756	unsigned int n;
757
758	if (!expect_insert_in_range_fail(test, mm, size, range_start: start, range_end: end))
759	return false;
760
761	n = div64_u64(dividend: start + size - 1, divisor: size);
762	drm_mm_for_each_node(node, mm) {
763	if (node->start < start || node->start + node->size > end) {
764	KUNIT_FAIL(test,
765	"node %d out of range, address [%llx + %llu], range [%llx, %llx]\n",
766	n, node->start, node->start + node->size, start, end);
767	return false;
768	}
769
770	if (node->start != n * size) {
771	KUNIT_FAIL(test, "node %d out of order, expected start %llx, found %llx\n",
772	n, n * size, node->start);
773	return false;
774	}
775
776	if (node->size != size) {
777	KUNIT_FAIL(test, "node %d has wrong size, expected size %llx, found %llx\n",
778	n, size, node->size);
779	return false;
780	}
781
782	if (drm_mm_hole_follows(node) && drm_mm_hole_node_end(hole_node: node) < end) {
783	KUNIT_FAIL(test, "node %d is followed by a hole!\n", n);
784	return false;
785	}
786
787	n++;
788	}
789
790	if (start > 0) {
791	node = __drm_mm_interval_first(mm, start: 0, last: start - 1);
792	if (drm_mm_node_allocated(node)) {
793	KUNIT_FAIL(test, "node before start: node=%llx+%llu, start=%llx\n",
794	node->start, node->size, start);
795	return false;
796	}
797	}
798
799	if (end < U64_MAX) {
800	node = __drm_mm_interval_first(mm, start: end, U64_MAX);
801	if (drm_mm_node_allocated(node)) {
802	KUNIT_FAIL(test, "node after end: node=%llx+%llu, end=%llx\n",
803	node->start, node->size, end);
804	return false;
805	}
806	}
807
808	return true;
809	}
810
811	static int __drm_test_mm_insert_range(struct kunit *test, unsigned int count, u64 size,
812	u64 start, u64 end)
813	{
814	const struct insert_mode *mode;
815	struct drm_mm mm;
816	struct drm_mm_node *nodes, *node, *next;
817	unsigned int n, start_n, end_n;
818	int ret;
819
820	DRM_MM_BUG_ON(!count);
821	DRM_MM_BUG_ON(!size);
822	DRM_MM_BUG_ON(end <= start);
823
824	/* Very similar to __drm_test_mm_insert(), but now instead of populating the
825	* full range of the drm_mm, we try to fill a small portion of it.
826	*/
827
828	ret = -ENOMEM;
829	nodes = vzalloc(array_size(count, sizeof(*nodes)));
830	KUNIT_ASSERT_TRUE(test, nodes);
831
832	ret = -EINVAL;
833	drm_mm_init(mm: &mm, start: 0, size: count * size);
834
835	start_n = div64_u64(dividend: start + size - 1, divisor: size);
836	end_n = div64_u64(dividend: end - size, divisor: size);
837
838	for (mode = insert_modes; mode->name; mode++) {
839	for (n = start_n; n <= end_n; n++) {
840	if (!expect_insert_in_range(test, mm: &mm, node: &nodes[n], size, alignment: size, color: n,
841	range_start: start, range_end: end, mode)) {
842	KUNIT_FAIL(test,
843	"%s insert failed, size %llu, step %d [%d, %d], range [%llx, %llx]\n",
844	mode->name, size, n, start_n, end_n, start, end);
845	goto out;
846	}
847	}
848
849	if (!assert_contiguous_in_range(test, mm: &mm, size, start, end)) {
850	KUNIT_FAIL(test,
851	"%s: range [%llx, %llx] not full after initialisation, size=%llu\n",
852	mode->name, start, end, size);
853	goto out;
854	}
855
856	/* Remove one and reinsert, it should refill itself */
857	for (n = start_n; n <= end_n; n++) {
858	u64 addr = nodes[n].start;
859
860	drm_mm_remove_node(node: &nodes[n]);
861	if (!expect_insert_in_range(test, mm: &mm, node: &nodes[n], size, alignment: size, color: n,
862	range_start: start, range_end: end, mode)) {
863	KUNIT_FAIL(test, "%s reinsert failed, step %d\n", mode->name, n);
864	goto out;
865	}
866
867	if (nodes[n].start != addr) {
868	KUNIT_FAIL(test,
869	"%s reinsert node moved, step %d, expected %llx, found %llx\n",
870	mode->name, n, addr, nodes[n].start);
871	goto out;
872	}
873	}
874
875	if (!assert_contiguous_in_range(test, mm: &mm, size, start, end)) {
876	KUNIT_FAIL(test,
877	"%s: range [%llx, %llx] not full after reinsertion, size=%llu\n",
878	mode->name, start, end, size);
879	goto out;
880	}
881
882	drm_mm_for_each_node_safe(node, next, &mm)
883	drm_mm_remove_node(node);
884	DRM_MM_BUG_ON(!drm_mm_clean(&mm));
885
886	cond_resched();
887	}
888
889	ret = 0;
890	out:
891	drm_mm_for_each_node_safe(node, next, &mm)
892	drm_mm_remove_node(node);
893	drm_mm_takedown(mm: &mm);
894	vfree(addr: nodes);
895	return ret;
896	}
897
898	static int insert_outside_range(struct kunit *test)
899	{
900	struct drm_mm mm;
901	const unsigned int start = 1024;
902	const unsigned int end = 2048;
903	const unsigned int size = end - start;
904
905	drm_mm_init(mm: &mm, start, size);
906
907	if (!expect_insert_in_range_fail(test, mm: &mm, size: 1, range_start: 0, range_end: start))
908	return -EINVAL;
909
910	if (!expect_insert_in_range_fail(test, mm: &mm, size,
911	range_start: start - size / 2, range_end: start + (size + 1) / 2))
912	return -EINVAL;
913
914	if (!expect_insert_in_range_fail(test, mm: &mm, size,
915	range_start: end - (size + 1) / 2, range_end: end + size / 2))
916	return -EINVAL;
917
918	if (!expect_insert_in_range_fail(test, mm: &mm, size: 1, range_start: end, range_end: end + size))
919	return -EINVAL;
920
921	drm_mm_takedown(mm: &mm);
922	return 0;
923	}
924
925	static void drm_test_mm_insert_range(struct kunit *test)
926	{
927	const unsigned int count = min_t(unsigned int, BIT(13), max_iterations);
928	unsigned int n;
929
930	/* Check that requests outside the bounds of drm_mm are rejected. */
931	KUNIT_ASSERT_FALSE(test, insert_outside_range(test));
932
933	for_each_prime_number_from(n, 1, 50) {
934	const u64 size = BIT_ULL(n);
935	const u64 max = count * size;
936
937	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert_range(test, count, size, 0, max));
938	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert_range(test, count, size, 1, max));
939	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert_range(test, count, size, 0, max - 1));
940	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert_range(test, count, size, 0, max / 2));
941	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert_range(test, count, size,
942	max / 2, max));
943	KUNIT_ASSERT_FALSE(test, __drm_test_mm_insert_range(test, count, size,
944	max / 4 + 1, 3 * max / 4 - 1));
945
946	cond_resched();
947	}
948	}
949
950	static int prepare_frag(struct kunit *test, struct drm_mm *mm, struct drm_mm_node *nodes,
951	unsigned int num_insert, const struct insert_mode *mode)
952	{
953	unsigned int size = 4096;
954	unsigned int i;
955
956	for (i = 0; i < num_insert; i++) {
957	if (!expect_insert(test, mm, node: &nodes[i], size, alignment: 0, color: i, mode) != 0) {
958	KUNIT_FAIL(test, "%s insert failed\n", mode->name);
959	return -EINVAL;
960	}
961	}
962
963	/* introduce fragmentation by freeing every other node */
964	for (i = 0; i < num_insert; i++) {
965	if (i % 2 == 0)
966	drm_mm_remove_node(node: &nodes[i]);
967	}
968
969	return 0;
970	}
971
972	static u64 get_insert_time(struct kunit *test, struct drm_mm *mm,
973	unsigned int num_insert, struct drm_mm_node *nodes,
974	const struct insert_mode *mode)
975	{
976	unsigned int size = 8192;
977	ktime_t start;
978	unsigned int i;
979
980	start = ktime_get();
981	for (i = 0; i < num_insert; i++) {
982	if (!expect_insert(test, mm, node: &nodes[i], size, alignment: 0, color: i, mode) != 0) {
983	KUNIT_FAIL(test, "%s insert failed\n", mode->name);
984	return 0;
985	}
986	}
987
988	return ktime_to_ns(ktime_sub(ktime_get(), start));
989	}
990
991	static void drm_test_mm_frag(struct kunit *test)
992	{
993	struct drm_mm mm;
994	const struct insert_mode *mode;
995	struct drm_mm_node *nodes, *node, *next;
996	unsigned int insert_size = 10000;
997	unsigned int scale_factor = 4;
998
999	/* We need 4 * insert_size nodes to hold intermediate allocated
1000	* drm_mm nodes.
1001	* 1 times for prepare_frag()
1002	* 1 times for get_insert_time()
1003	* 2 times for get_insert_time()
1004	*/
1005	nodes = vzalloc(array_size(insert_size * 4, sizeof(*nodes)));
1006	KUNIT_ASSERT_TRUE(test, nodes);
1007
1008	/* For BOTTOMUP and TOPDOWN, we first fragment the
1009	* address space using prepare_frag() and then try to verify
1010	* that insertions scale quadratically from 10k to 20k insertions
1011	*/
1012	drm_mm_init(mm: &mm, start: 1, U64_MAX - 2);
1013	for (mode = insert_modes; mode->name; mode++) {
1014	u64 insert_time1, insert_time2;
1015
1016	if (mode->mode != DRM_MM_INSERT_LOW &&
1017	mode->mode != DRM_MM_INSERT_HIGH)
1018	continue;
1019
1020	if (prepare_frag(test, mm: &mm, nodes, num_insert: insert_size, mode))
1021	goto err;
1022
1023	insert_time1 = get_insert_time(test, mm: &mm, num_insert: insert_size,
1024	nodes: nodes + insert_size, mode);
1025	if (insert_time1 == 0)
1026	goto err;
1027
1028	insert_time2 = get_insert_time(test, mm: &mm, num_insert: (insert_size * 2),
1029	nodes: nodes + insert_size * 2, mode);
1030	if (insert_time2 == 0)
1031	goto err;
1032
1033	kunit_info(test, "%s fragmented insert of %u and %u insertions took %llu and %llu nsecs\n",
1034	mode->name, insert_size, insert_size * 2, insert_time1, insert_time2);
1035
1036	if (insert_time2 > (scale_factor * insert_time1)) {
1037	KUNIT_FAIL(test, "%s fragmented insert took %llu nsecs more\n",
1038	mode->name, insert_time2 - (scale_factor * insert_time1));
1039	goto err;
1040	}
1041
1042	drm_mm_for_each_node_safe(node, next, &mm)
1043	drm_mm_remove_node(node);
1044	}
1045
1046	err:
1047	drm_mm_for_each_node_safe(node, next, &mm)
1048	drm_mm_remove_node(node);
1049	drm_mm_takedown(mm: &mm);
1050	vfree(addr: nodes);
1051	}
1052
1053	static void drm_test_mm_align(struct kunit *test)
1054	{
1055	const struct insert_mode *mode;
1056	const unsigned int max_count = min(8192u, max_prime);
1057	struct drm_mm mm;
1058	struct drm_mm_node *nodes, *node, *next;
1059	unsigned int prime;
1060
1061	/* For each of the possible insertion modes, we pick a few
1062	* arbitrary alignments and check that the inserted node
1063	* meets our requirements.
1064	*/
1065
1066	nodes = vzalloc(array_size(max_count, sizeof(*nodes)));
1067	KUNIT_ASSERT_TRUE(test, nodes);
1068
1069	drm_mm_init(mm: &mm, start: 1, U64_MAX - 2);
1070
1071	for (mode = insert_modes; mode->name; mode++) {
1072	unsigned int i = 0;
1073
1074	for_each_prime_number_from(prime, 1, max_count) {
1075	u64 size = next_prime_number(x: prime);
1076
1077	if (!expect_insert(test, mm: &mm, node: &nodes[i], size, alignment: prime, color: i, mode)) {
1078	KUNIT_FAIL(test, "%s insert failed with alignment=%d",
1079	mode->name, prime);
1080	goto out;
1081	}
1082
1083	i++;
1084	}
1085
1086	drm_mm_for_each_node_safe(node, next, &mm)
1087	drm_mm_remove_node(node);
1088	DRM_MM_BUG_ON(!drm_mm_clean(&mm));
1089
1090	cond_resched();
1091	}
1092
1093	out:
1094	drm_mm_for_each_node_safe(node, next, &mm)
1095	drm_mm_remove_node(node);
1096	drm_mm_takedown(mm: &mm);
1097	vfree(addr: nodes);
1098	}
1099
1100	static void drm_test_mm_align_pot(struct kunit *test, int max)
1101	{
1102	struct drm_mm mm;
1103	struct drm_mm_node *node, *next;
1104	int bit;
1105
1106	/* Check that we can align to the full u64 address space */
1107
1108	drm_mm_init(mm: &mm, start: 1, U64_MAX - 2);
1109
1110	for (bit = max - 1; bit; bit--) {
1111	u64 align, size;
1112
1113	node = kzalloc(size: sizeof(*node), GFP_KERNEL);
1114	if (!node) {
1115	KUNIT_FAIL(test, "failed to allocate node");
1116	goto out;
1117	}
1118
1119	align = BIT_ULL(bit);
1120	size = BIT_ULL(bit - 1) + 1;
1121	if (!expect_insert(test, mm: &mm, node, size, alignment: align, color: bit, mode: &insert_modes[0])) {
1122	KUNIT_FAIL(test, "insert failed with alignment=%llx [%d]", align, bit);
1123	goto out;
1124	}
1125
1126	cond_resched();
1127	}
1128
1129	out:
1130	drm_mm_for_each_node_safe(node, next, &mm) {
1131	drm_mm_remove_node(node);
1132	kfree(objp: node);
1133	}
1134	drm_mm_takedown(mm: &mm);
1135	}
1136
1137	static void drm_test_mm_align32(struct kunit *test)
1138	{
1139	drm_test_mm_align_pot(test, max: 32);
1140	}
1141
1142	static void drm_test_mm_align64(struct kunit *test)
1143	{
1144	drm_test_mm_align_pot(test, max: 64);
1145	}
1146
1147	static void show_scan(struct kunit *test, const struct drm_mm_scan *scan)
1148	{
1149	kunit_info(test, "scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n",
1150	scan->hit_start, scan->hit_end, scan->size, scan->alignment, scan->color);
1151	}
1152
1153	static void show_holes(struct kunit *test, const struct drm_mm *mm, int count)
1154	{
1155	u64 hole_start, hole_end;
1156	struct drm_mm_node *hole;
1157
1158	drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
1159	struct drm_mm_node *next = list_next_entry(hole, node_list);
1160	const char *node1 = NULL, *node2 = NULL;
1161
1162	if (drm_mm_node_allocated(node: hole))
1163	node1 = kasprintf(GFP_KERNEL, fmt: "[%llx + %lld, color=%ld], ",
1164	hole->start, hole->size, hole->color);
1165
1166	if (drm_mm_node_allocated(node: next))
1167	node2 = kasprintf(GFP_KERNEL, fmt: ", [%llx + %lld, color=%ld]",
1168	next->start, next->size, next->color);
1169
1170	kunit_info(test, "%sHole [%llx - %llx, size %lld]%s\n", node1,
1171	hole_start, hole_end, hole_end - hole_start, node2);
1172
1173	kfree(objp: node2);
1174	kfree(objp: node1);
1175
1176	if (!--count)
1177	break;
1178	}
1179	}
1180
1181	struct evict_node {
1182	struct drm_mm_node node;
1183	struct list_head link;
1184	};
1185
1186	static bool evict_nodes(struct kunit *test, struct drm_mm_scan *scan,
1187	struct evict_node *nodes, unsigned int *order, unsigned int count,
1188	bool use_color, struct list_head *evict_list)
1189	{
1190	struct evict_node *e, *en;
1191	unsigned int i;
1192
1193	for (i = 0; i < count; i++) {
1194	e = &nodes[order ? order[i] : i];
1195	list_add(new: &e->link, head: evict_list);
1196	if (drm_mm_scan_add_block(scan, node: &e->node))
1197	break;
1198	}
1199	list_for_each_entry_safe(e, en, evict_list, link) {
1200	if (!drm_mm_scan_remove_block(scan, node: &e->node))
1201	list_del(entry: &e->link);
1202	}
1203	if (list_empty(head: evict_list)) {
1204	KUNIT_FAIL(test,
1205	"Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n",
1206	scan->size, count, scan->alignment, scan->color);
1207	return false;
1208	}
1209
1210	list_for_each_entry(e, evict_list, link)
1211	drm_mm_remove_node(node: &e->node);
1212
1213	if (use_color) {
1214	struct drm_mm_node *node;
1215
1216	while ((node = drm_mm_scan_color_evict(scan))) {
1217	e = container_of(node, typeof(*e), node);
1218	drm_mm_remove_node(node: &e->node);
1219	list_add(new: &e->link, head: evict_list);
1220	}
1221	} else {
1222	if (drm_mm_scan_color_evict(scan)) {
1223	KUNIT_FAIL(test,
1224	"drm_mm_scan_color_evict unexpectedly reported overlapping nodes!\n");
1225	return false;
1226	}
1227	}
1228
1229	return true;
1230	}
1231
1232	static bool evict_nothing(struct kunit *test, struct drm_mm *mm,
1233	unsigned int total_size, struct evict_node *nodes)
1234	{
1235	struct drm_mm_scan scan;
1236	LIST_HEAD(evict_list);
1237	struct evict_node *e;
1238	struct drm_mm_node *node;
1239	unsigned int n;
1240
1241	drm_mm_scan_init(scan: &scan, mm, size: 1, alignment: 0, color: 0, mode: 0);
1242	for (n = 0; n < total_size; n++) {
1243	e = &nodes[n];
1244	list_add(new: &e->link, head: &evict_list);
1245	drm_mm_scan_add_block(scan: &scan, node: &e->node);
1246	}
1247	list_for_each_entry(e, &evict_list, link)
1248	drm_mm_scan_remove_block(scan: &scan, node: &e->node);
1249
1250	for (n = 0; n < total_size; n++) {
1251	e = &nodes[n];
1252
1253	if (!drm_mm_node_allocated(node: &e->node)) {
1254	KUNIT_FAIL(test, "node[%d] no longer allocated!\n", n);
1255	return false;
1256	}
1257
1258	e->link.next = NULL;
1259	}
1260
1261	drm_mm_for_each_node(node, mm) {
1262	e = container_of(node, typeof(*e), node);
1263	e->link.next = &e->link;
1264	}
1265
1266	for (n = 0; n < total_size; n++) {
1267	e = &nodes[n];
1268
1269	if (!e->link.next) {
1270	KUNIT_FAIL(test, "node[%d] no longer connected!\n", n);
1271	return false;
1272	}
1273	}
1274
1275	return assert_continuous(test, mm, size: nodes[0].node.size);
1276	}
1277
1278	static bool evict_everything(struct kunit *test, struct drm_mm *mm,
1279	unsigned int total_size, struct evict_node *nodes)
1280	{
1281	struct drm_mm_scan scan;
1282	LIST_HEAD(evict_list);
1283	struct evict_node *e;
1284	unsigned int n;
1285	int err;
1286
1287	drm_mm_scan_init(scan: &scan, mm, size: total_size, alignment: 0, color: 0, mode: 0);
1288	for (n = 0; n < total_size; n++) {
1289	e = &nodes[n];
1290	list_add(new: &e->link, head: &evict_list);
1291	if (drm_mm_scan_add_block(scan: &scan, node: &e->node))
1292	break;
1293	}
1294
1295	err = 0;
1296	list_for_each_entry(e, &evict_list, link) {
1297	if (!drm_mm_scan_remove_block(scan: &scan, node: &e->node)) {
1298	if (!err) {
1299	KUNIT_FAIL(test, "Node %lld not marked for eviction!\n",
1300	e->node.start);
1301	err = -EINVAL;
1302	}
1303	}
1304	}
1305	if (err)
1306	return false;
1307
1308	list_for_each_entry(e, &evict_list, link)
1309	drm_mm_remove_node(node: &e->node);
1310
1311	if (!assert_one_hole(test, mm, start: 0, end: total_size))
1312	return false;
1313
1314	list_for_each_entry(e, &evict_list, link) {
1315	err = drm_mm_reserve_node(mm, node: &e->node);
1316	if (err) {
1317	KUNIT_FAIL(test, "Failed to reinsert node after eviction: start=%llx\n",
1318	e->node.start);
1319	return false;
1320	}
1321	}
1322
1323	return assert_continuous(test, mm, size: nodes[0].node.size);
1324	}
1325
1326	static int evict_something(struct kunit *test, struct drm_mm *mm,
1327	u64 range_start, u64 range_end, struct evict_node *nodes,
1328	unsigned int *order, unsigned int count, unsigned int size,
1329	unsigned int alignment, const struct insert_mode *mode)
1330	{
1331	struct drm_mm_scan scan;
1332	LIST_HEAD(evict_list);
1333	struct evict_node *e;
1334	struct drm_mm_node tmp;
1335	int err;
1336
1337	drm_mm_scan_init_with_range(scan: &scan, mm, size, alignment, color: 0, start: range_start,
1338	end: range_end, mode: mode->mode);
1339	if (!evict_nodes(test, scan: &scan, nodes, order, count, use_color: false, evict_list: &evict_list))
1340	return -EINVAL;
1341
1342	memset(&tmp, 0, sizeof(tmp));
1343	err = drm_mm_insert_node_generic(mm, node: &tmp, size, alignment, color: 0,
1344	mode: DRM_MM_INSERT_EVICT);
1345	if (err) {
1346	KUNIT_FAIL(test, "Failed to insert into eviction hole: size=%d, align=%d\n",
1347	size, alignment);
1348	show_scan(test, scan: &scan);
1349	show_holes(test, mm, count: 3);
1350	return err;
1351	}
1352
1353	if (tmp.start < range_start || tmp.start + tmp.size > range_end) {
1354	KUNIT_FAIL(test,
1355	"Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
1356	tmp.start, tmp.size, range_start, range_end);
1357	err = -EINVAL;
1358	}
1359
1360	if (!assert_node(test, node: &tmp, mm, size, alignment, color: 0) ||
1361	drm_mm_hole_follows(node: &tmp)) {
1362	KUNIT_FAIL(test,
1363	"Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n",
1364	tmp.size, size, alignment, misalignment(&tmp, alignment),
1365	tmp.start, drm_mm_hole_follows(&tmp));
1366	err = -EINVAL;
1367	}
1368
1369	drm_mm_remove_node(node: &tmp);
1370	if (err)
1371	return err;
1372
1373	list_for_each_entry(e, &evict_list, link) {
1374	err = drm_mm_reserve_node(mm, node: &e->node);
1375	if (err) {
1376	KUNIT_FAIL(test, "Failed to reinsert node after eviction: start=%llx\n",
1377	e->node.start);
1378	return err;
1379	}
1380	}
1381
1382	if (!assert_continuous(test, mm, size: nodes[0].node.size)) {
1383	KUNIT_FAIL(test, "range is no longer continuous\n");
1384	return -EINVAL;
1385	}
1386
1387	return 0;
1388	}
1389
1390	static void drm_test_mm_evict(struct kunit *test)
1391	{
1392	DRM_RND_STATE(prng, random_seed);
1393	const unsigned int size = 8192;
1394	const struct insert_mode *mode;
1395	struct drm_mm mm;
1396	struct evict_node *nodes;
1397	struct drm_mm_node *node, *next;
1398	unsigned int *order, n;
1399
1400	/* Here we populate a full drm_mm and then try and insert a new node
1401	* by evicting other nodes in a random order. The drm_mm_scan should
1402	* pick the first matching hole it finds from the random list. We
1403	* repeat that for different allocation strategies, alignments and
1404	* sizes to try and stress the hole finder.
1405	*/
1406
1407	nodes = vzalloc(array_size(size, sizeof(*nodes)));
1408	KUNIT_ASSERT_TRUE(test, nodes);
1409
1410	order = drm_random_order(count: size, state: &prng);
1411	if (!order)
1412	goto err_nodes;
1413
1414	drm_mm_init(mm: &mm, start: 0, size);
1415	for (n = 0; n < size; n++) {
1416	if (drm_mm_insert_node(mm: &mm, node: &nodes[n].node, size: 1)) {
1417	KUNIT_FAIL(test, "insert failed, step %d\n", n);
1418	goto out;
1419	}
1420	}
1421
1422	/* First check that using the scanner doesn't break the mm */
1423	if (!evict_nothing(test, mm: &mm, total_size: size, nodes)) {
1424	KUNIT_FAIL(test, "evict_nothing() failed\n");
1425	goto out;
1426	}
1427	if (!evict_everything(test, mm: &mm, total_size: size, nodes)) {
1428	KUNIT_FAIL(test, "evict_everything() failed\n");
1429	goto out;
1430	}
1431
1432	for (mode = evict_modes; mode->name; mode++) {
1433	for (n = 1; n <= size; n <<= 1) {
1434	drm_random_reorder(order, count: size, state: &prng);
1435	if (evict_something(test, mm: &mm, range_start: 0, U64_MAX, nodes, order, count: size, size: n, alignment: 1,
1436	mode)) {
1437	KUNIT_FAIL(test, "%s evict_something(size=%u) failed\n",
1438	mode->name, n);
1439	goto out;
1440	}
1441	}
1442
1443	for (n = 1; n < size; n <<= 1) {
1444	drm_random_reorder(order, count: size, state: &prng);
1445	if (evict_something(test, mm: &mm, range_start: 0, U64_MAX, nodes, order, count: size,
1446	size: size / 2, alignment: n, mode)) {
1447	KUNIT_FAIL(test,
1448	"%s evict_something(size=%u, alignment=%u) failed\n",
1449	mode->name, size / 2, n);
1450	goto out;
1451	}
1452	}
1453
1454	for_each_prime_number_from(n, 1, min(size, max_prime)) {
1455	unsigned int nsize = (size - n + 1) / 2;
1456
1457	DRM_MM_BUG_ON(!nsize);
1458
1459	drm_random_reorder(order, count: size, state: &prng);
1460	if (evict_something(test, mm: &mm, range_start: 0, U64_MAX, nodes, order, count: size,
1461	size: nsize, alignment: n, mode)) {
1462	KUNIT_FAIL(test,
1463	"%s evict_something(size=%u, alignment=%u) failed\n",
1464	mode->name, nsize, n);
1465	goto out;
1466	}
1467	}
1468
1469	cond_resched();
1470	}
1471
1472	out:
1473	drm_mm_for_each_node_safe(node, next, &mm)
1474	drm_mm_remove_node(node);
1475	drm_mm_takedown(mm: &mm);
1476	kfree(objp: order);
1477	err_nodes:
1478	vfree(addr: nodes);
1479	}
1480
1481	static void drm_test_mm_evict_range(struct kunit *test)
1482	{
1483	DRM_RND_STATE(prng, random_seed);
1484	const unsigned int size = 8192;
1485	const unsigned int range_size = size / 2;
1486	const unsigned int range_start = size / 4;
1487	const unsigned int range_end = range_start + range_size;
1488	const struct insert_mode *mode;
1489	struct drm_mm mm;
1490	struct evict_node *nodes;
1491	struct drm_mm_node *node, *next;
1492	unsigned int *order, n;
1493
1494	/* Like drm_test_mm_evict() but now we are limiting the search to a
1495	* small portion of the full drm_mm.
1496	*/
1497
1498	nodes = vzalloc(array_size(size, sizeof(*nodes)));
1499	KUNIT_ASSERT_TRUE(test, nodes);
1500
1501	order = drm_random_order(count: size, state: &prng);
1502	if (!order)
1503	goto err_nodes;
1504
1505	drm_mm_init(mm: &mm, start: 0, size);
1506	for (n = 0; n < size; n++) {
1507	if (drm_mm_insert_node(mm: &mm, node: &nodes[n].node, size: 1)) {
1508	KUNIT_FAIL(test, "insert failed, step %d\n", n);
1509	goto out;
1510	}
1511	}
1512
1513	for (mode = evict_modes; mode->name; mode++) {
1514	for (n = 1; n <= range_size; n <<= 1) {
1515	drm_random_reorder(order, count: size, state: &prng);
1516	if (evict_something(test, mm: &mm, range_start, range_end, nodes,
1517	order, count: size, size: n, alignment: 1, mode)) {
1518	KUNIT_FAIL(test,
1519	"%s evict_something(size=%u) failed with range [%u, %u]\n",
1520	mode->name, n, range_start, range_end);
1521	goto out;
1522	}
1523	}
1524
1525	for (n = 1; n <= range_size; n <<= 1) {
1526	drm_random_reorder(order, count: size, state: &prng);
1527	if (evict_something(test, mm: &mm, range_start, range_end, nodes,
1528	order, count: size, size: range_size / 2, alignment: n, mode)) {
1529	KUNIT_FAIL(test,
1530	"%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
1531	mode->name, range_size / 2, n, range_start, range_end);
1532	goto out;
1533	}
1534	}
1535
1536	for_each_prime_number_from(n, 1, min(range_size, max_prime)) {
1537	unsigned int nsize = (range_size - n + 1) / 2;
1538
1539	DRM_MM_BUG_ON(!nsize);
1540
1541	drm_random_reorder(order, count: size, state: &prng);
1542	if (evict_something(test, mm: &mm, range_start, range_end, nodes,
1543	order, count: size, size: nsize, alignment: n, mode)) {
1544	KUNIT_FAIL(test,
1545	"%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
1546	mode->name, nsize, n, range_start, range_end);
1547	goto out;
1548	}
1549	}
1550
1551	cond_resched();
1552	}
1553
1554	out:
1555	drm_mm_for_each_node_safe(node, next, &mm)
1556	drm_mm_remove_node(node);
1557	drm_mm_takedown(mm: &mm);
1558	kfree(objp: order);
1559	err_nodes:
1560	vfree(addr: nodes);
1561	}
1562
1563	static unsigned int node_index(const struct drm_mm_node *node)
1564	{
1565	return div64_u64(dividend: node->start, divisor: node->size);
1566	}
1567
1568	static void drm_test_mm_topdown(struct kunit *test)
1569	{
1570	const struct insert_mode *topdown = &insert_modes[TOPDOWN];
1571
1572	DRM_RND_STATE(prng, random_seed);
1573	const unsigned int count = 8192;
1574	unsigned int size;
1575	unsigned long *bitmap;
1576	struct drm_mm mm;
1577	struct drm_mm_node *nodes, *node, *next;
1578	unsigned int *order, n, m, o = 0;
1579
1580	/* When allocating top-down, we expect to be returned a node
1581	* from a suitable hole at the top of the drm_mm. We check that
1582	* the returned node does match the highest available slot.
1583	*/
1584
1585	nodes = vzalloc(array_size(count, sizeof(*nodes)));
1586	KUNIT_ASSERT_TRUE(test, nodes);
1587
1588	bitmap = bitmap_zalloc(nbits: count, GFP_KERNEL);
1589	if (!bitmap)
1590	goto err_nodes;
1591
1592	order = drm_random_order(count, state: &prng);
1593	if (!order)
1594	goto err_bitmap;
1595
1596	for (size = 1; size <= 64; size <<= 1) {
1597	drm_mm_init(mm: &mm, start: 0, size: size * count);
1598	for (n = 0; n < count; n++) {
1599	if (!expect_insert(test, mm: &mm, node: &nodes[n], size, alignment: 0, color: n, mode: topdown)) {
1600	KUNIT_FAIL(test, "insert failed, size %u step %d\n", size, n);
1601	goto out;
1602	}
1603
1604	if (drm_mm_hole_follows(node: &nodes[n])) {
1605	KUNIT_FAIL(test,
1606	"hole after topdown insert %d, start=%llx\n, size=%u",
1607	n, nodes[n].start, size);
1608	goto out;
1609	}
1610
1611	if (!assert_one_hole(test, mm: &mm, start: 0, end: size * (count - n - 1)))
1612	goto out;
1613	}
1614
1615	if (!assert_continuous(test, mm: &mm, size))
1616	goto out;
1617
1618	drm_random_reorder(order, count, state: &prng);
1619	for_each_prime_number_from(n, 1, min(count, max_prime)) {
1620	for (m = 0; m < n; m++) {
1621	node = &nodes[order[(o + m) % count]];
1622	drm_mm_remove_node(node);
1623	__set_bit(node_index(node), bitmap);
1624	}
1625
1626	for (m = 0; m < n; m++) {
1627	unsigned int last;
1628
1629	node = &nodes[order[(o + m) % count]];
1630	if (!expect_insert(test, mm: &mm, node, size, alignment: 0, color: 0, mode: topdown)) {
1631	KUNIT_FAIL(test, "insert failed, step %d/%d\n", m, n);
1632	goto out;
1633	}
1634
1635	if (drm_mm_hole_follows(node)) {
1636	KUNIT_FAIL(test,
1637	"hole after topdown insert %d/%d, start=%llx\n",
1638	m, n, node->start);
1639	goto out;
1640	}
1641
1642	last = find_last_bit(addr: bitmap, size: count);
1643	if (node_index(node) != last) {
1644	KUNIT_FAIL(test,
1645	"node %d/%d, size %d, not inserted into upmost hole, expected %d, found %d\n",
1646	m, n, size, last, node_index(node));
1647	goto out;
1648	}
1649
1650	__clear_bit(last, bitmap);
1651	}
1652
1653	DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count);
1654
1655	o += n;
1656	}
1657
1658	drm_mm_for_each_node_safe(node, next, &mm)
1659	drm_mm_remove_node(node);
1660	DRM_MM_BUG_ON(!drm_mm_clean(&mm));
1661	cond_resched();
1662	}
1663
1664	out:
1665	drm_mm_for_each_node_safe(node, next, &mm)
1666	drm_mm_remove_node(node);
1667	drm_mm_takedown(mm: &mm);
1668	kfree(objp: order);
1669	err_bitmap:
1670	bitmap_free(bitmap);
1671	err_nodes:
1672	vfree(addr: nodes);
1673	}
1674
1675	static void drm_test_mm_bottomup(struct kunit *test)
1676	{
1677	const struct insert_mode *bottomup = &insert_modes[BOTTOMUP];
1678
1679	DRM_RND_STATE(prng, random_seed);
1680	const unsigned int count = 8192;
1681	unsigned int size;
1682	unsigned long *bitmap;
1683	struct drm_mm mm;
1684	struct drm_mm_node *nodes, *node, *next;
1685	unsigned int *order, n, m, o = 0;
1686
1687	/* Like drm_test_mm_topdown, but instead of searching for the last hole,
1688	* we search for the first.
1689	*/
1690
1691	nodes = vzalloc(array_size(count, sizeof(*nodes)));
1692	KUNIT_ASSERT_TRUE(test, nodes);
1693
1694	bitmap = bitmap_zalloc(nbits: count, GFP_KERNEL);
1695	if (!bitmap)
1696	goto err_nodes;
1697
1698	order = drm_random_order(count, state: &prng);
1699	if (!order)
1700	goto err_bitmap;
1701
1702	for (size = 1; size <= 64; size <<= 1) {
1703	drm_mm_init(mm: &mm, start: 0, size: size * count);
1704	for (n = 0; n < count; n++) {
1705	if (!expect_insert(test, mm: &mm, node: &nodes[n], size, alignment: 0, color: n, mode: bottomup)) {
1706	KUNIT_FAIL(test,
1707	"bottomup insert failed, size %u step %d\n", size, n);
1708	goto out;
1709	}
1710
1711	if (!assert_one_hole(test, mm: &mm, start: size * (n + 1), end: size * count))
1712	goto out;
1713	}
1714
1715	if (!assert_continuous(test, mm: &mm, size))
1716	goto out;
1717
1718	drm_random_reorder(order, count, state: &prng);
1719	for_each_prime_number_from(n, 1, min(count, max_prime)) {
1720	for (m = 0; m < n; m++) {
1721	node = &nodes[order[(o + m) % count]];
1722	drm_mm_remove_node(node);
1723	__set_bit(node_index(node), bitmap);
1724	}
1725
1726	for (m = 0; m < n; m++) {
1727	unsigned int first;
1728
1729	node = &nodes[order[(o + m) % count]];
1730	if (!expect_insert(test, mm: &mm, node, size, alignment: 0, color: 0, mode: bottomup)) {
1731	KUNIT_FAIL(test, "insert failed, step %d/%d\n", m, n);
1732	goto out;
1733	}
1734
1735	first = find_first_bit(addr: bitmap, size: count);
1736	if (node_index(node) != first) {
1737	KUNIT_FAIL(test,
1738	"node %d/%d not inserted into bottom hole, expected %d, found %d\n",
1739	m, n, first, node_index(node));
1740	goto out;
1741	}
1742	__clear_bit(first, bitmap);
1743	}
1744
1745	DRM_MM_BUG_ON(find_first_bit(bitmap, count) != count);
1746
1747	o += n;
1748	}
1749
1750	drm_mm_for_each_node_safe(node, next, &mm)
1751	drm_mm_remove_node(node);
1752	DRM_MM_BUG_ON(!drm_mm_clean(&mm));
1753	cond_resched();
1754	}
1755
1756	out:
1757	drm_mm_for_each_node_safe(node, next, &mm)
1758	drm_mm_remove_node(node);
1759	drm_mm_takedown(mm: &mm);
1760	kfree(objp: order);
1761	err_bitmap:
1762	bitmap_free(bitmap);
1763	err_nodes:
1764	vfree(addr: nodes);
1765	}
1766
1767	static void drm_test_mm_once(struct kunit *test, unsigned int mode)
1768	{
1769	struct drm_mm mm;
1770	struct drm_mm_node rsvd_lo, rsvd_hi, node;
1771
1772	drm_mm_init(mm: &mm, start: 0, size: 7);
1773
1774	memset(&rsvd_lo, 0, sizeof(rsvd_lo));
1775	rsvd_lo.start = 1;
1776	rsvd_lo.size = 1;
1777	if (drm_mm_reserve_node(mm: &mm, node: &rsvd_lo)) {
1778	KUNIT_FAIL(test, "Could not reserve low node\n");
1779	goto err;
1780	}
1781
1782	memset(&rsvd_hi, 0, sizeof(rsvd_hi));
1783	rsvd_hi.start = 5;
1784	rsvd_hi.size = 1;
1785	if (drm_mm_reserve_node(mm: &mm, node: &rsvd_hi)) {
1786	KUNIT_FAIL(test, "Could not reserve low node\n");
1787	goto err_lo;
1788	}
1789
1790	if (!drm_mm_hole_follows(node: &rsvd_lo) || !drm_mm_hole_follows(node: &rsvd_hi)) {
1791	KUNIT_FAIL(test, "Expected a hole after lo and high nodes!\n");
1792	goto err_hi;
1793	}
1794
1795	memset(&node, 0, sizeof(node));
1796	if (drm_mm_insert_node_generic(mm: &mm, node: &node, size: 2, alignment: 0, color: 0, mode)) {
1797	KUNIT_FAIL(test, "Could not insert the node into the available hole!\n");
1798	goto err_hi;
1799	}
1800
1801	drm_mm_remove_node(node: &node);
1802	err_hi:
1803	drm_mm_remove_node(node: &rsvd_hi);
1804	err_lo:
1805	drm_mm_remove_node(node: &rsvd_lo);
1806	err:
1807	drm_mm_takedown(mm: &mm);
1808	}
1809
1810	static void drm_test_mm_lowest(struct kunit *test)
1811	{
1812	drm_test_mm_once(test, mode: DRM_MM_INSERT_LOW);
1813	}
1814
1815	static void drm_test_mm_highest(struct kunit *test)
1816	{
1817	drm_test_mm_once(test, mode: DRM_MM_INSERT_HIGH);
1818	}
1819
1820	static void separate_adjacent_colors(const struct drm_mm_node *node,
1821	unsigned long color, u64 *start, u64 *end)
1822	{
1823	if (drm_mm_node_allocated(node) && node->color != color)
1824	++*start;
1825
1826	node = list_next_entry(node, node_list);
1827	if (drm_mm_node_allocated(node) && node->color != color)
1828	--*end;
1829	}
1830
1831	static bool colors_abutt(struct kunit *test, const struct drm_mm_node *node)
1832	{
1833	if (!drm_mm_hole_follows(node) &&
1834	drm_mm_node_allocated(list_next_entry(node, node_list))) {
1835	KUNIT_FAIL(test, "colors abutt; %ld [%llx + %llx] is next to %ld [%llx + %llx]!\n",
1836	node->color, node->start, node->size,
1837	list_next_entry(node, node_list)->color,
1838	list_next_entry(node, node_list)->start,
1839	list_next_entry(node, node_list)->size);
1840	return true;
1841	}
1842
1843	return false;
1844	}
1845
1846	static void drm_test_mm_color(struct kunit *test)
1847	{
1848	const unsigned int count = min(4096u, max_iterations);
1849	const struct insert_mode *mode;
1850	struct drm_mm mm;
1851	struct drm_mm_node *node, *nn;
1852	unsigned int n;
1853
1854	/* Color adjustment complicates everything. First we just check
1855	* that when we insert a node we apply any color_adjustment callback.
1856	* The callback we use should ensure that there is a gap between
1857	* any two nodes, and so after each insertion we check that those
1858	* holes are inserted and that they are preserved.
1859	*/
1860
1861	drm_mm_init(mm: &mm, start: 0, U64_MAX);
1862
1863	for (n = 1; n <= count; n++) {
1864	node = kzalloc(size: sizeof(*node), GFP_KERNEL);
1865	if (!node)
1866	goto out;
1867
1868	if (!expect_insert(test, mm: &mm, node, size: n, alignment: 0, color: n, mode: &insert_modes[0])) {
1869	KUNIT_FAIL(test, "insert failed, step %d\n", n);
1870	kfree(objp: node);
1871	goto out;
1872	}
1873	}
1874
1875	drm_mm_for_each_node_safe(node, nn, &mm) {
1876	if (node->color != node->size) {
1877	KUNIT_FAIL(test, "invalid color stored: expected %lld, found %ld\n",
1878	node->size, node->color);
1879
1880	goto out;
1881	}
1882
1883	drm_mm_remove_node(node);
1884	kfree(objp: node);
1885	}
1886
1887	/* Now, let's start experimenting with applying a color callback */
1888	mm.color_adjust = separate_adjacent_colors;
1889	for (mode = insert_modes; mode->name; mode++) {
1890	u64 last;
1891
1892	node = kzalloc(size: sizeof(*node), GFP_KERNEL);
1893	if (!node)
1894	goto out;
1895
1896	node->size = 1 + 2 * count;
1897	node->color = node->size;
1898
1899	if (drm_mm_reserve_node(mm: &mm, node)) {
1900	KUNIT_FAIL(test, "initial reserve failed!\n");
1901	goto out;
1902	}
1903
1904	last = node->start + node->size;
1905
1906	for (n = 1; n <= count; n++) {
1907	int rem;
1908
1909	node = kzalloc(size: sizeof(*node), GFP_KERNEL);
1910	if (!node)
1911	goto out;
1912
1913	node->start = last;
1914	node->size = n + count;
1915	node->color = node->size;
1916
1917	if (drm_mm_reserve_node(mm: &mm, node) != -ENOSPC) {
1918	KUNIT_FAIL(test, "reserve %d did not report color overlap!", n);
1919	goto out;
1920	}
1921
1922	node->start += n + 1;
1923	rem = misalignment(node, alignment: n + count);
1924	node->start += n + count - rem;
1925
1926	if (drm_mm_reserve_node(mm: &mm, node)) {
1927	KUNIT_FAIL(test, "reserve %d failed", n);
1928	goto out;
1929	}
1930
1931	last = node->start + node->size;
1932	}
1933
1934	for (n = 1; n <= count; n++) {
1935	node = kzalloc(size: sizeof(*node), GFP_KERNEL);
1936	if (!node)
1937	goto out;
1938
1939	if (!expect_insert(test, mm: &mm, node, size: n, alignment: n, color: n, mode)) {
1940	KUNIT_FAIL(test, "%s insert failed, step %d\n", mode->name, n);
1941	kfree(objp: node);
1942	goto out;
1943	}
1944	}
1945
1946	drm_mm_for_each_node_safe(node, nn, &mm) {
1947	u64 rem;
1948
1949	if (node->color != node->size) {
1950	KUNIT_FAIL(test,
1951	"%s invalid color stored: expected %lld, found %ld\n",
1952	mode->name, node->size, node->color);
1953
1954	goto out;
1955	}
1956
1957	if (colors_abutt(test, node))
1958	goto out;
1959
1960	div64_u64_rem(dividend: node->start, divisor: node->size, remainder: &rem);
1961	if (rem) {
1962	KUNIT_FAIL(test,
1963	"%s colored node misaligned, start=%llx expected alignment=%lld [rem=%lld]\n",
1964	mode->name, node->start, node->size, rem);
1965	goto out;
1966	}
1967
1968	drm_mm_remove_node(node);
1969	kfree(objp: node);
1970	}
1971
1972	cond_resched();
1973	}
1974
1975	out:
1976	drm_mm_for_each_node_safe(node, nn, &mm) {
1977	drm_mm_remove_node(node);
1978	kfree(objp: node);
1979	}
1980	drm_mm_takedown(mm: &mm);
1981	}
1982
1983	static int evict_color(struct kunit *test, struct drm_mm *mm, u64 range_start,
1984	u64 range_end, struct evict_node *nodes, unsigned int *order,
1985	unsigned int count, unsigned int size, unsigned int alignment,
1986	unsigned long color, const struct insert_mode *mode)
1987	{
1988	struct drm_mm_scan scan;
1989	LIST_HEAD(evict_list);
1990	struct evict_node *e;
1991	struct drm_mm_node tmp;
1992	int err;
1993
1994	drm_mm_scan_init_with_range(scan: &scan, mm, size, alignment, color, start: range_start,
1995	end: range_end, mode: mode->mode);
1996	if (!evict_nodes(test, scan: &scan, nodes, order, count, use_color: true, evict_list: &evict_list))
1997	return -EINVAL;
1998
1999	memset(&tmp, 0, sizeof(tmp));
2000	err = drm_mm_insert_node_generic(mm, node: &tmp, size, alignment, color,
2001	mode: DRM_MM_INSERT_EVICT);
2002	if (err) {
2003	KUNIT_FAIL(test,
2004	"Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n",
2005	size, alignment, color, err);
2006	show_scan(test, scan: &scan);
2007	show_holes(test, mm, count: 3);
2008	return err;
2009	}
2010
2011	if (tmp.start < range_start || tmp.start + tmp.size > range_end) {
2012	KUNIT_FAIL(test,
2013	"Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
2014	tmp.start, tmp.size, range_start, range_end);
2015	err = -EINVAL;
2016	}
2017
2018	if (colors_abutt(test, node: &tmp))
2019	err = -EINVAL;
2020
2021	if (!assert_node(test, node: &tmp, mm, size, alignment, color)) {
2022	KUNIT_FAIL(test,
2023	"Inserted did not fit the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx\n",
2024	tmp.size, size, alignment, misalignment(&tmp, alignment), tmp.start);
2025	err = -EINVAL;
2026	}
2027
2028	drm_mm_remove_node(node: &tmp);
2029	if (err)
2030	return err;
2031
2032	list_for_each_entry(e, &evict_list, link) {
2033	err = drm_mm_reserve_node(mm, node: &e->node);
2034	if (err) {
2035	KUNIT_FAIL(test, "Failed to reinsert node after eviction: start=%llx\n",
2036	e->node.start);
2037	return err;
2038	}
2039	}
2040
2041	cond_resched();
2042	return 0;
2043	}
2044
2045	static void drm_test_mm_color_evict(struct kunit *test)
2046	{
2047	DRM_RND_STATE(prng, random_seed);
2048	const unsigned int total_size = min(8192u, max_iterations);
2049	const struct insert_mode *mode;
2050	unsigned long color = 0;
2051	struct drm_mm mm;
2052	struct evict_node *nodes;
2053	struct drm_mm_node *node, *next;
2054	unsigned int *order, n;
2055
2056	/* Check that the drm_mm_scan also honours color adjustment when
2057	* choosing its victims to create a hole. Our color_adjust does not
2058	* allow two nodes to be placed together without an intervening hole
2059	* enlarging the set of victims that must be evicted.
2060	*/
2061
2062	nodes = vzalloc(array_size(total_size, sizeof(*nodes)));
2063	KUNIT_ASSERT_TRUE(test, nodes);
2064
2065	order = drm_random_order(count: total_size, state: &prng);
2066	if (!order)
2067	goto err_nodes;
2068
2069	drm_mm_init(mm: &mm, start: 0, size: 2 * total_size - 1);
2070	mm.color_adjust = separate_adjacent_colors;
2071	for (n = 0; n < total_size; n++) {
2072	if (!expect_insert(test, mm: &mm, node: &nodes[n].node,
2073	size: 1, alignment: 0, color: color++,
2074	mode: &insert_modes[0])) {
2075	KUNIT_FAIL(test, "insert failed, step %d\n", n);
2076	goto out;
2077	}
2078	}
2079
2080	for (mode = evict_modes; mode->name; mode++) {
2081	for (n = 1; n <= total_size; n <<= 1) {
2082	drm_random_reorder(order, count: total_size, state: &prng);
2083	if (evict_color(test, mm: &mm, range_start: 0, U64_MAX, nodes, order, count: total_size,
2084	size: n, alignment: 1, color: color++, mode)) {
2085	KUNIT_FAIL(test, "%s evict_color(size=%u) failed\n", mode->name, n);
2086	goto out;
2087	}
2088	}
2089
2090	for (n = 1; n < total_size; n <<= 1) {
2091	drm_random_reorder(order, count: total_size, state: &prng);
2092	if (evict_color(test, mm: &mm, range_start: 0, U64_MAX, nodes, order, count: total_size,
2093	size: total_size / 2, alignment: n, color: color++, mode)) {
2094	KUNIT_FAIL(test, "%s evict_color(size=%u, alignment=%u) failed\n",
2095	mode->name, total_size / 2, n);
2096	goto out;
2097	}
2098	}
2099
2100	for_each_prime_number_from(n, 1, min(total_size, max_prime)) {
2101	unsigned int nsize = (total_size - n + 1) / 2;
2102
2103	DRM_MM_BUG_ON(!nsize);
2104
2105	drm_random_reorder(order, count: total_size, state: &prng);
2106	if (evict_color(test, mm: &mm, range_start: 0, U64_MAX, nodes, order, count: total_size,
2107	size: nsize, alignment: n, color: color++, mode)) {
2108	KUNIT_FAIL(test, "%s evict_color(size=%u, alignment=%u) failed\n",
2109	mode->name, nsize, n);
2110	goto out;
2111	}
2112	}
2113
2114	cond_resched();
2115	}
2116
2117	out:
2118	drm_mm_for_each_node_safe(node, next, &mm)
2119	drm_mm_remove_node(node);
2120	drm_mm_takedown(mm: &mm);
2121	kfree(objp: order);
2122	err_nodes:
2123	vfree(addr: nodes);
2124	}
2125
2126	static void drm_test_mm_color_evict_range(struct kunit *test)
2127	{
2128	DRM_RND_STATE(prng, random_seed);
2129	const unsigned int total_size = 8192;
2130	const unsigned int range_size = total_size / 2;
2131	const unsigned int range_start = total_size / 4;
2132	const unsigned int range_end = range_start + range_size;
2133	const struct insert_mode *mode;
2134	unsigned long color = 0;
2135	struct drm_mm mm;
2136	struct evict_node *nodes;
2137	struct drm_mm_node *node, *next;
2138	unsigned int *order, n;
2139
2140	/* Like drm_test_mm_color_evict(), but limited to small portion of the full
2141	* drm_mm range.
2142	*/
2143
2144	nodes = vzalloc(array_size(total_size, sizeof(*nodes)));
2145	KUNIT_ASSERT_TRUE(test, nodes);
2146
2147	order = drm_random_order(count: total_size, state: &prng);
2148	if (!order)
2149	goto err_nodes;
2150
2151	drm_mm_init(mm: &mm, start: 0, size: 2 * total_size - 1);
2152	mm.color_adjust = separate_adjacent_colors;
2153	for (n = 0; n < total_size; n++) {
2154	if (!expect_insert(test, mm: &mm, node: &nodes[n].node,
2155	size: 1, alignment: 0, color: color++,
2156	mode: &insert_modes[0])) {
2157	KUNIT_FAIL(test, "insert failed, step %d\n", n);
2158	goto out;
2159	}
2160	}
2161
2162	for (mode = evict_modes; mode->name; mode++) {
2163	for (n = 1; n <= range_size; n <<= 1) {
2164	drm_random_reorder(order, count: range_size, state: &prng);
2165	if (evict_color(test, mm: &mm, range_start, range_end, nodes, order,
2166	count: total_size, size: n, alignment: 1, color: color++, mode)) {
2167	KUNIT_FAIL(test,
2168	"%s evict_color(size=%u) failed for range [%x, %x]\n",
2169	mode->name, n, range_start, range_end);
2170	goto out;
2171	}
2172	}
2173
2174	for (n = 1; n < range_size; n <<= 1) {
2175	drm_random_reorder(order, count: total_size, state: &prng);
2176	if (evict_color(test, mm: &mm, range_start, range_end, nodes, order,
2177	count: total_size, size: range_size / 2, alignment: n, color: color++, mode)) {
2178	KUNIT_FAIL(test,
2179	"%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
2180	mode->name, total_size / 2, n, range_start, range_end);
2181	goto out;
2182	}
2183	}
2184
2185	for_each_prime_number_from(n, 1, min(range_size, max_prime)) {
2186	unsigned int nsize = (range_size - n + 1) / 2;
2187
2188	DRM_MM_BUG_ON(!nsize);
2189
2190	drm_random_reorder(order, count: total_size, state: &prng);
2191	if (evict_color(test, mm: &mm, range_start, range_end, nodes, order,
2192	count: total_size, size: nsize, alignment: n, color: color++, mode)) {
2193	KUNIT_FAIL(test,
2194	"%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
2195	mode->name, nsize, n, range_start, range_end);
2196	goto out;
2197	}
2198	}
2199
2200	cond_resched();
2201	}
2202
2203	out:
2204	drm_mm_for_each_node_safe(node, next, &mm)
2205	drm_mm_remove_node(node);
2206	drm_mm_takedown(mm: &mm);
2207	kfree(objp: order);
2208	err_nodes:
2209	vfree(addr: nodes);
2210	}
2211
2212	static int drm_mm_suite_init(struct kunit_suite *suite)
2213	{
2214	while (!random_seed)
2215	random_seed = get_random_u32();
2216
2217	kunit_info(suite,
2218	"Testing DRM range manager, with random_seed=0x%x max_iterations=%u max_prime=%u\n",
2219	random_seed, max_iterations, max_prime);
2220
2221	return 0;
2222	}
2223
2224	module_param(random_seed, uint, 0400);
2225	module_param(max_iterations, uint, 0400);
2226	module_param(max_prime, uint, 0400);
2227
2228	static struct kunit_case drm_mm_tests[] = {
2229	KUNIT_CASE(drm_test_mm_init),
2230	KUNIT_CASE(drm_test_mm_debug),
2231	KUNIT_CASE(drm_test_mm_reserve),
2232	KUNIT_CASE(drm_test_mm_insert),
2233	KUNIT_CASE(drm_test_mm_replace),
2234	KUNIT_CASE(drm_test_mm_insert_range),
2235	KUNIT_CASE(drm_test_mm_frag),
2236	KUNIT_CASE(drm_test_mm_align),
2237	KUNIT_CASE(drm_test_mm_align32),
2238	KUNIT_CASE(drm_test_mm_align64),
2239	KUNIT_CASE(drm_test_mm_evict),
2240	KUNIT_CASE(drm_test_mm_evict_range),
2241	KUNIT_CASE(drm_test_mm_topdown),
2242	KUNIT_CASE(drm_test_mm_bottomup),
2243	KUNIT_CASE(drm_test_mm_lowest),
2244	KUNIT_CASE(drm_test_mm_highest),
2245	KUNIT_CASE(drm_test_mm_color),
2246	KUNIT_CASE(drm_test_mm_color_evict),
2247	KUNIT_CASE(drm_test_mm_color_evict_range),
2248	{}
2249	};
2250
2251	static struct kunit_suite drm_mm_test_suite = {
2252	.name = "drm_mm",
2253	.suite_init = drm_mm_suite_init,
2254	.test_cases = drm_mm_tests,
2255	};
2256
2257	kunit_test_suite(drm_mm_test_suite);
2258
2259	MODULE_AUTHOR("Intel Corporation");
2260	MODULE_LICENSE("GPL");
2261