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