1 /**************************************************************************
3 * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. USA.
4 * Copyright 2016 Intel Corporation
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:
15 * The above copyright notice and this permission notice (including the
16 * next paragraph) shall be included in all copies or substantial portions
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.
28 **************************************************************************/
31 * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
38 * Generic range manager structs
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>
48 #include <drm/drm_print.h>
50 #ifdef CONFIG_DRM_DEBUG_MM
51 #define DRM_MM_BUG_ON(expr) BUG_ON(expr)
53 #define DRM_MM_BUG_ON(expr) BUILD_BUG_ON_INVALID(expr)
57 * enum drm_mm_insert_mode - control search and allocation behaviour
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.
67 enum drm_mm_insert_mode {
69 * @DRM_MM_INSERT_BEST:
71 * Search for the smallest hole (within the search range) that fits
74 * Allocates the node from the bottom of the found hole.
76 DRM_MM_INSERT_BEST = 0,
81 * Search for the lowest hole (address closest to 0, within the search
82 * range) that fits the desired node.
84 * Allocates the node from the bottom of the found hole.
89 * @DRM_MM_INSERT_HIGH:
91 * Search for the highest hole (address closest to U64_MAX, within the
92 * search range) that fits the desired node.
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).
101 * @DRM_MM_INSERT_EVICT:
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.
108 * Allocates the node from the bottom of the found hole.
114 * struct drm_mm_node - allocated block in the DRM allocator
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
123 /** @color: Opaque driver-private tag. */
125 /** @start: Start address of the allocated block. */
127 /** @size: Size of the allocated block. */
131 struct list_head node_list;
132 struct list_head hole_stack;
134 struct rb_node rb_hole_size;
135 struct rb_node rb_hole_addr;
139 bool scanned_block : 1;
140 #ifdef CONFIG_DRM_DEBUG_MM
141 depot_stack_handle_t stack;
146 * struct drm_mm - DRM allocator
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.
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.
163 void (*color_adjust)(const struct drm_mm_node *node,
165 u64 *start, u64 *end);
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;
178 unsigned long scan_active;
182 * struct drm_mm_scan - DRM allocator eviction roaster data
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.
205 enum drm_mm_insert_mode mode;
209 * drm_mm_node_allocated - checks whether a node is allocated
210 * @node: drm_mm_node to check
212 * Drivers are required to clear a node prior to using it with the
213 * drm_mm range manager.
215 * Drivers should use this helper for proper encapsulation of drm_mm
219 * True if the @node is allocated.
221 static inline bool drm_mm_node_allocated(const struct drm_mm_node *node)
223 return node->allocated;
227 * drm_mm_initialized - checks whether an allocator is initialized
228 * @mm: drm_mm to check
230 * Drivers should clear the struct drm_mm prior to initialisation if they
231 * want to use this function.
233 * Drivers should use this helper for proper encapsulation of drm_mm
237 * True if the @mm is initialized.
239 static inline bool drm_mm_initialized(const struct drm_mm *mm)
241 return mm->hole_stack.next;
245 * drm_mm_hole_follows - checks whether a hole follows this node
246 * @node: drm_mm_node to check
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().
254 * True if a hole follows the @node.
256 static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
258 return node->hole_size;
261 static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
263 return hole_node->start + hole_node->size;
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
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()
275 * Start of the subsequent hole.
277 static inline u64 drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
279 DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node));
280 return __drm_mm_hole_node_start(hole_node);
283 static inline u64 __drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
285 return list_next_entry(hole_node, node_list)->start;
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
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().
297 * End of the subsequent hole.
299 static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
301 return __drm_mm_hole_node_end(hole_node);
305 * drm_mm_nodes - list of nodes under the drm_mm range manager
306 * @mm: the struct drm_mm range manger
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.
314 * The node list, may be empty.
316 #define drm_mm_nodes(mm) (&(mm)->head_node.node_list)
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
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.
326 #define drm_mm_for_each_node(entry, mm) \
327 list_for_each_entry(entry, drm_mm_nodes(mm), node_list)
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
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.
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)
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
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.
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.
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, \
364 pos = list_next_entry(pos, hole_stack))
367 * Basic range manager support (drm_mm.c)
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,
377 enum drm_mm_insert_mode mode);
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
388 * This is a simplified version of drm_mm_insert_node_in_range_generic() with no
389 * range restrictions applied.
391 * The preallocated node must be cleared to 0.
394 * 0 on success, -ENOSPC if there's no suitable hole.
397 drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
398 u64 size, u64 alignment,
400 enum drm_mm_insert_mode mode)
402 return drm_mm_insert_node_in_range(mm, node,
403 size, alignment, color,
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
413 * This is a simplified version of drm_mm_insert_node_generic() with @color set
416 * The preallocated node must be cleared to 0.
419 * 0 on success, -ENOSPC if there's no suitable hole.
421 static inline int drm_mm_insert_node(struct drm_mm *mm,
422 struct drm_mm_node *node,
425 return drm_mm_insert_node_generic(mm, node, size, 0, 0, 0);
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);
434 * drm_mm_clean - checks whether an allocator is clean
435 * @mm: drm_mm allocator to check
438 * True if the allocator is completely free, false if there's still a node
441 static inline bool drm_mm_clean(const struct drm_mm *mm)
443 return list_empty(drm_mm_nodes(mm));
447 __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);
450 * drm_mm_for_each_node_in_range - iterator to walk over a range of
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)
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.
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))
468 void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
470 u64 size, u64 alignment, unsigned long color,
472 enum drm_mm_insert_mode mode);
475 * drm_mm_scan_init - initialize lru scanning
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
483 * This is a simplified version of drm_mm_scan_init_with_range() with no range
484 * restrictions applied.
486 * This simply sets up the scanning routines with the parameters for the desired
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.
493 static inline void drm_mm_scan_init(struct drm_mm_scan *scan,
498 enum drm_mm_insert_mode mode)
500 drm_mm_scan_init_with_range(scan, mm,
501 size, alignment, color,
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);
511 void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p);