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