Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
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
46#include <linux/export.h>
47#include <linux/slab.h>
48#include <linux/sched.h>
49#include <linux/wait.h>
50#include <linux/dma-fence.h>
51
52static void drm_suballoc_remove_locked(struct drm_suballoc *sa);
53static void drm_suballoc_try_free(struct drm_suballoc_manager *sa_manager);
54
55/**
56 * drm_suballoc_manager_init() - Initialise the drm_suballoc_manager
57 * @sa_manager: pointer to the sa_manager
58 * @size: number of bytes we want to suballocate
59 * @align: alignment for each suballocated chunk
60 *
61 * Prepares the suballocation manager for suballocations.
62 */
63void drm_suballoc_manager_init(struct drm_suballoc_manager *sa_manager,
64 size_t size, size_t align)
65{
66 unsigned int i;
67
68 BUILD_BUG_ON(!is_power_of_2(DRM_SUBALLOC_MAX_QUEUES));
69
70 if (!align)
71 align = 1;
72
73 /* alignment must be a power of 2 */
74 if (WARN_ON_ONCE(align & (align - 1)))
75 align = roundup_pow_of_two(align);
76
77 init_waitqueue_head(&sa_manager->wq);
78 sa_manager->size = size;
79 sa_manager->align = align;
80 sa_manager->hole = &sa_manager->olist;
81 INIT_LIST_HEAD(&sa_manager->olist);
82 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
83 INIT_LIST_HEAD(&sa_manager->flist[i]);
84}
85EXPORT_SYMBOL(drm_suballoc_manager_init);
86
87/**
88 * drm_suballoc_manager_fini() - Destroy the drm_suballoc_manager
89 * @sa_manager: pointer to the sa_manager
90 *
91 * Cleans up the suballocation manager after use. All fences added
92 * with drm_suballoc_free() must be signaled, or we cannot clean up
93 * the entire manager.
94 */
95void drm_suballoc_manager_fini(struct drm_suballoc_manager *sa_manager)
96{
97 struct drm_suballoc *sa, *tmp;
98
99 if (!sa_manager->size)
100 return;
101
102 if (!list_empty(&sa_manager->olist)) {
103 sa_manager->hole = &sa_manager->olist;
104 drm_suballoc_try_free(sa_manager);
105 if (!list_empty(&sa_manager->olist))
106 DRM_ERROR("sa_manager is not empty, clearing anyway\n");
107 }
108 list_for_each_entry_safe(sa, tmp, &sa_manager->olist, olist) {
109 drm_suballoc_remove_locked(sa);
110 }
111
112 sa_manager->size = 0;
113}
114EXPORT_SYMBOL(drm_suballoc_manager_fini);
115
116static void drm_suballoc_remove_locked(struct drm_suballoc *sa)
117{
118 struct drm_suballoc_manager *sa_manager = sa->manager;
119
120 if (sa_manager->hole == &sa->olist)
121 sa_manager->hole = sa->olist.prev;
122
123 list_del_init(&sa->olist);
124 list_del_init(&sa->flist);
125 dma_fence_put(sa->fence);
126 kfree(sa);
127}
128
129static void drm_suballoc_try_free(struct drm_suballoc_manager *sa_manager)
130{
131 struct drm_suballoc *sa, *tmp;
132
133 if (sa_manager->hole->next == &sa_manager->olist)
134 return;
135
136 sa = list_entry(sa_manager->hole->next, struct drm_suballoc, olist);
137 list_for_each_entry_safe_from(sa, tmp, &sa_manager->olist, olist) {
138 if (!sa->fence || !dma_fence_is_signaled(sa->fence))
139 return;
140
141 drm_suballoc_remove_locked(sa);
142 }
143}
144
145static size_t drm_suballoc_hole_soffset(struct drm_suballoc_manager *sa_manager)
146{
147 struct list_head *hole = sa_manager->hole;
148
149 if (hole != &sa_manager->olist)
150 return list_entry(hole, struct drm_suballoc, olist)->eoffset;
151
152 return 0;
153}
154
155static size_t drm_suballoc_hole_eoffset(struct drm_suballoc_manager *sa_manager)
156{
157 struct list_head *hole = sa_manager->hole;
158
159 if (hole->next != &sa_manager->olist)
160 return list_entry(hole->next, struct drm_suballoc, olist)->soffset;
161 return sa_manager->size;
162}
163
164static bool drm_suballoc_try_alloc(struct drm_suballoc_manager *sa_manager,
165 struct drm_suballoc *sa,
166 size_t size, size_t align)
167{
168 size_t soffset, eoffset, wasted;
169
170 soffset = drm_suballoc_hole_soffset(sa_manager);
171 eoffset = drm_suballoc_hole_eoffset(sa_manager);
172 wasted = round_up(soffset, align) - soffset;
173
174 if ((eoffset - soffset) >= (size + wasted)) {
175 soffset += wasted;
176
177 sa->manager = sa_manager;
178 sa->soffset = soffset;
179 sa->eoffset = soffset + size;
180 list_add(&sa->olist, sa_manager->hole);
181 INIT_LIST_HEAD(&sa->flist);
182 sa_manager->hole = &sa->olist;
183 return true;
184 }
185 return false;
186}
187
188static bool __drm_suballoc_event(struct drm_suballoc_manager *sa_manager,
189 size_t size, size_t align)
190{
191 size_t soffset, eoffset, wasted;
192 unsigned int i;
193
194 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
195 if (!list_empty(&sa_manager->flist[i]))
196 return true;
197
198 soffset = drm_suballoc_hole_soffset(sa_manager);
199 eoffset = drm_suballoc_hole_eoffset(sa_manager);
200 wasted = round_up(soffset, align) - soffset;
201
202 return ((eoffset - soffset) >= (size + wasted));
203}
204
205/**
206 * drm_suballoc_event() - Check if we can stop waiting
207 * @sa_manager: pointer to the sa_manager
208 * @size: number of bytes we want to allocate
209 * @align: alignment we need to match
210 *
211 * Return: true if either there is a fence we can wait for or
212 * enough free memory to satisfy the allocation directly.
213 * false otherwise.
214 */
215static bool drm_suballoc_event(struct drm_suballoc_manager *sa_manager,
216 size_t size, size_t align)
217{
218 bool ret;
219
220 spin_lock(&sa_manager->wq.lock);
221 ret = __drm_suballoc_event(sa_manager, size, align);
222 spin_unlock(&sa_manager->wq.lock);
223 return ret;
224}
225
226static bool drm_suballoc_next_hole(struct drm_suballoc_manager *sa_manager,
227 struct dma_fence **fences,
228 unsigned int *tries)
229{
230 struct drm_suballoc *best_bo = NULL;
231 unsigned int i, best_idx;
232 size_t soffset, best, tmp;
233
234 /* if hole points to the end of the buffer */
235 if (sa_manager->hole->next == &sa_manager->olist) {
236 /* try again with its beginning */
237 sa_manager->hole = &sa_manager->olist;
238 return true;
239 }
240
241 soffset = drm_suballoc_hole_soffset(sa_manager);
242 /* to handle wrap around we add sa_manager->size */
243 best = sa_manager->size * 2;
244 /* go over all fence list and try to find the closest sa
245 * of the current last
246 */
247 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i) {
248 struct drm_suballoc *sa;
249
250 fences[i] = NULL;
251
252 if (list_empty(&sa_manager->flist[i]))
253 continue;
254
255 sa = list_first_entry(&sa_manager->flist[i],
256 struct drm_suballoc, flist);
257
258 if (!dma_fence_is_signaled(sa->fence)) {
259 fences[i] = sa->fence;
260 continue;
261 }
262
263 /* limit the number of tries each freelist gets */
264 if (tries[i] > 2)
265 continue;
266
267 tmp = sa->soffset;
268 if (tmp < soffset) {
269 /* wrap around, pretend it's after */
270 tmp += sa_manager->size;
271 }
272 tmp -= soffset;
273 if (tmp < best) {
274 /* this sa bo is the closest one */
275 best = tmp;
276 best_idx = i;
277 best_bo = sa;
278 }
279 }
280
281 if (best_bo) {
282 ++tries[best_idx];
283 sa_manager->hole = best_bo->olist.prev;
284
285 /*
286 * We know that this one is signaled,
287 * so it's safe to remove it.
288 */
289 drm_suballoc_remove_locked(best_bo);
290 return true;
291 }
292 return false;
293}
294
295/**
296 * drm_suballoc_alloc() - Allocate uninitialized suballoc object.
297 * @gfp: gfp flags used for memory allocation.
298 *
299 * Allocate memory for an uninitialized suballoc object. Intended usage is
300 * allocate memory for suballoc object outside of a reclaim tainted context
301 * and then be initialized at a later time in a reclaim tainted context.
302 *
303 * @drm_suballoc_free() should be used to release the memory if returned
304 * suballoc object is in uninitialized state.
305 *
306 * Return: a new uninitialized suballoc object, or an ERR_PTR(-ENOMEM).
307 */
308struct drm_suballoc *drm_suballoc_alloc(gfp_t gfp)
309{
310 struct drm_suballoc *sa;
311
312 sa = kmalloc_obj(*sa, gfp);
313 if (!sa)
314 return ERR_PTR(-ENOMEM);
315
316 sa->manager = NULL;
317
318 return sa;
319}
320EXPORT_SYMBOL(drm_suballoc_alloc);
321
322/**
323 * drm_suballoc_insert() - Initialize a suballocation and insert a hole.
324 * @sa_manager: pointer to the sa_manager
325 * @sa: The struct drm_suballoc.
326 * @size: number of bytes we want to suballocate.
327 * @intr: Whether to perform waits interruptible. This should typically
328 * always be true, unless the caller needs to propagate a
329 * non-interruptible context from above layers.
330 * @align: Alignment. Must not exceed the default manager alignment.
331 * If @align is zero, then the manager alignment is used.
332 *
333 * Try to make a suballocation on a pre-allocated suballoc object of size @size,
334 * which will be rounded up to the alignment specified in specified in
335 * drm_suballoc_manager_init().
336 *
337 * Return: zero on success, errno on failure.
338 */
339int drm_suballoc_insert(struct drm_suballoc_manager *sa_manager,
340 struct drm_suballoc *sa, size_t size,
341 bool intr, size_t align)
342{
343 struct dma_fence *fences[DRM_SUBALLOC_MAX_QUEUES];
344 unsigned int tries[DRM_SUBALLOC_MAX_QUEUES];
345 unsigned int count;
346 int i, r;
347
348 if (WARN_ON_ONCE(align > sa_manager->align))
349 return -EINVAL;
350 if (WARN_ON_ONCE(size > sa_manager->size || !size))
351 return -EINVAL;
352
353 if (!align)
354 align = sa_manager->align;
355
356 sa->manager = sa_manager;
357 sa->fence = NULL;
358 INIT_LIST_HEAD(&sa->olist);
359 INIT_LIST_HEAD(&sa->flist);
360
361 spin_lock(&sa_manager->wq.lock);
362 do {
363 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
364 tries[i] = 0;
365
366 do {
367 drm_suballoc_try_free(sa_manager);
368
369 if (drm_suballoc_try_alloc(sa_manager, sa,
370 size, align)) {
371 spin_unlock(&sa_manager->wq.lock);
372 return 0;
373 }
374
375 /* see if we can skip over some allocations */
376 } while (drm_suballoc_next_hole(sa_manager, fences, tries));
377
378 for (i = 0, count = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i)
379 if (fences[i])
380 fences[count++] = dma_fence_get(fences[i]);
381
382 if (count) {
383 long t;
384
385 spin_unlock(&sa_manager->wq.lock);
386 t = dma_fence_wait_any_timeout(fences, count, intr,
387 MAX_SCHEDULE_TIMEOUT,
388 NULL);
389 for (i = 0; i < count; ++i)
390 dma_fence_put(fences[i]);
391
392 r = (t > 0) ? 0 : t;
393 spin_lock(&sa_manager->wq.lock);
394 } else if (intr) {
395 /* if we have nothing to wait for block */
396 r = wait_event_interruptible_locked
397 (sa_manager->wq,
398 __drm_suballoc_event(sa_manager, size, align));
399 } else {
400 spin_unlock(&sa_manager->wq.lock);
401 wait_event(sa_manager->wq,
402 drm_suballoc_event(sa_manager, size, align));
403 r = 0;
404 spin_lock(&sa_manager->wq.lock);
405 }
406 } while (!r);
407
408 spin_unlock(&sa_manager->wq.lock);
409 sa->manager = NULL;
410 return r;
411}
412EXPORT_SYMBOL(drm_suballoc_insert);
413
414/**
415 * drm_suballoc_new() - Make a suballocation.
416 * @sa_manager: pointer to the sa_manager
417 * @size: number of bytes we want to suballocate.
418 * @gfp: gfp flags used for memory allocation. Typically GFP_KERNEL but
419 * the argument is provided for suballocations from reclaim context or
420 * where the caller wants to avoid pipelining rather than wait for
421 * reclaim.
422 * @intr: Whether to perform waits interruptible. This should typically
423 * always be true, unless the caller needs to propagate a
424 * non-interruptible context from above layers.
425 * @align: Alignment. Must not exceed the default manager alignment.
426 * If @align is zero, then the manager alignment is used.
427 *
428 * Try to make a suballocation of size @size, which will be rounded
429 * up to the alignment specified in specified in drm_suballoc_manager_init().
430 *
431 * Return: a new suballocated bo, or an ERR_PTR.
432 */
433struct drm_suballoc *
434drm_suballoc_new(struct drm_suballoc_manager *sa_manager, size_t size,
435 gfp_t gfp, bool intr, size_t align)
436{
437 struct drm_suballoc *sa;
438 int err;
439
440 sa = drm_suballoc_alloc(gfp);
441 if (IS_ERR(sa))
442 return sa;
443
444 err = drm_suballoc_insert(sa_manager, sa, size, intr, align);
445 if (err) {
446 drm_suballoc_free(sa, NULL);
447 return ERR_PTR(err);
448 }
449
450 return sa;
451}
452EXPORT_SYMBOL(drm_suballoc_new);
453
454/**
455 * drm_suballoc_free - Free a suballocation
456 * @suballoc: pointer to the suballocation
457 * @fence: fence that signals when suballocation is idle
458 *
459 * Free the suballocation. The suballocation can be re-used after @fence signals.
460 */
461void drm_suballoc_free(struct drm_suballoc *suballoc,
462 struct dma_fence *fence)
463{
464 struct drm_suballoc_manager *sa_manager;
465
466 if (!suballoc)
467 return;
468
469 if (!suballoc->manager) {
470 kfree(suballoc);
471 return;
472 }
473
474 sa_manager = suballoc->manager;
475
476 spin_lock(&sa_manager->wq.lock);
477 if (fence && !dma_fence_is_signaled(fence)) {
478 u32 idx;
479
480 suballoc->fence = dma_fence_get(fence);
481 idx = fence->context & (DRM_SUBALLOC_MAX_QUEUES - 1);
482 list_add_tail(&suballoc->flist, &sa_manager->flist[idx]);
483 } else {
484 drm_suballoc_remove_locked(suballoc);
485 }
486 wake_up_all_locked(&sa_manager->wq);
487 spin_unlock(&sa_manager->wq.lock);
488}
489EXPORT_SYMBOL(drm_suballoc_free);
490
491#ifdef CONFIG_DEBUG_FS
492void drm_suballoc_dump_debug_info(struct drm_suballoc_manager *sa_manager,
493 struct drm_printer *p,
494 unsigned long long suballoc_base)
495{
496 struct drm_suballoc *i;
497
498 spin_lock(&sa_manager->wq.lock);
499 list_for_each_entry(i, &sa_manager->olist, olist) {
500 unsigned long long soffset = i->soffset;
501 unsigned long long eoffset = i->eoffset;
502
503 if (&i->olist == sa_manager->hole)
504 drm_puts(p, ">");
505 else
506 drm_puts(p, " ");
507
508 drm_printf(p, "[0x%010llx 0x%010llx] size %8lld",
509 suballoc_base + soffset, suballoc_base + eoffset,
510 eoffset - soffset);
511
512 if (i->fence)
513 drm_printf(p, " protected by 0x%016llx on context %llu",
514 (unsigned long long)i->fence->seqno,
515 (unsigned long long)i->fence->context);
516
517 drm_puts(p, "\n");
518 }
519 spin_unlock(&sa_manager->wq.lock);
520}
521EXPORT_SYMBOL(drm_suballoc_dump_debug_info);
522#endif
523MODULE_AUTHOR("Multiple");
524MODULE_DESCRIPTION("Range suballocator helper");
525MODULE_LICENSE("Dual MIT/GPL");