20be74c5685ff60ee3e8b8fbef665916df91ba62
[WebKit.git] / 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