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