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