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] = { .name: "best", .mode: DRM_MM_INSERT_BEST },
32 [BOTTOMUP] = { .name: "bottom-up", .mode: DRM_MM_INSERT_LOW },
33 [TOPDOWN] = { .name: "top-down", .mode: DRM_MM_INSERT_HIGH },
34 [EVICT] = { .name: "evict", .mode: 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(node: 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(dividend: node->start, divisor: alignment, remainder: &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: &mm, start: 0, size);
148 if (!drm_mm_initialized(mm: &mm)) {
149 KUNIT_FAIL(test, "mm claims not to be initialized\n");
150 goto out;
151 }
152
153 if (!drm_mm_clean(mm: &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: &mm, start: 0, end: 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: &mm, node: &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: &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(node: &tmp);
180 if (!assert_one_hole(test, mm: &mm, start: 0, end: size)) {
181 KUNIT_FAIL(test, "mm does not have single hole after emptying");
182 goto out;
183 }
184
185out:
186 drm_mm_takedown(mm: &mm);
187}
188
189static void drm_test_mm_debug(struct kunit *test)
190{
191 struct drm_printer p = drm_dbg_printer(NULL, category: DRM_UT_CORE, prefix: 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: &mm, start: 0, size: 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: &mm, p: &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->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: &mm, start: 1, U64_MAX - 2);
250
251 for (bit = max - 1; bit; bit--) {
252 u64 align, size;
253
254 node = kzalloc(size: 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: &mm, node, size, alignment: align, color: bit, mode: &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(objp: node);
274 }
275 drm_mm_takedown(mm: &mm);
276}
277
278static void drm_test_mm_align32(struct kunit *test)
279{
280 drm_test_mm_align_pot(test, max: 32);
281}
282
283static void drm_test_mm_align64(struct kunit *test)
284{
285 drm_test_mm_align_pot(test, max: 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: &mm, start: 0, size: 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: &mm, node: &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: &mm, node: &rsvd_hi)) {
307 KUNIT_FAIL(test, "Could not reserve low node\n");
308 goto err_lo;
309 }
310
311 if (!drm_mm_hole_follows(node: &rsvd_lo) || !drm_mm_hole_follows(node: &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: &mm, node: &node, size: 2, alignment: 0, color: 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: &node);
323err_hi:
324 drm_mm_remove_node(node: &rsvd_hi);
325err_lo:
326 drm_mm_remove_node(node: &rsvd_lo);
327err:
328 drm_mm_takedown(mm: &mm);
329}
330
331static void drm_test_mm_lowest(struct kunit *test)
332{
333 drm_test_mm_once(test, mode: DRM_MM_INSERT_LOW);
334}
335
336static void drm_test_mm_highest(struct kunit *test)
337{
338 drm_test_mm_once(test, mode: 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

source code of linux/drivers/gpu/drm/tests/drm_mm_test.c