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