1 // SPDX-License-Identifier: MIT 2 /* 3 * Copyright © 2021 Intel Corporation 4 */ 5 6 #include <linux/bug.h> 7 #include <linux/export.h> 8 #include <linux/kmemleak.h> 9 #include <linux/module.h> 10 #include <linux/sizes.h> 11 12 #include <linux/gpu_buddy.h> 13 14 /** 15 * gpu_buddy_assert - assert a condition in the buddy allocator 16 * @condition: condition expected to be true 17 * 18 * When CONFIG_KUNIT is enabled, evaluates @condition and, if false, triggers 19 * a WARN_ON() and also calls kunit_fail_current_test() so that any running 20 * kunit test is properly marked as failed. The stringified condition is 21 * included in the failure message for easy identification. 22 * 23 * When CONFIG_KUNIT is not enabled, this reduces to WARN_ON() so production 24 * builds retain the same warning semantics as before. 25 */ 26 #if IS_ENABLED(CONFIG_KUNIT) 27 #include <kunit/test-bug.h> 28 #define gpu_buddy_assert(condition) do { \ 29 if (WARN_ON(!(condition))) \ 30 kunit_fail_current_test("gpu_buddy_assert(" #condition ")"); \ 31 } while (0) 32 #else 33 #define gpu_buddy_assert(condition) WARN_ON(!(condition)) 34 #endif 35 36 static struct kmem_cache *slab_blocks; 37 38 static unsigned int 39 gpu_buddy_block_state(struct gpu_buddy_block *block) 40 { 41 return block->header & GPU_BUDDY_HEADER_STATE; 42 } 43 44 static bool 45 gpu_buddy_block_is_allocated(struct gpu_buddy_block *block) 46 { 47 return gpu_buddy_block_state(block) == GPU_BUDDY_ALLOCATED; 48 } 49 50 static bool 51 gpu_buddy_block_is_split(struct gpu_buddy_block *block) 52 { 53 return gpu_buddy_block_state(block) == GPU_BUDDY_SPLIT; 54 } 55 56 static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block) 57 { 58 u64 offset = gpu_buddy_block_offset(block); 59 60 if (!offset) 61 /* 62 * __ffs64(0) is undefined; offset 0 is maximally aligned, so return 63 * a value greater than any possible alignment. 64 */ 65 return 64 + 1; 66 67 return __ffs64(offset); 68 } 69 70 RB_DECLARE_CALLBACKS_MAX(static, gpu_buddy_augment_cb, 71 struct gpu_buddy_block, rb, 72 unsigned int, subtree_max_alignment, 73 gpu_buddy_block_offset_alignment); 74 75 static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm, 76 struct gpu_buddy_block *parent, 77 unsigned int order, 78 u64 offset) 79 { 80 struct gpu_buddy_block *block; 81 82 BUG_ON(order > GPU_BUDDY_MAX_ORDER); 83 84 block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); 85 if (!block) 86 return NULL; 87 88 block->header = offset; 89 block->header |= order; 90 block->parent = parent; 91 92 RB_CLEAR_NODE(&block->rb); 93 94 BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED); 95 return block; 96 } 97 98 static void gpu_block_free(struct gpu_buddy *mm, 99 struct gpu_buddy_block *block) 100 { 101 kmem_cache_free(slab_blocks, block); 102 } 103 104 static enum gpu_buddy_free_tree 105 get_block_tree(struct gpu_buddy_block *block) 106 { 107 return gpu_buddy_block_is_clear(block) ? 108 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE; 109 } 110 111 static struct gpu_buddy_block * 112 rbtree_get_free_block(const struct rb_node *node) 113 { 114 return node ? rb_entry(node, struct gpu_buddy_block, rb) : NULL; 115 } 116 117 static struct gpu_buddy_block * 118 rbtree_last_free_block(struct rb_root *root) 119 { 120 return rbtree_get_free_block(rb_last(root)); 121 } 122 123 static bool rbtree_is_empty(struct rb_root *root) 124 { 125 return RB_EMPTY_ROOT(root); 126 } 127 128 static void rbtree_insert(struct gpu_buddy *mm, 129 struct gpu_buddy_block *block, 130 enum gpu_buddy_free_tree tree) 131 { 132 struct rb_node **link, *parent = NULL; 133 unsigned int block_alignment, order; 134 struct gpu_buddy_block *node; 135 struct rb_root *root; 136 137 order = gpu_buddy_block_order(block); 138 block_alignment = gpu_buddy_block_offset_alignment(block); 139 140 root = &mm->free_trees[tree][order]; 141 link = &root->rb_node; 142 143 while (*link) { 144 parent = *link; 145 node = rbtree_get_free_block(parent); 146 /* 147 * Manual augmentation update during insertion traversal. Required 148 * because rb_insert_augmented() only calls rotate callback during 149 * rotations. This ensures all ancestors on the insertion path have 150 * correct subtree_max_alignment values. 151 */ 152 if (node->subtree_max_alignment < block_alignment) 153 node->subtree_max_alignment = block_alignment; 154 155 if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node)) 156 link = &parent->rb_left; 157 else 158 link = &parent->rb_right; 159 } 160 161 block->subtree_max_alignment = block_alignment; 162 rb_link_node(&block->rb, parent, link); 163 rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb); 164 } 165 166 static void rbtree_remove(struct gpu_buddy *mm, 167 struct gpu_buddy_block *block) 168 { 169 unsigned int order = gpu_buddy_block_order(block); 170 enum gpu_buddy_free_tree tree; 171 struct rb_root *root; 172 173 tree = get_block_tree(block); 174 root = &mm->free_trees[tree][order]; 175 176 rb_erase_augmented(&block->rb, root, &gpu_buddy_augment_cb); 177 RB_CLEAR_NODE(&block->rb); 178 } 179 180 static void clear_reset(struct gpu_buddy_block *block) 181 { 182 block->header &= ~GPU_BUDDY_HEADER_CLEAR; 183 } 184 185 static void mark_cleared(struct gpu_buddy_block *block) 186 { 187 block->header |= GPU_BUDDY_HEADER_CLEAR; 188 } 189 190 static void mark_allocated(struct gpu_buddy *mm, 191 struct gpu_buddy_block *block) 192 { 193 block->header &= ~GPU_BUDDY_HEADER_STATE; 194 block->header |= GPU_BUDDY_ALLOCATED; 195 196 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 197 mm->used_scoreboard[gpu_buddy_block_order(block)]++; 198 199 rbtree_remove(mm, block); 200 } 201 202 static void mark_free(struct gpu_buddy *mm, 203 struct gpu_buddy_block *block) 204 { 205 enum gpu_buddy_free_tree tree; 206 207 if (gpu_buddy_block_is_allocated(block)) 208 mm->used_scoreboard[gpu_buddy_block_order(block)]--; 209 210 block->header &= ~GPU_BUDDY_HEADER_STATE; 211 block->header |= GPU_BUDDY_FREE; 212 213 mm->free_scoreboard[gpu_buddy_block_order(block)]++; 214 215 tree = get_block_tree(block); 216 rbtree_insert(mm, block, tree); 217 } 218 219 static void mark_split(struct gpu_buddy *mm, 220 struct gpu_buddy_block *block) 221 { 222 block->header &= ~GPU_BUDDY_HEADER_STATE; 223 block->header |= GPU_BUDDY_SPLIT; 224 225 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 226 227 rbtree_remove(mm, block); 228 } 229 230 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) 231 { 232 return s1 <= e2 && e1 >= s2; 233 } 234 235 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) 236 { 237 return s1 <= s2 && e1 >= e2; 238 } 239 240 static struct gpu_buddy_block * 241 __get_buddy(struct gpu_buddy_block *block) 242 { 243 struct gpu_buddy_block *parent; 244 245 parent = block->parent; 246 if (!parent) 247 return NULL; 248 249 if (parent->left == block) 250 return parent->right; 251 252 return parent->left; 253 } 254 255 static unsigned int __gpu_buddy_free(struct gpu_buddy *mm, 256 struct gpu_buddy_block *block, 257 bool force_merge) 258 { 259 struct gpu_buddy_block *parent; 260 unsigned int order; 261 262 while ((parent = block->parent)) { 263 struct gpu_buddy_block *buddy; 264 265 buddy = __get_buddy(block); 266 267 if (!gpu_buddy_block_is_free(buddy)) 268 break; 269 270 if (!force_merge) { 271 /* 272 * Check the block and its buddy clear state and exit 273 * the loop if they both have the dissimilar state. 274 */ 275 if (gpu_buddy_block_is_clear(block) != 276 gpu_buddy_block_is_clear(buddy)) 277 break; 278 279 if (gpu_buddy_block_is_clear(block)) 280 mark_cleared(parent); 281 } 282 283 rbtree_remove(mm, buddy); 284 mm->free_scoreboard[gpu_buddy_block_order(buddy)]--; 285 if (force_merge && gpu_buddy_block_is_clear(buddy)) 286 mm->clear_avail -= gpu_buddy_block_size(mm, buddy); 287 288 if (gpu_buddy_block_is_allocated(block)) 289 mm->used_scoreboard[gpu_buddy_block_order(block)]--; 290 291 gpu_block_free(mm, block); 292 gpu_block_free(mm, buddy); 293 294 block = parent; 295 } 296 297 order = gpu_buddy_block_order(block); 298 mark_free(mm, block); 299 300 return order; 301 } 302 303 static int __force_merge(struct gpu_buddy *mm, 304 u64 start, 305 u64 end, 306 unsigned int min_order) 307 { 308 unsigned int tree, order; 309 int i; 310 311 if (!min_order) 312 return -ENOMEM; 313 314 if (min_order > mm->max_order) 315 return -EINVAL; 316 317 for_each_free_tree(tree) { 318 for (i = min_order - 1; i >= 0; i--) { 319 struct rb_node *iter = rb_last(&mm->free_trees[tree][i]); 320 321 while (iter) { 322 struct gpu_buddy_block *block, *buddy; 323 u64 block_start, block_end; 324 325 block = rbtree_get_free_block(iter); 326 iter = rb_prev(iter); 327 328 if (!block || !block->parent) 329 continue; 330 331 block_start = gpu_buddy_block_offset(block); 332 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 333 334 if (!contains(start, end, block_start, block_end)) 335 continue; 336 337 buddy = __get_buddy(block); 338 if (!gpu_buddy_block_is_free(buddy)) 339 continue; 340 341 gpu_buddy_assert(gpu_buddy_block_is_clear(block) != 342 gpu_buddy_block_is_clear(buddy)); 343 344 /* 345 * Advance to the next node when the current node is the buddy, 346 * as freeing the block will also remove its buddy from the tree. 347 */ 348 if (iter == &buddy->rb) 349 iter = rb_prev(iter); 350 351 rbtree_remove(mm, block); 352 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 353 if (gpu_buddy_block_is_clear(block)) 354 mm->clear_avail -= gpu_buddy_block_size(mm, block); 355 356 order = __gpu_buddy_free(mm, block, true); 357 if (order >= min_order) 358 return 0; 359 } 360 } 361 } 362 363 return -ENOMEM; 364 } 365 366 /** 367 * gpu_buddy_init - init memory manager 368 * 369 * @mm: GPU buddy manager to initialize 370 * @size: size in bytes to manage 371 * @chunk_size: minimum page size in bytes for our allocations 372 * 373 * Initializes the memory manager and its resources. 374 * 375 * Returns: 376 * 0 on success, error code on failure. 377 */ 378 int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size) 379 { 380 unsigned int i, j, root_count = 0; 381 u64 offset = 0; 382 383 if (size < chunk_size) 384 return -EINVAL; 385 386 if (chunk_size < SZ_4K) 387 return -EINVAL; 388 389 if (!is_power_of_2(chunk_size)) 390 return -EINVAL; 391 392 size = round_down(size, chunk_size); 393 394 mm->size = size; 395 mm->avail = size; 396 mm->clear_avail = 0; 397 mm->chunk_size = chunk_size; 398 mm->max_order = ilog2(size) - ilog2(chunk_size); 399 400 BUG_ON(mm->max_order > GPU_BUDDY_MAX_ORDER); 401 402 mm->free_scoreboard = kcalloc(mm->max_order + 1, 403 sizeof(*mm->free_scoreboard), 404 GFP_KERNEL); 405 if (!mm->free_scoreboard) 406 return -ENOMEM; 407 408 mm->used_scoreboard = kcalloc(mm->max_order + 1, 409 sizeof(*mm->used_scoreboard), 410 GFP_KERNEL); 411 if (!mm->used_scoreboard) 412 goto out_free_free_scoreboard; 413 414 mm->free_trees = kmalloc_objs(*mm->free_trees, GPU_BUDDY_MAX_FREE_TREES); 415 if (!mm->free_trees) 416 goto out_free_used_scoreboard; 417 418 for_each_free_tree(i) { 419 mm->free_trees[i] = kmalloc_objs(struct rb_root, 420 mm->max_order + 1); 421 if (!mm->free_trees[i]) 422 goto out_free_tree; 423 424 for (j = 0; j <= mm->max_order; ++j) 425 mm->free_trees[i][j] = RB_ROOT; 426 } 427 428 mm->n_roots = hweight64(size); 429 430 mm->roots = kmalloc_objs(struct gpu_buddy_block *, mm->n_roots); 431 if (!mm->roots) 432 goto out_free_tree; 433 434 /* 435 * Split into power-of-two blocks, in case we are given a size that is 436 * not itself a power-of-two. 437 */ 438 do { 439 struct gpu_buddy_block *root; 440 unsigned int order; 441 u64 root_size; 442 443 order = ilog2(size) - ilog2(chunk_size); 444 root_size = chunk_size << order; 445 446 root = gpu_block_alloc(mm, NULL, order, offset); 447 if (!root) 448 goto out_free_roots; 449 450 mark_free(mm, root); 451 452 BUG_ON(root_count > mm->max_order); 453 BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size); 454 455 mm->roots[root_count] = root; 456 457 offset += root_size; 458 size -= root_size; 459 root_count++; 460 } while (size); 461 462 #ifdef CONFIG_LOCKDEP 463 mm->lock_dep_map = NULL; 464 #endif 465 return 0; 466 467 out_free_roots: 468 while (root_count--) 469 gpu_block_free(mm, mm->roots[root_count]); 470 kfree(mm->roots); 471 out_free_tree: 472 while (i--) 473 kfree(mm->free_trees[i]); 474 kfree(mm->free_trees); 475 out_free_used_scoreboard: 476 kfree(mm->used_scoreboard); 477 out_free_free_scoreboard: 478 kfree(mm->free_scoreboard); 479 return -ENOMEM; 480 } 481 EXPORT_SYMBOL(gpu_buddy_init); 482 483 /** 484 * gpu_buddy_fini - tear down the memory manager 485 * 486 * @mm: GPU buddy manager to free 487 * 488 * Cleanup memory manager resources and the freetree 489 */ 490 void gpu_buddy_fini(struct gpu_buddy *mm) 491 { 492 u64 root_size, size, start; 493 unsigned int order; 494 int i; 495 496 size = mm->size; 497 498 for (i = 0; i < mm->n_roots; ++i) { 499 order = ilog2(size) - ilog2(mm->chunk_size); 500 start = gpu_buddy_block_offset(mm->roots[i]); 501 __force_merge(mm, start, start + size, order); 502 503 gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i])); 504 505 gpu_block_free(mm, mm->roots[i]); 506 507 root_size = mm->chunk_size << order; 508 size -= root_size; 509 } 510 511 gpu_buddy_assert(mm->avail == mm->size); 512 513 for (i = 0; i <= mm->max_order; ++i) 514 gpu_buddy_assert(!mm->used_scoreboard[i]); 515 516 for_each_free_tree(i) 517 kfree(mm->free_trees[i]); 518 kfree(mm->free_trees); 519 kfree(mm->roots); 520 kfree(mm->free_scoreboard); 521 kfree(mm->used_scoreboard); 522 } 523 EXPORT_SYMBOL(gpu_buddy_fini); 524 525 static int split_block(struct gpu_buddy *mm, 526 struct gpu_buddy_block *block) 527 { 528 unsigned int block_order = gpu_buddy_block_order(block) - 1; 529 u64 offset = gpu_buddy_block_offset(block); 530 531 BUG_ON(!gpu_buddy_block_is_free(block)); 532 BUG_ON(!gpu_buddy_block_order(block)); 533 534 block->left = gpu_block_alloc(mm, block, block_order, offset); 535 if (!block->left) 536 return -ENOMEM; 537 538 block->right = gpu_block_alloc(mm, block, block_order, 539 offset + (mm->chunk_size << block_order)); 540 if (!block->right) { 541 gpu_block_free(mm, block->left); 542 return -ENOMEM; 543 } 544 545 mark_split(mm, block); 546 547 if (gpu_buddy_block_is_clear(block)) { 548 mark_cleared(block->left); 549 mark_cleared(block->right); 550 clear_reset(block); 551 } 552 553 mark_free(mm, block->left); 554 mark_free(mm, block->right); 555 556 return 0; 557 } 558 559 /** 560 * gpu_buddy_reset_clear - reset blocks clear state 561 * 562 * @mm: GPU buddy manager 563 * @is_clear: blocks clear state 564 * 565 * Reset the clear state based on @is_clear value for each block 566 * in the freetree. 567 */ 568 void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear) 569 { 570 enum gpu_buddy_free_tree src_tree, dst_tree; 571 u64 root_size, size, start; 572 unsigned int order; 573 int i; 574 575 gpu_buddy_driver_lock_held(mm); 576 size = mm->size; 577 for (i = 0; i < mm->n_roots; ++i) { 578 order = ilog2(size) - ilog2(mm->chunk_size); 579 start = gpu_buddy_block_offset(mm->roots[i]); 580 __force_merge(mm, start, start + size, order); 581 582 root_size = mm->chunk_size << order; 583 size -= root_size; 584 } 585 586 src_tree = is_clear ? GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE; 587 dst_tree = is_clear ? GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE; 588 589 for (i = 0; i <= mm->max_order; ++i) { 590 struct rb_root *root = &mm->free_trees[src_tree][i]; 591 struct gpu_buddy_block *block, *tmp; 592 593 rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) { 594 rbtree_remove(mm, block); 595 if (is_clear) { 596 mark_cleared(block); 597 mm->clear_avail += gpu_buddy_block_size(mm, block); 598 } else { 599 clear_reset(block); 600 mm->clear_avail -= gpu_buddy_block_size(mm, block); 601 } 602 603 rbtree_insert(mm, block, dst_tree); 604 } 605 } 606 } 607 EXPORT_SYMBOL(gpu_buddy_reset_clear); 608 609 /** 610 * gpu_buddy_free_block - free a block 611 * 612 * @mm: GPU buddy manager 613 * @block: block to be freed 614 */ 615 void gpu_buddy_free_block(struct gpu_buddy *mm, 616 struct gpu_buddy_block *block) 617 { 618 gpu_buddy_driver_lock_held(mm); 619 BUG_ON(!gpu_buddy_block_is_allocated(block)); 620 mm->avail += gpu_buddy_block_size(mm, block); 621 if (gpu_buddy_block_is_clear(block)) 622 mm->clear_avail += gpu_buddy_block_size(mm, block); 623 624 __gpu_buddy_free(mm, block, false); 625 } 626 EXPORT_SYMBOL(gpu_buddy_free_block); 627 628 /** 629 * gpu_buddy_allocated_addr_to_block - given relative address find the allocated block 630 * 631 * @mm: GPU buddy manager 632 * @addr: Relative address 633 * 634 * Returns: 635 * gpu_buddy_block on success, NULL or error code on failure 636 */ 637 struct gpu_buddy_block *gpu_buddy_allocated_addr_to_block(struct gpu_buddy *mm, u64 addr) 638 { 639 struct gpu_buddy_block *block; 640 LIST_HEAD(dfs); 641 u64 end; 642 int i; 643 644 gpu_buddy_driver_lock_held(mm); 645 646 end = addr + mm->chunk_size - 1; 647 for (i = 0; i < mm->n_roots; ++i) 648 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 649 650 do { 651 u64 block_start; 652 u64 block_end; 653 654 block = list_first_entry_or_null(&dfs, 655 struct gpu_buddy_block, 656 tmp_link); 657 if (!block) 658 break; 659 660 list_del(&block->tmp_link); 661 662 block_start = gpu_buddy_block_offset(block); 663 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 664 665 if (!overlaps(addr, end, block_start, block_end)) 666 continue; 667 668 if (gpu_buddy_block_is_allocated(block)) 669 return block; 670 else if (gpu_buddy_block_is_free(block)) 671 return NULL; 672 673 list_add(&block->right->tmp_link, &dfs); 674 list_add(&block->left->tmp_link, &dfs); 675 } while (1); 676 677 return ERR_PTR(-ENXIO); 678 } 679 EXPORT_SYMBOL(gpu_buddy_allocated_addr_to_block); 680 681 static void __gpu_buddy_free_list(struct gpu_buddy *mm, 682 struct list_head *objects, 683 bool mark_clear, 684 bool mark_dirty) 685 { 686 struct gpu_buddy_block *block, *on; 687 688 gpu_buddy_assert(!(mark_dirty && mark_clear)); 689 690 list_for_each_entry_safe(block, on, objects, link) { 691 if (mark_clear) 692 mark_cleared(block); 693 else if (mark_dirty) 694 clear_reset(block); 695 gpu_buddy_free_block(mm, block); 696 cond_resched(); 697 } 698 INIT_LIST_HEAD(objects); 699 } 700 701 static void gpu_buddy_free_list_internal(struct gpu_buddy *mm, 702 struct list_head *objects) 703 { 704 /* 705 * Don't touch the clear/dirty bit, since allocation is still internal 706 * at this point. For example we might have just failed part of the 707 * allocation. 708 */ 709 __gpu_buddy_free_list(mm, objects, false, false); 710 } 711 712 /** 713 * gpu_buddy_free_list - free blocks 714 * 715 * @mm: GPU buddy manager 716 * @objects: input list head to free blocks 717 * @flags: optional flags like GPU_BUDDY_CLEARED 718 */ 719 void gpu_buddy_free_list(struct gpu_buddy *mm, 720 struct list_head *objects, 721 unsigned int flags) 722 { 723 bool mark_clear = flags & GPU_BUDDY_CLEARED; 724 725 gpu_buddy_driver_lock_held(mm); 726 __gpu_buddy_free_list(mm, objects, mark_clear, !mark_clear); 727 } 728 EXPORT_SYMBOL(gpu_buddy_free_list); 729 730 static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags) 731 { 732 bool needs_clear = flags & GPU_BUDDY_CLEAR_ALLOCATION; 733 734 return needs_clear != gpu_buddy_block_is_clear(block); 735 } 736 737 static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, 738 struct gpu_buddy_block *block) 739 { 740 struct gpu_buddy_block *buddy = __get_buddy(block); 741 742 if (buddy && 743 (gpu_buddy_block_is_free(block) && 744 gpu_buddy_block_is_free(buddy))) { 745 rbtree_remove(mm, block); 746 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 747 __gpu_buddy_free(mm, block, false); 748 } 749 } 750 751 static struct gpu_buddy_block * 752 __alloc_range_bias(struct gpu_buddy *mm, 753 u64 start, u64 end, 754 unsigned int order, 755 unsigned long flags, 756 bool fallback) 757 { 758 u64 req_size = mm->chunk_size << order; 759 struct gpu_buddy_block *block; 760 LIST_HEAD(dfs); 761 int err; 762 int i; 763 764 end = end - 1; 765 766 for (i = 0; i < mm->n_roots; ++i) 767 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 768 769 do { 770 u64 block_start; 771 u64 block_end; 772 773 block = list_first_entry_or_null(&dfs, 774 struct gpu_buddy_block, 775 tmp_link); 776 if (!block) 777 break; 778 779 list_del(&block->tmp_link); 780 781 if (gpu_buddy_block_order(block) < order) 782 continue; 783 784 block_start = gpu_buddy_block_offset(block); 785 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 786 787 if (!overlaps(start, end, block_start, block_end)) 788 continue; 789 790 if (gpu_buddy_block_is_allocated(block)) 791 continue; 792 793 if (block_start < start || block_end > end) { 794 u64 adjusted_start = max(block_start, start); 795 u64 adjusted_end = min(block_end, end); 796 797 if (round_down(adjusted_end + 1, req_size) <= 798 round_up(adjusted_start, req_size)) 799 continue; 800 } 801 802 if (!fallback && block_incompatible(block, flags)) 803 continue; 804 805 if (contains(start, end, block_start, block_end) && 806 order == gpu_buddy_block_order(block)) { 807 /* 808 * Find the free block within the range. 809 */ 810 if (gpu_buddy_block_is_free(block)) 811 return block; 812 813 continue; 814 } 815 816 if (!gpu_buddy_block_is_split(block)) { 817 err = split_block(mm, block); 818 if (unlikely(err)) 819 goto err_undo; 820 } 821 822 list_add(&block->right->tmp_link, &dfs); 823 list_add(&block->left->tmp_link, &dfs); 824 } while (1); 825 826 return ERR_PTR(-ENOSPC); 827 828 err_undo: 829 /* 830 * We really don't want to leave around a bunch of split blocks, since 831 * bigger is better, so make sure we merge everything back before we 832 * free the allocated blocks. 833 */ 834 __gpu_buddy_undo_splits(mm, block); 835 return ERR_PTR(err); 836 } 837 838 static struct gpu_buddy_block * 839 __gpu_buddy_alloc_range_bias(struct gpu_buddy *mm, 840 u64 start, u64 end, 841 unsigned int order, 842 unsigned long flags) 843 { 844 struct gpu_buddy_block *block; 845 bool fallback = false; 846 847 block = __alloc_range_bias(mm, start, end, order, 848 flags, fallback); 849 if (IS_ERR(block)) 850 return __alloc_range_bias(mm, start, end, order, 851 flags, !fallback); 852 853 return block; 854 } 855 856 static struct gpu_buddy_block * 857 get_maxblock(struct gpu_buddy *mm, 858 unsigned int order, 859 enum gpu_buddy_free_tree tree) 860 { 861 struct gpu_buddy_block *max_block = NULL, *block = NULL; 862 struct rb_root *root; 863 unsigned int i; 864 865 for (i = order; i <= mm->max_order; ++i) { 866 root = &mm->free_trees[tree][i]; 867 block = rbtree_last_free_block(root); 868 if (!block) 869 continue; 870 871 if (!max_block) { 872 max_block = block; 873 continue; 874 } 875 876 if (gpu_buddy_block_offset(block) > 877 gpu_buddy_block_offset(max_block)) { 878 max_block = block; 879 } 880 } 881 882 return max_block; 883 } 884 885 static struct gpu_buddy_block * 886 alloc_from_freetree(struct gpu_buddy *mm, 887 unsigned int order, 888 unsigned long flags) 889 { 890 struct gpu_buddy_block *block = NULL; 891 struct rb_root *root; 892 enum gpu_buddy_free_tree tree; 893 unsigned int tmp; 894 int err; 895 896 tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ? 897 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE; 898 899 if (flags & GPU_BUDDY_TOPDOWN_ALLOCATION) { 900 block = get_maxblock(mm, order, tree); 901 if (block) 902 /* Store the obtained block order */ 903 tmp = gpu_buddy_block_order(block); 904 } else { 905 for (tmp = order; tmp <= mm->max_order; ++tmp) { 906 /* Get RB tree root for this order and tree */ 907 root = &mm->free_trees[tree][tmp]; 908 block = rbtree_last_free_block(root); 909 if (block) 910 break; 911 } 912 } 913 914 if (!block) { 915 /* Try allocating from the other tree */ 916 tree = (tree == GPU_BUDDY_CLEAR_TREE) ? 917 GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE; 918 919 for (tmp = order; tmp <= mm->max_order; ++tmp) { 920 root = &mm->free_trees[tree][tmp]; 921 block = rbtree_last_free_block(root); 922 if (block) 923 break; 924 } 925 926 if (!block) 927 return ERR_PTR(-ENOSPC); 928 } 929 930 BUG_ON(!gpu_buddy_block_is_free(block)); 931 932 while (tmp != order) { 933 err = split_block(mm, block); 934 if (unlikely(err)) 935 goto err_undo; 936 937 block = block->right; 938 tmp--; 939 } 940 return block; 941 942 err_undo: 943 __gpu_buddy_undo_splits(mm, block); 944 return ERR_PTR(err); 945 } 946 947 static bool 948 gpu_buddy_can_offset_align(u64 size, u64 min_block_size) 949 { 950 return size < min_block_size && is_power_of_2(size); 951 } 952 953 static bool gpu_buddy_subtree_can_satisfy(struct rb_node *node, 954 unsigned int alignment) 955 { 956 struct gpu_buddy_block *block; 957 958 block = rbtree_get_free_block(node); 959 return block->subtree_max_alignment >= alignment; 960 } 961 962 static struct gpu_buddy_block * 963 gpu_buddy_find_block_aligned(struct gpu_buddy *mm, 964 enum gpu_buddy_free_tree tree, 965 unsigned int order, 966 unsigned int alignment, 967 unsigned long flags) 968 { 969 struct rb_root *root = &mm->free_trees[tree][order]; 970 struct rb_node *rb = root->rb_node; 971 972 while (rb) { 973 struct gpu_buddy_block *block = rbtree_get_free_block(rb); 974 struct rb_node *left_node = rb->rb_left, *right_node = rb->rb_right; 975 976 if (right_node) { 977 if (gpu_buddy_subtree_can_satisfy(right_node, alignment)) { 978 rb = right_node; 979 continue; 980 } 981 } 982 983 if (gpu_buddy_block_offset_alignment(block) >= alignment) 984 return block; 985 986 if (left_node) { 987 if (gpu_buddy_subtree_can_satisfy(left_node, alignment)) { 988 rb = left_node; 989 continue; 990 } 991 } 992 993 break; 994 } 995 996 return NULL; 997 } 998 999 static struct gpu_buddy_block * 1000 gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm, 1001 u64 size, 1002 u64 min_block_size, 1003 unsigned long flags) 1004 { 1005 struct gpu_buddy_block *block = NULL; 1006 unsigned int order, tmp, alignment; 1007 enum gpu_buddy_free_tree tree; 1008 unsigned long pages; 1009 int err; 1010 1011 alignment = ilog2(min_block_size); 1012 pages = size >> ilog2(mm->chunk_size); 1013 order = fls(pages) - 1; 1014 1015 tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ? 1016 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE; 1017 1018 for (tmp = order; tmp <= mm->max_order; ++tmp) { 1019 block = gpu_buddy_find_block_aligned(mm, tree, tmp, 1020 alignment, flags); 1021 if (!block) { 1022 tree = (tree == GPU_BUDDY_CLEAR_TREE) ? 1023 GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE; 1024 block = gpu_buddy_find_block_aligned(mm, tree, tmp, 1025 alignment, flags); 1026 } 1027 1028 if (block) 1029 break; 1030 } 1031 1032 if (!block) 1033 return ERR_PTR(-ENOSPC); 1034 1035 while (gpu_buddy_block_order(block) > order) { 1036 struct gpu_buddy_block *left, *right; 1037 1038 err = split_block(mm, block); 1039 if (unlikely(err)) 1040 goto err_undo; 1041 1042 left = block->left; 1043 right = block->right; 1044 1045 if (gpu_buddy_block_offset_alignment(right) >= alignment) 1046 block = right; 1047 else 1048 block = left; 1049 } 1050 1051 return block; 1052 1053 err_undo: 1054 /* 1055 * We really don't want to leave around a bunch of split blocks, since 1056 * bigger is better, so make sure we merge everything back before we 1057 * free the allocated blocks. 1058 */ 1059 __gpu_buddy_undo_splits(mm, block); 1060 return ERR_PTR(err); 1061 } 1062 1063 static int __alloc_range(struct gpu_buddy *mm, 1064 struct list_head *dfs, 1065 u64 start, u64 size, 1066 struct list_head *blocks, 1067 u64 *total_allocated_on_err) 1068 { 1069 struct gpu_buddy_block *block; 1070 u64 total_allocated = 0; 1071 LIST_HEAD(allocated); 1072 u64 end; 1073 int err; 1074 1075 end = start + size - 1; 1076 1077 do { 1078 u64 block_start; 1079 u64 block_end; 1080 1081 block = list_first_entry_or_null(dfs, 1082 struct gpu_buddy_block, 1083 tmp_link); 1084 if (!block) 1085 break; 1086 1087 list_del(&block->tmp_link); 1088 1089 block_start = gpu_buddy_block_offset(block); 1090 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 1091 1092 if (!overlaps(start, end, block_start, block_end)) 1093 continue; 1094 1095 if (gpu_buddy_block_is_allocated(block)) { 1096 err = -ENOSPC; 1097 goto err_free; 1098 } 1099 1100 if (contains(start, end, block_start, block_end)) { 1101 if (gpu_buddy_block_is_free(block)) { 1102 mark_allocated(mm, block); 1103 total_allocated += gpu_buddy_block_size(mm, block); 1104 mm->avail -= gpu_buddy_block_size(mm, block); 1105 if (gpu_buddy_block_is_clear(block)) 1106 mm->clear_avail -= gpu_buddy_block_size(mm, block); 1107 list_add_tail(&block->link, &allocated); 1108 continue; 1109 } else if (!mm->clear_avail) { 1110 err = -ENOSPC; 1111 goto err_free; 1112 } 1113 } 1114 1115 if (!gpu_buddy_block_is_split(block)) { 1116 err = split_block(mm, block); 1117 if (unlikely(err)) 1118 goto err_undo; 1119 } 1120 1121 list_add(&block->right->tmp_link, dfs); 1122 list_add(&block->left->tmp_link, dfs); 1123 } while (1); 1124 1125 if (total_allocated < size) { 1126 err = -ENOSPC; 1127 goto err_free; 1128 } 1129 1130 list_splice_tail(&allocated, blocks); 1131 1132 return 0; 1133 1134 err_undo: 1135 /* 1136 * We really don't want to leave around a bunch of split blocks, since 1137 * bigger is better, so make sure we merge everything back before we 1138 * free the allocated blocks. 1139 */ 1140 __gpu_buddy_undo_splits(mm, block); 1141 1142 err_free: 1143 if (err == -ENOSPC && total_allocated_on_err) { 1144 list_splice_tail(&allocated, blocks); 1145 *total_allocated_on_err = total_allocated; 1146 } else { 1147 gpu_buddy_free_list_internal(mm, &allocated); 1148 } 1149 1150 return err; 1151 } 1152 1153 static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, 1154 u64 start, 1155 u64 size, 1156 u64 *total_allocated_on_err, 1157 struct list_head *blocks) 1158 { 1159 LIST_HEAD(dfs); 1160 int i; 1161 1162 for (i = 0; i < mm->n_roots; ++i) 1163 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 1164 1165 return __alloc_range(mm, &dfs, start, size, 1166 blocks, total_allocated_on_err); 1167 } 1168 1169 static int __alloc_contig_aligned_retry(struct gpu_buddy *mm, 1170 u64 unaligned_offset, 1171 u64 size, 1172 u64 min_block_size, 1173 struct list_head *blocks) 1174 { 1175 u64 aligned_offset = round_down(unaligned_offset, min_block_size); 1176 1177 return __gpu_buddy_alloc_range(mm, aligned_offset, size, NULL, blocks); 1178 } 1179 1180 static int __alloc_contig_try_harder(struct gpu_buddy *mm, 1181 u64 size, 1182 u64 min_block_size, 1183 struct list_head *blocks) 1184 { 1185 u64 rhs_offset, lhs_offset, filled; 1186 struct gpu_buddy_block *block; 1187 unsigned int tree, order; 1188 u64 modify_size; 1189 int err; 1190 1191 modify_size = rounddown_pow_of_two(size); 1192 order = ilog2(modify_size) - ilog2(mm->chunk_size); 1193 if (order == 0) 1194 return -ENOSPC; 1195 1196 for_each_free_tree(tree) { 1197 struct rb_root *root; 1198 struct rb_node *iter; 1199 1200 root = &mm->free_trees[tree][order]; 1201 if (rbtree_is_empty(root)) 1202 continue; 1203 1204 iter = rb_last(root); 1205 while (iter) { 1206 block = rbtree_get_free_block(iter); 1207 1208 rhs_offset = gpu_buddy_block_offset(block); 1209 1210 /* Allocate blocks traversing RHS */ 1211 err = __gpu_buddy_alloc_range(mm, rhs_offset, size, 1212 &filled, blocks); 1213 if (err && err != -ENOSPC) 1214 return err; 1215 if (!err && IS_ALIGNED(rhs_offset, min_block_size)) 1216 return 0; 1217 if (!err) { 1218 /* Allocate the unaligned RHS offset using round_down */ 1219 gpu_buddy_free_list_internal(mm, blocks); 1220 err = __alloc_contig_aligned_retry(mm, rhs_offset, 1221 size, 1222 min_block_size, 1223 blocks); 1224 if (!err) 1225 return 0; 1226 if (err != -ENOSPC) { 1227 gpu_buddy_free_list_internal(mm, blocks); 1228 return err; 1229 } 1230 goto next; 1231 } 1232 1233 if (size - filled > rhs_offset) 1234 goto next; 1235 1236 lhs_offset = rhs_offset - (size - filled); 1237 1238 /* Allocate the unaligned LHS offset using round_down */ 1239 gpu_buddy_free_list_internal(mm, blocks); 1240 err = __alloc_contig_aligned_retry(mm, lhs_offset, size, 1241 min_block_size, blocks); 1242 if (!err) 1243 return 0; 1244 if (err != -ENOSPC) { 1245 gpu_buddy_free_list_internal(mm, blocks); 1246 return err; 1247 } 1248 next: 1249 gpu_buddy_free_list_internal(mm, blocks); 1250 iter = rb_prev(iter); 1251 } 1252 } 1253 1254 return -ENOSPC; 1255 } 1256 1257 /** 1258 * gpu_buddy_block_trim - free unused pages 1259 * 1260 * @mm: GPU buddy manager 1261 * @start: start address to begin the trimming. 1262 * @new_size: original size requested 1263 * @blocks: Input and output list of allocated blocks. 1264 * MUST contain single block as input to be trimmed. 1265 * On success will contain the newly allocated blocks 1266 * making up the @new_size. Blocks always appear in 1267 * ascending order 1268 * 1269 * For contiguous allocation, we round up the size to the nearest 1270 * power of two value, drivers consume *actual* size, so remaining 1271 * portions are unused and can be optionally freed with this function 1272 * 1273 * Returns: 1274 * 0 on success, error code on failure. 1275 */ 1276 int gpu_buddy_block_trim(struct gpu_buddy *mm, 1277 u64 *start, 1278 u64 new_size, 1279 struct list_head *blocks) 1280 { 1281 struct gpu_buddy_block *parent; 1282 struct gpu_buddy_block *block; 1283 u64 block_start, block_end; 1284 LIST_HEAD(dfs); 1285 u64 new_start; 1286 int err; 1287 1288 gpu_buddy_driver_lock_held(mm); 1289 1290 if (!list_is_singular(blocks)) 1291 return -EINVAL; 1292 1293 block = list_first_entry(blocks, 1294 struct gpu_buddy_block, 1295 link); 1296 1297 block_start = gpu_buddy_block_offset(block); 1298 block_end = block_start + gpu_buddy_block_size(mm, block); 1299 1300 if (WARN_ON(!gpu_buddy_block_is_allocated(block))) 1301 return -EINVAL; 1302 1303 if (new_size > gpu_buddy_block_size(mm, block)) 1304 return -EINVAL; 1305 1306 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) 1307 return -EINVAL; 1308 1309 if (new_size == gpu_buddy_block_size(mm, block)) 1310 return 0; 1311 1312 new_start = block_start; 1313 if (start) { 1314 new_start = *start; 1315 1316 if (new_start < block_start) 1317 return -EINVAL; 1318 1319 if (!IS_ALIGNED(new_start, mm->chunk_size)) 1320 return -EINVAL; 1321 1322 if (range_overflows(new_start, new_size, block_end)) 1323 return -EINVAL; 1324 } 1325 1326 list_del(&block->link); 1327 mark_free(mm, block); 1328 mm->avail += gpu_buddy_block_size(mm, block); 1329 if (gpu_buddy_block_is_clear(block)) 1330 mm->clear_avail += gpu_buddy_block_size(mm, block); 1331 1332 /* Prevent recursively freeing this node */ 1333 parent = block->parent; 1334 block->parent = NULL; 1335 1336 list_add(&block->tmp_link, &dfs); 1337 err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL); 1338 if (err) { 1339 mark_allocated(mm, block); 1340 mm->avail -= gpu_buddy_block_size(mm, block); 1341 if (gpu_buddy_block_is_clear(block)) 1342 mm->clear_avail -= gpu_buddy_block_size(mm, block); 1343 list_add(&block->link, blocks); 1344 } 1345 1346 block->parent = parent; 1347 return err; 1348 } 1349 EXPORT_SYMBOL(gpu_buddy_block_trim); 1350 1351 static struct gpu_buddy_block * 1352 __gpu_buddy_alloc_blocks(struct gpu_buddy *mm, 1353 u64 start, u64 end, 1354 u64 size, u64 min_block_size, 1355 unsigned int order, 1356 unsigned long flags) 1357 { 1358 if (flags & GPU_BUDDY_RANGE_ALLOCATION) 1359 /* Allocate traversing within the range */ 1360 return __gpu_buddy_alloc_range_bias(mm, start, end, 1361 order, flags); 1362 else if (size < min_block_size) 1363 /* Allocate from an offset-aligned region without size rounding */ 1364 return gpu_buddy_offset_aligned_allocation(mm, size, 1365 min_block_size, 1366 flags); 1367 else 1368 /* Allocate from freetree */ 1369 return alloc_from_freetree(mm, order, flags); 1370 } 1371 1372 /** 1373 * gpu_buddy_alloc_blocks - allocate power-of-two blocks 1374 * 1375 * @mm: GPU buddy manager to allocate from 1376 * @start: start of the allowed range for this block 1377 * @end: end of the allowed range for this block 1378 * @size: size of the allocation in bytes 1379 * @min_block_size: alignment of the allocation 1380 * @blocks: output list head to add allocated blocks 1381 * @flags: GPU_BUDDY_*_ALLOCATION flags 1382 * 1383 * alloc_range_bias() called on range limitations, which traverses 1384 * the tree and returns the desired block. 1385 * 1386 * alloc_from_freetree() called when *no* range restrictions 1387 * are enforced, which picks the block from the freetree. 1388 * 1389 * Returns: 1390 * 0 on success, error code on failure. 1391 */ 1392 int gpu_buddy_alloc_blocks(struct gpu_buddy *mm, 1393 u64 start, u64 end, u64 size, 1394 u64 min_block_size, 1395 struct list_head *blocks, 1396 unsigned long flags) 1397 { 1398 struct gpu_buddy_block *block = NULL; 1399 u64 original_size, original_min_size; 1400 unsigned int min_order, order; 1401 LIST_HEAD(allocated); 1402 unsigned long pages; 1403 int err; 1404 1405 gpu_buddy_driver_lock_held(mm); 1406 1407 if (size < mm->chunk_size) 1408 return -EINVAL; 1409 1410 if (min_block_size < mm->chunk_size) 1411 return -EINVAL; 1412 1413 if (!is_power_of_2(min_block_size)) 1414 return -EINVAL; 1415 1416 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) 1417 return -EINVAL; 1418 1419 if (end > mm->size) 1420 return -EINVAL; 1421 1422 if (range_overflows(start, size, mm->size)) 1423 return -EINVAL; 1424 1425 /* Actual range allocation */ 1426 if (start + size == end) { 1427 if (!IS_ALIGNED(start | end, min_block_size)) 1428 return -EINVAL; 1429 1430 return __gpu_buddy_alloc_range(mm, start, size, NULL, blocks); 1431 } 1432 1433 original_size = size; 1434 original_min_size = min_block_size; 1435 1436 /* Roundup the size to power of 2 */ 1437 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) { 1438 size = roundup_pow_of_two(size); 1439 min_block_size = size; 1440 /* 1441 * Normalize the requested size to min_block_size for regular allocations. 1442 * Offset-aligned allocations intentionally skip size rounding. 1443 */ 1444 } else if (!gpu_buddy_can_offset_align(size, min_block_size)) { 1445 size = round_up(size, min_block_size); 1446 } 1447 1448 pages = size >> ilog2(mm->chunk_size); 1449 order = fls(pages) - 1; 1450 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size); 1451 1452 if (order > mm->max_order || size > mm->size) { 1453 if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) && 1454 !(flags & GPU_BUDDY_RANGE_ALLOCATION)) 1455 return __alloc_contig_try_harder(mm, original_size, 1456 original_min_size, blocks); 1457 1458 return -EINVAL; 1459 } 1460 1461 do { 1462 order = min(order, (unsigned int)fls(pages) - 1); 1463 BUG_ON(order > mm->max_order); 1464 /* 1465 * Regular allocations must not allocate blocks smaller than min_block_size. 1466 * Offset-aligned allocations deliberately bypass this constraint. 1467 */ 1468 BUG_ON(size >= min_block_size && order < min_order); 1469 1470 do { 1471 unsigned int fallback_order; 1472 1473 block = __gpu_buddy_alloc_blocks(mm, start, 1474 end, 1475 size, 1476 min_block_size, 1477 order, 1478 flags); 1479 if (!IS_ERR(block)) 1480 break; 1481 1482 if (size < min_block_size) { 1483 fallback_order = order; 1484 } else if (order == min_order) { 1485 fallback_order = min_order; 1486 } else { 1487 order--; 1488 continue; 1489 } 1490 1491 /* Try allocation through force merge method */ 1492 if (mm->clear_avail && 1493 !__force_merge(mm, start, end, fallback_order)) { 1494 block = __gpu_buddy_alloc_blocks(mm, start, 1495 end, 1496 size, 1497 min_block_size, 1498 fallback_order, 1499 flags); 1500 if (!IS_ERR(block)) { 1501 order = fallback_order; 1502 break; 1503 } 1504 } 1505 1506 /* 1507 * Try contiguous block allocation through 1508 * try harder method. 1509 */ 1510 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION && 1511 !(flags & GPU_BUDDY_RANGE_ALLOCATION)) 1512 return __alloc_contig_try_harder(mm, 1513 original_size, 1514 original_min_size, 1515 blocks); 1516 err = -ENOSPC; 1517 goto err_free; 1518 } while (1); 1519 1520 mark_allocated(mm, block); 1521 mm->avail -= gpu_buddy_block_size(mm, block); 1522 if (gpu_buddy_block_is_clear(block)) 1523 mm->clear_avail -= gpu_buddy_block_size(mm, block); 1524 kmemleak_update_trace(block); 1525 list_add_tail(&block->link, &allocated); 1526 1527 pages -= BIT(order); 1528 1529 if (!pages) 1530 break; 1531 } while (1); 1532 1533 /* Trim the allocated block to the required size */ 1534 if (!(flags & GPU_BUDDY_TRIM_DISABLE) && 1535 original_size != size) { 1536 struct list_head *trim_list; 1537 LIST_HEAD(temp); 1538 u64 trim_size; 1539 1540 trim_list = &allocated; 1541 trim_size = original_size; 1542 1543 if (!list_is_singular(&allocated)) { 1544 block = list_last_entry(&allocated, typeof(*block), link); 1545 list_move(&block->link, &temp); 1546 trim_list = &temp; 1547 trim_size = gpu_buddy_block_size(mm, block) - 1548 (size - original_size); 1549 } 1550 1551 gpu_buddy_block_trim(mm, 1552 NULL, 1553 trim_size, 1554 trim_list); 1555 1556 if (!list_empty(&temp)) 1557 list_splice_tail(trim_list, &allocated); 1558 } 1559 1560 list_splice_tail(&allocated, blocks); 1561 return 0; 1562 1563 err_free: 1564 gpu_buddy_free_list_internal(mm, &allocated); 1565 return err; 1566 } 1567 EXPORT_SYMBOL(gpu_buddy_alloc_blocks); 1568 1569 /** 1570 * gpu_buddy_block_print - print block information 1571 * 1572 * @mm: GPU buddy manager 1573 * @block: GPU buddy block 1574 */ 1575 void gpu_buddy_block_print(struct gpu_buddy *mm, 1576 struct gpu_buddy_block *block) 1577 { 1578 u64 start = gpu_buddy_block_offset(block); 1579 u64 size = gpu_buddy_block_size(mm, block); 1580 1581 pr_info("%#018llx-%#018llx: %llu\n", start, start + size, size); 1582 } 1583 EXPORT_SYMBOL(gpu_buddy_block_print); 1584 1585 /** 1586 * gpu_buddy_print - print allocator state 1587 * 1588 * @mm: GPU buddy manager 1589 * @p: GPU printer to use 1590 */ 1591 void gpu_buddy_print(struct gpu_buddy *mm) 1592 { 1593 int order; 1594 1595 gpu_buddy_driver_lock_held(mm); 1596 pr_info("chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n", 1597 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20); 1598 1599 for (order = mm->max_order; order >= 0; order--) { 1600 u64 free_count = mm->free_scoreboard[order]; 1601 u64 used_count = mm->used_scoreboard[order]; 1602 u64 block_size = mm->chunk_size << order; 1603 u64 free = free_count * block_size; 1604 u64 used = used_count * block_size; 1605 1606 if (block_size < SZ_1M) 1607 pr_info("order-%2d free: %8llu KiB, used: %8llu KiB, free_blocks: %llu, used_blocks: %llu\n", 1608 order, free >> 10, used >> 10, free_count, used_count); 1609 else 1610 pr_info("order-%2d free: %8llu MiB, used: %8llu MiB, free_blocks: %llu, used_blocks: %llu\n", 1611 order, free >> 20, used >> 20, free_count, used_count); 1612 } 1613 } 1614 EXPORT_SYMBOL(gpu_buddy_print); 1615 1616 static void gpu_buddy_module_exit(void) 1617 { 1618 kmem_cache_destroy(slab_blocks); 1619 } 1620 1621 static int __init gpu_buddy_module_init(void) 1622 { 1623 slab_blocks = KMEM_CACHE(gpu_buddy_block, 0); 1624 if (!slab_blocks) 1625 return -ENOMEM; 1626 1627 return 0; 1628 } 1629 1630 module_init(gpu_buddy_module_init); 1631 module_exit(gpu_buddy_module_exit); 1632 1633 MODULE_DESCRIPTION("GPU Buddy Allocator"); 1634 MODULE_LICENSE("Dual MIT/GPL"); 1635