JavaScriptCore/kjs/collector.cpp

   1 /*
   2  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 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 "CollectorHeapIterator.h"
  26 #include "ExecState.h"
  27 #include "JSGlobalObject.h"
  28 #include "JSLock.h"
  29 #include "JSString.h"
  30 #include "JSValue.h"
  31 #include "Machine.h"
  32 #include "Tracing.h"
  33 #include <algorithm>
  34 #include <setjmp.h>
  35 #include <stdlib.h>
  36 #include <wtf/FastMalloc.h>
  37 #include <wtf/HashCountedSet.h>
  38 #include <wtf/UnusedParam.h>
  39
  40 #if PLATFORM(DARWIN)
  41
  42 #include <mach/mach_port.h>
  43 #include <mach/mach_init.h>
  44 #include <mach/task.h>
  45 #include <mach/thread_act.h>
  46 #include <mach/vm_map.h>
  47
  48 #elif PLATFORM(WIN_OS)
  49
  50 #include <windows.h>
  51
  52 #elif PLATFORM(UNIX)
  53
  54 #include <stdlib.h>
  55 #include <sys/mman.h>
  56 #include <unistd.h>
  57
  58 #if PLATFORM(SOLARIS)
  59 #include <thread.h>
  60 #endif
  61
  62 #if PLATFORM(OPENBSD)
  63 #include <pthread.h>
  64 #endif
  65
  66 #if HAVE(PTHREAD_NP_H)
  67 #include <pthread_np.h>
  68 #endif
  69
  70 #endif
  71
  72 #define DEBUG_COLLECTOR 0
  73 #define COLLECT_ON_EVERY_ALLOCATION 0
  74
  75 using std::max;
  76
  77 namespace JSC {
  78
  79 // tunable parameters
  80
  81 const size_t SPARE_EMPTY_BLOCKS = 2;
  82 const size_t GROWTH_FACTOR = 2;
  83 const size_t LOW_WATER_FACTOR = 4;
  84 const size_t ALLOCATIONS_PER_COLLECTION = 4000;
  85 // This value has to be a macro to be used in max() without introducing
  86 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
  87 #define MIN_ARRAY_SIZE (static_cast<size_t>(14))
  88
  89 static void freeHeap(CollectorHeap*);
  90
  91 #if ENABLE(JSC_MULTIPLE_THREADS)
  92
  93 #if PLATFORM(DARWIN)
  94 typedef mach_port_t PlatformThread;
  95 #elif PLATFORM(WIN_OS)
  96 struct PlatformThread {
  97     PlatformThread(DWORD _id, HANDLE _handle) : id(_id), handle(_handle) {}
  98     DWORD id;
  99     HANDLE handle;
 100 };
 101 #endif
 102
 103 class Heap::Thread {
 104 public:
 105     Thread(pthread_t pthread, const PlatformThread& platThread, void* base)
 106         : posixThread(pthread)
 107         , platformThread(platThread)
 108         , stackBase(base)
 109     {
 110     }
 111
 112     Thread* next;
 113     pthread_t posixThread;
 114     PlatformThread platformThread;
 115     void* stackBase;
 116 };
 117
 118 #endif
 119
 120 Heap::Heap(JSGlobalData* globalData)
 121     : m_markListSet(0)
 122 #if ENABLE(JSC_MULTIPLE_THREADS)
 123     , m_registeredThreads(0)
 124 #endif
 125     , m_globalData(globalData)
 126 {
 127     ASSERT(globalData);
 128
 129 #if ENABLE(JSC_MULTIPLE_THREADS)
 130     int error = pthread_key_create(&m_currentThreadRegistrar, unregisterThread);
 131     if (error)
 132         CRASH();
 133 #endif
 134
 135     memset(&primaryHeap, 0, sizeof(CollectorHeap));
 136     memset(&numberHeap, 0, sizeof(CollectorHeap));
 137 }
 138
 139 Heap::~Heap()
 140 {
 141     // The destroy function must already have been called, so assert this.
 142     ASSERT(!m_globalData);
 143 }
 144
 145 void Heap::destroy()
 146 {
 147     JSLock lock(false);
 148
 149     if (!m_globalData)
 150         return;
 151
 152     // The global object is not GC protected at this point, so sweeping may delete it
 153     // (and thus the global data) before other objects that may use the global data.
 154     RefPtr<JSGlobalData> protect(m_globalData);
 155
 156     delete m_markListSet;
 157     m_markListSet = 0;
 158
 159     sweep<PrimaryHeap>();
 160     // No need to sweep number heap, because the JSNumber destructor doesn't do anything.
 161
 162     ASSERT(!primaryHeap.numLiveObjects);
 163
 164     freeHeap(&primaryHeap);
 165     freeHeap(&numberHeap);
 166
 167 #if ENABLE(JSC_MULTIPLE_THREADS)
 168 #ifndef NDEBUG
 169     int error =
 170 #endif
 171         pthread_key_delete(m_currentThreadRegistrar);
 172     ASSERT(!error);
 173
 174     MutexLocker registeredThreadsLock(m_registeredThreadsMutex);
 175     for (Heap::Thread* t = m_registeredThreads; t;) {
 176         Heap::Thread* next = t->next;
 177         delete t;
 178         t = next;
 179     }
 180 #endif
 181
 182     m_globalData = 0;
 183 }
 184
 185 template <HeapType heapType>
 186 static NEVER_INLINE CollectorBlock* allocateBlock()
 187 {
 188 #if PLATFORM(DARWIN)
 189     vm_address_t address = 0;
 190     // FIXME: tag the region as a JavaScriptCore heap when we get a registered VM tag: <rdar://problem/6054788>.
 191     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);
 192 #elif PLATFORM(WIN_OS)
 193      // windows virtual address granularity is naturally 64k
 194     LPVOID address = VirtualAlloc(NULL, BLOCK_SIZE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
 195 #elif HAVE(POSIX_MEMALIGN)
 196     void* address;
 197     posix_memalign(&address, BLOCK_SIZE, BLOCK_SIZE);
 198     memset(address, 0, BLOCK_SIZE);
 199 #else
 200
 201 #if ENABLE(JSC_MULTIPLE_THREADS)
 202 #error Need to initialize pagesize safely.
 203 #endif
 204     static size_t pagesize = getpagesize();
 205
 206     size_t extra = 0;
 207     if (BLOCK_SIZE > pagesize)
 208         extra = BLOCK_SIZE - pagesize;
 209
 210     void* mmapResult = mmap(NULL, BLOCK_SIZE + extra, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
 211     uintptr_t address = reinterpret_cast<uintptr_t>(mmapResult);
 212
 213     size_t adjust = 0;
 214     if ((address & BLOCK_OFFSET_MASK) != 0)
 215         adjust = BLOCK_SIZE - (address & BLOCK_OFFSET_MASK);
 216
 217     if (adjust > 0)
 218         munmap(reinterpret_cast<char*>(address), adjust);
 219
 220     if (adjust < extra)
 221         munmap(reinterpret_cast<char*>(address + adjust + BLOCK_SIZE), extra - adjust);
 222
 223     address += adjust;
 224     memset(reinterpret_cast<void*>(address), 0, BLOCK_SIZE);
 225 #endif
 226     reinterpret_cast<CollectorBlock*>(address)->type = heapType;
 227     return reinterpret_cast<CollectorBlock*>(address);
 228 }
 229
 230 static void freeBlock(CollectorBlock* block)
 231 {
 232 #if PLATFORM(DARWIN)
 233     vm_deallocate(current_task(), reinterpret_cast<vm_address_t>(block), BLOCK_SIZE);
 234 #elif PLATFORM(WIN_OS)
 235     VirtualFree(block, 0, MEM_RELEASE);
 236 #elif HAVE(POSIX_MEMALIGN)
 237     free(block);
 238 #else
 239     munmap(reinterpret_cast<char*>(block), BLOCK_SIZE);
 240 #endif
 241 }
 242
 243 static void freeHeap(CollectorHeap* heap)
 244 {
 245     for (size_t i = 0; i < heap->usedBlocks; ++i)
 246         if (heap->blocks[i])
 247             freeBlock(heap->blocks[i]);
 248     fastFree(heap->blocks);
 249     memset(heap, 0, sizeof(CollectorHeap));
 250 }
 251
 252 void Heap::recordExtraCost(size_t cost)
 253 {
 254     // Our frequency of garbage collection tries to balance memory use against speed
 255     // by collecting based on the number of newly created values. However, for values
 256     // that hold on to a great deal of memory that's not in the form of other JS values,
 257     // that is not good enough - in some cases a lot of those objects can pile up and
 258     // use crazy amounts of memory without a GC happening. So we track these extra
 259     // memory costs. Only unusually large objects are noted, and we only keep track
 260     // of this extra cost until the next GC. In garbage collected languages, most values
 261     // are either very short lived temporaries, or have extremely long lifetimes. So
 262     // if a large value survives one garbage collection, there is not much point to
 263     // collecting more frequently as long as it stays alive.
 264     // NOTE: we target the primaryHeap unconditionally as JSNumber doesn't modify cost
 265
 266     primaryHeap.extraCost += cost;
 267 }
 268
 269 template <HeapType heapType> ALWAYS_INLINE void* Heap::heapAllocate(size_t s)
 270 {
 271     typedef typename HeapConstants<heapType>::Block Block;
 272     typedef typename HeapConstants<heapType>::Cell Cell;
 273
 274     CollectorHeap& heap = heapType == PrimaryHeap ? primaryHeap : numberHeap;
 275     ASSERT(JSLock::lockCount() > 0);
 276     ASSERT(JSLock::currentThreadIsHoldingLock());
 277     ASSERT(s <= HeapConstants<heapType>::cellSize);
 278     UNUSED_PARAM(s); // s is now only used for the above assert
 279
 280     ASSERT(heap.operationInProgress == NoOperation);
 281     ASSERT(heapType == PrimaryHeap || heap.extraCost == 0);
 282     // FIXME: If another global variable access here doesn't hurt performance
 283     // too much, we could abort() in NDEBUG builds, which could help ensure we
 284     // don't spend any time debugging cases where we allocate inside an object's
 285     // deallocation code.
 286
 287     size_t numLiveObjects = heap.numLiveObjects;
 288     size_t usedBlocks = heap.usedBlocks;
 289     size_t i = heap.firstBlockWithPossibleSpace;
 290
 291 #if COLLECT_ON_EVERY_ALLOCATION
 292     collect();
 293 #endif
 294
 295     // if we have a huge amount of extra cost, we'll try to collect even if we still have
 296     // free cells left.
 297     if (heapType == PrimaryHeap && heap.extraCost > ALLOCATIONS_PER_COLLECTION) {
 298         size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
 299         size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
 300         const size_t newCost = numNewObjects + heap.extraCost;
 301         if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect)
 302             goto collect;
 303     }
 304
 305     ASSERT(heap.operationInProgress == NoOperation);
 306 #ifndef NDEBUG
 307     // FIXME: Consider doing this in NDEBUG builds too (see comment above).
 308     heap.operationInProgress = Allocation;
 309 #endif
 310
 311 scan:
 312     Block* targetBlock;
 313     size_t targetBlockUsedCells;
 314     if (i != usedBlocks) {
 315         targetBlock = reinterpret_cast<Block*>(heap.blocks[i]);
 316         targetBlockUsedCells = targetBlock->usedCells;
 317         ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
 318         while (targetBlockUsedCells == HeapConstants<heapType>::cellsPerBlock) {
 319             if (++i == usedBlocks)
 320                 goto collect;
 321             targetBlock = reinterpret_cast<Block*>(heap.blocks[i]);
 322             targetBlockUsedCells = targetBlock->usedCells;
 323             ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
 324         }
 325         heap.firstBlockWithPossibleSpace = i;
 326     } else {
 327
 328 collect:
 329         size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
 330         size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
 331         const size_t newCost = numNewObjects + heap.extraCost;
 332
 333         if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect) {
 334 #ifndef NDEBUG
 335             heap.operationInProgress = NoOperation;
 336 #endif
 337             bool collected = collect();
 338 #ifndef NDEBUG
 339             heap.operationInProgress = Allocation;
 340 #endif
 341             if (collected) {
 342                 numLiveObjects = heap.numLiveObjects;
 343                 usedBlocks = heap.usedBlocks;
 344                 i = heap.firstBlockWithPossibleSpace;
 345                 goto scan;
 346             }
 347         }
 348
 349         // didn't find a block, and GC didn't reclaim anything, need to allocate a new block
 350         size_t numBlocks = heap.numBlocks;
 351         if (usedBlocks == numBlocks) {
 352             numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
 353             heap.numBlocks = numBlocks;
 354             heap.blocks = static_cast<CollectorBlock**>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock*)));
 355         }
 356
 357         targetBlock = reinterpret_cast<Block*>(allocateBlock<heapType>());
 358         targetBlock->freeList = targetBlock->cells;
 359         targetBlock->heap = this;
 360         targetBlockUsedCells = 0;
 361         heap.blocks[usedBlocks] = reinterpret_cast<CollectorBlock*>(targetBlock);
 362         heap.usedBlocks = usedBlocks + 1;
 363         heap.firstBlockWithPossibleSpace = usedBlocks;
 364     }
 365
 366     // find a free spot in the block and detach it from the free list
 367     Cell* newCell = targetBlock->freeList;
 368
 369     // "next" field is a cell offset -- 0 means next cell, so a zeroed block is already initialized
 370     targetBlock->freeList = (newCell + 1) + newCell->u.freeCell.next;
 371
 372     targetBlock->usedCells = static_cast<uint32_t>(targetBlockUsedCells + 1);
 373     heap.numLiveObjects = numLiveObjects + 1;
 374
 375 #ifndef NDEBUG
 376     // FIXME: Consider doing this in NDEBUG builds too (see comment above).
 377     heap.operationInProgress = NoOperation;
 378 #endif
 379
 380     return newCell;
 381 }
 382
 383 void* Heap::allocate(size_t s)
 384 {
 385     return heapAllocate<PrimaryHeap>(s);
 386 }
 387
 388 void* Heap::allocateNumber(size_t s)
 389 {
 390     return heapAllocate<NumberHeap>(s);
 391 }
 392
 393 static inline void* currentThreadStackBase()
 394 {
 395 #if PLATFORM(DARWIN)
 396     pthread_t thread = pthread_self();
 397     return pthread_get_stackaddr_np(thread);
 398 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
 399     // offset 0x18 from the FS segment register gives a pointer to
 400     // the thread information block for the current thread
 401     NT_TIB* pTib;
 402     __asm {
 403         MOV EAX, FS:[18h]
 404         MOV pTib, EAX
 405     }
 406     return static_cast<void*>(pTib->StackBase);
 407 #elif PLATFORM(WIN_OS) && PLATFORM(X86_64) && COMPILER(MSVC)
 408     PNT_TIB64 pTib = reinterpret_cast<PNT_TIB64>(NtCurrentTeb());
 409     return reinterpret_cast<void*>(pTib->StackBase);
 410 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(GCC)
 411     // offset 0x18 from the FS segment register gives a pointer to
 412     // the thread information block for the current thread
 413     NT_TIB* pTib;
 414     asm ( "movl %%fs:0x18, %0\n"
 415           : "=r" (pTib)
 416         );
 417     return static_cast<void*>(pTib->StackBase);
 418 #elif PLATFORM(SOLARIS)
 419     stack_t s;
 420     thr_stksegment(&s);
 421     return s.ss_sp;
 422 #elif PLATFORM(OPENBSD)
 423     pthread_t thread = pthread_self();
 424     stack_t stack;
 425     pthread_stackseg_np(thread, &stack);
 426     return stack.ss_sp;
 427 #elif PLATFORM(UNIX)
 428     static void* stackBase = 0;
 429     static size_t stackSize = 0;
 430     static pthread_t stackThread;
 431     pthread_t thread = pthread_self();
 432     if (stackBase == 0 || thread != stackThread) {
 433         pthread_attr_t sattr;
 434         pthread_attr_init(&sattr);
 435 #if HAVE(PTHREAD_NP_H)
 436         // e.g. on FreeBSD 5.4, neundorf@kde.org
 437         pthread_attr_get_np(thread, &sattr);
 438 #else
 439         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
 440         pthread_getattr_np(thread, &sattr);
 441 #endif
 442         int rc = pthread_attr_getstack(&sattr, &stackBase, &stackSize);
 443         (void)rc; // FIXME: Deal with error code somehow? Seems fatal.
 444         ASSERT(stackBase);
 445         pthread_attr_destroy(&sattr);
 446         stackThread = thread;
 447     }
 448     return static_cast<char*>(stackBase) + stackSize;
 449 #else
 450 #error Need a way to get the stack base on this platform
 451 #endif
 452 }
 453
 454 #if ENABLE(JSC_MULTIPLE_THREADS)
 455
 456 static inline PlatformThread getCurrentPlatformThread()
 457 {
 458 #if PLATFORM(DARWIN)
 459     return pthread_mach_thread_np(pthread_self());
 460 #elif PLATFORM(WIN_OS)
 461     HANDLE threadHandle = pthread_getw32threadhandle_np(pthread_self());
 462     return PlatformThread(GetCurrentThreadId(), threadHandle);
 463 #endif
 464 }
 465
 466 void Heap::registerThread()
 467 {
 468     if (pthread_getspecific(m_currentThreadRegistrar))
 469         return;
 470
 471     pthread_setspecific(m_currentThreadRegistrar, this);
 472     Heap::Thread* thread = new Heap::Thread(pthread_self(), getCurrentPlatformThread(), currentThreadStackBase());
 473
 474     MutexLocker lock(m_registeredThreadsMutex);
 475
 476     thread->next = m_registeredThreads;
 477     m_registeredThreads = thread;
 478 }
 479
 480 void Heap::unregisterThread(void* p)
 481 {
 482     if (p)
 483         static_cast<Heap*>(p)->unregisterThread();
 484 }
 485
 486 void Heap::unregisterThread()
 487 {
 488     pthread_t currentPosixThread = pthread_self();
 489
 490     MutexLocker lock(m_registeredThreadsMutex);
 491
 492     if (pthread_equal(currentPosixThread, m_registeredThreads->posixThread)) {
 493         Thread* t = m_registeredThreads;
 494         m_registeredThreads = m_registeredThreads->next;
 495         delete t;
 496     } else {
 497         Heap::Thread* last = m_registeredThreads;
 498         Heap::Thread* t;
 499         for (t = m_registeredThreads->next; t; t = t->next) {
 500             if (pthread_equal(t->posixThread, currentPosixThread)) {
 501                 last->next = t->next;
 502                 break;
 503             }
 504             last = t;
 505         }
 506         ASSERT(t); // If t is NULL, we never found ourselves in the list.
 507         delete t;
 508     }
 509 }
 510
 511 #else // ENABLE(JSC_MULTIPLE_THREADS)
 512
 513 void Heap::registerThread()
 514 {
 515 }
 516
 517 #endif
 518
 519 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char*) - 1)) == 0)
 520
 521 // cell size needs to be a power of two for this to be valid
 522 #define IS_HALF_CELL_ALIGNED(p) (((intptr_t)(p) & (CELL_MASK >> 1)) == 0)
 523
 524 void Heap::markConservatively(void* start, void* end)
 525 {
 526     if (start > end) {
 527         void* tmp = start;
 528         start = end;
 529         end = tmp;
 530     }
 531
 532     ASSERT((static_cast<char*>(end) - static_cast<char*>(start)) < 0x1000000);
 533     ASSERT(IS_POINTER_ALIGNED(start));
 534     ASSERT(IS_POINTER_ALIGNED(end));
 535
 536     char** p = static_cast<char**>(start);
 537     char** e = static_cast<char**>(end);
 538
 539     size_t usedPrimaryBlocks = primaryHeap.usedBlocks;
 540     size_t usedNumberBlocks = numberHeap.usedBlocks;
 541     CollectorBlock** primaryBlocks = primaryHeap.blocks;
 542     CollectorBlock** numberBlocks = numberHeap.blocks;
 543
 544     const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
 545
 546     while (p != e) {
 547         char* x = *p++;
 548         if (IS_HALF_CELL_ALIGNED(x) && x) {
 549             uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
 550             xAsBits &= CELL_ALIGN_MASK;
 551             uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
 552             CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
 553             // Mark the the number heap, we can mark these Cells directly to avoid the virtual call cost
 554             for (size_t block = 0; block < usedNumberBlocks; block++) {
 555                 if ((numberBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
 556                     Heap::markCell(reinterpret_cast<JSCell*>(xAsBits));
 557                     goto endMarkLoop;
 558                 }
 559             }
 560
 561             // Mark the primary heap
 562             for (size_t block = 0; block < usedPrimaryBlocks; block++) {
 563                 if ((primaryBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
 564                     if (reinterpret_cast<CollectorCell*>(xAsBits)->u.freeCell.zeroIfFree != 0) {
 565                         JSCell* imp = reinterpret_cast<JSCell*>(xAsBits);
 566                         if (!imp->marked())
 567                             imp->mark();
 568                     }
 569                     break;
 570                 }
 571             }
 572         endMarkLoop:
 573             ;
 574         }
 575     }
 576 }
 577
 578 void NEVER_INLINE Heap::markCurrentThreadConservativelyInternal()
 579 {
 580     void* dummy;
 581     void* stackPointer = &dummy;
 582     void* stackBase = currentThreadStackBase();
 583     markConservatively(stackPointer, stackBase);
 584 }
 585
 586 void Heap::markCurrentThreadConservatively()
 587 {
 588     // setjmp forces volatile registers onto the stack
 589     jmp_buf registers;
 590 #if COMPILER(MSVC)
 591 #pragma warning(push)
 592 #pragma warning(disable: 4611)
 593 #endif
 594     setjmp(registers);
 595 #if COMPILER(MSVC)
 596 #pragma warning(pop)
 597 #endif
 598
 599     markCurrentThreadConservativelyInternal();
 600 }
 601
 602 #if ENABLE(JSC_MULTIPLE_THREADS)
 603
 604 static inline void suspendThread(const PlatformThread& platformThread)
 605 {
 606 #if PLATFORM(DARWIN)
 607     thread_suspend(platformThread);
 608 #elif PLATFORM(WIN_OS)
 609     SuspendThread(platformThread.handle);
 610 #else
 611 #error Need a way to suspend threads on this platform
 612 #endif
 613 }
 614
 615 static inline void resumeThread(const PlatformThread& platformThread)
 616 {
 617 #if PLATFORM(DARWIN)
 618     thread_resume(platformThread);
 619 #elif PLATFORM(WIN_OS)
 620     ResumeThread(platformThread.handle);
 621 #else
 622 #error Need a way to resume threads on this platform
 623 #endif
 624 }
 625
 626 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
 627
 628 #if PLATFORM(DARWIN)
 629
 630 #if PLATFORM(X86)
 631 typedef i386_thread_state_t PlatformThreadRegisters;
 632 #elif PLATFORM(X86_64)
 633 typedef x86_thread_state64_t PlatformThreadRegisters;
 634 #elif PLATFORM(PPC)
 635 typedef ppc_thread_state_t PlatformThreadRegisters;
 636 #elif PLATFORM(PPC64)
 637 typedef ppc_thread_state64_t PlatformThreadRegisters;
 638 #elif PLATFORM(ARM)
 639 typedef arm_thread_state_t PlatformThreadRegisters;
 640 #else
 641 #error Unknown Architecture
 642 #endif
 643
 644 #elif PLATFORM(WIN_OS)&& PLATFORM(X86)
 645 typedef CONTEXT PlatformThreadRegisters;
 646 #else
 647 #error Need a thread register struct for this platform
 648 #endif
 649
 650 size_t getPlatformThreadRegisters(const PlatformThread& platformThread, PlatformThreadRegisters& regs)
 651 {
 652 #if PLATFORM(DARWIN)
 653
 654 #if PLATFORM(X86)
 655     unsigned user_count = sizeof(regs)/sizeof(int);
 656     thread_state_flavor_t flavor = i386_THREAD_STATE;
 657 #elif PLATFORM(X86_64)
 658     unsigned user_count = x86_THREAD_STATE64_COUNT;
 659     thread_state_flavor_t flavor = x86_THREAD_STATE64;
 660 #elif PLATFORM(PPC)
 661     unsigned user_count = PPC_THREAD_STATE_COUNT;
 662     thread_state_flavor_t flavor = PPC_THREAD_STATE;
 663 #elif PLATFORM(PPC64)
 664     unsigned user_count = PPC_THREAD_STATE64_COUNT;
 665     thread_state_flavor_t flavor = PPC_THREAD_STATE64;
 666 #elif PLATFORM(ARM)
 667     unsigned user_count = ARM_THREAD_STATE_COUNT;
 668     thread_state_flavor_t flavor = ARM_THREAD_STATE;
 669 #else
 670 #error Unknown Architecture
 671 #endif
 672
 673     kern_return_t result = thread_get_state(platformThread, flavor, (thread_state_t)&regs, &user_count);
 674     if (result != KERN_SUCCESS) {
 675         WTFReportFatalError(__FILE__, __LINE__, WTF_PRETTY_FUNCTION,
 676                             "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);
 677         CRASH();
 678     }
 679     return user_count * sizeof(usword_t);
 680 // end PLATFORM(DARWIN)
 681
 682 #elif PLATFORM(WIN_OS) && PLATFORM(X86)
 683     regs.ContextFlags = CONTEXT_INTEGER | CONTEXT_CONTROL | CONTEXT_SEGMENTS;
 684     GetThreadContext(platformThread.handle, &regs);
 685     return sizeof(CONTEXT);
 686 #else
 687 #error Need a way to get thread registers on this platform
 688 #endif
 689 }
 690
 691 static inline void* otherThreadStackPointer(const PlatformThreadRegisters& regs)
 692 {
 693 #if PLATFORM(DARWIN)
 694
 695 #if __DARWIN_UNIX03
 696
 697 #if PLATFORM(X86)
 698     return reinterpret_cast<void*>(regs.__esp);
 699 #elif PLATFORM(X86_64)
 700     return reinterpret_cast<void*>(regs.__rsp);
 701 #elif PLATFORM(PPC) || PLATFORM(PPC64)
 702     return reinterpret_cast<void*>(regs.__r1);
 703 #elif PLATFORM(ARM)
 704     return reinterpret_cast<void*>(regs.__sp);
 705 #else
 706 #error Unknown Architecture
 707 #endif
 708
 709 #else // !__DARWIN_UNIX03
 710
 711 #if PLATFORM(X86)
 712     return reinterpret_cast<void*>(regs.esp);
 713 #elif PLATFORM(X86_64)
 714     return reinterpret_cast<void*>(regs.rsp);
 715 #elif (PLATFORM(PPC) || PLATFORM(PPC64))
 716     return reinterpret_cast<void*>(regs.r1);
 717 #else
 718 #error Unknown Architecture
 719 #endif
 720
 721 #endif // __DARWIN_UNIX03
 722
 723 // end PLATFORM(DARWIN)
 724 #elif PLATFORM(X86) && PLATFORM(WIN_OS)
 725     return reinterpret_cast<void*>((uintptr_t) regs.Esp);
 726 #else
 727 #error Need a way to get the stack pointer for another thread on this platform
 728 #endif
 729 }
 730
 731 void Heap::markOtherThreadConservatively(Thread* thread)
 732 {
 733     suspendThread(thread->platformThread);
 734
 735     PlatformThreadRegisters regs;
 736     size_t regSize = getPlatformThreadRegisters(thread->platformThread, regs);
 737
 738     // mark the thread's registers
 739     markConservatively(static_cast<void*>(&regs), static_cast<void*>(reinterpret_cast<char*>(&regs) + regSize));
 740
 741     void* stackPointer = otherThreadStackPointer(regs);
 742     markConservatively(stackPointer, thread->stackBase);
 743
 744     resumeThread(thread->platformThread);
 745 }
 746
 747 #endif
 748
 749 void Heap::markStackObjectsConservatively()
 750 {
 751     markCurrentThreadConservatively();
 752
 753 #if ENABLE(JSC_MULTIPLE_THREADS)
 754
 755     if (m_currentThreadRegistrar) {
 756
 757         MutexLocker lock(m_registeredThreadsMutex);
 758
 759 #ifndef NDEBUG
 760         // Forbid malloc during the mark phase. Marking a thread suspends it, so
 761         // a malloc inside mark() would risk a deadlock with a thread that had been
 762         // suspended while holding the malloc lock.
 763         fastMallocForbid();
 764 #endif
 765         // It is safe to access the registeredThreads list, because we earlier asserted that locks are being held,
 766         // and since this is a shared heap, they are real locks.
 767         for (Thread* thread = m_registeredThreads; thread; thread = thread->next) {
 768             if (!pthread_equal(thread->posixThread, pthread_self()))
 769                 markOtherThreadConservatively(thread);
 770         }
 771 #ifndef NDEBUG
 772         fastMallocAllow();
 773 #endif
 774     }
 775 #endif
 776 }
 777
 778 void Heap::setGCProtectNeedsLocking()
 779 {
 780     // Most clients do not need to call this, with the notable exception of WebCore.
 781     // Clients that use shared heap have JSLock protection, while others are supposed
 782     // to do explicit locking. WebCore violates this contract in Database code,
 783     // which calls gcUnprotect from a secondary thread.
 784     if (!m_protectedValuesMutex)
 785         m_protectedValuesMutex.set(new Mutex);
 786 }
 787
 788 void Heap::protect(JSValue* k)
 789 {
 790     ASSERT(k);
 791     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance);
 792
 793     if (JSImmediate::isImmediate(k))
 794         return;
 795
 796     if (m_protectedValuesMutex)
 797         m_protectedValuesMutex->lock();
 798
 799     m_protectedValues.add(k->asCell());
 800
 801     if (m_protectedValuesMutex)
 802         m_protectedValuesMutex->unlock();
 803 }
 804
 805 void Heap::unprotect(JSValue* k)
 806 {
 807     ASSERT(k);
 808     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance);
 809
 810     if (JSImmediate::isImmediate(k))
 811         return;
 812
 813     if (m_protectedValuesMutex)
 814         m_protectedValuesMutex->lock();
 815
 816     m_protectedValues.remove(k->asCell());
 817
 818     if (m_protectedValuesMutex)
 819         m_protectedValuesMutex->unlock();
 820 }
 821
 822 Heap* Heap::heap(const JSValue* v)
 823 {
 824     if (JSImmediate::isImmediate(v))
 825         return 0;
 826     return Heap::cellBlock(v->asCell())->heap;
 827 }
 828
 829 void Heap::markProtectedObjects()
 830 {
 831     if (m_protectedValuesMutex)
 832         m_protectedValuesMutex->lock();
 833
 834     ProtectCountSet::iterator end = m_protectedValues.end();
 835     for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it) {
 836         JSCell* val = it->first;
 837         if (!val->marked())
 838             val->mark();
 839     }
 840
 841     if (m_protectedValuesMutex)
 842         m_protectedValuesMutex->unlock();
 843 }
 844
 845 template <HeapType heapType> size_t Heap::sweep()
 846 {
 847     typedef typename HeapConstants<heapType>::Block Block;
 848     typedef typename HeapConstants<heapType>::Cell Cell;
 849
 850     // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
 851     CollectorHeap& heap = heapType == PrimaryHeap ? primaryHeap : numberHeap;
 852
 853     size_t emptyBlocks = 0;
 854     size_t numLiveObjects = heap.numLiveObjects;
 855
 856     for (size_t block = 0; block < heap.usedBlocks; block++) {
 857         Block* curBlock = reinterpret_cast<Block*>(heap.blocks[block]);
 858
 859         size_t usedCells = curBlock->usedCells;
 860         Cell* freeList = curBlock->freeList;
 861
 862         if (usedCells == HeapConstants<heapType>::cellsPerBlock) {
 863             // special case with a block where all cells are used -- testing indicates this happens often
 864             for (size_t i = 0; i < HeapConstants<heapType>::cellsPerBlock; i++) {
 865                 if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
 866                     Cell* cell = curBlock->cells + i;
 867
 868                     if (heapType != NumberHeap) {
 869                         JSCell* imp = reinterpret_cast<JSCell*>(cell);
 870                         // special case for allocated but uninitialized object
 871                         // (We don't need this check earlier because nothing prior this point
 872                         // assumes the object has a valid vptr.)
 873                         if (cell->u.freeCell.zeroIfFree == 0)
 874                             continue;
 875
 876                         imp->~JSCell();
 877                     }
 878
 879                     --usedCells;
 880                     --numLiveObjects;
 881
 882                     // put cell on the free list
 883                     cell->u.freeCell.zeroIfFree = 0;
 884                     cell->u.freeCell.next = freeList - (cell + 1);
 885                     freeList = cell;
 886                 }
 887             }
 888         } else {
 889             size_t minimumCellsToProcess = usedCells;
 890             for (size_t i = 0; (i < minimumCellsToProcess) & (i < HeapConstants<heapType>::cellsPerBlock); i++) {
 891                 Cell* cell = curBlock->cells + i;
 892                 if (cell->u.freeCell.zeroIfFree == 0) {
 893                     ++minimumCellsToProcess;
 894                 } else {
 895                     if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
 896                         if (heapType != NumberHeap) {
 897                             JSCell* imp = reinterpret_cast<JSCell*>(cell);
 898                             imp->~JSCell();
 899                         }
 900                         --usedCells;
 901                         --numLiveObjects;
 902
 903                         // put cell on the free list
 904                         cell->u.freeCell.zeroIfFree = 0;
 905                         cell->u.freeCell.next = freeList - (cell + 1);
 906                         freeList = cell;
 907                     }
 908                 }
 909             }
 910         }
 911
 912         curBlock->usedCells = static_cast<uint32_t>(usedCells);
 913         curBlock->freeList = freeList;
 914         curBlock->marked.clearAll();
 915
 916         if (usedCells == 0) {
 917             emptyBlocks++;
 918             if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
 919 #if !DEBUG_COLLECTOR
 920                 freeBlock(reinterpret_cast<CollectorBlock*>(curBlock));
 921 #endif
 922                 // swap with the last block so we compact as we go
 923                 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
 924                 heap.usedBlocks--;
 925                 block--; // Don't move forward a step in this case
 926
 927                 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
 928                     heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
 929                     heap.blocks = static_cast<CollectorBlock**>(fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock*)));
 930                 }
 931             }
 932         }
 933     }
 934
 935     if (heap.numLiveObjects != numLiveObjects)
 936         heap.firstBlockWithPossibleSpace = 0;
 937
 938     heap.numLiveObjects = numLiveObjects;
 939     heap.numLiveObjectsAtLastCollect = numLiveObjects;
 940     heap.extraCost = 0;
 941     return numLiveObjects;
 942 }
 943
 944 bool Heap::collect()
 945 {
 946 #ifndef NDEBUG
 947     if (m_globalData->isSharedInstance) {
 948         ASSERT(JSLock::lockCount() > 0);
 949         ASSERT(JSLock::currentThreadIsHoldingLock());
 950     }
 951 #endif
 952
 953     ASSERT((primaryHeap.operationInProgress == NoOperation) | (numberHeap.operationInProgress == NoOperation));
 954     if ((primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation))
 955         abort();
 956
 957     JAVASCRIPTCORE_GC_BEGIN();
 958     primaryHeap.operationInProgress = Collection;
 959     numberHeap.operationInProgress = Collection;
 960
 961     // MARK: first mark all referenced objects recursively starting out from the set of root objects
 962
 963     markStackObjectsConservatively();
 964     markProtectedObjects();
 965     if (m_markListSet && m_markListSet->size())
 966         ArgList::markLists(*m_markListSet);
 967     if (m_globalData->exception && !m_globalData->exception->marked())
 968         m_globalData->exception->mark();
 969     m_globalData->machine->registerFile().markCallFrames(this);
 970     m_globalData->smallStrings.mark();
 971
 972     JSGlobalObject* globalObject = m_globalData->head;
 973     do {
 974         globalObject->markCrossHeapDependentObjects();
 975         globalObject = globalObject->next();
 976     } while (globalObject != m_globalData->head);
 977
 978     JAVASCRIPTCORE_GC_MARKED();
 979
 980     size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
 981     size_t numLiveObjects = sweep<PrimaryHeap>();
 982     numLiveObjects += sweep<NumberHeap>();
 983
 984     primaryHeap.operationInProgress = NoOperation;
 985     numberHeap.operationInProgress = NoOperation;
 986     JAVASCRIPTCORE_GC_END(originalLiveObjects, numLiveObjects);
 987
 988     return numLiveObjects < originalLiveObjects;
 989 }
 990
 991 size_t Heap::size()
 992 {
 993     return primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
 994 }
 995
 996 size_t Heap::globalObjectCount()
 997 {
 998     size_t count = 0;
 999     if (JSGlobalObject* head = m_globalData->head) {
1000         JSGlobalObject* o = head;
1001         do {
1002             ++count;
1003             o = o->next();
1004         } while (o != head);
1005     }
1006     return count;
1007 }
1008
1009 size_t Heap::protectedGlobalObjectCount()
1010 {
1011     if (m_protectedValuesMutex)
1012         m_protectedValuesMutex->lock();
1013
1014     size_t count = 0;
1015     if (JSGlobalObject* head = m_globalData->head) {
1016         JSGlobalObject* o = head;
1017         do {
1018             if (m_protectedValues.contains(o))
1019                 ++count;
1020             o = o->next();
1021         } while (o != head);
1022     }
1023
1024     if (m_protectedValuesMutex)
1025         m_protectedValuesMutex->unlock();
1026
1027     return count;
1028 }
1029
1030 size_t Heap::protectedObjectCount()
1031 {
1032     if (m_protectedValuesMutex)
1033         m_protectedValuesMutex->lock();
1034
1035     size_t result = m_protectedValues.size();
1036
1037     if (m_protectedValuesMutex)
1038         m_protectedValuesMutex->unlock();
1039
1040     return result;
1041 }
1042
1043 static const char* typeName(JSCell* val)
1044 {
1045     if (val->isString())
1046         return "string";
1047     if (val->isNumber())
1048         return "number";
1049     if (val->isGetterSetter())
1050         return "gettersetter";
1051     ASSERT(val->isObject());
1052     const ClassInfo* info = static_cast<JSObject*>(val)->classInfo();
1053     return info ? info->className : "Object";
1054 }
1055
1056 HashCountedSet<const char*>* Heap::protectedObjectTypeCounts()
1057 {
1058     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
1059
1060     if (m_protectedValuesMutex)
1061         m_protectedValuesMutex->lock();
1062
1063     ProtectCountSet::iterator end = m_protectedValues.end();
1064     for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it)
1065         counts->add(typeName(it->first));
1066
1067     if (m_protectedValuesMutex)
1068         m_protectedValuesMutex->unlock();
1069
1070     return counts;
1071 }
1072
1073 bool Heap::isBusy()
1074 {
1075     return (primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation);
1076 }
1077
1078 Heap::iterator Heap::primaryHeapBegin()
1079 {
1080     return iterator(primaryHeap.blocks, primaryHeap.blocks + primaryHeap.usedBlocks);
1081 }
1082
1083 Heap::iterator Heap::primaryHeapEnd()
1084 {
1085     return iterator(primaryHeap.blocks + primaryHeap.usedBlocks, primaryHeap.blocks + primaryHeap.usedBlocks);
1086 }
1087
1088 } // namespace JSC