1 // SPDX-License-Identifier: MIT
3 * Copyright © 2021 Intel Corporation
6 #include <linux/kmemleak.h>
7 #include <linux/module.h>
8 #include <linux/sizes.h>
10 #include <drm/drm_buddy.h>
12 static struct kmem_cache
*slab_blocks
;
14 static struct drm_buddy_block
*drm_block_alloc(struct drm_buddy
*mm
,
15 struct drm_buddy_block
*parent
,
19 struct drm_buddy_block
*block
;
21 BUG_ON(order
> DRM_BUDDY_MAX_ORDER
);
23 block
= kmem_cache_zalloc(slab_blocks
, GFP_KERNEL
);
27 block
->header
= offset
;
28 block
->header
|= order
;
29 block
->parent
= parent
;
31 BUG_ON(block
->header
& DRM_BUDDY_HEADER_UNUSED
);
35 static void drm_block_free(struct drm_buddy
*mm
,
36 struct drm_buddy_block
*block
)
38 kmem_cache_free(slab_blocks
, block
);
41 static void list_insert_sorted(struct drm_buddy
*mm
,
42 struct drm_buddy_block
*block
)
44 struct drm_buddy_block
*node
;
45 struct list_head
*head
;
47 head
= &mm
->free_list
[drm_buddy_block_order(block
)];
48 if (list_empty(head
)) {
49 list_add(&block
->link
, head
);
53 list_for_each_entry(node
, head
, link
)
54 if (drm_buddy_block_offset(block
) < drm_buddy_block_offset(node
))
57 __list_add(&block
->link
, node
->link
.prev
, &node
->link
);
60 static void mark_allocated(struct drm_buddy_block
*block
)
62 block
->header
&= ~DRM_BUDDY_HEADER_STATE
;
63 block
->header
|= DRM_BUDDY_ALLOCATED
;
65 list_del(&block
->link
);
68 static void mark_free(struct drm_buddy
*mm
,
69 struct drm_buddy_block
*block
)
71 block
->header
&= ~DRM_BUDDY_HEADER_STATE
;
72 block
->header
|= DRM_BUDDY_FREE
;
74 list_insert_sorted(mm
, block
);
77 static void mark_split(struct drm_buddy_block
*block
)
79 block
->header
&= ~DRM_BUDDY_HEADER_STATE
;
80 block
->header
|= DRM_BUDDY_SPLIT
;
82 list_del(&block
->link
);
86 * drm_buddy_init - init memory manager
88 * @mm: DRM buddy manager to initialize
89 * @size: size in bytes to manage
90 * @chunk_size: minimum page size in bytes for our allocations
92 * Initializes the memory manager and its resources.
95 * 0 on success, error code on failure.
97 int drm_buddy_init(struct drm_buddy
*mm
, u64 size
, u64 chunk_size
)
102 if (size
< chunk_size
)
105 if (chunk_size
< PAGE_SIZE
)
108 if (!is_power_of_2(chunk_size
))
111 size
= round_down(size
, chunk_size
);
115 mm
->chunk_size
= chunk_size
;
116 mm
->max_order
= ilog2(size
) - ilog2(chunk_size
);
118 BUG_ON(mm
->max_order
> DRM_BUDDY_MAX_ORDER
);
120 mm
->free_list
= kmalloc_array(mm
->max_order
+ 1,
121 sizeof(struct list_head
),
126 for (i
= 0; i
<= mm
->max_order
; ++i
)
127 INIT_LIST_HEAD(&mm
->free_list
[i
]);
129 mm
->n_roots
= hweight64(size
);
131 mm
->roots
= kmalloc_array(mm
->n_roots
,
132 sizeof(struct drm_buddy_block
*),
141 * Split into power-of-two blocks, in case we are given a size that is
142 * not itself a power-of-two.
145 struct drm_buddy_block
*root
;
149 order
= ilog2(size
) - ilog2(chunk_size
);
150 root_size
= chunk_size
<< order
;
152 root
= drm_block_alloc(mm
, NULL
, order
, offset
);
158 BUG_ON(i
> mm
->max_order
);
159 BUG_ON(drm_buddy_block_size(mm
, root
) < chunk_size
);
172 drm_block_free(mm
, mm
->roots
[i
]);
175 kfree(mm
->free_list
);
178 EXPORT_SYMBOL(drm_buddy_init
);
181 * drm_buddy_fini - tear down the memory manager
183 * @mm: DRM buddy manager to free
185 * Cleanup memory manager resources and the freelist
187 void drm_buddy_fini(struct drm_buddy
*mm
)
191 for (i
= 0; i
< mm
->n_roots
; ++i
) {
192 WARN_ON(!drm_buddy_block_is_free(mm
->roots
[i
]));
193 drm_block_free(mm
, mm
->roots
[i
]);
196 WARN_ON(mm
->avail
!= mm
->size
);
199 kfree(mm
->free_list
);
201 EXPORT_SYMBOL(drm_buddy_fini
);
203 static int split_block(struct drm_buddy
*mm
,
204 struct drm_buddy_block
*block
)
206 unsigned int block_order
= drm_buddy_block_order(block
) - 1;
207 u64 offset
= drm_buddy_block_offset(block
);
209 BUG_ON(!drm_buddy_block_is_free(block
));
210 BUG_ON(!drm_buddy_block_order(block
));
212 block
->left
= drm_block_alloc(mm
, block
, block_order
, offset
);
216 block
->right
= drm_block_alloc(mm
, block
, block_order
,
217 offset
+ (mm
->chunk_size
<< block_order
));
219 drm_block_free(mm
, block
->left
);
223 mark_free(mm
, block
->left
);
224 mark_free(mm
, block
->right
);
231 static struct drm_buddy_block
*
232 __get_buddy(struct drm_buddy_block
*block
)
234 struct drm_buddy_block
*parent
;
236 parent
= block
->parent
;
240 if (parent
->left
== block
)
241 return parent
->right
;
247 * drm_get_buddy - get buddy address
249 * @block: DRM buddy block
251 * Returns the corresponding buddy block for @block, or NULL
252 * if this is a root block and can't be merged further.
253 * Requires some kind of locking to protect against
254 * any concurrent allocate and free operations.
256 struct drm_buddy_block
*
257 drm_get_buddy(struct drm_buddy_block
*block
)
259 return __get_buddy(block
);
261 EXPORT_SYMBOL(drm_get_buddy
);
263 static void __drm_buddy_free(struct drm_buddy
*mm
,
264 struct drm_buddy_block
*block
)
266 struct drm_buddy_block
*parent
;
268 while ((parent
= block
->parent
)) {
269 struct drm_buddy_block
*buddy
;
271 buddy
= __get_buddy(block
);
273 if (!drm_buddy_block_is_free(buddy
))
276 list_del(&buddy
->link
);
278 drm_block_free(mm
, block
);
279 drm_block_free(mm
, buddy
);
284 mark_free(mm
, block
);
288 * drm_buddy_free_block - free a block
290 * @mm: DRM buddy manager
291 * @block: block to be freed
293 void drm_buddy_free_block(struct drm_buddy
*mm
,
294 struct drm_buddy_block
*block
)
296 BUG_ON(!drm_buddy_block_is_allocated(block
));
297 mm
->avail
+= drm_buddy_block_size(mm
, block
);
298 __drm_buddy_free(mm
, block
);
300 EXPORT_SYMBOL(drm_buddy_free_block
);
303 * drm_buddy_free_list - free blocks
305 * @mm: DRM buddy manager
306 * @objects: input list head to free blocks
308 void drm_buddy_free_list(struct drm_buddy
*mm
, struct list_head
*objects
)
310 struct drm_buddy_block
*block
, *on
;
312 list_for_each_entry_safe(block
, on
, objects
, link
) {
313 drm_buddy_free_block(mm
, block
);
316 INIT_LIST_HEAD(objects
);
318 EXPORT_SYMBOL(drm_buddy_free_list
);
320 static inline bool overlaps(u64 s1
, u64 e1
, u64 s2
, u64 e2
)
322 return s1
<= e2
&& e1
>= s2
;
325 static inline bool contains(u64 s1
, u64 e1
, u64 s2
, u64 e2
)
327 return s1
<= s2
&& e1
>= e2
;
330 static struct drm_buddy_block
*
331 alloc_range_bias(struct drm_buddy
*mm
,
335 struct drm_buddy_block
*block
;
336 struct drm_buddy_block
*buddy
;
343 for (i
= 0; i
< mm
->n_roots
; ++i
)
344 list_add_tail(&mm
->roots
[i
]->tmp_link
, &dfs
);
350 block
= list_first_entry_or_null(&dfs
,
351 struct drm_buddy_block
,
356 list_del(&block
->tmp_link
);
358 if (drm_buddy_block_order(block
) < order
)
361 block_start
= drm_buddy_block_offset(block
);
362 block_end
= block_start
+ drm_buddy_block_size(mm
, block
) - 1;
364 if (!overlaps(start
, end
, block_start
, block_end
))
367 if (drm_buddy_block_is_allocated(block
))
370 if (contains(start
, end
, block_start
, block_end
) &&
371 order
== drm_buddy_block_order(block
)) {
373 * Find the free block within the range.
375 if (drm_buddy_block_is_free(block
))
381 if (!drm_buddy_block_is_split(block
)) {
382 err
= split_block(mm
, block
);
387 list_add(&block
->right
->tmp_link
, &dfs
);
388 list_add(&block
->left
->tmp_link
, &dfs
);
391 return ERR_PTR(-ENOSPC
);
395 * We really don't want to leave around a bunch of split blocks, since
396 * bigger is better, so make sure we merge everything back before we
397 * free the allocated blocks.
399 buddy
= __get_buddy(block
);
401 (drm_buddy_block_is_free(block
) &&
402 drm_buddy_block_is_free(buddy
)))
403 __drm_buddy_free(mm
, block
);
407 static struct drm_buddy_block
*
408 get_maxblock(struct drm_buddy
*mm
, unsigned int order
)
410 struct drm_buddy_block
*max_block
= NULL
, *node
;
413 for (i
= order
; i
<= mm
->max_order
; ++i
) {
414 if (!list_empty(&mm
->free_list
[i
])) {
415 node
= list_last_entry(&mm
->free_list
[i
],
416 struct drm_buddy_block
,
423 if (drm_buddy_block_offset(node
) >
424 drm_buddy_block_offset(max_block
)) {
433 static struct drm_buddy_block
*
434 alloc_from_freelist(struct drm_buddy
*mm
,
438 struct drm_buddy_block
*block
= NULL
;
442 if (flags
& DRM_BUDDY_TOPDOWN_ALLOCATION
) {
443 block
= get_maxblock(mm
, order
);
445 /* Store the obtained block order */
446 tmp
= drm_buddy_block_order(block
);
448 for (tmp
= order
; tmp
<= mm
->max_order
; ++tmp
) {
449 if (!list_empty(&mm
->free_list
[tmp
])) {
450 block
= list_last_entry(&mm
->free_list
[tmp
],
451 struct drm_buddy_block
,
460 return ERR_PTR(-ENOSPC
);
462 BUG_ON(!drm_buddy_block_is_free(block
));
464 while (tmp
!= order
) {
465 err
= split_block(mm
, block
);
469 block
= block
->right
;
476 __drm_buddy_free(mm
, block
);
480 static int __alloc_range(struct drm_buddy
*mm
,
481 struct list_head
*dfs
,
483 struct list_head
*blocks
,
484 u64
*total_allocated_on_err
)
486 struct drm_buddy_block
*block
;
487 struct drm_buddy_block
*buddy
;
488 u64 total_allocated
= 0;
489 LIST_HEAD(allocated
);
493 end
= start
+ size
- 1;
499 block
= list_first_entry_or_null(dfs
,
500 struct drm_buddy_block
,
505 list_del(&block
->tmp_link
);
507 block_start
= drm_buddy_block_offset(block
);
508 block_end
= block_start
+ drm_buddy_block_size(mm
, block
) - 1;
510 if (!overlaps(start
, end
, block_start
, block_end
))
513 if (drm_buddy_block_is_allocated(block
)) {
518 if (contains(start
, end
, block_start
, block_end
)) {
519 if (!drm_buddy_block_is_free(block
)) {
524 mark_allocated(block
);
525 total_allocated
+= drm_buddy_block_size(mm
, block
);
526 mm
->avail
-= drm_buddy_block_size(mm
, block
);
527 list_add_tail(&block
->link
, &allocated
);
531 if (!drm_buddy_block_is_split(block
)) {
532 err
= split_block(mm
, block
);
537 list_add(&block
->right
->tmp_link
, dfs
);
538 list_add(&block
->left
->tmp_link
, dfs
);
541 list_splice_tail(&allocated
, blocks
);
546 * We really don't want to leave around a bunch of split blocks, since
547 * bigger is better, so make sure we merge everything back before we
548 * free the allocated blocks.
550 buddy
= __get_buddy(block
);
552 (drm_buddy_block_is_free(block
) &&
553 drm_buddy_block_is_free(buddy
)))
554 __drm_buddy_free(mm
, block
);
557 if (err
== -ENOSPC
&& total_allocated_on_err
) {
558 list_splice_tail(&allocated
, blocks
);
559 *total_allocated_on_err
= total_allocated
;
561 drm_buddy_free_list(mm
, &allocated
);
567 static int __drm_buddy_alloc_range(struct drm_buddy
*mm
,
570 u64
*total_allocated_on_err
,
571 struct list_head
*blocks
)
576 for (i
= 0; i
< mm
->n_roots
; ++i
)
577 list_add_tail(&mm
->roots
[i
]->tmp_link
, &dfs
);
579 return __alloc_range(mm
, &dfs
, start
, size
,
580 blocks
, total_allocated_on_err
);
583 static int __alloc_contig_try_harder(struct drm_buddy
*mm
,
586 struct list_head
*blocks
)
588 u64 rhs_offset
, lhs_offset
, lhs_size
, filled
;
589 struct drm_buddy_block
*block
;
590 struct list_head
*list
;
591 LIST_HEAD(blocks_lhs
);
597 modify_size
= rounddown_pow_of_two(size
);
598 pages
= modify_size
>> ilog2(mm
->chunk_size
);
599 order
= fls(pages
) - 1;
603 list
= &mm
->free_list
[order
];
604 if (list_empty(list
))
607 list_for_each_entry_reverse(block
, list
, link
) {
608 /* Allocate blocks traversing RHS */
609 rhs_offset
= drm_buddy_block_offset(block
);
610 err
= __drm_buddy_alloc_range(mm
, rhs_offset
, size
,
612 if (!err
|| err
!= -ENOSPC
)
615 lhs_size
= max((size
- filled
), min_block_size
);
616 if (!IS_ALIGNED(lhs_size
, min_block_size
))
617 lhs_size
= round_up(lhs_size
, min_block_size
);
619 /* Allocate blocks traversing LHS */
620 lhs_offset
= drm_buddy_block_offset(block
) - lhs_size
;
621 err
= __drm_buddy_alloc_range(mm
, lhs_offset
, lhs_size
,
624 list_splice(&blocks_lhs
, blocks
);
626 } else if (err
!= -ENOSPC
) {
627 drm_buddy_free_list(mm
, blocks
);
630 /* Free blocks for the next iteration */
631 drm_buddy_free_list(mm
, blocks
);
638 * drm_buddy_block_trim - free unused pages
640 * @mm: DRM buddy manager
641 * @new_size: original size requested
642 * @blocks: Input and output list of allocated blocks.
643 * MUST contain single block as input to be trimmed.
644 * On success will contain the newly allocated blocks
645 * making up the @new_size. Blocks always appear in
648 * For contiguous allocation, we round up the size to the nearest
649 * power of two value, drivers consume *actual* size, so remaining
650 * portions are unused and can be optionally freed with this function
653 * 0 on success, error code on failure.
655 int drm_buddy_block_trim(struct drm_buddy
*mm
,
657 struct list_head
*blocks
)
659 struct drm_buddy_block
*parent
;
660 struct drm_buddy_block
*block
;
665 if (!list_is_singular(blocks
))
668 block
= list_first_entry(blocks
,
669 struct drm_buddy_block
,
672 if (WARN_ON(!drm_buddy_block_is_allocated(block
)))
675 if (new_size
> drm_buddy_block_size(mm
, block
))
678 if (!new_size
|| !IS_ALIGNED(new_size
, mm
->chunk_size
))
681 if (new_size
== drm_buddy_block_size(mm
, block
))
684 list_del(&block
->link
);
685 mark_free(mm
, block
);
686 mm
->avail
+= drm_buddy_block_size(mm
, block
);
688 /* Prevent recursively freeing this node */
689 parent
= block
->parent
;
690 block
->parent
= NULL
;
692 new_start
= drm_buddy_block_offset(block
);
693 list_add(&block
->tmp_link
, &dfs
);
694 err
= __alloc_range(mm
, &dfs
, new_start
, new_size
, blocks
, NULL
);
696 mark_allocated(block
);
697 mm
->avail
-= drm_buddy_block_size(mm
, block
);
698 list_add(&block
->link
, blocks
);
701 block
->parent
= parent
;
704 EXPORT_SYMBOL(drm_buddy_block_trim
);
707 * drm_buddy_alloc_blocks - allocate power-of-two blocks
709 * @mm: DRM buddy manager to allocate from
710 * @start: start of the allowed range for this block
711 * @end: end of the allowed range for this block
712 * @size: size of the allocation
713 * @min_block_size: alignment of the allocation
714 * @blocks: output list head to add allocated blocks
715 * @flags: DRM_BUDDY_*_ALLOCATION flags
717 * alloc_range_bias() called on range limitations, which traverses
718 * the tree and returns the desired block.
720 * alloc_from_freelist() called when *no* range restrictions
721 * are enforced, which picks the block from the freelist.
724 * 0 on success, error code on failure.
726 int drm_buddy_alloc_blocks(struct drm_buddy
*mm
,
727 u64 start
, u64 end
, u64 size
,
729 struct list_head
*blocks
,
732 struct drm_buddy_block
*block
= NULL
;
733 u64 original_size
, original_min_size
;
734 unsigned int min_order
, order
;
735 LIST_HEAD(allocated
);
739 if (size
< mm
->chunk_size
)
742 if (min_block_size
< mm
->chunk_size
)
745 if (!is_power_of_2(min_block_size
))
748 if (!IS_ALIGNED(start
| end
| size
, mm
->chunk_size
))
754 if (range_overflows(start
, size
, mm
->size
))
757 /* Actual range allocation */
758 if (start
+ size
== end
)
759 return __drm_buddy_alloc_range(mm
, start
, size
, NULL
, blocks
);
761 original_size
= size
;
762 original_min_size
= min_block_size
;
764 /* Roundup the size to power of 2 */
765 if (flags
& DRM_BUDDY_CONTIGUOUS_ALLOCATION
) {
766 size
= roundup_pow_of_two(size
);
767 min_block_size
= size
;
768 /* Align size value to min_block_size */
769 } else if (!IS_ALIGNED(size
, min_block_size
)) {
770 size
= round_up(size
, min_block_size
);
773 pages
= size
>> ilog2(mm
->chunk_size
);
774 order
= fls(pages
) - 1;
775 min_order
= ilog2(min_block_size
) - ilog2(mm
->chunk_size
);
778 order
= min(order
, (unsigned int)fls(pages
) - 1);
779 BUG_ON(order
> mm
->max_order
);
780 BUG_ON(order
< min_order
);
783 if (flags
& DRM_BUDDY_RANGE_ALLOCATION
)
784 /* Allocate traversing within the range */
785 block
= alloc_range_bias(mm
, start
, end
, order
);
787 /* Allocate from freelist */
788 block
= alloc_from_freelist(mm
, order
, flags
);
793 if (order
-- == min_order
) {
794 if (flags
& DRM_BUDDY_CONTIGUOUS_ALLOCATION
&&
795 !(flags
& DRM_BUDDY_RANGE_ALLOCATION
))
797 * Try contiguous block allocation through
800 return __alloc_contig_try_harder(mm
,
809 mark_allocated(block
);
810 mm
->avail
-= drm_buddy_block_size(mm
, block
);
811 kmemleak_update_trace(block
);
812 list_add_tail(&block
->link
, &allocated
);
820 /* Trim the allocated block to the required size */
821 if (original_size
!= size
) {
822 struct list_head
*trim_list
;
826 trim_list
= &allocated
;
827 trim_size
= original_size
;
829 if (!list_is_singular(&allocated
)) {
830 block
= list_last_entry(&allocated
, typeof(*block
), link
);
831 list_move(&block
->link
, &temp
);
833 trim_size
= drm_buddy_block_size(mm
, block
) -
834 (size
- original_size
);
837 drm_buddy_block_trim(mm
,
841 if (!list_empty(&temp
))
842 list_splice_tail(trim_list
, &allocated
);
845 list_splice_tail(&allocated
, blocks
);
849 drm_buddy_free_list(mm
, &allocated
);
852 EXPORT_SYMBOL(drm_buddy_alloc_blocks
);
855 * drm_buddy_block_print - print block information
857 * @mm: DRM buddy manager
858 * @block: DRM buddy block
859 * @p: DRM printer to use
861 void drm_buddy_block_print(struct drm_buddy
*mm
,
862 struct drm_buddy_block
*block
,
863 struct drm_printer
*p
)
865 u64 start
= drm_buddy_block_offset(block
);
866 u64 size
= drm_buddy_block_size(mm
, block
);
868 drm_printf(p
, "%#018llx-%#018llx: %llu\n", start
, start
+ size
, size
);
870 EXPORT_SYMBOL(drm_buddy_block_print
);
873 * drm_buddy_print - print allocator state
875 * @mm: DRM buddy manager
876 * @p: DRM printer to use
878 void drm_buddy_print(struct drm_buddy
*mm
, struct drm_printer
*p
)
882 drm_printf(p
, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB\n",
883 mm
->chunk_size
>> 10, mm
->size
>> 20, mm
->avail
>> 20);
885 for (order
= mm
->max_order
; order
>= 0; order
--) {
886 struct drm_buddy_block
*block
;
889 list_for_each_entry(block
, &mm
->free_list
[order
], link
) {
890 BUG_ON(!drm_buddy_block_is_free(block
));
894 drm_printf(p
, "order-%2d ", order
);
896 free
= count
* (mm
->chunk_size
<< order
);
898 drm_printf(p
, "free: %8llu KiB", free
>> 10);
900 drm_printf(p
, "free: %8llu MiB", free
>> 20);
902 drm_printf(p
, ", blocks: %llu\n", count
);
905 EXPORT_SYMBOL(drm_buddy_print
);
907 static void drm_buddy_module_exit(void)
909 kmem_cache_destroy(slab_blocks
);
912 static int __init
drm_buddy_module_init(void)
914 slab_blocks
= KMEM_CACHE(drm_buddy_block
, 0);
921 module_init(drm_buddy_module_init
);
922 module_exit(drm_buddy_module_exit
);
924 MODULE_DESCRIPTION("DRM Buddy Allocator");
925 MODULE_LICENSE("Dual MIT/GPL");