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