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/* hoardHeap, the base class for threadHeap and processHeap. */ 21 22#ifndef _HEAP_H_ 23#define _HEAP_H_ 24 25#include <OS.h> 26 27#include "config.h" 28 29#include "arch-specific.h" 30#include "superblock.h" 31#include "heapstats.h" 32 33 34namespace BPrivate { 35 36class processHeap; 37 38class hoardHeap { 39 public: 40 hoardHeap(void); 41 42 // A superblock that holds more than one object must hold at least 43 // this many bytes. 44 enum { SUPERBLOCK_SIZE = 8192 }; 45 46 // A thread heap must be at least 1/EMPTY_FRACTION empty before we 47 // start returning superblocks to the process heap. 48 enum { EMPTY_FRACTION = SUPERBLOCK_FULLNESS_GROUP - 1 }; 49 50 // Reset value for the least-empty bin. The last bin 51 // (SUPERBLOCK_FULLNESS_GROUP-1) is for completely full superblocks, 52 // so we use the next-to-last bin. 53 enum { RESET_LEAST_EMPTY_BIN = SUPERBLOCK_FULLNESS_GROUP - 2 }; 54 55 // The number of empty superblocks that we allow any thread heap to 56 // hold once the thread heap has fallen below 1/EMPTY_FRACTION 57 // empty. 58 enum { MAX_EMPTY_SUPERBLOCKS = EMPTY_FRACTION }; 59 60 // The maximum number of thread heaps we allow. (NOT the maximum 61 // number of threads -- Hoard imposes no such limit.) This must be 62 // a power of two! NB: This number is twice the maximum number of 63 // PROCESSORS supported by Hoard. 64 enum { MAX_HEAPS = B_MAX_CPU_COUNT * 2 }; 65 66 // ANDing with this rounds to MAX_HEAPS. 67 enum { MAX_HEAPS_MASK = MAX_HEAPS - 1 }; 68 69 // 70 // The number of size classes. This combined with the 71 // SIZE_CLASS_BASE determine the maximum size of an object. 72 // 73 // NB: Once this is changed, you must execute maketable.cpp and put 74 // the generated values into heap.cpp. 75 76#if MAX_INTERNAL_FRAGMENTATION == 2 77 enum { SIZE_CLASSES = 115 }; 78#elif MAX_INTERNAL_FRAGMENTATION == 6 79 enum { SIZE_CLASSES = 46 }; 80#elif MAX_INTERNAL_FRAGMENTATION == 10 81 enum { SIZE_CLASSES = 32 }; 82#else 83# error "Undefined size class base." 84#endif 85 86 // Every object is aligned so that it can always hold a double. 87 enum { ALIGNMENT = sizeof(double) }; 88 89 // ANDing with this rounds to ALIGNMENT. 90 enum { ALIGNMENT_MASK = ALIGNMENT - 1 }; 91 92 // Used for sanity checking. 93 enum { HEAP_MAGIC = 0x0badcafe }; 94 95 // Get the usage and allocated statistics. 96 inline void getStats(int sizeclass, int &U, int &A); 97 98 99#if HEAP_STATS 100 // How much is the maximum ever in use for this size class? 101 inline int maxInUse(int sizeclass); 102 103 // How much is the maximum memory allocated for this size class? 104 inline int maxAllocated(int sizeclass); 105#endif 106 107 // Insert a superblock into our list. 108 void insertSuperblock(int sizeclass, superblock *sb, processHeap *pHeap); 109 110 // Remove the superblock with the most free space. 111 superblock *removeMaxSuperblock(int sizeclass); 112 113 // Find an available superblock (i.e., with some space in it). 114 inline superblock *findAvailableSuperblock(int sizeclass, 115 block * &b, processHeap * pHeap); 116 117 // Lock this heap. 118 inline void lock(void); 119 120 // Unlock this heap. 121 inline void unlock(void); 122 123 // Set our index number (which heap we are). 124 inline void setIndex(int i); 125 126 // Get our index number (which heap we are). 127 inline int getIndex(void); 128 129 // Free a block into a superblock. 130 // This is used by processHeap::free(). 131 // Returns 1 iff the superblock was munmapped. 132 int freeBlock(block * &b, superblock * &sb, int sizeclass, 133 processHeap * pHeap); 134 135 //// Utility functions //// 136 137 // Return the size class for a given size. 138 inline static int sizeClass(const size_t sz); 139 140 // Return the size corresponding to a given size class. 141 inline static size_t sizeFromClass(const int sizeclass); 142 143 // Return the release threshold corresponding to a given size class. 144 inline static int getReleaseThreshold(const int sizeclass); 145 146 // Return how many blocks of a given size class fit into a superblock. 147 inline static int numBlocks(const int sizeclass); 148 149 // Align a value. 150 inline static size_t align(const size_t sz); 151 152 private: 153 // Disable copying and assignment. 154 155 hoardHeap(const hoardHeap &); 156 const hoardHeap & operator=(const hoardHeap &); 157 158 // Recycle a superblock. 159 inline void recycle(superblock *); 160 161 // Reuse a superblock (if one is available). 162 inline superblock *reuse(int sizeclass); 163 164 // Remove a particular superblock. 165 void removeSuperblock(superblock *, int sizeclass); 166 167 // Move a particular superblock from one bin to another. 168 void moveSuperblock(superblock *, 169 int sizeclass, int fromBin, int toBin); 170 171 // Update memory in-use and allocated statistics. 172 // (*UStats = just update U.) 173 inline void incStats(int sizeclass, int updateU, int updateA); 174 inline void incUStats(int sizeclass); 175 176 inline void decStats(int sizeclass, int updateU, int updateA); 177 inline void decUStats(int sizeclass); 178 179 //// Members //// 180 181 // Heap statistics. 182 heapStats _stats[SIZE_CLASSES]; 183 184 // The per-heap lock. 185 hoardLockType _lock; 186 187 // Which heap this is (0 = the process (global) heap). 188 int _index; 189 190 // Reusable superblocks. 191 superblock *_reusableSuperblocks; 192 int _reusableSuperblocksCount; 193 194 // Lists of superblocks. 195 superblock *_superblocks[SUPERBLOCK_FULLNESS_GROUP][SIZE_CLASSES]; 196 197 // The current least-empty superblock bin. 198 int _leastEmptyBin[SIZE_CLASSES]; 199 200#if HEAP_DEBUG 201 // For sanity checking. 202 const unsigned long _magic; 203#else 204# define _magic HEAP_MAGIC 205#endif 206 207 // The lookup table for size classes. 208 static size_t _sizeTable[SIZE_CLASSES]; 209 210 // The lookup table for release thresholds. 211 static size_t _threshold[SIZE_CLASSES]; 212 213 public: 214 static void initNumProcs(void); 215 216 protected: 217 // number of CPUs, cached 218 static int _numProcessors; 219 static int _numProcessorsMask; 220}; 221 222 223 224void 225hoardHeap::incStats(int sizeclass, int updateU, int updateA) 226{ 227 assert(_magic == HEAP_MAGIC); 228 assert(updateU >= 0); 229 assert(updateA >= 0); 230 assert(sizeclass >= 0); 231 assert(sizeclass < SIZE_CLASSES); 232 _stats[sizeclass].incStats(updateU, updateA); 233} 234 235 236void 237hoardHeap::incUStats(int sizeclass) 238{ 239 assert(_magic == HEAP_MAGIC); 240 assert(sizeclass >= 0); 241 assert(sizeclass < SIZE_CLASSES); 242 _stats[sizeclass].incUStats(); 243} 244 245 246void 247hoardHeap::decStats(int sizeclass, int updateU, int updateA) 248{ 249 assert(_magic == HEAP_MAGIC); 250 assert(updateU >= 0); 251 assert(updateA >= 0); 252 assert(sizeclass >= 0); 253 assert(sizeclass < SIZE_CLASSES); 254 _stats[sizeclass].decStats(updateU, updateA); 255} 256 257 258void 259hoardHeap::decUStats(int sizeclass) 260{ 261 assert(_magic == HEAP_MAGIC); 262 assert(sizeclass >= 0); 263 assert(sizeclass < SIZE_CLASSES); 264 _stats[sizeclass].decUStats(); 265} 266 267 268void 269hoardHeap::getStats(int sizeclass, int &U, int &A) 270{ 271 assert(_magic == HEAP_MAGIC); 272 assert(sizeclass >= 0); 273 assert(sizeclass < SIZE_CLASSES); 274 _stats[sizeclass].getStats(U, A); 275} 276 277 278#if HEAP_STATS 279int 280hoardHeap::maxInUse(int sizeclass) 281{ 282 assert(_magic == HEAP_MAGIC); 283 return _stats[sizeclass].getUmax(); 284} 285 286 287int 288hoardHeap::maxAllocated(int sizeclass) 289{ 290 assert(_magic == HEAP_MAGIC); 291 return _stats[sizeclass].getAmax(); 292} 293#endif // HEAP_STATS 294 295 296superblock * 297hoardHeap::findAvailableSuperblock(int sizeclass, 298 block * &b, processHeap * pHeap) 299{ 300 assert(this); 301 assert(_magic == HEAP_MAGIC); 302 assert(sizeclass >= 0); 303 assert(sizeclass < SIZE_CLASSES); 304 305 superblock *sb = NULL; 306 int reUsed = 0; 307 308 // Look through the superblocks, starting with the almost-full ones 309 // and going to the emptiest ones. The Least Empty Bin for a 310 // sizeclass is a conservative approximation (fixed after one 311 // iteration) of the first bin that has superblocks in it, starting 312 // with (surprise) the least-empty bin. 313 314 for (int i = _leastEmptyBin[sizeclass]; i >= 0; i--) { 315 sb = _superblocks[i][sizeclass]; 316 if (sb == NULL) { 317 if (i == _leastEmptyBin[sizeclass]) { 318 // There wasn't a superblock in this bin, 319 // so we adjust the least empty bin. 320 _leastEmptyBin[sizeclass]--; 321 } 322 } else if (sb->getNumAvailable() > 0) { 323 assert(sb->getOwner() == this); 324 break; 325 } 326 sb = NULL; 327 } 328 329#if 1 330 if (sb == NULL) { 331 // Try to reuse a superblock. 332 sb = reuse(sizeclass); 333 if (sb) { 334 assert(sb->getOwner() == this); 335 reUsed = 1; 336 } 337 } 338#endif 339 340 if (sb != NULL) { 341 // Sanity checks: 342 // This superblock is 'valid'. 343 assert(sb->isValid()); 344 // This superblock has the right ownership. 345 assert(sb->getOwner() == this); 346 347 int oldFullness = sb->getFullness(); 348 349 // Now get a block from the superblock. 350 // This superblock must have space available. 351 b = sb->getBlock(); 352 assert(b != NULL); 353 354 // Update the stats. 355 incUStats(sizeclass); 356 357 if (reUsed) { 358 insertSuperblock(sizeclass, sb, pHeap); 359 // Fix the stats (since insert will just have incremented them 360 // by this amount). 361 decStats(sizeclass, 362 sb->getNumBlocks() - sb->getNumAvailable(), 363 sb->getNumBlocks()); 364 } else { 365 // If we've crossed a fullness group, 366 // move the superblock. 367 int fullness = sb->getFullness(); 368 369 if (fullness != oldFullness) { 370 // Move the superblock. 371 moveSuperblock(sb, sizeclass, oldFullness, fullness); 372 } 373 } 374 } 375 // Either we didn't find a superblock or we did and got a block. 376 assert((sb == NULL) || (b != NULL)); 377 // Either we didn't get a block or we did and we also got a superblock. 378 assert((b == NULL) || (sb != NULL)); 379 380 return sb; 381} 382 383 384int 385hoardHeap::sizeClass(const size_t sz) 386{ 387 // Find the size class for a given object size 388 // (the smallest i such that _sizeTable[i] >= sz). 389 int sizeclass = 0; 390 while (_sizeTable[sizeclass] < sz) { 391 sizeclass++; 392 assert(sizeclass < SIZE_CLASSES); 393 } 394 return sizeclass; 395} 396 397 398size_t 399hoardHeap::sizeFromClass(const int sizeclass) 400{ 401 assert(sizeclass >= 0); 402 assert(sizeclass < SIZE_CLASSES); 403 return _sizeTable[sizeclass]; 404} 405 406 407int 408hoardHeap::getReleaseThreshold(const int sizeclass) 409{ 410 assert(sizeclass >= 0); 411 assert(sizeclass < SIZE_CLASSES); 412 return _threshold[sizeclass]; 413} 414 415 416int 417hoardHeap::numBlocks(const int sizeclass) 418{ 419 assert(sizeclass >= 0); 420 assert(sizeclass < SIZE_CLASSES); 421 const size_t s = sizeFromClass(sizeclass); 422 assert(s > 0); 423 const int blksize = align(sizeof(block) + s); 424 // Compute the number of blocks that will go into this superblock. 425 int nb = max_c(1, ((SUPERBLOCK_SIZE - sizeof(superblock)) / blksize)); 426 return nb; 427} 428 429 430void 431hoardHeap::lock(void) 432{ 433 assert(_magic == HEAP_MAGIC); 434 hoardLock(_lock); 435} 436 437 438void 439hoardHeap::unlock(void) 440{ 441 assert(_magic == HEAP_MAGIC); 442 hoardUnlock(_lock); 443} 444 445 446size_t 447hoardHeap::align(const size_t sz) 448{ 449 // Align sz up to the nearest multiple of ALIGNMENT. 450 // This is much faster than using multiplication 451 // and division. 452 return (sz + ALIGNMENT_MASK) & ~ALIGNMENT_MASK; 453} 454 455 456void 457hoardHeap::setIndex(int i) 458{ 459 _index = i; 460} 461 462 463int 464hoardHeap::getIndex(void) 465{ 466 return _index; 467} 468 469 470void 471hoardHeap::recycle(superblock *sb) 472{ 473 assert(sb != NULL); 474 assert(sb->getOwner() == this); 475 assert(sb->getNumBlocks() > 1); 476 assert(sb->getNext() == NULL); 477 assert(sb->getPrev() == NULL); 478 assert(hoardHeap::numBlocks(sb->getBlockSizeClass()) > 1); 479 sb->insertBefore(_reusableSuperblocks); 480 _reusableSuperblocks = sb; 481 ++_reusableSuperblocksCount; 482 // printf ("count: %d => %d\n", getIndex(), _reusableSuperblocksCount); 483} 484 485 486superblock * 487hoardHeap::reuse(int sizeclass) 488{ 489 if (_reusableSuperblocks == NULL) 490 return NULL; 491 492 // Make sure that we aren't using a sizeclass 493 // that is too big for a 'normal' superblock. 494 if (hoardHeap::numBlocks(sizeclass) <= 1) 495 return NULL; 496 497 // Pop off a superblock from the reusable-superblock list. 498 assert(_reusableSuperblocksCount > 0); 499 superblock *sb = _reusableSuperblocks; 500 _reusableSuperblocks = sb->getNext(); 501 sb->remove(); 502 assert(sb->getNumBlocks() > 1); 503 --_reusableSuperblocksCount; 504 505 // Reformat the superblock if necessary. 506 if (sb->getBlockSizeClass() != sizeclass) { 507 decStats(sb->getBlockSizeClass(), 508 sb->getNumBlocks() - sb->getNumAvailable(), 509 sb->getNumBlocks()); 510 511 sb = new((char *)sb) superblock(numBlocks(sizeclass), 512 sizeclass, this); 513 514 incStats(sizeclass, 515 sb->getNumBlocks() - sb->getNumAvailable(), 516 sb->getNumBlocks()); 517 } 518 519 assert(sb->getOwner() == this); 520 assert(sb->getBlockSizeClass() == sizeclass); 521 return sb; 522} 523 524} // namespace BPrivate 525 526#endif // _HEAP_H_ 527