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_new() - Make a suballocation. 297 * @sa_manager: pointer to the sa_manager 298 * @size: number of bytes we want to suballocate. 299 * @gfp: gfp flags used for memory allocation. Typically GFP_KERNEL but 300 * the argument is provided for suballocations from reclaim context or 301 * where the caller wants to avoid pipelining rather than wait for 302 * reclaim. 303 * @intr: Whether to perform waits interruptible. This should typically 304 * always be true, unless the caller needs to propagate a 305 * non-interruptible context from above layers. 306 * @align: Alignment. Must not exceed the default manager alignment. 307 * If @align is zero, then the manager alignment is used. 308 * 309 * Try to make a suballocation of size @size, which will be rounded 310 * up to the alignment specified in specified in drm_suballoc_manager_init(). 311 * 312 * Return: a new suballocated bo, or an ERR_PTR. 313 */ 314 struct drm_suballoc * 315 drm_suballoc_new(struct drm_suballoc_manager *sa_manager, size_t size, 316 gfp_t gfp, bool intr, size_t align) 317 { 318 struct dma_fence *fences[DRM_SUBALLOC_MAX_QUEUES]; 319 unsigned int tries[DRM_SUBALLOC_MAX_QUEUES]; 320 unsigned int count; 321 int i, r; 322 struct drm_suballoc *sa; 323 324 if (WARN_ON_ONCE(align > sa_manager->align)) 325 return ERR_PTR(-EINVAL); 326 if (WARN_ON_ONCE(size > sa_manager->size || !size)) 327 return ERR_PTR(-EINVAL); 328 329 if (!align) 330 align = sa_manager->align; 331 332 sa = kmalloc(sizeof(*sa), gfp); 333 if (!sa) 334 return ERR_PTR(-ENOMEM); 335 sa->manager = sa_manager; 336 sa->fence = NULL; 337 INIT_LIST_HEAD(&sa->olist); 338 INIT_LIST_HEAD(&sa->flist); 339 340 spin_lock(&sa_manager->wq.lock); 341 do { 342 for (i = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i) 343 tries[i] = 0; 344 345 do { 346 drm_suballoc_try_free(sa_manager); 347 348 if (drm_suballoc_try_alloc(sa_manager, sa, 349 size, align)) { 350 spin_unlock(&sa_manager->wq.lock); 351 return sa; 352 } 353 354 /* see if we can skip over some allocations */ 355 } while (drm_suballoc_next_hole(sa_manager, fences, tries)); 356 357 for (i = 0, count = 0; i < DRM_SUBALLOC_MAX_QUEUES; ++i) 358 if (fences[i]) 359 fences[count++] = dma_fence_get(fences[i]); 360 361 if (count) { 362 long t; 363 364 spin_unlock(&sa_manager->wq.lock); 365 t = dma_fence_wait_any_timeout(fences, count, intr, 366 MAX_SCHEDULE_TIMEOUT, 367 NULL); 368 for (i = 0; i < count; ++i) 369 dma_fence_put(fences[i]); 370 371 r = (t > 0) ? 0 : t; 372 spin_lock(&sa_manager->wq.lock); 373 } else if (intr) { 374 /* if we have nothing to wait for block */ 375 r = wait_event_interruptible_locked 376 (sa_manager->wq, 377 __drm_suballoc_event(sa_manager, size, align)); 378 } else { 379 spin_unlock(&sa_manager->wq.lock); 380 wait_event(sa_manager->wq, 381 drm_suballoc_event(sa_manager, size, align)); 382 r = 0; 383 spin_lock(&sa_manager->wq.lock); 384 } 385 } while (!r); 386 387 spin_unlock(&sa_manager->wq.lock); 388 kfree(sa); 389 return ERR_PTR(r); 390 } 391 EXPORT_SYMBOL(drm_suballoc_new); 392 393 /** 394 * drm_suballoc_free - Free a suballocation 395 * @suballoc: pointer to the suballocation 396 * @fence: fence that signals when suballocation is idle 397 * 398 * Free the suballocation. The suballocation can be re-used after @fence signals. 399 */ 400 void drm_suballoc_free(struct drm_suballoc *suballoc, 401 struct dma_fence *fence) 402 { 403 struct drm_suballoc_manager *sa_manager; 404 405 if (!suballoc) 406 return; 407 408 sa_manager = suballoc->manager; 409 410 spin_lock(&sa_manager->wq.lock); 411 if (fence && !dma_fence_is_signaled(fence)) { 412 u32 idx; 413 414 suballoc->fence = dma_fence_get(fence); 415 idx = fence->context & (DRM_SUBALLOC_MAX_QUEUES - 1); 416 list_add_tail(&suballoc->flist, &sa_manager->flist[idx]); 417 } else { 418 drm_suballoc_remove_locked(suballoc); 419 } 420 wake_up_all_locked(&sa_manager->wq); 421 spin_unlock(&sa_manager->wq.lock); 422 } 423 EXPORT_SYMBOL(drm_suballoc_free); 424 425 #ifdef CONFIG_DEBUG_FS 426 void drm_suballoc_dump_debug_info(struct drm_suballoc_manager *sa_manager, 427 struct drm_printer *p, 428 unsigned long long suballoc_base) 429 { 430 struct drm_suballoc *i; 431 432 spin_lock(&sa_manager->wq.lock); 433 list_for_each_entry(i, &sa_manager->olist, olist) { 434 unsigned long long soffset = i->soffset; 435 unsigned long long eoffset = i->eoffset; 436 437 if (&i->olist == sa_manager->hole) 438 drm_puts(p, ">"); 439 else 440 drm_puts(p, " "); 441 442 drm_printf(p, "[0x%010llx 0x%010llx] size %8lld", 443 suballoc_base + soffset, suballoc_base + eoffset, 444 eoffset - soffset); 445 446 if (i->fence) 447 drm_printf(p, " protected by 0x%016llx on context %llu", 448 (unsigned long long)i->fence->seqno, 449 (unsigned long long)i->fence->context); 450 451 drm_puts(p, "\n"); 452 } 453 spin_unlock(&sa_manager->wq.lock); 454 } 455 EXPORT_SYMBOL(drm_suballoc_dump_debug_info); 456 #endif 457 MODULE_AUTHOR("Multiple"); 458 MODULE_DESCRIPTION("Range suballocator helper"); 459 MODULE_LICENSE("Dual MIT/GPL"); 460