1 // SPDX-License-Identifier: MIT 2 /* 3 * Copyright © 2019 Intel Corporation 4 * Copyright © 2022 Maíra Canal <mairacanal@riseup.net> 5 */ 6 7 #include <kunit/test.h> 8 9 #include <linux/prime_numbers.h> 10 #include <linux/sched/signal.h> 11 #include <linux/sizes.h> 12 13 #include <linux/gpu_buddy.h> 14 15 #include "gpu_random.h" 16 17 static unsigned int random_seed; 18 19 static inline u64 get_size(int order, u64 chunk_size) 20 { 21 return (1 << order) * chunk_size; 22 } 23 24 static void gpu_test_buddy_subtree_offset_alignment_stress(struct kunit *test) 25 { 26 struct gpu_buddy_block *block; 27 struct rb_node *node = NULL; 28 const u64 mm_size = SZ_2M; 29 const u64 alignments[] = { 30 SZ_1M, 31 SZ_512K, 32 SZ_256K, 33 SZ_128K, 34 SZ_64K, 35 SZ_32K, 36 SZ_16K, 37 SZ_8K, 38 }; 39 struct list_head allocated[ARRAY_SIZE(alignments)]; 40 unsigned int i, max_subtree_align = 0; 41 int ret, order; 42 struct gpu_buddy mm; 43 44 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K), 45 "buddy_init failed\n"); 46 47 for (i = 0; i < ARRAY_SIZE(allocated); i++) 48 INIT_LIST_HEAD(&allocated[i]); 49 50 /* 51 * Exercise subtree_max_alignment tracking by allocating blocks with descending 52 * alignment constraints and freeing them in reverse order. This verifies that 53 * free-tree augmentation correctly propagates the maximum offset alignment 54 * present in each subtree at every stage. 55 */ 56 57 for (i = 0; i < ARRAY_SIZE(alignments); i++) { 58 struct gpu_buddy_block *root = NULL; 59 unsigned int expected; 60 u64 align; 61 62 align = alignments[i]; 63 expected = ilog2(align) - 1; 64 65 for (;;) { 66 ret = gpu_buddy_alloc_blocks(&mm, 67 0, mm_size, 68 SZ_4K, align, 69 &allocated[i], 70 0); 71 if (ret) 72 break; 73 74 block = list_last_entry(&allocated[i], 75 struct gpu_buddy_block, 76 link); 77 KUNIT_EXPECT_TRUE(test, IS_ALIGNED(gpu_buddy_block_offset(block), align)); 78 } 79 80 for (order = mm.max_order; order >= 0 && !root; order--) { 81 node = mm.free_tree[order].rb_node; 82 if (node) 83 root = container_of(node, 84 struct gpu_buddy_block, 85 rb); 86 } 87 88 KUNIT_ASSERT_NOT_NULL(test, root); 89 KUNIT_EXPECT_EQ(test, root->subtree_max_alignment, expected); 90 } 91 92 for (i = ARRAY_SIZE(alignments); i-- > 0; ) { 93 gpu_buddy_free_list(&mm, &allocated[i], 0); 94 95 for (order = 0; order <= mm.max_order; order++) { 96 node = mm.free_tree[order].rb_node; 97 if (!node) 98 continue; 99 100 block = container_of(node, struct gpu_buddy_block, rb); 101 max_subtree_align = max(max_subtree_align, 102 block->subtree_max_alignment); 103 } 104 105 KUNIT_EXPECT_GE(test, max_subtree_align, ilog2(alignments[i])); 106 } 107 108 gpu_buddy_fini(&mm); 109 } 110 111 static void gpu_test_buddy_offset_aligned_allocation(struct kunit *test) 112 { 113 struct gpu_buddy_block *block, *tmp; 114 int num_blocks, i, count = 0; 115 LIST_HEAD(allocated); 116 struct gpu_buddy mm; 117 u64 mm_size = SZ_4M; 118 LIST_HEAD(freed); 119 120 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K), 121 "buddy_init failed\n"); 122 123 num_blocks = mm_size / SZ_256K; 124 /* 125 * Allocate multiple sizes under a fixed offset alignment. 126 * Ensures alignment handling is independent of allocation size and 127 * exercises subtree max-alignment pruning for small requests. 128 */ 129 for (i = 0; i < num_blocks; i++) 130 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_256K, 131 &allocated, 0), 132 "buddy_alloc hit an error size=%u\n", SZ_8K); 133 134 list_for_each_entry(block, &allocated, link) { 135 /* Ensure the allocated block uses the expected 8 KB size */ 136 KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_8K); 137 /* Ensure the block starts at a 256 KB-aligned offset for proper alignment */ 138 KUNIT_EXPECT_TRUE(test, IS_ALIGNED(gpu_buddy_block_offset(block), SZ_256K)); 139 } 140 gpu_buddy_free_list(&mm, &allocated, 0); 141 142 for (i = 0; i < num_blocks; i++) 143 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K, 144 &allocated, 0), 145 "buddy_alloc hit an error size=%u\n", SZ_16K); 146 147 list_for_each_entry(block, &allocated, link) { 148 /* Ensure the allocated block uses the expected 16 KB size */ 149 KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, block), SZ_16K); 150 /* Ensure the block starts at a 256 KB-aligned offset for proper alignment */ 151 KUNIT_EXPECT_TRUE(test, IS_ALIGNED(gpu_buddy_block_offset(block), SZ_256K)); 152 } 153 154 /* 155 * Free alternating aligned blocks to introduce fragmentation. 156 * Ensures offset-aligned allocations remain valid after frees and 157 * verifies subtree max-alignment metadata is correctly maintained. 158 */ 159 list_for_each_entry_safe(block, tmp, &allocated, link) { 160 if (count % 2 == 0) 161 list_move_tail(&block->link, &freed); 162 count++; 163 } 164 gpu_buddy_free_list(&mm, &freed, 0); 165 166 for (i = 0; i < num_blocks / 2; i++) 167 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K, 168 &allocated, 0), 169 "buddy_alloc hit an error size=%u\n", SZ_16K); 170 171 /* 172 * Allocate with offset alignment after all slots are used; must fail. 173 * Confirms that no aligned offsets remain. 174 */ 175 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_16K, SZ_256K, 176 &allocated, 0), 177 "buddy_alloc hit an error size=%u\n", SZ_16K); 178 gpu_buddy_free_list(&mm, &allocated, 0); 179 gpu_buddy_fini(&mm); 180 } 181 182 static void gpu_test_buddy_fragmentation_performance(struct kunit *test) 183 { 184 struct gpu_buddy_block *block, *tmp; 185 int num_blocks, i, ret, count = 0; 186 LIST_HEAD(allocated_blocks); 187 unsigned long elapsed_ms; 188 LIST_HEAD(reverse_list); 189 LIST_HEAD(test_blocks); 190 LIST_HEAD(clear_list); 191 LIST_HEAD(dirty_list); 192 LIST_HEAD(free_list); 193 struct gpu_buddy mm; 194 u64 mm_size = SZ_4G; 195 ktime_t start, end; 196 197 /* 198 * Allocation under severe fragmentation 199 * 200 * Create severe fragmentation by allocating the entire 4 GiB address space 201 * as tiny 8 KiB blocks but forcing a 64 KiB alignment. The resulting pattern 202 * leaves many scattered holes. Split the allocations into two groups and 203 * return them with different flags to block coalescing, then repeatedly 204 * allocate and free 64 KiB blocks while timing the loop. This stresses how 205 * quickly the allocator can satisfy larger, aligned requests from a pool of 206 * highly fragmented space. 207 */ 208 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K), 209 "buddy_init failed\n"); 210 211 num_blocks = mm_size / SZ_64K; 212 213 start = ktime_get(); 214 /* Allocate with maximum fragmentation - 8K blocks with 64K alignment */ 215 for (i = 0; i < num_blocks; i++) 216 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_64K, 217 &allocated_blocks, 0), 218 "buddy_alloc hit an error size=%u\n", SZ_8K); 219 220 list_for_each_entry_safe(block, tmp, &allocated_blocks, link) { 221 if (count % 4 == 0 || count % 4 == 3) 222 list_move_tail(&block->link, &clear_list); 223 else 224 list_move_tail(&block->link, &dirty_list); 225 count++; 226 } 227 228 /* Free with different flags to ensure no coalescing */ 229 gpu_buddy_free_list(&mm, &clear_list, GPU_BUDDY_CLEARED); 230 gpu_buddy_free_list(&mm, &dirty_list, 0); 231 232 for (i = 0; i < num_blocks; i++) 233 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_64K, SZ_64K, 234 &test_blocks, 0), 235 "buddy_alloc hit an error size=%u\n", SZ_64K); 236 gpu_buddy_free_list(&mm, &test_blocks, 0); 237 238 end = ktime_get(); 239 elapsed_ms = ktime_to_ms(ktime_sub(end, start)); 240 241 kunit_info(test, "Fragmented allocation took %lu ms\n", elapsed_ms); 242 243 gpu_buddy_fini(&mm); 244 245 /* 246 * Reverse free order under fragmentation 247 * 248 * Construct a fragmented 4 GiB space by allocating every 8 KiB block with 249 * 64 KiB alignment, creating a dense scatter of small regions. Half of the 250 * blocks are selectively freed to form sparse gaps, while the remaining 251 * allocations are preserved, reordered in reverse, and released back with 252 * the cleared flag. This models a pathological reverse-ordered free pattern 253 * and measures how quickly the allocator can merge and reclaim space when 254 * deallocation occurs in the opposite order of allocation, exposing the 255 * cost difference between a linear freelist scan and an ordered tree lookup. 256 */ 257 ret = gpu_buddy_init(&mm, mm_size, SZ_4K); 258 KUNIT_ASSERT_EQ(test, ret, 0); 259 260 start = ktime_get(); 261 /* Allocate maximum fragmentation */ 262 for (i = 0; i < num_blocks; i++) 263 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, SZ_8K, SZ_64K, 264 &allocated_blocks, 0), 265 "buddy_alloc hit an error size=%u\n", SZ_8K); 266 267 list_for_each_entry_safe(block, tmp, &allocated_blocks, link) { 268 if (count % 2 == 0) 269 list_move_tail(&block->link, &free_list); 270 count++; 271 } 272 gpu_buddy_free_list(&mm, &free_list, GPU_BUDDY_CLEARED); 273 274 list_for_each_entry_safe_reverse(block, tmp, &allocated_blocks, link) 275 list_move(&block->link, &reverse_list); 276 gpu_buddy_free_list(&mm, &reverse_list, GPU_BUDDY_CLEARED); 277 278 end = ktime_get(); 279 elapsed_ms = ktime_to_ms(ktime_sub(end, start)); 280 281 kunit_info(test, "Reverse-ordered free took %lu ms\n", elapsed_ms); 282 283 gpu_buddy_fini(&mm); 284 } 285 286 static void gpu_test_buddy_alloc_range_bias(struct kunit *test) 287 { 288 u32 mm_size, size, ps, bias_size, bias_start, bias_end, bias_rem; 289 GPU_RND_STATE(prng, random_seed); 290 unsigned int i, count, *order; 291 struct gpu_buddy_block *block; 292 unsigned long flags; 293 struct gpu_buddy mm; 294 LIST_HEAD(allocated); 295 296 bias_size = SZ_1M; 297 ps = roundup_pow_of_two(prandom_u32_state(&prng) % bias_size); 298 ps = max(SZ_4K, ps); 299 mm_size = (SZ_8M-1) & ~(ps-1); /* Multiple roots */ 300 301 kunit_info(test, "mm_size=%u, ps=%u\n", mm_size, ps); 302 303 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, ps), 304 "buddy_init failed\n"); 305 306 count = mm_size / bias_size; 307 order = gpu_random_order(count, &prng); 308 KUNIT_EXPECT_TRUE(test, order); 309 310 /* 311 * Idea is to split the address space into uniform bias ranges, and then 312 * in some random order allocate within each bias, using various 313 * patterns within. This should detect if allocations leak out from a 314 * given bias, for example. 315 */ 316 317 for (i = 0; i < count; i++) { 318 LIST_HEAD(tmp); 319 u32 size; 320 321 bias_start = order[i] * bias_size; 322 bias_end = bias_start + bias_size; 323 bias_rem = bias_size; 324 325 /* internal round_up too big */ 326 KUNIT_ASSERT_TRUE_MSG(test, 327 gpu_buddy_alloc_blocks(&mm, bias_start, 328 bias_end, bias_size + ps, bias_size, 329 &allocated, 330 GPU_BUDDY_RANGE_ALLOCATION), 331 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n", 332 bias_start, bias_end, bias_size, bias_size); 333 334 /* size too big */ 335 KUNIT_ASSERT_TRUE_MSG(test, 336 gpu_buddy_alloc_blocks(&mm, bias_start, 337 bias_end, bias_size + ps, ps, 338 &allocated, 339 GPU_BUDDY_RANGE_ALLOCATION), 340 "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n", 341 bias_start, bias_end, bias_size + ps, ps); 342 343 /* bias range too small for size */ 344 KUNIT_ASSERT_TRUE_MSG(test, 345 gpu_buddy_alloc_blocks(&mm, bias_start + ps, 346 bias_end, bias_size, ps, 347 &allocated, 348 GPU_BUDDY_RANGE_ALLOCATION), 349 "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n", 350 bias_start + ps, bias_end, bias_size, ps); 351 352 /* bias misaligned */ 353 KUNIT_ASSERT_TRUE_MSG(test, 354 gpu_buddy_alloc_blocks(&mm, bias_start + ps, 355 bias_end - ps, 356 bias_size >> 1, bias_size >> 1, 357 &allocated, 358 GPU_BUDDY_RANGE_ALLOCATION), 359 "buddy_alloc h didn't fail with bias(%x-%x), size=%u, ps=%u\n", 360 bias_start + ps, bias_end - ps, bias_size >> 1, bias_size >> 1); 361 362 /* single big page */ 363 KUNIT_ASSERT_FALSE_MSG(test, 364 gpu_buddy_alloc_blocks(&mm, bias_start, 365 bias_end, bias_size, bias_size, 366 &tmp, 367 GPU_BUDDY_RANGE_ALLOCATION), 368 "buddy_alloc i failed with bias(%x-%x), size=%u, ps=%u\n", 369 bias_start, bias_end, bias_size, bias_size); 370 gpu_buddy_free_list(&mm, &tmp, 0); 371 372 /* single page with internal round_up */ 373 KUNIT_ASSERT_FALSE_MSG(test, 374 gpu_buddy_alloc_blocks(&mm, bias_start, 375 bias_end, ps, bias_size, 376 &tmp, 377 GPU_BUDDY_RANGE_ALLOCATION), 378 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n", 379 bias_start, bias_end, ps, bias_size); 380 gpu_buddy_free_list(&mm, &tmp, 0); 381 382 /* random size within */ 383 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps); 384 if (size) 385 KUNIT_ASSERT_FALSE_MSG(test, 386 gpu_buddy_alloc_blocks(&mm, bias_start, 387 bias_end, size, ps, 388 &tmp, 389 GPU_BUDDY_RANGE_ALLOCATION), 390 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n", 391 bias_start, bias_end, size, ps); 392 393 bias_rem -= size; 394 /* too big for current avail */ 395 KUNIT_ASSERT_TRUE_MSG(test, 396 gpu_buddy_alloc_blocks(&mm, bias_start, 397 bias_end, bias_rem + ps, ps, 398 &allocated, 399 GPU_BUDDY_RANGE_ALLOCATION), 400 "buddy_alloc didn't fail with bias(%x-%x), size=%u, ps=%u\n", 401 bias_start, bias_end, bias_rem + ps, ps); 402 403 if (bias_rem) { 404 /* random fill of the remainder */ 405 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps); 406 size = max(size, ps); 407 408 KUNIT_ASSERT_FALSE_MSG(test, 409 gpu_buddy_alloc_blocks(&mm, bias_start, 410 bias_end, size, ps, 411 &allocated, 412 GPU_BUDDY_RANGE_ALLOCATION), 413 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n", 414 bias_start, bias_end, size, ps); 415 /* 416 * Intentionally allow some space to be left 417 * unallocated, and ideally not always on the bias 418 * boundaries. 419 */ 420 gpu_buddy_free_list(&mm, &tmp, 0); 421 } else { 422 list_splice_tail(&tmp, &allocated); 423 } 424 } 425 426 kfree(order); 427 gpu_buddy_free_list(&mm, &allocated, 0); 428 gpu_buddy_fini(&mm); 429 430 /* 431 * Something more free-form. Idea is to pick a random starting bias 432 * range within the address space and then start filling it up. Also 433 * randomly grow the bias range in both directions as we go along. This 434 * should give us bias start/end which is not always uniform like above, 435 * and in some cases will require the allocator to jump over already 436 * allocated nodes in the middle of the address space. 437 */ 438 439 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, ps), 440 "buddy_init failed\n"); 441 442 bias_start = round_up(prandom_u32_state(&prng) % (mm_size - ps), ps); 443 bias_end = round_up(bias_start + prandom_u32_state(&prng) % (mm_size - bias_start), ps); 444 bias_end = max(bias_end, bias_start + ps); 445 bias_rem = bias_end - bias_start; 446 447 do { 448 u32 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps); 449 450 KUNIT_ASSERT_FALSE_MSG(test, 451 gpu_buddy_alloc_blocks(&mm, bias_start, 452 bias_end, size, ps, 453 &allocated, 454 GPU_BUDDY_RANGE_ALLOCATION), 455 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n", 456 bias_start, bias_end, size, ps); 457 bias_rem -= size; 458 459 /* 460 * Try to randomly grow the bias range in both directions, or 461 * only one, or perhaps don't grow at all. 462 */ 463 do { 464 u32 old_bias_start = bias_start; 465 u32 old_bias_end = bias_end; 466 467 if (bias_start) 468 bias_start -= round_up(prandom_u32_state(&prng) % bias_start, ps); 469 if (bias_end != mm_size) 470 bias_end += round_up(prandom_u32_state(&prng) % (mm_size - bias_end), ps); 471 472 bias_rem += old_bias_start - bias_start; 473 bias_rem += bias_end - old_bias_end; 474 } while (!bias_rem && (bias_start || bias_end != mm_size)); 475 } while (bias_rem); 476 477 KUNIT_ASSERT_EQ(test, bias_start, 0); 478 KUNIT_ASSERT_EQ(test, bias_end, mm_size); 479 KUNIT_ASSERT_TRUE_MSG(test, 480 gpu_buddy_alloc_blocks(&mm, bias_start, bias_end, 481 ps, ps, 482 &allocated, 483 GPU_BUDDY_RANGE_ALLOCATION), 484 "buddy_alloc passed with bias(%x-%x), size=%u\n", 485 bias_start, bias_end, ps); 486 487 gpu_buddy_free_list(&mm, &allocated, 0); 488 gpu_buddy_fini(&mm); 489 490 /* 491 * Allocate cleared blocks in the bias range when the GPU buddy's clear avail is 492 * zero. This will validate the bias range allocation in scenarios like system boot 493 * when no cleared blocks are available and exercise the fallback path too. The resulting 494 * blocks should always be dirty. 495 */ 496 497 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, ps), 498 "buddy_init failed\n"); 499 500 bias_start = round_up(prandom_u32_state(&prng) % (mm_size - ps), ps); 501 bias_end = round_up(bias_start + prandom_u32_state(&prng) % (mm_size - bias_start), ps); 502 bias_end = max(bias_end, bias_start + ps); 503 bias_rem = bias_end - bias_start; 504 505 flags = GPU_BUDDY_CLEAR_ALLOCATION | GPU_BUDDY_RANGE_ALLOCATION; 506 size = max(round_up(prandom_u32_state(&prng) % bias_rem, ps), ps); 507 508 KUNIT_ASSERT_FALSE_MSG(test, 509 gpu_buddy_alloc_blocks(&mm, bias_start, 510 bias_end, size, ps, 511 &allocated, 512 flags), 513 "buddy_alloc failed with bias(%x-%x), size=%u, ps=%u\n", 514 bias_start, bias_end, size, ps); 515 516 list_for_each_entry(block, &allocated, link) 517 KUNIT_EXPECT_EQ(test, gpu_buddy_block_is_clear(block), false); 518 519 gpu_buddy_free_list(&mm, &allocated, 0); 520 gpu_buddy_fini(&mm); 521 } 522 523 static void gpu_test_buddy_alloc_range(struct kunit *test) 524 { 525 GPU_RND_STATE(prng, random_seed); 526 struct gpu_buddy_block *block; 527 struct gpu_buddy mm; 528 u32 mm_size, total; 529 LIST_HEAD(blocks); 530 LIST_HEAD(tmp); 531 u32 ps = SZ_4K; 532 int ret; 533 534 mm_size = SZ_16M; 535 536 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, ps), 537 "buddy_init failed\n"); 538 539 /* 540 * Basic exact-range allocation. 541 * Allocate the entire mm as one exact range (start + size == end). 542 * This is the simplest case exercising __gpu_buddy_alloc_range. 543 */ 544 ret = gpu_buddy_alloc_blocks(&mm, 0, mm_size, mm_size, ps, &blocks, 0); 545 KUNIT_ASSERT_EQ_MSG(test, ret, 0, 546 "exact-range alloc of full mm failed\n"); 547 548 total = 0; 549 list_for_each_entry(block, &blocks, link) { 550 u64 offset = gpu_buddy_block_offset(block); 551 u64 bsize = gpu_buddy_block_size(&mm, block); 552 553 KUNIT_EXPECT_TRUE_MSG(test, offset + bsize <= (u64)mm_size, 554 "block [%llx, %llx) outside mm\n", offset, offset + bsize); 555 total += (u32)bsize; 556 } 557 KUNIT_EXPECT_EQ(test, total, mm_size); 558 KUNIT_EXPECT_EQ(test, mm.avail, 0ULL); 559 560 /* Full mm should be exhausted */ 561 ret = gpu_buddy_alloc_blocks(&mm, 0, ps, ps, ps, &tmp, 0); 562 KUNIT_EXPECT_NE_MSG(test, ret, 0, "alloc should fail when mm is full\n"); 563 564 gpu_buddy_free_list(&mm, &blocks, 0); 565 KUNIT_EXPECT_EQ(test, mm.avail, (u64)mm_size); 566 gpu_buddy_fini(&mm); 567 568 /* 569 * Exact-range allocation of sub-ranges. 570 * Split the mm into four equal quarters and allocate each as an exact 571 * range. Validates splitting and non-overlapping exact allocations. 572 */ 573 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 574 575 { 576 u32 quarter = mm_size / 4; 577 int i; 578 579 for (i = 0; i < 4; i++) { 580 u32 start = i * quarter; 581 u32 end = start + quarter; 582 583 ret = gpu_buddy_alloc_blocks(&mm, start, end, quarter, ps, &blocks, 0); 584 KUNIT_ASSERT_EQ_MSG(test, ret, 0, 585 "exact-range alloc quarter %d [%x, %x) failed\n", 586 i, start, end); 587 } 588 KUNIT_EXPECT_EQ(test, mm.avail, 0ULL); 589 gpu_buddy_free_list(&mm, &blocks, 0); 590 } 591 592 gpu_buddy_fini(&mm); 593 594 /* 595 * Minimum chunk-size exact range at various offsets. 596 * Allocate single-page exact ranges at the start, middle and end. 597 */ 598 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 599 600 ret = gpu_buddy_alloc_blocks(&mm, 0, ps, ps, ps, &blocks, 0); 601 KUNIT_ASSERT_EQ(test, ret, 0); 602 603 ret = gpu_buddy_alloc_blocks(&mm, mm_size / 2, mm_size / 2 + ps, ps, ps, &blocks, 0); 604 KUNIT_ASSERT_EQ(test, ret, 0); 605 606 ret = gpu_buddy_alloc_blocks(&mm, mm_size - ps, mm_size, ps, ps, &blocks, 0); 607 KUNIT_ASSERT_EQ(test, ret, 0); 608 609 total = 0; 610 list_for_each_entry(block, &blocks, link) 611 total += (u32)gpu_buddy_block_size(&mm, block); 612 KUNIT_EXPECT_EQ(test, total, 3 * ps); 613 614 gpu_buddy_free_list(&mm, &blocks, 0); 615 gpu_buddy_fini(&mm); 616 617 /* 618 * Non power-of-two mm size (multiple roots). 619 * Exact-range allocations that span root boundaries must still work. 620 */ 621 mm_size = SZ_4M + SZ_2M + SZ_1M; /* 7 MiB, three roots */ 622 623 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 624 KUNIT_EXPECT_GT(test, mm.n_roots, 1U); 625 626 /* Allocate first 4M root exactly */ 627 ret = gpu_buddy_alloc_blocks(&mm, 0, SZ_4M, SZ_4M, ps, &blocks, 0); 628 KUNIT_ASSERT_EQ(test, ret, 0); 629 630 /* Allocate second root (4M-6M) exactly */ 631 ret = gpu_buddy_alloc_blocks(&mm, SZ_4M, SZ_4M + SZ_2M, SZ_2M, ps, &blocks, 0); 632 KUNIT_ASSERT_EQ(test, ret, 0); 633 634 /* Allocate third root (6M-7M) exactly */ 635 ret = gpu_buddy_alloc_blocks(&mm, SZ_4M + SZ_2M, mm_size, SZ_1M, ps, &blocks, 0); 636 KUNIT_ASSERT_EQ(test, ret, 0); 637 638 KUNIT_EXPECT_EQ(test, mm.avail, 0ULL); 639 gpu_buddy_free_list(&mm, &blocks, 0); 640 641 /* Cross-root exact-range: the entire non-pot mm */ 642 ret = gpu_buddy_alloc_blocks(&mm, 0, mm_size, mm_size, ps, &blocks, 0); 643 KUNIT_ASSERT_EQ(test, ret, 0); 644 KUNIT_EXPECT_EQ(test, mm.avail, 0ULL); 645 646 gpu_buddy_free_list(&mm, &blocks, 0); 647 gpu_buddy_fini(&mm); 648 649 /* 650 * Randomized exact-range allocations. 651 * Divide the mm into N random-sized, contiguous, page-aligned slices 652 * and allocate each as an exact range in random order. 653 */ 654 mm_size = SZ_16M; 655 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 656 657 { 658 #define N_RAND_RANGES 16 659 u32 ranges[N_RAND_RANGES + 1]; /* boundaries */ 660 u32 order_arr[N_RAND_RANGES]; 661 u32 remaining = mm_size; 662 int i; 663 664 ranges[0] = 0; 665 for (i = 0; i < N_RAND_RANGES - 1; i++) { 666 u32 max_chunk = remaining - (N_RAND_RANGES - 1 - i) * ps; 667 u32 sz = max(round_up(prandom_u32_state(&prng) % max_chunk, ps), ps); 668 669 ranges[i + 1] = ranges[i] + sz; 670 remaining -= sz; 671 } 672 ranges[N_RAND_RANGES] = mm_size; 673 674 /* Create a random order */ 675 for (i = 0; i < N_RAND_RANGES; i++) 676 order_arr[i] = i; 677 for (i = N_RAND_RANGES - 1; i > 0; i--) { 678 u32 j = prandom_u32_state(&prng) % (i + 1); 679 u32 tmp_val = order_arr[i]; 680 681 order_arr[i] = order_arr[j]; 682 order_arr[j] = tmp_val; 683 } 684 685 for (i = 0; i < N_RAND_RANGES; i++) { 686 u32 idx = order_arr[i]; 687 u32 start = ranges[idx]; 688 u32 end = ranges[idx + 1]; 689 u32 sz = end - start; 690 691 ret = gpu_buddy_alloc_blocks(&mm, start, end, sz, ps, &blocks, 0); 692 KUNIT_ASSERT_EQ_MSG(test, ret, 0, 693 "random exact-range [%x, %x) sz=%x failed\n", 694 start, end, sz); 695 } 696 697 KUNIT_EXPECT_EQ(test, mm.avail, 0ULL); 698 gpu_buddy_free_list(&mm, &blocks, 0); 699 #undef N_RAND_RANGES 700 } 701 702 gpu_buddy_fini(&mm); 703 704 /* 705 * Negative case - partially allocated range. 706 * Allocate the first half, then try to exact-range allocate the full 707 * mm. This must fail because the first half is already occupied. 708 */ 709 mm_size = SZ_16M; 710 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 711 712 ret = gpu_buddy_alloc_blocks(&mm, 0, mm_size / 2, mm_size / 2, ps, &blocks, 0); 713 KUNIT_ASSERT_EQ(test, ret, 0); 714 715 ret = gpu_buddy_alloc_blocks(&mm, 0, mm_size, mm_size, ps, &tmp, 0); 716 KUNIT_EXPECT_NE_MSG(test, ret, 0, 717 "exact-range alloc should fail when range is partially used\n"); 718 719 /* Also try the already-occupied sub-range directly */ 720 ret = gpu_buddy_alloc_blocks(&mm, 0, mm_size / 2, mm_size / 2, ps, &tmp, 0); 721 KUNIT_EXPECT_NE_MSG(test, ret, 0, 722 "double alloc of same exact range should fail\n"); 723 724 /* The free second half should still be allocatable */ 725 ret = gpu_buddy_alloc_blocks(&mm, mm_size / 2, mm_size, mm_size / 2, ps, &blocks, 0); 726 KUNIT_ASSERT_EQ(test, ret, 0); 727 728 KUNIT_EXPECT_EQ(test, mm.avail, 0ULL); 729 gpu_buddy_free_list(&mm, &blocks, 0); 730 gpu_buddy_fini(&mm); 731 732 /* 733 * Negative case - checkerboard partial allocation. 734 * Allocate every other page-sized chunk in a small mm, then try to 735 * exact-range allocate a range covering two pages (one allocated, one 736 * free). This must fail. 737 */ 738 mm_size = SZ_64K; 739 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 740 741 { 742 u32 off; 743 744 for (off = 0; off < mm_size; off += 2 * ps) { 745 ret = gpu_buddy_alloc_blocks(&mm, off, off + ps, ps, ps, &blocks, 0); 746 KUNIT_ASSERT_EQ(test, ret, 0); 747 } 748 749 /* Try exact range over a pair [allocated, free] */ 750 ret = gpu_buddy_alloc_blocks(&mm, 0, 2 * ps, 2 * ps, ps, &tmp, 0); 751 KUNIT_EXPECT_NE_MSG(test, ret, 0, 752 "exact-range over partially allocated pair should fail\n"); 753 754 /* The free pages individually should still work */ 755 ret = gpu_buddy_alloc_blocks(&mm, ps, 2 * ps, ps, ps, &blocks, 0); 756 KUNIT_ASSERT_EQ(test, ret, 0); 757 758 gpu_buddy_free_list(&mm, &blocks, 0); 759 } 760 761 gpu_buddy_fini(&mm); 762 763 /* Negative case - misaligned start/end/size */ 764 mm_size = SZ_16M; 765 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 766 767 /* start not aligned to chunk_size */ 768 ret = gpu_buddy_alloc_blocks(&mm, ps / 2, ps / 2 + ps, ps, ps, &tmp, 0); 769 KUNIT_EXPECT_NE(test, ret, 0); 770 771 /* size not aligned */ 772 ret = gpu_buddy_alloc_blocks(&mm, 0, ps + 1, ps + 1, ps, &tmp, 0); 773 KUNIT_EXPECT_NE(test, ret, 0); 774 775 /* end exceeds mm size */ 776 ret = gpu_buddy_alloc_blocks(&mm, mm_size, mm_size + ps, ps, ps, &tmp, 0); 777 KUNIT_EXPECT_NE(test, ret, 0); 778 779 gpu_buddy_fini(&mm); 780 781 /* 782 * Free and re-allocate the same exact range. 783 * This exercises merge-on-free followed by exact-range re-split. 784 */ 785 mm_size = SZ_16M; 786 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 787 788 { 789 int i; 790 791 for (i = 0; i < 5; i++) { 792 ret = gpu_buddy_alloc_blocks(&mm, SZ_4M, SZ_4M + SZ_2M, 793 SZ_2M, ps, &blocks, 0); 794 KUNIT_ASSERT_EQ_MSG(test, ret, 0, 795 "re-alloc iteration %d failed\n", i); 796 797 total = 0; 798 list_for_each_entry(block, &blocks, link) { 799 u64 offset = gpu_buddy_block_offset(block); 800 u64 bsize = gpu_buddy_block_size(&mm, block); 801 802 KUNIT_EXPECT_GE(test, offset, (u64)SZ_4M); 803 KUNIT_EXPECT_LE(test, offset + bsize, (u64)(SZ_4M + SZ_2M)); 804 total += (u32)bsize; 805 } 806 KUNIT_EXPECT_EQ(test, total, SZ_2M); 807 808 gpu_buddy_free_list(&mm, &blocks, 0); 809 } 810 811 KUNIT_EXPECT_EQ(test, mm.avail, (u64)mm_size); 812 } 813 814 gpu_buddy_fini(&mm); 815 816 /* 817 * Various power-of-two exact ranges within a large mm. 818 * Allocate non-overlapping power-of-two exact ranges at their natural 819 * alignment, validating that the allocator handles different orders. 820 */ 821 mm_size = SZ_16M; 822 KUNIT_ASSERT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 823 824 /* Allocate 4K at offset 0 */ 825 ret = gpu_buddy_alloc_blocks(&mm, 0, SZ_4K, SZ_4K, ps, &blocks, 0); 826 KUNIT_ASSERT_EQ(test, ret, 0); 827 828 /* Allocate 64K at offset 64K */ 829 ret = gpu_buddy_alloc_blocks(&mm, SZ_64K, SZ_64K + SZ_64K, SZ_64K, ps, &blocks, 0); 830 KUNIT_ASSERT_EQ(test, ret, 0); 831 832 /* Allocate 1M at offset 1M */ 833 ret = gpu_buddy_alloc_blocks(&mm, SZ_1M, SZ_1M + SZ_1M, SZ_1M, ps, &blocks, 0); 834 KUNIT_ASSERT_EQ(test, ret, 0); 835 836 /* Allocate 4M at offset 4M */ 837 ret = gpu_buddy_alloc_blocks(&mm, SZ_4M, SZ_4M + SZ_4M, SZ_4M, ps, &blocks, 0); 838 KUNIT_ASSERT_EQ(test, ret, 0); 839 840 total = 0; 841 list_for_each_entry(block, &blocks, link) 842 total += (u32)gpu_buddy_block_size(&mm, block); 843 KUNIT_EXPECT_EQ(test, total, SZ_4K + SZ_64K + SZ_1M + SZ_4M); 844 845 gpu_buddy_free_list(&mm, &blocks, 0); 846 gpu_buddy_fini(&mm); 847 } 848 849 static void gpu_test_buddy_alloc_clear(struct kunit *test) 850 { 851 unsigned long n_pages, total, i = 0; 852 const unsigned long ps = SZ_4K; 853 struct gpu_buddy_block *block; 854 const int max_order = 12; 855 LIST_HEAD(allocated); 856 struct gpu_buddy mm; 857 unsigned int order; 858 u32 mm_size, size; 859 LIST_HEAD(dirty); 860 LIST_HEAD(clean); 861 862 mm_size = SZ_4K << max_order; 863 KUNIT_EXPECT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 864 865 KUNIT_EXPECT_EQ(test, mm.max_order, max_order); 866 867 /* 868 * Idea is to allocate and free some random portion of the address space, 869 * returning those pages as non-dirty and randomly alternate between 870 * requesting dirty and non-dirty pages (not going over the limit 871 * we freed as non-dirty), putting that into two separate lists. 872 * Loop over both lists at the end checking that the dirty list 873 * is indeed all dirty pages and vice versa. Free it all again, 874 * keeping the dirty/clear status. 875 */ 876 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 877 5 * ps, ps, &allocated, 878 GPU_BUDDY_TOPDOWN_ALLOCATION), 879 "buddy_alloc hit an error size=%lu\n", 5 * ps); 880 gpu_buddy_free_list(&mm, &allocated, GPU_BUDDY_CLEARED); 881 882 n_pages = 10; 883 do { 884 unsigned long flags; 885 struct list_head *list; 886 int slot = i % 2; 887 888 if (slot == 0) { 889 list = &dirty; 890 flags = 0; 891 } else { 892 list = &clean; 893 flags = GPU_BUDDY_CLEAR_ALLOCATION; 894 } 895 896 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 897 ps, ps, list, 898 flags), 899 "buddy_alloc hit an error size=%lu\n", ps); 900 } while (++i < n_pages); 901 902 list_for_each_entry(block, &clean, link) 903 KUNIT_EXPECT_EQ(test, gpu_buddy_block_is_clear(block), true); 904 905 list_for_each_entry(block, &dirty, link) 906 KUNIT_EXPECT_EQ(test, gpu_buddy_block_is_clear(block), false); 907 908 gpu_buddy_free_list(&mm, &clean, GPU_BUDDY_CLEARED); 909 910 /* 911 * Trying to go over the clear limit for some allocation. 912 * The allocation should never fail with reasonable page-size. 913 */ 914 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 915 10 * ps, ps, &clean, 916 GPU_BUDDY_CLEAR_ALLOCATION), 917 "buddy_alloc hit an error size=%lu\n", 10 * ps); 918 919 gpu_buddy_free_list(&mm, &clean, GPU_BUDDY_CLEARED); 920 gpu_buddy_free_list(&mm, &dirty, 0); 921 gpu_buddy_fini(&mm); 922 923 KUNIT_EXPECT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 924 925 /* 926 * Create a new mm. Intentionally fragment the address space by creating 927 * two alternating lists. Free both lists, one as dirty the other as clean. 928 * Try to allocate double the previous size with matching min_page_size. 929 * The allocation should never fail because buddy pairs coalesce 930 * unconditionally at free() time, rebuilding the larger block. Also check 931 * that the page is always dirty (a merged block spanning a dirty half is 932 * dirty). Free the page as dirty, then repeat the whole thing, increment 933 * the order until we hit the max_order. 934 */ 935 936 i = 0; 937 n_pages = mm_size / ps; 938 do { 939 struct list_head *list; 940 int slot = i % 2; 941 942 if (slot == 0) 943 list = &dirty; 944 else 945 list = &clean; 946 947 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 948 ps, ps, list, 0), 949 "buddy_alloc hit an error size=%lu\n", ps); 950 } while (++i < n_pages); 951 952 gpu_buddy_free_list(&mm, &clean, GPU_BUDDY_CLEARED); 953 gpu_buddy_free_list(&mm, &dirty, 0); 954 955 order = 1; 956 do { 957 size = SZ_4K << order; 958 959 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 960 size, size, &allocated, 961 GPU_BUDDY_CLEAR_ALLOCATION), 962 "buddy_alloc hit an error size=%u\n", size); 963 total = 0; 964 list_for_each_entry(block, &allocated, link) { 965 if (size != mm_size) 966 KUNIT_EXPECT_EQ(test, gpu_buddy_block_is_clear(block), false); 967 total += gpu_buddy_block_size(&mm, block); 968 } 969 KUNIT_EXPECT_EQ(test, total, size); 970 971 gpu_buddy_free_list(&mm, &allocated, 0); 972 } while (++order <= max_order); 973 974 gpu_buddy_fini(&mm); 975 976 /* 977 * Create a new mm with a non power-of-two size. Allocate a random size from each 978 * root, free as cleared and then call fini. This will ensure the multi-root 979 * force merge during fini. 980 */ 981 mm_size = (SZ_4K << max_order) + (SZ_4K << (max_order - 2)); 982 983 KUNIT_EXPECT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 984 KUNIT_EXPECT_EQ(test, mm.max_order, max_order); 985 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_4K << max_order, 986 4 * ps, ps, &allocated, 987 GPU_BUDDY_RANGE_ALLOCATION), 988 "buddy_alloc hit an error size=%lu\n", 4 * ps); 989 gpu_buddy_free_list(&mm, &allocated, GPU_BUDDY_CLEARED); 990 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, SZ_4K << max_order, 991 2 * ps, ps, &allocated, 992 GPU_BUDDY_CLEAR_ALLOCATION), 993 "buddy_alloc hit an error size=%lu\n", 2 * ps); 994 gpu_buddy_free_list(&mm, &allocated, GPU_BUDDY_CLEARED); 995 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, SZ_4K << max_order, mm_size, 996 ps, ps, &allocated, 997 GPU_BUDDY_RANGE_ALLOCATION), 998 "buddy_alloc hit an error size=%lu\n", ps); 999 gpu_buddy_free_list(&mm, &allocated, GPU_BUDDY_CLEARED); 1000 gpu_buddy_fini(&mm); 1001 1002 /* 1003 * Using a non-power-of-two mm size, allocate all 4KiB blocks and split 1004 * them across two alternating lists, then free one list as cleared and 1005 * the other as dirty. This interleaves cleared and dirty blocks so that 1006 * neighbouring buddies cannot be merged, fragmenting the address space. 1007 * After gpu_buddy_reset_clear(false) every block should be marked dirty 1008 * and the split blocks should be merged back to their original size, so 1009 * clear_avail must drop to 0. 1010 */ 1011 KUNIT_EXPECT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 1012 KUNIT_EXPECT_EQ(test, mm.max_order, max_order); 1013 1014 n_pages = mm_size / ps; 1015 for (i = 0; i < n_pages; i++) { 1016 struct list_head *list = (i % 2) ? &clean : &dirty; 1017 1018 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1019 ps, ps, list, 0), 1020 "buddy_alloc hit an error size=%lu\n", ps); 1021 } 1022 1023 gpu_buddy_free_list(&mm, &clean, GPU_BUDDY_CLEARED); 1024 gpu_buddy_free_list(&mm, &dirty, 0); 1025 gpu_buddy_reset_clear(&mm, false); 1026 KUNIT_EXPECT_EQ(test, gpu_buddy_clear_avail(&mm), 0); 1027 gpu_buddy_fini(&mm); 1028 1029 /* 1030 * Repeat the same fragmented setup, but this time call 1031 * gpu_buddy_reset_clear(true). Every block should be marked cleared and 1032 * the split blocks should be merged back to their original size, so the 1033 * whole address space (clear_avail) must equal mm_size. 1034 */ 1035 KUNIT_EXPECT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 1036 KUNIT_EXPECT_EQ(test, mm.max_order, max_order); 1037 1038 for (i = 0; i < n_pages; i++) { 1039 struct list_head *list = (i % 2) ? &clean : &dirty; 1040 1041 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1042 ps, ps, list, 0), 1043 "buddy_alloc hit an error size=%lu\n", ps); 1044 } 1045 1046 gpu_buddy_free_list(&mm, &clean, GPU_BUDDY_CLEARED); 1047 gpu_buddy_free_list(&mm, &dirty, 0); 1048 gpu_buddy_reset_clear(&mm, true); 1049 KUNIT_EXPECT_EQ(test, gpu_buddy_clear_avail(&mm), mm_size); 1050 gpu_buddy_fini(&mm); 1051 } 1052 1053 static void gpu_test_buddy_alloc_contiguous(struct kunit *test) 1054 { 1055 const unsigned long ps = SZ_4K, mm_size = 16 * 3 * SZ_4K; 1056 unsigned long i, n_pages, total; 1057 struct gpu_buddy_block *block; 1058 struct gpu_buddy mm; 1059 LIST_HEAD(left); 1060 LIST_HEAD(middle); 1061 LIST_HEAD(right); 1062 LIST_HEAD(allocated); 1063 1064 KUNIT_EXPECT_FALSE(test, gpu_buddy_init(&mm, mm_size, ps)); 1065 1066 /* 1067 * Idea is to fragment the address space by alternating block 1068 * allocations between three different lists; one for left, middle and 1069 * right. We can then free a list to simulate fragmentation. In 1070 * particular we want to exercise the GPU_BUDDY_CONTIGUOUS_ALLOCATION, 1071 * including the try_harder path. 1072 */ 1073 1074 i = 0; 1075 n_pages = mm_size / ps; 1076 do { 1077 struct list_head *list; 1078 int slot = i % 3; 1079 1080 if (slot == 0) 1081 list = &left; 1082 else if (slot == 1) 1083 list = &middle; 1084 else 1085 list = &right; 1086 KUNIT_ASSERT_FALSE_MSG(test, 1087 gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1088 ps, ps, list, 0), 1089 "buddy_alloc hit an error size=%lu\n", 1090 ps); 1091 } while (++i < n_pages); 1092 1093 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1094 3 * ps, ps, &allocated, 1095 GPU_BUDDY_CONTIGUOUS_ALLOCATION), 1096 "buddy_alloc didn't error size=%lu\n", 3 * ps); 1097 1098 gpu_buddy_free_list(&mm, &middle, 0); 1099 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1100 3 * ps, ps, &allocated, 1101 GPU_BUDDY_CONTIGUOUS_ALLOCATION), 1102 "buddy_alloc didn't error size=%lu\n", 3 * ps); 1103 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1104 2 * ps, ps, &allocated, 1105 GPU_BUDDY_CONTIGUOUS_ALLOCATION), 1106 "buddy_alloc didn't error size=%lu\n", 2 * ps); 1107 1108 gpu_buddy_free_list(&mm, &right, 0); 1109 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1110 3 * ps, ps, &allocated, 1111 GPU_BUDDY_CONTIGUOUS_ALLOCATION), 1112 "buddy_alloc didn't error size=%lu\n", 3 * ps); 1113 /* 1114 * At this point we should have enough contiguous space for 2 blocks, 1115 * however they are never buddies (since we freed middle and right) so 1116 * will require the try_harder logic to find them. 1117 */ 1118 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1119 2 * ps, ps, &allocated, 1120 GPU_BUDDY_CONTIGUOUS_ALLOCATION), 1121 "buddy_alloc hit an error size=%lu\n", 2 * ps); 1122 1123 gpu_buddy_free_list(&mm, &left, 0); 1124 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, 1125 3 * ps, ps, &allocated, 1126 GPU_BUDDY_CONTIGUOUS_ALLOCATION), 1127 "buddy_alloc hit an error size=%lu\n", 3 * ps); 1128 1129 total = 0; 1130 list_for_each_entry(block, &allocated, link) 1131 total += gpu_buddy_block_size(&mm, block); 1132 1133 KUNIT_ASSERT_EQ(test, total, ps * 2 + ps * 3); 1134 1135 gpu_buddy_free_list(&mm, &allocated, 0); 1136 gpu_buddy_fini(&mm); 1137 } 1138 1139 static void gpu_test_buddy_alloc_pathological(struct kunit *test) 1140 { 1141 u64 mm_size, size, start = 0; 1142 struct gpu_buddy_block *block; 1143 const int max_order = 3; 1144 unsigned long flags = 0; 1145 int order, top; 1146 struct gpu_buddy mm; 1147 LIST_HEAD(blocks); 1148 LIST_HEAD(holes); 1149 LIST_HEAD(tmp); 1150 1151 /* 1152 * Create a pot-sized mm, then allocate one of each possible 1153 * order within. This should leave the mm with exactly one 1154 * page left. Free the largest block, then whittle down again. 1155 * Eventually we will have a fully 50% fragmented mm. 1156 */ 1157 1158 mm_size = SZ_4K << max_order; 1159 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K), 1160 "buddy_init failed\n"); 1161 1162 KUNIT_EXPECT_EQ(test, mm.max_order, max_order); 1163 1164 for (top = max_order; top; top--) { 1165 /* Make room by freeing the largest allocated block */ 1166 block = list_first_entry_or_null(&blocks, typeof(*block), link); 1167 if (block) { 1168 list_del(&block->link); 1169 gpu_buddy_free_block(&mm, block); 1170 } 1171 1172 for (order = top; order--;) { 1173 size = get_size(order, mm.chunk_size); 1174 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, 1175 mm_size, size, size, 1176 &tmp, flags), 1177 "buddy_alloc hit -ENOMEM with order=%d, top=%d\n", 1178 order, top); 1179 1180 block = list_first_entry_or_null(&tmp, struct gpu_buddy_block, link); 1181 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n"); 1182 1183 list_move_tail(&block->link, &blocks); 1184 } 1185 1186 /* There should be one final page for this sub-allocation */ 1187 size = get_size(0, mm.chunk_size); 1188 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1189 size, size, &tmp, flags), 1190 "buddy_alloc hit -ENOMEM for hole\n"); 1191 1192 block = list_first_entry_or_null(&tmp, struct gpu_buddy_block, link); 1193 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n"); 1194 1195 list_move_tail(&block->link, &holes); 1196 1197 size = get_size(top, mm.chunk_size); 1198 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1199 size, size, &tmp, flags), 1200 "buddy_alloc unexpectedly succeeded at top-order %d/%d, it should be full!", 1201 top, max_order); 1202 } 1203 1204 gpu_buddy_free_list(&mm, &holes, 0); 1205 1206 /* Nothing larger than blocks of chunk_size now available */ 1207 for (order = 1; order <= max_order; order++) { 1208 size = get_size(order, mm.chunk_size); 1209 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1210 size, size, &tmp, flags), 1211 "buddy_alloc unexpectedly succeeded at order %d, it should be full!", 1212 order); 1213 } 1214 1215 list_splice_tail(&holes, &blocks); 1216 gpu_buddy_free_list(&mm, &blocks, 0); 1217 gpu_buddy_fini(&mm); 1218 } 1219 1220 static void gpu_test_buddy_alloc_pessimistic(struct kunit *test) 1221 { 1222 u64 mm_size, size, start = 0; 1223 struct gpu_buddy_block *block, *bn; 1224 const unsigned int max_order = 16; 1225 unsigned long flags = 0; 1226 struct gpu_buddy mm; 1227 unsigned int order; 1228 LIST_HEAD(blocks); 1229 LIST_HEAD(tmp); 1230 1231 /* 1232 * Create a pot-sized mm, then allocate one of each possible 1233 * order within. This should leave the mm with exactly one 1234 * page left. 1235 */ 1236 1237 mm_size = SZ_4K << max_order; 1238 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K), 1239 "buddy_init failed\n"); 1240 1241 KUNIT_EXPECT_EQ(test, mm.max_order, max_order); 1242 1243 for (order = 0; order < max_order; order++) { 1244 size = get_size(order, mm.chunk_size); 1245 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1246 size, size, &tmp, flags), 1247 "buddy_alloc hit -ENOMEM with order=%d\n", 1248 order); 1249 1250 block = list_first_entry_or_null(&tmp, struct gpu_buddy_block, link); 1251 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n"); 1252 1253 list_move_tail(&block->link, &blocks); 1254 } 1255 1256 /* And now the last remaining block available */ 1257 size = get_size(0, mm.chunk_size); 1258 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1259 size, size, &tmp, flags), 1260 "buddy_alloc hit -ENOMEM on final alloc\n"); 1261 1262 block = list_first_entry_or_null(&tmp, struct gpu_buddy_block, link); 1263 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n"); 1264 1265 list_move_tail(&block->link, &blocks); 1266 1267 /* Should be completely full! */ 1268 for (order = max_order; order--;) { 1269 size = get_size(order, mm.chunk_size); 1270 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1271 size, size, &tmp, flags), 1272 "buddy_alloc unexpectedly succeeded, it should be full!"); 1273 } 1274 1275 block = list_last_entry(&blocks, typeof(*block), link); 1276 list_del(&block->link); 1277 gpu_buddy_free_block(&mm, block); 1278 1279 /* As we free in increasing size, we make available larger blocks */ 1280 order = 1; 1281 list_for_each_entry_safe(block, bn, &blocks, link) { 1282 list_del(&block->link); 1283 gpu_buddy_free_block(&mm, block); 1284 1285 size = get_size(order, mm.chunk_size); 1286 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1287 size, size, &tmp, flags), 1288 "buddy_alloc hit -ENOMEM with order=%d\n", 1289 order); 1290 1291 block = list_first_entry_or_null(&tmp, struct gpu_buddy_block, link); 1292 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n"); 1293 1294 list_del(&block->link); 1295 gpu_buddy_free_block(&mm, block); 1296 order++; 1297 } 1298 1299 /* To confirm, now the whole mm should be available */ 1300 size = get_size(max_order, mm.chunk_size); 1301 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1302 size, size, &tmp, flags), 1303 "buddy_alloc (realloc) hit -ENOMEM with order=%d\n", 1304 max_order); 1305 1306 block = list_first_entry_or_null(&tmp, struct gpu_buddy_block, link); 1307 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n"); 1308 1309 list_del(&block->link); 1310 gpu_buddy_free_block(&mm, block); 1311 gpu_buddy_free_list(&mm, &blocks, 0); 1312 gpu_buddy_fini(&mm); 1313 } 1314 1315 static void gpu_test_buddy_alloc_optimistic(struct kunit *test) 1316 { 1317 u64 mm_size, size, start = 0; 1318 struct gpu_buddy_block *block; 1319 unsigned long flags = 0; 1320 const int max_order = 16; 1321 struct gpu_buddy mm; 1322 LIST_HEAD(blocks); 1323 LIST_HEAD(tmp); 1324 int order; 1325 1326 /* 1327 * Create a mm with one block of each order available, and 1328 * try to allocate them all. 1329 */ 1330 1331 mm_size = SZ_4K * ((1 << (max_order + 1)) - 1); 1332 1333 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K), 1334 "buddy_init failed\n"); 1335 1336 KUNIT_EXPECT_EQ(test, mm.max_order, max_order); 1337 1338 for (order = 0; order <= max_order; order++) { 1339 size = get_size(order, mm.chunk_size); 1340 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1341 size, size, &tmp, flags), 1342 "buddy_alloc hit -ENOMEM with order=%d\n", 1343 order); 1344 1345 block = list_first_entry_or_null(&tmp, struct gpu_buddy_block, link); 1346 KUNIT_ASSERT_TRUE_MSG(test, block, "alloc_blocks has no blocks\n"); 1347 1348 list_move_tail(&block->link, &blocks); 1349 } 1350 1351 /* Should be completely full! */ 1352 size = get_size(0, mm.chunk_size); 1353 KUNIT_ASSERT_TRUE_MSG(test, gpu_buddy_alloc_blocks(&mm, start, mm_size, 1354 size, size, &tmp, flags), 1355 "buddy_alloc unexpectedly succeeded, it should be full!"); 1356 1357 gpu_buddy_free_list(&mm, &blocks, 0); 1358 gpu_buddy_fini(&mm); 1359 } 1360 1361 static void gpu_test_buddy_alloc_limit(struct kunit *test) 1362 { 1363 u64 size = U64_MAX, start = 0; 1364 struct gpu_buddy_block *block; 1365 unsigned long flags = 0; 1366 LIST_HEAD(allocated); 1367 struct gpu_buddy mm; 1368 1369 KUNIT_EXPECT_FALSE(test, gpu_buddy_init(&mm, size, SZ_4K)); 1370 1371 KUNIT_EXPECT_EQ_MSG(test, mm.max_order, GPU_BUDDY_MAX_ORDER, 1372 "mm.max_order(%d) != %d\n", mm.max_order, 1373 GPU_BUDDY_MAX_ORDER); 1374 1375 size = mm.chunk_size << mm.max_order; 1376 KUNIT_EXPECT_FALSE(test, gpu_buddy_alloc_blocks(&mm, start, size, size, 1377 mm.chunk_size, &allocated, flags)); 1378 1379 block = list_first_entry_or_null(&allocated, struct gpu_buddy_block, link); 1380 KUNIT_EXPECT_TRUE(test, block); 1381 1382 KUNIT_EXPECT_EQ_MSG(test, gpu_buddy_block_order(block), mm.max_order, 1383 "block order(%d) != %d\n", 1384 gpu_buddy_block_order(block), mm.max_order); 1385 1386 KUNIT_EXPECT_EQ_MSG(test, gpu_buddy_block_size(&mm, block), 1387 BIT_ULL(mm.max_order) * mm.chunk_size, 1388 "block size(%llu) != %llu\n", 1389 gpu_buddy_block_size(&mm, block), 1390 BIT_ULL(mm.max_order) * mm.chunk_size); 1391 1392 gpu_buddy_free_list(&mm, &allocated, 0); 1393 gpu_buddy_fini(&mm); 1394 } 1395 1396 static void gpu_test_buddy_alloc_exceeds_max_order(struct kunit *test) 1397 { 1398 u64 mm_size = SZ_8G + SZ_2G, size = SZ_8G + SZ_1G, min_block_size = SZ_8G; 1399 struct gpu_buddy mm; 1400 LIST_HEAD(blocks); 1401 int err; 1402 1403 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, mm_size, SZ_4K), 1404 "buddy_init failed\n"); 1405 1406 /* CONTIGUOUS allocation should succeed via try_harder fallback */ 1407 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, 0, mm_size, size, 1408 SZ_4K, &blocks, 1409 GPU_BUDDY_CONTIGUOUS_ALLOCATION), 1410 "buddy_alloc hit an error size=%llu\n", size); 1411 gpu_buddy_free_list(&mm, &blocks, 0); 1412 1413 /* Non-CONTIGUOUS with large min_block_size should return -EINVAL */ 1414 err = gpu_buddy_alloc_blocks(&mm, 0, mm_size, size, min_block_size, &blocks, 0); 1415 KUNIT_EXPECT_EQ(test, err, -EINVAL); 1416 1417 /* Non-CONTIGUOUS + RANGE with large min_block_size should return -EINVAL */ 1418 err = gpu_buddy_alloc_blocks(&mm, 0, mm_size, size, min_block_size, &blocks, 1419 GPU_BUDDY_RANGE_ALLOCATION); 1420 KUNIT_EXPECT_EQ(test, err, -EINVAL); 1421 1422 /* CONTIGUOUS + RANGE should return -EINVAL (no try_harder for RANGE) */ 1423 err = gpu_buddy_alloc_blocks(&mm, 0, mm_size, size, SZ_4K, &blocks, 1424 GPU_BUDDY_CONTIGUOUS_ALLOCATION | GPU_BUDDY_RANGE_ALLOCATION); 1425 KUNIT_EXPECT_EQ(test, err, -EINVAL); 1426 1427 gpu_buddy_fini(&mm); 1428 } 1429 1430 static void gpu_test_buddy_addr_to_block(struct kunit *test) 1431 { 1432 struct gpu_buddy_block *allocated_block, *found_block; 1433 LIST_HEAD(allocated_list); 1434 const u64 test_size = SZ_4M + SZ_2M; 1435 const u64 alloc_start = SZ_4M; 1436 const u64 alloc_size = SZ_4K; 1437 const u64 chunk_size = SZ_4K; 1438 struct gpu_buddy mm; 1439 1440 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_init(&mm, test_size, chunk_size), 1441 "buddy_init failed\n"); 1442 1443 KUNIT_ASSERT_FALSE_MSG(test, gpu_buddy_alloc_blocks(&mm, alloc_start, 1444 alloc_start + alloc_size, 1445 alloc_size, chunk_size, 1446 &allocated_list, 0), 1447 "buddy_alloc failed\n"); 1448 1449 allocated_block = list_first_entry(&allocated_list, struct gpu_buddy_block, link); 1450 KUNIT_EXPECT_EQ(test, gpu_buddy_block_offset(allocated_block), alloc_start); 1451 KUNIT_EXPECT_EQ(test, gpu_buddy_block_size(&mm, allocated_block), alloc_size); 1452 1453 found_block = gpu_buddy_allocated_addr_to_block(&mm, alloc_start); 1454 KUNIT_EXPECT_PTR_EQ(test, found_block, allocated_block); 1455 1456 /* Unaligned address inside the allocated block (should resolve to the same block) */ 1457 found_block = gpu_buddy_allocated_addr_to_block(&mm, alloc_start + 16); 1458 KUNIT_EXPECT_PTR_EQ(test, found_block, allocated_block); 1459 1460 /* An unallocated address inside the manager should return NULL. */ 1461 found_block = gpu_buddy_allocated_addr_to_block(&mm, 1462 alloc_start - chunk_size); 1463 KUNIT_EXPECT_NULL(test, found_block); 1464 1465 /* An address outside the manager should return -ENXIO. */ 1466 found_block = gpu_buddy_allocated_addr_to_block(&mm, test_size); 1467 KUNIT_EXPECT_EQ(test, PTR_ERR(found_block), -ENXIO); 1468 1469 /* 3. Standard inline cleanup flow */ 1470 gpu_buddy_free_list(&mm, &allocated_list, 0); 1471 gpu_buddy_fini(&mm); 1472 } 1473 1474 static int gpu_buddy_suite_init(struct kunit_suite *suite) 1475 { 1476 while (!random_seed) 1477 random_seed = get_random_u32(); 1478 1479 kunit_info(suite, "Testing GPU buddy manager, with random_seed=0x%x\n", 1480 random_seed); 1481 1482 return 0; 1483 } 1484 1485 static struct kunit_case gpu_buddy_tests[] = { 1486 KUNIT_CASE(gpu_test_buddy_alloc_limit), 1487 KUNIT_CASE(gpu_test_buddy_alloc_optimistic), 1488 KUNIT_CASE(gpu_test_buddy_alloc_pessimistic), 1489 KUNIT_CASE(gpu_test_buddy_alloc_pathological), 1490 KUNIT_CASE(gpu_test_buddy_alloc_contiguous), 1491 KUNIT_CASE(gpu_test_buddy_alloc_clear), 1492 KUNIT_CASE(gpu_test_buddy_alloc_range), 1493 KUNIT_CASE(gpu_test_buddy_alloc_range_bias), 1494 KUNIT_CASE_SLOW(gpu_test_buddy_fragmentation_performance), 1495 KUNIT_CASE(gpu_test_buddy_alloc_exceeds_max_order), 1496 KUNIT_CASE(gpu_test_buddy_offset_aligned_allocation), 1497 KUNIT_CASE(gpu_test_buddy_subtree_offset_alignment_stress), 1498 KUNIT_CASE(gpu_test_buddy_addr_to_block), 1499 {} 1500 }; 1501 1502 static struct kunit_suite gpu_buddy_test_suite = { 1503 .name = "gpu_buddy", 1504 .suite_init = gpu_buddy_suite_init, 1505 .test_cases = gpu_buddy_tests, 1506 }; 1507 1508 kunit_test_suite(gpu_buddy_test_suite); 1509 1510 MODULE_AUTHOR("Intel Corporation"); 1511 MODULE_DESCRIPTION("Kunit test for gpu_buddy functions"); 1512 MODULE_LICENSE("GPL"); 1513