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