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