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 "drmP.h" 45 #include <linux/slab.h> 46 47 unsigned long drm_mm_tail_space(struct drm_mm *mm) 48 { 49 struct list_head *tail_node; 50 struct drm_mm_node *entry; 51 52 tail_node = mm->ml_entry.prev; 53 entry = list_entry(tail_node, struct drm_mm_node, ml_entry); 54 if (!entry->free) 55 return 0; 56 57 return entry->size; 58 } 59 60 int drm_mm_remove_space_from_tail(struct drm_mm *mm, unsigned long size) 61 { 62 struct list_head *tail_node; 63 struct drm_mm_node *entry; 64 65 tail_node = mm->ml_entry.prev; 66 entry = list_entry(tail_node, struct drm_mm_node, ml_entry); 67 if (!entry->free) 68 return -ENOMEM; 69 70 if (entry->size <= size) 71 return -ENOMEM; 72 73 entry->size -= size; 74 return 0; 75 } 76 77 78 static int drm_mm_create_tail_node(struct drm_mm *mm, 79 unsigned long start, 80 unsigned long size) 81 { 82 struct drm_mm_node *child; 83 84 child = (struct drm_mm_node *) 85 drm_alloc(sizeof(*child), DRM_MEM_MM); 86 if (!child) 87 return -ENOMEM; 88 89 child->free = 1; 90 child->size = size; 91 child->start = start; 92 child->mm = mm; 93 94 list_add_tail(&child->ml_entry, &mm->ml_entry); 95 list_add_tail(&child->fl_entry, &mm->fl_entry); 96 97 return 0; 98 } 99 100 101 int drm_mm_add_space_to_tail(struct drm_mm *mm, unsigned long size) 102 { 103 struct list_head *tail_node; 104 struct drm_mm_node *entry; 105 106 tail_node = mm->ml_entry.prev; 107 entry = list_entry(tail_node, struct drm_mm_node, ml_entry); 108 if (!entry->free) { 109 return drm_mm_create_tail_node(mm, entry->start + entry->size, size); 110 } 111 entry->size += size; 112 return 0; 113 } 114 115 static struct drm_mm_node *drm_mm_split_at_start(struct drm_mm_node *parent, 116 unsigned long size) 117 { 118 struct drm_mm_node *child; 119 120 child = (struct drm_mm_node *) 121 drm_alloc(sizeof(*child), DRM_MEM_MM); 122 if (!child) 123 return NULL; 124 125 INIT_LIST_HEAD(&child->fl_entry); 126 127 child->free = 0; 128 child->size = size; 129 child->start = parent->start; 130 child->mm = parent->mm; 131 132 list_add_tail(&child->ml_entry, &parent->ml_entry); 133 INIT_LIST_HEAD(&child->fl_entry); 134 135 parent->size -= size; 136 parent->start += size; 137 return child; 138 } 139 140 141 142 struct drm_mm_node *drm_mm_get_block(struct drm_mm_node * parent, 143 unsigned long size, unsigned alignment) 144 { 145 146 struct drm_mm_node *align_splitoff = NULL; 147 struct drm_mm_node *child; 148 unsigned tmp = 0; 149 150 if (alignment) 151 tmp = parent->start % alignment; 152 153 if (tmp) { 154 align_splitoff = drm_mm_split_at_start(parent, alignment - tmp); 155 if (!align_splitoff) 156 return NULL; 157 } 158 159 if (parent->size == size) { 160 list_del_init(&parent->fl_entry); 161 parent->free = 0; 162 return parent; 163 } else { 164 child = drm_mm_split_at_start(parent, size); 165 } 166 167 if (align_splitoff) 168 drm_mm_put_block(align_splitoff); 169 170 return child; 171 } 172 EXPORT_SYMBOL(drm_mm_get_block); 173 174 /* 175 * Put a block. Merge with the previous and / or next block if they are free. 176 * Otherwise add to the free stack. 177 */ 178 179 void drm_mm_put_block(struct drm_mm_node * cur) 180 { 181 182 struct drm_mm *mm = cur->mm; 183 struct list_head *cur_head = &cur->ml_entry; 184 struct list_head *root_head = &mm->ml_entry; 185 struct drm_mm_node *prev_node = NULL; 186 struct drm_mm_node *next_node; 187 188 int merged = 0; 189 190 if (cur_head->prev != root_head) { 191 prev_node = list_entry(cur_head->prev, struct drm_mm_node, ml_entry); 192 if (prev_node->free) { 193 prev_node->size += cur->size; 194 merged = 1; 195 } 196 } 197 if (cur_head->next != root_head) { 198 next_node = list_entry(cur_head->next, struct drm_mm_node, ml_entry); 199 if (next_node->free) { 200 if (merged) { 201 prev_node->size += next_node->size; 202 list_del(&next_node->ml_entry); 203 list_del(&next_node->fl_entry); 204 drm_free(next_node, sizeof(*next_node), 205 DRM_MEM_MM); 206 } else { 207 next_node->size += cur->size; 208 next_node->start = cur->start; 209 merged = 1; 210 } 211 } 212 } 213 if (!merged) { 214 cur->free = 1; 215 list_add(&cur->fl_entry, &mm->fl_entry); 216 } else { 217 list_del(&cur->ml_entry); 218 drm_free(cur, sizeof(*cur), DRM_MEM_MM); 219 } 220 } 221 EXPORT_SYMBOL(drm_mm_put_block); 222 223 struct drm_mm_node *drm_mm_search_free(const struct drm_mm * mm, 224 unsigned long size, 225 unsigned alignment, int best_match) 226 { 227 struct list_head *list; 228 const struct list_head *free_stack = &mm->fl_entry; 229 struct drm_mm_node *entry; 230 struct drm_mm_node *best; 231 unsigned long best_size; 232 unsigned wasted; 233 234 best = NULL; 235 best_size = ~0UL; 236 237 list_for_each(list, free_stack) { 238 entry = list_entry(list, struct drm_mm_node, fl_entry); 239 wasted = 0; 240 241 if (entry->size < size) 242 continue; 243 244 if (alignment) { 245 register unsigned tmp = entry->start % alignment; 246 if (tmp) 247 wasted += alignment - tmp; 248 } 249 250 251 if (entry->size >= size + wasted) { 252 if (!best_match) 253 return entry; 254 if (size < best_size) { 255 best = entry; 256 best_size = entry->size; 257 } 258 } 259 } 260 261 return best; 262 } 263 264 int drm_mm_clean(struct drm_mm * mm) 265 { 266 struct list_head *head = &mm->ml_entry; 267 268 return (head->next->next == head); 269 } 270 EXPORT_SYMBOL(drm_mm_search_free); 271 272 int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size) 273 { 274 INIT_LIST_HEAD(&mm->ml_entry); 275 INIT_LIST_HEAD(&mm->fl_entry); 276 277 return drm_mm_create_tail_node(mm, start, size); 278 } 279 EXPORT_SYMBOL(drm_mm_init); 280 281 void drm_mm_takedown(struct drm_mm * mm) 282 { 283 struct list_head *bnode = mm->fl_entry.next; 284 struct drm_mm_node *entry; 285 286 entry = list_entry(bnode, struct drm_mm_node, fl_entry); 287 288 if (entry->ml_entry.next != &mm->ml_entry || 289 entry->fl_entry.next != &mm->fl_entry) { 290 DRM_ERROR("Memory manager not clean. Delaying takedown\n"); 291 return; 292 } 293 294 list_del(&entry->fl_entry); 295 list_del(&entry->ml_entry); 296 297 drm_free(entry, sizeof(*entry), DRM_MEM_MM); 298 } 299