projects/linux·blob master · refs

1634 lines · 38.3 KiB

1// SPDX-License-Identifier: MIT
2/*
3 * Copyright © 2021 Intel Corporation
4 */
5
6#include <linux/bug.h>
7#include <linux/export.h>
8#include <linux/kmemleak.h>
9#include <linux/module.h>
10#include <linux/sizes.h>
11
12#include <linux/gpu_buddy.h>
13
14/**
15 * gpu_buddy_assert - assert a condition in the buddy allocator
16 * @condition: condition expected to be true
17 *
18 * When CONFIG_KUNIT is enabled, evaluates @condition and, if false, triggers
19 * a WARN_ON() and also calls kunit_fail_current_test() so that any running
20 * kunit test is properly marked as failed. The stringified condition is
21 * included in the failure message for easy identification.
22 *
23 * When CONFIG_KUNIT is not enabled, this reduces to WARN_ON() so production
24 * builds retain the same warning semantics as before.
25 */
26#if IS_ENABLED(CONFIG_KUNIT)
27#include <kunit/test-bug.h>
28#define gpu_buddy_assert(condition) do { \
29 if (WARN_ON(!(condition))) \
30 kunit_fail_current_test("gpu_buddy_assert(" #condition ")"); \
31} while (0)
32#else
33#define gpu_buddy_assert(condition) WARN_ON(!(condition))
34#endif
35
36static struct kmem_cache *slab_blocks;
37
38static unsigned int
39gpu_buddy_block_state(struct gpu_buddy_block *block)
40{
41 return block->header & GPU_BUDDY_HEADER_STATE;
42}
43
44static bool
45gpu_buddy_block_is_allocated(struct gpu_buddy_block *block)
46{
47 return gpu_buddy_block_state(block) == GPU_BUDDY_ALLOCATED;
48}
49
50static bool
51gpu_buddy_block_is_split(struct gpu_buddy_block *block)
52{
53 return gpu_buddy_block_state(block) == GPU_BUDDY_SPLIT;
54}
55
56static unsigned int gpu_buddy_block_offset_alignment(struct gpu_buddy_block *block)
57{
58 u64 offset = gpu_buddy_block_offset(block);
59
60 if (!offset)
61 /*
62 * __ffs64(0) is undefined; offset 0 is maximally aligned, so return
63 * a value greater than any possible alignment.
64 */
65 return 64 + 1;
66
67 return __ffs64(offset);
68}
69
70RB_DECLARE_CALLBACKS_MAX(static, gpu_buddy_augment_cb,
71 struct gpu_buddy_block, rb,
72 unsigned int, subtree_max_alignment,
73 gpu_buddy_block_offset_alignment);
74
75static struct gpu_buddy_block *gpu_block_alloc(struct gpu_buddy *mm,
76 struct gpu_buddy_block *parent,
77 unsigned int order,
78 u64 offset)
79{
80 struct gpu_buddy_block *block;
81
82 BUG_ON(order > GPU_BUDDY_MAX_ORDER);
83
84 block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);
85 if (!block)
86 return NULL;
87
88 block->header = offset;
89 block->header |= order;
90 block->parent = parent;
91
92 RB_CLEAR_NODE(&block->rb);
93
94 BUG_ON(block->header & GPU_BUDDY_HEADER_UNUSED);
95 return block;
96}
97
98static void gpu_block_free(struct gpu_buddy *mm,
99 struct gpu_buddy_block *block)
100{
101 kmem_cache_free(slab_blocks, block);
102}
103
104static enum gpu_buddy_free_tree
105get_block_tree(struct gpu_buddy_block *block)
106{
107 return gpu_buddy_block_is_clear(block) ?
108 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
109}
110
111static struct gpu_buddy_block *
112rbtree_get_free_block(const struct rb_node *node)
113{
114 return node ? rb_entry(node, struct gpu_buddy_block, rb) : NULL;
115}
116
117static struct gpu_buddy_block *
118rbtree_last_free_block(struct rb_root *root)
119{
120 return rbtree_get_free_block(rb_last(root));
121}
122
123static bool rbtree_is_empty(struct rb_root *root)
124{
125 return RB_EMPTY_ROOT(root);
126}
127
128static void rbtree_insert(struct gpu_buddy *mm,
129 struct gpu_buddy_block *block,
130 enum gpu_buddy_free_tree tree)
131{
132 struct rb_node **link, *parent = NULL;
133 unsigned int block_alignment, order;
134 struct gpu_buddy_block *node;
135 struct rb_root *root;
136
137 order = gpu_buddy_block_order(block);
138 block_alignment = gpu_buddy_block_offset_alignment(block);
139
140 root = &mm->free_trees[tree][order];
141 link = &root->rb_node;
142
143 while (*link) {
144 parent = *link;
145 node = rbtree_get_free_block(parent);
146 /*
147 * Manual augmentation update during insertion traversal. Required
148 * because rb_insert_augmented() only calls rotate callback during
149 * rotations. This ensures all ancestors on the insertion path have
150 * correct subtree_max_alignment values.
151 */
152 if (node->subtree_max_alignment < block_alignment)
153 node->subtree_max_alignment = block_alignment;
154
155 if (gpu_buddy_block_offset(block) < gpu_buddy_block_offset(node))
156 link = &parent->rb_left;
157 else
158 link = &parent->rb_right;
159 }
160
161 block->subtree_max_alignment = block_alignment;
162 rb_link_node(&block->rb, parent, link);
163 rb_insert_augmented(&block->rb, root, &gpu_buddy_augment_cb);
164}
165
166static void rbtree_remove(struct gpu_buddy *mm,
167 struct gpu_buddy_block *block)
168{
169 unsigned int order = gpu_buddy_block_order(block);
170 enum gpu_buddy_free_tree tree;
171 struct rb_root *root;
172
173 tree = get_block_tree(block);
174 root = &mm->free_trees[tree][order];
175
176 rb_erase_augmented(&block->rb, root, &gpu_buddy_augment_cb);
177 RB_CLEAR_NODE(&block->rb);
178}
179
180static void clear_reset(struct gpu_buddy_block *block)
181{
182 block->header &= ~GPU_BUDDY_HEADER_CLEAR;
183}
184
185static void mark_cleared(struct gpu_buddy_block *block)
186{
187 block->header |= GPU_BUDDY_HEADER_CLEAR;
188}
189
190static void mark_allocated(struct gpu_buddy *mm,
191 struct gpu_buddy_block *block)
192{
193 block->header &= ~GPU_BUDDY_HEADER_STATE;
194 block->header |= GPU_BUDDY_ALLOCATED;
195
196 mm->free_scoreboard[gpu_buddy_block_order(block)]--;
197 mm->used_scoreboard[gpu_buddy_block_order(block)]++;
198
199 rbtree_remove(mm, block);
200}
201
202static void mark_free(struct gpu_buddy *mm,
203 struct gpu_buddy_block *block)
204{
205 enum gpu_buddy_free_tree tree;
206
207 if (gpu_buddy_block_is_allocated(block))
208 mm->used_scoreboard[gpu_buddy_block_order(block)]--;
209
210 block->header &= ~GPU_BUDDY_HEADER_STATE;
211 block->header |= GPU_BUDDY_FREE;
212
213 mm->free_scoreboard[gpu_buddy_block_order(block)]++;
214
215 tree = get_block_tree(block);
216 rbtree_insert(mm, block, tree);
217}
218
219static void mark_split(struct gpu_buddy *mm,
220 struct gpu_buddy_block *block)
221{
222 block->header &= ~GPU_BUDDY_HEADER_STATE;
223 block->header |= GPU_BUDDY_SPLIT;
224
225 mm->free_scoreboard[gpu_buddy_block_order(block)]--;
226
227 rbtree_remove(mm, block);
228}
229
230static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
231{
232 return s1 <= e2 && e1 >= s2;
233}
234
235static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
236{
237 return s1 <= s2 && e1 >= e2;
238}
239
240static struct gpu_buddy_block *
241__get_buddy(struct gpu_buddy_block *block)
242{
243 struct gpu_buddy_block *parent;
244
245 parent = block->parent;
246 if (!parent)
247 return NULL;
248
249 if (parent->left == block)
250 return parent->right;
251
252 return parent->left;
253}
254
255static unsigned int __gpu_buddy_free(struct gpu_buddy *mm,
256 struct gpu_buddy_block *block,
257 bool force_merge)
258{
259 struct gpu_buddy_block *parent;
260 unsigned int order;
261
262 while ((parent = block->parent)) {
263 struct gpu_buddy_block *buddy;
264
265 buddy = __get_buddy(block);
266
267 if (!gpu_buddy_block_is_free(buddy))
268 break;
269
270 if (!force_merge) {
271 /*
272 * Check the block and its buddy clear state and exit
273 * the loop if they both have the dissimilar state.
274 */
275 if (gpu_buddy_block_is_clear(block) !=
276 gpu_buddy_block_is_clear(buddy))
277 break;
278
279 if (gpu_buddy_block_is_clear(block))
280 mark_cleared(parent);
281 }
282
283 rbtree_remove(mm, buddy);
284 mm->free_scoreboard[gpu_buddy_block_order(buddy)]--;
285 if (force_merge && gpu_buddy_block_is_clear(buddy))
286 mm->clear_avail -= gpu_buddy_block_size(mm, buddy);
287
288 if (gpu_buddy_block_is_allocated(block))
289 mm->used_scoreboard[gpu_buddy_block_order(block)]--;
290
291 gpu_block_free(mm, block);
292 gpu_block_free(mm, buddy);
293
294 block = parent;
295 }
296
297 order = gpu_buddy_block_order(block);
298 mark_free(mm, block);
299
300 return order;
301}
302
303static int __force_merge(struct gpu_buddy *mm,
304 u64 start,
305 u64 end,
306 unsigned int min_order)
307{
308 unsigned int tree, order;
309 int i;
310
311 if (!min_order)
312 return -ENOMEM;
313
314 if (min_order > mm->max_order)
315 return -EINVAL;
316
317 for_each_free_tree(tree) {
318 for (i = min_order - 1; i >= 0; i--) {
319 struct rb_node *iter = rb_last(&mm->free_trees[tree][i]);
320
321 while (iter) {
322 struct gpu_buddy_block *block, *buddy;
323 u64 block_start, block_end;
324
325 block = rbtree_get_free_block(iter);
326 iter = rb_prev(iter);
327
328 if (!block || !block->parent)
329 continue;
330
331 block_start = gpu_buddy_block_offset(block);
332 block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
333
334 if (!contains(start, end, block_start, block_end))
335 continue;
336
337 buddy = __get_buddy(block);
338 if (!gpu_buddy_block_is_free(buddy))
339 continue;
340
341 gpu_buddy_assert(gpu_buddy_block_is_clear(block) !=
342 gpu_buddy_block_is_clear(buddy));
343
344 /*
345 * Advance to the next node when the current node is the buddy,
346 * as freeing the block will also remove its buddy from the tree.
347 */
348 if (iter == &buddy->rb)
349 iter = rb_prev(iter);
350
351 rbtree_remove(mm, block);
352 mm->free_scoreboard[gpu_buddy_block_order(block)]--;
353 if (gpu_buddy_block_is_clear(block))
354 mm->clear_avail -= gpu_buddy_block_size(mm, block);
355
356 order = __gpu_buddy_free(mm, block, true);
357 if (order >= min_order)
358 return 0;
359 }
360 }
361 }
362
363 return -ENOMEM;
364}
365
366/**
367 * gpu_buddy_init - init memory manager
368 *
369 * @mm: GPU buddy manager to initialize
370 * @size: size in bytes to manage
371 * @chunk_size: minimum page size in bytes for our allocations
372 *
373 * Initializes the memory manager and its resources.
374 *
375 * Returns:
376 * 0 on success, error code on failure.
377 */
378int gpu_buddy_init(struct gpu_buddy *mm, u64 size, u64 chunk_size)
379{
380 unsigned int i, j, root_count = 0;
381 u64 offset = 0;
382
383 if (size < chunk_size)
384 return -EINVAL;
385
386 if (chunk_size < SZ_4K)
387 return -EINVAL;
388
389 if (!is_power_of_2(chunk_size))
390 return -EINVAL;
391
392 size = round_down(size, chunk_size);
393
394 mm->size = size;
395 mm->avail = size;
396 mm->clear_avail = 0;
397 mm->chunk_size = chunk_size;
398 mm->max_order = ilog2(size) - ilog2(chunk_size);
399
400 BUG_ON(mm->max_order > GPU_BUDDY_MAX_ORDER);
401
402 mm->free_scoreboard = kcalloc(mm->max_order + 1,
403 sizeof(*mm->free_scoreboard),
404 GFP_KERNEL);
405 if (!mm->free_scoreboard)
406 return -ENOMEM;
407
408 mm->used_scoreboard = kcalloc(mm->max_order + 1,
409 sizeof(*mm->used_scoreboard),
410 GFP_KERNEL);
411 if (!mm->used_scoreboard)
412 goto out_free_free_scoreboard;
413
414 mm->free_trees = kmalloc_objs(*mm->free_trees, GPU_BUDDY_MAX_FREE_TREES);
415 if (!mm->free_trees)
416 goto out_free_used_scoreboard;
417
418 for_each_free_tree(i) {
419 mm->free_trees[i] = kmalloc_objs(struct rb_root,
420 mm->max_order + 1);
421 if (!mm->free_trees[i])
422 goto out_free_tree;
423
424 for (j = 0; j <= mm->max_order; ++j)
425 mm->free_trees[i][j] = RB_ROOT;
426 }
427
428 mm->n_roots = hweight64(size);
429
430 mm->roots = kmalloc_objs(struct gpu_buddy_block *, mm->n_roots);
431 if (!mm->roots)
432 goto out_free_tree;
433
434 /*
435 * Split into power-of-two blocks, in case we are given a size that is
436 * not itself a power-of-two.
437 */
438 do {
439 struct gpu_buddy_block *root;
440 unsigned int order;
441 u64 root_size;
442
443 order = ilog2(size) - ilog2(chunk_size);
444 root_size = chunk_size << order;
445
446 root = gpu_block_alloc(mm, NULL, order, offset);
447 if (!root)
448 goto out_free_roots;
449
450 mark_free(mm, root);
451
452 BUG_ON(root_count > mm->max_order);
453 BUG_ON(gpu_buddy_block_size(mm, root) < chunk_size);
454
455 mm->roots[root_count] = root;
456
457 offset += root_size;
458 size -= root_size;
459 root_count++;
460 } while (size);
461
462#ifdef CONFIG_LOCKDEP
463 mm->lock_dep_map = NULL;
464#endif
465 return 0;
466
467out_free_roots:
468 while (root_count--)
469 gpu_block_free(mm, mm->roots[root_count]);
470 kfree(mm->roots);
471out_free_tree:
472 while (i--)
473 kfree(mm->free_trees[i]);
474 kfree(mm->free_trees);
475out_free_used_scoreboard:
476 kfree(mm->used_scoreboard);
477out_free_free_scoreboard:
478 kfree(mm->free_scoreboard);
479 return -ENOMEM;
480}
481EXPORT_SYMBOL(gpu_buddy_init);
482
483/**
484 * gpu_buddy_fini - tear down the memory manager
485 *
486 * @mm: GPU buddy manager to free
487 *
488 * Cleanup memory manager resources and the freetree
489 */
490void gpu_buddy_fini(struct gpu_buddy *mm)
491{
492 u64 root_size, size, start;
493 unsigned int order;
494 int i;
495
496 size = mm->size;
497
498 for (i = 0; i < mm->n_roots; ++i) {
499 order = ilog2(size) - ilog2(mm->chunk_size);
500 start = gpu_buddy_block_offset(mm->roots[i]);
501 __force_merge(mm, start, start + size, order);
502
503 gpu_buddy_assert(gpu_buddy_block_is_free(mm->roots[i]));
504
505 gpu_block_free(mm, mm->roots[i]);
506
507 root_size = mm->chunk_size << order;
508 size -= root_size;
509 }
510
511 gpu_buddy_assert(mm->avail == mm->size);
512
513 for (i = 0; i <= mm->max_order; ++i)
514 gpu_buddy_assert(!mm->used_scoreboard[i]);
515
516 for_each_free_tree(i)
517 kfree(mm->free_trees[i]);
518 kfree(mm->free_trees);
519 kfree(mm->roots);
520 kfree(mm->free_scoreboard);
521 kfree(mm->used_scoreboard);
522}
523EXPORT_SYMBOL(gpu_buddy_fini);
524
525static int split_block(struct gpu_buddy *mm,
526 struct gpu_buddy_block *block)
527{
528 unsigned int block_order = gpu_buddy_block_order(block) - 1;
529 u64 offset = gpu_buddy_block_offset(block);
530
531 BUG_ON(!gpu_buddy_block_is_free(block));
532 BUG_ON(!gpu_buddy_block_order(block));
533
534 block->left = gpu_block_alloc(mm, block, block_order, offset);
535 if (!block->left)
536 return -ENOMEM;
537
538 block->right = gpu_block_alloc(mm, block, block_order,
539 offset + (mm->chunk_size << block_order));
540 if (!block->right) {
541 gpu_block_free(mm, block->left);
542 return -ENOMEM;
543 }
544
545 mark_split(mm, block);
546
547 if (gpu_buddy_block_is_clear(block)) {
548 mark_cleared(block->left);
549 mark_cleared(block->right);
550 clear_reset(block);
551 }
552
553 mark_free(mm, block->left);
554 mark_free(mm, block->right);
555
556 return 0;
557}
558
559/**
560 * gpu_buddy_reset_clear - reset blocks clear state
561 *
562 * @mm: GPU buddy manager
563 * @is_clear: blocks clear state
564 *
565 * Reset the clear state based on @is_clear value for each block
566 * in the freetree.
567 */
568void gpu_buddy_reset_clear(struct gpu_buddy *mm, bool is_clear)
569{
570 enum gpu_buddy_free_tree src_tree, dst_tree;
571 u64 root_size, size, start;
572 unsigned int order;
573 int i;
574
575 gpu_buddy_driver_lock_held(mm);
576 size = mm->size;
577 for (i = 0; i < mm->n_roots; ++i) {
578 order = ilog2(size) - ilog2(mm->chunk_size);
579 start = gpu_buddy_block_offset(mm->roots[i]);
580 __force_merge(mm, start, start + size, order);
581
582 root_size = mm->chunk_size << order;
583 size -= root_size;
584 }
585
586 src_tree = is_clear ? GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE;
587 dst_tree = is_clear ? GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
588
589 for (i = 0; i <= mm->max_order; ++i) {
590 struct rb_root *root = &mm->free_trees[src_tree][i];
591 struct gpu_buddy_block *block, *tmp;
592
593 rbtree_postorder_for_each_entry_safe(block, tmp, root, rb) {
594 rbtree_remove(mm, block);
595 if (is_clear) {
596 mark_cleared(block);
597 mm->clear_avail += gpu_buddy_block_size(mm, block);
598 } else {
599 clear_reset(block);
600 mm->clear_avail -= gpu_buddy_block_size(mm, block);
601 }
602
603 rbtree_insert(mm, block, dst_tree);
604 }
605 }
606}
607EXPORT_SYMBOL(gpu_buddy_reset_clear);
608
609/**
610 * gpu_buddy_free_block - free a block
611 *
612 * @mm: GPU buddy manager
613 * @block: block to be freed
614 */
615void gpu_buddy_free_block(struct gpu_buddy *mm,
616 struct gpu_buddy_block *block)
617{
618 gpu_buddy_driver_lock_held(mm);
619 BUG_ON(!gpu_buddy_block_is_allocated(block));
620 mm->avail += gpu_buddy_block_size(mm, block);
621 if (gpu_buddy_block_is_clear(block))
622 mm->clear_avail += gpu_buddy_block_size(mm, block);
623
624 __gpu_buddy_free(mm, block, false);
625}
626EXPORT_SYMBOL(gpu_buddy_free_block);
627
628/**
629 * gpu_buddy_allocated_addr_to_block - given relative address find the allocated block
630 *
631 * @mm: GPU buddy manager
632 * @addr: Relative address
633 *
634 * Returns:
635 * gpu_buddy_block on success, NULL or error code on failure
636 */
637struct gpu_buddy_block *gpu_buddy_allocated_addr_to_block(struct gpu_buddy *mm, u64 addr)
638{
639 struct gpu_buddy_block *block;
640 LIST_HEAD(dfs);
641 u64 end;
642 int i;
643
644 gpu_buddy_driver_lock_held(mm);
645
646 end = addr + mm->chunk_size - 1;
647 for (i = 0; i < mm->n_roots; ++i)
648 list_add_tail(&mm->roots[i]->tmp_link, &dfs);
649
650 do {
651 u64 block_start;
652 u64 block_end;
653
654 block = list_first_entry_or_null(&dfs,
655 struct gpu_buddy_block,
656 tmp_link);
657 if (!block)
658 break;
659
660 list_del(&block->tmp_link);
661
662 block_start = gpu_buddy_block_offset(block);
663 block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
664
665 if (!overlaps(addr, end, block_start, block_end))
666 continue;
667
668 if (gpu_buddy_block_is_allocated(block))
669 return block;
670 else if (gpu_buddy_block_is_free(block))
671 return NULL;
672
673 list_add(&block->right->tmp_link, &dfs);
674 list_add(&block->left->tmp_link, &dfs);
675 } while (1);
676
677 return ERR_PTR(-ENXIO);
678}
679EXPORT_SYMBOL(gpu_buddy_allocated_addr_to_block);
680
681static void __gpu_buddy_free_list(struct gpu_buddy *mm,
682 struct list_head *objects,
683 bool mark_clear,
684 bool mark_dirty)
685{
686 struct gpu_buddy_block *block, *on;
687
688 gpu_buddy_assert(!(mark_dirty && mark_clear));
689
690 list_for_each_entry_safe(block, on, objects, link) {
691 if (mark_clear)
692 mark_cleared(block);
693 else if (mark_dirty)
694 clear_reset(block);
695 gpu_buddy_free_block(mm, block);
696 cond_resched();
697 }
698 INIT_LIST_HEAD(objects);
699}
700
701static void gpu_buddy_free_list_internal(struct gpu_buddy *mm,
702 struct list_head *objects)
703{
704 /*
705 * Don't touch the clear/dirty bit, since allocation is still internal
706 * at this point. For example we might have just failed part of the
707 * allocation.
708 */
709 __gpu_buddy_free_list(mm, objects, false, false);
710}
711
712/**
713 * gpu_buddy_free_list - free blocks
714 *
715 * @mm: GPU buddy manager
716 * @objects: input list head to free blocks
717 * @flags: optional flags like GPU_BUDDY_CLEARED
718 */
719void gpu_buddy_free_list(struct gpu_buddy *mm,
720 struct list_head *objects,
721 unsigned int flags)
722{
723 bool mark_clear = flags & GPU_BUDDY_CLEARED;
724
725 gpu_buddy_driver_lock_held(mm);
726 __gpu_buddy_free_list(mm, objects, mark_clear, !mark_clear);
727}
728EXPORT_SYMBOL(gpu_buddy_free_list);
729
730static bool block_incompatible(struct gpu_buddy_block *block, unsigned int flags)
731{
732 bool needs_clear = flags & GPU_BUDDY_CLEAR_ALLOCATION;
733
734 return needs_clear != gpu_buddy_block_is_clear(block);
735}
736
737static void __gpu_buddy_undo_splits(struct gpu_buddy *mm,
738 struct gpu_buddy_block *block)
739{
740 struct gpu_buddy_block *buddy = __get_buddy(block);
741
742 if (buddy &&
743 (gpu_buddy_block_is_free(block) &&
744 gpu_buddy_block_is_free(buddy))) {
745 rbtree_remove(mm, block);
746 mm->free_scoreboard[gpu_buddy_block_order(block)]--;
747 __gpu_buddy_free(mm, block, false);
748 }
749}
750
751static struct gpu_buddy_block *
752__alloc_range_bias(struct gpu_buddy *mm,
753 u64 start, u64 end,
754 unsigned int order,
755 unsigned long flags,
756 bool fallback)
757{
758 u64 req_size = mm->chunk_size << order;
759 struct gpu_buddy_block *block;
760 LIST_HEAD(dfs);
761 int err;
762 int i;
763
764 end = end - 1;
765
766 for (i = 0; i < mm->n_roots; ++i)
767 list_add_tail(&mm->roots[i]->tmp_link, &dfs);
768
769 do {
770 u64 block_start;
771 u64 block_end;
772
773 block = list_first_entry_or_null(&dfs,
774 struct gpu_buddy_block,
775 tmp_link);
776 if (!block)
777 break;
778
779 list_del(&block->tmp_link);
780
781 if (gpu_buddy_block_order(block) < order)
782 continue;
783
784 block_start = gpu_buddy_block_offset(block);
785 block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
786
787 if (!overlaps(start, end, block_start, block_end))
788 continue;
789
790 if (gpu_buddy_block_is_allocated(block))
791 continue;
792
793 if (block_start < start || block_end > end) {
794 u64 adjusted_start = max(block_start, start);
795 u64 adjusted_end = min(block_end, end);
796
797 if (round_down(adjusted_end + 1, req_size) <=
798 round_up(adjusted_start, req_size))
799 continue;
800 }
801
802 if (!fallback && block_incompatible(block, flags))
803 continue;
804
805 if (contains(start, end, block_start, block_end) &&
806 order == gpu_buddy_block_order(block)) {
807 /*
808 * Find the free block within the range.
809 */
810 if (gpu_buddy_block_is_free(block))
811 return block;
812
813 continue;
814 }
815
816 if (!gpu_buddy_block_is_split(block)) {
817 err = split_block(mm, block);
818 if (unlikely(err))
819 goto err_undo;
820 }
821
822 list_add(&block->right->tmp_link, &dfs);
823 list_add(&block->left->tmp_link, &dfs);
824 } while (1);
825
826 return ERR_PTR(-ENOSPC);
827
828err_undo:
829 /*
830 * We really don't want to leave around a bunch of split blocks, since
831 * bigger is better, so make sure we merge everything back before we
832 * free the allocated blocks.
833 */
834 __gpu_buddy_undo_splits(mm, block);
835 return ERR_PTR(err);
836}
837
838static struct gpu_buddy_block *
839__gpu_buddy_alloc_range_bias(struct gpu_buddy *mm,
840 u64 start, u64 end,
841 unsigned int order,
842 unsigned long flags)
843{
844 struct gpu_buddy_block *block;
845 bool fallback = false;
846
847 block = __alloc_range_bias(mm, start, end, order,
848 flags, fallback);
849 if (IS_ERR(block))
850 return __alloc_range_bias(mm, start, end, order,
851 flags, !fallback);
852
853 return block;
854}
855
856static struct gpu_buddy_block *
857get_maxblock(struct gpu_buddy *mm,
858 unsigned int order,
859 enum gpu_buddy_free_tree tree)
860{
861 struct gpu_buddy_block *max_block = NULL, *block = NULL;
862 struct rb_root *root;
863 unsigned int i;
864
865 for (i = order; i <= mm->max_order; ++i) {
866 root = &mm->free_trees[tree][i];
867 block = rbtree_last_free_block(root);
868 if (!block)
869 continue;
870
871 if (!max_block) {
872 max_block = block;
873 continue;
874 }
875
876 if (gpu_buddy_block_offset(block) >
877 gpu_buddy_block_offset(max_block)) {
878 max_block = block;
879 }
880 }
881
882 return max_block;
883}
884
885static struct gpu_buddy_block *
886alloc_from_freetree(struct gpu_buddy *mm,
887 unsigned int order,
888 unsigned long flags)
889{
890 struct gpu_buddy_block *block = NULL;
891 struct rb_root *root;
892 enum gpu_buddy_free_tree tree;
893 unsigned int tmp;
894 int err;
895
896 tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ?
897 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
898
899 if (flags & GPU_BUDDY_TOPDOWN_ALLOCATION) {
900 block = get_maxblock(mm, order, tree);
901 if (block)
902 /* Store the obtained block order */
903 tmp = gpu_buddy_block_order(block);
904 } else {
905 for (tmp = order; tmp <= mm->max_order; ++tmp) {
906 /* Get RB tree root for this order and tree */
907 root = &mm->free_trees[tree][tmp];
908 block = rbtree_last_free_block(root);
909 if (block)
910 break;
911 }
912 }
913
914 if (!block) {
915 /* Try allocating from the other tree */
916 tree = (tree == GPU_BUDDY_CLEAR_TREE) ?
917 GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE;
918
919 for (tmp = order; tmp <= mm->max_order; ++tmp) {
920 root = &mm->free_trees[tree][tmp];
921 block = rbtree_last_free_block(root);
922 if (block)
923 break;
924 }
925
926 if (!block)
927 return ERR_PTR(-ENOSPC);
928 }
929
930 BUG_ON(!gpu_buddy_block_is_free(block));
931
932 while (tmp != order) {
933 err = split_block(mm, block);
934 if (unlikely(err))
935 goto err_undo;
936
937 block = block->right;
938 tmp--;
939 }
940 return block;
941
942err_undo:
943 __gpu_buddy_undo_splits(mm, block);
944 return ERR_PTR(err);
945}
946
947static bool
948gpu_buddy_can_offset_align(u64 size, u64 min_block_size)
949{
950 return size < min_block_size && is_power_of_2(size);
951}
952
953static bool gpu_buddy_subtree_can_satisfy(struct rb_node *node,
954 unsigned int alignment)
955{
956 struct gpu_buddy_block *block;
957
958 block = rbtree_get_free_block(node);
959 return block->subtree_max_alignment >= alignment;
960}
961
962static struct gpu_buddy_block *
963gpu_buddy_find_block_aligned(struct gpu_buddy *mm,
964 enum gpu_buddy_free_tree tree,
965 unsigned int order,
966 unsigned int alignment,
967 unsigned long flags)
968{
969 struct rb_root *root = &mm->free_trees[tree][order];
970 struct rb_node *rb = root->rb_node;
971
972 while (rb) {
973 struct gpu_buddy_block *block = rbtree_get_free_block(rb);
974 struct rb_node *left_node = rb->rb_left, *right_node = rb->rb_right;
975
976 if (right_node) {
977 if (gpu_buddy_subtree_can_satisfy(right_node, alignment)) {
978 rb = right_node;
979 continue;
980 }
981 }
982
983 if (gpu_buddy_block_offset_alignment(block) >= alignment)
984 return block;
985
986 if (left_node) {
987 if (gpu_buddy_subtree_can_satisfy(left_node, alignment)) {
988 rb = left_node;
989 continue;
990 }
991 }
992
993 break;
994 }
995
996 return NULL;
997}
998
999static struct gpu_buddy_block *
1000gpu_buddy_offset_aligned_allocation(struct gpu_buddy *mm,
1001 u64 size,
1002 u64 min_block_size,
1003 unsigned long flags)
1004{
1005 struct gpu_buddy_block *block = NULL;
1006 unsigned int order, tmp, alignment;
1007 enum gpu_buddy_free_tree tree;
1008 unsigned long pages;
1009 int err;
1010
1011 alignment = ilog2(min_block_size);
1012 pages = size >> ilog2(mm->chunk_size);
1013 order = fls(pages) - 1;
1014
1015 tree = (flags & GPU_BUDDY_CLEAR_ALLOCATION) ?
1016 GPU_BUDDY_CLEAR_TREE : GPU_BUDDY_DIRTY_TREE;
1017
1018 for (tmp = order; tmp <= mm->max_order; ++tmp) {
1019 block = gpu_buddy_find_block_aligned(mm, tree, tmp,
1020 alignment, flags);
1021 if (!block) {
1022 tree = (tree == GPU_BUDDY_CLEAR_TREE) ?
1023 GPU_BUDDY_DIRTY_TREE : GPU_BUDDY_CLEAR_TREE;
1024 block = gpu_buddy_find_block_aligned(mm, tree, tmp,
1025 alignment, flags);
1026 }
1027
1028 if (block)
1029 break;
1030 }
1031
1032 if (!block)
1033 return ERR_PTR(-ENOSPC);
1034
1035 while (gpu_buddy_block_order(block) > order) {
1036 struct gpu_buddy_block *left, *right;
1037
1038 err = split_block(mm, block);
1039 if (unlikely(err))
1040 goto err_undo;
1041
1042 left = block->left;
1043 right = block->right;
1044
1045 if (gpu_buddy_block_offset_alignment(right) >= alignment)
1046 block = right;
1047 else
1048 block = left;
1049 }
1050
1051 return block;
1052
1053err_undo:
1054 /*
1055 * We really don't want to leave around a bunch of split blocks, since
1056 * bigger is better, so make sure we merge everything back before we
1057 * free the allocated blocks.
1058 */
1059 __gpu_buddy_undo_splits(mm, block);
1060 return ERR_PTR(err);
1061}
1062
1063static int __alloc_range(struct gpu_buddy *mm,
1064 struct list_head *dfs,
1065 u64 start, u64 size,
1066 struct list_head *blocks,
1067 u64 *total_allocated_on_err)
1068{
1069 struct gpu_buddy_block *block;
1070 u64 total_allocated = 0;
1071 LIST_HEAD(allocated);
1072 u64 end;
1073 int err;
1074
1075 end = start + size - 1;
1076
1077 do {
1078 u64 block_start;
1079 u64 block_end;
1080
1081 block = list_first_entry_or_null(dfs,
1082 struct gpu_buddy_block,
1083 tmp_link);
1084 if (!block)
1085 break;
1086
1087 list_del(&block->tmp_link);
1088
1089 block_start = gpu_buddy_block_offset(block);
1090 block_end = block_start + gpu_buddy_block_size(mm, block) - 1;
1091
1092 if (!overlaps(start, end, block_start, block_end))
1093 continue;
1094
1095 if (gpu_buddy_block_is_allocated(block)) {
1096 err = -ENOSPC;
1097 goto err_free;
1098 }
1099
1100 if (contains(start, end, block_start, block_end)) {
1101 if (gpu_buddy_block_is_free(block)) {
1102 mark_allocated(mm, block);
1103 total_allocated += gpu_buddy_block_size(mm, block);
1104 mm->avail -= gpu_buddy_block_size(mm, block);
1105 if (gpu_buddy_block_is_clear(block))
1106 mm->clear_avail -= gpu_buddy_block_size(mm, block);
1107 list_add_tail(&block->link, &allocated);
1108 continue;
1109 } else if (!mm->clear_avail) {
1110 err = -ENOSPC;
1111 goto err_free;
1112 }
1113 }
1114
1115 if (!gpu_buddy_block_is_split(block)) {
1116 err = split_block(mm, block);
1117 if (unlikely(err))
1118 goto err_undo;
1119 }
1120
1121 list_add(&block->right->tmp_link, dfs);
1122 list_add(&block->left->tmp_link, dfs);
1123 } while (1);
1124
1125 if (total_allocated < size) {
1126 err = -ENOSPC;
1127 goto err_free;
1128 }
1129
1130 list_splice_tail(&allocated, blocks);
1131
1132 return 0;
1133
1134err_undo:
1135 /*
1136 * We really don't want to leave around a bunch of split blocks, since
1137 * bigger is better, so make sure we merge everything back before we
1138 * free the allocated blocks.
1139 */
1140 __gpu_buddy_undo_splits(mm, block);
1141
1142err_free:
1143 if (err == -ENOSPC && total_allocated_on_err) {
1144 list_splice_tail(&allocated, blocks);
1145 *total_allocated_on_err = total_allocated;
1146 } else {
1147 gpu_buddy_free_list_internal(mm, &allocated);
1148 }
1149
1150 return err;
1151}
1152
1153static int __gpu_buddy_alloc_range(struct gpu_buddy *mm,
1154 u64 start,
1155 u64 size,
1156 u64 *total_allocated_on_err,
1157 struct list_head *blocks)
1158{
1159 LIST_HEAD(dfs);
1160 int i;
1161
1162 for (i = 0; i < mm->n_roots; ++i)
1163 list_add_tail(&mm->roots[i]->tmp_link, &dfs);
1164
1165 return __alloc_range(mm, &dfs, start, size,
1166 blocks, total_allocated_on_err);
1167}
1168
1169static int __alloc_contig_aligned_retry(struct gpu_buddy *mm,
1170 u64 unaligned_offset,
1171 u64 size,
1172 u64 min_block_size,
1173 struct list_head *blocks)
1174{
1175 u64 aligned_offset = round_down(unaligned_offset, min_block_size);
1176
1177 return __gpu_buddy_alloc_range(mm, aligned_offset, size, NULL, blocks);
1178}
1179
1180static int __alloc_contig_try_harder(struct gpu_buddy *mm,
1181 u64 size,
1182 u64 min_block_size,
1183 struct list_head *blocks)
1184{
1185 u64 rhs_offset, lhs_offset, filled;
1186 struct gpu_buddy_block *block;
1187 unsigned int tree, order;
1188 u64 modify_size;
1189 int err;
1190
1191 modify_size = rounddown_pow_of_two(size);
1192 order = ilog2(modify_size) - ilog2(mm->chunk_size);
1193 if (order == 0)
1194 return -ENOSPC;
1195
1196 for_each_free_tree(tree) {
1197 struct rb_root *root;
1198 struct rb_node *iter;
1199
1200 root = &mm->free_trees[tree][order];
1201 if (rbtree_is_empty(root))
1202 continue;
1203
1204 iter = rb_last(root);
1205 while (iter) {
1206 block = rbtree_get_free_block(iter);
1207
1208 rhs_offset = gpu_buddy_block_offset(block);
1209
1210 /* Allocate blocks traversing RHS */
1211 err = __gpu_buddy_alloc_range(mm, rhs_offset, size,
1212 &filled, blocks);
1213 if (err && err != -ENOSPC)
1214 return err;
1215 if (!err && IS_ALIGNED(rhs_offset, min_block_size))
1216 return 0;
1217 if (!err) {
1218 /* Allocate the unaligned RHS offset using round_down */
1219 gpu_buddy_free_list_internal(mm, blocks);
1220 err = __alloc_contig_aligned_retry(mm, rhs_offset,
1221 size,
1222 min_block_size,
1223 blocks);
1224 if (!err)
1225 return 0;
1226 if (err != -ENOSPC) {
1227 gpu_buddy_free_list_internal(mm, blocks);
1228 return err;
1229 }
1230 goto next;
1231 }
1232
1233 if (size - filled > rhs_offset)
1234 goto next;
1235
1236 lhs_offset = rhs_offset - (size - filled);
1237
1238 /* Allocate the unaligned LHS offset using round_down */
1239 gpu_buddy_free_list_internal(mm, blocks);
1240 err = __alloc_contig_aligned_retry(mm, lhs_offset, size,
1241 min_block_size, blocks);
1242 if (!err)
1243 return 0;
1244 if (err != -ENOSPC) {
1245 gpu_buddy_free_list_internal(mm, blocks);
1246 return err;
1247 }
1248next:
1249 gpu_buddy_free_list_internal(mm, blocks);
1250 iter = rb_prev(iter);
1251 }
1252 }
1253
1254 return -ENOSPC;
1255}
1256
1257/**
1258 * gpu_buddy_block_trim - free unused pages
1259 *
1260 * @mm: GPU buddy manager
1261 * @start: start address to begin the trimming.
1262 * @new_size: original size requested
1263 * @blocks: Input and output list of allocated blocks.
1264 * MUST contain single block as input to be trimmed.
1265 * On success will contain the newly allocated blocks
1266 * making up the @new_size. Blocks always appear in
1267 * ascending order
1268 *
1269 * For contiguous allocation, we round up the size to the nearest
1270 * power of two value, drivers consume *actual* size, so remaining
1271 * portions are unused and can be optionally freed with this function
1272 *
1273 * Returns:
1274 * 0 on success, error code on failure.
1275 */
1276int gpu_buddy_block_trim(struct gpu_buddy *mm,
1277 u64 *start,
1278 u64 new_size,
1279 struct list_head *blocks)
1280{
1281 struct gpu_buddy_block *parent;
1282 struct gpu_buddy_block *block;
1283 u64 block_start, block_end;
1284 LIST_HEAD(dfs);
1285 u64 new_start;
1286 int err;
1287
1288 gpu_buddy_driver_lock_held(mm);
1289
1290 if (!list_is_singular(blocks))
1291 return -EINVAL;
1292
1293 block = list_first_entry(blocks,
1294 struct gpu_buddy_block,
1295 link);
1296
1297 block_start = gpu_buddy_block_offset(block);
1298 block_end = block_start + gpu_buddy_block_size(mm, block);
1299
1300 if (WARN_ON(!gpu_buddy_block_is_allocated(block)))
1301 return -EINVAL;
1302
1303 if (new_size > gpu_buddy_block_size(mm, block))
1304 return -EINVAL;
1305
1306 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))
1307 return -EINVAL;
1308
1309 if (new_size == gpu_buddy_block_size(mm, block))
1310 return 0;
1311
1312 new_start = block_start;
1313 if (start) {
1314 new_start = *start;
1315
1316 if (new_start < block_start)
1317 return -EINVAL;
1318
1319 if (!IS_ALIGNED(new_start, mm->chunk_size))
1320 return -EINVAL;
1321
1322 if (range_overflows(new_start, new_size, block_end))
1323 return -EINVAL;
1324 }
1325
1326 list_del(&block->link);
1327 mark_free(mm, block);
1328 mm->avail += gpu_buddy_block_size(mm, block);
1329 if (gpu_buddy_block_is_clear(block))
1330 mm->clear_avail += gpu_buddy_block_size(mm, block);
1331
1332 /* Prevent recursively freeing this node */
1333 parent = block->parent;
1334 block->parent = NULL;
1335
1336 list_add(&block->tmp_link, &dfs);
1337 err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
1338 if (err) {
1339 mark_allocated(mm, block);
1340 mm->avail -= gpu_buddy_block_size(mm, block);
1341 if (gpu_buddy_block_is_clear(block))
1342 mm->clear_avail -= gpu_buddy_block_size(mm, block);
1343 list_add(&block->link, blocks);
1344 }
1345
1346 block->parent = parent;
1347 return err;
1348}
1349EXPORT_SYMBOL(gpu_buddy_block_trim);
1350
1351static struct gpu_buddy_block *
1352__gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
1353 u64 start, u64 end,
1354 u64 size, u64 min_block_size,
1355 unsigned int order,
1356 unsigned long flags)
1357{
1358 if (flags & GPU_BUDDY_RANGE_ALLOCATION)
1359 /* Allocate traversing within the range */
1360 return __gpu_buddy_alloc_range_bias(mm, start, end,
1361 order, flags);
1362 else if (size < min_block_size)
1363 /* Allocate from an offset-aligned region without size rounding */
1364 return gpu_buddy_offset_aligned_allocation(mm, size,
1365 min_block_size,
1366 flags);
1367 else
1368 /* Allocate from freetree */
1369 return alloc_from_freetree(mm, order, flags);
1370}
1371
1372/**
1373 * gpu_buddy_alloc_blocks - allocate power-of-two blocks
1374 *
1375 * @mm: GPU buddy manager to allocate from
1376 * @start: start of the allowed range for this block
1377 * @end: end of the allowed range for this block
1378 * @size: size of the allocation in bytes
1379 * @min_block_size: alignment of the allocation
1380 * @blocks: output list head to add allocated blocks
1381 * @flags: GPU_BUDDY_*_ALLOCATION flags
1382 *
1383 * alloc_range_bias() called on range limitations, which traverses
1384 * the tree and returns the desired block.
1385 *
1386 * alloc_from_freetree() called when *no* range restrictions
1387 * are enforced, which picks the block from the freetree.
1388 *
1389 * Returns:
1390 * 0 on success, error code on failure.
1391 */
1392int gpu_buddy_alloc_blocks(struct gpu_buddy *mm,
1393 u64 start, u64 end, u64 size,
1394 u64 min_block_size,
1395 struct list_head *blocks,
1396 unsigned long flags)
1397{
1398 struct gpu_buddy_block *block = NULL;
1399 u64 original_size, original_min_size;
1400 unsigned int min_order, order;
1401 LIST_HEAD(allocated);
1402 unsigned long pages;
1403 int err;
1404
1405 gpu_buddy_driver_lock_held(mm);
1406
1407 if (size < mm->chunk_size)
1408 return -EINVAL;
1409
1410 if (min_block_size < mm->chunk_size)
1411 return -EINVAL;
1412
1413 if (!is_power_of_2(min_block_size))
1414 return -EINVAL;
1415
1416 if (!IS_ALIGNED(start | end | size, mm->chunk_size))
1417 return -EINVAL;
1418
1419 if (end > mm->size)
1420 return -EINVAL;
1421
1422 if (range_overflows(start, size, mm->size))
1423 return -EINVAL;
1424
1425 /* Actual range allocation */
1426 if (start + size == end) {
1427 if (!IS_ALIGNED(start | end, min_block_size))
1428 return -EINVAL;
1429
1430 return __gpu_buddy_alloc_range(mm, start, size, NULL, blocks);
1431 }
1432
1433 original_size = size;
1434 original_min_size = min_block_size;
1435
1436 /* Roundup the size to power of 2 */
1437 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) {
1438 size = roundup_pow_of_two(size);
1439 min_block_size = size;
1440 /*
1441 * Normalize the requested size to min_block_size for regular allocations.
1442 * Offset-aligned allocations intentionally skip size rounding.
1443 */
1444 } else if (!gpu_buddy_can_offset_align(size, min_block_size)) {
1445 size = round_up(size, min_block_size);
1446 }
1447
1448 pages = size >> ilog2(mm->chunk_size);
1449 order = fls(pages) - 1;
1450 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
1451
1452 if (order > mm->max_order || size > mm->size) {
1453 if ((flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION) &&
1454 !(flags & GPU_BUDDY_RANGE_ALLOCATION))
1455 return __alloc_contig_try_harder(mm, original_size,
1456 original_min_size, blocks);
1457
1458 return -EINVAL;
1459 }
1460
1461 do {
1462 order = min(order, (unsigned int)fls(pages) - 1);
1463 BUG_ON(order > mm->max_order);
1464 /*
1465 * Regular allocations must not allocate blocks smaller than min_block_size.
1466 * Offset-aligned allocations deliberately bypass this constraint.
1467 */
1468 BUG_ON(size >= min_block_size && order < min_order);
1469
1470 do {
1471 unsigned int fallback_order;
1472
1473 block = __gpu_buddy_alloc_blocks(mm, start,
1474 end,
1475 size,
1476 min_block_size,
1477 order,
1478 flags);
1479 if (!IS_ERR(block))
1480 break;
1481
1482 if (size < min_block_size) {
1483 fallback_order = order;
1484 } else if (order == min_order) {
1485 fallback_order = min_order;
1486 } else {
1487 order--;
1488 continue;
1489 }
1490
1491 /* Try allocation through force merge method */
1492 if (mm->clear_avail &&
1493 !__force_merge(mm, start, end, fallback_order)) {
1494 block = __gpu_buddy_alloc_blocks(mm, start,
1495 end,
1496 size,
1497 min_block_size,
1498 fallback_order,
1499 flags);
1500 if (!IS_ERR(block)) {
1501 order = fallback_order;
1502 break;
1503 }
1504 }
1505
1506 /*
1507 * Try contiguous block allocation through
1508 * try harder method.
1509 */
1510 if (flags & GPU_BUDDY_CONTIGUOUS_ALLOCATION &&
1511 !(flags & GPU_BUDDY_RANGE_ALLOCATION))
1512 return __alloc_contig_try_harder(mm,
1513 original_size,
1514 original_min_size,
1515 blocks);
1516 err = -ENOSPC;
1517 goto err_free;
1518 } while (1);
1519
1520 mark_allocated(mm, block);
1521 mm->avail -= gpu_buddy_block_size(mm, block);
1522 if (gpu_buddy_block_is_clear(block))
1523 mm->clear_avail -= gpu_buddy_block_size(mm, block);
1524 kmemleak_update_trace(block);
1525 list_add_tail(&block->link, &allocated);
1526
1527 pages -= BIT(order);
1528
1529 if (!pages)
1530 break;
1531 } while (1);
1532
1533 /* Trim the allocated block to the required size */
1534 if (!(flags & GPU_BUDDY_TRIM_DISABLE) &&
1535 original_size != size) {
1536 struct list_head *trim_list;
1537 LIST_HEAD(temp);
1538 u64 trim_size;
1539
1540 trim_list = &allocated;
1541 trim_size = original_size;
1542
1543 if (!list_is_singular(&allocated)) {
1544 block = list_last_entry(&allocated, typeof(*block), link);
1545 list_move(&block->link, &temp);
1546 trim_list = &temp;
1547 trim_size = gpu_buddy_block_size(mm, block) -
1548 (size - original_size);
1549 }
1550
1551 gpu_buddy_block_trim(mm,
1552 NULL,
1553 trim_size,
1554 trim_list);
1555
1556 if (!list_empty(&temp))
1557 list_splice_tail(trim_list, &allocated);
1558 }
1559
1560 list_splice_tail(&allocated, blocks);
1561 return 0;
1562
1563err_free:
1564 gpu_buddy_free_list_internal(mm, &allocated);
1565 return err;
1566}
1567EXPORT_SYMBOL(gpu_buddy_alloc_blocks);
1568
1569/**
1570 * gpu_buddy_block_print - print block information
1571 *
1572 * @mm: GPU buddy manager
1573 * @block: GPU buddy block
1574 */
1575void gpu_buddy_block_print(struct gpu_buddy *mm,
1576 struct gpu_buddy_block *block)
1577{
1578 u64 start = gpu_buddy_block_offset(block);
1579 u64 size = gpu_buddy_block_size(mm, block);
1580
1581 pr_info("%#018llx-%#018llx: %llu\n", start, start + size, size);
1582}
1583EXPORT_SYMBOL(gpu_buddy_block_print);
1584
1585/**
1586 * gpu_buddy_print - print allocator state
1587 *
1588 * @mm: GPU buddy manager
1589 * @p: GPU printer to use
1590 */
1591void gpu_buddy_print(struct gpu_buddy *mm)
1592{
1593 int order;
1594
1595 gpu_buddy_driver_lock_held(mm);
1596 pr_info("chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n",
1597 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20);
1598
1599 for (order = mm->max_order; order >= 0; order--) {
1600 u64 free_count = mm->free_scoreboard[order];
1601 u64 used_count = mm->used_scoreboard[order];
1602 u64 block_size = mm->chunk_size << order;
1603 u64 free = free_count * block_size;
1604 u64 used = used_count * block_size;
1605
1606 if (block_size < SZ_1M)
1607 pr_info("order-%2d free: %8llu KiB, used: %8llu KiB, free_blocks: %llu, used_blocks: %llu\n",
1608 order, free >> 10, used >> 10, free_count, used_count);
1609 else
1610 pr_info("order-%2d free: %8llu MiB, used: %8llu MiB, free_blocks: %llu, used_blocks: %llu\n",
1611 order, free >> 20, used >> 20, free_count, used_count);
1612 }
1613}
1614EXPORT_SYMBOL(gpu_buddy_print);
1615
1616static void gpu_buddy_module_exit(void)
1617{
1618 kmem_cache_destroy(slab_blocks);
1619}
1620
1621static int __init gpu_buddy_module_init(void)
1622{
1623 slab_blocks = KMEM_CACHE(gpu_buddy_block, 0);
1624 if (!slab_blocks)
1625 return -ENOMEM;
1626
1627 return 0;
1628}
1629
1630module_init(gpu_buddy_module_init);
1631module_exit(gpu_buddy_module_exit);
1632
1633MODULE_DESCRIPTION("GPU Buddy Allocator");
1634MODULE_LICENSE("Dual MIT/GPL");