[linux-block.git] / drivers / gpu / drm / drm_buddy.c

// SPDX-License-Identifier: MIT
/*
 * Copyright © 2021 Intel Corporation
 */

#include <linux/kmemleak.h>
#include <linux/module.h>
#include <linux/sizes.h>

#include <drm/drm_buddy.h>

static struct kmem_cache *slab_blocks;

static struct drm_buddy_block *drm_block_alloc(struct drm_buddy *mm,
					       struct drm_buddy_block *parent,
					       unsigned int order,
					       u64 offset)
{
	struct drm_buddy_block *block;

	BUG_ON(order > DRM_BUDDY_MAX_ORDER);

	block = kmem_cache_zalloc(slab_blocks, GFP_KERNEL);
	if (!block)
		return NULL;

	block->header = offset;
	block->header |= order;
	block->parent = parent;

	BUG_ON(block->header & DRM_BUDDY_HEADER_UNUSED);
	return block;
}

static void drm_block_free(struct drm_buddy *mm,
			   struct drm_buddy_block *block)
{
	kmem_cache_free(slab_blocks, block);
}

static void mark_allocated(struct drm_buddy_block *block)
{
	block->header &= ~DRM_BUDDY_HEADER_STATE;
	block->header |= DRM_BUDDY_ALLOCATED;

	list_del(&block->link);
}

static void mark_free(struct drm_buddy *mm,
		      struct drm_buddy_block *block)
{
	block->header &= ~DRM_BUDDY_HEADER_STATE;
	block->header |= DRM_BUDDY_FREE;

	list_add(&block->link,
		 &mm->free_list[drm_buddy_block_order(block)]);
}

static void mark_split(struct drm_buddy_block *block)
{
	block->header &= ~DRM_BUDDY_HEADER_STATE;
	block->header |= DRM_BUDDY_SPLIT;

	list_del(&block->link);
}

/**
 * drm_buddy_init - init memory manager
 *
 * @mm: DRM buddy manager to initialize
 * @size: size in bytes to manage
 * @chunk_size: minimum page size in bytes for our allocations
 *
 * Initializes the memory manager and its resources.
 *
 * Returns:
 * 0 on success, error code on failure.
 */
int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size)
{
	unsigned int i;
	u64 offset;

	if (size < chunk_size)
		return -EINVAL;

	if (chunk_size < PAGE_SIZE)
		return -EINVAL;

	if (!is_power_of_2(chunk_size))
		return -EINVAL;

	size = round_down(size, chunk_size);

	mm->size = size;
	mm->avail = size;
	mm->chunk_size = chunk_size;
	mm->max_order = ilog2(size) - ilog2(chunk_size);

	BUG_ON(mm->max_order > DRM_BUDDY_MAX_ORDER);

	mm->free_list = kmalloc_array(mm->max_order + 1,
				      sizeof(struct list_head),
				      GFP_KERNEL);
	if (!mm->free_list)
		return -ENOMEM;

	for (i = 0; i <= mm->max_order; ++i)
		INIT_LIST_HEAD(&mm->free_list[i]);

	mm->n_roots = hweight64(size);

	mm->roots = kmalloc_array(mm->n_roots,
				  sizeof(struct drm_buddy_block *),
				  GFP_KERNEL);
	if (!mm->roots)
		goto out_free_list;

	offset = 0;
	i = 0;

	/*
	 * Split into power-of-two blocks, in case we are given a size that is
	 * not itself a power-of-two.
	 */
	do {
		struct drm_buddy_block *root;
		unsigned int order;
		u64 root_size;

		root_size = rounddown_pow_of_two(size);
		order = ilog2(root_size) - ilog2(chunk_size);

		root = drm_block_alloc(mm, NULL, order, offset);
		if (!root)
			goto out_free_roots;

		mark_free(mm, root);

		BUG_ON(i > mm->max_order);
		BUG_ON(drm_buddy_block_size(mm, root) < chunk_size);

		mm->roots[i] = root;

		offset += root_size;
		size -= root_size;
		i++;
	} while (size);

	return 0;

out_free_roots:
	while (i--)
		drm_block_free(mm, mm->roots[i]);
	kfree(mm->roots);
out_free_list:
	kfree(mm->free_list);
	return -ENOMEM;
}
EXPORT_SYMBOL(drm_buddy_init);

