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