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