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 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
);