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
20enum {
21	BEST,
22	BOTTOMUP,
23	TOPDOWN,
24	EVICT,
25};
26
27static const struct insert_mode {
28	const char *name;
29	enum drm_mm_insert_mode mode;
30} insert_modes[] = {
31	[BEST] = { "best", DRM_MM_INSERT_BEST },
32	[BOTTOMUP] = { "bottom-up", DRM_MM_INSERT_LOW },
33	[TOPDOWN] = { "top-down", DRM_MM_INSERT_HIGH },
34	[EVICT] = { "evict", DRM_MM_INSERT_EVICT },
35	{}
36};
37
38static bool assert_no_holes(struct kunit *test, const struct drm_mm *mm)
39{
40	struct drm_mm_node *hole;
41	u64 hole_start, __always_unused hole_end;
42	unsigned long count;
43
44	count = 0;
45	drm_mm_for_each_hole(hole, mm, hole_start, hole_end)
46		count++;
47	if (count) {
48		KUNIT_FAIL(test,
49			   "Expected to find no holes (after reserve), found %lu instead\n", count);
50		return false;
51	}
52
53	drm_mm_for_each_node(hole, mm) {
54		if (drm_mm_hole_follows(hole)) {
55			KUNIT_FAIL(test, "Hole follows node, expected none!\n");
56			return false;
57		}
58	}
59
60	return true;
61}
62
63static bool assert_one_hole(struct kunit *test, const struct drm_mm *mm, u64 start, u64 end)
64{
65	struct drm_mm_node *hole;
66	u64 hole_start, hole_end;
67	unsigned long count;
68	bool ok = true;
69
70	if (end <= start)
71		return true;
72
73	count = 0;
74	drm_mm_for_each_hole(hole, mm, hole_start, hole_end) {
75		if (start != hole_start || end != hole_end) {
76			if (ok)
77				KUNIT_FAIL(test,
78					   "empty mm has incorrect hole, found (%llx, %llx), expect (%llx, %llx)\n",
79					   hole_start, hole_end, start, end);
80			ok = false;
81		}
82		count++;
83	}
84	if (count != 1) {
85		KUNIT_FAIL(test, "Expected to find one hole, found %lu instead\n", count);
86		ok = false;
87	}
88
89	return ok;
90}
91
92static u64 misalignment(struct drm_mm_node *node, u64 alignment)
93{
94	u64 rem;
95
96	if (!alignment)
97		return 0;
98
99	div64_u64_rem(node->start, alignment, &rem);
100	return rem;
101}
102
103static bool assert_node(struct kunit *test, struct drm_mm_node *node, struct drm_mm *mm,
104			u64 size, u64 alignment, unsigned long color)
105{
106	bool ok = true;
107
108	if (!drm_mm_node_allocated(node) || node->mm != mm) {
109		KUNIT_FAIL(test, "node not allocated\n");
110		ok = false;
111	}
112
113	if (node->size != size) {
114		KUNIT_FAIL(test, "node has wrong size, found %llu, expected %llu\n",
115			   node->size, size);
116		ok = false;
117	}
118
119	if (misalignment(node, alignment)) {
120		KUNIT_FAIL(test,
121			   "node is misaligned, start %llx rem %llu, expected alignment %llu\n",
122			   node->start, misalignment(node, alignment), alignment);
123		ok = false;
124	}
125
126	if (node->color != color) {
127		KUNIT_FAIL(test, "node has wrong color, found %lu, expected %lu\n",
128			   node->color, color);
129		ok = false;
130	}
131
132	return ok;
133}
134
135static void drm_test_mm_init(struct kunit *test)
136{
137	const unsigned int size = 4096;
138	struct drm_mm mm;
139	struct drm_mm_node tmp;
140
141	/* Start with some simple checks on initialising the struct drm_mm */
142	memset(&mm, 0, sizeof(mm));
143	KUNIT_ASSERT_FALSE_MSG(test, drm_mm_initialized(&mm),
144			       "zeroed mm claims to be initialized\n");
145
146	memset(&mm, 0xff, sizeof(mm));
147	drm_mm_init(&mm, 0, size);
148	if (!drm_mm_initialized(&mm)) {
149		KUNIT_FAIL(test, "mm claims not to be initialized\n");
150		goto out;
151	}
152
153	if (!drm_mm_clean(&mm)) {
154		KUNIT_FAIL(test, "mm not empty on creation\n");
155		goto out;
156	}
157
158	/* After creation, it should all be one massive hole */
159	if (!assert_one_hole(test, &mm, 0, size)) {
160		KUNIT_FAIL(test, "mm not one hole on creation");
161		goto out;
162	}
163
164	memset(&tmp, 0, sizeof(tmp));
165	tmp.start = 0;
166	tmp.size = size;
167	if (drm_mm_reserve_node(&mm, &tmp)) {
168		KUNIT_FAIL(test, "failed to reserve whole drm_mm\n");
169		goto out;
170	}
171
172	/* After filling the range entirely, there should be no holes */
173	if (!assert_no_holes(test, &mm)) {
174		KUNIT_FAIL(test, "mm has holes when filled");
175		goto out;
176	}
177
178	/* And then after emptying it again, the massive hole should be back */
179	drm_mm_remove_node(&tmp);
180	if (!assert_one_hole(test, &mm, 0, size)) {
181		KUNIT_FAIL(test, "mm does not have single hole after emptying");
182		goto out;
183	}
184
185out:
186	drm_mm_takedown(&mm);
187}
188
189static void drm_test_mm_debug(struct kunit *test)
190{
191	struct drm_printer p = drm_dbg_printer(NULL, DRM_UT_CORE, test->name);
192	struct drm_mm mm;
193	struct drm_mm_node nodes[2];
194
195	/* Create a small drm_mm with a couple of nodes and a few holes, and
196	 * check that the debug iterator doesn't explode over a trivial drm_mm.
197	 */
198	drm_mm_init(&mm, 0, 4096);
199
200	memset(nodes, 0, sizeof(nodes));
201	nodes[0].start = 512;
202	nodes[0].size = 1024;
203	KUNIT_ASSERT_FALSE_MSG(test, drm_mm_reserve_node(&mm, &nodes[0]),
204			       "failed to reserve node[0] {start=%lld, size=%lld)\n",
205			       nodes[0].start, nodes[0].size);
206
207	nodes[1].size = 1024;
208	nodes[1].start = 4096 - 512 - nodes[1].size;
209	KUNIT_ASSERT_FALSE_MSG(test, drm_mm_reserve_node(&mm, &nodes[1]),
210			       "failed to reserve node[0] {start=%lld, size=%lld)\n",
211			       nodes[0].start, nodes[0].size);
212
213	drm_mm_print(&mm, &p);
214	KUNIT_SUCCEED(test);
215}
216
217static bool expect_insert(struct kunit *test, struct drm_mm *mm,
218			  struct drm_mm_node *node, u64 size, u64 alignment, unsigned long color,
219			const struct insert_mode *mode)
220{
221	int err;
222
223	err = drm_mm_insert_node_generic(mm, node,
224					 size, alignment, color,
225					 mode->mode);
226	if (err) {
227		KUNIT_FAIL(test,
228			   "insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n",
229			   size, alignment, color, mode->name, err);
230		return false;
231	}
232
233	if (!assert_node(test, node, mm, size, alignment, color)) {
234		drm_mm_remove_node(node);
235		return false;
236	}
237
238	return true;
239}
240
241static void drm_test_mm_align_pot(struct kunit *test, int max)
242{
243	struct drm_mm mm;
244	struct drm_mm_node *node, *next;
245	int bit;
246
247	/* Check that we can align to the full u64 address space */
248
249	drm_mm_init(&mm, 1, U64_MAX - 2);
250
251	for (bit = max - 1; bit; bit--) {
252		u64 align, size;
253
254		node = kzalloc(sizeof(*node), GFP_KERNEL);
255		if (!node) {
256			KUNIT_FAIL(test, "failed to allocate node");
257			goto out;
258		}
259
260		align = BIT_ULL(bit);
261		size = BIT_ULL(bit - 1) + 1;
262		if (!expect_insert(test, &mm, node, size, align, bit, &insert_modes[0])) {
263			KUNIT_FAIL(test, "insert failed with alignment=%llx [%d]", align, bit);
264			goto out;
265		}
266
267		cond_resched();
268	}
269
270out:
271	drm_mm_for_each_node_safe(node, next, &mm) {
272		drm_mm_remove_node(node);
273		kfree(node);
274	}
275	drm_mm_takedown(&mm);
276}
277
278static void drm_test_mm_align32(struct kunit *test)
279{
280	drm_test_mm_align_pot(test, 32);
281}
282
283static void drm_test_mm_align64(struct kunit *test)
284{
285	drm_test_mm_align_pot(test, 64);
286}
287
288static void drm_test_mm_once(struct kunit *test, unsigned int mode)
289{
290	struct drm_mm mm;
291	struct drm_mm_node rsvd_lo, rsvd_hi, node;
292
293	drm_mm_init(&mm, 0, 7);
294
295	memset(&rsvd_lo, 0, sizeof(rsvd_lo));
296	rsvd_lo.start = 1;
297	rsvd_lo.size = 1;
298	if (drm_mm_reserve_node(&mm, &rsvd_lo)) {
299		KUNIT_FAIL(test, "Could not reserve low node\n");
300		goto err;
301	}
302
303	memset(&rsvd_hi, 0, sizeof(rsvd_hi));
304	rsvd_hi.start = 5;
305	rsvd_hi.size = 1;
306	if (drm_mm_reserve_node(&mm, &rsvd_hi)) {
307		KUNIT_FAIL(test, "Could not reserve low node\n");
308		goto err_lo;
309	}
310
311	if (!drm_mm_hole_follows(&rsvd_lo) || !drm_mm_hole_follows(&rsvd_hi)) {
312		KUNIT_FAIL(test, "Expected a hole after lo and high nodes!\n");
313		goto err_hi;
314	}
315
316	memset(&node, 0, sizeof(node));
317	if (drm_mm_insert_node_generic(&mm, &node, 2, 0, 0, mode)) {
318		KUNIT_FAIL(test, "Could not insert the node into the available hole!\n");
319		goto err_hi;
320	}
321
322	drm_mm_remove_node(&node);
323err_hi:
324	drm_mm_remove_node(&rsvd_hi);
325err_lo:
326	drm_mm_remove_node(&rsvd_lo);
327err:
328	drm_mm_takedown(&mm);
329}
330
331static void drm_test_mm_lowest(struct kunit *test)
332{
333	drm_test_mm_once(test, DRM_MM_INSERT_LOW);
334}
335
336static void drm_test_mm_highest(struct kunit *test)
337{
338	drm_test_mm_once(test, DRM_MM_INSERT_HIGH);
339}
340
341static struct kunit_case drm_mm_tests[] = {
342	KUNIT_CASE(drm_test_mm_init),
343	KUNIT_CASE(drm_test_mm_debug),
344	KUNIT_CASE(drm_test_mm_align32),
345	KUNIT_CASE(drm_test_mm_align64),
346	KUNIT_CASE(drm_test_mm_lowest),
347	KUNIT_CASE(drm_test_mm_highest),
348	{}
349};
350
351static struct kunit_suite drm_mm_test_suite = {
352	.name = "drm_mm",
353	.test_cases = drm_mm_tests,
354};
355
356kunit_test_suite(drm_mm_test_suite);
357
358MODULE_AUTHOR("Intel Corporation");
359MODULE_LICENSE("GPL");
360