drivers/gpu/drm/drm_suballoc.c

   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
  50 static void drm_suballoc_remove_locked(struct drm_suballoc *sa);
  51 static 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  */
  61 void 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 }
  83 EXPORT_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  */
  93 void 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 }
 112 EXPORT_SYMBOL(drm_suballoc_manager_fini);
 113
 114 static 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
 127 static 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
 143 static 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
 153 static 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
 162 static 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
 186 static 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  */
 213 static 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
 224 static 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  */
 312 struct drm_suballoc *
 313 drm_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 }
 389 EXPORT_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  */
 398 void 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 }
 421 EXPORT_SYMBOL(drm_suballoc_free);
 422
 423 #ifdef CONFIG_DEBUG_FS
 424 void 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 }
 453 EXPORT_SYMBOL(drm_suballoc_dump_debug_info);
 454 #endif
 455 MODULE_AUTHOR("Multiple");
 456 MODULE_DESCRIPTION("Range suballocator helper");
 457 MODULE_LICENSE("Dual MIT/GPL");