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