1 /* 2 * Copyright 2003-2009, Axel Dörfler, axeld@pinc-software.de. 3 * Distributed under the terms of the MIT 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 //#define TRACE_HEAP 19 #ifdef TRACE_HEAP 20 # define TRACE(format...) dprintf(format) 21 #else 22 # define TRACE(format...) do { } while (false) 23 #endif 24 25 26 /*! This is a very simple malloc()/free() implementation - it only 27 manages a free list. 28 After heap_init() is called, all free memory is contained in one 29 big chunk, the only entry in the free link list (which is a single 30 linked list). 31 When memory is allocated, the smallest free chunk that contains 32 the requested size is split (or taken as a whole if it can't be 33 splitted anymore), and it's lower half will be removed from the 34 free list. 35 The free list is ordered by size, starting with the smallest 36 free chunk available. When a chunk is freed, it will be joint 37 with its predecessor or successor, if possible. 38 To ease list handling, the list anchor itself is a free chunk with 39 size 0 that can't be allocated. 40 */ 41 42 #define DEBUG_ALLOCATIONS 43 // if defined, freed memory is filled with 0xcc 44 45 class FreeChunk { 46 public: 47 void SetTo(size_t size, FreeChunk* next); 48 49 uint32 Size() const; 50 uint32 CompleteSize() const { return fSize; } 51 52 FreeChunk* Next() const { return fNext; } 53 void SetNext(FreeChunk* next) { fNext = next; } 54 55 FreeChunk* Split(uint32 splitSize); 56 bool IsTouching(FreeChunk* link); 57 FreeChunk* Join(FreeChunk* link); 58 void Remove(FreeChunk* previous = NULL); 59 void Enqueue(); 60 61 void* AllocatedAddress() const; 62 static FreeChunk* SetToAllocated(void* allocated); 63 static addr_t NextOffset() { return sizeof(uint32); } 64 65 private: 66 uint32 fSize; 67 FreeChunk* fNext; 68 }; 69 70 71 const static uint32 kAlignment = 4; 72 // all memory chunks will be a multiple of this 73 74 static void* sHeapBase; 75 static uint32 /*sHeapSize,*/ sMaxHeapSize, sAvailable; 76 static FreeChunk sFreeAnchor; 77 78 79 void 80 FreeChunk::SetTo(size_t size, FreeChunk* next) 81 { 82 fSize = size; 83 fNext = next; 84 } 85 86 87 /*! Returns the amount of bytes that can be allocated 88 in this chunk. 89 */ 90 uint32 91 FreeChunk::Size() const 92 { 93 return fSize - FreeChunk::NextOffset(); 94 } 95 96 97 /*! Splits the upper half at the requested location 98 and returns it. 99 */ 100 FreeChunk* 101 FreeChunk::Split(uint32 splitSize) 102 { 103 splitSize = (splitSize - 1 + kAlignment) & ~(kAlignment - 1); 104 105 FreeChunk* chunk 106 = (FreeChunk*)((uint8*)this + FreeChunk::NextOffset() + splitSize); 107 chunk->fSize = fSize - splitSize - FreeChunk::NextOffset(); 108 chunk->fNext = fNext; 109 110 fSize = splitSize + FreeChunk::NextOffset(); 111 112 return chunk; 113 } 114 115 116 /*! Checks if the specified chunk touches this chunk, so 117 that they could be joined. 118 */ 119 bool 120 FreeChunk::IsTouching(FreeChunk* chunk) 121 { 122 return chunk 123 && (((uint8*)this + fSize == (uint8*)chunk) 124 || (uint8*)chunk + chunk->fSize == (uint8*)this); 125 } 126 127 128 /*! Joins the chunk to this chunk and returns the pointer 129 to the new chunk - which will either be one of the 130 two chunks. 131 Note, the chunks must be joinable, or else this method 132 doesn't work correctly. Use FreeChunk::IsTouching() 133 to check if this method can be applied. 134 */ 135 FreeChunk* 136 FreeChunk::Join(FreeChunk* chunk) 137 { 138 if (chunk < this) { 139 chunk->fSize += fSize; 140 chunk->fNext = fNext; 141 142 return chunk; 143 } 144 145 fSize += chunk->fSize; 146 fNext = chunk->fNext; 147 148 return this; 149 } 150 151 152 void 153 FreeChunk::Remove(FreeChunk* previous) 154 { 155 if (previous == NULL) { 156 // find the previous chunk in the list 157 FreeChunk* chunk = sFreeAnchor.fNext; 158 159 while (chunk != NULL && chunk != this) { 160 previous = chunk; 161 chunk = chunk->fNext; 162 } 163 164 if (chunk == NULL) 165 panic("try to remove chunk that's not in list"); 166 } 167 168 previous->fNext = fNext; 169 fNext = NULL; 170 } 171 172 173 void 174 FreeChunk::Enqueue() 175 { 176 FreeChunk* chunk = sFreeAnchor.fNext; 177 FreeChunk* last = &sFreeAnchor; 178 while (chunk && chunk->Size() < fSize) { 179 last = chunk; 180 chunk = chunk->fNext; 181 } 182 183 fNext = chunk; 184 last->fNext = this; 185 186 #ifdef DEBUG_ALLOCATIONS 187 memset((uint8*)this + sizeof(FreeChunk), 0xde, 188 fSize - sizeof(FreeChunk)); 189 #endif 190 } 191 192 193 void* 194 FreeChunk::AllocatedAddress() const 195 { 196 return (void*)&fNext; 197 } 198 199 200 FreeChunk* 201 FreeChunk::SetToAllocated(void* allocated) 202 { 203 return (FreeChunk*)((uint8*)allocated - FreeChunk::NextOffset()); 204 } 205 206 207 // #pragma mark - 208 209 210 void 211 heap_release(stage2_args* args) 212 { 213 platform_release_heap(args, sHeapBase); 214 } 215 216 217 status_t 218 heap_init(stage2_args* args) 219 { 220 void* base; 221 void* top; 222 if (platform_init_heap(args, &base, &top) < B_OK) 223 return B_ERROR; 224 225 sHeapBase = base; 226 sMaxHeapSize = (uint8*)top - (uint8*)base; 227 sAvailable = sMaxHeapSize - FreeChunk::NextOffset(); 228 229 // declare the whole heap as one chunk, and add it 230 // to the free list 231 232 FreeChunk* chunk = (FreeChunk*)base; 233 chunk->SetTo(sMaxHeapSize, NULL); 234 sFreeAnchor.SetTo(0, chunk); 235 236 return B_OK; 237 } 238 239 240 #if 0 241 char* 242 grow_heap(uint32 bytes) 243 { 244 char* start; 245 246 if (sHeapSize + bytes > sMaxHeapSize) 247 return NULL; 248 249 start = (char*)sHeapBase + sHeapSize; 250 memset(start, 0, bytes); 251 sHeapSize += bytes; 252 253 return start; 254 } 255 #endif 256 257 #ifdef HEAP_TEST 258 void 259 dump_chunks(void) 260 { 261 FreeChunk* chunk = sFreeAnchor.Next(); 262 FreeChunk* last = &sFreeAnchor; 263 while (chunk != NULL) { 264 last = chunk; 265 266 printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk, 267 chunk->Size(), (uint8*)chunk + chunk->CompleteSize(), 268 chunk->Next()); 269 chunk = chunk->Next(); 270 } 271 } 272 #endif 273 274 uint32 275 heap_available(void) 276 { 277 return sAvailable; 278 } 279 280 281 void* 282 malloc(size_t size) 283 { 284 if (sHeapBase == NULL || size == 0) 285 return NULL; 286 287 // align the size requirement to a kAlignment bytes boundary 288 size = (size - 1 + kAlignment) & ~(size_t)(kAlignment - 1); 289 290 if (size > sAvailable) { 291 dprintf("malloc(): Out of memory!\n"); 292 return NULL; 293 } 294 295 FreeChunk* chunk = sFreeAnchor.Next(); 296 FreeChunk* last = &sFreeAnchor; 297 while (chunk && chunk->Size() < size) { 298 last = chunk; 299 chunk = chunk->Next(); 300 } 301 302 if (chunk == NULL) { 303 // could not find a free chunk as large as needed 304 dprintf("malloc(): Out of memory!\n"); 305 return NULL; 306 } 307 308 if (chunk->Size() > size + sizeof(FreeChunk) + kAlignment) { 309 // if this chunk is bigger than the requested size, 310 // we split it to form two chunks (with a minimal 311 // size of kAlignment allocatable bytes). 312 313 FreeChunk* freeChunk = chunk->Split(size); 314 last->SetNext(freeChunk); 315 316 // re-enqueue the free chunk at the correct position 317 freeChunk->Remove(last); 318 freeChunk->Enqueue(); 319 } else { 320 // remove the chunk from the free list 321 322 last->SetNext(chunk->Next()); 323 } 324 325 sAvailable -= size + sizeof(uint32); 326 327 TRACE("malloc(%lu) -> %p\n", size, chunk->AllocatedAddress()); 328 return chunk->AllocatedAddress(); 329 } 330 331 332 void* 333 realloc(void* oldBuffer, size_t newSize) 334 { 335 if (newSize == 0) { 336 TRACE("realloc(%p, %lu) -> NULL\n", oldBuffer, newSize); 337 free(oldBuffer); 338 return NULL; 339 } 340 341 size_t copySize = newSize; 342 if (oldBuffer != NULL) { 343 FreeChunk* oldChunk = FreeChunk::SetToAllocated(oldBuffer); 344 345 // Check if the old buffer still fits, and if it makes sense to keep it 346 if (oldChunk->Size() >= newSize 347 && (oldChunk->Size() < 128 || newSize > oldChunk->Size() / 3)) { 348 TRACE("realloc(%p, %lu) old buffer is large enough\n", 349 oldBuffer, newSize); 350 return oldChunk->AllocatedAddress(); 351 } 352 353 if (copySize > oldChunk->Size()) 354 copySize = oldChunk->Size(); 355 } 356 357 void* newBuffer = malloc(newSize); 358 if (newBuffer == NULL) 359 return NULL; 360 361 if (oldBuffer != NULL) { 362 memcpy(newBuffer, oldBuffer, copySize); 363 free(oldBuffer); 364 } 365 366 TRACE("realloc(%p, %lu) -> %p\n", oldBuffer, newSize, newBuffer); 367 return newBuffer; 368 } 369 370 371 void 372 free(void* allocated) 373 { 374 if (allocated == NULL) 375 return; 376 377 TRACE("free(%p)\n", allocated); 378 379 FreeChunk* freedChunk = FreeChunk::SetToAllocated(allocated); 380 381 #ifdef DEBUG_ALLOCATIONS 382 if (freedChunk->CompleteSize() > sMaxHeapSize) { 383 panic("freed chunk %p clobbered (%lx)!\n", freedChunk, 384 freedChunk->Size()); 385 } 386 { 387 FreeChunk* chunk = sFreeAnchor.Next(); 388 while (chunk) { 389 if (chunk->CompleteSize() > sMaxHeapSize || freedChunk == chunk) 390 panic("invalid chunk in free list, or double free\n"); 391 chunk = chunk->Next(); 392 } 393 } 394 #endif 395 396 sAvailable += freedChunk->CompleteSize(); 397 398 // try to join the new free chunk with an existing one 399 // it may be joined with up to two chunks 400 401 FreeChunk* chunk = sFreeAnchor.Next(); 402 FreeChunk* last = &sFreeAnchor; 403 int32 joinCount = 0; 404 405 while (chunk) { 406 if (chunk->IsTouching(freedChunk)) { 407 // almost "insert" it into the list before joining 408 // because the next pointer is inherited by the chunk 409 freedChunk->SetNext(chunk->Next()); 410 freedChunk = chunk->Join(freedChunk); 411 412 // remove the joined chunk from the list 413 last->SetNext(freedChunk->Next()); 414 chunk = last; 415 416 if (++joinCount == 2) 417 break; 418 } 419 420 last = chunk; 421 chunk = chunk->Next(); 422 } 423 424 // enqueue the link at the right position; the 425 // free link queue is ordered by size 426 427 freedChunk->Enqueue(); 428 } 429 430