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