1 // SPDX-License-Identifier: MIT 2 /* 3 * Copyright © 2021 Intel Corporation 4 */ 5 6 #include <kunit/test-bug.h> 7 8 #include <linux/export.h> 9 #include <linux/kmemleak.h> 10 #include <linux/module.h> 11 #include <linux/sizes.h> 12 13 #include <drm/drm_buddy.h> 14 #include <drm/drm_print.h> 15 16 enum drm_buddy_free_tree { 17 DRM_BUDDY_CLEAR_TREE = 0, 18 DRM_BUDDY_DIRTY_TREE, 19 DRM_BUDDY_MAX_FREE_TREES, 20 }; 21 22 static struct kmem_cache *slab_blocks; 23 24 #define for_each_free_tree(tree) \ 25 for ((tree) = 0; (tree) < DRM_BUDDY_MAX_FREE_TREES; (tree)++) 26 27 static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm, 28 struct drm_buddy_block *parent, 29 unsigned int order, 30 u64 offset) 31 { 32 struct drm_buddy_block *block; 33 34 BUG_ON(order > DRM_BUDDY_MAX_ORDER); 35 36 block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); 37 if (!block) 38 return NULL; 39 40 block->header = offset; 41 block->header |= order; 42 block->parent = parent; 43 44 RB_CLEAR_NODE(&block->rb); 45 46 BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED); 47 return block; 48 } 49 50 static void drm_block_free(struct drm_buddy *mm, 51 struct drm_buddy_block *block) 52 { 53 kmem_cache_free(slab_blocks, block); 54 } 55 56 static enum drm_buddy_free_tree 57 get_block_tree(struct drm_buddy_block *block) 58 { 59 return drm_buddy_block_is_clear(block) ? 60 DRM_BUDDY_CLEAR_TREE : DRM_BUDDY_DIRTY_TREE; 61 } 62 63 static struct drm_buddy_block * 64 rbtree_get_free_block(const struct rb_node *node) 65 { 66 return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL; 67 } 68 69 static struct drm_buddy_block * 70 rbtree_last_free_block(struct rb_root *root) 71 { 72 return rbtree_get_free_block(rb_last(root)); 73 } 74 75 static bool rbtree_is_empty(struct rb_root *root) 76 { 77 return RB_EMPTY_ROOT(root); 78 } 79 80 static bool drm_buddy_block_offset_less(const struct drm_buddy_block *block, 81 const struct drm_buddy_block *node) 82 { 83 return drm_buddy_block_offset(block) < drm_buddy_block_offset(node); 84 } 85 86 static bool rbtree_block_offset_less(struct rb_node *block, 87 const struct rb_node *node) 88 { 89 return drm_buddy_block_offset_less(rbtree_get_free_block(block), 90 rbtree_get_free_block(node)); 91 } 92 93 static void rbtree_insert(struct drm_buddy *mm, 94 struct drm_buddy_block *block, 95 enum drm_buddy_free_tree tree) 96 { 97 rb_add(&block->rb, 98 &mm->free_trees[tree][drm_buddy_block_order(block)], 99 rbtree_block_offset_less); 100 } 101 102 static void rbtree_remove(struct drm_buddy *mm, 103 struct drm_buddy_block *block) 104 { 105 unsigned int order = drm_buddy_block_order(block); 106 enum drm_buddy_free_tree tree; 107 struct rb_root *root; 108 109 tree = get_block_tree(block); 110 root = &mm->free_trees[tree][order]; 111 112 rb_erase(&block->rb, root); 113 RB_CLEAR_NODE(&block->rb); 114 } 115 116 static void clear_reset(struct drm_buddy_block *block) 117 { 118 block->header &= ~DRM_BUDDY_HEADER_CLEAR; 119 } 120 121 static void mark_cleared(struct drm_buddy_block *block) 122 { 123 block->header |= DRM_BUDDY_HEADER_CLEAR; 124 } 125 126 static void mark_allocated(struct drm_buddy *mm, 127 struct drm_buddy_block *block) 128 { 129 block->header &= ~DRM_BUDDY_HEADER_STATE; 130 block->header |= DRM_BUDDY_ALLOCATED; 131 132 rbtree_remove(mm, block); 133 } 134 135 static void mark_free(struct drm_buddy *mm, 136 struct drm_buddy_block *block) 137 { 138 enum drm_buddy_free_tree tree; 139 140 block->header &= ~DRM_BUDDY_HEADER_STATE; 141 block->header |= DRM_BUDDY_FREE; 142 143 tree = get_block_tree(block); 144 rbtree_insert(mm, block, tree); 145 } 146 147 static void mark_split(struct drm_buddy *mm, 148 struct drm_buddy_block *block) 149 { 150 block->header &= ~DRM_BUDDY_HEADER_STATE; 151 block->header |= DRM_BUDDY_SPLIT; 152 153 rbtree_remove(mm, block); 154 } 155 156 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) 157 { 158 return s1 <= e2 && e1 >= s2; 159 } 160 161 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) 162 { 163 return s1 <= s2 && e1 >= e2; 164 } 165 166 static struct drm_buddy_block * 167 __get_buddy(struct drm_buddy_block *block) 168 { 169 struct drm_buddy_block *parent; 170 171 parent = block->parent; 172 if (!parent) 173 return NULL; 174 175 if (parent->left == block) 176 return parent->right; 177 178 return parent->left; 179 } 180 181 static unsigned int __drm_buddy_free(struct drm_buddy *mm, 182 struct drm_buddy_block *block, 183 bool force_merge) 184 { 185 struct drm_buddy_block *parent; 186 unsigned int order; 187 188 while ((parent = block->parent)) { 189 struct drm_buddy_block *buddy; 190 191 buddy = __get_buddy(block); 192 193 if (!drm_buddy_block_is_free(buddy)) 194 break; 195 196 if (!force_merge) { 197 /* 198 * Check the block and its buddy clear state and exit 199 * the loop if they both have the dissimilar state. 200 */ 201 if (drm_buddy_block_is_clear(block) != 202 drm_buddy_block_is_clear(buddy)) 203 break; 204 205 if (drm_buddy_block_is_clear(block)) 206 mark_cleared(parent); 207 } 208 209 rbtree_remove(mm, buddy); 210 if (force_merge && drm_buddy_block_is_clear(buddy)) 211 mm->clear_avail -= drm_buddy_block_size(mm, buddy); 212 213 drm_block_free(mm, block); 214 drm_block_free(mm, buddy); 215 216 block = parent; 217 } 218 219 order = drm_buddy_block_order(block); 220 mark_free(mm, block); 221 222 return order; 223 } 224 225 static int __force_merge(struct drm_buddy *mm, 226 u64 start, 227 u64 end, 228 unsigned int min_order) 229 { 230 unsigned int tree, order; 231 int i; 232 233 if (!min_order) 234 return -ENOMEM; 235 236 if (min_order > mm->max_order) 237 return -EINVAL; 238 239 for_each_free_tree(tree) { 240 for (i = min_order - 1; i >= 0; i--) { 241 struct rb_node *iter = rb_last(&mm->free_trees[tree][i]); 242 243 while (iter) { 244 struct drm_buddy_block *block, *buddy; 245 u64 block_start, block_end; 246 247 block = rbtree_get_free_block(iter); 248 iter = rb_prev(iter); 249 250 if (!block || !block->parent) 251 continue; 252 253 block_start = drm_buddy_block_offset(block); 254 block_end = block_start + drm_buddy_block_size(mm, block) - 1; 255 256 if (!contains(start, end, block_start, block_end)) 257 continue; 258 259 buddy = __get_buddy(block); 260 if (!drm_buddy_block_is_free(buddy)) 261 continue; 262 263 WARN_ON(drm_buddy_block_is_clear(block) == 264 drm_buddy_block_is_clear(buddy)); 265 266 /* 267 * Advance to the next node when the current node is the buddy, 268 * as freeing the block will also remove its buddy from the tree. 269 */ 270 if (iter == &buddy->rb) 271 iter = rb_prev(iter); 272 273 rbtree_remove(mm, block); 274 if (drm_buddy_block_is_clear(block)) 275 mm->clear_avail -= drm_buddy_block_size(mm, block); 276 277 order = __drm_buddy_free(mm, block, true); 278 if (order >= min_order) 279 return 0; 280 } 281 } 282 } 283 284 return -ENOMEM; 285 } 286 287 /** 288 * drm_buddy_init - init memory manager 289 * 290 * @mm: DRM buddy manager to initialize 291 * @size: size in bytes to manage 292 * @chunk_size: minimum page size in bytes for our allocations 293 * 294 * Initializes the memory manager and its resources. 295 * 296 * Returns: 297 * 0 on success, error code on failure. 298 */ 299 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size) 300 { 301 unsigned int i, j, root_count = 0; 302 u64 offset = 0; 303 304 if (size < chunk_size) 305 return -EINVAL; 306 307 if (chunk_size < SZ_4K) 308 return -EINVAL; 309 310 if (!is_power_of_2(chunk_size)) 311 return -EINVAL; 312 313 size = round_down(size, chunk_size); 314 315 mm->size = size; 316 mm->avail = size; 317 mm->clear_avail = 0; 318 mm->chunk_size = chunk_size; 319 mm->max_order = ilog2(size) - ilog2(chunk_size); 320 321 BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER); 322 323 mm->free_trees = kmalloc_objs(*mm->free_trees, DRM_BUDDY_MAX_FREE_TREES, 324 GFP_KERNEL); 325 if (!mm->free_trees) 326 return -ENOMEM; 327 328 for_each_free_tree(i) { 329 mm->free_trees[i] = kmalloc_objs(struct rb_root, 330 mm->max_order + 1, GFP_KERNEL); 331 if (!mm->free_trees[i]) 332 goto out_free_tree; 333 334 for (j = 0; j <= mm->max_order; ++j) 335 mm->free_trees[i][j] = RB_ROOT; 336 } 337 338 mm->n_roots = hweight64(size); 339 340 mm->roots = kmalloc_objs(struct drm_buddy_block *, mm->n_roots, 341 GFP_KERNEL); 342 if (!mm->roots) 343 goto out_free_tree; 344 345 /* 346 * Split into power-of-two blocks, in case we are given a size that is 347 * not itself a power-of-two. 348 */ 349 do { 350 struct drm_buddy_block *root; 351 unsigned int order; 352 u64 root_size; 353 354 order = ilog2(size) - ilog2(chunk_size); 355 root_size = chunk_size << order; 356 357 root = drm_block_alloc(mm, NULL, order, offset); 358 if (!root) 359 goto out_free_roots; 360 361 mark_free(mm, root); 362 363 BUG_ON(root_count > mm->max_order); 364 BUG_ON(drm_buddy_block_size(mm, root) < chunk_size); 365 366 mm->roots[root_count] = root; 367 368 offset += root_size; 369 size -= root_size; 370 root_count++; 371 } while (size); 372 373 return 0; 374 375 out_free_roots: 376 while (root_count--) 377 drm_block_free(mm, mm->roots[root_count]); 378 kfree(mm->roots); 379 out_free_tree: 380 while (i--) 381 kfree(mm->free_trees[i]); 382 kfree(mm->free_trees); 383 return -ENOMEM; 384 } 385 EXPORT_SYMBOL(drm_buddy_init); 386 387 /** 388 * drm_buddy_fini - tear down the memory manager 389 * 390 * @mm: DRM buddy manager to free 391 * 392 * Cleanup memory manager resources and the freetree 393 */ 394 void drm_buddy_fini(struct drm_buddy *mm) 395 { 396 u64 root_size, size, start; 397 unsigned int order; 398 int i; 399 400 size = mm->size; 401 402 for (i = 0; i < mm->n_roots; ++i) { 403 order = ilog2(size) - ilog2(mm->chunk_size); 404 start = drm_buddy_block_offset(mm->roots[i]); 405 __force_merge(mm, start, start + size, order); 406 407 if (WARN_ON(!drm_buddy_block_is_free(mm->roots[i]))) 408 kunit_fail_current_test("buddy_fini() root"); 409 410 drm_block_free(mm, mm->roots[i]); 411 412 root_size = mm->chunk_size << order; 413 size -= root_size; 414 } 415 416 WARN_ON(mm->avail != mm->size); 417 418 for_each_free_tree(i) 419 kfree(mm->free_trees[i]); 420 kfree(mm->free_trees); 421 kfree(mm->roots); 422 } 423 EXPORT_SYMBOL(drm_buddy_fini); 424 425 static int split_block(struct drm_buddy *mm, 426 struct drm_buddy_block *block) 427 { 428 unsigned int block_order = drm_buddy_block_order(block) - 1; 429 u64 offset = drm_buddy_block_offset(block); 430 431 BUG_ON(!drm_buddy_block_is_free(block)); 432 BUG_ON(!drm_buddy_block_order(block)); 433 434 block->left = drm_block_alloc(mm, block, block_order, offset); 435 if (!block->left) 436 return -ENOMEM; 437 438 block->right = drm_block_alloc(mm, block, block_order, 439 offset + (mm->chunk_size << block_order)); 440 if (!block->right) { 441 drm_block_free(mm, block->left); 442 return -ENOMEM; 443 } 444 445 mark_split(mm, block); 446 447 if (drm_buddy_block_is_clear(block)) { 448 mark_cleared(block->left); 449 mark_cleared(block->right); 450 clear_reset(block); 451 } 452 453 mark_free(mm, block->left); 454 mark_free(mm, block->right); 455 456 return 0; 457 } 458 459 /** 460 * drm_get_buddy - get buddy address 461 * 462 * @block: DRM buddy block 463 * 464 * Returns the corresponding buddy block for @block, or NULL 465 * if this is a root block and can't be merged further. 466 * Requires some kind of locking to protect against 467 * any concurrent allocate and free operations. 468 */ 469 struct drm_buddy_block * 470 drm_get_buddy(struct drm_buddy_block *block) 471 { 472 return __get_buddy(block); 473 } 474 EXPORT_SYMBOL(drm_get_buddy); 475 476 /** 477 * drm_buddy_reset_clear - reset blocks clear state 478 * 479 * @mm: DRM buddy manager 480 * @is_clear: blocks clear state 481 * 482 * Reset the clear state based on @is_clear value for each block 483 * in the freetree. 484 */ 485 void drm_buddy_reset_clear(struct drm_buddy *mm, bool is_clear) 486 { 487 enum drm_buddy_free_tree src_tree, dst_tree; 488 u64 root_size, size, start; 489 unsigned int order; 490 int i; 491 492 size = mm->size; 493 for (i = 0; i < mm->n_roots; ++i) { 494 order = ilog2(size) - ilog2(mm->chunk_size); 495 start = drm_buddy_block_offset(mm->roots[i]); 496 __force_merge(mm, start, start + size, order); 497 498 root_size = mm->chunk_size << order; 499 size -= root_size; 500 } 501 502 src_tree = is_clear ? DRM_BUDDY_DIRTY_TREE : DRM_BUDDY_CLEAR_TREE; 503 dst_tree = is_clear ? DRM_BUDDY_CLEAR_TREE : DRM_BUDDY_DIRTY_TREE; 504 505 for (i = 0; i <= mm->max_order; ++i) { 506 struct rb_root *root = &mm->free_trees[src_tree][i]; 507 struct drm_buddy_block *block, *tmp; 508 509 rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) { 510 rbtree_remove(mm, block); 511 if (is_clear) { 512 mark_cleared(block); 513 mm->clear_avail += drm_buddy_block_size(mm, block); 514 } else { 515 clear_reset(block); 516 mm->clear_avail -= drm_buddy_block_size(mm, block); 517 } 518 519 rbtree_insert(mm, block, dst_tree); 520 } 521 } 522 } 523 EXPORT_SYMBOL(drm_buddy_reset_clear); 524 525 /** 526 * drm_buddy_free_block - free a block 527 * 528 * @mm: DRM buddy manager 529 * @block: block to be freed 530 */ 531 void drm_buddy_free_block(struct drm_buddy *mm, 532 struct drm_buddy_block *block) 533 { 534 BUG_ON(!drm_buddy_block_is_allocated(block)); 535 mm->avail += drm_buddy_block_size(mm, block); 536 if (drm_buddy_block_is_clear(block)) 537 mm->clear_avail += drm_buddy_block_size(mm, block); 538 539 __drm_buddy_free(mm, block, false); 540 } 541 EXPORT_SYMBOL(drm_buddy_free_block); 542 543 static void __drm_buddy_free_list(struct drm_buddy *mm, 544 struct list_head *objects, 545 bool mark_clear, 546 bool mark_dirty) 547 { 548 struct drm_buddy_block *block, *on; 549 550 WARN_ON(mark_dirty && mark_clear); 551 552 list_for_each_entry_safe(block, on, objects, link) { 553 if (mark_clear) 554 mark_cleared(block); 555 else if (mark_dirty) 556 clear_reset(block); 557 drm_buddy_free_block(mm, block); 558 cond_resched(); 559 } 560 INIT_LIST_HEAD(objects); 561 } 562 563 static void drm_buddy_free_list_internal(struct drm_buddy *mm, 564 struct list_head *objects) 565 { 566 /* 567 * Don't touch the clear/dirty bit, since allocation is still internal 568 * at this point. For example we might have just failed part of the 569 * allocation. 570 */ 571 __drm_buddy_free_list(mm, objects, false, false); 572 } 573 574 /** 575 * drm_buddy_free_list - free blocks 576 * 577 * @mm: DRM buddy manager 578 * @objects: input list head to free blocks 579 * @flags: optional flags like DRM_BUDDY_CLEARED 580 */ 581 void drm_buddy_free_list(struct drm_buddy *mm, 582 struct list_head *objects, 583 unsigned int flags) 584 { 585 bool mark_clear = flags & DRM_BUDDY_CLEARED; 586 587 __drm_buddy_free_list(mm, objects, mark_clear, !mark_clear); 588 } 589 EXPORT_SYMBOL(drm_buddy_free_list); 590 591 static bool block_incompatible(struct drm_buddy_block *block, unsigned int flags) 592 { 593 bool needs_clear = flags & DRM_BUDDY_CLEAR_ALLOCATION; 594 595 return needs_clear != drm_buddy_block_is_clear(block); 596 } 597 598 static struct drm_buddy_block * 599 __alloc_range_bias(struct drm_buddy *mm, 600 u64 start, u64 end, 601 unsigned int order, 602 unsigned long flags, 603 bool fallback) 604 { 605 u64 req_size = mm->chunk_size << order; 606 struct drm_buddy_block *block; 607 struct drm_buddy_block *buddy; 608 LIST_HEAD(dfs); 609 int err; 610 int i; 611 612 end = end - 1; 613 614 for (i = 0; i < mm->n_roots; ++i) 615 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 616 617 do { 618 u64 block_start; 619 u64 block_end; 620 621 block = list_first_entry_or_null(&dfs, 622 struct drm_buddy_block, 623 tmp_link); 624 if (!block) 625 break; 626 627 list_del(&block->tmp_link); 628 629 if (drm_buddy_block_order(block) < order) 630 continue; 631 632 block_start = drm_buddy_block_offset(block); 633 block_end = block_start + drm_buddy_block_size(mm, block) - 1; 634 635 if (!overlaps(start, end, block_start, block_end)) 636 continue; 637 638 if (drm_buddy_block_is_allocated(block)) 639 continue; 640 641 if (block_start < start || block_end > end) { 642 u64 adjusted_start = max(block_start, start); 643 u64 adjusted_end = min(block_end, end); 644 645 if (round_down(adjusted_end + 1, req_size) <= 646 round_up(adjusted_start, req_size)) 647 continue; 648 } 649 650 if (!fallback && block_incompatible(block, flags)) 651 continue; 652 653 if (contains(start, end, block_start, block_end) && 654 order == drm_buddy_block_order(block)) { 655 /* 656 * Find the free block within the range. 657 */ 658 if (drm_buddy_block_is_free(block)) 659 return block; 660 661 continue; 662 } 663 664 if (!drm_buddy_block_is_split(block)) { 665 err = split_block(mm, block); 666 if (unlikely(err)) 667 goto err_undo; 668 } 669 670 list_add(&block->right->tmp_link, &dfs); 671 list_add(&block->left->tmp_link, &dfs); 672 } while (1); 673 674 return ERR_PTR(-ENOSPC); 675 676 err_undo: 677 /* 678 * We really don't want to leave around a bunch of split blocks, since 679 * bigger is better, so make sure we merge everything back before we 680 * free the allocated blocks. 681 */ 682 buddy = __get_buddy(block); 683 if (buddy && 684 (drm_buddy_block_is_free(block) && 685 drm_buddy_block_is_free(buddy))) 686 __drm_buddy_free(mm, block, false); 687 return ERR_PTR(err); 688 } 689 690 static struct drm_buddy_block * 691 __drm_buddy_alloc_range_bias(struct drm_buddy *mm, 692 u64 start, u64 end, 693 unsigned int order, 694 unsigned long flags) 695 { 696 struct drm_buddy_block *block; 697 bool fallback = false; 698 699 block = __alloc_range_bias(mm, start, end, order, 700 flags, fallback); 701 if (IS_ERR(block)) 702 return __alloc_range_bias(mm, start, end, order, 703 flags, !fallback); 704 705 return block; 706 } 707 708 static struct drm_buddy_block * 709 get_maxblock(struct drm_buddy *mm, 710 unsigned int order, 711 enum drm_buddy_free_tree tree) 712 { 713 struct drm_buddy_block *max_block = NULL, *block = NULL; 714 struct rb_root *root; 715 unsigned int i; 716 717 for (i = order; i <= mm->max_order; ++i) { 718 root = &mm->free_trees[tree][i]; 719 block = rbtree_last_free_block(root); 720 if (!block) 721 continue; 722 723 if (!max_block) { 724 max_block = block; 725 continue; 726 } 727 728 if (drm_buddy_block_offset(block) > 729 drm_buddy_block_offset(max_block)) { 730 max_block = block; 731 } 732 } 733 734 return max_block; 735 } 736 737 static struct drm_buddy_block * 738 alloc_from_freetree(struct drm_buddy *mm, 739 unsigned int order, 740 unsigned long flags) 741 { 742 struct drm_buddy_block *block = NULL; 743 struct rb_root *root; 744 enum drm_buddy_free_tree tree; 745 unsigned int tmp; 746 int err; 747 748 tree = (flags & DRM_BUDDY_CLEAR_ALLOCATION) ? 749 DRM_BUDDY_CLEAR_TREE : DRM_BUDDY_DIRTY_TREE; 750 751 if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) { 752 block = get_maxblock(mm, order, tree); 753 if (block) 754 /* Store the obtained block order */ 755 tmp = drm_buddy_block_order(block); 756 } else { 757 for (tmp = order; tmp <= mm->max_order; ++tmp) { 758 /* Get RB tree root for this order and tree */ 759 root = &mm->free_trees[tree][tmp]; 760 block = rbtree_last_free_block(root); 761 if (block) 762 break; 763 } 764 } 765 766 if (!block) { 767 /* Try allocating from the other tree */ 768 tree = (tree == DRM_BUDDY_CLEAR_TREE) ? 769 DRM_BUDDY_DIRTY_TREE : DRM_BUDDY_CLEAR_TREE; 770 771 for (tmp = order; tmp <= mm->max_order; ++tmp) { 772 root = &mm->free_trees[tree][tmp]; 773 block = rbtree_last_free_block(root); 774 if (block) 775 break; 776 } 777 778 if (!block) 779 return ERR_PTR(-ENOSPC); 780 } 781 782 BUG_ON(!drm_buddy_block_is_free(block)); 783 784 while (tmp != order) { 785 err = split_block(mm, block); 786 if (unlikely(err)) 787 goto err_undo; 788 789 block = block->right; 790 tmp--; 791 } 792 return block; 793 794 err_undo: 795 if (tmp != order) 796 __drm_buddy_free(mm, block, false); 797 return ERR_PTR(err); 798 } 799 800 static int __alloc_range(struct drm_buddy *mm, 801 struct list_head *dfs, 802 u64 start, u64 size, 803 struct list_head *blocks, 804 u64 *total_allocated_on_err) 805 { 806 struct drm_buddy_block *block; 807 struct drm_buddy_block *buddy; 808 u64 total_allocated = 0; 809 LIST_HEAD(allocated); 810 u64 end; 811 int err; 812 813 end = start + size - 1; 814 815 do { 816 u64 block_start; 817 u64 block_end; 818 819 block = list_first_entry_or_null(dfs, 820 struct drm_buddy_block, 821 tmp_link); 822 if (!block) 823 break; 824 825 list_del(&block->tmp_link); 826 827 block_start = drm_buddy_block_offset(block); 828 block_end = block_start + drm_buddy_block_size(mm, block) - 1; 829 830 if (!overlaps(start, end, block_start, block_end)) 831 continue; 832 833 if (drm_buddy_block_is_allocated(block)) { 834 err = -ENOSPC; 835 goto err_free; 836 } 837 838 if (contains(start, end, block_start, block_end)) { 839 if (drm_buddy_block_is_free(block)) { 840 mark_allocated(mm, block); 841 total_allocated += drm_buddy_block_size(mm, block); 842 mm->avail -= drm_buddy_block_size(mm, block); 843 if (drm_buddy_block_is_clear(block)) 844 mm->clear_avail -= drm_buddy_block_size(mm, block); 845 list_add_tail(&block->link, &allocated); 846 continue; 847 } else if (!mm->clear_avail) { 848 err = -ENOSPC; 849 goto err_free; 850 } 851 } 852 853 if (!drm_buddy_block_is_split(block)) { 854 err = split_block(mm, block); 855 if (unlikely(err)) 856 goto err_undo; 857 } 858 859 list_add(&block->right->tmp_link, dfs); 860 list_add(&block->left->tmp_link, dfs); 861 } while (1); 862 863 if (total_allocated < size) { 864 err = -ENOSPC; 865 goto err_free; 866 } 867 868 list_splice_tail(&allocated, blocks); 869 870 return 0; 871 872 err_undo: 873 /* 874 * We really don't want to leave around a bunch of split blocks, since 875 * bigger is better, so make sure we merge everything back before we 876 * free the allocated blocks. 877 */ 878 buddy = __get_buddy(block); 879 if (buddy && 880 (drm_buddy_block_is_free(block) && 881 drm_buddy_block_is_free(buddy))) 882 __drm_buddy_free(mm, block, false); 883 884 err_free: 885 if (err == -ENOSPC && total_allocated_on_err) { 886 list_splice_tail(&allocated, blocks); 887 *total_allocated_on_err = total_allocated; 888 } else { 889 drm_buddy_free_list_internal(mm, &allocated); 890 } 891 892 return err; 893 } 894 895 static int __drm_buddy_alloc_range(struct drm_buddy *mm, 896 u64 start, 897 u64 size, 898 u64 *total_allocated_on_err, 899 struct list_head *blocks) 900 { 901 LIST_HEAD(dfs); 902 int i; 903 904 for (i = 0; i < mm->n_roots; ++i) 905 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 906 907 return __alloc_range(mm, &dfs, start, size, 908 blocks, total_allocated_on_err); 909 } 910 911 static int __alloc_contig_try_harder(struct drm_buddy *mm, 912 u64 size, 913 u64 min_block_size, 914 struct list_head *blocks) 915 { 916 u64 rhs_offset, lhs_offset, lhs_size, filled; 917 struct drm_buddy_block *block; 918 unsigned int tree, order; 919 LIST_HEAD(blocks_lhs); 920 unsigned long pages; 921 u64 modify_size; 922 int err; 923 924 modify_size = rounddown_pow_of_two(size); 925 pages = modify_size >> ilog2(mm->chunk_size); 926 order = fls(pages) - 1; 927 if (order == 0) 928 return -ENOSPC; 929 930 for_each_free_tree(tree) { 931 struct rb_root *root; 932 struct rb_node *iter; 933 934 root = &mm->free_trees[tree][order]; 935 if (rbtree_is_empty(root)) 936 continue; 937 938 iter = rb_last(root); 939 while (iter) { 940 block = rbtree_get_free_block(iter); 941 942 /* Allocate blocks traversing RHS */ 943 rhs_offset = drm_buddy_block_offset(block); 944 err = __drm_buddy_alloc_range(mm, rhs_offset, size, 945 &filled, blocks); 946 if (!err || err != -ENOSPC) 947 return err; 948 949 lhs_size = max((size - filled), min_block_size); 950 if (!IS_ALIGNED(lhs_size, min_block_size)) 951 lhs_size = round_up(lhs_size, min_block_size); 952 953 /* Allocate blocks traversing LHS */ 954 lhs_offset = drm_buddy_block_offset(block) - lhs_size; 955 err = __drm_buddy_alloc_range(mm, lhs_offset, lhs_size, 956 NULL, &blocks_lhs); 957 if (!err) { 958 list_splice(&blocks_lhs, blocks); 959 return 0; 960 } else if (err != -ENOSPC) { 961 drm_buddy_free_list_internal(mm, blocks); 962 return err; 963 } 964 /* Free blocks for the next iteration */ 965 drm_buddy_free_list_internal(mm, blocks); 966 967 iter = rb_prev(iter); 968 } 969 } 970 971 return -ENOSPC; 972 } 973 974 /** 975 * drm_buddy_block_trim - free unused pages 976 * 977 * @mm: DRM buddy manager 978 * @start: start address to begin the trimming. 979 * @new_size: original size requested 980 * @blocks: Input and output list of allocated blocks. 981 * MUST contain single block as input to be trimmed. 982 * On success will contain the newly allocated blocks 983 * making up the @new_size. Blocks always appear in 984 * ascending order 985 * 986 * For contiguous allocation, we round up the size to the nearest 987 * power of two value, drivers consume *actual* size, so remaining 988 * portions are unused and can be optionally freed with this function 989 * 990 * Returns: 991 * 0 on success, error code on failure. 992 */ 993 int drm_buddy_block_trim(struct drm_buddy *mm, 994 u64 *start, 995 u64 new_size, 996 struct list_head *blocks) 997 { 998 struct drm_buddy_block *parent; 999 struct drm_buddy_block *block; 1000 u64 block_start, block_end; 1001 LIST_HEAD(dfs); 1002 u64 new_start; 1003 int err; 1004 1005 if (!list_is_singular(blocks)) 1006 return -EINVAL; 1007 1008 block = list_first_entry(blocks, 1009 struct drm_buddy_block, 1010 link); 1011 1012 block_start = drm_buddy_block_offset(block); 1013 block_end = block_start + drm_buddy_block_size(mm, block); 1014 1015 if (WARN_ON(!drm_buddy_block_is_allocated(block))) 1016 return -EINVAL; 1017 1018 if (new_size > drm_buddy_block_size(mm, block)) 1019 return -EINVAL; 1020 1021 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) 1022 return -EINVAL; 1023 1024 if (new_size == drm_buddy_block_size(mm, block)) 1025 return 0; 1026 1027 new_start = block_start; 1028 if (start) { 1029 new_start = *start; 1030 1031 if (new_start < block_start) 1032 return -EINVAL; 1033 1034 if (!IS_ALIGNED(new_start, mm->chunk_size)) 1035 return -EINVAL; 1036 1037 if (range_overflows(new_start, new_size, block_end)) 1038 return -EINVAL; 1039 } 1040 1041 list_del(&block->link); 1042 mark_free(mm, block); 1043 mm->avail += drm_buddy_block_size(mm, block); 1044 if (drm_buddy_block_is_clear(block)) 1045 mm->clear_avail += drm_buddy_block_size(mm, block); 1046 1047 /* Prevent recursively freeing this node */ 1048 parent = block->parent; 1049 block->parent = NULL; 1050 1051 list_add(&block->tmp_link, &dfs); 1052 err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL); 1053 if (err) { 1054 mark_allocated(mm, block); 1055 mm->avail -= drm_buddy_block_size(mm, block); 1056 if (drm_buddy_block_is_clear(block)) 1057 mm->clear_avail -= drm_buddy_block_size(mm, block); 1058 list_add(&block->link, blocks); 1059 } 1060 1061 block->parent = parent; 1062 return err; 1063 } 1064 EXPORT_SYMBOL(drm_buddy_block_trim); 1065 1066 static struct drm_buddy_block * 1067 __drm_buddy_alloc_blocks(struct drm_buddy *mm, 1068 u64 start, u64 end, 1069 unsigned int order, 1070 unsigned long flags) 1071 { 1072 if (flags & DRM_BUDDY_RANGE_ALLOCATION) 1073 /* Allocate traversing within the range */ 1074 return __drm_buddy_alloc_range_bias(mm, start, end, 1075 order, flags); 1076 else 1077 /* Allocate from freetree */ 1078 return alloc_from_freetree(mm, order, flags); 1079 } 1080 1081 /** 1082 * drm_buddy_alloc_blocks - allocate power-of-two blocks 1083 * 1084 * @mm: DRM buddy manager to allocate from 1085 * @start: start of the allowed range for this block 1086 * @end: end of the allowed range for this block 1087 * @size: size of the allocation in bytes 1088 * @min_block_size: alignment of the allocation 1089 * @blocks: output list head to add allocated blocks 1090 * @flags: DRM_BUDDY_*_ALLOCATION flags 1091 * 1092 * alloc_range_bias() called on range limitations, which traverses 1093 * the tree and returns the desired block. 1094 * 1095 * alloc_from_freetree() called when *no* range restrictions 1096 * are enforced, which picks the block from the freetree. 1097 * 1098 * Returns: 1099 * 0 on success, error code on failure. 1100 */ 1101 int drm_buddy_alloc_blocks(struct drm_buddy *mm, 1102 u64 start, u64 end, u64 size, 1103 u64 min_block_size, 1104 struct list_head *blocks, 1105 unsigned long flags) 1106 { 1107 struct drm_buddy_block *block = NULL; 1108 u64 original_size, original_min_size; 1109 unsigned int min_order, order; 1110 LIST_HEAD(allocated); 1111 unsigned long pages; 1112 int err; 1113 1114 if (size < mm->chunk_size) 1115 return -EINVAL; 1116 1117 if (min_block_size < mm->chunk_size) 1118 return -EINVAL; 1119 1120 if (!is_power_of_2(min_block_size)) 1121 return -EINVAL; 1122 1123 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) 1124 return -EINVAL; 1125 1126 if (end > mm->size) 1127 return -EINVAL; 1128 1129 if (range_overflows(start, size, mm->size)) 1130 return -EINVAL; 1131 1132 /* Actual range allocation */ 1133 if (start + size == end) { 1134 if (!IS_ALIGNED(start | end, min_block_size)) 1135 return -EINVAL; 1136 1137 return __drm_buddy_alloc_range(mm, start, size, NULL, blocks); 1138 } 1139 1140 original_size = size; 1141 original_min_size = min_block_size; 1142 1143 /* Roundup the size to power of 2 */ 1144 if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION) { 1145 size = roundup_pow_of_two(size); 1146 min_block_size = size; 1147 /* Align size value to min_block_size */ 1148 } else if (!IS_ALIGNED(size, min_block_size)) { 1149 size = round_up(size, min_block_size); 1150 } 1151 1152 pages = size >> ilog2(mm->chunk_size); 1153 order = fls(pages) - 1; 1154 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size); 1155 1156 if (order > mm->max_order || size > mm->size) { 1157 if ((flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION) && 1158 !(flags & DRM_BUDDY_RANGE_ALLOCATION)) 1159 return __alloc_contig_try_harder(mm, original_size, 1160 original_min_size, blocks); 1161 1162 return -EINVAL; 1163 } 1164 1165 do { 1166 order = min(order, (unsigned int)fls(pages) - 1); 1167 BUG_ON(order > mm->max_order); 1168 BUG_ON(order < min_order); 1169 1170 do { 1171 block = __drm_buddy_alloc_blocks(mm, start, 1172 end, 1173 order, 1174 flags); 1175 if (!IS_ERR(block)) 1176 break; 1177 1178 if (order-- == min_order) { 1179 /* Try allocation through force merge method */ 1180 if (mm->clear_avail && 1181 !__force_merge(mm, start, end, min_order)) { 1182 block = __drm_buddy_alloc_blocks(mm, start, 1183 end, 1184 min_order, 1185 flags); 1186 if (!IS_ERR(block)) { 1187 order = min_order; 1188 break; 1189 } 1190 } 1191 1192 /* 1193 * Try contiguous block allocation through 1194 * try harder method. 1195 */ 1196 if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION && 1197 !(flags & DRM_BUDDY_RANGE_ALLOCATION)) 1198 return __alloc_contig_try_harder(mm, 1199 original_size, 1200 original_min_size, 1201 blocks); 1202 err = -ENOSPC; 1203 goto err_free; 1204 } 1205 } while (1); 1206 1207 mark_allocated(mm, block); 1208 mm->avail -= drm_buddy_block_size(mm, block); 1209 if (drm_buddy_block_is_clear(block)) 1210 mm->clear_avail -= drm_buddy_block_size(mm, block); 1211 kmemleak_update_trace(block); 1212 list_add_tail(&block->link, &allocated); 1213 1214 pages -= BIT(order); 1215 1216 if (!pages) 1217 break; 1218 } while (1); 1219 1220 /* Trim the allocated block to the required size */ 1221 if (!(flags & DRM_BUDDY_TRIM_DISABLE) && 1222 original_size != size) { 1223 struct list_head *trim_list; 1224 LIST_HEAD(temp); 1225 u64 trim_size; 1226 1227 trim_list = &allocated; 1228 trim_size = original_size; 1229 1230 if (!list_is_singular(&allocated)) { 1231 block = list_last_entry(&allocated, typeof(*block), link); 1232 list_move(&block->link, &temp); 1233 trim_list = &temp; 1234 trim_size = drm_buddy_block_size(mm, block) - 1235 (size - original_size); 1236 } 1237 1238 drm_buddy_block_trim(mm, 1239 NULL, 1240 trim_size, 1241 trim_list); 1242 1243 if (!list_empty(&temp)) 1244 list_splice_tail(trim_list, &allocated); 1245 } 1246 1247 list_splice_tail(&allocated, blocks); 1248 return 0; 1249 1250 err_free: 1251 drm_buddy_free_list_internal(mm, &allocated); 1252 return err; 1253 } 1254 EXPORT_SYMBOL(drm_buddy_alloc_blocks); 1255 1256 /** 1257 * drm_buddy_block_print - print block information 1258 * 1259 * @mm: DRM buddy manager 1260 * @block: DRM buddy block 1261 * @p: DRM printer to use 1262 */ 1263 void drm_buddy_block_print(struct drm_buddy *mm, 1264 struct drm_buddy_block *block, 1265 struct drm_printer *p) 1266 { 1267 u64 start = drm_buddy_block_offset(block); 1268 u64 size = drm_buddy_block_size(mm, block); 1269 1270 drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size); 1271 } 1272 EXPORT_SYMBOL(drm_buddy_block_print); 1273 1274 /** 1275 * drm_buddy_print - print allocator state 1276 * 1277 * @mm: DRM buddy manager 1278 * @p: DRM printer to use 1279 */ 1280 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p) 1281 { 1282 int order; 1283 1284 drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n", 1285 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20); 1286 1287 for (order = mm->max_order; order >= 0; order--) { 1288 struct drm_buddy_block *block, *tmp; 1289 struct rb_root *root; 1290 u64 count = 0, free; 1291 unsigned int tree; 1292 1293 for_each_free_tree(tree) { 1294 root = &mm->free_trees[tree][order]; 1295 1296 rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) { 1297 BUG_ON(!drm_buddy_block_is_free(block)); 1298 count++; 1299 } 1300 } 1301 1302 drm_printf(p, "order-%2d ", order); 1303 1304 free = count * (mm->chunk_size << order); 1305 if (free < SZ_1M) 1306 drm_printf(p, "free: %8llu KiB", free >> 10); 1307 else 1308 drm_printf(p, "free: %8llu MiB", free >> 20); 1309 1310 drm_printf(p, ", blocks: %llu\n", count); 1311 } 1312 } 1313 EXPORT_SYMBOL(drm_buddy_print); 1314 1315 static void drm_buddy_module_exit(void) 1316 { 1317 kmem_cache_destroy(slab_blocks); 1318 } 1319 1320 static int __init drm_buddy_module_init(void) 1321 { 1322 slab_blocks = KMEM_CACHE(drm_buddy_block, 0); 1323 if (!slab_blocks) 1324 return -ENOMEM; 1325 1326 return 0; 1327 } 1328 1329 module_init(drm_buddy_module_init); 1330 module_exit(drm_buddy_module_exit); 1331 1332 MODULE_DESCRIPTION("DRM Buddy Allocator"); 1333 MODULE_LICENSE("Dual MIT/GPL"); 1334