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