1 /**************************************************************************
3 * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND., USA.
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:
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
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.
26 * $FreeBSD: head/sys/dev/drm2/drm_mm.c 247833 2013-03-05 09:07:58Z kib $
27 **************************************************************************/
30 * Generic simple memory manager implementation. Intended to be used as a base
31 * class implementation for more advanced memory managers.
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.
38 * Aligned allocations can also see improvement.
41 * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
44 #include "dev/drm/drmP.h"
45 #include "dev/drm/drm_mm.h"
47 #define MM_UNUSED_TARGET 4
49 static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic)
51 struct drm_mm_node *child;
53 child = kmalloc(sizeof(*child), DRM_MEM_MM, M_ZERO |
54 (atomic ? M_NOWAIT : M_WAITOK));
56 if (unlikely(child == NULL)) {
57 spin_lock(&mm->unused_spin);
58 if (list_empty(&mm->unused_nodes))
62 list_entry(mm->unused_nodes.next,
63 struct drm_mm_node, node_list);
64 list_del(&child->node_list);
67 spin_unlock(&mm->unused_spin);
72 int drm_mm_pre_get(struct drm_mm *mm)
74 struct drm_mm_node *node;
76 spin_lock(&mm->unused_spin);
77 while (mm->num_unused < MM_UNUSED_TARGET) {
78 spin_unlock(&mm->unused_spin);
79 node = kmalloc(sizeof(*node), DRM_MEM_MM, M_WAITOK);
80 spin_lock(&mm->unused_spin);
82 if (unlikely(node == NULL)) {
83 int ret = (mm->num_unused < 2) ? -ENOMEM : 0;
84 spin_unlock(&mm->unused_spin);
88 list_add_tail(&node->node_list, &mm->unused_nodes);
90 spin_unlock(&mm->unused_spin);
94 static inline unsigned long drm_mm_hole_node_start(struct drm_mm_node *hole_node)
96 return hole_node->start + hole_node->size;
99 static inline unsigned long drm_mm_hole_node_end(struct drm_mm_node *hole_node)
101 struct drm_mm_node *next_node =
102 list_entry(hole_node->node_list.next, struct drm_mm_node,
105 return next_node->start;
108 static void drm_mm_insert_helper(struct drm_mm_node *hole_node,
109 struct drm_mm_node *node,
110 unsigned long size, unsigned alignment)
112 struct drm_mm *mm = hole_node->mm;
113 unsigned long tmp = 0, wasted = 0;
114 unsigned long hole_start = drm_mm_hole_node_start(hole_node);
115 unsigned long hole_end = drm_mm_hole_node_end(hole_node);
117 KASSERT(hole_node->hole_follows && !node->allocated, ("hole_node"));
120 tmp = hole_start % alignment;
123 hole_node->hole_follows = 0;
124 list_del_init(&hole_node->hole_stack);
126 wasted = alignment - tmp;
128 node->start = hole_start + wasted;
133 INIT_LIST_HEAD(&node->hole_stack);
134 list_add(&node->node_list, &hole_node->node_list);
136 KASSERT(node->start + node->size <= hole_end, ("hole pos"));
138 if (node->start + node->size < hole_end) {
139 list_add(&node->hole_stack, &mm->hole_stack);
140 node->hole_follows = 1;
142 node->hole_follows = 0;
146 struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *hole_node,
151 struct drm_mm_node *node;
153 node = drm_mm_kmalloc(hole_node->mm, atomic);
154 if (unlikely(node == NULL))
157 drm_mm_insert_helper(hole_node, node, size, alignment);
162 int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node,
163 unsigned long size, unsigned alignment)
165 struct drm_mm_node *hole_node;
167 hole_node = drm_mm_search_free(mm, size, alignment, 0);
171 drm_mm_insert_helper(hole_node, node, size, alignment);
176 static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,
177 struct drm_mm_node *node,
178 unsigned long size, unsigned alignment,
179 unsigned long start, unsigned long end)
181 struct drm_mm *mm = hole_node->mm;
182 unsigned long tmp = 0, wasted = 0;
183 unsigned long hole_start = drm_mm_hole_node_start(hole_node);
184 unsigned long hole_end = drm_mm_hole_node_end(hole_node);
186 KASSERT(hole_node->hole_follows && !node->allocated, ("hole_node"));
188 if (hole_start < start)
189 wasted += start - hole_start;
191 tmp = (hole_start + wasted) % alignment;
194 wasted += alignment - tmp;
197 hole_node->hole_follows = 0;
198 list_del_init(&hole_node->hole_stack);
201 node->start = hole_start + wasted;
206 INIT_LIST_HEAD(&node->hole_stack);
207 list_add(&node->node_list, &hole_node->node_list);
209 KASSERT(node->start + node->size <= hole_end, ("hole_end"));
210 KASSERT(node->start + node->size <= end, ("end"));
212 if (node->start + node->size < hole_end) {
213 list_add(&node->hole_stack, &mm->hole_stack);
214 node->hole_follows = 1;
216 node->hole_follows = 0;
220 struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *hole_node,
227 struct drm_mm_node *node;
229 node = drm_mm_kmalloc(hole_node->mm, atomic);
230 if (unlikely(node == NULL))
233 drm_mm_insert_helper_range(hole_node, node, size, alignment,
239 int drm_mm_insert_node_in_range(struct drm_mm *mm, struct drm_mm_node *node,
240 unsigned long size, unsigned alignment,
241 unsigned long start, unsigned long end)
243 struct drm_mm_node *hole_node;
245 hole_node = drm_mm_search_free_in_range(mm, size, alignment,
250 drm_mm_insert_helper_range(hole_node, node, size, alignment,
256 void drm_mm_remove_node(struct drm_mm_node *node)
258 struct drm_mm *mm = node->mm;
259 struct drm_mm_node *prev_node;
261 KASSERT(!node->scanned_block && !node->scanned_prev_free
262 && !node->scanned_next_free, ("node"));
265 list_entry(node->node_list.prev, struct drm_mm_node, node_list);
267 if (node->hole_follows) {
268 KASSERT(drm_mm_hole_node_start(node)
269 != drm_mm_hole_node_end(node), ("hole_follows"));
270 list_del(&node->hole_stack);
272 KASSERT(drm_mm_hole_node_start(node)
273 == drm_mm_hole_node_end(node), ("!hole_follows"));
275 if (!prev_node->hole_follows) {
276 prev_node->hole_follows = 1;
277 list_add(&prev_node->hole_stack, &mm->hole_stack);
279 list_move(&prev_node->hole_stack, &mm->hole_stack);
281 list_del(&node->node_list);
286 * Put a block. Merge with the previous and / or next block if they are free.
287 * Otherwise add to the free stack.
290 void drm_mm_put_block(struct drm_mm_node *node)
292 struct drm_mm *mm = node->mm;
294 drm_mm_remove_node(node);
296 spin_lock(&mm->unused_spin);
297 if (mm->num_unused < MM_UNUSED_TARGET) {
298 list_add(&node->node_list, &mm->unused_nodes);
301 drm_free(node, DRM_MEM_MM);
302 spin_unlock(&mm->unused_spin);
305 static int check_free_hole(unsigned long start, unsigned long end,
306 unsigned long size, unsigned alignment)
310 if (end - start < size)
314 unsigned tmp = start % alignment;
316 wasted = alignment - tmp;
319 if (end >= start + size + wasted) {
327 struct drm_mm_node *drm_mm_search_free(const struct drm_mm *mm,
329 unsigned alignment, int best_match)
331 struct drm_mm_node *entry;
332 struct drm_mm_node *best;
333 unsigned long best_size;
338 list_for_each_entry(entry, &mm->hole_stack, hole_stack) {
339 KASSERT(entry->hole_follows, ("hole_follows"));
340 if (!check_free_hole(drm_mm_hole_node_start(entry),
341 drm_mm_hole_node_end(entry),
348 if (entry->size < best_size) {
350 best_size = entry->size;
357 struct drm_mm_node *drm_mm_search_free_in_range(const struct drm_mm *mm,
364 struct drm_mm_node *entry;
365 struct drm_mm_node *best;
366 unsigned long best_size;
368 KASSERT(!mm->scanned_blocks, ("scanned"));
373 list_for_each_entry(entry, &mm->hole_stack, hole_stack) {
374 unsigned long adj_start = drm_mm_hole_node_start(entry) < start ?
375 start : drm_mm_hole_node_start(entry);
376 unsigned long adj_end = drm_mm_hole_node_end(entry) > end ?
377 end : drm_mm_hole_node_end(entry);
379 KASSERT(entry->hole_follows, ("hole_follows"));
380 if (!check_free_hole(adj_start, adj_end, size, alignment))
386 if (entry->size < best_size) {
388 best_size = entry->size;
395 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
397 list_replace(&old->node_list, &new->node_list);
398 list_replace(&old->hole_stack, &new->hole_stack);
399 new->hole_follows = old->hole_follows;
401 new->start = old->start;
402 new->size = old->size;
408 void drm_mm_init_scan(struct drm_mm *mm, unsigned long size,
411 mm->scan_alignment = alignment;
412 mm->scan_size = size;
413 mm->scanned_blocks = 0;
414 mm->scan_hit_start = 0;
415 mm->scan_hit_size = 0;
416 mm->scan_check_range = 0;
417 mm->prev_scanned_node = NULL;
420 void drm_mm_init_scan_with_range(struct drm_mm *mm, unsigned long size,
425 mm->scan_alignment = alignment;
426 mm->scan_size = size;
427 mm->scanned_blocks = 0;
428 mm->scan_hit_start = 0;
429 mm->scan_hit_size = 0;
430 mm->scan_start = start;
432 mm->scan_check_range = 1;
433 mm->prev_scanned_node = NULL;
436 int drm_mm_scan_add_block(struct drm_mm_node *node)
438 struct drm_mm *mm = node->mm;
439 struct drm_mm_node *prev_node;
440 unsigned long hole_start, hole_end;
441 unsigned long adj_start;
442 unsigned long adj_end;
444 mm->scanned_blocks++;
446 KASSERT(!node->scanned_block, ("node->scanned_block"));
447 node->scanned_block = 1;
449 prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
452 node->scanned_preceeds_hole = prev_node->hole_follows;
453 prev_node->hole_follows = 1;
454 list_del(&node->node_list);
455 node->node_list.prev = &prev_node->node_list;
456 node->node_list.next = &mm->prev_scanned_node->node_list;
457 mm->prev_scanned_node = node;
459 hole_start = drm_mm_hole_node_start(prev_node);
460 hole_end = drm_mm_hole_node_end(prev_node);
461 if (mm->scan_check_range) {
462 adj_start = hole_start < mm->scan_start ?
463 mm->scan_start : hole_start;
464 adj_end = hole_end > mm->scan_end ?
465 mm->scan_end : hole_end;
467 adj_start = hole_start;
471 if (check_free_hole(adj_start , adj_end,
472 mm->scan_size, mm->scan_alignment)) {
473 mm->scan_hit_start = hole_start;
474 mm->scan_hit_size = hole_end;
482 int drm_mm_scan_remove_block(struct drm_mm_node *node)
484 struct drm_mm *mm = node->mm;
485 struct drm_mm_node *prev_node;
487 mm->scanned_blocks--;
489 KASSERT(node->scanned_block, ("scanned_block"));
490 node->scanned_block = 0;
492 prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
495 prev_node->hole_follows = node->scanned_preceeds_hole;
496 INIT_LIST_HEAD(&node->node_list);
497 list_add(&node->node_list, &prev_node->node_list);
499 /* Only need to check for containement because start&size for the
500 * complete resulting free block (not just the desired part) is
502 if (node->start >= mm->scan_hit_start &&
503 node->start + node->size
504 <= mm->scan_hit_start + mm->scan_hit_size) {
511 int drm_mm_clean(struct drm_mm * mm)
513 struct list_head *head = &mm->head_node.node_list;
515 return (head->next->next == head);
518 int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
520 INIT_LIST_HEAD(&mm->hole_stack);
521 INIT_LIST_HEAD(&mm->unused_nodes);
523 mm->scanned_blocks = 0;
524 spin_init(&mm->unused_spin);
526 INIT_LIST_HEAD(&mm->head_node.node_list);
527 INIT_LIST_HEAD(&mm->head_node.hole_stack);
528 mm->head_node.hole_follows = 1;
529 mm->head_node.scanned_block = 0;
530 mm->head_node.scanned_prev_free = 0;
531 mm->head_node.scanned_next_free = 0;
532 mm->head_node.mm = mm;
533 mm->head_node.start = start + size;
534 mm->head_node.size = start - mm->head_node.start;
535 list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack);
540 void drm_mm_takedown(struct drm_mm * mm)
542 struct drm_mm_node *entry, *next;
544 if (!list_empty(&mm->head_node.node_list)) {
545 DRM_ERROR("Memory manager not clean. Delaying takedown\n");
549 spin_lock(&mm->unused_spin);
550 list_for_each_entry_safe(entry, next, &mm->unused_nodes, node_list) {
551 list_del(&entry->node_list);
552 drm_free(entry, DRM_MEM_MM);
555 spin_unlock(&mm->unused_spin);
557 spin_uninit(&mm->unused_spin);
559 KASSERT(mm->num_unused == 0, ("num_unused != 0"));
562 void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
564 struct drm_mm_node *entry;
565 unsigned long total_used = 0, total_free = 0, total = 0;
566 unsigned long hole_start, hole_end, hole_size;
568 hole_start = drm_mm_hole_node_start(&mm->head_node);
569 hole_end = drm_mm_hole_node_end(&mm->head_node);
570 hole_size = hole_end - hole_start;
572 kprintf("%s 0x%08lx-0x%08lx: %8lu: free\n",
573 prefix, hole_start, hole_end,
575 total_free += hole_size;
577 drm_mm_for_each_node(entry, mm) {
578 kprintf("%s 0x%08lx-0x%08lx: %8lu: used\n",
579 prefix, entry->start, entry->start + entry->size,
581 total_used += entry->size;
583 if (entry->hole_follows) {
584 hole_start = drm_mm_hole_node_start(entry);
585 hole_end = drm_mm_hole_node_end(entry);
586 hole_size = hole_end - hole_start;
587 kprintf("%s 0x%08lx-0x%08lx: %8lu: free\n",
588 prefix, hole_start, hole_end,
590 total_free += hole_size;
593 total = total_free + total_used;
595 kprintf("%s total: %lu, used %lu free %lu\n", prefix, total,
596 total_used, total_free);