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
32 struct 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 */
69 struct 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
96 static inline u64
drm_buddy_block_offset(struct drm_buddy_block * block)97 drm_buddy_block_offset(struct drm_buddy_block *block)
98 {
99 return block->header & DRM_BUDDY_HEADER_OFFSET;
100 }
101
102 static inline unsigned int
drm_buddy_block_order(struct drm_buddy_block * block)103 drm_buddy_block_order(struct drm_buddy_block *block)
104 {
105 return block->header & DRM_BUDDY_HEADER_ORDER;
106 }
107
108 static inline unsigned int
drm_buddy_block_state(struct drm_buddy_block * block)109 drm_buddy_block_state(struct drm_buddy_block *block)
110 {
111 return block->header & DRM_BUDDY_HEADER_STATE;
112 }
113
114 static inline bool
drm_buddy_block_is_allocated(struct drm_buddy_block * block)115 drm_buddy_block_is_allocated(struct drm_buddy_block *block)
116 {
117 return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED;
118 }
119
120 static inline bool
drm_buddy_block_is_clear(struct drm_buddy_block * block)121 drm_buddy_block_is_clear(struct drm_buddy_block *block)
122 {
123 return block->header & DRM_BUDDY_HEADER_CLEAR;
124 }
125
126 static inline bool
drm_buddy_block_is_free(struct drm_buddy_block * block)127 drm_buddy_block_is_free(struct drm_buddy_block *block)
128 {
129 return drm_buddy_block_state(block) == DRM_BUDDY_FREE;
130 }
131
132 static inline bool
drm_buddy_block_is_split(struct drm_buddy_block * block)133 drm_buddy_block_is_split(struct drm_buddy_block *block)
134 {
135 return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT;
136 }
137
138 static inline u64
drm_buddy_block_size(struct drm_buddy * mm,struct drm_buddy_block * block)139 drm_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
145 int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size);
146
147 void drm_buddy_fini(struct drm_buddy *mm);
148
149 struct drm_buddy_block *
150 drm_get_buddy(struct drm_buddy_block *block);
151
152 int 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
158 int drm_buddy_block_trim(struct drm_buddy *mm,
159 u64 *start,
160 u64 new_size,
161 struct list_head *blocks);
162
163 void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block);
164
165 void drm_buddy_free_list(struct drm_buddy *mm,
166 struct list_head *objects,
167 unsigned int flags);
168
169 void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p);
170 void drm_buddy_block_print(struct drm_buddy *mm,
171 struct drm_buddy_block *block,
172 struct drm_printer *p);
173 #endif
174