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