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 int drm_mm_reserve_node(struct drm_mm
*mm
, struct drm_mm_node
*node
)
152 struct drm_mm_node
*hole
;
153 unsigned long end
= node
->start
+ node
->size
;
154 unsigned long hole_start
;
155 unsigned long hole_end
;
157 BUG_ON(node
== NULL
);
159 /* Find the relevant hole to add our node to */
160 drm_mm_for_each_hole(hole
, mm
, hole_start
, hole_end
) {
161 if (hole_start
> node
->start
|| hole_end
< end
)
167 INIT_LIST_HEAD(&node
->hole_stack
);
168 list_add(&node
->node_list
, &hole
->node_list
);
170 if (node
->start
== hole_start
) {
171 hole
->hole_follows
= 0;
172 list_del_init(&hole
->hole_stack
);
175 node
->hole_follows
= 0;
176 if (end
!= hole_end
) {
177 list_add(&node
->hole_stack
, &mm
->hole_stack
);
178 node
->hole_follows
= 1;
184 WARN(1, "no hole found for node 0x%lx + 0x%lx\n",
185 node
->start
, node
->size
);
188 EXPORT_SYMBOL(drm_mm_reserve_node
);
190 struct drm_mm_node
*drm_mm_get_block_generic(struct drm_mm_node
*hole_node
,
196 struct drm_mm_node
*node
;
198 node
= drm_mm_kmalloc(hole_node
->mm
, atomic
);
199 if (unlikely(node
== NULL
))
202 drm_mm_insert_helper(hole_node
, node
, size
, alignment
, color
);
206 EXPORT_SYMBOL(drm_mm_get_block_generic
);
209 * Search for free space and insert a preallocated memory node. Returns
210 * -ENOSPC if no suitable free area is available. The preallocated memory node
213 int drm_mm_insert_node_generic(struct drm_mm
*mm
, struct drm_mm_node
*node
,
214 unsigned long size
, unsigned alignment
,
217 struct drm_mm_node
*hole_node
;
219 hole_node
= drm_mm_search_free_generic(mm
, size
, alignment
,
224 drm_mm_insert_helper(hole_node
, node
, size
, alignment
, color
);
227 EXPORT_SYMBOL(drm_mm_insert_node_generic
);
229 int drm_mm_insert_node(struct drm_mm
*mm
, struct drm_mm_node
*node
,
230 unsigned long size
, unsigned alignment
)
232 return drm_mm_insert_node_generic(mm
, node
, size
, alignment
, 0);
234 EXPORT_SYMBOL(drm_mm_insert_node
);
236 static void drm_mm_insert_helper_range(struct drm_mm_node
*hole_node
,
237 struct drm_mm_node
*node
,
238 unsigned long size
, unsigned alignment
,
240 unsigned long start
, unsigned long end
)
242 struct drm_mm
*mm
= hole_node
->mm
;
243 unsigned long hole_start
= drm_mm_hole_node_start(hole_node
);
244 unsigned long hole_end
= drm_mm_hole_node_end(hole_node
);
245 unsigned long adj_start
= hole_start
;
246 unsigned long adj_end
= hole_end
;
248 BUG_ON(!hole_node
->hole_follows
|| node
->allocated
);
250 if (adj_start
< start
)
255 if (mm
->color_adjust
)
256 mm
->color_adjust(hole_node
, color
, &adj_start
, &adj_end
);
259 unsigned tmp
= adj_start
% alignment
;
261 adj_start
+= alignment
- tmp
;
264 if (adj_start
== hole_start
) {
265 hole_node
->hole_follows
= 0;
266 list_del(&hole_node
->hole_stack
);
269 node
->start
= adj_start
;
275 INIT_LIST_HEAD(&node
->hole_stack
);
276 list_add(&node
->node_list
, &hole_node
->node_list
);
278 BUG_ON(node
->start
+ node
->size
> adj_end
);
279 BUG_ON(node
->start
+ node
->size
> end
);
281 node
->hole_follows
= 0;
282 if (__drm_mm_hole_node_start(node
) < hole_end
) {
283 list_add(&node
->hole_stack
, &mm
->hole_stack
);
284 node
->hole_follows
= 1;
288 struct drm_mm_node
*drm_mm_get_block_range_generic(struct drm_mm_node
*hole_node
,
296 struct drm_mm_node
*node
;
298 node
= drm_mm_kmalloc(hole_node
->mm
, atomic
);
299 if (unlikely(node
== NULL
))
302 drm_mm_insert_helper_range(hole_node
, node
, size
, alignment
, color
,
307 EXPORT_SYMBOL(drm_mm_get_block_range_generic
);
310 * Search for free space and insert a preallocated memory node. Returns
311 * -ENOSPC if no suitable free area is available. This is for range
312 * restricted allocations. The preallocated memory node must be cleared.
314 int drm_mm_insert_node_in_range_generic(struct drm_mm
*mm
, struct drm_mm_node
*node
,
315 unsigned long size
, unsigned alignment
, unsigned long color
,
316 unsigned long start
, unsigned long end
)
318 struct drm_mm_node
*hole_node
;
320 hole_node
= drm_mm_search_free_in_range_generic(mm
,
321 size
, alignment
, color
,
326 drm_mm_insert_helper_range(hole_node
, node
,
327 size
, alignment
, color
,
331 EXPORT_SYMBOL(drm_mm_insert_node_in_range_generic
);
333 int drm_mm_insert_node_in_range(struct drm_mm
*mm
, struct drm_mm_node
*node
,
334 unsigned long size
, unsigned alignment
,
335 unsigned long start
, unsigned long end
)
337 return drm_mm_insert_node_in_range_generic(mm
, node
, size
, alignment
, 0, start
, end
);
339 EXPORT_SYMBOL(drm_mm_insert_node_in_range
);
342 * Remove a memory node from the allocator.
344 void drm_mm_remove_node(struct drm_mm_node
*node
)
346 struct drm_mm
*mm
= node
->mm
;
347 struct drm_mm_node
*prev_node
;
349 BUG_ON(node
->scanned_block
|| node
->scanned_prev_free
350 || node
->scanned_next_free
);
353 list_entry(node
->node_list
.prev
, struct drm_mm_node
, node_list
);
355 if (node
->hole_follows
) {
356 BUG_ON(__drm_mm_hole_node_start(node
) ==
357 __drm_mm_hole_node_end(node
));
358 list_del(&node
->hole_stack
);
360 BUG_ON(__drm_mm_hole_node_start(node
) !=
361 __drm_mm_hole_node_end(node
));
364 if (!prev_node
->hole_follows
) {
365 prev_node
->hole_follows
= 1;
366 list_add(&prev_node
->hole_stack
, &mm
->hole_stack
);
368 list_move(&prev_node
->hole_stack
, &mm
->hole_stack
);
370 list_del(&node
->node_list
);
373 EXPORT_SYMBOL(drm_mm_remove_node
);
376 * Remove a memory node from the allocator and free the allocated struct
377 * drm_mm_node. Only to be used on a struct drm_mm_node obtained by one of the
378 * drm_mm_get_block functions.
380 void drm_mm_put_block(struct drm_mm_node
*node
)
383 struct drm_mm
*mm
= node
->mm
;
385 drm_mm_remove_node(node
);
387 spin_lock(&mm
->unused_lock
);
388 if (mm
->num_unused
< MM_UNUSED_TARGET
) {
389 list_add(&node
->node_list
, &mm
->unused_nodes
);
393 spin_unlock(&mm
->unused_lock
);
395 EXPORT_SYMBOL(drm_mm_put_block
);
397 static int check_free_hole(unsigned long start
, unsigned long end
,
398 unsigned long size
, unsigned alignment
)
400 if (end
- start
< size
)
404 unsigned tmp
= start
% alignment
;
406 start
+= alignment
- tmp
;
409 return end
>= start
+ size
;
412 struct drm_mm_node
*drm_mm_search_free_generic(const struct drm_mm
*mm
,
418 struct drm_mm_node
*entry
;
419 struct drm_mm_node
*best
;
420 unsigned long adj_start
;
421 unsigned long adj_end
;
422 unsigned long best_size
;
424 BUG_ON(mm
->scanned_blocks
);
429 drm_mm_for_each_hole(entry
, mm
, adj_start
, adj_end
) {
430 if (mm
->color_adjust
) {
431 mm
->color_adjust(entry
, color
, &adj_start
, &adj_end
);
432 if (adj_end
<= adj_start
)
436 if (!check_free_hole(adj_start
, adj_end
, size
, alignment
))
442 if (entry
->size
< best_size
) {
444 best_size
= entry
->size
;
450 EXPORT_SYMBOL(drm_mm_search_free_generic
);
452 struct drm_mm_node
*drm_mm_search_free_in_range_generic(const struct drm_mm
*mm
,
460 struct drm_mm_node
*entry
;
461 struct drm_mm_node
*best
;
462 unsigned long adj_start
;
463 unsigned long adj_end
;
464 unsigned long best_size
;
466 BUG_ON(mm
->scanned_blocks
);
471 drm_mm_for_each_hole(entry
, mm
, adj_start
, adj_end
) {
472 if (adj_start
< start
)
477 if (mm
->color_adjust
) {
478 mm
->color_adjust(entry
, color
, &adj_start
, &adj_end
);
479 if (adj_end
<= adj_start
)
483 if (!check_free_hole(adj_start
, adj_end
, size
, alignment
))
489 if (entry
->size
< best_size
) {
491 best_size
= entry
->size
;
497 EXPORT_SYMBOL(drm_mm_search_free_in_range_generic
);
500 * Moves an allocation. To be used with embedded struct drm_mm_node.
502 void drm_mm_replace_node(struct drm_mm_node
*old
, struct drm_mm_node
*new)
504 list_replace(&old
->node_list
, &new->node_list
);
505 list_replace(&old
->hole_stack
, &new->hole_stack
);
506 new->hole_follows
= old
->hole_follows
;
508 new->start
= old
->start
;
509 new->size
= old
->size
;
510 new->color
= old
->color
;
515 EXPORT_SYMBOL(drm_mm_replace_node
);
518 * Initializa lru scanning.
520 * This simply sets up the scanning routines with the parameters for the desired
523 * Warning: As long as the scan list is non-empty, no other operations than
524 * adding/removing nodes to/from the scan list are allowed.
526 void drm_mm_init_scan(struct drm_mm
*mm
,
531 mm
->scan_color
= color
;
532 mm
->scan_alignment
= alignment
;
533 mm
->scan_size
= size
;
534 mm
->scanned_blocks
= 0;
535 mm
->scan_hit_start
= 0;
536 mm
->scan_hit_end
= 0;
537 mm
->scan_check_range
= 0;
538 mm
->prev_scanned_node
= NULL
;
540 EXPORT_SYMBOL(drm_mm_init_scan
);
543 * Initializa lru scanning.
545 * This simply sets up the scanning routines with the parameters for the desired
546 * hole. This version is for range-restricted scans.
548 * Warning: As long as the scan list is non-empty, no other operations than
549 * adding/removing nodes to/from the scan list are allowed.
551 void drm_mm_init_scan_with_range(struct drm_mm
*mm
,
558 mm
->scan_color
= color
;
559 mm
->scan_alignment
= alignment
;
560 mm
->scan_size
= size
;
561 mm
->scanned_blocks
= 0;
562 mm
->scan_hit_start
= 0;
563 mm
->scan_hit_end
= 0;
564 mm
->scan_start
= start
;
566 mm
->scan_check_range
= 1;
567 mm
->prev_scanned_node
= NULL
;
569 EXPORT_SYMBOL(drm_mm_init_scan_with_range
);
572 * Add a node to the scan list that might be freed to make space for the desired
575 * Returns non-zero, if a hole has been found, zero otherwise.
577 int drm_mm_scan_add_block(struct drm_mm_node
*node
)
579 struct drm_mm
*mm
= node
->mm
;
580 struct drm_mm_node
*prev_node
;
581 unsigned long hole_start
, hole_end
;
582 unsigned long adj_start
, adj_end
;
584 mm
->scanned_blocks
++;
586 BUG_ON(node
->scanned_block
);
587 node
->scanned_block
= 1;
589 prev_node
= list_entry(node
->node_list
.prev
, struct drm_mm_node
,
592 node
->scanned_preceeds_hole
= prev_node
->hole_follows
;
593 prev_node
->hole_follows
= 1;
594 list_del(&node
->node_list
);
595 node
->node_list
.prev
= &prev_node
->node_list
;
596 node
->node_list
.next
= &mm
->prev_scanned_node
->node_list
;
597 mm
->prev_scanned_node
= node
;
599 adj_start
= hole_start
= drm_mm_hole_node_start(prev_node
);
600 adj_end
= hole_end
= drm_mm_hole_node_end(prev_node
);
602 if (mm
->scan_check_range
) {
603 if (adj_start
< mm
->scan_start
)
604 adj_start
= mm
->scan_start
;
605 if (adj_end
> mm
->scan_end
)
606 adj_end
= mm
->scan_end
;
609 if (mm
->color_adjust
)
610 mm
->color_adjust(prev_node
, mm
->scan_color
,
611 &adj_start
, &adj_end
);
613 if (check_free_hole(adj_start
, adj_end
,
614 mm
->scan_size
, mm
->scan_alignment
)) {
615 mm
->scan_hit_start
= hole_start
;
616 mm
->scan_hit_end
= hole_end
;
622 EXPORT_SYMBOL(drm_mm_scan_add_block
);
625 * Remove a node from the scan list.
627 * Nodes _must_ be removed in the exact same order from the scan list as they
628 * have been added, otherwise the internal state of the memory manager will be
631 * When the scan list is empty, the selected memory nodes can be freed. An
632 * immediately following drm_mm_search_free with best_match = 0 will then return
633 * the just freed block (because its at the top of the free_stack list).
635 * Returns one if this block should be evicted, zero otherwise. Will always
636 * return zero when no hole has been found.
638 int drm_mm_scan_remove_block(struct drm_mm_node
*node
)
640 struct drm_mm
*mm
= node
->mm
;
641 struct drm_mm_node
*prev_node
;
643 mm
->scanned_blocks
--;
645 BUG_ON(!node
->scanned_block
);
646 node
->scanned_block
= 0;
648 prev_node
= list_entry(node
->node_list
.prev
, struct drm_mm_node
,
651 prev_node
->hole_follows
= node
->scanned_preceeds_hole
;
652 list_add(&node
->node_list
, &prev_node
->node_list
);
654 return (drm_mm_hole_node_end(node
) > mm
->scan_hit_start
&&
655 node
->start
< mm
->scan_hit_end
);
657 EXPORT_SYMBOL(drm_mm_scan_remove_block
);
659 int drm_mm_clean(struct drm_mm
* mm
)
661 struct list_head
*head
= &mm
->head_node
.node_list
;
663 return (head
->next
->next
== head
);
665 EXPORT_SYMBOL(drm_mm_clean
);
667 void drm_mm_init(struct drm_mm
* mm
, unsigned long start
, unsigned long size
)
669 INIT_LIST_HEAD(&mm
->hole_stack
);
670 INIT_LIST_HEAD(&mm
->unused_nodes
);
672 mm
->scanned_blocks
= 0;
673 spin_lock_init(&mm
->unused_lock
);
675 /* Clever trick to avoid a special case in the free hole tracking. */
676 INIT_LIST_HEAD(&mm
->head_node
.node_list
);
677 INIT_LIST_HEAD(&mm
->head_node
.hole_stack
);
678 mm
->head_node
.hole_follows
= 1;
679 mm
->head_node
.scanned_block
= 0;
680 mm
->head_node
.scanned_prev_free
= 0;
681 mm
->head_node
.scanned_next_free
= 0;
682 mm
->head_node
.mm
= mm
;
683 mm
->head_node
.start
= start
+ size
;
684 mm
->head_node
.size
= start
- mm
->head_node
.start
;
685 list_add_tail(&mm
->head_node
.hole_stack
, &mm
->hole_stack
);
687 mm
->color_adjust
= NULL
;
689 EXPORT_SYMBOL(drm_mm_init
);
691 void drm_mm_takedown(struct drm_mm
* mm
)
693 struct drm_mm_node
*entry
, *next
;
695 if (WARN(!list_empty(&mm
->head_node
.node_list
),
696 "Memory manager not clean. Delaying takedown\n")) {
700 spin_lock(&mm
->unused_lock
);
701 list_for_each_entry_safe(entry
, next
, &mm
->unused_nodes
, node_list
) {
702 list_del(&entry
->node_list
);
706 spin_unlock(&mm
->unused_lock
);
708 BUG_ON(mm
->num_unused
!= 0);
710 EXPORT_SYMBOL(drm_mm_takedown
);
712 static unsigned long drm_mm_debug_hole(struct drm_mm_node
*entry
,
715 unsigned long hole_start
, hole_end
, hole_size
;
717 if (entry
->hole_follows
) {
718 hole_start
= drm_mm_hole_node_start(entry
);
719 hole_end
= drm_mm_hole_node_end(entry
);
720 hole_size
= hole_end
- hole_start
;
721 printk(KERN_DEBUG
"%s 0x%08lx-0x%08lx: %8lu: free\n",
722 prefix
, hole_start
, hole_end
,
730 void drm_mm_debug_table(struct drm_mm
*mm
, const char *prefix
)
732 struct drm_mm_node
*entry
;
733 unsigned long total_used
= 0, total_free
= 0, total
= 0;
735 total_free
+= drm_mm_debug_hole(&mm
->head_node
, prefix
);
737 drm_mm_for_each_node(entry
, mm
) {
738 printk(KERN_DEBUG
"%s 0x%08lx-0x%08lx: %8lu: used\n",
739 prefix
, entry
->start
, entry
->start
+ entry
->size
,
741 total_used
+= entry
->size
;
742 total_free
+= drm_mm_debug_hole(entry
, prefix
);
744 total
= total_free
+ total_used
;
746 printk(KERN_DEBUG
"%s total: %lu, used %lu free %lu\n", prefix
, total
,
747 total_used
, total_free
);
749 EXPORT_SYMBOL(drm_mm_debug_table
);
751 #if defined(CONFIG_DEBUG_FS)
752 static unsigned long drm_mm_dump_hole(struct seq_file
*m
, struct drm_mm_node
*entry
)
754 unsigned long hole_start
, hole_end
, hole_size
;
756 if (entry
->hole_follows
) {
757 hole_start
= drm_mm_hole_node_start(entry
);
758 hole_end
= drm_mm_hole_node_end(entry
);
759 hole_size
= hole_end
- hole_start
;
760 seq_printf(m
, "0x%08lx-0x%08lx: 0x%08lx: free\n",
761 hole_start
, hole_end
, hole_size
);
768 int drm_mm_dump_table(struct seq_file
*m
, struct drm_mm
*mm
)
770 struct drm_mm_node
*entry
;
771 unsigned long total_used
= 0, total_free
= 0, total
= 0;
773 total_free
+= drm_mm_dump_hole(m
, &mm
->head_node
);
775 drm_mm_for_each_node(entry
, mm
) {
776 seq_printf(m
, "0x%08lx-0x%08lx: 0x%08lx: used\n",
777 entry
->start
, entry
->start
+ entry
->size
,
779 total_used
+= entry
->size
;
780 total_free
+= drm_mm_dump_hole(m
, entry
);
782 total
= total_free
+ total_used
;
784 seq_printf(m
, "total: %lu, used %lu free %lu\n", total
, total_used
, total_free
);
787 EXPORT_SYMBOL(drm_mm_dump_table
);