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 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_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 */ 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_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 */ 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 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 */ 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 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 */ 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_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} 389EXPORT_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 */ 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_FS 424void 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} 453EXPORT_SYMBOL(drm_suballoc_dump_debug_info); 454#endif 455MODULE_AUTHOR("Multiple"); 456MODULE_DESCRIPTION("Range suballocator helper"); 457MODULE_LICENSE("Dual MIT/GPL"); 458