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>
45 #include <drm/drm_mm.h>
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 void drm_mm_insert_helper(struct drm_mm_node
*hole_node
,
106 struct drm_mm_node
*node
,
107 unsigned long size
, unsigned alignment
,
110 struct drm_mm
*mm
= hole_node
->mm
;
111 unsigned long hole_start
= drm_mm_hole_node_start(hole_node
);
112 unsigned long hole_end
= drm_mm_hole_node_end(hole_node
);
113 unsigned long adj_start
= hole_start
;
114 unsigned long adj_end
= hole_end
;
116 BUG_ON(node
->allocated
);
118 if (mm
->color_adjust
)
119 mm
->color_adjust(hole_node
, color
, &adj_start
, &adj_end
);
122 unsigned tmp
= adj_start
% alignment
;
124 adj_start
+= alignment
- tmp
;
127 if (adj_start
== hole_start
) {
128 hole_node
->hole_follows
= 0;
129 list_del(&hole_node
->hole_stack
);
132 node
->start
= adj_start
;
138 INIT_LIST_HEAD(&node
->hole_stack
);
139 list_add(&node
->node_list
, &hole_node
->node_list
);
141 BUG_ON(node
->start
+ node
->size
> adj_end
);
143 node
->hole_follows
= 0;
144 if (__drm_mm_hole_node_start(node
) < hole_end
) {
145 list_add(&node
->hole_stack
, &mm
->hole_stack
);
146 node
->hole_follows
= 1;
150 struct drm_mm_node
*drm_mm_create_block(struct drm_mm
*mm
,
155 struct drm_mm_node
*hole
, *node
;
156 unsigned long end
= start
+ size
;
157 unsigned long hole_start
;
158 unsigned long hole_end
;
160 drm_mm_for_each_hole(hole
, mm
, hole_start
, hole_end
) {
161 if (hole_start
> start
|| hole_end
< end
)
164 node
= drm_mm_kmalloc(mm
, atomic
);
165 if (unlikely(node
== NULL
))
173 INIT_LIST_HEAD(&node
->hole_stack
);
174 list_add(&node
->node_list
, &hole
->node_list
);
176 if (start
== hole_start
) {
177 hole
->hole_follows
= 0;
178 list_del_init(&hole
->hole_stack
);
181 node
->hole_follows
= 0;
182 if (end
!= hole_end
) {
183 list_add(&node
->hole_stack
, &mm
->hole_stack
);
184 node
->hole_follows
= 1;
190 WARN(1, "no hole found for block 0x%lx + 0x%lx\n", start
, size
);
193 EXPORT_SYMBOL(drm_mm_create_block
);
195 struct drm_mm_node
*drm_mm_get_block_generic(struct drm_mm_node
*hole_node
,
201 struct drm_mm_node
*node
;
203 node
= drm_mm_kmalloc(hole_node
->mm
, atomic
);
204 if (unlikely(node
== NULL
))
207 drm_mm_insert_helper(hole_node
, node
, size
, alignment
, color
);
211 EXPORT_SYMBOL(drm_mm_get_block_generic
);
214 * Search for free space and insert a preallocated memory node. Returns
215 * -ENOSPC if no suitable free area is available. The preallocated memory node
218 int drm_mm_insert_node_generic(struct drm_mm
*mm
, struct drm_mm_node
*node
,
219 unsigned long size
, unsigned alignment
,
222 struct drm_mm_node
*hole_node
;
224 hole_node
= drm_mm_search_free_generic(mm
, size
, alignment
,
229 drm_mm_insert_helper(hole_node
, node
, size
, alignment
, color
);
232 EXPORT_SYMBOL(drm_mm_insert_node_generic
);
234 int drm_mm_insert_node(struct drm_mm
*mm
, struct drm_mm_node
*node
,
235 unsigned long size
, unsigned alignment
)
237 return drm_mm_insert_node_generic(mm
, node
, size
, alignment
, 0);
239 EXPORT_SYMBOL(drm_mm_insert_node
);
241 static void drm_mm_insert_helper_range(struct drm_mm_node
*hole_node
,
242 struct drm_mm_node
*node
,
243 unsigned long size
, unsigned alignment
,
245 unsigned long start
, unsigned long end
)
247 struct drm_mm
*mm
= hole_node
->mm
;
248 unsigned long hole_start
= drm_mm_hole_node_start(hole_node
);
249 unsigned long hole_end
= drm_mm_hole_node_end(hole_node
);
250 unsigned long adj_start
= hole_start
;
251 unsigned long adj_end
= hole_end
;
253 BUG_ON(!hole_node
->hole_follows
|| node
->allocated
);
255 if (adj_start
< start
)
260 if (mm
->color_adjust
)
261 mm
->color_adjust(hole_node
, color
, &adj_start
, &adj_end
);
264 unsigned tmp
= adj_start
% alignment
;
266 adj_start
+= alignment
- tmp
;
269 if (adj_start
== hole_start
) {
270 hole_node
->hole_follows
= 0;
271 list_del(&hole_node
->hole_stack
);
274 node
->start
= adj_start
;
280 INIT_LIST_HEAD(&node
->hole_stack
);
281 list_add(&node
->node_list
, &hole_node
->node_list
);
283 BUG_ON(node
->start
+ node
->size
> adj_end
);
284 BUG_ON(node
->start
+ node
->size
> end
);
286 node
->hole_follows
= 0;
287 if (__drm_mm_hole_node_start(node
) < hole_end
) {
288 list_add(&node
->hole_stack
, &mm
->hole_stack
);
289 node
->hole_follows
= 1;
293 struct drm_mm_node
*drm_mm_get_block_range_generic(struct drm_mm_node
*hole_node
,
301 struct drm_mm_node
*node
;
303 node
= drm_mm_kmalloc(hole_node
->mm
, atomic
);
304 if (unlikely(node
== NULL
))
307 drm_mm_insert_helper_range(hole_node
, node
, size
, alignment
, color
,
312 EXPORT_SYMBOL(drm_mm_get_block_range_generic
);
315 * Search for free space and insert a preallocated memory node. Returns
316 * -ENOSPC if no suitable free area is available. This is for range
317 * restricted allocations. The preallocated memory node must be cleared.
319 int drm_mm_insert_node_in_range_generic(struct drm_mm
*mm
, struct drm_mm_node
*node
,
320 unsigned long size
, unsigned alignment
, unsigned long color
,
321 unsigned long start
, unsigned long end
)
323 struct drm_mm_node
*hole_node
;
325 hole_node
= drm_mm_search_free_in_range_generic(mm
,
326 size
, alignment
, color
,
331 drm_mm_insert_helper_range(hole_node
, node
,
332 size
, alignment
, color
,
336 EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic
);
338 int drm_mm_insert_node_in_range(struct drm_mm
*mm
, struct drm_mm_node
*node
,
339 unsigned long size
, unsigned alignment
,
340 unsigned long start
, unsigned long end
)
342 return drm_mm_insert_node_in_range_generic(mm
, node
, size
, alignment
, 0, start
, end
);
344 EXPORT_SYMBOL(drm_mm_insert_node_in_range
);
347 * Remove a memory node from the allocator.
349 void drm_mm_remove_node(struct drm_mm_node
*node
)
351 struct drm_mm
*mm
= node
->mm
;
352 struct drm_mm_node
*prev_node
;
354 BUG_ON(node
->scanned_block
|| node
->scanned_prev_free
355 || node
->scanned_next_free
);
358 list_entry(node
->node_list
.prev
, struct drm_mm_node
, node_list
);
360 if (node
->hole_follows
) {
361 BUG_ON(__drm_mm_hole_node_start(node
) ==
362 __drm_mm_hole_node_end(node
));
363 list_del(&node
->hole_stack
);
365 BUG_ON(__drm_mm_hole_node_start(node
) !=
366 __drm_mm_hole_node_end(node
));
369 if (!prev_node
->hole_follows
) {
370 prev_node
->hole_follows
= 1;
371 list_add(&prev_node
->hole_stack
, &mm
->hole_stack
);
373 list_move(&prev_node
->hole_stack
, &mm
->hole_stack
);
375 list_del(&node
->node_list
);
378 EXPORT_SYMBOL(drm_mm_remove_node
);
381 * Remove a memory node from the allocator and free the allocated struct
382 * drm_mm_node. Only to be used on a struct drm_mm_node obtained by one of the
383 * drm_mm_get_block functions.
385 void drm_mm_put_block(struct drm_mm_node
*node
)
388 struct drm_mm
*mm
= node
->mm
;
390 drm_mm_remove_node(node
);
392 spin_lock(&mm
->unused_lock
);
393 if (mm
->num_unused
< MM_UNUSED_TARGET
) {
394 list_add(&node
->node_list
, &mm
->unused_nodes
);
398 spin_unlock(&mm
->unused_lock
);
400 EXPORT_SYMBOL(drm_mm_put_block
);
402 static int check_free_hole(unsigned long start
, unsigned long end
,
403 unsigned long size
, unsigned alignment
)
405 if (end
- start
< size
)
409 unsigned tmp
= start
% alignment
;
411 start
+= alignment
- tmp
;
414 return end
>= start
+ size
;
417 struct drm_mm_node
*drm_mm_search_free_generic(const struct drm_mm
*mm
,
423 struct drm_mm_node
*entry
;
424 struct drm_mm_node
*best
;
425 unsigned long adj_start
;
426 unsigned long adj_end
;
427 unsigned long best_size
;
429 BUG_ON(mm
->scanned_blocks
);
434 drm_mm_for_each_hole(entry
, mm
, adj_start
, adj_end
) {
435 if (mm
->color_adjust
) {
436 mm
->color_adjust(entry
, color
, &adj_start
, &adj_end
);
437 if (adj_end
<= adj_start
)
441 if (!check_free_hole(adj_start
, adj_end
, size
, alignment
))
447 if (entry
->size
< best_size
) {
449 best_size
= entry
->size
;
455 EXPORT_SYMBOL(drm_mm_search_free_generic
);
457 struct drm_mm_node
*drm_mm_search_free_in_range_generic(const struct drm_mm
*mm
,
465 struct drm_mm_node
*entry
;
466 struct drm_mm_node
*best
;
467 unsigned long adj_start
;
468 unsigned long adj_end
;
469 unsigned long best_size
;
471 BUG_ON(mm
->scanned_blocks
);
476 drm_mm_for_each_hole(entry
, mm
, adj_start
, adj_end
) {
477 if (adj_start
< start
)
482 if (mm
->color_adjust
) {
483 mm
->color_adjust(entry
, color
, &adj_start
, &adj_end
);
484 if (adj_end
<= adj_start
)
488 if (!check_free_hole(adj_start
, adj_end
, size
, alignment
))
494 if (entry
->size
< best_size
) {
496 best_size
= entry
->size
;
502 EXPORT_SYMBOL(drm_mm_search_free_in_range_generic
);
505 * Moves an allocation. To be used with embedded struct drm_mm_node.
507 void drm_mm_replace_node(struct drm_mm_node
*old
, struct drm_mm_node
*new)
509 list_replace(&old
->node_list
, &new->node_list
);
510 list_replace(&old
->hole_stack
, &new->hole_stack
);
511 new->hole_follows
= old
->hole_follows
;
513 new->start
= old
->start
;
514 new->size
= old
->size
;
515 new->color
= old
->color
;
520 EXPORT_SYMBOL(drm_mm_replace_node
);
523 * Initializa lru scanning.
525 * This simply sets up the scanning routines with the parameters for the desired
528 * Warning: As long as the scan list is non-empty, no other operations than
529 * adding/removing nodes to/from the scan list are allowed.
531 void drm_mm_init_scan(struct drm_mm
*mm
,
536 mm
->scan_color
= color
;
537 mm
->scan_alignment
= alignment
;
538 mm
->scan_size
= size
;
539 mm
->scanned_blocks
= 0;
540 mm
->scan_hit_start
= 0;
541 mm
->scan_hit_end
= 0;
542 mm
->scan_check_range
= 0;
543 mm
->prev_scanned_node
= NULL
;
545 EXPORT_SYMBOL(drm_mm_init_scan
);
548 * Initializa lru scanning.
550 * This simply sets up the scanning routines with the parameters for the desired
551 * hole. This version is for range-restricted scans.
553 * Warning: As long as the scan list is non-empty, no other operations than
554 * adding/removing nodes to/from the scan list are allowed.
556 void drm_mm_init_scan_with_range(struct drm_mm
*mm
,
563 mm
->scan_color
= color
;
564 mm
->scan_alignment
= alignment
;
565 mm
->scan_size
= size
;
566 mm
->scanned_blocks
= 0;
567 mm
->scan_hit_start
= 0;
568 mm
->scan_hit_end
= 0;
569 mm
->scan_start
= start
;
571 mm
->scan_check_range
= 1;
572 mm
->prev_scanned_node
= NULL
;
574 EXPORT_SYMBOL(drm_mm_init_scan_with_range
);
577 * Add a node to the scan list that might be freed to make space for the desired
580 * Returns non-zero, if a hole has been found, zero otherwise.
582 int drm_mm_scan_add_block(struct drm_mm_node
*node
)
584 struct drm_mm
*mm
= node
->mm
;
585 struct drm_mm_node
*prev_node
;
586 unsigned long hole_start
, hole_end
;
587 unsigned long adj_start
, adj_end
;
589 mm
->scanned_blocks
++;
591 BUG_ON(node
->scanned_block
);
592 node
->scanned_block
= 1;
594 prev_node
= list_entry(node
->node_list
.prev
, struct drm_mm_node
,
597 node
->scanned_preceeds_hole
= prev_node
->hole_follows
;
598 prev_node
->hole_follows
= 1;
599 list_del(&node
->node_list
);
600 node
->node_list
.prev
= &prev_node
->node_list
;
601 node
->node_list
.next
= &mm
->prev_scanned_node
->node_list
;
602 mm
->prev_scanned_node
= node
;
604 adj_start
= hole_start
= drm_mm_hole_node_start(prev_node
);
605 adj_end
= hole_end
= drm_mm_hole_node_end(prev_node
);
607 if (mm
->scan_check_range
) {
608 if (adj_start
< mm
->scan_start
)
609 adj_start
= mm
->scan_start
;
610 if (adj_end
> mm
->scan_end
)
611 adj_end
= mm
->scan_end
;
614 if (mm
->color_adjust
)
615 mm
->color_adjust(prev_node
, mm
->scan_color
,
616 &adj_start
, &adj_end
);
618 if (check_free_hole(adj_start
, adj_end
,
619 mm
->scan_size
, mm
->scan_alignment
)) {
620 mm
->scan_hit_start
= hole_start
;
621 mm
->scan_hit_end
= hole_end
;
627 EXPORT_SYMBOL(drm_mm_scan_add_block
);
630 * Remove a node from the scan list.
632 * Nodes _must_ be removed in the exact same order from the scan list as they
633 * have been added, otherwise the internal state of the memory manager will be
636 * When the scan list is empty, the selected memory nodes can be freed. An
637 * immediately following drm_mm_search_free with best_match = 0 will then return
638 * the just freed block (because its at the top of the free_stack list).
640 * Returns one if this block should be evicted, zero otherwise. Will always
641 * return zero when no hole has been found.
643 int drm_mm_scan_remove_block(struct drm_mm_node
*node
)
645 struct drm_mm
*mm
= node
->mm
;
646 struct drm_mm_node
*prev_node
;
648 mm
->scanned_blocks
--;
650 BUG_ON(!node
->scanned_block
);
651 node
->scanned_block
= 0;
653 prev_node
= list_entry(node
->node_list
.prev
, struct drm_mm_node
,
656 prev_node
->hole_follows
= node
->scanned_preceeds_hole
;
657 list_add(&node
->node_list
, &prev_node
->node_list
);
659 return (drm_mm_hole_node_end(node
) > mm
->scan_hit_start
&&
660 node
->start
< mm
->scan_hit_end
);
662 EXPORT_SYMBOL(drm_mm_scan_remove_block
);
664 int drm_mm_clean(struct drm_mm
* mm
)
666 struct list_head
*head
= &mm
->head_node
.node_list
;
668 return (head
->next
->next
== head
);
670 EXPORT_SYMBOL(drm_mm_clean
);
672 int drm_mm_init(struct drm_mm
* mm
, unsigned long start
, unsigned long size
)
674 INIT_LIST_HEAD(&mm
->hole_stack
);
675 INIT_LIST_HEAD(&mm
->unused_nodes
);
677 mm
->scanned_blocks
= 0;
678 spin_lock_init(&mm
->unused_lock
);
680 /* Clever trick to avoid a special case in the free hole tracking. */
681 INIT_LIST_HEAD(&mm
->head_node
.node_list
);
682 INIT_LIST_HEAD(&mm
->head_node
.hole_stack
);
683 mm
->head_node
.hole_follows
= 1;
684 mm
->head_node
.scanned_block
= 0;
685 mm
->head_node
.scanned_prev_free
= 0;
686 mm
->head_node
.scanned_next_free
= 0;
687 mm
->head_node
.mm
= mm
;
688 mm
->head_node
.start
= start
+ size
;
689 mm
->head_node
.size
= start
- mm
->head_node
.start
;
690 list_add_tail(&mm
->head_node
.hole_stack
, &mm
->hole_stack
);
692 mm
->color_adjust
= NULL
;
696 EXPORT_SYMBOL(drm_mm_init
);
698 void drm_mm_takedown(struct drm_mm
* mm
)
700 struct drm_mm_node
*entry
, *next
;
702 if (!list_empty(&mm
->head_node
.node_list
)) {
703 DRM_ERROR("Memory manager not clean. Delaying takedown\n");
707 spin_lock(&mm
->unused_lock
);
708 list_for_each_entry_safe(entry
, next
, &mm
->unused_nodes
, node_list
) {
709 list_del(&entry
->node_list
);
713 spin_unlock(&mm
->unused_lock
);
715 BUG_ON(mm
->num_unused
!= 0);
717 EXPORT_SYMBOL(drm_mm_takedown
);
719 void drm_mm_debug_table(struct drm_mm
*mm
, const char *prefix
)
721 struct drm_mm_node
*entry
;
722 unsigned long total_used
= 0, total_free
= 0, total
= 0;
723 unsigned long hole_start
, hole_end
, hole_size
;
725 hole_start
= drm_mm_hole_node_start(&mm
->head_node
);
726 hole_end
= drm_mm_hole_node_end(&mm
->head_node
);
727 hole_size
= hole_end
- hole_start
;
729 printk(KERN_DEBUG
"%s 0x%08lx-0x%08lx: %8lu: free\n",
730 prefix
, hole_start
, hole_end
,
732 total_free
+= hole_size
;
734 drm_mm_for_each_node(entry
, mm
) {
735 printk(KERN_DEBUG
"%s 0x%08lx-0x%08lx: %8lu: used\n",
736 prefix
, entry
->start
, entry
->start
+ entry
->size
,
738 total_used
+= entry
->size
;
740 if (entry
->hole_follows
) {
741 hole_start
= drm_mm_hole_node_start(entry
);
742 hole_end
= drm_mm_hole_node_end(entry
);
743 hole_size
= hole_end
- hole_start
;
744 printk(KERN_DEBUG
"%s 0x%08lx-0x%08lx: %8lu: free\n",
745 prefix
, hole_start
, hole_end
,
747 total_free
+= hole_size
;
750 total
= total_free
+ total_used
;
752 printk(KERN_DEBUG
"%s total: %lu, used %lu free %lu\n", prefix
, total
,
753 total_used
, total_free
);
755 EXPORT_SYMBOL(drm_mm_debug_table
);
757 #if defined(CONFIG_DEBUG_FS)
758 int drm_mm_dump_table(struct seq_file
*m
, struct drm_mm
*mm
)
760 struct drm_mm_node
*entry
;
761 unsigned long total_used
= 0, total_free
= 0, total
= 0;
762 unsigned long hole_start
, hole_end
, hole_size
;
764 hole_start
= drm_mm_hole_node_start(&mm
->head_node
);
765 hole_end
= drm_mm_hole_node_end(&mm
->head_node
);
766 hole_size
= hole_end
- hole_start
;
768 seq_printf(m
, "0x%08lx-0x%08lx: 0x%08lx: free\n",
769 hole_start
, hole_end
, hole_size
);
770 total_free
+= hole_size
;
772 drm_mm_for_each_node(entry
, mm
) {
773 seq_printf(m
, "0x%08lx-0x%08lx: 0x%08lx: used\n",
774 entry
->start
, entry
->start
+ entry
->size
,
776 total_used
+= entry
->size
;
777 if (entry
->hole_follows
) {
778 hole_start
= drm_mm_hole_node_start(entry
);
779 hole_end
= drm_mm_hole_node_end(entry
);
780 hole_size
= hole_end
- hole_start
;
781 seq_printf(m
, "0x%08lx-0x%08lx: 0x%08lx: free\n",
782 hole_start
, hole_end
, hole_size
);
783 total_free
+= hole_size
;
786 total
= total_free
+ total_used
;
788 seq_printf(m
, "total: %lu, used %lu free %lu\n", total
, total_used
, total_free
);
791 EXPORT_SYMBOL(drm_mm_dump_table
);