1// SPDX-License-Identifier: MIT
2/*
3 * Copyright © 2021 Intel Corporation
4 */
5
6#include <linux/kmemleak.h>
7#include <linux/module.h>
8#include <linux/sizes.h>
9
10#include <drm/drm_buddy.h>
11
12static struct kmem_cache *slab_blocks;
13
14static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm,
15 struct drm_buddy_block *parent,
16 unsigned int order,
17 u64 offset)
18{
19 struct drm_buddy_block *block;
20
21 BUG_ON(order > DRM_BUDDY_MAX_ORDER);
22
23 block = kmem_cache_zalloc(k: slab_blocks, GFP_KERNEL);
24 if (!block)
25 return NULL;
26
27 block->header = offset;
28 block->header |= order;
29 block->parent = parent;
30
31 BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
32 return block;
33}
34
35static void drm_block_free(struct drm_buddy *mm,
36 struct drm_buddy_block *block)
37{
38 kmem_cache_free(s: slab_blocks, objp: block);
39}
40
41static void list_insert_sorted(struct drm_buddy *mm,
42 struct drm_buddy_block *block)
43{
44 struct drm_buddy_block *node;
45 struct list_head *head;
46
47 head = &mm->free_list[drm_buddy_block_order(block)];
48 if (list_empty(head)) {
49 list_add(new: &block->link, head);
50 return;
51 }
52
53 list_for_each_entry(node, head, link)
54 if (drm_buddy_block_offset(block) < drm_buddy_block_offset(block: node))
55 break;
56
57 __list_add(new: &block->link, prev: node->link.prev, next: &node->link);
58}
59
60static void mark_allocated(struct drm_buddy_block *block)
61{
62 block->header &= ~DRM_BUDDY_HEADER_STATE;
63 block->header |= DRM_BUDDY_ALLOCATED;
64
65 list_del(entry: &block->link);
66}
67
68static void mark_free(struct drm_buddy *mm,
69 struct drm_buddy_block *block)
70{
71 block->header &= ~DRM_BUDDY_HEADER_STATE;
72 block->header |= DRM_BUDDY_FREE;
73
74 list_insert_sorted(mm, block);
75}
76
77static void mark_split(struct drm_buddy_block *block)
78{
79 block->header &= ~DRM_BUDDY_HEADER_STATE;
80 block->header |= DRM_BUDDY_SPLIT;
81
82 list_del(entry: &block->link);
83}
84
85/**
86 * drm_buddy_init - init memory manager
87 *
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
91 *
92 * Initializes the memory manager and its resources.
93 *
94 * Returns:
95 * 0 on success, error code on failure.
96 */
97int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
98{
99 unsigned int i;
100 u64 offset;
101
102 if (size < chunk_size)
103 return -EINVAL;
104
105 if (chunk_size < PAGE_SIZE)
106 return -EINVAL;
107
108 if (!is_power_of_2(n: chunk_size))
109 return -EINVAL;
110
111 size = round_down(size, chunk_size);
112
113 mm->size = size;
114 mm->avail = size;
115 mm->chunk_size = chunk_size;
116 mm->max_order = ilog2(size) - ilog2(chunk_size);
117
118 BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
119
120 mm->free_list = kmalloc_array(n: mm->max_order + 1,
121 size: sizeof(struct list_head),
122 GFP_KERNEL);
123 if (!mm->free_list)
124 return -ENOMEM;
125
126 for (i = 0; i <= mm->max_order; ++i)
127 INIT_LIST_HEAD(list: &mm->free_list[i]);
128
129 mm->n_roots = hweight64(size);
130
131 mm->roots = kmalloc_array(n: mm->n_roots,
132 size: sizeof(struct drm_buddy_block *),
133 GFP_KERNEL);
134 if (!mm->roots)
135 goto out_free_list;
136
137 offset = 0;
138 i = 0;
139
140 /*
141 * Split into power-of-two blocks, in case we are given a size that is
142 * not itself a power-of-two.
143 */
144 do {
145 struct drm_buddy_block *root;
146 unsigned int order;
147 u64 root_size;
148
149 order = ilog2(size) - ilog2(chunk_size);
150 root_size = chunk_size << order;
151
152 root = drm_block_alloc(mm, NULL, order, offset);
153 if (!root)
154 goto out_free_roots;
155
156 mark_free(mm, block: root);
157
158 BUG_ON(i > mm->max_order);
159 BUG_ON(drm_buddy_block_size(mm, root) < chunk_size);
160
161 mm->roots[i] = root;
162
163 offset += root_size;
164 size -= root_size;
165 i++;
166 } while (size);
167
168 return 0;
169
170out_free_roots:
171 while (i--)
172 drm_block_free(mm, block: mm->roots[i]);
173 kfree(objp: mm->roots);
174out_free_list:
175 kfree(objp: mm->free_list);
176 return -ENOMEM;
177}
178EXPORT_SYMBOL(drm_buddy_init);
179
180/**
181 * drm_buddy_fini - tear down the memory manager
182 *
183 * @mm: DRM buddy manager to free
184 *
185 * Cleanup memory manager resources and the freelist
186 */
187void drm_buddy_fini(struct drm_buddy *mm)
188{
189 int i;
190
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, block: mm->roots[i]);
194 }
195
196 WARN_ON(mm->avail != mm->size);
197
198 kfree(objp: mm->roots);
199 kfree(objp: mm->free_list);
200}
201EXPORT_SYMBOL(drm_buddy_fini);
202
203static int split_block(struct drm_buddy *mm,
204 struct drm_buddy_block *block)
205{
206 unsigned int block_order = drm_buddy_block_order(block) - 1;
207 u64 offset = drm_buddy_block_offset(block);
208
209 BUG_ON(!drm_buddy_block_is_free(block));
210 BUG_ON(!drm_buddy_block_order(block));
211
212 block->left = drm_block_alloc(mm, parent: block, order: block_order, offset);
213 if (!block->left)
214 return -ENOMEM;
215
216 block->right = drm_block_alloc(mm, parent: block, order: block_order,
217 offset: offset + (mm->chunk_size << block_order));
218 if (!block->right) {
219 drm_block_free(mm, block: block->left);
220 return -ENOMEM;
221 }
222
223 mark_free(mm, block: block->left);
224 mark_free(mm, block: block->right);
225
226 mark_split(block);
227
228 return 0;
229}
230
231static struct drm_buddy_block *
232__get_buddy(struct drm_buddy_block *block)
233{
234 struct drm_buddy_block *parent;
235
236 parent = block->parent;
237 if (!parent)
238 return NULL;
239
240 if (parent->left == block)
241 return parent->right;
242
243 return parent->left;
244}
245
246/**
247 * drm_get_buddy - get buddy address
248 *
249 * @block: DRM buddy block
250 *
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.
255 */
256struct drm_buddy_block *
257drm_get_buddy(struct drm_buddy_block *block)
258{
259 return __get_buddy(block);
260}
261EXPORT_SYMBOL(drm_get_buddy);
262
263static void __drm_buddy_free(struct drm_buddy *mm,
264 struct drm_buddy_block *block)
265{
266 struct drm_buddy_block *parent;
267
268 while ((parent = block->parent)) {
269 struct drm_buddy_block *buddy;
270
271 buddy = __get_buddy(block);
272
273 if (!drm_buddy_block_is_free(block: buddy))
274 break;
275
276 list_del(entry: &buddy->link);
277
278 drm_block_free(mm, block);
279 drm_block_free(mm, block: buddy);
280
281 block = parent;
282 }
283
284 mark_free(mm, block);
285}
286
287/**
288 * drm_buddy_free_block - free a block
289 *
290 * @mm: DRM buddy manager
291 * @block: block to be freed
292 */
293void drm_buddy_free_block(struct drm_buddy *mm,
294 struct drm_buddy_block *block)
295{
296 BUG_ON(!drm_buddy_block_is_allocated(block));
297 mm->avail += drm_buddy_block_size(mm, block);
298 __drm_buddy_free(mm, block);
299}
300EXPORT_SYMBOL(drm_buddy_free_block);
301
302/**
303 * drm_buddy_free_list - free blocks
304 *
305 * @mm: DRM buddy manager
306 * @objects: input list head to free blocks
307 */
308void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects)
309{
310 struct drm_buddy_block *block, *on;
311
312 list_for_each_entry_safe(block, on, objects, link) {
313 drm_buddy_free_block(mm, block);
314 cond_resched();
315 }
316 INIT_LIST_HEAD(list: objects);
317}
318EXPORT_SYMBOL(drm_buddy_free_list);
319
320static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
321{
322 return s1 <= e2 && e1 >= s2;
323}
324
325static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
326{
327 return s1 <= s2 && e1 >= e2;
328}
329
330static struct drm_buddy_block *
331alloc_range_bias(struct drm_buddy *mm,
332 u64 start, u64 end,
333 unsigned int order)
334{
335 u64 req_size = mm->chunk_size << order;
336 struct drm_buddy_block *block;
337 struct drm_buddy_block *buddy;
338 LIST_HEAD(dfs);
339 int err;
340 int i;
341
342 end = end - 1;
343
344 for (i = 0; i < mm->n_roots; ++i)
345 list_add_tail(new: &mm->roots[i]->tmp_link, head: &dfs);
346
347 do {
348 u64 block_start;
349 u64 block_end;
350
351 block = list_first_entry_or_null(&dfs,
352 struct drm_buddy_block,
353 tmp_link);
354 if (!block)
355 break;
356
357 list_del(entry: &block->tmp_link);
358
359 if (drm_buddy_block_order(block) < order)
360 continue;
361
362 block_start = drm_buddy_block_offset(block);
363 block_end = block_start + drm_buddy_block_size(mm, block) - 1;
364
365 if (!overlaps(s1: start, e1: end, s2: block_start, e2: block_end))
366 continue;
367
368 if (drm_buddy_block_is_allocated(block))
369 continue;
370
371 if (block_start < start || block_end > end) {
372 u64 adjusted_start = max(block_start, start);
373 u64 adjusted_end = min(block_end, end);
374
375 if (round_down(adjusted_end + 1, req_size) <=
376 round_up(adjusted_start, req_size))
377 continue;
378 }
379
380 if (contains(s1: start, e1: end, s2: block_start, e2: block_end) &&
381 order == drm_buddy_block_order(block)) {
382 /*
383 * Find the free block within the range.
384 */
385 if (drm_buddy_block_is_free(block))
386 return block;
387
388 continue;
389 }
390
391 if (!drm_buddy_block_is_split(block)) {
392 err = split_block(mm, block);
393 if (unlikely(err))
394 goto err_undo;
395 }
396
397 list_add(new: &block->right->tmp_link, head: &dfs);
398 list_add(new: &block->left->tmp_link, head: &dfs);
399 } while (1);
400
401 return ERR_PTR(error: -ENOSPC);
402
403err_undo:
404 /*
405 * We really don't want to leave around a bunch of split blocks, since
406 * bigger is better, so make sure we merge everything back before we
407 * free the allocated blocks.
408 */
409 buddy = __get_buddy(block);
410 if (buddy &&
411 (drm_buddy_block_is_free(block) &&
412 drm_buddy_block_is_free(block: buddy)))
413 __drm_buddy_free(mm, block);
414 return ERR_PTR(error: err);
415}
416
417static struct drm_buddy_block *
418get_maxblock(struct drm_buddy *mm, unsigned int order)
419{
420 struct drm_buddy_block *max_block = NULL, *node;
421 unsigned int i;
422
423 for (i = order; i <= mm->max_order; ++i) {
424 if (!list_empty(head: &mm->free_list[i])) {
425 node = list_last_entry(&mm->free_list[i],
426 struct drm_buddy_block,
427 link);
428 if (!max_block) {
429 max_block = node;
430 continue;
431 }
432
433 if (drm_buddy_block_offset(block: node) >
434 drm_buddy_block_offset(block: max_block)) {
435 max_block = node;
436 }
437 }
438 }
439
440 return max_block;
441}
442
443static struct drm_buddy_block *
444alloc_from_freelist(struct drm_buddy *mm,
445 unsigned int order,
446 unsigned long flags)
447{
448 struct drm_buddy_block *block = NULL;
449 unsigned int tmp;
450 int err;
451
452 if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) {
453 block = get_maxblock(mm, order);
454 if (block)
455 /* Store the obtained block order */
456 tmp = drm_buddy_block_order(block);
457 } else {
458 for (tmp = order; tmp <= mm->max_order; ++tmp) {
459 if (!list_empty(head: &mm->free_list[tmp])) {
460 block = list_last_entry(&mm->free_list[tmp],
461 struct drm_buddy_block,
462 link);
463 if (block)
464 break;
465 }
466 }
467 }
468
469 if (!block)
470 return ERR_PTR(error: -ENOSPC);
471
472 BUG_ON(!drm_buddy_block_is_free(block));
473
474 while (tmp != order) {
475 err = split_block(mm, block);
476 if (unlikely(err))
477 goto err_undo;
478
479 block = block->right;
480 tmp--;
481 }
482 return block;
483
484err_undo:
485 if (tmp != order)
486 __drm_buddy_free(mm, block);
487 return ERR_PTR(error: err);
488}
489
490static int __alloc_range(struct drm_buddy *mm,
491 struct list_head *dfs,
492 u64 start, u64 size,
493 struct list_head *blocks,
494 u64 *total_allocated_on_err)
495{
496 struct drm_buddy_block *block;
497 struct drm_buddy_block *buddy;
498 u64 total_allocated = 0;
499 LIST_HEAD(allocated);
500 u64 end;
501 int err;
502
503 end = start + size - 1;
504
505 do {
506 u64 block_start;
507 u64 block_end;
508
509 block = list_first_entry_or_null(dfs,
510 struct drm_buddy_block,
511 tmp_link);
512 if (!block)
513 break;
514
515 list_del(entry: &block->tmp_link);
516
517 block_start = drm_buddy_block_offset(block);
518 block_end = block_start + drm_buddy_block_size(mm, block) - 1;
519
520 if (!overlaps(s1: start, e1: end, s2: block_start, e2: block_end))
521 continue;
522
523 if (drm_buddy_block_is_allocated(block)) {
524 err = -ENOSPC;
525 goto err_free;
526 }
527
528 if (contains(s1: start, e1: end, s2: block_start, e2: block_end)) {
529 if (!drm_buddy_block_is_free(block)) {
530 err = -ENOSPC;
531 goto err_free;
532 }
533
534 mark_allocated(block);
535 total_allocated += drm_buddy_block_size(mm, block);
536 mm->avail -= drm_buddy_block_size(mm, block);
537 list_add_tail(new: &block->link, head: &allocated);
538 continue;
539 }
540
541 if (!drm_buddy_block_is_split(block)) {
542 err = split_block(mm, block);
543 if (unlikely(err))
544 goto err_undo;
545 }
546
547 list_add(new: &block->right->tmp_link, head: dfs);
548 list_add(new: &block->left->tmp_link, head: dfs);
549 } while (1);
550
551 if (total_allocated < size) {
552 err = -ENOSPC;
553 goto err_free;
554 }
555
556 list_splice_tail(list: &allocated, head: blocks);
557
558 return 0;
559
560err_undo:
561 /*
562 * We really don't want to leave around a bunch of split blocks, since
563 * bigger is better, so make sure we merge everything back before we
564 * free the allocated blocks.
565 */
566 buddy = __get_buddy(block);
567 if (buddy &&
568 (drm_buddy_block_is_free(block) &&
569 drm_buddy_block_is_free(block: buddy)))
570 __drm_buddy_free(mm, block);
571
572err_free:
573 if (err == -ENOSPC && total_allocated_on_err) {
574 list_splice_tail(list: &allocated, head: blocks);
575 *total_allocated_on_err = total_allocated;
576 } else {
577 drm_buddy_free_list(mm, &allocated);
578 }
579
580 return err;
581}
582
583static int __drm_buddy_alloc_range(struct drm_buddy *mm,
584 u64 start,
585 u64 size,
586 u64 *total_allocated_on_err,
587 struct list_head *blocks)
588{
589 LIST_HEAD(dfs);
590 int i;
591
592 for (i = 0; i < mm->n_roots; ++i)
593 list_add_tail(new: &mm->roots[i]->tmp_link, head: &dfs);
594
595 return __alloc_range(mm, dfs: &dfs, start, size,
596 blocks, total_allocated_on_err);
597}
598
599static int __alloc_contig_try_harder(struct drm_buddy *mm,
600 u64 size,
601 u64 min_block_size,
602 struct list_head *blocks)
603{
604 u64 rhs_offset, lhs_offset, lhs_size, filled;
605 struct drm_buddy_block *block;
606 struct list_head *list;
607 LIST_HEAD(blocks_lhs);
608 unsigned long pages;
609 unsigned int order;
610 u64 modify_size;
611 int err;
612
613 modify_size = rounddown_pow_of_two(size);
614 pages = modify_size >> ilog2(mm->chunk_size);
615 order = fls(x: pages) - 1;
616 if (order == 0)
617 return -ENOSPC;
618
619 list = &mm->free_list[order];
620 if (list_empty(head: list))
621 return -ENOSPC;
622
623 list_for_each_entry_reverse(block, list, link) {
624 /* Allocate blocks traversing RHS */
625 rhs_offset = drm_buddy_block_offset(block);
626 err = __drm_buddy_alloc_range(mm, start: rhs_offset, size,
627 total_allocated_on_err: &filled, blocks);
628 if (!err || err != -ENOSPC)
629 return err;
630
631 lhs_size = max((size - filled), min_block_size);
632 if (!IS_ALIGNED(lhs_size, min_block_size))
633 lhs_size = round_up(lhs_size, min_block_size);
634
635 /* Allocate blocks traversing LHS */
636 lhs_offset = drm_buddy_block_offset(block) - lhs_size;
637 err = __drm_buddy_alloc_range(mm, start: lhs_offset, size: lhs_size,
638 NULL, blocks: &blocks_lhs);
639 if (!err) {
640 list_splice(list: &blocks_lhs, head: blocks);
641 return 0;
642 } else if (err != -ENOSPC) {
643 drm_buddy_free_list(mm, blocks);
644 return err;
645 }
646 /* Free blocks for the next iteration */
647 drm_buddy_free_list(mm, blocks);
648 }
649
650 return -ENOSPC;
651}
652
653/**
654 * drm_buddy_block_trim - free unused pages
655 *
656 * @mm: DRM buddy manager
657 * @new_size: original size requested
658 * @blocks: Input and output list of allocated blocks.
659 * MUST contain single block as input to be trimmed.
660 * On success will contain the newly allocated blocks
661 * making up the @new_size. Blocks always appear in
662 * ascending order
663 *
664 * For contiguous allocation, we round up the size to the nearest
665 * power of two value, drivers consume *actual* size, so remaining
666 * portions are unused and can be optionally freed with this function
667 *
668 * Returns:
669 * 0 on success, error code on failure.
670 */
671int drm_buddy_block_trim(struct drm_buddy *mm,
672 u64 new_size,
673 struct list_head *blocks)
674{
675 struct drm_buddy_block *parent;
676 struct drm_buddy_block *block;
677 LIST_HEAD(dfs);
678 u64 new_start;
679 int err;
680
681 if (!list_is_singular(head: blocks))
682 return -EINVAL;
683
684 block = list_first_entry(blocks,
685 struct drm_buddy_block,
686 link);
687
688 if (WARN_ON(!drm_buddy_block_is_allocated(block)))
689 return -EINVAL;
690
691 if (new_size > drm_buddy_block_size(mm, block))
692 return -EINVAL;
693
694 if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))
695 return -EINVAL;
696
697 if (new_size == drm_buddy_block_size(mm, block))
698 return 0;
699
700 list_del(entry: &block->link);
701 mark_free(mm, block);
702 mm->avail += drm_buddy_block_size(mm, block);
703
704 /* Prevent recursively freeing this node */
705 parent = block->parent;
706 block->parent = NULL;
707
708 new_start = drm_buddy_block_offset(block);
709 list_add(new: &block->tmp_link, head: &dfs);
710 err = __alloc_range(mm, dfs: &dfs, start: new_start, size: new_size, blocks, NULL);
711 if (err) {
712 mark_allocated(block);
713 mm->avail -= drm_buddy_block_size(mm, block);
714 list_add(new: &block->link, head: blocks);
715 }
716
717 block->parent = parent;
718 return err;
719}
720EXPORT_SYMBOL(drm_buddy_block_trim);
721
722/**
723 * drm_buddy_alloc_blocks - allocate power-of-two blocks
724 *
725 * @mm: DRM buddy manager to allocate from
726 * @start: start of the allowed range for this block
727 * @end: end of the allowed range for this block
728 * @size: size of the allocation
729 * @min_block_size: alignment of the allocation
730 * @blocks: output list head to add allocated blocks
731 * @flags: DRM_BUDDY_*_ALLOCATION flags
732 *
733 * alloc_range_bias() called on range limitations, which traverses
734 * the tree and returns the desired block.
735 *
736 * alloc_from_freelist() called when *no* range restrictions
737 * are enforced, which picks the block from the freelist.
738 *
739 * Returns:
740 * 0 on success, error code on failure.
741 */
742int drm_buddy_alloc_blocks(struct drm_buddy *mm,
743 u64 start, u64 end, u64 size,
744 u64 min_block_size,
745 struct list_head *blocks,
746 unsigned long flags)
747{
748 struct drm_buddy_block *block = NULL;
749 u64 original_size, original_min_size;
750 unsigned int min_order, order;
751 LIST_HEAD(allocated);
752 unsigned long pages;
753 int err;
754
755 if (size < mm->chunk_size)
756 return -EINVAL;
757
758 if (min_block_size < mm->chunk_size)
759 return -EINVAL;
760
761 if (!is_power_of_2(n: min_block_size))
762 return -EINVAL;
763
764 if (!IS_ALIGNED(start | end | size, mm->chunk_size))
765 return -EINVAL;
766
767 if (end > mm->size)
768 return -EINVAL;
769
770 if (range_overflows(start, size, mm->size))
771 return -EINVAL;
772
773 /* Actual range allocation */
774 if (start + size == end) {
775 if (!IS_ALIGNED(start | end, min_block_size))
776 return -EINVAL;
777
778 return __drm_buddy_alloc_range(mm, start, size, NULL, blocks);
779 }
780
781 original_size = size;
782 original_min_size = min_block_size;
783
784 /* Roundup the size to power of 2 */
785 if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION) {
786 size = roundup_pow_of_two(size);
787 min_block_size = size;
788 /* Align size value to min_block_size */
789 } else if (!IS_ALIGNED(size, min_block_size)) {
790 size = round_up(size, min_block_size);
791 }
792
793 pages = size >> ilog2(mm->chunk_size);
794 order = fls(x: pages) - 1;
795 min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
796
797 do {
798 order = min(order, (unsigned int)fls(pages) - 1);
799 BUG_ON(order > mm->max_order);
800 BUG_ON(order < min_order);
801
802 do {
803 if (flags & DRM_BUDDY_RANGE_ALLOCATION)
804 /* Allocate traversing within the range */
805 block = alloc_range_bias(mm, start, end, order);
806 else
807 /* Allocate from freelist */
808 block = alloc_from_freelist(mm, order, flags);
809
810 if (!IS_ERR(ptr: block))
811 break;
812
813 if (order-- == min_order) {
814 if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION &&
815 !(flags & DRM_BUDDY_RANGE_ALLOCATION))
816 /*
817 * Try contiguous block allocation through
818 * try harder method
819 */
820 return __alloc_contig_try_harder(mm,
821 size: original_size,
822 min_block_size: original_min_size,
823 blocks);
824 err = -ENOSPC;
825 goto err_free;
826 }
827 } while (1);
828
829 mark_allocated(block);
830 mm->avail -= drm_buddy_block_size(mm, block);
831 kmemleak_update_trace(ptr: block);
832 list_add_tail(new: &block->link, head: &allocated);
833
834 pages -= BIT(order);
835
836 if (!pages)
837 break;
838 } while (1);
839
840 /* Trim the allocated block to the required size */
841 if (original_size != size) {
842 struct list_head *trim_list;
843 LIST_HEAD(temp);
844 u64 trim_size;
845
846 trim_list = &allocated;
847 trim_size = original_size;
848
849 if (!list_is_singular(head: &allocated)) {
850 block = list_last_entry(&allocated, typeof(*block), link);
851 list_move(list: &block->link, head: &temp);
852 trim_list = &temp;
853 trim_size = drm_buddy_block_size(mm, block) -
854 (size - original_size);
855 }
856
857 drm_buddy_block_trim(mm,
858 trim_size,
859 trim_list);
860
861 if (!list_empty(head: &temp))
862 list_splice_tail(list: trim_list, head: &allocated);
863 }
864
865 list_splice_tail(list: &allocated, head: blocks);
866 return 0;
867
868err_free:
869 drm_buddy_free_list(mm, &allocated);
870 return err;
871}
872EXPORT_SYMBOL(drm_buddy_alloc_blocks);
873
874/**
875 * drm_buddy_block_print - print block information
876 *
877 * @mm: DRM buddy manager
878 * @block: DRM buddy block
879 * @p: DRM printer to use
880 */
881void drm_buddy_block_print(struct drm_buddy *mm,
882 struct drm_buddy_block *block,
883 struct drm_printer *p)
884{
885 u64 start = drm_buddy_block_offset(block);
886 u64 size = drm_buddy_block_size(mm, block);
887
888 drm_printf(p, f: "%#018llx-%#018llx: %llu\n", start, start + size, size);
889}
890EXPORT_SYMBOL(drm_buddy_block_print);
891
892/**
893 * drm_buddy_print - print allocator state
894 *
895 * @mm: DRM buddy manager
896 * @p: DRM printer to use
897 */
898void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)
899{
900 int order;
901
902 drm_printf(p, f: "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB\n",
903 mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20);
904
905 for (order = mm->max_order; order >= 0; order--) {
906 struct drm_buddy_block *block;
907 u64 count = 0, free;
908
909 list_for_each_entry(block, &mm->free_list[order], link) {
910 BUG_ON(!drm_buddy_block_is_free(block));
911 count++;
912 }
913
914 drm_printf(p, f: "order-%2d ", order);
915
916 free = count * (mm->chunk_size << order);
917 if (free < SZ_1M)
918 drm_printf(p, f: "free: %8llu KiB", free >> 10);
919 else
920 drm_printf(p, f: "free: %8llu MiB", free >> 20);
921
922 drm_printf(p, f: ", blocks: %llu\n", count);
923 }
924}
925EXPORT_SYMBOL(drm_buddy_print);
926
927static void drm_buddy_module_exit(void)
928{
929 kmem_cache_destroy(s: slab_blocks);
930}
931
932static int __init drm_buddy_module_init(void)
933{
934 slab_blocks = KMEM_CACHE(drm_buddy_block, 0);
935 if (!slab_blocks)
936 return -ENOMEM;
937
938 return 0;
939}
940
941module_init(drm_buddy_module_init);
942module_exit(drm_buddy_module_exit);
943
944MODULE_DESCRIPTION("DRM Buddy Allocator");
945MODULE_LICENSE("Dual MIT/GPL");
946

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