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