01d7f23d2dc1197bc243cb603bc746452a58ecd7
[WebKit.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 byte offset -- 0 means next cell, so a zeroed block is already initialized
291   // could avoid the casts by using a cell offset, but this avoids a relatively-slow multiply
292   targetBlock->freeList = reinterpret_cast<Cell*>(reinterpret_cast<char*>(newCell + 1) + newCell->u.freeCell.next);
293
294   targetBlock->usedCells = static_cast<uint32_t>(targetBlockUsedCells + 1);
295   heap.numLiveObjects = numLiveObjects + 1;
296
297 #ifndef NDEBUG
298   // FIXME: Consider doing this in NDEBUG builds too (see comment above).
299   heap.operationInProgress = NoOperation;
300 #endif
301
302   return newCell;
303 }
304
305 void* Collector::allocate(size_t s) 
306 {
307     return heapAllocate<PrimaryHeap>(s);
308 }
309
310 void* Collector::allocateNumber(size_t s) 
311 {
312     return heapAllocate<NumberHeap>(s);
313 }
314
315 static inline void* currentThreadStackBase()
316 {
317 #if PLATFORM(DARWIN)
318     pthread_t thread = pthread_self();
319     return pthread_get_stackaddr_np(thread);
320 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
321     // offset 0x18 from the FS segment register gives a pointer to
322     // the thread information block for the current thread
323     NT_TIB* pTib;
324     __asm {
325         MOV EAX, FS:[18h]
326         MOV pTib, EAX
327     }
328     return (void*)pTib->StackBase;
329 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(GCC)
330     // offset 0x18 from the FS segment register gives a pointer to
331     // the thread information block for the current thread
332     NT_TIB* pTib;
333     asm ( "movl %%fs:0x18, %0\n"
334           : "=r" (pTib)
335         );
336     return (void*)pTib->StackBase;
337 #elif PLATFORM(UNIX)
338     static void *stackBase = 0;
339     static size_t stackSize = 0;
340     static pthread_t stackThread;
341     pthread_t thread = pthread_self();
342     if (stackBase == 0 || thread != stackThread) {
343         pthread_attr_t sattr;
344         pthread_attr_init(&sattr);
345 #if HAVE(PTHREAD_NP_H)
346         // e.g. on FreeBSD 5.4, neundorf@kde.org
347         pthread_attr_get_np(thread, &sattr);
348 #else
349         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
350         pthread_getattr_np(thread, &sattr);
351 #endif
352         int rc = pthread_attr_getstack(&sattr, &stackBase, &stackSize);
353         (void)rc; // FIXME: deal with error code somehow?  seems fatal...
354         ASSERT(stackBase);
355         pthread_attr_destroy(&sattr);
356         stackThread = thread;
357     }
358     return (void*)(size_t(stackBase) + stackSize);
359 #else
360 #error Need a way to get the stack base on this platform
361 #endif
362 }
363
364 #if USE(MULTIPLE_THREADS)
365 static pthread_t mainThread;
366 #endif
367
368 void Collector::registerAsMainThread()
369 {
370 #if USE(MULTIPLE_THREADS)
371     mainThread = pthread_self();
372 #endif
373 }
374
375 static inline bool onMainThread()
376 {
377 #if USE(MULTIPLE_THREADS)
378 #if PLATFORM(DARWIN)
379     return pthread_main_np();
380 #else
381     return !!pthread_equal(pthread_self(), mainThread);
382 #endif
383 #else
384     return true;
385 #endif
386 }
387
388 #if USE(MULTIPLE_THREADS)
389
390 #if PLATFORM(DARWIN)
391 typedef mach_port_t PlatformThread;
392 #elif PLATFORM(WIN_OS)
393 struct PlatformThread {
394     PlatformThread(DWORD _id, HANDLE _handle) : id(_id), handle(_handle) {}
395     DWORD id;
396     HANDLE handle;
397 };
398 #endif
399
400 static inline PlatformThread getCurrentPlatformThread()
401 {
402 #if PLATFORM(DARWIN)
403     return pthread_mach_thread_np(pthread_self());
404 #elif PLATFORM(WIN_OS)
405     HANDLE threadHandle = pthread_getw32threadhandle_np(pthread_self());
406     return PlatformThread(GetCurrentThreadId(), threadHandle);
407 #endif
408 }
409
410 class Collector::Thread {
411 public:
412   Thread(pthread_t pthread, const PlatformThread& platThread, void* base) 
413   : posixThread(pthread), platformThread(platThread), stackBase(base) {}
414   Thread* next;
415   pthread_t posixThread;
416   PlatformThread platformThread;
417   void* stackBase;
418 };
419
420 pthread_key_t registeredThreadKey;
421 pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;
422 Collector::Thread* registeredThreads;
423
424 static void destroyRegisteredThread(void* data) 
425 {
426   Collector::Thread* thread = (Collector::Thread*)data;
427
428   // Can't use JSLock convenience object here because we don't want to re-register
429   // an exiting thread.
430   JSLock::lock();
431   
432   if (registeredThreads == thread) {
433     registeredThreads = registeredThreads->next;
434   } else {
435     Collector::Thread *last = registeredThreads;
436     Collector::Thread *t;
437     for (t = registeredThreads->next; t != NULL; t = t->next) {
438       if (t == thread) {          
439           last->next = t->next;
440           break;
441       }
442       last = t;
443     }
444     ASSERT(t); // If t is NULL, we never found ourselves in the list.
445   }
446
447   JSLock::unlock();
448
449   delete thread;
450 }
451
452 static void initializeRegisteredThreadKey()
453 {
454   pthread_key_create(&registeredThreadKey, destroyRegisteredThread);
455 }
456
457 void Collector::registerThread()
458 {
459   ASSERT(JSLock::lockCount() > 0);
460   ASSERT(JSLock::currentThreadIsHoldingLock());
461   
462   pthread_once(&registeredThreadKeyOnce, initializeRegisteredThreadKey);
463
464   if (!pthread_getspecific(registeredThreadKey)) {
465 #if PLATFORM(DARWIN)
466       if (onMainThread())
467           CollectorHeapIntrospector::init(&primaryHeap, &numberHeap);
468 #endif
469
470     Collector::Thread *thread = new Collector::Thread(pthread_self(), getCurrentPlatformThread(), currentThreadStackBase());
471
472     thread->next = registeredThreads;
473     registeredThreads = thread;
474     pthread_setspecific(registeredThreadKey, thread);
475   }
476 }
477
478 #endif
479
480 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
481
482 // cell size needs to be a power of two for this to be valid
483 #define IS_HALF_CELL_ALIGNED(p) (((intptr_t)(p) & (CELL_MASK >> 1)) == 0)
484
485 void Collector::markStackObjectsConservatively(void *start, void *end)
486 {
487   if (start > end) {
488     void* tmp = start;
489     start = end;
490     end = tmp;
491   }
492
493   ASSERT(((char*)end - (char*)start) < 0x1000000);
494   ASSERT(IS_POINTER_ALIGNED(start));
495   ASSERT(IS_POINTER_ALIGNED(end));
496   
497   char** p = (char**)start;
498   char** e = (char**)end;
499     
500   size_t usedPrimaryBlocks = primaryHeap.usedBlocks;
501   size_t usedNumberBlocks = numberHeap.usedBlocks;
502   CollectorBlock **primaryBlocks = primaryHeap.blocks;
503   CollectorBlock **numberBlocks = numberHeap.blocks;
504
505   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
506
507   while (p != e) {
508       char* x = *p++;
509       if (IS_HALF_CELL_ALIGNED(x) && x) {
510           uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
511           xAsBits &= CELL_ALIGN_MASK;
512           uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
513           CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
514           // Mark the the number heap, we can mark these Cells directly to avoid the virtual call cost
515           for (size_t block = 0; block < usedNumberBlocks; block++) {
516               if ((numberBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
517                   Collector::markCell(reinterpret_cast<JSCell*>(xAsBits));
518                   goto endMarkLoop;
519               }
520           }
521           
522           // Mark the primary heap
523           for (size_t block = 0; block < usedPrimaryBlocks; block++) {
524               if ((primaryBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
525                   if (((CollectorCell*)xAsBits)->u.freeCell.zeroIfFree != 0) {
526                       JSCell* imp = reinterpret_cast<JSCell*>(xAsBits);
527                       if (!imp->marked())
528                           imp->mark();
529                   }
530                   break;
531               }
532           }
533       endMarkLoop:
534           ;
535       }
536   }
537 }
538
539 void Collector::markCurrentThreadConservatively()
540 {
541     // setjmp forces volatile registers onto the stack
542     jmp_buf registers;
543 #if COMPILER(MSVC)
544 #pragma warning(push)
545 #pragma warning(disable: 4611)
546 #endif
547     setjmp(registers);
548 #if COMPILER(MSVC)
549 #pragma warning(pop)
550 #endif
551
552     void* dummy;
553     void* stackPointer = &dummy;
554     void* stackBase = currentThreadStackBase();
555
556     markStackObjectsConservatively(stackPointer, stackBase);
557 }
558
559 #if USE(MULTIPLE_THREADS)
560
561 static inline void suspendThread(const PlatformThread& platformThread)
562 {
563 #if PLATFORM(DARWIN)
564   thread_suspend(platformThread);
565 #elif PLATFORM(WIN_OS)
566   SuspendThread(platformThread.handle);
567 #else
568 #error Need a way to suspend threads on this platform
569 #endif
570 }
571
572 static inline void resumeThread(const PlatformThread& platformThread)
573 {
574 #if PLATFORM(DARWIN)
575   thread_resume(platformThread);
576 #elif PLATFORM(WIN_OS)
577   ResumeThread(platformThread.handle);
578 #else
579 #error Need a way to resume threads on this platform
580 #endif
581 }
582
583 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
584
585 #if PLATFORM(DARWIN)
586
587 #if     PLATFORM(X86)
588 typedef i386_thread_state_t PlatformThreadRegisters;
589 #elif   PLATFORM(X86_64)
590 typedef x86_thread_state64_t PlatformThreadRegisters;
591 #elif   PLATFORM(PPC)
592 typedef ppc_thread_state_t PlatformThreadRegisters;
593 #elif   PLATFORM(PPC64)
594 typedef ppc_thread_state64_t PlatformThreadRegisters;
595 #else
596 #error Unknown Architecture
597 #endif
598
599 #elif PLATFORM(WIN_OS)&& PLATFORM(X86)
600 typedef CONTEXT PlatformThreadRegisters;
601 #else
602 #error Need a thread register struct for this platform
603 #endif
604
605 size_t getPlatformThreadRegisters(const PlatformThread& platformThread, PlatformThreadRegisters& regs)
606 {
607 #if PLATFORM(DARWIN)
608
609 #if     PLATFORM(X86)
610   unsigned user_count = sizeof(regs)/sizeof(int);
611   thread_state_flavor_t flavor = i386_THREAD_STATE;
612 #elif   PLATFORM(X86_64)
613   unsigned user_count = x86_THREAD_STATE64_COUNT;
614   thread_state_flavor_t flavor = x86_THREAD_STATE64;
615 #elif   PLATFORM(PPC) 
616   unsigned user_count = PPC_THREAD_STATE_COUNT;
617   thread_state_flavor_t flavor = PPC_THREAD_STATE;
618 #elif   PLATFORM(PPC64)
619   unsigned user_count = PPC_THREAD_STATE64_COUNT;
620   thread_state_flavor_t flavor = PPC_THREAD_STATE64;
621 #else
622 #error Unknown Architecture
623 #endif
624
625   kern_return_t result = thread_get_state(platformThread, flavor, (thread_state_t)&regs, &user_count);
626   if (result != KERN_SUCCESS) {
627     WTFReportFatalError(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, 
628                         "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);
629     CRASH();
630   }
631   return user_count * sizeof(usword_t);
632 // end PLATFORM(DARWIN)
633
634 #elif PLATFORM(WIN_OS) && PLATFORM(X86)
635   regs.ContextFlags = CONTEXT_INTEGER | CONTEXT_CONTROL | CONTEXT_SEGMENTS;
636   GetThreadContext(platformThread.handle, &regs);
637   return sizeof(CONTEXT);
638 #else
639 #error Need a way to get thread registers on this platform
640 #endif
641 }
642
643 static inline void* otherThreadStackPointer(const PlatformThreadRegisters& regs)
644 {
645 #if PLATFORM(DARWIN)
646
647 #if __DARWIN_UNIX03
648
649 #if PLATFORM(X86)
650   return (void*)regs.__esp;
651 #elif PLATFORM(X86_64)
652   return (void*)regs.__rsp;
653 #elif PLATFORM(PPC) || PLATFORM(PPC64)
654   return (void*)regs.__r1;
655 #else
656 #error Unknown Architecture
657 #endif
658
659 #else // !__DARWIN_UNIX03
660
661 #if PLATFORM(X86)
662   return (void*)regs.esp;
663 #elif PLATFORM(X86_64)
664   return (void*)regs.rsp;
665 #elif (PLATFORM(PPC) || PLATFORM(PPC64))
666   return (void*)regs.r1;
667 #else
668 #error Unknown Architecture
669 #endif
670
671 #endif // __DARWIN_UNIX03
672
673 // end PLATFORM(DARWIN)
674 #elif PLATFORM(X86) && PLATFORM(WIN_OS)
675   return (void*)(uintptr_t)regs.Esp;
676 #else
677 #error Need a way to get the stack pointer for another thread on this platform
678 #endif
679 }
680
681 void Collector::markOtherThreadConservatively(Thread* thread)
682 {
683   suspendThread(thread->platformThread);
684
685   PlatformThreadRegisters regs;
686   size_t regSize = getPlatformThreadRegisters(thread->platformThread, regs);
687
688   // mark the thread's registers
689   markStackObjectsConservatively((void*)&regs, (void*)((char*)&regs + regSize));
690  
691   void* stackPointer = otherThreadStackPointer(regs);
692   markStackObjectsConservatively(stackPointer, thread->stackBase);
693
694   resumeThread(thread->platformThread);
695 }
696
697 #endif
698
699 void Collector::markStackObjectsConservatively()
700 {
701   markCurrentThreadConservatively();
702
703 #if USE(MULTIPLE_THREADS)
704   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
705     if (!pthread_equal(thread->posixThread, pthread_self())) {
706       markOtherThreadConservatively(thread);
707     }
708   }
709 #endif
710 }
711
712 typedef HashCountedSet<JSCell*> ProtectCountSet;
713
714 static ProtectCountSet& protectedValues()
715 {
716     static ProtectCountSet staticProtectCountSet;
717     return staticProtectCountSet;
718 }
719
720 void Collector::protect(JSValue *k)
721 {
722     ASSERT(k);
723     ASSERT(JSLock::lockCount() > 0);
724     ASSERT(JSLock::currentThreadIsHoldingLock());
725
726     if (JSImmediate::isImmediate(k))
727       return;
728
729     protectedValues().add(k->asCell());
730 }
731
732 void Collector::unprotect(JSValue *k)
733 {
734     ASSERT(k);
735     ASSERT(JSLock::lockCount() > 0);
736     ASSERT(JSLock::currentThreadIsHoldingLock());
737
738     if (JSImmediate::isImmediate(k))
739       return;
740
741     protectedValues().remove(k->asCell());
742 }
743
744 void Collector::collectOnMainThreadOnly(JSValue* value)
745 {
746     ASSERT(value);
747     ASSERT(JSLock::lockCount() > 0);
748     ASSERT(JSLock::currentThreadIsHoldingLock());
749
750     if (JSImmediate::isImmediate(value))
751       return;
752
753     JSCell* cell = value->asCell();
754     cellBlock(cell)->collectOnMainThreadOnly.set(cellOffset(cell));
755     ++mainThreadOnlyObjectCount;
756 }
757
758 void Collector::markProtectedObjects()
759 {
760   ProtectCountSet& protectedValues = KJS::protectedValues();
761   ProtectCountSet::iterator end = protectedValues.end();
762   for (ProtectCountSet::iterator it = protectedValues.begin(); it != end; ++it) {
763     JSCell *val = it->first;
764     if (!val->marked())
765       val->mark();
766   }
767 }
768
769 void Collector::markMainThreadOnlyObjects()
770 {
771 #if USE(MULTIPLE_THREADS)
772     ASSERT(!onMainThread());
773 #endif
774
775     // Optimization for clients that never register "main thread only" objects.
776     if (!mainThreadOnlyObjectCount)
777         return;
778
779     // FIXME: We can optimize this marking algorithm by keeping an exact set of 
780     // "main thread only" objects when the "main thread only" object count is 
781     // small. We don't want to keep an exact set all the time, because WebCore 
782     // tends to create lots of "main thread only" objects, and all that set 
783     // thrashing can be expensive.
784     
785     size_t count = 0;
786     
787     // We don't look at the numberHeap as primitive values can never be marked as main thread only
788     for (size_t block = 0; block < primaryHeap.usedBlocks; block++) {
789         ASSERT(count < mainThreadOnlyObjectCount);
790         
791         CollectorBlock* curBlock = primaryHeap.blocks[block];
792         size_t minimumCellsToProcess = curBlock->usedCells;
793         for (size_t i = 0; (i < minimumCellsToProcess) & (i < CELLS_PER_BLOCK); i++) {
794             CollectorCell* cell = curBlock->cells + i;
795             if (cell->u.freeCell.zeroIfFree == 0)
796                 ++minimumCellsToProcess;
797             else {
798                 if (curBlock->collectOnMainThreadOnly.get(i)) {
799                     if (!curBlock->marked.get(i)) {
800                         JSCell* imp = reinterpret_cast<JSCell*>(cell);
801                         imp->mark();
802                     }
803                     if (++count == mainThreadOnlyObjectCount)
804                         return;
805                 }
806             }
807         }
808     }
809 }
810
811 template <Collector::HeapType heapType> size_t Collector::sweep(bool currentThreadIsMainThread)
812 {
813     typedef typename HeapConstants<heapType>::Block Block;
814     typedef typename HeapConstants<heapType>::Cell Cell;
815
816     UNUSED_PARAM(currentThreadIsMainThread); // currentThreadIsMainThread is only used in ASSERTs
817     // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
818     CollectorHeap& heap = heapType == Collector::PrimaryHeap ? primaryHeap : numberHeap;
819     
820     size_t emptyBlocks = 0;
821     size_t numLiveObjects = heap.numLiveObjects;
822     
823     for (size_t block = 0; block < heap.usedBlocks; block++) {
824         Block* curBlock = (Block*)heap.blocks[block];
825         
826         size_t usedCells = curBlock->usedCells;
827         Cell* freeList = curBlock->freeList;
828         
829         if (usedCells == HeapConstants<heapType>::cellsPerBlock) {
830             // special case with a block where all cells are used -- testing indicates this happens often
831             for (size_t i = 0; i < HeapConstants<heapType>::cellsPerBlock; i++) {
832                 if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
833                     Cell* cell = curBlock->cells + i;
834                     
835                     if (heapType != Collector::NumberHeap) {
836                         JSCell* imp = reinterpret_cast<JSCell*>(cell);
837                         // special case for allocated but uninitialized object
838                         // (We don't need this check earlier because nothing prior this point 
839                         // assumes the object has a valid vptr.)
840                         if (cell->u.freeCell.zeroIfFree == 0)
841                             continue;
842                         
843                         ASSERT(currentThreadIsMainThread || !curBlock->collectOnMainThreadOnly.get(i));
844                         if (curBlock->collectOnMainThreadOnly.get(i)) {
845                             curBlock->collectOnMainThreadOnly.clear(i);
846                             --Collector::mainThreadOnlyObjectCount;
847                         }
848                         imp->~JSCell();
849                     }
850                     
851                     --usedCells;
852                     --numLiveObjects;
853                     
854                     // put cell on the free list
855                     cell->u.freeCell.zeroIfFree = 0;
856                     cell->u.freeCell.next = reinterpret_cast<char*>(freeList) - reinterpret_cast<char*>(cell + 1);
857                     freeList = cell;
858                 }
859             }
860         } else {
861             size_t minimumCellsToProcess = usedCells;
862             for (size_t i = 0; (i < minimumCellsToProcess) & (i < HeapConstants<heapType>::cellsPerBlock); i++) {
863                 Cell *cell = curBlock->cells + i;
864                 if (cell->u.freeCell.zeroIfFree == 0) {
865                     ++minimumCellsToProcess;
866                 } else {
867                     if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
868                         if (heapType != Collector::NumberHeap) {
869                             JSCell *imp = reinterpret_cast<JSCell*>(cell);
870                             ASSERT(currentThreadIsMainThread || !curBlock->collectOnMainThreadOnly.get(i));
871                             if (curBlock->collectOnMainThreadOnly.get(i)) {
872                                 curBlock->collectOnMainThreadOnly.clear(i);
873                                 --Collector::mainThreadOnlyObjectCount;
874                             }
875                             imp->~JSCell();
876                         }
877                         --usedCells;
878                         --numLiveObjects;
879                         
880                         // put cell on the free list
881                         cell->u.freeCell.zeroIfFree = 0;
882                         cell->u.freeCell.next = reinterpret_cast<char*>(freeList) - reinterpret_cast<char*>(cell + 1);
883                         freeList = cell;
884                     }
885                 }
886             }
887         }
888         
889         curBlock->usedCells = static_cast<uint32_t>(usedCells);
890         curBlock->freeList = freeList;
891         curBlock->marked.clearAll();
892         
893         if (usedCells == 0) {
894             emptyBlocks++;
895             if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
896 #if !DEBUG_COLLECTOR
897                 freeBlock((CollectorBlock*)curBlock);
898 #endif
899                 // swap with the last block so we compact as we go
900                 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
901                 heap.usedBlocks--;
902                 block--; // Don't move forward a step in this case
903                 
904                 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
905                     heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
906                     heap.blocks = (CollectorBlock**)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
907                 }
908             }
909         }
910     }
911     
912     if (heap.numLiveObjects != numLiveObjects)
913         heap.firstBlockWithPossibleSpace = 0;
914         
915     heap.numLiveObjects = numLiveObjects;
916     heap.numLiveObjectsAtLastCollect = numLiveObjects;
917     heap.extraCost = 0;
918     return numLiveObjects;
919 }
920     
921 bool Collector::collect()
922 {
923   ASSERT(JSLock::lockCount() > 0);
924   ASSERT(JSLock::currentThreadIsHoldingLock());
925
926   ASSERT((primaryHeap.operationInProgress == NoOperation) | (numberHeap.operationInProgress == NoOperation));
927   if ((primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation))
928     abort();
929     
930   primaryHeap.operationInProgress = Collection;
931   numberHeap.operationInProgress = Collection;
932
933   bool currentThreadIsMainThread = onMainThread();
934
935   // MARK: first mark all referenced objects recursively starting out from the set of root objects
936
937 #ifndef NDEBUG
938   // Forbid malloc during the mark phase. Marking a thread suspends it, so 
939   // a malloc inside mark() would risk a deadlock with a thread that had been 
940   // suspended while holding the malloc lock.
941   fastMallocForbid();
942 #endif
943
944   markStackObjectsConservatively();
945   markProtectedObjects();
946   List::markProtectedLists();
947 #if USE(MULTIPLE_THREADS)
948   if (!currentThreadIsMainThread)
949     markMainThreadOnlyObjects();
950 #endif
951
952 #ifndef NDEBUG
953   fastMallocAllow();
954 #endif
955     
956   size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
957   size_t numLiveObjects = sweep<PrimaryHeap>(currentThreadIsMainThread);
958   numLiveObjects += sweep<NumberHeap>(currentThreadIsMainThread);
959   
960   primaryHeap.operationInProgress = NoOperation;
961   numberHeap.operationInProgress = NoOperation;
962   
963   bool newMemoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
964   if (newMemoryFull && newMemoryFull != memoryFull)
965       reportOutOfMemoryToAllExecStates();
966   memoryFull = newMemoryFull;
967
968   return numLiveObjects < originalLiveObjects;
969 }
970
971 size_t Collector::size() 
972 {
973   return primaryHeap.numLiveObjects + numberHeap.numLiveObjects; 
974 }
975
976 size_t Collector::numGlobalObjects()
977 {
978   size_t count = 0;
979   if (JSGlobalObject::head()) {
980     JSGlobalObject* o = JSGlobalObject::head();
981     do {
982       ++count;
983       o = o->next();
984     } while (o != JSGlobalObject::head());
985   }
986   return count;
987 }
988
989 size_t Collector::numProtectedObjects()
990 {
991   return protectedValues().size();
992 }
993
994 static const char *typeName(JSCell *val)
995 {
996   const char *name = "???";
997   switch (val->type()) {
998     case UnspecifiedType:
999       break;
1000     case UndefinedType:
1001       name = "undefined";
1002       break;
1003     case NullType:
1004       name = "null";
1005       break;
1006     case BooleanType:
1007       name = "boolean";
1008       break;
1009     case StringType:
1010       name = "string";
1011       break;
1012     case NumberType:
1013       name = "number";
1014       break;
1015     case ObjectType: {
1016       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
1017       name = info ? info->className : "Object";
1018       break;
1019     }
1020     case GetterSetterType:
1021       name = "gettersetter";
1022       break;
1023   }
1024   return name;
1025 }
1026
1027 HashCountedSet<const char*>* Collector::rootObjectTypeCounts()
1028 {
1029     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
1030
1031     ProtectCountSet& protectedValues = KJS::protectedValues();
1032     ProtectCountSet::iterator end = protectedValues.end();
1033     for (ProtectCountSet::iterator it = protectedValues.begin(); it != end; ++it)
1034         counts->add(typeName(it->first));
1035
1036     return counts;
1037 }
1038
1039 bool Collector::isBusy()
1040 {
1041     return (primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation);
1042 }
1043
1044 void Collector::reportOutOfMemoryToAllExecStates()
1045 {
1046     JSGlobalObject* o = JSGlobalObject::head();
1047     if (!o)
1048         return;
1049     
1050     do {
1051         ExecState* exec = o->currentExec() ? o->currentExec() : o->globalExec();
1052         exec->setException(Error::create(exec, GeneralError, "Out of memory"));
1053         o = o->next();
1054     } while(o != JSGlobalObject::head());
1055 }
1056
1057 } // namespace KJS