~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/drm/drm_mm.h

Version: ~ [ linux-6.1-rc7 ] ~ [ linux-6.0.10 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.80 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.156 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.225 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.267 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.300 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.334 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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  */
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  */
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  */
289 static inline bool drm_mm_hole_follows(const struct drm_mm_node *node)
290 {
291         return node->hole_size;
292 }
293 
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  */
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 
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  */
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
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  */
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  */
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  */
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 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp