src/system/runtime_loader/heap.cpp

   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
  17 static 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
  37 struct 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
  53 static size_t sAvailable;
  54 static free_chunk sFreeAnchor;
  55
  56
  57 /** Returns the amount of bytes that can be allocated
  58  *      in this chunk.
  59  */
  60
  61 size_t
  62 free_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
  72 free_chunk *
  73 free_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
  89 bool
  90 free_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
 106 free_chunk *
 107 free_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
 123 void
 124 free_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
 146 void
 147 free_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
 160 void *
 161 free_chunk::AllocatedAddress() const
 162 {
 163         return (void *)&next;
 164 }
 165
 166
 167 free_chunk *
 168 free_chunk::SetToAllocated(void *allocated)
 169 {
 170         return (free_chunk *)((uint8 *)allocated - sizeof(size_t));
 171 }
 172
 173
 174 //      #pragma mark - private functions
 175
 176
 177 static status_t
 178 add_area(size_t size)
 179 {
 180         void *base;
 181         area_id area = _kern_create_area("rld heap", &base,
 182                 B_RANDOMIZED_ANY_ADDRESS, size, 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
 200 static status_t
 201 grow_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
 212 status_t
 213 heap_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
 225 void
 226 dump_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
 239 void *
 240 realloc(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
 268 void *
 269 malloc(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
 277 restart:
 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
 321 void
 322 free(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