drivers/gpu/drm/drm_mm.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
  21  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
  22  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  23  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
  24  * USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  *
  27  **************************************************************************/
  28
  29 /*
  30  * Generic simple memory manager implementation. Intended to be used as a base
  31  * class implementation for more advanced memory managers.
  32  *
  33  * Note that the algorithm used is quite simple and there might be substantial
  34  * performance gains if a smarter free list is implemented. Currently it is just an
  35  * unordered stack of free regions. This could easily be improved if an RB-tree
  36  * is used instead. At least if we expect heavy fragmentation.
  37  *
  38  * Aligned allocations can also see improvement.
  39  *
  40  * Authors:
  41  * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
  42  */
  43
  44 #include <drm/drmP.h>
  45 #include <drm/drm_mm.h>
  46 #include <linux/slab.h>
  47 #include <linux/seq_file.h>
  48 #include <linux/export.h>
  49 #include <linux/interval_tree_generic.h>
  50 #include <linux/rbtree.h>
  51
  52 /**
  53  * DOC: Overview
  54  *
  55  * drm_mm provides a simple range allocator. The drivers are free to use the
  56  * resource allocator from the linux core if it suits them, the upside of drm_mm
  57  * is that it's in the DRM core. Which means that it's easier to extend for
  58  * some of the crazier special purpose needs of gpus.
  59  *
  60  * The main data struct is &drm_mm, allocations are tracked in &drm_mm_node.
  61  * Drivers are free to embed either of them into their own suitable
  62  * datastructures. drm_mm itself will not do any allocations of its own, so if
  63  * drivers choose not to embed nodes they need to still allocate them
  64  * themselves.
  65  *
  66  * The range allocator also supports reservation of preallocated blocks. This is
  67  * useful for taking over initial mode setting configurations from the firmware,
  68  * where an object needs to be created which exactly matches the firmware's
  69  * scanout target. As long as the range is still free it can be inserted anytime
  70  * after the allocator is initialized, which helps with avoiding looped
  71  * depencies in the driver load sequence.
  72  *
  73  * drm_mm maintains a stack of most recently freed holes, which of all
  74  * simplistic datastructures seems to be a fairly decent approach to clustering
  75  * allocations and avoiding too much fragmentation. This means free space
  76  * searches are O(num_holes). Given that all the fancy features drm_mm supports
  77  * something better would be fairly complex and since gfx thrashing is a fairly
  78  * steep cliff not a real concern. Removing a node again is O(1). With the
  79  * rbtree to track free holes, free hole search becomes O(log(num_holes)).
  80  *
  81  * drm_mm supports a few features: Alignment and range restrictions can be
  82  * supplied. Further more every &drm_mm_node has a color value (which is just an
  83  * opaqua unsigned long) which in conjunction with a driver callback can be used
  84  * to implement sophisticated placement restrictions. The i915 DRM driver uses
  85  * this to implement guard pages between incompatible caching domains in the
  86  * graphics TT.
  87  *
  88  * Two behaviors are supported for searching and allocating: bottom-up and top-down.
  89  * The default is bottom-up. Top-down allocation can be used if the memory area
  90  * has different restrictions, or just to reduce fragmentation.
  91  *
  92  * Finally iteration helpers to walk all nodes and all holes are provided as are
  93  * some basic allocator dumpers for debugging.
  94  */
  95
  96 static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
  97                                                 u64 size,
  98                                                 unsigned alignment,
  99                                                 unsigned long color,
 100                                                 enum drm_mm_search_flags flags);
 101 static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
 102                                                 u64 size,
 103                                                 unsigned alignment,
 104                                                 unsigned long color,
 105                                                 u64 start,
 106                                                 u64 end,
 107                                                 enum drm_mm_search_flags flags);
 108
 109 #define START(node) ((node)->start)
 110 #define LAST(node)  ((node)->start + (node)->size - 1)
 111
 112 INTERVAL_TREE_DEFINE(struct drm_mm_node, rb,
 113                      u64, __subtree_last,
 114                      START, LAST, static inline, drm_mm_interval_tree)
 115
 116 struct drm_mm_node *
 117 drm_mm_interval_first(struct drm_mm *mm, u64 start, u64 last)
 118 {
 119         return drm_mm_interval_tree_iter_first(&mm->interval_tree,
 120                                                start, last);
 121 }
 122 EXPORT_SYMBOL(drm_mm_interval_first);
 123
 124 struct drm_mm_node *
 125 drm_mm_interval_next(struct drm_mm_node *node, u64 start, u64 last)
 126 {
 127         return drm_mm_interval_tree_iter_next(node, start, last);
 128 }
 129 EXPORT_SYMBOL(drm_mm_interval_next);
 130
 131 static void drm_mm_interval_tree_add_node(struct drm_mm_node *hole_node,
 132                                           struct drm_mm_node *node)
 133 {
 134         struct drm_mm *mm = hole_node->mm;
 135         struct rb_node **link, *rb;
 136         struct drm_mm_node *parent;
 137
 138         node->__subtree_last = LAST(node);
 139
 140         if (hole_node->allocated) {
 141                 rb = &hole_node->rb;
 142                 while (rb) {
 143                         parent = rb_entry(rb, struct drm_mm_node, rb);
 144                         if (parent->__subtree_last >= node->__subtree_last)
 145                                 break;
 146
 147                         parent->__subtree_last = node->__subtree_last;
 148                         rb = rb_parent(rb);
 149                 }
 150
 151                 rb = &hole_node->rb;
 152                 link = &hole_node->rb.rb_right;
 153         } else {
 154                 rb = NULL;
 155                 link = &mm->interval_tree.rb_node;
 156         }
 157
 158         while (*link) {
 159                 rb = *link;
 160                 parent = rb_entry(rb, struct drm_mm_node, rb);
 161                 if (parent->__subtree_last < node->__subtree_last)
 162                         parent->__subtree_last = node->__subtree_last;
 163                 if (node->start < parent->start)
 164                         link = &parent->rb.rb_left;
 165                 else
 166                         link = &parent->rb.rb_right;
 167         }
 168
 169         rb_link_node(&node->rb, rb, link);
 170         rb_insert_augmented(&node->rb,
 171                             &mm->interval_tree,
 172                             &drm_mm_interval_tree_augment);
 173 }
 174
 175 static void
 176 rb_insert_hole_node(struct drm_mm_node *hole_node, struct drm_mm *mm)
 177 {
 178         struct rb_node **new = &(mm->holes_tree.rb_node);
 179         struct rb_node *parent = NULL;
 180         struct drm_mm_node *cur;
 181
 182         while (*new) {
 183                 parent = *new;
 184                 cur = rb_entry(parent, struct drm_mm_node, hole_node);
 185
 186                 if (__drm_mm_hole_node_start(hole_node)
 187                                 < __drm_mm_hole_node_start(cur))
 188                         new = &parent->rb_left;
 189                 else
 190                         new = &parent->rb_right;
 191         }
 192         rb_link_node(&hole_node->hole_node, parent, new);
 193         rb_insert_color(&hole_node->hole_node, &mm->holes_tree);
 194 }
 195
 196 static void rb_erase_hole_node(struct drm_mm_node *hole_node, struct drm_mm *mm)
 197 {
 198         rb_erase(&hole_node->hole_node, &mm->holes_tree);
 199 }
 200
 201 static void drm_mm_insert_helper(struct drm_mm_node *hole_node,
 202                                  struct drm_mm_node *node,
 203                                  u64 size, unsigned alignment,
 204                                  unsigned long color,
 205                                  enum drm_mm_allocator_flags flags)
 206 {
 207         struct drm_mm *mm = hole_node->mm;
 208         u64 hole_start = drm_mm_hole_node_start(hole_node);
 209         u64 hole_end = drm_mm_hole_node_end(hole_node);
 210         u64 adj_start = hole_start;
 211         u64 adj_end = hole_end;
 212
 213         BUG_ON(node->allocated);
 214
 215         if (mm->color_adjust)
 216                 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
 217
 218         if (flags & DRM_MM_CREATE_TOP)
 219                 adj_start = adj_end - size;
 220
 221         if (alignment) {
 222                 u64 tmp = adj_start;
 223                 unsigned rem;
 224
 225                 rem = do_div(tmp, alignment);
 226                 if (rem) {
 227                         if (flags & DRM_MM_CREATE_TOP)
 228                                 adj_start -= rem;
 229                         else
 230                                 adj_start += alignment - rem;
 231                 }
 232         }
 233
 234         BUG_ON(adj_start < hole_start);
 235         BUG_ON(adj_end > hole_end);
 236
 237         if (adj_start == hole_start) {
 238                 hole_node->hole_follows = 0;
 239                 list_del(&hole_node->hole_stack);
 240                 rb_erase_hole_node(hole_node, mm);
 241         }
 242
 243         node->start = adj_start;
 244         node->size = size;
 245         node->mm = mm;
 246         node->color = color;
 247         node->allocated = 1;
 248
 249         list_add(&node->node_list, &hole_node->node_list);
 250
 251         drm_mm_interval_tree_add_node(hole_node, node);
 252
 253         BUG_ON(node->start + node->size > adj_end);
 254
 255         node->hole_follows = 0;
 256         if (__drm_mm_hole_node_start(node) < hole_end) {
 257                 list_add(&node->hole_stack, &mm->hole_stack);
 258                 rb_insert_hole_node(node, mm);
 259                 node->hole_follows = 1;
 260         }
 261 }
 262
 263 /**
 264  * drm_mm_reserve_node - insert an pre-initialized node
 265  * @mm: drm_mm allocator to insert @node into
 266  * @node: drm_mm_node to insert
 267  *
 268  * This functions inserts an already set-up drm_mm_node into the allocator,
 269  * meaning that start, size and color must be set by the caller. This is useful
 270  * to initialize the allocator with preallocated objects which must be set-up
 271  * before the range allocator can be set-up, e.g. when taking over a firmware
 272  * framebuffer.
 273  *
 274  * Returns:
 275  * 0 on success, -ENOSPC if there's no hole where @node is.
 276  */
 277 int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node)
 278 {
 279         u64 end = node->start + node->size;
 280         struct drm_mm_node *hole;
 281         u64 hole_start, hole_end;
 282
 283         if (WARN_ON(node->size == 0))
 284                 return -EINVAL;
 285
 286         /* Find the relevant hole to add our node to */
 287         hole = drm_mm_interval_tree_iter_first(&mm->interval_tree,
 288                                                node->start, ~(u64)0);
 289         if (hole) {
 290                 if (hole->start < end)
 291                         return -ENOSPC;
 292         } else {
 293                 hole = list_entry(&mm->head_node.node_list,
 294                                   typeof(*hole), node_list);
 295         }
 296
 297         hole = list_last_entry(&hole->node_list, typeof(*hole), node_list);
 298         if (!hole->hole_follows)
 299                 return -ENOSPC;
 300
 301         hole_start = __drm_mm_hole_node_start(hole);
 302         hole_end = __drm_mm_hole_node_end(hole);
 303         if (hole_start > node->start || hole_end < end)
 304                 return -ENOSPC;
 305
 306         node->mm = mm;
 307         node->allocated = 1;
 308
 309         list_add(&node->node_list, &hole->node_list);
 310
 311         drm_mm_interval_tree_add_node(hole, node);
 312
 313         if (node->start == hole_start) {
 314                 hole->hole_follows = 0;
 315                 list_del(&hole->hole_stack);
 316                 rb_erase_hole_node(hole, mm);
 317         }
 318
 319         node->hole_follows = 0;
 320         if (end != hole_end) {
 321                 list_add(&node->hole_stack, &mm->hole_stack);
 322                 rb_insert_hole_node(node, mm);
 323                 node->hole_follows = 1;
 324         }
 325
 326         return 0;
 327 }
 328 EXPORT_SYMBOL(drm_mm_reserve_node);
 329
 330 /**
 331  * drm_mm_insert_node_generic - search for space and insert @node
 332  * @mm: drm_mm to allocate from
 333  * @node: preallocate node to insert
 334  * @size: size of the allocation
 335  * @alignment: alignment of the allocation
 336  * @color: opaque tag value to use for this node
 337  * @sflags: flags to fine-tune the allocation search
 338  * @aflags: flags to fine-tune the allocation behavior
 339  *
 340  * The preallocated node must be cleared to 0.
 341  *
 342  * Returns:
 343  * 0 on success, -ENOSPC if there's no suitable hole.
 344  */
 345 int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
 346                                u64 size, unsigned alignment,
 347                                unsigned long color,
 348                                enum drm_mm_search_flags sflags,
 349                                enum drm_mm_allocator_flags aflags)
 350 {
 351         struct drm_mm_node *hole_node;
 352
 353         if (WARN_ON(size == 0))
 354                 return -EINVAL;
 355
 356         hole_node = drm_mm_search_free_generic(mm, size, alignment,
 357                                                color, sflags);
 358         if (!hole_node)
 359                 return -ENOSPC;
 360
 361         drm_mm_insert_helper(hole_node, node, size, alignment, color, aflags);
 362         return 0;
 363 }
 364 EXPORT_SYMBOL(drm_mm_insert_node_generic);
 365
 366 static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,
 367                                        struct drm_mm_node *node,
 368                                        u64 size, unsigned alignment,
 369                                        unsigned long color,
 370                                        u64 start, u64 end,
 371                                        enum drm_mm_allocator_flags flags)
 372 {
 373         struct drm_mm *mm = hole_node->mm;
 374         u64 hole_start = drm_mm_hole_node_start(hole_node);
 375         u64 hole_end = drm_mm_hole_node_end(hole_node);
 376         u64 adj_start = hole_start;
 377         u64 adj_end = hole_end;
 378
 379         BUG_ON(!hole_node->hole_follows || node->allocated);
 380
 381         if (mm->color_adjust)
 382                 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
 383
 384         adj_start = max(adj_start, start);
 385         adj_end = min(adj_end, end);
 386
 387         if (flags & DRM_MM_CREATE_TOP)
 388                 adj_start = adj_end - size;
 389
 390         if (alignment) {
 391                 u64 tmp = adj_start;
 392                 unsigned rem;
 393
 394                 rem = do_div(tmp, alignment);
 395                 if (rem) {
 396                         if (flags & DRM_MM_CREATE_TOP)
 397                                 adj_start -= rem;
 398                         else
 399                                 adj_start += alignment - rem;
 400                 }
 401         }
 402
 403         if (adj_start == hole_start) {
 404                 hole_node->hole_follows = 0;
 405                 list_del(&hole_node->hole_stack);
 406                 rb_erase_hole_node(hole_node, mm);
 407         }
 408
 409         node->start = adj_start;
 410         node->size = size;
 411         node->mm = mm;
 412         node->color = color;
 413         node->allocated = 1;
 414
 415         list_add(&node->node_list, &hole_node->node_list);
 416
 417         drm_mm_interval_tree_add_node(hole_node, node);
 418
 419         BUG_ON(node->start < start);
 420         BUG_ON(node->start < adj_start);
 421         BUG_ON(node->start + node->size > adj_end);
 422         BUG_ON(node->start + node->size > end);
 423
 424         node->hole_follows = 0;
 425         if (__drm_mm_hole_node_start(node) < hole_end) {
 426                 list_add(&node->hole_stack, &mm->hole_stack);
 427                 rb_insert_hole_node(node, mm);
 428                 node->hole_follows = 1;
 429         }
 430 }
 431
 432 /**
 433  * drm_mm_insert_node_in_range_generic - ranged search for space and insert @node
 434  * @mm: drm_mm to allocate from
 435  * @node: preallocate node to insert
 436  * @size: size of the allocation
 437  * @alignment: alignment of the allocation
 438  * @color: opaque tag value to use for this node
 439  * @start: start of the allowed range for this node
 440  * @end: end of the allowed range for this node
 441  * @sflags: flags to fine-tune the allocation search
 442  * @aflags: flags to fine-tune the allocation behavior
 443  *
 444  * The preallocated node must be cleared to 0.
 445  *
 446  * Returns:
 447  * 0 on success, -ENOSPC if there's no suitable hole.
 448  */
 449 int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node,
 450                                         u64 size, unsigned alignment,
 451                                         unsigned long color,
 452                                         u64 start, u64 end,
 453                                         enum drm_mm_search_flags sflags,
 454                                         enum drm_mm_allocator_flags aflags)
 455 {
 456         struct drm_mm_node *hole_node;
 457
 458         if (WARN_ON(size == 0))
 459                 return -EINVAL;
 460
 461         hole_node = drm_mm_search_free_in_range_generic(mm,
 462                                                         size, alignment, color,
 463                                                         start, end, sflags);
 464         if (!hole_node)
 465                 return -ENOSPC;
 466
 467         drm_mm_insert_helper_range(hole_node, node,
 468                                    size, alignment, color,
 469                                    start, end, aflags);
 470         return 0;
 471 }
 472 EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic);
 473
 474 /**
 475  * drm_mm_remove_node - Remove a memory node from the allocator.
 476  * @node: drm_mm_node to remove
 477  *
 478  * This just removes a node from its drm_mm allocator. The node does not need to
 479  * be cleared again before it can be re-inserted into this or any other drm_mm
 480  * allocator. It is a bug to call this function on a un-allocated node.
 481  */
 482 void drm_mm_remove_node(struct drm_mm_node *node)
 483 {
 484         struct drm_mm *mm = node->mm;
 485         struct drm_mm_node *prev_node;
 486
 487         if (WARN_ON(!node->allocated))
 488                 return;
 489
 490         BUG_ON(node->scanned_block || node->scanned_prev_free
 491                                    || node->scanned_next_free);
 492
 493         prev_node =
 494             list_entry(node->node_list.prev, struct drm_mm_node, node_list);
 495
 496         if (node->hole_follows) {
 497                 BUG_ON(__drm_mm_hole_node_start(node) ==
 498                        __drm_mm_hole_node_end(node));
 499                 list_del(&node->hole_stack);
 500                 rb_erase_hole_node(node, mm);
 501         } else
 502                 BUG_ON(__drm_mm_hole_node_start(node) !=
 503                        __drm_mm_hole_node_end(node));
 504
 505
 506         if (!prev_node->hole_follows) {
 507                 prev_node->hole_follows = 1;
 508                 list_add(&prev_node->hole_stack, &mm->hole_stack);
 509                 rb_insert_hole_node(prev_node, mm);
 510         } else
 511                 list_move(&prev_node->hole_stack, &mm->hole_stack);
 512
 513         drm_mm_interval_tree_remove(node, &mm->interval_tree);
 514         list_del(&node->node_list);
 515         node->allocated = 0;
 516 }
 517 EXPORT_SYMBOL(drm_mm_remove_node);
 518
 519 static int check_free_hole(u64 start, u64 end, u64 size, unsigned alignment)
 520 {
 521         if (end - start < size)
 522                 return 0;
 523
 524         if (alignment) {
 525                 u64 tmp = start;
 526                 unsigned rem;
 527
 528                 rem = do_div(tmp, alignment);
 529                 if (rem)
 530                         start += alignment - rem;
 531         }
 532
 533         return end >= start + size;
 534 }
 535
 536 static struct drm_mm_node *get_first_hole(const struct drm_mm *mm,
 537                 enum drm_mm_search_flags flags)
 538 {
 539         if (flags & DRM_MM_SEARCH_BOTTOM_UP) {
 540                 struct rb_node *node = rb_first(&mm->holes_tree);
 541
 542                 if (!node)
 543                         return NULL;
 544
 545                 return rb_entry(node, struct drm_mm_node, hole_node);
 546         } else if (flags & DRM_MM_SEARCH_BELOW) {
 547                 return list_entry((mm)->hole_stack.prev,
 548                                 struct drm_mm_node, hole_stack);
 549         } else {
 550                 return list_entry((mm)->hole_stack.next,
 551                                 struct drm_mm_node, hole_stack);
 552         }
 553 }
 554
 555 static struct drm_mm_node *get_next_hole(struct drm_mm_node *entry,
 556                 enum drm_mm_search_flags flags)
 557 {
 558         if (flags & DRM_MM_SEARCH_BOTTOM_UP) {
 559                 struct rb_node *node = rb_next(&entry->hole_node);
 560
 561                 if (!node)
 562                         return NULL;
 563
 564                 return rb_entry(node, struct drm_mm_node, hole_node);
 565         } else if (flags & DRM_MM_SEARCH_BELOW) {
 566                 return list_entry(entry->hole_stack.prev,
 567                                 struct drm_mm_node, hole_stack);
 568         } else {
 569                 return list_entry(entry->hole_stack.next,
 570                                 struct drm_mm_node, hole_stack);
 571         }
 572 }
 573
 574 static bool drm_mm_hole_traversal_condition(const struct drm_mm *mm,
 575                 struct drm_mm_node *entry, enum drm_mm_search_flags flags)
 576 {
 577         if (flags & DRM_MM_SEARCH_BOTTOM_UP)
 578                 return entry ? 1 : 0;
 579         else
 580                 return (&entry->hole_stack != &(mm)->hole_stack) ? 1 : 0;
 581 }
 582
 583 static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
 584                                                       u64 size,
 585                                                       unsigned alignment,
 586                                                       unsigned long color,
 587                                                       enum drm_mm_search_flags flags)
 588 {
 589         struct drm_mm_node *entry;
 590         struct drm_mm_node *best;
 591         u64 adj_start;
 592         u64 adj_end;
 593         u64 best_size;
 594
 595         BUG_ON(mm->scanned_blocks);
 596
 597         best = NULL;
 598         best_size = ~0UL;
 599
 600         for (entry = get_first_hole(mm, flags);
 601                         drm_mm_hole_traversal_condition(mm, entry, flags);
 602                         entry = get_next_hole(entry, flags)) {
 603                 u64 hole_size;
 604
 605                 adj_start = drm_mm_hole_node_start(entry);
 606                 adj_end = drm_mm_hole_node_end(entry);
 607                 hole_size = adj_end - adj_start;
 608
 609                 if (mm->color_adjust) {
 610                         mm->color_adjust(entry, color, &adj_start, &adj_end);
 611                         if (adj_end <= adj_start)
 612                                 continue;
 613                 }
 614
 615                 if (!check_free_hole(adj_start, adj_end, size, alignment))
 616                         continue;
 617
 618                 if (!(flags & DRM_MM_SEARCH_BEST))
 619                         return entry;
 620
 621                 if (hole_size < best_size) {
 622                         best = entry;
 623                         best_size = hole_size;
 624                 }
 625         }
 626
 627         return best;
 628 }
 629
 630 static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
 631                                                         u64 size,
 632                                                         unsigned alignment,
 633                                                         unsigned long color,
 634                                                         u64 start,
 635                                                         u64 end,
 636                                                         enum drm_mm_search_flags flags)
 637 {
 638         struct drm_mm_node *entry;
 639         struct drm_mm_node *best;
 640         u64 adj_start;
 641         u64 adj_end;
 642         u64 best_size;
 643
 644         BUG_ON(mm->scanned_blocks);
 645
 646         best = NULL;
 647         best_size = ~0UL;
 648
 649         for (entry = get_first_hole(mm, flags);
 650                         drm_mm_hole_traversal_condition(mm, entry, flags);
 651                         entry = get_next_hole(entry, flags)) {
 652                 u64 hole_size;
 653
 654                 adj_start = drm_mm_hole_node_start(entry);
 655                 adj_end = drm_mm_hole_node_end(entry);
 656                 hole_size = adj_end - adj_start;
 657
 658                 if (mm->color_adjust) {
 659                         mm->color_adjust(entry, color, &adj_start, &adj_end);
 660                         if (adj_end <= adj_start)
 661                                 continue;
 662                 }
 663
 664                 adj_start = max(adj_start, start);
 665                 adj_end = min(adj_end, end);
 666
 667                 if (!check_free_hole(adj_start, adj_end, size, alignment))
 668                         continue;
 669
 670                 if (!(flags & DRM_MM_SEARCH_BEST))
 671                         return entry;
 672
 673                 if (hole_size < best_size) {
 674                         best = entry;
 675                         best_size = hole_size;
 676                 }
 677         }
 678
 679         return best;
 680 }
 681
 682 /**
 683  * drm_mm_replace_node - move an allocation from @old to @new
 684  * @old: drm_mm_node to remove from the allocator
 685  * @new: drm_mm_node which should inherit @old's allocation
 686  *
 687  * This is useful for when drivers embed the drm_mm_node structure and hence
 688  * can't move allocations by reassigning pointers. It's a combination of remove
 689  * and insert with the guarantee that the allocation start will match.
 690  */
 691 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
 692 {
 693         list_replace(&old->node_list, &new->node_list);
 694         list_replace(&old->hole_stack, &new->hole_stack);
 695         rb_replace_node(&old->rb, &new->rb, &old->mm->interval_tree);
 696         new->hole_follows = old->hole_follows;
 697         new->mm = old->mm;
 698         new->start = old->start;
 699         new->size = old->size;
 700         new->color = old->color;
 701         new->__subtree_last = old->__subtree_last;
 702
 703         old->allocated = 0;
 704         new->allocated = 1;
 705
 706         if (old->hole_follows)
 707                 rb_replace_node(&old->hole_node, &new->hole_node,
 708                         &old->mm->holes_tree);
 709
 710 }
 711 EXPORT_SYMBOL(drm_mm_replace_node);
 712
 713 /**
 714  * DOC: lru scan roaster
 715  *
 716  * Very often GPUs need to have continuous allocations for a given object. When
 717  * evicting objects to make space for a new one it is therefore not most
 718  * efficient when we simply start to select all objects from the tail of an LRU
 719  * until there's a suitable hole: Especially for big objects or nodes that
 720  * otherwise have special allocation constraints there's a good chance we evict
 721  * lots of (smaller) objects unecessarily.
 722  *
 723  * The DRM range allocator supports this use-case through the scanning
 724  * interfaces. First a scan operation needs to be initialized with
 725  * drm_mm_init_scan() or drm_mm_init_scan_with_range(). The the driver adds
 726  * objects to the roaster (probably by walking an LRU list, but this can be
 727  * freely implemented) until a suitable hole is found or there's no further
 728  * evitable object.
 729  *
 730  * The the driver must walk through all objects again in exactly the reverse
 731  * order to restore the allocator state. Note that while the allocator is used
 732  * in the scan mode no other operation is allowed.
 733  *
 734  * Finally the driver evicts all objects selected in the scan. Adding and
 735  * removing an object is O(1), and since freeing a node is also O(1) the overall
 736  * complexity is O(scanned_objects). So like the free stack which needs to be
 737  * walked before a scan operation even begins this is linear in the number of
 738  * objects. It doesn't seem to hurt badly.
 739  */
 740
 741 /**
 742  * drm_mm_init_scan - initialize lru scanning
 743  * @mm: drm_mm to scan
 744  * @size: size of the allocation
 745  * @alignment: alignment of the allocation
 746  * @color: opaque tag value to use for the allocation
 747  *
 748  * This simply sets up the scanning routines with the parameters for the desired
 749  * hole. Note that there's no need to specify allocation flags, since they only
 750  * change the place a node is allocated from within a suitable hole.
 751  *
 752  * Warning:
 753  * As long as the scan list is non-empty, no other operations than
 754  * adding/removing nodes to/from the scan list are allowed.
 755  */
 756 void drm_mm_init_scan(struct drm_mm *mm,
 757                       u64 size,
 758                       unsigned alignment,
 759                       unsigned long color)
 760 {
 761         mm->scan_color = color;
 762         mm->scan_alignment = alignment;
 763         mm->scan_size = size;
 764         mm->scanned_blocks = 0;
 765         mm->scan_hit_start = 0;
 766         mm->scan_hit_end = 0;
 767         mm->scan_check_range = 0;
 768         mm->prev_scanned_node = NULL;
 769 }
 770 EXPORT_SYMBOL(drm_mm_init_scan);
 771
 772 /**
 773  * drm_mm_init_scan - initialize range-restricted lru scanning
 774  * @mm: drm_mm to scan
 775  * @size: size of the allocation
 776  * @alignment: alignment of the allocation
 777  * @color: opaque tag value to use for the allocation
 778  * @start: start of the allowed range for the allocation
 779  * @end: end of the allowed range for the allocation
 780  *
 781  * This simply sets up the scanning routines with the parameters for the desired
 782  * hole. Note that there's no need to specify allocation flags, since they only
 783  * change the place a node is allocated from within a suitable hole.
 784  *
 785  * Warning:
 786  * As long as the scan list is non-empty, no other operations than
 787  * adding/removing nodes to/from the scan list are allowed.
 788  */
 789 void drm_mm_init_scan_with_range(struct drm_mm *mm,
 790                                  u64 size,
 791                                  unsigned alignment,
 792                                  unsigned long color,
 793                                  u64 start,
 794                                  u64 end)
 795 {
 796         mm->scan_color = color;
 797         mm->scan_alignment = alignment;
 798         mm->scan_size = size;
 799         mm->scanned_blocks = 0;
 800         mm->scan_hit_start = 0;
 801         mm->scan_hit_end = 0;
 802         mm->scan_start = start;
 803         mm->scan_end = end;
 804         mm->scan_check_range = 1;
 805         mm->prev_scanned_node = NULL;
 806 }
 807 EXPORT_SYMBOL(drm_mm_init_scan_with_range);
 808
 809 /**
 810  * drm_mm_scan_add_block - add a node to the scan list
 811  * @node: drm_mm_node to add
 812  *
 813  * Add a node to the scan list that might be freed to make space for the desired
 814  * hole.
 815  *
 816  * Returns:
 817  * True if a hole has been found, false otherwise.
 818  */
 819 bool drm_mm_scan_add_block(struct drm_mm_node *node)
 820 {
 821         struct drm_mm *mm = node->mm;
 822         struct drm_mm_node *prev_node;
 823         u64 hole_start, hole_end;
 824         u64 adj_start, adj_end;
 825
 826         mm->scanned_blocks++;
 827
 828         BUG_ON(node->scanned_block);
 829         node->scanned_block = 1;
 830
 831         prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
 832                                node_list);
 833
 834         node->scanned_preceeds_hole = prev_node->hole_follows;
 835         prev_node->hole_follows = 1;
 836         list_del(&node->node_list);
 837         node->node_list.prev = &prev_node->node_list;
 838         node->node_list.next = &mm->prev_scanned_node->node_list;
 839         mm->prev_scanned_node = node;
 840
 841         adj_start = hole_start = drm_mm_hole_node_start(prev_node);
 842         adj_end = hole_end = drm_mm_hole_node_end(prev_node);
 843
 844         if (mm->scan_check_range) {
 845                 if (adj_start < mm->scan_start)
 846                         adj_start = mm->scan_start;
 847                 if (adj_end > mm->scan_end)
 848                         adj_end = mm->scan_end;
 849         }
 850
 851         if (mm->color_adjust)
 852                 mm->color_adjust(prev_node, mm->scan_color,
 853                                  &adj_start, &adj_end);
 854
 855         if (check_free_hole(adj_start, adj_end,
 856                             mm->scan_size, mm->scan_alignment)) {
 857                 mm->scan_hit_start = hole_start;
 858                 mm->scan_hit_end = hole_end;
 859                 return true;
 860         }
 861
 862         return false;
 863 }
 864 EXPORT_SYMBOL(drm_mm_scan_add_block);
 865
 866 /**
 867  * drm_mm_scan_remove_block - remove a node from the scan list
 868  * @node: drm_mm_node to remove
 869  *
 870  * Nodes _must_ be removed in the exact same order from the scan list as they
 871  * have been added, otherwise the internal state of the memory manager will be
 872  * corrupted.
 873  *
 874  * When the scan list is empty, the selected memory nodes can be freed. An
 875  * immediately following drm_mm_search_free with !DRM_MM_SEARCH_BEST will then
 876  * return the just freed block (because its at the top of the free_stack list).
 877  *
 878  * Returns:
 879  * True if this block should be evicted, false otherwise. Will always
 880  * return false when no hole has been found.
 881  */
 882 bool drm_mm_scan_remove_block(struct drm_mm_node *node)
 883 {
 884         struct drm_mm *mm = node->mm;
 885         struct drm_mm_node *prev_node;
 886
 887         mm->scanned_blocks--;
 888
 889         BUG_ON(!node->scanned_block);
 890         node->scanned_block = 0;
 891
 892         prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
 893                                node_list);
 894
 895         prev_node->hole_follows = node->scanned_preceeds_hole;
 896         list_add(&node->node_list, &prev_node->node_list);
 897
 898          return (drm_mm_hole_node_end(node) > mm->scan_hit_start &&
 899                  node->start < mm->scan_hit_end);
 900 }
 901 EXPORT_SYMBOL(drm_mm_scan_remove_block);
 902
 903 /**
 904  * drm_mm_clean - checks whether an allocator is clean
 905  * @mm: drm_mm allocator to check
 906  *
 907  * Returns:
 908  * True if the allocator is completely free, false if there's still a node
 909  * allocated in it.
 910  */
 911 bool drm_mm_clean(struct drm_mm * mm)
 912 {
 913         struct list_head *head = &mm->head_node.node_list;
 914
 915         return (head->next->next == head);
 916 }
 917 EXPORT_SYMBOL(drm_mm_clean);
 918
 919 /**
 920  * drm_mm_init - initialize a drm-mm allocator
 921  * @mm: the drm_mm structure to initialize
 922  * @start: start of the range managed by @mm
 923  * @size: end of the range managed by @mm
 924  *
 925  * Note that @mm must be cleared to 0 before calling this function.
 926  */
 927 void drm_mm_init(struct drm_mm * mm, u64 start, u64 size)
 928 {
 929         INIT_LIST_HEAD(&mm->hole_stack);
 930         mm->scanned_blocks = 0;
 931
 932         /* Clever trick to avoid a special case in the free hole tracking. */
 933         INIT_LIST_HEAD(&mm->head_node.node_list);
 934         mm->head_node.hole_follows = 1;
 935         mm->head_node.scanned_block = 0;
 936         mm->head_node.scanned_prev_free = 0;
 937         mm->head_node.scanned_next_free = 0;
 938         mm->head_node.mm = mm;
 939         mm->head_node.start = start + size;
 940         mm->head_node.size = start - mm->head_node.start;
 941         list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack);
 942
 943         mm->interval_tree = RB_ROOT;
 944         mm->color_adjust = NULL;
 945         mm->holes_tree = RB_ROOT;
 946         rb_insert_hole_node(&mm->head_node, mm);
 947 }
 948 EXPORT_SYMBOL(drm_mm_init);
 949
 950 /**
 951  * drm_mm_takedown - clean up a drm_mm allocator
 952  * @mm: drm_mm allocator to clean up
 953  *
 954  * Note that it is a bug to call this function on an allocator which is not
 955  * clean.
 956  */
 957 void drm_mm_takedown(struct drm_mm * mm)
 958 {
 959         WARN(!list_empty(&mm->head_node.node_list),
 960              "Memory manager not clean during takedown.\n");
 961 }
 962 EXPORT_SYMBOL(drm_mm_takedown);
 963
 964 static u64 drm_mm_debug_hole(struct drm_mm_node *entry,
 965                                      const char *prefix)
 966 {
 967         u64 hole_start, hole_end, hole_size;
 968
 969         if (entry->hole_follows) {
 970                 hole_start = drm_mm_hole_node_start(entry);
 971                 hole_end = drm_mm_hole_node_end(entry);
 972                 hole_size = hole_end - hole_start;
 973                 pr_debug("%s %#llx-%#llx: %llu: free\n", prefix, hole_start,
 974                          hole_end, hole_size);
 975                 return hole_size;
 976         }
 977
 978         return 0;
 979 }
 980
 981 /**
 982  * drm_mm_debug_table - dump allocator state to dmesg
 983  * @mm: drm_mm allocator to dump
 984  * @prefix: prefix to use for dumping to dmesg
 985  */
 986 void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
 987 {
 988         struct drm_mm_node *entry;
 989         u64 total_used = 0, total_free = 0, total = 0;
 990
 991         total_free += drm_mm_debug_hole(&mm->head_node, prefix);
 992
 993         drm_mm_for_each_node(entry, mm) {
 994                 pr_debug("%s %#llx-%#llx: %llu: used\n", prefix, entry->start,
 995                          entry->start + entry->size, entry->size);
 996                 total_used += entry->size;
 997                 total_free += drm_mm_debug_hole(entry, prefix);
 998         }
 999         total = total_free + total_used;
1000
1001         pr_debug("%s total: %llu, used %llu free %llu\n", prefix, total,
1002                  total_used, total_free);
1003 }
1004 EXPORT_SYMBOL(drm_mm_debug_table);
1005
1006 #if defined(CONFIG_DEBUG_FS)
1007 static u64 drm_mm_dump_hole(struct seq_file *m, struct drm_mm_node *entry)
1008 {
1009         u64 hole_start, hole_end, hole_size;
1010
1011         if (entry->hole_follows) {
1012                 hole_start = drm_mm_hole_node_start(entry);
1013                 hole_end = drm_mm_hole_node_end(entry);
1014                 hole_size = hole_end - hole_start;
1015                 seq_printf(m, "%#018llx-%#018llx: %llu: free\n", hole_start,
1016                            hole_end, hole_size);
1017                 return hole_size;
1018         }
1019
1020         return 0;
1021 }
1022
1023 /**
1024  * drm_mm_dump_table - dump allocator state to a seq_file
1025  * @m: seq_file to dump to
1026  * @mm: drm_mm allocator to dump
1027  */
1028 int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm)
1029 {
1030         struct drm_mm_node *entry;
1031         u64 total_used = 0, total_free = 0, total = 0;
1032
1033         total_free += drm_mm_dump_hole(m, &mm->head_node);
1034
1035         drm_mm_for_each_node(entry, mm) {
1036                 seq_printf(m, "%#018llx-%#018llx: %llu: used\n", entry->start,
1037                            entry->start + entry->size, entry->size);
1038                 total_used += entry->size;
1039                 total_free += drm_mm_dump_hole(m, entry);
1040         }
1041         total = total_free + total_used;
1042
1043         seq_printf(m, "total: %llu, used %llu free %llu\n", total,
1044                    total_used, total_free);
1045         return 0;
1046 }
1047 EXPORT_SYMBOL(drm_mm_dump_table);
1048 #endif