src/wsbm_mm.c

   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 Hellström <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 }