/**
 * drm_buddy_fini - tear down the memory manager
 *
 * @mm: DRM buddy manager to free
 *
 * Cleanup memory manager resources and the freelist
 */
void drm_buddy_fini(struct drm_buddy *mm)
{
	int i;

	for (i = 0; i < mm->n_roots; ++i) {
		WARN_ON(!drm_buddy_block_is_free(mm->roots[i]));
		drm_block_free(mm, mm->roots[i]);
	}

	WARN_ON(mm->avail != mm->size);

	kfree(mm->roots);
	kfree(mm->free_list);
}
EXPORT_SYMBOL(drm_buddy_fini);

static int split_block(struct drm_buddy *mm,
		       struct drm_buddy_block *block)
{
	unsigned int block_order = drm_buddy_block_order(block) - 1;
	u64 offset = drm_buddy_block_offset(block);

	BUG_ON(!drm_buddy_block_is_free(block));
	BUG_ON(!drm_buddy_block_order(block));

	block->left = drm_block_alloc(mm, block, block_order, offset);
	if (!block->left)
		return -ENOMEM;

	block->right = drm_block_alloc(mm, block, block_order,
				       offset + (mm->chunk_size << block_order));
	if (!block->right) {
		drm_block_free(mm, block->left);
		return -ENOMEM;
	}

	mark_free(mm, block->left);
	mark_free(mm, block->right);

	mark_split(block);

	return 0;
}

static struct drm_buddy_block *
__get_buddy(struct drm_buddy_block *block)
{
	struct drm_buddy_block *parent;

	parent = block->parent;
	if (!parent)
		return NULL;

	if (parent->left == block)
		return parent->right;

	return parent->left;
}

/**
 * drm_get_buddy - get buddy address
 *
 * @block: DRM buddy block
 *
 * Returns the corresponding buddy block for @block, or NULL
 * if this is a root block and can't be merged further.
 * Requires some kind of locking to protect against
 * any concurrent allocate and free operations.
 */
struct drm_buddy_block *
drm_get_buddy(struct drm_buddy_block *block)
{
	return __get_buddy(block);
}
EXPORT_SYMBOL(drm_get_buddy);

static void __drm_buddy_free(struct drm_buddy *mm,
			     struct drm_buddy_block *block)
{
	struct drm_buddy_block *parent;

	while ((parent = block->parent)) {
		struct drm_buddy_block *buddy;

		buddy = __get_buddy(block);

		if (!drm_buddy_block_is_free(buddy))
			break;

		list_del(&buddy->link);

		drm_block_free(mm, block);
		drm_block_free(mm, buddy);

		block = parent;
	}

	mark_free(mm, block);
}

/**
 * drm_buddy_free_block - free a block
 *
 * @mm: DRM buddy manager
 * @block: block to be freed
 */
void drm_buddy_free_block(struct drm_buddy *mm,
			  struct drm_buddy_block *block)
{
	BUG_ON(!drm_buddy_block_is_allocated(block));
	mm->avail += drm_buddy_block_size(mm, block);
	__drm_buddy_free(mm, block);
}
EXPORT_SYMBOL(drm_buddy_free_block);

/**
 * drm_buddy_free_list - free blocks
 *
 * @mm: DRM buddy manager
 * @objects: input list head to free blocks
 */
void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects)
{
	struct drm_buddy_block *block, *on;

	list_for_each_entry_safe(block, on, objects, link) {
		drm_buddy_free_block(mm, block);
		cond_resched();
	}
	INIT_LIST_HEAD(objects);
}
EXPORT_SYMBOL(drm_buddy_free_list);

static inline bool overlaps(u64 s1, u64 e1, u64 s2, u64 e2)
{
	return s1 <= e2 && e1 >= s2;
}

static inline bool contains(u64 s1, u64 e1, u64 s2, u64 e2)
{
	return s1 <= s2 && e1 >= e2;
}

