include/drm/drm_mm.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. USA.
   4  * Copyright 2016 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 above copyright notice and this permission notice (including the
  16  * next paragraph) shall be included in all copies or substantial portions
  17  * of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
  22  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
  23  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  24  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
  25  * USE OR OTHER DEALINGS IN THE SOFTWARE.
  26  *
  27  *
  28  **************************************************************************/
  29 /*
  30  * Authors:
  31  * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
  32  */
  33
  34 #ifndef _DRM_MM_H_
  35 #define _DRM_MM_H_
  36
  37 /*
  38  * Generic range manager structs
  39  */
  40 #include <linux/bug.h>
  41 #include <linux/rbtree.h>
  42 #include <linux/kernel.h>
  43 #include <linux/list.h>
  44 #include <linux/spinlock.h>
  45 #ifdef CONFIG_DRM_DEBUG_MM
  46 #include <linux/stackdepot.h>
  47 #endif
  48 #include <drm/drm_print.h>
  49
  50 #ifdef CONFIG_DRM_DEBUG_MM
  51 #define DRM_MM_BUG_ON(expr) BUG_ON(expr)
  52 #else
  53 #define DRM_MM_BUG_ON(expr) BUILD_BUG_ON_INVALID(expr)
  54 #endif
  55
  56 /**
  57  * enum drm_mm_insert_mode - control search and allocation behaviour
  58  *
  59  * The &struct drm_mm range manager supports finding a suitable modes using
  60  * a number of search trees. These trees are oranised by size, by address and
  61  * in most recent eviction order. This allows the user to find either the
  62  * smallest hole to reuse, the lowest or highest address to reuse, or simply
  63  * reuse the most recent eviction that fits. When allocating the &drm_mm_node
  64  * from within the hole, the &drm_mm_insert_mode also dictate whether to
  65  * allocate the lowest matching address or the highest.
  66  */
  67 enum drm_mm_insert_mode {
  68         /**
  69          * @DRM_MM_INSERT_BEST:
  70          *
  71          * Search for the smallest hole (within the search range) that fits
  72          * the desired node.
  73          *
  74          * Allocates the node from the bottom of the found hole.
  75          */
  76         DRM_MM_INSERT_BEST = 0,
  77
  78         /**
  79          * @DRM_MM_INSERT_LOW:
  80          *
  81          * Search for the lowest hole (address closest to 0, within the search
  82          * range) that fits the desired node.
  83          *
  84          * Allocates the node from the bottom of the found hole.
  85          */
  86         DRM_MM_INSERT_LOW,
  87
  88         /**
  89          * @DRM_MM_INSERT_HIGH:
  90          *
  91          * Search for the highest hole (address closest to U64_MAX, within the
  92          * search range) that fits the desired node.
  93          *
  94          * Allocates the node from the *top* of the found hole. The specified
  95          * alignment for the node is applied to the base of the node
  96          * (&drm_mm_node.start).
  97          */
  98         DRM_MM_INSERT_HIGH,
  99
 100         /**
 101          * @DRM_MM_INSERT_EVICT:
 102          *
 103          * Search for the most recently evicted hole (within the search range)
 104          * that fits the desired node. This is appropriate for use immediately
 105          * after performing an eviction scan (see drm_mm_scan_init()) and
 106          * removing the selected nodes to form a hole.
 107          *
 108          * Allocates the node from the bottom of the found hole.
 109          */
 110         DRM_MM_INSERT_EVICT,
 111 };
 112
 113 /**
 114  * struct drm_mm_node - allocated block in the DRM allocator
 115  *
 116  * This represents an allocated block in a &drm_mm allocator. Except for
 117  * pre-reserved nodes inserted using drm_mm_reserve_node() the structure is
 118  * entirely opaque and should only be accessed through the provided funcions.
 119  * Since allocation of these nodes is entirely handled by the driver they can be
 120  * embedded.
 121  */
 122 struct drm_mm_node {
 123         /** @color: Opaque driver-private tag. */
 124         unsigned long color;
 125         /** @start: Start address of the allocated block. */
 126         u64 start;
 127         /** @size: Size of the allocated block. */
 128         u64 size;
 129         /* private: */
 130         struct drm_mm *mm;
 131         struct list_head node_list;
 132         struct list_head hole_stack;
 133         struct rb_node rb;
 134         struct rb_node rb_hole_size;
 135         struct rb_node rb_hole_addr;
 136         u64 __subtree_last;
 137         u64 hole_size;
 138         bool allocated : 1;
 139         bool scanned_block : 1;
 140 #ifdef CONFIG_DRM_DEBUG_MM
 141         depot_stack_handle_t stack;
 142 #endif
 143 };
 144
 145 /**
 146  * struct drm_mm - DRM allocator
 147  *
 148  * DRM range allocator with a few special functions and features geared towards
 149  * managing GPU memory. Except for the @color_adjust callback the structure is
 150  * entirely opaque and should only be accessed through the provided functions
 151  * and macros. This structure can be embedded into larger driver structures.
 152  */
 153 struct drm_mm {
 154         /**
 155          * @color_adjust:
 156          *
 157          * Optional driver callback to further apply restrictions on a hole. The
 158          * node argument points at the node containing the hole from which the
 159          * block would be allocated (see drm_mm_hole_follows() and friends). The
 160          * other arguments are the size of the block to be allocated. The driver
 161          * can adjust the start and end as needed to e.g. insert guard pages.
 162          */
 163         void (*color_adjust)(const struct drm_mm_node *node,
 164                              unsigned long color,
 165                              u64 *start, u64 *end);
 166
 167         /* private: */
 168         /* List of all memory nodes that immediately precede a free hole. */
 169         struct list_head hole_stack;
 170         /* head_node.node_list is the list of all memory nodes, ordered
 171          * according to the (increasing) start address of the memory node. */
 172         struct drm_mm_node head_node;
 173         /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
 174         struct rb_root interval_tree;
 175         struct rb_root holes_size;
 176         struct rb_root holes_addr;
 177
 178         unsigned long scan_active;
 179 };
 180
 181 /**
 182  * struct drm_mm_scan - DRM allocator eviction roaster data
 183  *
 184  * This structure tracks data needed for the eviction roaster set up using
 185  * drm_mm_scan_init(), and used with drm_mm_scan_add_block() and
 186  * drm_mm_scan_remove_block(). The structure is entirely opaque and should only
 187  * be accessed through the provided functions and macros. It is meant to be
 188  * allocated temporarily by the driver on the stack.
 189  */
 190 struct drm_mm_scan {
 191         /* private: */
 192         struct drm_mm *mm;
 193
 194         u64 size;
 195         u64 alignment;
 196         u64 remainder_mask;
 197
 198         u64 range_start;
 199         u64 range_end;
 200
 201         u64 hit_start;
 202         u64 hit_end;
 203
 204         unsigned long color;
 205         enum drm_mm_insert_mode mode;
 206 };
 207
 208 /**
 209  * drm_mm_node_allocated - checks whether a node is allocated
 210  * @node: drm_mm_node to check
 211  *
 212  * Drivers are required to clear a node prior to using it with the
 213  * drm_mm range manager.
 214  *
 215  * Drivers should use this helper for proper encapsulation of drm_mm
 216  * internals.
 217  *
 218  * Returns:
 219  * True if the @node is allocated.
 220  */
 221 static inline bool drm_mm_node_allocated(const struct drm_mm_node *node)
 222 {
 223         return node->allocated;
 224 }
 225
 226 /**
 227  * drm_mm_initialized - checks whether an allocator is initialized
 228  * @mm: drm_mm to check
 229  *
 230  * Drivers should clear the struct drm_mm prior to initialisation if they
 231  * want to use this function.
 232  *
 233  * Drivers should use this helper for proper encapsulation of drm_mm
 234  * internals.
 235  *
 236  * Returns:
 237  * True if the @mm is initialized.
 238  */
 239 static inline bool drm_mm_initialized(const struct drm_mm *mm)
 240 {
 241         return mm->hole_stack.next;
 242 }
 243
 244 /**
 245  * drm_mm_hole_follows - checks whether a hole follows this node
 246  * @node: drm_mm_node to check
 247  *
 248  * Holes are embedded into the drm_mm using the tail of a drm_mm_node.
 249  * If you wish to know whether a hole follows this particular node,
 250  * query this function. See also drm_mm_hole_node_start() and
 251  * drm_mm_hole_node_end().
 252  *
 253  * Returns:
 254  * True if a hole follows the @node.
 255  */
 256 static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
 257 {
 258         return node->hole_size;
 259 }
 260
 261 static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
 262 {
 263         return hole_node->start + hole_node->size;
 264 }
 265
 266 /**
 267  * drm_mm_hole_node_start - computes the start of the hole following @node
 268  * @hole_node: drm_mm_node which implicitly tracks the following hole
 269  *
 270  * This is useful for driver-specific debug dumpers. Otherwise drivers should
 271  * not inspect holes themselves. Drivers must check first whether a hole indeed
 272  * follows by looking at drm_mm_hole_follows()
 273  *
 274  * Returns:
 275  * Start of the subsequent hole.
 276  */
 277 static inline u64 drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
 278 {
 279         DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node));
 280         return __drm_mm_hole_node_start(hole_node);
 281 }
 282
 283 static inline u64 __drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
 284 {
 285         return list_next_entry(hole_node, node_list)->start;
 286 }
 287
 288 /**
 289  * drm_mm_hole_node_end - computes the end of the hole following @node
 290  * @hole_node: drm_mm_node which implicitly tracks the following hole
 291  *
 292  * This is useful for driver-specific debug dumpers. Otherwise drivers should
 293  * not inspect holes themselves. Drivers must check first whether a hole indeed
 294  * follows by looking at drm_mm_hole_follows().
 295  *
 296  * Returns:
 297  * End of the subsequent hole.
 298  */
 299 static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
 300 {
 301         return __drm_mm_hole_node_end(hole_node);
 302 }
 303
 304 /**
 305  * drm_mm_nodes - list of nodes under the drm_mm range manager
 306  * @mm: the struct drm_mm range manger
 307  *
 308  * As the drm_mm range manager hides its node_list deep with its
 309  * structure, extracting it looks painful and repetitive. This is
 310  * not expected to be used outside of the drm_mm_for_each_node()
 311  * macros and similar internal functions.
 312  *
 313  * Returns:
 314  * The node list, may be empty.
 315  */
 316 #define drm_mm_nodes(mm) (&(mm)->head_node.node_list)
 317
 318 /**
 319  * drm_mm_for_each_node - iterator to walk over all allocated nodes
 320  * @entry: &struct drm_mm_node to assign to in each iteration step
 321  * @mm: &drm_mm allocator to walk
 322  *
 323  * This iterator walks over all nodes in the range allocator. It is implemented
 324  * with list_for_each(), so not save against removal of elements.
 325  */
 326 #define drm_mm_for_each_node(entry, mm) \
 327         list_for_each_entry(entry, drm_mm_nodes(mm), node_list)
 328
 329 /**
 330  * drm_mm_for_each_node_safe - iterator to walk over all allocated nodes
 331  * @entry: &struct drm_mm_node to assign to in each iteration step
 332  * @next: &struct drm_mm_node to store the next step
 333  * @mm: &drm_mm allocator to walk
 334  *
 335  * This iterator walks over all nodes in the range allocator. It is implemented
 336  * with list_for_each_safe(), so save against removal of elements.
 337  */
 338 #define drm_mm_for_each_node_safe(entry, next, mm) \
 339         list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)
 340
 341 /**
 342  * drm_mm_for_each_hole - iterator to walk over all holes
 343  * @pos: &drm_mm_node used internally to track progress
 344  * @mm: &drm_mm allocator to walk
 345  * @hole_start: ulong variable to assign the hole start to on each iteration
 346  * @hole_end: ulong variable to assign the hole end to on each iteration
 347  *
 348  * This iterator walks over all holes in the range allocator. It is implemented
 349  * with list_for_each(), so not save against removal of elements. @entry is used
 350  * internally and will not reflect a real drm_mm_node for the very first hole.
 351  * Hence users of this iterator may not access it.
 352  *
 353  * Implementation Note:
 354  * We need to inline list_for_each_entry in order to be able to set hole_start
 355  * and hole_end on each iteration while keeping the macro sane.
 356  */
 357 #define drm_mm_for_each_hole(pos, mm, hole_start, hole_end) \
 358         for (pos = list_first_entry(&(mm)->hole_stack, \
 359                                     typeof(*pos), hole_stack); \
 360              &pos->hole_stack != &(mm)->hole_stack ? \
 361              hole_start = drm_mm_hole_node_start(pos), \
 362              hole_end = hole_start + pos->hole_size, \
 363              1 : 0; \
 364              pos = list_next_entry(pos, hole_stack))
 365
 366 /*
 367  * Basic range manager support (drm_mm.c)
 368  */
 369 int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node);
 370 int drm_mm_insert_node_in_range(struct drm_mm *mm,
 371                                 struct drm_mm_node *node,
 372                                 u64 size,
 373                                 u64 alignment,
 374                                 unsigned long color,
 375                                 u64 start,
 376                                 u64 end,
 377                                 enum drm_mm_insert_mode mode);
 378
 379 /**
 380  * drm_mm_insert_node_generic - search for space and insert @node
 381  * @mm: drm_mm to allocate from
 382  * @node: preallocate node to insert
 383  * @size: size of the allocation
 384  * @alignment: alignment of the allocation
 385  * @color: opaque tag value to use for this node
 386  * @mode: fine-tune the allocation search and placement
 387  *
 388  * This is a simplified version of drm_mm_insert_node_in_range_generic() with no
 389  * range restrictions applied.
 390  *
 391  * The preallocated node must be cleared to 0.
 392  *
 393  * Returns:
 394  * 0 on success, -ENOSPC if there's no suitable hole.
 395  */
 396 static inline int
 397 drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
 398                            u64 size, u64 alignment,
 399                            unsigned long color,
 400                            enum drm_mm_insert_mode mode)
 401 {
 402         return drm_mm_insert_node_in_range(mm, node,
 403                                            size, alignment, color,
 404                                            0, U64_MAX, mode);
 405 }
 406
 407 /**
 408  * drm_mm_insert_node - search for space and insert @node
 409  * @mm: drm_mm to allocate from
 410  * @node: preallocate node to insert
 411  * @size: size of the allocation
 412  *
 413  * This is a simplified version of drm_mm_insert_node_generic() with @color set
 414  * to 0.
 415  *
 416  * The preallocated node must be cleared to 0.
 417  *
 418  * Returns:
 419  * 0 on success, -ENOSPC if there's no suitable hole.
 420  */
 421 static inline int drm_mm_insert_node(struct drm_mm *mm,
 422                                      struct drm_mm_node *node,
 423                                      u64 size)
 424 {
 425         return drm_mm_insert_node_generic(mm, node, size, 0, 0, 0);
 426 }
 427
 428 void drm_mm_remove_node(struct drm_mm_node *node);
 429 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new);
 430 void drm_mm_init(struct drm_mm *mm, u64 start, u64 size);
 431 void drm_mm_takedown(struct drm_mm *mm);
 432
 433 /**
 434  * drm_mm_clean - checks whether an allocator is clean
 435  * @mm: drm_mm allocator to check
 436  *
 437  * Returns:
 438  * True if the allocator is completely free, false if there's still a node
 439  * allocated in it.
 440  */
 441 static inline bool drm_mm_clean(const struct drm_mm *mm)
 442 {
 443         return list_empty(drm_mm_nodes(mm));
 444 }
 445
 446 struct drm_mm_node *
 447 __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);
 448
 449 /**
 450  * drm_mm_for_each_node_in_range - iterator to walk over a range of
 451  * allocated nodes
 452  * @node__: drm_mm_node structure to assign to in each iteration step
 453  * @mm__: drm_mm allocator to walk
 454  * @start__: starting offset, the first node will overlap this
 455  * @end__: ending offset, the last node will start before this (but may overlap)
 456  *
 457  * This iterator walks over all nodes in the range allocator that lie
 458  * between @start and @end. It is implemented similarly to list_for_each(),
 459  * but using the internal interval tree to accelerate the search for the
 460  * starting node, and so not safe against removal of elements. It assumes
 461  * that @end is within (or is the upper limit of) the drm_mm allocator.
 462  */
 463 #define drm_mm_for_each_node_in_range(node__, mm__, start__, end__)     \
 464         for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)-1); \
 465              node__ && node__->start < (end__);                         \
 466              node__ = list_next_entry(node__, node_list))
 467
 468 void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
 469                                  struct drm_mm *mm,
 470                                  u64 size, u64 alignment, unsigned long color,
 471                                  u64 start, u64 end,
 472                                  enum drm_mm_insert_mode mode);
 473
 474 /**
 475  * drm_mm_scan_init - initialize lru scanning
 476  * @scan: scan state
 477  * @mm: drm_mm to scan
 478  * @size: size of the allocation
 479  * @alignment: alignment of the allocation
 480  * @color: opaque tag value to use for the allocation
 481  * @mode: fine-tune the allocation search and placement
 482  *
 483  * This is a simplified version of drm_mm_scan_init_with_range() with no range
 484  * restrictions applied.
 485  *
 486  * This simply sets up the scanning routines with the parameters for the desired
 487  * hole.
 488  *
 489  * Warning:
 490  * As long as the scan list is non-empty, no other operations than
 491  * adding/removing nodes to/from the scan list are allowed.
 492  */
 493 static inline void drm_mm_scan_init(struct drm_mm_scan *scan,
 494                                     struct drm_mm *mm,
 495                                     u64 size,
 496                                     u64 alignment,
 497                                     unsigned long color,
 498                                     enum drm_mm_insert_mode mode)
 499 {
 500         drm_mm_scan_init_with_range(scan, mm,
 501                                     size, alignment, color,
 502                                     0, U64_MAX, mode);
 503 }
 504
 505 bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
 506                            struct drm_mm_node *node);
 507 bool drm_mm_scan_remove_block(struct drm_mm_scan *scan,
 508                               struct drm_mm_node *node);
 509 struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan);
 510
 511 void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p);
 512
 513 #endif