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