src/system/libroot/posix/malloc/arch-specific.cpp

   1 ///-*-C++-*-//////////////////////////////////////////////////////////////////
   2 //
   3 // Hoard: A Fast, Scalable, and Memory-Efficient Allocator
   4 //        for Shared-Memory Multiprocessors
   5 // Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
   6 //
   7 // Copyright (c) 1998-2000, The University of Texas at Austin.
   8 //
   9 // This library is free software; you can redistribute it and/or modify
  10 // it under the terms of the GNU Library General Public License as
  11 // published by the Free Software Foundation, http://www.fsf.org.
  12 //
  13 // This library is distributed in the hope that it will be useful, but
  14 // WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16 // Library General Public License for more details.
  17 //
  18 //////////////////////////////////////////////////////////////////////////////
  19
  20 #include "arch-specific.h"
  21 #include "heap.h"
  22
  23 #include <OS.h>
  24 #include <Debug.h>
  25 #include <syscalls.h>
  26
  27 #include <libroot_private.h>
  28
  29 #include <stdlib.h>
  30 #include <unistd.h>
  31
  32 //#define TRACE_CHUNKS
  33 #ifdef TRACE_CHUNKS
  34 #       define CTRACE(x) debug_printf x
  35 #else
  36 #       define CTRACE(x) ;
  37 #endif
  38
  39 using namespace BPrivate;
  40
  41 struct free_chunk {
  42         free_chunk      *next;
  43         size_t          size;
  44 };
  45
  46
  47 static const size_t kInitialHeapSize = 64 * B_PAGE_SIZE;
  48         // that's about what hoard allocates anyway (should be kHeapIncrement
  49         // aligned)
  50
  51 static const size_t kHeapIncrement = 16 * B_PAGE_SIZE;
  52         // the steps in which to increase the heap size (must be a power of 2)
  53
  54 #if B_HAIKU_64_BIT
  55 static const addr_t kHeapReservationBase = 0x1000000000;
  56 static const addr_t kHeapReservationSize = 0x1000000000;
  57 #else
  58 static const addr_t kHeapReservationBase = 0x18000000;
  59 static const addr_t kHeapReservationSize = 0x48000000;
  60 #endif
  61
  62 static area_id sHeapArea;
  63 static hoardLockType sHeapLock;
  64 static void *sHeapBase;
  65 static addr_t sFreeHeapBase;
  66 static size_t sFreeHeapSize, sHeapAreaSize;
  67 static free_chunk *sFreeChunks;
  68
  69
  70 void
  71 __init_after_fork(void)
  72 {
  73         // find the heap area
  74         sHeapArea = area_for((void*)sFreeHeapBase);
  75         if (sHeapArea < 0) {
  76                 // Where is it gone?
  77                 debug_printf("hoard: init_after_fork(): thread %" B_PRId32 ", Heap "
  78                         "area not found! Base address: %p\n", find_thread(NULL),
  79                         sHeapBase);
  80                 exit(1);
  81         }
  82 }
  83
  84
  85 extern "C" status_t
  86 __init_heap(void)
  87 {
  88         hoardHeap::initNumProcs();
  89
  90         // This will locate the heap base at 384 MB and reserve the next 1152 MB
  91         // for it. They may get reclaimed by other areas, though, but the maximum
  92         // size of the heap is guaranteed until the space is really needed.
  93         sHeapBase = (void *)kHeapReservationBase;
  94         status_t status = _kern_reserve_address_range((addr_t *)&sHeapBase,
  95                 B_RANDOMIZED_BASE_ADDRESS, kHeapReservationSize);
  96         if (status != B_OK)
  97                 sHeapBase = NULL;
  98
  99         uint32 protection = B_READ_AREA | B_WRITE_AREA;
 100         if (__gABIVersion < B_HAIKU_ABI_GCC_2_HAIKU)
 101                 protection |= B_EXECUTE_AREA;
 102         sHeapArea = create_area("heap", (void **)&sHeapBase,
 103                 status == B_OK ? B_EXACT_ADDRESS : B_RANDOMIZED_BASE_ADDRESS,
 104                 kInitialHeapSize, B_NO_LOCK, protection);
 105         if (sHeapArea < B_OK)
 106                 return sHeapArea;
 107
 108         sFreeHeapBase = (addr_t)sHeapBase;
 109         sHeapAreaSize = kInitialHeapSize;
 110
 111         hoardLockInit(sHeapLock, "heap");
 112
 113         return B_OK;
 114 }
 115
 116
 117 extern "C" void
 118 __heap_terminate_after()
 119 {
 120         // nothing to do
 121 }
 122
 123
 124 static void
 125 insert_chunk(free_chunk *newChunk)
 126 {
 127         free_chunk *chunk = (free_chunk *)sFreeChunks, *smaller = NULL;
 128         for (; chunk != NULL; chunk = chunk->next) {
 129                 if (chunk->size < newChunk->size)
 130                         smaller = chunk;
 131                 else
 132                         break;
 133         }
 134
 135         if (smaller) {
 136                 newChunk->next = smaller->next;
 137                 smaller->next = newChunk;
 138         } else {
 139                 newChunk->next = sFreeChunks;
 140                 sFreeChunks = newChunk;
 141         }
 142 }
 143
 144
 145 namespace BPrivate {
 146
 147 void *
 148 hoardSbrk(long size)
 149 {
 150         assert(size > 0);
 151         CTRACE(("sbrk: size = %ld\n", size));
 152
 153         // align size request
 154         size = (size + hoardHeap::ALIGNMENT - 1) & ~(hoardHeap::ALIGNMENT - 1);
 155
 156         // choose correct protection flags
 157         uint32 protection = B_READ_AREA | B_WRITE_AREA;
 158         if (__gABIVersion < B_HAIKU_ABI_GCC_2_HAIKU)
 159                 protection |= B_EXECUTE_AREA;
 160
 161         hoardLock(sHeapLock);
 162
 163         // find chunk in free list
 164         free_chunk *chunk = sFreeChunks, *last = NULL;
 165         for (; chunk != NULL; chunk = chunk->next) {
 166                 CTRACE(("  chunk %p (%ld)\n", chunk, chunk->size));
 167
 168                 if (chunk->size < (size_t)size) {
 169                         last = chunk;
 170                         continue;
 171                 }
 172
 173                 // this chunk is large enough to satisfy the request
 174
 175                 SERIAL_PRINT(("HEAP-%ld: found free chunk to hold %ld bytes\n",
 176                         find_thread(NULL), size));
 177
 178                 void *address = (void *)chunk;
 179
 180                 if (chunk->size > (size_t)size + sizeof(free_chunk)) {
 181                         // divide this chunk into smaller bits
 182                         size_t newSize = chunk->size - size;
 183                         free_chunk *next = chunk->next;
 184
 185                         chunk = (free_chunk *)((addr_t)chunk + size);
 186                         chunk->next = next;
 187                         chunk->size = newSize;
 188
 189                         if (last != NULL) {
 190                                 last->next = next;
 191                                 insert_chunk(chunk);
 192                         } else
 193                                 sFreeChunks = chunk;
 194                 } else {
 195                         chunk = chunk->next;
 196
 197                         if (last != NULL)
 198                                 last->next = chunk;
 199                         else
 200                                 sFreeChunks = chunk;
 201                 }
 202
 203                 hoardUnlock(sHeapLock);
 204                 return address;
 205         }
 206
 207         // There was no chunk, let's see if the area is large enough
 208
 209         size_t oldHeapSize = sFreeHeapSize;
 210         sFreeHeapSize += size;
 211
 212         // round to next heap increment aligned size
 213         size_t incrementAlignedSize = (sFreeHeapSize + kHeapIncrement - 1)
 214                 & ~(kHeapIncrement - 1);
 215
 216         if (incrementAlignedSize <= sHeapAreaSize) {
 217                 SERIAL_PRINT(("HEAP-%ld: heap area large enough for %ld\n",
 218                         find_thread(NULL), size));
 219                 // the area is large enough already
 220                 hoardUnlock(sHeapLock);
 221                 return (void *)(sFreeHeapBase + oldHeapSize);
 222         }
 223
 224         // We need to grow the area
 225
 226         SERIAL_PRINT(("HEAP-%ld: need to resize heap area to %ld (%ld requested)\n",
 227                 find_thread(NULL), incrementAlignedSize, size));
 228
 229         status_t status = resize_area(sHeapArea, incrementAlignedSize);
 230         if (status != B_OK) {
 231                 // Either the system is out of memory or another area is in the way and
 232                 // prevents ours from being resized. As a special case of the latter
 233                 // the user might have mmap()ed something over malloc()ed memory. This
 234                 // splits the heap area in two, the first one retaining the original
 235                 // area ID. In either case, if there's still memory, it is a good idea
 236                 // to try and allocate a new area.
 237                 sFreeHeapSize = oldHeapSize;
 238
 239                 if (status == B_NO_MEMORY) {
 240                         hoardUnlock(sHeapLock);
 241                         return NULL;
 242                 }
 243
 244                 size_t newHeapSize = (size + kHeapIncrement - 1) / kHeapIncrement
 245                         * kHeapIncrement;
 246
 247                 // First try at the location directly after the current heap area, if
 248                 // that is still in the reserved memory region.
 249                 void* base = (void*)(sFreeHeapBase + sHeapAreaSize);
 250                 area_id area = -1;
 251                 if (sHeapBase != NULL
 252                         && base >= sHeapBase
 253                         && (addr_t)base + newHeapSize
 254                                 <= (addr_t)sHeapBase + kHeapReservationSize) {
 255                         area = create_area("heap", &base, B_EXACT_ADDRESS, newHeapSize,
 256                                 B_NO_LOCK, protection);
 257
 258                         if (area == B_NO_MEMORY) {
 259                                 hoardUnlock(sHeapLock);
 260                                 return NULL;
 261                         }
 262                 }
 263
 264                 // If we don't have an area yet, try again with a free location
 265                 // allocation.
 266                 if (area < 0) {
 267                         base = (void*)(sFreeHeapBase + sHeapAreaSize);
 268                         area = create_area("heap", &base, B_RANDOMIZED_BASE_ADDRESS,
 269                                 newHeapSize, B_NO_LOCK, protection);
 270                 }
 271
 272                 if (area < 0) {
 273                         hoardUnlock(sHeapLock);
 274                         return NULL;
 275                 }
 276
 277                 // We have a new area, so make it the new heap area.
 278                 sHeapArea = area;
 279                 sFreeHeapBase = (addr_t)base;
 280                 sHeapAreaSize = newHeapSize;
 281                 sFreeHeapSize = size;
 282                 oldHeapSize = 0;
 283         } else
 284                 sHeapAreaSize = incrementAlignedSize;
 285
 286         hoardUnlock(sHeapLock);
 287         return (void *)(sFreeHeapBase + oldHeapSize);
 288 }
 289
 290
 291 void
 292 hoardUnsbrk(void *ptr, long size)
 293 {
 294         CTRACE(("unsbrk: %p, %ld!\n", ptr, size));
 295
 296         hoardLock(sHeapLock);
 297
 298         // TODO: hoard always allocates and frees in typical sizes, so we could
 299         //      save a lot of effort if we just had a similar mechanism
 300
 301         // We add this chunk to our free list - first, try to find an adjacent
 302         // chunk, so that we can merge them together
 303
 304         free_chunk *chunk = (free_chunk *)sFreeChunks, *last = NULL, *smaller = NULL;
 305         for (; chunk != NULL; chunk = chunk->next) {
 306                 if ((addr_t)chunk + chunk->size == (addr_t)ptr
 307                         || (addr_t)ptr + size == (addr_t)chunk) {
 308                         // chunks are adjacent - merge them
 309
 310                         CTRACE(("  found adjacent chunks: %p, %ld\n", chunk, chunk->size));
 311                         if (last)
 312                                 last->next = chunk->next;
 313                         else
 314                                 sFreeChunks = chunk->next;
 315
 316                         if ((addr_t)chunk < (addr_t)ptr)
 317                                 chunk->size += size;
 318                         else {
 319                                 free_chunk *newChunk = (free_chunk *)ptr;
 320                                 newChunk->next = chunk->next;
 321                                 newChunk->size = size + chunk->size;
 322                                 chunk = newChunk;
 323                         }
 324
 325                         insert_chunk(chunk);
 326                         hoardUnlock(sHeapLock);
 327                         return;
 328                 }
 329
 330                 last = chunk;
 331
 332                 if (chunk->size < (size_t)size)
 333                         smaller = chunk;
 334         }
 335
 336         // we didn't find an adjacent chunk, so insert the new chunk into the list
 337
 338         free_chunk *newChunk = (free_chunk *)ptr;
 339         newChunk->size = size;
 340         if (smaller) {
 341                 newChunk->next = smaller->next;
 342                 smaller->next = newChunk;
 343         } else {
 344                 newChunk->next = sFreeChunks;
 345                 sFreeChunks = newChunk;
 346         }
 347
 348         hoardUnlock(sHeapLock);
 349 }
 350
 351
 352 void
 353 hoardLockInit(hoardLockType &lock, const char *name)
 354 {
 355         mutex_init_etc(&lock, name, MUTEX_FLAG_ADAPTIVE);
 356 }
 357
 358
 359 void
 360 hoardLock(hoardLockType &lock)
 361 {
 362         mutex_lock(&lock);
 363 }
 364
 365
 366 void
 367 hoardUnlock(hoardLockType &lock)
 368 {
 369         mutex_unlock(&lock);
 370 }
 371
 372
 373 void
 374 hoardYield(void)
 375 {
 376         _kern_thread_yield();
 377 }
 378
 379 }       // namespace BPrivate