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 52 static void drm_suballoc_remove_locked(struct drm_suballoc *sa); 53 static 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 */ 63 void 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 } 85 EXPORT_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 */ 95 void 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 } 114 EXPORT_SYMBOL(drm_suballoc_manager_fini); 115 116 static 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 129 static 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 145 static 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 155 static 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 164 static 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 188 static 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 */ 215 static 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 226 static 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 */ 308 struct 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 } 320 EXPORT_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 */ 339 int 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 } 412 EXPORT_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 */ 433 struct drm_suballoc * 434 drm_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 } 452 EXPORT_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 */ 461 void 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 } 489 EXPORT_SYMBOL(drm_suballoc_free); 490 491 #ifdef CONFIG_DEBUG_FS 492 void 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 } 521 EXPORT_SYMBOL(drm_suballoc_dump_debug_info); 522 #endif 523 MODULE_AUTHOR("Multiple"); 524 MODULE_DESCRIPTION("Range suballocator helper"); 525 MODULE_LICENSE("Dual MIT/GPL"); 526