1 /* 2 ** Copyright 2003, Axel Dörfler, axeld@pinc-software.de. All rights reserved. 3 ** Distributed under the terms of the OpenBeOS License. 4 */ 5 6 7 #include <boot/heap.h> 8 #include <boot/platform.h> 9 #include <util/kernel_cpp.h> 10 11 #ifdef HEAP_TEST 12 # include <stdio.h> 13 #endif 14 #include <stdlib.h> 15 #include <string.h> 16 17 18 /* This is a very simple malloc()/free() implementation - it only 19 * manages a free list. 20 * After heap_init() is called, all free memory is contained in one 21 * big chunk, the only entry in the free link list (which is a single 22 * linked list). 23 * When memory is allocated, the smallest free chunk that contains 24 * the requested size is split (or taken as a whole if it can't be 25 * splitted anymore), and it's lower half will be removed from the 26 * free list. 27 * The free list is ordered by size, starting with the smallest 28 * free chunk available. When a chunk is freed, it will be joint 29 * with its predecessor or successor, if possible. 30 * To ease list handling, the list anchor itself is a free chunk with 31 * size 0 that can't be allocated. 32 */ 33 34 35 struct free_chunk { 36 uint32 size; 37 free_chunk *next; 38 39 uint32 Size() const; 40 free_chunk *Split(uint32 splitSize); 41 bool IsTouching(free_chunk *link); 42 free_chunk *Join(free_chunk *link); 43 void Remove(free_chunk *previous = NULL); 44 void Enqueue(); 45 46 void *AllocatedAddress() const; 47 static free_chunk *SetToAllocated(void *allocated); 48 }; 49 50 51 static void *sHeapBase; 52 static uint32 /*sHeapSize,*/ sMaxHeapSize, sAvailable; 53 static free_chunk sFreeAnchor; 54 55 56 /** Returns the amount of bytes that can be allocated 57 * in this chunk. 58 */ 59 60 uint32 61 free_chunk::Size() const 62 { 63 return size - sizeof(uint32); 64 } 65 66 67 /** Splits the upper half at the requested location 68 * and returns it. 69 */ 70 71 free_chunk * 72 free_chunk::Split(uint32 splitSize) 73 { 74 free_chunk *chunk = (free_chunk *)((uint8 *)this + sizeof(uint32) + splitSize); 75 chunk->size = size - splitSize - sizeof(uint32); 76 chunk->next = next; 77 78 size = splitSize + sizeof(uint32); 79 80 return chunk; 81 } 82 83 84 /** Checks if the specified chunk touches this chunk, so 85 * that they could be joined. 86 */ 87 88 bool 89 free_chunk::IsTouching(free_chunk *chunk) 90 { 91 return chunk 92 && (((uint8 *)this + size == (uint8 *)chunk) 93 || (uint8 *)chunk + chunk->size == (uint8 *)this); 94 } 95 96 97 /** Joins the chunk to this chunk and returns the pointer 98 * to the new chunk - which will either be one of the 99 * two chunks. 100 * Note, the chunks must be joinable, or else this method 101 * doesn't work correctly. Use free_chunk::IsTouching() 102 * to check if this method can be applied. 103 */ 104 105 free_chunk * 106 free_chunk::Join(free_chunk *chunk) 107 { 108 if (chunk < this) { 109 chunk->size += size; 110 chunk->next = next; 111 112 return chunk; 113 } 114 115 size += chunk->size; 116 next = chunk->next; 117 118 return this; 119 } 120 121 122 void 123 free_chunk::Remove(free_chunk *previous) 124 { 125 if (previous == NULL) { 126 // find the previous chunk in the list 127 free_chunk *chunk = sFreeAnchor.next; 128 129 while (chunk != NULL && chunk != this) { 130 previous = chunk; 131 chunk = chunk->next; 132 } 133 134 if (chunk == NULL) 135 panic("try to remove chunk that's not in list"); 136 } 137 138 previous->next = this->next; 139 this->next = NULL; 140 } 141 142 143 void 144 free_chunk::Enqueue() 145 { 146 free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor; 147 while (chunk && chunk->Size() < size) { 148 last = chunk; 149 chunk = chunk->next; 150 } 151 152 this->next = chunk; 153 last->next = this; 154 } 155 156 157 void * 158 free_chunk::AllocatedAddress() const 159 { 160 return (void *)&next; 161 } 162 163 164 free_chunk * 165 free_chunk::SetToAllocated(void *allocated) 166 { 167 return (free_chunk *)((uint8 *)allocated - sizeof(uint32)); 168 } 169 170 171 // #pragma mark - 172 173 174 void 175 heap_release(stage2_args *args) 176 { 177 platform_release_heap(args, sHeapBase); 178 } 179 180 181 status_t 182 heap_init(stage2_args *args) 183 { 184 void *base, *top; 185 if (platform_init_heap(args, &base, &top) < B_OK) 186 return B_ERROR; 187 188 sHeapBase = base; 189 sMaxHeapSize = (uint8 *)top - (uint8 *)base; 190 sAvailable = sMaxHeapSize - sizeof(uint32); 191 192 // declare the whole heap as one chunk, and add it 193 // to the free list 194 195 free_chunk *chunk = (free_chunk *)base; 196 chunk->size = sMaxHeapSize; 197 chunk->next = NULL; 198 199 sFreeAnchor.size = 0; 200 sFreeAnchor.next = chunk; 201 202 return B_OK; 203 } 204 205 206 #if 0 207 char * 208 grow_heap(uint32 bytes) 209 { 210 char *start; 211 212 if (sHeapSize + bytes > sMaxHeapSize) 213 return NULL; 214 215 start = (char *)sHeapBase + sHeapSize; 216 memset(start, 0, bytes); 217 sHeapSize += bytes; 218 219 return start; 220 } 221 #endif 222 223 #ifdef HEAP_TEST 224 void 225 dump_chunks(void) 226 { 227 free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor; 228 while (chunk != NULL) { 229 last = chunk; 230 231 printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk, chunk->size, (uint8 *)chunk + chunk->size, chunk->next); 232 chunk = chunk->next; 233 } 234 } 235 #endif 236 237 uint32 238 heap_available(void) 239 { 240 return sAvailable; 241 } 242 243 244 void * 245 malloc(size_t size) 246 { 247 if (sHeapBase == NULL || size == 0) 248 return NULL; 249 250 // align the size requirement to a 4 bytes boundary 251 size = (size + 3) & 0xfffffffc; 252 253 if (size > sAvailable) 254 return NULL; 255 256 free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor; 257 while (chunk && chunk->Size() < size) { 258 last = chunk; 259 chunk = chunk->next; 260 } 261 262 if (chunk == NULL) { 263 // could not find a free chunk as large as needed 264 return NULL; 265 } 266 267 if (chunk->Size() > size + sizeof(free_chunk) + 4) { 268 // if this chunk is bigger than the requested size, 269 // we split it to form two chunks (with a minimal 270 // size of 4 allocatable bytes). 271 272 free_chunk *freeChunk = chunk->Split(size); 273 last->next = freeChunk; 274 275 // re-enqueue the free chunk at the correct position 276 freeChunk->Remove(last); 277 freeChunk->Enqueue(); 278 } else { 279 // remove the chunk from the free list 280 281 last->next = chunk->next; 282 } 283 284 sAvailable -= size + sizeof(uint32); 285 286 return chunk->AllocatedAddress(); 287 } 288 289 290 void * 291 realloc(void *oldBuffer, size_t newSize) 292 { 293 // ToDo: improve this implementation! 294 295 if (newSize == 0) { 296 free(oldBuffer); 297 return NULL; 298 } 299 300 void *newBuffer = malloc(newSize); 301 if (newBuffer == NULL) 302 return NULL; 303 304 if (oldBuffer) { 305 free_chunk *oldChunk = free_chunk::SetToAllocated(oldBuffer); 306 307 if (newSize > oldChunk->size) 308 newSize = oldChunk->size; 309 310 memcpy(newBuffer, oldBuffer, newSize); 311 free(oldBuffer); 312 } 313 314 return newBuffer; 315 } 316 317 318 void 319 free(void *allocated) 320 { 321 if (allocated == NULL) 322 return; 323 324 free_chunk *freedChunk = free_chunk::SetToAllocated(allocated); 325 sAvailable += freedChunk->size; 326 327 // try to join the new free chunk with an existing one 328 // it may be joined with up to two chunks 329 330 free_chunk *chunk = sFreeAnchor.next, *last = &sFreeAnchor; 331 int32 joinCount = 0; 332 333 while (chunk) { 334 if (chunk->IsTouching(freedChunk)) { 335 // almost "insert" it into the list before joining 336 // because the next pointer is inherited by the chunk 337 freedChunk->next = chunk->next; 338 freedChunk = chunk->Join(freedChunk); 339 340 // remove the joined chunk from the list 341 last->next = freedChunk->next; 342 chunk = last; 343 344 if (++joinCount == 2) 345 break; 346 } 347 348 last = chunk; 349 chunk = chunk->next; 350 } 351 352 // enqueue the link at the right position; the 353 // free link queue is ordered by size 354 355 freedChunk->Enqueue(); 356 } 357 358