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