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