src/mesa/main/mm.c

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