drivers/gpu/drm/i915/i915_buddy.c - linux - Git at Google

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

 #include <linux/kmemleak.h>
 #include <linux/slab.h>

 #include "i915_buddy.h"

 #include "i915_gem.h"
 #include "i915_globals.h"
 #include "i915_utils.h"

 static struct i915_global_block {
 	struct i915_global base;
 	struct kmem_cache *slab_blocks;
 } global;

 static void i915_global_buddy_shrink(void)
 {
 	kmem_cache_shrink(global.slab_blocks);
 }

 static void i915_global_buddy_exit(void)
 {
 	kmem_cache_destroy(global.slab_blocks);
 }

 static struct i915_global_block global = { {
 	.shrink = i915_global_buddy_shrink,
 	.exit = i915_global_buddy_exit,
 } };

 int __init i915_global_buddy_init(void)
 {
 	global.slab_blocks = KMEM_CACHE(i915_buddy_block, SLAB_HWCACHE_ALIGN);
 	if (!global.slab_blocks)
 		return -ENOMEM;

 	i915_global_register(&global.base);
 	return 0;
 }

 static struct i915_buddy_block *i915_block_alloc(struct i915_buddy_block *parent,
 						 unsigned int order,
 						 u64 offset)
 {
 	struct i915_buddy_block *block;

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

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

 	return block;
 }

 static void i915_block_free(struct i915_buddy_block *block)
 {
 	kmem_cache_free(global.slab_blocks, block);
 }

 static void mark_allocated(struct i915_buddy_block *block)
 {
 	block->header &= ~I915_BUDDY_HEADER_STATE;
 	block->header |= I915_BUDDY_ALLOCATED;

 	list_del(&block->link);
 }

 static void mark_free(struct i915_buddy_mm *mm,
 		      struct i915_buddy_block *block)
 {
 	block->header &= ~I915_BUDDY_HEADER_STATE;
 	block->header |= I915_BUDDY_FREE;

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

 static void mark_split(struct i915_buddy_block *block)
 {
 	block->header &= ~I915_BUDDY_HEADER_STATE;
 	block->header |= I915_BUDDY_SPLIT;

 	list_del(&block->link);
 }

 int i915_buddy_init(struct i915_buddy_mm *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->chunk_size = chunk_size;
 	mm->max_order = ilog2(size) - ilog2(chunk_size);

 	GEM_BUG_ON(mm->max_order > I915_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 i915_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 i915_buddy_block *root;
 		unsigned int order;
 		u64 root_size;

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

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

 		mark_free(mm, root);

 		GEM_BUG_ON(i > mm->max_order);
 		GEM_BUG_ON(i915_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--)
 		i915_block_free(mm->roots[i]);
 	kfree(mm->roots);
 out_free_list:
 	kfree(mm->free_list);
 	return -ENOMEM;
 }

 void i915_buddy_fini(struct i915_buddy_mm *mm)
 {
 	int i;

 	for (i = 0; i < mm->n_roots; ++i) {
 		GEM_WARN_ON(!i915_buddy_block_is_free(mm->roots[i]));
 		i915_block_free(mm->roots[i]);
 	}

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

 static int split_block(struct i915_buddy_mm *mm,
 		       struct i915_buddy_block *block)
 {
 	unsigned int block_order = i915_buddy_block_order(block) - 1;
 	u64 offset = i915_buddy_block_offset(block);

 	GEM_BUG_ON(!i915_buddy_block_is_free(block));
 	GEM_BUG_ON(!i915_buddy_block_order(block));

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

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

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

 	mark_split(block);

 	return 0;
 }

 static struct i915_buddy_block *
 get_buddy(struct i915_buddy_block *block)
 {
 	struct i915_buddy_block *parent;

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

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

 	return parent->left;
 }

 static void __i915_buddy_free(struct i915_buddy_mm *mm,
 			      struct i915_buddy_block *block)
 {
 	struct i915_buddy_block *parent;

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

 		buddy = get_buddy(block);

 		if (!i915_buddy_block_is_free(buddy))
 			break;

 		list_del(&buddy->link);

 		i915_block_free(block);
 		i915_block_free(buddy);

 		block = parent;
 	}

 	mark_free(mm, block);
 }

 void i915_buddy_free(struct i915_buddy_mm *mm,
 		     struct i915_buddy_block *block)
 {
 	GEM_BUG_ON(!i915_buddy_block_is_allocated(block));
 	__i915_buddy_free(mm, block);
 }

 void i915_buddy_free_list(struct i915_buddy_mm *mm, struct list_head *objects)
 {
 	struct i915_buddy_block *block, *on;

 	list_for_each_entry_safe(block, on, objects, link) {
 		i915_buddy_free(mm, block);
 		cond_resched();
 	}
 	INIT_LIST_HEAD(objects);
 }

 /*
  * Allocate power-of-two block. The order value here translates to:
  *
  *   0 = 2^0 * mm->chunk_size
  *   1 = 2^1 * mm->chunk_size
  *   2 = 2^2 * mm->chunk_size
  *   ...
  */
 struct i915_buddy_block *
 i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order)
 {
 	struct i915_buddy_block *block = NULL;
 	unsigned int i;
 	int err;

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

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

 	GEM_BUG_ON(!i915_buddy_block_is_free(block));

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

 		/* Go low */
 		block = block->left;
 		i--;
 	}

 	mark_allocated(block);
 	kmemleak_update_trace(block);
 	return block;

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

 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;
 }

 /*
  * Allocate range. Note that it's safe to chain together multiple alloc_ranges
  * with the same blocks list.
  *
  * Intended for pre-allocating portions of the address space, for example to
  * reserve a block for the initial framebuffer or similar, hence the expectation
  * here is that i915_buddy_alloc() is still the main vehicle for
  * allocations, so if that's not the case then the drm_mm range allocator is
  * probably a much better fit, and so you should probably go use that instead.
  */
 int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
 			   struct list_head *blocks,
 			   u64 start, u64 size)
 {
 	struct i915_buddy_block *block;
 	struct i915_buddy_block *buddy;
 	LIST_HEAD(allocated);
 	LIST_HEAD(dfs);
 	u64 end;
 	int err;
 	int i;

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

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

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

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

 	end = start + size - 1;

 	do {
 		u64 block_start;
 		u64 block_end;

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

 		list_del(&block->tmp_link);

 		block_start = i915_buddy_block_offset(block);
 		block_end = block_start + i915_buddy_block_size(mm, block) - 1;

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

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

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

 			mark_allocated(block);
 			list_add_tail(&block->link, &allocated);
 			continue;
 		}

 		if (!i915_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 &&
 	    (i915_buddy_block_is_free(block) &&
 	     i915_buddy_block_is_free(buddy)))
 		__i915_buddy_free(mm, block);

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

 #if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
 #include "selftests/i915_buddy.c"
 #endif
	// SPDX-License-Identifier: MIT
	/*
	* Copyright © 2019 Intel Corporation
	*/

	#include <linux/kmemleak.h>
	#include <linux/slab.h>

	#include "i915_buddy.h"

	#include "i915_gem.h"
	#include "i915_globals.h"
	#include "i915_utils.h"

	static struct i915_global_block {
	struct i915_global base;
	struct kmem_cache *slab_blocks;
	} global;

	static void i915_global_buddy_shrink(void)
	{
	kmem_cache_shrink(global.slab_blocks);
	}

	static void i915_global_buddy_exit(void)
	{
	kmem_cache_destroy(global.slab_blocks);
	}

	static struct i915_global_block global = { {
	.shrink = i915_global_buddy_shrink,
	.exit = i915_global_buddy_exit,
	} };

	int __init i915_global_buddy_init(void)
	{
	global.slab_blocks = KMEM_CACHE(i915_buddy_block, SLAB_HWCACHE_ALIGN);
	if (!global.slab_blocks)
	return -ENOMEM;

	i915_global_register(&global.base);
	return 0;
	}

	static struct i915_buddy_block i915_block_alloc(struct i915_buddy_block parent,
	unsigned int order,
	u64 offset)
	{
	struct i915_buddy_block *block;

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

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

	return block;
	}

	static void i915_block_free(struct i915_buddy_block *block)
	{
	kmem_cache_free(global.slab_blocks, block);
	}

	static void mark_allocated(struct i915_buddy_block *block)
	{
	block->header &= ~I915_BUDDY_HEADER_STATE;
	block->header \|= I915_BUDDY_ALLOCATED;

	list_del(&block->link);
	}

	static void mark_free(struct i915_buddy_mm *mm,
	struct i915_buddy_block *block)
	{
	block->header &= ~I915_BUDDY_HEADER_STATE;
	block->header \|= I915_BUDDY_FREE;

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

	static void mark_split(struct i915_buddy_block *block)
	{
	block->header &= ~I915_BUDDY_HEADER_STATE;
	block->header \|= I915_BUDDY_SPLIT;

	list_del(&block->link);
	}

	int i915_buddy_init(struct i915_buddy_mm *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->chunk_size = chunk_size;
	mm->max_order = ilog2(size) - ilog2(chunk_size);

	GEM_BUG_ON(mm->max_order > I915_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 i915_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 i915_buddy_block *root;
	unsigned int order;
	u64 root_size;

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

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

	mark_free(mm, root);

	GEM_BUG_ON(i > mm->max_order);
	GEM_BUG_ON(i915_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--)
	i915_block_free(mm->roots[i]);
	kfree(mm->roots);
	out_free_list:
	kfree(mm->free_list);
	return -ENOMEM;
	}

	void i915_buddy_fini(struct i915_buddy_mm *mm)
	{
	int i;

	for (i = 0; i < mm->n_roots; ++i) {
	GEM_WARN_ON(!i915_buddy_block_is_free(mm->roots[i]));
	i915_block_free(mm->roots[i]);
	}

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

	static int split_block(struct i915_buddy_mm *mm,
	struct i915_buddy_block *block)
	{
	unsigned int block_order = i915_buddy_block_order(block) - 1;
	u64 offset = i915_buddy_block_offset(block);

	GEM_BUG_ON(!i915_buddy_block_is_free(block));
	GEM_BUG_ON(!i915_buddy_block_order(block));

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

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

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

	mark_split(block);

	return 0;
	}

	static struct i915_buddy_block *
	get_buddy(struct i915_buddy_block *block)
	{
	struct i915_buddy_block *parent;

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

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

	return parent->left;
	}

	static void __i915_buddy_free(struct i915_buddy_mm *mm,
	struct i915_buddy_block *block)
	{
	struct i915_buddy_block *parent;

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

	buddy = get_buddy(block);

	if (!i915_buddy_block_is_free(buddy))
	break;

	list_del(&buddy->link);

	i915_block_free(block);
	i915_block_free(buddy);

	block = parent;
	}

	mark_free(mm, block);
	}

	void i915_buddy_free(struct i915_buddy_mm *mm,
	struct i915_buddy_block *block)
	{
	GEM_BUG_ON(!i915_buddy_block_is_allocated(block));
	__i915_buddy_free(mm, block);
	}

	void i915_buddy_free_list(struct i915_buddy_mm mm, struct list_head objects)
	{
	struct i915_buddy_block block, on;

	list_for_each_entry_safe(block, on, objects, link) {
	i915_buddy_free(mm, block);
	cond_resched();
	}
	INIT_LIST_HEAD(objects);
	}

	/*
	* Allocate power-of-two block. The order value here translates to:
	*
	* 0 = 2^0 * mm->chunk_size
	* 1 = 2^1 * mm->chunk_size
	* 2 = 2^2 * mm->chunk_size
	* ...
	*/
	struct i915_buddy_block *
	i915_buddy_alloc(struct i915_buddy_mm *mm, unsigned int order)
	{
	struct i915_buddy_block *block = NULL;
	unsigned int i;
	int err;

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

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

	GEM_BUG_ON(!i915_buddy_block_is_free(block));

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

	/* Go low */
	block = block->left;
	i--;
	}

	mark_allocated(block);
	kmemleak_update_trace(block);
	return block;

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

	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;
	}

	/*
	* Allocate range. Note that it's safe to chain together multiple alloc_ranges
	* with the same blocks list.
	*
	* Intended for pre-allocating portions of the address space, for example to
	* reserve a block for the initial framebuffer or similar, hence the expectation
	* here is that i915_buddy_alloc() is still the main vehicle for
	* allocations, so if that's not the case then the drm_mm range allocator is
	* probably a much better fit, and so you should probably go use that instead.
	*/
	int i915_buddy_alloc_range(struct i915_buddy_mm *mm,
	struct list_head *blocks,
	u64 start, u64 size)
	{
	struct i915_buddy_block *block;
	struct i915_buddy_block *buddy;
	LIST_HEAD(allocated);
	LIST_HEAD(dfs);
	u64 end;
	int err;
	int i;

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

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

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

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

	end = start + size - 1;

	do {
	u64 block_start;
	u64 block_end;

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

	list_del(&block->tmp_link);

	block_start = i915_buddy_block_offset(block);
	block_end = block_start + i915_buddy_block_size(mm, block) - 1;

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

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

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

	mark_allocated(block);
	list_add_tail(&block->link, &allocated);
	continue;
	}

	if (!i915_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 &&
	(i915_buddy_block_is_free(block) &&
	i915_buddy_block_is_free(buddy)))
	__i915_buddy_free(mm, block);

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

	#if IS_ENABLED(CONFIG_DRM_I915_SELFTEST)
	#include "selftests/i915_buddy.c"
	#endif