[linux-block.git] / include / drm / drm_buddy.h

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

#ifndef __DRM_BUDDY_H__
#define __DRM_BUDDY_H__

#include <linux/bitops.h>
#include <linux/list.h>
#include <linux/slab.h>
#include <linux/sched.h>

#include <drm/drm_print.h>

#define range_overflows(start, size, max) ({ \
	typeof(start) start__ = (start); \
	typeof(size) size__ = (size); \
	typeof(max) max__ = (max); \
	(void)(&start__ == &size__); \
	(void)(&start__ == &max__); \
	start__ >= max__ || size__ > max__ - start__; \
})

#define DRM_BUDDY_RANGE_ALLOCATION (1 << 0)
#define DRM_BUDDY_TOPDOWN_ALLOCATION (1 << 1)

struct drm_buddy_block {
#define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
#define DRM_BUDDY_HEADER_STATE  GENMASK_ULL(11, 10)
#define   DRM_BUDDY_ALLOCATED	   (1 << 10)
#define   DRM_BUDDY_FREE	   (2 << 10)
#define   DRM_BUDDY_SPLIT	   (3 << 10)
/* Free to be used, if needed in the future */
#define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6)
#define DRM_BUDDY_HEADER_ORDER  GENMASK_ULL(5, 0)
	u64 header;

	struct drm_buddy_block *left;
	struct drm_buddy_block *right;
	struct drm_buddy_block *parent;

	void *private; /* owned by creator */

	/*
	 * While the block is allocated by the user through drm_buddy_alloc*,
	 * the user has ownership of the link, for example to maintain within
	 * a list, if so desired. As soon as the block is freed with
	 * drm_buddy_free* ownership is given back to the mm.
	 */
	struct list_head link;
	struct list_head tmp_link;
};

/* Order-zero must be at least PAGE_SIZE */
#define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT)

/*
 * Binary Buddy System.
 *
 * Locking should be handled by the user, a simple mutex around
 * drm_buddy_alloc* and drm_buddy_free* should suffice.
 */
struct drm_buddy {
	/* Maintain a free list for each order. */
	struct list_head *free_list;

	/*
	 * Maintain explicit binary tree(s) to track the allocation of the
	 * address space. This gives us a simple way of finding a buddy block
	 * and performing the potentially recursive merge step when freeing a
	 * block.  Nodes are either allocated or free, in which case they will
	 * also exist on the respective free list.
	 */
	struct drm_buddy_block **roots;

	/*
	 * Anything from here is public, and remains static for the lifetime of
	 * the mm. Everything above is considered do-not-touch.
	 */
	unsigned int n_roots;
	unsigned int max_order;

	/* Must be at least PAGE_SIZE */
	u64 chunk_size;
	u64 size;
	u64 avail;
};

static inline u64
drm_buddy_block_offset(struct drm_buddy_block *block)
{
	return block->header & DRM_BUDDY_HEADER_OFFSET;
}

static inline unsigned int
drm_buddy_block_order(struct drm_buddy_block *block)
{
	return block->header & DRM_BUDDY_HEADER_ORDER;
}

static inline unsigned int
drm_buddy_block_state(struct drm_buddy_block *block)
{
	return block->header & DRM_BUDDY_HEADER_STATE;
}

static inline bool
drm_buddy_block_is_allocated(struct drm_buddy_block *block)
{
	return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
}

static inline bool
drm_buddy_block_is_free(struct drm_buddy_block *block)
{
	return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
}

static inline bool
drm_buddy_block_is_split(struct drm_buddy_block *block)
{
	return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
}

static inline u64
drm_buddy_block_size(struct drm_buddy *mm,
		     struct drm_buddy_block *block)
{
	return mm->chunk_size << drm_buddy_block_order(block);
}

int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);

void drm_buddy_fini(struct drm_buddy *mm);

struct drm_buddy_block *
drm_get_buddy(struct drm_buddy_block *block);

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

int drm_buddy_block_trim(struct drm_buddy *mm,
			 u64 new_size,
			 struct list_head *blocks);

void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);

void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects);

void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
void drm_buddy_block_print(struct drm_buddy *mm,
			   struct drm_buddy_block *block,
			   struct drm_printer *p);

#endif
Commit	Line	Data
6387a3c4 A	1	/* SPDX-License-Identifier: MIT */
	2	/*
	3	* Copyright © 2021 Intel Corporation
	4	*/
	5
	6	#ifndef __DRM_BUDDY_H__
	7	#define __DRM_BUDDY_H__
	8
	9	#include <linux/bitops.h>
	10	#include <linux/list.h>
	11	#include <linux/slab.h>
	12	#include <linux/sched.h>
	13
	14	#include <drm/drm_print.h>
	15
	16	#define range_overflows(start, size, max) ({ \
	17	typeof(start) start__ = (start); \
	18	typeof(size) size__ = (size); \
	19	typeof(max) max__ = (max); \
	20	(void)(&start__ == &size__); \
	21	(void)(&start__ == &max__); \
	22	start__ >= max__ \|\| size__ > max__ - start__; \
	23	})
	24
