1 // SPDX-License-Identifier: GPL-2.0 OR MIT
2 /*
3 * Copyright 2011 Red Hat Inc.
4 * Copyright 2023 Intel Corporation.
5 * All Rights Reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sub license, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
18 * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
21 * USE OR OTHER DEALINGS IN THE SOFTWARE.
22 *
23 * The above copyright notice and this permission notice (including the
24 * next paragraph) shall be included in all copies or substantial portions
25 * of the Software.
26 *
27 */
28 /* Algorithm:
29 *
30 * We store the last allocated bo in "hole", we always try to allocate
31 * after the last allocated bo. Principle is that in a linear GPU ring
32 * progression was is after last is the oldest bo we allocated and thus
33 * the first one that should no longer be in use by the GPU.
34 *
35 * If it's not the case we skip over the bo after last to the closest
36 * done bo if such one exist. If none exist and we are not asked to
37 * block we report failure to allocate.
38 *
39 * If we are asked to block we wait on all the oldest fence of all
40 * rings. We just wait for any of those fence to complete.
41 */
42
43 #include <drm/drm_suballoc.h>
44 #include <drm/drm_print.h>
45 #include <linux/slab.h>
46 #include <linux/sched.h>
47 #include <linux/wait.h>
48 #include <linux/dma-fence.h>
49
50 static void drm_suballoc_remove_locked(struct drm_suballoc *sa);
51 static void drm_suballoc_try_free(struct drm_suballoc_manager *sa_manager);
52
53 /**
54 * drm_suballoc_manager_init() - Initialise the drm_suballoc_manager
55 * @sa_manager: pointer to the sa_manager
56 * @size: number of bytes we want to suballocate
57 * @align: alignment for each suballocated chunk
58 *
59 * Prepares the suballocation manager for suballocations.
60 */
drm_suballoc_manager_init(struct drm_suballoc_manager * sa_manager,size_t size,size_t align)61 void drm_suballoc_manager_init(struct drm_suballoc_manager *sa_manager,
62 size_t size, size_t align)
63 {
64 unsigned int i;
65
66 BUILD_BUG_ON(!is_power_of_2(DRM_SUBALLOC_MAX_QUEUES));
67
68 if (!align)
69 align = 1;
70
71 /* alignment must be a power of 2 */
72 if (WARN_ON_ONCE(align & (align - 1)))
73 align = roundup_pow_of_two(align);
74
75 init_waitqueue_head(&sa_manager->wq);
76 sa_manager->size = size;
77 sa_manager->align = align;
78 sa_manager->hole = &sa_manager->olist;
79 INIT_LIST_HEAD(&sa_manager->olist);
80 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
81 INIT_LIST_HEAD(&sa_manager->flist[i]);
82 }
83 EXPORT_SYMBOL(drm_suballoc_manager_init);
84
85 /**
86 * drm_suballoc_manager_fini() - Destroy the drm_suballoc_manager
87 * @sa_manager: pointer to the sa_manager
88 *
89 * Cleans up the suballocation manager after use. All fences added
90 * with drm_suballoc_free() must be signaled, or we cannot clean up
91 * the entire manager.
92 */
drm_suballoc_manager_fini(struct drm_suballoc_manager * sa_manager)93 void drm_suballoc_manager_fini(struct drm_suballoc_manager *sa_manager)
94 {
95 struct drm_suballoc *sa, *tmp;
96
97 if (!sa_manager->size)
98 return;
99
100 if (!list_empty(&sa_manager->olist)) {
101 sa_manager->hole = &sa_manager->olist;
102 drm_suballoc_try_free(sa_manager);
103 if (!list_empty(&sa_manager->olist))
104 DRM_ERROR("sa_manager is not empty, clearing anyway\n");
105 }
106 list_for_each_entry_safe(sa, tmp, &sa_manager->olist, olist) {
107 drm_suballoc_remove_locked(sa);
108 }
109
110 sa_manager->size = 0;
111 }
112 EXPORT_SYMBOL(drm_suballoc_manager_fini);
113
drm_suballoc_remove_locked(struct drm_suballoc * sa)114 static void drm_suballoc_remove_locked(struct drm_suballoc *sa)
115 {
116 struct drm_suballoc_manager *sa_manager = sa->manager;
117
118 if (sa_manager->hole == &sa->olist)
119 sa_manager->hole = sa->olist.prev;
120
121 list_del_init(&sa->olist);
122 list_del_init(&sa->flist);
123 dma_fence_put(sa->fence);
124 kfree(sa);
125 }
126
drm_suballoc_try_free(struct drm_suballoc_manager * sa_manager)127 static void drm_suballoc_try_free(struct drm_suballoc_manager *sa_manager)
128 {
129 struct drm_suballoc *sa, *tmp;
130
131 if (sa_manager->hole->next == &sa_manager->olist)
132 return;
133
134 sa = list_entry(sa_manager->hole->next, struct drm_suballoc, olist);
135 list_for_each_entry_safe_from(sa, tmp, &sa_manager->olist, olist) {
136 if (!sa->fence || !dma_fence_is_signaled(sa->fence))
137 return;
138
139 drm_suballoc_remove_locked(sa);
140 }
141 }
142
drm_suballoc_hole_soffset(struct drm_suballoc_manager * sa_manager)143 static size_t drm_suballoc_hole_soffset(struct drm_suballoc_manager *sa_manager)
144 {
145 struct list_head *hole = sa_manager->hole;
146
147 if (hole != &sa_manager->olist)
148 return list_entry(hole, struct drm_suballoc, olist)->eoffset;
149
150 return 0;
151 }
152
drm_suballoc_hole_eoffset(struct drm_suballoc_manager * sa_manager)153 static size_t drm_suballoc_hole_eoffset(struct drm_suballoc_manager *sa_manager)
154 {
155 struct list_head *hole = sa_manager->hole;
156
157 if (hole->next != &sa_manager->olist)
158 return list_entry(hole->next, struct drm_suballoc, olist)->soffset;
159 return sa_manager->size;
160 }
161
drm_suballoc_try_alloc(struct drm_suballoc_manager * sa_manager,struct drm_suballoc * sa,size_t size,size_t align)162 static bool drm_suballoc_try_alloc(struct drm_suballoc_manager *sa_manager,
163 struct drm_suballoc *sa,
164 size_t size, size_t align)
165 {
166 size_t soffset, eoffset, wasted;
167
168 soffset = drm_suballoc_hole_soffset(sa_manager);
169 eoffset = drm_suballoc_hole_eoffset(sa_manager);
170 wasted = round_up(soffset, align) - soffset;
171
172 if ((eoffset - soffset) >= (size + wasted)) {
173 soffset += wasted;
174
175 sa->manager = sa_manager;
176 sa->soffset = soffset;
177 sa->eoffset = soffset + size;
178 list_add(&sa->olist, sa_manager->hole);
179 INIT_LIST_HEAD(&sa->flist);
180 sa_manager->hole = &sa->olist;
181 return true;
182 }
183 return false;
184 }
185
__drm_suballoc_event(struct drm_suballoc_manager * sa_manager,size_t size,size_t align)186 static bool __drm_suballoc_event(struct drm_suballoc_manager *sa_manager,
187 size_t size, size_t align)
188 {
189 size_t soffset, eoffset, wasted;
190 unsigned int i;
191
192 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
193 if (!list_empty(&sa_manager->flist[i]))
194 return true;
195
196 soffset = drm_suballoc_hole_soffset(sa_manager);
197 eoffset = drm_suballoc_hole_eoffset(sa_manager);
198 wasted = round_up(soffset, align) - soffset;
199
200 return ((eoffset - soffset) >= (size + wasted));
201 }
202
203 /**
204 * drm_suballoc_event() - Check if we can stop waiting
205 * @sa_manager: pointer to the sa_manager
206 * @size: number of bytes we want to allocate
207 * @align: alignment we need to match
208 *
209 * Return: true if either there is a fence we can wait for or
210 * enough free memory to satisfy the allocation directly.
211 * false otherwise.
212 */
drm_suballoc_event(struct drm_suballoc_manager * sa_manager,size_t size,size_t align)213 static bool drm_suballoc_event(struct drm_suballoc_manager *sa_manager,
214 size_t size, size_t align)
215 {
216 bool ret;
217
218 spin_lock(&sa_manager->wq.lock);
219 ret = __drm_suballoc_event(sa_manager, size, align);
220 spin_unlock(&sa_manager->wq.lock);
221 return ret;
222 }
223
drm_suballoc_next_hole(struct drm_suballoc_manager * sa_manager,struct dma_fence ** fences,unsigned int * tries)224 static bool drm_suballoc_next_hole(struct drm_suballoc_manager *sa_manager,
225 struct dma_fence **fences,
226 unsigned int *tries)
227 {
228 struct drm_suballoc *best_bo = NULL;
229 unsigned int i, best_idx;
230 size_t soffset, best, tmp;
231
232 /* if hole points to the end of the buffer */
233 if (sa_manager->hole->next == &sa_manager->olist) {
234 /* try again with its beginning */
235 sa_manager->hole = &sa_manager->olist;
236 return true;
237 }
238
239 soffset = drm_suballoc_hole_soffset(sa_manager);
240 /* to handle wrap around we add sa_manager->size */
241 best = sa_manager->size * 2;
242 /* go over all fence list and try to find the closest sa
243 * of the current last
244 */
245 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i) {
246 struct drm_suballoc *sa;
247
248 fences[i] = NULL;
249
250 if (list_empty(&sa_manager->flist[i]))
251 continue;
252
253 sa = list_first_entry(&sa_manager->flist[i],
254 struct drm_suballoc, flist);
255
256 if (!dma_fence_is_signaled(sa->fence)) {
257 fences[i] = sa->fence;
258 continue;
259 }
260
261 /* limit the number of tries each freelist gets */
262 if (tries[i] > 2)
263 continue;
264
265 tmp = sa->soffset;
266 if (tmp < soffset) {
267 /* wrap around, pretend it's after */
268 tmp += sa_manager->size;
269 }
270 tmp -= soffset;
271 if (tmp < best) {
272 /* this sa bo is the closest one */
273 best = tmp;
274 best_idx = i;
275 best_bo = sa;
276 }
277 }
278
279 if (best_bo) {
280 ++tries[best_idx];
281 sa_manager->hole = best_bo->olist.prev;
282
283 /*
284 * We know that this one is signaled,
285 * so it's safe to remove it.
286 */
287 drm_suballoc_remove_locked(best_bo);
288 return true;
289 }
290 return false;
291 }
292
293 /**
294 * drm_suballoc_new() - Make a suballocation.
295 * @sa_manager: pointer to the sa_manager
296 * @size: number of bytes we want to suballocate.
297 * @gfp: gfp flags used for memory allocation. Typically GFP_KERNEL but
298 * the argument is provided for suballocations from reclaim context or
299 * where the caller wants to avoid pipelining rather than wait for
300 * reclaim.
301 * @intr: Whether to perform waits interruptible. This should typically
302 * always be true, unless the caller needs to propagate a
303 * non-interruptible context from above layers.
304 * @align: Alignment. Must not exceed the default manager alignment.
305 * If @align is zero, then the manager alignment is used.
306 *
307 * Try to make a suballocation of size @size, which will be rounded
308 * up to the alignment specified in specified in drm_suballoc_manager_init().
309 *
310 * Return: a new suballocated bo, or an ERR_PTR.
311 */
312 struct drm_suballoc *
drm_suballoc_new(struct drm_suballoc_manager * sa_manager,size_t size,gfp_t gfp,bool intr,size_t align)313 drm_suballoc_new(struct drm_suballoc_manager *sa_manager, size_t size,
314 gfp_t gfp, bool intr, size_t align)
315 {
316 struct dma_fence *fences[DRM_SUBALLOC_MAX_QUEUES];
317 unsigned int tries[DRM_SUBALLOC_MAX_QUEUES];
318 unsigned int count;
319 int i, r;
320 struct drm_suballoc *sa;
321
322 if (WARN_ON_ONCE(align > sa_manager->align))
323 return ERR_PTR(-EINVAL);
324 if (WARN_ON_ONCE(size > sa_manager->size || !size))
325 return ERR_PTR(-EINVAL);
326
327 if (!align)
328 align = sa_manager->align;
329
330 sa = kmalloc(sizeof(*sa), gfp);
331 if (!sa)
332 return ERR_PTR(-ENOMEM);
333 sa->manager = sa_manager;
334 sa->fence = NULL;
335 INIT_LIST_HEAD(&sa->olist);
336 INIT_LIST_HEAD(&sa->flist);
337
338 spin_lock(&sa_manager->wq.lock);
339 do {
340 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
341 tries[i] = 0;
342
343 do {
344 drm_suballoc_try_free(sa_manager);
345
346 if (drm_suballoc_try_alloc(sa_manager, sa,
347 size, align)) {
348 spin_unlock(&sa_manager->wq.lock);
349 return sa;
350 }
351
352 /* see if we can skip over some allocations */
353 } while (drm_suballoc_next_hole(sa_manager, fences, tries));
354
355 for (i = 0, count = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
356 if (fences[i])
357 fences[count++] = dma_fence_get(fences[i]);
358
359 if (count) {
360 long t;
361
362 spin_unlock(&sa_manager->wq.lock);
363 t = dma_fence_wait_any_timeout(fences, count, intr,
364 MAX_SCHEDULE_TIMEOUT,
365 NULL);
366 for (i = 0; i < count; ++i)
367 dma_fence_put(fences[i]);
368
369 r = (t > 0) ? 0 : t;
370 spin_lock(&sa_manager->wq.lock);
371 } else if (intr) {
372 /* if we have nothing to wait for block */
373 r = wait_event_interruptible_locked
374 (sa_manager->wq,
375 __drm_suballoc_event(sa_manager, size, align));
376 } else {
377 spin_unlock(&sa_manager->wq.lock);
378 wait_event(sa_manager->wq,
379 drm_suballoc_event(sa_manager, size, align));
380 r = 0;
381 spin_lock(&sa_manager->wq.lock);
382 }
383 } while (!r);
384
385 spin_unlock(&sa_manager->wq.lock);
386 kfree(sa);
387 return ERR_PTR(r);
388 }
389 EXPORT_SYMBOL(drm_suballoc_new);
390
391 /**
392 * drm_suballoc_free - Free a suballocation
393 * @suballoc: pointer to the suballocation
394 * @fence: fence that signals when suballocation is idle
395 *
396 * Free the suballocation. The suballocation can be re-used after @fence signals.
397 */
drm_suballoc_free(struct drm_suballoc * suballoc,struct dma_fence * fence)398 void drm_suballoc_free(struct drm_suballoc *suballoc,
399 struct dma_fence *fence)
400 {
401 struct drm_suballoc_manager *sa_manager;
402
403 if (!suballoc)
404 return;
405
406 sa_manager = suballoc->manager;
407
408 spin_lock(&sa_manager->wq.lock);
409 if (fence && !dma_fence_is_signaled(fence)) {
410 u32 idx;
411
412 suballoc->fence = dma_fence_get(fence);
413 idx = fence->context & (DRM_SUBALLOC_MAX_QUEUES - 1);
414 list_add_tail(&suballoc->flist, &sa_manager->flist[idx]);
415 } else {
416 drm_suballoc_remove_locked(suballoc);
417 }
418 wake_up_all_locked(&sa_manager->wq);
419 spin_unlock(&sa_manager->wq.lock);
420 }
421 EXPORT_SYMBOL(drm_suballoc_free);
422
423 #ifdef CONFIG_DEBUG_FS
drm_suballoc_dump_debug_info(struct drm_suballoc_manager * sa_manager,struct drm_printer * p,unsigned long long suballoc_base)424 void drm_suballoc_dump_debug_info(struct drm_suballoc_manager *sa_manager,
425 struct drm_printer *p,
426 unsigned long long suballoc_base)
427 {
428 struct drm_suballoc *i;
429
430 spin_lock(&sa_manager->wq.lock);
431 list_for_each_entry(i, &sa_manager->olist, olist) {
432 unsigned long long soffset = i->soffset;
433 unsigned long long eoffset = i->eoffset;
434
435 if (&i->olist == sa_manager->hole)
436 drm_puts(p, ">");
437 else
438 drm_puts(p, " ");
439
440 drm_printf(p, "[0x%010llx 0x%010llx] size %8lld",
441 suballoc_base + soffset, suballoc_base + eoffset,
442 eoffset - soffset);
443
444 if (i->fence)
445 drm_printf(p, " protected by 0x%016llx on context %llu",
446 (unsigned long long)i->fence->seqno,
447 (unsigned long long)i->fence->context);
448
449 drm_puts(p, "\n");
450 }
451 spin_unlock(&sa_manager->wq.lock);
452 }
453 EXPORT_SYMBOL(drm_suballoc_dump_debug_info);
454 #endif
455 MODULE_AUTHOR("Multiple");
456 MODULE_DESCRIPTION("Range suballocator helper");
457 MODULE_LICENSE("Dual MIT/GPL");
458