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