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