Refactor Heap allocation logic into separate AllocationSpace class
[WebKit-https.git] / Source / JavaScriptCore / heap / Heap.cpp
1 /*
2  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2011 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 "Heap.h"
23
24 #include "CodeBlock.h"
25 #include "ConservativeRoots.h"
26 #include "GCActivityCallback.h"
27 #include "HeapRootVisitor.h"
28 #include "Interpreter.h"
29 #include "JSGlobalData.h"
30 #include "JSGlobalObject.h"
31 #include "JSLock.h"
32 #include "JSONObject.h"
33 #include "Tracing.h"
34 #include <algorithm>
35
36
37 using namespace std;
38 using namespace JSC;
39
40 namespace JSC {
41
42 namespace { 
43
44 static const size_t largeHeapSize = 16 * 1024 * 1024;
45 static const size_t smallHeapSize = 512 * 1024;
46
47 static size_t heapSizeForHint(HeapSize heapSize)
48 {
49 #if ENABLE(LARGE_HEAP)
50     if (heapSize == LargeHeap)
51         return largeHeapSize;
52     ASSERT(heapSize == SmallHeap);
53     return smallHeapSize;
54 #else
55     ASSERT_UNUSED(heapSize, heapSize == LargeHeap || heapSize == SmallHeap);
56     return smallHeapSize;
57 #endif
58 }
59
60 static inline bool isValidSharedInstanceThreadState()
61 {
62     if (!JSLock::lockCount())
63         return false;
64
65     if (!JSLock::currentThreadIsHoldingLock())
66         return false;
67
68     return true;
69 }
70
71 static inline bool isValidThreadState(JSGlobalData* globalData)
72 {
73     if (globalData->identifierTable != wtfThreadData().currentIdentifierTable())
74         return false;
75
76     if (globalData->isSharedInstance() && !isValidSharedInstanceThreadState())
77         return false;
78
79     return true;
80 }
81
82 class CountFunctor {
83 public:
84     typedef size_t ReturnType;
85
86     CountFunctor();
87     void count(size_t);
88     ReturnType returnValue();
89
90 private:
91     ReturnType m_count;
92 };
93
94 inline CountFunctor::CountFunctor()
95     : m_count(0)
96 {
97 }
98
99 inline void CountFunctor::count(size_t count)
100 {
101     m_count += count;
102 }
103
104 inline CountFunctor::ReturnType CountFunctor::returnValue()
105 {
106     return m_count;
107 }
108
109 struct ClearMarks : MarkedBlock::VoidFunctor {
110     void operator()(MarkedBlock*);
111 };
112
113 inline void ClearMarks::operator()(MarkedBlock* block)
114 {
115     block->clearMarks();
116     block->notifyMayHaveFreshFreeCells();
117 }
118
119 struct Sweep : MarkedBlock::VoidFunctor {
120     void operator()(MarkedBlock*);
121 };
122
123 inline void Sweep::operator()(MarkedBlock* block)
124 {
125     block->sweep();
126 }
127
128 struct MarkCount : CountFunctor {
129     void operator()(MarkedBlock*);
130 };
131
132 inline void MarkCount::operator()(MarkedBlock* block)
133 {
134     count(block->markCount());
135 }
136
137 struct Size : CountFunctor {
138     void operator()(MarkedBlock*);
139 };
140
141 inline void Size::operator()(MarkedBlock* block)
142 {
143     count(block->markCount() * block->cellSize());
144 }
145
146 struct Capacity : CountFunctor {
147     void operator()(MarkedBlock*);
148 };
149
150 inline void Capacity::operator()(MarkedBlock* block)
151 {
152     count(block->capacity());
153 }
154
155 struct Count : public CountFunctor {
156     void operator()(JSCell*);
157 };
158
159 inline void Count::operator()(JSCell*)
160 {
161     count(1);
162 }
163
164 struct CountIfGlobalObject : CountFunctor {
165     void operator()(JSCell*);
166 };
167
168 inline void CountIfGlobalObject::operator()(JSCell* cell)
169 {
170     if (!cell->isObject())
171         return;
172     if (!asObject(cell)->isGlobalObject())
173         return;
174     count(1);
175 }
176
177 class RecordType {
178 public:
179     typedef PassOwnPtr<TypeCountSet> ReturnType;
180
181     RecordType();
182     void operator()(JSCell*);
183     ReturnType returnValue();
184
185 private:
186     const char* typeName(JSCell*);
187     OwnPtr<TypeCountSet> m_typeCountSet;
188 };
189
190 inline RecordType::RecordType()
191     : m_typeCountSet(adoptPtr(new TypeCountSet))
192 {
193 }
194
195 inline const char* RecordType::typeName(JSCell* cell)
196 {
197     const ClassInfo* info = cell->classInfo();
198     if (!info || !info->className)
199         return "[unknown]";
200     return info->className;
201 }
202
203 inline void RecordType::operator()(JSCell* cell)
204 {
205     m_typeCountSet->add(typeName(cell));
206 }
207
208 inline PassOwnPtr<TypeCountSet> RecordType::returnValue()
209 {
210     return m_typeCountSet.release();
211 }
212
213 } // anonymous namespace
214
215 Heap::Heap(JSGlobalData* globalData, HeapSize heapSize)
216     : m_heapSize(heapSize)
217     , m_minBytesPerCycle(heapSizeForHint(heapSize))
218     , m_operationInProgress(NoOperation)
219     , m_objectSpace(this)
220     , m_extraCost(0)
221     , m_markListSet(0)
222     , m_activityCallback(DefaultGCActivityCallback::create(this))
223     , m_machineThreads(this)
224     , m_slotVisitor(globalData->jsArrayVPtr)
225     , m_handleHeap(globalData)
226     , m_isSafeToCollect(false)
227     , m_globalData(globalData)
228 {
229     m_objectSpace.setHighWaterMark(m_minBytesPerCycle);
230     (*m_activityCallback)();
231     m_numberOfFreeBlocks = 0;
232     m_blockFreeingThread = createThread(blockFreeingThreadStartFunc, this, "JavaScriptCore::BlockFree");
233     ASSERT(m_blockFreeingThread);
234 }
235
236 Heap::~Heap()
237 {
238     // destroy our thread
239     {
240         MutexLocker locker(m_freeBlockLock);
241         m_blockFreeingThreadShouldQuit = true;
242         m_freeBlockCondition.broadcast();
243     }
244     waitForThreadCompletion(m_blockFreeingThread, 0);
245     
246     // The destroy function must already have been called, so assert this.
247     ASSERT(!m_globalData);
248 }
249
250 void Heap::destroy()
251 {
252     JSLock lock(SilenceAssertionsOnly);
253
254     if (!m_globalData)
255         return;
256
257     ASSERT(!m_globalData->dynamicGlobalObject);
258     ASSERT(m_operationInProgress == NoOperation);
259     
260     // The global object is not GC protected at this point, so sweeping may delete it
261     // (and thus the global data) before other objects that may use the global data.
262     RefPtr<JSGlobalData> protect(m_globalData);
263
264 #if ENABLE(JIT)
265     m_globalData->jitStubs->clearHostFunctionStubs();
266 #endif
267
268     delete m_markListSet;
269     m_markListSet = 0;
270
271     clearMarks();
272     m_handleHeap.finalizeWeakHandles();
273     m_globalData->smallStrings.finalizeSmallStrings();
274
275     shrink();
276     ASSERT(!size());
277     
278 #if ENABLE(SIMPLE_HEAP_PROFILING)
279     m_slotVisitor.m_visitedTypeCounts.dump(stderr, "Visited Type Counts");
280     m_destroyedTypeCounts.dump(stderr, "Destroyed Type Counts");
281 #endif
282     
283     releaseFreeBlocks();
284
285     m_globalData = 0;
286 }
287
288 void Heap::waitForRelativeTimeWhileHoldingLock(double relative)
289 {
290     if (m_blockFreeingThreadShouldQuit)
291         return;
292     m_freeBlockCondition.timedWait(m_freeBlockLock, currentTime() + relative);
293 }
294
295 void Heap::waitForRelativeTime(double relative)
296 {
297     // If this returns early, that's fine, so long as it doesn't do it too
298     // frequently. It would only be a bug if this function failed to return
299     // when it was asked to do so.
300     
301     MutexLocker locker(m_freeBlockLock);
302     waitForRelativeTimeWhileHoldingLock(relative);
303 }
304
305 void* Heap::blockFreeingThreadStartFunc(void* heap)
306 {
307     static_cast<Heap*>(heap)->blockFreeingThreadMain();
308     return 0;
309 }
310
311 void Heap::blockFreeingThreadMain()
312 {
313     while (!m_blockFreeingThreadShouldQuit) {
314         // Generally wait for one second before scavenging free blocks. This
315         // may return early, particularly when we're being asked to quit.
316         waitForRelativeTime(1.0);
317         if (m_blockFreeingThreadShouldQuit)
318             break;
319         
320         // Now process the list of free blocks. Keep freeing until half of the
321         // blocks that are currently on the list are gone. Assume that a size_t
322         // field can be accessed atomically.
323         size_t currentNumberOfFreeBlocks = m_numberOfFreeBlocks;
324         if (!currentNumberOfFreeBlocks)
325             continue;
326         
327         size_t desiredNumberOfFreeBlocks = currentNumberOfFreeBlocks / 2;
328         
329         while (!m_blockFreeingThreadShouldQuit) {
330             MarkedBlock* block;
331             {
332                 MutexLocker locker(m_freeBlockLock);
333                 if (m_numberOfFreeBlocks <= desiredNumberOfFreeBlocks)
334                     block = 0;
335                 else {
336                     block = m_freeBlocks.removeHead();
337                     ASSERT(block);
338                     m_numberOfFreeBlocks--;
339                 }
340             }
341             
342             if (!block)
343                 break;
344             
345             MarkedBlock::destroy(block);
346         }
347     }
348 }
349
350 void Heap::reportExtraMemoryCostSlowCase(size_t cost)
351 {
352     // Our frequency of garbage collection tries to balance memory use against speed
353     // by collecting based on the number of newly created values. However, for values
354     // that hold on to a great deal of memory that's not in the form of other JS values,
355     // that is not good enough - in some cases a lot of those objects can pile up and
356     // use crazy amounts of memory without a GC happening. So we track these extra
357     // memory costs. Only unusually large objects are noted, and we only keep track
358     // of this extra cost until the next GC. In garbage collected languages, most values
359     // are either very short lived temporaries, or have extremely long lifetimes. So
360     // if a large value survives one garbage collection, there is not much point to
361     // collecting more frequently as long as it stays alive.
362
363     if (m_extraCost > maxExtraCost && m_extraCost > m_objectSpace.highWaterMark() / 2)
364         collectAllGarbage();
365     m_extraCost += cost;
366 }
367
368 void Heap::protect(JSValue k)
369 {
370     ASSERT(k);
371     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance());
372
373     if (!k.isCell())
374         return;
375
376     m_protectedValues.add(k.asCell());
377 }
378
379 bool Heap::unprotect(JSValue k)
380 {
381     ASSERT(k);
382     ASSERT(JSLock::currentThreadIsHoldingLock() || !m_globalData->isSharedInstance());
383
384     if (!k.isCell())
385         return false;
386
387     return m_protectedValues.remove(k.asCell());
388 }
389
390 void Heap::markProtectedObjects(HeapRootVisitor& heapRootVisitor)
391 {
392     ProtectCountSet::iterator end = m_protectedValues.end();
393     for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it)
394         heapRootVisitor.visit(&it->first);
395 }
396
397 void Heap::pushTempSortVector(Vector<ValueStringPair>* tempVector)
398 {
399     m_tempSortingVectors.append(tempVector);
400 }
401
402 void Heap::popTempSortVector(Vector<ValueStringPair>* tempVector)
403 {
404     ASSERT_UNUSED(tempVector, tempVector == m_tempSortingVectors.last());
405     m_tempSortingVectors.removeLast();
406 }
407     
408 void Heap::markTempSortVectors(HeapRootVisitor& heapRootVisitor)
409 {
410     typedef Vector<Vector<ValueStringPair>* > VectorOfValueStringVectors;
411
412     VectorOfValueStringVectors::iterator end = m_tempSortingVectors.end();
413     for (VectorOfValueStringVectors::iterator it = m_tempSortingVectors.begin(); it != end; ++it) {
414         Vector<ValueStringPair>* tempSortingVector = *it;
415
416         Vector<ValueStringPair>::iterator vectorEnd = tempSortingVector->end();
417         for (Vector<ValueStringPair>::iterator vectorIt = tempSortingVector->begin(); vectorIt != vectorEnd; ++vectorIt) {
418             if (vectorIt->first)
419                 heapRootVisitor.visit(&vectorIt->first);
420         }
421     }
422 }
423
424 void Heap::harvestWeakReferences()
425 {
426     m_slotVisitor.harvestWeakReferences();
427 }
428
429 inline RegisterFile& Heap::registerFile()
430 {
431     return m_globalData->interpreter->registerFile();
432 }
433
434 void Heap::getConservativeRegisterRoots(HashSet<JSCell*>& roots)
435 {
436     ASSERT(isValidThreadState(m_globalData));
437     if (m_operationInProgress != NoOperation)
438         CRASH();
439     m_operationInProgress = Collection;
440     ConservativeRoots registerFileRoots(&m_objectSpace.blocks());
441     registerFile().gatherConservativeRoots(registerFileRoots);
442     size_t registerFileRootCount = registerFileRoots.size();
443     JSCell** registerRoots = registerFileRoots.roots();
444     for (size_t i = 0; i < registerFileRootCount; i++) {
445         setMarked(registerRoots[i]);
446         roots.add(registerRoots[i]);
447     }
448     m_operationInProgress = NoOperation;
449 }
450
451 void Heap::markRoots()
452 {
453     ASSERT(isValidThreadState(m_globalData));
454     if (m_operationInProgress != NoOperation)
455         CRASH();
456     m_operationInProgress = Collection;
457
458     void* dummy;
459
460     // We gather conservative roots before clearing mark bits because conservative
461     // gathering uses the mark bits to determine whether a reference is valid.
462     ConservativeRoots machineThreadRoots(&m_objectSpace.blocks());
463     m_machineThreads.gatherConservativeRoots(machineThreadRoots, &dummy);
464
465     ConservativeRoots registerFileRoots(&m_objectSpace.blocks());
466     registerFile().gatherConservativeRoots(registerFileRoots);
467
468     clearMarks();
469
470     SlotVisitor& visitor = m_slotVisitor;
471     HeapRootVisitor heapRootVisitor(visitor);
472
473     visitor.append(machineThreadRoots);
474     visitor.drain();
475
476     visitor.append(registerFileRoots);
477     visitor.drain();
478
479     markProtectedObjects(heapRootVisitor);
480     visitor.drain();
481     
482     markTempSortVectors(heapRootVisitor);
483     visitor.drain();
484
485     if (m_markListSet && m_markListSet->size())
486         MarkedArgumentBuffer::markLists(heapRootVisitor, *m_markListSet);
487     if (m_globalData->exception)
488         heapRootVisitor.visit(&m_globalData->exception);
489     visitor.drain();
490
491     m_handleHeap.visitStrongHandles(heapRootVisitor);
492     visitor.drain();
493
494     m_handleStack.visit(heapRootVisitor);
495     visitor.drain();
496
497     // Weak handles must be marked last, because their owners use the set of
498     // opaque roots to determine reachability.
499     int lastOpaqueRootCount;
500     do {
501         lastOpaqueRootCount = visitor.opaqueRootCount();
502         m_handleHeap.visitWeakHandles(heapRootVisitor);
503         visitor.drain();
504     // If the set of opaque roots has grown, more weak handles may have become reachable.
505     } while (lastOpaqueRootCount != visitor.opaqueRootCount());
506
507     // Need to call this here because weak handle processing could add weak
508     // reference harvesters.
509     harvestWeakReferences();
510
511     visitor.reset();
512
513     m_operationInProgress = NoOperation;
514 }
515
516 void Heap::clearMarks()
517 {
518     m_objectSpace.forEachBlock<ClearMarks>();
519 }
520
521 void Heap::sweep()
522 {
523     m_objectSpace.forEachBlock<Sweep>();
524 }
525
526 size_t Heap::objectCount()
527 {
528     return m_objectSpace.forEachBlock<MarkCount>();
529 }
530
531 size_t Heap::size()
532 {
533     return m_objectSpace.forEachBlock<Size>();
534 }
535
536 size_t Heap::capacity()
537 {
538     return m_objectSpace.forEachBlock<Capacity>();
539 }
540
541 size_t Heap::protectedGlobalObjectCount()
542 {
543     return forEachProtectedCell<CountIfGlobalObject>();
544 }
545
546 size_t Heap::globalObjectCount()
547 {
548     return m_objectSpace.forEachCell<CountIfGlobalObject>();
549 }
550
551 size_t Heap::protectedObjectCount()
552 {
553     return forEachProtectedCell<Count>();
554 }
555
556 PassOwnPtr<TypeCountSet> Heap::protectedObjectTypeCounts()
557 {
558     return forEachProtectedCell<RecordType>();
559 }
560
561 PassOwnPtr<TypeCountSet> Heap::objectTypeCounts()
562 {
563     return m_objectSpace.forEachCell<RecordType>();
564 }
565
566 void Heap::collectAllGarbage()
567 {
568     if (!m_isSafeToCollect)
569         return;
570     if (!m_globalData->dynamicGlobalObject)
571         m_globalData->recompileAllJSFunctions();
572
573     collect(DoSweep);
574 }
575
576 void Heap::collect(SweepToggle sweepToggle)
577 {
578     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
579     ASSERT(m_isSafeToCollect);
580     JAVASCRIPTCORE_GC_BEGIN();
581     
582     canonicalizeBlocks();
583     
584     markRoots();
585     m_handleHeap.finalizeWeakHandles();
586     m_globalData->smallStrings.finalizeSmallStrings();
587
588     JAVASCRIPTCORE_GC_MARKED();
589     
590     resetAllocator();
591
592     if (sweepToggle == DoSweep) {
593         sweep();
594         shrink();
595     }
596
597     // To avoid pathological GC churn in large heaps, we set the allocation high
598     // water mark to be proportional to the current size of the heap. The exact
599     // proportion is a bit arbitrary. A 2X multiplier gives a 1:1 (heap size :
600     // new bytes allocated) proportion, and seems to work well in benchmarks.
601     size_t proportionalBytes = 2 * size();
602     m_objectSpace.setHighWaterMark(max(proportionalBytes, m_minBytesPerCycle));
603     JAVASCRIPTCORE_GC_END();
604
605     (*m_activityCallback)();
606 }
607
608 void Heap::canonicalizeBlocks()
609 {
610     m_objectSpace.canonicalizeBlocks();
611 }
612
613 void Heap::resetAllocator()
614 {
615     m_extraCost = 0;
616     m_objectSpace.resetAllocator();
617 }
618
619 void Heap::setActivityCallback(PassOwnPtr<GCActivityCallback> activityCallback)
620 {
621     m_activityCallback = activityCallback;
622 }
623
624 GCActivityCallback* Heap::activityCallback()
625 {
626     return m_activityCallback.get();
627 }
628
629 bool Heap::isValidAllocation(size_t bytes)
630 {
631     if (!isValidThreadState(m_globalData))
632         return false;
633
634     if (bytes > MarkedSpace::maxCellSize)
635         return false;
636
637     if (m_operationInProgress != NoOperation)
638         return false;
639     
640     return true;
641 }
642
643 void Heap::freeBlocks(MarkedBlock* head)
644 {
645     m_objectSpace.freeBlocks(head);
646 }
647
648 void Heap::shrink()
649 {
650     m_objectSpace.shrink();
651 }
652
653 void Heap::releaseFreeBlocks()
654 {
655     while (true) {
656         MarkedBlock* block;
657         {
658             MutexLocker locker(m_freeBlockLock);
659             if (!m_numberOfFreeBlocks)
660                 block = 0;
661             else {
662                 block = m_freeBlocks.removeHead();
663                 ASSERT(block);
664                 m_numberOfFreeBlocks--;
665             }
666         }
667         
668         if (!block)
669             break;
670         
671         MarkedBlock::destroy(block);
672     }
673 }
674
675 #if ENABLE(GGC)
676 void Heap::writeBarrierSlowCase(const JSCell* owner, JSCell* cell)
677 {
678 }
679
680 #else
681
682 void Heap::writeBarrierSlowCase(const JSCell*, JSCell*)
683 {
684 }
685 #endif
686
687 } // namespace JSC