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