afea229f	25	#define DRM_BUDDY_RANGE_ALLOCATION (1 << 0)
476e4063	26	#define DRM_BUDDY_TOPDOWN_ALLOCATION (1 << 1)
afea229f	27
6387a3c4 A	28	struct drm_buddy_block {
	29	#define DRM_BUDDY_HEADER_OFFSET GENMASK_ULL(63, 12)
	30	#define DRM_BUDDY_HEADER_STATE GENMASK_ULL(11, 10)
	31	#define DRM_BUDDY_ALLOCATED (1 << 10)
	32	#define DRM_BUDDY_FREE (2 << 10)
	33	#define DRM_BUDDY_SPLIT (3 << 10)
	34	/* Free to be used, if needed in the future */
	35	#define DRM_BUDDY_HEADER_UNUSED GENMASK_ULL(9, 6)
	36	#define DRM_BUDDY_HEADER_ORDER GENMASK_ULL(5, 0)
	37	u64 header;
	38
	39	struct drm_buddy_block *left;
	40	struct drm_buddy_block *right;
	41	struct drm_buddy_block *parent;
	42
	43	void private; / owned by creator */
	44
	45	/*
	46	* While the block is allocated by the user through drm_buddy_alloc*,
	47	* the user has ownership of the link, for example to maintain within
	48	* a list, if so desired. As soon as the block is freed with
	49	* drm_buddy_free* ownership is given back to the mm.
	50	*/
	51	struct list_head link;
	52	struct list_head tmp_link;
	53	};
	54
	55	/* Order-zero must be at least PAGE_SIZE */
	56	#define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT)
	57
	58	/*
	59	* Binary Buddy System.
	60	*
	61	* Locking should be handled by the user, a simple mutex around
	62	* drm_buddy_alloc* and drm_buddy_free* should suffice.
	63	*/
	64	struct drm_buddy {
	65	/* Maintain a free list for each order. */
	66	struct list_head *free_list;
	67
	68	/*
	69	* Maintain explicit binary tree(s) to track the allocation of the
	70	* address space. This gives us a simple way of finding a buddy block
	71	* and performing the potentially recursive merge step when freeing a
	72	* block. Nodes are either allocated or free, in which case they will
	73	* also exist on the respective free list.
	74	*/
	75	struct drm_buddy_block **roots;
	76
	77	/*
	78	* Anything from here is public, and remains static for the lifetime of
	79	* the mm. Everything above is considered do-not-touch.
	80	*/
	81	unsigned int n_roots;
	82	unsigned int max_order;
	83
	84	/* Must be at least PAGE_SIZE */
	85	u64 chunk_size;
	86	u64 size;
	87	u64 avail;
	88	};
	89
	90	static inline u64
	91	drm_buddy_block_offset(struct drm_buddy_block *block)
92	{
93	return block->header & DRM_BUDDY_HEADER_OFFSET;
94	}
95
96	static inline unsigned int
97	drm_buddy_block_order(struct drm_buddy_block *block)
98	{
99	return block->header & DRM_BUDDY_HEADER_ORDER;
100	}
101
102	static inline unsigned int
103	drm_buddy_block_state(struct drm_buddy_block *block)
104	{
105	return block->header & DRM_BUDDY_HEADER_STATE;
106	}
107
108	static inline bool
109	drm_buddy_block_is_allocated(struct drm_buddy_block *block)
110	{
111	return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
112	}
113
114	static inline bool
115	drm_buddy_block_is_free(struct drm_buddy_block *block)
116	{
117	return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
118	}
119
120	static inline bool
121	drm_buddy_block_is_split(struct drm_buddy_block *block)
122	{
123	return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
124	}
125
126	static inline u64
127	drm_buddy_block_size(struct drm_buddy *mm,
128	struct drm_buddy_block *block)
129	{
130	return mm->chunk_size << drm_buddy_block_order(block);
131	}
132
133	int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
134
135	void drm_buddy_fini(struct drm_buddy *mm);
136
92937f17 A	137	struct drm_buddy_block *
	138	drm_get_buddy(struct drm_buddy_block *block);
	139
afea229f A	140	int drm_buddy_alloc_blocks(struct drm_buddy *mm,
	141	u64 start, u64 end, u64 size,
	142	u64 min_page_size,
	143	struct list_head *blocks,
	144	unsigned long flags);
6387a3c4	145
95ee2a8b A	146	int drm_buddy_block_trim(struct drm_buddy *mm,
	147	u64 new_size,
	148	struct list_head *blocks);
	149
6387a3c4 A	150	void drm_buddy_free_block(struct drm_buddy mm, struct drm_buddy_block block);
	151
	152	void drm_buddy_free_list(struct drm_buddy mm, struct list_head objects);
	153
	154	void drm_buddy_print(struct drm_buddy mm, struct drm_printer p);
	155	void drm_buddy_block_print(struct drm_buddy *mm,
	156	struct drm_buddy_block *block,
	157	struct drm_printer *p);
	158
	159	#endif