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 26using 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 34size_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 52size_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 65size_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 74size_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 83size_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 91size_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 102int hoardHeap::fMaxThreadHeaps = 1; 103int hoardHeap::_numProcessors; 104int hoardHeap::_numProcessorsMask; 105 106 107// Return ceil(log_2(num)). 108// num must be positive. 109 110static int 111lg(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 128hoardHeap::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 150void 151hoardHeap::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 213superblock * 214hoardHeap::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 268void 269hoardHeap::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 293void 294hoardHeap::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 329int 330hoardHeap::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 448void 449hoardHeap::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 461