Home | History | Annotate | Download | only in src 
      1 /**************************************************************************
      2  *
      3  * Copyright 2006-2008 Tungsten Graphics, Inc., Cedar Park, TX., USA.
      4  * All Rights Reserved.
      5  * Copyright 2009 VMware, Inc., Palo Alto, CA., USA.
      6  * All Rights Reserved.
      7  *
      8  * Permission is hereby granted, free of charge, to any person obtaining a
      9  * copy of this software and associated documentation files (the
     10  * "Software"), to deal in the Software without restriction, including
     11  * without limitation the rights to use, copy, modify, merge, publish,
     12  * distribute, sub license, and/or sell copies of the Software, and to
     13  * permit persons to whom the Software is furnished to do so, subject to
     14  * the following conditions:
     15  *
     16  * The above copyright notice and this permission notice (including the
     17  * next paragraph) shall be included in all copies or substantial portions
     18  * of the Software.
     19  *
     20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     21  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     22  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
     23  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
     24  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
     25  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
     26  * USE OR OTHER DEALINGS IN THE SOFTWARE.
     27  *
     28  **************************************************************************/
     29 
     30 /*
     31  * Generic simple memory manager implementation. Intended to be used as a base
     32  * class implementation for more advanced memory managers.
     33  *
     34  * Note that the algorithm used is quite simple and there might be substantial
     35  * performance gains if a smarter free list is implemented. Currently it is just an
     36  * unordered stack of free regions. This could easily be improved if an RB-tree
     37  * is used instead. At least if we expect heavy fragmentation.
     38  * Note that this implementation is more or less identical to the drm core manager
     39  * in the linux kernel.
     40  *
     41  * Authors:
     42  * Thomas Hellstrm <thomas-at-tungstengraphics-dot-com>
     43  */
     44 
     45 #ifdef HAVE_CONFIG_H
     46 #include "config.h"
     47 #endif
     48 
     49 #include "wsbm_mm.h"
     50 #include <errno.h>
     51 #include <stdlib.h>
     52 
     53 unsigned long
     54 wsbmMMTailSpace(struct _WsbmMM *mm)
     55 {
     56     struct _WsbmListHead *tail_node;
     57     struct _WsbmMMNode *entry;
     58 
     59     tail_node = mm->ml_entry.prev;
     60     entry = WSBMLISTENTRY(tail_node, struct _WsbmMMNode, ml_entry);
     61 
     62     if (!entry->free)
     63 	return 0;
     64 
     65     return entry->size;
     66 }
     67 
     68 int
     69 wsbmMMRemoveSpaceFromTail(struct _WsbmMM *mm, unsigned long size)
     70 {
     71     struct _WsbmListHead *tail_node;
     72     struct _WsbmMMNode *entry;
     73 
     74     tail_node = mm->ml_entry.prev;
     75     entry = WSBMLISTENTRY(tail_node, struct _WsbmMMNode, ml_entry);
     76 
     77     if (!entry->free)
     78 	return -ENOMEM;
     79 
     80     if (entry->size <= size)
     81 	return -ENOMEM;
     82 
     83     entry->size -= size;
     84     return 0;
     85 }
     86 
     87 static int
     88 wsbmMMCreateTailNode(struct _WsbmMM *mm,
     89 		     unsigned long start, unsigned long size)
     90 {
     91     struct _WsbmMMNode *child;
     92 
     93     child = (struct _WsbmMMNode *)malloc(sizeof(*child));
     94     if (!child)
     95 	return -ENOMEM;
     96 
     97     child->free = 1;
     98     child->size = size;
     99     child->start = start;
    100     child->mm = mm;
    101 
    102     WSBMLISTADDTAIL(&child->ml_entry, &mm->ml_entry);
    103     WSBMLISTADDTAIL(&child->fl_entry, &mm->fl_entry);
    104 
    105     return 0;
    106 }
    107 
    108 static struct _WsbmMMNode *
    109 wsbmMMSplitAtStart(struct _WsbmMMNode *parent, unsigned long size)
    110 {
    111     struct _WsbmMMNode *child;
    112 
    113     child = (struct _WsbmMMNode *)malloc(sizeof(*child));
    114     if (!child)
    115 	return NULL;
    116 
    117     WSBMINITLISTHEAD(&child->fl_entry);
    118 
    119     child->free = 0;
    120     child->size = size;
    121     child->start = parent->start;
    122     child->mm = parent->mm;
    123 
    124     WSBMLISTADDTAIL(&child->ml_entry, &parent->ml_entry);
    125     WSBMINITLISTHEAD(&child->fl_entry);
    126 
    127     parent->size -= size;
    128     parent->start += size;
    129     return child;
    130 }
    131 
    132 struct _WsbmMMNode *
    133 wsbmMMGetBlock(struct _WsbmMMNode *parent,
    134 	       unsigned long size, unsigned alignment)
    135 {
    136 
    137     struct _WsbmMMNode *align_splitoff = NULL;
    138     struct _WsbmMMNode *child;
    139     unsigned tmp = 0;
    140 
    141     if (alignment)
    142 	tmp = parent->start % alignment;
    143 
    144     if (tmp) {
    145 	align_splitoff = wsbmMMSplitAtStart(parent, alignment - tmp);
    146 	if (!align_splitoff)
    147 	    return NULL;
    148     }
    149 
    150     if (parent->size == size) {
    151 	WSBMLISTDELINIT(&parent->fl_entry);
    152 	parent->free = 0;
    153 	return parent;
    154     } else {
    155 	child = wsbmMMSplitAtStart(parent, size);
    156     }
    157 
    158     if (align_splitoff)
    159 	wsbmMMPutBlock(align_splitoff);
    160 
    161     return child;
    162 }
    163 
    164 /*
    165  * Put a block. Merge with the previous and / or next block if they are free.
    166  * Otherwise add to the free stack.
    167  */
    168 
    169 void
    170 wsbmMMPutBlock(struct _WsbmMMNode *cur)
    171 {
    172 
    173     struct _WsbmMM *mm = cur->mm;
    174     struct _WsbmListHead *cur_head = &cur->ml_entry;
    175     struct _WsbmListHead *root_head = &mm->ml_entry;
    176     struct _WsbmMMNode *prev_node = NULL;
    177     struct _WsbmMMNode *next_node;
    178 
    179     int merged = 0;
    180 
    181     if (cur_head->prev != root_head) {
    182 	prev_node =
    183 	    WSBMLISTENTRY(cur_head->prev, struct _WsbmMMNode, ml_entry);
    184 	if (prev_node->free) {
    185 	    prev_node->size += cur->size;
    186 	    merged = 1;
    187 	}
    188     }
    189     if (cur_head->next != root_head) {
    190 	next_node =
    191 	    WSBMLISTENTRY(cur_head->next, struct _WsbmMMNode, ml_entry);
    192 	if (next_node->free) {
    193 	    if (merged) {
    194 		prev_node->size += next_node->size;
    195 		WSBMLISTDEL(&next_node->ml_entry);
    196 		WSBMLISTDEL(&next_node->fl_entry);
    197 		free(next_node);
    198 	    } else {
    199 		next_node->size += cur->size;
    200 		next_node->start = cur->start;
    201 		merged = 1;
    202 	    }
    203 	}
    204     }
    205     if (!merged) {
    206 	cur->free = 1;
    207 	WSBMLISTADD(&cur->fl_entry, &mm->fl_entry);
    208     } else {
    209 	WSBMLISTDEL(&cur->ml_entry);
    210 	free(cur);
    211     }
    212 }
    213 
    214 struct _WsbmMMNode *
    215 wsbmMMSearchFree(const struct _WsbmMM *mm,
    216 		 unsigned long size, unsigned alignment, int best_match)
    217 {
    218     struct _WsbmListHead *list;
    219     const struct _WsbmListHead *free_stack = &mm->fl_entry;
    220     struct _WsbmMMNode *entry;
    221     struct _WsbmMMNode *best;
    222     unsigned long best_size;
    223     unsigned wasted;
    224 
    225     best = NULL;
    226     best_size = ~0UL;
    227 
    228     WSBMLISTFOREACH(list, free_stack) {
    229 	entry = WSBMLISTENTRY(list, struct _WsbmMMNode, fl_entry);
    230 
    231 	wasted = 0;
    232 
    233 	if (entry->size < size)
    234 	    continue;
    235 
    236 	if (alignment) {
    237 	    register unsigned tmp = entry->start % alignment;
    238 
    239 	    if (tmp)
    240 		wasted += alignment - tmp;
    241 	}
    242 
    243 	if (entry->size >= size + wasted) {
    244 	    if (!best_match)
    245 		return entry;
    246 	    if (size < best_size) {
    247 		best = entry;
    248 		best_size = entry->size;
    249 	    }
    250 	}
    251     }
    252 
    253     return best;
    254 }
    255 
    256 int
    257 wsbmMMclean(struct _WsbmMM *mm)
    258 {
    259     struct _WsbmListHead *head = &mm->ml_entry;
    260 
    261     return (head->next->next == head);
    262 }
    263 
    264 int
    265 wsbmMMinit(struct _WsbmMM *mm, unsigned long start, unsigned long size)
    266 {
    267     WSBMINITLISTHEAD(&mm->ml_entry);
    268     WSBMINITLISTHEAD(&mm->fl_entry);
    269 
    270     return wsbmMMCreateTailNode(mm, start, size);
    271 }
    272 
    273 void
    274 wsbmMMtakedown(struct _WsbmMM *mm)
    275 {
    276     struct _WsbmListHead *bnode = mm->fl_entry.next;
    277     struct _WsbmMMNode *entry;
    278 
    279     entry = WSBMLISTENTRY(bnode, struct _WsbmMMNode, fl_entry);
    280 
    281     if (entry->ml_entry.next != &mm->ml_entry ||
    282 	entry->fl_entry.next != &mm->fl_entry) {
    283 	return;
    284     }
    285 
    286     WSBMLISTDEL(&entry->fl_entry);
    287     WSBMLISTDEL(&entry->ml_entry);
    288     free(entry);
    289 }
    290