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