1 // SPDX-License-Identifier: MIT 2 /* 3 * Copyright © 2021 Intel Corporation 4 */ 5 6 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt 7 8 #include <linux/bug.h> 9 #include <linux/export.h> 10 #include <linux/kmemleak.h> 11 #include <linux/module.h> 12 #include <linux/sizes.h> 13 #include <linux/slab.h> 14 15 #include <linux/gpu_buddy.h> 16 17 /** 18 * gpu_buddy_assert - assert a condition in the buddy allocator 19 * @condition: condition expected to be true 20 * 21 * When CONFIG_KUNIT is enabled, evaluates @condition and, if false, triggers 22 * a WARN_ON() and also calls kunit_fail_current_test() so that any running 23 * kunit test is properly marked as failed. The stringified condition is 24 * included in the failure message for easy identification. 25 * 26 * When CONFIG_KUNIT is not enabled, this reduces to WARN_ON() so production 27 * builds retain the same warning semantics as before. 28 */ 29 #if IS_ENABLED(CONFIG_KUNIT) 30 #include <kunit/test-bug.h> 31 #define gpu_buddy_assert(condition) do { \ 32 if (WARN_ON(!(condition))) \ 33 kunit_fail_current_test("gpu_buddy_assert(" #condition ")"); \ 34 } while (0) 35 #else 36 #define gpu_buddy_assert(condition) WARN_ON(!(condition)) 37 #endif 38 39 static struct kmem_cache *slab_blocks; 40 static struct kmem_cache *slab_extents; 41 42 /* 43 * Dirty tracker 44 * ------------- 45 * 46 * The dirty tracker maintains an augmented interval rbtree of contiguous 47 * dirty address ranges, decoupled from the buddy free trees. 48 * Each node covers a maximal coalesced run; adjacent extents are merged 49 * on insertion so the tree always holds the smallest possible number of 50 * extents. The augmentation field @subtree_max_size lets the allocator 51 * locate the largest dirty extent in O(log E). 52 * 53 * Free trees (mm->free_tree[]) 54 * ---------------------------- 55 * 56 * Per-order augmented rbtrees of FREE buddy blocks, keyed by offset. 57 * Every node carries: 58 * - subtree_max_alignment: largest natural alignment in the subtree, 59 * used by aligned/range allocations to skip unsuitable subtrees in 60 * O(log N). 61 * - subtree_block_state: the highest clear class (DIRTY < MIXED < CLEAR) 62 * of any block in the subtree, maintained as a max augment. A value of 63 * >= MIXED means a clear-or-mixed block exists; == CLEAR means a 64 * fully-clear block exists. 65 * 66 * Block classes 67 * ------------- 68 * 69 * Each FREE block falls into one of three classes, determined in 70 * mark_free() by querying the dirty tracker for the block's range: 71 * 72 * clear -- HEADER_CLEAR set; no dirty extent overlaps the range. 73 * mixed -- HEADER_CLEAR unset; range has both dirty and clear bytes. 74 * dirty -- HEADER_CLEAR unset; range is fully dirty. 75 * 76 * Clear allocation 77 * ---------------- 78 * 79 * A clear (CLEAR_ALLOCATION) request prefers clear -> mixed -> dirty. 80 * Climbing from the requested order up to max_order, rbtree_last_clear_free_block() 81 * returns, in one O(log N) descent per order, the right-most clear-or-mixed block 82 * (fully-clear preferred over mixed) at the lowest order whose free tree contains 83 * such a block. Only if no clear-or-mixed block exists at any order >= the 84 * requested one does it fall back to a dirty block. 85 * 86 * Clear state is reported to the driver per whole block via HEADER_CLEAR, so a 87 * fully-clear block of the requested order lets the driver skip the clear pass. 88 * 89 * The effective allocation preference depends on how the driver handles 90 * freed blocks: 91 * 92 * 1) Never clear on free: 93 * No free block contains clear bytes, so clear allocations always 94 * fall back to dirty blocks. 95 * 96 * 2) Always clear on free: 97 * Freed blocks become clear while untouched blocks remain dirty. 98 * Merging clear and dirty buddies produces mixed blocks, which are 99 * reclassified when split. Over time, clear blocks become dominant, 100 * so clear allocations are typically satisfied from clear blocks, 101 * following a clear -> mixed -> dirty preference. 102 * 103 * 3) Selective clear on free: 104 * For each order examined, fully-clear blocks are preferred over 105 * mixed blocks, and mixed blocks are preferred over dirty blocks. 106 * If a clear or mixed block is found at an order, it is selected 107 * without searching higher orders. Dirty blocks are used only when 108 * no clear or mixed block exists at any eligible order. 109 */ 110 111 static u64 extent_size(struct gpu_dirty_extent *dirty_extent) 112 { 113 return dirty_extent->end - dirty_extent->start; 114 } 115 116 RB_DECLARE_CALLBACKS_MAX(static, gpu_dirty_augment_cb, 117 struct gpu_dirty_extent, rb, 118 u64, subtree_max_size, 119 extent_size) 120 121 static struct gpu_dirty_extent *extent_alloc(struct gpu_dirty_tracker *dirty_tracker) 122 { 123 return kmem_cache_alloc(slab_extents, GFP_KERNEL); 124 } 125 126 static void extent_free(struct gpu_dirty_tracker *dirty_tracker, 127 struct gpu_dirty_extent *dirty_extent) 128 { 129 kmem_cache_free(slab_extents, dirty_extent); 130 } 131 132 /* Return the rightmost extent whose start is strictly below @offset. */ 133 static struct gpu_dirty_extent * 134 prev_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset) 135 { 136 struct rb_node *rb = dirty_tracker->root.rb_node; 137 struct gpu_dirty_extent *dirty_extent = NULL; 138 139 while (rb) { 140 struct gpu_dirty_extent *tmp_extent = 141 rb_entry(rb, struct gpu_dirty_extent, rb); 142 143 if (tmp_extent->start < offset) { 144 dirty_extent = tmp_extent; 145 rb = rb->rb_right; 146 } else { 147 rb = rb->rb_left; 148 } 149 } 150 151 return dirty_extent; 152 } 153 154 /* Return the leftmost extent whose start is at or above @offset. */ 155 static struct gpu_dirty_extent * 156 next_extent(struct gpu_dirty_tracker *dirty_tracker, u64 offset) 157 { 158 struct rb_node *rb = dirty_tracker->root.rb_node; 159 struct gpu_dirty_extent *dirty_extent = NULL; 160 161 while (rb) { 162 struct gpu_dirty_extent *tmp_extent = 163 rb_entry(rb, struct gpu_dirty_extent, rb); 164 165 if (tmp_extent->start >= offset) { 166 dirty_extent = tmp_extent; 167 rb = rb->rb_left; 168 } else { 169 rb = rb->rb_right; 170 } 171 } 172 173 return dirty_extent; 174 } 175 176 static void insert_extent(struct gpu_dirty_tracker *dirty_tracker, 177 struct gpu_dirty_extent *dirty_extent) 178 { 179 struct rb_node **link = &dirty_tracker->root.rb_node; 180 struct rb_node *parent = NULL; 181 u64 size = extent_size(dirty_extent); 182 183 while (*link) { 184 struct gpu_dirty_extent *tmp_extent; 185 186 parent = *link; 187 tmp_extent = rb_entry(parent, struct gpu_dirty_extent, rb); 188 189 if (tmp_extent->subtree_max_size < size) 190 tmp_extent->subtree_max_size = size; 191 192 if (dirty_extent->start < tmp_extent->start) 193 link = &parent->rb_left; 194 else 195 link = &parent->rb_right; 196 } 197 198 dirty_extent->subtree_max_size = size; 199 rb_link_node(&dirty_extent->rb, parent, link); 200 rb_insert_augmented(&dirty_extent->rb, &dirty_tracker->root, &gpu_dirty_augment_cb); 201 } 202 203 static void remove_extent(struct gpu_dirty_tracker *dirty_tracker, 204 struct gpu_dirty_extent *dirty_extent) 205 { 206 rb_erase_augmented(&dirty_extent->rb, &dirty_tracker->root, &gpu_dirty_augment_cb); 207 RB_CLEAR_NODE(&dirty_extent->rb); 208 } 209 210 static void gpu_dirty_tracker_init(struct gpu_dirty_tracker *dirty_tracker) 211 { 212 dirty_tracker->root = RB_ROOT; 213 dirty_tracker->total_dirty = 0; 214 } 215 216 static void gpu_dirty_tracker_empty(struct gpu_dirty_tracker *dirty_tracker) 217 { 218 struct rb_node *rb; 219 220 while ((rb = rb_first(&dirty_tracker->root))) { 221 struct gpu_dirty_extent *dirty_extent = 222 rb_entry(rb, struct gpu_dirty_extent, rb); 223 224 remove_extent(dirty_tracker, dirty_extent); 225 extent_free(dirty_tracker, dirty_extent); 226 } 227 228 dirty_tracker->total_dirty = 0; 229 } 230 231 static void gpu_dirty_tracker_fini(struct gpu_dirty_tracker *dirty_tracker) 232 { 233 gpu_dirty_tracker_empty(dirty_tracker); 234 } 235 236 /* 237 * Mark the range [start, start + size] as dirty. Merge with the neighbour on 238 * each side if they are contiguous, so the tree never holds two adjacent ranges. 239 */ 240 static void gpu_dirty_tracker_mark_dirty(struct gpu_dirty_tracker *dirty_tracker, 241 u64 start, u64 size) 242 { 243 struct gpu_dirty_extent *left, *right, *dirty_extent; 244 u64 end = start + size; 245 246 gpu_buddy_assert(size); 247 248 /* Find contiguous neighbours, if any. */ 249 left = prev_extent(dirty_tracker, start); 250 if (left && left->end != start) 251 left = NULL; 252 253 right = next_extent(dirty_tracker, end); 254 if (right && right->start != end) 255 right = NULL; 256 257 if (left && right) { 258 /* Merge left + new + right into a single extent. */ 259 remove_extent(dirty_tracker, left); 260 remove_extent(dirty_tracker, right); 261 left->end = right->end; 262 extent_free(dirty_tracker, right); 263 insert_extent(dirty_tracker, left); 264 } else if (left) { 265 /* Extend left neighbour rightwards. */ 266 remove_extent(dirty_tracker, left); 267 left->end = end; 268 insert_extent(dirty_tracker, left); 269 } else if (right) { 270 /* Extend right neighbour leftwards. */ 271 remove_extent(dirty_tracker, right); 272 right->start = start; 273 insert_extent(dirty_tracker, right); 274 } else { 275 /* Standalone extent. */ 276 dirty_extent = extent_alloc(dirty_tracker); 277 if (!dirty_extent) { 278 pr_warn_once("dirty extent allocation failed, skipping tracker update\n"); 279 return; 280 } 281 dirty_extent->start = start; 282 dirty_extent->end = end; 283 insert_extent(dirty_tracker, dirty_extent); 284 } 285 286 dirty_tracker->total_dirty += size; 287 } 288 289 /* 290 * Remove the range [start, start + size] from the dirty tracker. Punch the 291 * range out of every overlapping dirty extent, splitting one extent in two if 292 * the removed range falls strictly inside it. 293 */ 294 static void gpu_dirty_tracker_remove_range(struct gpu_dirty_tracker *dirty_tracker, 295 u64 start, u64 size) 296 { 297 struct gpu_dirty_extent *dirty_extent, *next; 298 u64 end = start + size; 299 300 gpu_buddy_assert(size); 301 302 dirty_extent = prev_extent(dirty_tracker, start + 1); 303 if (!dirty_extent) 304 dirty_extent = next_extent(dirty_tracker, start); 305 306 while (dirty_extent && dirty_extent->start < end) { 307 struct rb_node *next_node = rb_next(&dirty_extent->rb); 308 u64 extent_start = dirty_extent->start; 309 u64 extent_end = dirty_extent->end; 310 311 if (next_node) 312 next = rb_entry(next_node, struct gpu_dirty_extent, rb); 313 else 314 next = NULL; 315 316 /* Skip a non-overlapping neighbour returned by prev_extent(). */ 317 if (extent_end <= start) { 318 dirty_extent = next; 319 continue; 320 } 321 322 if (extent_start < start && extent_end > end) { 323 /* 324 * Removed range lies strictly inside this dirty extent: 325 * split it into the dirty left and right halves. 326 */ 327 struct gpu_dirty_extent *right = extent_alloc(dirty_tracker); 328 329 if (!right) { 330 pr_warn_once("dirty extent allocation failed, skipping tracker update\n"); 331 dirty_extent = next; 332 continue; 333 } 334 335 remove_extent(dirty_tracker, dirty_extent); 336 337 dirty_extent->end = start; 338 right->start = end; 339 right->end = extent_end; 340 341 insert_extent(dirty_tracker, dirty_extent); 342 insert_extent(dirty_tracker, right); 343 344 dirty_tracker->total_dirty -= size; 345 } else if (extent_start >= start && extent_end <= end) { 346 /* Extent fully covered: drop it. */ 347 remove_extent(dirty_tracker, dirty_extent); 348 extent_free(dirty_tracker, dirty_extent); 349 350 dirty_tracker->total_dirty -= (extent_end - extent_start); 351 } else if (extent_start < start) { 352 /* Extent overlaps from the left: trim its right end. */ 353 remove_extent(dirty_tracker, dirty_extent); 354 dirty_extent->end = start; 355 insert_extent(dirty_tracker, dirty_extent); 356 357 dirty_tracker->total_dirty -= (extent_end - start); 358 } else { 359 /* Extent overlaps from the right: trim its left end. */ 360 remove_extent(dirty_tracker, dirty_extent); 361 dirty_extent->start = end; 362 insert_extent(dirty_tracker, dirty_extent); 363 364 dirty_tracker->total_dirty -= (end - extent_start); 365 } 366 367 dirty_extent = next; 368 } 369 } 370 371 static enum gpu_block_state 372 gpu_dirty_range_state(struct gpu_dirty_tracker *dirty_tracker, 373 u64 start, u64 size) 374 { 375 struct gpu_dirty_extent *dirty_extent; 376 u64 end = start + size; 377 378 dirty_extent = prev_extent(dirty_tracker, start + 1); 379 if (dirty_extent) { 380 if (dirty_extent->start <= start && dirty_extent->end >= end) 381 return GPU_BLOCK_DIRTY; 382 if (dirty_extent->start < end && dirty_extent->end > start) 383 return GPU_BLOCK_MIXED; 384 } 385 386 dirty_extent = next_extent(dirty_tracker, start); 387 if (dirty_extent && dirty_extent->start < end) 388 return GPU_BLOCK_MIXED; 389 390 return GPU_BLOCK_CLEAR; 391 } 392 393 static struct rb_node * 394 dirty_tracker_descend_right(struct rb_node *node, u64 min_size) 395 { 396 while (node->rb_right) { 397 struct gpu_dirty_extent *tmp_extent; 398 399 tmp_extent = rb_entry(node->rb_right, struct gpu_dirty_extent, rb); 400 401 if (tmp_extent->subtree_max_size < min_size) 402 break; 403 node = node->rb_right; 404 } 405 406 return node; 407 } 408 409 static struct gpu_dirty_extent * 410 gpu_dirty_tracker_find(struct gpu_dirty_tracker *dirty_tracker, 411 u64 min_size, u64 *aligned_start_out) 412 { 413 struct rb_node *rb = dirty_tracker->root.rb_node; 414 struct gpu_dirty_extent *root_extent; 415 struct rb_node *parent; 416 417 if (!min_size || !is_power_of_2(min_size)) 418 return NULL; 419 420 if (!rb) 421 return NULL; 422 423 root_extent = rb_entry(rb, struct gpu_dirty_extent, rb); 424 if (root_extent->subtree_max_size < min_size) 425 return NULL; 426 427 rb = dirty_tracker_descend_right(rb, min_size); 428 429 while (rb) { 430 struct gpu_dirty_extent *dirty_extent; 431 u64 aligned_start; 432 433 dirty_extent = rb_entry(rb, struct gpu_dirty_extent, rb); 434 aligned_start = ALIGN(dirty_extent->start, min_size); 435 436 /* Check if a min_size block fits after the alignment skip. */ 437 if (aligned_start <= dirty_extent->end && 438 dirty_extent->end - aligned_start >= min_size) { 439 *aligned_start_out = aligned_start; 440 return dirty_extent; 441 } 442 443 if (rb->rb_left) { 444 struct gpu_dirty_extent *tmp_extent; 445 446 tmp_extent = rb_entry(rb->rb_left, struct gpu_dirty_extent, rb); 447 if (tmp_extent->subtree_max_size >= min_size) { 448 rb = dirty_tracker_descend_right(rb->rb_left, min_size); 449 continue; 450 } 451 } 452 453 /* Walk up until we exit a node via its right child. */ 454 parent = rb_parent(rb); 455 while (parent && parent->rb_right != rb) { 456 rb = parent; 457 parent = rb_parent(rb); 458 } 459 rb = parent; 460 } 461 462 return NULL; 463 } 464 465 static unsigned int 466 gpu_buddy_block_state(struct gpu_buddy_block *block) 467 { 468 return block->header & GPU_BUDDY_HEADER_STATE; 469 } 470 471 static bool 472 gpu_buddy_block_is_allocated(struct gpu_buddy_block *block) 473 { 474 return gpu_buddy_block_state(block) == GPU_BUDDY_ALLOCATED; 475 } 476 477 static bool 478 gpu_buddy_block_is_split(struct gpu_buddy_block *block) 479 { 480 return gpu_buddy_block_state(block) == GPU_BUDDY_SPLIT; 481 } 482 483 static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block) 484 { 485 u64 offset = gpu_buddy_block_offset(block); 486 487 if (!offset) 488 /* 489 * __ffs64(0) is undefined; offset 0 is maximally aligned, so return 490 * a value greater than any possible alignment. 491 */ 492 return 64 + 1; 493 494 return __ffs64(offset); 495 } 496 497 static inline enum gpu_block_state 498 gpu_block_cached_state(struct gpu_buddy_block *block) 499 { 500 if (gpu_buddy_block_is_clear(block)) 501 return GPU_BLOCK_CLEAR; 502 if (block->has_clear) 503 return GPU_BLOCK_MIXED; 504 return GPU_BLOCK_DIRTY; 505 } 506 507 static inline void gpu_buddy_augment_compute(struct gpu_buddy_block *block) 508 { 509 enum gpu_block_state block_state; 510 struct gpu_buddy_block *right; 511 struct gpu_buddy_block *left; 512 unsigned int max_align; 513 514 max_align = gpu_buddy_block_offset_alignment(block); 515 block_state = gpu_block_cached_state(block); 516 517 left = rb_entry_safe(block->rb.rb_left, struct gpu_buddy_block, rb); 518 if (left) { 519 if (left->subtree_max_alignment > max_align) 520 max_align = left->subtree_max_alignment; 521 522 block_state = max(block_state, left->subtree_block_state); 523 } 524 525 right = rb_entry_safe(block->rb.rb_right, struct gpu_buddy_block, rb); 526 if (right) { 527 if (right->subtree_max_alignment > max_align) 528 max_align = right->subtree_max_alignment; 529 530 block_state = max(block_state, right->subtree_block_state); 531 } 532 533 block->subtree_max_alignment = max_align; 534 block->subtree_block_state = block_state; 535 } 536 537 static void gpu_buddy_augment_propagate(struct rb_node *rb, struct rb_node *stop) 538 { 539 while (rb != stop) { 540 struct gpu_buddy_block *block; 541 unsigned int old_align; 542 enum gpu_block_state old_block_state; 543 544 block = rb_entry(rb, struct gpu_buddy_block, rb); 545 old_align = block->subtree_max_alignment; 546 old_block_state = block->subtree_block_state; 547 548 gpu_buddy_augment_compute(block); 549 if (block->subtree_max_alignment == old_align && 550 block->subtree_block_state == old_block_state) 551 break; 552 553 rb = rb_parent(&block->rb); 554 } 555 } 556 557 static void gpu_buddy_augment_copy(struct rb_node *rb_old, struct rb_node *rb_new) 558 { 559 struct gpu_buddy_block *old; 560 struct gpu_buddy_block *new; 561 562 old = rb_entry(rb_old, struct gpu_buddy_block, rb); 563 new = rb_entry(rb_new, struct gpu_buddy_block, rb); 564 565 new->subtree_max_alignment = old->subtree_max_alignment; 566 new->subtree_block_state = old->subtree_block_state; 567 } 568 569 static void gpu_buddy_augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new) 570 { 571 struct gpu_buddy_block *old; 572 struct gpu_buddy_block *new; 573 574 old = rb_entry(rb_old, struct gpu_buddy_block, rb); 575 new = rb_entry(rb_new, struct gpu_buddy_block, rb); 576 577 new->subtree_max_alignment = old->subtree_max_alignment; 578 new->subtree_block_state = old->subtree_block_state; 579 580 gpu_buddy_augment_compute(old); 581 } 582 583 static const struct rb_augment_callbacks gpu_buddy_augment_cb = { 584 .propagate = gpu_buddy_augment_propagate, 585 .copy = gpu_buddy_augment_copy, 586 .rotate = gpu_buddy_augment_rotate, 587 }; 588 589 static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm, 590 struct gpu_buddy_block *parent, 591 unsigned int order, 592 u64 offset) 593 { 594 struct gpu_buddy_block *block; 595 596 BUG_ON(order > GPU_BUDDY_MAX_ORDER); 597 598 block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL); 599 if (!block) 600 return NULL; 601 602 block->header = offset; 603 block->header |= order; 604 block->parent = parent; 605 606 RB_CLEAR_NODE(&block->rb); 607 608 BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED); 609 return block; 610 } 611 612 static void gpu_block_free(struct gpu_buddy *mm, 613 struct gpu_buddy_block *block) 614 { 615 kmem_cache_free(slab_blocks, block); 616 } 617 618 static struct gpu_buddy_block * 619 rbtree_get_free_block(const struct rb_node *node) 620 { 621 return node ? rb_entry(node, struct gpu_buddy_block, rb) : NULL; 622 } 623 624 static struct gpu_buddy_block * 625 rbtree_last_free_block(struct rb_root *root) 626 { 627 return rbtree_get_free_block(rb_last(root)); 628 } 629 630 static struct gpu_buddy_block * 631 rbtree_last_clear_free_block(struct rb_root *root, 632 enum gpu_block_state min_block_state) 633 { 634 struct rb_node *node = root->rb_node; 635 struct gpu_buddy_block *block = NULL; 636 struct gpu_buddy_block *root_block; 637 enum gpu_block_state target_state; 638 639 root_block = rbtree_get_free_block(node); 640 if (!root_block || root_block->subtree_block_state < min_block_state) 641 return NULL; 642 643 target_state = root_block->subtree_block_state; 644 645 while (node) { 646 struct gpu_buddy_block *right_block; 647 struct gpu_buddy_block *node_block; 648 649 node_block = rbtree_get_free_block(node); 650 right_block = rbtree_get_free_block(node->rb_right); 651 652 if (right_block && right_block->subtree_block_state >= target_state) { 653 node = node->rb_right; 654 continue; 655 } 656 657 if (gpu_block_cached_state(node_block) == target_state) { 658 block = node_block; 659 break; 660 } 661 662 node = node->rb_left; 663 } 664 665 return block; 666 } 667 668 static void rbtree_insert(struct gpu_buddy *mm, 669 struct gpu_buddy_block *block) 670 { 671 struct rb_node **link, *parent = NULL; 672 enum gpu_block_state block_state; 673 struct gpu_buddy_block *node; 674 unsigned int block_alignment; 675 struct rb_root *root; 676 unsigned int order; 677 678 order = gpu_buddy_block_order(block); 679 block_alignment = gpu_buddy_block_offset_alignment(block); 680 block_state = gpu_block_cached_state(block); 681 682 root = &mm->free_tree[order]; 683 link = &root->rb_node; 684 685 while (*link) { 686 parent = *link; 687 node = rbtree_get_free_block(parent); 688 /* 689 * Manual augmentation update during insertion traversal. Required 690 * because rb_insert_augmented() only calls rotate callback during 691 * rotations. This ensures all ancestors on the insertion path have 692 * correct subtree_max_alignment / subtree_block_state values. 693 */ 694 if (node->subtree_max_alignment < block_alignment) 695 node->subtree_max_alignment = block_alignment; 696 if (node->subtree_block_state < block_state) 697 node->subtree_block_state = block_state; 698 699 if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node)) 700 link = &parent->rb_left; 701 else 702 link = &parent->rb_right; 703 } 704 705 block->subtree_max_alignment = block_alignment; 706 block->subtree_block_state = block_state; 707 rb_link_node(&block->rb, parent, link); 708 rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb); 709 } 710 711 static void rbtree_remove(struct gpu_buddy *mm, 712 struct gpu_buddy_block *block) 713 { 714 unsigned int order = gpu_buddy_block_order(block); 715 716 rb_erase_augmented(&block->rb, &mm->free_tree[order], &gpu_buddy_augment_cb); 717 RB_CLEAR_NODE(&block->rb); 718 } 719 720 static void mark_allocated(struct gpu_buddy *mm, 721 struct gpu_buddy_block *block) 722 { 723 block->header &= ~GPU_BUDDY_HEADER_STATE; 724 block->header |= GPU_BUDDY_ALLOCATED; 725 726 block->has_clear = false; 727 728 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 729 mm->used_scoreboard[gpu_buddy_block_order(block)]++; 730 731 rbtree_remove(mm, block); 732 } 733 734 static void __mark_free(struct gpu_buddy *mm, 735 struct gpu_buddy_block *block, 736 enum gpu_block_state block_state) 737 { 738 if (gpu_buddy_block_is_allocated(block)) 739 mm->used_scoreboard[gpu_buddy_block_order(block)]--; 740 741 block->header &= ~GPU_BUDDY_HEADER_STATE; 742 block->header |= GPU_BUDDY_FREE; 743 744 block->header &= ~GPU_BUDDY_HEADER_CLEAR; 745 746 block->has_clear = (block_state != GPU_BLOCK_DIRTY); 747 if (block_state == GPU_BLOCK_CLEAR) 748 block->header |= GPU_BUDDY_HEADER_CLEAR; 749 750 mm->free_scoreboard[gpu_buddy_block_order(block)]++; 751 752 rbtree_insert(mm, block); 753 } 754 755 static void mark_free(struct gpu_buddy *mm, 756 struct gpu_buddy_block *block) 757 { 758 enum gpu_block_state block_state; 759 760 block_state = gpu_dirty_range_state(&mm->dirty, 761 gpu_buddy_block_offset(block), 762 gpu_buddy_block_size(mm, block)); 763 __mark_free(mm, block, block_state); 764 } 765 766 static void mark_split(struct gpu_buddy *mm, 767 struct gpu_buddy_block *block) 768 { 769 block->header &= ~GPU_BUDDY_HEADER_STATE; 770 block->header |= GPU_BUDDY_SPLIT; 771 772 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 773 774 rbtree_remove(mm, block); 775 } 776 777 static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2) 778 { 779 return s1 <= e2 && e1 >= s2; 780 } 781 782 static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2) 783 { 784 return s1 <= s2 && e1 >= e2; 785 } 786 787 static struct gpu_buddy_block * 788 __get_buddy(struct gpu_buddy_block *block) 789 { 790 struct gpu_buddy_block *parent; 791 792 parent = block->parent; 793 if (!parent) 794 return NULL; 795 796 if (parent->left == block) 797 return parent->right; 798 799 return parent->left; 800 } 801 802 static unsigned int __gpu_buddy_free(struct gpu_buddy *mm, 803 struct gpu_buddy_block *block) 804 { 805 enum gpu_block_state block_state; 806 struct gpu_buddy_block *parent; 807 unsigned int order; 808 809 block_state = gpu_block_cached_state(block); 810 811 while ((parent = block->parent)) { 812 struct gpu_buddy_block *buddy = __get_buddy(block); 813 814 if (!gpu_buddy_block_is_free(buddy)) 815 break; 816 817 if (block_state != GPU_BLOCK_MIXED) { 818 enum gpu_block_state buddy_state; 819 820 buddy_state = gpu_block_cached_state(buddy); 821 822 if (buddy_state != block_state) 823 block_state = GPU_BLOCK_MIXED; 824 } 825 826 rbtree_remove(mm, buddy); 827 mm->free_scoreboard[gpu_buddy_block_order(buddy)]--; 828 829 if (gpu_buddy_block_is_allocated(block)) 830 mm->used_scoreboard[gpu_buddy_block_order(block)]--; 831 832 gpu_block_free(mm, block); 833 gpu_block_free(mm, buddy); 834 835 block = parent; 836 } 837 838 order = gpu_buddy_block_order(block); 839 __mark_free(mm, block, block_state); 840 841 return order; 842 } 843 844 /** 845 * gpu_buddy_init - init memory manager 846 * 847 * @mm: GPU buddy manager to initialize 848 * @size: size in bytes to manage 849 * @chunk_size: minimum page size in bytes for our allocations 850 * 851 * Initializes the memory manager and its resources. 852 * 853 * Returns: 854 * 0 on success, error code on failure. 855 */ 856 int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size) 857 { 858 unsigned int root_count = 0; 859 u64 offset = 0; 860 861 if (size < chunk_size) 862 return -EINVAL; 863 864 if (chunk_size < SZ_4K) 865 return -EINVAL; 866 867 if (!is_power_of_2(chunk_size)) 868 return -EINVAL; 869 870 size = round_down(size, chunk_size); 871 872 mm->size = size; 873 mm->avail = size; 874 mm->chunk_size = chunk_size; 875 mm->max_order = ilog2(size) - ilog2(chunk_size); 876 877 BUG_ON(mm->max_order > GPU_BUDDY_MAX_ORDER); 878 879 mm->free_scoreboard = kzalloc_objs(*mm->free_scoreboard, 880 mm->max_order + 1); 881 if (!mm->free_scoreboard) 882 return -ENOMEM; 883 884 mm->used_scoreboard = kzalloc_objs(*mm->used_scoreboard, 885 mm->max_order + 1); 886 if (!mm->used_scoreboard) 887 goto out_free_free_scoreboard; 888 889 mm->free_tree = kzalloc_objs(struct rb_root, mm->max_order + 1); 890 if (!mm->free_tree) 891 goto out_free_used_scoreboard; 892 893 gpu_dirty_tracker_init(&mm->dirty); 894 895 mm->n_roots = hweight64(size); 896 897 mm->roots = kmalloc_objs(struct gpu_buddy_block *, mm->n_roots); 898 if (!mm->roots) 899 goto out_free_tree; 900 901 /* 902 * Split into power-of-two blocks, in case we are given a size that is 903 * not itself a power-of-two. 904 */ 905 do { 906 struct gpu_buddy_block *root; 907 unsigned int order; 908 u64 root_size; 909 910 order = ilog2(size) - ilog2(chunk_size); 911 root_size = chunk_size << order; 912 913 root = gpu_block_alloc(mm, NULL, order, offset); 914 if (!root) 915 goto out_free_roots; 916 917 gpu_dirty_tracker_mark_dirty(&mm->dirty, offset, root_size); 918 __mark_free(mm, root, GPU_BLOCK_DIRTY); 919 920 BUG_ON(root_count > mm->max_order); 921 BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size); 922 923 mm->roots[root_count] = root; 924 925 offset += root_size; 926 size -= root_size; 927 root_count++; 928 } while (size); 929 930 #ifdef CONFIG_LOCKDEP 931 mm->lock_dep_map = NULL; 932 #endif 933 return 0; 934 935 out_free_roots: 936 while (root_count--) 937 gpu_block_free(mm, mm->roots[root_count]); 938 kfree(mm->roots); 939 out_free_tree: 940 gpu_dirty_tracker_fini(&mm->dirty); 941 kfree(mm->free_tree); 942 out_free_used_scoreboard: 943 kfree(mm->used_scoreboard); 944 out_free_free_scoreboard: 945 kfree(mm->free_scoreboard); 946 return -ENOMEM; 947 } 948 EXPORT_SYMBOL(gpu_buddy_init); 949 950 /** 951 * gpu_buddy_fini - tear down the memory manager 952 * 953 * @mm: GPU buddy manager to free 954 * 955 * Cleanup memory manager resources and the freetree 956 */ 957 void gpu_buddy_fini(struct gpu_buddy *mm) 958 { 959 u64 root_size, size; 960 unsigned int order; 961 int i; 962 963 size = mm->size; 964 965 for (i = 0; i < mm->n_roots; ++i) { 966 order = ilog2(size) - ilog2(mm->chunk_size); 967 root_size = mm->chunk_size << order; 968 969 gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i])); 970 gpu_block_free(mm, mm->roots[i]); 971 size -= root_size; 972 } 973 974 gpu_buddy_assert(mm->avail == mm->size); 975 976 for (i = 0; i <= mm->max_order; ++i) 977 gpu_buddy_assert(!mm->used_scoreboard[i]); 978 979 gpu_dirty_tracker_fini(&mm->dirty); 980 kfree(mm->free_tree); 981 kfree(mm->roots); 982 kfree(mm->free_scoreboard); 983 kfree(mm->used_scoreboard); 984 } 985 EXPORT_SYMBOL(gpu_buddy_fini); 986 987 static int split_block(struct gpu_buddy *mm, 988 struct gpu_buddy_block *block) 989 { 990 unsigned int block_order = gpu_buddy_block_order(block) - 1; 991 u64 offset = gpu_buddy_block_offset(block); 992 enum gpu_block_state parent_state; 993 994 BUG_ON(!gpu_buddy_block_is_free(block)); 995 BUG_ON(!gpu_buddy_block_order(block)); 996 997 block->left = gpu_block_alloc(mm, block, block_order, offset); 998 if (!block->left) 999 return -ENOMEM; 1000 1001 block->right = gpu_block_alloc(mm, block, block_order, 1002 offset + (mm->chunk_size << block_order)); 1003 if (!block->right) { 1004 gpu_block_free(mm, block->left); 1005 return -ENOMEM; 1006 } 1007 1008 parent_state = gpu_block_cached_state(block); 1009 1010 mark_split(mm, block); 1011 1012 if (parent_state == GPU_BLOCK_MIXED) { 1013 mark_free(mm, block->left); 1014 mark_free(mm, block->right); 1015 } else { 1016 __mark_free(mm, block->left, parent_state); 1017 __mark_free(mm, block->right, parent_state); 1018 } 1019 1020 return 0; 1021 } 1022 1023 /** 1024 * gpu_buddy_reset_clear - reset blocks clear state 1025 * 1026 * @mm: GPU buddy manager 1027 * @is_clear: blocks clear state 1028 * 1029 * Reset the clear state based on @is_clear value for each block 1030 * in the freetree. 1031 */ 1032 void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear) 1033 { 1034 unsigned int i; 1035 1036 gpu_buddy_driver_lock_held(mm); 1037 1038 gpu_dirty_tracker_empty(&mm->dirty); 1039 1040 for (i = 0; i <= mm->max_order; ++i) { 1041 struct gpu_buddy_block *block, *tmp; 1042 1043 rbtree_postorder_for_each_entry_safe(block, tmp, 1044 &mm->free_tree[i], rb) { 1045 if (is_clear) { 1046 if (!gpu_buddy_block_is_clear(block)) 1047 block->header |= GPU_BUDDY_HEADER_CLEAR; 1048 block->has_clear = true; 1049 } else { 1050 block->header &= ~GPU_BUDDY_HEADER_CLEAR; 1051 block->has_clear = false; 1052 gpu_dirty_tracker_mark_dirty(&mm->dirty, 1053 gpu_buddy_block_offset(block), 1054 gpu_buddy_block_size(mm, block)); 1055 } 1056 1057 gpu_buddy_augment_compute(block); 1058 } 1059 } 1060 } 1061 EXPORT_SYMBOL(gpu_buddy_reset_clear); 1062 1063 static void __gpu_buddy_free_block_internal(struct gpu_buddy *mm, 1064 struct gpu_buddy_block *block) 1065 { 1066 u64 size = gpu_buddy_block_size(mm, block); 1067 1068 gpu_buddy_driver_lock_held(mm); 1069 BUG_ON(!gpu_buddy_block_is_allocated(block)); 1070 1071 mm->avail += size; 1072 __gpu_buddy_free(mm, block); 1073 } 1074 1075 /** 1076 * gpu_buddy_free_block - free a block 1077 * 1078 * @mm: GPU buddy manager 1079 * @block: block to be freed 1080 */ 1081 void gpu_buddy_free_block(struct gpu_buddy *mm, 1082 struct gpu_buddy_block *block) 1083 { 1084 if (!gpu_buddy_block_is_clear(block)) 1085 gpu_dirty_tracker_mark_dirty(&mm->dirty, 1086 gpu_buddy_block_offset(block), 1087 gpu_buddy_block_size(mm, block)); 1088 1089 __gpu_buddy_free_block_internal(mm, block); 1090 } 1091 EXPORT_SYMBOL(gpu_buddy_free_block); 1092 1093 /** 1094 * gpu_buddy_allocated_addr_to_block - given relative address find the allocated block 1095 * 1096 * @mm: GPU buddy manager 1097 * @addr: Relative address 1098 * 1099 * Returns: 1100 * gpu_buddy_block on success, NULL or error code on failure 1101 */ 1102 struct gpu_buddy_block *gpu_buddy_allocated_addr_to_block(struct gpu_buddy *mm, u64 addr) 1103 { 1104 struct gpu_buddy_block *block; 1105 LIST_HEAD(dfs); 1106 u64 end; 1107 int i; 1108 1109 gpu_buddy_driver_lock_held(mm); 1110 1111 end = addr + mm->chunk_size - 1; 1112 for (i = 0; i < mm->n_roots; ++i) 1113 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 1114 1115 do { 1116 u64 block_start; 1117 u64 block_end; 1118 1119 block = list_first_entry_or_null(&dfs, 1120 struct gpu_buddy_block, 1121 tmp_link); 1122 if (!block) 1123 break; 1124 1125 list_del(&block->tmp_link); 1126 1127 block_start = gpu_buddy_block_offset(block); 1128 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 1129 1130 if (!overlaps(addr, end, block_start, block_end)) 1131 continue; 1132 1133 if (gpu_buddy_block_is_allocated(block)) 1134 return block; 1135 else if (gpu_buddy_block_is_free(block)) 1136 return NULL; 1137 1138 list_add(&block->right->tmp_link, &dfs); 1139 list_add(&block->left->tmp_link, &dfs); 1140 } while (1); 1141 1142 return ERR_PTR(-ENXIO); 1143 } 1144 EXPORT_SYMBOL(gpu_buddy_allocated_addr_to_block); 1145 1146 static void __gpu_buddy_free_list(struct gpu_buddy *mm, 1147 struct list_head *objects, 1148 bool mark_clear, 1149 bool mark_dirty) 1150 { 1151 struct gpu_buddy_block *block, *on; 1152 u64 dirty_start = 0, dirty_size = 0; 1153 1154 gpu_buddy_assert(!(mark_dirty && mark_clear)); 1155 1156 list_for_each_entry_safe(block, on, objects, link) { 1157 u64 offset = gpu_buddy_block_offset(block); 1158 u64 size = gpu_buddy_block_size(mm, block); 1159 1160 if (mark_clear) 1161 block->header |= GPU_BUDDY_HEADER_CLEAR; 1162 else if (mark_dirty) 1163 block->header &= ~GPU_BUDDY_HEADER_CLEAR; 1164 1165 /* 1166 * Coalesce contiguous dirty blocks into one extent update so 1167 * a multi-block contiguous free costs a single mark_dirty(). 1168 * Flush the pending extent and start over on a gap. 1169 */ 1170 if (!gpu_buddy_block_is_clear(block)) { 1171 if (dirty_size && 1172 (dirty_start + dirty_size == offset || 1173 offset + size == dirty_start)) { 1174 dirty_start = min(dirty_start, offset); 1175 dirty_size += size; 1176 } else { 1177 if (dirty_size) 1178 gpu_dirty_tracker_mark_dirty(&mm->dirty, 1179 dirty_start, 1180 dirty_size); 1181 dirty_start = offset; 1182 dirty_size = size; 1183 } 1184 } 1185 1186 __gpu_buddy_free_block_internal(mm, block); 1187 cond_resched(); 1188 } 1189 1190 if (dirty_size) 1191 gpu_dirty_tracker_mark_dirty(&mm->dirty, dirty_start, dirty_size); 1192 1193 INIT_LIST_HEAD(objects); 1194 } 1195 1196 static void gpu_buddy_free_list_internal(struct gpu_buddy *mm, 1197 struct list_head *objects) 1198 { 1199 /* 1200 * Don't touch the clear/dirty bit, since allocation is still internal 1201 * at this point. For example we might have just failed part of the 1202 * allocation. 1203 */ 1204 __gpu_buddy_free_list(mm, objects, false, false); 1205 } 1206 1207 /** 1208 * gpu_buddy_free_list - free blocks 1209 * 1210 * @mm: GPU buddy manager 1211 * @objects: input list head to free blocks 1212 * @flags: optional flags like GPU_BUDDY_CLEARED 1213 */ 1214 void gpu_buddy_free_list(struct gpu_buddy *mm, 1215 struct list_head *objects, 1216 unsigned int flags) 1217 { 1218 bool mark_clear = flags & GPU_BUDDY_CLEARED; 1219 1220 gpu_buddy_driver_lock_held(mm); 1221 __gpu_buddy_free_list(mm, objects, mark_clear, !mark_clear); 1222 } 1223 EXPORT_SYMBOL(gpu_buddy_free_list); 1224 1225 static void __gpu_buddy_undo_splits(struct gpu_buddy *mm, 1226 struct gpu_buddy_block *block) 1227 { 1228 struct gpu_buddy_block *buddy = __get_buddy(block); 1229 1230 if (buddy && 1231 (gpu_buddy_block_is_free(block) && 1232 gpu_buddy_block_is_free(buddy))) { 1233 rbtree_remove(mm, block); 1234 mm->free_scoreboard[gpu_buddy_block_order(block)]--; 1235 __gpu_buddy_free(mm, block); 1236 } 1237 } 1238 1239 static struct gpu_buddy_block * 1240 __alloc_range_bias(struct gpu_buddy *mm, 1241 u64 start, u64 end, 1242 unsigned int order, 1243 unsigned long flags) 1244 { 1245 u64 req_size = mm->chunk_size << order; 1246 struct gpu_buddy_block *block; 1247 LIST_HEAD(dfs); 1248 int err; 1249 int i; 1250 1251 end = end - 1; 1252 1253 /* 1254 * This range-constrained search hands back the highest/right-most 1255 * address that satisfies the request: the roots are seeded high-to-low 1256 * and the right (higher-address) child is descended first, making 1257 * top-down the default placement here. A non-top-down clear request is 1258 * the only exception, where the descent is biased towards clear or 1259 * clear-containing subtrees to satisfy the clear preference. 1260 */ 1261 for (i = mm->n_roots - 1; i >= 0; --i) 1262 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 1263 1264 do { 1265 u64 block_start; 1266 u64 block_end; 1267 1268 block = list_first_entry_or_null(&dfs, 1269 struct gpu_buddy_block, 1270 tmp_link); 1271 if (!block) 1272 break; 1273 1274 list_del(&block->tmp_link); 1275 1276 if (gpu_buddy_block_order(block) < order) 1277 continue; 1278 1279 block_start = gpu_buddy_block_offset(block); 1280 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 1281 1282 if (!overlaps(start, end, block_start, block_end)) 1283 continue; 1284 1285 if (gpu_buddy_block_is_allocated(block)) 1286 continue; 1287 1288 if (block_start < start || block_end > end) { 1289 u64 adjusted_start = max(block_start, start); 1290 u64 adjusted_end = min(block_end, end); 1291 1292 if (round_down(adjusted_end + 1, req_size) <= 1293 round_up(adjusted_start, req_size)) 1294 continue; 1295 } 1296 1297 if (contains(start, end, block_start, block_end) && 1298 order == gpu_buddy_block_order(block)) { 1299 /* 1300 * Find the free block within the range. 1301 */ 1302 if (gpu_buddy_block_is_free(block)) 1303 return block; 1304 1305 continue; 1306 } 1307 1308 if (!gpu_buddy_block_is_split(block)) { 1309 err = split_block(mm, block); 1310 if (unlikely(err)) 1311 goto err_undo; 1312 } 1313 1314 /* 1315 * Top-down is a strict address-placement policy, so when it is 1316 * requested we ignore clear steering and simply descend the 1317 * right (higher-address) child first. Only a non-top-down clear 1318 * request biases the descent towards clear/has_clear subtrees. 1319 */ 1320 if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) && 1321 !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) { 1322 struct gpu_buddy_block *prefer; 1323 1324 if (gpu_buddy_block_is_clear(block->right)) 1325 prefer = block->right; 1326 else if (gpu_buddy_block_is_clear(block->left)) 1327 prefer = block->left; 1328 else if (block->right->has_clear) 1329 prefer = block->right; 1330 else if (block->left->has_clear) 1331 prefer = block->left; 1332 else 1333 prefer = block->right; 1334 1335 if (prefer == block->right) { 1336 list_add(&block->left->tmp_link, &dfs); 1337 list_add(&block->right->tmp_link, &dfs); 1338 } else { 1339 list_add(&block->right->tmp_link, &dfs); 1340 list_add(&block->left->tmp_link, &dfs); 1341 } 1342 } else { 1343 list_add(&block->left->tmp_link, &dfs); 1344 list_add(&block->right->tmp_link, &dfs); 1345 } 1346 } while (1); 1347 1348 return ERR_PTR(-ENOSPC); 1349 1350 err_undo: 1351 /* 1352 * We really don't want to leave around a bunch of split blocks, since 1353 * bigger is better, so make sure we merge everything back before we 1354 * free the allocated blocks. 1355 */ 1356 __gpu_buddy_undo_splits(mm, block); 1357 return ERR_PTR(err); 1358 } 1359 1360 /* Return the highest-address free block of at least @order. */ 1361 static struct gpu_buddy_block * 1362 get_maxblock(struct gpu_buddy *mm, 1363 unsigned int order) 1364 { 1365 struct gpu_buddy_block *max_block; 1366 struct gpu_buddy_block *block; 1367 unsigned int i; 1368 1369 /* 1370 * Top-down allocation is a strict address-placement policy: the block 1371 * is chosen purely by offset, regardless of its clear/dirty state. 1372 * Clear state is re-derived from the dirty tracker once the allocation 1373 * completes, and the driver is responsible for issuing the clear pass 1374 * if a clear region is required. 1375 */ 1376 max_block = NULL; 1377 1378 for (i = order; i <= mm->max_order; ++i) { 1379 block = rbtree_last_free_block(&mm->free_tree[i]); 1380 if (!block) 1381 continue; 1382 1383 if (!max_block || 1384 gpu_buddy_block_offset(block) > gpu_buddy_block_offset(max_block)) 1385 max_block = block; 1386 } 1387 1388 return max_block; 1389 } 1390 1391 static struct gpu_buddy_block * 1392 alloc_from_freetree(struct gpu_buddy *mm, 1393 unsigned int order, 1394 unsigned long flags) 1395 { 1396 struct gpu_buddy_block *block = NULL; 1397 unsigned int tmp; 1398 int err; 1399 1400 if (flags & GPU_BUDDY_TOPDOWN_ALLOCATION) { 1401 block = get_maxblock(mm, order); 1402 if (block) 1403 tmp = gpu_buddy_block_order(block); 1404 } else { 1405 if (flags & GPU_BUDDY_CLEAR_ALLOCATION) { 1406 for (tmp = order; tmp <= mm->max_order; ++tmp) { 1407 block = rbtree_last_clear_free_block(&mm->free_tree[tmp], 1408 GPU_BLOCK_MIXED); 1409 if (block) 1410 break; 1411 } 1412 } 1413 if (!block) { 1414 for (tmp = order; tmp <= mm->max_order; ++tmp) { 1415 block = rbtree_last_free_block(&mm->free_tree[tmp]); 1416 if (block) 1417 break; 1418 } 1419 } 1420 } 1421 1422 if (!block) 1423 return ERR_PTR(-ENOSPC); 1424 1425 BUG_ON(!gpu_buddy_block_is_free(block)); 1426 1427 while (tmp != order) { 1428 err = split_block(mm, block); 1429 if (unlikely(err)) 1430 goto err_undo; 1431 1432 if ((flags & GPU_BUDDY_CLEAR_ALLOCATION) && 1433 !(flags & GPU_BUDDY_TOPDOWN_ALLOCATION)) { 1434 bool right_clear, left_clear; 1435 1436 right_clear = gpu_buddy_block_is_clear(block->right); 1437 left_clear = gpu_buddy_block_is_clear(block->left); 1438 1439 if (right_clear) 1440 block = block->right; 1441 else if (left_clear) 1442 block = block->left; 1443 else if (block->right->has_clear) 1444 block = block->right; 1445 else if (block->left->has_clear) 1446 block = block->left; 1447 else 1448 block = block->right; 1449 } else { 1450 block = block->right; 1451 } 1452 tmp--; 1453 } 1454 return block; 1455 1456 err_undo: 1457 __gpu_buddy_undo_splits(mm, block); 1458 return ERR_PTR(err); 1459 } 1460 1461 static bool 1462 gpu_buddy_can_offset_align(u64 size, u64 min_block_size) 1463 { 1464 return size < min_block_size && is_power_of_2(size); 1465 } 1466 1467 static bool gpu_buddy_subtree_can_satisfy(struct rb_node *node, 1468 unsigned int alignment) 1469 { 1470 struct gpu_buddy_block *block; 1471 1472 block = rbtree_get_free_block(node); 1473 return block->subtree_max_alignment >= alignment; 1474 } 1475 1476 static struct gpu_buddy_block * 1477 gpu_buddy_find_block_aligned(struct gpu_buddy *mm, 1478 unsigned int order, 1479 unsigned int alignment) 1480 { 1481 struct rb_root *root = &mm->free_tree[order]; 1482 struct rb_node *rb = root->rb_node; 1483 1484 while (rb) { 1485 struct gpu_buddy_block *block = rbtree_get_free_block(rb); 1486 struct rb_node *left_node = rb->rb_left, *right_node = rb->rb_right; 1487 1488 if (right_node) { 1489 if (gpu_buddy_subtree_can_satisfy(right_node, alignment)) { 1490 rb = right_node; 1491 continue; 1492 } 1493 } 1494 1495 if (gpu_buddy_block_offset_alignment(block) >= alignment) 1496 return block; 1497 1498 if (left_node) { 1499 if (gpu_buddy_subtree_can_satisfy(left_node, alignment)) { 1500 rb = left_node; 1501 continue; 1502 } 1503 } 1504 1505 break; 1506 } 1507 1508 return NULL; 1509 } 1510 1511 static struct gpu_buddy_block * 1512 gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm, 1513 u64 size, 1514 u64 min_block_size) 1515 { 1516 struct gpu_buddy_block *block = NULL; 1517 unsigned int order, tmp, alignment; 1518 unsigned long pages; 1519 int err; 1520 1521 alignment = ilog2(min_block_size); 1522 pages = size >> ilog2(mm->chunk_size); 1523 order = fls(pages) - 1; 1524 1525 /* 1526 * Offset-aligned allocation is a strict address-placement policy: the 1527 * block is chosen purely by its offset alignment, regardless of its 1528 * clear/dirty state. Clear state is re-derived from the dirty tracker 1529 * once the allocation completes, and the driver is responsible for 1530 * issuing the clear pass if a clear region is required. 1531 */ 1532 for (tmp = order; tmp <= mm->max_order; ++tmp) { 1533 block = gpu_buddy_find_block_aligned(mm, tmp, alignment); 1534 if (block) 1535 break; 1536 } 1537 1538 if (!block) 1539 return ERR_PTR(-ENOSPC); 1540 1541 while (gpu_buddy_block_order(block) > order) { 1542 struct gpu_buddy_block *left, *right; 1543 1544 err = split_block(mm, block); 1545 if (unlikely(err)) 1546 goto err_undo; 1547 1548 left = block->left; 1549 right = block->right; 1550 1551 if (gpu_buddy_block_offset_alignment(right) >= alignment) 1552 block = right; 1553 else 1554 block = left; 1555 } 1556 1557 return block; 1558 1559 err_undo: 1560 /* 1561 * We really don't want to leave around a bunch of split blocks, since 1562 * bigger is better, so make sure we merge everything back before we 1563 * free the allocated blocks. 1564 */ 1565 __gpu_buddy_undo_splits(mm, block); 1566 return ERR_PTR(err); 1567 } 1568 1569 static int __alloc_range(struct gpu_buddy *mm, 1570 struct list_head *dfs, 1571 u64 start, u64 size, 1572 unsigned long flags, 1573 struct list_head *blocks, 1574 u64 *total_allocated_on_err) 1575 { 1576 struct gpu_buddy_block *block; 1577 u64 total_allocated = 0; 1578 LIST_HEAD(allocated); 1579 u64 end; 1580 int err; 1581 1582 end = start + size - 1; 1583 1584 do { 1585 u64 block_start; 1586 u64 block_end; 1587 1588 block = list_first_entry_or_null(dfs, 1589 struct gpu_buddy_block, 1590 tmp_link); 1591 if (!block) 1592 break; 1593 1594 list_del(&block->tmp_link); 1595 1596 block_start = gpu_buddy_block_offset(block); 1597 block_end = block_start + gpu_buddy_block_size(mm, block) - 1; 1598 1599 if (!overlaps(start, end, block_start, block_end)) 1600 continue; 1601 1602 if (gpu_buddy_block_is_allocated(block)) { 1603 err = -ENOSPC; 1604 goto err_free; 1605 } 1606 1607 if (contains(start, end, block_start, block_end)) { 1608 if (gpu_buddy_block_is_free(block)) { 1609 u64 block_offset; 1610 u64 block_size; 1611 1612 block_size = gpu_buddy_block_size(mm, block); 1613 block_offset = gpu_buddy_block_offset(block); 1614 1615 if (!gpu_buddy_block_is_clear(block)) 1616 gpu_dirty_tracker_remove_range(&mm->dirty, 1617 block_offset, 1618 block_size); 1619 1620 mark_allocated(mm, block); 1621 total_allocated += block_size; 1622 mm->avail -= block_size; 1623 1624 list_add_tail(&block->link, &allocated); 1625 continue; 1626 } 1627 } 1628 1629 if (!gpu_buddy_block_is_split(block)) { 1630 err = split_block(mm, block); 1631 if (unlikely(err)) 1632 goto err_undo; 1633 } 1634 1635 list_add(&block->right->tmp_link, dfs); 1636 list_add(&block->left->tmp_link, dfs); 1637 } while (1); 1638 1639 if (total_allocated < size) { 1640 err = -ENOSPC; 1641 goto err_free; 1642 } 1643 1644 list_splice_tail(&allocated, blocks); 1645 1646 return 0; 1647 1648 err_undo: 1649 /* 1650 * We really don't want to leave around a bunch of split blocks, since 1651 * bigger is better, so make sure we merge everything back before we 1652 * free the allocated blocks. 1653 */ 1654 __gpu_buddy_undo_splits(mm, block); 1655 1656 err_free: 1657 if (err == -ENOSPC && total_allocated_on_err) { 1658 list_splice_tail(&allocated, blocks); 1659 *total_allocated_on_err = total_allocated; 1660 } else { 1661 gpu_buddy_free_list_internal(mm, &allocated); 1662 } 1663 1664 return err; 1665 } 1666 1667 static int __gpu_buddy_alloc_range(struct gpu_buddy *mm, 1668 u64 start, 1669 u64 size, 1670 unsigned long flags, 1671 u64 *total_allocated_on_err, 1672 struct list_head *blocks) 1673 { 1674 LIST_HEAD(dfs); 1675 int i; 1676 1677 for (i = 0; i < mm->n_roots; ++i) 1678 list_add_tail(&mm->roots[i]->tmp_link, &dfs); 1679 1680 return __alloc_range(mm, &dfs, start, size, flags, 1681 blocks, total_allocated_on_err); 1682 } 1683 1684 static int __alloc_contig_aligned_retry(struct gpu_buddy *mm, 1685 u64 unaligned_offset, 1686 u64 size, 1687 u64 min_block_size, 1688 unsigned long flags, 1689 struct list_head *blocks) 1690 { 1691 u64 aligned_offset = round_down(unaligned_offset, min_block_size); 1692 1693 return __gpu_buddy_alloc_range(mm, aligned_offset, size, flags, 1694 NULL, blocks); 1695 } 1696 1697 static int __alloc_contig_try_harder(struct gpu_buddy *mm, 1698 u64 size, 1699 u64 min_block_size, 1700 unsigned long flags, 1701 struct list_head *blocks) 1702 { 1703 u64 rhs_offset, lhs_offset, filled; 1704 struct gpu_buddy_block *block; 1705 struct rb_root *root; 1706 struct rb_node *iter; 1707 unsigned long pages; 1708 unsigned int order; 1709 u64 modify_size; 1710 int err; 1711 1712 modify_size = rounddown_pow_of_two(size); 1713 pages = modify_size >> ilog2(mm->chunk_size); 1714 order = fls(pages) - 1; 1715 if (order == 0) 1716 return -ENOSPC; 1717 1718 root = &mm->free_tree[order]; 1719 if (RB_EMPTY_ROOT(root)) 1720 return -ENOSPC; 1721 1722 iter = rb_last(root); 1723 while (iter) { 1724 block = rbtree_get_free_block(iter); 1725 1726 rhs_offset = gpu_buddy_block_offset(block); 1727 1728 /* Allocate blocks traversing RHS */ 1729 err = __gpu_buddy_alloc_range(mm, rhs_offset, size, 1730 flags, &filled, blocks); 1731 if (err && err != -ENOSPC) 1732 return err; 1733 if (!err && IS_ALIGNED(rhs_offset, min_block_size)) 1734 return 0; 1735 if (!err) { 1736 /* Allocate the unaligned RHS offset using round_down */ 1737 gpu_buddy_free_list_internal(mm, blocks); 1738 err = __alloc_contig_aligned_retry(mm, rhs_offset, 1739 size, 1740 min_block_size, 1741 flags, blocks); 1742 if (!err) 1743 return 0; 1744 if (err != -ENOSPC) { 1745 gpu_buddy_free_list_internal(mm, blocks); 1746 return err; 1747 } 1748 goto next; 1749 } 1750 1751 if (size - filled > rhs_offset) 1752 goto next; 1753 1754 lhs_offset = rhs_offset - (size - filled); 1755 1756 /* Allocate the unaligned LHS offset using round_down */ 1757 gpu_buddy_free_list_internal(mm, blocks); 1758 err = __alloc_contig_aligned_retry(mm, lhs_offset, 1759 size, 1760 min_block_size, 1761 flags, blocks); 1762 if (!err) 1763 return 0; 1764 if (err != -ENOSPC) { 1765 gpu_buddy_free_list_internal(mm, blocks); 1766 return err; 1767 } 1768 next: 1769 gpu_buddy_free_list_internal(mm, blocks); 1770 iter = rb_prev(iter); 1771 } 1772 1773 return -ENOSPC; 1774 } 1775 1776 /** 1777 * gpu_buddy_block_trim - free unused pages 1778 * 1779 * @mm: GPU buddy manager 1780 * @start: start address to begin the trimming. 1781 * @new_size: original size requested 1782 * @blocks: Input and output list of allocated blocks. 1783 * MUST contain single block as input to be trimmed. 1784 * On success will contain the newly allocated blocks 1785 * making up the @new_size. Blocks always appear in 1786 * ascending order 1787 * 1788 * For contiguous allocation, we round up the size to the nearest 1789 * power of two value, drivers consume *actual* size, so remaining 1790 * portions are unused and can be optionally freed with this function 1791 * 1792 * Returns: 1793 * 0 on success, error code on failure. 1794 */ 1795 int gpu_buddy_block_trim(struct gpu_buddy *mm, 1796 u64 *start, 1797 u64 new_size, 1798 struct list_head *blocks) 1799 { 1800 struct gpu_buddy_block *parent; 1801 struct gpu_buddy_block *block; 1802 u64 block_start, block_end; 1803 LIST_HEAD(dfs); 1804 bool was_clear; 1805 u64 new_start; 1806 int err; 1807 1808 gpu_buddy_driver_lock_held(mm); 1809 1810 if (!list_is_singular(blocks)) 1811 return -EINVAL; 1812 1813 block = list_first_entry(blocks, 1814 struct gpu_buddy_block, 1815 link); 1816 1817 block_start = gpu_buddy_block_offset(block); 1818 block_end = block_start + gpu_buddy_block_size(mm, block); 1819 1820 if (WARN_ON(!gpu_buddy_block_is_allocated(block))) 1821 return -EINVAL; 1822 1823 if (new_size > gpu_buddy_block_size(mm, block)) 1824 return -EINVAL; 1825 1826 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size)) 1827 return -EINVAL; 1828 1829 if (new_size == gpu_buddy_block_size(mm, block)) 1830 return 0; 1831 1832 new_start = block_start; 1833 if (start) { 1834 new_start = *start; 1835 1836 if (new_start < block_start) 1837 return -EINVAL; 1838 1839 if (!IS_ALIGNED(new_start, mm->chunk_size)) 1840 return -EINVAL; 1841 1842 if (range_overflows(new_start, new_size, block_end)) 1843 return -EINVAL; 1844 } 1845 1846 list_del(&block->link); 1847 1848 was_clear = gpu_buddy_block_is_clear(block); 1849 1850 if (!was_clear) 1851 gpu_dirty_tracker_mark_dirty(&mm->dirty, 1852 gpu_buddy_block_offset(block), 1853 gpu_buddy_block_size(mm, block)); 1854 1855 __mark_free(mm, block, was_clear ? GPU_BLOCK_CLEAR : GPU_BLOCK_DIRTY); 1856 mm->avail += gpu_buddy_block_size(mm, block); 1857 1858 /* Prevent recursively freeing this node */ 1859 parent = block->parent; 1860 block->parent = NULL; 1861 1862 list_add(&block->tmp_link, &dfs); 1863 err = __alloc_range(mm, &dfs, new_start, new_size, 1864 was_clear ? GPU_BUDDY_CLEAR_ALLOCATION : 0, 1865 blocks, NULL); 1866 if (err) { 1867 mark_allocated(mm, block); 1868 mm->avail -= gpu_buddy_block_size(mm, block); 1869 if (!was_clear) { 1870 gpu_dirty_tracker_remove_range(&mm->dirty, 1871 gpu_buddy_block_offset(block), 1872 gpu_buddy_block_size(mm, block)); 1873 } 1874 if (was_clear) 1875 block->header |= GPU_BUDDY_HEADER_CLEAR; 1876 list_add(&block->link, blocks); 1877 } 1878 1879 block->parent = parent; 1880 return err; 1881 } 1882 EXPORT_SYMBOL(gpu_buddy_block_trim); 1883 1884 static bool dirty_steer_window(struct gpu_buddy *mm, u64 req_size, 1885 u64 *start, u64 *end, unsigned long *flags) 1886 { 1887 u64 aligned_start; 1888 struct gpu_dirty_extent *ext = 1889 gpu_dirty_tracker_find(&mm->dirty, req_size, &aligned_start); 1890 1891 if (!ext) 1892 return false; 1893 1894 *start = aligned_start; 1895 *end = ext->end; 1896 *flags |= GPU_BUDDY_RANGE_ALLOCATION; 1897 return true; 1898 } 1899 1900 static struct gpu_buddy_block * 1901 __gpu_buddy_alloc_blocks(struct gpu_buddy *mm, 1902 u64 start, u64 end, 1903 u64 size, u64 min_block_size, 1904 unsigned int order, 1905 unsigned long flags) 1906 { 1907 struct gpu_buddy_block *block; 1908 bool steered = false; 1909 1910 /* Allocate from dirty tracker */ 1911 if (!(flags & GPU_BUDDY_RANGE_ALLOCATION) && 1912 !(flags & GPU_BUDDY_CLEAR_ALLOCATION) && 1913 size >= min_block_size && 1914 gpu_buddy_clear_avail(mm) && mm->dirty.total_dirty) { 1915 u64 block_size = mm->chunk_size << order; 1916 1917 steered = dirty_steer_window(mm, block_size, 1918 &start, &end, &flags); 1919 } 1920 1921 if (flags & GPU_BUDDY_RANGE_ALLOCATION) { 1922 /* Allocate traversing within the range */ 1923 block = __alloc_range_bias(mm, start, end, order, flags); 1924 if (!IS_ERR(block) || !steered) 1925 return block; 1926 1927 flags &= ~GPU_BUDDY_RANGE_ALLOCATION; 1928 } 1929 1930 if (size < min_block_size) 1931 /* Allocate from an offset-aligned region without size rounding */ 1932 return gpu_buddy_offset_aligned_allocation(mm, size, 1933 min_block_size); 1934 1935 /* Allocate from freetree */ 1936 return alloc_from_freetree(mm, order, flags); 1937 } 1938 1939 /** 1940 * gpu_buddy_alloc_blocks - allocate power-of-two blocks 1941 * 1942 * @mm: GPU buddy manager to allocate from 1943 * @start: start of the allowed range for this block 1944 * @end: end of the allowed range for this block 1945 * @size: size of the allocation in bytes 1946 * @min_block_size: alignment of the allocation 1947 * @blocks: output list head to add allocated blocks 1948 * @flags: GPU_BUDDY_*_ALLOCATION flags 1949 * 1950 * alloc_range_bias() called on range limitations, which traverses 1951 * the tree and returns the desired block. 1952 * 1953 * alloc_from_freetree() called when *no* range restrictions 1954 * are enforced, which picks the block from the freetree. 1955 * 1956 * Returns: 1957 * 0 on success, error code on failure. 1958 */ 1959 int gpu_buddy_alloc_blocks(struct gpu_buddy *mm, 1960 u64 start, u64 end, u64 size, 1961 u64 min_block_size, 1962 struct list_head *blocks, 1963 unsigned long flags) 1964 { 1965 struct gpu_buddy_block *block = NULL; 1966 u64 original_size, original_min_size; 1967 unsigned int min_order, order; 1968 LIST_HEAD(allocated); 1969 unsigned long pages; 1970 int err; 1971 1972 gpu_buddy_driver_lock_held(mm); 1973 1974 if (size < mm->chunk_size) 1975 return -EINVAL; 1976 1977 if (min_block_size < mm->chunk_size) 1978 return -EINVAL; 1979 1980 if (!is_power_of_2(min_block_size)) 1981 return -EINVAL; 1982 1983 if (!IS_ALIGNED(start | end | size, mm->chunk_size)) 1984 return -EINVAL; 1985 1986 if (end > mm->size) 1987 return -EINVAL; 1988 1989 if (range_overflows(start, size, mm->size)) 1990 return -EINVAL; 1991 1992 /* Actual range allocation */ 1993 if (start + size == end) { 1994 if (!IS_ALIGNED(start | end, min_block_size)) 1995 return -EINVAL; 1996 1997 return __gpu_buddy_alloc_range(mm, start, size, flags, NULL, blocks); 1998 } 1999 2000 original_size = size; 2001 original_min_size = min_block_size; 2002 2003 /* Roundup the size to power of 2 */ 2004 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) { 2005 size = roundup_pow_of_two(size); 2006 min_block_size = size; 2007 /* 2008 * Normalize the requested size to min_block_size for regular allocations. 2009 * Offset-aligned allocations intentionally skip size rounding. 2010 */ 2011 } else if (!gpu_buddy_can_offset_align(size, min_block_size)) { 2012 size = round_up(size, min_block_size); 2013 } 2014 2015 pages = size >> ilog2(mm->chunk_size); 2016 order = fls(pages) - 1; 2017 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size); 2018 2019 if (order > mm->max_order || size > mm->size) { 2020 if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) && 2021 !(flags & GPU_BUDDY_RANGE_ALLOCATION)) 2022 return __alloc_contig_try_harder(mm, original_size, 2023 original_min_size, 2024 flags, blocks); 2025 2026 return -EINVAL; 2027 } 2028 2029 do { 2030 order = min(order, (unsigned int)fls(pages) - 1); 2031 BUG_ON(order > mm->max_order); 2032 /* 2033 * Regular allocations must not allocate blocks smaller than min_block_size. 2034 * Offset-aligned allocations deliberately bypass this constraint. 2035 */ 2036 BUG_ON(size >= min_block_size && order < min_order); 2037 2038 do { 2039 block = __gpu_buddy_alloc_blocks(mm, start, 2040 end, 2041 size, 2042 min_block_size, 2043 order, 2044 flags); 2045 if (!IS_ERR(block)) 2046 break; 2047 2048 if (size >= min_block_size && order > min_order) { 2049 order--; 2050 continue; 2051 } 2052 2053 /* 2054 * Try contiguous block allocation through 2055 * try harder method. 2056 */ 2057 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION && 2058 !(flags & GPU_BUDDY_RANGE_ALLOCATION)) { 2059 err = __alloc_contig_try_harder(mm, 2060 original_size, 2061 original_min_size, 2062 flags, 2063 blocks); 2064 if (!err) 2065 return 0; 2066 if (err != -ENOSPC) 2067 return err; 2068 goto err_free; 2069 } 2070 err = -ENOSPC; 2071 goto err_free; 2072 } while (1); 2073 2074 if (!gpu_buddy_block_is_clear(block)) 2075 gpu_dirty_tracker_remove_range(&mm->dirty, 2076 gpu_buddy_block_offset(block), 2077 gpu_buddy_block_size(mm, block)); 2078 2079 mark_allocated(mm, block); 2080 mm->avail -= gpu_buddy_block_size(mm, block); 2081 2082 kmemleak_update_trace(block); 2083 list_add_tail(&block->link, &allocated); 2084 2085 pages -= BIT(order); 2086 2087 if (!pages) 2088 break; 2089 } while (1); 2090 2091 /* Trim the allocated block to the required size */ 2092 if (!(flags & GPU_BUDDY_TRIM_DISABLE) && 2093 original_size != size) { 2094 struct list_head *trim_list; 2095 LIST_HEAD(temp); 2096 u64 trim_size; 2097 2098 trim_list = &allocated; 2099 trim_size = original_size; 2100 2101 if (!list_is_singular(&allocated)) { 2102 block = list_last_entry(&allocated, typeof(*block), link); 2103 list_move(&block->link, &temp); 2104 trim_list = &temp; 2105 trim_size = gpu_buddy_block_size(mm, block) - 2106 (size - original_size); 2107 } 2108 2109 gpu_buddy_block_trim(mm, 2110 NULL, 2111 trim_size, 2112 trim_list); 2113 2114 if (!list_empty(&temp)) 2115 list_splice_tail(trim_list, &allocated); 2116 } 2117 2118 list_splice_tail(&allocated, blocks); 2119 return 0; 2120 2121 err_free: 2122 gpu_buddy_free_list_internal(mm, &allocated); 2123 return err; 2124 } 2125 EXPORT_SYMBOL(gpu_buddy_alloc_blocks); 2126 2127 /** 2128 * gpu_buddy_block_print - print block information 2129 * 2130 * @mm: GPU buddy manager 2131 * @block: GPU buddy block 2132 */ 2133 void gpu_buddy_block_print(struct gpu_buddy *mm, 2134 struct gpu_buddy_block *block) 2135 { 2136 u64 start = gpu_buddy_block_offset(block); 2137 u64 size = gpu_buddy_block_size(mm, block); 2138 2139 pr_info("%#018llx-%#018llx: %llu\n", start, start + size, size); 2140 } 2141 EXPORT_SYMBOL(gpu_buddy_block_print); 2142 2143 /** 2144 * gpu_buddy_print - print allocator state 2145 * 2146 * @mm: GPU buddy manager 2147 */ 2148 void gpu_buddy_print(struct gpu_buddy *mm) 2149 { 2150 int order; 2151 2152 gpu_buddy_driver_lock_held(mm); 2153 pr_info("chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n", 2154 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, 2155 gpu_buddy_clear_avail(mm) >> 20); 2156 2157 for (order = mm->max_order; order >= 0; order--) { 2158 u64 free_count = mm->free_scoreboard[order]; 2159 u64 used_count = mm->used_scoreboard[order]; 2160 u64 block_size = mm->chunk_size << order; 2161 u64 free = free_count * block_size; 2162 u64 used = used_count * block_size; 2163 2164 if (block_size < SZ_1M) 2165 pr_info("order-%2d free: %8llu KiB, used: %8llu KiB, free_blocks: %llu, used_blocks: %llu\n", 2166 order, free >> 10, used >> 10, free_count, used_count); 2167 else 2168 pr_info("order-%2d free: %8llu MiB, used: %8llu MiB, free_blocks: %llu, used_blocks: %llu\n", 2169 order, free >> 20, used >> 20, free_count, used_count); 2170 } 2171 } 2172 EXPORT_SYMBOL(gpu_buddy_print); 2173 2174 static void gpu_buddy_module_exit(void) 2175 { 2176 kmem_cache_destroy(slab_extents); 2177 kmem_cache_destroy(slab_blocks); 2178 } 2179 2180 static int __init gpu_buddy_module_init(void) 2181 { 2182 slab_blocks = KMEM_CACHE(gpu_buddy_block, 0); 2183 if (!slab_blocks) 2184 return -ENOMEM; 2185 2186 slab_extents = KMEM_CACHE(gpu_dirty_extent, 0); 2187 if (!slab_extents) 2188 goto err_destroy_blocks; 2189 2190 return 0; 2191 2192 err_destroy_blocks: 2193 kmem_cache_destroy(slab_blocks); 2194 return -ENOMEM; 2195 } 2196 2197 module_init(gpu_buddy_module_init); 2198 module_exit(gpu_buddy_module_exit); 2199 2200 MODULE_DESCRIPTION("GPU Buddy Allocator"); 2201 MODULE_LICENSE("Dual MIT/GPL"); 2202