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