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.
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>
46 #include <linux/slab.h>
47 #include <linux/seq_file.h>
48 #include <linux/export.h>
50 #define MM_UNUSED_TARGET 4
52 static struct drm_mm_node *drm_mm_kmalloc(struct drm_mm *mm, int atomic)
54 struct drm_mm_node *child;
57 child = kzalloc(sizeof(*child), GFP_ATOMIC);
59 child = kzalloc(sizeof(*child), GFP_KERNEL);
61 if (unlikely(child == NULL)) {
62 spin_lock(&mm->unused_lock);
63 if (list_empty(&mm->unused_nodes))
67 list_entry(mm->unused_nodes.next,
68 struct drm_mm_node, node_list);
69 list_del(&child->node_list);
72 spin_unlock(&mm->unused_lock);
77 /* drm_mm_pre_get() - pre allocate drm_mm_node structure
78 * drm_mm: memory manager struct we are pre-allocating for
80 * Returns 0 on success or -ENOMEM if allocation fails.
82 int drm_mm_pre_get(struct drm_mm *mm)
84 struct drm_mm_node *node;
86 spin_lock(&mm->unused_lock);
87 while (mm->num_unused < MM_UNUSED_TARGET) {
88 spin_unlock(&mm->unused_lock);
89 node = kzalloc(sizeof(*node), GFP_KERNEL);
90 spin_lock(&mm->unused_lock);
92 if (unlikely(node == NULL)) {
93 int ret = (mm->num_unused < 2) ? -ENOMEM : 0;
94 spin_unlock(&mm->unused_lock);
98 list_add_tail(&node->node_list, &mm->unused_nodes);
100 spin_unlock(&mm->unused_lock);
103 EXPORT_SYMBOL(drm_mm_pre_get);
105 static inline unsigned long drm_mm_hole_node_start(struct drm_mm_node *hole_node)
107 return hole_node->start + hole_node->size;
110 static inline unsigned long drm_mm_hole_node_end(struct drm_mm_node *hole_node)
112 struct drm_mm_node *next_node =
113 list_entry(hole_node->node_list.next, struct drm_mm_node,
116 return next_node->start;
119 static void drm_mm_insert_helper(struct drm_mm_node *hole_node,
120 struct drm_mm_node *node,
121 unsigned long size, unsigned alignment,
124 struct drm_mm *mm = hole_node->mm;
125 unsigned long hole_start = drm_mm_hole_node_start(hole_node);
126 unsigned long hole_end = drm_mm_hole_node_end(hole_node);
127 unsigned long adj_start = hole_start;
128 unsigned long adj_end = hole_end;
130 BUG_ON(!hole_node->hole_follows || node->allocated);
132 if (mm->color_adjust)
133 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
136 unsigned tmp = adj_start % alignment;
138 adj_start += alignment - tmp;
141 if (adj_start == hole_start) {
142 hole_node->hole_follows = 0;
143 list_del(&hole_node->hole_stack);
146 node->start = adj_start;
152 INIT_LIST_HEAD(&node->hole_stack);
153 list_add(&node->node_list, &hole_node->node_list);
155 BUG_ON(node->start + node->size > adj_end);
157 node->hole_follows = 0;
158 if (node->start + node->size < hole_end) {
159 list_add(&node->hole_stack, &mm->hole_stack);
160 node->hole_follows = 1;
164 struct drm_mm_node *drm_mm_get_block_generic(struct drm_mm_node *hole_node,
170 struct drm_mm_node *node;
172 node = drm_mm_kmalloc(hole_node->mm, atomic);
173 if (unlikely(node == NULL))
176 drm_mm_insert_helper(hole_node, node, size, alignment, color);
180 EXPORT_SYMBOL(drm_mm_get_block_generic);
183 * Search for free space and insert a preallocated memory node. Returns
184 * -ENOSPC if no suitable free area is available. The preallocated memory node
187 int drm_mm_insert_node(struct drm_mm *mm, struct drm_mm_node *node,
188 unsigned long size, unsigned alignment)
190 struct drm_mm_node *hole_node;
192 hole_node = drm_mm_search_free(mm, size, alignment, false);
196 drm_mm_insert_helper(hole_node, node, size, alignment, 0);
200 EXPORT_SYMBOL(drm_mm_insert_node);
202 static void drm_mm_insert_helper_range(struct drm_mm_node *hole_node,
203 struct drm_mm_node *node,
204 unsigned long size, unsigned alignment,
206 unsigned long start, unsigned long end)
208 struct drm_mm *mm = hole_node->mm;
209 unsigned long hole_start = drm_mm_hole_node_start(hole_node);
210 unsigned long hole_end = drm_mm_hole_node_end(hole_node);
211 unsigned long adj_start = hole_start;
212 unsigned long adj_end = hole_end;
214 BUG_ON(!hole_node->hole_follows || node->allocated);
216 if (mm->color_adjust)
217 mm->color_adjust(hole_node, color, &adj_start, &adj_end);
219 if (adj_start < start)
223 unsigned tmp = adj_start % alignment;
225 adj_start += alignment - tmp;
228 if (adj_start == hole_start) {
229 hole_node->hole_follows = 0;
230 list_del(&hole_node->hole_stack);
233 node->start = adj_start;
239 INIT_LIST_HEAD(&node->hole_stack);
240 list_add(&node->node_list, &hole_node->node_list);
242 BUG_ON(node->start + node->size > adj_end);
243 BUG_ON(node->start + node->size > end);
245 node->hole_follows = 0;
246 if (node->start + node->size < hole_end) {
247 list_add(&node->hole_stack, &mm->hole_stack);
248 node->hole_follows = 1;
252 struct drm_mm_node *drm_mm_get_block_range_generic(struct drm_mm_node *hole_node,
260 struct drm_mm_node *node;
262 node = drm_mm_kmalloc(hole_node->mm, atomic);
263 if (unlikely(node == NULL))
266 drm_mm_insert_helper_range(hole_node, node, size, alignment, color,
271 EXPORT_SYMBOL(drm_mm_get_block_range_generic);
274 * Search for free space and insert a preallocated memory node. Returns
275 * -ENOSPC if no suitable free area is available. This is for range
276 * restricted allocations. The preallocated memory node must be cleared.
278 int drm_mm_insert_node_in_range(struct drm_mm *mm, struct drm_mm_node *node,
279 unsigned long size, unsigned alignment,
280 unsigned long start, unsigned long end)
282 struct drm_mm_node *hole_node;
284 hole_node = drm_mm_search_free_in_range(mm, size, alignment,
289 drm_mm_insert_helper_range(hole_node, node, size, alignment, 0,
294 EXPORT_SYMBOL(drm_mm_insert_node_in_range);
297 * Remove a memory node from the allocator.
299 void drm_mm_remove_node(struct drm_mm_node *node)
301 struct drm_mm *mm = node->mm;
302 struct drm_mm_node *prev_node;
304 BUG_ON(node->scanned_block || node->scanned_prev_free
305 || node->scanned_next_free);
308 list_entry(node->node_list.prev, struct drm_mm_node, node_list);
310 if (node->hole_follows) {
311 BUG_ON(drm_mm_hole_node_start(node)
312 == drm_mm_hole_node_end(node));
313 list_del(&node->hole_stack);
315 BUG_ON(drm_mm_hole_node_start(node)
316 != drm_mm_hole_node_end(node));
318 if (!prev_node->hole_follows) {
319 prev_node->hole_follows = 1;
320 list_add(&prev_node->hole_stack, &mm->hole_stack);
322 list_move(&prev_node->hole_stack, &mm->hole_stack);
324 list_del(&node->node_list);
327 EXPORT_SYMBOL(drm_mm_remove_node);
330 * Remove a memory node from the allocator and free the allocated struct
331 * drm_mm_node. Only to be used on a struct drm_mm_node obtained by one of the
332 * drm_mm_get_block functions.
334 void drm_mm_put_block(struct drm_mm_node *node)
337 struct drm_mm *mm = node->mm;
339 drm_mm_remove_node(node);
341 spin_lock(&mm->unused_lock);
342 if (mm->num_unused < MM_UNUSED_TARGET) {
343 list_add(&node->node_list, &mm->unused_nodes);
347 spin_unlock(&mm->unused_lock);
349 EXPORT_SYMBOL(drm_mm_put_block);
351 static int check_free_hole(unsigned long start, unsigned long end,
352 unsigned long size, unsigned alignment)
354 if (end - start < size)
358 unsigned tmp = start % alignment;
360 start += alignment - tmp;
363 return end >= start + size;
366 struct drm_mm_node *drm_mm_search_free_generic(const struct drm_mm *mm,
372 struct drm_mm_node *entry;
373 struct drm_mm_node *best;
374 unsigned long best_size;
376 BUG_ON(mm->scanned_blocks);
381 list_for_each_entry(entry, &mm->hole_stack, hole_stack) {
382 unsigned long adj_start = drm_mm_hole_node_start(entry);
383 unsigned long adj_end = drm_mm_hole_node_end(entry);
385 if (mm->color_adjust) {
386 mm->color_adjust(entry, color, &adj_start, &adj_end);
387 if (adj_end <= adj_start)
391 BUG_ON(!entry->hole_follows);
392 if (!check_free_hole(adj_start, adj_end, size, alignment))
398 if (entry->size < best_size) {
400 best_size = entry->size;
406 EXPORT_SYMBOL(drm_mm_search_free_generic);
408 struct drm_mm_node *drm_mm_search_free_in_range_generic(const struct drm_mm *mm,
416 struct drm_mm_node *entry;
417 struct drm_mm_node *best;
418 unsigned long best_size;
420 BUG_ON(mm->scanned_blocks);
425 list_for_each_entry(entry, &mm->hole_stack, hole_stack) {
426 unsigned long adj_start = drm_mm_hole_node_start(entry) < start ?
427 start : drm_mm_hole_node_start(entry);
428 unsigned long adj_end = drm_mm_hole_node_end(entry) > end ?
429 end : drm_mm_hole_node_end(entry);
431 BUG_ON(!entry->hole_follows);
433 if (mm->color_adjust) {
434 mm->color_adjust(entry, color, &adj_start, &adj_end);
435 if (adj_end <= adj_start)
439 if (!check_free_hole(adj_start, adj_end, size, alignment))
445 if (entry->size < best_size) {
447 best_size = entry->size;
453 EXPORT_SYMBOL(drm_mm_search_free_in_range_generic);
456 * Moves an allocation. To be used with embedded struct drm_mm_node.
458 void drm_mm_replace_node(struct drm_mm_node *old, struct drm_mm_node *new)
460 list_replace(&old->node_list, &new->node_list);
461 list_replace(&old->hole_stack, &new->hole_stack);
462 new->hole_follows = old->hole_follows;
464 new->start = old->start;
465 new->size = old->size;
466 new->color = old->color;
471 EXPORT_SYMBOL(drm_mm_replace_node);
474 * Initializa lru scanning.
476 * This simply sets up the scanning routines with the parameters for the desired
479 * Warning: As long as the scan list is non-empty, no other operations than
480 * adding/removing nodes to/from the scan list are allowed.
482 void drm_mm_init_scan(struct drm_mm *mm,
487 mm->scan_color = color;
488 mm->scan_alignment = alignment;
489 mm->scan_size = size;
490 mm->scanned_blocks = 0;
491 mm->scan_hit_start = 0;
492 mm->scan_hit_size = 0;
493 mm->scan_check_range = 0;
494 mm->prev_scanned_node = NULL;
496 EXPORT_SYMBOL(drm_mm_init_scan);
499 * Initializa lru scanning.
501 * This simply sets up the scanning routines with the parameters for the desired
502 * hole. This version is for range-restricted scans.
504 * Warning: As long as the scan list is non-empty, no other operations than
505 * adding/removing nodes to/from the scan list are allowed.
507 void drm_mm_init_scan_with_range(struct drm_mm *mm,
514 mm->scan_color = color;
515 mm->scan_alignment = alignment;
516 mm->scan_size = size;
517 mm->scanned_blocks = 0;
518 mm->scan_hit_start = 0;
519 mm->scan_hit_size = 0;
520 mm->scan_start = start;
522 mm->scan_check_range = 1;
523 mm->prev_scanned_node = NULL;
525 EXPORT_SYMBOL(drm_mm_init_scan_with_range);
528 * Add a node to the scan list that might be freed to make space for the desired
531 * Returns non-zero, if a hole has been found, zero otherwise.
533 int drm_mm_scan_add_block(struct drm_mm_node *node)
535 struct drm_mm *mm = node->mm;
536 struct drm_mm_node *prev_node;
537 unsigned long hole_start, hole_end;
538 unsigned long adj_start;
539 unsigned long adj_end;
541 mm->scanned_blocks++;
543 BUG_ON(node->scanned_block);
544 node->scanned_block = 1;
546 prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
549 node->scanned_preceeds_hole = prev_node->hole_follows;
550 prev_node->hole_follows = 1;
551 list_del(&node->node_list);
552 node->node_list.prev = &prev_node->node_list;
553 node->node_list.next = &mm->prev_scanned_node->node_list;
554 mm->prev_scanned_node = node;
556 hole_start = drm_mm_hole_node_start(prev_node);
557 hole_end = drm_mm_hole_node_end(prev_node);
559 adj_start = hole_start;
562 if (mm->color_adjust)
563 mm->color_adjust(prev_node, mm->scan_color, &adj_start, &adj_end);
565 if (mm->scan_check_range) {
566 if (adj_start < mm->scan_start)
567 adj_start = mm->scan_start;
568 if (adj_end > mm->scan_end)
569 adj_end = mm->scan_end;
572 if (check_free_hole(adj_start, adj_end,
573 mm->scan_size, mm->scan_alignment)) {
574 mm->scan_hit_start = hole_start;
575 mm->scan_hit_size = hole_end;
582 EXPORT_SYMBOL(drm_mm_scan_add_block);
585 * Remove a node from the scan list.
587 * Nodes _must_ be removed in the exact same order from the scan list as they
588 * have been added, otherwise the internal state of the memory manager will be
591 * When the scan list is empty, the selected memory nodes can be freed. An
592 * immediately following drm_mm_search_free with best_match = 0 will then return
593 * the just freed block (because its at the top of the free_stack list).
595 * Returns one if this block should be evicted, zero otherwise. Will always
596 * return zero when no hole has been found.
598 int drm_mm_scan_remove_block(struct drm_mm_node *node)
600 struct drm_mm *mm = node->mm;
601 struct drm_mm_node *prev_node;
603 mm->scanned_blocks--;
605 BUG_ON(!node->scanned_block);
606 node->scanned_block = 0;
608 prev_node = list_entry(node->node_list.prev, struct drm_mm_node,
611 prev_node->hole_follows = node->scanned_preceeds_hole;
612 INIT_LIST_HEAD(&node->node_list);
613 list_add(&node->node_list, &prev_node->node_list);
615 /* Only need to check for containement because start&size for the
616 * complete resulting free block (not just the desired part) is
618 if (node->start >= mm->scan_hit_start &&
619 node->start + node->size
620 <= mm->scan_hit_start + mm->scan_hit_size) {
626 EXPORT_SYMBOL(drm_mm_scan_remove_block);
628 int drm_mm_clean(struct drm_mm * mm)
630 struct list_head *head = &mm->head_node.node_list;
632 return (head->next->next == head);
634 EXPORT_SYMBOL(drm_mm_clean);
636 int drm_mm_init(struct drm_mm * mm, unsigned long start, unsigned long size)
638 INIT_LIST_HEAD(&mm->hole_stack);
639 INIT_LIST_HEAD(&mm->unused_nodes);
641 mm->scanned_blocks = 0;
642 spin_lock_init(&mm->unused_lock);
644 /* Clever trick to avoid a special case in the free hole tracking. */
645 INIT_LIST_HEAD(&mm->head_node.node_list);
646 INIT_LIST_HEAD(&mm->head_node.hole_stack);
647 mm->head_node.hole_follows = 1;
648 mm->head_node.scanned_block = 0;
649 mm->head_node.scanned_prev_free = 0;
650 mm->head_node.scanned_next_free = 0;
651 mm->head_node.mm = mm;
652 mm->head_node.start = start + size;
653 mm->head_node.size = start - mm->head_node.start;
654 list_add_tail(&mm->head_node.hole_stack, &mm->hole_stack);
656 mm->color_adjust = NULL;
660 EXPORT_SYMBOL(drm_mm_init);
662 void drm_mm_takedown(struct drm_mm * mm)
664 struct drm_mm_node *entry, *next;
666 if (!list_empty(&mm->head_node.node_list)) {
667 DRM_ERROR("Memory manager not clean. Delaying takedown\n");
671 spin_lock(&mm->unused_lock);
672 list_for_each_entry_safe(entry, next, &mm->unused_nodes, node_list) {
673 list_del(&entry->node_list);
677 spin_unlock(&mm->unused_lock);
679 BUG_ON(mm->num_unused != 0);
681 EXPORT_SYMBOL(drm_mm_takedown);
683 void drm_mm_debug_table(struct drm_mm *mm, const char *prefix)
685 struct drm_mm_node *entry;
686 unsigned long total_used = 0, total_free = 0, total = 0;
687 unsigned long hole_start, hole_end, hole_size;
689 hole_start = drm_mm_hole_node_start(&mm->head_node);
690 hole_end = drm_mm_hole_node_end(&mm->head_node);
691 hole_size = hole_end - hole_start;
693 printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: free\n",
694 prefix, hole_start, hole_end,
696 total_free += hole_size;
698 drm_mm_for_each_node(entry, mm) {
699 printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: used\n",
700 prefix, entry->start, entry->start + entry->size,
702 total_used += entry->size;
704 if (entry->hole_follows) {
705 hole_start = drm_mm_hole_node_start(entry);
706 hole_end = drm_mm_hole_node_end(entry);
707 hole_size = hole_end - hole_start;
708 printk(KERN_DEBUG "%s 0x%08lx-0x%08lx: %8lu: free\n",
709 prefix, hole_start, hole_end,
711 total_free += hole_size;
714 total = total_free + total_used;
716 printk(KERN_DEBUG "%s total: %lu, used %lu free %lu\n", prefix, total,
717 total_used, total_free);
719 EXPORT_SYMBOL(drm_mm_debug_table);
721 #if defined(CONFIG_DEBUG_FS)
722 int drm_mm_dump_table(struct seq_file *m, struct drm_mm *mm)
724 struct drm_mm_node *entry;
725 unsigned long total_used = 0, total_free = 0, total = 0;
726 unsigned long hole_start, hole_end, hole_size;
728 hole_start = drm_mm_hole_node_start(&mm->head_node);
729 hole_end = drm_mm_hole_node_end(&mm->head_node);
730 hole_size = hole_end - hole_start;
732 seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: free\n",
733 hole_start, hole_end, hole_size);
734 total_free += hole_size;
736 drm_mm_for_each_node(entry, mm) {
737 seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: used\n",
738 entry->start, entry->start + entry->size,
740 total_used += entry->size;
741 if (entry->hole_follows) {
742 hole_start = drm_mm_hole_node_start(entry);
743 hole_end = drm_mm_hole_node_end(entry);
744 hole_size = hole_end - hole_start;
745 seq_printf(m, "0x%08lx-0x%08lx: 0x%08lx: free\n",
746 hole_start, hole_end, hole_size);
747 total_free += hole_size;
750 total = total_free + total_used;
752 seq_printf(m, "total: %lu, used %lu free %lu\n", total, total_used, total_free);
755 EXPORT_SYMBOL(drm_mm_dump_table);