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_array(GPU_BUDDY_MAX_FREE_TREES, 415 sizeof(*mm->free_trees), 416 GFP_KERNEL); 417 if (!mm->free_trees) 418 goto out_free_used_scoreboard; 419 420 for_each_free_tree(i) { 421 mm->free_trees[i] = kmalloc_array(mm->max_order + 1, 422 sizeof(struct rb_root), 423 GFP_KERNEL); 424 if (!mm->free_trees[i]) 425 goto out_free_tree; 426 427 for (j = 0; j <= mm->max_order; ++j) 428 mm->free_trees[i][j] = RB_ROOT; 429 } 430 431 mm->n_roots = hweight64(size); 432 433 mm->roots = kmalloc_array(mm->n_roots, 434 sizeof(struct gpu_buddy_block *), 435 GFP_KERNEL); 436 if (!mm->roots) 437 goto out_free_tree; 438 439 /* 440 * Split into power-of-two blocks, in case we are given a size that is 441 * not itself a power-of-two. 442 */ 443 do { 444 struct gpu_buddy_block *root; 445 unsigned int order; 446 u64 root_size; 447 448 order = ilog2(size) - ilog2(chunk_size); 449 root_size = chunk_size << order; 450 451 root = gpu_block_alloc(mm, NULL, order, offset); 452 if (!root) 453 goto out_free_roots; 454 455 mark_free(mm, root); 456 457 BUG_ON(root_count > mm->max_order); 458 BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size); 459 460 mm->roots[root_count] = root; 461 462 offset += root_size; 463 size -= root_size; 464 root_count++; 465 } while (size); 466 467 #ifdef CONFIG_LOCKDEP 468 mm->lock_dep_map = NULL; 469 #endif 470 return 0; 471 472 out_free_roots: 473 while (root_count--) 474 gpu_block_free(mm, mm->roots[root_count]); 475 kfree(mm->roots); 476 out_free_tree: 477 while (i--) 478 kfree(mm->free_trees[i]); 479 kfree(mm->free_trees); 480 out_free_used_scoreboard: 481 kfree(mm->used_scoreboard); 482 out_free_free_scoreboard: 483 kfree(mm->free_scoreboard); 484 return -ENOMEM; 485 } 486 EXPORT_SYMBOL(gpu_buddy_init); 487 488 /** 489 * gpu_buddy_fini - tear down the memory manager 490 * 491 * @mm: GPU buddy manager to free 492 * 493 * Cleanup memory manager resources and the freetree 494 */ 495 void gpu_buddy_fini(struct gpu_buddy *mm) 496 { 497 u64 root_size, size, start; 498 unsigned int order; 499 int i; 500 501 size = mm->size; 502 503 for (i = 0; i < mm->n_roots; ++i) { 504 order = ilog2(size) - ilog2(mm->chunk_size); 505 start = gpu_buddy_block_offset(mm->roots[i]); 506 __force_merge(mm, start, start + size, order); 507 508 gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i])); 509 510 gpu_block_free(mm, mm->roots[i]); 511 512 root_size = mm->chunk_size << order; 513 size -= root_size; 514 } 515 516 gpu_buddy_assert(mm->avail == mm->size); 517 518 for (i = 0; i <= mm->max_order; ++i) 519 gpu_buddy_assert(!mm->used_scoreboard[i]); 520 521 for_each_free_tree(i) 522 kfree(mm->free_trees[i]); 523 kfree(mm->free_trees); 524 kfree(mm->roots); 525 kfree(mm->free_scoreboard); 526 kfree(mm->used_scoreboard); 527 } 528 EXPORT_SYMBOL(gpu_buddy_fini); 529 530 static int split_block(struct gpu_buddy *mm, 531 struct gpu_buddy_block *block) 532 { 533 unsigned int block_order = gpu_buddy_block_order(block) - 1; 534 u64 offset = gpu_buddy_block_offset(block); 535 536 BUG_ON(!gpu_buddy_block_is_free(block)); 537 BUG_ON(!gpu_buddy_block_order(block)); 538 539 block->left = gpu_block_alloc(mm, block, block_order, offset); 540 if (!block->left) 541 return -ENOMEM; 542 543 block->right = gpu_block_alloc(mm, block, block_order, 544 offset + (mm->chunk_size << block_order)); 545 if (!block->right) { 546 gpu_block_free(mm, block->left); 547 return -ENOMEM; 548 } 549 550 mark_split(mm, block); 551 552 if (gpu_buddy_block_is_clear(block)) { 553 mark_cleared(block->left); 554 mark_cleared(block->right); 555 clear_reset(block); 556 } 557 558 mark_free(mm, block->left); 559 mark_free(mm, block->right); 560 561 return 0; 562 } 563 564 /** 565 * gpu_buddy_reset_clear - reset blocks clear state 566 * 567 * @mm: GPU buddy manager 568 * @is_clear: blocks clear state 569 * 570 * Reset the clear state based on @is_clear value for each block 571 * in the freetree. 572 */ 573 void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear) 574 { 575 enum gpu_buddy_free_tree src_tree, dst_tree; 576 u64 root_size, size, start; 577 unsigned int order; 578 int i; 579 580 gpu_buddy_driver_lock_held(mm); 581 size = mm->size; 582 for (i = 0; i < mm->n_roots; ++i) { 583 order = ilog2(size) - ilog2(mm->chunk_size); 584 start = gpu_buddy_block_offset(mm->roots[i]); 585 __force_merge(mm, start, start + size, order); 586 587 root_size = mm->chunk_size << order; 588 size -= root_size; 589 } 590 591 src_tree = is_clear ? GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE; 592 dst_tree = is_clear ? GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE; 593 594 for (i = 0; i <= mm->max_order; ++i) { 595 struct rb_root *root = &mm->free_trees[src_tree][i]; 596 struct gpu_buddy_block *block, *tmp; 597 598 rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) { 599 rbtree_remove(mm, block); 600 if (is_clear) { 601 mark_cleared(block); 602 mm->clear_avail += gpu_buddy_block_size(mm, block); 603 } else { 604 clear_reset(block); 605 mm->clear_avail -= gpu_buddy_block_size(mm, block); 606 } 607 608 rbtree_insert(mm, block, dst_tree); 609 } 610 } 611 } 612 EXPORT_SYMBOL(gpu_buddy_reset_clear); 613 614 /** 615 * gpu_buddy_free_block - free a block 616 * 617 * @mm: GPU buddy manager 618 * @block: block to be freed 619 */ 620 void gpu_buddy_free_block(struct gpu_buddy *mm, 621 struct gpu_buddy_block *block) 622 { 623 gpu_buddy_driver_lock_held(mm); 624 BUG_ON(!gpu_buddy_block_is_allocated(block)); 625 mm->avail += gpu_buddy_block_size(mm, block); 626 if (gpu_buddy_block_is_clear(block)) 627 mm->clear_avail += gpu_buddy_block_size(mm, block); 628 629 __gpu_buddy_free(mm, block, false); 630 } 631 EXPORT_SYMBOL(gpu_buddy_free_block); 632 633 /** 634 * gpu_buddy_allocated_addr_to_block - given relative address find the allocated block 635 * 636 * @mm: GPU buddy manager 637 * @addr: Relative address 638 * 639 * Returns: 640 * gpu_buddy_block on success, NULL or error code on failure 641 */ 642 struct gpu_buddy_block *gpu_buddy_allocated_addr_to_block(struct gpu_buddy *mm, u64 addr) 643 { 644 struct gpu_buddy_block *block; 645 LIST_HEAD(dfs); 646 u64 end; 647 int i; 648 649 gpu_buddy_driver_lock_held(mm); 650 651 end = addr + mm->chunk_size - 1; 652 for (i = 0; i < mm->n_roots; ++i) 653 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 654 655 do { 656 u64 block_start; 657 u64 block_end; 658 659 block = list_first_entry_or_null(&dfs, 660 struct gpu_buddy_block, 661 tmp_link); 662 if (!block) 663 break; 664 665 list_del(&block->tmp_link); 666 667 block_start = gpu_buddy_block_offset(block); 668 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 669 670 if (!overlaps(addr, end, block_start, block_end)) 671 continue; 672 673 if (gpu_buddy_block_is_allocated(block)) 674 return block; 675 else if (gpu_buddy_block_is_free(block)) 676 return NULL; 677 678 list_add(&block->right->tmp_link, &dfs); 679 list_add(&block->left->tmp_link, &dfs); 680 } while (1); 681 682 return ERR_PTR(-ENXIO); 683 } 684 EXPORT_SYMBOL(gpu_buddy_allocated_addr_to_block); 685 686 static void __gpu_buddy_free_list(struct gpu_buddy *mm, 687 struct list_head *objects, 688 bool mark_clear, 689 bool mark_dirty) 690 { 691 struct gpu_buddy_block *block, *on; 692 693 gpu_buddy_assert(!(mark_dirty && mark_clear)); 694 695 list_for_each_entry_safe(block, on, objects, link) { 696 if (mark_clear) 697 mark_cleared(block); 698 else if (mark_dirty) 699 clear_reset(block); 700 gpu_buddy_free_block(mm, block); 701 cond_resched(); 702 } 703 INIT_LIST_HEAD(objects); 704 } 705 706 static void gpu_buddy_free_list_internal(struct gpu_buddy *mm, 707 struct list_head *objects) 708 { 709 /* 710 * Don't touch the clear/dirty bit, since allocation is still internal 711 * at this point. For example we might have just failed part of the 712 * allocation. 713 */ 714 __gpu_buddy_free_list(mm, objects, false, false); 715 } 716 717 /** 718 * gpu_buddy_free_list - free blocks 719 * 720 * @mm: GPU buddy manager 721 * @objects: input list head to free blocks 722 * @flags: optional flags like GPU_BUDDY_CLEARED 723 */ 724 void gpu_buddy_free_list(struct gpu_buddy *mm, 725 struct list_head *objects, 726 unsigned int flags) 727 { 728 bool mark_clear = flags & GPU_BUDDY_CLEARED; 729 730 gpu_buddy_driver_lock_held(mm); 731 __gpu_buddy_free_list(mm, objects, mark_clear, !mark_clear); 732 } 733 EXPORT_SYMBOL(gpu_buddy_free_list); 734 735 static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags) 736 { 737 bool needs_clear = flags & GPU_BUDDY_CLEAR_ALLOCATION; 738 739 return needs_clear != gpu_buddy_block_is_clear(block); 740 } 741 742 static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, 743 struct gpu_buddy_block *block) 744 { 745 struct gpu_buddy_block *buddy = __get_buddy(block); 746 747 if (buddy && 748 (gpu_buddy_block_is_free(block) && 749 gpu_buddy_block_is_free(buddy))) { 750 rbtree_remove(mm, block); 751 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 752 __gpu_buddy_free(mm, block, false); 753 } 754 } 755 756 static struct gpu_buddy_block * 757 __alloc_range_bias(struct gpu_buddy *mm, 758 u64 start, u64 end, 759 unsigned int order, 760 unsigned long flags, 761 bool fallback) 762 { 763 u64 req_size = mm->chunk_size << order; 764 struct gpu_buddy_block *block; 765 LIST_HEAD(dfs); 766 int err; 767 int i; 768 769 end = end - 1; 770 771 for (i = 0; i < mm->n_roots; ++i) 772 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 773 774 do { 775 u64 block_start; 776 u64 block_end; 777 778 block = list_first_entry_or_null(&dfs, 779 struct gpu_buddy_block, 780 tmp_link); 781 if (!block) 782 break; 783 784 list_del(&block->tmp_link); 785 786 if (gpu_buddy_block_order(block) < order) 787 continue; 788 789 block_start = gpu_buddy_block_offset(block); 790 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 791 792 if (!overlaps(start, end, block_start, block_end)) 793 continue; 794 795 if (gpu_buddy_block_is_allocated(block)) 796 continue; 797 798 if (block_start < start || block_end > end) { 799 u64 adjusted_start = max(block_start, start); 800 u64 adjusted_end = min(block_end, end); 801 802 if (round_down(adjusted_end + 1, req_size) <= 803 round_up(adjusted_start, req_size)) 804 continue; 805 } 806 807 if (!fallback && block_incompatible(block, flags)) 808 continue; 809 810 if (contains(start, end, block_start, block_end) && 811 order == gpu_buddy_block_order(block)) { 812 /* 813 * Find the free block within the range. 814 */ 815 if (gpu_buddy_block_is_free(block)) 816 return block; 817 818 continue; 819 } 820 821 if (!gpu_buddy_block_is_split(block)) { 822 err = split_block(mm, block); 823 if (unlikely(err)) 824 goto err_undo; 825 } 826 827 list_add(&block->right->tmp_link, &dfs); 828 list_add(&block->left->tmp_link, &dfs); 829 } while (1); 830 831 return ERR_PTR(-ENOSPC); 832 833 err_undo: 834 /* 835 * We really don't want to leave around a bunch of split blocks, since 836 * bigger is better, so make sure we merge everything back before we 837 * free the allocated blocks. 838 */ 839 __gpu_buddy_undo_splits(mm, block); 840 return ERR_PTR(err); 841 } 842 843 static struct gpu_buddy_block * 844 __gpu_buddy_alloc_range_bias(struct gpu_buddy *mm, 845 u64 start, u64 end, 846 unsigned int order, 847 unsigned long flags) 848 { 849 struct gpu_buddy_block *block; 850 bool fallback = false; 851 852 block = __alloc_range_bias(mm, start, end, order, 853 flags, fallback); 854 if (IS_ERR(block)) 855 return __alloc_range_bias(mm, start, end, order, 856 flags, !fallback); 857 858 return block; 859 } 860 861 static struct gpu_buddy_block * 862 get_maxblock(struct gpu_buddy *mm, 863 unsigned int order, 864 enum gpu_buddy_free_tree tree) 865 { 866 struct gpu_buddy_block *max_block = NULL, *block = NULL; 867 struct rb_root *root; 868 unsigned int i; 869 870 for (i = order; i <= mm->max_order; ++i) { 871 root = &mm->free_trees[tree][i]; 872 block = rbtree_last_free_block(root); 873 if (!block) 874 continue; 875 876 if (!max_block) { 877 max_block = block; 878 continue; 879 } 880 881 if (gpu_buddy_block_offset(block) > 882 gpu_buddy_block_offset(max_block)) { 883 max_block = block; 884 } 885 } 886 887 return max_block; 888 } 889 890 static struct gpu_buddy_block * 891 alloc_from_freetree(struct gpu_buddy *mm, 892 unsigned int order, 893 unsigned long flags) 894 { 895 struct gpu_buddy_block *block = NULL; 896 struct rb_root *root; 897 enum gpu_buddy_free_tree tree; 898 unsigned int tmp; 899 int err; 900 901 tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ? 902 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE; 903 904 if (flags & GPU_BUDDY_TOPDOWN_ALLOCATION) { 905 block = get_maxblock(mm, order, tree); 906 if (block) 907 /* Store the obtained block order */ 908 tmp = gpu_buddy_block_order(block); 909 } else { 910 for (tmp = order; tmp <= mm->max_order; ++tmp) { 911 /* Get RB tree root for this order and tree */ 912 root = &mm->free_trees[tree][tmp]; 913 block = rbtree_last_free_block(root); 914 if (block) 915 break; 916 } 917 } 918 919 if (!block) { 920 /* Try allocating from the other tree */ 921 tree = (tree == GPU_BUDDY_CLEAR_TREE) ? 922 GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE; 923 924 for (tmp = order; tmp <= mm->max_order; ++tmp) { 925 root = &mm->free_trees[tree][tmp]; 926 block = rbtree_last_free_block(root); 927 if (block) 928 break; 929 } 930 931 if (!block) 932 return ERR_PTR(-ENOSPC); 933 } 934 935 BUG_ON(!gpu_buddy_block_is_free(block)); 936 937 while (tmp != order) { 938 err = split_block(mm, block); 939 if (unlikely(err)) 940 goto err_undo; 941 942 block = block->right; 943 tmp--; 944 } 945 return block; 946 947 err_undo: 948 __gpu_buddy_undo_splits(mm, block); 949 return ERR_PTR(err); 950 } 951 952 static bool 953 gpu_buddy_can_offset_align(u64 size, u64 min_block_size) 954 { 955 return size < min_block_size && is_power_of_2(size); 956 } 957 958 static bool gpu_buddy_subtree_can_satisfy(struct rb_node *node, 959 unsigned int alignment) 960 { 961 struct gpu_buddy_block *block; 962 963 block = rbtree_get_free_block(node); 964 return block->subtree_max_alignment >= alignment; 965 } 966 967 static struct gpu_buddy_block * 968 gpu_buddy_find_block_aligned(struct gpu_buddy *mm, 969 enum gpu_buddy_free_tree tree, 970 unsigned int order, 971 unsigned int alignment, 972 unsigned long flags) 973 { 974 struct rb_root *root = &mm->free_trees[tree][order]; 975 struct rb_node *rb = root->rb_node; 976 977 while (rb) { 978 struct gpu_buddy_block *block = rbtree_get_free_block(rb); 979 struct rb_node *left_node = rb->rb_left, *right_node = rb->rb_right; 980 981 if (right_node) { 982 if (gpu_buddy_subtree_can_satisfy(right_node, alignment)) { 983 rb = right_node; 984 continue; 985 } 986 } 987 988 if (gpu_buddy_block_offset_alignment(block) >= alignment) 989 return block; 990 991 if (left_node) { 992 if (gpu_buddy_subtree_can_satisfy(left_node, alignment)) { 993 rb = left_node; 994 continue; 995 } 996 } 997 998 break; 999 } 1000 1001 return NULL; 1002 } 1003 1004 static struct gpu_buddy_block * 1005 gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm, 1006 u64 size, 1007 u64 min_block_size, 1008 unsigned long flags) 1009 { 1010 struct gpu_buddy_block *block = NULL; 1011 unsigned int order, tmp, alignment; 1012 enum gpu_buddy_free_tree tree; 1013 unsigned long pages; 1014 int err; 1015 1016 alignment = ilog2(min_block_size); 1017 pages = size >> ilog2(mm->chunk_size); 1018 order = fls(pages) - 1; 1019 1020 tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ? 1021 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE; 1022 1023 for (tmp = order; tmp <= mm->max_order; ++tmp) { 1024 block = gpu_buddy_find_block_aligned(mm, tree, tmp, 1025 alignment, flags); 1026 if (!block) { 1027 tree = (tree == GPU_BUDDY_CLEAR_TREE) ? 1028 GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE; 1029 block = gpu_buddy_find_block_aligned(mm, tree, tmp, 1030 alignment, flags); 1031 } 1032 1033 if (block) 1034 break; 1035 } 1036 1037 if (!block) 1038 return ERR_PTR(-ENOSPC); 1039 1040 while (gpu_buddy_block_order(block) > order) { 1041 struct gpu_buddy_block *left, *right; 1042 1043 err = split_block(mm, block); 1044 if (unlikely(err)) 1045 goto err_undo; 1046 1047 left = block->left; 1048 right = block->right; 1049 1050 if (gpu_buddy_block_offset_alignment(right) >= alignment) 1051 block = right; 1052 else 1053 block = left; 1054 } 1055 1056 return block; 1057 1058 err_undo: 1059 /* 1060 * We really don't want to leave around a bunch of split blocks, since 1061 * bigger is better, so make sure we merge everything back before we 1062 * free the allocated blocks. 1063 */ 1064 __gpu_buddy_undo_splits(mm, block); 1065 return ERR_PTR(err); 1066 } 1067 1068 static int __alloc_range(struct gpu_buddy *mm, 1069 struct list_head *dfs, 1070 u64 start, u64 size, 1071 struct list_head *blocks, 1072 u64 *total_allocated_on_err) 1073 { 1074 struct gpu_buddy_block *block; 1075 u64 total_allocated = 0; 1076 LIST_HEAD(allocated); 1077 u64 end; 1078 int err; 1079 1080 end = start + size - 1; 1081 1082 do { 1083 u64 block_start; 1084 u64 block_end; 1085 1086 block = list_first_entry_or_null(dfs, 1087 struct gpu_buddy_block, 1088 tmp_link); 1089 if (!block) 1090 break; 1091 1092 list_del(&block->tmp_link); 1093 1094 block_start = gpu_buddy_block_offset(block); 1095 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 1096 1097 if (!overlaps(start, end, block_start, block_end)) 1098 continue; 1099 1100 if (gpu_buddy_block_is_allocated(block)) { 1101 err = -ENOSPC; 1102 goto err_free; 1103 } 1104 1105 if (contains(start, end, block_start, block_end)) { 1106 if (gpu_buddy_block_is_free(block)) { 1107 mark_allocated(mm, block); 1108 total_allocated += gpu_buddy_block_size(mm, block); 1109 mm->avail -= gpu_buddy_block_size(mm, block); 1110 if (gpu_buddy_block_is_clear(block)) 1111 mm->clear_avail -= gpu_buddy_block_size(mm, block); 1112 list_add_tail(&block->link, &allocated); 1113 continue; 1114 } else if (!mm->clear_avail) { 1115 err = -ENOSPC; 1116 goto err_free; 1117 } 1118 } 1119 1120 if (!gpu_buddy_block_is_split(block)) { 1121 err = split_block(mm, block); 1122 if (unlikely(err)) 1123 goto err_undo; 1124 } 1125 1126 list_add(&block->right->tmp_link, dfs); 1127 list_add(&block->left->tmp_link, dfs); 1128 } while (1); 1129 1130 if (total_allocated < size) { 1131 err = -ENOSPC; 1132 goto err_free; 1133 } 1134 1135 list_splice_tail(&allocated, blocks); 1136 1137 return 0; 1138 1139 err_undo: 1140 /* 1141 * We really don't want to leave around a bunch of split blocks, since 1142 * bigger is better, so make sure we merge everything back before we 1143 * free the allocated blocks. 1144 */ 1145 __gpu_buddy_undo_splits(mm, block); 1146 1147 err_free: 1148 if (err == -ENOSPC && total_allocated_on_err) { 1149 list_splice_tail(&allocated, blocks); 1150 *total_allocated_on_err = total_allocated; 1151 } else { 1152 gpu_buddy_free_list_internal(mm, &allocated); 1153 } 1154 1155 return err; 1156 } 1157 1158 static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, 1159 u64 start, 1160 u64 size, 1161 u64 *total_allocated_on_err, 1162 struct list_head *blocks) 1163 { 1164 LIST_HEAD(dfs); 1165 int i; 1166 1167 for (i = 0; i < mm->n_roots; ++i) 1168 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 1169 1170 return __alloc_range(mm, &dfs, start, size, 1171 blocks, total_allocated_on_err); 1172 } 1173 1174 static int __alloc_contig_aligned_retry(struct gpu_buddy *mm, 1175 u64 unaligned_offset, 1176 u64 size, 1177 u64 min_block_size, 1178 struct list_head *blocks) 1179 { 1180 u64 aligned_offset = round_down(unaligned_offset, min_block_size); 1181 1182 return __gpu_buddy_alloc_range(mm, aligned_offset, size, NULL, blocks); 1183 } 1184 1185 static int __alloc_contig_try_harder(struct gpu_buddy *mm, 1186 u64 size, 1187 u64 min_block_size, 1188 struct list_head *blocks) 1189 { 1190 u64 rhs_offset, lhs_offset, filled; 1191 struct gpu_buddy_block *block; 1192 unsigned int tree, order; 1193 u64 modify_size; 1194 int err; 1195 1196 modify_size = rounddown_pow_of_two(size); 1197 order = ilog2(modify_size) - ilog2(mm->chunk_size); 1198 if (order == 0) 1199 return -ENOSPC; 1200 1201 for_each_free_tree(tree) { 1202 struct rb_root *root; 1203 struct rb_node *iter; 1204 1205 root = &mm->free_trees[tree][order]; 1206 if (rbtree_is_empty(root)) 1207 continue; 1208 1209 iter = rb_last(root); 1210 while (iter) { 1211 block = rbtree_get_free_block(iter); 1212 1213 rhs_offset = gpu_buddy_block_offset(block); 1214 1215 /* Allocate blocks traversing RHS */ 1216 err = __gpu_buddy_alloc_range(mm, rhs_offset, size, 1217 &filled, blocks); 1218 if (err && err != -ENOSPC) 1219 return err; 1220 if (!err && IS_ALIGNED(rhs_offset, min_block_size)) 1221 return 0; 1222 if (!err) { 1223 /* Allocate the unaligned RHS offset using round_down */ 1224 gpu_buddy_free_list_internal(mm, blocks); 1225 err = __alloc_contig_aligned_retry(mm, rhs_offset, 1226 size, 1227 min_block_size, 1228 blocks); 1229 if (!err) 1230 return 0; 1231 if (err != -ENOSPC) { 1232 gpu_buddy_free_list_internal(mm, blocks); 1233 return err; 1234 } 1235 goto next; 1236 } 1237 1238 if (size - filled > rhs_offset) 1239 goto next; 1240 1241 lhs_offset = rhs_offset - (size - filled); 1242 1243 /* Allocate the unaligned LHS offset using round_down */ 1244 gpu_buddy_free_list_internal(mm, blocks); 1245 err = __alloc_contig_aligned_retry(mm, lhs_offset, size, 1246 min_block_size, blocks); 1247 if (!err) 1248 return 0; 1249 if (err != -ENOSPC) { 1250 gpu_buddy_free_list_internal(mm, blocks); 1251 return err; 1252 } 1253 next: 1254 gpu_buddy_free_list_internal(mm, blocks); 1255 iter = rb_prev(iter); 1256 } 1257 } 1258 1259 return -ENOSPC; 1260 } 1261 1262 /** 1263 * gpu_buddy_block_trim - free unused pages 1264 * 1265 * @mm: GPU buddy manager 1266 * @start: start address to begin the trimming. 1267 * @new_size: original size requested 1268 * @blocks: Input and output list of allocated blocks. 1269 * MUST contain single block as input to be trimmed. 1270 * On success will contain the newly allocated blocks 1271 * making up the @new_size. Blocks always appear in 1272 * ascending order 1273 * 1274 * For contiguous allocation, we round up the size to the nearest 1275 * power of two value, drivers consume *actual* size, so remaining 1276 * portions are unused and can be optionally freed with this function 1277 * 1278 * Returns: 1279 * 0 on success, error code on failure. 1280 */ 1281 int gpu_buddy_block_trim(struct gpu_buddy *mm, 1282 u64 *start, 1283 u64 new_size, 1284 struct list_head *blocks) 1285 { 1286 struct gpu_buddy_block *parent; 1287 struct gpu_buddy_block *block; 1288 u64 block_start, block_end; 1289 LIST_HEAD(dfs); 1290 u64 new_start; 1291 int err; 1292 1293 gpu_buddy_driver_lock_held(mm); 1294 1295 if (!list_is_singular(blocks)) 1296 return -EINVAL; 1297 1298 block = list_first_entry(blocks, 1299 struct gpu_buddy_block, 1300 link); 1301 1302 block_start = gpu_buddy_block_offset(block); 1303 block_end = block_start + gpu_buddy_block_size(mm, block); 1304 1305 if (WARN_ON(!gpu_buddy_block_is_allocated(block))) 1306 return -EINVAL; 1307 1308 if (new_size > gpu_buddy_block_size(mm, block)) 1309 return -EINVAL; 1310 1311 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) 1312 return -EINVAL; 1313 1314 if (new_size == gpu_buddy_block_size(mm, block)) 1315 return 0; 1316 1317 new_start = block_start; 1318 if (start) { 1319 new_start = *start; 1320 1321 if (new_start < block_start) 1322 return -EINVAL; 1323 1324 if (!IS_ALIGNED(new_start, mm->chunk_size)) 1325 return -EINVAL; 1326 1327 if (range_overflows(new_start, new_size, block_end)) 1328 return -EINVAL; 1329 } 1330 1331 list_del(&block->link); 1332 mark_free(mm, block); 1333 mm->avail += gpu_buddy_block_size(mm, block); 1334 if (gpu_buddy_block_is_clear(block)) 1335 mm->clear_avail += gpu_buddy_block_size(mm, block); 1336 1337 /* Prevent recursively freeing this node */ 1338 parent = block->parent; 1339 block->parent = NULL; 1340 1341 list_add(&block->tmp_link, &dfs); 1342 err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL); 1343 if (err) { 1344 mark_allocated(mm, block); 1345 mm->avail -= gpu_buddy_block_size(mm, block); 1346 if (gpu_buddy_block_is_clear(block)) 1347 mm->clear_avail -= gpu_buddy_block_size(mm, block); 1348 list_add(&block->link, blocks); 1349 } 1350 1351 block->parent = parent; 1352 return err; 1353 } 1354 EXPORT_SYMBOL(gpu_buddy_block_trim); 1355 1356 static struct gpu_buddy_block * 1357 __gpu_buddy_alloc_blocks(struct gpu_buddy *mm, 1358 u64 start, u64 end, 1359 u64 size, u64 min_block_size, 1360 unsigned int order, 1361 unsigned long flags) 1362 { 1363 if (flags & GPU_BUDDY_RANGE_ALLOCATION) 1364 /* Allocate traversing within the range */ 1365 return __gpu_buddy_alloc_range_bias(mm, start, end, 1366 order, flags); 1367 else if (size < min_block_size) 1368 /* Allocate from an offset-aligned region without size rounding */ 1369 return gpu_buddy_offset_aligned_allocation(mm, size, 1370 min_block_size, 1371 flags); 1372 else 1373 /* Allocate from freetree */ 1374 return alloc_from_freetree(mm, order, flags); 1375 } 1376 1377 /** 1378 * gpu_buddy_alloc_blocks - allocate power-of-two blocks 1379 * 1380 * @mm: GPU buddy manager to allocate from 1381 * @start: start of the allowed range for this block 1382 * @end: end of the allowed range for this block 1383 * @size: size of the allocation in bytes 1384 * @min_block_size: alignment of the allocation 1385 * @blocks: output list head to add allocated blocks 1386 * @flags: GPU_BUDDY_*_ALLOCATION flags 1387 * 1388 * alloc_range_bias() called on range limitations, which traverses 1389 * the tree and returns the desired block. 1390 * 1391 * alloc_from_freetree() called when *no* range restrictions 1392 * are enforced, which picks the block from the freetree. 1393 * 1394 * Returns: 1395 * 0 on success, error code on failure. 1396 */ 1397 int gpu_buddy_alloc_blocks(struct gpu_buddy *mm, 1398 u64 start, u64 end, u64 size, 1399 u64 min_block_size, 1400 struct list_head *blocks, 1401 unsigned long flags) 1402 { 1403 struct gpu_buddy_block *block = NULL; 1404 u64 original_size, original_min_size; 1405 unsigned int min_order, order; 1406 LIST_HEAD(allocated); 1407 unsigned long pages; 1408 int err; 1409 1410 gpu_buddy_driver_lock_held(mm); 1411 1412 if (size < mm->chunk_size) 1413 return -EINVAL; 1414 1415 if (min_block_size < mm->chunk_size) 1416 return -EINVAL; 1417 1418 if (!is_power_of_2(min_block_size)) 1419 return -EINVAL; 1420 1421 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) 1422 return -EINVAL; 1423 1424 if (end > mm->size) 1425 return -EINVAL; 1426 1427 if (range_overflows(start, size, mm->size)) 1428 return -EINVAL; 1429 1430 /* Actual range allocation */ 1431 if (start + size == end) { 1432 if (!IS_ALIGNED(start | end, min_block_size)) 1433 return -EINVAL; 1434 1435 return __gpu_buddy_alloc_range(mm, start, size, NULL, blocks); 1436 } 1437 1438 original_size = size; 1439 original_min_size = min_block_size; 1440 1441 /* Roundup the size to power of 2 */ 1442 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) { 1443 size = roundup_pow_of_two(size); 1444 min_block_size = size; 1445 /* 1446 * Normalize the requested size to min_block_size for regular allocations. 1447 * Offset-aligned allocations intentionally skip size rounding. 1448 */ 1449 } else if (!gpu_buddy_can_offset_align(size, min_block_size)) { 1450 size = round_up(size, min_block_size); 1451 } 1452 1453 pages = size >> ilog2(mm->chunk_size); 1454 order = fls(pages) - 1; 1455 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size); 1456 1457 if (order > mm->max_order || size > mm->size) { 1458 if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) && 1459 !(flags & GPU_BUDDY_RANGE_ALLOCATION)) 1460 return __alloc_contig_try_harder(mm, original_size, 1461 original_min_size, blocks); 1462 1463 return -EINVAL; 1464 } 1465 1466 do { 1467 order = min(order, (unsigned int)fls(pages) - 1); 1468 BUG_ON(order > mm->max_order); 1469 /* 1470 * Regular allocations must not allocate blocks smaller than min_block_size. 1471 * Offset-aligned allocations deliberately bypass this constraint. 1472 */ 1473 BUG_ON(size >= min_block_size && order < min_order); 1474 1475 do { 1476 unsigned int fallback_order; 1477 1478 block = __gpu_buddy_alloc_blocks(mm, start, 1479 end, 1480 size, 1481 min_block_size, 1482 order, 1483 flags); 1484 if (!IS_ERR(block)) 1485 break; 1486 1487 if (size < min_block_size) { 1488 fallback_order = order; 1489 } else if (order == min_order) { 1490 fallback_order = min_order; 1491 } else { 1492 order--; 1493 continue; 1494 } 1495 1496 /* Try allocation through force merge method */ 1497 if (mm->clear_avail && 1498 !__force_merge(mm, start, end, fallback_order)) { 1499 block = __gpu_buddy_alloc_blocks(mm, start, 1500 end, 1501 size, 1502 min_block_size, 1503 fallback_order, 1504 flags); 1505 if (!IS_ERR(block)) { 1506 order = fallback_order; 1507 break; 1508 } 1509 } 1510 1511 /* 1512 * Try contiguous block allocation through 1513 * try harder method. 1514 */ 1515 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION && 1516 !(flags & GPU_BUDDY_RANGE_ALLOCATION)) 1517 return __alloc_contig_try_harder(mm, 1518 original_size, 1519 original_min_size, 1520 blocks); 1521 err = -ENOSPC; 1522 goto err_free; 1523 } while (1); 1524 1525 mark_allocated(mm, block); 1526 mm->avail -= gpu_buddy_block_size(mm, block); 1527 if (gpu_buddy_block_is_clear(block)) 1528 mm->clear_avail -= gpu_buddy_block_size(mm, block); 1529 kmemleak_update_trace(block); 1530 list_add_tail(&block->link, &allocated); 1531 1532 pages -= BIT(order); 1533 1534 if (!pages) 1535 break; 1536 } while (1); 1537 1538 /* Trim the allocated block to the required size */ 1539 if (!(flags & GPU_BUDDY_TRIM_DISABLE) && 1540 original_size != size) { 1541 struct list_head *trim_list; 1542 LIST_HEAD(temp); 1543 u64 trim_size; 1544 1545 trim_list = &allocated; 1546 trim_size = original_size; 1547 1548 if (!list_is_singular(&allocated)) { 1549 block = list_last_entry(&allocated, typeof(*block), link); 1550 list_move(&block->link, &temp); 1551 trim_list = &temp; 1552 trim_size = gpu_buddy_block_size(mm, block) - 1553 (size - original_size); 1554 } 1555 1556 gpu_buddy_block_trim(mm, 1557 NULL, 1558 trim_size, 1559 trim_list); 1560 1561 if (!list_empty(&temp)) 1562 list_splice_tail(trim_list, &allocated); 1563 } 1564 1565 list_splice_tail(&allocated, blocks); 1566 return 0; 1567 1568 err_free: 1569 gpu_buddy_free_list_internal(mm, &allocated); 1570 return err; 1571 } 1572 EXPORT_SYMBOL(gpu_buddy_alloc_blocks); 1573 1574 /** 1575 * gpu_buddy_block_print - print block information 1576 * 1577 * @mm: GPU buddy manager 1578 * @block: GPU buddy block 1579 */ 1580 void gpu_buddy_block_print(struct gpu_buddy *mm, 1581 struct gpu_buddy_block *block) 1582 { 1583 u64 start = gpu_buddy_block_offset(block); 1584 u64 size = gpu_buddy_block_size(mm, block); 1585 1586 pr_info("%#018llx-%#018llx: %llu\n", start, start + size, size); 1587 } 1588 EXPORT_SYMBOL(gpu_buddy_block_print); 1589 1590 /** 1591 * gpu_buddy_print - print allocator state 1592 * 1593 * @mm: GPU buddy manager 1594 * @p: GPU printer to use 1595 */ 1596 void gpu_buddy_print(struct gpu_buddy *mm) 1597 { 1598 int order; 1599 1600 gpu_buddy_driver_lock_held(mm); 1601 pr_info("chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n", 1602 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20); 1603 1604 for (order = mm->max_order; order >= 0; order--) { 1605 u64 free_count = mm->free_scoreboard[order]; 1606 u64 used_count = mm->used_scoreboard[order]; 1607 u64 block_size = mm->chunk_size << order; 1608 u64 free = free_count * block_size; 1609 u64 used = used_count * block_size; 1610 1611 if (block_size < SZ_1M) 1612 pr_info("order-%2d free: %8llu KiB, used: %8llu KiB, free_blocks: %llu, used_blocks: %llu\n", 1613 order, free >> 10, used >> 10, free_count, used_count); 1614 else 1615 pr_info("order-%2d free: %8llu MiB, used: %8llu MiB, free_blocks: %llu, used_blocks: %llu\n", 1616 order, free >> 20, used >> 20, free_count, used_count); 1617 } 1618 } 1619 EXPORT_SYMBOL(gpu_buddy_print); 1620 1621 static void gpu_buddy_module_exit(void) 1622 { 1623 kmem_cache_destroy(slab_blocks); 1624 } 1625 1626 static int __init gpu_buddy_module_init(void) 1627 { 1628 slab_blocks = KMEM_CACHE(gpu_buddy_block, 0); 1629 if (!slab_blocks) 1630 return -ENOMEM; 1631 1632 return 0; 1633 } 1634 1635 module_init(gpu_buddy_module_init); 1636 module_exit(gpu_buddy_module_exit); 1637 1638 MODULE_DESCRIPTION("GPU Buddy Allocator"); 1639 MODULE_LICENSE("Dual MIT/GPL"); 1640