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