1249d6048SJerome Glisse /**************************************************************************
2249d6048SJerome Glisse *
3249d6048SJerome Glisse * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX. USA.
4ba004e39SChris Wilson * Copyright 2016 Intel Corporation
5249d6048SJerome Glisse * All Rights Reserved.
6249d6048SJerome Glisse *
7249d6048SJerome Glisse * Permission is hereby granted, free of charge, to any person obtaining a
8249d6048SJerome Glisse * copy of this software and associated documentation files (the
9249d6048SJerome Glisse * "Software"), to deal in the Software without restriction, including
10249d6048SJerome Glisse * without limitation the rights to use, copy, modify, merge, publish,
11249d6048SJerome Glisse * distribute, sub license, and/or sell copies of the Software, and to
12249d6048SJerome Glisse * permit persons to whom the Software is furnished to do so, subject to
13249d6048SJerome Glisse * the following conditions:
14249d6048SJerome Glisse *
15249d6048SJerome Glisse * The above copyright notice and this permission notice (including the
16249d6048SJerome Glisse * next paragraph) shall be included in all copies or substantial portions
17249d6048SJerome Glisse * of the Software.
18249d6048SJerome Glisse *
19249d6048SJerome Glisse * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20249d6048SJerome Glisse * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21249d6048SJerome Glisse * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
22249d6048SJerome Glisse * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
23249d6048SJerome Glisse * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
24249d6048SJerome Glisse * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
25249d6048SJerome Glisse * USE OR OTHER DEALINGS IN THE SOFTWARE.
26249d6048SJerome Glisse *
27249d6048SJerome Glisse *
28249d6048SJerome Glisse **************************************************************************/
29249d6048SJerome Glisse /*
30249d6048SJerome Glisse * Authors:
31249d6048SJerome Glisse * Thomas Hellstrom <thomas-at-tungstengraphics-dot-com>
32249d6048SJerome Glisse */
33249d6048SJerome Glisse
34249d6048SJerome Glisse #ifndef _DRM_MM_H_
35249d6048SJerome Glisse #define _DRM_MM_H_
36249d6048SJerome Glisse
37249d6048SJerome Glisse /*
38249d6048SJerome Glisse * Generic range manager structs
39249d6048SJerome Glisse */
4086e81f0eSDavid Herrmann #include <linux/bug.h>
41202b52b7SChris Wilson #include <linux/rbtree.h>
42*ae710a45SAndy Shevchenko #include <linux/limits.h>
43589ee628SIngo Molnar #include <linux/mm_types.h>
44249d6048SJerome Glisse #include <linux/list.h>
4586e81f0eSDavid Herrmann #include <linux/spinlock.h>
465705670dSChris Wilson #ifdef CONFIG_DRM_DEBUG_MM
475705670dSChris Wilson #include <linux/stackdepot.h>
485705670dSChris Wilson #endif
49*ae710a45SAndy Shevchenko #include <linux/types.h>
50*ae710a45SAndy Shevchenko
51b5c3714fSDaniel Vetter #include <drm/drm_print.h>
52249d6048SJerome Glisse
53b3ee963fSChris Wilson #ifdef CONFIG_DRM_DEBUG_MM
54b3ee963fSChris Wilson #define DRM_MM_BUG_ON(expr) BUG_ON(expr)
55b3ee963fSChris Wilson #else
56b3ee963fSChris Wilson #define DRM_MM_BUG_ON(expr) BUILD_BUG_ON_INVALID(expr)
57b3ee963fSChris Wilson #endif
58b3ee963fSChris Wilson
594e64e553SChris Wilson /**
604e64e553SChris Wilson * enum drm_mm_insert_mode - control search and allocation behaviour
614e64e553SChris Wilson *
624e64e553SChris Wilson * The &struct drm_mm range manager supports finding a suitable modes using
634e64e553SChris Wilson * a number of search trees. These trees are oranised by size, by address and
644e64e553SChris Wilson * in most recent eviction order. This allows the user to find either the
654e64e553SChris Wilson * smallest hole to reuse, the lowest or highest address to reuse, or simply
664e64e553SChris Wilson * reuse the most recent eviction that fits. When allocating the &drm_mm_node
674e64e553SChris Wilson * from within the hole, the &drm_mm_insert_mode also dictate whether to
684e64e553SChris Wilson * allocate the lowest matching address or the highest.
694e64e553SChris Wilson */
704e64e553SChris Wilson enum drm_mm_insert_mode {
714e64e553SChris Wilson /**
724e64e553SChris Wilson * @DRM_MM_INSERT_BEST:
734e64e553SChris Wilson *
744e64e553SChris Wilson * Search for the smallest hole (within the search range) that fits
754e64e553SChris Wilson * the desired node.
764e64e553SChris Wilson *
774e64e553SChris Wilson * Allocates the node from the bottom of the found hole.
784e64e553SChris Wilson */
794e64e553SChris Wilson DRM_MM_INSERT_BEST = 0,
8031e5d7c6SDavid Herrmann
814e64e553SChris Wilson /**
824e64e553SChris Wilson * @DRM_MM_INSERT_LOW:
834e64e553SChris Wilson *
844e64e553SChris Wilson * Search for the lowest hole (address closest to 0, within the search
854e64e553SChris Wilson * range) that fits the desired node.
864e64e553SChris Wilson *
874e64e553SChris Wilson * Allocates the node from the bottom of the found hole.
884e64e553SChris Wilson */
894e64e553SChris Wilson DRM_MM_INSERT_LOW,
9062347f9eSLauri Kasanen
914e64e553SChris Wilson /**
924e64e553SChris Wilson * @DRM_MM_INSERT_HIGH:
934e64e553SChris Wilson *
944e64e553SChris Wilson * Search for the highest hole (address closest to U64_MAX, within the
954e64e553SChris Wilson * search range) that fits the desired node.
964e64e553SChris Wilson *
974e64e553SChris Wilson * Allocates the node from the *top* of the found hole. The specified
984e64e553SChris Wilson * alignment for the node is applied to the base of the node
994e64e553SChris Wilson * (&drm_mm_node.start).
1004e64e553SChris Wilson */
1014e64e553SChris Wilson DRM_MM_INSERT_HIGH,
1024e64e553SChris Wilson
1034e64e553SChris Wilson /**
1044e64e553SChris Wilson * @DRM_MM_INSERT_EVICT:
1054e64e553SChris Wilson *
1064e64e553SChris Wilson * Search for the most recently evicted hole (within the search range)
1074e64e553SChris Wilson * that fits the desired node. This is appropriate for use immediately
1084e64e553SChris Wilson * after performing an eviction scan (see drm_mm_scan_init()) and
1094e64e553SChris Wilson * removing the selected nodes to form a hole.
1104e64e553SChris Wilson *
1114e64e553SChris Wilson * Allocates the node from the bottom of the found hole.
1124e64e553SChris Wilson */
1134e64e553SChris Wilson DRM_MM_INSERT_EVICT,
11483bc4ec3SChris Wilson
11583bc4ec3SChris Wilson /**
11683bc4ec3SChris Wilson * @DRM_MM_INSERT_ONCE:
11783bc4ec3SChris Wilson *
11883bc4ec3SChris Wilson * Only check the first hole for suitablity and report -ENOSPC
11983bc4ec3SChris Wilson * immediately otherwise, rather than check every hole until a
12083bc4ec3SChris Wilson * suitable one is found. Can only be used in conjunction with another
12183bc4ec3SChris Wilson * search method such as DRM_MM_INSERT_HIGH or DRM_MM_INSERT_LOW.
12283bc4ec3SChris Wilson */
12383bc4ec3SChris Wilson DRM_MM_INSERT_ONCE = BIT(31),
12483bc4ec3SChris Wilson
12583bc4ec3SChris Wilson /**
12683bc4ec3SChris Wilson * @DRM_MM_INSERT_HIGHEST:
12783bc4ec3SChris Wilson *
12883bc4ec3SChris Wilson * Only check the highest hole (the hole with the largest address) and
12983bc4ec3SChris Wilson * insert the node at the top of the hole or report -ENOSPC if
13083bc4ec3SChris Wilson * unsuitable.
13183bc4ec3SChris Wilson *
13283bc4ec3SChris Wilson * Does not search all holes.
13383bc4ec3SChris Wilson */
13483bc4ec3SChris Wilson DRM_MM_INSERT_HIGHEST = DRM_MM_INSERT_HIGH | DRM_MM_INSERT_ONCE,
13583bc4ec3SChris Wilson
13683bc4ec3SChris Wilson /**
13783bc4ec3SChris Wilson * @DRM_MM_INSERT_LOWEST:
13883bc4ec3SChris Wilson *
13983bc4ec3SChris Wilson * Only check the lowest hole (the hole with the smallest address) and
14083bc4ec3SChris Wilson * insert the node at the bottom of the hole or report -ENOSPC if
14183bc4ec3SChris Wilson * unsuitable.
14283bc4ec3SChris Wilson *
14383bc4ec3SChris Wilson * Does not search all holes.
14483bc4ec3SChris Wilson */
14583bc4ec3SChris Wilson DRM_MM_INSERT_LOWEST = DRM_MM_INSERT_LOW | DRM_MM_INSERT_ONCE,
1464e64e553SChris Wilson };
14762347f9eSLauri Kasanen
14805fc0321SDaniel Vetter /**
14905fc0321SDaniel Vetter * struct drm_mm_node - allocated block in the DRM allocator
15005fc0321SDaniel Vetter *
15105fc0321SDaniel Vetter * This represents an allocated block in a &drm_mm allocator. Except for
15205fc0321SDaniel Vetter * pre-reserved nodes inserted using drm_mm_reserve_node() the structure is
15305fc0321SDaniel Vetter * entirely opaque and should only be accessed through the provided funcions.
15405fc0321SDaniel Vetter * Since allocation of these nodes is entirely handled by the driver they can be
15505fc0321SDaniel Vetter * embedded.
15605fc0321SDaniel Vetter */
157249d6048SJerome Glisse struct drm_mm_node {
15805fc0321SDaniel Vetter /** @color: Opaque driver-private tag. */
15905fc0321SDaniel Vetter unsigned long color;
16005fc0321SDaniel Vetter /** @start: Start address of the allocated block. */
16105fc0321SDaniel Vetter u64 start;
16205fc0321SDaniel Vetter /** @size: Size of the allocated block. */
16305fc0321SDaniel Vetter u64 size;
16405fc0321SDaniel Vetter /* private: */
1654e64e553SChris Wilson struct drm_mm *mm;
166d1024ce9SDaniel Vetter struct list_head node_list;
167ea7b1dd4SDaniel Vetter struct list_head hole_stack;
168202b52b7SChris Wilson struct rb_node rb;
1694e64e553SChris Wilson struct rb_node rb_hole_size;
1704e64e553SChris Wilson struct rb_node rb_hole_addr;
171202b52b7SChris Wilson u64 __subtree_last;
1724e64e553SChris Wilson u64 hole_size;
1730cdea445SNirmoy Das u64 subtree_max_hole;
1744ee92c71SChris Wilson unsigned long flags;
1754ee92c71SChris Wilson #define DRM_MM_NODE_ALLOCATED_BIT 0
1764ee92c71SChris Wilson #define DRM_MM_NODE_SCANNED_BIT 1
1775705670dSChris Wilson #ifdef CONFIG_DRM_DEBUG_MM
1785705670dSChris Wilson depot_stack_handle_t stack;
1795705670dSChris Wilson #endif
180249d6048SJerome Glisse };
181249d6048SJerome Glisse
18205fc0321SDaniel Vetter /**
18305fc0321SDaniel Vetter * struct drm_mm - DRM allocator
18405fc0321SDaniel Vetter *
18505fc0321SDaniel Vetter * DRM range allocator with a few special functions and features geared towards
18605fc0321SDaniel Vetter * managing GPU memory. Except for the @color_adjust callback the structure is
18705fc0321SDaniel Vetter * entirely opaque and should only be accessed through the provided functions
18805fc0321SDaniel Vetter * and macros. This structure can be embedded into larger driver structures.
18905fc0321SDaniel Vetter */
190249d6048SJerome Glisse struct drm_mm {
19105fc0321SDaniel Vetter /**
19205fc0321SDaniel Vetter * @color_adjust:
19305fc0321SDaniel Vetter *
19405fc0321SDaniel Vetter * Optional driver callback to further apply restrictions on a hole. The
19505fc0321SDaniel Vetter * node argument points at the node containing the hole from which the
19605fc0321SDaniel Vetter * block would be allocated (see drm_mm_hole_follows() and friends). The
19705fc0321SDaniel Vetter * other arguments are the size of the block to be allocated. The driver
19805fc0321SDaniel Vetter * can adjust the start and end as needed to e.g. insert guard pages.
19905fc0321SDaniel Vetter */
20005fc0321SDaniel Vetter void (*color_adjust)(const struct drm_mm_node *node,
20105fc0321SDaniel Vetter unsigned long color,
20205fc0321SDaniel Vetter u64 *start, u64 *end);
20305fc0321SDaniel Vetter
20405fc0321SDaniel Vetter /* private: */
20525985edcSLucas De Marchi /* List of all memory nodes that immediately precede a free hole. */
206ea7b1dd4SDaniel Vetter struct list_head hole_stack;
207ea7b1dd4SDaniel Vetter /* head_node.node_list is the list of all memory nodes, ordered
208ea7b1dd4SDaniel Vetter * according to the (increasing) start address of the memory node. */
209ea7b1dd4SDaniel Vetter struct drm_mm_node head_node;
210202b52b7SChris Wilson /* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
211f808c13fSDavidlohr Bueso struct rb_root_cached interval_tree;
2122f7e8769SChris Wilson struct rb_root_cached holes_size;
2134e64e553SChris Wilson struct rb_root holes_addr;
214202b52b7SChris Wilson
2159a71e277SChris Wilson unsigned long scan_active;
2169a71e277SChris Wilson };
2179a71e277SChris Wilson
21805fc0321SDaniel Vetter /**
21905fc0321SDaniel Vetter * struct drm_mm_scan - DRM allocator eviction roaster data
22005fc0321SDaniel Vetter *
22105fc0321SDaniel Vetter * This structure tracks data needed for the eviction roaster set up using
22205fc0321SDaniel Vetter * drm_mm_scan_init(), and used with drm_mm_scan_add_block() and
22305fc0321SDaniel Vetter * drm_mm_scan_remove_block(). The structure is entirely opaque and should only
22405fc0321SDaniel Vetter * be accessed through the provided functions and macros. It is meant to be
22505fc0321SDaniel Vetter * allocated temporarily by the driver on the stack.
22605fc0321SDaniel Vetter */
2279a71e277SChris Wilson struct drm_mm_scan {
22805fc0321SDaniel Vetter /* private: */
2299a71e277SChris Wilson struct drm_mm *mm;
2309a71e277SChris Wilson
2319a71e277SChris Wilson u64 size;
2329a71e277SChris Wilson u64 alignment;
2339a956b15SChris Wilson u64 remainder_mask;
2349a71e277SChris Wilson
2359a71e277SChris Wilson u64 range_start;
2369a71e277SChris Wilson u64 range_end;
2379a71e277SChris Wilson
2389a71e277SChris Wilson u64 hit_start;
2399a71e277SChris Wilson u64 hit_end;
2409a71e277SChris Wilson
2419a71e277SChris Wilson unsigned long color;
2424e64e553SChris Wilson enum drm_mm_insert_mode mode;
243249d6048SJerome Glisse };
244249d6048SJerome Glisse
245e18c0412SDaniel Vetter /**
246e18c0412SDaniel Vetter * drm_mm_node_allocated - checks whether a node is allocated
247e18c0412SDaniel Vetter * @node: drm_mm_node to check
248e18c0412SDaniel Vetter *
249ba004e39SChris Wilson * Drivers are required to clear a node prior to using it with the
250ba004e39SChris Wilson * drm_mm range manager.
251ba004e39SChris Wilson *
252ba004e39SChris Wilson * Drivers should use this helper for proper encapsulation of drm_mm
253e18c0412SDaniel Vetter * internals.
254e18c0412SDaniel Vetter *
255e18c0412SDaniel Vetter * Returns:
256e18c0412SDaniel Vetter * True if the @node is allocated.
257e18c0412SDaniel Vetter */
drm_mm_node_allocated(const struct drm_mm_node * node)25845b186f1SChris Wilson static inline bool drm_mm_node_allocated(const struct drm_mm_node *node)
259b0b7af18SDaniel Vetter {
2604ee92c71SChris Wilson return test_bit(DRM_MM_NODE_ALLOCATED_BIT, &node->flags);
261b0b7af18SDaniel Vetter }
262b0b7af18SDaniel Vetter
263e18c0412SDaniel Vetter /**
264e18c0412SDaniel Vetter * drm_mm_initialized - checks whether an allocator is initialized
265e18c0412SDaniel Vetter * @mm: drm_mm to check
266e18c0412SDaniel Vetter *
267ba004e39SChris Wilson * Drivers should clear the struct drm_mm prior to initialisation if they
268ba004e39SChris Wilson * want to use this function.
269ba004e39SChris Wilson *
270ba004e39SChris Wilson * Drivers should use this helper for proper encapsulation of drm_mm
271e18c0412SDaniel Vetter * internals.
272e18c0412SDaniel Vetter *
273e18c0412SDaniel Vetter * Returns:
274e18c0412SDaniel Vetter * True if the @mm is initialized.
275e18c0412SDaniel Vetter */
drm_mm_initialized(const struct drm_mm * mm)27645b186f1SChris Wilson static inline bool drm_mm_initialized(const struct drm_mm *mm)
27731a5b8ceSDaniel Vetter {
2782214ddc2SChris Wilson return READ_ONCE(mm->hole_stack.next);
27931a5b8ceSDaniel Vetter }
2809e8944abSChris Wilson
2813f85fb34SChris Wilson /**
2823f85fb34SChris Wilson * drm_mm_hole_follows - checks whether a hole follows this node
2833f85fb34SChris Wilson * @node: drm_mm_node to check
2843f85fb34SChris Wilson *
2853f85fb34SChris Wilson * Holes are embedded into the drm_mm using the tail of a drm_mm_node.
2863f85fb34SChris Wilson * If you wish to know whether a hole follows this particular node,
28705fc0321SDaniel Vetter * query this function. See also drm_mm_hole_node_start() and
28805fc0321SDaniel Vetter * drm_mm_hole_node_end().
2893f85fb34SChris Wilson *
2903f85fb34SChris Wilson * Returns:
2913f85fb34SChris Wilson * True if a hole follows the @node.
2923f85fb34SChris Wilson */
drm_mm_hole_follows(const struct drm_mm_node * node)2933f85fb34SChris Wilson static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
2943f85fb34SChris Wilson {
2954e64e553SChris Wilson return node->hole_size;
2963f85fb34SChris Wilson }
2973f85fb34SChris Wilson
__drm_mm_hole_node_start(const struct drm_mm_node * hole_node)29845b186f1SChris Wilson static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
2999e8944abSChris Wilson {
3009e8944abSChris Wilson return hole_node->start + hole_node->size;
3019e8944abSChris Wilson }
3029e8944abSChris Wilson
303e18c0412SDaniel Vetter /**
304e18c0412SDaniel Vetter * drm_mm_hole_node_start - computes the start of the hole following @node
305e18c0412SDaniel Vetter * @hole_node: drm_mm_node which implicitly tracks the following hole
306e18c0412SDaniel Vetter *
307ba004e39SChris Wilson * This is useful for driver-specific debug dumpers. Otherwise drivers should
308ba004e39SChris Wilson * not inspect holes themselves. Drivers must check first whether a hole indeed
3093f85fb34SChris Wilson * follows by looking at drm_mm_hole_follows()
310e18c0412SDaniel Vetter *
311e18c0412SDaniel Vetter * Returns:
312e18c0412SDaniel Vetter * Start of the subsequent hole.
313e18c0412SDaniel Vetter */
drm_mm_hole_node_start(const struct drm_mm_node * hole_node)31445b186f1SChris Wilson static inline u64 drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
3159e8944abSChris Wilson {
3163f85fb34SChris Wilson DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node));
3179e8944abSChris Wilson return __drm_mm_hole_node_start(hole_node);
3189e8944abSChris Wilson }
3199e8944abSChris Wilson
__drm_mm_hole_node_end(const struct drm_mm_node * hole_node)32045b186f1SChris Wilson static inline u64 __drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
3219e8944abSChris Wilson {
32287069f44SGeliang Tang return list_next_entry(hole_node, node_list)->start;
3239e8944abSChris Wilson }
3249e8944abSChris Wilson
325e18c0412SDaniel Vetter /**
326e18c0412SDaniel Vetter * drm_mm_hole_node_end - computes the end of the hole following @node
327e18c0412SDaniel Vetter * @hole_node: drm_mm_node which implicitly tracks the following hole
328e18c0412SDaniel Vetter *
329ba004e39SChris Wilson * This is useful for driver-specific debug dumpers. Otherwise drivers should
330ba004e39SChris Wilson * not inspect holes themselves. Drivers must check first whether a hole indeed
3313f85fb34SChris Wilson * follows by looking at drm_mm_hole_follows().
332e18c0412SDaniel Vetter *
333e18c0412SDaniel Vetter * Returns:
334e18c0412SDaniel Vetter * End of the subsequent hole.
335e18c0412SDaniel Vetter */
drm_mm_hole_node_end(const struct drm_mm_node * hole_node)33645b186f1SChris Wilson static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
3379e8944abSChris Wilson {
3389e8944abSChris Wilson return __drm_mm_hole_node_end(hole_node);
3399e8944abSChris Wilson }
3409e8944abSChris Wilson
3412bc98c86SChris Wilson /**
3422bc98c86SChris Wilson * drm_mm_nodes - list of nodes under the drm_mm range manager
343e5e1065fSWang Qing * @mm: the struct drm_mm range manager
3442bc98c86SChris Wilson *
3452bc98c86SChris Wilson * As the drm_mm range manager hides its node_list deep with its
3462bc98c86SChris Wilson * structure, extracting it looks painful and repetitive. This is
3472bc98c86SChris Wilson * not expected to be used outside of the drm_mm_for_each_node()
3482bc98c86SChris Wilson * macros and similar internal functions.
3492bc98c86SChris Wilson *
3502bc98c86SChris Wilson * Returns:
3512bc98c86SChris Wilson * The node list, may be empty.
3522bc98c86SChris Wilson */
3532bc98c86SChris Wilson #define drm_mm_nodes(mm) (&(mm)->head_node.node_list)
354ad579002SChris Wilson
355e18c0412SDaniel Vetter /**
356e18c0412SDaniel Vetter * drm_mm_for_each_node - iterator to walk over all allocated nodes
35705fc0321SDaniel Vetter * @entry: &struct drm_mm_node to assign to in each iteration step
35805fc0321SDaniel Vetter * @mm: &drm_mm allocator to walk
359e18c0412SDaniel Vetter *
360e18c0412SDaniel Vetter * This iterator walks over all nodes in the range allocator. It is implemented
36105fc0321SDaniel Vetter * with list_for_each(), so not save against removal of elements.
362e18c0412SDaniel Vetter */
363ad579002SChris Wilson #define drm_mm_for_each_node(entry, mm) \
3642bc98c86SChris Wilson list_for_each_entry(entry, drm_mm_nodes(mm), node_list)
365ad579002SChris Wilson
366ad579002SChris Wilson /**
367ad579002SChris Wilson * drm_mm_for_each_node_safe - iterator to walk over all allocated nodes
36805fc0321SDaniel Vetter * @entry: &struct drm_mm_node to assign to in each iteration step
36905fc0321SDaniel Vetter * @next: &struct drm_mm_node to store the next step
37005fc0321SDaniel Vetter * @mm: &drm_mm allocator to walk
371ad579002SChris Wilson *
372ad579002SChris Wilson * This iterator walks over all nodes in the range allocator. It is implemented
37305fc0321SDaniel Vetter * with list_for_each_safe(), so save against removal of elements.
374ad579002SChris Wilson */
375ad579002SChris Wilson #define drm_mm_for_each_node_safe(entry, next, mm) \
3762bc98c86SChris Wilson list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)
3779e8944abSChris Wilson
378e18c0412SDaniel Vetter /**
379e18c0412SDaniel Vetter * drm_mm_for_each_hole - iterator to walk over all holes
3804e64e553SChris Wilson * @pos: &drm_mm_node used internally to track progress
38105fc0321SDaniel Vetter * @mm: &drm_mm allocator to walk
382e18c0412SDaniel Vetter * @hole_start: ulong variable to assign the hole start to on each iteration
383e18c0412SDaniel Vetter * @hole_end: ulong variable to assign the hole end to on each iteration
384e18c0412SDaniel Vetter *
385e18c0412SDaniel Vetter * This iterator walks over all holes in the range allocator. It is implemented
38605fc0321SDaniel Vetter * with list_for_each(), so not save against removal of elements. @entry is used
387e18c0412SDaniel Vetter * internally and will not reflect a real drm_mm_node for the very first hole.
388e18c0412SDaniel Vetter * Hence users of this iterator may not access it.
389e18c0412SDaniel Vetter *
390e18c0412SDaniel Vetter * Implementation Note:
391e18c0412SDaniel Vetter * We need to inline list_for_each_entry in order to be able to set hole_start
392e18c0412SDaniel Vetter * and hole_end on each iteration while keeping the macro sane.
3939e8944abSChris Wilson */
3944e64e553SChris Wilson #define drm_mm_for_each_hole(pos, mm, hole_start, hole_end) \
3954e64e553SChris Wilson for (pos = list_first_entry(&(mm)->hole_stack, \
3964e64e553SChris Wilson typeof(*pos), hole_stack); \
3974e64e553SChris Wilson &pos->hole_stack != &(mm)->hole_stack ? \
3984e64e553SChris Wilson hole_start = drm_mm_hole_node_start(pos), \
3994e64e553SChris Wilson hole_end = hole_start + pos->hole_size, \
4004e64e553SChris Wilson 1 : 0; \
4014e64e553SChris Wilson pos = list_next_entry(pos, hole_stack))
40262347f9eSLauri Kasanen
403249d6048SJerome Glisse /*
404249d6048SJerome Glisse * Basic range manager support (drm_mm.c)
405249d6048SJerome Glisse */
406e18c0412SDaniel Vetter int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node);
4074e64e553SChris Wilson int drm_mm_insert_node_in_range(struct drm_mm *mm,
408b8103450SChris Wilson struct drm_mm_node *node,
409440fd528SThierry Reding u64 size,
41071733207SChris Wilson u64 alignment,
411b8103450SChris Wilson unsigned long color,
412440fd528SThierry Reding u64 start,
413440fd528SThierry Reding u64 end,
4144e64e553SChris Wilson enum drm_mm_insert_mode mode);
41531e5d7c6SDavid Herrmann
416adb040b8SChris Wilson /**
417adb040b8SChris Wilson * drm_mm_insert_node_generic - search for space and insert @node
418adb040b8SChris Wilson * @mm: drm_mm to allocate from
419adb040b8SChris Wilson * @node: preallocate node to insert
420adb040b8SChris Wilson * @size: size of the allocation
421adb040b8SChris Wilson * @alignment: alignment of the allocation
422adb040b8SChris Wilson * @color: opaque tag value to use for this node
4234e64e553SChris Wilson * @mode: fine-tune the allocation search and placement
424adb040b8SChris Wilson *
4250a2adb02SLiviu Dudau * This is a simplified version of drm_mm_insert_node_in_range() with no
42605fc0321SDaniel Vetter * range restrictions applied.
42705fc0321SDaniel Vetter *
428adb040b8SChris Wilson * The preallocated node must be cleared to 0.
429adb040b8SChris Wilson *
430adb040b8SChris Wilson * Returns:
431adb040b8SChris Wilson * 0 on success, -ENOSPC if there's no suitable hole.
432adb040b8SChris Wilson */
433adb040b8SChris Wilson static inline int
drm_mm_insert_node_generic(struct drm_mm * mm,struct drm_mm_node * node,u64 size,u64 alignment,unsigned long color,enum drm_mm_insert_mode mode)434adb040b8SChris Wilson drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
435adb040b8SChris Wilson u64 size, u64 alignment,
436adb040b8SChris Wilson unsigned long color,
4374e64e553SChris Wilson enum drm_mm_insert_mode mode)
438adb040b8SChris Wilson {
4394e64e553SChris Wilson return drm_mm_insert_node_in_range(mm, node,
4404e64e553SChris Wilson size, alignment, color,
4414e64e553SChris Wilson 0, U64_MAX, mode);
442adb040b8SChris Wilson }
443adb040b8SChris Wilson
444adb040b8SChris Wilson /**
445adb040b8SChris Wilson * drm_mm_insert_node - search for space and insert @node
446adb040b8SChris Wilson * @mm: drm_mm to allocate from
447adb040b8SChris Wilson * @node: preallocate node to insert
448adb040b8SChris Wilson * @size: size of the allocation
449adb040b8SChris Wilson *
450adb040b8SChris Wilson * This is a simplified version of drm_mm_insert_node_generic() with @color set
451adb040b8SChris Wilson * to 0.
452adb040b8SChris Wilson *
453adb040b8SChris Wilson * The preallocated node must be cleared to 0.
454adb040b8SChris Wilson *
455adb040b8SChris Wilson * Returns:
456adb040b8SChris Wilson * 0 on success, -ENOSPC if there's no suitable hole.
457adb040b8SChris Wilson */
drm_mm_insert_node(struct drm_mm * mm,struct drm_mm_node * node,u64 size)458adb040b8SChris Wilson static inline int drm_mm_insert_node(struct drm_mm *mm,
459adb040b8SChris Wilson struct drm_mm_node *node,
4604e64e553SChris Wilson u64 size)
461adb040b8SChris Wilson {
4624e64e553SChris Wilson return drm_mm_insert_node_generic(mm, node, size, 0, 0, 0);
463adb040b8SChris Wilson }
464adb040b8SChris Wilson
465e18c0412SDaniel Vetter void drm_mm_remove_node(struct drm_mm_node *node);
466e18c0412SDaniel Vetter void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new);
46745b186f1SChris Wilson void drm_mm_init(struct drm_mm *mm, u64 start, u64 size);
468e18c0412SDaniel Vetter void drm_mm_takedown(struct drm_mm *mm);
469ac9bb7b7SChris Wilson
470ac9bb7b7SChris Wilson /**
471ac9bb7b7SChris Wilson * drm_mm_clean - checks whether an allocator is clean
472ac9bb7b7SChris Wilson * @mm: drm_mm allocator to check
473ac9bb7b7SChris Wilson *
474ac9bb7b7SChris Wilson * Returns:
475ac9bb7b7SChris Wilson * True if the allocator is completely free, false if there's still a node
476ac9bb7b7SChris Wilson * allocated in it.
477ac9bb7b7SChris Wilson */
drm_mm_clean(const struct drm_mm * mm)478ac9bb7b7SChris Wilson static inline bool drm_mm_clean(const struct drm_mm *mm)
479ac9bb7b7SChris Wilson {
480ac9bb7b7SChris Wilson return list_empty(drm_mm_nodes(mm));
481ac9bb7b7SChris Wilson }
482249d6048SJerome Glisse
483202b52b7SChris Wilson struct drm_mm_node *
48445b186f1SChris Wilson __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);
485202b52b7SChris Wilson
486522e85ddSChris Wilson /**
487522e85ddSChris Wilson * drm_mm_for_each_node_in_range - iterator to walk over a range of
488522e85ddSChris Wilson * allocated nodes
4898b2fb7b6SChris Wilson * @node__: drm_mm_node structure to assign to in each iteration step
4908b2fb7b6SChris Wilson * @mm__: drm_mm allocator to walk
4918b2fb7b6SChris Wilson * @start__: starting offset, the first node will overlap this
4928b2fb7b6SChris Wilson * @end__: ending offset, the last node will start before this (but may overlap)
493522e85ddSChris Wilson *
494522e85ddSChris Wilson * This iterator walks over all nodes in the range allocator that lie
495522e85ddSChris Wilson * between @start and @end. It is implemented similarly to list_for_each(),
496522e85ddSChris Wilson * but using the internal interval tree to accelerate the search for the
497522e85ddSChris Wilson * starting node, and so not safe against removal of elements. It assumes
498522e85ddSChris Wilson * that @end is within (or is the upper limit of) the drm_mm allocator.
499bbba9693SChris Wilson * If [@start, @end] are beyond the range of the drm_mm, the iterator may walk
500bbba9693SChris Wilson * over the special _unallocated_ &drm_mm.head_node, and may even continue
501bbba9693SChris Wilson * indefinitely.
502522e85ddSChris Wilson */
5038b2fb7b6SChris Wilson #define drm_mm_for_each_node_in_range(node__, mm__, start__, end__) \
5048b2fb7b6SChris Wilson for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)-1); \
505bbba9693SChris Wilson node__->start < (end__); \
5068b2fb7b6SChris Wilson node__ = list_next_entry(node__, node_list))
507202b52b7SChris Wilson
5089a71e277SChris Wilson void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
5099a71e277SChris Wilson struct drm_mm *mm,
5100b04d474SChris Wilson u64 size, u64 alignment, unsigned long color,
5110b04d474SChris Wilson u64 start, u64 end,
5124e64e553SChris Wilson enum drm_mm_insert_mode mode);
5132c4b3895SChris Wilson
5142c4b3895SChris Wilson /**
5152c4b3895SChris Wilson * drm_mm_scan_init - initialize lru scanning
5162c4b3895SChris Wilson * @scan: scan state
5172c4b3895SChris Wilson * @mm: drm_mm to scan
5182c4b3895SChris Wilson * @size: size of the allocation
5192c4b3895SChris Wilson * @alignment: alignment of the allocation
5202c4b3895SChris Wilson * @color: opaque tag value to use for the allocation
5214e64e553SChris Wilson * @mode: fine-tune the allocation search and placement
5222c4b3895SChris Wilson *
52305fc0321SDaniel Vetter * This is a simplified version of drm_mm_scan_init_with_range() with no range
52405fc0321SDaniel Vetter * restrictions applied.
52505fc0321SDaniel Vetter *
5262c4b3895SChris Wilson * This simply sets up the scanning routines with the parameters for the desired
5270b04d474SChris Wilson * hole.
5282c4b3895SChris Wilson *
5292c4b3895SChris Wilson * Warning:
5302c4b3895SChris Wilson * As long as the scan list is non-empty, no other operations than
5312c4b3895SChris Wilson * adding/removing nodes to/from the scan list are allowed.
5322c4b3895SChris Wilson */
drm_mm_scan_init(struct drm_mm_scan * scan,struct drm_mm * mm,u64 size,u64 alignment,unsigned long color,enum drm_mm_insert_mode mode)5332c4b3895SChris Wilson static inline void drm_mm_scan_init(struct drm_mm_scan *scan,
5342c4b3895SChris Wilson struct drm_mm *mm,
5352c4b3895SChris Wilson u64 size,
5362c4b3895SChris Wilson u64 alignment,
5370b04d474SChris Wilson unsigned long color,
5384e64e553SChris Wilson enum drm_mm_insert_mode mode)
5392c4b3895SChris Wilson {
5400b04d474SChris Wilson drm_mm_scan_init_with_range(scan, mm,
5410b04d474SChris Wilson size, alignment, color,
5424e64e553SChris Wilson 0, U64_MAX, mode);
5432c4b3895SChris Wilson }
5442c4b3895SChris Wilson
5459a71e277SChris Wilson bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
5469a71e277SChris Wilson struct drm_mm_node *node);
5479a71e277SChris Wilson bool drm_mm_scan_remove_block(struct drm_mm_scan *scan,
5489a71e277SChris Wilson struct drm_mm_node *node);
5493fa489daSChris Wilson struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan);
550709ea971SDaniel Vetter
551b5c3714fSDaniel Vetter void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p);
552fa8a1238SDave Airlie
553249d6048SJerome Glisse #endif
554