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 enum drm_mm_search_flags {
  57         DRM_MM_SEARCH_DEFAULT =         0,
  58         DRM_MM_SEARCH_BEST =            1 << 0,
  59         DRM_MM_SEARCH_BELOW =           1 << 1,
  60 };
  61
  62 enum drm_mm_allocator_flags {
  63         DRM_MM_CREATE_DEFAULT =         0,
  64         DRM_MM_CREATE_TOP =             1 << 0,
  65 };
  66
  67 #define DRM_MM_BOTTOMUP DRM_MM_SEARCH_DEFAULT, DRM_MM_CREATE_DEFAULT
  68 #define DRM_MM_TOPDOWN DRM_MM_SEARCH_BELOW, DRM_MM_CREATE_TOP
  69
  70 /**
  71  * struct drm_mm_node - allocated block in the DRM allocator
  72  *
  73  * This represents an allocated block in a &drm_mm allocator. Except for
  74  * pre-reserved nodes inserted using drm_mm_reserve_node() the structure is
  75  * entirely opaque and should only be accessed through the provided funcions.
  76  * Since allocation of these nodes is entirely handled by the driver they can be
  77  * embedded.
  78  */
  79 struct drm_mm_node {
  80         /** @color: Opaque driver-private tag. */
  81         unsigned long color;
  82         /** @start: Start address of the allocated block. */
  83         u64 start;
  84         /** @size: Size of the allocated block. */
  85         u64 size;
  86         /* private: */
  87         struct list_head node_list;
  88         struct list_head hole_stack;
  89         struct rb_node rb;
  90         unsigned hole_follows : 1;
  91         unsigned allocated : 1;
  92         bool scanned_block : 1;
  93         u64 __subtree_last;
  94         struct drm_mm *mm;
  95 #ifdef CONFIG_DRM_DEBUG_MM
  96         depot_stack_handle_t stack;
  97 #endif
  98 };
  99
 100 /**
 101  * struct drm_mm - DRM allocator
 102  *
 103  * DRM range allocator with a few special functions and features geared towards
 104  * managing GPU memory. Except for the @color_adjust callback the structure is
 105  * entirely opaque and should only be accessed through the provided functions
 106  * and macros. This structure can be embedded into larger driver structures.
 107  */
 108 struct drm_mm {
 109         /**
 110          * @color_adjust:
 111          *
 112          * Optional driver callback to further apply restrictions on a hole. The
 113          * node argument points at the node containing the hole from which the
 114          * block would be allocated (see drm_mm_hole_follows() and friends). The
 115          * other arguments are the size of the block to be allocated. The driver
 116          * can adjust the start and end as needed to e.g. insert guard pages.
 117          */
 118         void (*color_adjust)(const struct drm_mm_node *node,
 119                              unsigned long color,
 120                              u64 *start, u64 *end);
 121
 122         /* private: */
 123         /* List of all memory nodes that immediately precede a free hole. */
 124         struct list_head hole_stack;
 125         /* head_node.node_list is the list of all memory nodes, ordered
 126          * according to the (increasing) start address of the memory node. */
 127         struct drm_mm_node head_node;
 128         /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
 129         struct rb_root interval_tree;
 130
 131         unsigned long scan_active;
 132 };
 133
 134 /**
 135  * struct drm_mm_scan - DRM allocator eviction roaster data
 136  *
 137  * This structure tracks data needed for the eviction roaster set up using
 138  * drm_mm_scan_init(), and used with drm_mm_scan_add_block() and
 139  * drm_mm_scan_remove_block(). The structure is entirely opaque and should only
 140  * be accessed through the provided functions and macros. It is meant to be
 141  * allocated temporarily by the driver on the stack.
 142  */
 143 struct drm_mm_scan {
 144         /* private: */
 145         struct drm_mm *mm;
 146
 147         u64 size;
 148         u64 alignment;
 149         u64 remainder_mask;
 150
 151         u64 range_start;
 152         u64 range_end;
 153
 154         u64 hit_start;
 155         u64 hit_end;
 156
 157         unsigned long color;
 158         unsigned int flags;
 159 };
 160
 161 /**
 162  * drm_mm_node_allocated - checks whether a node is allocated
 163  * @node: drm_mm_node to check
 164  *
 165  * Drivers are required to clear a node prior to using it with the
 166  * drm_mm range manager.
 167  *
 168  * Drivers should use this helper for proper encapsulation of drm_mm
 169  * internals.
 170  *
 171  * Returns:
 172  * True if the @node is allocated.
 173  */
 174 static inline bool drm_mm_node_allocated(const struct drm_mm_node *node)
 175 {
 176         return node->allocated;
 177 }
 178
 179 /**
 180  * drm_mm_initialized - checks whether an allocator is initialized
 181  * @mm: drm_mm to check
 182  *
 183  * Drivers should clear the struct drm_mm prior to initialisation if they
 184  * want to use this function.
 185  *
 186  * Drivers should use this helper for proper encapsulation of drm_mm
 187  * internals.
 188  *
 189  * Returns:
 190  * True if the @mm is initialized.
 191  */
 192 static inline bool drm_mm_initialized(const struct drm_mm *mm)
 193 {
 194         return mm->hole_stack.next;
 195 }
 196
 197 /**
 198  * drm_mm_hole_follows - checks whether a hole follows this node
 199  * @node: drm_mm_node to check
 200  *
 201  * Holes are embedded into the drm_mm using the tail of a drm_mm_node.
 202  * If you wish to know whether a hole follows this particular node,
 203  * query this function. See also drm_mm_hole_node_start() and
 204  * drm_mm_hole_node_end().
 205  *
 206  * Returns:
 207  * True if a hole follows the @node.
 208  */
 209 static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
 210 {
 211         return node->hole_follows;
 212 }
 213
 214 static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
 215 {
 216         return hole_node->start + hole_node->size;
 217 }
 218
 219 /**
 220  * drm_mm_hole_node_start - computes the start of the hole following @node
 221  * @hole_node: drm_mm_node which implicitly tracks the following hole
 222  *
 223  * This is useful for driver-specific debug dumpers. Otherwise drivers should
 224  * not inspect holes themselves. Drivers must check first whether a hole indeed
 225  * follows by looking at drm_mm_hole_follows()
 226  *
 227  * Returns:
 228  * Start of the subsequent hole.
 229  */
 230 static inline u64 drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
 231 {
 232         DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node));
 233         return __drm_mm_hole_node_start(hole_node);
 234 }
 235
 236 static inline u64 __drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
 237 {
 238         return list_next_entry(hole_node, node_list)->start;
 239 }
 240
 241 /**
 242  * drm_mm_hole_node_end - computes the end of the hole following @node
 243  * @hole_node: drm_mm_node which implicitly tracks the following hole
 244  *
 245  * This is useful for driver-specific debug dumpers. Otherwise drivers should
 246  * not inspect holes themselves. Drivers must check first whether a hole indeed
 247  * follows by looking at drm_mm_hole_follows().
 248  *
 249  * Returns:
 250  * End of the subsequent hole.
 251  */
 252 static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
 253 {
 254         return __drm_mm_hole_node_end(hole_node);
 255 }
 256
 257 /**
 258  * drm_mm_nodes - list of nodes under the drm_mm range manager
 259  * @mm: the struct drm_mm range manger
 260  *
 261  * As the drm_mm range manager hides its node_list deep with its
 262  * structure, extracting it looks painful and repetitive. This is
 263  * not expected to be used outside of the drm_mm_for_each_node()
 264  * macros and similar internal functions.
 265  *
 266  * Returns:
 267  * The node list, may be empty.
 268  */
 269 #define drm_mm_nodes(mm) (&(mm)->head_node.node_list)
 270
 271 /**
 272  * drm_mm_for_each_node - iterator to walk over all allocated nodes
 273  * @entry: &struct drm_mm_node to assign to in each iteration step
 274  * @mm: &drm_mm allocator to walk
 275  *
 276  * This iterator walks over all nodes in the range allocator. It is implemented
 277  * with list_for_each(), so not save against removal of elements.
 278  */
 279 #define drm_mm_for_each_node(entry, mm) \
 280         list_for_each_entry(entry, drm_mm_nodes(mm), node_list)
 281
 282 /**
 283  * drm_mm_for_each_node_safe - iterator to walk over all allocated nodes
 284  * @entry: &struct drm_mm_node to assign to in each iteration step
 285  * @next: &struct drm_mm_node to store the next step
 286  * @mm: &drm_mm allocator to walk
 287  *
 288  * This iterator walks over all nodes in the range allocator. It is implemented
 289  * with list_for_each_safe(), so save against removal of elements.
 290  */
 291 #define drm_mm_for_each_node_safe(entry, next, mm) \
 292         list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)
 293
 294 #define __drm_mm_for_each_hole(entry, mm, hole_start, hole_end, backwards) \
 295         for (entry = list_entry((backwards) ? (mm)->hole_stack.prev : (mm)->hole_stack.next, struct drm_mm_node, hole_stack); \
 296              &entry->hole_stack != &(mm)->hole_stack ? \
 297              hole_start = drm_mm_hole_node_start(entry), \
 298              hole_end = drm_mm_hole_node_end(entry), \
 299              1 : 0; \
 300              entry = list_entry((backwards) ? entry->hole_stack.prev : entry->hole_stack.next, struct drm_mm_node, hole_stack))
 301
 302 /**
 303  * drm_mm_for_each_hole - iterator to walk over all holes
 304  * @entry: &drm_mm_node used internally to track progress
 305  * @mm: &drm_mm allocator to walk
 306  * @hole_start: ulong variable to assign the hole start to on each iteration
 307  * @hole_end: ulong variable to assign the hole end to on each iteration
 308  *
 309  * This iterator walks over all holes in the range allocator. It is implemented
 310  * with list_for_each(), so not save against removal of elements. @entry is used
 311  * internally and will not reflect a real drm_mm_node for the very first hole.
 312  * Hence users of this iterator may not access it.
 313  *
 314  * Implementation Note:
 315  * We need to inline list_for_each_entry in order to be able to set hole_start
 316  * and hole_end on each iteration while keeping the macro sane.
 317  *
 318  * The __drm_mm_for_each_hole version is similar, but with added support for
 319  * going backwards.
 320  */
 321 #define drm_mm_for_each_hole(entry, mm, hole_start, hole_end) \
 322         __drm_mm_for_each_hole(entry, mm, hole_start, hole_end, 0)
 323
 324 /*
 325  * Basic range manager support (drm_mm.c)
 326  */
 327 int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node);
 328 int drm_mm_insert_node_in_range_generic(struct drm_mm *mm,
 329                                         struct drm_mm_node *node,
 330                                         u64 size,
 331                                         u64 alignment,
 332                                         unsigned long color,
 333                                         u64 start,
 334                                         u64 end,
 335                                         enum drm_mm_search_flags sflags,
 336                                         enum drm_mm_allocator_flags aflags);
 337
 338 /**
 339  * drm_mm_insert_node_in_range - ranged search for space and insert @node
 340  * @mm: drm_mm to allocate from
 341  * @node: preallocate node to insert
 342  * @size: size of the allocation
 343  * @alignment: alignment of the allocation
 344  * @start: start of the allowed range for this node
 345  * @end: end of the allowed range for this node
 346  * @flags: flags to fine-tune the allocation
 347  *
 348  * This is a simplified version of drm_mm_insert_node_in_range_generic() with
 349  * @color set to 0.
 350  *
 351  * The preallocated node must be cleared to 0.
 352  *
 353  * Returns:
 354  * 0 on success, -ENOSPC if there's no suitable hole.
 355  */
 356 static inline int drm_mm_insert_node_in_range(struct drm_mm *mm,
 357                                               struct drm_mm_node *node,
 358                                               u64 size,
 359                                               u64 alignment,
 360                                               u64 start,
 361                                               u64 end,
 362                                               enum drm_mm_search_flags flags)
 363 {
 364         return drm_mm_insert_node_in_range_generic(mm, node, size, alignment,
 365                                                    0, start, end, flags,
 366                                                    DRM_MM_CREATE_DEFAULT);
 367 }
 368
 369 /**
 370  * drm_mm_insert_node_generic - search for space and insert @node
 371  * @mm: drm_mm to allocate from
 372  * @node: preallocate node to insert
 373  * @size: size of the allocation
 374  * @alignment: alignment of the allocation
 375  * @color: opaque tag value to use for this node
 376  * @sflags: flags to fine-tune the allocation search
 377  * @aflags: flags to fine-tune the allocation behavior
 378  *
 379  * This is a simplified version of drm_mm_insert_node_in_range_generic() with no
 380  * range restrictions applied.
 381  *
 382  * The preallocated node must be cleared to 0.
 383  *
 384  * Returns:
 385  * 0 on success, -ENOSPC if there's no suitable hole.
 386  */
 387 static inline int
 388 drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
 389                            u64 size, u64 alignment,
 390                            unsigned long color,
 391                            enum drm_mm_search_flags sflags,
 392                            enum drm_mm_allocator_flags aflags)
 393 {
 394         return drm_mm_insert_node_in_range_generic(mm, node,
 395                                                    size, alignment, 0,
 396                                                    0, U64_MAX,
 397                                                    sflags, aflags);
 398 }
 399
 400 /**
 401  * drm_mm_insert_node - search for space and insert @node
 402  * @mm: drm_mm to allocate from
 403  * @node: preallocate node to insert
 404  * @size: size of the allocation
 405  * @alignment: alignment of the allocation
 406  * @flags: flags to fine-tune the allocation
 407  *
 408  * This is a simplified version of drm_mm_insert_node_generic() with @color set
 409  * to 0.
 410  *
 411  * The preallocated node must be cleared to 0.
 412  *
 413  * Returns:
 414  * 0 on success, -ENOSPC if there's no suitable hole.
 415  */
 416 static inline int drm_mm_insert_node(struct drm_mm *mm,
 417                                      struct drm_mm_node *node,
 418                                      u64 size,
 419                                      u64 alignment,
 420                                      enum drm_mm_search_flags flags)
 421 {
 422         return drm_mm_insert_node_generic(mm, node,
 423                                           size, alignment, 0,
 424                                           flags, DRM_MM_CREATE_DEFAULT);
 425 }
 426
 427 void drm_mm_remove_node(struct drm_mm_node *node);
 428 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new);
 429 void drm_mm_init(struct drm_mm *mm, u64 start, u64 size);
 430 void drm_mm_takedown(struct drm_mm *mm);
 431
 432 /**
 433  * drm_mm_clean - checks whether an allocator is clean
 434  * @mm: drm_mm allocator to check
 435  *
 436  * Returns:
 437  * True if the allocator is completely free, false if there's still a node
 438  * allocated in it.
 439  */
 440 static inline bool drm_mm_clean(const struct drm_mm *mm)
 441 {
 442         return list_empty(drm_mm_nodes(mm));
 443 }
 444
 445 struct drm_mm_node *
 446 __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);
 447
 448 /**
 449  * drm_mm_for_each_node_in_range - iterator to walk over a range of
 450  * allocated nodes
 451  * @node__: drm_mm_node structure to assign to in each iteration step
 452  * @mm__: drm_mm allocator to walk
 453  * @start__: starting offset, the first node will overlap this
 454  * @end__: ending offset, the last node will start before this (but may overlap)
 455  *
 456  * This iterator walks over all nodes in the range allocator that lie
 457  * between @start and @end. It is implemented similarly to list_for_each(),
 458  * but using the internal interval tree to accelerate the search for the
 459  * starting node, and so not safe against removal of elements. It assumes
 460  * that @end is within (or is the upper limit of) the drm_mm allocator.
 461  */
 462 #define drm_mm_for_each_node_in_range(node__, mm__, start__, end__)     \
 463         for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)-1); \
 464              node__ && node__->start < (end__);                         \
 465              node__ = list_next_entry(node__, node_list))
 466
 467 void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
 468                                  struct drm_mm *mm,
 469                                  u64 size, u64 alignment, unsigned long color,
 470                                  u64 start, u64 end,
 471                                  unsigned int flags);
 472
 473 /**
 474  * drm_mm_scan_init - initialize lru scanning
 475  * @scan: scan state
 476  * @mm: drm_mm to scan
 477  * @size: size of the allocation
 478  * @alignment: alignment of the allocation
 479  * @color: opaque tag value to use for the allocation
 480  * @flags: flags to specify how the allocation will be performed afterwards
 481  *
 482  * This is a simplified version of drm_mm_scan_init_with_range() with no range
 483  * restrictions applied.
 484  *
 485  * This simply sets up the scanning routines with the parameters for the desired
 486  * hole.
 487  *
 488  * Warning:
 489  * As long as the scan list is non-empty, no other operations than
 490  * adding/removing nodes to/from the scan list are allowed.
 491  */
 492 static inline void drm_mm_scan_init(struct drm_mm_scan *scan,
 493                                     struct drm_mm *mm,
 494                                     u64 size,
 495                                     u64 alignment,
 496                                     unsigned long color,
 497                                     unsigned int flags)
 498 {
 499         drm_mm_scan_init_with_range(scan, mm,
 500                                     size, alignment, color,
 501                                     0, U64_MAX,
 502                                     flags);
 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