13d0432bae24d33c50969e51b903a61b55fd00dc
[WebKit-https.git] / JavaScriptCore / kjs / collector.cpp
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  *  Copyright (C) 2003, 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
4  *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>
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 "ExecState.h"
26 #include "JSGlobalObject.h"
27 #include "internal.h"
28 #include "list.h"
29 #include "value.h"
30 #include <algorithm>
31 #include <setjmp.h>
32 #include <stdlib.h>
33 #include <wtf/FastMalloc.h>
34 #include <wtf/HashCountedSet.h>
35 #include <wtf/UnusedParam.h>
36
37 #if USE(MULTIPLE_THREADS)
38 #include <pthread.h>
39 #include <wtf/ThreadSpecific.h>
40 #endif
41
42 #if PLATFORM(DARWIN)
43
44 #include <mach/mach_port.h>
45 #include <mach/mach_init.h>
46 #include <mach/task.h>
47 #include <mach/thread_act.h>
48 #include <mach/vm_map.h>
49
50 #include "CollectorHeapIntrospector.h"
51
52 #elif PLATFORM(WIN_OS)
53
54 #include <windows.h>
55
56 #elif PLATFORM(UNIX)
57
58 #include <stdlib.h>
59 #include <sys/mman.h>
60 #include <unistd.h>
61
62 #if PLATFORM(SOLARIS)
63 #include <thread.h>
64 #endif
65
66 #if HAVE(PTHREAD_NP_H)
67 #include <pthread_np.h>
68 #else
69 #include <pthread.h>
70 #endif
71
72 #endif
73
74 #define DEBUG_COLLECTOR 0
75 #define COLLECT_ON_EVERY_ALLOCATION 0
76
77 using std::max;
78 using namespace WTF;
79
80 namespace KJS {
81
82 // tunable parameters
83
84 #define SPARE_EMPTY_BLOCKS 2UL
85 #define MIN_ARRAY_SIZE 14UL
86 #define GROWTH_FACTOR 2UL
87 #define LOW_WATER_FACTOR 4UL
88 #define ALLOCATIONS_PER_COLLECTION 4000UL
89
90 Heap::Heap()
91 {
92     memset(this, 0, sizeof(Heap));
93 }
94
95 Heap* Heap::threadHeap()
96 {
97 #if USE(MULTIPLE_THREADS)
98     static ThreadSpecific<Heap> sharedInstance;
99     return sharedInstance;
100 #else
101     static Heap sharedInstance;
102     return &sharedInstance;
103 #endif
104 }
105
106 static NEVER_INLINE CollectorBlock* allocateBlock()
107 {
108 #if PLATFORM(DARWIN)    
109     vm_address_t address = 0;
110     vm_map(current_task(), &address, BLOCK_SIZE, BLOCK_OFFSET_MASK, VM_FLAGS_ANYWHERE, MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_DEFAULT, VM_INHERIT_DEFAULT);
111 #elif PLATFORM(WIN_OS)
112      // windows virtual address granularity is naturally 64k
113     LPVOID address = VirtualAlloc(NULL, BLOCK_SIZE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
114 #elif HAVE(POSIX_MEMALIGN)
115     void* address;
116     posix_memalign(&address, BLOCK_SIZE, BLOCK_SIZE);
117     memset(address, 0, BLOCK_SIZE);
118 #else
119     static size_t pagesize = getpagesize();
120     
121     size_t extra = 0;
122     if (BLOCK_SIZE > pagesize)
123         extra = BLOCK_SIZE - pagesize;
124
125     void* mmapResult = mmap(NULL, BLOCK_SIZE + extra, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
126     uintptr_t address = reinterpret_cast<uintptr_t>(mmapResult);
127
128     size_t adjust = 0;
129     if ((address & BLOCK_OFFSET_MASK) != 0)
130         adjust = BLOCK_SIZE - (address & BLOCK_OFFSET_MASK);
131
132     if (adjust > 0)
133         munmap(reinterpret_cast<void*>(address), adjust);
134
135     if (adjust < extra)
136         munmap(reinterpret_cast<void*>(address + adjust + BLOCK_SIZE), extra - adjust);
137
138     address += adjust;
139     memset(reinterpret_cast<void*>(address), 0, BLOCK_SIZE);
140 #endif
141
142     return reinterpret_cast<CollectorBlock*>(address);
143 }
144
145 static void freeBlock(CollectorBlock* block)
146 {
147 #if PLATFORM(DARWIN)    
148     vm_deallocate(current_task(), reinterpret_cast<vm_address_t>(block), BLOCK_SIZE);
149 #elif PLATFORM(WIN_OS)
150     VirtualFree(block, BLOCK_SIZE, MEM_RELEASE);
151 #elif HAVE(POSIX_MEMALIGN)
152     free(block);
153 #else
154     munmap(block, BLOCK_SIZE);
155 #endif
156 }
157
158 void Heap::recordExtraCost(size_t cost)
159 {
160     // Our frequency of garbage collection tries to balance memory use against speed
161     // by collecting based on the number of newly created values. However, for values
162     // that hold on to a great deal of memory that's not in the form of other JS values,
163     // that is not good enough - in some cases a lot of those objects can pile up and
164     // use crazy amounts of memory without a GC happening. So we track these extra
165     // memory costs. Only unusually large objects are noted, and we only keep track
166     // of this extra cost until the next GC. In garbage collected languages, most values
167     // are either very short lived temporaries, or have extremely long lifetimes. So
168     // if a large value survives one garbage collection, there is not much point to
169     // collecting more frequently as long as it stays alive.
170     // NOTE: we target the primaryHeap unconditionally as JSNumber doesn't modify cost 
171
172     primaryHeap.extraCost += cost;
173 }
174
175 template <Heap::HeapType heapType> struct HeapConstants;
176
177 template <> struct HeapConstants<Heap::PrimaryHeap> {
178     static const size_t cellSize = CELL_SIZE;
179     static const size_t cellsPerBlock = CELLS_PER_BLOCK;
180     static const size_t bitmapShift = 0;
181     typedef CollectorCell Cell;
182     typedef CollectorBlock Block;
183 };
184
185 template <> struct HeapConstants<Heap::NumberHeap> {
186     static const size_t cellSize = SMALL_CELL_SIZE;
187     static const size_t cellsPerBlock = SMALL_CELLS_PER_BLOCK;
188     static const size_t bitmapShift = 1;
189     typedef SmallCollectorCell Cell;
190     typedef SmallCellCollectorBlock Block;
191 };
192
193 template <Heap::HeapType heapType> void* Heap::heapAllocate(size_t s)
194 {
195   typedef typename HeapConstants<heapType>::Block Block;
196   typedef typename HeapConstants<heapType>::Cell Cell;
197
198   CollectorHeap& heap = heapType == PrimaryHeap ? primaryHeap : numberHeap;
199   ASSERT(JSLock::lockCount() > 0);
200   ASSERT(JSLock::currentThreadIsHoldingLock());
201   ASSERT(this == threadHeap());
202   ASSERT(s <= HeapConstants<heapType>::cellSize);
203   UNUSED_PARAM(s); // s is now only used for the above assert
204
205   ASSERT(heap.operationInProgress == NoOperation);
206   ASSERT(heapType == PrimaryHeap || heap.extraCost == 0);
207   // FIXME: If another global variable access here doesn't hurt performance
208   // too much, we could abort() in NDEBUG builds, which could help ensure we
209   // don't spend any time debugging cases where we allocate inside an object's
210   // deallocation code.
211
212   size_t numLiveObjects = heap.numLiveObjects;
213   size_t usedBlocks = heap.usedBlocks;
214   size_t i = heap.firstBlockWithPossibleSpace;
215
216 #if COLLECT_ON_EVERY_ALLOCATION
217   collect();
218 #endif
219
220   // if we have a huge amount of extra cost, we'll try to collect even if we still have
221   // free cells left.
222   if (heapType == PrimaryHeap && heap.extraCost > ALLOCATIONS_PER_COLLECTION) {
223       size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
224       size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
225       const size_t newCost = numNewObjects + heap.extraCost;
226       if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect)
227           goto collect;
228   }
229
230   ASSERT(heap.operationInProgress == NoOperation);
231 #ifndef NDEBUG
232   // FIXME: Consider doing this in NDEBUG builds too (see comment above).
233   heap.operationInProgress = Allocation;
234 #endif
235
236 scan:
237   Block* targetBlock;
238   size_t targetBlockUsedCells;
239   if (i != usedBlocks) {
240     targetBlock = (Block*)heap.blocks[i];
241     targetBlockUsedCells = targetBlock->usedCells;
242     ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
243     while (targetBlockUsedCells == HeapConstants<heapType>::cellsPerBlock) {
244       if (++i == usedBlocks)
245         goto collect;
246       targetBlock = (Block*)heap.blocks[i];
247       targetBlockUsedCells = targetBlock->usedCells;
248       ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
249     }
250     heap.firstBlockWithPossibleSpace = i;
251   } else {
252
253 collect:
254     size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
255     size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
256     const size_t newCost = numNewObjects + heap.extraCost;
257
258     if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect) {
259 #ifndef NDEBUG
260       heap.operationInProgress = NoOperation;
261 #endif
262       bool collected = collect();
263 #ifndef NDEBUG
264       heap.operationInProgress = Allocation;
265 #endif
266       if (collected) {
267         numLiveObjects = heap.numLiveObjects;
268         usedBlocks = heap.usedBlocks;
269         i = heap.firstBlockWithPossibleSpace;
270         goto scan;
271       }
272     }
273   
274     // didn't find a block, and GC didn't reclaim anything, need to allocate a new block
275     size_t numBlocks = heap.numBlocks;
276     if (usedBlocks == numBlocks) {
277       numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
278       heap.numBlocks = numBlocks;
279       heap.blocks = static_cast<CollectorBlock **>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock *)));
280     }
281
282     targetBlock = (Block*)allocateBlock();
283     targetBlock->freeList = targetBlock->cells;
284     targetBlock->heap = this;
285     targetBlockUsedCells = 0;
286     heap.blocks[usedBlocks] = (CollectorBlock*)targetBlock;
287     heap.usedBlocks = usedBlocks + 1;
288     heap.firstBlockWithPossibleSpace = usedBlocks;
289   }
290   
291   // find a free spot in the block and detach it from the free list
292   Cell *newCell = targetBlock->freeList;
293   
294   // "next" field is a cell offset -- 0 means next cell, so a zeroed block is already initialized
295   targetBlock->freeList = (newCell + 1) + newCell->u.freeCell.next;
296
297   targetBlock->usedCells = static_cast<uint32_t>(targetBlockUsedCells + 1);
298   heap.numLiveObjects = numLiveObjects + 1;
299
300 #ifndef NDEBUG
301   // FIXME: Consider doing this in NDEBUG builds too (see comment above).
302   heap.operationInProgress = NoOperation;
303 #endif
304
305   return newCell;
306 }
307
308 void* Heap::allocate(size_t s) 
309 {
310     return heapAllocate<PrimaryHeap>(s);
311 }
312
313 void* Heap::allocateNumber(size_t s) 
314 {
315     return heapAllocate<NumberHeap>(s);
316 }
317
318 static inline void* currentThreadStackBase()
319 {
320 #if PLATFORM(DARWIN)
321     pthread_t thread = pthread_self();
322     return pthread_get_stackaddr_np(thread);
323 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
324     // offset 0x18 from the FS segment register gives a pointer to
325     // the thread information block for the current thread
326     NT_TIB* pTib;
327     __asm {
328         MOV EAX, FS:[18h]
329         MOV pTib, EAX
330     }
331     return (void*)pTib->StackBase;
332 #elif PLATFORM(WIN_OS) && PLATFORM(X86_64) && COMPILER(MSVC)
333     PNT_TIB64 pTib = reinterpret_cast<PNT_TIB64>(NtCurrentTeb());
334     return (void*)pTib->StackBase;
335 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(GCC)
336     // offset 0x18 from the FS segment register gives a pointer to
337     // the thread information block for the current thread
338     NT_TIB* pTib;
339     asm ( "movl %%fs:0x18, %0\n"
340           : "=r" (pTib)
341         );
342     return (void*)pTib->StackBase;
343 #elif PLATFORM(SOLARIS)
344     stack_t s;
345     thr_stksegment(&s);
346     return s.ss_sp;
347 #elif PLATFORM(UNIX)
348     static void* stackBase = 0;
349     static size_t stackSize = 0;
350     static pthread_t stackThread;
351     pthread_t thread = pthread_self();
352     if (stackBase == 0 || thread != stackThread) {
353         pthread_attr_t sattr;
354         pthread_attr_init(&sattr);
355 #if HAVE(PTHREAD_NP_H)
356         // e.g. on FreeBSD 5.4, neundorf@kde.org
357         pthread_attr_get_np(thread, &sattr);
358 #else
359         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
360         pthread_getattr_np(thread, &sattr);
361 #endif
362         int rc = pthread_attr_getstack(&sattr, &stackBase, &stackSize);
363         (void)rc; // FIXME: Deal with error code somehow? Seems fatal.
364         ASSERT(stackBase);
365         pthread_attr_destroy(&sattr);
366         stackThread = thread;
367     }
368     return static_cast<char*>(stackBase) + stackSize;
369 #else
370 #error Need a way to get the stack base on this platform
371 #endif
372 }
373
374 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
375
376 // cell size needs to be a power of two for this to be valid
377 #define IS_HALF_CELL_ALIGNED(p) (((intptr_t)(p) & (CELL_MASK >> 1)) == 0)
378
379 void Heap::markStackObjectsConservatively(void *start, void *end)
380 {
381   if (start > end) {
382     void* tmp = start;
383     start = end;
384     end = tmp;
385   }
386
387   ASSERT(((char*)end - (char*)start) < 0x1000000);
388   ASSERT(IS_POINTER_ALIGNED(start));
389   ASSERT(IS_POINTER_ALIGNED(end));
390   
391   char** p = (char**)start;
392   char** e = (char**)end;
393     
394   size_t usedPrimaryBlocks = primaryHeap.usedBlocks;
395   size_t usedNumberBlocks = numberHeap.usedBlocks;
396   CollectorBlock **primaryBlocks = primaryHeap.blocks;
397   CollectorBlock **numberBlocks = numberHeap.blocks;
398
399   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
400
401   while (p != e) {
402       char* x = *p++;
403       if (IS_HALF_CELL_ALIGNED(x) && x) {
404           uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
405           xAsBits &= CELL_ALIGN_MASK;
406           uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
407           CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
408           // Mark the the number heap, we can mark these Cells directly to avoid the virtual call cost
409           for (size_t block = 0; block < usedNumberBlocks; block++) {
410               if ((numberBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
411                   Heap::markCell(reinterpret_cast<JSCell*>(xAsBits));
412                   goto endMarkLoop;
413               }
414           }
415           
416           // Mark the primary heap
417           for (size_t block = 0; block < usedPrimaryBlocks; block++) {
418               if ((primaryBlocks[block] == blockAddr) & (offset <= lastCellOffset)) {
419                   if (((CollectorCell*)xAsBits)->u.freeCell.zeroIfFree != 0) {
420                       JSCell* imp = reinterpret_cast<JSCell*>(xAsBits);
421                       if (!imp->marked())
422                           imp->mark();
423                   }
424                   break;
425               }
426           }
427       endMarkLoop:
428           ;
429       }
430   }
431 }
432
433 void NEVER_INLINE Heap::markStackObjectsConservativelyInternal()
434 {
435     void* dummy;
436     void* stackPointer = &dummy;
437     void* stackBase = currentThreadStackBase();
438     markStackObjectsConservatively(stackPointer, stackBase);
439 }
440
441 void Heap::markStackObjectsConservatively()
442 {
443     // setjmp forces volatile registers onto the stack
444     jmp_buf registers;
445 #if COMPILER(MSVC)
446 #pragma warning(push)
447 #pragma warning(disable: 4611)
448 #endif
449     setjmp(registers);
450 #if COMPILER(MSVC)
451 #pragma warning(pop)
452 #endif
453
454     markStackObjectsConservativelyInternal();
455 }
456
457 void Heap::protect(JSValue *k)
458 {
459     ASSERT(k);
460     ASSERT(JSLock::lockCount() > 0);
461     ASSERT(JSLock::currentThreadIsHoldingLock());
462
463     if (JSImmediate::isImmediate(k))
464       return;
465
466     protectedValues.add(k->asCell());
467 }
468
469 void Heap::unprotect(JSValue *k)
470 {
471     ASSERT(k);
472     ASSERT(JSLock::lockCount() > 0);
473     ASSERT(JSLock::currentThreadIsHoldingLock());
474
475     if (JSImmediate::isImmediate(k))
476       return;
477
478     protectedValues.remove(k->asCell());
479 }
480
481 Heap* Heap::heap(const JSValue* v)
482 {
483     if (JSImmediate::isImmediate(v))
484         return 0;
485     // FIXME: should assert that the result equals threadHeap(), but currently, this fails as database code uses gcUnprotect from a different thread.
486     // That's a race condition and should be fixed.
487     return Heap::cellBlock(v->asCell())->heap;
488 }
489
490 void Heap::markProtectedObjects()
491 {
492   HashCountedSet<JSCell*>::iterator end = protectedValues.end();
493   for (HashCountedSet<JSCell*>::iterator it = protectedValues.begin(); it != end; ++it) {
494     JSCell *val = it->first;
495     if (!val->marked())
496       val->mark();
497   }
498 }
499
500 template <Heap::HeapType heapType> size_t Heap::sweep()
501 {
502     typedef typename HeapConstants<heapType>::Block Block;
503     typedef typename HeapConstants<heapType>::Cell Cell;
504
505     // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
506     CollectorHeap& heap = heapType == Heap::PrimaryHeap ? primaryHeap : numberHeap;
507     
508     size_t emptyBlocks = 0;
509     size_t numLiveObjects = heap.numLiveObjects;
510     
511     for (size_t block = 0; block < heap.usedBlocks; block++) {
512         Block* curBlock = (Block*)heap.blocks[block];
513         
514         size_t usedCells = curBlock->usedCells;
515         Cell* freeList = curBlock->freeList;
516         
517         if (usedCells == HeapConstants<heapType>::cellsPerBlock) {
518             // special case with a block where all cells are used -- testing indicates this happens often
519             for (size_t i = 0; i < HeapConstants<heapType>::cellsPerBlock; i++) {
520                 if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
521                     Cell* cell = curBlock->cells + i;
522                     
523                     if (heapType != Heap::NumberHeap) {
524                         JSCell* imp = reinterpret_cast<JSCell*>(cell);
525                         // special case for allocated but uninitialized object
526                         // (We don't need this check earlier because nothing prior this point 
527                         // assumes the object has a valid vptr.)
528                         if (cell->u.freeCell.zeroIfFree == 0)
529                             continue;
530                         
531                         imp->~JSCell();
532                     }
533                     
534                     --usedCells;
535                     --numLiveObjects;
536                     
537                     // put cell on the free list
538                     cell->u.freeCell.zeroIfFree = 0;
539                     cell->u.freeCell.next = freeList - (cell + 1);
540                     freeList = cell;
541                 }
542             }
543         } else {
544             size_t minimumCellsToProcess = usedCells;
545             for (size_t i = 0; (i < minimumCellsToProcess) & (i < HeapConstants<heapType>::cellsPerBlock); i++) {
546                 Cell *cell = curBlock->cells + i;
547                 if (cell->u.freeCell.zeroIfFree == 0) {
548                     ++minimumCellsToProcess;
549                 } else {
550                     if (!curBlock->marked.get(i >> HeapConstants<heapType>::bitmapShift)) {
551                         if (heapType != Heap::NumberHeap) {
552                             JSCell *imp = reinterpret_cast<JSCell*>(cell);
553                             imp->~JSCell();
554                         }
555                         --usedCells;
556                         --numLiveObjects;
557                         
558                         // put cell on the free list
559                         cell->u.freeCell.zeroIfFree = 0;
560                         cell->u.freeCell.next = freeList - (cell + 1); 
561                         freeList = cell;
562                     }
563                 }
564             }
565         }
566         
567         curBlock->usedCells = static_cast<uint32_t>(usedCells);
568         curBlock->freeList = freeList;
569         curBlock->marked.clearAll();
570         
571         if (usedCells == 0) {
572             emptyBlocks++;
573             if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
574 #if !DEBUG_COLLECTOR
575                 freeBlock((CollectorBlock*)curBlock);
576 #endif
577                 // swap with the last block so we compact as we go
578                 heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
579                 heap.usedBlocks--;
580                 block--; // Don't move forward a step in this case
581                 
582                 if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
583                     heap.numBlocks = heap.numBlocks / GROWTH_FACTOR; 
584                     heap.blocks = (CollectorBlock**)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
585                 }
586             }
587         }
588     }
589     
590     if (heap.numLiveObjects != numLiveObjects)
591         heap.firstBlockWithPossibleSpace = 0;
592         
593     heap.numLiveObjects = numLiveObjects;
594     heap.numLiveObjectsAtLastCollect = numLiveObjects;
595     heap.extraCost = 0;
596     return numLiveObjects;
597 }
598     
599 bool Heap::collect()
600 {
601   ASSERT(JSLock::lockCount() > 0);
602   ASSERT(JSLock::currentThreadIsHoldingLock());
603   ASSERT(this == threadHeap());
604
605   ASSERT((primaryHeap.operationInProgress == NoOperation) | (numberHeap.operationInProgress == NoOperation));
606   if ((primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation))
607     abort();
608     
609   primaryHeap.operationInProgress = Collection;
610   numberHeap.operationInProgress = Collection;
611
612   // MARK: first mark all referenced objects recursively starting out from the set of root objects
613
614 #ifndef NDEBUG
615   // Forbid malloc during the mark phase. Marking a thread suspends it, so 
616   // a malloc inside mark() would risk a deadlock with a thread that had been 
617   // suspended while holding the malloc lock.
618   fastMallocForbid();
619 #endif
620
621   markStackObjectsConservatively();
622   markProtectedObjects();
623   if (m_markListSet.size())
624     List::markProtectedLists(m_markListSet);
625
626 #ifndef NDEBUG
627   fastMallocAllow();
628 #endif
629     
630   size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
631   size_t numLiveObjects = sweep<PrimaryHeap>();
632   numLiveObjects += sweep<NumberHeap>();
633   
634   primaryHeap.operationInProgress = NoOperation;
635   numberHeap.operationInProgress = NoOperation;
636   
637   return numLiveObjects < originalLiveObjects;
638 }
639
640 size_t Heap::size() 
641 {
642   return primaryHeap.numLiveObjects + numberHeap.numLiveObjects; 
643 }
644
645 size_t Heap::globalObjectCount()
646 {
647   size_t count = 0;
648   if (JSGlobalObject::head()) {
649     JSGlobalObject* o = JSGlobalObject::head();
650     do {
651       ++count;
652       o = o->next();
653     } while (o != JSGlobalObject::head());
654   }
655   return count;
656 }
657
658 size_t Heap::protectedGlobalObjectCount()
659 {
660   size_t count = 0;
661   if (JSGlobalObject::head()) {
662     JSGlobalObject* o = JSGlobalObject::head();
663     do {
664       if (protectedValues.contains(o))
665         ++count;
666       o = o->next();
667     } while (o != JSGlobalObject::head());
668   }
669   return count;
670 }
671
672 size_t Heap::protectedObjectCount()
673 {
674   return protectedValues.size();
675 }
676
677 static const char *typeName(JSCell *val)
678 {
679   const char *name = "???";
680   switch (val->type()) {
681     case UnspecifiedType:
682       break;
683     case UndefinedType:
684       name = "undefined";
685       break;
686     case NullType:
687       name = "null";
688       break;
689     case BooleanType:
690       name = "boolean";
691       break;
692     case StringType:
693       name = "string";
694       break;
695     case NumberType:
696       name = "number";
697       break;
698     case ObjectType: {
699       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
700       name = info ? info->className : "Object";
701       break;
702     }
703     case GetterSetterType:
704       name = "gettersetter";
705       break;
706   }
707   return name;
708 }
709
710 HashCountedSet<const char*>* Heap::protectedObjectTypeCounts()
711 {
712     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
713
714     HashCountedSet<JSCell*>::iterator end = protectedValues.end();
715     for (HashCountedSet<JSCell*>::iterator it = protectedValues.begin(); it != end; ++it)
716         counts->add(typeName(it->first));
717
718     return counts;
719 }
720
721 bool Heap::isBusy()
722 {
723     return (primaryHeap.operationInProgress != NoOperation) | (numberHeap.operationInProgress != NoOperation);
724 }
725
726 void Heap::reportOutOfMemoryToAllExecStates()
727 {
728     if (!JSGlobalObject::head())
729         return;
730
731     JSGlobalObject* globalObject = JSGlobalObject::head();
732     do {
733         ExecStateStack::const_iterator end = globalObject->activeExecStates().end();
734         for (ExecStateStack::const_iterator it = globalObject->activeExecStates().begin(); it != end; ++it)
735             (*it)->setException(Error::create(*it, GeneralError, "Out of memory"));
736         globalObject = globalObject->next();
737     } while (globalObject != JSGlobalObject::head());
738 }
739
740 } // namespace KJS