2010-12-09 Michael Saboff <msaboff@apple.com>
[WebKit-https.git] / JavaScriptCore / runtime / Collector.cpp
1 /*
2  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
3  *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>
4  *
5  *  This library is free software; you can redistribute it and/or
6  *  modify it under the terms of the GNU Lesser General Public
7  *  License as published by the Free Software Foundation; either
8  *  version 2 of the License, or (at your option) any later version.
9  *
10  *  This library is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  *  Lesser General Public License for more details.
14  *
15  *  You should have received a copy of the GNU Lesser General Public
16  *  License along with this library; if not, write to the Free Software
17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
18  *
19  */
20
21 #include "config.h"
22 #include "Collector.h"
23
24 #include "ArgList.h"
25 #include "CallFrame.h"
26 #include "CodeBlock.h"
27 #include "CollectorHeapIterator.h"
28 #include "GCActivityCallback.h"
29 #include "Interpreter.h"
30 #include "JSArray.h"
31 #include "JSGlobalObject.h"
32 #include "JSLock.h"
33 #include "JSONObject.h"
34 #include "JSString.h"
35 #include "JSValue.h"
36 #include "JSZombie.h"
37 #include "MarkStack.h"
38 #include "Nodes.h"
39 #include "Tracing.h"
40 #include <algorithm>
41 #include <limits.h>
42 #include <setjmp.h>
43 #include <stdlib.h>
44 #include <wtf/FastMalloc.h>
45 #include <wtf/HashCountedSet.h>
46 #include <wtf/WTFThreadData.h>
47 #include <wtf/UnusedParam.h>
48 #include <wtf/VMTags.h>
49
50 #if OS(DARWIN)
51
52 #include <mach/mach_init.h>
53 #include <mach/mach_port.h>
54 #include <mach/task.h>
55 #include <mach/thread_act.h>
56 #include <mach/vm_map.h>
57
58 #elif OS(WINDOWS)
59
60 #include <windows.h>
61 #include <malloc.h>
62
63 #elif OS(HAIKU)
64
65 #include <OS.h>
66
67 #elif OS(UNIX)
68
69 #include <stdlib.h>
70 #if !OS(HAIKU)
71 #include <sys/mman.h>
72 #endif
73 #include <unistd.h>
74
75 #if OS(SOLARIS)
76 #include <thread.h>
77 #else
78 #include <pthread.h>
79 #endif
80
81 #if HAVE(PTHREAD_NP_H)
82 #include <pthread_np.h>
83 #endif
84
85 #if OS(QNX)
86 #include <fcntl.h>
87 #include <sys/procfs.h>
88 #include <stdio.h>
89 #include <errno.h>
90 #endif
91
92 #endif
93
94 #define COLLECT_ON_EVERY_ALLOCATION 0
95
96 using std::max;
97
98 namespace JSC {
99
100 // tunable parameters
101
102 const size_t GROWTH_FACTOR = 2;
103 const size_t LOW_WATER_FACTOR = 4;
104 const size_t ALLOCATIONS_PER_COLLECTION = 3600;
105 // This value has to be a macro to be used in max() without introducing
106 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
107 #define MIN_ARRAY_SIZE (static_cast<size_t>(14))
108
109 #if ENABLE(JSC_MULTIPLE_THREADS)
110
111 #if OS(DARWIN)
112 typedef mach_port_t PlatformThread;
113 #elif OS(WINDOWS)
114 typedef HANDLE PlatformThread;
115 #endif
116
117 class Heap::Thread {
118 public:
119     Thread(pthread_t pthread, const PlatformThread& platThread, void* base) 
120         : posixThread(pthread)
121         , platformThread(platThread)
122         , stackBase(base)
123     {
124     }
125
126     Thread* next;
127     pthread_t posixThread;
128     PlatformThread platformThread;
129     void* stackBase;
130 };
131
132 #endif
133
134 Heap::Heap(JSGlobalData* globalData)
135     : m_markListSet(0)
136 #if ENABLE(JSC_MULTIPLE_THREADS)
137     , m_registeredThreads(0)
138     , m_currentThreadRegistrar(0)
139 #endif
140     , m_globalData(globalData)
141 {
142     ASSERT(globalData);
143     memset(&m_heap, 0, sizeof(CollectorHeap));
144     allocateBlock();
145     m_activityCallback = DefaultGCActivityCallback::create(this);
146     (*m_activityCallback)();
147 }
148
149 Heap::~Heap()
150 {
151     // The destroy function must already have been called, so assert this.
152     ASSERT(!m_globalData);
153 }
154
155 void Heap::destroy()
156 {
157     JSLock lock(SilenceAssertionsOnly);
158
159     if (!m_globalData)
160         return;
161
162     ASSERT(!m_globalData->dynamicGlobalObject);
163     ASSERT(!isBusy());
164     
165     // The global object is not GC protected at this point, so sweeping may delete it
166     // (and thus the global data) before other objects that may use the global data.
167     RefPtr<JSGlobalData> protect(m_globalData);
168
169     delete m_markListSet;
170     m_markListSet = 0;
171
172     freeBlocks();
173
174     for (unsigned i = 0; i < m_weakGCHandlePools.size(); ++i)
175         m_weakGCHandlePools[i].deallocate();
176
177 #if ENABLE(JSC_MULTIPLE_THREADS)
178     if (m_currentThreadRegistrar) {
179         int error = pthread_key_delete(m_currentThreadRegistrar);
180         ASSERT_UNUSED(error, !error);
181     }
182
183     MutexLocker registeredThreadsLock(m_registeredThreadsMutex);
184     for (Heap::Thread* t = m_registeredThreads; t;) {
185         Heap::Thread* next = t->next;
186         delete t;
187         t = next;
188     }
189 #endif
190     m_blockallocator.destroy();
191     m_globalData = 0;
192 }
193
194 NEVER_INLINE CollectorBlock* Heap::allocateBlock()
195 {
196     AlignedCollectorBlock allocation = m_blockallocator.allocate();
197     CollectorBlock* block = static_cast<CollectorBlock*>(allocation.base());
198     if (!block)
199         CRASH();
200
201     // Initialize block.
202
203     block->heap = this;
204     clearMarkBits(block);
205
206     Structure* dummyMarkableCellStructure = m_globalData->dummyMarkableCellStructure.get();
207     for (size_t i = 0; i < HeapConstants::cellsPerBlock; ++i)
208         new (&block->cells[i]) JSCell(dummyMarkableCellStructure);
209     
210     // Add block to blocks vector.
211
212     size_t numBlocks = m_heap.numBlocks;
213     if (m_heap.usedBlocks == numBlocks) {
214         static const size_t maxNumBlocks = ULONG_MAX / sizeof(AlignedCollectorBlock) / GROWTH_FACTOR;
215         if (numBlocks > maxNumBlocks)
216             CRASH();
217         numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
218         m_heap.numBlocks = numBlocks;
219         m_heap.blocks = static_cast<AlignedCollectorBlock*>(fastRealloc(m_heap.blocks, numBlocks * sizeof(AlignedCollectorBlock)));
220     }
221     m_heap.blocks[m_heap.usedBlocks++] = allocation;
222
223     return block;
224 }
225
226 NEVER_INLINE void Heap::freeBlock(size_t block)
227 {
228     m_heap.didShrink = true;
229
230     ObjectIterator it(m_heap, block);
231     ObjectIterator end(m_heap, block + 1);
232     for ( ; it != end; ++it)
233         (*it)->~JSCell();
234     m_heap.blocks[block].deallocate();
235
236     // swap with the last block so we compact as we go
237     m_heap.blocks[block] = m_heap.blocks[m_heap.usedBlocks - 1];
238     m_heap.usedBlocks--;
239
240     if (m_heap.numBlocks > MIN_ARRAY_SIZE && m_heap.usedBlocks < m_heap.numBlocks / LOW_WATER_FACTOR) {
241         m_heap.numBlocks = m_heap.numBlocks / GROWTH_FACTOR; 
242         m_heap.blocks = static_cast<AlignedCollectorBlock*>(fastRealloc(m_heap.blocks, m_heap.numBlocks * sizeof(AlignedCollectorBlock)));
243     }
244 }
245
246 void Heap::freeBlocks()
247 {
248     ProtectCountSet protectedValuesCopy = m_protectedValues;
249
250     clearMarkBits();
251     ProtectCountSet::iterator protectedValuesEnd = protectedValuesCopy.end();
252     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
253         markCell(it->first);
254
255     m_heap.nextCell = 0;
256     m_heap.nextBlock = 0;
257     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
258     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
259     for ( ; it != end; ++it)
260         (*it)->~JSCell();
261
262     ASSERT(!protectedObjectCount());
263
264     protectedValuesEnd = protectedValuesCopy.end();
265     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
266         it->first->~JSCell();
267
268     for (size_t block = 0; block < m_heap.usedBlocks; ++block)
269         m_heap.blocks[block].deallocate();
270
271     fastFree(m_heap.blocks);
272
273     memset(&m_heap, 0, sizeof(CollectorHeap));
274 }
275
276 void Heap::recordExtraCost(size_t cost)
277 {
278     // Our frequency of garbage collection tries to balance memory use against speed
279     // by collecting based on the number of newly created values. However, for values
280     // that hold on to a great deal of memory that's not in the form of other JS values,
281     // that is not good enough - in some cases a lot of those objects can pile up and
282     // use crazy amounts of memory without a GC happening. So we track these extra
283     // memory costs. Only unusually large objects are noted, and we only keep track
284     // of this extra cost until the next GC. In garbage collected languages, most values
285     // are either very short lived temporaries, or have extremely long lifetimes. So
286     // if a large value survives one garbage collection, there is not much point to
287     // collecting more frequently as long as it stays alive.
288
289     if (m_heap.extraCost > maxExtraCost && m_heap.extraCost > m_heap.usedBlocks * BLOCK_SIZE / 2) {
290         // If the last iteration through the heap deallocated blocks, we need
291         // to clean up remaining garbage before marking. Otherwise, the conservative
292         // marking mechanism might follow a pointer to unmapped memory.
293         if (m_heap.didShrink)
294             sweep();
295         reset();
296     }
297     m_heap.extraCost += cost;
298 }
299
300 void* Heap::allocate(size_t s)
301 {
302     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
303     typedef HeapConstants::Block Block;
304     typedef HeapConstants::Cell Cell;
305     
306     ASSERT(JSLock::lockCount() > 0);
307     ASSERT(JSLock::currentThreadIsHoldingLock());
308     ASSERT_UNUSED(s, s <= HeapConstants::cellSize);
309
310     ASSERT(m_heap.operationInProgress == NoOperation);
311
312 #if COLLECT_ON_EVERY_ALLOCATION
313     collectAllGarbage();
314     ASSERT(m_heap.operationInProgress == NoOperation);
315 #endif
316
317 allocate:
318
319     // Fast case: find the next garbage cell and recycle it.
320
321     do {
322         ASSERT(m_heap.nextBlock < m_heap.usedBlocks);
323         Block* block = m_heap.collectorBlock(m_heap.nextBlock);
324         do {
325             ASSERT(m_heap.nextCell < HeapConstants::cellsPerBlock);
326             if (!block->marked.get(m_heap.nextCell)) { // Always false for the last cell in the block
327                 Cell* cell = &block->cells[m_heap.nextCell];
328
329                 m_heap.operationInProgress = Allocation;
330                 JSCell* imp = reinterpret_cast<JSCell*>(cell);
331                 imp->~JSCell();
332                 m_heap.operationInProgress = NoOperation;
333
334                 ++m_heap.nextCell;
335                 return cell;
336             }
337             block->marked.advanceToNextPossibleFreeCell(m_heap.nextCell);
338         } while (m_heap.nextCell != HeapConstants::cellsPerBlock);
339         m_heap.nextCell = 0;
340     } while (++m_heap.nextBlock != m_heap.usedBlocks);
341
342     // Slow case: reached the end of the heap. Mark live objects and start over.
343
344     reset();
345     goto allocate;
346 }
347
348 void Heap::resizeBlocks()
349 {
350     m_heap.didShrink = false;
351
352     size_t usedCellCount = markedCells();
353     size_t minCellCount = usedCellCount + max(ALLOCATIONS_PER_COLLECTION, usedCellCount);
354     size_t minBlockCount = (minCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
355
356     size_t maxCellCount = 1.25f * minCellCount;
357     size_t maxBlockCount = (maxCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
358
359     if (m_heap.usedBlocks < minBlockCount)
360         growBlocks(minBlockCount);
361     else if (m_heap.usedBlocks > maxBlockCount)
362         shrinkBlocks(maxBlockCount);
363 }
364
365 void Heap::growBlocks(size_t neededBlocks)
366 {
367     ASSERT(m_heap.usedBlocks < neededBlocks);
368     while (m_heap.usedBlocks < neededBlocks)
369         allocateBlock();
370 }
371
372 void Heap::shrinkBlocks(size_t neededBlocks)
373 {
374     ASSERT(m_heap.usedBlocks > neededBlocks);
375     
376     // Clear the always-on last bit, so isEmpty() isn't fooled by it.
377     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
378         m_heap.collectorBlock(i)->marked.clear(HeapConstants::cellsPerBlock - 1);
379
380     for (size_t i = 0; i != m_heap.usedBlocks && m_heap.usedBlocks != neededBlocks; ) {
381         if (m_heap.collectorBlock(i)->marked.isEmpty()) {
382             freeBlock(i);
383         } else
384             ++i;
385     }
386
387     // Reset the always-on last bit.
388     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
389         m_heap.collectorBlock(i)->marked.set(HeapConstants::cellsPerBlock - 1);
390 }
391
392 #if OS(WINCE)
393 JS_EXPORTDATA void* g_stackBase = 0;
394
395 inline bool isPageWritable(void* page)
396 {
397     MEMORY_BASIC_INFORMATION memoryInformation;
398     DWORD result = VirtualQuery(page, &memoryInformation, sizeof(memoryInformation));
399
400     // return false on error, including ptr outside memory
401     if (result != sizeof(memoryInformation))
402         return false;
403
404     DWORD protect = memoryInformation.Protect & ~(PAGE_GUARD | PAGE_NOCACHE);
405     return protect == PAGE_READWRITE
406         || protect == PAGE_WRITECOPY
407         || protect == PAGE_EXECUTE_READWRITE
408         || protect == PAGE_EXECUTE_WRITECOPY;
409 }
410
411 static void* getStackBase(void* previousFrame)
412 {
413     // find the address of this stack frame by taking the address of a local variable
414     bool isGrowingDownward;
415     void* thisFrame = (void*)(&isGrowingDownward);
416
417     isGrowingDownward = previousFrame < &thisFrame;
418     static DWORD pageSize = 0;
419     if (!pageSize) {
420         SYSTEM_INFO systemInfo;
421         GetSystemInfo(&systemInfo);
422         pageSize = systemInfo.dwPageSize;
423     }
424
425     // scan all of memory starting from this frame, and return the last writeable page found
426     register char* currentPage = (char*)((DWORD)thisFrame & ~(pageSize - 1));
427     if (isGrowingDownward) {
428         while (currentPage > 0) {
429             // check for underflow
430             if (currentPage >= (char*)pageSize)
431                 currentPage -= pageSize;
432             else
433                 currentPage = 0;
434             if (!isPageWritable(currentPage))
435                 return currentPage + pageSize;
436         }
437         return 0;
438     } else {
439         while (true) {
440             // guaranteed to complete because isPageWritable returns false at end of memory
441             currentPage += pageSize;
442             if (!isPageWritable(currentPage))
443                 return currentPage;
444         }
445     }
446 }
447 #endif
448
449 #if OS(QNX)
450 static inline void *currentThreadStackBaseQNX()
451 {
452     static void* stackBase = 0;
453     static size_t stackSize = 0;
454     static pthread_t stackThread;
455     pthread_t thread = pthread_self();
456     if (stackBase == 0 || thread != stackThread) {
457         struct _debug_thread_info threadInfo;
458         memset(&threadInfo, 0, sizeof(threadInfo));
459         threadInfo.tid = pthread_self();
460         int fd = open("/proc/self", O_RDONLY);
461         if (fd == -1) {
462             LOG_ERROR("Unable to open /proc/self (errno: %d)", errno);
463             return 0;
464         }
465         devctl(fd, DCMD_PROC_TIDSTATUS, &threadInfo, sizeof(threadInfo), 0);
466         close(fd);
467         stackBase = reinterpret_cast<void*>(threadInfo.stkbase);
468         stackSize = threadInfo.stksize;
469         ASSERT(stackBase);
470         stackThread = thread;
471     }
472     return static_cast<char*>(stackBase) + stackSize;
473 }
474 #endif
475
476 static inline void* currentThreadStackBase()
477 {
478 #if OS(DARWIN)
479     pthread_t thread = pthread_self();
480     return pthread_get_stackaddr_np(thread);
481 #elif OS(WINDOWS) && CPU(X86) && COMPILER(MSVC)
482     // offset 0x18 from the FS segment register gives a pointer to
483     // the thread information block for the current thread
484     NT_TIB* pTib;
485     __asm {
486         MOV EAX, FS:[18h]
487         MOV pTib, EAX
488     }
489     return static_cast<void*>(pTib->StackBase);
490 #elif OS(WINDOWS) && CPU(X86) && COMPILER(GCC)
491     // offset 0x18 from the FS segment register gives a pointer to
492     // the thread information block for the current thread
493     NT_TIB* pTib;
494     asm ( "movl %%fs:0x18, %0\n"
495           : "=r" (pTib)
496         );
497     return static_cast<void*>(pTib->StackBase);
498 #elif OS(WINDOWS) && CPU(X86_64)
499     PNT_TIB64 pTib = reinterpret_cast<PNT_TIB64>(NtCurrentTeb());
500     return reinterpret_cast<void*>(pTib->StackBase);
501 #elif OS(QNX)
502     AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
503     MutexLocker locker(mutex);
504     return currentThreadStackBaseQNX();
505 #elif OS(SOLARIS)
506     stack_t s;
507     thr_stksegment(&s);
508     return s.ss_sp;
509 #elif OS(OPENBSD)
510     pthread_t thread = pthread_self();
511     stack_t stack;
512     pthread_stackseg_np(thread, &stack);
513     return stack.ss_sp;
514 #elif OS(SYMBIAN)
515     TThreadStackInfo info;
516     RThread thread;
517     thread.StackInfo(info);
518     return (void*)info.iBase;
519 #elif OS(HAIKU)
520     thread_info threadInfo;
521     get_thread_info(find_thread(NULL), &threadInfo);
522     return threadInfo.stack_end;
523 #elif OS(UNIX)
524     AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
525     MutexLocker locker(mutex);
526     static void* stackBase = 0;
527     static size_t stackSize = 0;
528     static pthread_t stackThread;
529     pthread_t thread = pthread_self();
530     if (stackBase == 0 || thread != stackThread) {
531         pthread_attr_t sattr;
532         pthread_attr_init(&sattr);
533 #if HAVE(PTHREAD_NP_H) || OS(NETBSD)
534         // e.g. on FreeBSD 5.4, neundorf@kde.org
535         pthread_attr_get_np(thread, &sattr);
536 #else
537         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
538         pthread_getattr_np(thread, &sattr);
539 #endif
540         int rc = pthread_attr_getstack(&sattr, &stackBase, &stackSize);
541         (void)rc; // FIXME: Deal with error code somehow? Seems fatal.
542         ASSERT(stackBase);
543         pthread_attr_destroy(&sattr);
544         stackThread = thread;
545     }
546     return static_cast<char*>(stackBase) + stackSize;
547 #elif OS(WINCE)
548     AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
549     MutexLocker locker(mutex);
550     if (g_stackBase)
551         return g_stackBase;
552     else {
553         int dummy;
554         return getStackBase(&dummy);
555     }
556 #else
557 #error Need a way to get the stack base on this platform
558 #endif
559 }
560
561 #if ENABLE(JSC_MULTIPLE_THREADS)
562
563 static inline PlatformThread getCurrentPlatformThread()
564 {
565 #if OS(DARWIN)
566     return pthread_mach_thread_np(pthread_self());
567 #elif OS(WINDOWS)
568     return pthread_getw32threadhandle_np(pthread_self());
569 #endif
570 }
571
572 void Heap::makeUsableFromMultipleThreads()
573 {
574     if (m_currentThreadRegistrar)
575         return;
576
577     int error = pthread_key_create(&m_currentThreadRegistrar, unregisterThread);
578     if (error)
579         CRASH();
580 }
581
582 void Heap::registerThread()
583 {
584     ASSERT(!m_globalData->exclusiveThread || m_globalData->exclusiveThread == currentThread());
585
586     if (!m_currentThreadRegistrar || pthread_getspecific(m_currentThreadRegistrar))
587         return;
588
589     pthread_setspecific(m_currentThreadRegistrar, this);
590     Heap::Thread* thread = new Heap::Thread(pthread_self(), getCurrentPlatformThread(), currentThreadStackBase());
591
592     MutexLocker lock(m_registeredThreadsMutex);
593
594     thread->next = m_registeredThreads;
595     m_registeredThreads = thread;
596 }
597
598 void Heap::unregisterThread(void* p)
599 {
600     if (p)
601         static_cast<Heap*>(p)->unregisterThread();
602 }
603
604 void Heap::unregisterThread()
605 {
606     pthread_t currentPosixThread = pthread_self();
607
608     MutexLocker lock(m_registeredThreadsMutex);
609
610     if (pthread_equal(currentPosixThread, m_registeredThreads->posixThread)) {
611         Thread* t = m_registeredThreads;
612         m_registeredThreads = m_registeredThreads->next;
613         delete t;
614     } else {
615         Heap::Thread* last = m_registeredThreads;
616         Heap::Thread* t;
617         for (t = m_registeredThreads->next; t; t = t->next) {
618             if (pthread_equal(t->posixThread, currentPosixThread)) {
619                 last->next = t->next;
620                 break;
621             }
622             last = t;
623         }
624         ASSERT(t); // If t is NULL, we never found ourselves in the list.
625         delete t;
626     }
627 }
628
629 #else // ENABLE(JSC_MULTIPLE_THREADS)
630
631 void Heap::registerThread()
632 {
633 }
634
635 #endif
636
637 inline bool isPointerAligned(void* p)
638 {
639     return (((intptr_t)(p) & (sizeof(char*) - 1)) == 0);
640 }
641
642 // Cell size needs to be a power of two for isPossibleCell to be valid.
643 COMPILE_ASSERT(sizeof(CollectorCell) % 2 == 0, Collector_cell_size_is_power_of_two);
644
645 static inline bool isCellAligned(void *p)
646 {
647     return (((intptr_t)(p) & CELL_MASK) == 0);
648 }
649
650 static inline bool isPossibleCell(void* p)
651 {
652     return isCellAligned(p) && p;
653 }
654
655 void Heap::markConservatively(MarkStack& markStack, void* start, void* end)
656 {
657     if (start > end) {
658         void* tmp = start;
659         start = end;
660         end = tmp;
661     }
662
663     ASSERT((static_cast<char*>(end) - static_cast<char*>(start)) < 0x1000000);
664     ASSERT(isPointerAligned(start));
665     ASSERT(isPointerAligned(end));
666
667     char** p = static_cast<char**>(start);
668     char** e = static_cast<char**>(end);
669
670     while (p != e) {
671         char* x = *p++;
672         if (isPossibleCell(x)) {
673             size_t usedBlocks;
674             uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
675             xAsBits &= CELL_ALIGN_MASK;
676
677             uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
678             const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
679             if (offset > lastCellOffset)
680                 continue;
681
682             CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
683             usedBlocks = m_heap.usedBlocks;
684             for (size_t block = 0; block < usedBlocks; block++) {
685                 if (m_heap.collectorBlock(block) != blockAddr)
686                     continue;
687                 markStack.append(reinterpret_cast<JSCell*>(xAsBits));
688             }
689         }
690     }
691 }
692
693 void NEVER_INLINE Heap::markCurrentThreadConservativelyInternal(MarkStack& markStack)
694 {
695     void* dummy;
696     void* stackPointer = &dummy;
697     void* stackBase = currentThreadStackBase();
698     markConservatively(markStack, stackPointer, stackBase);
699     markStack.drain();
700 }
701
702 #if COMPILER(GCC)
703 #define REGISTER_BUFFER_ALIGNMENT __attribute__ ((aligned (sizeof(void*))))
704 #else
705 #define REGISTER_BUFFER_ALIGNMENT
706 #endif
707
708 void Heap::markCurrentThreadConservatively(MarkStack& markStack)
709 {
710     // setjmp forces volatile registers onto the stack
711     jmp_buf registers REGISTER_BUFFER_ALIGNMENT;
712 #if COMPILER(MSVC)
713 #pragma warning(push)
714 #pragma warning(disable: 4611)
715 #endif
716     setjmp(registers);
717 #if COMPILER(MSVC)
718 #pragma warning(pop)
719 #endif
720
721     markCurrentThreadConservativelyInternal(markStack);
722 }
723
724 #if ENABLE(JSC_MULTIPLE_THREADS)
725
726 static inline void suspendThread(const PlatformThread& platformThread)
727 {
728 #if OS(DARWIN)
729     thread_suspend(platformThread);
730 #elif OS(WINDOWS)
731     SuspendThread(platformThread);
732 #else
733 #error Need a way to suspend threads on this platform
734 #endif
735 }
736
737 static inline void resumeThread(const PlatformThread& platformThread)
738 {
739 #if OS(DARWIN)
740     thread_resume(platformThread);
741 #elif OS(WINDOWS)
742     ResumeThread(platformThread);
743 #else
744 #error Need a way to resume threads on this platform
745 #endif
746 }
747
748 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
749
750 #if OS(DARWIN)
751
752 #if CPU(X86)
753 typedef i386_thread_state_t PlatformThreadRegisters;
754 #elif CPU(X86_64)
755 typedef x86_thread_state64_t PlatformThreadRegisters;
756 #elif CPU(PPC)
757 typedef ppc_thread_state_t PlatformThreadRegisters;
758 #elif CPU(PPC64)
759 typedef ppc_thread_state64_t PlatformThreadRegisters;
760 #elif CPU(ARM)
761 typedef arm_thread_state_t PlatformThreadRegisters;
762 #else
763 #error Unknown Architecture
764 #endif
765
766 #elif OS(WINDOWS) && CPU(X86)
767 typedef CONTEXT PlatformThreadRegisters;
768 #else
769 #error Need a thread register struct for this platform
770 #endif
771
772 static size_t getPlatformThreadRegisters(const PlatformThread& platformThread, PlatformThreadRegisters& regs)
773 {
774 #if OS(DARWIN)
775
776 #if CPU(X86)
777     unsigned user_count = sizeof(regs)/sizeof(int);
778     thread_state_flavor_t flavor = i386_THREAD_STATE;
779 #elif CPU(X86_64)
780     unsigned user_count = x86_THREAD_STATE64_COUNT;
781     thread_state_flavor_t flavor = x86_THREAD_STATE64;
782 #elif CPU(PPC) 
783     unsigned user_count = PPC_THREAD_STATE_COUNT;
784     thread_state_flavor_t flavor = PPC_THREAD_STATE;
785 #elif CPU(PPC64)
786     unsigned user_count = PPC_THREAD_STATE64_COUNT;
787     thread_state_flavor_t flavor = PPC_THREAD_STATE64;
788 #elif CPU(ARM)
789     unsigned user_count = ARM_THREAD_STATE_COUNT;
790     thread_state_flavor_t flavor = ARM_THREAD_STATE;
791 #else
792 #error Unknown Architecture
793 #endif
794
795     kern_return_t result = thread_get_state(platformThread, flavor, (thread_state_t)&regs, &user_count);
796     if (result != KERN_SUCCESS) {
797         WTFReportFatalError(__FILE__, __LINE__, WTF_PRETTY_FUNCTION, 
798                             "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);
799         CRASH();
800     }
801     return user_count * sizeof(usword_t);
802 // end OS(DARWIN)
803
804 #elif OS(WINDOWS) && CPU(X86)
805     regs.ContextFlags = CONTEXT_INTEGER | CONTEXT_CONTROL | CONTEXT_SEGMENTS;
806     GetThreadContext(platformThread, &regs);
807     return sizeof(CONTEXT);
808 #else
809 #error Need a way to get thread registers on this platform
810 #endif
811 }
812
813 static inline void* otherThreadStackPointer(const PlatformThreadRegisters& regs)
814 {
815 #if OS(DARWIN)
816
817 #if __DARWIN_UNIX03
818
819 #if CPU(X86)
820     return reinterpret_cast<void*>(regs.__esp);
821 #elif CPU(X86_64)
822     return reinterpret_cast<void*>(regs.__rsp);
823 #elif CPU(PPC) || CPU(PPC64)
824     return reinterpret_cast<void*>(regs.__r1);
825 #elif CPU(ARM)
826     return reinterpret_cast<void*>(regs.__sp);
827 #else
828 #error Unknown Architecture
829 #endif
830
831 #else // !__DARWIN_UNIX03
832
833 #if CPU(X86)
834     return reinterpret_cast<void*>(regs.esp);
835 #elif CPU(X86_64)
836     return reinterpret_cast<void*>(regs.rsp);
837 #elif CPU(PPC) || CPU(PPC64)
838     return reinterpret_cast<void*>(regs.r1);
839 #else
840 #error Unknown Architecture
841 #endif
842
843 #endif // __DARWIN_UNIX03
844
845 // end OS(DARWIN)
846 #elif CPU(X86) && OS(WINDOWS)
847     return reinterpret_cast<void*>((uintptr_t) regs.Esp);
848 #else
849 #error Need a way to get the stack pointer for another thread on this platform
850 #endif
851 }
852
853 void Heap::markOtherThreadConservatively(MarkStack& markStack, Thread* thread)
854 {
855     suspendThread(thread->platformThread);
856
857     PlatformThreadRegisters regs;
858     size_t regSize = getPlatformThreadRegisters(thread->platformThread, regs);
859
860     // mark the thread's registers
861     markConservatively(markStack, static_cast<void*>(&regs), static_cast<void*>(reinterpret_cast<char*>(&regs) + regSize));
862     markStack.drain();
863
864     void* stackPointer = otherThreadStackPointer(regs);
865     markConservatively(markStack, stackPointer, thread->stackBase);
866     markStack.drain();
867
868     resumeThread(thread->platformThread);
869 }
870
871 #endif
872
873 void Heap::markStackObjectsConservatively(MarkStack& markStack)
874 {
875     markCurrentThreadConservatively(markStack);
876
877 #if ENABLE(JSC_MULTIPLE_THREADS)
878
879     if (m_currentThreadRegistrar) {
880
881         MutexLocker lock(m_registeredThreadsMutex);
882
883 #ifndef NDEBUG
884         // Forbid malloc during the mark phase. Marking a thread suspends it, so 
885         // a malloc inside markChildren() would risk a deadlock with a thread that had been 
886         // suspended while holding the malloc lock.
887         fastMallocForbid();
888 #endif
889         // It is safe to access the registeredThreads list, because we earlier asserted that locks are being held,
890         // and since this is a shared heap, they are real locks.
891         for (Thread* thread = m_registeredThreads; thread; thread = thread->next) {
892             if (!pthread_equal(thread->posixThread, pthread_self()))
893                 markOtherThreadConservatively(markStack, thread);
894         }
895 #ifndef NDEBUG
896         fastMallocAllow();
897 #endif
898     }
899 #endif
900 }
901
902 void Heap::updateWeakGCHandles()
903 {
904     for (unsigned i = 0; i < m_weakGCHandlePools.size(); ++i)
905         weakGCHandlePool(i)->update();
906 }
907
908 void WeakGCHandlePool::update()
909 {
910     for (unsigned i = 1; i < WeakGCHandlePool::numPoolEntries; ++i) {
911         if (m_entries[i].isValidPtr()) {
912             JSCell* cell = m_entries[i].get();
913             if (!cell || !Heap::isCellMarked(cell))
914                 m_entries[i].invalidate();
915         }
916     }
917 }
918
919 WeakGCHandle* Heap::addWeakGCHandle(JSCell* ptr)
920 {
921     for (unsigned i = 0; i < m_weakGCHandlePools.size(); ++i)
922         if (!weakGCHandlePool(i)->isFull())
923             return weakGCHandlePool(i)->allocate(ptr);
924
925     AlignedMemory<WeakGCHandlePool::poolSize> allocation = m_weakGCHandlePoolAllocator.allocate();
926     m_weakGCHandlePools.append(allocation);
927
928     WeakGCHandlePool* pool = new (allocation) WeakGCHandlePool();
929     return pool->allocate(ptr);
930 }
931
932 void Heap::protect(JSValue k)
933 {
934     ASSERT(k);
935     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance());
936
937     if (!k.isCell())
938         return;
939
940     m_protectedValues.add(k.asCell());
941 }
942
943 bool Heap::unprotect(JSValue k)
944 {
945     ASSERT(k);
946     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance());
947
948     if (!k.isCell())
949         return false;
950
951     return m_protectedValues.remove(k.asCell());
952 }
953
954 void Heap::markProtectedObjects(MarkStack& markStack)
955 {
956     ProtectCountSet::iterator end = m_protectedValues.end();
957     for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it) {
958         markStack.append(it->first);
959         markStack.drain();
960     }
961 }
962
963 void Heap::pushTempSortVector(Vector<ValueStringPair>* tempVector)
964 {
965     m_tempSortingVectors.append(tempVector);
966 }
967
968 void Heap::popTempSortVector(Vector<ValueStringPair>* tempVector)
969 {
970     ASSERT_UNUSED(tempVector, tempVector == m_tempSortingVectors.last());
971     m_tempSortingVectors.removeLast();
972 }
973     
974 void Heap::markTempSortVectors(MarkStack& markStack)
975 {
976     typedef Vector<Vector<ValueStringPair>* > VectorOfValueStringVectors;
977
978     VectorOfValueStringVectors::iterator end = m_tempSortingVectors.end();
979     for (VectorOfValueStringVectors::iterator it = m_tempSortingVectors.begin(); it != end; ++it) {
980         Vector<ValueStringPair>* tempSortingVector = *it;
981
982         Vector<ValueStringPair>::iterator vectorEnd = tempSortingVector->end();
983         for (Vector<ValueStringPair>::iterator vectorIt = tempSortingVector->begin(); vectorIt != vectorEnd; ++vectorIt)
984             if (vectorIt->first)
985                 markStack.append(vectorIt->first);
986         markStack.drain();
987     }
988 }
989     
990 void Heap::clearMarkBits()
991 {
992     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
993         clearMarkBits(m_heap.collectorBlock(i));
994 }
995
996 void Heap::clearMarkBits(CollectorBlock* block)
997 {
998     // allocate assumes that the last cell in every block is marked.
999     block->marked.clearAll();
1000     block->marked.set(HeapConstants::cellsPerBlock - 1);
1001 }
1002
1003 size_t Heap::markedCells(size_t startBlock, size_t startCell) const
1004 {
1005     ASSERT(startBlock <= m_heap.usedBlocks);
1006     ASSERT(startCell < HeapConstants::cellsPerBlock);
1007
1008     if (startBlock >= m_heap.usedBlocks)
1009         return 0;
1010
1011     size_t result = 0;
1012     result += m_heap.collectorBlock(startBlock)->marked.count(startCell);
1013     for (size_t i = startBlock + 1; i < m_heap.usedBlocks; ++i)
1014         result += m_heap.collectorBlock(i)->marked.count();
1015
1016     return result;
1017 }
1018
1019 void Heap::sweep()
1020 {
1021     ASSERT(m_heap.operationInProgress == NoOperation);
1022     if (m_heap.operationInProgress != NoOperation)
1023         CRASH();
1024     m_heap.operationInProgress = Collection;
1025     
1026 #if !ENABLE(JSC_ZOMBIES)
1027     Structure* dummyMarkableCellStructure = m_globalData->dummyMarkableCellStructure.get();
1028 #endif
1029
1030     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
1031     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
1032     for ( ; it != end; ++it) {
1033         JSCell* cell = *it;
1034 #if ENABLE(JSC_ZOMBIES)
1035         if (!cell->isZombie()) {
1036             const ClassInfo* info = cell->classInfo();
1037             cell->~JSCell();
1038             new (cell) JSZombie(info, JSZombie::leakedZombieStructure());
1039             Heap::markCell(cell);
1040         }
1041 #else
1042         cell->~JSCell();
1043         // Callers of sweep assume it's safe to mark any cell in the heap.
1044         new (cell) JSCell(dummyMarkableCellStructure);
1045 #endif
1046     }
1047
1048     m_heap.operationInProgress = NoOperation;
1049 }
1050
1051 void Heap::markRoots()
1052 {
1053 #ifndef NDEBUG
1054     if (m_globalData->isSharedInstance()) {
1055         ASSERT(JSLock::lockCount() > 0);
1056         ASSERT(JSLock::currentThreadIsHoldingLock());
1057     }
1058 #endif
1059
1060     ASSERT(m_heap.operationInProgress == NoOperation);
1061     if (m_heap.operationInProgress != NoOperation)
1062         CRASH();
1063
1064     m_heap.operationInProgress = Collection;
1065
1066     MarkStack& markStack = m_globalData->markStack;
1067
1068     // Reset mark bits.
1069     clearMarkBits();
1070
1071     // Mark stack roots.
1072     markStackObjectsConservatively(markStack);
1073     m_globalData->interpreter->registerFile().markCallFrames(markStack, this);
1074
1075     // Mark explicitly registered roots.
1076     markProtectedObjects(markStack);
1077     
1078     // Mark temporary vector for Array sorting
1079     markTempSortVectors(markStack);
1080
1081     // Mark misc. other roots.
1082     if (m_markListSet && m_markListSet->size())
1083         MarkedArgumentBuffer::markLists(markStack, *m_markListSet);
1084     if (m_globalData->exception)
1085         markStack.append(m_globalData->exception);
1086     if (m_globalData->firstStringifierToMark)
1087         JSONObject::markStringifiers(markStack, m_globalData->firstStringifierToMark);
1088
1089     // Mark the small strings cache last, since it will clear itself if nothing
1090     // else has marked it.
1091     m_globalData->smallStrings.markChildren(markStack);
1092
1093     markStack.drain();
1094     markStack.compact();
1095
1096     updateWeakGCHandles();
1097
1098     m_heap.operationInProgress = NoOperation;
1099 }
1100
1101 size_t Heap::objectCount() const
1102 {
1103     return m_heap.nextBlock * HeapConstants::cellsPerBlock // allocated full blocks
1104            + m_heap.nextCell // allocated cells in current block
1105            + markedCells(m_heap.nextBlock, m_heap.nextCell) // marked cells in remainder of m_heap
1106            - m_heap.usedBlocks; // 1 cell per block is a dummy sentinel
1107 }
1108
1109 void Heap::addToStatistics(Heap::Statistics& statistics) const
1110 {
1111     statistics.size += m_heap.usedBlocks * BLOCK_SIZE;
1112     statistics.free += m_heap.usedBlocks * BLOCK_SIZE - (objectCount() * HeapConstants::cellSize);
1113 }
1114
1115 Heap::Statistics Heap::statistics() const
1116 {
1117     Statistics statistics = { 0, 0 };
1118     addToStatistics(statistics);
1119     return statistics;
1120 }
1121
1122 size_t Heap::size() const
1123 {
1124     return m_heap.usedBlocks * BLOCK_SIZE;
1125 }
1126
1127 size_t Heap::globalObjectCount()
1128 {
1129     size_t count = 0;
1130     if (JSGlobalObject* head = m_globalData->head) {
1131         JSGlobalObject* o = head;
1132         do {
1133             ++count;
1134             o = o->next();
1135         } while (o != head);
1136     }
1137     return count;
1138 }
1139
1140 size_t Heap::protectedGlobalObjectCount()
1141 {
1142     size_t count = 0;
1143     if (JSGlobalObject* head = m_globalData->head) {
1144         JSGlobalObject* o = head;
1145         do {
1146             if (m_protectedValues.contains(o))
1147                 ++count;
1148             o = o->next();
1149         } while (o != head);
1150     }
1151
1152     return count;
1153 }
1154
1155 size_t Heap::protectedObjectCount()
1156 {
1157     return m_protectedValues.size();
1158 }
1159
1160 static const char* typeName(JSCell* cell)
1161 {
1162     if (cell->isString())
1163         return "string";
1164     if (cell->isGetterSetter())
1165         return "Getter-Setter";
1166     if (cell->isAPIValueWrapper())
1167         return "API wrapper";
1168     if (cell->isPropertyNameIterator())
1169         return "For-in iterator";
1170     if (!cell->isObject())
1171         return "[empty cell]";
1172     const ClassInfo* info = cell->classInfo();
1173     return info ? info->className : "Object";
1174 }
1175
1176 HashCountedSet<const char*>* Heap::protectedObjectTypeCounts()
1177 {
1178     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
1179
1180     ProtectCountSet::iterator end = m_protectedValues.end();
1181     for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it)
1182         counts->add(typeName(it->first));
1183
1184     return counts;
1185 }
1186
1187 HashCountedSet<const char*>* Heap::objectTypeCounts()
1188 {
1189     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
1190
1191     LiveObjectIterator it = primaryHeapBegin();
1192     LiveObjectIterator heapEnd = primaryHeapEnd();
1193     for ( ; it != heapEnd; ++it)
1194         counts->add(typeName(*it));
1195
1196     return counts;
1197 }
1198
1199 bool Heap::isBusy()
1200 {
1201     return m_heap.operationInProgress != NoOperation;
1202 }
1203
1204 void Heap::reset()
1205 {
1206     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
1207     JAVASCRIPTCORE_GC_BEGIN();
1208
1209     markRoots();
1210
1211     JAVASCRIPTCORE_GC_MARKED();
1212
1213     m_heap.nextCell = 0;
1214     m_heap.nextBlock = 0;
1215     m_heap.nextNumber = 0;
1216     m_heap.extraCost = 0;
1217 #if ENABLE(JSC_ZOMBIES)
1218     sweep();
1219 #endif
1220     resizeBlocks();
1221
1222     JAVASCRIPTCORE_GC_END();
1223
1224     (*m_activityCallback)();
1225 }
1226
1227 void Heap::collectAllGarbage()
1228 {
1229     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
1230     JAVASCRIPTCORE_GC_BEGIN();
1231
1232     // If the last iteration through the heap deallocated blocks, we need
1233     // to clean up remaining garbage before marking. Otherwise, the conservative
1234     // marking mechanism might follow a pointer to unmapped memory.
1235     if (m_heap.didShrink)
1236         sweep();
1237
1238     markRoots();
1239
1240     JAVASCRIPTCORE_GC_MARKED();
1241
1242     m_heap.nextCell = 0;
1243     m_heap.nextBlock = 0;
1244     m_heap.nextNumber = 0;
1245     m_heap.extraCost = 0;
1246     sweep();
1247     resizeBlocks();
1248
1249     JAVASCRIPTCORE_GC_END();
1250 }
1251
1252 LiveObjectIterator Heap::primaryHeapBegin()
1253 {
1254     return LiveObjectIterator(m_heap, 0);
1255 }
1256
1257 LiveObjectIterator Heap::primaryHeapEnd()
1258 {
1259     return LiveObjectIterator(m_heap, m_heap.usedBlocks);
1260 }
1261
1262 void Heap::setActivityCallback(PassOwnPtr<GCActivityCallback> activityCallback)
1263 {
1264     m_activityCallback = activityCallback;
1265 }
1266
1267 GCActivityCallback* Heap::activityCallback()
1268 {
1269     return m_activityCallback.get();
1270 }
1271
1272 } // namespace JSC