1 /************************************************************************** 2 * 3 * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. 4 * All Rights Reserved. 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a 7 * copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sub license, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice (including the 15 * next paragraph) shall be included in all copies or substantial portions 16 * of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 21 * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 22 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 23 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 24 * USE OR OTHER DEALINGS IN THE SOFTWARE. 25 * 26 * 27 **************************************************************************/ 28 29 /* 30 * Generic simple memory manager implementation. Intended to be used as a base 31 * class implementation for more advanced memory managers. 32 * 33 * Note that the algorithm used is quite simple and there might be substantial 34 * performance gains if a smarter free list is implemented. Currently it is just an 35 * unordered stack of free regions. This could easily be improved if an RB-tree 36 * is used instead. At least if we expect heavy fragmentation. 37 * 38 * Aligned allocations can also see improvement. 39 * 40 * Authors: 41 * Thomas Hellström <thomas-at-tungstengraphics-dot-com> 42 */ 43 44 #include <drm/drmP.h> 45 #include <drm/drm_mm.h> 46 #include <linux/slab.h> 47 #include <linux/seq_file.h> 48 #include <linux/export.h> 49 50 /** 51 * DOC: Overview 52 * 53 * drm_mm provides a simple range allocator. The drivers are free to use the 54 * resource allocator from the linux core if it suits them, the upside of drm_mm 55 * is that it's in the DRM core. Which means that it's easier to extend for 56 * some of the crazier special purpose needs of gpus. 57 * 58 * The main data struct is &drm_mm, allocations are tracked in &drm_mm_node. 59 * Drivers are free to embed either of them into their own suitable 60 * datastructures. drm_mm itself will not do any allocations of its own, so if 61 * drivers choose not to embed nodes they need to still allocate them 62 * themselves. 63 * 64 * The range allocator also supports reservation of preallocated blocks. This is 65 * useful for taking over initial mode setting configurations from the firmware, 66 * where an object needs to be created which exactly matches the firmware's 67 * scanout target. As long as the range is still free it can be inserted anytime 68 * after the allocator is initialized, which helps with avoiding looped 69 * depencies in the driver load sequence. 70 * 71 * drm_mm maintains a stack of most recently freed holes, which of all 72 * simplistic datastructures seems to be a fairly decent approach to clustering 73 * allocations and avoiding too much fragmentation. This means free space 74 * searches are O(num_holes). Given that all the fancy features drm_mm supports 75 * something better would be fairly complex and since gfx thrashing is a fairly 76 * steep cliff not a real concern. Removing a node again is O(1). 77 * 78 * drm_mm supports a few features: Alignment and range restrictions can be 79 * supplied. Further more every &drm_mm_node has a color value (which is just an 80 * opaqua unsigned long) which in conjunction with a driver callback can be used 81 * to implement sophisticated placement restrictions. The i915 DRM driver uses 82 * this to implement guard pages between incompatible caching domains in the 83 * graphics TT. 84 * 85 * Two behaviors are supported for searching and allocating: bottom-up and top-down. 86 * The default is bottom-up. Top-down allocation can be used if the memory area 87 * has different restrictions, or just to reduce fragmentation. 88 * 89 * Finally iteration helpers to walk all nodes and all holes are provided as are 90 * some basic allocator dumpers for debugging. 91 */ 92 93 static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, 94 u64 size, 95 unsigned alignment, 96 unsigned long color, 97 enum drm_mm_search_flags flags); 98 static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, 99 u64 size, 100 unsigned alignment, 101 unsigned long color, 102 u64 start, 103 u64 end, 104 enum drm_mm_search_flags flags); 105 106 static void drm_mm_insert_helper(struct drm_mm_node *hole_node, 107 struct drm_mm_node *node, 108 u64 size, unsigned alignment, 109 unsigned long color, 110 enum drm_mm_allocator_flags flags) 111 { 112 struct drm_mm *mm = hole_node->mm; 113 u64 hole_start = drm_mm_hole_node_start(hole_node); 114 u64 hole_end = drm_mm_hole_node_end(hole_node); 115 u64 adj_start = hole_start; 116 u64 adj_end = hole_end; 117 118 BUG_ON(node->allocated); 119 120 if (mm->color_adjust) 121 mm->color_adjust(hole_node, color, &adj_start, &adj_end); 122 123 if (flags & DRM_MM_CREATE_TOP) 124 adj_start = adj_end - size; 125 126 if (alignment) { 127 u64 tmp = adj_start; 128 unsigned rem; 129 130 rem = do_div(tmp, alignment); 131 if (rem) { 132 if (flags & DRM_MM_CREATE_TOP) 133 adj_start -= rem; 134 else 135 adj_start += alignment - rem; 136 } 137 } 138 139 BUG_ON(adj_start < hole_start); 140 BUG_ON(adj_end > hole_end); 141 142 if (adj_start == hole_start) { 143 hole_node->hole_follows = 0; 144 list_del(&hole_node->hole_stack); 145 } 146 147 node->start = adj_start; 148 node->size = size; 149 node->mm = mm; 150 node->color = color; 151 node->allocated = 1; 152 153 list_add(&node->node_list, &hole_node->node_list); 154 155 BUG_ON(node->start + node->size > adj_end); 156 157 node->hole_follows = 0; 158 if (__drm_mm_hole_node_start(node) < hole_end) { 159 list_add(&node->hole_stack, &mm->hole_stack); 160 node->hole_follows = 1; 161 } 162 } 163 164 /** 165 * drm_mm_reserve_node - insert an pre-initialized node 166 * @mm: drm_mm allocator to insert @node into 167 * @node: drm_mm_node to insert 168 * 169 * This functions inserts an already set-up drm_mm_node into the allocator, 170 * meaning that start, size and color must be set by the caller. This is useful 171 * to initialize the allocator with preallocated objects which must be set-up 172 * before the range allocator can be set-up, e.g. when taking over a firmware 173 * framebuffer. 174 * 175 * Returns: 176 * 0 on success, -ENOSPC if there's no hole where @node is. 177 */ 178 int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) 179 { 180 struct drm_mm_node *hole; 181 u64 end; 182 u64 hole_start; 183 u64 hole_end; 184 185 BUG_ON(node == NULL); 186 187 if (WARN_ON(node->size == 0)) 188 return -EINVAL; 189 190 if (WARN_ON(node->size == 0)) 191 return -EINVAL; 192 193 end = node->start + node->size; 194 195 /* Find the relevant hole to add our node to */ 196 drm_mm_for_each_hole(hole, mm, hole_start, hole_end) { 197 if (hole_start > node->start || hole_end < end) 198 continue; 199 200 node->mm = mm; 201 node->allocated = 1; 202 203 list_add(&node->node_list, &hole->node_list); 204 205 if (node->start == hole_start) { 206 hole->hole_follows = 0; 207 list_del_init(&hole->hole_stack); 208 } 209 210 node->hole_follows = 0; 211 if (end != hole_end) { 212 list_add(&node->hole_stack, &mm->hole_stack); 213 node->hole_follows = 1; 214 } 215 216 return 0; 217 } 218 219 return -ENOSPC; 220 } 221 EXPORT_SYMBOL(drm_mm_reserve_node); 222 223 /** 224 * drm_mm_insert_node_generic - search for space and insert @node 225 * @mm: drm_mm to allocate from 226 * @node: preallocate node to insert 227 * @size: size of the allocation 228 * @alignment: alignment of the allocation 229 * @color: opaque tag value to use for this node 230 * @sflags: flags to fine-tune the allocation search 231 * @aflags: flags to fine-tune the allocation behavior 232 * 233 * The preallocated node must be cleared to 0. 234 * 235 * Returns: 236 * 0 on success, -ENOSPC if there's no suitable hole. 237 */ 238 int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node, 239 u64 size, unsigned alignment, 240 unsigned long color, 241 enum drm_mm_search_flags sflags, 242 enum drm_mm_allocator_flags aflags) 243 { 244 struct drm_mm_node *hole_node; 245 246 if (WARN_ON(size == 0)) 247 return -EINVAL; 248 249 if (WARN_ON(size == 0)) 250 return -EINVAL; 251 252 hole_node = drm_mm_search_free_generic(mm, size, alignment, 253 color, sflags); 254 if (!hole_node) 255 return -ENOSPC; 256 257 drm_mm_insert_helper(hole_node, node, size, alignment, color, aflags); 258 return 0; 259 } 260 EXPORT_SYMBOL(drm_mm_insert_node_generic); 261 262 static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, 263 struct drm_mm_node *node, 264 u64 size, unsigned alignment, 265 unsigned long color, 266 u64 start, u64 end, 267 enum drm_mm_allocator_flags flags) 268 { 269 struct drm_mm *mm = hole_node->mm; 270 u64 hole_start = drm_mm_hole_node_start(hole_node); 271 u64 hole_end = drm_mm_hole_node_end(hole_node); 272 u64 adj_start = hole_start; 273 u64 adj_end = hole_end; 274 275 BUG_ON(!hole_node->hole_follows || node->allocated); 276 277 if (adj_start < start) 278 adj_start = start; 279 if (adj_end > end) 280 adj_end = end; 281 282 if (mm->color_adjust) 283 mm->color_adjust(hole_node, color, &adj_start, &adj_end); 284 285 if (flags & DRM_MM_CREATE_TOP) 286 adj_start = adj_end - size; 287 288 if (alignment) { 289 u64 tmp = adj_start; 290 unsigned rem; 291 292 rem = do_div(tmp, alignment); 293 if (rem) { 294 if (flags & DRM_MM_CREATE_TOP) 295 adj_start -= rem; 296 else 297 adj_start += alignment - rem; 298 } 299 } 300 301 if (adj_start == hole_start) { 302 hole_node->hole_follows = 0; 303 list_del(&hole_node->hole_stack); 304 } 305 306 node->start = adj_start; 307 node->size = size; 308 node->mm = mm; 309 node->color = color; 310 node->allocated = 1; 311 312 list_add(&node->node_list, &hole_node->node_list); 313 314 BUG_ON(node->start < start); 315 BUG_ON(node->start < adj_start); 316 BUG_ON(node->start + node->size > adj_end); 317 BUG_ON(node->start + node->size > end); 318 319 node->hole_follows = 0; 320 if (__drm_mm_hole_node_start(node) < hole_end) { 321 list_add(&node->hole_stack, &mm->hole_stack); 322 node->hole_follows = 1; 323 } 324 } 325 326 /** 327 * drm_mm_insert_node_in_range_generic - ranged search for space and insert @node 328 * @mm: drm_mm to allocate from 329 * @node: preallocate node to insert 330 * @size: size of the allocation 331 * @alignment: alignment of the allocation 332 * @color: opaque tag value to use for this node 333 * @start: start of the allowed range for this node 334 * @end: end of the allowed range for this node 335 * @sflags: flags to fine-tune the allocation search 336 * @aflags: flags to fine-tune the allocation behavior 337 * 338 * The preallocated node must be cleared to 0. 339 * 340 * Returns: 341 * 0 on success, -ENOSPC if there's no suitable hole. 342 */ 343 int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node, 344 u64 size, unsigned alignment, 345 unsigned long color, 346 u64 start, u64 end, 347 enum drm_mm_search_flags sflags, 348 enum drm_mm_allocator_flags aflags) 349 { 350 struct drm_mm_node *hole_node; 351 352 if (WARN_ON(size == 0)) 353 return -EINVAL; 354 355 if (WARN_ON(size == 0)) 356 return -EINVAL; 357 358 hole_node = drm_mm_search_free_in_range_generic(mm, 359 size, alignment, color, 360 start, end, sflags); 361 if (!hole_node) 362 return -ENOSPC; 363 364 drm_mm_insert_helper_range(hole_node, node, 365 size, alignment, color, 366 start, end, aflags); 367 return 0; 368 } 369 EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic); 370 371 /** 372 * drm_mm_remove_node - Remove a memory node from the allocator. 373 * @node: drm_mm_node to remove 374 * 375 * This just removes a node from its drm_mm allocator. The node does not need to 376 * be cleared again before it can be re-inserted into this or any other drm_mm 377 * allocator. It is a bug to call this function on a un-allocated node. 378 */ 379 void drm_mm_remove_node(struct drm_mm_node *node) 380 { 381 struct drm_mm *mm = node->mm; 382 struct drm_mm_node *prev_node; 383 384 if (WARN_ON(!node->allocated)) 385 return; 386 387 BUG_ON(node->scanned_block || node->scanned_prev_free 388 || node->scanned_next_free); 389 390 prev_node = 391 list_entry(node->node_list.prev, struct drm_mm_node, node_list); 392 393 if (node->hole_follows) { 394 BUG_ON(__drm_mm_hole_node_start(node) == 395 __drm_mm_hole_node_end(node)); 396 list_del(&node->hole_stack); 397 } else 398 BUG_ON(__drm_mm_hole_node_start(node) != 399 __drm_mm_hole_node_end(node)); 400 401 402 if (!prev_node->hole_follows) { 403 prev_node->hole_follows = 1; 404 list_add(&prev_node->hole_stack, &mm->hole_stack); 405 } else 406 list_move(&prev_node->hole_stack, &mm->hole_stack); 407 408 list_del(&node->node_list); 409 node->allocated = 0; 410 } 411 EXPORT_SYMBOL(drm_mm_remove_node); 412 413 static int check_free_hole(u64 start, u64 end, u64 size, unsigned alignment) 414 { 415 if (end - start < size) 416 return 0; 417 418 if (alignment) { 419 u64 tmp = start; 420 unsigned rem; 421 422 rem = do_div(tmp, alignment); 423 if (rem) 424 start += alignment - rem; 425 } 426 427 return end >= start + size; 428 } 429 430 static struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, 431 u64 size, 432 unsigned alignment, 433 unsigned long color, 434 enum drm_mm_search_flags flags) 435 { 436 struct drm_mm_node *entry; 437 struct drm_mm_node *best; 438 u64 adj_start; 439 u64 adj_end; 440 u64 best_size; 441 442 BUG_ON(mm->scanned_blocks); 443 444 best = NULL; 445 best_size = ~0UL; 446 447 __drm_mm_for_each_hole(entry, mm, adj_start, adj_end, 448 flags & DRM_MM_SEARCH_BELOW) { 449 u64 hole_size = adj_end - adj_start; 450 451 if (mm->color_adjust) { 452 mm->color_adjust(entry, color, &adj_start, &adj_end); 453 if (adj_end <= adj_start) 454 continue; 455 } 456 457 if (!check_free_hole(adj_start, adj_end, size, alignment)) 458 continue; 459 460 if (!(flags & DRM_MM_SEARCH_BEST)) 461 return entry; 462 463 if (hole_size < best_size) { 464 best = entry; 465 best_size = hole_size; 466 } 467 } 468 469 return best; 470 } 471 472 static struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, 473 u64 size, 474 unsigned alignment, 475 unsigned long color, 476 u64 start, 477 u64 end, 478 enum drm_mm_search_flags flags) 479 { 480 struct drm_mm_node *entry; 481 struct drm_mm_node *best; 482 u64 adj_start; 483 u64 adj_end; 484 u64 best_size; 485 486 BUG_ON(mm->scanned_blocks); 487 488 best = NULL; 489 best_size = ~0UL; 490 491 __drm_mm_for_each_hole(entry, mm, adj_start, adj_end, 492 flags & DRM_MM_SEARCH_BELOW) { 493 u64 hole_size = adj_end - adj_start; 494 495 if (adj_start < start) 496 adj_start = start; 497 if (adj_end > end) 498 adj_end = end; 499 500 if (mm->color_adjust) { 501 mm->color_adjust(entry, color, &adj_start, &adj_end); 502 if (adj_end <= adj_start) 503 continue; 504 } 505 506 if (!check_free_hole(adj_start, adj_end, size, alignment)) 507 continue; 508 509 if (!(flags & DRM_MM_SEARCH_BEST)) 510 return entry; 511 512 if (hole_size < best_size) { 513 best = entry; 514 best_size = hole_size; 515 } 516 } 517 518 return best; 519 } 520 521 /** 522 * drm_mm_replace_node - move an allocation from @old to @new 523 * @old: drm_mm_node to remove from the allocator 524 * @new: drm_mm_node which should inherit @old's allocation 525 * 526 * This is useful for when drivers embed the drm_mm_node structure and hence 527 * can't move allocations by reassigning pointers. It's a combination of remove 528 * and insert with the guarantee that the allocation start will match. 529 */ 530 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) 531 { 532 list_replace(&old->node_list, &new->node_list); 533 list_replace(&old->hole_stack, &new->hole_stack); 534 new->hole_follows = old->hole_follows; 535 new->mm = old->mm; 536 new->start = old->start; 537 new->size = old->size; 538 new->color = old->color; 539 540 old->allocated = 0; 541 new->allocated = 1; 542 } 543 EXPORT_SYMBOL(drm_mm_replace_node); 544 545 /** 546 * DOC: lru scan roaster 547 * 548 * Very often GPUs need to have continuous allocations for a given object. When 549 * evicting objects to make space for a new one it is therefore not most 550 * efficient when we simply start to select all objects from the tail of an LRU 551 * until there's a suitable hole: Especially for big objects or nodes that 552 * otherwise have special allocation constraints there's a good chance we evict 553 * lots of (smaller) objects unecessarily. 554 * 555 * The DRM range allocator supports this use-case through the scanning 556 * interfaces. First a scan operation needs to be initialized with 557 * drm_mm_init_scan() or drm_mm_init_scan_with_range(). The the driver adds 558 * objects to the roaster (probably by walking an LRU list, but this can be 559 * freely implemented) until a suitable hole is found or there's no further 560 * evitable object. 561 * 562 * The the driver must walk through all objects again in exactly the reverse 563 * order to restore the allocator state. Note that while the allocator is used 564 * in the scan mode no other operation is allowed. 565 * 566 * Finally the driver evicts all objects selected in the scan. Adding and 567 * removing an object is O(1), and since freeing a node is also O(1) the overall 568 * complexity is O(scanned_objects). So like the free stack which needs to be 569 * walked before a scan operation even begins this is linear in the number of 570 * objects. It doesn't seem to hurt badly. 571 */ 572 573 /** 574 * drm_mm_init_scan - initialize lru scanning 575 * @mm: drm_mm to scan 576 * @size: size of the allocation 577 * @alignment: alignment of the allocation 578 * @color: opaque tag value to use for the allocation 579 * 580 * This simply sets up the scanning routines with the parameters for the desired 581 * hole. Note that there's no need to specify allocation flags, since they only 582 * change the place a node is allocated from within a suitable hole. 583 * 584 * Warning: 585 * As long as the scan list is non-empty, no other operations than 586 * adding/removing nodes to/from the scan list are allowed. 587 */ 588 void drm_mm_init_scan(struct drm_mm *mm, 589 u64 size, 590 unsigned alignment, 591 unsigned long color) 592 { 593 mm->scan_color = color; 594 mm->scan_alignment = alignment; 595 mm->scan_size = size; 596 mm->scanned_blocks = 0; 597 mm->scan_hit_start = 0; 598 mm->scan_hit_end = 0; 599 mm->scan_check_range = 0; 600 mm->prev_scanned_node = NULL; 601 } 602 EXPORT_SYMBOL(drm_mm_init_scan); 603 604 /** 605 * drm_mm_init_scan - initialize range-restricted lru scanning 606 * @mm: drm_mm to scan 607 * @size: size of the allocation 608 * @alignment: alignment of the allocation 609 * @color: opaque tag value to use for the allocation 610 * @start: start of the allowed range for the allocation 611 * @end: end of the allowed range for the allocation 612 * 613 * This simply sets up the scanning routines with the parameters for the desired 614 * hole. Note that there's no need to specify allocation flags, since they only 615 * change the place a node is allocated from within a suitable hole. 616 * 617 * Warning: 618 * As long as the scan list is non-empty, no other operations than 619 * adding/removing nodes to/from the scan list are allowed. 620 */ 621 void drm_mm_init_scan_with_range(struct drm_mm *mm, 622 u64 size, 623 unsigned alignment, 624 unsigned long color, 625 u64 start, 626 u64 end) 627 { 628 mm->scan_color = color; 629 mm->scan_alignment = alignment; 630 mm->scan_size = size; 631 mm->scanned_blocks = 0; 632 mm->scan_hit_start = 0; 633 mm->scan_hit_end = 0; 634 mm->scan_start = start; 635 mm->scan_end = end; 636 mm->scan_check_range = 1; 637 mm->prev_scanned_node = NULL; 638 } 639 EXPORT_SYMBOL(drm_mm_init_scan_with_range); 640 641 /** 642 * drm_mm_scan_add_block - add a node to the scan list 643 * @node: drm_mm_node to add 644 * 645 * Add a node to the scan list that might be freed to make space for the desired 646 * hole. 647 * 648 * Returns: 649 * True if a hole has been found, false otherwise. 650 */ 651 bool drm_mm_scan_add_block(struct drm_mm_node *node) 652 { 653 struct drm_mm *mm = node->mm; 654 struct drm_mm_node *prev_node; 655 u64 hole_start, hole_end; 656 u64 adj_start, adj_end; 657 658 mm->scanned_blocks++; 659 660 BUG_ON(node->scanned_block); 661 node->scanned_block = 1; 662 663 prev_node = list_entry(node->node_list.prev, struct drm_mm_node, 664 node_list); 665 666 node->scanned_preceeds_hole = prev_node->hole_follows; 667 prev_node->hole_follows = 1; 668 list_del(&node->node_list); 669 node->node_list.prev = &prev_node->node_list; 670 node->node_list.next = &mm->prev_scanned_node->node_list; 671 mm->prev_scanned_node = node; 672 673 adj_start = hole_start = drm_mm_hole_node_start(prev_node); 674 adj_end = hole_end = drm_mm_hole_node_end(prev_node); 675 676 if (mm->scan_check_range) { 677 if (adj_start < mm->scan_start) 678 adj_start = mm->scan_start; 679 if (adj_end > mm->scan_end) 680 adj_end = mm->scan_end; 681 } 682 683 if (mm->color_adjust) 684 mm->color_adjust(prev_node, mm->scan_color, 685 &adj_start, &adj_end); 686 687 if (check_free_hole(adj_start, adj_end, 688 mm->scan_size, mm->scan_alignment)) { 689 mm->scan_hit_start = hole_start; 690 mm->scan_hit_end = hole_end; 691 return true; 692 } 693 694 return false; 695 } 696 EXPORT_SYMBOL(drm_mm_scan_add_block); 697 698 /** 699 * drm_mm_scan_remove_block - remove a node from the scan list 700 * @node: drm_mm_node to remove 701 * 702 * Nodes _must_ be removed in the exact same order from the scan list as they 703 * have been added, otherwise the internal state of the memory manager will be 704 * corrupted. 705 * 706 * When the scan list is empty, the selected memory nodes can be freed. An 707 * immediately following drm_mm_search_free with !DRM_MM_SEARCH_BEST will then 708 * return the just freed block (because its at the top of the free_stack list). 709 * 710 * Returns: 711 * True if this block should be evicted, false otherwise. Will always 712 * return false when no hole has been found. 713 */ 714 bool drm_mm_scan_remove_block(struct drm_mm_node *node) 715 { 716 struct drm_mm *mm = node->mm; 717 struct drm_mm_node *prev_node; 718 719 mm->scanned_blocks--; 720 721 BUG_ON(!node->scanned_block); 722 node->scanned_block = 0; 723 724 prev_node = list_entry(node->node_list.prev, struct drm_mm_node, 725 node_list); 726 727 prev_node->hole_follows = node->scanned_preceeds_hole; 728 list_add(&node->node_list, &prev_node->node_list); 729 730 return (drm_mm_hole_node_end(node) > mm->scan_hit_start && 731 node->start < mm->scan_hit_end); 732 } 733 EXPORT_SYMBOL(drm_mm_scan_remove_block); 734 735 /** 736 * drm_mm_clean - checks whether an allocator is clean 737 * @mm: drm_mm allocator to check 738 * 739 * Returns: 740 * True if the allocator is completely free, false if there's still a node 741 * allocated in it. 742 */ 743 bool drm_mm_clean(struct drm_mm * mm) 744 { 745 struct list_head *head = &mm->head_node.node_list; 746 747 return (head->next->next == head); 748 } 749 EXPORT_SYMBOL(drm_mm_clean); 750 751 /** 752 * drm_mm_init - initialize a drm-mm allocator 753 * @mm: the drm_mm structure to initialize 754 * @start: start of the range managed by @mm 755 * @size: end of the range managed by @mm 756 * 757 * Note that @mm must be cleared to 0 before calling this function. 758 */ 759 void drm_mm_init(struct drm_mm * mm, u64 start, u64 size) 760 { 761 INIT_LIST_HEAD(&mm->hole_stack); 762 mm->scanned_blocks = 0; 763 764 /* Clever trick to avoid a special case in the free hole tracking. */ 765 INIT_LIST_HEAD(&mm->head_node.node_list); 766 mm->head_node.hole_follows = 1; 767 mm->head_node.scanned_block = 0; 768 mm->head_node.scanned_prev_free = 0; 769 mm->head_node.scanned_next_free = 0; 770 mm->head_node.mm = mm; 771 mm->head_node.start = start + size; 772 mm->head_node.size = start - mm->head_node.start; 773 list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack); 774 775 mm->color_adjust = NULL; 776 } 777 EXPORT_SYMBOL(drm_mm_init); 778 779 /** 780 * drm_mm_takedown - clean up a drm_mm allocator 781 * @mm: drm_mm allocator to clean up 782 * 783 * Note that it is a bug to call this function on an allocator which is not 784 * clean. 785 */ 786 void drm_mm_takedown(struct drm_mm * mm) 787 { 788 WARN(!list_empty(&mm->head_node.node_list), 789 "Memory manager not clean during takedown.\n"); 790 } 791 EXPORT_SYMBOL(drm_mm_takedown); 792 793 static u64 drm_mm_debug_hole(struct drm_mm_node *entry, 794 const char *prefix) 795 { 796 u64 hole_start, hole_end, hole_size; 797 798 if (entry->hole_follows) { 799 hole_start = drm_mm_hole_node_start(entry); 800 hole_end = drm_mm_hole_node_end(entry); 801 hole_size = hole_end - hole_start; 802 pr_debug("%s %#llx-%#llx: %llu: free\n", prefix, hole_start, 803 hole_end, hole_size); 804 return hole_size; 805 } 806 807 return 0; 808 } 809 810 /** 811 * drm_mm_debug_table - dump allocator state to dmesg 812 * @mm: drm_mm allocator to dump 813 * @prefix: prefix to use for dumping to dmesg 814 */ 815 void drm_mm_debug_table(struct drm_mm *mm, const char *prefix) 816 { 817 struct drm_mm_node *entry; 818 u64 total_used = 0, total_free = 0, total = 0; 819 820 total_free += drm_mm_debug_hole(&mm->head_node, prefix); 821 822 drm_mm_for_each_node(entry, mm) { 823 pr_debug("%s %#llx-%#llx: %llu: used\n", prefix, entry->start, 824 entry->start + entry->size, entry->size); 825 total_used += entry->size; 826 total_free += drm_mm_debug_hole(entry, prefix); 827 } 828 total = total_free + total_used; 829 830 pr_debug("%s total: %llu, used %llu free %llu\n", prefix, total, 831 total_used, total_free); 832 } 833 EXPORT_SYMBOL(drm_mm_debug_table); 834 835 #if defined(CONFIG_DEBUG_FS) 836 static u64 drm_mm_dump_hole(struct seq_file *m, struct drm_mm_node *entry) 837 { 838 u64 hole_start, hole_end, hole_size; 839 840 if (entry->hole_follows) { 841 hole_start = drm_mm_hole_node_start(entry); 842 hole_end = drm_mm_hole_node_end(entry); 843 hole_size = hole_end - hole_start; 844 seq_printf(m, "%#018llx-%#018llx: %llu: free\n", hole_start, 845 hole_end, hole_size); 846 return hole_size; 847 } 848 849 return 0; 850 } 851 852 /** 853 * drm_mm_dump_table - dump allocator state to a seq_file 854 * @m: seq_file to dump to 855 * @mm: drm_mm allocator to dump 856 */ 857 int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm) 858 { 859 struct drm_mm_node *entry; 860 u64 total_used = 0, total_free = 0, total = 0; 861 862 total_free += drm_mm_dump_hole(m, &mm->head_node); 863 864 drm_mm_for_each_node(entry, mm) { 865 seq_printf(m, "%#018llx-%#018llx: %llu: used\n", entry->start, 866 entry->start + entry->size, entry->size); 867 total_used += entry->size; 868 total_free += drm_mm_dump_hole(m, entry); 869 } 870 total = total_free + total_used; 871 872 seq_printf(m, "total: %llu, used %llu free %llu\n", total, 873 total_used, total_free); 874 return 0; 875 } 876 EXPORT_SYMBOL(drm_mm_dump_table); 877 #endif 878