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