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
  31
  32 void
  33 u_mmDumpMemInfo(const struct mem_block *heap)
  34 {
  35    debug_printf("Memory heap %p:\n", (void *) heap);
  36    if (heap == NULL) {
  37       debug_printf("  heap == 0\n");
  38    }
  39    else {
  40       const struct mem_block *p;
  41       int total_used = 0, total_free = 0;
  42
  43       for (p = heap->next; p != heap; p = p->next) {
  44          debug_printf("  Offset:%08x, Size:%08x, %c%c\n", p->ofs, p->size,
  45                       p->free ? 'F':'.',
  46                       p->reserved ? 'R':'.');
  47          if (p->free)
  48             total_free += p->size;
  49          else
  50             total_used += p->size;
  51       }
  52
  53       debug_printf("'\nMemory stats: total = %d, used = %d, free = %d\n",
  54                    total_used + total_free, total_used, total_free);
  55       debug_printf("\nFree list:\n");
  56
  57       for (p = heap->next_free; p != heap; p = p->next_free) {
  58          debug_printf(" FREE Offset:%08x, Size:%08x, %c%c\n", p->ofs, p->size,
  59                       p->free ? 'F':'.',
  60                       p->reserved ? 'R':'.');
  61       }
  62
  63    }
  64    debug_printf("End of memory blocks\n");
  65 }
  66
  67
  68 struct mem_block *
  69 u_mmInit(int ofs, int size)
  70 {
  71    struct mem_block *heap, *block;
  72
  73    if (size <= 0)
  74       return NULL;
  75
  76    heap = CALLOC_STRUCT(mem_block);
  77    if (!heap)
  78       return NULL;
  79
  80    block = CALLOC_STRUCT(mem_block);
  81    if (!block) {
  82       FREE(heap);
  83       return NULL;
  84    }
  85
  86    heap->next = block;
  87    heap->prev = block;
  88    heap->next_free = block;
  89    heap->prev_free = block;
  90
  91    block->heap = heap;
  92    block->next = heap;
  93    block->prev = heap;
  94    block->next_free = heap;
  95    block->prev_free = heap;
  96
  97    block->ofs = ofs;
  98    block->size = size;
  99    block->free = 1;
 100
 101    return heap;
 102 }
 103
 104
 105 static struct mem_block *
 106 SliceBlock(struct mem_block *p,
 107            int startofs, int size,
 108            int reserved, UNUSED int alignment)
 109 {
 110    struct mem_block *newblock;
 111
 112    /* break left  [p, newblock, p->next], then p = newblock */
 113    if (startofs > p->ofs) {
 114       newblock = CALLOC_STRUCT(mem_block);
 115       if (!newblock)
 116          return NULL;
 117       newblock->ofs = startofs;
 118       newblock->size = p->size - (startofs - p->ofs);
 119       newblock->free = 1;
 120       newblock->heap = p->heap;
 121
 122       newblock->next = p->next;
 123       newblock->prev = p;
 124       p->next->prev = newblock;
 125       p->next = newblock;
 126
 127       newblock->next_free = p->next_free;
 128       newblock->prev_free = p;
 129       p->next_free->prev_free = newblock;
 130       p->next_free = newblock;
 131
 132       p->size -= newblock->size;
 133       p = newblock;
 134    }
 135
 136    /* break right, also [p, newblock, p->next] */
 137    if (size < p->size) {
 138       newblock = CALLOC_STRUCT(mem_block);
 139       if (!newblock)
 140          return NULL;
 141       newblock->ofs = startofs + size;
 142       newblock->size = p->size - size;
 143       newblock->free = 1;
 144       newblock->heap = p->heap;
 145
 146       newblock->next = p->next;
 147       newblock->prev = p;
 148       p->next->prev = newblock;
 149       p->next = newblock;
 150
 151       newblock->next_free = p->next_free;
 152       newblock->prev_free = p;
 153       p->next_free->prev_free = newblock;
 154       p->next_free = newblock;
 155
 156       p->size = size;
 157    }
 158
 159    /* p = middle block */
 160    p->free = 0;
 161
 162    /* Remove p from the free list:
 163     */
 164    p->next_free->prev_free = p->prev_free;
 165    p->prev_free->next_free = p->next_free;
 166
 167    p->next_free = 0;
 168    p->prev_free = 0;
 169
 170    p->reserved = reserved;
 171    return p;
 172 }
 173
 174
 175 struct mem_block *
 176 u_mmAllocMem(struct mem_block *heap, int size, int align2, int startSearch)
 177 {
 178    struct mem_block *p;
 179    const int mask = (1 << align2)-1;
 180    int startofs = 0;
 181    int endofs;
 182
 183    assert(size >= 0);
 184    assert(align2 >= 0);
 185    /* Make sure that a byte alignment isn't getting passed for our
 186     * power-of-two alignment arg.
 187     */
 188    assert(align2 < 32);
 189
 190    if (!heap || align2 < 0 || size <= 0)
 191       return NULL;
 192
 193    for (p = heap->next_free; p != heap; p = p->next_free) {
 194       assert(p->free);
 195
 196       startofs = (p->ofs + mask) & ~mask;
 197       if ( startofs < startSearch ) {
 198          startofs = startSearch;
 199       }
 200       endofs = startofs+size;
 201       if (endofs <= (p->ofs+p->size))
 202          break;
 203    }
 204
 205    if (p == heap)
 206       return NULL;
 207
 208    assert(p->free);
 209    p = SliceBlock(p,startofs,size,0,mask+1);
 210
 211    return p;
 212 }
 213
 214
 215 struct mem_block *
 216 u_mmFindBlock(struct mem_block *heap, int start)
 217 {
 218    struct mem_block *p;
 219
 220    for (p = heap->next; p != heap; p = p->next) {
 221       if (p->ofs == start)
 222          return p;
 223    }
 224
 225    return NULL;
 226 }
 227
 228
 229 static inline int
 230 Join2Blocks(struct mem_block *p)
 231 {
 232    /* XXX there should be some assertions here */
 233
 234    /* NOTE: heap->free == 0 */
 235
 236    if (p->free && p->next->free) {
 237       struct mem_block *q = p->next;
 238
 239       assert(p->ofs + p->size == q->ofs);
 240       p->size += q->size;
 241
 242       p->next = q->next;
 243       q->next->prev = p;
 244
 245       q->next_free->prev_free = q->prev_free;
 246       q->prev_free->next_free = q->next_free;
 247
 248       FREE(q);
 249       return 1;
 250    }
 251    return 0;
 252 }
 253
 254 int
 255 u_mmFreeMem(struct mem_block *b)
 256 {
 257    if (!b)
 258       return 0;
 259
 260    if (b->free) {
 261       debug_printf("block already free\n");
 262       return -1;
 263    }
 264    if (b->reserved) {
 265       debug_printf("block is reserved\n");
 266       return -1;
 267    }
 268
 269    b->free = 1;
 270    b->next_free = b->heap->next_free;
 271    b->prev_free = b->heap;
 272    b->next_free->prev_free = b;
 273    b->prev_free->next_free = b;
 274
 275    Join2Blocks(b);
 276    if (b->prev != b->heap)
 277       Join2Blocks(b->prev);
 278
 279    return 0;
 280 }
 281
 282
 283 void
 284 u_mmDestroy(struct mem_block *heap)
 285 {
 286    struct mem_block *p;
 287
 288    if (!heap)
 289       return;
 290
 291    for (p = heap->next; p != heap; ) {
 292       struct mem_block *next = p->next;
 293       FREE(p);
 294       p = next;
 295    }
 296
 297    FREE(heap);
 298 }