1 /* 2 * Copyright 2006, Haiku Inc. 3 * Copyright 2002, Thomas Kurschel. 4 * 5 * Distributed under the terms of the MIT license. 6 */ 7 8 /** Memory manager used for graphics mem 9 * 10 * It has the following features 11 * - doesn't access memory to be managed 12 * - memory block's owner is identified by tag, 13 * tag is verified during free, and all memory 14 * belonging to one tag can be freed at once 15 * - multi-threading save 16 */ 17 18 #include "memory_manager.h" 19 20 #include <KernelExport.h> 21 #include <stdlib.h> 22 23 24 //#define TRACE_MEMORY_MANAGER 25 #ifdef TRACE_MEMORY_MANAGER 26 # define TRACE(x) dprintf x 27 #else 28 # define TRACE(x) ; 29 #endif 30 31 32 // allocated memory block 33 typedef struct mem_block { 34 struct mem_block *prev, *next; 35 uint32 base; 36 uint32 size; 37 void *tag; 38 bool allocated; 39 } mem_block; 40 41 // memory heap 42 struct mem_info { 43 mem_block *first; 44 area_id heap_area; 45 uint32 block_size; 46 sem_id lock; 47 mem_block *heap; 48 mem_block *unused; 49 uint32 heap_entries; 50 }; 51 52 53 /** merge "block" with successor */ 54 55 static void 56 merge(mem_info *mem, mem_block *block) 57 { 58 mem_block *next = block->next; 59 60 block->size += next->size; 61 62 if (next->next) 63 next->next->prev = block; 64 65 block->next = next->next; 66 next->next = mem->unused; 67 mem->unused = next; 68 } 69 70 71 /** free memory block including merge */ 72 73 static mem_block * 74 freeblock(mem_info *mem, mem_block *block) 75 { 76 mem_block *prev, *next; 77 78 block->allocated = false; 79 prev = block->prev; 80 81 if (prev && !prev->allocated) { 82 block = prev; 83 merge(mem, prev); 84 } 85 86 next = block->next; 87 88 if (next && !next->allocated) 89 merge(mem, block); 90 91 return block; 92 } 93 94 95 // #pragma mark - 96 97 98 /** Init memory manager. 99 * 100 * \param start start of address space 101 * \param length length of address space 102 * \param blockSize - granularity 103 * \param heapEntries - maximum number of blocks 104 */ 105 106 mem_info * 107 mem_init(const char* name, uint32 start, uint32 length, 108 uint32 blockSize, uint32 heapEntries) 109 { 110 mem_block *first; 111 mem_info *mem; 112 uint i; 113 uint32 size; 114 115 TRACE(("mem_init(name=%s, start=%lx, length=%lx, blockSize=%lx, heapEntries=%ld)\n", 116 name, start, length, blockSize, heapEntries)); 117 118 mem = malloc(sizeof(*mem)); 119 if (mem == NULL) 120 goto err1; 121 122 mem->block_size = blockSize; 123 mem->heap_entries = heapEntries; 124 mem->lock = create_sem(1, name); 125 if (mem->lock < 0) 126 goto err2; 127 128 // align size to B_PAGE_SIZE 129 size = heapEntries * sizeof(mem_block); 130 size = (size + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1); 131 132 mem->heap_area = create_area(name, (void **)&mem->heap, 133 B_ANY_ADDRESS, size, B_FULL_LOCK, B_READ_AREA | B_WRITE_AREA); 134 135 if (mem->heap_area < 0 || mem->heap == NULL) 136 goto err3; 137 138 for (i = 1; i < heapEntries; ++i) { 139 mem->heap[i - 1].next = &mem->heap[i]; 140 } 141 142 mem->heap[heapEntries - 1].next = NULL; 143 mem->unused = &mem->heap[1]; 144 145 first = &mem->heap[0]; 146 mem->first = first; 147 148 first->base = start; 149 first->size = length; 150 first->prev = first->next = NULL; 151 first->allocated = false; 152 153 return mem; 154 155 err3: 156 delete_sem(mem->lock); 157 err2: 158 free(mem); 159 err1: 160 return NULL; 161 } 162 163 164 /** destroy heap */ 165 166 void 167 mem_destroy(mem_info *mem) 168 { 169 TRACE(("mem_destroy(mem %p)\n", mem)); 170 171 delete_area(mem->heap_area); 172 delete_sem(mem->lock); 173 free(mem); 174 } 175 176 177 /** Allocate memory block 178 * 179 * \param mem heap handle 180 * \param size size in bytes 181 * \param tag owner tag 182 * 183 * \param blockID - returns block id 184 * \param offset - returns start address of block 185 */ 186 187 status_t 188 mem_alloc(mem_info *mem, uint32 size, void *tag, uint32 *blockID, uint32 *offset) 189 { 190 mem_block *current, *newEntry; 191 status_t status; 192 193 TRACE(("mem_alloc(mem %p, size=%lx, tag=%p)\n", mem, size, tag)); 194 195 status = acquire_sem(mem->lock); 196 if (status != B_OK) 197 return status; 198 199 // we assume block_size is power of two 200 size = (size + mem->block_size - 1) & ~(mem->block_size - 1); 201 202 // simple first fit 203 for (current = mem->first; current; current = current->next) { 204 if (!current->allocated && current->size >= size) 205 break; 206 } 207 208 if (current == NULL) { 209 TRACE(("mem_alloc: out of memory\n")); 210 goto err; 211 } 212 213 if (size != current->size) { 214 newEntry = mem->unused; 215 216 if (newEntry == NULL) { 217 TRACE(("mem_alloc: out of blocks\n")); 218 goto err; 219 } 220 221 mem->unused = newEntry->next; 222 223 newEntry->next = current->next; 224 newEntry->prev = current; 225 newEntry->allocated = false; 226 newEntry->base = current->base + size; 227 newEntry->size = current->size - size; 228 229 if (current->next) 230 current->next->prev = newEntry; 231 232 current->next = newEntry; 233 current->size = size; 234 } 235 236 current->allocated = true; 237 current->tag = tag; 238 239 *blockID = current - mem->heap + 1; 240 *offset = current->base; 241 242 release_sem(mem->lock); 243 244 TRACE(("mem_alloc(block_id=%ld, offset=%lx)\n", *blockID, *offset)); 245 return B_OK; 246 247 err: 248 release_sem(mem->lock); 249 return B_NO_MEMORY; 250 } 251 252 253 /** Free memory 254 * \param mem heap handle 255 * \param blockID block id 256 * \param tag owner tag (must match tag passed to mem_alloc()) 257 */ 258 259 status_t 260 mem_free(mem_info *mem, uint32 blockID, void *tag) 261 { 262 mem_block *block; 263 status_t status; 264 265 TRACE(("mem_free(mem %p, blockID=%ld, tag=%p)\n", mem, blockID, tag)); 266 267 status = acquire_sem(mem->lock); 268 if (status != B_OK) 269 return status; 270 271 --blockID; 272 273 if (blockID >= mem->heap_entries) { 274 TRACE(("mem_free: invalid ID %lu\n", blockID)); 275 goto err; 276 } 277 278 block = &mem->heap[blockID]; 279 if (!block->allocated || block->tag != tag) { 280 TRACE(("mem_free: not owner\n")); 281 goto err; 282 } 283 284 freeblock(mem, block); 285 286 release_sem(mem->lock); 287 return B_OK; 288 289 err: 290 release_sem(mem->lock); 291 return B_BAD_VALUE; 292 } 293 294 295 /** Free all memory belonging to owner "tag" */ 296 297 status_t 298 mem_freetag(mem_info *mem, void *tag) 299 { 300 mem_block *current; 301 status_t status; 302 303 TRACE(("mem_freetag(mem %p, tag=%p)\n", mem, tag)); 304 305 status = acquire_sem(mem->lock); 306 if (status != B_OK) 307 return status; 308 309 for (current = mem->first; current; current = current->next) { 310 if (current->allocated && current->tag == tag) 311 current = freeblock(mem, current); 312 } 313 314 release_sem(mem->lock); 315 return B_OK; 316 } 317