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