static struct drm_buddy_block *
alloc_range_bias(struct drm_buddy *mm,
		 u64 start, u64 end,
		 unsigned int order)
{
	struct drm_buddy_block *block;
	struct drm_buddy_block *buddy;
	LIST_HEAD(dfs);
	int err;
	int i;

	end = end - 1;

	for (i = 0; i < mm->n_roots; ++i)
		list_add_tail(&mm->roots[i]->tmp_link, &dfs);

	do {
		u64 block_start;
		u64 block_end;

		block = list_first_entry_or_null(&dfs,
						 struct drm_buddy_block,
						 tmp_link);
		if (!block)
			break;

		list_del(&block->tmp_link);

		if (drm_buddy_block_order(block) < order)
			continue;

		block_start = drm_buddy_block_offset(block);
		block_end = block_start + drm_buddy_block_size(mm, block) - 1;

		if (!overlaps(start, end, block_start, block_end))
			continue;

		if (drm_buddy_block_is_allocated(block))
			continue;

		if (contains(start, end, block_start, block_end) &&
		    order == drm_buddy_block_order(block)) {
			/*
			 * Find the free block within the range.
			 */
			if (drm_buddy_block_is_free(block))
				return block;

			continue;
		}

		if (!drm_buddy_block_is_split(block)) {
			err = split_block(mm, block);
			if (unlikely(err))
				goto err_undo;
		}

		list_add(&block->right->tmp_link, &dfs);
		list_add(&block->left->tmp_link, &dfs);
	} while (1);

	return ERR_PTR(-ENOSPC);

err_undo:
	/*
	 * We really don't want to leave around a bunch of split blocks, since
	 * bigger is better, so make sure we merge everything back before we
	 * free the allocated blocks.
	 */
	buddy = __get_buddy(block);
	if (buddy &&
	    (drm_buddy_block_is_free(block) &&
	     drm_buddy_block_is_free(buddy)))
		__drm_buddy_free(mm, block);
	return ERR_PTR(err);
}

static struct drm_buddy_block *
get_maxblock(struct list_head *head)
{
	struct drm_buddy_block *max_block = NULL, *node;

	max_block = list_first_entry_or_null(head,
					     struct drm_buddy_block,
					     link);
	if (!max_block)
		return NULL;

	list_for_each_entry(node, head, link) {
		if (drm_buddy_block_offset(node) >
		    drm_buddy_block_offset(max_block))
			max_block = node;
	}

	return max_block;
}

static struct drm_buddy_block *
alloc_from_freelist(struct drm_buddy *mm,
		    unsigned int order,
		    unsigned long flags)
{
	struct drm_buddy_block *block = NULL;
	unsigned int i;
	int err;

	for (i = order; i <= mm->max_order; ++i) {
		if (flags & DRM_BUDDY_TOPDOWN_ALLOCATION) {
			block = get_maxblock(&mm->free_list[i]);
			if (block)
				break;
		} else {
			block = list_first_entry_or_null(&mm->free_list[i],
							 struct drm_buddy_block,
							 link);
			if (block)
				break;
		}
	}

	if (!block)
		return ERR_PTR(-ENOSPC);

	BUG_ON(!drm_buddy_block_is_free(block));

	while (i != order) {
		err = split_block(mm, block);
		if (unlikely(err))
			goto err_undo;

		block = block->right;
		i--;
	}
	return block;

err_undo:
	if (i != order)
		__drm_buddy_free(mm, block);
	return ERR_PTR(err);
}

static int __alloc_range(struct drm_buddy *mm,
			 struct list_head *dfs,
			 u64 start, u64 size,
			 struct list_head *blocks)
{
	struct drm_buddy_block *block;
	struct drm_buddy_block *buddy;
	LIST_HEAD(allocated);
	u64 end;
	int err;

	end = start + size - 1;

	do {
		u64 block_start;
		u64 block_end;

		block = list_first_entry_or_null(dfs,
						 struct drm_buddy_block,
						 tmp_link);
		if (!block)
			break;

		list_del(&block->tmp_link);

		block_start = drm_buddy_block_offset(block);
		block_end = block_start + drm_buddy_block_size(mm, block) - 1;

		if (!overlaps(start, end, block_start, block_end))
			continue;

		if (drm_buddy_block_is_allocated(block)) {
			err = -ENOSPC;
			goto err_free;
		}

		if (contains(start, end, block_start, block_end)) {
			if (!drm_buddy_block_is_free(block)) {
				err = -ENOSPC;
				goto err_free;
			}

			mark_allocated(block);
			mm->avail -= drm_buddy_block_size(mm, block);
			list_add_tail(&block->link, &allocated);
			continue;
		}

		if (!drm_buddy_block_is_split(block)) {
			err = split_block(mm, block);
			if (unlikely(err))
				goto err_undo;
		}

		list_add(&block->right->tmp_link, dfs);
		list_add(&block->left->tmp_link, dfs);
	} while (1);

	list_splice_tail(&allocated, blocks);
	return 0;

err_undo:
	/*
	 * We really don't want to leave around a bunch of split blocks, since
	 * bigger is better, so make sure we merge everything back before we
	 * free the allocated blocks.
	 */
	buddy = __get_buddy(block);
	if (buddy &&
	    (drm_buddy_block_is_free(block) &&
	     drm_buddy_block_is_free(buddy)))
		__drm_buddy_free(mm, block);

err_free:
	drm_buddy_free_list(mm, &allocated);
	return err;
}

static int __drm_buddy_alloc_range(struct drm_buddy *mm,
				   u64 start,
				   u64 size,
				   struct list_head *blocks)
{
	LIST_HEAD(dfs);
	int i;

	for (i = 0; i < mm->n_roots; ++i)
		list_add_tail(&mm->roots[i]->tmp_link, &dfs);

	return __alloc_range(mm, &dfs, start, size, blocks);
}

/**
 * drm_buddy_block_trim - free unused pages
 *
 * @mm: DRM buddy manager
 * @new_size: original size requested
 * @blocks: Input and output list of allocated blocks.
 * MUST contain single block as input to be trimmed.
 * On success will contain the newly allocated blocks
 * making up the @new_size. Blocks always appear in
 * ascending order
 *
 * For contiguous allocation, we round up the size to the nearest
 * power of two value, drivers consume *actual* size, so remaining
 * portions are unused and can be optionally freed with this function
 *
 * Returns:
 * 0 on success, error code on failure.
 */
int drm_buddy_block_trim(struct drm_buddy *mm,
			 u64 new_size,
			 struct list_head *blocks)
{
	struct drm_buddy_block *parent;
	struct drm_buddy_block *block;
	LIST_HEAD(dfs);
	u64 new_start;
	int err;

	if (!list_is_singular(blocks))
		return -EINVAL;

	block = list_first_entry(blocks,
				 struct drm_buddy_block,
				 link);

	if (WARN_ON(!drm_buddy_block_is_allocated(block)))
		return -EINVAL;

	if (new_size > drm_buddy_block_size(mm, block))
		return -EINVAL;

	if (!new_size || !IS_ALIGNED(new_size, mm->chunk_size))
		return -EINVAL;

	if (new_size == drm_buddy_block_size(mm, block))
		return 0;

	list_del(&block->link);
	mark_free(mm, block);
	mm->avail += drm_buddy_block_size(mm, block);

	/* Prevent recursively freeing this node */
	parent = block->parent;
	block->parent = NULL;

	new_start = drm_buddy_block_offset(block);
	list_add(&block->tmp_link, &dfs);
	err =  __alloc_range(mm, &dfs, new_start, new_size, blocks);
	if (err) {
		mark_allocated(block);
		mm->avail -= drm_buddy_block_size(mm, block);
		list_add(&block->link, blocks);
	}

	block->parent = parent;
	return err;
}
EXPORT_SYMBOL(drm_buddy_block_trim);

/**
 * drm_buddy_alloc_blocks - allocate power-of-two blocks
 *
 * @mm: DRM buddy manager to allocate from
 * @start: start of the allowed range for this block
 * @end: end of the allowed range for this block
 * @size: size of the allocation
 * @min_page_size: alignment of the allocation
 * @blocks: output list head to add allocated blocks
 * @flags: DRM_BUDDY_*_ALLOCATION flags
 *
 * alloc_range_bias() called on range limitations, which traverses
 * the tree and returns the desired block.
 *
 * alloc_from_freelist() called when *no* range restrictions
 * are enforced, which picks the block from the freelist.
 *
 * Returns:
 * 0 on success, error code on failure.
 */
