458 lines · c
1// SPDX-License-Identifier: GPL-2.0 OR MIT2/*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 a8 * copy of this software and associated documentation files (the9 * "Software"), to deal in the Software without restriction, including10 * without limitation the rights to use, copy, modify, merge, publish,11 * distribute, sub license, and/or sell copies of the Software, and to12 * permit persons to whom the Software is furnished to do so, subject to13 * the following conditions:14 *15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,17 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL18 * 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 OR20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE21 * USE OR OTHER DEALINGS IN THE SOFTWARE.22 *23 * The above copyright notice and this permission notice (including the24 * next paragraph) shall be included in all copies or substantial portions25 * of the Software.26 *27 */28/* Algorithm:29 *30 * We store the last allocated bo in "hole", we always try to allocate31 * after the last allocated bo. Principle is that in a linear GPU ring32 * progression was is after last is the oldest bo we allocated and thus33 * 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 closest36 * done bo if such one exist. If none exist and we are not asked to37 * block we report failure to allocate.38 *39 * If we are asked to block we wait on all the oldest fence of all40 * 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 50static void drm_suballoc_remove_locked(struct drm_suballoc *sa);51static void drm_suballoc_try_free(struct drm_suballoc_manager *sa_manager);52 53/**54 * drm_suballoc_manager_init() - Initialise the drm_suballoc_manager55 * @sa_manager: pointer to the sa_manager56 * @size: number of bytes we want to suballocate57 * @align: alignment for each suballocated chunk58 *59 * Prepares the suballocation manager for suballocations.60 */61void 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}83EXPORT_SYMBOL(drm_suballoc_manager_init);84 85/**86 * drm_suballoc_manager_fini() - Destroy the drm_suballoc_manager87 * @sa_manager: pointer to the sa_manager88 *89 * Cleans up the suballocation manager after use. All fences added90 * with drm_suballoc_free() must be signaled, or we cannot clean up91 * the entire manager.92 */93void 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}112EXPORT_SYMBOL(drm_suballoc_manager_fini);113 114static 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 127static 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 143static 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 153static 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 162static 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 186static 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 waiting205 * @sa_manager: pointer to the sa_manager206 * @size: number of bytes we want to allocate207 * @align: alignment we need to match208 *209 * Return: true if either there is a fence we can wait for or210 * enough free memory to satisfy the allocation directly.211 * false otherwise.212 */213static 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 224static 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 sa243 * of the current last244 */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_manager296 * @size: number of bytes we want to suballocate.297 * @gfp: gfp flags used for memory allocation. Typically GFP_KERNEL but298 * the argument is provided for suballocations from reclaim context or299 * where the caller wants to avoid pipelining rather than wait for300 * reclaim.301 * @intr: Whether to perform waits interruptible. This should typically302 * always be true, unless the caller needs to propagate a303 * 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 rounded308 * up to the alignment specified in specified in drm_suballoc_manager_init().309 *310 * Return: a new suballocated bo, or an ERR_PTR.311 */312struct drm_suballoc *313drm_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_locked374 (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}389EXPORT_SYMBOL(drm_suballoc_new);390 391/**392 * drm_suballoc_free - Free a suballocation393 * @suballoc: pointer to the suballocation394 * @fence: fence that signals when suballocation is idle395 *396 * Free the suballocation. The suballocation can be re-used after @fence signals.397 */398void 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}421EXPORT_SYMBOL(drm_suballoc_free);422 423#ifdef CONFIG_DEBUG_FS424void 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 else438 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}453EXPORT_SYMBOL(drm_suballoc_dump_debug_info);454#endif455MODULE_AUTHOR("Multiple");456MODULE_DESCRIPTION("Range suballocator helper");457MODULE_LICENSE("Dual MIT/GPL");458