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