src/system/libroot/posix/malloc/heap.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 "config.h"
  21
  22 #include "heap.h"
  23 #include "processheap.h"
  24 #include "superblock.h"
  25
  26 using namespace BPrivate;
  27
  28 // NB: Use maketable.cpp to update this
  29 //     if SIZE_CLASSES, ALIGNMENT, SIZE_CLASS_BASE, MAX_EMPTY_SUPERBLOCKS,
  30 //     or SUPERBLOCK_SIZE changes.
  31
  32 #if (MAX_INTERNAL_FRAGMENTATION == 2)
  33
  34 size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {
  35         8UL, 16UL, 24UL, 32UL, 40UL, 48UL, 56UL, 72UL, 80UL, 96UL, 120UL, 144UL,
  36         168UL, 200UL, 240UL, 288UL, 344UL, 416UL, 496UL, 592UL, 712UL, 856UL,
  37         1024UL, 1232UL, 1472UL, 1768UL, 2120UL, 2544UL, 3048UL, 3664UL,
  38         4392UL, 5272UL, 6320UL, 7584UL, 9104UL, 10928UL, 13112UL, 15728UL,
  39         18872UL, 22648UL, 27176UL, 32616UL, 39136UL, 46960UL, 56352UL,
  40         67624UL, 81144UL, 97376UL, 116848UL, 140216UL, 168256UL, 201904UL,
  41         242288UL, 290744UL, 348896UL, 418672UL, 502408UL, 602888UL, 723464UL,
  42         868152UL, 1041784UL, 1250136UL, 1500160UL, 1800192UL, 2160232UL,
  43         2592280UL, 3110736UL, 3732880UL, 4479456UL, 5375344UL, 6450408UL,
  44         7740496UL, 9288592UL, 11146312UL, 13375568UL, 16050680UL, 19260816UL,
  45         23112984UL, 27735576UL, 33282688UL, 39939224UL, 47927072UL,
  46         57512488UL, 69014984UL, 82817976UL, 99381576UL, 119257888UL,
  47         143109472UL, 171731360UL, 206077632UL, 247293152UL, 296751776UL,
  48         356102144UL, 427322560UL, 512787072UL, 615344512UL, 738413376UL,
  49         886096064UL, 1063315264UL
  50 };
  51
  52 size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {
  53         4096UL, 2048UL, 1364UL, 1024UL, 816UL, 680UL, 584UL, 452UL, 408UL,
  54         340UL, 272UL, 224UL, 192UL, 160UL, 136UL, 112UL, 92UL, 76UL, 64UL,
  55         52UL, 44UL, 36UL, 32UL, 24UL, 20UL, 16UL, 12UL, 12UL, 8UL, 8UL, 4UL,
  56         4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL,
  57         4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL,
  58         4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL,
  59         4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL,
  60         4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL
  61 };
  62
  63 #elif (MAX_INTERNAL_FRAGMENTATION == 6)
  64
  65 size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {
  66         8UL, 16UL, 24UL, 32UL, 48UL, 72UL, 112UL, 176UL, 288UL, 456UL, 728UL,
  67         1160UL, 1848UL, 2952UL, 4728UL, 7560UL, 12096UL, 19344UL, 30952UL,
  68         49520UL, 79232UL, 126768UL, 202832UL, 324520UL, 519232UL, 830768UL,
  69         1329232UL, 2126768UL, 3402824UL, 5444520UL, 8711232UL, 13937968UL,
  70         22300752UL, 35681200UL, 57089912UL, 91343856UL, 146150176UL,
  71         233840256UL, 374144416UL, 598631040UL, 957809728UL, 1532495488UL
  72 };
  73
  74 size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {
  75         4096UL, 2048UL, 1364UL, 1024UL, 680UL, 452UL, 292UL, 184UL, 112UL, 68UL,
  76         44UL, 28UL, 16UL, 8UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL,
  77         4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL,
  78         4UL, 4UL, 4UL, 4UL, 4UL
  79 };
  80
  81 #elif (MAX_INTERNAL_FRAGMENTATION == 10)
  82
  83 size_t hoardHeap::_sizeTable[hoardHeap::SIZE_CLASSES] = {
  84         8UL, 16UL, 32UL, 64UL, 128UL, 256UL, 512UL, 1024UL, 2048UL, 4096UL,
  85         8192UL, 16384UL, 32768UL, 65536UL, 131072UL, 262144UL, 524288UL,
  86         1048576UL, 2097152UL, 4194304UL, 8388608UL, 16777216UL, 33554432UL,
  87         67108864UL, 134217728UL, 268435456UL, 536870912UL, 1073741824UL,
  88         2147483648UL
  89 };
  90
  91 size_t hoardHeap::_threshold[hoardHeap::SIZE_CLASSES] = {
  92         4096UL, 2048UL, 1024UL, 512UL, 256UL, 128UL, 64UL, 32UL, 16UL, 8UL, 4UL,
  93         4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL, 4UL,
  94         4UL, 4UL, 4UL, 4UL
  95 };
  96
  97 #else
  98 #       error "Undefined size class base."
  99 #endif
 100
 101
 102 int hoardHeap::fMaxThreadHeaps = 1;
 103 int hoardHeap::_numProcessors;
 104 int hoardHeap::_numProcessorsMask;
 105
 106
 107 // Return ceil(log_2(num)).
 108 // num must be positive.
 109
 110 static int
 111 lg(int num)
 112 {
 113         assert(num > 0);
 114         int power = 0;
 115         int n = 1;
 116         // Invariant: 2^power == n.
 117         while (n < num) {
 118                 n <<= 1;
 119                 power++;
 120         }
 121         return power;
 122 }
 123
 124
 125 //      #pragma mark -
 126
 127
 128 hoardHeap::hoardHeap(void)
 129         :
 130         _index(0), _reusableSuperblocks(NULL), _reusableSuperblocksCount(0)
 131 #if HEAP_DEBUG
 132         , _magic(HEAP_MAGIC)
 133 #endif
 134 {
 135         initLock();
 136
 137         for (int i = 0; i < SUPERBLOCK_FULLNESS_GROUP; i++) {
 138                 for (int j = 0; j < SIZE_CLASSES; j++) {
 139                         // Initialize all superblocks lists to empty.
 140                         _superblocks[i][j] = NULL;
 141                 }
 142         }
 143
 144         for (int k = 0; k < SIZE_CLASSES; k++) {
 145                 _leastEmptyBin[k] = 0;
 146         }
 147 }
 148
 149
 150 void
 151 hoardHeap::insertSuperblock(int sizeclass,
 152         superblock *sb, processHeap *pHeap)
 153 {
 154         assert(sb->isValid());
 155         assert(sb->getBlockSizeClass() == sizeclass);
 156         assert(sb->getPrev() == NULL);
 157         assert(sb->getNext() == NULL);
 158         assert(_magic == HEAP_MAGIC);
 159
 160         // Now it's ours.
 161         sb->setOwner(this);
 162
 163         // How full is this superblock?  We'll use this information to put
 164         // it into the right 'bin'.
 165         sb->computeFullness();
 166         int fullness = sb->getFullness();
 167
 168         // Update the stats.
 169         incStats(sizeclass, sb->getNumBlocks() - sb->getNumAvailable(),
 170                 sb->getNumBlocks());
 171
 172         if (fullness == 0
 173                 && sb->getNumBlocks() > 1
 174                 && sb->getNumBlocks() == sb->getNumAvailable()) {
 175                 // Recycle this superblock.
 176 #if 0
 177                 removeSuperblock(sb, sizeclass);
 178                 // Update the stats.
 179                 decStats(sizeclass,
 180                                  sb->getNumBlocks() - sb->getNumAvailable(), sb->getNumBlocks());
 181                 // Free it immediately.
 182                 const size_t s = sizeFromClass(sizeclass);
 183                 const int blksize = align(sizeof(block) + s);
 184 #if HEAP_LOG
 185                 // Record the memory deallocation.
 186                 MemoryRequest m;
 187                 m.deallocate((int)sb->getNumBlocks() *
 188                                          (int)sizeFromClass(sb->getBlockSizeClass()));
 189                 pHeap->getLog(getIndex()).append(m);
 190 #endif
 191 #if HEAP_FRAG_STATS
 192
 193                 pHeap->setDeallocated(0, sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
 194 #endif
 195
 196                 hoardUnsbrk(sb, align(sizeof(superblock) + blksize));
 197 #else
 198                 recycle(sb);
 199 #endif
 200         } else {
 201                 // Insert it into the appropriate list.
 202                 superblock *&head = _superblocks[fullness][sizeclass];
 203                 sb->insertBefore(head);
 204                 head = sb;
 205                 assert(head->isValid());
 206
 207                 // Reset the least-empty bin counter.
 208                 _leastEmptyBin[sizeclass] = RESET_LEAST_EMPTY_BIN;
 209         }
 210 }
 211
 212
 213 superblock *
 214 hoardHeap::removeMaxSuperblock(int sizeclass)
 215 {
 216         assert(_magic == HEAP_MAGIC);
 217
 218         superblock *head = NULL;
 219
 220         // First check the reusable superblocks list.
 221
 222         head = reuse(sizeclass);
 223         if (head) {
 224                 // We found one. Since we're removing this superblock, update the
 225                 // stats accordingly.
 226                 decStats(sizeclass,
 227                         head->getNumBlocks() - head->getNumAvailable(),
 228                         head->getNumBlocks());
 229
 230                 return head;
 231         }
 232
 233         // Instead of finding the superblock with the most available space
 234         // (something that would either involve a linear scan through the
 235         // superblocks or maintaining the superblocks in sorted order), we
 236         // just pick one that is no more than
 237         // 1/(SUPERBLOCK_FULLNESS_GROUP-1) more full than the superblock
 238         // with the most available space.  We start with the emptiest group.
 239
 240         int i = 0;
 241
 242         // Note: the last group (SUPERBLOCK_FULLNESS_GROUP - 1) is full, so
 243         // we never need to check it. But for robustness, we leave it in.
 244         while (i < SUPERBLOCK_FULLNESS_GROUP) {
 245                 head = _superblocks[i][sizeclass];
 246                 if (head)
 247                         break;
 248
 249                 i++;
 250         }
 251
 252         if (!head)
 253                 return NULL;
 254
 255         // Make sure that this superblock is at least 1/EMPTY_FRACTION
 256         // empty.
 257         assert(head->getNumAvailable() * EMPTY_FRACTION >= head->getNumBlocks());
 258
 259         removeSuperblock(head, sizeclass);
 260
 261         assert(head->isValid());
 262         assert(head->getPrev() == NULL);
 263         assert(head->getNext() == NULL);
 264         return head;
 265 }
 266
 267
 268 void
 269 hoardHeap::removeSuperblock(superblock *sb, int sizeclass)
 270 {
 271         assert(_magic == HEAP_MAGIC);
 272
 273         assert(sb->isValid());
 274         assert(sb->getOwner() == this);
 275         assert(sb->getBlockSizeClass() == sizeclass);
 276
 277         for (int i = 0; i < SUPERBLOCK_FULLNESS_GROUP; i++) {
 278                 if (sb == _superblocks[i][sizeclass]) {
 279                         _superblocks[i][sizeclass] = sb->getNext();
 280                         if (_superblocks[i][sizeclass] != NULL) {
 281                                 assert(_superblocks[i][sizeclass]->isValid());
 282                         }
 283                         break;
 284                 }
 285         }
 286
 287         sb->remove();
 288         decStats(sizeclass, sb->getNumBlocks() - sb->getNumAvailable(),
 289                 sb->getNumBlocks());
 290 }
 291
 292
 293 void
 294 hoardHeap::moveSuperblock(superblock *sb,
 295         int sizeclass, int fromBin, int toBin)
 296 {
 297         assert(_magic == HEAP_MAGIC);
 298         assert(sb->isValid());
 299         assert(sb->getOwner() == this);
 300         assert(sb->getBlockSizeClass() == sizeclass);
 301         assert(sb->getFullness() == toBin);
 302
 303         // Remove the superblock from the old bin.
 304
 305         superblock *&oldHead = _superblocks[fromBin][sizeclass];
 306         if (sb == oldHead) {
 307                 oldHead = sb->getNext();
 308                 if (oldHead != NULL) {
 309                         assert(oldHead->isValid());
 310                 }
 311         }
 312
 313         sb->remove();
 314
 315         // Insert the superblock into the new bin.
 316
 317         superblock *&newHead = _superblocks[toBin][sizeclass];
 318         sb->insertBefore(newHead);
 319         newHead = sb;
 320         assert(newHead->isValid());
 321
 322         // Reset the least-empty bin counter.
 323         _leastEmptyBin[sizeclass] = RESET_LEAST_EMPTY_BIN;
 324 }
 325
 326
 327 // The heap lock must be held when this procedure is called.
 328
 329 int
 330 hoardHeap::freeBlock(block * &b, superblock * &sb,
 331         int sizeclass, processHeap *pHeap)
 332 {
 333         assert(sb->isValid());
 334         assert(b->isValid());
 335         assert(this == sb->getOwner());
 336
 337         const int oldFullness = sb->getFullness();
 338         sb->putBlock(b);
 339         decUStats(sizeclass);
 340         const int newFullness = sb->getFullness();
 341
 342         // Free big superblocks.
 343         if (sb->getNumBlocks() == 1) {
 344                 removeSuperblock(sb, sizeclass);
 345                 const size_t s = sizeFromClass(sizeclass);
 346                 const int blksize = align(sizeof(block) + s);
 347 #if HEAP_LOG
 348                 // Record the memory deallocation.
 349                 MemoryRequest m;
 350                 m.deallocate((int)sb->getNumBlocks()
 351                         * (int)sizeFromClass(sb->getBlockSizeClass()));
 352                 pHeap->getLog(getIndex()).append(m);
 353 #endif
 354 #if HEAP_FRAG_STATS
 355                 pHeap->setDeallocated(0,
 356                         sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
 357 #endif
 358                 hoardUnsbrk(sb, align(sizeof(superblock) + blksize));
 359                 return 1;
 360         }
 361
 362         // If the fullness value has changed, move the superblock.
 363         if (newFullness != oldFullness) {
 364                 moveSuperblock(sb, sizeclass, oldFullness, newFullness);
 365         } else {
 366                 // Move the superblock to the front of its list (to reduce
 367                 // paging).
 368                 superblock *&head = _superblocks[newFullness][sizeclass];
 369                 if (sb != head) {
 370                         sb->remove();
 371                         sb->insertBefore(head);
 372                         head = sb;
 373                 }
 374         }
 375
 376         // If the superblock is now empty, recycle it.
 377
 378         if ((newFullness == 0) && (sb->getNumBlocks() == sb->getNumAvailable())) {
 379                 removeSuperblock(sb, sizeclass);
 380 #if 0
 381                 // Free it immediately.
 382                 const size_t s = sizeFromClass(sizeclass);
 383                 const int blksize = align(sizeof(block) + s);
 384 #if HEAP_LOG
 385                 // Record the memory deallocation.
 386                 MemoryRequest m;
 387                 m.deallocate((int)sb->getNumBlocks()
 388                         * (int)sizeFromClass(sb->getBlockSizeClass()));
 389                 pHeap->getLog(getIndex()).append(m);
 390 #endif
 391 #if HEAP_FRAG_STATS
 392                 pHeap->setDeallocated(0,
 393                         sb->getNumBlocks() * sizeFromClass(sb->getBlockSizeClass()));
 394 #endif
 395
 396                 hoardUnsbrk(sb, align(sizeof(superblock) + blksize));
 397                 return 1;
 398 #else
 399                 recycle(sb);
 400                 // Update the stats.  This restores the stats to their state
 401                 // before the call to removeSuperblock, above.
 402                 incStats(sizeclass,
 403                         sb->getNumBlocks() - sb->getNumAvailable(), sb->getNumBlocks());
 404 #endif
 405         }
 406
 407         // If this is the process heap, then we're done.
 408         if (this == (hoardHeap *)pHeap)
 409                 return 0;
 410
 411         //
 412         // Release a superblock, if necessary.
 413         //
 414
 415         //
 416         // Check to see if the amount free exceeds the release threshold
 417         // (two superblocks worth of blocks for a given sizeclass) and if
 418         // the heap is sufficiently empty.
 419         //
 420
 421         // We never move anything to the process heap if we're on a
 422         // uniprocessor.
 423         if (_numProcessors > 1) {
 424                 int inUse, allocated;
 425                 getStats(sizeclass, inUse, allocated);
 426                 if ((inUse < allocated - getReleaseThreshold(sizeclass))
 427                         && (EMPTY_FRACTION * inUse <
 428                                 EMPTY_FRACTION * allocated - allocated)) {
 429
 430                         // We've crossed the magical threshold. Find the superblock with
 431                         // the most free blocks and give it to the process heap.
 432                         superblock *const maxSb = removeMaxSuperblock(sizeclass);
 433                         assert(maxSb != NULL);
 434
 435                         // Update the statistics.
 436
 437                         assert(maxSb->getNumBlocks() >= maxSb->getNumAvailable());
 438
 439                         // Give the superblock back to the process heap.
 440                         pHeap->release(maxSb);
 441                 }
 442         }
 443
 444         return 0;
 445 }
 446
 447
 448 void
 449 hoardHeap::initNumProcs(void)
 450 {
 451         system_info info;
 452         if (get_system_info(&info) != B_OK)
 453                 hoardHeap::_numProcessors = 1;
 454         else
 455                 hoardHeap::_numProcessors = info.cpu_count;
 456
 457         fMaxThreadHeaps = 1 << (lg(_numProcessors) + 1);
 458         _numProcessorsMask = fMaxThreadHeaps - 1;
 459 }
 460