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