int drm_buddy_alloc_blocks(struct drm_buddy *mm,
			   u64 start, u64 end, u64 size,
			   u64 min_page_size,
			   struct list_head *blocks,
			   unsigned long flags)
{
	struct drm_buddy_block *block = NULL;
	unsigned int min_order, order;
	unsigned long pages;
	LIST_HEAD(allocated);
	int err;

	if (size < mm->chunk_size)
		return -EINVAL;

	if (min_page_size < mm->chunk_size)
		return -EINVAL;

	if (!is_power_of_2(min_page_size))
		return -EINVAL;

	if (!IS_ALIGNED(start | end | size, mm->chunk_size))
		return -EINVAL;

	if (end > mm->size)
		return -EINVAL;

	if (range_overflows(start, size, mm->size))
		return -EINVAL;

	/* Actual range allocation */
	if (start + size == end)
		return __drm_buddy_alloc_range(mm, start, size, blocks);

	pages = size >> ilog2(mm->chunk_size);
	order = fls(pages) - 1;
	min_order = ilog2(min_page_size) - ilog2(mm->chunk_size);

	do {
		order = min(order, (unsigned int)fls(pages) - 1);
		BUG_ON(order > mm->max_order);
		BUG_ON(order < min_order);

		do {
			if (flags & DRM_BUDDY_RANGE_ALLOCATION)
				/* Allocate traversing within the range */
				block = alloc_range_bias(mm, start, end, order);
			else
				/* Allocate from freelist */
				block = alloc_from_freelist(mm, order, flags);

			if (!IS_ERR(block))
				break;

			if (order-- == min_order) {
				err = -ENOSPC;
				goto err_free;
			}
		} while (1);

		mark_allocated(block);
		mm->avail -= drm_buddy_block_size(mm, block);
		kmemleak_update_trace(block);
		list_add_tail(&block->link, &allocated);

		pages -= BIT(order);

		if (!pages)
			break;
	} while (1);

	list_splice_tail(&allocated, blocks);
	return 0;

err_free:
	drm_buddy_free_list(mm, &allocated);
	return err;
}
EXPORT_SYMBOL(drm_buddy_alloc_blocks);

/**
 * drm_buddy_block_print - print block information
 *
 * @mm: DRM buddy manager
 * @block: DRM buddy block
 * @p: DRM printer to use
 */
void drm_buddy_block_print(struct drm_buddy *mm,
			   struct drm_buddy_block *block,
			   struct drm_printer *p)
{
	u64 start = drm_buddy_block_offset(block);
	u64 size = drm_buddy_block_size(mm, block);

	drm_printf(p, "%#018llx-%#018llx: %llu\n", start, start + size, size);
}
EXPORT_SYMBOL(drm_buddy_block_print);

/**
 * drm_buddy_print - print allocator state
 *
 * @mm: DRM buddy manager
 * @p: DRM printer to use
 */
void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p)
{
	int order;

	drm_printf(p, "chunk_size: %lluKiB, total: %lluMiB, free: %lluMiB\n",
		   mm->chunk_size >> 10, mm->size >> 20, mm->avail >> 20);

	for (order = mm->max_order; order >= 0; order--) {
		struct drm_buddy_block *block;
		u64 count = 0, free;

		list_for_each_entry(block, &mm->free_list[order], link) {
			BUG_ON(!drm_buddy_block_is_free(block));
			count++;
		}

		drm_printf(p, "order-%d ", order);

		free = count * (mm->chunk_size << order);
		if (free < SZ_1M)
			drm_printf(p, "free: %lluKiB", free >> 10);
		else
			drm_printf(p, "free: %lluMiB", free >> 20);

		drm_printf(p, ", pages: %llu\n", count);
	}
}
EXPORT_SYMBOL(drm_buddy_print);

static void drm_buddy_module_exit(void)
{
	kmem_cache_destroy(slab_blocks);
}

static int __init drm_buddy_module_init(void)
{
	slab_blocks = KMEM_CACHE(drm_buddy_block, 0);
	if (!slab_blocks)
		return -ENOMEM;

	return 0;
}

module_init(drm_buddy_module_init);
module_exit(drm_buddy_module_exit);

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