16387a3c4SArunpravin // SPDX-License-Identifier: MIT
26387a3c4SArunpravin /*
36387a3c4SArunpravin * Copyright © 2021 Intel Corporation
46387a3c4SArunpravin */
56387a3c4SArunpravin
66387a3c4SArunpravin #include <linux/kmemleak.h>
76387a3c4SArunpravin #include <linux/module.h>
86387a3c4SArunpravin #include <linux/sizes.h>
96387a3c4SArunpravin
106387a3c4SArunpravin #include <drm/drm_buddy.h>
116387a3c4SArunpravin
126387a3c4SArunpravin static struct kmem_cache *slab_blocks;
136387a3c4SArunpravin
drm_block_alloc(struct drm_buddy * mm,struct drm_buddy_block * parent,unsigned int order,u64 offset)146387a3c4SArunpravin static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm,
156387a3c4SArunpravin struct drm_buddy_block *parent,
166387a3c4SArunpravin unsigned int order,
176387a3c4SArunpravin u64 offset)
186387a3c4SArunpravin {
196387a3c4SArunpravin struct drm_buddy_block *block;
206387a3c4SArunpravin
216387a3c4SArunpravin BUG_ON(order > DRM_BUDDY_MAX_ORDER);
226387a3c4SArunpravin
236387a3c4SArunpravin block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);
246387a3c4SArunpravin if (!block)
256387a3c4SArunpravin return NULL;
266387a3c4SArunpravin
276387a3c4SArunpravin block->header = offset;
286387a3c4SArunpravin block->header |= order;
296387a3c4SArunpravin block->parent = parent;
306387a3c4SArunpravin
316387a3c4SArunpravin BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
326387a3c4SArunpravin return block;
336387a3c4SArunpravin }
346387a3c4SArunpravin
drm_block_free(struct drm_buddy * mm,struct drm_buddy_block * block)356387a3c4SArunpravin static void drm_block_free(struct drm_buddy *mm,
366387a3c4SArunpravin struct drm_buddy_block *block)
376387a3c4SArunpravin {
386387a3c4SArunpravin kmem_cache_free(slab_blocks, block);
396387a3c4SArunpravin }
406387a3c4SArunpravin
list_insert_sorted(struct drm_buddy * mm,struct drm_buddy_block * block)415640e816SArunpravin Paneer Selvam static void list_insert_sorted(struct drm_buddy *mm,
425640e816SArunpravin Paneer Selvam struct drm_buddy_block *block)
435640e816SArunpravin Paneer Selvam {
445640e816SArunpravin Paneer Selvam struct drm_buddy_block *node;
455640e816SArunpravin Paneer Selvam struct list_head *head;
465640e816SArunpravin Paneer Selvam
475640e816SArunpravin Paneer Selvam head = &mm->free_list[drm_buddy_block_order(block)];
485640e816SArunpravin Paneer Selvam if (list_empty(head)) {
495640e816SArunpravin Paneer Selvam list_add(&block->link, head);
505640e816SArunpravin Paneer Selvam return;
515640e816SArunpravin Paneer Selvam }
525640e816SArunpravin Paneer Selvam
535640e816SArunpravin Paneer Selvam list_for_each_entry(node, head, link)
545640e816SArunpravin Paneer Selvam if (drm_buddy_block_offset(block) < drm_buddy_block_offset(node))
555640e816SArunpravin Paneer Selvam break;
565640e816SArunpravin Paneer Selvam
575640e816SArunpravin Paneer Selvam __list_add(&block->link, node->link.prev, &node->link);
585640e816SArunpravin Paneer Selvam }
595640e816SArunpravin Paneer Selvam
clear_reset(struct drm_buddy_block * block)6096950929SArunpravin Paneer Selvam static void clear_reset(struct drm_buddy_block *block)
6196950929SArunpravin Paneer Selvam {
6296950929SArunpravin Paneer Selvam block->header &= ~DRM_BUDDY_HEADER_CLEAR;
6396950929SArunpravin Paneer Selvam }
6496950929SArunpravin Paneer Selvam
mark_cleared(struct drm_buddy_block * block)6596950929SArunpravin Paneer Selvam static void mark_cleared(struct drm_buddy_block *block)
6696950929SArunpravin Paneer Selvam {
6796950929SArunpravin Paneer Selvam block->header |= DRM_BUDDY_HEADER_CLEAR;
6896950929SArunpravin Paneer Selvam }
6996950929SArunpravin Paneer Selvam
mark_allocated(struct drm_buddy_block * block)706387a3c4SArunpravin static void mark_allocated(struct drm_buddy_block *block)
716387a3c4SArunpravin {
726387a3c4SArunpravin block->header &= ~DRM_BUDDY_HEADER_STATE;
736387a3c4SArunpravin block->header |= DRM_BUDDY_ALLOCATED;
746387a3c4SArunpravin
756387a3c4SArunpravin list_del(&block->link);
766387a3c4SArunpravin }
776387a3c4SArunpravin
mark_free(struct drm_buddy * mm,struct drm_buddy_block * block)786387a3c4SArunpravin static void mark_free(struct drm_buddy *mm,
796387a3c4SArunpravin struct drm_buddy_block *block)
806387a3c4SArunpravin {
816387a3c4SArunpravin block->header &= ~DRM_BUDDY_HEADER_STATE;
826387a3c4SArunpravin block->header |= DRM_BUDDY_FREE;
836387a3c4SArunpravin
845640e816SArunpravin Paneer Selvam list_insert_sorted(mm, block);
856387a3c4SArunpravin }
866387a3c4SArunpravin
mark_split(struct drm_buddy_block * block)876387a3c4SArunpravin static void mark_split(struct drm_buddy_block *block)
886387a3c4SArunpravin {
896387a3c4SArunpravin block->header &= ~DRM_BUDDY_HEADER_STATE;
906387a3c4SArunpravin block->header |= DRM_BUDDY_SPLIT;
916387a3c4SArunpravin
926387a3c4SArunpravin list_del(&block->link);
936387a3c4SArunpravin }
946387a3c4SArunpravin
overlaps(u64 s1,u64 e1,u64 s2,u64 e2)9596950929SArunpravin Paneer Selvam static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
9696950929SArunpravin Paneer Selvam {
9796950929SArunpravin Paneer Selvam return s1 <= e2 && e1 >= s2;
9896950929SArunpravin Paneer Selvam }
9996950929SArunpravin Paneer Selvam
contains(u64 s1,u64 e1,u64 s2,u64 e2)10096950929SArunpravin Paneer Selvam static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
10196950929SArunpravin Paneer Selvam {
10296950929SArunpravin Paneer Selvam return s1 <= s2 && e1 >= e2;
10396950929SArunpravin Paneer Selvam }
10496950929SArunpravin Paneer Selvam
10596950929SArunpravin Paneer Selvam static struct drm_buddy_block *
__get_buddy(struct drm_buddy_block * block)10696950929SArunpravin Paneer Selvam __get_buddy(struct drm_buddy_block *block)
10796950929SArunpravin Paneer Selvam {
10896950929SArunpravin Paneer Selvam struct drm_buddy_block *parent;
10996950929SArunpravin Paneer Selvam
11096950929SArunpravin Paneer Selvam parent = block->parent;
11196950929SArunpravin Paneer Selvam if (!parent)
11296950929SArunpravin Paneer Selvam return NULL;
11396950929SArunpravin Paneer Selvam
11496950929SArunpravin Paneer Selvam if (parent->left == block)
11596950929SArunpravin Paneer Selvam return parent->right;
11696950929SArunpravin Paneer Selvam
11796950929SArunpravin Paneer Selvam return parent->left;
11896950929SArunpravin Paneer Selvam }
11996950929SArunpravin Paneer Selvam
__drm_buddy_free(struct drm_buddy * mm,struct drm_buddy_block * block,bool force_merge)12096950929SArunpravin Paneer Selvam static unsigned int __drm_buddy_free(struct drm_buddy *mm,
12196950929SArunpravin Paneer Selvam struct drm_buddy_block *block,
12296950929SArunpravin Paneer Selvam bool force_merge)
12396950929SArunpravin Paneer Selvam {
12496950929SArunpravin Paneer Selvam struct drm_buddy_block *parent;
12596950929SArunpravin Paneer Selvam unsigned int order;
12696950929SArunpravin Paneer Selvam
12796950929SArunpravin Paneer Selvam while ((parent = block->parent)) {
12896950929SArunpravin Paneer Selvam struct drm_buddy_block *buddy;
12996950929SArunpravin Paneer Selvam
13096950929SArunpravin Paneer Selvam buddy = __get_buddy(block);
13196950929SArunpravin Paneer Selvam
13296950929SArunpravin Paneer Selvam if (!drm_buddy_block_is_free(buddy))
13396950929SArunpravin Paneer Selvam break;
13496950929SArunpravin Paneer Selvam
13596950929SArunpravin Paneer Selvam if (!force_merge) {
13696950929SArunpravin Paneer Selvam /*
13796950929SArunpravin Paneer Selvam * Check the block and its buddy clear state and exit
13896950929SArunpravin Paneer Selvam * the loop if they both have the dissimilar state.
13996950929SArunpravin Paneer Selvam */
14096950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block) !=
14196950929SArunpravin Paneer Selvam drm_buddy_block_is_clear(buddy))
14296950929SArunpravin Paneer Selvam break;
14396950929SArunpravin Paneer Selvam
14496950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block))
14596950929SArunpravin Paneer Selvam mark_cleared(parent);
14696950929SArunpravin Paneer Selvam }
14796950929SArunpravin Paneer Selvam
14896950929SArunpravin Paneer Selvam list_del(&buddy->link);
14996950929SArunpravin Paneer Selvam if (force_merge && drm_buddy_block_is_clear(buddy))
15096950929SArunpravin Paneer Selvam mm->clear_avail -= drm_buddy_block_size(mm, buddy);
15196950929SArunpravin Paneer Selvam
15296950929SArunpravin Paneer Selvam drm_block_free(mm, block);
15396950929SArunpravin Paneer Selvam drm_block_free(mm, buddy);
15496950929SArunpravin Paneer Selvam
15596950929SArunpravin Paneer Selvam block = parent;
15696950929SArunpravin Paneer Selvam }
15796950929SArunpravin Paneer Selvam
15896950929SArunpravin Paneer Selvam order = drm_buddy_block_order(block);
15996950929SArunpravin Paneer Selvam mark_free(mm, block);
16096950929SArunpravin Paneer Selvam
16196950929SArunpravin Paneer Selvam return order;
16296950929SArunpravin Paneer Selvam }
16396950929SArunpravin Paneer Selvam
__force_merge(struct drm_buddy * mm,u64 start,u64 end,unsigned int min_order)16496950929SArunpravin Paneer Selvam static int __force_merge(struct drm_buddy *mm,
16596950929SArunpravin Paneer Selvam u64 start,
16696950929SArunpravin Paneer Selvam u64 end,
16796950929SArunpravin Paneer Selvam unsigned int min_order)
16896950929SArunpravin Paneer Selvam {
16996950929SArunpravin Paneer Selvam unsigned int order;
17096950929SArunpravin Paneer Selvam int i;
17196950929SArunpravin Paneer Selvam
17296950929SArunpravin Paneer Selvam if (!min_order)
17396950929SArunpravin Paneer Selvam return -ENOMEM;
17496950929SArunpravin Paneer Selvam
17596950929SArunpravin Paneer Selvam if (min_order > mm->max_order)
17696950929SArunpravin Paneer Selvam return -EINVAL;
17796950929SArunpravin Paneer Selvam
17896950929SArunpravin Paneer Selvam for (i = min_order - 1; i >= 0; i--) {
17996950929SArunpravin Paneer Selvam struct drm_buddy_block *block, *prev;
18096950929SArunpravin Paneer Selvam
18196950929SArunpravin Paneer Selvam list_for_each_entry_safe_reverse(block, prev, &mm->free_list[i], link) {
18296950929SArunpravin Paneer Selvam struct drm_buddy_block *buddy;
18396950929SArunpravin Paneer Selvam u64 block_start, block_end;
18496950929SArunpravin Paneer Selvam
18596950929SArunpravin Paneer Selvam if (!block->parent)
18696950929SArunpravin Paneer Selvam continue;
18796950929SArunpravin Paneer Selvam
18896950929SArunpravin Paneer Selvam block_start = drm_buddy_block_offset(block);
18996950929SArunpravin Paneer Selvam block_end = block_start + drm_buddy_block_size(mm, block) - 1;
19096950929SArunpravin Paneer Selvam
19196950929SArunpravin Paneer Selvam if (!contains(start, end, block_start, block_end))
19296950929SArunpravin Paneer Selvam continue;
19396950929SArunpravin Paneer Selvam
19496950929SArunpravin Paneer Selvam buddy = __get_buddy(block);
19596950929SArunpravin Paneer Selvam if (!drm_buddy_block_is_free(buddy))
19696950929SArunpravin Paneer Selvam continue;
19796950929SArunpravin Paneer Selvam
19896950929SArunpravin Paneer Selvam WARN_ON(drm_buddy_block_is_clear(block) ==
19996950929SArunpravin Paneer Selvam drm_buddy_block_is_clear(buddy));
20096950929SArunpravin Paneer Selvam
20196950929SArunpravin Paneer Selvam /*
20296950929SArunpravin Paneer Selvam * If the prev block is same as buddy, don't access the
20396950929SArunpravin Paneer Selvam * block in the next iteration as we would free the
20496950929SArunpravin Paneer Selvam * buddy block as part of the free function.
20596950929SArunpravin Paneer Selvam */
20696950929SArunpravin Paneer Selvam if (prev == buddy)
20796950929SArunpravin Paneer Selvam prev = list_prev_entry(prev, link);
20896950929SArunpravin Paneer Selvam
20996950929SArunpravin Paneer Selvam list_del(&block->link);
21096950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block))
21196950929SArunpravin Paneer Selvam mm->clear_avail -= drm_buddy_block_size(mm, block);
21296950929SArunpravin Paneer Selvam
21396950929SArunpravin Paneer Selvam order = __drm_buddy_free(mm, block, true);
21496950929SArunpravin Paneer Selvam if (order >= min_order)
21596950929SArunpravin Paneer Selvam return 0;
21696950929SArunpravin Paneer Selvam }
21796950929SArunpravin Paneer Selvam }
21896950929SArunpravin Paneer Selvam
21996950929SArunpravin Paneer Selvam return -ENOMEM;
22096950929SArunpravin Paneer Selvam }
22196950929SArunpravin Paneer Selvam
2226387a3c4SArunpravin /**
2236387a3c4SArunpravin * drm_buddy_init - init memory manager
2246387a3c4SArunpravin *
2256387a3c4SArunpravin * @mm: DRM buddy manager to initialize
2266387a3c4SArunpravin * @size: size in bytes to manage
2276387a3c4SArunpravin * @chunk_size: minimum page size in bytes for our allocations
2286387a3c4SArunpravin *
2296387a3c4SArunpravin * Initializes the memory manager and its resources.
2306387a3c4SArunpravin *
2316387a3c4SArunpravin * Returns:
2326387a3c4SArunpravin * 0 on success, error code on failure.
2336387a3c4SArunpravin */
drm_buddy_init(struct drm_buddy * mm,u64 size,u64 chunk_size)2346387a3c4SArunpravin int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
2356387a3c4SArunpravin {
2366387a3c4SArunpravin unsigned int i;
2376387a3c4SArunpravin u64 offset;
2386387a3c4SArunpravin
2396387a3c4SArunpravin if (size < chunk_size)
2406387a3c4SArunpravin return -EINVAL;
2416387a3c4SArunpravin
242117bbc0eSMatthew Auld if (chunk_size < SZ_4K)
2436387a3c4SArunpravin return -EINVAL;
2446387a3c4SArunpravin
2456387a3c4SArunpravin if (!is_power_of_2(chunk_size))
2466387a3c4SArunpravin return -EINVAL;
2476387a3c4SArunpravin
2486387a3c4SArunpravin size = round_down(size, chunk_size);
2496387a3c4SArunpravin
2506387a3c4SArunpravin mm->size = size;
2516387a3c4SArunpravin mm->avail = size;
252bb21700bSArunpravin Paneer Selvam mm->clear_avail = 0;
2536387a3c4SArunpravin mm->chunk_size = chunk_size;
2546387a3c4SArunpravin mm->max_order = ilog2(size) - ilog2(chunk_size);
2556387a3c4SArunpravin
2566387a3c4SArunpravin BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);
2576387a3c4SArunpravin
2586387a3c4SArunpravin mm->free_list = kmalloc_array(mm->max_order + 1,
2596387a3c4SArunpravin sizeof(struct list_head),
2606387a3c4SArunpravin GFP_KERNEL);
2616387a3c4SArunpravin if (!mm->free_list)
2626387a3c4SArunpravin return -ENOMEM;
2636387a3c4SArunpravin
2646387a3c4SArunpravin for (i = 0; i <= mm->max_order; ++i)
2656387a3c4SArunpravin INIT_LIST_HEAD(&mm->free_list[i]);
2666387a3c4SArunpravin
2676387a3c4SArunpravin mm->n_roots = hweight64(size);
2686387a3c4SArunpravin
2696387a3c4SArunpravin mm->roots = kmalloc_array(mm->n_roots,
2706387a3c4SArunpravin sizeof(struct drm_buddy_block *),
2716387a3c4SArunpravin GFP_KERNEL);
2726387a3c4SArunpravin if (!mm->roots)
2736387a3c4SArunpravin goto out_free_list;
2746387a3c4SArunpravin
2756387a3c4SArunpravin offset = 0;
2766387a3c4SArunpravin i = 0;
2776387a3c4SArunpravin
2786387a3c4SArunpravin /*
2796387a3c4SArunpravin * Split into power-of-two blocks, in case we are given a size that is
2806387a3c4SArunpravin * not itself a power-of-two.
2816387a3c4SArunpravin */
2826387a3c4SArunpravin do {
2836387a3c4SArunpravin struct drm_buddy_block *root;
2846387a3c4SArunpravin unsigned int order;
2856387a3c4SArunpravin u64 root_size;
2866387a3c4SArunpravin
2874453545bSDavid Gow order = ilog2(size) - ilog2(chunk_size);
2884453545bSDavid Gow root_size = chunk_size << order;
2896387a3c4SArunpravin
2906387a3c4SArunpravin root = drm_block_alloc(mm, NULL, order, offset);
2916387a3c4SArunpravin if (!root)
2926387a3c4SArunpravin goto out_free_roots;
2936387a3c4SArunpravin
2946387a3c4SArunpravin mark_free(mm, root);
2956387a3c4SArunpravin
2966387a3c4SArunpravin BUG_ON(i > mm->max_order);
2976387a3c4SArunpravin BUG_ON(drm_buddy_block_size(mm, root) < chunk_size);
2986387a3c4SArunpravin
2996387a3c4SArunpravin mm->roots[i] = root;
3006387a3c4SArunpravin
3016387a3c4SArunpravin offset += root_size;
3026387a3c4SArunpravin size -= root_size;
3036387a3c4SArunpravin i++;
3046387a3c4SArunpravin } while (size);
3056387a3c4SArunpravin
3066387a3c4SArunpravin return 0;
3076387a3c4SArunpravin
3086387a3c4SArunpravin out_free_roots:
3096387a3c4SArunpravin while (i--)
3106387a3c4SArunpravin drm_block_free(mm, mm->roots[i]);
3116387a3c4SArunpravin kfree(mm->roots);
3126387a3c4SArunpravin out_free_list:
3136387a3c4SArunpravin kfree(mm->free_list);
3146387a3c4SArunpravin return -ENOMEM;
3156387a3c4SArunpravin }
3166387a3c4SArunpravin EXPORT_SYMBOL(drm_buddy_init);
3176387a3c4SArunpravin
3186387a3c4SArunpravin /**
3196387a3c4SArunpravin * drm_buddy_fini - tear down the memory manager
3206387a3c4SArunpravin *
3216387a3c4SArunpravin * @mm: DRM buddy manager to free
3226387a3c4SArunpravin *
3236387a3c4SArunpravin * Cleanup memory manager resources and the freelist
3246387a3c4SArunpravin */
drm_buddy_fini(struct drm_buddy * mm)3256387a3c4SArunpravin void drm_buddy_fini(struct drm_buddy *mm)
3266387a3c4SArunpravin {
32796950929SArunpravin Paneer Selvam u64 root_size, size;
32896950929SArunpravin Paneer Selvam unsigned int order;
3296387a3c4SArunpravin int i;
3306387a3c4SArunpravin
33196950929SArunpravin Paneer Selvam size = mm->size;
33296950929SArunpravin Paneer Selvam
3336387a3c4SArunpravin for (i = 0; i < mm->n_roots; ++i) {
33496950929SArunpravin Paneer Selvam order = ilog2(size) - ilog2(mm->chunk_size);
33596950929SArunpravin Paneer Selvam __force_merge(mm, 0, size, order);
33696950929SArunpravin Paneer Selvam
3376387a3c4SArunpravin WARN_ON(!drm_buddy_block_is_free(mm->roots[i]));
3386387a3c4SArunpravin drm_block_free(mm, mm->roots[i]);
33996950929SArunpravin Paneer Selvam
34096950929SArunpravin Paneer Selvam root_size = mm->chunk_size << order;
34196950929SArunpravin Paneer Selvam size -= root_size;
3426387a3c4SArunpravin }
3436387a3c4SArunpravin
3446387a3c4SArunpravin WARN_ON(mm->avail != mm->size);
3456387a3c4SArunpravin
3466387a3c4SArunpravin kfree(mm->roots);
3476387a3c4SArunpravin kfree(mm->free_list);
3486387a3c4SArunpravin }
3496387a3c4SArunpravin EXPORT_SYMBOL(drm_buddy_fini);
3506387a3c4SArunpravin
split_block(struct drm_buddy * mm,struct drm_buddy_block * block)3516387a3c4SArunpravin static int split_block(struct drm_buddy *mm,
3526387a3c4SArunpravin struct drm_buddy_block *block)
3536387a3c4SArunpravin {
3546387a3c4SArunpravin unsigned int block_order = drm_buddy_block_order(block) - 1;
3556387a3c4SArunpravin u64 offset = drm_buddy_block_offset(block);
3566387a3c4SArunpravin
3576387a3c4SArunpravin BUG_ON(!drm_buddy_block_is_free(block));
3586387a3c4SArunpravin BUG_ON(!drm_buddy_block_order(block));
3596387a3c4SArunpravin
3606387a3c4SArunpravin block->left = drm_block_alloc(mm, block, block_order, offset);
3616387a3c4SArunpravin if (!block->left)
3626387a3c4SArunpravin return -ENOMEM;
3636387a3c4SArunpravin
3646387a3c4SArunpravin block->right = drm_block_alloc(mm, block, block_order,
3656387a3c4SArunpravin offset + (mm->chunk_size << block_order));
3666387a3c4SArunpravin if (!block->right) {
3676387a3c4SArunpravin drm_block_free(mm, block->left);
3686387a3c4SArunpravin return -ENOMEM;
3696387a3c4SArunpravin }
3706387a3c4SArunpravin
3716387a3c4SArunpravin mark_free(mm, block->left);
3726387a3c4SArunpravin mark_free(mm, block->right);
3736387a3c4SArunpravin
37496950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block)) {
37596950929SArunpravin Paneer Selvam mark_cleared(block->left);
37696950929SArunpravin Paneer Selvam mark_cleared(block->right);
37796950929SArunpravin Paneer Selvam clear_reset(block);
37896950929SArunpravin Paneer Selvam }
37996950929SArunpravin Paneer Selvam
3806387a3c4SArunpravin mark_split(block);
3816387a3c4SArunpravin
3826387a3c4SArunpravin return 0;
3836387a3c4SArunpravin }
3846387a3c4SArunpravin
38592937f17SArunpravin /**
38692937f17SArunpravin * drm_get_buddy - get buddy address
38792937f17SArunpravin *
38892937f17SArunpravin * @block: DRM buddy block
38992937f17SArunpravin *
39092937f17SArunpravin * Returns the corresponding buddy block for @block, or NULL
39192937f17SArunpravin * if this is a root block and can't be merged further.
39292937f17SArunpravin * Requires some kind of locking to protect against
39392937f17SArunpravin * any concurrent allocate and free operations.
39492937f17SArunpravin */
39592937f17SArunpravin struct drm_buddy_block *
drm_get_buddy(struct drm_buddy_block * block)39692937f17SArunpravin drm_get_buddy(struct drm_buddy_block *block)
39792937f17SArunpravin {
39892937f17SArunpravin return __get_buddy(block);
39992937f17SArunpravin }
40092937f17SArunpravin EXPORT_SYMBOL(drm_get_buddy);
40192937f17SArunpravin
4026387a3c4SArunpravin /**
4036387a3c4SArunpravin * drm_buddy_free_block - free a block
4046387a3c4SArunpravin *
4056387a3c4SArunpravin * @mm: DRM buddy manager
4066387a3c4SArunpravin * @block: block to be freed
4076387a3c4SArunpravin */
drm_buddy_free_block(struct drm_buddy * mm,struct drm_buddy_block * block)4086387a3c4SArunpravin void drm_buddy_free_block(struct drm_buddy *mm,
4096387a3c4SArunpravin struct drm_buddy_block *block)
4106387a3c4SArunpravin {
4116387a3c4SArunpravin BUG_ON(!drm_buddy_block_is_allocated(block));
4126387a3c4SArunpravin mm->avail += drm_buddy_block_size(mm, block);
41396950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block))
41496950929SArunpravin Paneer Selvam mm->clear_avail += drm_buddy_block_size(mm, block);
41596950929SArunpravin Paneer Selvam
41696950929SArunpravin Paneer Selvam __drm_buddy_free(mm, block, false);
4176387a3c4SArunpravin }
4186387a3c4SArunpravin EXPORT_SYMBOL(drm_buddy_free_block);
4196387a3c4SArunpravin
__drm_buddy_free_list(struct drm_buddy * mm,struct list_head * objects,bool mark_clear,bool mark_dirty)42096950929SArunpravin Paneer Selvam static void __drm_buddy_free_list(struct drm_buddy *mm,
42196950929SArunpravin Paneer Selvam struct list_head *objects,
42296950929SArunpravin Paneer Selvam bool mark_clear,
42396950929SArunpravin Paneer Selvam bool mark_dirty)
42496950929SArunpravin Paneer Selvam {
42596950929SArunpravin Paneer Selvam struct drm_buddy_block *block, *on;
42696950929SArunpravin Paneer Selvam
42796950929SArunpravin Paneer Selvam WARN_ON(mark_dirty && mark_clear);
42896950929SArunpravin Paneer Selvam
42996950929SArunpravin Paneer Selvam list_for_each_entry_safe(block, on, objects, link) {
43096950929SArunpravin Paneer Selvam if (mark_clear)
43196950929SArunpravin Paneer Selvam mark_cleared(block);
43296950929SArunpravin Paneer Selvam else if (mark_dirty)
43396950929SArunpravin Paneer Selvam clear_reset(block);
43496950929SArunpravin Paneer Selvam drm_buddy_free_block(mm, block);
43596950929SArunpravin Paneer Selvam cond_resched();
43696950929SArunpravin Paneer Selvam }
43796950929SArunpravin Paneer Selvam INIT_LIST_HEAD(objects);
43896950929SArunpravin Paneer Selvam }
43996950929SArunpravin Paneer Selvam
drm_buddy_free_list_internal(struct drm_buddy * mm,struct list_head * objects)44096950929SArunpravin Paneer Selvam static void drm_buddy_free_list_internal(struct drm_buddy *mm,
44196950929SArunpravin Paneer Selvam struct list_head *objects)
44296950929SArunpravin Paneer Selvam {
44396950929SArunpravin Paneer Selvam /*
44496950929SArunpravin Paneer Selvam * Don't touch the clear/dirty bit, since allocation is still internal
44596950929SArunpravin Paneer Selvam * at this point. For example we might have just failed part of the
44696950929SArunpravin Paneer Selvam * allocation.
44796950929SArunpravin Paneer Selvam */
44896950929SArunpravin Paneer Selvam __drm_buddy_free_list(mm, objects, false, false);
44996950929SArunpravin Paneer Selvam }
45096950929SArunpravin Paneer Selvam
4516387a3c4SArunpravin /**
4526387a3c4SArunpravin * drm_buddy_free_list - free blocks
4536387a3c4SArunpravin *
4546387a3c4SArunpravin * @mm: DRM buddy manager
4556387a3c4SArunpravin * @objects: input list head to free blocks
45696950929SArunpravin Paneer Selvam * @flags: optional flags like DRM_BUDDY_CLEARED
4576387a3c4SArunpravin */
drm_buddy_free_list(struct drm_buddy * mm,struct list_head * objects,unsigned int flags)45896950929SArunpravin Paneer Selvam void drm_buddy_free_list(struct drm_buddy *mm,
45996950929SArunpravin Paneer Selvam struct list_head *objects,
46096950929SArunpravin Paneer Selvam unsigned int flags)
4616387a3c4SArunpravin {
46296950929SArunpravin Paneer Selvam bool mark_clear = flags & DRM_BUDDY_CLEARED;
4636387a3c4SArunpravin
46496950929SArunpravin Paneer Selvam __drm_buddy_free_list(mm, objects, mark_clear, !mark_clear);
4656387a3c4SArunpravin }
4666387a3c4SArunpravin EXPORT_SYMBOL(drm_buddy_free_list);
4676387a3c4SArunpravin
block_incompatible(struct drm_buddy_block * block,unsigned int flags)46896950929SArunpravin Paneer Selvam static bool block_incompatible(struct drm_buddy_block *block, unsigned int flags)
469afea229fSArunpravin {
47096950929SArunpravin Paneer Selvam bool needs_clear = flags & DRM_BUDDY_CLEAR_ALLOCATION;
471afea229fSArunpravin
47296950929SArunpravin Paneer Selvam return needs_clear != drm_buddy_block_is_clear(block);
473afea229fSArunpravin }
474afea229fSArunpravin
475afea229fSArunpravin static struct drm_buddy_block *
__alloc_range_bias(struct drm_buddy * mm,u64 start,u64 end,unsigned int order,unsigned long flags,bool fallback)47696950929SArunpravin Paneer Selvam __alloc_range_bias(struct drm_buddy *mm,
477afea229fSArunpravin u64 start, u64 end,
47896950929SArunpravin Paneer Selvam unsigned int order,
47996950929SArunpravin Paneer Selvam unsigned long flags,
48096950929SArunpravin Paneer Selvam bool fallback)
481afea229fSArunpravin {
482f41900e4SMatthew Auld u64 req_size = mm->chunk_size << order;
483afea229fSArunpravin struct drm_buddy_block *block;
484afea229fSArunpravin struct drm_buddy_block *buddy;
485afea229fSArunpravin LIST_HEAD(dfs);
486afea229fSArunpravin int err;
487afea229fSArunpravin int i;
488afea229fSArunpravin
489afea229fSArunpravin end = end - 1;
490afea229fSArunpravin
491afea229fSArunpravin for (i = 0; i < mm->n_roots; ++i)
492afea229fSArunpravin list_add_tail(&mm->roots[i]->tmp_link, &dfs);
493afea229fSArunpravin
494afea229fSArunpravin do {
495afea229fSArunpravin u64 block_start;
496afea229fSArunpravin u64 block_end;
497afea229fSArunpravin
498afea229fSArunpravin block = list_first_entry_or_null(&dfs,
499afea229fSArunpravin struct drm_buddy_block,
500afea229fSArunpravin tmp_link);
501afea229fSArunpravin if (!block)
502afea229fSArunpravin break;
503afea229fSArunpravin
504afea229fSArunpravin list_del(&block->tmp_link);
505afea229fSArunpravin
506afea229fSArunpravin if (drm_buddy_block_order(block) < order)
507afea229fSArunpravin continue;
508afea229fSArunpravin
509afea229fSArunpravin block_start = drm_buddy_block_offset(block);
510afea229fSArunpravin block_end = block_start + drm_buddy_block_size(mm, block) - 1;
511afea229fSArunpravin
512afea229fSArunpravin if (!overlaps(start, end, block_start, block_end))
513afea229fSArunpravin continue;
514afea229fSArunpravin
515afea229fSArunpravin if (drm_buddy_block_is_allocated(block))
516afea229fSArunpravin continue;
517afea229fSArunpravin
518f41900e4SMatthew Auld if (block_start < start || block_end > end) {
519f41900e4SMatthew Auld u64 adjusted_start = max(block_start, start);
520f41900e4SMatthew Auld u64 adjusted_end = min(block_end, end);
521f41900e4SMatthew Auld
522f41900e4SMatthew Auld if (round_down(adjusted_end + 1, req_size) <=
523f41900e4SMatthew Auld round_up(adjusted_start, req_size))
524f41900e4SMatthew Auld continue;
525f41900e4SMatthew Auld }
526f41900e4SMatthew Auld
52796950929SArunpravin Paneer Selvam if (!fallback && block_incompatible(block, flags))
52896950929SArunpravin Paneer Selvam continue;
52996950929SArunpravin Paneer Selvam
5305a5a10d9SArunpravin Paneer Selvam if (contains(start, end, block_start, block_end) &&
5315a5a10d9SArunpravin Paneer Selvam order == drm_buddy_block_order(block)) {
532afea229fSArunpravin /*
533afea229fSArunpravin * Find the free block within the range.
5346387a3c4SArunpravin */
535afea229fSArunpravin if (drm_buddy_block_is_free(block))
536afea229fSArunpravin return block;
537afea229fSArunpravin
538afea229fSArunpravin continue;
539afea229fSArunpravin }
540afea229fSArunpravin
541afea229fSArunpravin if (!drm_buddy_block_is_split(block)) {
542afea229fSArunpravin err = split_block(mm, block);
543afea229fSArunpravin if (unlikely(err))
544afea229fSArunpravin goto err_undo;
545afea229fSArunpravin }
546afea229fSArunpravin
547afea229fSArunpravin list_add(&block->right->tmp_link, &dfs);
548afea229fSArunpravin list_add(&block->left->tmp_link, &dfs);
549afea229fSArunpravin } while (1);
550afea229fSArunpravin
551afea229fSArunpravin return ERR_PTR(-ENOSPC);
552afea229fSArunpravin
553afea229fSArunpravin err_undo:
554afea229fSArunpravin /*
555afea229fSArunpravin * We really don't want to leave around a bunch of split blocks, since
556afea229fSArunpravin * bigger is better, so make sure we merge everything back before we
557afea229fSArunpravin * free the allocated blocks.
558afea229fSArunpravin */
55992937f17SArunpravin buddy = __get_buddy(block);
560afea229fSArunpravin if (buddy &&
561afea229fSArunpravin (drm_buddy_block_is_free(block) &&
562afea229fSArunpravin drm_buddy_block_is_free(buddy)))
56396950929SArunpravin Paneer Selvam __drm_buddy_free(mm, block, false);
564afea229fSArunpravin return ERR_PTR(err);
565afea229fSArunpravin }
566afea229fSArunpravin
567afea229fSArunpravin static struct drm_buddy_block *
__drm_buddy_alloc_range_bias(struct drm_buddy * mm,u64 start,u64 end,unsigned int order,unsigned long flags)56896950929SArunpravin Paneer Selvam __drm_buddy_alloc_range_bias(struct drm_buddy *mm,
56996950929SArunpravin Paneer Selvam u64 start, u64 end,
57096950929SArunpravin Paneer Selvam unsigned int order,
57196950929SArunpravin Paneer Selvam unsigned long flags)
572476e4063SArunpravin {
57396950929SArunpravin Paneer Selvam struct drm_buddy_block *block;
57496950929SArunpravin Paneer Selvam bool fallback = false;
57596950929SArunpravin Paneer Selvam
57696950929SArunpravin Paneer Selvam block = __alloc_range_bias(mm, start, end, order,
57796950929SArunpravin Paneer Selvam flags, fallback);
578bb21700bSArunpravin Paneer Selvam if (IS_ERR(block))
57996950929SArunpravin Paneer Selvam return __alloc_range_bias(mm, start, end, order,
58096950929SArunpravin Paneer Selvam flags, !fallback);
58196950929SArunpravin Paneer Selvam
58296950929SArunpravin Paneer Selvam return block;
58396950929SArunpravin Paneer Selvam }
58496950929SArunpravin Paneer Selvam
58596950929SArunpravin Paneer Selvam static struct drm_buddy_block *
get_maxblock(struct drm_buddy * mm,unsigned int order,unsigned long flags)58696950929SArunpravin Paneer Selvam get_maxblock(struct drm_buddy *mm, unsigned int order,
58796950929SArunpravin Paneer Selvam unsigned long flags)
58896950929SArunpravin Paneer Selvam {
58996950929SArunpravin Paneer Selvam struct drm_buddy_block *max_block = NULL, *block = NULL;
5905640e816SArunpravin Paneer Selvam unsigned int i;
591476e4063SArunpravin
5925640e816SArunpravin Paneer Selvam for (i = order; i <= mm->max_order; ++i) {
59396950929SArunpravin Paneer Selvam struct drm_buddy_block *tmp_block;
59496950929SArunpravin Paneer Selvam
59596950929SArunpravin Paneer Selvam list_for_each_entry_reverse(tmp_block, &mm->free_list[i], link) {
59696950929SArunpravin Paneer Selvam if (block_incompatible(tmp_block, flags))
59796950929SArunpravin Paneer Selvam continue;
59896950929SArunpravin Paneer Selvam
59996950929SArunpravin Paneer Selvam block = tmp_block;
60096950929SArunpravin Paneer Selvam break;
60196950929SArunpravin Paneer Selvam }
60296950929SArunpravin Paneer Selvam
60396950929SArunpravin Paneer Selvam if (!block)
60496950929SArunpravin Paneer Selvam continue;
60596950929SArunpravin Paneer Selvam
6065640e816SArunpravin Paneer Selvam if (!max_block) {
60796950929SArunpravin Paneer Selvam max_block = block;
6085640e816SArunpravin Paneer Selvam continue;
6095640e816SArunpravin Paneer Selvam }
6105640e816SArunpravin Paneer Selvam
61196950929SArunpravin Paneer Selvam if (drm_buddy_block_offset(block) >
6125640e816SArunpravin Paneer Selvam drm_buddy_block_offset(max_block)) {
61396950929SArunpravin Paneer Selvam max_block = block;
6145640e816SArunpravin Paneer Selvam }
615476e4063SArunpravin }
616476e4063SArunpravin
617476e4063SArunpravin return max_block;
618476e4063SArunpravin }
619476e4063SArunpravin
620476e4063SArunpravin static struct drm_buddy_block *
alloc_from_freelist(struct drm_buddy * mm,unsigned int order,unsigned long flags)621afea229fSArunpravin alloc_from_freelist(struct drm_buddy *mm,
622afea229fSArunpravin unsigned int order,
623afea229fSArunpravin unsigned long flags)
6246387a3c4SArunpravin {
6256387a3c4SArunpravin struct drm_buddy_block *block = NULL;
6265640e816SArunpravin Paneer Selvam unsigned int tmp;
6276387a3c4SArunpravin int err;
6286387a3c4SArunpravin
629476e4063SArunpravin if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) {
63096950929SArunpravin Paneer Selvam block = get_maxblock(mm, order, flags);
631476e4063SArunpravin if (block)
6325640e816SArunpravin Paneer Selvam /* Store the obtained block order */
6335640e816SArunpravin Paneer Selvam tmp = drm_buddy_block_order(block);
634476e4063SArunpravin } else {
6355640e816SArunpravin Paneer Selvam for (tmp = order; tmp <= mm->max_order; ++tmp) {
63696950929SArunpravin Paneer Selvam struct drm_buddy_block *tmp_block;
63796950929SArunpravin Paneer Selvam
63896950929SArunpravin Paneer Selvam list_for_each_entry_reverse(tmp_block, &mm->free_list[tmp], link) {
63996950929SArunpravin Paneer Selvam if (block_incompatible(tmp_block, flags))
64096950929SArunpravin Paneer Selvam continue;
64196950929SArunpravin Paneer Selvam
64296950929SArunpravin Paneer Selvam block = tmp_block;
64396950929SArunpravin Paneer Selvam break;
64496950929SArunpravin Paneer Selvam }
64596950929SArunpravin Paneer Selvam
64696950929SArunpravin Paneer Selvam if (block)
64796950929SArunpravin Paneer Selvam break;
64896950929SArunpravin Paneer Selvam }
64996950929SArunpravin Paneer Selvam }
65096950929SArunpravin Paneer Selvam
65196950929SArunpravin Paneer Selvam if (!block) {
65296950929SArunpravin Paneer Selvam /* Fallback method */
65396950929SArunpravin Paneer Selvam for (tmp = order; tmp <= mm->max_order; ++tmp) {
6545640e816SArunpravin Paneer Selvam if (!list_empty(&mm->free_list[tmp])) {
6555640e816SArunpravin Paneer Selvam block = list_last_entry(&mm->free_list[tmp],
6566387a3c4SArunpravin struct drm_buddy_block,
6576387a3c4SArunpravin link);
6586387a3c4SArunpravin if (block)
6596387a3c4SArunpravin break;
6606387a3c4SArunpravin }
661476e4063SArunpravin }
6626387a3c4SArunpravin
6636387a3c4SArunpravin if (!block)
6646387a3c4SArunpravin return ERR_PTR(-ENOSPC);
66596950929SArunpravin Paneer Selvam }
6666387a3c4SArunpravin
6676387a3c4SArunpravin BUG_ON(!drm_buddy_block_is_free(block));
6686387a3c4SArunpravin
6695640e816SArunpravin Paneer Selvam while (tmp != order) {
6706387a3c4SArunpravin err = split_block(mm, block);
6716387a3c4SArunpravin if (unlikely(err))
672afea229fSArunpravin goto err_undo;
6736387a3c4SArunpravin
674afea229fSArunpravin block = block->right;
6755640e816SArunpravin Paneer Selvam tmp--;
6766387a3c4SArunpravin }
6776387a3c4SArunpravin return block;
6786387a3c4SArunpravin
679afea229fSArunpravin err_undo:
6805640e816SArunpravin Paneer Selvam if (tmp != order)
68196950929SArunpravin Paneer Selvam __drm_buddy_free(mm, block, false);
6826387a3c4SArunpravin return ERR_PTR(err);
6836387a3c4SArunpravin }
6846387a3c4SArunpravin
__alloc_range(struct drm_buddy * mm,struct list_head * dfs,u64 start,u64 size,struct list_head * blocks,u64 * total_allocated_on_err)685afea229fSArunpravin static int __alloc_range(struct drm_buddy *mm,
686afea229fSArunpravin struct list_head *dfs,
687afea229fSArunpravin u64 start, u64 size,
6880a1844bfSArunpravin Paneer Selvam struct list_head *blocks,
6890a1844bfSArunpravin Paneer Selvam u64 *total_allocated_on_err)
6906387a3c4SArunpravin {
6916387a3c4SArunpravin struct drm_buddy_block *block;
6926387a3c4SArunpravin struct drm_buddy_block *buddy;
6930a1844bfSArunpravin Paneer Selvam u64 total_allocated = 0;
6946387a3c4SArunpravin LIST_HEAD(allocated);
6956387a3c4SArunpravin u64 end;
6966387a3c4SArunpravin int err;
6976387a3c4SArunpravin
6986387a3c4SArunpravin end = start + size - 1;
6996387a3c4SArunpravin
7006387a3c4SArunpravin do {
7016387a3c4SArunpravin u64 block_start;
7026387a3c4SArunpravin u64 block_end;
7036387a3c4SArunpravin
704afea229fSArunpravin block = list_first_entry_or_null(dfs,
7056387a3c4SArunpravin struct drm_buddy_block,
7066387a3c4SArunpravin tmp_link);
7076387a3c4SArunpravin if (!block)
7086387a3c4SArunpravin break;
7096387a3c4SArunpravin
7106387a3c4SArunpravin list_del(&block->tmp_link);
7116387a3c4SArunpravin
7126387a3c4SArunpravin block_start = drm_buddy_block_offset(block);
7136387a3c4SArunpravin block_end = block_start + drm_buddy_block_size(mm, block) - 1;
7146387a3c4SArunpravin
7156387a3c4SArunpravin if (!overlaps(start, end, block_start, block_end))
7166387a3c4SArunpravin continue;
7176387a3c4SArunpravin
7186387a3c4SArunpravin if (drm_buddy_block_is_allocated(block)) {
7196387a3c4SArunpravin err = -ENOSPC;
7206387a3c4SArunpravin goto err_free;
7216387a3c4SArunpravin }
7226387a3c4SArunpravin
7236387a3c4SArunpravin if (contains(start, end, block_start, block_end)) {
72496950929SArunpravin Paneer Selvam if (drm_buddy_block_is_free(block)) {
7256387a3c4SArunpravin mark_allocated(block);
7260a1844bfSArunpravin Paneer Selvam total_allocated += drm_buddy_block_size(mm, block);
7276387a3c4SArunpravin mm->avail -= drm_buddy_block_size(mm, block);
72896950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block))
72996950929SArunpravin Paneer Selvam mm->clear_avail -= drm_buddy_block_size(mm, block);
7306387a3c4SArunpravin list_add_tail(&block->link, &allocated);
7316387a3c4SArunpravin continue;
73296950929SArunpravin Paneer Selvam } else if (!mm->clear_avail) {
73396950929SArunpravin Paneer Selvam err = -ENOSPC;
73496950929SArunpravin Paneer Selvam goto err_free;
73596950929SArunpravin Paneer Selvam }
7366387a3c4SArunpravin }
7376387a3c4SArunpravin
7386387a3c4SArunpravin if (!drm_buddy_block_is_split(block)) {
7396387a3c4SArunpravin err = split_block(mm, block);
7406387a3c4SArunpravin if (unlikely(err))
7416387a3c4SArunpravin goto err_undo;
7426387a3c4SArunpravin }
7436387a3c4SArunpravin
744afea229fSArunpravin list_add(&block->right->tmp_link, dfs);
745afea229fSArunpravin list_add(&block->left->tmp_link, dfs);
7466387a3c4SArunpravin } while (1);
7476387a3c4SArunpravin
7488746c6c9SArunpravin Paneer Selvam if (total_allocated < size) {
7498746c6c9SArunpravin Paneer Selvam err = -ENOSPC;
7508746c6c9SArunpravin Paneer Selvam goto err_free;
7518746c6c9SArunpravin Paneer Selvam }
7528746c6c9SArunpravin Paneer Selvam
75302f76a9cSArunpravin Paneer Selvam list_splice_tail(&allocated, blocks);
75402f76a9cSArunpravin Paneer Selvam
7556387a3c4SArunpravin return 0;
7566387a3c4SArunpravin
7576387a3c4SArunpravin err_undo:
7586387a3c4SArunpravin /*
7596387a3c4SArunpravin * We really don't want to leave around a bunch of split blocks, since
7606387a3c4SArunpravin * bigger is better, so make sure we merge everything back before we
7616387a3c4SArunpravin * free the allocated blocks.
7626387a3c4SArunpravin */
76392937f17SArunpravin buddy = __get_buddy(block);
7646387a3c4SArunpravin if (buddy &&
7656387a3c4SArunpravin (drm_buddy_block_is_free(block) &&
7666387a3c4SArunpravin drm_buddy_block_is_free(buddy)))
76796950929SArunpravin Paneer Selvam __drm_buddy_free(mm, block, false);
7686387a3c4SArunpravin
7696387a3c4SArunpravin err_free:
7700a1844bfSArunpravin Paneer Selvam if (err == -ENOSPC && total_allocated_on_err) {
7710a1844bfSArunpravin Paneer Selvam list_splice_tail(&allocated, blocks);
7720a1844bfSArunpravin Paneer Selvam *total_allocated_on_err = total_allocated;
7730a1844bfSArunpravin Paneer Selvam } else {
77496950929SArunpravin Paneer Selvam drm_buddy_free_list_internal(mm, &allocated);
7750a1844bfSArunpravin Paneer Selvam }
7760a1844bfSArunpravin Paneer Selvam
7776387a3c4SArunpravin return err;
7786387a3c4SArunpravin }
779afea229fSArunpravin
__drm_buddy_alloc_range(struct drm_buddy * mm,u64 start,u64 size,u64 * total_allocated_on_err,struct list_head * blocks)780afea229fSArunpravin static int __drm_buddy_alloc_range(struct drm_buddy *mm,
781afea229fSArunpravin u64 start,
782afea229fSArunpravin u64 size,
7830a1844bfSArunpravin Paneer Selvam u64 *total_allocated_on_err,
784afea229fSArunpravin struct list_head *blocks)
785afea229fSArunpravin {
786afea229fSArunpravin LIST_HEAD(dfs);
787afea229fSArunpravin int i;
788afea229fSArunpravin
789afea229fSArunpravin for (i = 0; i < mm->n_roots; ++i)
790afea229fSArunpravin list_add_tail(&mm->roots[i]->tmp_link, &dfs);
791afea229fSArunpravin
7920a1844bfSArunpravin Paneer Selvam return __alloc_range(mm, &dfs, start, size,
7930a1844bfSArunpravin Paneer Selvam blocks, total_allocated_on_err);
7940a1844bfSArunpravin Paneer Selvam }
7950a1844bfSArunpravin Paneer Selvam
__alloc_contig_try_harder(struct drm_buddy * mm,u64 size,u64 min_block_size,struct list_head * blocks)7960a1844bfSArunpravin Paneer Selvam static int __alloc_contig_try_harder(struct drm_buddy *mm,
7970a1844bfSArunpravin Paneer Selvam u64 size,
7980a1844bfSArunpravin Paneer Selvam u64 min_block_size,
7990a1844bfSArunpravin Paneer Selvam struct list_head *blocks)
8000a1844bfSArunpravin Paneer Selvam {
8010a1844bfSArunpravin Paneer Selvam u64 rhs_offset, lhs_offset, lhs_size, filled;
8020a1844bfSArunpravin Paneer Selvam struct drm_buddy_block *block;
8030a1844bfSArunpravin Paneer Selvam struct list_head *list;
8040a1844bfSArunpravin Paneer Selvam LIST_HEAD(blocks_lhs);
8050a1844bfSArunpravin Paneer Selvam unsigned long pages;
8060a1844bfSArunpravin Paneer Selvam unsigned int order;
8070a1844bfSArunpravin Paneer Selvam u64 modify_size;
8080a1844bfSArunpravin Paneer Selvam int err;
8090a1844bfSArunpravin Paneer Selvam
8100a1844bfSArunpravin Paneer Selvam modify_size = rounddown_pow_of_two(size);
8110a1844bfSArunpravin Paneer Selvam pages = modify_size >> ilog2(mm->chunk_size);
8120a1844bfSArunpravin Paneer Selvam order = fls(pages) - 1;
8130a1844bfSArunpravin Paneer Selvam if (order == 0)
8140a1844bfSArunpravin Paneer Selvam return -ENOSPC;
8150a1844bfSArunpravin Paneer Selvam
8160a1844bfSArunpravin Paneer Selvam list = &mm->free_list[order];
8170a1844bfSArunpravin Paneer Selvam if (list_empty(list))
8180a1844bfSArunpravin Paneer Selvam return -ENOSPC;
8190a1844bfSArunpravin Paneer Selvam
8200a1844bfSArunpravin Paneer Selvam list_for_each_entry_reverse(block, list, link) {
8210a1844bfSArunpravin Paneer Selvam /* Allocate blocks traversing RHS */
8220a1844bfSArunpravin Paneer Selvam rhs_offset = drm_buddy_block_offset(block);
8230a1844bfSArunpravin Paneer Selvam err = __drm_buddy_alloc_range(mm, rhs_offset, size,
8240a1844bfSArunpravin Paneer Selvam &filled, blocks);
8250a1844bfSArunpravin Paneer Selvam if (!err || err != -ENOSPC)
8260a1844bfSArunpravin Paneer Selvam return err;
8270a1844bfSArunpravin Paneer Selvam
8280a1844bfSArunpravin Paneer Selvam lhs_size = max((size - filled), min_block_size);
8290a1844bfSArunpravin Paneer Selvam if (!IS_ALIGNED(lhs_size, min_block_size))
8300a1844bfSArunpravin Paneer Selvam lhs_size = round_up(lhs_size, min_block_size);
8310a1844bfSArunpravin Paneer Selvam
8320a1844bfSArunpravin Paneer Selvam /* Allocate blocks traversing LHS */
8330a1844bfSArunpravin Paneer Selvam lhs_offset = drm_buddy_block_offset(block) - lhs_size;
8340a1844bfSArunpravin Paneer Selvam err = __drm_buddy_alloc_range(mm, lhs_offset, lhs_size,
8350a1844bfSArunpravin Paneer Selvam NULL, &blocks_lhs);
8360a1844bfSArunpravin Paneer Selvam if (!err) {
8370a1844bfSArunpravin Paneer Selvam list_splice(&blocks_lhs, blocks);
8380a1844bfSArunpravin Paneer Selvam return 0;
8390a1844bfSArunpravin Paneer Selvam } else if (err != -ENOSPC) {
84096950929SArunpravin Paneer Selvam drm_buddy_free_list_internal(mm, blocks);
8410a1844bfSArunpravin Paneer Selvam return err;
8420a1844bfSArunpravin Paneer Selvam }
8430a1844bfSArunpravin Paneer Selvam /* Free blocks for the next iteration */
84496950929SArunpravin Paneer Selvam drm_buddy_free_list_internal(mm, blocks);
8450a1844bfSArunpravin Paneer Selvam }
8460a1844bfSArunpravin Paneer Selvam
8470a1844bfSArunpravin Paneer Selvam return -ENOSPC;
848afea229fSArunpravin }
849afea229fSArunpravin
850afea229fSArunpravin /**
85195ee2a8bSArunpravin * drm_buddy_block_trim - free unused pages
85295ee2a8bSArunpravin *
85395ee2a8bSArunpravin * @mm: DRM buddy manager
854*d507ae0dSArunpravin Paneer Selvam * @start: start address to begin the trimming.
85595ee2a8bSArunpravin * @new_size: original size requested
85695ee2a8bSArunpravin * @blocks: Input and output list of allocated blocks.
85795ee2a8bSArunpravin * MUST contain single block as input to be trimmed.
85895ee2a8bSArunpravin * On success will contain the newly allocated blocks
85995ee2a8bSArunpravin * making up the @new_size. Blocks always appear in
86095ee2a8bSArunpravin * ascending order
86195ee2a8bSArunpravin *
86295ee2a8bSArunpravin * For contiguous allocation, we round up the size to the nearest
86395ee2a8bSArunpravin * power of two value, drivers consume *actual* size, so remaining
86495ee2a8bSArunpravin * portions are unused and can be optionally freed with this function
86595ee2a8bSArunpravin *
86695ee2a8bSArunpravin * Returns:
86795ee2a8bSArunpravin * 0 on success, error code on failure.
86895ee2a8bSArunpravin */
drm_buddy_block_trim(struct drm_buddy * mm,u64 * start,u64 new_size,struct list_head * blocks)86995ee2a8bSArunpravin int drm_buddy_block_trim(struct drm_buddy *mm,
870*d507ae0dSArunpravin Paneer Selvam u64 *start,
87195ee2a8bSArunpravin u64 new_size,
87295ee2a8bSArunpravin struct list_head *blocks)
87395ee2a8bSArunpravin {
87495ee2a8bSArunpravin struct drm_buddy_block *parent;
87595ee2a8bSArunpravin struct drm_buddy_block *block;
876*d507ae0dSArunpravin Paneer Selvam u64 block_start, block_end;
87795ee2a8bSArunpravin LIST_HEAD(dfs);
87895ee2a8bSArunpravin u64 new_start;
87995ee2a8bSArunpravin int err;
88095ee2a8bSArunpravin
88195ee2a8bSArunpravin if (!list_is_singular(blocks))
88295ee2a8bSArunpravin return -EINVAL;
88395ee2a8bSArunpravin
88495ee2a8bSArunpravin block = list_first_entry(blocks,
88595ee2a8bSArunpravin struct drm_buddy_block,
88695ee2a8bSArunpravin link);
88795ee2a8bSArunpravin
888*d507ae0dSArunpravin Paneer Selvam block_start = drm_buddy_block_offset(block);
889*d507ae0dSArunpravin Paneer Selvam block_end = block_start + drm_buddy_block_size(mm, block);
890*d507ae0dSArunpravin Paneer Selvam
89195ee2a8bSArunpravin if (WARN_ON(!drm_buddy_block_is_allocated(block)))
89295ee2a8bSArunpravin return -EINVAL;
89395ee2a8bSArunpravin
89495ee2a8bSArunpravin if (new_size > drm_buddy_block_size(mm, block))
89595ee2a8bSArunpravin return -EINVAL;
89695ee2a8bSArunpravin
89795ee2a8bSArunpravin if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))
89895ee2a8bSArunpravin return -EINVAL;
89995ee2a8bSArunpravin
90095ee2a8bSArunpravin if (new_size == drm_buddy_block_size(mm, block))
90195ee2a8bSArunpravin return 0;
90295ee2a8bSArunpravin
903*d507ae0dSArunpravin Paneer Selvam new_start = block_start;
904*d507ae0dSArunpravin Paneer Selvam if (start) {
905*d507ae0dSArunpravin Paneer Selvam new_start = *start;
906*d507ae0dSArunpravin Paneer Selvam
907*d507ae0dSArunpravin Paneer Selvam if (new_start < block_start)
908*d507ae0dSArunpravin Paneer Selvam return -EINVAL;
909*d507ae0dSArunpravin Paneer Selvam
910*d507ae0dSArunpravin Paneer Selvam if (!IS_ALIGNED(new_start, mm->chunk_size))
911*d507ae0dSArunpravin Paneer Selvam return -EINVAL;
912*d507ae0dSArunpravin Paneer Selvam
913*d507ae0dSArunpravin Paneer Selvam if (range_overflows(new_start, new_size, block_end))
914*d507ae0dSArunpravin Paneer Selvam return -EINVAL;
915*d507ae0dSArunpravin Paneer Selvam }
916*d507ae0dSArunpravin Paneer Selvam
91795ee2a8bSArunpravin list_del(&block->link);
91895ee2a8bSArunpravin mark_free(mm, block);
91995ee2a8bSArunpravin mm->avail += drm_buddy_block_size(mm, block);
92096950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block))
92196950929SArunpravin Paneer Selvam mm->clear_avail += drm_buddy_block_size(mm, block);
92295ee2a8bSArunpravin
92395ee2a8bSArunpravin /* Prevent recursively freeing this node */
92495ee2a8bSArunpravin parent = block->parent;
92595ee2a8bSArunpravin block->parent = NULL;
92695ee2a8bSArunpravin
92795ee2a8bSArunpravin list_add(&block->tmp_link, &dfs);
9280a1844bfSArunpravin Paneer Selvam err = __alloc_range(mm, &dfs, new_start, new_size, blocks, NULL);
92995ee2a8bSArunpravin if (err) {
93095ee2a8bSArunpravin mark_allocated(block);
93195ee2a8bSArunpravin mm->avail -= drm_buddy_block_size(mm, block);
93296950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block))
93396950929SArunpravin Paneer Selvam mm->clear_avail -= drm_buddy_block_size(mm, block);
93495ee2a8bSArunpravin list_add(&block->link, blocks);
93595ee2a8bSArunpravin }
93695ee2a8bSArunpravin
93795ee2a8bSArunpravin block->parent = parent;
93895ee2a8bSArunpravin return err;
93995ee2a8bSArunpravin }
94095ee2a8bSArunpravin EXPORT_SYMBOL(drm_buddy_block_trim);
94195ee2a8bSArunpravin
94296950929SArunpravin Paneer Selvam static struct drm_buddy_block *
__drm_buddy_alloc_blocks(struct drm_buddy * mm,u64 start,u64 end,unsigned int order,unsigned long flags)94396950929SArunpravin Paneer Selvam __drm_buddy_alloc_blocks(struct drm_buddy *mm,
94496950929SArunpravin Paneer Selvam u64 start, u64 end,
94596950929SArunpravin Paneer Selvam unsigned int order,
94696950929SArunpravin Paneer Selvam unsigned long flags)
94796950929SArunpravin Paneer Selvam {
94896950929SArunpravin Paneer Selvam if (flags & DRM_BUDDY_RANGE_ALLOCATION)
94996950929SArunpravin Paneer Selvam /* Allocate traversing within the range */
95096950929SArunpravin Paneer Selvam return __drm_buddy_alloc_range_bias(mm, start, end,
95196950929SArunpravin Paneer Selvam order, flags);
95296950929SArunpravin Paneer Selvam else
95396950929SArunpravin Paneer Selvam /* Allocate from freelist */
95496950929SArunpravin Paneer Selvam return alloc_from_freelist(mm, order, flags);
95596950929SArunpravin Paneer Selvam }
95696950929SArunpravin Paneer Selvam
95795ee2a8bSArunpravin /**
958afea229fSArunpravin * drm_buddy_alloc_blocks - allocate power-of-two blocks
959afea229fSArunpravin *
960afea229fSArunpravin * @mm: DRM buddy manager to allocate from
961afea229fSArunpravin * @start: start of the allowed range for this block
962afea229fSArunpravin * @end: end of the allowed range for this block
96396950929SArunpravin Paneer Selvam * @size: size of the allocation in bytes
9640a1844bfSArunpravin Paneer Selvam * @min_block_size: alignment of the allocation
965afea229fSArunpravin * @blocks: output list head to add allocated blocks
966afea229fSArunpravin * @flags: DRM_BUDDY_*_ALLOCATION flags
967afea229fSArunpravin *
968afea229fSArunpravin * alloc_range_bias() called on range limitations, which traverses
969afea229fSArunpravin * the tree and returns the desired block.
970afea229fSArunpravin *
971afea229fSArunpravin * alloc_from_freelist() called when *no* range restrictions
972afea229fSArunpravin * are enforced, which picks the block from the freelist.
973afea229fSArunpravin *
974afea229fSArunpravin * Returns:
975afea229fSArunpravin * 0 on success, error code on failure.
976afea229fSArunpravin */
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)977afea229fSArunpravin int drm_buddy_alloc_blocks(struct drm_buddy *mm,
978afea229fSArunpravin u64 start, u64 end, u64 size,
9790a1844bfSArunpravin Paneer Selvam u64 min_block_size,
980afea229fSArunpravin struct list_head *blocks,
981afea229fSArunpravin unsigned long flags)
982afea229fSArunpravin {
983afea229fSArunpravin struct drm_buddy_block *block = NULL;
9840a1844bfSArunpravin Paneer Selvam u64 original_size, original_min_size;
985afea229fSArunpravin unsigned int min_order, order;
986afea229fSArunpravin LIST_HEAD(allocated);
9870a1844bfSArunpravin Paneer Selvam unsigned long pages;
988afea229fSArunpravin int err;
989afea229fSArunpravin
990afea229fSArunpravin if (size < mm->chunk_size)
991afea229fSArunpravin return -EINVAL;
992afea229fSArunpravin
9930a1844bfSArunpravin Paneer Selvam if (min_block_size < mm->chunk_size)
994afea229fSArunpravin return -EINVAL;
995afea229fSArunpravin
9960a1844bfSArunpravin Paneer Selvam if (!is_power_of_2(min_block_size))
997afea229fSArunpravin return -EINVAL;
998afea229fSArunpravin
999afea229fSArunpravin if (!IS_ALIGNED(start | end | size, mm->chunk_size))
1000afea229fSArunpravin return -EINVAL;
1001afea229fSArunpravin
1002afea229fSArunpravin if (end > mm->size)
1003afea229fSArunpravin return -EINVAL;
1004afea229fSArunpravin
1005afea229fSArunpravin if (range_overflows(start, size, mm->size))
1006afea229fSArunpravin return -EINVAL;
1007afea229fSArunpravin
1008afea229fSArunpravin /* Actual range allocation */
10092986314aSMatthew Auld if (start + size == end) {
10102986314aSMatthew Auld if (!IS_ALIGNED(start | end, min_block_size))
10112986314aSMatthew Auld return -EINVAL;
10122986314aSMatthew Auld
10130a1844bfSArunpravin Paneer Selvam return __drm_buddy_alloc_range(mm, start, size, NULL, blocks);
10142986314aSMatthew Auld }
1015afea229fSArunpravin
10160a1844bfSArunpravin Paneer Selvam original_size = size;
10170a1844bfSArunpravin Paneer Selvam original_min_size = min_block_size;
10180a1844bfSArunpravin Paneer Selvam
10190a1844bfSArunpravin Paneer Selvam /* Roundup the size to power of 2 */
10200a1844bfSArunpravin Paneer Selvam if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION) {
10210a1844bfSArunpravin Paneer Selvam size = roundup_pow_of_two(size);
10220a1844bfSArunpravin Paneer Selvam min_block_size = size;
10230a1844bfSArunpravin Paneer Selvam /* Align size value to min_block_size */
10240a1844bfSArunpravin Paneer Selvam } else if (!IS_ALIGNED(size, min_block_size)) {
10250a1844bfSArunpravin Paneer Selvam size = round_up(size, min_block_size);
10260a1844bfSArunpravin Paneer Selvam }
10275f778760SArunpravin Paneer Selvam
1028afea229fSArunpravin pages = size >> ilog2(mm->chunk_size);
1029afea229fSArunpravin order = fls(pages) - 1;
10300a1844bfSArunpravin Paneer Selvam min_order = ilog2(min_block_size) - ilog2(mm->chunk_size);
1031afea229fSArunpravin
1032afea229fSArunpravin do {
1033afea229fSArunpravin order = min(order, (unsigned int)fls(pages) - 1);
1034afea229fSArunpravin BUG_ON(order > mm->max_order);
1035afea229fSArunpravin BUG_ON(order < min_order);
1036afea229fSArunpravin
1037afea229fSArunpravin do {
103896950929SArunpravin Paneer Selvam block = __drm_buddy_alloc_blocks(mm, start,
103996950929SArunpravin Paneer Selvam end,
104096950929SArunpravin Paneer Selvam order,
104196950929SArunpravin Paneer Selvam flags);
1042afea229fSArunpravin if (!IS_ERR(block))
1043afea229fSArunpravin break;
1044afea229fSArunpravin
1045afea229fSArunpravin if (order-- == min_order) {
104696950929SArunpravin Paneer Selvam /* Try allocation through force merge method */
104796950929SArunpravin Paneer Selvam if (mm->clear_avail &&
104896950929SArunpravin Paneer Selvam !__force_merge(mm, start, end, min_order)) {
104996950929SArunpravin Paneer Selvam block = __drm_buddy_alloc_blocks(mm, start,
105096950929SArunpravin Paneer Selvam end,
105196950929SArunpravin Paneer Selvam min_order,
105296950929SArunpravin Paneer Selvam flags);
105396950929SArunpravin Paneer Selvam if (!IS_ERR(block)) {
105496950929SArunpravin Paneer Selvam order = min_order;
105596950929SArunpravin Paneer Selvam break;
105696950929SArunpravin Paneer Selvam }
105796950929SArunpravin Paneer Selvam }
105896950929SArunpravin Paneer Selvam
10590a1844bfSArunpravin Paneer Selvam /*
10600a1844bfSArunpravin Paneer Selvam * Try contiguous block allocation through
106196950929SArunpravin Paneer Selvam * try harder method.
10620a1844bfSArunpravin Paneer Selvam */
106396950929SArunpravin Paneer Selvam if (flags & DRM_BUDDY_CONTIGUOUS_ALLOCATION &&
106496950929SArunpravin Paneer Selvam !(flags & DRM_BUDDY_RANGE_ALLOCATION))
10650a1844bfSArunpravin Paneer Selvam return __alloc_contig_try_harder(mm,
10660a1844bfSArunpravin Paneer Selvam original_size,
10670a1844bfSArunpravin Paneer Selvam original_min_size,
10680a1844bfSArunpravin Paneer Selvam blocks);
1069afea229fSArunpravin err = -ENOSPC;
1070afea229fSArunpravin goto err_free;
1071afea229fSArunpravin }
1072afea229fSArunpravin } while (1);
1073afea229fSArunpravin
1074afea229fSArunpravin mark_allocated(block);
1075afea229fSArunpravin mm->avail -= drm_buddy_block_size(mm, block);
107696950929SArunpravin Paneer Selvam if (drm_buddy_block_is_clear(block))
107796950929SArunpravin Paneer Selvam mm->clear_avail -= drm_buddy_block_size(mm, block);
1078afea229fSArunpravin kmemleak_update_trace(block);
1079afea229fSArunpravin list_add_tail(&block->link, &allocated);
1080afea229fSArunpravin
1081afea229fSArunpravin pages -= BIT(order);
1082afea229fSArunpravin
1083afea229fSArunpravin if (!pages)
1084afea229fSArunpravin break;
1085afea229fSArunpravin } while (1);
1086afea229fSArunpravin
10870a1844bfSArunpravin Paneer Selvam /* Trim the allocated block to the required size */
1088*d507ae0dSArunpravin Paneer Selvam if (!(flags & DRM_BUDDY_TRIM_DISABLE) &&
1089*d507ae0dSArunpravin Paneer Selvam original_size != size) {
10900a1844bfSArunpravin Paneer Selvam struct list_head *trim_list;
10910a1844bfSArunpravin Paneer Selvam LIST_HEAD(temp);
10920a1844bfSArunpravin Paneer Selvam u64 trim_size;
10930a1844bfSArunpravin Paneer Selvam
10940a1844bfSArunpravin Paneer Selvam trim_list = &allocated;
10950a1844bfSArunpravin Paneer Selvam trim_size = original_size;
10960a1844bfSArunpravin Paneer Selvam
10970a1844bfSArunpravin Paneer Selvam if (!list_is_singular(&allocated)) {
10980a1844bfSArunpravin Paneer Selvam block = list_last_entry(&allocated, typeof(*block), link);
10990a1844bfSArunpravin Paneer Selvam list_move(&block->link, &temp);
11000a1844bfSArunpravin Paneer Selvam trim_list = &temp;
11010a1844bfSArunpravin Paneer Selvam trim_size = drm_buddy_block_size(mm, block) -
11020a1844bfSArunpravin Paneer Selvam (size - original_size);
11030a1844bfSArunpravin Paneer Selvam }
11040a1844bfSArunpravin Paneer Selvam
11050a1844bfSArunpravin Paneer Selvam drm_buddy_block_trim(mm,
1106*d507ae0dSArunpravin Paneer Selvam NULL,
11070a1844bfSArunpravin Paneer Selvam trim_size,
11080a1844bfSArunpravin Paneer Selvam trim_list);
11090a1844bfSArunpravin Paneer Selvam
11100a1844bfSArunpravin Paneer Selvam if (!list_empty(&temp))
11110a1844bfSArunpravin Paneer Selvam list_splice_tail(trim_list, &allocated);
11120a1844bfSArunpravin Paneer Selvam }
11130a1844bfSArunpravin Paneer Selvam
1114afea229fSArunpravin list_splice_tail(&allocated, blocks);
1115afea229fSArunpravin return 0;
1116afea229fSArunpravin
1117afea229fSArunpravin err_free:
111896950929SArunpravin Paneer Selvam drm_buddy_free_list_internal(mm, &allocated);
1119afea229fSArunpravin return err;
1120afea229fSArunpravin }
1121afea229fSArunpravin EXPORT_SYMBOL(drm_buddy_alloc_blocks);
11226387a3c4SArunpravin
11236387a3c4SArunpravin /**
11246387a3c4SArunpravin * drm_buddy_block_print - print block information
11256387a3c4SArunpravin *
11266387a3c4SArunpravin * @mm: DRM buddy manager
11276387a3c4SArunpravin * @block: DRM buddy block
11286387a3c4SArunpravin * @p: DRM printer to use
11296387a3c4SArunpravin */
drm_buddy_block_print(struct drm_buddy * mm,struct drm_buddy_block * block,struct drm_printer * p)11306387a3c4SArunpravin void drm_buddy_block_print(struct drm_buddy *mm,
11316387a3c4SArunpravin struct drm_buddy_block *block,
11326387a3c4SArunpravin struct drm_printer *p)
11336387a3c4SArunpravin {
11346387a3c4SArunpravin u64 start = drm_buddy_block_offset(block);
11356387a3c4SArunpravin u64 size = drm_buddy_block_size(mm, block);
11366387a3c4SArunpravin
11376387a3c4SArunpravin drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size);
11386387a3c4SArunpravin }
11396387a3c4SArunpravin EXPORT_SYMBOL(drm_buddy_block_print);
11406387a3c4SArunpravin
11416387a3c4SArunpravin /**
11426387a3c4SArunpravin * drm_buddy_print - print allocator state
11436387a3c4SArunpravin *
11446387a3c4SArunpravin * @mm: DRM buddy manager
11456387a3c4SArunpravin * @p: DRM printer to use
11466387a3c4SArunpravin */
drm_buddy_print(struct drm_buddy * mm,struct drm_printer * p)11476387a3c4SArunpravin void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)
11486387a3c4SArunpravin {
11496387a3c4SArunpravin int order;
11506387a3c4SArunpravin
115196950929SArunpravin Paneer Selvam drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB, clear_free: %lluMiB\n",
115296950929SArunpravin Paneer Selvam mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20, mm->clear_avail >> 20);
11536387a3c4SArunpravin
11546387a3c4SArunpravin for (order = mm->max_order; order >= 0; order--) {
11556387a3c4SArunpravin struct drm_buddy_block *block;
11566387a3c4SArunpravin u64 count = 0, free;
11576387a3c4SArunpravin
11586387a3c4SArunpravin list_for_each_entry(block, &mm->free_list[order], link) {
11596387a3c4SArunpravin BUG_ON(!drm_buddy_block_is_free(block));
11606387a3c4SArunpravin count++;
11616387a3c4SArunpravin }
11626387a3c4SArunpravin
1163cd11589bSMa Jun drm_printf(p, "order-%2d ", order);
11646387a3c4SArunpravin
11656387a3c4SArunpravin free = count * (mm->chunk_size << order);
11666387a3c4SArunpravin if (free < SZ_1M)
1167cd11589bSMa Jun drm_printf(p, "free: %8llu KiB", free >> 10);
11686387a3c4SArunpravin else
1169cd11589bSMa Jun drm_printf(p, "free: %8llu MiB", free >> 20);
11706387a3c4SArunpravin
1171cd11589bSMa Jun drm_printf(p, ", blocks: %llu\n", count);
11726387a3c4SArunpravin }
11736387a3c4SArunpravin }
11746387a3c4SArunpravin EXPORT_SYMBOL(drm_buddy_print);
11756387a3c4SArunpravin
drm_buddy_module_exit(void)11766387a3c4SArunpravin static void drm_buddy_module_exit(void)
11776387a3c4SArunpravin {
11786387a3c4SArunpravin kmem_cache_destroy(slab_blocks);
11796387a3c4SArunpravin }
11806387a3c4SArunpravin
drm_buddy_module_init(void)11816387a3c4SArunpravin static int __init drm_buddy_module_init(void)
11826387a3c4SArunpravin {
11836387a3c4SArunpravin slab_blocks = KMEM_CACHE(drm_buddy_block, 0);
11846387a3c4SArunpravin if (!slab_blocks)
11856387a3c4SArunpravin return -ENOMEM;
11866387a3c4SArunpravin
11876387a3c4SArunpravin return 0;
11886387a3c4SArunpravin }
11896387a3c4SArunpravin
11906387a3c4SArunpravin module_init(drm_buddy_module_init);
11916387a3c4SArunpravin module_exit(drm_buddy_module_exit);
11926387a3c4SArunpravin
11936387a3c4SArunpravin MODULE_DESCRIPTION("DRM Buddy Allocator");
11946387a3c4SArunpravin MODULE_LICENSE("Dual MIT/GPL");
1195