| @@ -1,1125 +1,1130 @@ | | | @@ -1,1125 +1,1130 @@ |
1 | /* $NetBSD: drm_mm.c,v 1.14 2021/12/19 11:51:32 riastradh Exp $ */ | | 1 | /* $NetBSD: drm_mm.c,v 1.15 2022/02/14 13:02:31 riastradh Exp $ */ |
2 | | | 2 | |
3 | /************************************************************************** | | 3 | /************************************************************************** |
4 | * | | 4 | * |
5 | * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. | | 5 | * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. |
6 | * Copyright 2016 Intel Corporation | | 6 | * Copyright 2016 Intel Corporation |
7 | * All Rights Reserved. | | 7 | * All Rights Reserved. |
8 | * | | 8 | * |
9 | * Permission is hereby granted, free of charge, to any person obtaining a | | 9 | * Permission is hereby granted, free of charge, to any person obtaining a |
10 | * copy of this software and associated documentation files (the | | 10 | * copy of this software and associated documentation files (the |
11 | * "Software"), to deal in the Software without restriction, including | | 11 | * "Software"), to deal in the Software without restriction, including |
12 | * without limitation the rights to use, copy, modify, merge, publish, | | 12 | * without limitation the rights to use, copy, modify, merge, publish, |
13 | * distribute, sub license, and/or sell copies of the Software, and to | | 13 | * distribute, sub license, and/or sell copies of the Software, and to |
14 | * permit persons to whom the Software is furnished to do so, subject to | | 14 | * permit persons to whom the Software is furnished to do so, subject to |
15 | * the following conditions: | | 15 | * the following conditions: |
16 | * | | 16 | * |
17 | * The above copyright notice and this permission notice (including the | | 17 | * The above copyright notice and this permission notice (including the |
18 | * next paragraph) shall be included in all copies or substantial portions | | 18 | * next paragraph) shall be included in all copies or substantial portions |
19 | * of the Software. | | 19 | * of the Software. |
20 | * | | 20 | * |
21 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | | 21 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
22 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | | 22 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
23 | * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL | | 23 | * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL |
24 | * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, | | 24 | * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, |
25 | * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR | | 25 | * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR |
26 | * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE | | 26 | * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE |
27 | * USE OR OTHER DEALINGS IN THE SOFTWARE. | | 27 | * USE OR OTHER DEALINGS IN THE SOFTWARE. |
28 | * | | 28 | * |
29 | * | | 29 | * |
30 | **************************************************************************/ | | 30 | **************************************************************************/ |
31 | | | 31 | |
32 | /* | | 32 | /* |
33 | * Generic simple memory manager implementation. Intended to be used as a base | | 33 | * Generic simple memory manager implementation. Intended to be used as a base |
34 | * class implementation for more advanced memory managers. | | 34 | * class implementation for more advanced memory managers. |
35 | * | | 35 | * |
36 | * Note that the algorithm used is quite simple and there might be substantial | | 36 | * Note that the algorithm used is quite simple and there might be substantial |
37 | * performance gains if a smarter free list is implemented. Currently it is | | 37 | * performance gains if a smarter free list is implemented. Currently it is |
38 | * just an unordered stack of free regions. This could easily be improved if | | 38 | * just an unordered stack of free regions. This could easily be improved if |
39 | * an RB-tree is used instead. At least if we expect heavy fragmentation. | | 39 | * an RB-tree is used instead. At least if we expect heavy fragmentation. |
40 | * | | 40 | * |
41 | * Aligned allocations can also see improvement. | | 41 | * Aligned allocations can also see improvement. |
42 | * | | 42 | * |
43 | * Authors: | | 43 | * Authors: |
44 | * Thomas Hellström <thomas-at-tungstengraphics-dot-com> | | 44 | * Thomas Hellström <thomas-at-tungstengraphics-dot-com> |
45 | */ | | 45 | */ |
46 | | | 46 | |
47 | #include <sys/cdefs.h> | | 47 | #include <sys/cdefs.h> |
48 | __KERNEL_RCSID(0, "$NetBSD: drm_mm.c,v 1.14 2021/12/19 11:51:32 riastradh Exp $"); | | 48 | __KERNEL_RCSID(0, "$NetBSD: drm_mm.c,v 1.15 2022/02/14 13:02:31 riastradh Exp $"); |
49 | | | 49 | |
50 | #include <linux/export.h> | | 50 | #include <linux/export.h> |
51 | #include <linux/interval_tree_generic.h> | | 51 | #include <linux/interval_tree_generic.h> |
52 | #include <linux/seq_file.h> | | 52 | #include <linux/seq_file.h> |
53 | #include <linux/slab.h> | | 53 | #include <linux/slab.h> |
54 | #include <linux/stacktrace.h> | | 54 | #include <linux/stacktrace.h> |
55 | | | 55 | |
56 | #include <drm/drm_mm.h> | | 56 | #include <drm/drm_mm.h> |
57 | | | 57 | |
58 | /** | | 58 | /** |
59 | * DOC: Overview | | 59 | * DOC: Overview |
60 | * | | 60 | * |
61 | * drm_mm provides a simple range allocator. The drivers are free to use the | | 61 | * drm_mm provides a simple range allocator. The drivers are free to use the |
62 | * resource allocator from the linux core if it suits them, the upside of drm_mm | | 62 | * resource allocator from the linux core if it suits them, the upside of drm_mm |
63 | * is that it's in the DRM core. Which means that it's easier to extend for | | 63 | * is that it's in the DRM core. Which means that it's easier to extend for |
64 | * some of the crazier special purpose needs of gpus. | | 64 | * some of the crazier special purpose needs of gpus. |
65 | * | | 65 | * |
66 | * The main data struct is &drm_mm, allocations are tracked in &drm_mm_node. | | 66 | * The main data struct is &drm_mm, allocations are tracked in &drm_mm_node. |
67 | * Drivers are free to embed either of them into their own suitable | | 67 | * Drivers are free to embed either of them into their own suitable |
68 | * datastructures. drm_mm itself will not do any memory allocations of its own, | | 68 | * datastructures. drm_mm itself will not do any memory allocations of its own, |
69 | * so if drivers choose not to embed nodes they need to still allocate them | | 69 | * so if drivers choose not to embed nodes they need to still allocate them |
70 | * themselves. | | 70 | * themselves. |
71 | * | | 71 | * |
72 | * The range allocator also supports reservation of preallocated blocks. This is | | 72 | * The range allocator also supports reservation of preallocated blocks. This is |
73 | * useful for taking over initial mode setting configurations from the firmware, | | 73 | * useful for taking over initial mode setting configurations from the firmware, |
74 | * where an object needs to be created which exactly matches the firmware's | | 74 | * where an object needs to be created which exactly matches the firmware's |
75 | * scanout target. As long as the range is still free it can be inserted anytime | | 75 | * scanout target. As long as the range is still free it can be inserted anytime |
76 | * after the allocator is initialized, which helps with avoiding looped | | 76 | * after the allocator is initialized, which helps with avoiding looped |
77 | * dependencies in the driver load sequence. | | 77 | * dependencies in the driver load sequence. |
78 | * | | 78 | * |
79 | * drm_mm maintains a stack of most recently freed holes, which of all | | 79 | * drm_mm maintains a stack of most recently freed holes, which of all |
80 | * simplistic datastructures seems to be a fairly decent approach to clustering | | 80 | * simplistic datastructures seems to be a fairly decent approach to clustering |
81 | * allocations and avoiding too much fragmentation. This means free space | | 81 | * allocations and avoiding too much fragmentation. This means free space |
82 | * searches are O(num_holes). Given that all the fancy features drm_mm supports | | 82 | * searches are O(num_holes). Given that all the fancy features drm_mm supports |
83 | * something better would be fairly complex and since gfx thrashing is a fairly | | 83 | * something better would be fairly complex and since gfx thrashing is a fairly |
84 | * steep cliff not a real concern. Removing a node again is O(1). | | 84 | * steep cliff not a real concern. Removing a node again is O(1). |
85 | * | | 85 | * |
86 | * drm_mm supports a few features: Alignment and range restrictions can be | | 86 | * drm_mm supports a few features: Alignment and range restrictions can be |
87 | * supplied. Furthermore every &drm_mm_node has a color value (which is just an | | 87 | * supplied. Furthermore every &drm_mm_node has a color value (which is just an |
88 | * opaque unsigned long) which in conjunction with a driver callback can be used | | 88 | * opaque unsigned long) which in conjunction with a driver callback can be used |
89 | * to implement sophisticated placement restrictions. The i915 DRM driver uses | | 89 | * to implement sophisticated placement restrictions. The i915 DRM driver uses |
90 | * this to implement guard pages between incompatible caching domains in the | | 90 | * this to implement guard pages between incompatible caching domains in the |
91 | * graphics TT. | | 91 | * graphics TT. |
92 | * | | 92 | * |
93 | * Two behaviors are supported for searching and allocating: bottom-up and | | 93 | * Two behaviors are supported for searching and allocating: bottom-up and |
94 | * top-down. The default is bottom-up. Top-down allocation can be used if the | | 94 | * top-down. The default is bottom-up. Top-down allocation can be used if the |
95 | * memory area has different restrictions, or just to reduce fragmentation. | | 95 | * memory area has different restrictions, or just to reduce fragmentation. |
96 | * | | 96 | * |
97 | * Finally iteration helpers to walk all nodes and all holes are provided as are | | 97 | * Finally iteration helpers to walk all nodes and all holes are provided as are |
98 | * some basic allocator dumpers for debugging. | | 98 | * some basic allocator dumpers for debugging. |
99 | * | | 99 | * |
100 | * Note that this range allocator is not thread-safe, drivers need to protect | | 100 | * Note that this range allocator is not thread-safe, drivers need to protect |
101 | * modifications with their own locking. The idea behind this is that for a full | | 101 | * modifications with their own locking. The idea behind this is that for a full |
102 | * memory manager additional data needs to be protected anyway, hence internal | | 102 | * memory manager additional data needs to be protected anyway, hence internal |
103 | * locking would be fully redundant. | | 103 | * locking would be fully redundant. |
104 | */ | | 104 | */ |
105 | | | 105 | |
106 | #ifdef CONFIG_DRM_DEBUG_MM | | 106 | #ifdef CONFIG_DRM_DEBUG_MM |
107 | #include <linux/stackdepot.h> | | 107 | #include <linux/stackdepot.h> |
108 | | | 108 | |
109 | #define STACKDEPTH 32 | | 109 | #define STACKDEPTH 32 |
110 | #define BUFSZ 4096 | | 110 | #define BUFSZ 4096 |
111 | | | 111 | |
112 | static noinline void save_stack(struct drm_mm_node *node) | | 112 | static noinline void save_stack(struct drm_mm_node *node) |
113 | { | | 113 | { |
114 | unsigned long entries[STACKDEPTH]; | | 114 | unsigned long entries[STACKDEPTH]; |
115 | unsigned int n; | | 115 | unsigned int n; |
116 | | | 116 | |
117 | n = stack_trace_save(entries, ARRAY_SIZE(entries), 1); | | 117 | n = stack_trace_save(entries, ARRAY_SIZE(entries), 1); |
118 | | | 118 | |
119 | /* May be called under spinlock, so avoid sleeping */ | | 119 | /* May be called under spinlock, so avoid sleeping */ |
120 | node->stack = stack_depot_save(entries, n, GFP_NOWAIT); | | 120 | node->stack = stack_depot_save(entries, n, GFP_NOWAIT); |
121 | } | | 121 | } |
122 | | | 122 | |
123 | static void show_leaks(struct drm_mm *mm) | | 123 | static void show_leaks(struct drm_mm *mm) |
124 | { | | 124 | { |
125 | struct drm_mm_node *node; | | 125 | struct drm_mm_node *node; |
126 | unsigned long *entries; | | 126 | unsigned long *entries; |
127 | unsigned int nr_entries; | | 127 | unsigned int nr_entries; |
128 | char *buf; | | 128 | char *buf; |
129 | | | 129 | |
130 | buf = kmalloc(BUFSZ, GFP_KERNEL); | | 130 | buf = kmalloc(BUFSZ, GFP_KERNEL); |
131 | if (!buf) | | 131 | if (!buf) |
132 | return; | | 132 | return; |
133 | | | 133 | |
134 | list_for_each_entry(node, drm_mm_nodes(mm), node_list) { | | 134 | list_for_each_entry(node, drm_mm_nodes(mm), node_list) { |
135 | if (!node->stack) { | | 135 | if (!node->stack) { |
136 | DRM_ERROR("node [%08"PRIx64" + %08"PRIx64"]: unknown owner\n", | | 136 | DRM_ERROR("node [%08"PRIx64" + %08"PRIx64"]: unknown owner\n", |
137 | node->start, node->size); | | 137 | node->start, node->size); |
138 | continue; | | 138 | continue; |
139 | } | | 139 | } |
140 | | | 140 | |
141 | nr_entries = stack_depot_fetch(node->stack, &entries); | | 141 | nr_entries = stack_depot_fetch(node->stack, &entries); |
142 | stack_trace_snprint(buf, BUFSZ, entries, nr_entries, 0); | | 142 | stack_trace_snprint(buf, BUFSZ, entries, nr_entries, 0); |
143 | DRM_ERROR("node [%08"PRIx64" + %08"PRIx64"]: inserted at\n%s", | | 143 | DRM_ERROR("node [%08"PRIx64" + %08"PRIx64"]: inserted at\n%s", |
144 | node->start, node->size, buf); | | 144 | node->start, node->size, buf); |
145 | } | | 145 | } |
146 | | | 146 | |
147 | kfree(buf); | | 147 | kfree(buf); |
148 | } | | 148 | } |
149 | | | 149 | |
150 | #undef STACKDEPTH | | 150 | #undef STACKDEPTH |
151 | #undef BUFSZ | | 151 | #undef BUFSZ |
152 | #else | | 152 | #else |
153 | static void save_stack(struct drm_mm_node *node) { } | | 153 | static void save_stack(struct drm_mm_node *node) { } |
154 | static void show_leaks(struct drm_mm *mm) { } | | 154 | static void show_leaks(struct drm_mm *mm) { } |
155 | #endif | | 155 | #endif |
156 | | | 156 | |
157 | #define START(node) ((node)->start) | | 157 | #define START(node) ((node)->start) |
158 | #define LAST(node) ((node)->start + (node)->size - 1) | | 158 | #define LAST(node) ((node)->start + (node)->size - 1) |
159 | | | 159 | |
160 | #ifndef __NetBSD__ | | 160 | #ifndef __NetBSD__ |
161 | INTERVAL_TREE_DEFINE(struct drm_mm_node, rb, | | 161 | INTERVAL_TREE_DEFINE(struct drm_mm_node, rb, |
162 | u64, __subtree_last, | | 162 | u64, __subtree_last, |
163 | START, LAST, static inline, drm_mm_interval_tree) | | 163 | START, LAST, static inline, drm_mm_interval_tree) |
164 | #endif | | 164 | #endif |
165 | | | 165 | |
166 | struct drm_mm_node * | | 166 | struct drm_mm_node * |
167 | __drm_mm_interval_first(const struct drm_mm *mm_const, u64 start, u64 last) | | 167 | __drm_mm_interval_first(const struct drm_mm *mm_const, u64 start, u64 last) |
168 | { | | 168 | { |
169 | struct drm_mm *mm = __UNCONST(mm_const); | | 169 | struct drm_mm *mm = __UNCONST(mm_const); |
170 | #ifdef __NetBSD__ | | 170 | #ifdef __NetBSD__ |
171 | struct drm_mm_node *node; | | 171 | struct drm_mm_node *node; |
172 | list_for_each_entry(node, &mm->head_node.node_list, node_list) { | | 172 | list_for_each_entry(node, &mm->head_node.node_list, node_list) { |
173 | if (node->start <= start) | | 173 | if (node->start <= start) |
174 | return node; | | 174 | return node; |
175 | } | | 175 | } |
176 | return NULL; | | 176 | return NULL; |
177 | #else | | 177 | #else |
178 | return drm_mm_interval_tree_iter_first((struct rb_root_cached *)&mm->interval_tree, | | 178 | return drm_mm_interval_tree_iter_first((struct rb_root_cached *)&mm->interval_tree, |
179 | start, last) ?: (struct drm_mm_node *)&mm->head_node; | | 179 | start, last) ?: (struct drm_mm_node *)&mm->head_node; |
180 | #endif | | 180 | #endif |
181 | } | | 181 | } |
182 | EXPORT_SYMBOL(__drm_mm_interval_first); | | 182 | EXPORT_SYMBOL(__drm_mm_interval_first); |
183 | | | 183 | |
184 | #ifndef __NetBSD__ | | 184 | #ifndef __NetBSD__ |
185 | static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, | | 185 | static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node, |
186 | struct drm_mm_node *node) | | 186 | struct drm_mm_node *node) |
187 | { | | 187 | { |
188 | struct drm_mm *mm = hole_node->mm; | | 188 | struct drm_mm *mm = hole_node->mm; |
189 | struct rb_node **link, *rb; | | 189 | struct rb_node **link, *rb; |
190 | struct drm_mm_node *parent; | | 190 | struct drm_mm_node *parent; |
191 | bool leftmost; | | 191 | bool leftmost; |
192 | | | 192 | |
193 | node->__subtree_last = LAST(node); | | 193 | node->__subtree_last = LAST(node); |
194 | | | 194 | |
195 | if (drm_mm_node_allocated(hole_node)) { | | 195 | if (drm_mm_node_allocated(hole_node)) { |
196 | rb = &hole_node->rb; | | 196 | rb = &hole_node->rb; |
197 | while (rb) { | | 197 | while (rb) { |
198 | parent = rb_entry(rb, struct drm_mm_node, rb); | | 198 | parent = rb_entry(rb, struct drm_mm_node, rb); |
199 | if (parent->__subtree_last >= node->__subtree_last) | | 199 | if (parent->__subtree_last >= node->__subtree_last) |
200 | break; | | 200 | break; |
201 | | | 201 | |
202 | parent->__subtree_last = node->__subtree_last; | | 202 | parent->__subtree_last = node->__subtree_last; |
203 | rb = rb_parent(rb); | | 203 | rb = rb_parent(rb); |
204 | } | | 204 | } |
205 | | | 205 | |
206 | rb = &hole_node->rb; | | 206 | rb = &hole_node->rb; |
207 | link = &hole_node->rb.rb_right; | | 207 | link = &hole_node->rb.rb_right; |
208 | leftmost = false; | | 208 | leftmost = false; |
209 | } else { | | 209 | } else { |
210 | rb = NULL; | | 210 | rb = NULL; |
211 | link = &mm->interval_tree.rb_root.rb_node; | | 211 | link = &mm->interval_tree.rb_root.rb_node; |
212 | leftmost = true; | | 212 | leftmost = true; |
213 | } | | 213 | } |
214 | | | 214 | |
215 | while (*link) { | | 215 | while (*link) { |
216 | rb = *link; | | 216 | rb = *link; |
217 | parent = rb_entry(rb, struct drm_mm_node, rb); | | 217 | parent = rb_entry(rb, struct drm_mm_node, rb); |
218 | if (parent->__subtree_last < node->__subtree_last) | | 218 | if (parent->__subtree_last < node->__subtree_last) |
219 | parent->__subtree_last = node->__subtree_last; | | 219 | parent->__subtree_last = node->__subtree_last; |
220 | if (node->start < parent->start) { | | 220 | if (node->start < parent->start) { |
221 | link = &parent->rb.rb_left; | | 221 | link = &parent->rb.rb_left; |
222 | } else { | | 222 | } else { |
223 | link = &parent->rb.rb_right; | | 223 | link = &parent->rb.rb_right; |
224 | leftmost = false; | | 224 | leftmost = false; |
225 | } | | 225 | } |
226 | } | | 226 | } |
227 | | | 227 | |
228 | rb_link_node(&node->rb, rb, link); | | 228 | rb_link_node(&node->rb, rb, link); |
229 | rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost, | | 229 | rb_insert_augmented_cached(&node->rb, &mm->interval_tree, leftmost, |
230 | &drm_mm_interval_tree_augment); | | 230 | &drm_mm_interval_tree_augment); |
231 | } | | 231 | } |
232 | #endif | | 232 | #endif |
233 | | | 233 | |
234 | #ifdef __NetBSD__ | | 234 | #ifdef __NetBSD__ |
235 | | | 235 | |
236 | static int | | 236 | static int |
237 | compare_hole_addrs(void *cookie, const void *va, const void *vb) | | 237 | compare_hole_addrs(void *cookie, const void *va, const void *vb) |
238 | { | | 238 | { |
239 | const struct drm_mm_node *a = va, *b = vb; | | 239 | const struct drm_mm_node *a = va, *b = vb; |
240 | const u64 aa = __drm_mm_hole_node_start(a); | | 240 | const u64 aa = __drm_mm_hole_node_start(a); |
241 | const u64 ba = __drm_mm_hole_node_start(b); | | 241 | const u64 ba = __drm_mm_hole_node_start(b); |
242 | | | 242 | |
243 | if (aa < ba) | | 243 | if (aa < ba) |
244 | return -1; | | 244 | return -1; |
245 | if (aa > ba) | | 245 | if (aa > ba) |
246 | return +1; | | 246 | return +1; |
247 | return 0; | | 247 | return 0; |
248 | } | | 248 | } |
249 | | | 249 | |
250 | static int | | 250 | static int |
251 | compare_hole_addr_key(void *cookie, const void *vn, const void *vk) | | 251 | compare_hole_addr_key(void *cookie, const void *vn, const void *vk) |
252 | { | | 252 | { |
253 | const struct drm_mm_node *n = vn; | | 253 | const struct drm_mm_node *n = vn; |
254 | const u64 a = __drm_mm_hole_node_start(n); | | 254 | const u64 a = __drm_mm_hole_node_start(n); |
255 | const u64 *k = vk; | | 255 | const u64 *k = vk; |
256 | | | 256 | |
257 | if (a < *k) | | 257 | if (a < *k) |
258 | return -1; | | 258 | return -1; |
259 | if (a > *k) | | 259 | if (a > *k) |
260 | return +1; | | 260 | return +1; |
261 | return 0; | | 261 | return 0; |
262 | } | | 262 | } |
263 | | | 263 | |
264 | static const rb_tree_ops_t holes_addr_rb_ops = { | | 264 | static const rb_tree_ops_t holes_addr_rb_ops = { |
265 | .rbto_compare_nodes = compare_hole_addrs, | | 265 | .rbto_compare_nodes = compare_hole_addrs, |
266 | .rbto_compare_key = compare_hole_addr_key, | | 266 | .rbto_compare_key = compare_hole_addr_key, |
267 | .rbto_node_offset = offsetof(struct drm_mm_node, rb_hole_addr), | | 267 | .rbto_node_offset = offsetof(struct drm_mm_node, rb_hole_addr), |
268 | }; | | 268 | }; |
269 | | | 269 | |
270 | #else | | 270 | #else |
271 | | | 271 | |
272 | #define RB_INSERT(root, member, expr) do { \ | | 272 | #define RB_INSERT(root, member, expr) do { \ |
273 | struct rb_node **link = &root.rb_node, *rb = NULL; \ | | 273 | struct rb_node **link = &root.rb_node, *rb = NULL; \ |
274 | u64 x = expr(node); \ | | 274 | u64 x = expr(node); \ |
275 | while (*link) { \ | | 275 | while (*link) { \ |
276 | rb = *link; \ | | 276 | rb = *link; \ |
277 | if (x < expr(rb_entry(rb, struct drm_mm_node, member))) \ | | 277 | if (x < expr(rb_entry(rb, struct drm_mm_node, member))) \ |
278 | link = &rb->rb_left; \ | | 278 | link = &rb->rb_left; \ |
279 | else \ | | 279 | else \ |
280 | link = &rb->rb_right; \ | | 280 | link = &rb->rb_right; \ |
281 | } \ | | 281 | } \ |
282 | rb_link_node(&node->member, rb, link); \ | | 282 | rb_link_node(&node->member, rb, link); \ |
283 | rb_insert_color(&node->member, &root); \ | | 283 | rb_insert_color(&node->member, &root); \ |
284 | } while (0) | | 284 | } while (0) |
285 | | | 285 | |
286 | #endif | | 286 | #endif |
287 | | | 287 | |
288 | #define HOLE_SIZE(NODE) ((NODE)->hole_size) | | 288 | #define HOLE_SIZE(NODE) ((NODE)->hole_size) |
289 | #define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE)) | | 289 | #define HOLE_ADDR(NODE) (__drm_mm_hole_node_start(NODE)) |
290 | | | 290 | |
291 | static u64 rb_to_hole_size(struct rb_node *rb) | | 291 | static u64 rb_to_hole_size(struct rb_node *rb) |
292 | { | | 292 | { |
293 | return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; | | 293 | return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; |
294 | } | | 294 | } |
295 | | | 295 | |
296 | static int | | 296 | static int |
297 | compare_hole_sizes(void *cookie, const void *va, const void *vb) | | 297 | compare_hole_sizes(void *cookie, const void *va, const void *vb) |
298 | { | | 298 | { |
299 | const struct drm_mm_node *a = va, *b = vb; | | 299 | const struct drm_mm_node *a = va, *b = vb; |
300 | | | 300 | |
301 | if (a->hole_size > b->hole_size) | | 301 | if (a->hole_size > b->hole_size) |
302 | return -1; | | 302 | return -1; |
303 | if (a->hole_size < b->hole_size) | | 303 | if (a->hole_size < b->hole_size) |
304 | return +1; | | 304 | return +1; |
305 | return (a < b ? -1 : a > b ? +1 : 0); | | 305 | return (a < b ? -1 : a > b ? +1 : 0); |
306 | } | | 306 | } |
307 | | | 307 | |
308 | static int | | 308 | static int |
309 | compare_hole_size_key(void *cookie, const void *vn, const void *vk) | | 309 | compare_hole_size_key(void *cookie, const void *vn, const void *vk) |
310 | { | | 310 | { |
311 | const struct drm_mm_node *n = vn; | | 311 | const struct drm_mm_node *n = vn; |
312 | const u64 *k = vk; | | 312 | const u64 *k = vk; |
313 | | | 313 | |
314 | if (n->hole_size > *k) | | 314 | if (n->hole_size > *k) |
315 | return -1; | | 315 | return -1; |
316 | if (n->hole_size < *k) | | 316 | if (n->hole_size < *k) |
317 | return +1; | | 317 | return +1; |
318 | return 0; | | 318 | return 0; |
319 | } | | 319 | } |
320 | | | 320 | |
321 | static const rb_tree_ops_t holes_size_rb_ops = { | | 321 | static const rb_tree_ops_t holes_size_rb_ops = { |
322 | .rbto_compare_nodes = compare_hole_sizes, | | 322 | .rbto_compare_nodes = compare_hole_sizes, |
323 | .rbto_compare_key = compare_hole_size_key, | | 323 | .rbto_compare_key = compare_hole_size_key, |
324 | .rbto_node_offset = offsetof(struct drm_mm_node, rb_hole_size), | | 324 | .rbto_node_offset = offsetof(struct drm_mm_node, rb_hole_size), |
325 | }; | | 325 | }; |
326 | | | 326 | |
327 | static void insert_hole_size(struct rb_root_cached *root, | | 327 | static void insert_hole_size(struct rb_root_cached *root, |
328 | struct drm_mm_node *node) | | 328 | struct drm_mm_node *node) |
329 | { | | 329 | { |
330 | #ifdef __NetBSD__ | | 330 | #ifdef __NetBSD__ |
331 | struct drm_mm_node *collision __diagused; | | 331 | struct drm_mm_node *collision __diagused; |
332 | collision = rb_tree_insert_node(&root->rb_root.rbr_tree, node); | | 332 | collision = rb_tree_insert_node(&root->rb_root.rbr_tree, node); |
333 | KASSERT(collision == node); | | 333 | KASSERT(collision == node); |
334 | #else | | 334 | #else |
335 | struct rb_node **link = &root->rb_root.rb_node, *rb = NULL; | | 335 | struct rb_node **link = &root->rb_root.rb_node, *rb = NULL; |
336 | u64 x = node->hole_size; | | 336 | u64 x = node->hole_size; |
337 | bool first = true; | | 337 | bool first = true; |
338 | | | 338 | |
339 | while (*link) { | | 339 | while (*link) { |
340 | rb = *link; | | 340 | rb = *link; |
341 | if (x > rb_to_hole_size(rb)) { | | 341 | if (x > rb_to_hole_size(rb)) { |
342 | link = &rb->rb_left; | | 342 | link = &rb->rb_left; |
343 | } else { | | 343 | } else { |
344 | link = &rb->rb_right; | | 344 | link = &rb->rb_right; |
345 | first = false; | | 345 | first = false; |
346 | } | | 346 | } |
347 | } | | 347 | } |
348 | | | 348 | |
349 | rb_link_node(&node->rb_hole_size, rb, link); | | 349 | rb_link_node(&node->rb_hole_size, rb, link); |
350 | rb_insert_color_cached(&node->rb_hole_size, root, first); | | 350 | rb_insert_color_cached(&node->rb_hole_size, root, first); |
351 | #endif | | 351 | #endif |
352 | } | | 352 | } |
353 | | | 353 | |
354 | static void add_hole(struct drm_mm_node *node) | | 354 | static void add_hole(struct drm_mm_node *node) |
355 | { | | 355 | { |
356 | struct drm_mm *mm = node->mm; | | 356 | struct drm_mm *mm = node->mm; |
357 | | | 357 | |
358 | node->hole_size = | | 358 | node->hole_size = |
359 | __drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node); | | 359 | __drm_mm_hole_node_end(node) - __drm_mm_hole_node_start(node); |
360 | DRM_MM_BUG_ON(!drm_mm_hole_follows(node)); | | 360 | DRM_MM_BUG_ON(!drm_mm_hole_follows(node)); |
361 | | | 361 | |
362 | insert_hole_size(&mm->holes_size, node); | | 362 | insert_hole_size(&mm->holes_size, node); |
363 | #ifdef __NetBSD__ | | 363 | #ifdef __NetBSD__ |
364 | struct drm_mm_node *collision __diagused; | | 364 | struct drm_mm_node *collision __diagused; |
365 | collision = rb_tree_insert_node(&mm->holes_addr.rbr_tree, node); | | 365 | collision = rb_tree_insert_node(&mm->holes_addr.rbr_tree, node); |
366 | KASSERT(collision == node); | | 366 | KASSERT(collision == node); |
367 | #else | | 367 | #else |
368 | RB_INSERT(mm->holes_addr, rb_hole_addr, HOLE_ADDR); | | 368 | RB_INSERT(mm->holes_addr, rb_hole_addr, HOLE_ADDR); |
369 | #endif | | 369 | #endif |
370 | | | 370 | |
371 | list_add(&node->hole_stack, &mm->hole_stack); | | 371 | list_add(&node->hole_stack, &mm->hole_stack); |
372 | } | | 372 | } |
373 | | | 373 | |
374 | static void rm_hole(struct drm_mm_node *node) | | 374 | static void rm_hole(struct drm_mm_node *node) |
375 | { | | 375 | { |
376 | DRM_MM_BUG_ON(!drm_mm_hole_follows(node)); | | 376 | DRM_MM_BUG_ON(!drm_mm_hole_follows(node)); |
377 | | | 377 | |
378 | list_del(&node->hole_stack); | | 378 | list_del(&node->hole_stack); |
379 | rb_erase_cached(&node->rb_hole_size, &node->mm->holes_size); | | 379 | rb_erase_cached(&node->rb_hole_size, &node->mm->holes_size); |
380 | rb_erase(&node->rb_hole_addr, &node->mm->holes_addr); | | 380 | rb_erase(&node->rb_hole_addr, &node->mm->holes_addr); |
381 | node->hole_size = 0; | | 381 | node->hole_size = 0; |
382 | | | 382 | |
383 | DRM_MM_BUG_ON(drm_mm_hole_follows(node)); | | 383 | DRM_MM_BUG_ON(drm_mm_hole_follows(node)); |
384 | } | | 384 | } |
385 | | | 385 | |
386 | static inline struct drm_mm_node *rb_hole_size_to_node(struct rb_node *rb) | | 386 | static inline struct drm_mm_node *rb_hole_size_to_node(struct rb_node *rb) |
387 | { | | 387 | { |
388 | return rb_entry_safe(rb, struct drm_mm_node, rb_hole_size); | | 388 | return rb_entry_safe(rb, struct drm_mm_node, rb_hole_size); |
389 | } | | 389 | } |
390 | | | 390 | |
391 | static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb) | | 391 | static inline struct drm_mm_node *rb_hole_addr_to_node(struct rb_node *rb) |
392 | { | | 392 | { |
393 | return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr); | | 393 | return rb_entry_safe(rb, struct drm_mm_node, rb_hole_addr); |
394 | } | | 394 | } |
395 | | | 395 | |
396 | static inline u64 rb_hole_size(struct rb_node *rb) | | 396 | static inline u64 rb_hole_size(struct rb_node *rb) |
397 | { | | 397 | { |
398 | return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; | | 398 | return rb_entry(rb, struct drm_mm_node, rb_hole_size)->hole_size; |
399 | } | | 399 | } |
400 | | | 400 | |
401 | static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size) | | 401 | static struct drm_mm_node *best_hole(struct drm_mm *mm, u64 size) |
402 | { | | 402 | { |
403 | #ifdef __NetBSD__ | | 403 | #ifdef __NetBSD__ |
404 | return rb_tree_find_node_leq(&mm->holes_size.rb_root.rbr_tree, &size); | | 404 | struct drm_mm_node *best; |
| | | 405 | |
| | | 406 | best = rb_tree_find_node_leq(&mm->holes_size.rb_root.rbr_tree, &size); |
| | | 407 | KASSERT(best == NULL || size <= best->hole_size); |
| | | 408 | |
| | | 409 | return best; |
405 | #else | | 410 | #else |
406 | struct rb_node *rb = mm->holes_size.rb_root.rb_node; | | 411 | struct rb_node *rb = mm->holes_size.rb_root.rb_node; |
407 | struct drm_mm_node *best = NULL; | | 412 | struct drm_mm_node *best = NULL; |
408 | | | 413 | |
409 | do { | | 414 | do { |
410 | struct drm_mm_node *node = | | 415 | struct drm_mm_node *node = |
411 | rb_entry(rb, struct drm_mm_node, rb_hole_size); | | 416 | rb_entry(rb, struct drm_mm_node, rb_hole_size); |
412 | | | 417 | |
413 | if (size <= node->hole_size) { | | 418 | if (size <= node->hole_size) { |
414 | best = node; | | 419 | best = node; |
415 | rb = rb->rb_right; | | 420 | rb = rb->rb_right; |
416 | } else { | | 421 | } else { |
417 | rb = rb->rb_left; | | 422 | rb = rb->rb_left; |
418 | } | | 423 | } |
419 | } while (rb); | | 424 | } while (rb); |
420 | | | 425 | |
421 | return best; | | 426 | return best; |
422 | #endif | | 427 | #endif |
423 | } | | 428 | } |
424 | | | 429 | |
425 | static struct drm_mm_node *find_hole(struct drm_mm *mm, u64 addr) | | 430 | static struct drm_mm_node *find_hole(struct drm_mm *mm, u64 addr) |
426 | { | | 431 | { |
427 | #ifdef __NetBSD__ | | 432 | #ifdef __NetBSD__ |
428 | return rb_tree_find_node_leq(&mm->holes_addr.rbr_tree, &addr); | | 433 | return rb_tree_find_node_leq(&mm->holes_addr.rbr_tree, &addr); |
429 | #else | | 434 | #else |
430 | struct rb_node *rb = mm->holes_addr.rb_node; | | 435 | struct rb_node *rb = mm->holes_addr.rb_node; |
431 | struct drm_mm_node *node = NULL; | | 436 | struct drm_mm_node *node = NULL; |
432 | | | 437 | |
433 | while (rb) { | | 438 | while (rb) { |
434 | u64 hole_start; | | 439 | u64 hole_start; |
435 | | | 440 | |
436 | node = rb_hole_addr_to_node(rb); | | 441 | node = rb_hole_addr_to_node(rb); |
437 | hole_start = __drm_mm_hole_node_start(node); | | 442 | hole_start = __drm_mm_hole_node_start(node); |
438 | | | 443 | |
439 | if (addr < hole_start) | | 444 | if (addr < hole_start) |
440 | rb = node->rb_hole_addr.rb_left; | | 445 | rb = node->rb_hole_addr.rb_left; |
441 | else if (addr > hole_start + node->hole_size) | | 446 | else if (addr > hole_start + node->hole_size) |
442 | rb = node->rb_hole_addr.rb_right; | | 447 | rb = node->rb_hole_addr.rb_right; |
443 | else | | 448 | else |
444 | break; | | 449 | break; |
445 | } | | 450 | } |
446 | | | 451 | |
447 | return node; | | 452 | return node; |
448 | #endif | | 453 | #endif |
449 | } | | 454 | } |
450 | | | 455 | |
451 | static struct drm_mm_node * | | 456 | static struct drm_mm_node * |
452 | first_hole(struct drm_mm *mm, | | 457 | first_hole(struct drm_mm *mm, |
453 | u64 start, u64 end, u64 size, | | 458 | u64 start, u64 end, u64 size, |
454 | enum drm_mm_insert_mode mode) | | 459 | enum drm_mm_insert_mode mode) |
455 | { | | 460 | { |
456 | switch (mode) { | | 461 | switch (mode) { |
457 | default: | | 462 | default: |
458 | case DRM_MM_INSERT_BEST: | | 463 | case DRM_MM_INSERT_BEST: |
459 | return best_hole(mm, size); | | 464 | return best_hole(mm, size); |
460 | | | 465 | |
461 | case DRM_MM_INSERT_LOW: | | 466 | case DRM_MM_INSERT_LOW: |
462 | return find_hole(mm, start); | | 467 | return find_hole(mm, start); |
463 | | | 468 | |
464 | case DRM_MM_INSERT_HIGH: | | 469 | case DRM_MM_INSERT_HIGH: |
465 | return find_hole(mm, end); | | 470 | return find_hole(mm, end); |
466 | | | 471 | |
467 | case DRM_MM_INSERT_EVICT: | | 472 | case DRM_MM_INSERT_EVICT: |
468 | return list_first_entry_or_null(&mm->hole_stack, | | 473 | return list_first_entry_or_null(&mm->hole_stack, |
469 | struct drm_mm_node, | | 474 | struct drm_mm_node, |
470 | hole_stack); | | 475 | hole_stack); |
471 | } | | 476 | } |
472 | } | | 477 | } |
473 | | | 478 | |
474 | static struct drm_mm_node * | | 479 | static struct drm_mm_node * |
475 | next_hole(struct drm_mm *mm, | | 480 | next_hole(struct drm_mm *mm, |
476 | struct drm_mm_node *node, | | 481 | struct drm_mm_node *node, |
477 | enum drm_mm_insert_mode mode) | | 482 | enum drm_mm_insert_mode mode) |
478 | { | | 483 | { |
479 | switch (mode) { | | 484 | switch (mode) { |
480 | default: | | 485 | default: |
481 | case DRM_MM_INSERT_BEST: | | 486 | case DRM_MM_INSERT_BEST: |
482 | #ifdef __NetBSD__ | | 487 | #ifdef __NetBSD__ |
483 | return RB_TREE_PREV(&mm->holes_size.rb_root.rbr_tree, node); | | 488 | return RB_TREE_PREV(&mm->holes_size.rb_root.rbr_tree, node); |
484 | #else | | 489 | #else |
485 | return rb_hole_size_to_node(rb_prev(&node->rb_hole_size)); | | 490 | return rb_hole_size_to_node(rb_prev(&node->rb_hole_size)); |
486 | #endif | | 491 | #endif |
487 | | | 492 | |
488 | case DRM_MM_INSERT_LOW: | | 493 | case DRM_MM_INSERT_LOW: |
489 | #ifdef __NetBSD__ | | 494 | #ifdef __NetBSD__ |
490 | return RB_TREE_NEXT(&mm->holes_addr.rbr_tree, node); | | 495 | return RB_TREE_NEXT(&mm->holes_addr.rbr_tree, node); |
491 | #else | | 496 | #else |
492 | return rb_hole_addr_to_node(rb_next(&node->rb_hole_addr)); | | 497 | return rb_hole_addr_to_node(rb_next(&node->rb_hole_addr)); |
493 | #endif | | 498 | #endif |
494 | | | 499 | |
495 | case DRM_MM_INSERT_HIGH: | | 500 | case DRM_MM_INSERT_HIGH: |
496 | #ifdef __NetBSD__ | | 501 | #ifdef __NetBSD__ |
497 | return RB_TREE_PREV(&mm->holes_addr.rbr_tree, node); | | 502 | return RB_TREE_PREV(&mm->holes_addr.rbr_tree, node); |
498 | #else | | 503 | #else |
499 | return rb_hole_addr_to_node(rb_prev(&node->rb_hole_addr)); | | 504 | return rb_hole_addr_to_node(rb_prev(&node->rb_hole_addr)); |
500 | #endif | | 505 | #endif |
501 | | | 506 | |
502 | case DRM_MM_INSERT_EVICT: | | 507 | case DRM_MM_INSERT_EVICT: |
503 | node = list_next_entry(node, hole_stack); | | 508 | node = list_next_entry(node, hole_stack); |
504 | return &node->hole_stack == &mm->hole_stack ? NULL : node; | | 509 | return &node->hole_stack == &mm->hole_stack ? NULL : node; |
505 | } | | 510 | } |
506 | } | | 511 | } |
507 | | | 512 | |
508 | /** | | 513 | /** |
509 | * drm_mm_reserve_node - insert an pre-initialized node | | 514 | * drm_mm_reserve_node - insert an pre-initialized node |
510 | * @mm: drm_mm allocator to insert @node into | | 515 | * @mm: drm_mm allocator to insert @node into |
511 | * @node: drm_mm_node to insert | | 516 | * @node: drm_mm_node to insert |
512 | * | | 517 | * |
513 | * This functions inserts an already set-up &drm_mm_node into the allocator, | | 518 | * This functions inserts an already set-up &drm_mm_node into the allocator, |
514 | * meaning that start, size and color must be set by the caller. All other | | 519 | * meaning that start, size and color must be set by the caller. All other |
515 | * fields must be cleared to 0. This is useful to initialize the allocator with | | 520 | * fields must be cleared to 0. This is useful to initialize the allocator with |
516 | * preallocated objects which must be set-up before the range allocator can be | | 521 | * preallocated objects which must be set-up before the range allocator can be |
517 | * set-up, e.g. when taking over a firmware framebuffer. | | 522 | * set-up, e.g. when taking over a firmware framebuffer. |
518 | * | | 523 | * |
519 | * Returns: | | 524 | * Returns: |
520 | * 0 on success, -ENOSPC if there's no hole where @node is. | | 525 | * 0 on success, -ENOSPC if there's no hole where @node is. |
521 | */ | | 526 | */ |
522 | int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) | | 527 | int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) |
523 | { | | 528 | { |
524 | u64 end = node->start + node->size; | | 529 | u64 end = node->start + node->size; |
525 | struct drm_mm_node *hole; | | 530 | struct drm_mm_node *hole; |
526 | u64 hole_start, hole_end; | | 531 | u64 hole_start, hole_end; |
527 | u64 adj_start, adj_end; | | 532 | u64 adj_start, adj_end; |
528 | | | 533 | |
529 | end = node->start + node->size; | | 534 | end = node->start + node->size; |
530 | if (unlikely(end <= node->start)) | | 535 | if (unlikely(end <= node->start)) |
531 | return -ENOSPC; | | 536 | return -ENOSPC; |
532 | | | 537 | |
533 | /* Find the relevant hole to add our node to */ | | 538 | /* Find the relevant hole to add our node to */ |
534 | hole = find_hole(mm, node->start); | | 539 | hole = find_hole(mm, node->start); |
535 | if (!hole) | | 540 | if (!hole) |
536 | return -ENOSPC; | | 541 | return -ENOSPC; |
537 | | | 542 | |
538 | adj_start = hole_start = __drm_mm_hole_node_start(hole); | | 543 | adj_start = hole_start = __drm_mm_hole_node_start(hole); |
539 | adj_end = hole_end = hole_start + hole->hole_size; | | 544 | adj_end = hole_end = hole_start + hole->hole_size; |
540 | | | 545 | |
541 | if (mm->color_adjust) | | 546 | if (mm->color_adjust) |
542 | mm->color_adjust(hole, node->color, &adj_start, &adj_end); | | 547 | mm->color_adjust(hole, node->color, &adj_start, &adj_end); |
543 | | | 548 | |
544 | if (adj_start > node->start || adj_end < end) | | 549 | if (adj_start > node->start || adj_end < end) |
545 | return -ENOSPC; | | 550 | return -ENOSPC; |
546 | | | 551 | |
547 | node->mm = mm; | | 552 | node->mm = mm; |
548 | | | 553 | |
549 | __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); | | 554 | __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); |
550 | list_add(&node->node_list, &hole->node_list); | | 555 | list_add(&node->node_list, &hole->node_list); |
551 | #ifndef __NetBSD__ | | 556 | #ifndef __NetBSD__ |
552 | drm_mm_interval_tree_add_node(hole, node); | | 557 | drm_mm_interval_tree_add_node(hole, node); |
553 | #endif | | 558 | #endif |
554 | node->hole_size = 0; | | 559 | node->hole_size = 0; |
555 | | | 560 | |
556 | rm_hole(hole); | | 561 | rm_hole(hole); |
557 | if (node->start > hole_start) | | 562 | if (node->start > hole_start) |
558 | add_hole(hole); | | 563 | add_hole(hole); |
559 | if (end < hole_end) | | 564 | if (end < hole_end) |
560 | add_hole(node); | | 565 | add_hole(node); |
561 | | | 566 | |
562 | save_stack(node); | | 567 | save_stack(node); |
563 | return 0; | | 568 | return 0; |
564 | } | | 569 | } |
565 | EXPORT_SYMBOL(drm_mm_reserve_node); | | 570 | EXPORT_SYMBOL(drm_mm_reserve_node); |
566 | | | 571 | |
567 | static u64 rb_to_hole_size_or_zero(struct rb_node *rb) | | 572 | static u64 rb_to_hole_size_or_zero(struct rb_node *rb) |
568 | { | | 573 | { |
569 | return rb ? rb_to_hole_size(rb) : 0; | | 574 | return rb ? rb_to_hole_size(rb) : 0; |
570 | } | | 575 | } |
571 | | | 576 | |
572 | /** | | 577 | /** |
573 | * drm_mm_insert_node_in_range - ranged search for space and insert @node | | 578 | * drm_mm_insert_node_in_range - ranged search for space and insert @node |
574 | * @mm: drm_mm to allocate from | | 579 | * @mm: drm_mm to allocate from |
575 | * @node: preallocate node to insert | | 580 | * @node: preallocate node to insert |
576 | * @size: size of the allocation | | 581 | * @size: size of the allocation |
577 | * @alignment: alignment of the allocation | | 582 | * @alignment: alignment of the allocation |
578 | * @color: opaque tag value to use for this node | | 583 | * @color: opaque tag value to use for this node |
579 | * @range_start: start of the allowed range for this node | | 584 | * @range_start: start of the allowed range for this node |
580 | * @range_end: end of the allowed range for this node | | 585 | * @range_end: end of the allowed range for this node |
581 | * @mode: fine-tune the allocation search and placement | | 586 | * @mode: fine-tune the allocation search and placement |
582 | * | | 587 | * |
583 | * The preallocated @node must be cleared to 0. | | 588 | * The preallocated @node must be cleared to 0. |
584 | * | | 589 | * |
585 | * Returns: | | 590 | * Returns: |
586 | * 0 on success, -ENOSPC if there's no suitable hole. | | 591 | * 0 on success, -ENOSPC if there's no suitable hole. |
587 | */ | | 592 | */ |
588 | int drm_mm_insert_node_in_range(struct drm_mm * const mm, | | 593 | int drm_mm_insert_node_in_range(struct drm_mm * const mm, |
589 | struct drm_mm_node * const node, | | 594 | struct drm_mm_node * const node, |
590 | u64 size, u64 alignment, | | 595 | u64 size, u64 alignment, |
591 | unsigned long color, | | 596 | unsigned long color, |
592 | u64 range_start, u64 range_end, | | 597 | u64 range_start, u64 range_end, |
593 | enum drm_mm_insert_mode mode) | | 598 | enum drm_mm_insert_mode mode) |
594 | { | | 599 | { |
595 | struct drm_mm_node *hole; | | 600 | struct drm_mm_node *hole; |
596 | u64 remainder_mask; | | 601 | u64 remainder_mask; |
597 | bool once; | | 602 | bool once; |
598 | | | 603 | |
599 | DRM_MM_BUG_ON(range_start > range_end); | | 604 | DRM_MM_BUG_ON(range_start > range_end); |
600 | | | 605 | |
601 | if (unlikely(size == 0 || range_end - range_start < size)) | | 606 | if (unlikely(size == 0 || range_end - range_start < size)) |
602 | return -ENOSPC; | | 607 | return -ENOSPC; |
603 | | | 608 | |
604 | if (rb_to_hole_size_or_zero(rb_first_cached(&mm->holes_size)) < size) | | 609 | if (rb_to_hole_size_or_zero(rb_first_cached(&mm->holes_size)) < size) |
605 | return -ENOSPC; | | 610 | return -ENOSPC; |
606 | | | 611 | |
607 | if (alignment <= 1) | | 612 | if (alignment <= 1) |
608 | alignment = 0; | | 613 | alignment = 0; |
609 | | | 614 | |
610 | once = mode & DRM_MM_INSERT_ONCE; | | 615 | once = mode & DRM_MM_INSERT_ONCE; |
611 | mode &= ~DRM_MM_INSERT_ONCE; | | 616 | mode &= ~DRM_MM_INSERT_ONCE; |
612 | | | 617 | |
613 | remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0; | | 618 | remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0; |
614 | for (hole = first_hole(mm, range_start, range_end, size, mode); | | 619 | for (hole = first_hole(mm, range_start, range_end, size, mode); |
615 | hole; | | 620 | hole; |
616 | hole = once ? NULL : next_hole(mm, hole, mode)) { | | 621 | hole = once ? NULL : next_hole(mm, hole, mode)) { |
617 | u64 hole_start = __drm_mm_hole_node_start(hole); | | 622 | u64 hole_start = __drm_mm_hole_node_start(hole); |
618 | u64 hole_end = hole_start + hole->hole_size; | | 623 | u64 hole_end = hole_start + hole->hole_size; |
619 | u64 adj_start, adj_end; | | 624 | u64 adj_start, adj_end; |
620 | u64 col_start, col_end; | | 625 | u64 col_start, col_end; |
621 | | | 626 | |
622 | if (mode == DRM_MM_INSERT_LOW && hole_start >= range_end) | | 627 | if (mode == DRM_MM_INSERT_LOW && hole_start >= range_end) |
623 | break; | | 628 | break; |
624 | | | 629 | |
625 | if (mode == DRM_MM_INSERT_HIGH && hole_end <= range_start) | | 630 | if (mode == DRM_MM_INSERT_HIGH && hole_end <= range_start) |
626 | break; | | 631 | break; |
627 | | | 632 | |
628 | col_start = hole_start; | | 633 | col_start = hole_start; |
629 | col_end = hole_end; | | 634 | col_end = hole_end; |
630 | if (mm->color_adjust) | | 635 | if (mm->color_adjust) |
631 | mm->color_adjust(hole, color, &col_start, &col_end); | | 636 | mm->color_adjust(hole, color, &col_start, &col_end); |
632 | | | 637 | |
633 | adj_start = max(col_start, range_start); | | 638 | adj_start = max(col_start, range_start); |
634 | adj_end = min(col_end, range_end); | | 639 | adj_end = min(col_end, range_end); |
635 | | | 640 | |
636 | if (adj_end <= adj_start || adj_end - adj_start < size) | | 641 | if (adj_end <= adj_start || adj_end - adj_start < size) |
637 | continue; | | 642 | continue; |
638 | | | 643 | |
639 | if (mode == DRM_MM_INSERT_HIGH) | | 644 | if (mode == DRM_MM_INSERT_HIGH) |
640 | adj_start = adj_end - size; | | 645 | adj_start = adj_end - size; |
641 | | | 646 | |
642 | if (alignment) { | | 647 | if (alignment) { |
643 | u64 rem; | | 648 | u64 rem; |
644 | | | 649 | |
645 | if (likely(remainder_mask)) | | 650 | if (likely(remainder_mask)) |
646 | rem = adj_start & remainder_mask; | | 651 | rem = adj_start & remainder_mask; |
647 | else | | 652 | else |
648 | div64_u64_rem(adj_start, alignment, &rem); | | 653 | div64_u64_rem(adj_start, alignment, &rem); |
649 | if (rem) { | | 654 | if (rem) { |
650 | adj_start -= rem; | | 655 | adj_start -= rem; |
651 | if (mode != DRM_MM_INSERT_HIGH) | | 656 | if (mode != DRM_MM_INSERT_HIGH) |
652 | adj_start += alignment; | | 657 | adj_start += alignment; |
653 | | | 658 | |
654 | if (adj_start < max(col_start, range_start) || | | 659 | if (adj_start < max(col_start, range_start) || |
655 | min(col_end, range_end) - adj_start < size) | | 660 | min(col_end, range_end) - adj_start < size) |
656 | continue; | | 661 | continue; |
657 | | | 662 | |
658 | if (adj_end <= adj_start || | | 663 | if (adj_end <= adj_start || |
659 | adj_end - adj_start < size) | | 664 | adj_end - adj_start < size) |
660 | continue; | | 665 | continue; |
661 | } | | 666 | } |
662 | } | | 667 | } |
663 | | | 668 | |
664 | node->mm = mm; | | 669 | node->mm = mm; |
665 | node->size = size; | | 670 | node->size = size; |
666 | node->start = adj_start; | | 671 | node->start = adj_start; |
667 | node->color = color; | | 672 | node->color = color; |
668 | node->hole_size = 0; | | 673 | node->hole_size = 0; |
669 | | | 674 | |
670 | __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); | | 675 | __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); |
671 | list_add(&node->node_list, &hole->node_list); | | 676 | list_add(&node->node_list, &hole->node_list); |
672 | #ifndef __NetBSD__ | | 677 | #ifndef __NetBSD__ |
673 | drm_mm_interval_tree_add_node(hole, node); | | 678 | drm_mm_interval_tree_add_node(hole, node); |
674 | #endif | | 679 | #endif |
675 | | | 680 | |
676 | rm_hole(hole); | | 681 | rm_hole(hole); |
677 | if (adj_start > hole_start) | | 682 | if (adj_start > hole_start) |
678 | add_hole(hole); | | 683 | add_hole(hole); |
679 | if (adj_start + size < hole_end) | | 684 | if (adj_start + size < hole_end) |
680 | add_hole(node); | | 685 | add_hole(node); |
681 | | | 686 | |
682 | save_stack(node); | | 687 | save_stack(node); |
683 | return 0; | | 688 | return 0; |
684 | } | | 689 | } |
685 | | | 690 | |
686 | return -ENOSPC; | | 691 | return -ENOSPC; |
687 | } | | 692 | } |
688 | EXPORT_SYMBOL(drm_mm_insert_node_in_range); | | 693 | EXPORT_SYMBOL(drm_mm_insert_node_in_range); |
689 | | | 694 | |
690 | static inline bool drm_mm_node_scanned_block(const struct drm_mm_node *node) | | 695 | static inline bool drm_mm_node_scanned_block(const struct drm_mm_node *node) |
691 | { | | 696 | { |
692 | return test_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); | | 697 | return test_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); |
693 | } | | 698 | } |
694 | | | 699 | |
695 | /** | | 700 | /** |
696 | * drm_mm_remove_node - Remove a memory node from the allocator. | | 701 | * drm_mm_remove_node - Remove a memory node from the allocator. |
697 | * @node: drm_mm_node to remove | | 702 | * @node: drm_mm_node to remove |
698 | * | | 703 | * |
699 | * This just removes a node from its drm_mm allocator. The node does not need to | | 704 | * This just removes a node from its drm_mm allocator. The node does not need to |
700 | * be cleared again before it can be re-inserted into this or any other drm_mm | | 705 | * be cleared again before it can be re-inserted into this or any other drm_mm |
701 | * allocator. It is a bug to call this function on a unallocated node. | | 706 | * allocator. It is a bug to call this function on a unallocated node. |
702 | */ | | 707 | */ |
703 | void drm_mm_remove_node(struct drm_mm_node *node) | | 708 | void drm_mm_remove_node(struct drm_mm_node *node) |
704 | { | | 709 | { |
705 | struct drm_mm *mm = node->mm; | | 710 | struct drm_mm *mm = node->mm; |
706 | struct drm_mm_node *prev_node; | | 711 | struct drm_mm_node *prev_node; |
707 | | | 712 | |
708 | DRM_MM_BUG_ON(!drm_mm_node_allocated(node)); | | 713 | DRM_MM_BUG_ON(!drm_mm_node_allocated(node)); |
709 | DRM_MM_BUG_ON(drm_mm_node_scanned_block(node)); | | 714 | DRM_MM_BUG_ON(drm_mm_node_scanned_block(node)); |
710 | | | 715 | |
711 | prev_node = list_prev_entry(node, node_list); | | 716 | prev_node = list_prev_entry(node, node_list); |
712 | | | 717 | |
713 | if (drm_mm_hole_follows(node)) | | 718 | if (drm_mm_hole_follows(node)) |
714 | rm_hole(node); | | 719 | rm_hole(node); |
715 | | | 720 | |
716 | #ifdef __NetBSD__ | | 721 | #ifdef __NetBSD__ |
717 | __USE(mm); | | 722 | __USE(mm); |
718 | #else | | 723 | #else |
719 | drm_mm_interval_tree_remove(node, &mm->interval_tree); | | 724 | drm_mm_interval_tree_remove(node, &mm->interval_tree); |
720 | #endif | | 725 | #endif |
721 | list_del(&node->node_list); | | 726 | list_del(&node->node_list); |
722 | | | 727 | |
723 | if (drm_mm_hole_follows(prev_node)) | | 728 | if (drm_mm_hole_follows(prev_node)) |
724 | rm_hole(prev_node); | | 729 | rm_hole(prev_node); |
725 | add_hole(prev_node); | | 730 | add_hole(prev_node); |
726 | | | 731 | |
727 | clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); | | 732 | clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &node->flags); |
728 | } | | 733 | } |
729 | EXPORT_SYMBOL(drm_mm_remove_node); | | 734 | EXPORT_SYMBOL(drm_mm_remove_node); |
730 | | | 735 | |
731 | /** | | 736 | /** |
732 | * drm_mm_replace_node - move an allocation from @old to @new | | 737 | * drm_mm_replace_node - move an allocation from @old to @new |
733 | * @old: drm_mm_node to remove from the allocator | | 738 | * @old: drm_mm_node to remove from the allocator |
734 | * @new: drm_mm_node which should inherit @old's allocation | | 739 | * @new: drm_mm_node which should inherit @old's allocation |
735 | * | | 740 | * |
736 | * This is useful for when drivers embed the drm_mm_node structure and hence | | 741 | * This is useful for when drivers embed the drm_mm_node structure and hence |
737 | * can't move allocations by reassigning pointers. It's a combination of remove | | 742 | * can't move allocations by reassigning pointers. It's a combination of remove |
738 | * and insert with the guarantee that the allocation start will match. | | 743 | * and insert with the guarantee that the allocation start will match. |
739 | */ | | 744 | */ |
740 | void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) | | 745 | void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) |
741 | { | | 746 | { |
742 | struct drm_mm *mm = old->mm; | | 747 | struct drm_mm *mm = old->mm; |
743 | | | 748 | |
744 | DRM_MM_BUG_ON(!drm_mm_node_allocated(old)); | | 749 | DRM_MM_BUG_ON(!drm_mm_node_allocated(old)); |
745 | | | 750 | |
746 | *new = *old; | | 751 | *new = *old; |
747 | | | 752 | |
748 | __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &new->flags); | | 753 | __set_bit(DRM_MM_NODE_ALLOCATED_BIT, &new->flags); |
749 | list_replace(&old->node_list, &new->node_list); | | 754 | list_replace(&old->node_list, &new->node_list); |
750 | #ifndef __NetBSD__ | | 755 | #ifndef __NetBSD__ |
751 | rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree); | | 756 | rb_replace_node_cached(&old->rb, &new->rb, &mm->interval_tree); |
752 | #endif | | 757 | #endif |
753 | | | 758 | |
754 | if (drm_mm_hole_follows(old)) { | | 759 | if (drm_mm_hole_follows(old)) { |
755 | list_replace(&old->hole_stack, &new->hole_stack); | | 760 | list_replace(&old->hole_stack, &new->hole_stack); |
756 | rb_replace_node_cached(&old->rb_hole_size, | | 761 | rb_replace_node_cached(&old->rb_hole_size, |
757 | &new->rb_hole_size, | | 762 | &new->rb_hole_size, |
758 | &mm->holes_size); | | 763 | &mm->holes_size); |
759 | rb_replace_node(&old->rb_hole_addr, | | 764 | rb_replace_node(&old->rb_hole_addr, |
760 | &new->rb_hole_addr, | | 765 | &new->rb_hole_addr, |
761 | &mm->holes_addr); | | 766 | &mm->holes_addr); |
762 | } | | 767 | } |
763 | | | 768 | |
764 | clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &old->flags); | | 769 | clear_bit_unlock(DRM_MM_NODE_ALLOCATED_BIT, &old->flags); |
765 | } | | 770 | } |
766 | EXPORT_SYMBOL(drm_mm_replace_node); | | 771 | EXPORT_SYMBOL(drm_mm_replace_node); |
767 | | | 772 | |
768 | /** | | 773 | /** |
769 | * DOC: lru scan roster | | 774 | * DOC: lru scan roster |
770 | * | | 775 | * |
771 | * Very often GPUs need to have continuous allocations for a given object. When | | 776 | * Very often GPUs need to have continuous allocations for a given object. When |
772 | * evicting objects to make space for a new one it is therefore not most | | 777 | * evicting objects to make space for a new one it is therefore not most |
773 | * efficient when we simply start to select all objects from the tail of an LRU | | 778 | * efficient when we simply start to select all objects from the tail of an LRU |
774 | * until there's a suitable hole: Especially for big objects or nodes that | | 779 | * until there's a suitable hole: Especially for big objects or nodes that |
775 | * otherwise have special allocation constraints there's a good chance we evict | | 780 | * otherwise have special allocation constraints there's a good chance we evict |
776 | * lots of (smaller) objects unnecessarily. | | 781 | * lots of (smaller) objects unnecessarily. |
777 | * | | 782 | * |
778 | * The DRM range allocator supports this use-case through the scanning | | 783 | * The DRM range allocator supports this use-case through the scanning |
779 | * interfaces. First a scan operation needs to be initialized with | | 784 | * interfaces. First a scan operation needs to be initialized with |
780 | * drm_mm_scan_init() or drm_mm_scan_init_with_range(). The driver adds | | 785 | * drm_mm_scan_init() or drm_mm_scan_init_with_range(). The driver adds |
781 | * objects to the roster, probably by walking an LRU list, but this can be | | 786 | * objects to the roster, probably by walking an LRU list, but this can be |
782 | * freely implemented. Eviction candiates are added using | | 787 | * freely implemented. Eviction candiates are added using |
783 | * drm_mm_scan_add_block() until a suitable hole is found or there are no | | 788 | * drm_mm_scan_add_block() until a suitable hole is found or there are no |
784 | * further evictable objects. Eviction roster metadata is tracked in &struct | | 789 | * further evictable objects. Eviction roster metadata is tracked in &struct |
785 | * drm_mm_scan. | | 790 | * drm_mm_scan. |
786 | * | | 791 | * |
787 | * The driver must walk through all objects again in exactly the reverse | | 792 | * The driver must walk through all objects again in exactly the reverse |
788 | * order to restore the allocator state. Note that while the allocator is used | | 793 | * order to restore the allocator state. Note that while the allocator is used |
789 | * in the scan mode no other operation is allowed. | | 794 | * in the scan mode no other operation is allowed. |
790 | * | | 795 | * |
791 | * Finally the driver evicts all objects selected (drm_mm_scan_remove_block() | | 796 | * Finally the driver evicts all objects selected (drm_mm_scan_remove_block() |
792 | * reported true) in the scan, and any overlapping nodes after color adjustment | | 797 | * reported true) in the scan, and any overlapping nodes after color adjustment |
793 | * (drm_mm_scan_color_evict()). Adding and removing an object is O(1), and | | 798 | * (drm_mm_scan_color_evict()). Adding and removing an object is O(1), and |
794 | * since freeing a node is also O(1) the overall complexity is | | 799 | * since freeing a node is also O(1) the overall complexity is |
795 | * O(scanned_objects). So like the free stack which needs to be walked before a | | 800 | * O(scanned_objects). So like the free stack which needs to be walked before a |
796 | * scan operation even begins this is linear in the number of objects. It | | 801 | * scan operation even begins this is linear in the number of objects. It |
797 | * doesn't seem to hurt too badly. | | 802 | * doesn't seem to hurt too badly. |
798 | */ | | 803 | */ |
799 | | | 804 | |
800 | /** | | 805 | /** |
801 | * drm_mm_scan_init_with_range - initialize range-restricted lru scanning | | 806 | * drm_mm_scan_init_with_range - initialize range-restricted lru scanning |
802 | * @scan: scan state | | 807 | * @scan: scan state |
803 | * @mm: drm_mm to scan | | 808 | * @mm: drm_mm to scan |
804 | * @size: size of the allocation | | 809 | * @size: size of the allocation |
805 | * @alignment: alignment of the allocation | | 810 | * @alignment: alignment of the allocation |
806 | * @color: opaque tag value to use for the allocation | | 811 | * @color: opaque tag value to use for the allocation |
807 | * @start: start of the allowed range for the allocation | | 812 | * @start: start of the allowed range for the allocation |
808 | * @end: end of the allowed range for the allocation | | 813 | * @end: end of the allowed range for the allocation |
809 | * @mode: fine-tune the allocation search and placement | | 814 | * @mode: fine-tune the allocation search and placement |
810 | * | | 815 | * |
811 | * This simply sets up the scanning routines with the parameters for the desired | | 816 | * This simply sets up the scanning routines with the parameters for the desired |
812 | * hole. | | 817 | * hole. |
813 | * | | 818 | * |
814 | * Warning: | | 819 | * Warning: |
815 | * As long as the scan list is non-empty, no other operations than | | 820 | * As long as the scan list is non-empty, no other operations than |
816 | * adding/removing nodes to/from the scan list are allowed. | | 821 | * adding/removing nodes to/from the scan list are allowed. |
817 | */ | | 822 | */ |
818 | void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, | | 823 | void drm_mm_scan_init_with_range(struct drm_mm_scan *scan, |
819 | struct drm_mm *mm, | | 824 | struct drm_mm *mm, |
820 | u64 size, | | 825 | u64 size, |
821 | u64 alignment, | | 826 | u64 alignment, |
822 | unsigned long color, | | 827 | unsigned long color, |
823 | u64 start, | | 828 | u64 start, |
824 | u64 end, | | 829 | u64 end, |
825 | enum drm_mm_insert_mode mode) | | 830 | enum drm_mm_insert_mode mode) |
826 | { | | 831 | { |
827 | DRM_MM_BUG_ON(start >= end); | | 832 | DRM_MM_BUG_ON(start >= end); |
828 | DRM_MM_BUG_ON(!size || size > end - start); | | 833 | DRM_MM_BUG_ON(!size || size > end - start); |
829 | DRM_MM_BUG_ON(mm->scan_active); | | 834 | DRM_MM_BUG_ON(mm->scan_active); |
830 | | | 835 | |
831 | scan->mm = mm; | | 836 | scan->mm = mm; |
832 | | | 837 | |
833 | if (alignment <= 1) | | 838 | if (alignment <= 1) |
834 | alignment = 0; | | 839 | alignment = 0; |
835 | | | 840 | |
836 | scan->color = color; | | 841 | scan->color = color; |
837 | scan->alignment = alignment; | | 842 | scan->alignment = alignment; |
838 | scan->remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0; | | 843 | scan->remainder_mask = is_power_of_2(alignment) ? alignment - 1 : 0; |
839 | scan->size = size; | | 844 | scan->size = size; |
840 | scan->mode = mode; | | 845 | scan->mode = mode; |
841 | | | 846 | |
842 | DRM_MM_BUG_ON(end <= start); | | 847 | DRM_MM_BUG_ON(end <= start); |
843 | scan->range_start = start; | | 848 | scan->range_start = start; |
844 | scan->range_end = end; | | 849 | scan->range_end = end; |
845 | | | 850 | |
846 | scan->hit_start = U64_MAX; | | 851 | scan->hit_start = U64_MAX; |
847 | scan->hit_end = 0; | | 852 | scan->hit_end = 0; |
848 | } | | 853 | } |
849 | EXPORT_SYMBOL(drm_mm_scan_init_with_range); | | 854 | EXPORT_SYMBOL(drm_mm_scan_init_with_range); |
850 | | | 855 | |
851 | /** | | 856 | /** |
852 | * drm_mm_scan_add_block - add a node to the scan list | | 857 | * drm_mm_scan_add_block - add a node to the scan list |
853 | * @scan: the active drm_mm scanner | | 858 | * @scan: the active drm_mm scanner |
854 | * @node: drm_mm_node to add | | 859 | * @node: drm_mm_node to add |
855 | * | | 860 | * |
856 | * Add a node to the scan list that might be freed to make space for the desired | | 861 | * Add a node to the scan list that might be freed to make space for the desired |
857 | * hole. | | 862 | * hole. |
858 | * | | 863 | * |
859 | * Returns: | | 864 | * Returns: |
860 | * True if a hole has been found, false otherwise. | | 865 | * True if a hole has been found, false otherwise. |
861 | */ | | 866 | */ |
862 | bool drm_mm_scan_add_block(struct drm_mm_scan *scan, | | 867 | bool drm_mm_scan_add_block(struct drm_mm_scan *scan, |
863 | struct drm_mm_node *node) | | 868 | struct drm_mm_node *node) |
864 | { | | 869 | { |
865 | struct drm_mm *mm = scan->mm; | | 870 | struct drm_mm *mm = scan->mm; |
866 | struct drm_mm_node *hole; | | 871 | struct drm_mm_node *hole; |
867 | u64 hole_start, hole_end; | | 872 | u64 hole_start, hole_end; |
868 | u64 col_start, col_end; | | 873 | u64 col_start, col_end; |
869 | u64 adj_start, adj_end; | | 874 | u64 adj_start, adj_end; |
870 | | | 875 | |
871 | DRM_MM_BUG_ON(node->mm != mm); | | 876 | DRM_MM_BUG_ON(node->mm != mm); |
872 | DRM_MM_BUG_ON(!drm_mm_node_allocated(node)); | | 877 | DRM_MM_BUG_ON(!drm_mm_node_allocated(node)); |
873 | DRM_MM_BUG_ON(drm_mm_node_scanned_block(node)); | | 878 | DRM_MM_BUG_ON(drm_mm_node_scanned_block(node)); |
874 | __set_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); | | 879 | __set_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); |
875 | mm->scan_active++; | | 880 | mm->scan_active++; |
876 | | | 881 | |
877 | /* Remove this block from the node_list so that we enlarge the hole | | 882 | /* Remove this block from the node_list so that we enlarge the hole |
878 | * (distance between the end of our previous node and the start of | | 883 | * (distance between the end of our previous node and the start of |
879 | * or next), without poisoning the link so that we can restore it | | 884 | * or next), without poisoning the link so that we can restore it |
880 | * later in drm_mm_scan_remove_block(). | | 885 | * later in drm_mm_scan_remove_block(). |
881 | */ | | 886 | */ |
882 | hole = list_prev_entry(node, node_list); | | 887 | hole = list_prev_entry(node, node_list); |
883 | DRM_MM_BUG_ON(list_next_entry(hole, node_list) != node); | | 888 | DRM_MM_BUG_ON(list_next_entry(hole, node_list) != node); |
884 | __list_del_entry(&node->node_list); | | 889 | __list_del_entry(&node->node_list); |
885 | | | 890 | |
886 | hole_start = __drm_mm_hole_node_start(hole); | | 891 | hole_start = __drm_mm_hole_node_start(hole); |
887 | hole_end = __drm_mm_hole_node_end(hole); | | 892 | hole_end = __drm_mm_hole_node_end(hole); |
888 | | | 893 | |
889 | col_start = hole_start; | | 894 | col_start = hole_start; |
890 | col_end = hole_end; | | 895 | col_end = hole_end; |
891 | if (mm->color_adjust) | | 896 | if (mm->color_adjust) |
892 | mm->color_adjust(hole, scan->color, &col_start, &col_end); | | 897 | mm->color_adjust(hole, scan->color, &col_start, &col_end); |
893 | | | 898 | |
894 | adj_start = max(col_start, scan->range_start); | | 899 | adj_start = max(col_start, scan->range_start); |
895 | adj_end = min(col_end, scan->range_end); | | 900 | adj_end = min(col_end, scan->range_end); |
896 | if (adj_end <= adj_start || adj_end - adj_start < scan->size) | | 901 | if (adj_end <= adj_start || adj_end - adj_start < scan->size) |
897 | return false; | | 902 | return false; |
898 | | | 903 | |
899 | if (scan->mode == DRM_MM_INSERT_HIGH) | | 904 | if (scan->mode == DRM_MM_INSERT_HIGH) |
900 | adj_start = adj_end - scan->size; | | 905 | adj_start = adj_end - scan->size; |
901 | | | 906 | |
902 | if (scan->alignment) { | | 907 | if (scan->alignment) { |
903 | u64 rem; | | 908 | u64 rem; |
904 | | | 909 | |
905 | if (likely(scan->remainder_mask)) | | 910 | if (likely(scan->remainder_mask)) |
906 | rem = adj_start & scan->remainder_mask; | | 911 | rem = adj_start & scan->remainder_mask; |
907 | else | | 912 | else |
908 | div64_u64_rem(adj_start, scan->alignment, &rem); | | 913 | div64_u64_rem(adj_start, scan->alignment, &rem); |
909 | if (rem) { | | 914 | if (rem) { |
910 | adj_start -= rem; | | 915 | adj_start -= rem; |
911 | if (scan->mode != DRM_MM_INSERT_HIGH) | | 916 | if (scan->mode != DRM_MM_INSERT_HIGH) |
912 | adj_start += scan->alignment; | | 917 | adj_start += scan->alignment; |
913 | if (adj_start < max(col_start, scan->range_start) || | | 918 | if (adj_start < max(col_start, scan->range_start) || |
914 | min(col_end, scan->range_end) - adj_start < scan->size) | | 919 | min(col_end, scan->range_end) - adj_start < scan->size) |
915 | return false; | | 920 | return false; |
916 | | | 921 | |
917 | if (adj_end <= adj_start || | | 922 | if (adj_end <= adj_start || |
918 | adj_end - adj_start < scan->size) | | 923 | adj_end - adj_start < scan->size) |
919 | return false; | | 924 | return false; |
920 | } | | 925 | } |
921 | } | | 926 | } |
922 | | | 927 | |
923 | scan->hit_start = adj_start; | | 928 | scan->hit_start = adj_start; |
924 | scan->hit_end = adj_start + scan->size; | | 929 | scan->hit_end = adj_start + scan->size; |
925 | | | 930 | |
926 | DRM_MM_BUG_ON(scan->hit_start >= scan->hit_end); | | 931 | DRM_MM_BUG_ON(scan->hit_start >= scan->hit_end); |
927 | DRM_MM_BUG_ON(scan->hit_start < hole_start); | | 932 | DRM_MM_BUG_ON(scan->hit_start < hole_start); |
928 | DRM_MM_BUG_ON(scan->hit_end > hole_end); | | 933 | DRM_MM_BUG_ON(scan->hit_end > hole_end); |
929 | | | 934 | |
930 | return true; | | 935 | return true; |
931 | } | | 936 | } |
932 | EXPORT_SYMBOL(drm_mm_scan_add_block); | | 937 | EXPORT_SYMBOL(drm_mm_scan_add_block); |
933 | | | 938 | |
934 | /** | | 939 | /** |
935 | * drm_mm_scan_remove_block - remove a node from the scan list | | 940 | * drm_mm_scan_remove_block - remove a node from the scan list |
936 | * @scan: the active drm_mm scanner | | 941 | * @scan: the active drm_mm scanner |
937 | * @node: drm_mm_node to remove | | 942 | * @node: drm_mm_node to remove |
938 | * | | 943 | * |
939 | * Nodes **must** be removed in exactly the reverse order from the scan list as | | 944 | * Nodes **must** be removed in exactly the reverse order from the scan list as |
940 | * they have been added (e.g. using list_add() as they are added and then | | 945 | * they have been added (e.g. using list_add() as they are added and then |
941 | * list_for_each() over that eviction list to remove), otherwise the internal | | 946 | * list_for_each() over that eviction list to remove), otherwise the internal |
942 | * state of the memory manager will be corrupted. | | 947 | * state of the memory manager will be corrupted. |
943 | * | | 948 | * |
944 | * When the scan list is empty, the selected memory nodes can be freed. An | | 949 | * When the scan list is empty, the selected memory nodes can be freed. An |
945 | * immediately following drm_mm_insert_node_in_range_generic() or one of the | | 950 | * immediately following drm_mm_insert_node_in_range_generic() or one of the |
946 | * simpler versions of that function with !DRM_MM_SEARCH_BEST will then return | | 951 | * simpler versions of that function with !DRM_MM_SEARCH_BEST will then return |
947 | * the just freed block (because it's at the top of the free_stack list). | | 952 | * the just freed block (because it's at the top of the free_stack list). |
948 | * | | 953 | * |
949 | * Returns: | | 954 | * Returns: |
950 | * True if this block should be evicted, false otherwise. Will always | | 955 | * True if this block should be evicted, false otherwise. Will always |
951 | * return false when no hole has been found. | | 956 | * return false when no hole has been found. |
952 | */ | | 957 | */ |
953 | bool drm_mm_scan_remove_block(struct drm_mm_scan *scan, | | 958 | bool drm_mm_scan_remove_block(struct drm_mm_scan *scan, |
954 | struct drm_mm_node *node) | | 959 | struct drm_mm_node *node) |
955 | { | | 960 | { |
956 | struct drm_mm_node *prev_node; | | 961 | struct drm_mm_node *prev_node; |
957 | | | 962 | |
958 | DRM_MM_BUG_ON(node->mm != scan->mm); | | 963 | DRM_MM_BUG_ON(node->mm != scan->mm); |
959 | DRM_MM_BUG_ON(!drm_mm_node_scanned_block(node)); | | 964 | DRM_MM_BUG_ON(!drm_mm_node_scanned_block(node)); |
960 | __clear_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); | | 965 | __clear_bit(DRM_MM_NODE_SCANNED_BIT, &node->flags); |
961 | | | 966 | |
962 | DRM_MM_BUG_ON(!node->mm->scan_active); | | 967 | DRM_MM_BUG_ON(!node->mm->scan_active); |
963 | node->mm->scan_active--; | | 968 | node->mm->scan_active--; |
964 | | | 969 | |
965 | /* During drm_mm_scan_add_block() we decoupled this node leaving | | 970 | /* During drm_mm_scan_add_block() we decoupled this node leaving |
966 | * its pointers intact. Now that the caller is walking back along | | 971 | * its pointers intact. Now that the caller is walking back along |
967 | * the eviction list we can restore this block into its rightful | | 972 | * the eviction list we can restore this block into its rightful |
968 | * place on the full node_list. To confirm that the caller is walking | | 973 | * place on the full node_list. To confirm that the caller is walking |
969 | * backwards correctly we check that prev_node->next == node->next, | | 974 | * backwards correctly we check that prev_node->next == node->next, |
970 | * i.e. both believe the same node should be on the other side of the | | 975 | * i.e. both believe the same node should be on the other side of the |
971 | * hole. | | 976 | * hole. |
972 | */ | | 977 | */ |
973 | prev_node = list_prev_entry(node, node_list); | | 978 | prev_node = list_prev_entry(node, node_list); |
974 | DRM_MM_BUG_ON(list_next_entry(prev_node, node_list) != | | 979 | DRM_MM_BUG_ON(list_next_entry(prev_node, node_list) != |
975 | list_next_entry(node, node_list)); | | 980 | list_next_entry(node, node_list)); |
976 | list_add(&node->node_list, &prev_node->node_list); | | 981 | list_add(&node->node_list, &prev_node->node_list); |
977 | | | 982 | |
978 | return (node->start + node->size > scan->hit_start && | | 983 | return (node->start + node->size > scan->hit_start && |
979 | node->start < scan->hit_end); | | 984 | node->start < scan->hit_end); |
980 | } | | 985 | } |
981 | EXPORT_SYMBOL(drm_mm_scan_remove_block); | | 986 | EXPORT_SYMBOL(drm_mm_scan_remove_block); |
982 | | | 987 | |
983 | /** | | 988 | /** |
984 | * drm_mm_scan_color_evict - evict overlapping nodes on either side of hole | | 989 | * drm_mm_scan_color_evict - evict overlapping nodes on either side of hole |
985 | * @scan: drm_mm scan with target hole | | 990 | * @scan: drm_mm scan with target hole |
986 | * | | 991 | * |
987 | * After completing an eviction scan and removing the selected nodes, we may | | 992 | * After completing an eviction scan and removing the selected nodes, we may |
988 | * need to remove a few more nodes from either side of the target hole if | | 993 | * need to remove a few more nodes from either side of the target hole if |
989 | * mm.color_adjust is being used. | | 994 | * mm.color_adjust is being used. |
990 | * | | 995 | * |
991 | * Returns: | | 996 | * Returns: |
992 | * A node to evict, or NULL if there are no overlapping nodes. | | 997 | * A node to evict, or NULL if there are no overlapping nodes. |
993 | */ | | 998 | */ |
994 | struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan) | | 999 | struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan) |
995 | { | | 1000 | { |
996 | struct drm_mm *mm = scan->mm; | | 1001 | struct drm_mm *mm = scan->mm; |
997 | struct drm_mm_node *hole; | | 1002 | struct drm_mm_node *hole; |
998 | u64 hole_start, hole_end; | | 1003 | u64 hole_start, hole_end; |
999 | | | 1004 | |
1000 | DRM_MM_BUG_ON(list_empty(&mm->hole_stack)); | | 1005 | DRM_MM_BUG_ON(list_empty(&mm->hole_stack)); |
1001 | | | 1006 | |
1002 | if (!mm->color_adjust) | | 1007 | if (!mm->color_adjust) |
1003 | return NULL; | | 1008 | return NULL; |
1004 | | | 1009 | |
1005 | /* | | 1010 | /* |
1006 | * The hole found during scanning should ideally be the first element | | 1011 | * The hole found during scanning should ideally be the first element |
1007 | * in the hole_stack list, but due to side-effects in the driver it | | 1012 | * in the hole_stack list, but due to side-effects in the driver it |
1008 | * may not be. | | 1013 | * may not be. |
1009 | */ | | 1014 | */ |
1010 | list_for_each_entry(hole, &mm->hole_stack, hole_stack) { | | 1015 | list_for_each_entry(hole, &mm->hole_stack, hole_stack) { |
1011 | hole_start = __drm_mm_hole_node_start(hole); | | 1016 | hole_start = __drm_mm_hole_node_start(hole); |
1012 | hole_end = hole_start + hole->hole_size; | | 1017 | hole_end = hole_start + hole->hole_size; |
1013 | | | 1018 | |
1014 | if (hole_start <= scan->hit_start && | | 1019 | if (hole_start <= scan->hit_start && |
1015 | hole_end >= scan->hit_end) | | 1020 | hole_end >= scan->hit_end) |
1016 | break; | | 1021 | break; |
1017 | } | | 1022 | } |
1018 | | | 1023 | |
1019 | /* We should only be called after we found the hole previously */ | | 1024 | /* We should only be called after we found the hole previously */ |
1020 | DRM_MM_BUG_ON(&hole->hole_stack == &mm->hole_stack); | | 1025 | DRM_MM_BUG_ON(&hole->hole_stack == &mm->hole_stack); |
1021 | if (unlikely(&hole->hole_stack == &mm->hole_stack)) | | 1026 | if (unlikely(&hole->hole_stack == &mm->hole_stack)) |
1022 | return NULL; | | 1027 | return NULL; |
1023 | | | 1028 | |
1024 | DRM_MM_BUG_ON(hole_start > scan->hit_start); | | 1029 | DRM_MM_BUG_ON(hole_start > scan->hit_start); |
1025 | DRM_MM_BUG_ON(hole_end < scan->hit_end); | | 1030 | DRM_MM_BUG_ON(hole_end < scan->hit_end); |
1026 | | | 1031 | |
1027 | mm->color_adjust(hole, scan->color, &hole_start, &hole_end); | | 1032 | mm->color_adjust(hole, scan->color, &hole_start, &hole_end); |
1028 | if (hole_start > scan->hit_start) | | 1033 | if (hole_start > scan->hit_start) |
1029 | return hole; | | 1034 | return hole; |
1030 | if (hole_end < scan->hit_end) | | 1035 | if (hole_end < scan->hit_end) |
1031 | return list_next_entry(hole, node_list); | | 1036 | return list_next_entry(hole, node_list); |
1032 | | | 1037 | |
1033 | return NULL; | | 1038 | return NULL; |
1034 | } | | 1039 | } |
1035 | EXPORT_SYMBOL(drm_mm_scan_color_evict); | | 1040 | EXPORT_SYMBOL(drm_mm_scan_color_evict); |
1036 | | | 1041 | |
1037 | /** | | 1042 | /** |
1038 | * drm_mm_init - initialize a drm-mm allocator | | 1043 | * drm_mm_init - initialize a drm-mm allocator |
1039 | * @mm: the drm_mm structure to initialize | | 1044 | * @mm: the drm_mm structure to initialize |
1040 | * @start: start of the range managed by @mm | | 1045 | * @start: start of the range managed by @mm |
1041 | * @size: end of the range managed by @mm | | 1046 | * @size: end of the range managed by @mm |
1042 | * | | 1047 | * |
1043 | * Note that @mm must be cleared to 0 before calling this function. | | 1048 | * Note that @mm must be cleared to 0 before calling this function. |
1044 | */ | | 1049 | */ |
1045 | void drm_mm_init(struct drm_mm *mm, u64 start, u64 size) | | 1050 | void drm_mm_init(struct drm_mm *mm, u64 start, u64 size) |
1046 | { | | 1051 | { |
1047 | DRM_MM_BUG_ON(start + size <= start); | | 1052 | DRM_MM_BUG_ON(start + size <= start); |
1048 | | | 1053 | |
1049 | mm->color_adjust = NULL; | | 1054 | mm->color_adjust = NULL; |
1050 | | | 1055 | |
1051 | INIT_LIST_HEAD(&mm->hole_stack); | | 1056 | INIT_LIST_HEAD(&mm->hole_stack); |
1052 | #ifdef __NetBSD__ | | 1057 | #ifdef __NetBSD__ |
1053 | /* XXX interval tree */ | | 1058 | /* XXX interval tree */ |
1054 | rb_tree_init(&mm->holes_size.rb_root.rbr_tree, &holes_size_rb_ops); | | 1059 | rb_tree_init(&mm->holes_size.rb_root.rbr_tree, &holes_size_rb_ops); |
1055 | rb_tree_init(&mm->holes_addr.rbr_tree, &holes_addr_rb_ops); | | 1060 | rb_tree_init(&mm->holes_addr.rbr_tree, &holes_addr_rb_ops); |
1056 | #else | | 1061 | #else |
1057 | mm->interval_tree = RB_ROOT_CACHED; | | 1062 | mm->interval_tree = RB_ROOT_CACHED; |
1058 | mm->holes_size = RB_ROOT_CACHED; | | 1063 | mm->holes_size = RB_ROOT_CACHED; |
1059 | mm->holes_addr = RB_ROOT; | | 1064 | mm->holes_addr = RB_ROOT; |
1060 | #endif | | 1065 | #endif |
1061 | | | 1066 | |
1062 | /* Clever trick to avoid a special case in the free hole tracking. */ | | 1067 | /* Clever trick to avoid a special case in the free hole tracking. */ |
1063 | INIT_LIST_HEAD(&mm->head_node.node_list); | | 1068 | INIT_LIST_HEAD(&mm->head_node.node_list); |
1064 | mm->head_node.flags = 0; | | 1069 | mm->head_node.flags = 0; |
1065 | mm->head_node.mm = mm; | | 1070 | mm->head_node.mm = mm; |
1066 | mm->head_node.start = start + size; | | 1071 | mm->head_node.start = start + size; |
1067 | mm->head_node.size = -size; | | 1072 | mm->head_node.size = -size; |
1068 | add_hole(&mm->head_node); | | 1073 | add_hole(&mm->head_node); |
1069 | | | 1074 | |
1070 | mm->scan_active = 0; | | 1075 | mm->scan_active = 0; |
1071 | } | | 1076 | } |
1072 | EXPORT_SYMBOL(drm_mm_init); | | 1077 | EXPORT_SYMBOL(drm_mm_init); |
1073 | | | 1078 | |
1074 | /** | | 1079 | /** |
1075 | * drm_mm_takedown - clean up a drm_mm allocator | | 1080 | * drm_mm_takedown - clean up a drm_mm allocator |
1076 | * @mm: drm_mm allocator to clean up | | 1081 | * @mm: drm_mm allocator to clean up |
1077 | * | | 1082 | * |
1078 | * Note that it is a bug to call this function on an allocator which is not | | 1083 | * Note that it is a bug to call this function on an allocator which is not |
1079 | * clean. | | 1084 | * clean. |
1080 | */ | | 1085 | */ |
1081 | void drm_mm_takedown(struct drm_mm *mm) | | 1086 | void drm_mm_takedown(struct drm_mm *mm) |
1082 | { | | 1087 | { |
1083 | if (WARN(!drm_mm_clean(mm), | | 1088 | if (WARN(!drm_mm_clean(mm), |
1084 | "Memory manager not clean during takedown.\n")) | | 1089 | "Memory manager not clean during takedown.\n")) |
1085 | show_leaks(mm); | | 1090 | show_leaks(mm); |
1086 | } | | 1091 | } |
1087 | EXPORT_SYMBOL(drm_mm_takedown); | | 1092 | EXPORT_SYMBOL(drm_mm_takedown); |
1088 | | | 1093 | |
1089 | static u64 drm_mm_dump_hole(struct drm_printer *p, const struct drm_mm_node *entry) | | 1094 | static u64 drm_mm_dump_hole(struct drm_printer *p, const struct drm_mm_node *entry) |
1090 | { | | 1095 | { |
1091 | u64 start, size; | | 1096 | u64 start, size; |
1092 | | | 1097 | |
1093 | size = entry->hole_size; | | 1098 | size = entry->hole_size; |
1094 | if (size) { | | 1099 | if (size) { |
1095 | start = drm_mm_hole_node_start(entry); | | 1100 | start = drm_mm_hole_node_start(entry); |
1096 | drm_printf(p, "%#018"PRIx64"-%#018"PRIx64": %"PRIu64": free\n", | | 1101 | drm_printf(p, "%#018"PRIx64"-%#018"PRIx64": %"PRIu64": free\n", |
1097 | start, start + size, size); | | 1102 | start, start + size, size); |
1098 | } | | 1103 | } |
1099 | | | 1104 | |
1100 | return size; | | 1105 | return size; |
1101 | } | | 1106 | } |
1102 | /** | | 1107 | /** |
1103 | * drm_mm_print - print allocator state | | 1108 | * drm_mm_print - print allocator state |
1104 | * @mm: drm_mm allocator to print | | 1109 | * @mm: drm_mm allocator to print |
1105 | * @p: DRM printer to use | | 1110 | * @p: DRM printer to use |
1106 | */ | | 1111 | */ |
1107 | void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p) | | 1112 | void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p) |
1108 | { | | 1113 | { |
1109 | const struct drm_mm_node *entry; | | 1114 | const struct drm_mm_node *entry; |
1110 | u64 total_used = 0, total_free = 0, total = 0; | | 1115 | u64 total_used = 0, total_free = 0, total = 0; |
1111 | | | 1116 | |
1112 | total_free += drm_mm_dump_hole(p, &mm->head_node); | | 1117 | total_free += drm_mm_dump_hole(p, &mm->head_node); |
1113 | | | 1118 | |
1114 | drm_mm_for_each_node(entry, mm) { | | 1119 | drm_mm_for_each_node(entry, mm) { |
1115 | drm_printf(p, "%#018"PRIx64"-%#018"PRIx64": %"PRIu64": used\n", entry->start, | | 1120 | drm_printf(p, "%#018"PRIx64"-%#018"PRIx64": %"PRIu64": used\n", entry->start, |
1116 | entry->start + entry->size, entry->size); | | 1121 | entry->start + entry->size, entry->size); |
1117 | total_used += entry->size; | | 1122 | total_used += entry->size; |
1118 | total_free += drm_mm_dump_hole(p, entry); | | 1123 | total_free += drm_mm_dump_hole(p, entry); |
1119 | } | | 1124 | } |
1120 | total = total_free + total_used; | | 1125 | total = total_free + total_used; |
1121 | | | 1126 | |
1122 | drm_printf(p, "total: %"PRIu64", used %"PRIu64" free %"PRIu64"\n", total, | | 1127 | drm_printf(p, "total: %"PRIu64", used %"PRIu64" free %"PRIu64"\n", total, |
1123 | total_used, total_free); | | 1128 | total_used, total_free); |
1124 | } | | 1129 | } |
1125 | EXPORT_SYMBOL(drm_mm_print); | | 1130 | EXPORT_SYMBOL(drm_mm_print); |