Copying collection shouldn't require O(live bytes) memory overhead
[WebKit-https.git] / Source / JavaScriptCore / heap / Heap.h
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
4  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
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 #ifndef Heap_h
23 #define Heap_h
24
25 #include "BlockAllocator.h"
26 #include "CopyVisitor.h"
27 #include "DFGCodeBlocks.h"
28 #include "GCThreadSharedData.h"
29 #include "HandleSet.h"
30 #include "HandleStack.h"
31 #include "JITStubRoutineSet.h"
32 #include "MarkedAllocator.h"
33 #include "MarkedBlock.h"
34 #include "MarkedBlockSet.h"
35 #include "MarkedSpace.h"
36 #include "Options.h"
37 #include "SlotVisitor.h"
38 #include "WeakHandleOwner.h"
39 #include "WriteBarrierSupport.h"
40 #include <wtf/HashCountedSet.h>
41 #include <wtf/HashSet.h>
42
43 #define COLLECT_ON_EVERY_ALLOCATION 0
44
45 namespace JSC {
46
47     class CopiedSpace;
48     class CodeBlock;
49     class ExecutableBase;
50     class GCActivityCallback;
51     class GCAwareJITStubRoutine;
52     class GlobalCodeBlock;
53     class Heap;
54     class HeapRootVisitor;
55     class IncrementalSweeper;
56     class JITStubRoutine;
57     class JSCell;
58     class JSGlobalData;
59     class JSStack;
60     class JSValue;
61     class LiveObjectIterator;
62     class LLIntOffsetsExtractor;
63     class MarkedArgumentBuffer;
64     class WeakGCHandlePool;
65     class SlotVisitor;
66
67     typedef std::pair<JSValue, WTF::String> ValueStringPair;
68     typedef HashCountedSet<JSCell*> ProtectCountSet;
69     typedef HashCountedSet<const char*> TypeCountSet;
70
71     enum OperationInProgress { NoOperation, Allocation, Collection };
72
73     enum HeapType { SmallHeap, LargeHeap };
74
75     class Heap {
76         WTF_MAKE_NONCOPYABLE(Heap);
77     public:
78         friend class JIT;
79         friend class GCThreadSharedData;
80         static Heap* heap(const JSValue); // 0 for immediate values
81         static Heap* heap(const JSCell*);
82
83         // This constant determines how many blocks we iterate between checks of our 
84         // deadline when calling Heap::isPagedOut. Decreasing it will cause us to detect 
85         // overstepping our deadline more quickly, while increasing it will cause 
86         // our scan to run faster. 
87         static const unsigned s_timeCheckResolution = 16;
88
89         static bool isMarked(const void*);
90         static bool testAndSetMarked(const void*);
91         static void setMarked(const void*);
92
93         static bool isWriteBarrierEnabled();
94         static void writeBarrier(const JSCell*, JSValue);
95         static void writeBarrier(const JSCell*, JSCell*);
96         static uint8_t* addressOfCardFor(JSCell*);
97
98         Heap(JSGlobalData*, HeapType);
99         ~Heap();
100         JS_EXPORT_PRIVATE void lastChanceToFinalize();
101
102         JSGlobalData* globalData() const { return m_globalData; }
103         MarkedSpace& objectSpace() { return m_objectSpace; }
104         MachineThreads& machineThreads() { return m_machineThreads; }
105
106         JS_EXPORT_PRIVATE GCActivityCallback* activityCallback();
107         JS_EXPORT_PRIVATE void setActivityCallback(GCActivityCallback*);
108         JS_EXPORT_PRIVATE void setGarbageCollectionTimerEnabled(bool);
109
110         JS_EXPORT_PRIVATE IncrementalSweeper* sweeper();
111
112         // true if an allocation or collection is in progress
113         inline bool isBusy();
114         
115         MarkedAllocator& firstAllocatorWithoutDestructors() { return m_objectSpace.firstAllocator(); }
116         MarkedAllocator& allocatorForObjectWithoutDestructor(size_t bytes) { return m_objectSpace.allocatorFor(bytes); }
117         MarkedAllocator& allocatorForObjectWithNormalDestructor(size_t bytes) { return m_objectSpace.normalDestructorAllocatorFor(bytes); }
118         MarkedAllocator& allocatorForObjectWithImmortalStructureDestructor(size_t bytes) { return m_objectSpace.immortalStructureDestructorAllocatorFor(bytes); }
119         CopiedAllocator& storageAllocator() { return m_storageSpace.allocator(); }
120         CheckedBoolean tryAllocateStorage(size_t, void**);
121         CheckedBoolean tryReallocateStorage(void**, size_t, size_t);
122
123         typedef void (*Finalizer)(JSCell*);
124         JS_EXPORT_PRIVATE void addFinalizer(JSCell*, Finalizer);
125         void addCompiledCode(ExecutableBase*);
126
127         void notifyIsSafeToCollect() { m_isSafeToCollect = true; }
128         bool isSafeToCollect() const { return m_isSafeToCollect; }
129
130         JS_EXPORT_PRIVATE void collectAllGarbage();
131         enum SweepToggle { DoNotSweep, DoSweep };
132         bool shouldCollect();
133         void collect(SweepToggle);
134
135         void reportExtraMemoryCost(size_t cost);
136         JS_EXPORT_PRIVATE void reportAbandonedObjectGraph();
137
138         JS_EXPORT_PRIVATE void protect(JSValue);
139         JS_EXPORT_PRIVATE bool unprotect(JSValue); // True when the protect count drops to 0.
140         
141         void jettisonDFGCodeBlock(PassOwnPtr<CodeBlock>);
142
143         JS_EXPORT_PRIVATE size_t size();
144         JS_EXPORT_PRIVATE size_t capacity();
145         JS_EXPORT_PRIVATE size_t objectCount();
146         JS_EXPORT_PRIVATE size_t globalObjectCount();
147         JS_EXPORT_PRIVATE size_t protectedObjectCount();
148         JS_EXPORT_PRIVATE size_t protectedGlobalObjectCount();
149         JS_EXPORT_PRIVATE PassOwnPtr<TypeCountSet> protectedObjectTypeCounts();
150         JS_EXPORT_PRIVATE PassOwnPtr<TypeCountSet> objectTypeCounts();
151         void showStatistics();
152
153         void pushTempSortVector(Vector<ValueStringPair>*);
154         void popTempSortVector(Vector<ValueStringPair>*);
155     
156         HashSet<MarkedArgumentBuffer*>& markListSet() { if (!m_markListSet) m_markListSet = adoptPtr(new HashSet<MarkedArgumentBuffer*>); return *m_markListSet; }
157         
158         template<typename Functor> typename Functor::ReturnType forEachProtectedCell(Functor&);
159         template<typename Functor> typename Functor::ReturnType forEachProtectedCell();
160
161         HandleSet* handleSet() { return &m_handleSet; }
162         HandleStack* handleStack() { return &m_handleStack; }
163
164         void getConservativeRegisterRoots(HashSet<JSCell*>& roots);
165
166         double lastGCLength() { return m_lastGCLength; }
167         void increaseLastGCLength(double amount) { m_lastGCLength += amount; }
168
169         JS_EXPORT_PRIVATE void deleteAllCompiledCode();
170
171         void didAllocate(size_t);
172         void didAbandon(size_t);
173
174         bool isPagedOut(double deadline);
175         void didStartVMShutdown();
176
177     private:
178         friend class CodeBlock;
179         friend class GCAwareJITStubRoutine;
180         friend class JITStubRoutine;
181         friend class LLIntOffsetsExtractor;
182         friend class MarkedSpace;
183         friend class MarkedAllocator;
184         friend class MarkedBlock;
185         friend class CopiedSpace;
186         friend class CopyVisitor;
187         friend class SlotVisitor;
188         friend class IncrementalSweeper;
189         friend class HeapStatistics;
190         template<typename T> friend void* allocateCell(Heap&);
191         template<typename T> friend void* allocateCell(Heap&, size_t);
192
193         void* allocateWithImmortalStructureDestructor(size_t); // For use with special objects whose Structures never die.
194         void* allocateWithNormalDestructor(size_t); // For use with objects that inherit directly or indirectly from JSDestructibleObject.
195         void* allocateWithoutDestructor(size_t); // For use with objects without destructors.
196
197         static const size_t minExtraCost = 256;
198         static const size_t maxExtraCost = 1024 * 1024;
199         
200         class FinalizerOwner : public WeakHandleOwner {
201             virtual void finalize(Handle<Unknown>, void* context);
202         };
203
204         JS_EXPORT_PRIVATE bool isValidAllocation(size_t);
205         JS_EXPORT_PRIVATE void reportExtraMemoryCostSlowCase(size_t);
206
207         void markRoots(bool fullGC);
208         void markProtectedObjects(HeapRootVisitor&);
209         void markTempSortVectors(HeapRootVisitor&);
210         void copyBackingStores();
211         void harvestWeakReferences();
212         void finalizeUnconditionalFinalizers();
213         void deleteUnmarkedCompiledCode();
214         void zombifyDeadObjects();
215         void markDeadObjects();
216
217         JSStack& stack();
218         BlockAllocator& blockAllocator();
219
220         const HeapType m_heapType;
221         const size_t m_ramSize;
222         const size_t m_minBytesPerCycle;
223         size_t m_sizeAfterLastCollect;
224
225         size_t m_bytesAllocatedLimit;
226         size_t m_bytesAllocated;
227         size_t m_bytesAbandoned;
228         
229         OperationInProgress m_operationInProgress;
230         BlockAllocator m_blockAllocator;
231         MarkedSpace m_objectSpace;
232         CopiedSpace m_storageSpace;
233
234 #if ENABLE(SIMPLE_HEAP_PROFILING)
235         VTableSpectrum m_destroyedTypeCounts;
236 #endif
237
238         ProtectCountSet m_protectedValues;
239         Vector<Vector<ValueStringPair>* > m_tempSortingVectors;
240         OwnPtr<HashSet<MarkedArgumentBuffer*> > m_markListSet;
241
242         MachineThreads m_machineThreads;
243         
244         GCThreadSharedData m_sharedData;
245         SlotVisitor m_slotVisitor;
246         CopyVisitor m_copyVisitor;
247
248         HandleSet m_handleSet;
249         HandleStack m_handleStack;
250         DFGCodeBlocks m_dfgCodeBlocks;
251         JITStubRoutineSet m_jitStubRoutines;
252         FinalizerOwner m_finalizerOwner;
253         
254         bool m_isSafeToCollect;
255
256         JSGlobalData* m_globalData;
257         double m_lastGCLength;
258         double m_lastCodeDiscardTime;
259
260         DoublyLinkedList<ExecutableBase> m_compiledCode;
261         
262         GCActivityCallback* m_activityCallback;
263         IncrementalSweeper* m_sweeper;
264         Vector<MarkedBlock*> m_blockSnapshot;
265     };
266
267     struct MarkedBlockSnapshotFunctor : public MarkedBlock::VoidFunctor {
268         MarkedBlockSnapshotFunctor(Vector<MarkedBlock*>& blocks) 
269             : m_index(0) 
270             , m_blocks(blocks)
271         {
272         }
273     
274         void operator()(MarkedBlock* block) { m_blocks[m_index++] = block; }
275     
276         size_t m_index;
277         Vector<MarkedBlock*>& m_blocks;
278     };
279
280     inline bool Heap::shouldCollect()
281     {
282         if (Options::gcMaxHeapSize())
283             return m_bytesAllocated > Options::gcMaxHeapSize() && m_isSafeToCollect && m_operationInProgress == NoOperation;
284 #if ENABLE(GGC)
285         return m_objectSpace.nurseryWaterMark() >= m_minBytesPerCycle && m_isSafeToCollect && m_operationInProgress == NoOperation;
286 #else
287         return m_bytesAllocated > m_bytesAllocatedLimit && m_isSafeToCollect && m_operationInProgress == NoOperation;
288 #endif
289     }
290
291     bool Heap::isBusy()
292     {
293         return m_operationInProgress != NoOperation;
294     }
295
296     inline Heap* Heap::heap(const JSCell* cell)
297     {
298         return MarkedBlock::blockFor(cell)->heap();
299     }
300
301     inline Heap* Heap::heap(const JSValue v)
302     {
303         if (!v.isCell())
304             return 0;
305         return heap(v.asCell());
306     }
307
308     inline bool Heap::isMarked(const void* cell)
309     {
310         return MarkedBlock::blockFor(cell)->isMarked(cell);
311     }
312
313     inline bool Heap::testAndSetMarked(const void* cell)
314     {
315         return MarkedBlock::blockFor(cell)->testAndSetMarked(cell);
316     }
317
318     inline void Heap::setMarked(const void* cell)
319     {
320         MarkedBlock::blockFor(cell)->setMarked(cell);
321     }
322
323     inline bool Heap::isWriteBarrierEnabled()
324     {
325 #if ENABLE(GGC) || ENABLE(WRITE_BARRIER_PROFILING)
326         return true;
327 #else
328         return false;
329 #endif
330     }
331
332 #if ENABLE(GGC)
333     inline uint8_t* Heap::addressOfCardFor(JSCell* cell)
334     {
335         return MarkedBlock::blockFor(cell)->addressOfCardFor(cell);
336     }
337
338     inline void Heap::writeBarrier(const JSCell* owner, JSCell*)
339     {
340         WriteBarrierCounters::countWriteBarrier();
341         MarkedBlock* block = MarkedBlock::blockFor(owner);
342         if (block->isMarked(owner))
343             block->setDirtyObject(owner);
344     }
345
346     inline void Heap::writeBarrier(const JSCell* owner, JSValue value)
347     {
348         if (!value)
349             return;
350         if (!value.isCell())
351             return;
352         writeBarrier(owner, value.asCell());
353     }
354 #else
355
356     inline void Heap::writeBarrier(const JSCell*, JSCell*)
357     {
358         WriteBarrierCounters::countWriteBarrier();
359     }
360
361     inline void Heap::writeBarrier(const JSCell*, JSValue)
362     {
363         WriteBarrierCounters::countWriteBarrier();
364     }
365 #endif
366
367     inline void Heap::reportExtraMemoryCost(size_t cost)
368     {
369         if (cost > minExtraCost) 
370             reportExtraMemoryCostSlowCase(cost);
371     }
372
373     template<typename Functor> inline typename Functor::ReturnType Heap::forEachProtectedCell(Functor& functor)
374     {
375         ProtectCountSet::iterator end = m_protectedValues.end();
376         for (ProtectCountSet::iterator it = m_protectedValues.begin(); it != end; ++it)
377             functor(it->key);
378         m_handleSet.forEachStrongHandle(functor, m_protectedValues);
379
380         return functor.returnValue();
381     }
382
383     template<typename Functor> inline typename Functor::ReturnType Heap::forEachProtectedCell()
384     {
385         Functor functor;
386         return forEachProtectedCell(functor);
387     }
388
389     inline void* Heap::allocateWithNormalDestructor(size_t bytes)
390     {
391         ASSERT(isValidAllocation(bytes));
392         return m_objectSpace.allocateWithNormalDestructor(bytes);
393     }
394     
395     inline void* Heap::allocateWithImmortalStructureDestructor(size_t bytes)
396     {
397         ASSERT(isValidAllocation(bytes));
398         return m_objectSpace.allocateWithImmortalStructureDestructor(bytes);
399     }
400     
401     inline void* Heap::allocateWithoutDestructor(size_t bytes)
402     {
403         ASSERT(isValidAllocation(bytes));
404         return m_objectSpace.allocateWithoutDestructor(bytes);
405     }
406    
407     inline CheckedBoolean Heap::tryAllocateStorage(size_t bytes, void** outPtr)
408     {
409         return m_storageSpace.tryAllocate(bytes, outPtr);
410     }
411     
412     inline CheckedBoolean Heap::tryReallocateStorage(void** ptr, size_t oldSize, size_t newSize)
413     {
414         return m_storageSpace.tryReallocate(ptr, oldSize, newSize);
415     }
416
417     inline BlockAllocator& Heap::blockAllocator()
418     {
419         return m_blockAllocator;
420     }
421
422 } // namespace JSC
423
424 #endif // Heap_h