path: root/drivers/gpu/drm/drm_buddy.c

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

#include <kunit/test-bug.h>

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

#include <drm/drm_buddy.h>
#include <drm/drm_print.h>

enum drm_buddy_free_tree {
	DRM_BUDDY_CLEAR_TREE = 0,
	DRM_BUDDY_DIRTY_TREE,
	DRM_BUDDY_MAX_FREE_TREES,
};

static struct kmem_cache *slab_blocks;

#define for_each_free_tree(tree) \
	for ((tree) = 0; (tree) < DRM_BUDDY_MAX_FREE_TREES; (tree)++)

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;

	RB_CLEAR_NODE(&block->rb);

	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 enum drm_buddy_free_tree
get_block_tree(struct drm_buddy_block *block)
{
	return drm_buddy_block_is_clear(block) ?
	       DRM_BUDDY_CLEAR_TREE : DRM_BUDDY_DIRTY_TREE;
}

static struct drm_buddy_block *
rbtree_get_free_block(const struct rb_node *node)
{
	return node ? rb_entry(node, struct drm_buddy_block, rb) : NULL;
}

static struct drm_buddy_block *
rbtree_last_free_block(struct rb_root *root)
{
	return rbtree_get_free_block(rb_last(root));
}

static bool rbtree_is_empty(struct rb_root *root)
{
	return RB_EMPTY_ROOT(root);
}

static bool drm_buddy_block_offset_less(const struct drm_buddy_block *block,
					const struct drm_buddy_block *