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 	bool allocated : 1;
172 	bool scanned_block : 1;
173 #ifdef CONFIG_DRM_DEBUG_MM
174 	depot_stack_handle_t stack;
175 #endif
176 };
177 
178 /**
179  * struct drm_mm - DRM allocator
180  *
181  * DRM range allocator with a few special functions and features geared towards
182  * managing GPU memory. Except for the @color_adjust callback the structure is
183  * entirely opaque and should only be accessed through the provided functions
184  * and macros. This structure can be embedded into larger driver structures.
185  */
186 struct drm_mm {
187 	/**
188 	 * @color_adjust:
189 	 *
190 	 * Optional driver callback to further apply restrictions on a hole. The
191 	 * node argument points at the node containing the hole from which the
192 	 * block would be allocated (see drm_mm_hole_follows() and friends). The
193 	 * other arguments are the size of the block to be allocated. The driver
194 	 * can adjust the start and end as needed to e.g. insert guard pages.
195 	 */
196 	void (*color_adjust)(const struct drm_mm_node *node,
197 			     unsigned long color,
198 			     u64 *start, u64 *end);
199 
200 	/* private: */
201 	/* List of all memory nodes that immediately precede a free hole. */
202 	struct list_head hole_stack;
203 	/* head_node.node_list is the list of all memory nodes, ordered
204 	 * according to the (increasing) start address of the memory node. */
205 	struct drm_mm_node head_node;
206 	/* Keep an interval_tree for fast lookup of drm_mm_nodes by address. */
207 	struct rb_root_cached interval_tree;
208 	struct rb_root_cached holes_size;
209 	struct rb_root holes_addr;
210 
211 	unsigned long scan_active;
212 };
213 
214 /**
215  * struct drm_mm_scan - DRM allocator eviction roaster data
216  *
217  * This structure tracks data needed for the eviction roaster set up using
218  * drm_mm_scan_init(), and used with drm_mm_scan_add_block() and
219  * drm_mm_scan_remove_block(). The structure is entirely opaque and should only
220  * be accessed through the provided functions and macros. It is meant to be
221  * allocated temporarily by the driver on the stack.
222  */
223 struct drm_mm_scan {
224 	/* private: */
225 	struct drm_mm *mm;
226 
227 	u64 size;
228 	u64 alignment;
229 	u64 remainder_mask;
230 
231 	u64 range_start;
232 	u64 range_end;
233 
234 	u64 hit_start;
235 	u64 hit_end;
236 
237 	unsigned long color;
238 	enum drm_mm_insert_mode mode;
239 };
240 
241 /**
242  * drm_mm_node_allocated - checks whether a node is allocated
243  * @node: drm_mm_node to check
244  *
245  * Drivers are required to clear a node prior to using it with the
246  * drm_mm range manager.
247  *
248  * Drivers should use this helper for proper encapsulation of drm_mm
249  * internals.
250  *
251  * Returns:
252  * True if the @node is allocated.
253  */
drm_mm_node_allocated(const struct drm_mm_node * node)254 static inline bool drm_mm_node_allocated(const struct drm_mm_node *node)
255 {
256 	return node->allocated;
257 }
258 
259 /**
260  * drm_mm_initialized - checks whether an allocator is initialized
261  * @mm: drm_mm to check
262  *
263  * Drivers should clear the struct drm_mm prior to initialisation if they
264  * want to use this function.
265  *
266  * Drivers should use this helper for proper encapsulation of drm_mm
267  * internals.
268  *
269  * Returns:
270  * True if the @mm is initialized.
271  */
drm_mm_initialized(const struct drm_mm * mm)272 static inline bool drm_mm_initialized(const struct drm_mm *mm)
273 {
274 	return mm->hole_stack.next;
275 }
276 
277 /**
278  * drm_mm_hole_follows - checks whether a hole follows this node
279  * @node: drm_mm_node to check
280  *
281  * Holes are embedded into the drm_mm using the tail of a drm_mm_node.
282  * If you wish to know whether a hole follows this particular node,
283  * query this function. See also drm_mm_hole_node_start() and
284  * drm_mm_hole_node_end().
285  *
286  * Returns:
287  * True if a hole follows the @node.
288  */
drm_mm_hole_follows(const struct drm_mm_node * node)289 static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
290 {
291 	return node->hole_size;
292 }
293 
__drm_mm_hole_node_start(const struct drm_mm_node * hole_node)294 static inline u64 __drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
295 {
296 	return hole_node->start + hole_node->size;
297 }
298 
299 /**
300  * drm_mm_hole_node_start - computes the start of the hole following @node
301  * @hole_node: drm_mm_node which implicitly tracks the following hole
302  *
303  * This is useful for driver-specific debug dumpers. Otherwise drivers should
304  * not inspect holes themselves. Drivers must check first whether a hole indeed
305  * follows by looking at drm_mm_hole_follows()
306  *
307  * Returns:
308  * Start of the subsequent hole.
309  */
drm_mm_hole_node_start(const struct drm_mm_node * hole_node)310 static inline u64 drm_mm_hole_node_start(const struct drm_mm_node *hole_node)
311 {
312 	DRM_MM_BUG_ON(!drm_mm_hole_follows(hole_node));
313 	return __drm_mm_hole_node_start(hole_node);
314 }
315 
__drm_mm_hole_node_end(const struct drm_mm_node * hole_node)316 static inline u64 __drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
317 {
318 	return list_next_entry(hole_node, node_list)->start;
319 }
320 
321 /**
322  * drm_mm_hole_node_end - computes the end of the hole following @node
323  * @hole_node: drm_mm_node which implicitly tracks the following hole
324  *
325  * This is useful for driver-specific debug dumpers. Otherwise drivers should
326  * not inspect holes themselves. Drivers must check first whether a hole indeed
327  * follows by looking at drm_mm_hole_follows().
328  *
329  * Returns:
330  * End of the subsequent hole.
331  */
drm_mm_hole_node_end(const struct drm_mm_node * hole_node)332 static inline u64 drm_mm_hole_node_end(const struct drm_mm_node *hole_node)
333 {
334 	return __drm_mm_hole_node_end(hole_node);
335 }
336 
337 /**
338  * drm_mm_nodes - list of nodes under the drm_mm range manager
339  * @mm: the struct drm_mm range manger
340  *
341  * As the drm_mm range manager hides its node_list deep with its
342  * structure, extracting it looks painful and repetitive. This is
343  * not expected to be used outside of the drm_mm_for_each_node()
344  * macros and similar internal functions.
345  *
346  * Returns:
347  * The node list, may be empty.
348  */
349 #define drm_mm_nodes(mm) (&(mm)->head_node.node_list)
350 
351 /**
352  * drm_mm_for_each_node - iterator to walk over all allocated nodes
353  * @entry: &struct drm_mm_node to assign to in each iteration step
354  * @mm: &drm_mm allocator to walk
355  *
356  * This iterator walks over all nodes in the range allocator. It is implemented
357  * with list_for_each(), so not save against removal of elements.
358  */
359 #define drm_mm_for_each_node(entry, mm) \
360 	list_for_each_entry(entry, drm_mm_nodes(mm), node_list)
361 
362 /**
363  * drm_mm_for_each_node_safe - iterator to walk over all allocated nodes
364  * @entry: &struct drm_mm_node to assign to in each iteration step
365  * @next: &struct drm_mm_node to store the next step
366  * @mm: &drm_mm allocator to walk
367  *
368  * This iterator walks over all nodes in the range allocator. It is implemented
369  * with list_for_each_safe(), so save against removal of elements.
370  */
371 #define drm_mm_for_each_node_safe(entry, next, mm) \
372 	list_for_each_entry_safe(entry, next, drm_mm_nodes(mm), node_list)
373 
374 /**
375  * drm_mm_for_each_hole - iterator to walk over all holes
376  * @pos: &drm_mm_node used internally to track progress
377  * @mm: &drm_mm allocator to walk
378  * @hole_start: ulong variable to assign the hole start to on each iteration
379  * @hole_end: ulong variable to assign the hole end to on each iteration
380  *
381  * This iterator walks over all holes in the range allocator. It is implemented
382  * with list_for_each(), so not save against removal of elements. @entry is used
383  * internally and will not reflect a real drm_mm_node for the very first hole.
384  * Hence users of this iterator may not access it.
385  *
386  * Implementation Note:
387  * We need to inline list_for_each_entry in order to be able to set hole_start
388  * and hole_end on each iteration while keeping the macro sane.
389  */
390 #define drm_mm_for_each_hole(pos, mm, hole_start, hole_end) \
391 	for (pos = list_first_entry(&(mm)->hole_stack, \
392 				    typeof(*pos), hole_stack); \
393 	     &pos->hole_stack != &(mm)->hole_stack ? \
394 	     hole_start = drm_mm_hole_node_start(pos), \
395 	     hole_end = hole_start + pos->hole_size, \
396 	     1 : 0; \
397 	     pos = list_next_entry(pos, hole_stack))
398 
399 /*
400  * Basic range manager support (drm_mm.c)
401  */
402 int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node);
403 int drm_mm_insert_node_in_range(struct drm_mm *mm,
404 				struct drm_mm_node *node,
405 				u64 size,
406 				u64 alignment,
407 				unsigned long color,
408 				u64 start,
409 				u64 end,
410 				enum drm_mm_insert_mode mode);
411 
412 /**
413  * drm_mm_insert_node_generic - search for space and insert @node
414  * @mm: drm_mm to allocate from
415  * @node: preallocate node to insert
416  * @size: size of the allocation
417  * @alignment: alignment of the allocation
418  * @color: opaque tag value to use for this node
419  * @mode: fine-tune the allocation search and placement
420  *
421  * This is a simplified version of drm_mm_insert_node_in_range() with no
422  * range restrictions applied.
423  *
424  * The preallocated node must be cleared to 0.
425  *
426  * Returns:
427  * 0 on success, -ENOSPC if there's no suitable hole.
428  */
429 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)430 drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node,
431 			   u64 size, u64 alignment,
432 			   unsigned long color,
433 			   enum drm_mm_insert_mode mode)
434 {
435 	return drm_mm_insert_node_in_range(mm, node,
436 					   size, alignment, color,
437 					   0, U64_MAX, mode);
438 }
439 
440 /**
441  * drm_mm_insert_node - search for space and insert @node
442  * @mm: drm_mm to allocate from
443  * @node: preallocate node to insert
444  * @size: size of the allocation
445  *
446  * This is a simplified version of drm_mm_insert_node_generic() with @color set
447  * to 0.
448  *
449  * The preallocated node must be cleared to 0.
450  *
451  * Returns:
452  * 0 on success, -ENOSPC if there's no suitable hole.
453  */
drm_mm_insert_node(struct drm_mm * mm,struct drm_mm_node * node,u64 size)454 static inline int drm_mm_insert_node(struct drm_mm *mm,
455 				     struct drm_mm_node *node,
456 				     u64 size)
457 {
458 	return drm_mm_insert_node_generic(mm, node, size, 0, 0, 0);
459 }
460 
461 void drm_mm_remove_node(struct drm_mm_node *node);
462 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new);
463 void drm_mm_init(struct drm_mm *mm, u64 start, u64 size);
464 void drm_mm_takedown(struct drm_mm *mm);
465 
466 /**
467  * drm_mm_clean - checks whether an allocator is clean
468  * @mm: drm_mm allocator to check
469  *
470  * Returns:
471  * True if the allocator is completely free, false if there's still a node
472  * allocated in it.
473  */
drm_mm_clean(const struct drm_mm * mm)474 static inline bool drm_mm_clean(const struct drm_mm *mm)
475 {
476 	return list_empty(drm_mm_nodes(mm));
477 }
478 
479 struct drm_mm_node *
480 __drm_mm_interval_first(const struct drm_mm *mm, u64 start, u64 last);
481 
482 /**
483  * drm_mm_for_each_node_in_range - iterator to walk over a range of
484  * allocated nodes
485  * @node__: drm_mm_node structure to assign to in each iteration step
486  * @mm__: drm_mm allocator to walk
487  * @start__: starting offset, the first node will overlap this
488  * @end__: ending offset, the last node will start before this (but may overlap)
489  *
490  * This iterator walks over all nodes in the range allocator that lie
491  * between @start and @end. It is implemented similarly to list_for_each(),
492  * but using the internal interval tree to accelerate the search for the
493  * starting node, and so not safe against removal of elements. It assumes
494  * that @end is within (or is the upper limit of) the drm_mm allocator.
495  * If [@start, @end] are beyond the range of the drm_mm, the iterator may walk
496  * over the special _unallocated_ &drm_mm.head_node, and may even continue
497  * indefinitely.
498  */
499 #define drm_mm_for_each_node_in_range(node__, mm__, start__, end__)	\
500 	for (node__ = __drm_mm_interval_first((mm__), (start__), (end__)-1); \
501 	     node__->start < (end__);					\
502 	     node__ = list_next_entry(node__, node_list))
503 
504 void drm_mm_scan_init_with_range(struct drm_mm_scan *scan,
505 				 struct drm_mm *mm,
506 				 u64 size, u64 alignment, unsigned long color,
507 				 u64 start, u64 end,
508 				 enum drm_mm_insert_mode mode);
509 
510 /**
511  * drm_mm_scan_init - initialize lru scanning
512  * @scan: scan state
513  * @mm: drm_mm to scan
514  * @size: size of the allocation
515  * @alignment: alignment of the allocation
516  * @color: opaque tag value to use for the allocation
517  * @mode: fine-tune the allocation search and placement
518  *
519  * This is a simplified version of drm_mm_scan_init_with_range() with no range
520  * restrictions applied.
521  *
522  * This simply sets up the scanning routines with the parameters for the desired
523  * hole.
524  *
525  * Warning:
526  * As long as the scan list is non-empty, no other operations than
527  * adding/removing nodes to/from the scan list are allowed.
528  */
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)529 static inline void drm_mm_scan_init(struct drm_mm_scan *scan,
530 				    struct drm_mm *mm,
531 				    u64 size,
532 				    u64 alignment,
533 				    unsigned long color,
534 				    enum drm_mm_insert_mode mode)
535 {
536 	drm_mm_scan_init_with_range(scan, mm,
537 				    size, alignment, color,
538 				    0, U64_MAX, mode);
539 }
540 
541 bool drm_mm_scan_add_block(struct drm_mm_scan *scan,
542 			   struct drm_mm_node *node);
543 bool drm_mm_scan_remove_block(struct drm_mm_scan *scan,
544 			      struct drm_mm_node *node);
545 struct drm_mm_node *drm_mm_scan_color_evict(struct drm_mm_scan *scan);
546 
547 void drm_mm_print(const struct drm_mm *mm, struct drm_printer *p);
548 
549 #endif
550