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

source code of linux/drivers/gpu/drm/drm_buddy.c