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