]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - drivers/gpu/drm/selftests/test-drm_mm.c
2 * Test cases for the drm_mm range manager
5 #define pr_fmt(fmt) "drm_mm: " fmt
7 #include <linux/module.h>
8 #include <linux/prime_numbers.h>
9 #include <linux/slab.h>
10 #include <linux/random.h>
11 #include <linux/vmalloc.h>
13 #include <drm/drm_mm.h>
15 #include "../lib/drm_random.h"
17 #define TESTS "drm_mm_selftests.h"
18 #include "drm_selftest.h"
20 static unsigned int random_seed
;
21 static unsigned int max_iterations
= 8192;
22 static unsigned int max_prime
= 128;
31 static const struct insert_mode
{
33 enum drm_mm_insert_mode mode
;
35 [BEST
] = { "best", DRM_MM_INSERT_BEST
},
36 [BOTTOMUP
] = { "bottom-up", DRM_MM_INSERT_LOW
},
37 [TOPDOWN
] = { "top-down", DRM_MM_INSERT_HIGH
},
38 [EVICT
] = { "evict", DRM_MM_INSERT_EVICT
},
41 { "bottom-up", DRM_MM_INSERT_LOW
},
42 { "top-down", DRM_MM_INSERT_HIGH
},
46 static int igt_sanitycheck(void *ignored
)
48 pr_info("%s - ok!\n", __func__
);
52 static bool assert_no_holes(const struct drm_mm
*mm
)
54 struct drm_mm_node
*hole
;
55 u64 hole_start
, hole_end
;
59 drm_mm_for_each_hole(hole
, mm
, hole_start
, hole_end
)
62 pr_err("Expected to find no holes (after reserve), found %lu instead\n", count
);
66 drm_mm_for_each_node(hole
, mm
) {
67 if (drm_mm_hole_follows(hole
)) {
68 pr_err("Hole follows node, expected none!\n");
76 static bool assert_one_hole(const struct drm_mm
*mm
, u64 start
, u64 end
)
78 struct drm_mm_node
*hole
;
79 u64 hole_start
, hole_end
;
87 drm_mm_for_each_hole(hole
, mm
, hole_start
, hole_end
) {
88 if (start
!= hole_start
|| end
!= hole_end
) {
90 pr_err("empty mm has incorrect hole, found (%llx, %llx), expect (%llx, %llx)\n",
98 pr_err("Expected to find one hole, found %lu instead\n", count
);
105 static bool assert_continuous(const struct drm_mm
*mm
, u64 size
)
107 struct drm_mm_node
*node
, *check
, *found
;
111 if (!assert_no_holes(mm
))
116 drm_mm_for_each_node(node
, mm
) {
117 if (node
->start
!= addr
) {
118 pr_err("node[%ld] list out of order, expected %llx found %llx\n",
119 n
, addr
, node
->start
);
123 if (node
->size
!= size
) {
124 pr_err("node[%ld].size incorrect, expected %llx, found %llx\n",
125 n
, size
, node
->size
);
129 if (drm_mm_hole_follows(node
)) {
130 pr_err("node[%ld] is followed by a hole!\n", n
);
135 drm_mm_for_each_node_in_range(check
, mm
, addr
, addr
+ size
) {
137 pr_err("lookup return wrong node, expected start %llx, found %llx\n",
138 node
->start
, check
->start
);
144 pr_err("lookup failed for node %llx + %llx\n",
156 static u64
misalignment(struct drm_mm_node
*node
, u64 alignment
)
163 div64_u64_rem(node
->start
, alignment
, &rem
);
167 static bool assert_node(struct drm_mm_node
*node
, struct drm_mm
*mm
,
168 u64 size
, u64 alignment
, unsigned long color
)
172 if (!drm_mm_node_allocated(node
) || node
->mm
!= mm
) {
173 pr_err("node not allocated\n");
177 if (node
->size
!= size
) {
178 pr_err("node has wrong size, found %llu, expected %llu\n",
183 if (misalignment(node
, alignment
)) {
184 pr_err("node is misaligned, start %llx rem %llu, expected alignment %llu\n",
185 node
->start
, misalignment(node
, alignment
), alignment
);
189 if (node
->color
!= color
) {
190 pr_err("node has wrong color, found %lu, expected %lu\n",
198 #define show_mm(mm) do { \
199 struct drm_printer __p = drm_debug_printer(__func__); \
200 drm_mm_print((mm), &__p); } while (0)
202 static int igt_init(void *ignored
)
204 const unsigned int size
= 4096;
206 struct drm_mm_node tmp
;
209 /* Start with some simple checks on initialising the struct drm_mm */
210 memset(&mm
, 0, sizeof(mm
));
211 if (drm_mm_initialized(&mm
)) {
212 pr_err("zeroed mm claims to be initialized\n");
216 memset(&mm
, 0xff, sizeof(mm
));
217 drm_mm_init(&mm
, 0, size
);
218 if (!drm_mm_initialized(&mm
)) {
219 pr_err("mm claims not to be initialized\n");
223 if (!drm_mm_clean(&mm
)) {
224 pr_err("mm not empty on creation\n");
228 /* After creation, it should all be one massive hole */
229 if (!assert_one_hole(&mm
, 0, size
)) {
234 memset(&tmp
, 0, sizeof(tmp
));
237 ret
= drm_mm_reserve_node(&mm
, &tmp
);
239 pr_err("failed to reserve whole drm_mm\n");
243 /* After filling the range entirely, there should be no holes */
244 if (!assert_no_holes(&mm
)) {
249 /* And then after emptying it again, the massive hole should be back */
250 drm_mm_remove_node(&tmp
);
251 if (!assert_one_hole(&mm
, 0, size
)) {
259 drm_mm_takedown(&mm
);
263 static int igt_debug(void *ignored
)
266 struct drm_mm_node nodes
[2];
269 /* Create a small drm_mm with a couple of nodes and a few holes, and
270 * check that the debug iterator doesn't explode over a trivial drm_mm.
273 drm_mm_init(&mm
, 0, 4096);
275 memset(nodes
, 0, sizeof(nodes
));
276 nodes
[0].start
= 512;
277 nodes
[0].size
= 1024;
278 ret
= drm_mm_reserve_node(&mm
, &nodes
[0]);
280 pr_err("failed to reserve node[0] {start=%lld, size=%lld)\n",
281 nodes
[0].start
, nodes
[0].size
);
285 nodes
[1].size
= 1024;
286 nodes
[1].start
= 4096 - 512 - nodes
[1].size
;
287 ret
= drm_mm_reserve_node(&mm
, &nodes
[1]);
289 pr_err("failed to reserve node[1] {start=%lld, size=%lld)\n",
290 nodes
[1].start
, nodes
[1].size
);
298 static struct drm_mm_node
*set_node(struct drm_mm_node
*node
,
306 static bool expect_reserve_fail(struct drm_mm
*mm
, struct drm_mm_node
*node
)
310 err
= drm_mm_reserve_node(mm
, node
);
311 if (likely(err
== -ENOSPC
))
315 pr_err("impossible reserve succeeded, node %llu + %llu\n",
316 node
->start
, node
->size
);
317 drm_mm_remove_node(node
);
319 pr_err("impossible reserve failed with wrong error %d [expected %d], node %llu + %llu\n",
320 err
, -ENOSPC
, node
->start
, node
->size
);
325 static bool check_reserve_boundaries(struct drm_mm
*mm
,
329 const struct boundary
{
333 #define B(st, sz) { (st), (sz), "{ " #st ", " #sz "}" }
344 B(count
*size
, -size
),
345 B(count
*size
, count
*size
),
346 B(count
*size
, -count
*size
),
347 B(count
*size
, -(count
+1)*size
),
348 B((count
+1)*size
, size
),
349 B((count
+1)*size
, -size
),
350 B((count
+1)*size
, -2*size
),
353 struct drm_mm_node tmp
= {};
356 for (n
= 0; n
< ARRAY_SIZE(boundaries
); n
++) {
357 if (!expect_reserve_fail(mm
,
360 boundaries
[n
].size
))) {
361 pr_err("boundary[%d:%s] failed, count=%u, size=%lld\n",
362 n
, boundaries
[n
].name
, count
, size
);
370 static int __igt_reserve(unsigned int count
, u64 size
)
372 DRM_RND_STATE(prng
, random_seed
);
374 struct drm_mm_node tmp
, *nodes
, *node
, *next
;
375 unsigned int *order
, n
, m
, o
= 0;
378 /* For exercising drm_mm_reserve_node(), we want to check that
379 * reservations outside of the drm_mm range are rejected, and to
380 * overlapping and otherwise already occupied ranges. Afterwards,
381 * the tree and nodes should be intact.
384 DRM_MM_BUG_ON(!count
);
385 DRM_MM_BUG_ON(!size
);
388 order
= drm_random_order(count
, &prng
);
392 nodes
= vzalloc(array_size(count
, sizeof(*nodes
)));
397 drm_mm_init(&mm
, 0, count
* size
);
399 if (!check_reserve_boundaries(&mm
, count
, size
))
402 for (n
= 0; n
< count
; n
++) {
403 nodes
[n
].start
= order
[n
] * size
;
404 nodes
[n
].size
= size
;
406 err
= drm_mm_reserve_node(&mm
, &nodes
[n
]);
408 pr_err("reserve failed, step %d, start %llu\n",
414 if (!drm_mm_node_allocated(&nodes
[n
])) {
415 pr_err("reserved node not allocated! step %d, start %llu\n",
420 if (!expect_reserve_fail(&mm
, &nodes
[n
]))
424 /* After random insertion the nodes should be in order */
425 if (!assert_continuous(&mm
, size
))
428 /* Repeated use should then fail */
429 drm_random_reorder(order
, count
, &prng
);
430 for (n
= 0; n
< count
; n
++) {
431 if (!expect_reserve_fail(&mm
,
432 set_node(&tmp
, order
[n
] * size
, 1)))
435 /* Remove and reinsert should work */
436 drm_mm_remove_node(&nodes
[order
[n
]]);
437 err
= drm_mm_reserve_node(&mm
, &nodes
[order
[n
]]);
439 pr_err("reserve failed, step %d, start %llu\n",
446 if (!assert_continuous(&mm
, size
))
449 /* Overlapping use should then fail */
450 for (n
= 0; n
< count
; n
++) {
451 if (!expect_reserve_fail(&mm
, set_node(&tmp
, 0, size
*count
)))
454 for (n
= 0; n
< count
; n
++) {
455 if (!expect_reserve_fail(&mm
,
458 size
* (count
- n
))))
462 /* Remove several, reinsert, check full */
463 for_each_prime_number(n
, min(max_prime
, count
)) {
464 for (m
= 0; m
< n
; m
++) {
465 node
= &nodes
[order
[(o
+ m
) % count
]];
466 drm_mm_remove_node(node
);
469 for (m
= 0; m
< n
; m
++) {
470 node
= &nodes
[order
[(o
+ m
) % count
]];
471 err
= drm_mm_reserve_node(&mm
, node
);
473 pr_err("reserve failed, step %d/%d, start %llu\n",
482 if (!assert_continuous(&mm
, size
))
488 drm_mm_for_each_node_safe(node
, next
, &mm
)
489 drm_mm_remove_node(node
);
490 drm_mm_takedown(&mm
);
498 static int igt_reserve(void *ignored
)
500 const unsigned int count
= min_t(unsigned int, BIT(10), max_iterations
);
503 for_each_prime_number_from(n
, 1, 54) {
504 u64 size
= BIT_ULL(n
);
506 ret
= __igt_reserve(count
, size
- 1);
510 ret
= __igt_reserve(count
, size
);
514 ret
= __igt_reserve(count
, size
+ 1);
524 static bool expect_insert(struct drm_mm
*mm
, struct drm_mm_node
*node
,
525 u64 size
, u64 alignment
, unsigned long color
,
526 const struct insert_mode
*mode
)
530 err
= drm_mm_insert_node_generic(mm
, node
,
531 size
, alignment
, color
,
534 pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) failed with err=%d\n",
535 size
, alignment
, color
, mode
->name
, err
);
539 if (!assert_node(node
, mm
, size
, alignment
, color
)) {
540 drm_mm_remove_node(node
);
547 static bool expect_insert_fail(struct drm_mm
*mm
, u64 size
)
549 struct drm_mm_node tmp
= {};
552 err
= drm_mm_insert_node(mm
, &tmp
, size
);
553 if (likely(err
== -ENOSPC
))
557 pr_err("impossible insert succeeded, node %llu + %llu\n",
558 tmp
.start
, tmp
.size
);
559 drm_mm_remove_node(&tmp
);
561 pr_err("impossible insert failed with wrong error %d [expected %d], size %llu\n",
567 static int __igt_insert(unsigned int count
, u64 size
, bool replace
)
569 DRM_RND_STATE(prng
, random_seed
);
570 const struct insert_mode
*mode
;
572 struct drm_mm_node
*nodes
, *node
, *next
;
573 unsigned int *order
, n
, m
, o
= 0;
576 /* Fill a range with lots of nodes, check it doesn't fail too early */
578 DRM_MM_BUG_ON(!count
);
579 DRM_MM_BUG_ON(!size
);
582 nodes
= vmalloc(array_size(count
, sizeof(*nodes
)));
586 order
= drm_random_order(count
, &prng
);
591 drm_mm_init(&mm
, 0, count
* size
);
593 for (mode
= insert_modes
; mode
->name
; mode
++) {
594 for (n
= 0; n
< count
; n
++) {
595 struct drm_mm_node tmp
;
597 node
= replace
? &tmp
: &nodes
[n
];
598 memset(node
, 0, sizeof(*node
));
599 if (!expect_insert(&mm
, node
, size
, 0, n
, mode
)) {
600 pr_err("%s insert failed, size %llu step %d\n",
601 mode
->name
, size
, n
);
606 drm_mm_replace_node(&tmp
, &nodes
[n
]);
607 if (drm_mm_node_allocated(&tmp
)) {
608 pr_err("replaced old-node still allocated! step %d\n",
613 if (!assert_node(&nodes
[n
], &mm
, size
, 0, n
)) {
614 pr_err("replaced node did not inherit parameters, size %llu step %d\n",
619 if (tmp
.start
!= nodes
[n
].start
) {
620 pr_err("replaced node mismatch location expected [%llx + %llx], found [%llx + %llx]\n",
622 nodes
[n
].start
, nodes
[n
].size
);
628 /* After random insertion the nodes should be in order */
629 if (!assert_continuous(&mm
, size
))
632 /* Repeated use should then fail */
633 if (!expect_insert_fail(&mm
, size
))
636 /* Remove one and reinsert, as the only hole it should refill itself */
637 for (n
= 0; n
< count
; n
++) {
638 u64 addr
= nodes
[n
].start
;
640 drm_mm_remove_node(&nodes
[n
]);
641 if (!expect_insert(&mm
, &nodes
[n
], size
, 0, n
, mode
)) {
642 pr_err("%s reinsert failed, size %llu step %d\n",
643 mode
->name
, size
, n
);
647 if (nodes
[n
].start
!= addr
) {
648 pr_err("%s reinsert node moved, step %d, expected %llx, found %llx\n",
649 mode
->name
, n
, addr
, nodes
[n
].start
);
653 if (!assert_continuous(&mm
, size
))
657 /* Remove several, reinsert, check full */
658 for_each_prime_number(n
, min(max_prime
, count
)) {
659 for (m
= 0; m
< n
; m
++) {
660 node
= &nodes
[order
[(o
+ m
) % count
]];
661 drm_mm_remove_node(node
);
664 for (m
= 0; m
< n
; m
++) {
665 node
= &nodes
[order
[(o
+ m
) % count
]];
666 if (!expect_insert(&mm
, node
, size
, 0, n
, mode
)) {
667 pr_err("%s multiple reinsert failed, size %llu step %d\n",
668 mode
->name
, size
, n
);
675 if (!assert_continuous(&mm
, size
))
678 if (!expect_insert_fail(&mm
, size
))
682 drm_mm_for_each_node_safe(node
, next
, &mm
)
683 drm_mm_remove_node(node
);
684 DRM_MM_BUG_ON(!drm_mm_clean(&mm
));
691 drm_mm_for_each_node_safe(node
, next
, &mm
)
692 drm_mm_remove_node(node
);
693 drm_mm_takedown(&mm
);
701 static int igt_insert(void *ignored
)
703 const unsigned int count
= min_t(unsigned int, BIT(10), max_iterations
);
707 for_each_prime_number_from(n
, 1, 54) {
708 u64 size
= BIT_ULL(n
);
710 ret
= __igt_insert(count
, size
- 1, false);
714 ret
= __igt_insert(count
, size
, false);
718 ret
= __igt_insert(count
, size
+ 1, false);
728 static int igt_replace(void *ignored
)
730 const unsigned int count
= min_t(unsigned int, BIT(10), max_iterations
);
734 /* Reuse igt_insert to exercise replacement by inserting a dummy node,
735 * then replacing it with the intended node. We want to check that
736 * the tree is intact and all the information we need is carried
737 * across to the target node.
740 for_each_prime_number_from(n
, 1, 54) {
741 u64 size
= BIT_ULL(n
);
743 ret
= __igt_insert(count
, size
- 1, true);
747 ret
= __igt_insert(count
, size
, true);
751 ret
= __igt_insert(count
, size
+ 1, true);
761 static bool expect_insert_in_range(struct drm_mm
*mm
, struct drm_mm_node
*node
,
762 u64 size
, u64 alignment
, unsigned long color
,
763 u64 range_start
, u64 range_end
,
764 const struct insert_mode
*mode
)
768 err
= drm_mm_insert_node_in_range(mm
, node
,
769 size
, alignment
, color
,
770 range_start
, range_end
,
773 pr_err("insert (size=%llu, alignment=%llu, color=%lu, mode=%s) nto range [%llx, %llx] failed with err=%d\n",
774 size
, alignment
, color
, mode
->name
,
775 range_start
, range_end
, err
);
779 if (!assert_node(node
, mm
, size
, alignment
, color
)) {
780 drm_mm_remove_node(node
);
787 static bool expect_insert_in_range_fail(struct drm_mm
*mm
,
792 struct drm_mm_node tmp
= {};
795 err
= drm_mm_insert_node_in_range(mm
, &tmp
,
797 range_start
, range_end
,
799 if (likely(err
== -ENOSPC
))
803 pr_err("impossible insert succeeded, node %llx + %llu, range [%llx, %llx]\n",
804 tmp
.start
, tmp
.size
, range_start
, range_end
);
805 drm_mm_remove_node(&tmp
);
807 pr_err("impossible insert failed with wrong error %d [expected %d], size %llu, range [%llx, %llx]\n",
808 err
, -ENOSPC
, size
, range_start
, range_end
);
814 static bool assert_contiguous_in_range(struct drm_mm
*mm
,
819 struct drm_mm_node
*node
;
822 if (!expect_insert_in_range_fail(mm
, size
, start
, end
))
825 n
= div64_u64(start
+ size
- 1, size
);
826 drm_mm_for_each_node(node
, mm
) {
827 if (node
->start
< start
|| node
->start
+ node
->size
> end
) {
828 pr_err("node %d out of range, address [%llx + %llu], range [%llx, %llx]\n",
829 n
, node
->start
, node
->start
+ node
->size
, start
, end
);
833 if (node
->start
!= n
* size
) {
834 pr_err("node %d out of order, expected start %llx, found %llx\n",
835 n
, n
* size
, node
->start
);
839 if (node
->size
!= size
) {
840 pr_err("node %d has wrong size, expected size %llx, found %llx\n",
841 n
, size
, node
->size
);
845 if (drm_mm_hole_follows(node
) &&
846 drm_mm_hole_node_end(node
) < end
) {
847 pr_err("node %d is followed by a hole!\n", n
);
855 node
= __drm_mm_interval_first(mm
, 0, start
- 1);
856 if (node
->allocated
) {
857 pr_err("node before start: node=%llx+%llu, start=%llx\n",
858 node
->start
, node
->size
, start
);
864 node
= __drm_mm_interval_first(mm
, end
, U64_MAX
);
865 if (node
->allocated
) {
866 pr_err("node after end: node=%llx+%llu, end=%llx\n",
867 node
->start
, node
->size
, end
);
875 static int __igt_insert_range(unsigned int count
, u64 size
, u64 start
, u64 end
)
877 const struct insert_mode
*mode
;
879 struct drm_mm_node
*nodes
, *node
, *next
;
880 unsigned int n
, start_n
, end_n
;
883 DRM_MM_BUG_ON(!count
);
884 DRM_MM_BUG_ON(!size
);
885 DRM_MM_BUG_ON(end
<= start
);
887 /* Very similar to __igt_insert(), but now instead of populating the
888 * full range of the drm_mm, we try to fill a small portion of it.
892 nodes
= vzalloc(array_size(count
, sizeof(*nodes
)));
897 drm_mm_init(&mm
, 0, count
* size
);
899 start_n
= div64_u64(start
+ size
- 1, size
);
900 end_n
= div64_u64(end
- size
, size
);
902 for (mode
= insert_modes
; mode
->name
; mode
++) {
903 for (n
= start_n
; n
<= end_n
; n
++) {
904 if (!expect_insert_in_range(&mm
, &nodes
[n
],
907 pr_err("%s insert failed, size %llu, step %d [%d, %d], range [%llx, %llx]\n",
915 if (!assert_contiguous_in_range(&mm
, size
, start
, end
)) {
916 pr_err("%s: range [%llx, %llx] not full after initialisation, size=%llu\n",
917 mode
->name
, start
, end
, size
);
921 /* Remove one and reinsert, it should refill itself */
922 for (n
= start_n
; n
<= end_n
; n
++) {
923 u64 addr
= nodes
[n
].start
;
925 drm_mm_remove_node(&nodes
[n
]);
926 if (!expect_insert_in_range(&mm
, &nodes
[n
],
929 pr_err("%s reinsert failed, step %d\n", mode
->name
, n
);
933 if (nodes
[n
].start
!= addr
) {
934 pr_err("%s reinsert node moved, step %d, expected %llx, found %llx\n",
935 mode
->name
, n
, addr
, nodes
[n
].start
);
940 if (!assert_contiguous_in_range(&mm
, size
, start
, end
)) {
941 pr_err("%s: range [%llx, %llx] not full after reinsertion, size=%llu\n",
942 mode
->name
, start
, end
, size
);
946 drm_mm_for_each_node_safe(node
, next
, &mm
)
947 drm_mm_remove_node(node
);
948 DRM_MM_BUG_ON(!drm_mm_clean(&mm
));
955 drm_mm_for_each_node_safe(node
, next
, &mm
)
956 drm_mm_remove_node(node
);
957 drm_mm_takedown(&mm
);
963 static int insert_outside_range(void)
966 const unsigned int start
= 1024;
967 const unsigned int end
= 2048;
968 const unsigned int size
= end
- start
;
970 drm_mm_init(&mm
, start
, size
);
972 if (!expect_insert_in_range_fail(&mm
, 1, 0, start
))
975 if (!expect_insert_in_range_fail(&mm
, size
,
976 start
- size
/2, start
+ (size
+1)/2))
979 if (!expect_insert_in_range_fail(&mm
, size
,
980 end
- (size
+1)/2, end
+ size
/2))
983 if (!expect_insert_in_range_fail(&mm
, 1, end
, end
+ size
))
986 drm_mm_takedown(&mm
);
990 static int igt_insert_range(void *ignored
)
992 const unsigned int count
= min_t(unsigned int, BIT(13), max_iterations
);
996 /* Check that requests outside the bounds of drm_mm are rejected. */
997 ret
= insert_outside_range();
1001 for_each_prime_number_from(n
, 1, 50) {
1002 const u64 size
= BIT_ULL(n
);
1003 const u64 max
= count
* size
;
1005 ret
= __igt_insert_range(count
, size
, 0, max
);
1009 ret
= __igt_insert_range(count
, size
, 1, max
);
1013 ret
= __igt_insert_range(count
, size
, 0, max
- 1);
1017 ret
= __igt_insert_range(count
, size
, 0, max
/2);
1021 ret
= __igt_insert_range(count
, size
, max
/2, max
);
1025 ret
= __igt_insert_range(count
, size
, max
/4+1, 3*max
/4-1);
1035 static int igt_align(void *ignored
)
1037 const struct insert_mode
*mode
;
1038 const unsigned int max_count
= min(8192u, max_prime
);
1040 struct drm_mm_node
*nodes
, *node
, *next
;
1044 /* For each of the possible insertion modes, we pick a few
1045 * arbitrary alignments and check that the inserted node
1046 * meets our requirements.
1049 nodes
= vzalloc(array_size(max_count
, sizeof(*nodes
)));
1053 drm_mm_init(&mm
, 1, U64_MAX
- 2);
1055 for (mode
= insert_modes
; mode
->name
; mode
++) {
1058 for_each_prime_number_from(prime
, 1, max_count
) {
1059 u64 size
= next_prime_number(prime
);
1061 if (!expect_insert(&mm
, &nodes
[i
],
1064 pr_err("%s insert failed with alignment=%d",
1072 drm_mm_for_each_node_safe(node
, next
, &mm
)
1073 drm_mm_remove_node(node
);
1074 DRM_MM_BUG_ON(!drm_mm_clean(&mm
));
1081 drm_mm_for_each_node_safe(node
, next
, &mm
)
1082 drm_mm_remove_node(node
);
1083 drm_mm_takedown(&mm
);
1089 static int igt_align_pot(int max
)
1092 struct drm_mm_node
*node
, *next
;
1096 /* Check that we can align to the full u64 address space */
1098 drm_mm_init(&mm
, 1, U64_MAX
- 2);
1100 for (bit
= max
- 1; bit
; bit
--) {
1103 node
= kzalloc(sizeof(*node
), GFP_KERNEL
);
1109 align
= BIT_ULL(bit
);
1110 size
= BIT_ULL(bit
-1) + 1;
1111 if (!expect_insert(&mm
, node
,
1113 &insert_modes
[0])) {
1114 pr_err("insert failed with alignment=%llx [%d]",
1124 drm_mm_for_each_node_safe(node
, next
, &mm
) {
1125 drm_mm_remove_node(node
);
1128 drm_mm_takedown(&mm
);
1132 static int igt_align32(void *ignored
)
1134 return igt_align_pot(32);
1137 static int igt_align64(void *ignored
)
1139 return igt_align_pot(64);
1142 static void show_scan(const struct drm_mm_scan
*scan
)
1144 pr_info("scan: hit [%llx, %llx], size=%lld, align=%lld, color=%ld\n",
1145 scan
->hit_start
, scan
->hit_end
,
1146 scan
->size
, scan
->alignment
, scan
->color
);
1149 static void show_holes(const struct drm_mm
*mm
, int count
)
1151 u64 hole_start
, hole_end
;
1152 struct drm_mm_node
*hole
;
1154 drm_mm_for_each_hole(hole
, mm
, hole_start
, hole_end
) {
1155 struct drm_mm_node
*next
= list_next_entry(hole
, node_list
);
1156 const char *node1
= NULL
, *node2
= NULL
;
1158 if (hole
->allocated
)
1159 node1
= kasprintf(GFP_KERNEL
,
1160 "[%llx + %lld, color=%ld], ",
1161 hole
->start
, hole
->size
, hole
->color
);
1163 if (next
->allocated
)
1164 node2
= kasprintf(GFP_KERNEL
,
1165 ", [%llx + %lld, color=%ld]",
1166 next
->start
, next
->size
, next
->color
);
1168 pr_info("%sHole [%llx - %llx, size %lld]%s\n",
1170 hole_start
, hole_end
, hole_end
- hole_start
,
1182 struct drm_mm_node node
;
1183 struct list_head link
;
1186 static bool evict_nodes(struct drm_mm_scan
*scan
,
1187 struct evict_node
*nodes
,
1188 unsigned int *order
,
1191 struct list_head
*evict_list
)
1193 struct evict_node
*e
, *en
;
1196 for (i
= 0; i
< count
; i
++) {
1197 e
= &nodes
[order
? order
[i
] : i
];
1198 list_add(&e
->link
, evict_list
);
1199 if (drm_mm_scan_add_block(scan
, &e
->node
))
1202 list_for_each_entry_safe(e
, en
, evict_list
, link
) {
1203 if (!drm_mm_scan_remove_block(scan
, &e
->node
))
1206 if (list_empty(evict_list
)) {
1207 pr_err("Failed to find eviction: size=%lld [avail=%d], align=%lld (color=%lu)\n",
1208 scan
->size
, count
, scan
->alignment
, scan
->color
);
1212 list_for_each_entry(e
, evict_list
, link
)
1213 drm_mm_remove_node(&e
->node
);
1216 struct drm_mm_node
*node
;
1218 while ((node
= drm_mm_scan_color_evict(scan
))) {
1219 e
= container_of(node
, typeof(*e
), node
);
1220 drm_mm_remove_node(&e
->node
);
1221 list_add(&e
->link
, evict_list
);
1224 if (drm_mm_scan_color_evict(scan
)) {
1225 pr_err("drm_mm_scan_color_evict unexpectedly reported overlapping nodes!\n");
1233 static bool evict_nothing(struct drm_mm
*mm
,
1234 unsigned int total_size
,
1235 struct evict_node
*nodes
)
1237 struct drm_mm_scan scan
;
1238 LIST_HEAD(evict_list
);
1239 struct evict_node
*e
;
1240 struct drm_mm_node
*node
;
1243 drm_mm_scan_init(&scan
, mm
, 1, 0, 0, 0);
1244 for (n
= 0; n
< total_size
; n
++) {
1246 list_add(&e
->link
, &evict_list
);
1247 drm_mm_scan_add_block(&scan
, &e
->node
);
1249 list_for_each_entry(e
, &evict_list
, link
)
1250 drm_mm_scan_remove_block(&scan
, &e
->node
);
1252 for (n
= 0; n
< total_size
; n
++) {
1255 if (!drm_mm_node_allocated(&e
->node
)) {
1256 pr_err("node[%d] no longer allocated!\n", n
);
1260 e
->link
.next
= NULL
;
1263 drm_mm_for_each_node(node
, mm
) {
1264 e
= container_of(node
, typeof(*e
), node
);
1265 e
->link
.next
= &e
->link
;
1268 for (n
= 0; n
< total_size
; n
++) {
1271 if (!e
->link
.next
) {
1272 pr_err("node[%d] no longer connected!\n", n
);
1277 return assert_continuous(mm
, nodes
[0].node
.size
);
1280 static bool evict_everything(struct drm_mm
*mm
,
1281 unsigned int total_size
,
1282 struct evict_node
*nodes
)
1284 struct drm_mm_scan scan
;
1285 LIST_HEAD(evict_list
);
1286 struct evict_node
*e
;
1290 drm_mm_scan_init(&scan
, mm
, total_size
, 0, 0, 0);
1291 for (n
= 0; n
< total_size
; n
++) {
1293 list_add(&e
->link
, &evict_list
);
1294 if (drm_mm_scan_add_block(&scan
, &e
->node
))
1299 list_for_each_entry(e
, &evict_list
, link
) {
1300 if (!drm_mm_scan_remove_block(&scan
, &e
->node
)) {
1302 pr_err("Node %lld not marked for eviction!\n",
1311 list_for_each_entry(e
, &evict_list
, link
)
1312 drm_mm_remove_node(&e
->node
);
1314 if (!assert_one_hole(mm
, 0, total_size
))
1317 list_for_each_entry(e
, &evict_list
, link
) {
1318 err
= drm_mm_reserve_node(mm
, &e
->node
);
1320 pr_err("Failed to reinsert node after eviction: start=%llx\n",
1326 return assert_continuous(mm
, nodes
[0].node
.size
);
1329 static int evict_something(struct drm_mm
*mm
,
1330 u64 range_start
, u64 range_end
,
1331 struct evict_node
*nodes
,
1332 unsigned int *order
,
1335 unsigned int alignment
,
1336 const struct insert_mode
*mode
)
1338 struct drm_mm_scan scan
;
1339 LIST_HEAD(evict_list
);
1340 struct evict_node
*e
;
1341 struct drm_mm_node tmp
;
1344 drm_mm_scan_init_with_range(&scan
, mm
,
1346 range_start
, range_end
,
1348 if (!evict_nodes(&scan
,
1349 nodes
, order
, count
, false,
1353 memset(&tmp
, 0, sizeof(tmp
));
1354 err
= drm_mm_insert_node_generic(mm
, &tmp
, size
, alignment
, 0,
1355 DRM_MM_INSERT_EVICT
);
1357 pr_err("Failed to insert into eviction hole: size=%d, align=%d\n",
1364 if (tmp
.start
< range_start
|| tmp
.start
+ tmp
.size
> range_end
) {
1365 pr_err("Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
1366 tmp
.start
, tmp
.size
, range_start
, range_end
);
1370 if (!assert_node(&tmp
, mm
, size
, alignment
, 0) ||
1371 drm_mm_hole_follows(&tmp
)) {
1372 pr_err("Inserted did not fill the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx, hole-follows?=%d\n",
1374 alignment
, misalignment(&tmp
, alignment
),
1375 tmp
.start
, drm_mm_hole_follows(&tmp
));
1379 drm_mm_remove_node(&tmp
);
1383 list_for_each_entry(e
, &evict_list
, link
) {
1384 err
= drm_mm_reserve_node(mm
, &e
->node
);
1386 pr_err("Failed to reinsert node after eviction: start=%llx\n",
1392 if (!assert_continuous(mm
, nodes
[0].node
.size
)) {
1393 pr_err("range is no longer continuous\n");
1400 static int igt_evict(void *ignored
)
1402 DRM_RND_STATE(prng
, random_seed
);
1403 const unsigned int size
= 8192;
1404 const struct insert_mode
*mode
;
1406 struct evict_node
*nodes
;
1407 struct drm_mm_node
*node
, *next
;
1408 unsigned int *order
, n
;
1411 /* Here we populate a full drm_mm and then try and insert a new node
1412 * by evicting other nodes in a random order. The drm_mm_scan should
1413 * pick the first matching hole it finds from the random list. We
1414 * repeat that for different allocation strategies, alignments and
1415 * sizes to try and stress the hole finder.
1419 nodes
= vzalloc(array_size(size
, sizeof(*nodes
)));
1423 order
= drm_random_order(size
, &prng
);
1428 drm_mm_init(&mm
, 0, size
);
1429 for (n
= 0; n
< size
; n
++) {
1430 err
= drm_mm_insert_node(&mm
, &nodes
[n
].node
, 1);
1432 pr_err("insert failed, step %d\n", n
);
1438 /* First check that using the scanner doesn't break the mm */
1439 if (!evict_nothing(&mm
, size
, nodes
)) {
1440 pr_err("evict_nothing() failed\n");
1443 if (!evict_everything(&mm
, size
, nodes
)) {
1444 pr_err("evict_everything() failed\n");
1448 for (mode
= evict_modes
; mode
->name
; mode
++) {
1449 for (n
= 1; n
<= size
; n
<<= 1) {
1450 drm_random_reorder(order
, size
, &prng
);
1451 err
= evict_something(&mm
, 0, U64_MAX
,
1456 pr_err("%s evict_something(size=%u) failed\n",
1463 for (n
= 1; n
< size
; n
<<= 1) {
1464 drm_random_reorder(order
, size
, &prng
);
1465 err
= evict_something(&mm
, 0, U64_MAX
,
1470 pr_err("%s evict_something(size=%u, alignment=%u) failed\n",
1471 mode
->name
, size
/2, n
);
1477 for_each_prime_number_from(n
, 1, min(size
, max_prime
)) {
1478 unsigned int nsize
= (size
- n
+ 1) / 2;
1480 DRM_MM_BUG_ON(!nsize
);
1482 drm_random_reorder(order
, size
, &prng
);
1483 err
= evict_something(&mm
, 0, U64_MAX
,
1488 pr_err("%s evict_something(size=%u, alignment=%u) failed\n",
1489 mode
->name
, nsize
, n
);
1500 drm_mm_for_each_node_safe(node
, next
, &mm
)
1501 drm_mm_remove_node(node
);
1502 drm_mm_takedown(&mm
);
1510 static int igt_evict_range(void *ignored
)
1512 DRM_RND_STATE(prng
, random_seed
);
1513 const unsigned int size
= 8192;
1514 const unsigned int range_size
= size
/ 2;
1515 const unsigned int range_start
= size
/ 4;
1516 const unsigned int range_end
= range_start
+ range_size
;
1517 const struct insert_mode
*mode
;
1519 struct evict_node
*nodes
;
1520 struct drm_mm_node
*node
, *next
;
1521 unsigned int *order
, n
;
1524 /* Like igt_evict() but now we are limiting the search to a
1525 * small portion of the full drm_mm.
1529 nodes
= vzalloc(array_size(size
, sizeof(*nodes
)));
1533 order
= drm_random_order(size
, &prng
);
1538 drm_mm_init(&mm
, 0, size
);
1539 for (n
= 0; n
< size
; n
++) {
1540 err
= drm_mm_insert_node(&mm
, &nodes
[n
].node
, 1);
1542 pr_err("insert failed, step %d\n", n
);
1548 for (mode
= evict_modes
; mode
->name
; mode
++) {
1549 for (n
= 1; n
<= range_size
; n
<<= 1) {
1550 drm_random_reorder(order
, size
, &prng
);
1551 err
= evict_something(&mm
, range_start
, range_end
,
1556 pr_err("%s evict_something(size=%u) failed with range [%u, %u]\n",
1557 mode
->name
, n
, range_start
, range_end
);
1562 for (n
= 1; n
<= range_size
; n
<<= 1) {
1563 drm_random_reorder(order
, size
, &prng
);
1564 err
= evict_something(&mm
, range_start
, range_end
,
1569 pr_err("%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
1570 mode
->name
, range_size
/2, n
, range_start
, range_end
);
1575 for_each_prime_number_from(n
, 1, min(range_size
, max_prime
)) {
1576 unsigned int nsize
= (range_size
- n
+ 1) / 2;
1578 DRM_MM_BUG_ON(!nsize
);
1580 drm_random_reorder(order
, size
, &prng
);
1581 err
= evict_something(&mm
, range_start
, range_end
,
1586 pr_err("%s evict_something(size=%u, alignment=%u) failed with range [%u, %u]\n",
1587 mode
->name
, nsize
, n
, range_start
, range_end
);
1597 drm_mm_for_each_node_safe(node
, next
, &mm
)
1598 drm_mm_remove_node(node
);
1599 drm_mm_takedown(&mm
);
1607 static unsigned int node_index(const struct drm_mm_node
*node
)
1609 return div64_u64(node
->start
, node
->size
);
1612 static int igt_topdown(void *ignored
)
1614 const struct insert_mode
*topdown
= &insert_modes
[TOPDOWN
];
1615 DRM_RND_STATE(prng
, random_seed
);
1616 const unsigned int count
= 8192;
1618 unsigned long *bitmap
;
1620 struct drm_mm_node
*nodes
, *node
, *next
;
1621 unsigned int *order
, n
, m
, o
= 0;
1624 /* When allocating top-down, we expect to be returned a node
1625 * from a suitable hole at the top of the drm_mm. We check that
1626 * the returned node does match the highest available slot.
1630 nodes
= vzalloc(array_size(count
, sizeof(*nodes
)));
1634 bitmap
= bitmap_zalloc(count
, GFP_KERNEL
);
1638 order
= drm_random_order(count
, &prng
);
1643 for (size
= 1; size
<= 64; size
<<= 1) {
1644 drm_mm_init(&mm
, 0, size
*count
);
1645 for (n
= 0; n
< count
; n
++) {
1646 if (!expect_insert(&mm
, &nodes
[n
],
1649 pr_err("insert failed, size %u step %d\n", size
, n
);
1653 if (drm_mm_hole_follows(&nodes
[n
])) {
1654 pr_err("hole after topdown insert %d, start=%llx\n, size=%u",
1655 n
, nodes
[n
].start
, size
);
1659 if (!assert_one_hole(&mm
, 0, size
*(count
- n
- 1)))
1663 if (!assert_continuous(&mm
, size
))
1666 drm_random_reorder(order
, count
, &prng
);
1667 for_each_prime_number_from(n
, 1, min(count
, max_prime
)) {
1668 for (m
= 0; m
< n
; m
++) {
1669 node
= &nodes
[order
[(o
+ m
) % count
]];
1670 drm_mm_remove_node(node
);
1671 __set_bit(node_index(node
), bitmap
);
1674 for (m
= 0; m
< n
; m
++) {
1677 node
= &nodes
[order
[(o
+ m
) % count
]];
1678 if (!expect_insert(&mm
, node
,
1681 pr_err("insert failed, step %d/%d\n", m
, n
);
1685 if (drm_mm_hole_follows(node
)) {
1686 pr_err("hole after topdown insert %d/%d, start=%llx\n",
1691 last
= find_last_bit(bitmap
, count
);
1692 if (node_index(node
) != last
) {
1693 pr_err("node %d/%d, size %d, not inserted into upmost hole, expected %d, found %d\n",
1694 m
, n
, size
, last
, node_index(node
));
1698 __clear_bit(last
, bitmap
);
1701 DRM_MM_BUG_ON(find_first_bit(bitmap
, count
) != count
);
1706 drm_mm_for_each_node_safe(node
, next
, &mm
)
1707 drm_mm_remove_node(node
);
1708 DRM_MM_BUG_ON(!drm_mm_clean(&mm
));
1714 drm_mm_for_each_node_safe(node
, next
, &mm
)
1715 drm_mm_remove_node(node
);
1716 drm_mm_takedown(&mm
);
1719 bitmap_free(bitmap
);
1726 static int igt_bottomup(void *ignored
)
1728 const struct insert_mode
*bottomup
= &insert_modes
[BOTTOMUP
];
1729 DRM_RND_STATE(prng
, random_seed
);
1730 const unsigned int count
= 8192;
1732 unsigned long *bitmap
;
1734 struct drm_mm_node
*nodes
, *node
, *next
;
1735 unsigned int *order
, n
, m
, o
= 0;
1738 /* Like igt_topdown, but instead of searching for the last hole,
1739 * we search for the first.
1743 nodes
= vzalloc(array_size(count
, sizeof(*nodes
)));
1747 bitmap
= bitmap_zalloc(count
, GFP_KERNEL
);
1751 order
= drm_random_order(count
, &prng
);
1756 for (size
= 1; size
<= 64; size
<<= 1) {
1757 drm_mm_init(&mm
, 0, size
*count
);
1758 for (n
= 0; n
< count
; n
++) {
1759 if (!expect_insert(&mm
, &nodes
[n
],
1762 pr_err("bottomup insert failed, size %u step %d\n", size
, n
);
1766 if (!assert_one_hole(&mm
, size
*(n
+ 1), size
*count
))
1770 if (!assert_continuous(&mm
, size
))
1773 drm_random_reorder(order
, count
, &prng
);
1774 for_each_prime_number_from(n
, 1, min(count
, max_prime
)) {
1775 for (m
= 0; m
< n
; m
++) {
1776 node
= &nodes
[order
[(o
+ m
) % count
]];
1777 drm_mm_remove_node(node
);
1778 __set_bit(node_index(node
), bitmap
);
1781 for (m
= 0; m
< n
; m
++) {
1784 node
= &nodes
[order
[(o
+ m
) % count
]];
1785 if (!expect_insert(&mm
, node
,
1788 pr_err("insert failed, step %d/%d\n", m
, n
);
1792 first
= find_first_bit(bitmap
, count
);
1793 if (node_index(node
) != first
) {
1794 pr_err("node %d/%d not inserted into bottom hole, expected %d, found %d\n",
1795 m
, n
, first
, node_index(node
));
1798 __clear_bit(first
, bitmap
);
1801 DRM_MM_BUG_ON(find_first_bit(bitmap
, count
) != count
);
1806 drm_mm_for_each_node_safe(node
, next
, &mm
)
1807 drm_mm_remove_node(node
);
1808 DRM_MM_BUG_ON(!drm_mm_clean(&mm
));
1814 drm_mm_for_each_node_safe(node
, next
, &mm
)
1815 drm_mm_remove_node(node
);
1816 drm_mm_takedown(&mm
);
1819 bitmap_free(bitmap
);
1826 static int __igt_once(unsigned int mode
)
1829 struct drm_mm_node rsvd_lo
, rsvd_hi
, node
;
1832 drm_mm_init(&mm
, 0, 7);
1834 memset(&rsvd_lo
, 0, sizeof(rsvd_lo
));
1837 err
= drm_mm_reserve_node(&mm
, &rsvd_lo
);
1839 pr_err("Could not reserve low node\n");
1843 memset(&rsvd_hi
, 0, sizeof(rsvd_hi
));
1846 err
= drm_mm_reserve_node(&mm
, &rsvd_hi
);
1848 pr_err("Could not reserve low node\n");
1852 if (!drm_mm_hole_follows(&rsvd_lo
) || !drm_mm_hole_follows(&rsvd_hi
)) {
1853 pr_err("Expected a hole after lo and high nodes!\n");
1858 memset(&node
, 0, sizeof(node
));
1859 err
= drm_mm_insert_node_generic(&mm
, &node
,
1861 mode
| DRM_MM_INSERT_ONCE
);
1863 pr_err("Unexpectedly inserted the node into the wrong hole: node.start=%llx\n",
1869 err
= drm_mm_insert_node_generic(&mm
, &node
, 2, 0, 0, mode
);
1871 pr_err("Could not insert the node into the available hole!\n");
1877 drm_mm_remove_node(&node
);
1879 drm_mm_remove_node(&rsvd_hi
);
1881 drm_mm_remove_node(&rsvd_lo
);
1883 drm_mm_takedown(&mm
);
1887 static int igt_lowest(void *ignored
)
1889 return __igt_once(DRM_MM_INSERT_LOW
);
1892 static int igt_highest(void *ignored
)
1894 return __igt_once(DRM_MM_INSERT_HIGH
);
1897 static void separate_adjacent_colors(const struct drm_mm_node
*node
,
1898 unsigned long color
,
1902 if (node
->allocated
&& node
->color
!= color
)
1905 node
= list_next_entry(node
, node_list
);
1906 if (node
->allocated
&& node
->color
!= color
)
1910 static bool colors_abutt(const struct drm_mm_node
*node
)
1912 if (!drm_mm_hole_follows(node
) &&
1913 list_next_entry(node
, node_list
)->allocated
) {
1914 pr_err("colors abutt; %ld [%llx + %llx] is next to %ld [%llx + %llx]!\n",
1915 node
->color
, node
->start
, node
->size
,
1916 list_next_entry(node
, node_list
)->color
,
1917 list_next_entry(node
, node_list
)->start
,
1918 list_next_entry(node
, node_list
)->size
);
1925 static int igt_color(void *ignored
)
1927 const unsigned int count
= min(4096u, max_iterations
);
1928 const struct insert_mode
*mode
;
1930 struct drm_mm_node
*node
, *nn
;
1932 int ret
= -EINVAL
, err
;
1934 /* Color adjustment complicates everything. First we just check
1935 * that when we insert a node we apply any color_adjustment callback.
1936 * The callback we use should ensure that there is a gap between
1937 * any two nodes, and so after each insertion we check that those
1938 * holes are inserted and that they are preserved.
1941 drm_mm_init(&mm
, 0, U64_MAX
);
1943 for (n
= 1; n
<= count
; n
++) {
1944 node
= kzalloc(sizeof(*node
), GFP_KERNEL
);
1950 if (!expect_insert(&mm
, node
,
1952 &insert_modes
[0])) {
1953 pr_err("insert failed, step %d\n", n
);
1959 drm_mm_for_each_node_safe(node
, nn
, &mm
) {
1960 if (node
->color
!= node
->size
) {
1961 pr_err("invalid color stored: expected %lld, found %ld\n",
1962 node
->size
, node
->color
);
1967 drm_mm_remove_node(node
);
1971 /* Now, let's start experimenting with applying a color callback */
1972 mm
.color_adjust
= separate_adjacent_colors
;
1973 for (mode
= insert_modes
; mode
->name
; mode
++) {
1976 node
= kzalloc(sizeof(*node
), GFP_KERNEL
);
1982 node
->size
= 1 + 2*count
;
1983 node
->color
= node
->size
;
1985 err
= drm_mm_reserve_node(&mm
, node
);
1987 pr_err("initial reserve failed!\n");
1992 last
= node
->start
+ node
->size
;
1994 for (n
= 1; n
<= count
; n
++) {
1997 node
= kzalloc(sizeof(*node
), GFP_KERNEL
);
2004 node
->size
= n
+ count
;
2005 node
->color
= node
->size
;
2007 err
= drm_mm_reserve_node(&mm
, node
);
2008 if (err
!= -ENOSPC
) {
2009 pr_err("reserve %d did not report color overlap! err=%d\n",
2014 node
->start
+= n
+ 1;
2015 rem
= misalignment(node
, n
+ count
);
2016 node
->start
+= n
+ count
- rem
;
2018 err
= drm_mm_reserve_node(&mm
, node
);
2020 pr_err("reserve %d failed, err=%d\n", n
, err
);
2025 last
= node
->start
+ node
->size
;
2028 for (n
= 1; n
<= count
; n
++) {
2029 node
= kzalloc(sizeof(*node
), GFP_KERNEL
);
2035 if (!expect_insert(&mm
, node
,
2038 pr_err("%s insert failed, step %d\n",
2045 drm_mm_for_each_node_safe(node
, nn
, &mm
) {
2048 if (node
->color
!= node
->size
) {
2049 pr_err("%s invalid color stored: expected %lld, found %ld\n",
2050 mode
->name
, node
->size
, node
->color
);
2055 if (colors_abutt(node
))
2058 div64_u64_rem(node
->start
, node
->size
, &rem
);
2060 pr_err("%s colored node misaligned, start=%llx expected alignment=%lld [rem=%lld]\n",
2061 mode
->name
, node
->start
, node
->size
, rem
);
2065 drm_mm_remove_node(node
);
2074 drm_mm_for_each_node_safe(node
, nn
, &mm
) {
2075 drm_mm_remove_node(node
);
2078 drm_mm_takedown(&mm
);
2082 static int evict_color(struct drm_mm
*mm
,
2083 u64 range_start
, u64 range_end
,
2084 struct evict_node
*nodes
,
2085 unsigned int *order
,
2088 unsigned int alignment
,
2089 unsigned long color
,
2090 const struct insert_mode
*mode
)
2092 struct drm_mm_scan scan
;
2093 LIST_HEAD(evict_list
);
2094 struct evict_node
*e
;
2095 struct drm_mm_node tmp
;
2098 drm_mm_scan_init_with_range(&scan
, mm
,
2099 size
, alignment
, color
,
2100 range_start
, range_end
,
2102 if (!evict_nodes(&scan
,
2103 nodes
, order
, count
, true,
2107 memset(&tmp
, 0, sizeof(tmp
));
2108 err
= drm_mm_insert_node_generic(mm
, &tmp
, size
, alignment
, color
,
2109 DRM_MM_INSERT_EVICT
);
2111 pr_err("Failed to insert into eviction hole: size=%d, align=%d, color=%lu, err=%d\n",
2112 size
, alignment
, color
, err
);
2118 if (tmp
.start
< range_start
|| tmp
.start
+ tmp
.size
> range_end
) {
2119 pr_err("Inserted [address=%llu + %llu] did not fit into the request range [%llu, %llu]\n",
2120 tmp
.start
, tmp
.size
, range_start
, range_end
);
2124 if (colors_abutt(&tmp
))
2127 if (!assert_node(&tmp
, mm
, size
, alignment
, color
)) {
2128 pr_err("Inserted did not fit the eviction hole: size=%lld [%d], align=%d [rem=%lld], start=%llx\n",
2130 alignment
, misalignment(&tmp
, alignment
), tmp
.start
);
2134 drm_mm_remove_node(&tmp
);
2138 list_for_each_entry(e
, &evict_list
, link
) {
2139 err
= drm_mm_reserve_node(mm
, &e
->node
);
2141 pr_err("Failed to reinsert node after eviction: start=%llx\n",
2151 static int igt_color_evict(void *ignored
)
2153 DRM_RND_STATE(prng
, random_seed
);
2154 const unsigned int total_size
= min(8192u, max_iterations
);
2155 const struct insert_mode
*mode
;
2156 unsigned long color
= 0;
2158 struct evict_node
*nodes
;
2159 struct drm_mm_node
*node
, *next
;
2160 unsigned int *order
, n
;
2163 /* Check that the drm_mm_scan also honours color adjustment when
2164 * choosing its victims to create a hole. Our color_adjust does not
2165 * allow two nodes to be placed together without an intervening hole
2166 * enlarging the set of victims that must be evicted.
2170 nodes
= vzalloc(array_size(total_size
, sizeof(*nodes
)));
2174 order
= drm_random_order(total_size
, &prng
);
2179 drm_mm_init(&mm
, 0, 2*total_size
- 1);
2180 mm
.color_adjust
= separate_adjacent_colors
;
2181 for (n
= 0; n
< total_size
; n
++) {
2182 if (!expect_insert(&mm
, &nodes
[n
].node
,
2184 &insert_modes
[0])) {
2185 pr_err("insert failed, step %d\n", n
);
2190 for (mode
= evict_modes
; mode
->name
; mode
++) {
2191 for (n
= 1; n
<= total_size
; n
<<= 1) {
2192 drm_random_reorder(order
, total_size
, &prng
);
2193 err
= evict_color(&mm
, 0, U64_MAX
,
2194 nodes
, order
, total_size
,
2198 pr_err("%s evict_color(size=%u) failed\n",
2204 for (n
= 1; n
< total_size
; n
<<= 1) {
2205 drm_random_reorder(order
, total_size
, &prng
);
2206 err
= evict_color(&mm
, 0, U64_MAX
,
2207 nodes
, order
, total_size
,
2208 total_size
/2, n
, color
++,
2211 pr_err("%s evict_color(size=%u, alignment=%u) failed\n",
2212 mode
->name
, total_size
/2, n
);
2217 for_each_prime_number_from(n
, 1, min(total_size
, max_prime
)) {
2218 unsigned int nsize
= (total_size
- n
+ 1) / 2;
2220 DRM_MM_BUG_ON(!nsize
);
2222 drm_random_reorder(order
, total_size
, &prng
);
2223 err
= evict_color(&mm
, 0, U64_MAX
,
2224 nodes
, order
, total_size
,
2228 pr_err("%s evict_color(size=%u, alignment=%u) failed\n",
2229 mode
->name
, nsize
, n
);
2241 drm_mm_for_each_node_safe(node
, next
, &mm
)
2242 drm_mm_remove_node(node
);
2243 drm_mm_takedown(&mm
);
2251 static int igt_color_evict_range(void *ignored
)
2253 DRM_RND_STATE(prng
, random_seed
);
2254 const unsigned int total_size
= 8192;
2255 const unsigned int range_size
= total_size
/ 2;
2256 const unsigned int range_start
= total_size
/ 4;
2257 const unsigned int range_end
= range_start
+ range_size
;
2258 const struct insert_mode
*mode
;
2259 unsigned long color
= 0;
2261 struct evict_node
*nodes
;
2262 struct drm_mm_node
*node
, *next
;
2263 unsigned int *order
, n
;
2266 /* Like igt_color_evict(), but limited to small portion of the full
2271 nodes
= vzalloc(array_size(total_size
, sizeof(*nodes
)));
2275 order
= drm_random_order(total_size
, &prng
);
2280 drm_mm_init(&mm
, 0, 2*total_size
- 1);
2281 mm
.color_adjust
= separate_adjacent_colors
;
2282 for (n
= 0; n
< total_size
; n
++) {
2283 if (!expect_insert(&mm
, &nodes
[n
].node
,
2285 &insert_modes
[0])) {
2286 pr_err("insert failed, step %d\n", n
);
2291 for (mode
= evict_modes
; mode
->name
; mode
++) {
2292 for (n
= 1; n
<= range_size
; n
<<= 1) {
2293 drm_random_reorder(order
, range_size
, &prng
);
2294 err
= evict_color(&mm
, range_start
, range_end
,
2295 nodes
, order
, total_size
,
2299 pr_err("%s evict_color(size=%u) failed for range [%x, %x]\n",
2300 mode
->name
, n
, range_start
, range_end
);
2305 for (n
= 1; n
< range_size
; n
<<= 1) {
2306 drm_random_reorder(order
, total_size
, &prng
);
2307 err
= evict_color(&mm
, range_start
, range_end
,
2308 nodes
, order
, total_size
,
2309 range_size
/2, n
, color
++,
2312 pr_err("%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
2313 mode
->name
, total_size
/2, n
, range_start
, range_end
);
2318 for_each_prime_number_from(n
, 1, min(range_size
, max_prime
)) {
2319 unsigned int nsize
= (range_size
- n
+ 1) / 2;
2321 DRM_MM_BUG_ON(!nsize
);
2323 drm_random_reorder(order
, total_size
, &prng
);
2324 err
= evict_color(&mm
, range_start
, range_end
,
2325 nodes
, order
, total_size
,
2329 pr_err("%s evict_color(size=%u, alignment=%u) failed for range [%x, %x]\n",
2330 mode
->name
, nsize
, n
, range_start
, range_end
);
2342 drm_mm_for_each_node_safe(node
, next
, &mm
)
2343 drm_mm_remove_node(node
);
2344 drm_mm_takedown(&mm
);
2352 #include "drm_selftest.c"
2354 static int __init
test_drm_mm_init(void)
2358 while (!random_seed
)
2359 random_seed
= get_random_int();
2361 pr_info("Testing DRM range manger (struct drm_mm), with random_seed=0x%x max_iterations=%u max_prime=%u\n",
2362 random_seed
, max_iterations
, max_prime
);
2363 err
= run_selftests(selftests
, ARRAY_SIZE(selftests
), NULL
);
2365 return err
> 0 ? 0 : err
;
2368 static void __exit
test_drm_mm_exit(void)
2372 module_init(test_drm_mm_init
);
2373 module_exit(test_drm_mm_exit
);
2375 module_param(random_seed
, uint
, 0400);
2376 module_param(max_iterations
, uint
, 0400);
2377 module_param(max_prime
, uint
, 0400);
2379 MODULE_AUTHOR("Intel Corporation");
2380 MODULE_LICENSE("GPL");