JavaScriptCore/runtime/Collector.cpp

   1 /*
   2  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
   3  *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Lesser General Public
   7  *  License as published by the Free Software Foundation; either
   8  *  version 2 of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free Software
  17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  *
  19  */
  20
  21 #include "config.h"
  22 #include "Collector.h"
  23
  24 #include "ArgList.h"
  25 #include "CallFrame.h"
  26 #include "CodeBlock.h"
  27 #include "CollectorHeapIterator.h"
  28 #include "GCActivityCallback.h"
  29 #include "Interpreter.h"
  30 #include "JSArray.h"
  31 #include "JSGlobalObject.h"
  32 #include "JSLock.h"
  33 #include "JSONObject.h"
  34 #include "JSString.h"
  35 #include "JSValue.h"
  36 #include "JSZombie.h"
  37 #include "MarkStack.h"
  38 #include "Nodes.h"
  39 #include "Tracing.h"
  40 #include <algorithm>
  41 #include <limits.h>
  42 #include <setjmp.h>
  43 #include <stdlib.h>
  44 #include <wtf/FastMalloc.h>
  45 #include <wtf/HashCountedSet.h>
  46 #include <wtf/WTFThreadData.h>
  47 #include <wtf/UnusedParam.h>
  48 #include <wtf/VMTags.h>
  49
  50 #if OS(DARWIN)
  51
  52 #include <mach/mach_init.h>
  53 #include <mach/mach_port.h>
  54 #include <mach/task.h>
  55 #include <mach/thread_act.h>
  56 #include <mach/vm_map.h>
  57
  58 #elif OS(WINDOWS)
  59
  60 #include <windows.h>
  61 #include <malloc.h>
  62
  63 #elif OS(HAIKU)
  64
  65 #include <OS.h>
  66
  67 #elif OS(UNIX)
  68
  69 #include <stdlib.h>
  70 #if !OS(HAIKU)
  71 #include <sys/mman.h>
  72 #endif
  73 #include <unistd.h>
  74
  75 #if OS(SOLARIS)
  76 #include <thread.h>
  77 #else
  78 #include <pthread.h>
  79 #endif
  80
  81 #if HAVE(PTHREAD_NP_H)
  82 #include <pthread_np.h>
  83 #endif
  84
  85 #if OS(QNX)
  86 #include <fcntl.h>
  87 #include <sys/procfs.h>
  88 #include <stdio.h>
  89 #include <errno.h>
  90 #endif
  91
  92 #endif
  93
  94 #define COLLECT_ON_EVERY_ALLOCATION 0
  95
  96 using std::max;
  97
  98 namespace JSC {
  99
 100 // tunable parameters
 101
 102 const size_t GROWTH_FACTOR = 2;
 103 const size_t LOW_WATER_FACTOR = 4;
 104 const size_t ALLOCATIONS_PER_COLLECTION = 3600;
 105 // This value has to be a macro to be used in max() without introducing
 106 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
 107 #define MIN_ARRAY_SIZE (static_cast<size_t>(14))
 108
 109 #if ENABLE(JSC_MULTIPLE_THREADS)
 110
 111 #if OS(DARWIN)
 112 typedef mach_port_t PlatformThread;
 113 #elif OS(WINDOWS)
 114 typedef HANDLE PlatformThread;
 115 #endif
 116
 117 class Heap::Thread {
 118 public:
 119     Thread(pthread_t pthread, const PlatformThread& platThread, void* base)
 120         : posixThread(pthread)
 121         , platformThread(platThread)
 122         , stackBase(base)
 123     {
 124     }
 125
 126     Thread* next;
 127     pthread_t posixThread;
 128     PlatformThread platformThread;
 129     void* stackBase;
 130 };
 131
 132 #endif
 133
 134 Heap::Heap(JSGlobalData* globalData)
 135     : m_markListSet(0)
 136 #if ENABLE(JSC_MULTIPLE_THREADS)
 137     , m_registeredThreads(0)
 138     , m_currentThreadRegistrar(0)
 139 #endif
 140     , m_globalData(globalData)
 141 {
 142     ASSERT(globalData);
 143     memset(&m_heap, 0, sizeof(CollectorHeap));
 144     allocateBlock();
 145     m_activityCallback = DefaultGCActivityCallback::create(this);
 146     (*m_activityCallback)();
 147 }
 148
 149 Heap::~Heap()
 150 {
 151     // The destroy function must already have been called, so assert this.
 152     ASSERT(!m_globalData);
 153 }
 154
 155 void Heap::destroy()
 156 {
 157     JSLock lock(SilenceAssertionsOnly);
 158
 159     if (!m_globalData)
 160         return;
 161
 162     ASSERT(!m_globalData->dynamicGlobalObject);
 163     ASSERT(!isBusy());
 164
 165     // The global object is not GC protected at this point, so sweeping may delete it
 166     // (and thus the global data) before other objects that may use the global data.
 167     RefPtr<JSGlobalData> protect(m_globalData);
 168
 169     delete m_markListSet;
 170     m_markListSet = 0;
 171
 172     freeBlocks();
 173
 174     for (unsigned i = 0; i < m_weakGCHandlePools.size(); ++i)
 175         m_weakGCHandlePools[i].deallocate();
 176
 177 #if ENABLE(JSC_MULTIPLE_THREADS)
 178     if (m_currentThreadRegistrar) {
 179         int error = pthread_key_delete(m_currentThreadRegistrar);
 180         ASSERT_UNUSED(error, !error);
 181     }
 182
 183     MutexLocker registeredThreadsLock(m_registeredThreadsMutex);
 184     for (Heap::Thread* t = m_registeredThreads; t;) {
 185         Heap::Thread* next = t->next;
 186         delete t;
 187         t = next;
 188     }
 189 #endif
 190     m_blockallocator.destroy();
 191     m_globalData = 0;
 192 }
 193
 194 NEVER_INLINE CollectorBlock* Heap::allocateBlock()
 195 {
 196     AlignedCollectorBlock allocation = m_blockallocator.allocate();
 197     CollectorBlock* block = static_cast<CollectorBlock*>(allocation.base());
 198     if (!block)
 199         CRASH();
 200
 201     // Initialize block.
 202
 203     block->heap = this;
 204     clearMarkBits(block);
 205
 206     Structure* dummyMarkableCellStructure = m_globalData->dummyMarkableCellStructure.get();
 207     for (size_t i = 0; i < HeapConstants::cellsPerBlock; ++i)
 208         new (&block->cells[i]) JSCell(dummyMarkableCellStructure);
 209
 210     // Add block to blocks vector.
 211
 212     size_t numBlocks = m_heap.numBlocks;
 213     if (m_heap.usedBlocks == numBlocks) {
 214         static const size_t maxNumBlocks = ULONG_MAX / sizeof(AlignedCollectorBlock) / GROWTH_FACTOR;
 215         if (numBlocks > maxNumBlocks)
 216             CRASH();
 217         numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
 218         m_heap.numBlocks = numBlocks;
 219         m_heap.blocks = static_cast<AlignedCollectorBlock*>(fastRealloc(m_heap.blocks, numBlocks * sizeof(AlignedCollectorBlock)));
 220     }
 221     m_heap.blocks[m_heap.usedBlocks++] = allocation;
 222
 223     return block;
 224 }
 225
 226 NEVER_INLINE void Heap::freeBlock(size_t block)
 227 {
 228     m_heap.didShrink = true;
 229
 230     ObjectIterator it(m_heap, block);
 231     ObjectIterator end(m_heap, block + 1);
 232     for ( ; it != end; ++it)
 233         (*it)->~JSCell();
 234     m_heap.blocks[block].deallocate();
 235
 236     // swap with the last block so we compact as we go
 237     m_heap.blocks[block] = m_heap.blocks[m_heap.usedBlocks - 1];
 238     m_heap.usedBlocks--;
 239
 240     if (m_heap.numBlocks > MIN_ARRAY_SIZE && m_heap.usedBlocks < m_heap.numBlocks / LOW_WATER_FACTOR) {
 241         m_heap.numBlocks = m_heap.numBlocks / GROWTH_FACTOR;
 242         m_heap.blocks = static_cast<AlignedCollectorBlock*>(fastRealloc(m_heap.blocks, m_heap.numBlocks * sizeof(AlignedCollectorBlock)));
 243     }
 244 }
 245
 246 void Heap::freeBlocks()
 247 {
 248     ProtectCountSet protectedValuesCopy = m_protectedValues;
 249
 250     clearMarkBits();
 251     ProtectCountSet::iterator protectedValuesEnd = protectedValuesCopy.end();
 252     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
 253         markCell(it->first);
 254
 255     m_heap.nextCell = 0;
 256     m_heap.nextBlock = 0;
 257     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
 258     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
 259     for ( ; it != end; ++it)
 260         (*it)->~JSCell();
 261
 262     ASSERT(!protectedObjectCount());
 263
 264     protectedValuesEnd = protectedValuesCopy.end();
 265     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
 266         it->first->~JSCell();
 267
 268     for (size_t block = 0; block < m_heap.usedBlocks; ++block)
 269         m_heap.blocks[block].deallocate();
 270
 271     fastFree(m_heap.blocks);
 272
 273     memset(&m_heap, 0, sizeof(CollectorHeap));
 274 }
 275
 276 void Heap::recordExtraCost(size_t cost)
 277 {
 278     // Our frequency of garbage collection tries to balance memory use against speed
 279     // by collecting based on the number of newly created values. However, for values
 280     // that hold on to a great deal of memory that's not in the form of other JS values,
 281     // that is not good enough - in some cases a lot of those objects can pile up and
 282     // use crazy amounts of memory without a GC happening. So we track these extra
 283     // memory costs. Only unusually large objects are noted, and we only keep track
 284     // of this extra cost until the next GC. In garbage collected languages, most values
 285     // are either very short lived temporaries, or have extremely long lifetimes. So
 286     // if a large value survives one garbage collection, there is not much point to
 287     // collecting more frequently as long as it stays alive.
 288
 289     if (m_heap.extraCost > maxExtraCost && m_heap.extraCost > m_heap.usedBlocks * BLOCK_SIZE / 2) {
 290         // If the last iteration through the heap deallocated blocks, we need
 291         // to clean up remaining garbage before marking. Otherwise, the conservative
 292         // marking mechanism might follow a pointer to unmapped memory.
 293         if (m_heap.didShrink)
 294             sweep();
 295         reset();
 296     }
 297     m_heap.extraCost += cost;
 298 }
 299
 300 void* Heap::allocate(size_t s)
 301 {
 302     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
 303     typedef HeapConstants::Block Block;
 304     typedef HeapConstants::Cell Cell;
 305
 306     ASSERT(JSLock::lockCount() > 0);
 307     ASSERT(JSLock::currentThreadIsHoldingLock());
 308     ASSERT_UNUSED(s, s <= HeapConstants::cellSize);
 309
 310     ASSERT(m_heap.operationInProgress == NoOperation);
 311
 312 #if COLLECT_ON_EVERY_ALLOCATION
 313     collectAllGarbage();
 314     ASSERT(m_heap.operationInProgress == NoOperation);
 315 #endif
 316
 317 allocate:
 318
 319     // Fast case: find the next garbage cell and recycle it.
 320
 321     do {
 322         ASSERT(m_heap.nextBlock < m_heap.usedBlocks);
 323         Block* block = m_heap.collectorBlock(m_heap.nextBlock);
 324         do {
 325             ASSERT(m_heap.nextCell < HeapConstants::cellsPerBlock);
 326             if (!block->marked.get(m_heap.nextCell)) { // Always false for the last cell in the block
 327                 Cell* cell = &block->cells[m_heap.nextCell];
 328
 329                 m_heap.operationInProgress = Allocation;
 330                 JSCell* imp = reinterpret_cast<JSCell*>(cell);
 331                 imp->~JSCell();
 332                 m_heap.operationInProgress = NoOperation;
 333
 334                 ++m_heap.nextCell;
 335                 return cell;
 336             }
 337             block->marked.advanceToNextPossibleFreeCell(m_heap.nextCell);
 338         } while (m_heap.nextCell != HeapConstants::cellsPerBlock);
 339         m_heap.nextCell = 0;
 340     } while (++m_heap.nextBlock != m_heap.usedBlocks);
 341
 342     // Slow case: reached the end of the heap. Mark live objects and start over.
 343
 344     reset();
 345     goto allocate;
 346 }
 347
 348 void Heap::resizeBlocks()
 349 {
 350     m_heap.didShrink = false;
 351
 352     size_t usedCellCount = markedCells();
 353     size_t minCellCount = usedCellCount + max(ALLOCATIONS_PER_COLLECTION, usedCellCount);
 354     size_t minBlockCount = (minCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
 355
 356     size_t maxCellCount = 1.25f * minCellCount;
 357     size_t maxBlockCount = (maxCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
 358
 359     if (m_heap.usedBlocks < minBlockCount)
 360         growBlocks(minBlockCount);
 361     else if (m_heap.usedBlocks > maxBlockCount)
 362         shrinkBlocks(maxBlockCount);
 363 }
 364
 365 void Heap::growBlocks(size_t neededBlocks)
 366 {
 367     ASSERT(m_heap.usedBlocks < neededBlocks);
 368     while (m_heap.usedBlocks < neededBlocks)
 369         allocateBlock();
 370 }
 371
 372 void Heap::shrinkBlocks(size_t neededBlocks)
 373 {
 374     ASSERT(m_heap.usedBlocks > neededBlocks);
 375
 376     // Clear the always-on last bit, so isEmpty() isn't fooled by it.
 377     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
 378         m_heap.collectorBlock(i)->marked.clear(HeapConstants::cellsPerBlock - 1);
 379
 380     for (size_t i = 0; i != m_heap.usedBlocks && m_heap.usedBlocks != neededBlocks; ) {
 381         if (m_heap.collectorBlock(i)->marked.isEmpty()) {
 382             freeBlock(i);
 383         } else
 384             ++i;
 385     }
 386
 387     // Reset the always-on last bit.
 388     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
 389         m_heap.collectorBlock(i)->marked.set(HeapConstants::cellsPerBlock - 1);
 390 }
 391
 392 #if OS(WINCE)
 393 JS_EXPORTDATA void* g_stackBase = 0;
 394
 395 inline bool isPageWritable(void* page)
 396 {
 397     MEMORY_BASIC_INFORMATION memoryInformation;
 398     DWORD result = VirtualQuery(page, &memoryInformation, sizeof(memoryInformation));
 399
 400     // return false on error, including ptr outside memory
 401     if (result != sizeof(memoryInformation))
 402         return false;
 403
 404     DWORD protect = memoryInformation.Protect & ~(PAGE_GUARD | PAGE_NOCACHE);
 405     return protect == PAGE_READWRITE
 406         || protect == PAGE_WRITECOPY
 407         || protect == PAGE_EXECUTE_READWRITE
 408         || protect == PAGE_EXECUTE_WRITECOPY;
 409 }
 410
 411 static void* getStackBase(void* previousFrame)
 412 {
 413     // find the address of this stack frame by taking the address of a local variable
 414     bool isGrowingDownward;
 415     void* thisFrame = (void*)(&isGrowingDownward);
 416
 417     isGrowingDownward = previousFrame < &thisFrame;
 418     static DWORD pageSize = 0;
 419     if (!pageSize) {
 420         SYSTEM_INFO systemInfo;
 421         GetSystemInfo(&systemInfo);
 422         pageSize = systemInfo.dwPageSize;
 423     }
 424
 425     // scan all of memory starting from this frame, and return the last writeable page found
 426     register char* currentPage = (char*)((DWORD)thisFrame & ~(pageSize - 1));
 427     if (isGrowingDownward) {
 428         while (currentPage > 0) {
 429             // check for underflow
 430             if (currentPage >= (char*)pageSize)
 431                 currentPage -= pageSize;
 432             else
 433                 currentPage = 0;
 434             if (!isPageWritable(currentPage))
 435                 return currentPage + pageSize;
 436         }
 437         return 0;
 438     } else {
 439         while (true) {
 440             // guaranteed to complete because isPageWritable returns false at end of memory
 441             currentPage += pageSize;
 442             if (!isPageWritable(currentPage))
 443                 return currentPage;
 444         }
 445     }
 446 }
 447 #endif
 448
 449 #if OS(QNX)
 450 static inline void *currentThreadStackBaseQNX()
 451 {
 452     static void* stackBase = 0;
 453     static size_t stackSize = 0;
 454     static pthread_t stackThread;
 455     pthread_t thread = pthread_self();
 456     if (stackBase == 0 || thread != stackThread) {
 457         struct _debug_thread_info threadInfo;
 458         memset(&threadInfo, 0, sizeof(threadInfo));
 459         threadInfo.tid = pthread_self();
 460         int fd = open("/proc/self", O_RDONLY);
 461         if (fd == -1) {
 462             LOG_ERROR("Unable to open /proc/self (errno: %d)", errno);
 463             return 0;
 464         }
 465         devctl(fd, DCMD_PROC_TIDSTATUS, &threadInfo, sizeof(threadInfo), 0);
 466         close(fd);
 467         stackBase = reinterpret_cast<void*>(threadInfo.stkbase);
 468         stackSize = threadInfo.stksize;
 469         ASSERT(stackBase);
 470         stackThread = thread;
 471     }
 472     return static_cast<char*>(stackBase) + stackSize;
 473 }
 474 #endif
 475
 476 static inline void* currentThreadStackBase()
 477 {
 478 #if OS(DARWIN)
 479     pthread_t thread = pthread_self();
 480     return pthread_get_stackaddr_np(thread);
 481 #elif OS(WINDOWS) && CPU(X86) && COMPILER(MSVC)
 482     // offset 0x18 from the FS segment register gives a pointer to
 483     // the thread information block for the current thread
 484     NT_TIB* pTib;
 485     __asm {
 486         MOV EAX, FS:[18h]
 487         MOV pTib, EAX
 488     }
 489     return static_cast<void*>(pTib->StackBase);
 490 #elif OS(WINDOWS) && CPU(X86) && COMPILER(GCC)
 491     // offset 0x18 from the FS segment register gives a pointer to
 492     // the thread information block for the current thread
 493     NT_TIB* pTib;
 494     asm ( "movl %%fs:0x18, %0\n"
 495           : "=r" (pTib)
 496         );
 497     return static_cast<void*>(pTib->StackBase);
 498 #elif OS(WINDOWS) && CPU(X86_64)
 499     PNT_TIB64 pTib = reinterpret_cast<PNT_TIB64>(NtCurrentTeb());
 500     return reinterpret_cast<void*>(pTib->StackBase);
 501 #elif OS(QNX)
 502     AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
 503     MutexLocker locker(mutex);
 504     return currentThreadStackBaseQNX();
 505 #elif OS(SOLARIS)
 506     stack_t s;
 507     thr_stksegment(&s);
 508     return s.ss_sp;
 509 #elif OS(OPENBSD)
 510     pthread_t thread = pthread_self();
 511     stack_t stack;
 512     pthread_stackseg_np(thread, &stack);
 513     return stack.ss_sp;
 514 #elif OS(SYMBIAN)
 515     TThreadStackInfo info;
 516     RThread thread;
 517     thread.StackInfo(info);
 518     return (void*)info.iBase;
 519 #elif OS(HAIKU)
 520     thread_info threadInfo;
 521     get_thread_info(find_thread(NULL), &threadInfo);
 522     return threadInfo.stack_end;
 523 #elif OS(UNIX)
 524     AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
 525     MutexLocker locker(mutex);
 526     static void* stackBase = 0;
 527     static size_t stackSize = 0;
 528     static pthread_t stackThread;
 529     pthread_t thread = pthread_self();
 530     if (stackBase == 0 || thread != stackThread) {
 531         pthread_attr_t sattr;
 532         pthread_attr_init(&sattr);
 533 #if HAVE(PTHREAD_NP_H) || OS(NETBSD)
 534         // e.g. on FreeBSD 5.4, neundorf@kde.org
 535         pthread_attr_get_np(thread, &sattr);
 536 #else
 537         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
 538         pthread_getattr_np(thread, &sattr);
 539 #endif
 540         int rc = pthread_attr_getstack(&sattr, &stackBase, &stackSize);
 541         (void)rc; // FIXME: Deal with error code somehow? Seems fatal.
 542         ASSERT(stackBase);
 543         pthread_attr_destroy(&sattr);
 544         stackThread = thread;
 545     }
 546     return static_cast<char*>(stackBase) + stackSize;
 547 #elif OS(WINCE)
 548     AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
 549     MutexLocker locker(mutex);
 550     if (g_stackBase)
 551         return g_stackBase;
 552     else {
 553         int dummy;
 554         return getStackBase(&dummy);
 555     }
 556 #else
 557 #error Need a way to get the stack base on this platform
 558 #endif
 559 }
 560
 561 #if ENABLE(JSC_MULTIPLE_THREADS)
 562
 563 static inline PlatformThread getCurrentPlatformThread()
 564 {
 565 #if OS(DARWIN)
 566     return pthread_mach_thread_np(pthread_self());
 567 #elif OS(WINDOWS)
 568     return pthread_getw32threadhandle_np(pthread_self());
 569 #endif
 570 }
 571
 572 void Heap::makeUsableFromMultipleThreads()
 573 {
 574     if (m_currentThreadRegistrar)
 575         return;
 576
 577     int error = pthread_key_create(&m_currentThreadRegistrar, unregisterThread);
 578     if (error)
 579         CRASH();
 580 }
 581
 582 void Heap::registerThread()
 583 {
 584     ASSERT(!m_globalData->exclusiveThread || m_globalData->exclusiveThread == currentThread());
 585
 586     if (!m_currentThreadRegistrar || pthread_getspecific(m_currentThreadRegistrar))
 587         return;
 588
 589     pthread_setspecific(m_currentThreadRegistrar, this);
 590     Heap::Thread* thread = new Heap::Thread(pthread_self(), getCurrentPlatformThread(), currentThreadStackBase());
 591
 592     MutexLocker lock(m_registeredThreadsMutex);
 593
 594     thread->next = m_registeredThreads;
 595     m_registeredThreads = thread;
 596 }
 597
 598 void Heap::unregisterThread(void* p)
 599 {
 600     if (p)
 601         static_cast<Heap*>(p)->unregisterThread();
 602 }
 603
 604 void Heap::unregisterThread()
 605 {
 606     pthread_t currentPosixThread = pthread_self();
 607
 608     MutexLocker lock(m_registeredThreadsMutex);
 609
 610     if (pthread_equal(currentPosixThread, m_registeredThreads->posixThread)) {
 611         Thread* t = m_registeredThreads;
 612         m_registeredThreads = m_registeredThreads->next;
 613         delete t;
 614     } else {
 615         Heap::Thread* last = m_registeredThreads;
 616         Heap::Thread* t;
 617         for (t = m_registeredThreads->next; t; t = t->next) {
 618             if (pthread_equal(t->posixThread, currentPosixThread)) {
 619                 last->next = t->next;
 620                 break;
 621             }
 622             last = t;
 623         }
 624         ASSERT(t); // If t is NULL, we never found ourselves in the list.
 625         delete t;
 626     }
 627 }
 628
 629 #else // ENABLE(JSC_MULTIPLE_THREADS)
 630
 631 void Heap::registerThread()
 632 {
 633 }
 634
 635 #endif
 636
 637 inline bool isPointerAligned(void* p)
 638 {
 639     return (((intptr_t)(p) & (sizeof(char*) - 1)) == 0);
 640 }
 641
 642 // Cell size needs to be a power of two for isPossibleCell to be valid.
 643 COMPILE_ASSERT(sizeof(CollectorCell) % 2 == 0, Collector_cell_size_is_power_of_two);
 644
 645 static inline bool isCellAligned(void *p)
 646 {
 647     return (((intptr_t)(p) & CELL_MASK) == 0);
 648 }
 649
 650 static inline bool isPossibleCell(void* p)
 651 {
 652     return isCellAligned(p) && p;
 653 }
 654
 655 void Heap::markConservatively(MarkStack& markStack, void* start, void* end)
 656 {
 657     if (start > end) {
 658         void* tmp = start;
 659         start = end;
 660         end = tmp;
 661     }
 662
 663     ASSERT((static_cast<char*>(end) - static_cast<char*>(start)) < 0x1000000);
 664     ASSERT(isPointerAligned(start));
 665     ASSERT(isPointerAligned(end));
 666
 667     char** p = static_cast<char**>(start);
 668     char** e = static_cast<char**>(end);
 669
 670     while (p != e) {
 671         char* x = *p++;
 672         if (isPossibleCell(x)) {
 673             size_t usedBlocks;
 674             uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
 675             xAsBits &= CELL_ALIGN_MASK;
 676
 677             uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
 678             const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
 679             if (offset > lastCellOffset)
 680                 continue;
 681
 682             CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
 683             usedBlocks = m_heap.usedBlocks;
 684             for (size_t block = 0; block < usedBlocks; block++) {
 685                 if (m_heap.collectorBlock(block) != blockAddr)
 686                     continue;
 687                 markStack.append(reinterpret_cast<JSCell*>(xAsBits));
 688             }
 689         }
 690     }
 691 }
 692
 693 void NEVER_INLINE Heap::markCurrentThreadConservativelyInternal(MarkStack& markStack)
 694 {
 695     void* dummy;
 696     void* stackPointer = &dummy;
 697     void* stackBase = currentThreadStackBase();
 698     markConservatively(markStack, stackPointer, stackBase);
 699     markStack.drain();
 700 }
 701
 702 #if COMPILER(GCC)
 703 #define REGISTER_BUFFER_ALIGNMENT __attribute__ ((aligned (sizeof(void*))))
 704 #else
 705 #define REGISTER_BUFFER_ALIGNMENT
 706 #endif
 707
 708 void Heap::markCurrentThreadConservatively(MarkStack& markStack)
 709 {
 710     // setjmp forces volatile registers onto the stack
 711     jmp_buf registers REGISTER_BUFFER_ALIGNMENT;
 712 #if COMPILER(MSVC)
 713 #pragma warning(push)
 714 #pragma warning(disable: 4611)
 715 #endif
 716     setjmp(registers);
 717 #if COMPILER(MSVC)
 718 #pragma warning(pop)
 719 #endif
 720
 721     markCurrentThreadConservativelyInternal(markStack);
 722 }
 723
 724 #if ENABLE(JSC_MULTIPLE_THREADS)
 725
 726 static inline void suspendThread(const PlatformThread& platformThread)
 727 {
 728 #if OS(DARWIN)
 729     thread_suspend(platformThread);
 730 #elif OS(WINDOWS)
 731     SuspendThread(platformThread);
 732 #else
 733 #error Need a way to suspend threads on this platform
 734 #endif
 735 }
 736
 737 static inline void resumeThread(const PlatformThread& platformThread)
 738 {
 739 #if OS(DARWIN)
 740     thread_resume(platformThread);
 741 #elif OS(WINDOWS)
 742     ResumeThread(platformThread);
 743 #else
 744 #error Need a way to resume threads on this platform
 745 #endif
 746 }
 747
 748 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
 749
 750 #if OS(DARWIN)
 751
 752 #if CPU(X86)
 753 typedef i386_thread_state_t PlatformThreadRegisters;
 754 #elif CPU(X86_64)
 755 typedef x86_thread_state64_t PlatformThreadRegisters;
 756 #elif CPU(PPC)
 757 typedef ppc_thread_state_t PlatformThreadRegisters;
 758 #elif CPU(PPC64)
 759 typedef ppc_thread_state64_t PlatformThreadRegisters;
 760 #elif CPU(ARM)
 761 typedef arm_thread_state_t PlatformThreadRegisters;
 762 #else
 763 #error Unknown Architecture
 764 #endif
 765
 766 #elif OS(WINDOWS) && CPU(X86)
 767 typedef CONTEXT PlatformThreadRegisters;
 768 #else
 769 #error Need a thread register struct for this platform
 770 #endif
 771
 772 static size_t getPlatformThreadRegisters(const PlatformThread& platformThread, PlatformThreadRegisters& regs)
 773 {
 774 #if OS(DARWIN)
 775
 776 #if CPU(X86)
 777     unsigned user_count = sizeof(regs)/sizeof(int);
 778     thread_state_flavor_t flavor = i386_THREAD_STATE;
 779 #elif CPU(X86_64)
 780     unsigned user_count = x86_THREAD_STATE64_COUNT;
 781     thread_state_flavor_t flavor = x86_THREAD_STATE64;
 782 #elif CPU(PPC)
 783     unsigned user_count = PPC_THREAD_STATE_COUNT;
 784     thread_state_flavor_t flavor = PPC_THREAD_STATE;
 785 #elif CPU(PPC64)
 786     unsigned user_count = PPC_THREAD_STATE64_COUNT;
 787     thread_state_flavor_t flavor = PPC_THREAD_STATE64;
 788 #elif CPU(ARM)
 789     unsigned user_count = ARM_THREAD_STATE_COUNT;
 790     thread_state_flavor_t flavor = ARM_THREAD_STATE;
 791 #else
 792 #error Unknown Architecture
 793 #endif
 794
 795     kern_return_t result = thread_get_state(platformThread, flavor, (thread_state_t)&regs, &user_count);
 796     if (result != KERN_SUCCESS) {
 797         WTFReportFatalError(__FILE__, __LINE__, WTF_PRETTY_FUNCTION,
 798                             "JavaScript garbage collection failed because thread_get_state returned an error (%d). This is probably the result of running inside Rosetta, which is not supported.", result);
 799         CRASH();
 800     }
 801     return user_count * sizeof(usword_t);
 802 // end OS(DARWIN)
 803
 804 #elif OS(WINDOWS) && CPU(X86)
 805     regs.ContextFlags = CONTEXT_INTEGER | CONTEXT_CONTROL | CONTEXT_SEGMENTS;
 806     GetThreadContext(platformThread, &regs);
 807     return sizeof(CONTEXT);
 808 #else
 809 #error Need a way to get thread registers on this platform
 810 #endif
 811 }
 812
 813 static inline void* otherThreadStackPointer(const PlatformThreadRegisters& regs)
 814 {
 815 #if OS(DARWIN)
 816
 817 #if __DARWIN_UNIX03
 818
 819 #if CPU(X86)
 820     return reinterpret_cast<void*>(regs.__esp);
 821 #elif CPU(X86_64)
 822     return reinterpret_cast<void*>(regs.__rsp);
 823 #elif CPU(PPC) || CPU(PPC64)
 824     return reinterpret_cast<void*>(regs.__r1);
 825 #elif CPU(ARM)
 826     return reinterpret_cast<void*>(regs.__sp);
 827 #else
 828 #error Unknown Architecture
 829 #endif
 830
 831 #else // !__DARWIN_UNIX03
 832
 833 #if CPU(X86)
 834     return reinterpret_cast<void*>(regs.esp);
 835 #elif CPU(X86_64)
 836     return reinterpret_cast<void*>(regs.rsp);
 837 #elif CPU(PPC) || CPU(PPC64)
 838     return reinterpret_cast<void*>(regs.r1);
 839 #else
 840 #error Unknown Architecture
 841 #endif
 842
 843 #endif // __DARWIN_UNIX03
 844
 845 // end OS(DARWIN)
 846 #elif CPU(X86) && OS(WINDOWS)
 847     return reinterpret_cast<void*>((uintptr_t) regs.Esp);
 848 #else
 849 #error Need a way to get the stack pointer for another thread on this platform
 850 #endif
 851 }
 852
 853 void Heap::markOtherThreadConservatively(MarkStack& markStack, Thread* thread)
 854 {
 855     suspendThread(thread->platformThread);
 856
 857     PlatformThreadRegisters regs;
 858     size_t regSize = getPlatformThreadRegisters(thread->platformThread, regs);
 859
 860     // mark the thread's registers
 861     markConservatively(markStack, static_cast<void*>(&regs), static_cast<void*>(reinterpret_cast<char*>(&regs) + regSize));
 862     markStack.drain();
 863
 864     void* stackPointer = otherThreadStackPointer(regs);
 865     markConservatively(markStack, stackPointer, thread->stackBase);
 866     markStack.drain();
 867
 868     resumeThread(thread->platformThread);
 869 }
 870
 871 #endif
 872
 873 void Heap::markStackObjectsConservatively(MarkStack& markStack)
 874 {
 875     markCurrentThreadConservatively(markStack);
 876
 877 #if ENABLE(JSC_MULTIPLE_THREADS)
 878
 879     if (m_currentThreadRegistrar) {
 880
 881         MutexLocker lock(m_registeredThreadsMutex);
 882
 883 #ifndef NDEBUG
 884         // Forbid malloc during the mark phase. Marking a thread suspends it, so
 885         // a malloc inside markChildren() would risk a deadlock with a thread that had been
 886         // suspended while holding the malloc lock.
 887         fastMallocForbid();
 888 #endif
 889         // It is safe to access the registeredThreads list, because we earlier asserted that locks are being held,
 890         // and since this is a shared heap, they are real locks.
 891         for (Thread* thread = m_registeredThreads; thread; thread = thread->next) {
 892             if (!pthread_equal(thread->posixThread, pthread_self()))
 893                 markOtherThreadConservatively(markStack, thread);
 894         }
 895 #ifndef NDEBUG
 896         fastMallocAllow();
 897 #endif
 898     }
 899 #endif
 900 }
 901
 902 void Heap::updateWeakGCHandles()
 903 {
 904     for (unsigned i = 0; i < m_weakGCHandlePools.size(); ++i)
 905         weakGCHandlePool(i)->update();
 906 }
 907
 908 void WeakGCHandlePool::update()
 909 {
 910     for (unsigned i = 1; i < WeakGCHandlePool::numPoolEntries; ++i) {
 911         if (m_entries[i].isValidPtr()) {
 912             JSCell* cell = m_entries[i].get();
 913             if (!cell || !Heap::isCellMarked(cell))
 914                 m_entries[i].invalidate();
 915         }
 916     }
 917 }
 918
 919 WeakGCHandle* Heap::addWeakGCHandle(JSCell* ptr)
 920 {
 921     for (unsigned i = 0; i < m_weakGCHandlePools.size(); ++i)
 922         if (!weakGCHandlePool(i)->isFull())
 923             return weakGCHandlePool(i)->allocate(ptr);
 924
 925     AlignedMemory<WeakGCHandlePool::poolSize> allocation = m_weakGCHandlePoolAllocator.allocate();
 926     m_weakGCHandlePools.append(allocation);
 927
 928     WeakGCHandlePool* pool = new (allocation) WeakGCHandlePool();
 929     return pool->allocate(ptr);
 930 }
 931
 932 void Heap::protect(JSValue k)
 933 {
 934     ASSERT(k);
 935     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance());
 936
 937     if (!k.isCell())
 938         return;
 939
 940     m_protectedValues.add(k.asCell());
 941 }
 942
 943 bool Heap::unprotect(JSValue k)
 944 {
 945     ASSERT(k);
 946     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance());
 947
 948     if (!k.isCell())
 949         return false;
 950
 951     return m_protectedValues.remove(k.asCell());
 952 }
 953
 954 void Heap::markProtectedObjects(MarkStack& markStack)
 955 {
 956     ProtectCountSet::iterator end = m_protectedValues.end();
 957     for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it) {
 958         markStack.append(it->first);
 959         markStack.drain();
 960     }
 961 }
 962
 963 void Heap::clearMarkBits()
 964 {
 965     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
 966         clearMarkBits(m_heap.collectorBlock(i));
 967 }
 968
 969 void Heap::clearMarkBits(CollectorBlock* block)
 970 {
 971     // allocate assumes that the last cell in every block is marked.
 972     block->marked.clearAll();
 973     block->marked.set(HeapConstants::cellsPerBlock - 1);
 974 }
 975
 976 size_t Heap::markedCells(size_t startBlock, size_t startCell) const
 977 {
 978     ASSERT(startBlock <= m_heap.usedBlocks);
 979     ASSERT(startCell < HeapConstants::cellsPerBlock);
 980
 981     if (startBlock >= m_heap.usedBlocks)
 982         return 0;
 983
 984     size_t result = 0;
 985     result += m_heap.collectorBlock(startBlock)->marked.count(startCell);
 986     for (size_t i = startBlock + 1; i < m_heap.usedBlocks; ++i)
 987         result += m_heap.collectorBlock(i)->marked.count();
 988
 989     return result;
 990 }
 991
 992 void Heap::sweep()
 993 {
 994     ASSERT(m_heap.operationInProgress == NoOperation);
 995     if (m_heap.operationInProgress != NoOperation)
 996         CRASH();
 997     m_heap.operationInProgress = Collection;
 998
 999 #if !ENABLE(JSC_ZOMBIES)
1000     Structure* dummyMarkableCellStructure = m_globalData->dummyMarkableCellStructure.get();
1001 #endif
1002
1003     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
1004     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
1005     for ( ; it != end; ++it) {
1006         JSCell* cell = *it;
1007 #if ENABLE(JSC_ZOMBIES)
1008         if (!cell->isZombie()) {
1009             const ClassInfo* info = cell->classInfo();
1010             cell->~JSCell();
1011             new (cell) JSZombie(info, JSZombie::leakedZombieStructure());
1012             Heap::markCell(cell);
1013         }
1014 #else
1015         cell->~JSCell();
1016         // Callers of sweep assume it's safe to mark any cell in the heap.
1017         new (cell) JSCell(dummyMarkableCellStructure);
1018 #endif
1019     }
1020
1021     m_heap.operationInProgress = NoOperation;
1022 }
1023
1024 void Heap::markRoots()
1025 {
1026 #ifndef NDEBUG
1027     if (m_globalData->isSharedInstance()) {
1028         ASSERT(JSLock::lockCount() > 0);
1029         ASSERT(JSLock::currentThreadIsHoldingLock());
1030     }
1031 #endif
1032
1033     ASSERT(m_heap.operationInProgress == NoOperation);
1034     if (m_heap.operationInProgress != NoOperation)
1035         CRASH();
1036
1037     m_heap.operationInProgress = Collection;
1038
1039     MarkStack& markStack = m_globalData->markStack;
1040
1041     // Reset mark bits.
1042     clearMarkBits();
1043
1044     // Mark stack roots.
1045     markStackObjectsConservatively(markStack);
1046     m_globalData->interpreter->registerFile().markCallFrames(markStack, this);
1047
1048     // Mark explicitly registered roots.
1049     markProtectedObjects(markStack);
1050
1051     // Mark misc. other roots.
1052     if (m_markListSet && m_markListSet->size())
1053         MarkedArgumentBuffer::markLists(markStack, *m_markListSet);
1054     if (m_globalData->exception)
1055         markStack.append(m_globalData->exception);
1056     if (m_globalData->firstStringifierToMark)
1057         JSONObject::markStringifiers(markStack, m_globalData->firstStringifierToMark);
1058
1059     // Mark the small strings cache last, since it will clear itself if nothing
1060     // else has marked it.
1061     m_globalData->smallStrings.markChildren(markStack);
1062
1063     markStack.drain();
1064     markStack.compact();
1065
1066     updateWeakGCHandles();
1067
1068     m_heap.operationInProgress = NoOperation;
1069 }
1070
1071 size_t Heap::objectCount() const
1072 {
1073     return m_heap.nextBlock * HeapConstants::cellsPerBlock // allocated full blocks
1074            + m_heap.nextCell // allocated cells in current block
1075            + markedCells(m_heap.nextBlock, m_heap.nextCell) // marked cells in remainder of m_heap
1076            - m_heap.usedBlocks; // 1 cell per block is a dummy sentinel
1077 }
1078
1079 void Heap::addToStatistics(Heap::Statistics& statistics) const
1080 {
1081     statistics.size += m_heap.usedBlocks * BLOCK_SIZE;
1082     statistics.free += m_heap.usedBlocks * BLOCK_SIZE - (objectCount() * HeapConstants::cellSize);
1083 }
1084
1085 Heap::Statistics Heap::statistics() const
1086 {
1087     Statistics statistics = { 0, 0 };
1088     addToStatistics(statistics);
1089     return statistics;
1090 }
1091
1092 size_t Heap::size() const
1093 {
1094     return m_heap.usedBlocks * BLOCK_SIZE;
1095 }
1096
1097 size_t Heap::globalObjectCount()
1098 {
1099     size_t count = 0;
1100     if (JSGlobalObject* head = m_globalData->head) {
1101         JSGlobalObject* o = head;
1102         do {
1103             ++count;
1104             o = o->next();
1105         } while (o != head);
1106     }
1107     return count;
1108 }
1109
1110 size_t Heap::protectedGlobalObjectCount()
1111 {
1112     size_t count = 0;
1113     if (JSGlobalObject* head = m_globalData->head) {
1114         JSGlobalObject* o = head;
1115         do {
1116             if (m_protectedValues.contains(o))
1117                 ++count;
1118             o = o->next();
1119         } while (o != head);
1120     }
1121
1122     return count;
1123 }
1124
1125 size_t Heap::protectedObjectCount()
1126 {
1127     return m_protectedValues.size();
1128 }
1129
1130 static const char* typeName(JSCell* cell)
1131 {
1132     if (cell->isString())
1133         return "string";
1134     if (cell->isGetterSetter())
1135         return "Getter-Setter";
1136     if (cell->isAPIValueWrapper())
1137         return "API wrapper";
1138     if (cell->isPropertyNameIterator())
1139         return "For-in iterator";
1140     if (!cell->isObject())
1141         return "[empty cell]";
1142     const ClassInfo* info = cell->classInfo();
1143     return info ? info->className : "Object";
1144 }
1145
1146 HashCountedSet<const char*>* Heap::protectedObjectTypeCounts()
1147 {
1148     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
1149
1150     ProtectCountSet::iterator end = m_protectedValues.end();
1151     for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it)
1152         counts->add(typeName(it->first));
1153
1154     return counts;
1155 }
1156
1157 HashCountedSet<const char*>* Heap::objectTypeCounts()
1158 {
1159     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
1160
1161     LiveObjectIterator it = primaryHeapBegin();
1162     LiveObjectIterator heapEnd = primaryHeapEnd();
1163     for ( ; it != heapEnd; ++it)
1164         counts->add(typeName(*it));
1165
1166     return counts;
1167 }
1168
1169 bool Heap::isBusy()
1170 {
1171     return m_heap.operationInProgress != NoOperation;
1172 }
1173
1174 void Heap::reset()
1175 {
1176     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
1177     JAVASCRIPTCORE_GC_BEGIN();
1178
1179     markRoots();
1180
1181     JAVASCRIPTCORE_GC_MARKED();
1182
1183     m_heap.nextCell = 0;
1184     m_heap.nextBlock = 0;
1185     m_heap.nextNumber = 0;
1186     m_heap.extraCost = 0;
1187 #if ENABLE(JSC_ZOMBIES)
1188     sweep();
1189 #endif
1190     resizeBlocks();
1191
1192     JAVASCRIPTCORE_GC_END();
1193
1194     (*m_activityCallback)();
1195 }
1196
1197 void Heap::collectAllGarbage()
1198 {
1199     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
1200     JAVASCRIPTCORE_GC_BEGIN();
1201
1202     // If the last iteration through the heap deallocated blocks, we need
1203     // to clean up remaining garbage before marking. Otherwise, the conservative
1204     // marking mechanism might follow a pointer to unmapped memory.
1205     if (m_heap.didShrink)
1206         sweep();
1207
1208     markRoots();
1209
1210     JAVASCRIPTCORE_GC_MARKED();
1211
1212     m_heap.nextCell = 0;
1213     m_heap.nextBlock = 0;
1214     m_heap.nextNumber = 0;
1215     m_heap.extraCost = 0;
1216     sweep();
1217     resizeBlocks();
1218
1219     JAVASCRIPTCORE_GC_END();
1220 }
1221
1222 LiveObjectIterator Heap::primaryHeapBegin()
1223 {
1224     return LiveObjectIterator(m_heap, 0);
1225 }
1226
1227 LiveObjectIterator Heap::primaryHeapEnd()
1228 {
1229     return LiveObjectIterator(m_heap, m_heap.usedBlocks);
1230 }
1231
1232 void Heap::setActivityCallback(PassOwnPtr<GCActivityCallback> activityCallback)
1233 {
1234     m_activityCallback = activityCallback;
1235 }
1236
1237 GCActivityCallback* Heap::activityCallback()
1238 {
1239     return m_activityCallback.get();
1240 }
1241
1242 } // namespace JSC