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 | |
29 | struct drm_buddy_block { |
30 | #define GENMASK_ULL(63, 12) |
31 | #define GENMASK_ULL(11, 10) |
32 | #define DRM_BUDDY_ALLOCATED (1 << 10) |
33 | #define DRM_BUDDY_FREE (2 << 10) |
34 | #define DRM_BUDDY_SPLIT (3 << 10) |
35 | /* Free to be used, if needed in the future */ |
36 | #define GENMASK_ULL(9, 6) |
37 | #define GENMASK_ULL(5, 0) |
38 | u64 ; |
39 | |
40 | struct drm_buddy_block *left; |
41 | struct drm_buddy_block *right; |
42 | struct drm_buddy_block *parent; |
43 | |
44 | void *private; /* owned by creator */ |
45 | |
46 | /* |
47 | * While the block is allocated by the user through drm_buddy_alloc*, |
48 | * the user has ownership of the link, for example to maintain within |
49 | * a list, if so desired. As soon as the block is freed with |
50 | * drm_buddy_free* ownership is given back to the mm. |
51 | */ |
52 | struct list_head link; |
53 | struct list_head tmp_link; |
54 | }; |
55 | |
56 | /* Order-zero must be at least PAGE_SIZE */ |
57 | #define DRM_BUDDY_MAX_ORDER (63 - PAGE_SHIFT) |
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 list_head *free_list; |
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 PAGE_SIZE */ |
86 | u64 chunk_size; |
87 | u64 size; |
88 | u64 avail; |
89 | }; |
90 | |
91 | static inline u64 |
92 | drm_buddy_block_offset(struct drm_buddy_block *block) |
93 | { |
94 | return block->header & DRM_BUDDY_HEADER_OFFSET; |
95 | } |
96 | |
97 | static inline unsigned int |
98 | drm_buddy_block_order(struct drm_buddy_block *block) |
99 | { |
100 | return block->header & DRM_BUDDY_HEADER_ORDER; |
101 | } |
102 | |
103 | static inline unsigned int |
104 | drm_buddy_block_state(struct drm_buddy_block *block) |
105 | { |
106 | return block->header & DRM_BUDDY_HEADER_STATE; |
107 | } |
108 | |
109 | static inline bool |
110 | drm_buddy_block_is_allocated(struct drm_buddy_block *block) |
111 | { |
112 | return drm_buddy_block_state(block) == DRM_BUDDY_ALLOCATED; |
113 | } |
114 | |
115 | static inline bool |
116 | drm_buddy_block_is_free(struct drm_buddy_block *block) |
117 | { |
118 | return drm_buddy_block_state(block) == DRM_BUDDY_FREE; |
119 | } |
120 | |
121 | static inline bool |
122 | drm_buddy_block_is_split(struct drm_buddy_block *block) |
123 | { |
124 | return drm_buddy_block_state(block) == DRM_BUDDY_SPLIT; |
125 | } |
126 | |
127 | static inline u64 |
128 | drm_buddy_block_size(struct drm_buddy *mm, |
129 | struct drm_buddy_block *block) |
130 | { |
131 | return mm->chunk_size << drm_buddy_block_order(block); |
132 | } |
133 | |
134 | int drm_buddy_init(struct drm_buddy *mm, u64 size, u64 chunk_size); |
135 | |
136 | void drm_buddy_fini(struct drm_buddy *mm); |
137 | |
138 | struct drm_buddy_block * |
139 | drm_get_buddy(struct drm_buddy_block *block); |
140 | |
141 | int drm_buddy_alloc_blocks(struct drm_buddy *mm, |
142 | u64 start, u64 end, u64 size, |
143 | u64 min_page_size, |
144 | struct list_head *blocks, |
145 | unsigned long flags); |
146 | |
147 | int drm_buddy_block_trim(struct drm_buddy *mm, |
148 | u64 new_size, |
149 | struct list_head *blocks); |
150 | |
151 | void drm_buddy_free_block(struct drm_buddy *mm, struct drm_buddy_block *block); |
152 | |
153 | void drm_buddy_free_list(struct drm_buddy *mm, struct list_head *objects); |
154 | |
155 | void drm_buddy_print(struct drm_buddy *mm, struct drm_printer *p); |
156 | void drm_buddy_block_print(struct drm_buddy *mm, |
157 | struct drm_buddy_block *block, |
158 | struct drm_printer *p); |
159 | #endif |
160 | |