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