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