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