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