1 // SPDX-License-Identifier: MIT 2 /* 3 * Copyright © 2021 Intel Corporation 4 */ 5 6 #include <linux/kmemleak.h> 7 #include <linux/module.h> 8 #include <linux/sizes.h> 9 10 #include <drm/drm_buddy.h> 11 12 static struct kmem_cache *slab_blocks; 13 14 static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm, 15 struct drm_buddy_block *parent, 16 unsigned int order, 17 u64 offset) 18 { 19 struct drm_buddy_block *block; 20 21 BUG_ON(order > DRM_BUDDY_MAX_ORDER); 22 23 block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); 24 if (!block) 25 return NULL; 26 27 block->header = offset; 28 block->header |= order; 29 block->parent = parent; 30 31 BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED); 32 return block; 33 } 34 35 static void drm_block_free(struct drm_buddy *mm, 36 struct drm_buddy_block *block) 37 { 38 kmem_cache_free(slab_blocks, block); 39 } 40 41 static void list_insert_sorted(struct drm_buddy *mm, 42 struct drm_buddy_block *block) 43 { 44 struct drm_buddy_block *node; 45 struct list_head *head; 46 47 head = &mm->free_list[drm_buddy_block_order(block)]; 48 if (list_empty(head)) { 49 list_add(&block->link, head); 50 return; 51 } 52 53 list_for_each_entry(node, head, link) 54 if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node)) 55 break; 56 57 __list_add(&block->link, node->link.prev, &node->link); 58 } 59 60 static void mark_allocated(struct drm_buddy_block *block) 61 { 62 block->header &= ~DRM_BUDDY_HEADER_STATE; 63 block->header |= DRM_BUDDY_ALLOCATED; 64 65 list_del(&block->link); 66 } 67 68 static void mark_free(struct drm_buddy *mm, 69 struct drm_buddy_block *block) 70 { 71 block->header &= ~DRM_BUDDY_HEADER_STATE; 72 block->header |= DRM_BUDDY_FREE; 73 74 list_insert_sorted(mm, block); 75 } 76 77 static void mark_split(struct drm_buddy_block *block) 78 { 79 block->header &= ~DRM_BUDDY_HEADER_STATE; 80 block->header |= DRM_BUDDY_SPLIT; 81 82 list_del(&block->link); 83 } 84 85 /** 86 * drm_buddy_init - init memory manager 87 * 88 * @mm: DRM buddy manager to initialize 89 * @size: size in bytes to manage 90 * @chunk_size: minimum page size in bytes for our allocations 91 * 92 * Initializes the memory manager and its resources. 93 * 94 * Returns: 95 * 0 on success, error code on failure. 96 */ 97 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size) 98 { 99 unsigned int i; 100 u64 offset; 101 102 if (size < chunk_size) 103 return -EINVAL; 104 105 if (chunk_size < PAGE_SIZE) 106 return -EINVAL; 107 108 if (!is_power_of_2(chunk_size)) 109 return -EINVAL; 110 111 size = round_down(size, chunk_size); 112 113 mm->size = size; 114 mm->avail = size; 115 mm->chunk_size = chunk_size; 116 mm->max_order = ilog2(size) - ilog2(chunk_size); 117 118 BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER); 119 120 mm->free_list = kmalloc_array(mm->max_order + 1, 121 sizeof(struct list_head), 122 GFP_KERNEL); 123 if (!mm->free_list) 124 return -ENOMEM; 125 126 for (i = 0; i <= mm->max_order; ++i) 127 INIT_LIST_HEAD(&mm->free_list[i]); 128 129 mm->n_roots = hweight64(size); 130 131 mm->roots = kmalloc_array(mm->n_roots, 132 sizeof(struct drm_buddy_block *), 133 GFP_KERNEL); 134 if (!mm->roots) 135 goto out_free_list; 136 137 offset = 0; 138 i = 0; 139 140 /* 141 * Split into power-of-two blocks, in case we are given a size that is 142 * not itself a power-of-two. 143 */ 144 do { 145 struct drm_buddy_block *root; 146 unsigned int order; 147 u64 root_size; 148 149 order = ilog2(size) - ilog2(chunk_size); 150 root_size = chunk_size << order; 151 152 root = drm_block_alloc(mm, NULL, order, offset); 153 if (!root) 154 goto out_free_roots; 155 156 mark_free(mm, root); 157 158 BUG_ON(i > mm->max_order); 159 BUG_ON(drm_buddy_block_size(mm, root) < chunk_size); 160 161 mm->roots[i] = root; 162 163 offset += root_size; 164 size -= root_size; 165 i++; 166 } while (size); 167 168 return 0; 169 170 out_free_roots: 171 while (i--) 172 drm_block_free(mm, mm->roots[i]); 173 kfree(mm->roots); 174 out_free_list: 175 kfree(mm->free_list); 176 return -ENOMEM; 177 } 178 EXPORT_SYMBOL(drm_buddy_init); 179 180 /** 181 * drm_buddy_fini - tear down the memory manager 182 * 183 * @mm: DRM buddy manager to free 184 * 185 * Cleanup memory manager resources and the freelist 186 */ 187 void drm_buddy_fini(struct drm_buddy *mm) 188 { 189 int i; 190 191 for (i = 0; i < mm->n_roots; ++i) { 192 WARN_ON(!drm_buddy_block_is_free(mm->roots[i])); 193 drm_block_free(mm, mm->roots[i]); 194 } 195 196 WARN_ON(mm->avail != mm->size); 197 198 kfree(mm->roots); 199 kfree(mm->free_list); 200 } 201 EXPORT_SYMBOL(drm_buddy_fini); 202 203 static int split_block(struct drm_buddy *mm, 204 struct drm_buddy_block *block) 205 { 206 unsigned int block_order = drm_buddy_block_order(block) - 1; 207 u64 offset = drm_buddy_block_offset(block); 208 209 BUG_ON(!drm_buddy_block_is_free(block)); 210 BUG_ON(!drm_buddy_block_order(block)); 211 212 block->left = drm_block_alloc(mm, block, block_order, offset); 213 if (!block->left) 214 return -ENOMEM; 215 216 block->right = drm_block_alloc(mm, block, block_order, 217 offset + (mm->chunk_size << block_order)); 218 if (!block->right) { 219 drm_block_free(mm, block->left); 220 return -ENOMEM; 221 } 222 223 mark_free(mm, block->left); 224 mark_free(mm, block->right); 225 226 mark_split(block); 227 228 return 0; 229 } 230 231 static struct drm_buddy_block * 232 __get_buddy(struct drm_buddy_block *block) 233 { 234 struct drm_buddy_block *parent; 235 236 parent = block->parent; 237 if (!parent) 238 return NULL; 239 240 if (parent->left == block) 241 return parent->right; 242 243 return parent->left; 244 } 245 246 /** 247 * drm_get_buddy - get buddy address 248 * 249 * @block: DRM buddy block 250 * 251 * Returns the corresponding buddy block for @block, or NULL 252 * if this is a root block and can't be merged further. 253 * Requires some kind of locking to protect against 254 * any concurrent allocate and free operations. 255 */ 256 struct drm_buddy_block * 257 drm_get_buddy(struct drm_buddy_block *block) 258 { 259 return __get_buddy(block); 260 } 261 EXPORT_SYMBOL(drm_get_buddy); 262 263 static void __drm_buddy_free(struct drm_buddy *mm, 264 struct drm_buddy_block *block) 265 { 266 struct drm_buddy_block *parent; 267 268 while ((parent = block->parent)) { 269 struct drm_buddy_block *buddy; 270 271 buddy = __get_buddy(block); 272 273 if (!drm_buddy_block_is_free(buddy)) 274 break; 275 276 list_del(&buddy->link); 277 278 drm_block_free(mm, block); 279 drm_block_free(mm, buddy); 280 281 block = parent; 282 } 283 284 mark_free(mm, block); 285 } 286 287 /** 288 * drm_buddy_free_block - free a block 289 * 290 * @mm: DRM buddy manager 291 * @block: block to be freed 292 */ 293 void drm_buddy_free_block(struct drm_buddy *mm, 294 struct drm_buddy_block *block) 295 { 296 BUG_ON(!drm_buddy_block_is_allocated(block)); 297 mm->avail += drm_buddy_block_size(mm, block); 298 __drm_buddy_free(mm, block); 299 } 300 EXPORT_SYMBOL(drm_buddy_free_block); 301 302 /** 303 * drm_buddy_free_list - free blocks 304 * 305 * @mm: DRM buddy manager 306 * @objects: input list head to free blocks 307 */ 308 void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects) 309 { 310 struct drm_buddy_block *block, *on; 311 312 list_for_each_entry_safe(block, on, objects, link) { 313 drm_buddy_free_block(mm, block); 314 cond_resched(); 315 } 316 INIT_LIST_HEAD(objects); 317 } 318 EXPORT_SYMBOL(drm_buddy_free_list); 319 320 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) 321 { 322 return s1 <= e2 && e1 >= s2; 323 } 324 325 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) 326 { 327 return s1 <= s2 && e1 >= e2; 328 } 329 330 static struct drm_buddy_block * 331 alloc_range_bias(struct drm_buddy *mm, 332 u64 start, u64 end, 333 unsigned int order) 334 { 335 u64 req_size = mm->chunk_size << order; 336 struct drm_buddy_block *block; 337 struct drm_buddy_block *buddy; 338 LIST_HEAD(dfs); 339 int err; 340 int i; 341 342 end = end - 1; 343 344 for (i = 0; i < mm->n_roots; ++i) 345 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 346 347 do { 348 u64 block_start; 349 u64 block_end; 350 351 block = list_first_entry_or_null(&dfs, 352 struct drm_buddy_block, 353 tmp_link); 354 if (!block) 355 break; 356 357 list_del(&block->tmp_link); 358 359 if (drm_buddy_block_order(block) < order) 360 continue; 361 362 block_start = drm_buddy_block_offset(block); 363 block_end = block_start + drm_buddy_block_size(mm, block) - 1; 364 365 if (!overlaps(start, end, block_start, block_end)) 366 continue; 367 368 if (drm_buddy_block_is_allocated(block)) 369 continue; 370 371 if (block_start < start || block_end > end) { 372 u64 adjusted_start = max(block_start, start); 373 u64 adjusted_end = min(block_end, end); 374 375 if (round_down(adjusted_end + 1, req_size) <= 376 round_up(adjusted_start, req_size)) 377 continue; 378 } 379 380 if (contains(start, end, block_start, block_end) && 381 order == drm_buddy_block_order(block)) { 382 /* 383 * Find the free block within the range. 384 */ 385 if (drm_buddy_block_is_free(block)) 386 return block; 387 388 continue; 389 } 390 391 if (!drm_buddy_block_is_split(block)) { 392 err = split_block(mm, block); 393 if (unlikely(err)) 394 goto err_undo; 395 } 396 397 list_add(&block->right->tmp_link, &dfs); 398 list_add(&block->left->tmp_link, &dfs); 399 } while (1); 400 401 return ERR_PTR(-ENOSPC); 402 403 err_undo: 404 /* 405 * We really don't want to leave around a bunch of split blocks, since 406 * bigger is better, so make sure we merge everything back before we 407 * free the allocated blocks. 408 */ 409 buddy = __get_buddy(block); 410 if (buddy && 411 (drm_buddy_block_is_free(block) && 412 drm_buddy_block_is_free(buddy))) 413 __drm_buddy_free(mm, block); 414 return ERR_PTR(err); 415 } 416 417 static struct drm_buddy_block * 418 get_maxblock(struct drm_buddy *mm, unsigned int order) 419 { 420 struct drm_buddy_block *max_block = NULL, *node; 421 unsigned int i; 422 423 for (i = order; i <= mm->max_order; ++i) { 424 if (!list_empty(&mm->free_list[i])) { 425 node = list_last_entry(&mm->free_list[i], 426 struct drm_buddy_block, 427 link); 428 if (!max_block) { 429 max_block = node; 430 continue; 431 } 432 433 if (drm_buddy_block_offset(node) > 434 drm_buddy_block_offset(max_block)) { 435 max_block = node; 436 } 437 } 438 } 439 440 return max_block; 441 } 442 443 static struct drm_buddy_block * 444 alloc_from_freelist(struct drm_buddy *mm, 445 unsigned int order, 446 unsigned long flags) 447 { 448 struct drm_buddy_block *block = NULL; 449 unsigned int tmp; 450 int err; 451 452 if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) { 453 block = get_maxblock(mm, order); 454 if (block) 455 /* Store the obtained block order */ 456 tmp = drm_buddy_block_order(block); 457 } else { 458 for (tmp = order; tmp <= mm->max_order; ++tmp) { 459 if (!list_empty(&mm->free_list[tmp])) { 460 block = list_last_entry(&mm->free_list[tmp], 461 struct drm_buddy_block, 462 link); 463 if (block) 464 break; 465 } 466 } 467 } 468 469 if (!block) 470 return ERR_PTR(-ENOSPC); 471 472 BUG_ON(!drm_buddy_block_is_free(block)); 473 474 while (tmp != order) { 475 err = split_block(mm, block); 476 if (unlikely(err)) 477 goto err_undo; 478 479 block = block->right; 480 tmp--; 481 } 482 return block; 483 484 err_undo: 485 if (tmp != order) 486 __drm_buddy_free(mm, block); 487 return ERR_PTR(err); 488 } 489 490 static int __alloc_range(struct drm_buddy *mm, 491 struct list_head *dfs, 492 u64 start, u64 size, 493 struct list_head *blocks, 494 u64 *total_allocated_on_err) 495 { 496 struct drm_buddy_block *block; 497 struct drm_buddy_block *buddy; 498 u64 total_allocated = 0; 499 LIST_HEAD(allocated); 500 u64 end; 501 int err; 502 503 end = start + size - 1; 504 505 do { 506 u64 block_start; 507 u64 block_end; 508 509 block = list_first_entry_or_null(dfs, 510 struct drm_buddy_block, 511 tmp_link); 512 if (!block) 513 break; 514 515 list_del(&block->tmp_link); 516 517 block_start = drm_buddy_block_offset(block); 518 block_end = block_start + drm_buddy_block_size(mm, block) - 1; 519 520 if (!overlaps(start, end, block_start, block_end)) 521 continue; 522 523 if (drm_buddy_block_is_allocated(block)) { 524 err = -ENOSPC; 525 goto err_free; 526 } 527 528 if (contains(start, end, block_start, block_end)) { 529 if (!drm_buddy_block_is_free(block)) { 530 err = -ENOSPC; 531 goto err_free; 532 } 533 534 mark_allocated(block); 535 total_allocated += drm_buddy_block_size(mm, block); 536 mm->avail -= drm_buddy_block_size(mm, block); 537 list_add_tail(&block->link, &allocated); 538 continue; 539 } 540 541 if (!drm_buddy_block_is_split(block)) { 542 err = split_block(mm, block); 543 if (unlikely(err)) 544 goto err_undo; 545 } 546 547 list_add(&block->right->tmp_link, dfs); 548 list_add(&block->left->tmp_link, dfs); 549 } while (1); 550 551 if (total_allocated < size) { 552 err = -ENOSPC; 553 goto err_free; 554 } 555 556 list_splice_tail(&allocated, blocks); 557 558 return 0; 559 560 err_undo: 561 /* 562 * We really don't want to leave around a bunch of split blocks, since 563 * bigger is better, so make sure we merge everything back before we 564 * free the allocated blocks. 565 */ 566 buddy = __get_buddy(block); 567 if (buddy && 568 (drm_buddy_block_is_free(block) && 569 drm_buddy_block_is_free(buddy))) 570 __drm_buddy_free(mm, block); 571 572 err_free: 573 if (err == -ENOSPC && total_allocated_on_err) { 574 list_splice_tail(&allocated, blocks); 575 *total_allocated_on_err = total_allocated; 576 } else { 577 drm_buddy_free_list(mm, &allocated); 578 } 579 580 return err; 581 } 582 583 static int __drm_buddy_alloc_range(struct drm_buddy *mm, 584 u64 start, 585 u64 size, 586 u64 *total_allocated_on_err, 587 struct list_head *blocks) 588 { 589 LIST_HEAD(dfs); 590 int i; 591 592 for (i = 0; i < mm->n_roots; ++i) 593 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 594 595 return __alloc_range(mm, &dfs, start, size, 596 blocks, total_allocated_on_err); 597 } 598 599 static int __alloc_contig_try_harder(struct drm_buddy *mm, 600 u64 size, 601 u64 min_block_size, 602 struct list_head *blocks) 603 { 604 u64 rhs_offset, lhs_offset, lhs_size, filled; 605 struct drm_buddy_block *block; 606 struct list_head *list; 607 LIST_HEAD(blocks_lhs); 608 unsigned long pages; 609 unsigned int order; 610 u64 modify_size; 611 int err; 612 613 modify_size = rounddown_pow_of_two(size); 614 pages = modify_size >> ilog2(mm->chunk_size); 615 order = fls(pages) - 1; 616 if (order == 0) 617 return -ENOSPC; 618 619 list = &mm->free_list[order]; 620 if (list_empty(list)) 621 return -ENOSPC; 622 623 list_for_each_entry_reverse(block, list, link) { 624 /* Allocate blocks traversing RHS */ 625 rhs_offset = drm_buddy_block_offset(block); 626 err = __drm_buddy_alloc_range(mm, rhs_offset, size, 627 &filled, blocks); 628 if (!err || err != -ENOSPC) 629 return err; 630 631 lhs_size = max((size - filled), min_block_size); 632 if (!IS_ALIGNED(lhs_size, min_block_size)) 633 lhs_size = round_up(lhs_size, min_block_size); 634 635 /* Allocate blocks traversing LHS */ 636 lhs_offset = drm_buddy_block_offset(block) - lhs_size; 637 err = __drm_buddy_alloc_range(mm, lhs_offset, lhs_size, 638 NULL, &blocks_lhs); 639 if (!err) { 640 list_splice(&blocks_lhs, blocks); 641 return 0; 642 } else if (err != -ENOSPC) { 643 drm_buddy_free_list(mm, blocks); 644 return err; 645 } 646 /* Free blocks for the next iteration */ 647 drm_buddy_free_list(mm, blocks); 648 } 649 650 return -ENOSPC; 651 } 652 653 /** 654 * drm_buddy_block_trim - free unused pages 655 * 656 * @mm: DRM buddy manager 657 * @new_size: original size requested 658 * @blocks: Input and output list of allocated blocks. 659 * MUST contain single block as input to be trimmed. 660 * On success will contain the newly allocated blocks 661 * making up the @new_size. Blocks always appear in 662 * ascending order 663 * 664 * For contiguous allocation, we round up the size to the nearest 665 * power of two value, drivers consume *actual* size, so remaining 666 * portions are unused and can be optionally freed with this function 667 * 668 * Returns: 669 * 0 on success, error code on failure. 670 */ 671 int drm_buddy_block_trim(struct drm_buddy *mm, 672 u64 new_size, 673 struct list_head *blocks) 674 { 675 struct drm_buddy_block *parent; 676 struct drm_buddy_block *block; 677 LIST_HEAD(dfs); 678 u64 new_start; 679 int err; 680 681 if (!list_is_singular(blocks)) 682 return -EINVAL; 683 684 block = list_first_entry(blocks, 685 struct drm_buddy_block, 686 link); 687 688 if (WARN_ON(!drm_buddy_block_is_allocated(block))) 689 return -EINVAL; 690 691 if (new_size > drm_buddy_block_size(mm, block)) 692 return -EINVAL; 693 694 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) 695 return -EINVAL; 696 697 if (new_size == drm_buddy_block_size(mm, block)) 698 return 0; 699 700 list_del(&block->link); 701 mark_free(mm, block); 702 mm->avail += drm_buddy_block_size(mm, block); 703 704 /* Prevent recursively freeing this node */ 705 parent = block->parent; 706 block->parent = NULL; 707 708 new_start = drm_buddy_block_offset(block); 709 list_add(&block->tmp_link, &dfs); 710 err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL); 711 if (err) { 712 mark_allocated(block); 713 mm->avail -= drm_buddy_block_size(mm, block); 714 list_add(&block->link, blocks); 715 } 716 717 block->parent = parent; 718 return err; 719 } 720 EXPORT_SYMBOL(drm_buddy_block_trim); 721 722 /** 723 * drm_buddy_alloc_blocks - allocate power-of-two blocks 724 * 725 * @mm: DRM buddy manager to allocate from 726 * @start: start of the allowed range for this block 727 * @end: end of the allowed range for this block 728 * @size: size of the allocation 729 * @min_block_size: alignment of the allocation 730 * @blocks: output list head to add allocated blocks 731 * @flags: DRM_BUDDY_*_ALLOCATION flags 732 * 733 * alloc_range_bias() called on range limitations, which traverses 734 * the tree and returns the desired block. 735 * 736 * alloc_from_freelist() called when *no* range restrictions 737 * are enforced, which picks the block from the freelist. 738 * 739 * Returns: 740 * 0 on success, error code on failure. 741 */ 742 int drm_buddy_alloc_blocks(struct drm_buddy *mm, 743 u64 start, u64 end, u64 size, 744 u64 min_block_size, 745 struct list_head *blocks, 746 unsigned long flags) 747 { 748 struct drm_buddy_block *block = NULL; 749 u64 original_size, original_min_size; 750 unsigned int min_order, order; 751 LIST_HEAD(allocated); 752 unsigned long pages; 753 int err; 754 755 if (size < mm->chunk_size) 756 return -EINVAL; 757 758 if (min_block_size < mm->chunk_size) 759 return -EINVAL; 760 761 if (!is_power_of_2(min_block_size)) 762 return -EINVAL; 763 764 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) 765 return -EINVAL; 766 767 if (end > mm->size) 768 return -EINVAL; 769 770 if (range_overflows(start, size, mm->size)) 771 return -EINVAL; 772 773 /* Actual range allocation */ 774 if (start + size == end) { 775 if (!IS_ALIGNED(start | end, min_block_size)) 776 return -EINVAL; 777 778 return __drm_buddy_alloc_range(mm, start, size, NULL, blocks); 779 } 780 781 original_size = size; 782 original_min_size = min_block_size; 783 784 /* Roundup the size to power of 2 */ 785 if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION) { 786 size = roundup_pow_of_two(size); 787 min_block_size = size; 788 /* Align size value to min_block_size */ 789 } else if (!IS_ALIGNED(size, min_block_size)) { 790 size = round_up(size, min_block_size); 791 } 792 793 pages = size >> ilog2(mm->chunk_size); 794 order = fls(pages) - 1; 795 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size); 796 797 do { 798 order = min(order, (unsigned int)fls(pages) - 1); 799 BUG_ON(order > mm->max_order); 800 BUG_ON(order < min_order); 801 802 do { 803 if (flags & DRM_BUDDY_RANGE_ALLOCATION) 804 /* Allocate traversing within the range */ 805 block = alloc_range_bias(mm, start, end, order); 806 else 807 /* Allocate from freelist */ 808 block = alloc_from_freelist(mm, order, flags); 809 810 if (!IS_ERR(block)) 811 break; 812 813 if (order-- == min_order) { 814 if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION && 815 !(flags & DRM_BUDDY_RANGE_ALLOCATION)) 816 /* 817 * Try contiguous block allocation through 818 * try harder method 819 */ 820 return __alloc_contig_try_harder(mm, 821 original_size, 822 original_min_size, 823 blocks); 824 err = -ENOSPC; 825 goto err_free; 826 } 827 } while (1); 828 829 mark_allocated(block); 830 mm->avail -= drm_buddy_block_size(mm, block); 831 kmemleak_update_trace(block); 832 list_add_tail(&block->link, &allocated); 833 834 pages -= BIT(order); 835 836 if (!pages) 837 break; 838 } while (1); 839 840 /* Trim the allocated block to the required size */ 841 if (original_size != size) { 842 struct list_head *trim_list; 843 LIST_HEAD(temp); 844 u64 trim_size; 845 846 trim_list = &allocated; 847 trim_size = original_size; 848 849 if (!list_is_singular(&allocated)) { 850 block = list_last_entry(&allocated, typeof(*block), link); 851 list_move(&block->link, &temp); 852 trim_list = &temp; 853 trim_size = drm_buddy_block_size(mm, block) - 854 (size - original_size); 855 } 856 857 drm_buddy_block_trim(mm, 858 trim_size, 859 trim_list); 860 861 if (!list_empty(&temp)) 862 list_splice_tail(trim_list, &allocated); 863 } 864 865 list_splice_tail(&allocated, blocks); 866 return 0; 867 868 err_free: 869 drm_buddy_free_list(mm, &allocated); 870 return err; 871 } 872 EXPORT_SYMBOL(drm_buddy_alloc_blocks); 873 874 /** 875 * drm_buddy_block_print - print block information 876 * 877 * @mm: DRM buddy manager 878 * @block: DRM buddy block 879 * @p: DRM printer to use 880 */ 881 void drm_buddy_block_print(struct drm_buddy *mm, 882 struct drm_buddy_block *block, 883 struct drm_printer *p) 884 { 885 u64 start = drm_buddy_block_offset(block); 886 u64 size = drm_buddy_block_size(mm, block); 887 888 drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size); 889 } 890 EXPORT_SYMBOL(drm_buddy_block_print); 891 892 /** 893 * drm_buddy_print - print allocator state 894 * 895 * @mm: DRM buddy manager 896 * @p: DRM printer to use 897 */ 898 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p) 899 { 900 int order; 901 902 drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB\n", 903 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20); 904 905 for (order = mm->max_order; order >= 0; order--) { 906 struct drm_buddy_block *block; 907 u64 count = 0, free; 908 909 list_for_each_entry(block, &mm->free_list[order], link) { 910 BUG_ON(!drm_buddy_block_is_free(block)); 911 count++; 912 } 913 914 drm_printf(p, "order-%2d ", order); 915 916 free = count * (mm->chunk_size << order); 917 if (free < SZ_1M) 918 drm_printf(p, "free: %8llu KiB", free >> 10); 919 else 920 drm_printf(p, "free: %8llu MiB", free >> 20); 921 922 drm_printf(p, ", blocks: %llu\n", count); 923 } 924 } 925 EXPORT_SYMBOL(drm_buddy_print); 926 927 static void drm_buddy_module_exit(void) 928 { 929 kmem_cache_destroy(slab_blocks); 930 } 931 932 static int __init drm_buddy_module_init(void) 933 { 934 slab_blocks = KMEM_CACHE(drm_buddy_block, 0); 935 if (!slab_blocks) 936 return -ENOMEM; 937 938 return 0; 939 } 940 941 module_init(drm_buddy_module_init); 942 module_exit(drm_buddy_module_exit); 943 944 MODULE_DESCRIPTION("DRM Buddy Allocator"); 945 MODULE_LICENSE("Dual MIT/GPL"); 946