1203287Srnoland/************************************************************************** 2203287Srnoland * 3203287Srnoland * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA. 4203287Srnoland * All Rights Reserved. 5203287Srnoland * 6203287Srnoland * Permission is hereby granted, free of charge, to any person obtaining a 7203287Srnoland * copy of this software and associated documentation files (the 8203287Srnoland * "Software"), to deal in the Software without restriction, including 9203287Srnoland * without limitation the rights to use, copy, modify, merge, publish, 10203287Srnoland * distribute, sub license, and/or sell copies of the Software, and to 11203287Srnoland * permit persons to whom the Software is furnished to do so, subject to 12203287Srnoland * the following conditions: 13203287Srnoland * 14203287Srnoland * The above copyright notice and this permission notice (including the 15203287Srnoland * next paragraph) shall be included in all copies or substantial portions 16203287Srnoland * of the Software. 17203287Srnoland * 18203287Srnoland * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19203287Srnoland * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20203287Srnoland * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL 21203287Srnoland * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, 22203287Srnoland * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 23203287Srnoland * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE 24203287Srnoland * USE OR OTHER DEALINGS IN THE SOFTWARE. 25203287Srnoland * 26203287Srnoland * 27203287Srnoland **************************************************************************/ 28203287Srnoland 29203287Srnoland#include <sys/cdefs.h> 30203287Srnoland__FBSDID("$FreeBSD$"); 31203287Srnoland 32203287Srnoland/* 33203287Srnoland * Generic simple memory manager implementation. Intended to be used as a base 34203287Srnoland * class implementation for more advanced memory managers. 35203287Srnoland * 36203287Srnoland * Note that the algorithm used is quite simple and there might be substantial 37203287Srnoland * performance gains if a smarter free list is implemented. Currently it is just an 38203287Srnoland * unordered stack of free regions. This could easily be improved if an RB-tree 39203287Srnoland * is used instead. At least if we expect heavy fragmentation. 40203287Srnoland * 41203287Srnoland * Aligned allocations can also see improvement. 42203287Srnoland * 43203287Srnoland * Authors: 44203287Srnoland * Thomas Hellstr��m <thomas-at-tungstengraphics-dot-com> 45203287Srnoland */ 46203287Srnoland 47203287Srnoland#include "dev/drm/drmP.h" 48203287Srnoland#include "dev/drm/drm_mm.h" 49203287Srnoland 50203287Srnoland#define MM_UNUSED_TARGET 4 51203287Srnoland 52203287Srnolandunsigned long drm_mm_tail_space(struct drm_mm *mm) 53203287Srnoland{ 54203287Srnoland struct list_head *tail_node; 55203287Srnoland struct drm_mm_node *entry; 56203287Srnoland 57203287Srnoland tail_node = mm->ml_entry.prev; 58203287Srnoland entry = list_entry(tail_node, struct drm_mm_node, ml_entry); 59203287Srnoland if (!entry->free) 60203287Srnoland return 0; 61203287Srnoland 62203287Srnoland return entry->size; 63203287Srnoland} 64203287Srnoland 65203287Srnolandint drm_mm_remove_space_from_tail(struct drm_mm *mm, unsigned long size) 66203287Srnoland{ 67203287Srnoland struct list_head *tail_node; 68203287Srnoland struct drm_mm_node *entry; 69203287Srnoland 70203287Srnoland tail_node = mm->ml_entry.prev; 71203287Srnoland entry = list_entry(tail_node, struct drm_mm_node, ml_entry); 72203287Srnoland if (!entry->free) 73203287Srnoland return -ENOMEM; 74203287Srnoland 75203287Srnoland if (entry->size <= size) 76203287Srnoland return -ENOMEM; 77203287Srnoland 78203287Srnoland entry->size -= size; 79203287Srnoland return 0; 80203287Srnoland} 81203287Srnoland 82203287Srnolandstatic struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic) 83203287Srnoland{ 84203287Srnoland struct drm_mm_node *child; 85203287Srnoland 86203287Srnoland if (atomic) 87203287Srnoland child = malloc(sizeof(*child), DRM_MEM_MM, M_NOWAIT); 88203287Srnoland else 89203287Srnoland child = malloc(sizeof(*child), DRM_MEM_MM, M_WAITOK); 90203287Srnoland 91203287Srnoland if (unlikely(child == NULL)) { 92203287Srnoland mtx_lock(&mm->unused_lock); 93203287Srnoland if (list_empty(&mm->unused_nodes)) 94203287Srnoland child = NULL; 95203287Srnoland else { 96203287Srnoland child = 97203287Srnoland list_entry(mm->unused_nodes.next, 98203287Srnoland struct drm_mm_node, fl_entry); 99203287Srnoland list_del(&child->fl_entry); 100203287Srnoland --mm->num_unused; 101203287Srnoland } 102203287Srnoland mtx_unlock(&mm->unused_lock); 103203287Srnoland } 104203287Srnoland return child; 105203287Srnoland} 106203287Srnoland 107203287Srnolandint drm_mm_pre_get(struct drm_mm *mm) 108203287Srnoland{ 109203287Srnoland struct drm_mm_node *node; 110203287Srnoland 111203287Srnoland mtx_lock(&mm->unused_lock); 112203287Srnoland while (mm->num_unused < MM_UNUSED_TARGET) { 113203287Srnoland mtx_unlock(&mm->unused_lock); 114203287Srnoland node = malloc(sizeof(*node), DRM_MEM_MM, M_WAITOK); 115203287Srnoland mtx_lock(&mm->unused_lock); 116203287Srnoland 117203287Srnoland if (unlikely(node == NULL)) { 118203287Srnoland int ret = (mm->num_unused < 2) ? -ENOMEM : 0; 119203287Srnoland mtx_unlock(&mm->unused_lock); 120203287Srnoland return ret; 121203287Srnoland } 122203287Srnoland ++mm->num_unused; 123203287Srnoland list_add_tail(&node->fl_entry, &mm->unused_nodes); 124203287Srnoland } 125203287Srnoland mtx_unlock(&mm->unused_lock); 126203287Srnoland return 0; 127203287Srnoland} 128203287Srnoland 129203287Srnolandstatic int drm_mm_create_tail_node(struct drm_mm *mm, 130203287Srnoland unsigned long start, 131203287Srnoland unsigned long size, int atomic) 132203287Srnoland{ 133203287Srnoland struct drm_mm_node *child; 134203287Srnoland 135203287Srnoland child = drm_mm_kmalloc(mm, atomic); 136203287Srnoland if (unlikely(child == NULL)) 137203287Srnoland return -ENOMEM; 138203287Srnoland 139203287Srnoland child->free = 1; 140203287Srnoland child->size = size; 141203287Srnoland child->start = start; 142203287Srnoland child->mm = mm; 143203287Srnoland 144203287Srnoland list_add_tail(&child->ml_entry, &mm->ml_entry); 145203287Srnoland list_add_tail(&child->fl_entry, &mm->fl_entry); 146203287Srnoland 147203287Srnoland return 0; 148203287Srnoland} 149203287Srnoland 150203287Srnolandint drm_mm_add_space_to_tail(struct drm_mm *mm, unsigned long size, int atomic) 151203287Srnoland{ 152203287Srnoland struct list_head *tail_node; 153203287Srnoland struct drm_mm_node *entry; 154203287Srnoland 155203287Srnoland tail_node = mm->ml_entry.prev; 156203287Srnoland entry = list_entry(tail_node, struct drm_mm_node, ml_entry); 157203287Srnoland if (!entry->free) { 158203287Srnoland return drm_mm_create_tail_node(mm, entry->start + entry->size, 159203287Srnoland size, atomic); 160203287Srnoland } 161203287Srnoland entry->size += size; 162203287Srnoland return 0; 163203287Srnoland} 164203287Srnoland 165203287Srnolandstatic struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent, 166203287Srnoland unsigned long size, 167203287Srnoland int atomic) 168203287Srnoland{ 169203287Srnoland struct drm_mm_node *child; 170203287Srnoland 171203287Srnoland child = drm_mm_kmalloc(parent->mm, atomic); 172203287Srnoland if (unlikely(child == NULL)) 173203287Srnoland return NULL; 174203287Srnoland 175203287Srnoland INIT_LIST_HEAD(&child->fl_entry); 176203287Srnoland 177203287Srnoland child->free = 0; 178203287Srnoland child->size = size; 179203287Srnoland child->start = parent->start; 180203287Srnoland child->mm = parent->mm; 181203287Srnoland 182203287Srnoland list_add_tail(&child->ml_entry, &parent->ml_entry); 183203287Srnoland INIT_LIST_HEAD(&child->fl_entry); 184203287Srnoland 185203287Srnoland parent->size -= size; 186203287Srnoland parent->start += size; 187203287Srnoland return child; 188203287Srnoland} 189203287Srnoland 190203287Srnoland 191203287Srnolandstruct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *node, 192203287Srnoland unsigned long size, 193203287Srnoland unsigned alignment, 194203287Srnoland int atomic) 195203287Srnoland{ 196203287Srnoland 197203287Srnoland struct drm_mm_node *align_splitoff = NULL; 198203287Srnoland unsigned tmp = 0; 199203287Srnoland 200203287Srnoland if (alignment) 201203287Srnoland tmp = node->start % alignment; 202203287Srnoland 203203287Srnoland if (tmp) { 204203287Srnoland align_splitoff = 205203287Srnoland drm_mm_split_at_start(node, alignment - tmp, atomic); 206203287Srnoland if (unlikely(align_splitoff == NULL)) 207203287Srnoland return NULL; 208203287Srnoland } 209203287Srnoland 210203287Srnoland if (node->size == size) { 211203287Srnoland list_del_init(&node->fl_entry); 212203287Srnoland node->free = 0; 213203287Srnoland } else { 214203287Srnoland node = drm_mm_split_at_start(node, size, atomic); 215203287Srnoland } 216203287Srnoland 217203287Srnoland if (align_splitoff) 218203287Srnoland drm_mm_put_block(align_splitoff); 219203287Srnoland 220203287Srnoland return node; 221203287Srnoland} 222203287Srnoland 223203287Srnoland/* 224203287Srnoland * Put a block. Merge with the previous and / or next block if they are free. 225203287Srnoland * Otherwise add to the free stack. 226203287Srnoland */ 227203287Srnoland 228203287Srnolandvoid drm_mm_put_block(struct drm_mm_node *cur) 229203287Srnoland{ 230203287Srnoland 231203287Srnoland struct drm_mm *mm = cur->mm; 232203287Srnoland struct list_head *cur_head = &cur->ml_entry; 233203287Srnoland struct list_head *root_head = &mm->ml_entry; 234203287Srnoland struct drm_mm_node *prev_node = NULL; 235203287Srnoland struct drm_mm_node *next_node; 236203287Srnoland 237203287Srnoland int merged = 0; 238203287Srnoland 239203287Srnoland if (cur_head->prev != root_head) { 240203287Srnoland prev_node = 241203287Srnoland list_entry(cur_head->prev, struct drm_mm_node, ml_entry); 242203287Srnoland if (prev_node->free) { 243203287Srnoland prev_node->size += cur->size; 244203287Srnoland merged = 1; 245203287Srnoland } 246203287Srnoland } 247203287Srnoland if (cur_head->next != root_head) { 248203287Srnoland next_node = 249203287Srnoland list_entry(cur_head->next, struct drm_mm_node, ml_entry); 250203287Srnoland if (next_node->free) { 251203287Srnoland if (merged) { 252203287Srnoland prev_node->size += next_node->size; 253203287Srnoland list_del(&next_node->ml_entry); 254203287Srnoland list_del(&next_node->fl_entry); 255203287Srnoland if (mm->num_unused < MM_UNUSED_TARGET) { 256203287Srnoland list_add(&next_node->fl_entry, 257203287Srnoland &mm->unused_nodes); 258203287Srnoland ++mm->num_unused; 259203287Srnoland } else 260203287Srnoland free(next_node, DRM_MEM_MM); 261203287Srnoland } else { 262203287Srnoland next_node->size += cur->size; 263203287Srnoland next_node->start = cur->start; 264203287Srnoland merged = 1; 265203287Srnoland } 266203287Srnoland } 267203287Srnoland } 268203287Srnoland if (!merged) { 269203287Srnoland cur->free = 1; 270203287Srnoland list_add(&cur->fl_entry, &mm->fl_entry); 271203287Srnoland } else { 272203287Srnoland list_del(&cur->ml_entry); 273203287Srnoland if (mm->num_unused < MM_UNUSED_TARGET) { 274203287Srnoland list_add(&cur->fl_entry, &mm->unused_nodes); 275203287Srnoland ++mm->num_unused; 276203287Srnoland } else 277203287Srnoland free(cur, DRM_MEM_MM); 278203287Srnoland } 279203287Srnoland} 280203287Srnoland 281203287Srnolandstruct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm, 282203287Srnoland unsigned long size, 283203287Srnoland unsigned alignment, int best_match) 284203287Srnoland{ 285203287Srnoland struct list_head *list; 286203287Srnoland const struct list_head *free_stack = &mm->fl_entry; 287203287Srnoland struct drm_mm_node *entry; 288203287Srnoland struct drm_mm_node *best; 289203287Srnoland unsigned long best_size; 290203287Srnoland unsigned wasted; 291203287Srnoland 292203287Srnoland best = NULL; 293203287Srnoland best_size = ~0UL; 294203287Srnoland 295203287Srnoland list_for_each(list, free_stack) { 296203287Srnoland entry = list_entry(list, struct drm_mm_node, fl_entry); 297203287Srnoland wasted = 0; 298203287Srnoland 299203287Srnoland if (entry->size < size) 300203287Srnoland continue; 301203287Srnoland 302203287Srnoland if (alignment) { 303203287Srnoland register unsigned tmp = entry->start % alignment; 304203287Srnoland if (tmp) 305203287Srnoland wasted += alignment - tmp; 306203287Srnoland } 307203287Srnoland 308203287Srnoland if (entry->size >= size + wasted) { 309203287Srnoland if (!best_match) 310203287Srnoland return entry; 311203287Srnoland if (size < best_size) { 312203287Srnoland best = entry; 313203287Srnoland best_size = entry->size; 314203287Srnoland } 315203287Srnoland } 316203287Srnoland } 317203287Srnoland 318203287Srnoland return best; 319203287Srnoland} 320203287Srnoland 321203287Srnolandint drm_mm_clean(struct drm_mm * mm) 322203287Srnoland{ 323203287Srnoland struct list_head *head = &mm->ml_entry; 324203287Srnoland 325203287Srnoland return (head->next->next == head); 326203287Srnoland} 327203287Srnoland 328203287Srnolandint drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size) 329203287Srnoland{ 330203287Srnoland INIT_LIST_HEAD(&mm->ml_entry); 331203287Srnoland INIT_LIST_HEAD(&mm->fl_entry); 332203287Srnoland INIT_LIST_HEAD(&mm->unused_nodes); 333203287Srnoland mm->num_unused = 0; 334203287Srnoland mtx_init(&mm->unused_lock, "drm_unused", NULL, MTX_DEF); 335203287Srnoland 336207118Srnoland /* XXX This could be non-atomic but gets called from a locked path */ 337207118Srnoland return drm_mm_create_tail_node(mm, start, size, 1); 338203287Srnoland} 339203287Srnoland 340203287Srnolandvoid drm_mm_takedown(struct drm_mm * mm) 341203287Srnoland{ 342203287Srnoland struct list_head *bnode = mm->fl_entry.next; 343203287Srnoland struct drm_mm_node *entry; 344203287Srnoland struct drm_mm_node *next; 345203287Srnoland 346203287Srnoland entry = list_entry(bnode, struct drm_mm_node, fl_entry); 347203287Srnoland 348203287Srnoland if (entry->ml_entry.next != &mm->ml_entry || 349203287Srnoland entry->fl_entry.next != &mm->fl_entry) { 350203287Srnoland DRM_ERROR("Memory manager not clean. Delaying takedown\n"); 351203287Srnoland return; 352203287Srnoland } 353203287Srnoland 354203287Srnoland list_del(&entry->fl_entry); 355203287Srnoland list_del(&entry->ml_entry); 356203287Srnoland free(entry, DRM_MEM_MM); 357203287Srnoland 358203287Srnoland mtx_lock(&mm->unused_lock); 359203287Srnoland list_for_each_entry_safe(entry, next, &mm->unused_nodes, fl_entry) { 360203287Srnoland list_del(&entry->fl_entry); 361203287Srnoland free(entry, DRM_MEM_MM); 362203287Srnoland --mm->num_unused; 363203287Srnoland } 364203287Srnoland mtx_unlock(&mm->unused_lock); 365203287Srnoland 366203287Srnoland mtx_destroy(&mm->unused_lock); 367203287Srnoland 368203287Srnoland KASSERT(mm->num_unused == 0, ("num_unused != 0")); 369203287Srnoland} 370