JavaScriptCore/kjs/collector.cpp

   1 // -*- mode: c++; c-basic-offset: 4 -*-
   2 /*
   3  *  Copyright (C) 2003, 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
   4  *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License as published by the Free Software Foundation; either
   9  *  version 2 of the License, or (at your option) any later version.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  *  Lesser General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Lesser General Public
  17  *  License along with this library; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #include "config.h"
  23 #include "collector.h"
  24
  25 #include "ExecState.h"
  26 #include "JSGlobalObject.h"
  27 #include "internal.h"
  28 #include "list.h"
  29 #include "value.h"
  30 #include <algorithm>
  31 #include <setjmp.h>
  32 #include <stdlib.h>
  33 #include <wtf/FastMalloc.h>
  34 #include <wtf/HashCountedSet.h>
  35 #include <wtf/UnusedParam.h>
  36
  37 #if USE(MULTIPLE_THREADS)
  38 #include <pthread.h>
  39 #include <wtf/ThreadSpecific.h>
  40 #endif
  41
  42 #if PLATFORM(DARWIN)
  43
  44 #include <mach/mach_port.h>
  45 #include <mach/mach_init.h>
  46 #include <mach/task.h>
  47 #include <mach/thread_act.h>
  48 #include <mach/vm_map.h>
  49
  50 #include "CollectorHeapIntrospector.h"
  51
  52 #elif PLATFORM(WIN_OS)
  53
  54 #include <windows.h>
  55
  56 #elif PLATFORM(UNIX)
  57
  58 #include <stdlib.h>
  59 #include <sys/mman.h>
  60 #include <unistd.h>
  61
  62 #if PLATFORM(SOLARIS)
  63 #include <thread.h>
  64 #endif
  65
  66 #if HAVE(PTHREAD_NP_H)
  67 #include <pthread_np.h>
  68 #else
  69 #include <pthread.h>
  70 #endif
  71
  72 #endif
  73
  74 #define DEBUG_COLLECTOR 0
  75 #define COLLECT_ON_EVERY_ALLOCATION 0
  76
  77 using std::max;
  78 using namespace WTF;
  79
  80 namespace KJS {
  81
  82 // tunable parameters
  83
  84 #define SPARE_EMPTY_BLOCKS 2UL
  85 #define MIN_ARRAY_SIZE 14UL
  86 #define GROWTH_FACTOR 2UL
  87 #define LOW_WATER_FACTOR 4UL
  88 #define ALLOCATIONS_PER_COLLECTION 4000UL
  89
  90 Heap::Heap()
  91 {
  92     memset(this, 0, sizeof(Heap));
  93 }
  94
  95 Heap* Heap::threadHeap()
  96 {
  97 #if USE(MULTIPLE_THREADS)
  98     static ThreadSpecific<Heap> sharedInstance;
  99     return sharedInstance;
 100 #else
 101     static Heap sharedInstance;
 102     return &sharedInstance;
 103 #endif
 104 }
 105
 106 static NEVER_INLINE CollectorBlock* allocateBlock()
 107 {
 108 #if PLATFORM(DARWIN)
 109     vm_address_t address = 0;
 110     vm_map(current_task(), &address, BLOCK_SIZE, BLOCK_OFFSET_MASK, VM_FLAGS_ANYWHERE, MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_DEFAULT, VM_INHERIT_DEFAULT);
 111 #elif PLATFORM(WIN_OS)
 112      // windows virtual address granularity is naturally 64k
 113     LPVOID address = VirtualAlloc(NULL, BLOCK_SIZE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
 114 #elif HAVE(POSIX_MEMALIGN)
 115     void* address;
 116     posix_memalign(&address, BLOCK_SIZE, BLOCK_SIZE);
 117     memset(address, 0, BLOCK_SIZE);
 118 #else
 119     static size_t pagesize = getpagesize();
 120
 121     size_t extra = 0;
 122     if (BLOCK_SIZE > pagesize)
 123         extra = BLOCK_SIZE - pagesize;
 124
 125     void* mmapResult = mmap(NULL, BLOCK_SIZE + extra, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
 126     uintptr_t address = reinterpret_cast<uintptr_t>(mmapResult);
 127
 128     size_t adjust = 0;
 129     if ((address & BLOCK_OFFSET_MASK) != 0)
 130         adjust = BLOCK_SIZE - (address & BLOCK_OFFSET_MASK);
 131
 132     if (adjust > 0)
 133         munmap(reinterpret_cast<void*>(address), adjust);
 134
 135     if (adjust < extra)
 136         munmap(reinterpret_cast<void*>(address + adjust + BLOCK_SIZE), extra - adjust);
 137
 138     address += adjust;
 139     memset(reinterpret_cast<void*>(address), 0, BLOCK_SIZE);
 140 #endif
 141
 142     return reinterpret_cast<CollectorBlock*>(address);
 143 }
 144
 145 static void freeBlock(CollectorBlock* block)
 146 {
 147 #if PLATFORM(DARWIN)
 148     vm_deallocate(current_task(), reinterpret_cast<vm_address_t>(block), BLOCK_SIZE);
 149 #elif PLATFORM(WIN_OS)
 150     VirtualFree(block, BLOCK_SIZE, MEM_RELEASE);
 151 #elif HAVE(POSIX_MEMALIGN)
 152     free(block);
 153 #else
 154     munmap(block, BLOCK_SIZE);
 155 #endif
 156 }
 157
 158 void Heap::recordExtraCost(size_t cost)
 159 {
 160     // Our frequency of garbage collection tries to balance memory use against speed
 161     // by collecting based on the number of newly created values. However, for values
 162     // that hold on to a great deal of memory that's not in the form of other JS values,
 163     // that is not good enough - in some cases a lot of those objects can pile up and
 164     // use crazy amounts of memory without a GC happening. So we track these extra
 165     // memory costs. Only unusually large objects are noted, and we only keep track
 166     // of this extra cost until the next GC. In garbage collected languages, most values
 167     // are either very short lived temporaries, or have extremely long lifetimes. So
 168     // if a large value survives one garbage collection, there is not much point to
 169     // collecting more frequently as long as it stays alive.
 170     // NOTE: we target the primaryHeap unconditionally as JSNumber doesn't modify cost
 171
 172     primaryHeap.extraCost += cost;
 173 }
 174
 175 template <Heap::HeapType heapType> struct HeapConstants;
 176
 177 template <> struct HeapConstants<Heap::PrimaryHeap> {
 178     static const size_t cellSize = CELL_SIZE;
 179     static const size_t cellsPerBlock = CELLS_PER_BLOCK;
 180     static const size_t bitmapShift = 0;
 181     typedef CollectorCell Cell;
 182     typedef CollectorBlock Block;
 183 };
 184
 185 template <> struct HeapConstants<Heap::NumberHeap> {
 186     static const size_t cellSize = SMALL_CELL_SIZE;
 187     static const size_t cellsPerBlock = SMALL_CELLS_PER_BLOCK;
 188     static const size_t bitmapShift = 1;
 189     typedef SmallCollectorCell Cell;
 190     typedef SmallCellCollectorBlock Block;
 191 };
 192
 193 template <Heap::HeapType heapType> void* Heap::heapAllocate(size_t s)
 194 {
 195   typedef typename HeapConstants<heapType>::Block Block;
 196   typedef typename HeapConstants<heapType>::Cell Cell;
 197
 198   CollectorHeap& heap = heapType == PrimaryHeap ? primaryHeap : numberHeap;
 199   ASSERT(JSLock::lockCount() > 0);
 200   ASSERT(JSLock::currentThreadIsHoldingLock());
 201   ASSERT(this == threadHeap());
 202   ASSERT(s <= HeapConstants<heapType>::cellSize);
 203   UNUSED_PARAM(s); // s is now only used for the above assert
 204
 205   ASSERT(heap.operationInProgress == NoOperation);
 206   ASSERT(heapType == PrimaryHeap || heap.extraCost == 0);
 207   // FIXME: If another global variable access here doesn't hurt performance
 208   // too much, we could abort() in NDEBUG builds, which could help ensure we
 209   // don't spend any time debugging cases where we allocate inside an object's
 210   // deallocation code.
 211
 212   size_t numLiveObjects = heap.numLiveObjects;
 213   size_t usedBlocks = heap.usedBlocks;
 214   size_t i = heap.firstBlockWithPossibleSpace;
 215
 216 #if COLLECT_ON_EVERY_ALLOCATION
 217   collect();
 218 #endif
 219
 220   // if we have a huge amount of extra cost, we'll try to collect even if we still have
 221   // free cells left.
 222   if (heapType == PrimaryHeap && heap.extraCost > ALLOCATIONS_PER_COLLECTION) {
 223       size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
 224       size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
 225       const size_t newCost = numNewObjects + heap.extraCost;
 226       if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect)
 227           goto collect;
 228   }
 229
 230   ASSERT(heap.operationInProgress == NoOperation);
 231 #ifndef NDEBUG
 232   // FIXME: Consider doing this in NDEBUG builds too (see comment above).
 233   heap.operationInProgress = Allocation;
 234 #endif
 235
 236 scan:
 237   Block* targetBlock;
 238   size_t targetBlockUsedCells;
 239   if (i != usedBlocks) {
 240     targetBlock = (Block*)heap.blocks[i];
 241     targetBlockUsedCells = targetBlock->usedCells;
 242     ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
 243     while (targetBlockUsedCells == HeapConstants<heapType>::cellsPerBlock) {
 244       if (++i == usedBlocks)
 245         goto collect;
 246       targetBlock = (Block*)heap.blocks[i];
 247       targetBlockUsedCells = targetBlock->usedCells;
 248       ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
 249     }
 250     heap.firstBlockWithPossibleSpace = i;
 251   } else {
 252
 253 collect:
 254     size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
 255     size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
 256     const size_t newCost = numNewObjects + heap.extraCost;
 257
 258     if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect) {
 259 #ifndef NDEBUG
 260       heap.operationInProgress = NoOperation;
 261 #endif
 262       bool collected = collect();
 263 #ifndef NDEBUG
 264       heap.operationInProgress = Allocation;
 265 #endif
 266       if (collected) {
 267         numLiveObjects = heap.numLiveObjects;
 268         usedBlocks = heap.usedBlocks;
 269         i = heap.firstBlockWithPossibleSpace;
 270         goto scan;
 271       }
 272     }
 273
 274     // didn't find a block, and GC didn't reclaim anything, need to allocate a new block
 275     size_t numBlocks = heap.numBlocks;
 276     if (usedBlocks == numBlocks) {
 277       numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
 278       heap.numBlocks = numBlocks;
 279       heap.blocks = static_cast<CollectorBlock **>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock *)));
 280     }
 281
 282     targetBlock = (Block*)allocateBlock();
 283     targetBlock->freeList = targetBlock->cells;
 284     targetBlock->heap = this;
 285     targetBlockUsedCells = 0;
 286     heap.blocks[usedBlocks] = (CollectorBlock*)targetBlock;
 287     heap.usedBlocks = usedBlocks + 1;
 288     heap.firstBlockWithPossibleSpace = usedBlocks;
 289   }
 290
 291   // find a free spot in the block and detach it from the free list
 292   Cell *newCell = targetBlock->freeList;
 293
 294   // "next" field is a cell offset -- 0 means next cell, so a zeroed block is already initialized
 295   targetBlock->freeList = (newCell + 1) + newCell->u.freeCell.next;
 296
 297   targetBlock->usedCells = static_cast<uint32_t>(targetBlockUsedCells + 1);
 298   heap.numLiveObjects = numLiveObjects + 1;
 299
 300 #ifndef NDEBUG
 301   // FIXME: Consider doing this in NDEBUG builds too (see comment above).
 302   heap.operationInProgress = NoOperation;
 303 #endif
 304
 305   return newCell;
 306 }
 307
 308 void* Heap::allocate(size_t s)
 309 {
 310     return heapAllocate<PrimaryHeap>(s);
 311 }
 312
 313 void* Heap::allocateNumber(size_t s)
 314 {
 315     return heapAllocate<NumberHeap>(s);
 316 }
 317
 318 static inline void* currentThreadStackBase()
 319 {
 320 #if PLATFORM(DARWIN)
 321     pthread_t thread = pthread_self();
 322     return pthread_get_stackaddr_np(thread);
 323 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
 324     // offset 0x18 from the FS segment register gives a pointer to
 325     // the thread information block for the current thread
 326     NT_TIB* pTib;
 327     __asm {
 328         MOV EAX, FS:[18h]
 329         MOV pTib, EAX
 330     }
 331     return (void*)pTib->StackBase;
 332 #elif PLATFORM(WIN_OS) && PLATFORM(X86_64) && COMPILER(MSVC)
 333     PNT_TIB64 pTib = reinterpret_cast<PNT_TIB64>(NtCurrentTeb());
 334     return (void*)pTib->StackBase;
 335 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(GCC)
 336     // offset 0x18 from the FS segment register gives a pointer to
 337     // the thread information block for the current thread
 338     NT_TIB* pTib;
 339     asm ( "movl %%fs:0x18, %0\n"
 340           : "=r" (pTib)
 341         );
 342     return (void*)pTib->StackBase;
 343 #elif PLATFORM(SOLARIS)
 344     stack_t s;
 345     thr_stksegment(&s);
 346     return s.ss_sp;
 347 #elif PLATFORM(UNIX)
 348     static void* stackBase = 0;
 349     static size_t stackSize = 0;
 350     static pthread_t stackThread;
 351     pthread_t thread = pthread_self();
 352     if (stackBase == 0 || thread != stackThread) {
 353         pthread_attr_t sattr;
 354         pthread_attr_init(&sattr);
 355 #if HAVE(PTHREAD_NP_H)
 356         // e.g. on FreeBSD 5.4, neundorf@kde.org
 357         pthread_attr_get_np(thread, &sattr);
 358 #else
 359         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
 360         pthread_getattr_np(thread, &sattr);
 361 #endif
 362         int rc = pthread_attr_getstack(&sattr, &stackBase, &stackSize);
 363         (void)rc; // FIXME: Deal with error code somehow? Seems fatal.
 364         ASSERT(stackBase);
 365         pthread_attr_destroy(&sattr);
 366         stackThread = thread;
 367     }
 368     return static_cast<char*>(stackBase) + stackSize;
 369 #else
 370 #error Need a way to get the stack base on this platform
 371 #endif
 372 }
 373
 374 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
 375
 376 // cell size needs to be a power of two for this to be valid
 377 #define IS_HALF_CELL_ALIGNED(p) (((intptr_t)(p) & (CELL_MASK >> 1)) == 0)
 378
 379 void Heap::markStackObjectsConservatively(void *start, void *end)
 380 {
 381   if (start > end) {
 382     void* tmp = start;
 383     start = end;
 384     end = tmp;
 385   }
 386
 387   ASSERT(((char*)end - (char*)start) < 0x1000000);
 388   ASSERT(IS_POINTER_ALIGNED(start));
 389   ASSERT(IS_POINTER_ALIGNED(end));
 390
 391   char** p = (char**)start;
 392   char** e = (char**)end;
 393
 394   size_t usedPrimaryBlocks = primaryHeap.usedBlocks;
 395   size_t usedNumberBlocks = numberHeap.usedBlocks;
 396   CollectorBlock **primaryBlocks = primaryHeap.blocks;
 397   CollectorBlock **numberBlocks = numberHeap.blocks;
 398
 399   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
 400
 401   while (p != e) {
 402       char* x = *p++;
 403       if (IS_HALF_CELL_ALIGNED(x) && x) {
 404           uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
 405           xAsBits &= CELL_ALIGN_MASK;
 406           uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
 407           CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
 408           // Mark the the number heap, we can mark these Cells directly to avoid the virtual call cost
 409           for (size_t block = 0; block < usedNumberBlocks; block++) {
 410               if ((numberBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
 411                   Heap::markCell(reinterpret_cast<JSCell*>(xAsBits));
 412                   goto endMarkLoop;
 413               }
 414           }
 415
 416           // Mark the primary heap
 417           for (size_t block = 0; block < usedPrimaryBlocks; block++) {
 418               if ((primaryBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
 419                   if (((CollectorCell*)xAsBits)->u.freeCell.zeroIfFree != 0) {
 420                       JSCell* imp = reinterpret_cast<JSCell*>(xAsBits);
 421                       if (!imp->marked())
 422                           imp->mark();
 423                   }
 424                   break;
 425               }
 426           }
 427       endMarkLoop:
 428           ;
 429       }
 430   }
 431 }
 432
 433 void NEVER_INLINE Heap::markStackObjectsConservativelyInternal()
 434 {
 435     void* dummy;
 436     void* stackPointer = &dummy;
 437     void* stackBase = currentThreadStackBase();
 438     markStackObjectsConservatively(stackPointer, stackBase);
 439 }
 440
 441 void Heap::markStackObjectsConservatively()
 442 {
 443     // setjmp forces volatile registers onto the stack
 444     jmp_buf registers;
 445 #if COMPILER(MSVC)
 446 #pragma warning(push)
 447 #pragma warning(disable: 4611)
 448 #endif
 449     setjmp(registers);
 450 #if COMPILER(MSVC)
 451 #pragma warning(pop)
 452 #endif
 453
 454     markStackObjectsConservativelyInternal();
 455 }
 456
 457 void Heap::protect(JSValue *k)
 458 {
 459     ASSERT(k);
 460     ASSERT(JSLock::lockCount() > 0);
 461     ASSERT(JSLock::currentThreadIsHoldingLock());
 462
 463     if (JSImmediate::isImmediate(k))
 464       return;
 465
 466     protectedValues.add(k->asCell());
 467 }
 468
 469 void Heap::unprotect(JSValue *k)
 470 {
 471     ASSERT(k);
 472     ASSERT(JSLock::lockCount() > 0);
 473     ASSERT(JSLock::currentThreadIsHoldingLock());
 474
 475     if (JSImmediate::isImmediate(k))
 476       return;
 477
 478     protectedValues.remove(k->asCell());
 479 }
 480
 481 Heap* Heap::heap(const JSValue* v)
 482 {
 483     if (JSImmediate::isImmediate(v))
 484         return 0;
 485     // FIXME: should assert that the result equals threadHeap(), but currently, this fails as database code uses gcUnprotect from a different thread.
 486     // That's a race condition and should be fixed.
 487     return Heap::cellBlock(v->asCell())->heap;
 488 }
 489
 490 void Heap::markProtectedObjects()
 491 {
 492   HashCountedSet<JSCell*>::iterator end = protectedValues.end();
 493   for (HashCountedSet<JSCell*>::iterator it = protectedValues.begin(); it != end; ++it) {
 494     JSCell *val = it->first;
 495     if (!val->marked())
 496       val->mark();
 497   }
 498 }
 499
 500 template <Heap::HeapType heapType> size_t Heap::sweep()
 501 {
 502     typedef typename HeapConstants<heapType>::Block Block;
 503     typedef typename HeapConstants<heapType>::Cell Cell;
 504
 505     // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
 506     CollectorHeap& heap = heapType == Heap::PrimaryHeap ? primaryHeap : numberHeap;
 507
 508     size_t emptyBlocks = 0;
 509     size_t numLiveObjects = heap.numLiveObjects;
 510
 511     for (size_t block = 0; block < heap.usedBlocks; block++) {
 512         Block* curBlock = (Block*)heap.blocks[block];
 513
 514         size_t usedCells = curBlock->usedCells;
 515         Cell* freeList = curBlock->freeList;
 516
 517         if (usedCells == HeapConstants<heapType>::cellsPerBlock) {
 518             // special case with a block where all cells are used -- testing indicates this happens often
 519             for (size_t i = 0; i < HeapConstants<heapType>::cellsPerBlock; i++) {
 520                 if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
 521                     Cell* cell = curBlock->cells + i;
 522
 523                     if (heapType != Heap::NumberHeap) {
 524                         JSCell* imp = reinterpret_cast<JSCell*>(cell);
 525                         // special case for allocated but uninitialized object
 526                         // (We don't need this check earlier because nothing prior this point
 527                         // assumes the object has a valid vptr.)
 528                         if (cell->u.freeCell.zeroIfFree == 0)
 529                             continue;
 530
 531                         imp->~JSCell();
 532                     }
 533
 534                     --usedCells;
 535                     --numLiveObjects;
 536
 537                     // put cell on the free list
 538                     cell->u.freeCell.zeroIfFree = 0;
 539                     cell->u.freeCell.next = freeList - (cell + 1);
 540                     freeList = cell;
 541                 }
 542             }
 543         } else {
 544             size_t minimumCellsToProcess = usedCells;
 545             for (size_t i = 0; (i < minimumCellsToProcess) & (i < HeapConstants<heapType>::cellsPerBlock); i++) {
 546                 Cell *cell = curBlock->cells + i;
 547                 if (cell->u.freeCell.zeroIfFree == 0) {
 548                     ++minimumCellsToProcess;
 549                 } else {
 550                     if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
 551                         if (heapType != Heap::NumberHeap) {
 552                             JSCell *imp = reinterpret_cast<JSCell*>(cell);
 553                             imp->~JSCell();
 554                         }
 555                         --usedCells;
 556                         --numLiveObjects;
 557
 558                         // put cell on the free list
 559                         cell->u.freeCell.zeroIfFree = 0;
 560                         cell->u.freeCell.next = freeList - (cell + 1);
 561                         freeList = cell;
 562                     }
 563                 }
 564             }
 565         }
 566
 567         curBlock->usedCells = static_cast<uint32_t>(usedCells);
 568         curBlock->freeList = freeList;
 569         curBlock->marked.clearAll();
 570
 571         if (usedCells == 0) {
 572             emptyBlocks++;
 573             if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
 574 #if !DEBUG_COLLECTOR
 575                 freeBlock((CollectorBlock*)curBlock);
 576 #endif
 577                 // swap with the last block so we compact as we go
 578                 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
 579                 heap.usedBlocks--;
 580                 block--; // Don't move forward a step in this case
 581
 582                 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
 583                     heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
 584                     heap.blocks = (CollectorBlock**)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
 585                 }
 586             }
 587         }
 588     }
 589
 590     if (heap.numLiveObjects != numLiveObjects)
 591         heap.firstBlockWithPossibleSpace = 0;
 592
 593     heap.numLiveObjects = numLiveObjects;
 594     heap.numLiveObjectsAtLastCollect = numLiveObjects;
 595     heap.extraCost = 0;
 596     return numLiveObjects;
 597 }
 598
 599 bool Heap::collect()
 600 {
 601   ASSERT(JSLock::lockCount() > 0);
 602   ASSERT(JSLock::currentThreadIsHoldingLock());
 603   ASSERT(this == threadHeap());
 604
 605   ASSERT((primaryHeap.operationInProgress == NoOperation) | (numberHeap.operationInProgress == NoOperation));
 606   if ((primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation))
 607     abort();
 608
 609   primaryHeap.operationInProgress = Collection;
 610   numberHeap.operationInProgress = Collection;
 611
 612   // MARK: first mark all referenced objects recursively starting out from the set of root objects
 613
 614 #ifndef NDEBUG
 615   // Forbid malloc during the mark phase. Marking a thread suspends it, so
 616   // a malloc inside mark() would risk a deadlock with a thread that had been
 617   // suspended while holding the malloc lock.
 618   fastMallocForbid();
 619 #endif
 620
 621   markStackObjectsConservatively();
 622   markProtectedObjects();
 623   if (m_markListSet.size())
 624     List::markProtectedLists(m_markListSet);
 625
 626 #ifndef NDEBUG
 627   fastMallocAllow();
 628 #endif
 629
 630   size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
 631   size_t numLiveObjects = sweep<PrimaryHeap>();
 632   numLiveObjects += sweep<NumberHeap>();
 633
 634   primaryHeap.operationInProgress = NoOperation;
 635   numberHeap.operationInProgress = NoOperation;
 636
 637   return numLiveObjects < originalLiveObjects;
 638 }
 639
 640 size_t Heap::size()
 641 {
 642   return primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
 643 }
 644
 645 size_t Heap::globalObjectCount()
 646 {
 647   size_t count = 0;
 648   if (JSGlobalObject::head()) {
 649     JSGlobalObject* o = JSGlobalObject::head();
 650     do {
 651       ++count;
 652       o = o->next();
 653     } while (o != JSGlobalObject::head());
 654   }
 655   return count;
 656 }
 657
 658 size_t Heap::protectedGlobalObjectCount()
 659 {
 660   size_t count = 0;
 661   if (JSGlobalObject::head()) {
 662     JSGlobalObject* o = JSGlobalObject::head();
 663     do {
 664       if (protectedValues.contains(o))
 665         ++count;
 666       o = o->next();
 667     } while (o != JSGlobalObject::head());
 668   }
 669   return count;
 670 }
 671
 672 size_t Heap::protectedObjectCount()
 673 {
 674   return protectedValues.size();
 675 }
 676
 677 static const char *typeName(JSCell *val)
 678 {
 679   const char *name = "???";
 680   switch (val->type()) {
 681     case UnspecifiedType:
 682       break;
 683     case UndefinedType:
 684       name = "undefined";
 685       break;
 686     case NullType:
 687       name = "null";
 688       break;
 689     case BooleanType:
 690       name = "boolean";
 691       break;
 692     case StringType:
 693       name = "string";
 694       break;
 695     case NumberType:
 696       name = "number";
 697       break;
 698     case ObjectType: {
 699       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
 700       name = info ? info->className : "Object";
 701       break;
 702     }
 703     case GetterSetterType:
 704       name = "gettersetter";
 705       break;
 706   }
 707   return name;
 708 }
 709
 710 HashCountedSet<const char*>* Heap::protectedObjectTypeCounts()
 711 {
 712     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
 713
 714     HashCountedSet<JSCell*>::iterator end = protectedValues.end();
 715     for (HashCountedSet<JSCell*>::iterator it = protectedValues.begin(); it != end; ++it)
 716         counts->add(typeName(it->first));
 717
 718     return counts;
 719 }
 720
 721 bool Heap::isBusy()
 722 {
 723     return (primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation);
 724 }
 725
 726 void Heap::reportOutOfMemoryToAllExecStates()
 727 {
 728     if (!JSGlobalObject::head())
 729         return;
 730
 731     JSGlobalObject* globalObject = JSGlobalObject::head();
 732     do {
 733         ExecStateStack::const_iterator end = globalObject->activeExecStates().end();
 734         for (ExecStateStack::const_iterator it = globalObject->activeExecStates().begin(); it != end; ++it)
 735             (*it)->setException(Error::create(*it, GeneralError, "Out of memory"));
 736         globalObject = globalObject->next();
 737     } while (globalObject != JSGlobalObject::head());
 738 }
 739
 740 } // namespace KJS