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 <sys/pool.h> 11 12 #include <drm/drm_buddy.h> 13 14 static struct pool 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 #ifdef __linux__ 26 block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); 27 #else 28 block = pool_get(&slab_blocks, PR_WAITOK | PR_ZERO); 29 #endif 30 if (!block) 31 return NULL; 32 33 block->header = offset; 34 block->header |= order; 35 block->parent = parent; 36 37 BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED); 38 return block; 39 } 40 41 static void drm_block_free(struct drm_buddy *mm, 42 struct drm_buddy_block *block) 43 { 44 #ifdef __linux__ 45 kmem_cache_free(slab_blocks, block); 46 #else 47 pool_put(&slab_blocks, block); 48 #endif 49 } 50 51 static void list_insert_sorted(struct drm_buddy *mm, 52 struct drm_buddy_block *block) 53 { 54 struct drm_buddy_block *node; 55 struct list_head *head; 56 57 head = &mm->free_list[drm_buddy_block_order(block)]; 58 if (list_empty(head)) { 59 list_add(&block->link, head); 60 return; 61 } 62 63 list_for_each_entry(node, head, link) 64 if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node)) 65 break; 66 67 __list_add(&block->link, node->link.prev, &node->link); 68 } 69 70 static void mark_allocated(struct drm_buddy_block *block) 71 { 72 block->header &= ~DRM_BUDDY_HEADER_STATE; 73 block->header |= DRM_BUDDY_ALLOCATED; 74 75 list_del(&block->link); 76 } 77 78 static void mark_free(struct drm_buddy *mm, 79 struct drm_buddy_block *block) 80 { 81 block->header &= ~DRM_BUDDY_HEADER_STATE; 82 block->header |= DRM_BUDDY_FREE; 83 84 list_insert_sorted(mm, block); 85 } 86 87 static void mark_split(struct drm_buddy_block *block) 88 { 89 block->header &= ~DRM_BUDDY_HEADER_STATE; 90 block->header |= DRM_BUDDY_SPLIT; 91 92 list_del(&block->link); 93 } 94 95 /** 96 * drm_buddy_init - init memory manager 97 * 98 * @mm: DRM buddy manager to initialize 99 * @size: size in bytes to manage 100 * @chunk_size: minimum page size in bytes for our allocations 101 * 102 * Initializes the memory manager and its resources. 103 * 104 * Returns: 105 * 0 on success, error code on failure. 106 */ 107 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size) 108 { 109 unsigned int i; 110 u64 offset; 111 112 if (size < chunk_size) 113 return -EINVAL; 114 115 if (chunk_size < PAGE_SIZE) 116 return -EINVAL; 117 118 if (!is_power_of_2(chunk_size)) 119 return -EINVAL; 120 121 size = round_down(size, chunk_size); 122 123 mm->size = size; 124 mm->avail = size; 125 mm->chunk_size = chunk_size; 126 mm->max_order = ilog2(size) - ilog2(chunk_size); 127 128 BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER); 129 130 mm->free_list = kmalloc_array(mm->max_order + 1, 131 sizeof(struct list_head), 132 GFP_KERNEL); 133 if (!mm->free_list) 134 return -ENOMEM; 135 136 for (i = 0; i <= mm->max_order; ++i) 137 INIT_LIST_HEAD(&mm->free_list[i]); 138 139 mm->n_roots = hweight64(size); 140 141 mm->roots = kmalloc_array(mm->n_roots, 142 sizeof(struct drm_buddy_block *), 143 GFP_KERNEL); 144 if (!mm->roots) 145 goto out_free_list; 146 147 offset = 0; 148 i = 0; 149 150 /* 151 * Split into power-of-two blocks, in case we are given a size that is 152 * not itself a power-of-two. 153 */ 154 do { 155 struct drm_buddy_block *root; 156 unsigned int order; 157 u64 root_size; 158 159 order = ilog2(size) - ilog2(chunk_size); 160 root_size = chunk_size << order; 161 162 root = drm_block_alloc(mm, NULL, order, offset); 163 if (!root) 164 goto out_free_roots; 165 166 mark_free(mm, root); 167 168 BUG_ON(i > mm->max_order); 169 BUG_ON(drm_buddy_block_size(mm, root) < chunk_size); 170 171 mm->roots[i] = root; 172 173 offset += root_size; 174 size -= root_size; 175 i++; 176 } while (size); 177 178 return 0; 179 180 out_free_roots: 181 while (i--) 182 drm_block_free(mm, mm->roots[i]); 183 kfree(mm->roots); 184 out_free_list: 185 kfree(mm->free_list); 186 return -ENOMEM; 187 } 188 EXPORT_SYMBOL(drm_buddy_init); 189 190 /** 191 * drm_buddy_fini - tear down the memory manager 192 * 193 * @mm: DRM buddy manager to free 194 * 195 * Cleanup memory manager resources and the freelist 196 */ 197 void drm_buddy_fini(struct drm_buddy *mm) 198 { 199 int i; 200 201 for (i = 0; i < mm->n_roots; ++i) { 202 WARN_ON(!drm_buddy_block_is_free(mm->roots[i])); 203 drm_block_free(mm, mm->roots[i]); 204 } 205 206 WARN_ON(mm->avail != mm->size); 207 208 kfree(mm->roots); 209 kfree(mm->free_list); 210 } 211 EXPORT_SYMBOL(drm_buddy_fini); 212 213 static int split_block(struct drm_buddy *mm, 214 struct drm_buddy_block *block) 215 { 216 unsigned int block_order = drm_buddy_block_order(block) - 1; 217 u64 offset = drm_buddy_block_offset(block); 218 219 BUG_ON(!drm_buddy_block_is_free(block)); 220 BUG_ON(!drm_buddy_block_order(block)); 221 222 block->left = drm_block_alloc(mm, block, block_order, offset); 223 if (!block->left) 224 return -ENOMEM; 225 226 block->right = drm_block_alloc(mm, block, block_order, 227 offset + (mm->chunk_size << block_order)); 228 if (!block->right) { 229 drm_block_free(mm, block->left); 230 return -ENOMEM; 231 } 232 233 mark_free(mm, block->left); 234 mark_free(mm, block->right); 235 236 mark_split(block); 237 238 return 0; 239 } 240 241 static struct drm_buddy_block * 242 __get_buddy(struct drm_buddy_block *block) 243 { 244 struct drm_buddy_block *parent; 245 246 parent = block->parent; 247 if (!parent) 248 return NULL; 249 250 if (parent->left == block) 251 return parent->right; 252 253 return parent->left; 254 } 255 256 /** 257 * drm_get_buddy - get buddy address 258 * 259 * @block: DRM buddy block 260 * 261 * Returns the corresponding buddy block for @block, or NULL 262 * if this is a root block and can't be merged further. 263 * Requires some kind of locking to protect against 264 * any concurrent allocate and free operations. 265 */ 266 struct drm_buddy_block * 267 drm_get_buddy(struct drm_buddy_block *block) 268 { 269 return __get_buddy(block); 270 } 271 EXPORT_SYMBOL(drm_get_buddy); 272 273 static void __drm_buddy_free(struct drm_buddy *mm, 274 struct drm_buddy_block *block) 275 { 276 struct drm_buddy_block *parent; 277 278 while ((parent = block->parent)) { 279 struct drm_buddy_block *buddy; 280 281 buddy = __get_buddy(block); 282 283 if (!drm_buddy_block_is_free(buddy)) 284 break; 285 286 list_del(&buddy->link); 287 288 drm_block_free(mm, block); 289 drm_block_free(mm, buddy); 290 291 block = parent; 292 } 293 294 mark_free(mm, block); 295 } 296 297 /** 298 * drm_buddy_free_block - free a block 299 * 300 * @mm: DRM buddy manager 301 * @block: block to be freed 302 */ 303 void drm_buddy_free_block(struct drm_buddy *mm, 304 struct drm_buddy_block *block) 305 { 306 BUG_ON(!drm_buddy_block_is_allocated(block)); 307 mm->avail += drm_buddy_block_size(mm, block); 308 __drm_buddy_free(mm, block); 309 } 310 EXPORT_SYMBOL(drm_buddy_free_block); 311 312 /** 313 * drm_buddy_free_list - free blocks 314 * 315 * @mm: DRM buddy manager 316 * @objects: input list head to free blocks 317 */ 318 void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects) 319 { 320 struct drm_buddy_block *block, *on; 321 322 list_for_each_entry_safe(block, on, objects, link) { 323 drm_buddy_free_block(mm, block); 324 cond_resched(); 325 } 326 INIT_LIST_HEAD(objects); 327 } 328 EXPORT_SYMBOL(drm_buddy_free_list); 329 330 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) 331 { 332 return s1 <= e2 && e1 >= s2; 333 } 334 335 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) 336 { 337 return s1 <= s2 && e1 >= e2; 338 } 339 340 static struct drm_buddy_block * 341 alloc_range_bias(struct drm_buddy *mm, 342 u64 start, u64 end, 343 unsigned int order) 344 { 345 struct drm_buddy_block *block; 346 struct drm_buddy_block *buddy; 347 DRM_LIST_HEAD(dfs); 348 int err; 349 int i; 350 351 end = end - 1; 352 353 for (i = 0; i < mm->n_roots; ++i) 354 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 355 356 do { 357 u64 block_start; 358 u64 block_end; 359 360 block = list_first_entry_or_null(&dfs, 361 struct drm_buddy_block, 362 tmp_link); 363 if (!block) 364 break; 365 366 list_del(&block->tmp_link); 367 368 if (drm_buddy_block_order(block) < order) 369 continue; 370 371 block_start = drm_buddy_block_offset(block); 372 block_end = block_start + drm_buddy_block_size(mm, block) - 1; 373 374 if (!overlaps(start, end, block_start, block_end)) 375 continue; 376 377 if (drm_buddy_block_is_allocated(block)) 378 continue; 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 { 495 struct drm_buddy_block *block; 496 struct drm_buddy_block *buddy; 497 DRM_LIST_HEAD(allocated); 498 u64 end; 499 int err; 500 501 end = start + size - 1; 502 503 do { 504 u64 block_start; 505 u64 block_end; 506 507 block = list_first_entry_or_null(dfs, 508 struct drm_buddy_block, 509 tmp_link); 510 if (!block) 511 break; 512 513 list_del(&block->tmp_link); 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 err = -ENOSPC; 523 goto err_free; 524 } 525 526 if (contains(start, end, block_start, block_end)) { 527 if (!drm_buddy_block_is_free(block)) { 528 err = -ENOSPC; 529 goto err_free; 530 } 531 532 mark_allocated(block); 533 mm->avail -= drm_buddy_block_size(mm, block); 534 list_add_tail(&block->link, &allocated); 535 continue; 536 } 537 538 if (!drm_buddy_block_is_split(block)) { 539 err = split_block(mm, block); 540 if (unlikely(err)) 541 goto err_undo; 542 } 543 544 list_add(&block->right->tmp_link, dfs); 545 list_add(&block->left->tmp_link, dfs); 546 } while (1); 547 548 list_splice_tail(&allocated, blocks); 549 return 0; 550 551 err_undo: 552 /* 553 * We really don't want to leave around a bunch of split blocks, since 554 * bigger is better, so make sure we merge everything back before we 555 * free the allocated blocks. 556 */ 557 buddy = __get_buddy(block); 558 if (buddy && 559 (drm_buddy_block_is_free(block) && 560 drm_buddy_block_is_free(buddy))) 561 __drm_buddy_free(mm, block); 562 563 err_free: 564 drm_buddy_free_list(mm, &allocated); 565 return err; 566 } 567 568 static int __drm_buddy_alloc_range(struct drm_buddy *mm, 569 u64 start, 570 u64 size, 571 struct list_head *blocks) 572 { 573 DRM_LIST_HEAD(dfs); 574 int i; 575 576 for (i = 0; i < mm->n_roots; ++i) 577 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 578 579 return __alloc_range(mm, &dfs, start, size, blocks); 580 } 581 582 /** 583 * drm_buddy_block_trim - free unused pages 584 * 585 * @mm: DRM buddy manager 586 * @new_size: original size requested 587 * @blocks: Input and output list of allocated blocks. 588 * MUST contain single block as input to be trimmed. 589 * On success will contain the newly allocated blocks 590 * making up the @new_size. Blocks always appear in 591 * ascending order 592 * 593 * For contiguous allocation, we round up the size to the nearest 594 * power of two value, drivers consume *actual* size, so remaining 595 * portions are unused and can be optionally freed with this function 596 * 597 * Returns: 598 * 0 on success, error code on failure. 599 */ 600 int drm_buddy_block_trim(struct drm_buddy *mm, 601 u64 new_size, 602 struct list_head *blocks) 603 { 604 struct drm_buddy_block *parent; 605 struct drm_buddy_block *block; 606 DRM_LIST_HEAD(dfs); 607 u64 new_start; 608 int err; 609 610 if (!list_is_singular(blocks)) 611 return -EINVAL; 612 613 block = list_first_entry(blocks, 614 struct drm_buddy_block, 615 link); 616 617 if (WARN_ON(!drm_buddy_block_is_allocated(block))) 618 return -EINVAL; 619 620 if (new_size > drm_buddy_block_size(mm, block)) 621 return -EINVAL; 622 623 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) 624 return -EINVAL; 625 626 if (new_size == drm_buddy_block_size(mm, block)) 627 return 0; 628 629 list_del(&block->link); 630 mark_free(mm, block); 631 mm->avail += drm_buddy_block_size(mm, block); 632 633 /* Prevent recursively freeing this node */ 634 parent = block->parent; 635 block->parent = NULL; 636 637 new_start = drm_buddy_block_offset(block); 638 list_add(&block->tmp_link, &dfs); 639 err = __alloc_range(mm, &dfs, new_start, new_size, blocks); 640 if (err) { 641 mark_allocated(block); 642 mm->avail -= drm_buddy_block_size(mm, block); 643 list_add(&block->link, blocks); 644 } 645 646 block->parent = parent; 647 return err; 648 } 649 EXPORT_SYMBOL(drm_buddy_block_trim); 650 651 /** 652 * drm_buddy_alloc_blocks - allocate power-of-two blocks 653 * 654 * @mm: DRM buddy manager to allocate from 655 * @start: start of the allowed range for this block 656 * @end: end of the allowed range for this block 657 * @size: size of the allocation 658 * @min_page_size: alignment of the allocation 659 * @blocks: output list head to add allocated blocks 660 * @flags: DRM_BUDDY_*_ALLOCATION flags 661 * 662 * alloc_range_bias() called on range limitations, which traverses 663 * the tree and returns the desired block. 664 * 665 * alloc_from_freelist() called when *no* range restrictions 666 * are enforced, which picks the block from the freelist. 667 * 668 * Returns: 669 * 0 on success, error code on failure. 670 */ 671 int drm_buddy_alloc_blocks(struct drm_buddy *mm, 672 u64 start, u64 end, u64 size, 673 u64 min_page_size, 674 struct list_head *blocks, 675 unsigned long flags) 676 { 677 struct drm_buddy_block *block = NULL; 678 unsigned int min_order, order; 679 unsigned long pages; 680 DRM_LIST_HEAD(allocated); 681 int err; 682 683 if (size < mm->chunk_size) 684 return -EINVAL; 685 686 if (min_page_size < mm->chunk_size) 687 return -EINVAL; 688 689 if (!is_power_of_2(min_page_size)) 690 return -EINVAL; 691 692 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) 693 return -EINVAL; 694 695 if (end > mm->size) 696 return -EINVAL; 697 698 if (range_overflows(start, size, mm->size)) 699 return -EINVAL; 700 701 /* Actual range allocation */ 702 if (start + size == end) 703 return __drm_buddy_alloc_range(mm, start, size, blocks); 704 705 if (!IS_ALIGNED(size, min_page_size)) 706 return -EINVAL; 707 708 pages = size >> ilog2(mm->chunk_size); 709 order = fls(pages) - 1; 710 min_order = ilog2(min_page_size) - ilog2(mm->chunk_size); 711 712 do { 713 order = min(order, (unsigned int)fls(pages) - 1); 714 BUG_ON(order > mm->max_order); 715 BUG_ON(order < min_order); 716 717 do { 718 if (flags & DRM_BUDDY_RANGE_ALLOCATION) 719 /* Allocate traversing within the range */ 720 block = alloc_range_bias(mm, start, end, order); 721 else 722 /* Allocate from freelist */ 723 block = alloc_from_freelist(mm, order, flags); 724 725 if (!IS_ERR(block)) 726 break; 727 728 if (order-- == min_order) { 729 err = -ENOSPC; 730 goto err_free; 731 } 732 } while (1); 733 734 mark_allocated(block); 735 mm->avail -= drm_buddy_block_size(mm, block); 736 kmemleak_update_trace(block); 737 list_add_tail(&block->link, &allocated); 738 739 pages -= BIT(order); 740 741 if (!pages) 742 break; 743 } while (1); 744 745 list_splice_tail(&allocated, blocks); 746 return 0; 747 748 err_free: 749 drm_buddy_free_list(mm, &allocated); 750 return err; 751 } 752 EXPORT_SYMBOL(drm_buddy_alloc_blocks); 753 754 /** 755 * drm_buddy_block_print - print block information 756 * 757 * @mm: DRM buddy manager 758 * @block: DRM buddy block 759 * @p: DRM printer to use 760 */ 761 void drm_buddy_block_print(struct drm_buddy *mm, 762 struct drm_buddy_block *block, 763 struct drm_printer *p) 764 { 765 u64 start = drm_buddy_block_offset(block); 766 u64 size = drm_buddy_block_size(mm, block); 767 768 drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size); 769 } 770 EXPORT_SYMBOL(drm_buddy_block_print); 771 772 /** 773 * drm_buddy_print - print allocator state 774 * 775 * @mm: DRM buddy manager 776 * @p: DRM printer to use 777 */ 778 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p) 779 { 780 int order; 781 782 drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB\n", 783 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20); 784 785 for (order = mm->max_order; order >= 0; order--) { 786 struct drm_buddy_block *block; 787 u64 count = 0, free; 788 789 list_for_each_entry(block, &mm->free_list[order], link) { 790 BUG_ON(!drm_buddy_block_is_free(block)); 791 count++; 792 } 793 794 drm_printf(p, "order-%2d ", order); 795 796 free = count * (mm->chunk_size << order); 797 if (free < SZ_1M) 798 drm_printf(p, "free: %8llu KiB", free >> 10); 799 else 800 drm_printf(p, "free: %8llu MiB", free >> 20); 801 802 drm_printf(p, ", blocks: %llu\n", count); 803 } 804 } 805 EXPORT_SYMBOL(drm_buddy_print); 806 807 void drm_buddy_module_exit(void) 808 { 809 #ifdef __linux__ 810 kmem_cache_destroy(slab_blocks); 811 #else 812 pool_destroy(&slab_blocks); 813 #endif 814 } 815 816 int __init drm_buddy_module_init(void) 817 { 818 #ifdef __linux__ 819 slab_blocks = KMEM_CACHE(drm_buddy_block, 0); 820 if (!slab_blocks) 821 return -ENOMEM; 822 #else 823 pool_init(&slab_blocks, sizeof(struct drm_buddy_block), 824 CACHELINESIZE, IPL_NONE, 0, "drmbb", NULL); 825 #endif 826 827 return 0; 828 } 829 830 module_init(drm_buddy_module_init); 831 module_exit(drm_buddy_module_exit); 832 833 MODULE_DESCRIPTION("DRM Buddy Allocator"); 834 MODULE_LICENSE("Dual MIT/GPL"); 835