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