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 enum {
21 BEST,
22 BOTTOMUP,
23 TOPDOWN,
24 EVICT,
25 };
26
27 static 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
assert_no_holes(struct kunit * test,const struct drm_mm * mm)38 static 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
assert_one_hole(struct kunit * test,const struct drm_mm * mm,u64 start,u64 end)63 static 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
misalignment(struct drm_mm_node * node,u64 alignment)92 static 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
assert_node(struct kunit * test,struct drm_mm_node * node,struct drm_mm * mm,u64 size,u64 alignment,unsigned long color)103 static 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
drm_test_mm_init(struct kunit * test)135 static 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
185 out:
186 drm_mm_takedown(&mm);
187 }
188
drm_test_mm_debug(struct kunit * test)189 static 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
expect_insert(struct kunit * test,struct drm_mm * mm,struct drm_mm_node * node,u64 size,u64 alignment,unsigned long color,const struct insert_mode * mode)217 static 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
drm_test_mm_align_pot(struct kunit * test,int max)241 static 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
270 out:
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
drm_test_mm_align32(struct kunit * test)278 static void drm_test_mm_align32(struct kunit *test)
279 {
280 drm_test_mm_align_pot(test, 32);
281 }
282
drm_test_mm_align64(struct kunit * test)283 static void drm_test_mm_align64(struct kunit *test)
284 {
285 drm_test_mm_align_pot(test, 64);
286 }
287
drm_test_mm_once(struct kunit * test,unsigned int mode)288 static 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);
323 err_hi:
324 drm_mm_remove_node(&rsvd_hi);
325 err_lo:
326 drm_mm_remove_node(&rsvd_lo);
327 err:
328 drm_mm_takedown(&mm);
329 }
330
drm_test_mm_lowest(struct kunit * test)331 static void drm_test_mm_lowest(struct kunit *test)
332 {
333 drm_test_mm_once(test, DRM_MM_INSERT_LOW);
334 }
335
drm_test_mm_highest(struct kunit * test)336 static void drm_test_mm_highest(struct kunit *test)
337 {
338 drm_test_mm_once(test, DRM_MM_INSERT_HIGH);
339 }
340
341 static 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
351 static struct kunit_suite drm_mm_test_suite = {
352 .name = "drm_mm",
353 .test_cases = drm_mm_tests,
354 };
355
356 kunit_test_suite(drm_mm_test_suite);
357
358 MODULE_AUTHOR("Intel Corporation");
359 MODULE_DESCRIPTION("Test cases for the drm_mm range manager");
360 MODULE_LICENSE("GPL");
361