13f6063ccSDavid Shao /************************************************************************** 23f6063ccSDavid Shao * 33f6063ccSDavid Shao * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. 43f6063ccSDavid Shao * All Rights Reserved. 53f6063ccSDavid Shao * 63f6063ccSDavid Shao * Permission is hereby granted, free of charge, to any person obtaining a 73f6063ccSDavid Shao * copy of this software and associated documentation files (the 83f6063ccSDavid Shao * "Software"), to deal in the Software without restriction, including 93f6063ccSDavid Shao * without limitation the rights to use, copy, modify, merge, publish, 103f6063ccSDavid Shao * distribute, sub license, and/or sell copies of the Software, and to 113f6063ccSDavid Shao * permit persons to whom the Software is furnished to do so, subject to 123f6063ccSDavid Shao * the following conditions: 133f6063ccSDavid Shao * 143f6063ccSDavid Shao * The above copyright notice and this permission notice (including the 153f6063ccSDavid Shao * next paragraph) shall be included in all copies or substantial portions 163f6063ccSDavid Shao * of the Software. 173f6063ccSDavid Shao * 183f6063ccSDavid Shao * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 193f6063ccSDavid Shao * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 203f6063ccSDavid Shao * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 213f6063ccSDavid Shao * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 223f6063ccSDavid Shao * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 233f6063ccSDavid Shao * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 243f6063ccSDavid Shao * USE OR OTHER DEALINGS IN THE SOFTWARE. 253f6063ccSDavid Shao * 26ea132f0fSFrançois Tigeot * 273f6063ccSDavid Shao **************************************************************************/ 283f6063ccSDavid Shao 293f6063ccSDavid Shao /* 303f6063ccSDavid Shao * Generic simple memory manager implementation. Intended to be used as a base 313f6063ccSDavid Shao * class implementation for more advanced memory managers. 323f6063ccSDavid Shao * 333f6063ccSDavid Shao * Note that the algorithm used is quite simple and there might be substantial 343f6063ccSDavid Shao * performance gains if a smarter free list is implemented. Currently it is just an 353f6063ccSDavid Shao * unordered stack of free regions. This could easily be improved if an RB-tree 363f6063ccSDavid Shao * is used instead. At least if we expect heavy fragmentation. 373f6063ccSDavid Shao * 383f6063ccSDavid Shao * Aligned allocations can also see improvement. 393f6063ccSDavid Shao * 403f6063ccSDavid Shao * Authors: 413f6063ccSDavid Shao * Thomas Hellström <thomas-at-tungstengraphics-dot-com> 423f6063ccSDavid Shao */ 433f6063ccSDavid Shao 4418e26a6dSFrançois Tigeot #include <drm/drmP.h> 4518e26a6dSFrançois Tigeot #include <drm/drm_mm.h> 46b6fbc077SFrançois Tigeot #include <linux/slab.h> 479edbd4a0SFrançois Tigeot #include <linux/seq_file.h> 48ea132f0fSFrançois Tigeot #include <linux/export.h> 493f6063ccSDavid Shao 503f6063ccSDavid Shao #define MM_UNUSED_TARGET 4 513f6063ccSDavid Shao 523f6063ccSDavid Shao static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic) 533f6063ccSDavid Shao { 543f6063ccSDavid Shao struct drm_mm_node *child; 553f6063ccSDavid Shao 56ea132f0fSFrançois Tigeot if (atomic) 57b6fbc077SFrançois Tigeot child = kzalloc(sizeof(*child), GFP_ATOMIC); 58ea132f0fSFrançois Tigeot else 59b6fbc077SFrançois Tigeot child = kzalloc(sizeof(*child), GFP_KERNEL); 603f6063ccSDavid Shao 613f6063ccSDavid Shao if (unlikely(child == NULL)) { 62ea132f0fSFrançois Tigeot spin_lock(&mm->unused_lock); 633f6063ccSDavid Shao if (list_empty(&mm->unused_nodes)) 643f6063ccSDavid Shao child = NULL; 653f6063ccSDavid Shao else { 663f6063ccSDavid Shao child = 673f6063ccSDavid Shao list_entry(mm->unused_nodes.next, 685718399fSFrançois Tigeot struct drm_mm_node, node_list); 695718399fSFrançois Tigeot list_del(&child->node_list); 703f6063ccSDavid Shao --mm->num_unused; 713f6063ccSDavid Shao } 72ea132f0fSFrançois Tigeot spin_unlock(&mm->unused_lock); 733f6063ccSDavid Shao } 743f6063ccSDavid Shao return child; 753f6063ccSDavid Shao } 763f6063ccSDavid Shao 773f6063ccSDavid Shao int drm_mm_pre_get(struct drm_mm *mm) 783f6063ccSDavid Shao { 793f6063ccSDavid Shao struct drm_mm_node *node; 803f6063ccSDavid Shao 81ea132f0fSFrançois Tigeot spin_lock(&mm->unused_lock); 823f6063ccSDavid Shao while (mm->num_unused < MM_UNUSED_TARGET) { 83ea132f0fSFrançois Tigeot spin_unlock(&mm->unused_lock); 84b6fbc077SFrançois Tigeot node = kzalloc(sizeof(*node), GFP_KERNEL); 85ea132f0fSFrançois Tigeot spin_lock(&mm->unused_lock); 863f6063ccSDavid Shao 873f6063ccSDavid Shao if (unlikely(node == NULL)) { 883f6063ccSDavid Shao int ret = (mm->num_unused < 2) ? -ENOMEM : 0; 89ea132f0fSFrançois Tigeot spin_unlock(&mm->unused_lock); 903f6063ccSDavid Shao return ret; 913f6063ccSDavid Shao } 923f6063ccSDavid Shao ++mm->num_unused; 935718399fSFrançois Tigeot list_add_tail(&node->node_list, &mm->unused_nodes); 943f6063ccSDavid Shao } 95ea132f0fSFrançois Tigeot spin_unlock(&mm->unused_lock); 963f6063ccSDavid Shao return 0; 973f6063ccSDavid Shao } 98ba55f2f5SFrançois Tigeot 99ba55f2f5SFrançois Tigeot /** 100ba55f2f5SFrançois Tigeot * DOC: Overview 101ba55f2f5SFrançois Tigeot * 102ba55f2f5SFrançois Tigeot * drm_mm provides a simple range allocator. The drivers are free to use the 103ba55f2f5SFrançois Tigeot * resource allocator from the linux core if it suits them, the upside of drm_mm 104ba55f2f5SFrançois Tigeot * is that it's in the DRM core. Which means that it's easier to extend for 105ba55f2f5SFrançois Tigeot * some of the crazier special purpose needs of gpus. 106ba55f2f5SFrançois Tigeot * 107ba55f2f5SFrançois Tigeot * The main data struct is &drm_mm, allocations are tracked in &drm_mm_node. 108ba55f2f5SFrançois Tigeot * Drivers are free to embed either of them into their own suitable 109ba55f2f5SFrançois Tigeot * datastructures. drm_mm itself will not do any allocations of its own, so if 110ba55f2f5SFrançois Tigeot * drivers choose not to embed nodes they need to still allocate them 111ba55f2f5SFrançois Tigeot * themselves. 112ba55f2f5SFrançois Tigeot * 113ba55f2f5SFrançois Tigeot * The range allocator also supports reservation of preallocated blocks. This is 114ba55f2f5SFrançois Tigeot * useful for taking over initial mode setting configurations from the firmware, 115ba55f2f5SFrançois Tigeot * where an object needs to be created which exactly matches the firmware's 116ba55f2f5SFrançois Tigeot * scanout target. As long as the range is still free it can be inserted anytime 117ba55f2f5SFrançois Tigeot * after the allocator is initialized, which helps with avoiding looped 118ba55f2f5SFrançois Tigeot * depencies in the driver load sequence. 119ba55f2f5SFrançois Tigeot * 120ba55f2f5SFrançois Tigeot * drm_mm maintains a stack of most recently freed holes, which of all 121ba55f2f5SFrançois Tigeot * simplistic datastructures seems to be a fairly decent approach to clustering 122ba55f2f5SFrançois Tigeot * allocations and avoiding too much fragmentation. This means free space 123ba55f2f5SFrançois Tigeot * searches are O(num_holes). Given that all the fancy features drm_mm supports 124ba55f2f5SFrançois Tigeot * something better would be fairly complex and since gfx thrashing is a fairly 125ba55f2f5SFrançois Tigeot * steep cliff not a real concern. Removing a node again is O(1). 126ba55f2f5SFrançois Tigeot * 127ba55f2f5SFrançois Tigeot * drm_mm supports a few features: Alignment and range restrictions can be 128ba55f2f5SFrançois Tigeot * supplied. Further more every &drm_mm_node has a color value (which is just an 129ba55f2f5SFrançois Tigeot * opaqua unsigned long) which in conjunction with a driver callback can be used 130ba55f2f5SFrançois Tigeot * to implement sophisticated placement restrictions. The i915 DRM driver uses 131ba55f2f5SFrançois Tigeot * this to implement guard pages between incompatible caching domains in the 132ba55f2f5SFrançois Tigeot * graphics TT. 133ba55f2f5SFrançois Tigeot * 134ba55f2f5SFrançois Tigeot * Two behaviors are supported for searching and allocating: bottom-up and top-down. 135ba55f2f5SFrançois Tigeot * The default is bottom-up. Top-down allocation can be used if the memory area 136ba55f2f5SFrançois Tigeot * has different restrictions, or just to reduce fragmentation. 137ba55f2f5SFrançois Tigeot * 138ba55f2f5SFrançois Tigeot * Finally iteration helpers to walk all nodes and all holes are provided as are 139ba55f2f5SFrançois Tigeot * some basic allocator dumpers for debugging. 140ba55f2f5SFrançois Tigeot */ 1413f6063ccSDavid Shao 1425718399fSFrançois Tigeot static void drm_mm_insert_helper(struct drm_mm_node *hole_node, 1435718399fSFrançois Tigeot struct drm_mm_node *node, 144*f77dbd6cSFrançois Tigeot u64 size, unsigned alignment, 145ba55f2f5SFrançois Tigeot unsigned long color, 146ba55f2f5SFrançois Tigeot enum drm_mm_allocator_flags flags) 1473f6063ccSDavid Shao { 1485718399fSFrançois Tigeot struct drm_mm *mm = hole_node->mm; 149*f77dbd6cSFrançois Tigeot u64 hole_start = drm_mm_hole_node_start(hole_node); 150*f77dbd6cSFrançois Tigeot u64 hole_end = drm_mm_hole_node_end(hole_node); 151*f77dbd6cSFrançois Tigeot u64 adj_start = hole_start; 152*f77dbd6cSFrançois Tigeot u64 adj_end = hole_end; 1533f6063ccSDavid Shao 154b6fbc077SFrançois Tigeot BUG_ON(node->allocated); 1553f6063ccSDavid Shao 156ea132f0fSFrançois Tigeot if (mm->color_adjust) 157ea132f0fSFrançois Tigeot mm->color_adjust(hole_node, color, &adj_start, &adj_end); 1583f6063ccSDavid Shao 159ba55f2f5SFrançois Tigeot if (flags & DRM_MM_CREATE_TOP) 160ba55f2f5SFrançois Tigeot adj_start = adj_end - size; 161ba55f2f5SFrançois Tigeot 162ea132f0fSFrançois Tigeot if (alignment) { 163*f77dbd6cSFrançois Tigeot u64 tmp = adj_start; 164*f77dbd6cSFrançois Tigeot unsigned rem; 165*f77dbd6cSFrançois Tigeot 166*f77dbd6cSFrançois Tigeot rem = do_div(tmp, alignment); 167*f77dbd6cSFrançois Tigeot if (rem) { 168ba55f2f5SFrançois Tigeot if (flags & DRM_MM_CREATE_TOP) 169*f77dbd6cSFrançois Tigeot adj_start -= rem; 170ba55f2f5SFrançois Tigeot else 171*f77dbd6cSFrançois Tigeot adj_start += alignment - rem; 172ea132f0fSFrançois Tigeot } 173ba55f2f5SFrançois Tigeot } 174ba55f2f5SFrançois Tigeot 175ba55f2f5SFrançois Tigeot BUG_ON(adj_start < hole_start); 176ba55f2f5SFrançois Tigeot BUG_ON(adj_end > hole_end); 177ea132f0fSFrançois Tigeot 178ea132f0fSFrançois Tigeot if (adj_start == hole_start) { 1795718399fSFrançois Tigeot hole_node->hole_follows = 0; 180ea132f0fSFrançois Tigeot list_del(&hole_node->hole_stack); 181ea132f0fSFrançois Tigeot } 1823f6063ccSDavid Shao 183ea132f0fSFrançois Tigeot node->start = adj_start; 1845718399fSFrançois Tigeot node->size = size; 1855718399fSFrançois Tigeot node->mm = mm; 186ea132f0fSFrançois Tigeot node->color = color; 1875718399fSFrançois Tigeot node->allocated = 1; 1883f6063ccSDavid Shao 1895718399fSFrançois Tigeot INIT_LIST_HEAD(&node->hole_stack); 1905718399fSFrançois Tigeot list_add(&node->node_list, &hole_node->node_list); 1915718399fSFrançois Tigeot 192ea132f0fSFrançois Tigeot BUG_ON(node->start + node->size > adj_end); 1935718399fSFrançois Tigeot 194ea132f0fSFrançois Tigeot node->hole_follows = 0; 195b6fbc077SFrançois Tigeot if (__drm_mm_hole_node_start(node) < hole_end) { 1965718399fSFrançois Tigeot list_add(&node->hole_stack, &mm->hole_stack); 1975718399fSFrançois Tigeot node->hole_follows = 1; 1985718399fSFrançois Tigeot } 1993f6063ccSDavid Shao } 2003f6063ccSDavid Shao 201ba55f2f5SFrançois Tigeot /** 202ba55f2f5SFrançois Tigeot * drm_mm_reserve_node - insert an pre-initialized node 203ba55f2f5SFrançois Tigeot * @mm: drm_mm allocator to insert @node into 204ba55f2f5SFrançois Tigeot * @node: drm_mm_node to insert 205ba55f2f5SFrançois Tigeot * 206ba55f2f5SFrançois Tigeot * This functions inserts an already set-up drm_mm_node into the allocator, 207ba55f2f5SFrançois Tigeot * meaning that start, size and color must be set by the caller. This is useful 208ba55f2f5SFrançois Tigeot * to initialize the allocator with preallocated objects which must be set-up 209ba55f2f5SFrançois Tigeot * before the range allocator can be set-up, e.g. when taking over a firmware 210ba55f2f5SFrançois Tigeot * framebuffer. 211ba55f2f5SFrançois Tigeot * 212ba55f2f5SFrançois Tigeot * Returns: 213ba55f2f5SFrançois Tigeot * 0 on success, -ENOSPC if there's no hole where @node is. 214ba55f2f5SFrançois Tigeot */ 2159edbd4a0SFrançois Tigeot int drm_mm_reserve_node(struct drm_mm *mm, struct drm_mm_node *node) 216b6fbc077SFrançois Tigeot { 2179edbd4a0SFrançois Tigeot struct drm_mm_node *hole; 218*f77dbd6cSFrançois Tigeot u64 end = node->start + node->size; 219*f77dbd6cSFrançois Tigeot u64 hole_start; 220*f77dbd6cSFrançois Tigeot u64 hole_end; 221b6fbc077SFrançois Tigeot 2229edbd4a0SFrançois Tigeot BUG_ON(node == NULL); 2239edbd4a0SFrançois Tigeot 2249edbd4a0SFrançois Tigeot /* Find the relevant hole to add our node to */ 225b6fbc077SFrançois Tigeot drm_mm_for_each_hole(hole, mm, hole_start, hole_end) { 2269edbd4a0SFrançois Tigeot if (hole_start > node->start || hole_end < end) 227b6fbc077SFrançois Tigeot continue; 228b6fbc077SFrançois Tigeot 229b6fbc077SFrançois Tigeot node->mm = mm; 230b6fbc077SFrançois Tigeot node->allocated = 1; 231b6fbc077SFrançois Tigeot 232b6fbc077SFrançois Tigeot INIT_LIST_HEAD(&node->hole_stack); 233b6fbc077SFrançois Tigeot list_add(&node->node_list, &hole->node_list); 234b6fbc077SFrançois Tigeot 2359edbd4a0SFrançois Tigeot if (node->start == hole_start) { 236b6fbc077SFrançois Tigeot hole->hole_follows = 0; 237b6fbc077SFrançois Tigeot list_del_init(&hole->hole_stack); 238b6fbc077SFrançois Tigeot } 239b6fbc077SFrançois Tigeot 240b6fbc077SFrançois Tigeot node->hole_follows = 0; 241b6fbc077SFrançois Tigeot if (end != hole_end) { 242b6fbc077SFrançois Tigeot list_add(&node->hole_stack, &mm->hole_stack); 243b6fbc077SFrançois Tigeot node->hole_follows = 1; 244b6fbc077SFrançois Tigeot } 245b6fbc077SFrançois Tigeot 2469edbd4a0SFrançois Tigeot return 0; 247b6fbc077SFrançois Tigeot } 248b6fbc077SFrançois Tigeot 2499edbd4a0SFrançois Tigeot return -ENOSPC; 250b6fbc077SFrançois Tigeot } 2519edbd4a0SFrançois Tigeot EXPORT_SYMBOL(drm_mm_reserve_node); 252b6fbc077SFrançois Tigeot 2535718399fSFrançois Tigeot struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *hole_node, 2543f6063ccSDavid Shao unsigned long size, 2553f6063ccSDavid Shao unsigned alignment, 256ea132f0fSFrançois Tigeot unsigned long color, 2573f6063ccSDavid Shao int atomic) 2583f6063ccSDavid Shao { 2595718399fSFrançois Tigeot struct drm_mm_node *node; 2603f6063ccSDavid Shao 2615718399fSFrançois Tigeot node = drm_mm_kmalloc(hole_node->mm, atomic); 2625718399fSFrançois Tigeot if (unlikely(node == NULL)) 2633f6063ccSDavid Shao return NULL; 2643f6063ccSDavid Shao 265ba55f2f5SFrançois Tigeot drm_mm_insert_helper(hole_node, node, size, alignment, color, DRM_MM_CREATE_DEFAULT); 2663f6063ccSDavid Shao 2673f6063ccSDavid Shao return node; 2683f6063ccSDavid Shao } 269ea132f0fSFrançois Tigeot 270ea132f0fSFrançois Tigeot /** 271ba55f2f5SFrançois Tigeot * drm_mm_insert_node_generic - search for space and insert @node 272ba55f2f5SFrançois Tigeot * @mm: drm_mm to allocate from 273ba55f2f5SFrançois Tigeot * @node: preallocate node to insert 274ba55f2f5SFrançois Tigeot * @size: size of the allocation 275ba55f2f5SFrançois Tigeot * @alignment: alignment of the allocation 276ba55f2f5SFrançois Tigeot * @color: opaque tag value to use for this node 277ba55f2f5SFrançois Tigeot * @sflags: flags to fine-tune the allocation search 278ba55f2f5SFrançois Tigeot * @aflags: flags to fine-tune the allocation behavior 279ba55f2f5SFrançois Tigeot * 280ba55f2f5SFrançois Tigeot * The preallocated node must be cleared to 0. 281ba55f2f5SFrançois Tigeot * 282ba55f2f5SFrançois Tigeot * Returns: 283ba55f2f5SFrançois Tigeot * 0 on success, -ENOSPC if there's no suitable hole. 284ea132f0fSFrançois Tigeot */ 285ea132f0fSFrançois Tigeot int drm_mm_insert_node_generic(struct drm_mm *mm, struct drm_mm_node *node, 286*f77dbd6cSFrançois Tigeot u64 size, unsigned alignment, 2879edbd4a0SFrançois Tigeot unsigned long color, 288ba55f2f5SFrançois Tigeot enum drm_mm_search_flags sflags, 289ba55f2f5SFrançois Tigeot enum drm_mm_allocator_flags aflags) 290ea132f0fSFrançois Tigeot { 291ea132f0fSFrançois Tigeot struct drm_mm_node *hole_node; 292ea132f0fSFrançois Tigeot 293ea132f0fSFrançois Tigeot hole_node = drm_mm_search_free_generic(mm, size, alignment, 294ba55f2f5SFrançois Tigeot color, sflags); 295ea132f0fSFrançois Tigeot if (!hole_node) 296ea132f0fSFrançois Tigeot return -ENOSPC; 297ea132f0fSFrançois Tigeot 298ba55f2f5SFrançois Tigeot drm_mm_insert_helper(hole_node, node, size, alignment, color, aflags); 299ea132f0fSFrançois Tigeot return 0; 300ea132f0fSFrançois Tigeot } 301ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_insert_node_generic); 3023f6063ccSDavid Shao 3035718399fSFrançois Tigeot static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node, 3045718399fSFrançois Tigeot struct drm_mm_node *node, 305*f77dbd6cSFrançois Tigeot u64 size, unsigned alignment, 306ea132f0fSFrançois Tigeot unsigned long color, 307*f77dbd6cSFrançois Tigeot u64 start, u64 end, 308ba55f2f5SFrançois Tigeot enum drm_mm_allocator_flags flags) 3095718399fSFrançois Tigeot { 3105718399fSFrançois Tigeot struct drm_mm *mm = hole_node->mm; 311*f77dbd6cSFrançois Tigeot u64 hole_start = drm_mm_hole_node_start(hole_node); 312*f77dbd6cSFrançois Tigeot u64 hole_end = drm_mm_hole_node_end(hole_node); 313*f77dbd6cSFrançois Tigeot u64 adj_start = hole_start; 314*f77dbd6cSFrançois Tigeot u64 adj_end = hole_end; 3155718399fSFrançois Tigeot 316ea132f0fSFrançois Tigeot BUG_ON(!hole_node->hole_follows || node->allocated); 3175718399fSFrançois Tigeot 318ea132f0fSFrançois Tigeot if (adj_start < start) 319ea132f0fSFrançois Tigeot adj_start = start; 320ea132f0fSFrançois Tigeot if (adj_end > end) 321ea132f0fSFrançois Tigeot adj_end = end; 3225718399fSFrançois Tigeot 323ea132f0fSFrançois Tigeot if (mm->color_adjust) 324ea132f0fSFrançois Tigeot mm->color_adjust(hole_node, color, &adj_start, &adj_end); 325ea132f0fSFrançois Tigeot 326352ff8bdSFrançois Tigeot if (flags & DRM_MM_CREATE_TOP) 327352ff8bdSFrançois Tigeot adj_start = adj_end - size; 328352ff8bdSFrançois Tigeot 329ea132f0fSFrançois Tigeot if (alignment) { 330*f77dbd6cSFrançois Tigeot u64 tmp = adj_start; 331*f77dbd6cSFrançois Tigeot unsigned rem; 332*f77dbd6cSFrançois Tigeot 333*f77dbd6cSFrançois Tigeot rem = do_div(tmp, alignment); 334*f77dbd6cSFrançois Tigeot if (rem) { 335ba55f2f5SFrançois Tigeot if (flags & DRM_MM_CREATE_TOP) 336*f77dbd6cSFrançois Tigeot adj_start -= rem; 337ba55f2f5SFrançois Tigeot else 338*f77dbd6cSFrançois Tigeot adj_start += alignment - rem; 3395718399fSFrançois Tigeot } 340ba55f2f5SFrançois Tigeot } 3415718399fSFrançois Tigeot 342ea132f0fSFrançois Tigeot if (adj_start == hole_start) { 343ea132f0fSFrançois Tigeot hole_node->hole_follows = 0; 344ea132f0fSFrançois Tigeot list_del(&hole_node->hole_stack); 345ea132f0fSFrançois Tigeot } 346ea132f0fSFrançois Tigeot 347ea132f0fSFrançois Tigeot node->start = adj_start; 3485718399fSFrançois Tigeot node->size = size; 3495718399fSFrançois Tigeot node->mm = mm; 350ea132f0fSFrançois Tigeot node->color = color; 3515718399fSFrançois Tigeot node->allocated = 1; 3525718399fSFrançois Tigeot 3535718399fSFrançois Tigeot INIT_LIST_HEAD(&node->hole_stack); 3545718399fSFrançois Tigeot list_add(&node->node_list, &hole_node->node_list); 3555718399fSFrançois Tigeot 356ba55f2f5SFrançois Tigeot BUG_ON(node->start < start); 357ba55f2f5SFrançois Tigeot BUG_ON(node->start < adj_start); 358ea132f0fSFrançois Tigeot BUG_ON(node->start + node->size > adj_end); 359ea132f0fSFrançois Tigeot BUG_ON(node->start + node->size > end); 3605718399fSFrançois Tigeot 361ea132f0fSFrançois Tigeot node->hole_follows = 0; 362b6fbc077SFrançois Tigeot if (__drm_mm_hole_node_start(node) < hole_end) { 3635718399fSFrançois Tigeot list_add(&node->hole_stack, &mm->hole_stack); 3645718399fSFrançois Tigeot node->hole_follows = 1; 3655718399fSFrançois Tigeot } 3665718399fSFrançois Tigeot } 3675718399fSFrançois Tigeot 368ea132f0fSFrançois Tigeot /** 369ba55f2f5SFrançois Tigeot * drm_mm_insert_node_in_range_generic - ranged search for space and insert @node 370ba55f2f5SFrançois Tigeot * @mm: drm_mm to allocate from 371ba55f2f5SFrançois Tigeot * @node: preallocate node to insert 372ba55f2f5SFrançois Tigeot * @size: size of the allocation 373ba55f2f5SFrançois Tigeot * @alignment: alignment of the allocation 374ba55f2f5SFrançois Tigeot * @color: opaque tag value to use for this node 375ba55f2f5SFrançois Tigeot * @start: start of the allowed range for this node 376ba55f2f5SFrançois Tigeot * @end: end of the allowed range for this node 377ba55f2f5SFrançois Tigeot * @sflags: flags to fine-tune the allocation search 378ba55f2f5SFrançois Tigeot * @aflags: flags to fine-tune the allocation behavior 379ba55f2f5SFrançois Tigeot * 380ba55f2f5SFrançois Tigeot * The preallocated node must be cleared to 0. 381ba55f2f5SFrançois Tigeot * 382ba55f2f5SFrançois Tigeot * Returns: 383ba55f2f5SFrançois Tigeot * 0 on success, -ENOSPC if there's no suitable hole. 384ea132f0fSFrançois Tigeot */ 385ea132f0fSFrançois Tigeot int drm_mm_insert_node_in_range_generic(struct drm_mm *mm, struct drm_mm_node *node, 386*f77dbd6cSFrançois Tigeot u64 size, unsigned alignment, 387ba55f2f5SFrançois Tigeot unsigned long color, 388*f77dbd6cSFrançois Tigeot u64 start, u64 end, 389ba55f2f5SFrançois Tigeot enum drm_mm_search_flags sflags, 390ba55f2f5SFrançois Tigeot enum drm_mm_allocator_flags aflags) 391ea132f0fSFrançois Tigeot { 392ea132f0fSFrançois Tigeot struct drm_mm_node *hole_node; 393ea132f0fSFrançois Tigeot 394ea132f0fSFrançois Tigeot hole_node = drm_mm_search_free_in_range_generic(mm, 395ea132f0fSFrançois Tigeot size, alignment, color, 396ba55f2f5SFrançois Tigeot start, end, sflags); 397ea132f0fSFrançois Tigeot if (!hole_node) 398ea132f0fSFrançois Tigeot return -ENOSPC; 399ea132f0fSFrançois Tigeot 400ea132f0fSFrançois Tigeot drm_mm_insert_helper_range(hole_node, node, 401ea132f0fSFrançois Tigeot size, alignment, color, 402ba55f2f5SFrançois Tigeot start, end, aflags); 403ea132f0fSFrançois Tigeot return 0; 404ea132f0fSFrançois Tigeot } 405ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic); 4065718399fSFrançois Tigeot 407ea132f0fSFrançois Tigeot /** 408ba55f2f5SFrançois Tigeot * drm_mm_remove_node - Remove a memory node from the allocator. 409ba55f2f5SFrançois Tigeot * @node: drm_mm_node to remove 410ba55f2f5SFrançois Tigeot * 411ba55f2f5SFrançois Tigeot * This just removes a node from its drm_mm allocator. The node does not need to 412ba55f2f5SFrançois Tigeot * be cleared again before it can be re-inserted into this or any other drm_mm 413ba55f2f5SFrançois Tigeot * allocator. It is a bug to call this function on a un-allocated node. 414ea132f0fSFrançois Tigeot */ 4155718399fSFrançois Tigeot void drm_mm_remove_node(struct drm_mm_node *node) 4165718399fSFrançois Tigeot { 4175718399fSFrançois Tigeot struct drm_mm *mm = node->mm; 4185718399fSFrançois Tigeot struct drm_mm_node *prev_node; 4195718399fSFrançois Tigeot 4209edbd4a0SFrançois Tigeot if (WARN_ON(!node->allocated)) 4219edbd4a0SFrançois Tigeot return; 4229edbd4a0SFrançois Tigeot 423ea132f0fSFrançois Tigeot BUG_ON(node->scanned_block || node->scanned_prev_free 424ea132f0fSFrançois Tigeot || node->scanned_next_free); 4255718399fSFrançois Tigeot 4265718399fSFrançois Tigeot prev_node = 4275718399fSFrançois Tigeot list_entry(node->node_list.prev, struct drm_mm_node, node_list); 4285718399fSFrançois Tigeot 4295718399fSFrançois Tigeot if (node->hole_follows) { 430b6fbc077SFrançois Tigeot BUG_ON(__drm_mm_hole_node_start(node) == 431b6fbc077SFrançois Tigeot __drm_mm_hole_node_end(node)); 4325718399fSFrançois Tigeot list_del(&node->hole_stack); 4335718399fSFrançois Tigeot } else 434b6fbc077SFrançois Tigeot BUG_ON(__drm_mm_hole_node_start(node) != 435b6fbc077SFrançois Tigeot __drm_mm_hole_node_end(node)); 436b6fbc077SFrançois Tigeot 4375718399fSFrançois Tigeot 4385718399fSFrançois Tigeot if (!prev_node->hole_follows) { 4395718399fSFrançois Tigeot prev_node->hole_follows = 1; 4405718399fSFrançois Tigeot list_add(&prev_node->hole_stack, &mm->hole_stack); 4415718399fSFrançois Tigeot } else 4425718399fSFrançois Tigeot list_move(&prev_node->hole_stack, &mm->hole_stack); 4435718399fSFrançois Tigeot 4445718399fSFrançois Tigeot list_del(&node->node_list); 4455718399fSFrançois Tigeot node->allocated = 0; 4465718399fSFrançois Tigeot } 447ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_remove_node); 4485718399fSFrançois Tigeot 4493f6063ccSDavid Shao /* 450ea132f0fSFrançois Tigeot * Remove a memory node from the allocator and free the allocated struct 451ea132f0fSFrançois Tigeot * drm_mm_node. Only to be used on a struct drm_mm_node obtained by one of the 452ea132f0fSFrançois Tigeot * drm_mm_get_block functions. 4533f6063ccSDavid Shao */ 4545718399fSFrançois Tigeot void drm_mm_put_block(struct drm_mm_node *node) 4553f6063ccSDavid Shao { 456ea132f0fSFrançois Tigeot 4575718399fSFrançois Tigeot struct drm_mm *mm = node->mm; 4583f6063ccSDavid Shao 4595718399fSFrançois Tigeot drm_mm_remove_node(node); 4603f6063ccSDavid Shao 461ea132f0fSFrançois Tigeot spin_lock(&mm->unused_lock); 4623f6063ccSDavid Shao if (mm->num_unused < MM_UNUSED_TARGET) { 4635718399fSFrançois Tigeot list_add(&node->node_list, &mm->unused_nodes); 4643f6063ccSDavid Shao ++mm->num_unused; 4653f6063ccSDavid Shao } else 466b6fbc077SFrançois Tigeot kfree(node); 467ea132f0fSFrançois Tigeot spin_unlock(&mm->unused_lock); 4683f6063ccSDavid Shao } 4695718399fSFrançois Tigeot 470*f77dbd6cSFrançois Tigeot static int check_free_hole(u64 start, u64 end, u64 size, unsigned alignment) 4715718399fSFrançois Tigeot { 4725718399fSFrançois Tigeot if (end - start < size) 4735718399fSFrançois Tigeot return 0; 4745718399fSFrançois Tigeot 4755718399fSFrançois Tigeot if (alignment) { 476*f77dbd6cSFrançois Tigeot u64 tmp = start; 477*f77dbd6cSFrançois Tigeot unsigned rem; 478*f77dbd6cSFrançois Tigeot 479*f77dbd6cSFrançois Tigeot rem = do_div(tmp, alignment); 480*f77dbd6cSFrançois Tigeot if (rem) 481*f77dbd6cSFrançois Tigeot start += alignment - rem; 4823f6063ccSDavid Shao } 4835718399fSFrançois Tigeot 484ea132f0fSFrançois Tigeot return end >= start + size; 4853f6063ccSDavid Shao } 4865718399fSFrançois Tigeot 487ea132f0fSFrançois Tigeot struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm, 488*f77dbd6cSFrançois Tigeot u64 size, 4895718399fSFrançois Tigeot unsigned alignment, 490ea132f0fSFrançois Tigeot unsigned long color, 4919edbd4a0SFrançois Tigeot enum drm_mm_search_flags flags) 4925718399fSFrançois Tigeot { 4935718399fSFrançois Tigeot struct drm_mm_node *entry; 4945718399fSFrançois Tigeot struct drm_mm_node *best; 495*f77dbd6cSFrançois Tigeot u64 adj_start; 496*f77dbd6cSFrançois Tigeot u64 adj_end; 497*f77dbd6cSFrançois Tigeot u64 best_size; 4985718399fSFrançois Tigeot 499ea132f0fSFrançois Tigeot BUG_ON(mm->scanned_blocks); 5005718399fSFrançois Tigeot 5015718399fSFrançois Tigeot best = NULL; 5025718399fSFrançois Tigeot best_size = ~0UL; 5035718399fSFrançois Tigeot 504ba55f2f5SFrançois Tigeot __drm_mm_for_each_hole(entry, mm, adj_start, adj_end, 505ba55f2f5SFrançois Tigeot flags & DRM_MM_SEARCH_BELOW) { 506*f77dbd6cSFrançois Tigeot u64 hole_size = adj_end - adj_start; 507ba55f2f5SFrançois Tigeot 508ea132f0fSFrançois Tigeot if (mm->color_adjust) { 509ea132f0fSFrançois Tigeot mm->color_adjust(entry, color, &adj_start, &adj_end); 510ea132f0fSFrançois Tigeot if (adj_end <= adj_start) 511ea132f0fSFrançois Tigeot continue; 512ea132f0fSFrançois Tigeot } 513ea132f0fSFrançois Tigeot 5145718399fSFrançois Tigeot if (!check_free_hole(adj_start, adj_end, size, alignment)) 5155718399fSFrançois Tigeot continue; 5165718399fSFrançois Tigeot 5179edbd4a0SFrançois Tigeot if (!(flags & DRM_MM_SEARCH_BEST)) 5185718399fSFrançois Tigeot return entry; 5195718399fSFrançois Tigeot 520ba55f2f5SFrançois Tigeot if (hole_size < best_size) { 5215718399fSFrançois Tigeot best = entry; 522ba55f2f5SFrançois Tigeot best_size = hole_size; 5235718399fSFrançois Tigeot } 5245718399fSFrançois Tigeot } 5255718399fSFrançois Tigeot 5265718399fSFrançois Tigeot return best; 5275718399fSFrançois Tigeot } 5285718399fSFrançois Tigeot 529ea132f0fSFrançois Tigeot struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm, 530*f77dbd6cSFrançois Tigeot u64 size, 531ea132f0fSFrançois Tigeot unsigned alignment, 532ea132f0fSFrançois Tigeot unsigned long color, 533*f77dbd6cSFrançois Tigeot u64 start, 534*f77dbd6cSFrançois Tigeot u64 end, 5359edbd4a0SFrançois Tigeot enum drm_mm_search_flags flags) 536ea132f0fSFrançois Tigeot { 537ea132f0fSFrançois Tigeot struct drm_mm_node *entry; 538ea132f0fSFrançois Tigeot struct drm_mm_node *best; 539*f77dbd6cSFrançois Tigeot u64 adj_start; 540*f77dbd6cSFrançois Tigeot u64 adj_end; 541*f77dbd6cSFrançois Tigeot u64 best_size; 542ea132f0fSFrançois Tigeot 543ea132f0fSFrançois Tigeot BUG_ON(mm->scanned_blocks); 544ea132f0fSFrançois Tigeot 545ea132f0fSFrançois Tigeot best = NULL; 546ea132f0fSFrançois Tigeot best_size = ~0UL; 547ea132f0fSFrançois Tigeot 548ba55f2f5SFrançois Tigeot __drm_mm_for_each_hole(entry, mm, adj_start, adj_end, 549ba55f2f5SFrançois Tigeot flags & DRM_MM_SEARCH_BELOW) { 550*f77dbd6cSFrançois Tigeot u64 hole_size = adj_end - adj_start; 551ba55f2f5SFrançois Tigeot 552b6fbc077SFrançois Tigeot if (adj_start < start) 553b6fbc077SFrançois Tigeot adj_start = start; 554b6fbc077SFrançois Tigeot if (adj_end > end) 555b6fbc077SFrançois Tigeot adj_end = end; 556ea132f0fSFrançois Tigeot 557ea132f0fSFrançois Tigeot if (mm->color_adjust) { 558ea132f0fSFrançois Tigeot mm->color_adjust(entry, color, &adj_start, &adj_end); 559ea132f0fSFrançois Tigeot if (adj_end <= adj_start) 560ea132f0fSFrançois Tigeot continue; 561ea132f0fSFrançois Tigeot } 562ea132f0fSFrançois Tigeot 563ea132f0fSFrançois Tigeot if (!check_free_hole(adj_start, adj_end, size, alignment)) 564ea132f0fSFrançois Tigeot continue; 565ea132f0fSFrançois Tigeot 5669edbd4a0SFrançois Tigeot if (!(flags & DRM_MM_SEARCH_BEST)) 567ea132f0fSFrançois Tigeot return entry; 568ea132f0fSFrançois Tigeot 569ba55f2f5SFrançois Tigeot if (hole_size < best_size) { 570ea132f0fSFrançois Tigeot best = entry; 571ba55f2f5SFrançois Tigeot best_size = hole_size; 572ea132f0fSFrançois Tigeot } 573ea132f0fSFrançois Tigeot } 574ea132f0fSFrançois Tigeot 575ea132f0fSFrançois Tigeot return best; 576ea132f0fSFrançois Tigeot } 577ea132f0fSFrançois Tigeot 578ea132f0fSFrançois Tigeot /** 579ba55f2f5SFrançois Tigeot * drm_mm_replace_node - move an allocation from @old to @new 580ba55f2f5SFrançois Tigeot * @old: drm_mm_node to remove from the allocator 581ba55f2f5SFrançois Tigeot * @new: drm_mm_node which should inherit @old's allocation 582ba55f2f5SFrançois Tigeot * 583ba55f2f5SFrançois Tigeot * This is useful for when drivers embed the drm_mm_node structure and hence 584ba55f2f5SFrançois Tigeot * can't move allocations by reassigning pointers. It's a combination of remove 585ba55f2f5SFrançois Tigeot * and insert with the guarantee that the allocation start will match. 586ea132f0fSFrançois Tigeot */ 5875718399fSFrançois Tigeot void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new) 5885718399fSFrançois Tigeot { 5895718399fSFrançois Tigeot list_replace(&old->node_list, &new->node_list); 5905718399fSFrançois Tigeot list_replace(&old->hole_stack, &new->hole_stack); 5915718399fSFrançois Tigeot new->hole_follows = old->hole_follows; 5925718399fSFrançois Tigeot new->mm = old->mm; 5935718399fSFrançois Tigeot new->start = old->start; 5945718399fSFrançois Tigeot new->size = old->size; 595ea132f0fSFrançois Tigeot new->color = old->color; 5965718399fSFrançois Tigeot 5975718399fSFrançois Tigeot old->allocated = 0; 5985718399fSFrançois Tigeot new->allocated = 1; 5995718399fSFrançois Tigeot } 600ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_replace_node); 6015718399fSFrançois Tigeot 602ea132f0fSFrançois Tigeot /** 603ba55f2f5SFrançois Tigeot * DOC: lru scan roaster 604ba55f2f5SFrançois Tigeot * 605ba55f2f5SFrançois Tigeot * Very often GPUs need to have continuous allocations for a given object. When 606ba55f2f5SFrançois Tigeot * evicting objects to make space for a new one it is therefore not most 607ba55f2f5SFrançois Tigeot * efficient when we simply start to select all objects from the tail of an LRU 608ba55f2f5SFrançois Tigeot * until there's a suitable hole: Especially for big objects or nodes that 609ba55f2f5SFrançois Tigeot * otherwise have special allocation constraints there's a good chance we evict 610ba55f2f5SFrançois Tigeot * lots of (smaller) objects unecessarily. 611ba55f2f5SFrançois Tigeot * 612ba55f2f5SFrançois Tigeot * The DRM range allocator supports this use-case through the scanning 613ba55f2f5SFrançois Tigeot * interfaces. First a scan operation needs to be initialized with 614ba55f2f5SFrançois Tigeot * drm_mm_init_scan() or drm_mm_init_scan_with_range(). The the driver adds 615ba55f2f5SFrançois Tigeot * objects to the roaster (probably by walking an LRU list, but this can be 616ba55f2f5SFrançois Tigeot * freely implemented) until a suitable hole is found or there's no further 617ba55f2f5SFrançois Tigeot * evitable object. 618ba55f2f5SFrançois Tigeot * 619ba55f2f5SFrançois Tigeot * The the driver must walk through all objects again in exactly the reverse 620ba55f2f5SFrançois Tigeot * order to restore the allocator state. Note that while the allocator is used 621ba55f2f5SFrançois Tigeot * in the scan mode no other operation is allowed. 622ba55f2f5SFrançois Tigeot * 623ba55f2f5SFrançois Tigeot * Finally the driver evicts all objects selected in the scan. Adding and 624ba55f2f5SFrançois Tigeot * removing an object is O(1), and since freeing a node is also O(1) the overall 625ba55f2f5SFrançois Tigeot * complexity is O(scanned_objects). So like the free stack which needs to be 626ba55f2f5SFrançois Tigeot * walked before a scan operation even begins this is linear in the number of 627ba55f2f5SFrançois Tigeot * objects. It doesn't seem to hurt badly. 628ba55f2f5SFrançois Tigeot */ 629ba55f2f5SFrançois Tigeot 630ba55f2f5SFrançois Tigeot /** 631ba55f2f5SFrançois Tigeot * drm_mm_init_scan - initialize lru scanning 632ba55f2f5SFrançois Tigeot * @mm: drm_mm to scan 633ba55f2f5SFrançois Tigeot * @size: size of the allocation 634ba55f2f5SFrançois Tigeot * @alignment: alignment of the allocation 635ba55f2f5SFrançois Tigeot * @color: opaque tag value to use for the allocation 636ea132f0fSFrançois Tigeot * 637ea132f0fSFrançois Tigeot * This simply sets up the scanning routines with the parameters for the desired 638ba55f2f5SFrançois Tigeot * hole. Note that there's no need to specify allocation flags, since they only 639ba55f2f5SFrançois Tigeot * change the place a node is allocated from within a suitable hole. 640ea132f0fSFrançois Tigeot * 641ba55f2f5SFrançois Tigeot * Warning: 642ba55f2f5SFrançois Tigeot * As long as the scan list is non-empty, no other operations than 643ea132f0fSFrançois Tigeot * adding/removing nodes to/from the scan list are allowed. 644ea132f0fSFrançois Tigeot */ 645ea132f0fSFrançois Tigeot void drm_mm_init_scan(struct drm_mm *mm, 646*f77dbd6cSFrançois Tigeot u64 size, 647ea132f0fSFrançois Tigeot unsigned alignment, 648ea132f0fSFrançois Tigeot unsigned long color) 6495718399fSFrançois Tigeot { 650ea132f0fSFrançois Tigeot mm->scan_color = color; 6515718399fSFrançois Tigeot mm->scan_alignment = alignment; 6525718399fSFrançois Tigeot mm->scan_size = size; 6535718399fSFrançois Tigeot mm->scanned_blocks = 0; 6545718399fSFrançois Tigeot mm->scan_hit_start = 0; 655ea132f0fSFrançois Tigeot mm->scan_hit_end = 0; 6565718399fSFrançois Tigeot mm->scan_check_range = 0; 6575718399fSFrançois Tigeot mm->prev_scanned_node = NULL; 6585718399fSFrançois Tigeot } 659ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_init_scan); 6605718399fSFrançois Tigeot 661ea132f0fSFrançois Tigeot /** 662ba55f2f5SFrançois Tigeot * drm_mm_init_scan - initialize range-restricted lru scanning 663ba55f2f5SFrançois Tigeot * @mm: drm_mm to scan 664ba55f2f5SFrançois Tigeot * @size: size of the allocation 665ba55f2f5SFrançois Tigeot * @alignment: alignment of the allocation 666ba55f2f5SFrançois Tigeot * @color: opaque tag value to use for the allocation 667ba55f2f5SFrançois Tigeot * @start: start of the allowed range for the allocation 668ba55f2f5SFrançois Tigeot * @end: end of the allowed range for the allocation 669ea132f0fSFrançois Tigeot * 670ea132f0fSFrançois Tigeot * This simply sets up the scanning routines with the parameters for the desired 671ba55f2f5SFrançois Tigeot * hole. Note that there's no need to specify allocation flags, since they only 672ba55f2f5SFrançois Tigeot * change the place a node is allocated from within a suitable hole. 673ea132f0fSFrançois Tigeot * 674ba55f2f5SFrançois Tigeot * Warning: 675ba55f2f5SFrançois Tigeot * As long as the scan list is non-empty, no other operations than 676ea132f0fSFrançois Tigeot * adding/removing nodes to/from the scan list are allowed. 677ea132f0fSFrançois Tigeot */ 678ea132f0fSFrançois Tigeot void drm_mm_init_scan_with_range(struct drm_mm *mm, 679*f77dbd6cSFrançois Tigeot u64 size, 6805718399fSFrançois Tigeot unsigned alignment, 681ea132f0fSFrançois Tigeot unsigned long color, 682*f77dbd6cSFrançois Tigeot u64 start, 683*f77dbd6cSFrançois Tigeot u64 end) 6845718399fSFrançois Tigeot { 685ea132f0fSFrançois Tigeot mm->scan_color = color; 6865718399fSFrançois Tigeot mm->scan_alignment = alignment; 6875718399fSFrançois Tigeot mm->scan_size = size; 6885718399fSFrançois Tigeot mm->scanned_blocks = 0; 6895718399fSFrançois Tigeot mm->scan_hit_start = 0; 690ea132f0fSFrançois Tigeot mm->scan_hit_end = 0; 6915718399fSFrançois Tigeot mm->scan_start = start; 6925718399fSFrançois Tigeot mm->scan_end = end; 6935718399fSFrançois Tigeot mm->scan_check_range = 1; 6945718399fSFrançois Tigeot mm->prev_scanned_node = NULL; 6955718399fSFrançois Tigeot } 696ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_init_scan_with_range); 6975718399fSFrançois Tigeot 698ea132f0fSFrançois Tigeot /** 699ba55f2f5SFrançois Tigeot * drm_mm_scan_add_block - add a node to the scan list 700ba55f2f5SFrançois Tigeot * @node: drm_mm_node to add 701ba55f2f5SFrançois Tigeot * 702ea132f0fSFrançois Tigeot * Add a node to the scan list that might be freed to make space for the desired 703ea132f0fSFrançois Tigeot * hole. 704ea132f0fSFrançois Tigeot * 705ba55f2f5SFrançois Tigeot * Returns: 706ba55f2f5SFrançois Tigeot * True if a hole has been found, false otherwise. 707ea132f0fSFrançois Tigeot */ 708ba55f2f5SFrançois Tigeot bool drm_mm_scan_add_block(struct drm_mm_node *node) 7095718399fSFrançois Tigeot { 7105718399fSFrançois Tigeot struct drm_mm *mm = node->mm; 7115718399fSFrançois Tigeot struct drm_mm_node *prev_node; 712*f77dbd6cSFrançois Tigeot u64 hole_start, hole_end; 713*f77dbd6cSFrançois Tigeot u64 adj_start, adj_end; 7145718399fSFrançois Tigeot 7155718399fSFrançois Tigeot mm->scanned_blocks++; 7165718399fSFrançois Tigeot 717ea132f0fSFrançois Tigeot BUG_ON(node->scanned_block); 7185718399fSFrançois Tigeot node->scanned_block = 1; 7195718399fSFrançois Tigeot 7205718399fSFrançois Tigeot prev_node = list_entry(node->node_list.prev, struct drm_mm_node, 7215718399fSFrançois Tigeot node_list); 7225718399fSFrançois Tigeot 7235718399fSFrançois Tigeot node->scanned_preceeds_hole = prev_node->hole_follows; 7245718399fSFrançois Tigeot prev_node->hole_follows = 1; 7255718399fSFrançois Tigeot list_del(&node->node_list); 7265718399fSFrançois Tigeot node->node_list.prev = &prev_node->node_list; 7275718399fSFrançois Tigeot node->node_list.next = &mm->prev_scanned_node->node_list; 7285718399fSFrançois Tigeot mm->prev_scanned_node = node; 7295718399fSFrançois Tigeot 730ea132f0fSFrançois Tigeot adj_start = hole_start = drm_mm_hole_node_start(prev_node); 731ea132f0fSFrançois Tigeot adj_end = hole_end = drm_mm_hole_node_end(prev_node); 732ea132f0fSFrançois Tigeot 7335718399fSFrançois Tigeot if (mm->scan_check_range) { 734ea132f0fSFrançois Tigeot if (adj_start < mm->scan_start) 735ea132f0fSFrançois Tigeot adj_start = mm->scan_start; 736ea132f0fSFrançois Tigeot if (adj_end > mm->scan_end) 737ea132f0fSFrançois Tigeot adj_end = mm->scan_end; 7385718399fSFrançois Tigeot } 7395718399fSFrançois Tigeot 740ea132f0fSFrançois Tigeot if (mm->color_adjust) 741ea132f0fSFrançois Tigeot mm->color_adjust(prev_node, mm->scan_color, 742ea132f0fSFrançois Tigeot &adj_start, &adj_end); 743ea132f0fSFrançois Tigeot 7445718399fSFrançois Tigeot if (check_free_hole(adj_start, adj_end, 7455718399fSFrançois Tigeot mm->scan_size, mm->scan_alignment)) { 7465718399fSFrançois Tigeot mm->scan_hit_start = hole_start; 747ea132f0fSFrançois Tigeot mm->scan_hit_end = hole_end; 748ba55f2f5SFrançois Tigeot return true; 7495718399fSFrançois Tigeot } 7505718399fSFrançois Tigeot 751ba55f2f5SFrançois Tigeot return false; 7525718399fSFrançois Tigeot } 753ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_scan_add_block); 7545718399fSFrançois Tigeot 755ea132f0fSFrançois Tigeot /** 756ba55f2f5SFrançois Tigeot * drm_mm_scan_remove_block - remove a node from the scan list 757ba55f2f5SFrançois Tigeot * @node: drm_mm_node to remove 758ea132f0fSFrançois Tigeot * 759ea132f0fSFrançois Tigeot * Nodes _must_ be removed in the exact same order from the scan list as they 760ea132f0fSFrançois Tigeot * have been added, otherwise the internal state of the memory manager will be 761ea132f0fSFrançois Tigeot * corrupted. 762ea132f0fSFrançois Tigeot * 763ea132f0fSFrançois Tigeot * When the scan list is empty, the selected memory nodes can be freed. An 7649edbd4a0SFrançois Tigeot * immediately following drm_mm_search_free with !DRM_MM_SEARCH_BEST will then 7659edbd4a0SFrançois Tigeot * return the just freed block (because its at the top of the free_stack list). 766ea132f0fSFrançois Tigeot * 767ba55f2f5SFrançois Tigeot * Returns: 768ba55f2f5SFrançois Tigeot * True if this block should be evicted, false otherwise. Will always 769ba55f2f5SFrançois Tigeot * return false when no hole has been found. 770ea132f0fSFrançois Tigeot */ 771ba55f2f5SFrançois Tigeot bool drm_mm_scan_remove_block(struct drm_mm_node *node) 7725718399fSFrançois Tigeot { 7735718399fSFrançois Tigeot struct drm_mm *mm = node->mm; 7745718399fSFrançois Tigeot struct drm_mm_node *prev_node; 7755718399fSFrançois Tigeot 7765718399fSFrançois Tigeot mm->scanned_blocks--; 7775718399fSFrançois Tigeot 778ea132f0fSFrançois Tigeot BUG_ON(!node->scanned_block); 7795718399fSFrançois Tigeot node->scanned_block = 0; 7805718399fSFrançois Tigeot 7815718399fSFrançois Tigeot prev_node = list_entry(node->node_list.prev, struct drm_mm_node, 7825718399fSFrançois Tigeot node_list); 7835718399fSFrançois Tigeot 7845718399fSFrançois Tigeot prev_node->hole_follows = node->scanned_preceeds_hole; 7855718399fSFrançois Tigeot list_add(&node->node_list, &prev_node->node_list); 7865718399fSFrançois Tigeot 787ea132f0fSFrançois Tigeot return (drm_mm_hole_node_end(node) > mm->scan_hit_start && 788ea132f0fSFrançois Tigeot node->start < mm->scan_hit_end); 7895718399fSFrançois Tigeot } 790ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_scan_remove_block); 7915718399fSFrançois Tigeot 792ba55f2f5SFrançois Tigeot /** 793ba55f2f5SFrançois Tigeot * drm_mm_clean - checks whether an allocator is clean 794ba55f2f5SFrançois Tigeot * @mm: drm_mm allocator to check 795ba55f2f5SFrançois Tigeot * 796ba55f2f5SFrançois Tigeot * Returns: 797ba55f2f5SFrançois Tigeot * True if the allocator is completely free, false if there's still a node 798ba55f2f5SFrançois Tigeot * allocated in it. 799ba55f2f5SFrançois Tigeot */ 800ba55f2f5SFrançois Tigeot bool drm_mm_clean(struct drm_mm * mm) 8013f6063ccSDavid Shao { 8025718399fSFrançois Tigeot struct list_head *head = &mm->head_node.node_list; 8033f6063ccSDavid Shao 8043f6063ccSDavid Shao return (head->next->next == head); 8053f6063ccSDavid Shao } 806ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_clean); 8073f6063ccSDavid Shao 808ba55f2f5SFrançois Tigeot /** 809ba55f2f5SFrançois Tigeot * drm_mm_init - initialize a drm-mm allocator 810ba55f2f5SFrançois Tigeot * @mm: the drm_mm structure to initialize 811ba55f2f5SFrançois Tigeot * @start: start of the range managed by @mm 812ba55f2f5SFrançois Tigeot * @size: end of the range managed by @mm 813ba55f2f5SFrançois Tigeot * 814ba55f2f5SFrançois Tigeot * Note that @mm must be cleared to 0 before calling this function. 815ba55f2f5SFrançois Tigeot */ 816*f77dbd6cSFrançois Tigeot void drm_mm_init(struct drm_mm * mm, u64 start, u64 size) 8173f6063ccSDavid Shao { 8185718399fSFrançois Tigeot INIT_LIST_HEAD(&mm->hole_stack); 81921d4e127Szrj INIT_LIST_HEAD(&mm->unused_nodes); 82021d4e127Szrj mm->num_unused = 0; 8215718399fSFrançois Tigeot mm->scanned_blocks = 0; 8223f6063ccSDavid Shao 823ea132f0fSFrançois Tigeot /* Clever trick to avoid a special case in the free hole tracking. */ 8245718399fSFrançois Tigeot INIT_LIST_HEAD(&mm->head_node.node_list); 8255718399fSFrançois Tigeot INIT_LIST_HEAD(&mm->head_node.hole_stack); 8265718399fSFrançois Tigeot mm->head_node.hole_follows = 1; 8275718399fSFrançois Tigeot mm->head_node.scanned_block = 0; 8285718399fSFrançois Tigeot mm->head_node.scanned_prev_free = 0; 8295718399fSFrançois Tigeot mm->head_node.scanned_next_free = 0; 8305718399fSFrançois Tigeot mm->head_node.mm = mm; 8315718399fSFrançois Tigeot mm->head_node.start = start + size; 8325718399fSFrançois Tigeot mm->head_node.size = start - mm->head_node.start; 8335718399fSFrançois Tigeot list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack); 8345718399fSFrançois Tigeot 835ea132f0fSFrançois Tigeot mm->color_adjust = NULL; 8363f6063ccSDavid Shao } 837ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_init); 8383f6063ccSDavid Shao 839ba55f2f5SFrançois Tigeot /** 840ba55f2f5SFrançois Tigeot * drm_mm_takedown - clean up a drm_mm allocator 841ba55f2f5SFrançois Tigeot * @mm: drm_mm allocator to clean up 842ba55f2f5SFrançois Tigeot * 843ba55f2f5SFrançois Tigeot * Note that it is a bug to call this function on an allocator which is not 844ba55f2f5SFrançois Tigeot * clean. 845ba55f2f5SFrançois Tigeot */ 8463f6063ccSDavid Shao void drm_mm_takedown(struct drm_mm * mm) 8473f6063ccSDavid Shao { 848ba55f2f5SFrançois Tigeot WARN(!list_empty(&mm->head_node.node_list), 849ba55f2f5SFrançois Tigeot "Memory manager not clean during takedown.\n"); 8503f6063ccSDavid Shao } 851ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_takedown); 8525718399fSFrançois Tigeot 853*f77dbd6cSFrançois Tigeot static u64 drm_mm_debug_hole(struct drm_mm_node *entry, 854ba55f2f5SFrançois Tigeot const char *prefix) 8555718399fSFrançois Tigeot { 856*f77dbd6cSFrançois Tigeot u64 hole_start, hole_end, hole_size; 8575718399fSFrançois Tigeot 8585718399fSFrançois Tigeot if (entry->hole_follows) { 8595718399fSFrançois Tigeot hole_start = drm_mm_hole_node_start(entry); 8605718399fSFrançois Tigeot hole_end = drm_mm_hole_node_end(entry); 8615718399fSFrançois Tigeot hole_size = hole_end - hole_start; 862*f77dbd6cSFrançois Tigeot pr_debug("%s %#llx-%#llx: %llu: free\n", prefix, hole_start, 863*f77dbd6cSFrançois Tigeot hole_end, hole_size); 864ba55f2f5SFrançois Tigeot return hole_size; 8655718399fSFrançois Tigeot } 866ba55f2f5SFrançois Tigeot 867ba55f2f5SFrançois Tigeot return 0; 868ba55f2f5SFrançois Tigeot } 869ba55f2f5SFrançois Tigeot 870ba55f2f5SFrançois Tigeot /** 871ba55f2f5SFrançois Tigeot * drm_mm_debug_table - dump allocator state to dmesg 872ba55f2f5SFrançois Tigeot * @mm: drm_mm allocator to dump 873ba55f2f5SFrançois Tigeot * @prefix: prefix to use for dumping to dmesg 874ba55f2f5SFrançois Tigeot */ 875ba55f2f5SFrançois Tigeot void drm_mm_debug_table(struct drm_mm *mm, const char *prefix) 876ba55f2f5SFrançois Tigeot { 877ba55f2f5SFrançois Tigeot struct drm_mm_node *entry; 878*f77dbd6cSFrançois Tigeot u64 total_used = 0, total_free = 0, total = 0; 879ba55f2f5SFrançois Tigeot 880ba55f2f5SFrançois Tigeot total_free += drm_mm_debug_hole(&mm->head_node, prefix); 881ba55f2f5SFrançois Tigeot 882ba55f2f5SFrançois Tigeot drm_mm_for_each_node(entry, mm) { 883*f77dbd6cSFrançois Tigeot pr_debug("%s %#llx-%#llx: %llu: used\n", prefix, entry->start, 884*f77dbd6cSFrançois Tigeot entry->start + entry->size, entry->size); 885ba55f2f5SFrançois Tigeot total_used += entry->size; 886ba55f2f5SFrançois Tigeot total_free += drm_mm_debug_hole(entry, prefix); 8875718399fSFrançois Tigeot } 8885718399fSFrançois Tigeot total = total_free + total_used; 8895718399fSFrançois Tigeot 890*f77dbd6cSFrançois Tigeot pr_debug("%s total: %llu, used %llu free %llu\n", prefix, total, 8915718399fSFrançois Tigeot total_used, total_free); 8925718399fSFrançois Tigeot } 893ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_debug_table); 894ea132f0fSFrançois Tigeot 895ea132f0fSFrançois Tigeot #if defined(CONFIG_DEBUG_FS) 896*f77dbd6cSFrançois Tigeot static u64 drm_mm_dump_hole(struct seq_file *m, struct drm_mm_node *entry) 897ea132f0fSFrançois Tigeot { 898*f77dbd6cSFrançois Tigeot u64 hole_start, hole_end, hole_size; 899ea132f0fSFrançois Tigeot 900ea132f0fSFrançois Tigeot if (entry->hole_follows) { 901ea132f0fSFrançois Tigeot hole_start = drm_mm_hole_node_start(entry); 902ea132f0fSFrançois Tigeot hole_end = drm_mm_hole_node_end(entry); 903ea132f0fSFrançois Tigeot hole_size = hole_end - hole_start; 90419c468b4SFrançois Tigeot seq_printf(m, "%#018llx-%#018llx: %llu: free\n", hole_start, 90519c468b4SFrançois Tigeot hole_end, hole_size); 906b6fbc077SFrançois Tigeot return hole_size; 907ea132f0fSFrançois Tigeot } 908b6fbc077SFrançois Tigeot 909b6fbc077SFrançois Tigeot return 0; 910b6fbc077SFrançois Tigeot } 911b6fbc077SFrançois Tigeot 912ba55f2f5SFrançois Tigeot /** 913ba55f2f5SFrançois Tigeot * drm_mm_dump_table - dump allocator state to a seq_file 914ba55f2f5SFrançois Tigeot * @m: seq_file to dump to 915ba55f2f5SFrançois Tigeot * @mm: drm_mm allocator to dump 916ba55f2f5SFrançois Tigeot */ 917b6fbc077SFrançois Tigeot int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm) 918b6fbc077SFrançois Tigeot { 919b6fbc077SFrançois Tigeot struct drm_mm_node *entry; 920*f77dbd6cSFrançois Tigeot u64 total_used = 0, total_free = 0, total = 0; 921b6fbc077SFrançois Tigeot 922b6fbc077SFrançois Tigeot total_free += drm_mm_dump_hole(m, &mm->head_node); 923b6fbc077SFrançois Tigeot 924b6fbc077SFrançois Tigeot drm_mm_for_each_node(entry, mm) { 92519c468b4SFrançois Tigeot seq_printf(m, "%#018llx-%#018llx: %llu: used\n", entry->start, 92619c468b4SFrançois Tigeot entry->start + entry->size, entry->size); 927b6fbc077SFrançois Tigeot total_used += entry->size; 928b6fbc077SFrançois Tigeot total_free += drm_mm_dump_hole(m, entry); 929ea132f0fSFrançois Tigeot } 930ea132f0fSFrançois Tigeot total = total_free + total_used; 931ea132f0fSFrançois Tigeot 932*f77dbd6cSFrançois Tigeot seq_printf(m, "total: %llu, used %llu free %llu\n", total, 933*f77dbd6cSFrançois Tigeot total_used, total_free); 934ea132f0fSFrançois Tigeot return 0; 935ea132f0fSFrançois Tigeot } 936ea132f0fSFrançois Tigeot EXPORT_SYMBOL(drm_mm_dump_table); 937ea132f0fSFrançois Tigeot #endif 938