src/util/u_mm.c

   1 /**************************************************************************
   2  *
   3  * Copyright (C) 1999 Wittawat Yamwong
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included
  13  * in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  16  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * WITTAWAT YAMWONG, OR ANY OTHER CONTRIBUTORS BE LIABLE FOR ANY CLAIM,
  19  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
  20  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
  21  * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22  *
  23  **************************************************************************/
  24
  25
  26 #include "util/u_debug.h"
  27
  28 #include "util/u_memory.h"
  29 #include "util/u_mm.h"
  30 #include "util/macros.h"
  31
  32
  33 void
  34 u_mmDumpMemInfo(const struct mem_block *heap)
  35 {
  36    debug_printf("Memory heap %p:\n", (void *) heap);
  37    if (heap == NULL) {
  38       debug_printf("  heap == 0\n");
  39    }
  40    else {
  41       const struct mem_block *p;
  42       int total_used = 0, total_free = 0;
  43
  44       for (p = heap->next; p != heap; p = p->next) {
  45          debug_printf("  Offset:%08x, Size:%08x, %c%c\n", p->ofs, p->size,
  46                       p->free ? 'F':'.',
  47                       p->reserved ? 'R':'.');
  48          if (p->free)
  49             total_free += p->size;
  50          else
  51             total_used += p->size;
  52       }
  53
  54       debug_printf("'\nMemory stats: total = %d, used = %d, free = %d\n",
  55                    total_used + total_free, total_used, total_free);
  56       debug_printf("\nFree list:\n");
  57
  58       for (p = heap->next_free; p != heap; p = p->next_free) {
  59          debug_printf(" FREE Offset:%08x, Size:%08x, %c%c\n", p->ofs, p->size,
  60                       p->free ? 'F':'.',
  61                       p->reserved ? 'R':'.');
  62       }
  63
  64    }
  65    debug_printf("End of memory blocks\n");
  66 }
  67
  68
  69 struct mem_block *
  70 u_mmInit(int ofs, int size)
  71 {
  72    struct mem_block *heap, *block;
  73
  74    if (size <= 0)
  75       return NULL;
  76
  77    heap = CALLOC_STRUCT(mem_block);
  78    if (!heap)
  79       return NULL;
  80
  81    block = CALLOC_STRUCT(mem_block);
  82    if (!block) {
  83       FREE(heap);
  84       return NULL;
  85    }
  86
  87    heap->next = block;
  88    heap->prev = block;
  89    heap->next_free = block;
  90    heap->prev_free = block;
  91
  92    block->heap = heap;
  93    block->next = heap;
  94    block->prev = heap;
  95    block->next_free = heap;
  96    block->prev_free = heap;
  97
  98    block->ofs = ofs;
  99    block->size = size;
 100    block->free = 1;
 101
 102    return heap;
 103 }
 104
 105
 106 static struct mem_block *
 107 SliceBlock(struct mem_block *p,
 108            int startofs, int size,
 109            int reserved, UNUSED int alignment)
 110 {
 111    struct mem_block *newblock;
 112
 113    /* break left  [p, newblock, p->next], then p = newblock */
 114    if (startofs > p->ofs) {
 115       newblock = CALLOC_STRUCT(mem_block);
 116       if (!newblock)
 117          return NULL;
 118       newblock->ofs = startofs;
 119       newblock->size = p->size - (startofs - p->ofs);
 120       newblock->free = 1;
 121       newblock->heap = p->heap;
 122
 123       newblock->next = p->next;
 124       newblock->prev = p;
 125       p->next->prev = newblock;
 126       p->next = newblock;
 127
 128       newblock->next_free = p->next_free;
 129       newblock->prev_free = p;
 130       p->next_free->prev_free = newblock;
 131       p->next_free = newblock;
 132
 133       p->size -= newblock->size;
 134       p = newblock;
 135    }
 136
 137    /* break right, also [p, newblock, p->next] */
 138    if (size < p->size) {
 139       newblock = CALLOC_STRUCT(mem_block);
 140       if (!newblock)
 141          return NULL;
 142       newblock->ofs = startofs + size;
 143       newblock->size = p->size - size;
 144       newblock->free = 1;
 145       newblock->heap = p->heap;
 146
 147       newblock->next = p->next;
 148       newblock->prev = p;
 149       p->next->prev = newblock;
 150       p->next = newblock;
 151
 152       newblock->next_free = p->next_free;
 153       newblock->prev_free = p;
 154       p->next_free->prev_free = newblock;
 155       p->next_free = newblock;
 156
 157       p->size = size;
 158    }
 159
 160    /* p = middle block */
 161    p->free = 0;
 162
 163    /* Remove p from the free list:
 164     */
 165    p->next_free->prev_free = p->prev_free;
 166    p->prev_free->next_free = p->next_free;
 167
 168    p->next_free = 0;
 169    p->prev_free = 0;
 170
 171    p->reserved = reserved;
 172    return p;
 173 }
 174
 175
 176 struct mem_block *
 177 u_mmAllocMem(struct mem_block *heap, int size, int align2, int startSearch)
 178 {
 179    struct mem_block *p;
 180    const int mask = (1 << align2)-1;
 181    int startofs = 0;
 182    int endofs;
 183
 184    assert(size >= 0);
 185    assert(align2 >= 0);
 186    /* Make sure that a byte alignment isn't getting passed for our
 187     * power-of-two alignment arg.
 188     */
 189    assert(align2 < 32);
 190
 191    if (!heap || align2 < 0 || size <= 0)
 192       return NULL;
 193
 194    for (p = heap->next_free; p != heap; p = p->next_free) {
 195       assert(p->free);
 196
 197       startofs = (p->ofs + mask) & ~mask;
 198       if ( startofs < startSearch ) {
 199          startofs = startSearch;
 200       }
 201       endofs = startofs+size;
 202       if (endofs <= (p->ofs+p->size))
 203          break;
 204    }
 205
 206    if (p == heap)
 207       return NULL;
 208
 209    assert(p->free);
 210    p = SliceBlock(p,startofs,size,0,mask+1);
 211
 212    return p;
 213 }
 214
 215
 216 struct mem_block *
 217 u_mmFindBlock(struct mem_block *heap, int start)
 218 {
 219    struct mem_block *p;
 220
 221    for (p = heap->next; p != heap; p = p->next) {
 222       if (p->ofs == start)
 223          return p;
 224    }
 225
 226    return NULL;
 227 }
 228
 229
 230 static inline int
 231 Join2Blocks(struct mem_block *p)
 232 {
 233    /* XXX there should be some assertions here */
 234
 235    /* NOTE: heap->free == 0 */
 236
 237    if (p->free && p->next->free) {
 238       struct mem_block *q = p->next;
 239
 240       assert(p->ofs + p->size == q->ofs);
 241       p->size += q->size;
 242
 243       p->next = q->next;
 244       q->next->prev = p;
 245
 246       q->next_free->prev_free = q->prev_free;
 247       q->prev_free->next_free = q->next_free;
 248
 249       FREE(q);
 250       return 1;
 251    }
 252    return 0;
 253 }
 254
 255 int
 256 u_mmFreeMem(struct mem_block *b)
 257 {
 258    if (!b)
 259       return 0;
 260
 261    if (b->free) {
 262       debug_printf("block already free\n");
 263       return -1;
 264    }
 265    if (b->reserved) {
 266       debug_printf("block is reserved\n");
 267       return -1;
 268    }
 269
 270    b->free = 1;
 271    b->next_free = b->heap->next_free;
 272    b->prev_free = b->heap;
 273    b->next_free->prev_free = b;
 274    b->prev_free->next_free = b;
 275
 276    Join2Blocks(b);
 277    if (b->prev != b->heap)
 278       Join2Blocks(b->prev);
 279
 280    return 0;
 281 }
 282
 283
 284 void
 285 u_mmDestroy(struct mem_block *heap)
 286 {
 287    struct mem_block *p;
 288
 289    if (!heap)
 290       return;
 291
 292    for (p = heap->next; p != heap; ) {
 293       struct mem_block *next = p->next;
 294       FREE(p);
 295       p = next;
 296    }
 297
 298    FREE(heap);
 299 }