Make the HeapVerifier useful again.
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedAllocator.h
1 /*
2  * Copyright (C) 2012-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #pragma once
27
28 #include "AllocatorAttributes.h"
29 #include "FreeList.h"
30 #include "MarkedBlock.h"
31 #include <wtf/FastBitVector.h>
32 #include <wtf/SentinelLinkedList.h>
33 #include <wtf/Vector.h>
34
35 namespace JSC {
36
37 class GCDeferralContext;
38 class Heap;
39 class MarkedSpace;
40 class LLIntOffsetsExtractor;
41
42 #define FOR_EACH_MARKED_ALLOCATOR_BIT(macro) \
43     macro(live, Live) /* The set of block indices that have actual blocks. */\
44     macro(empty, Empty) /* The set of all blocks that have no live objects and nothing to destroy. */ \
45     macro(allocated, Allocated) /* The set of all blocks that are full of live objects. */\
46     macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
47     macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
48     macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
49     \
50     /* These are computed during marking. */\
51     macro(markingNotEmpty, MarkingNotEmpty) /* The set of all blocks that are not empty. */ \
52     macro(markingRetired, MarkingRetired) /* The set of all blocks that are retired. */
53
54 // FIXME: We defined canAllocateButNotEmpty and empty to be exclusive:
55 //
56 //     canAllocateButNotEmpty & empty == 0
57 //
58 // Instead of calling it canAllocate and making it inclusive:
59 //
60 //     canAllocate & empty == empty
61 //
62 // The latter is probably better. I'll leave it to a future bug to fix that, since breathing on
63 // this code leads to regressions for days, and it's not clear that making this change would
64 // improve perf since it would not change the collector's behavior, and either way the allocator
65 // has to look at both bitvectors.
66 // https://bugs.webkit.org/show_bug.cgi?id=162121
67
68 // Note that this collector supports overlapping allocator state with marking state, since in a
69 // concurrent collector you allow allocation while marking is running. So it's best to visualize a
70 // full mutable->eden collect->mutate->full collect cycle and see how the bits above get affected.
71 // The example below tries to be exhaustive about what happens to the bits, but omits a lot of
72 // things that happen to other state.
73 //
74 // Create allocator
75 // - all bits are empty
76 // Start allocating in some block
77 // - allocate the block and set the live bit.
78 // - the empty bit for the block flickers on and then gets immediately cleared by sweeping.
79 // - set the eden bit.
80 // Finish allocating in that block
81 // - set the allocated bit.
82 // Do that to a lot of blocks and then start an eden collection.
83 // - beginMarking() has nothing to do.
84 // - by default we have cleared markingNotEmpty/markingRetired bits.
85 // - marking builds up markingNotEmpty/markingRetired bits.
86 // We do endMarking()
87 // - clear all allocated bits.
88 // - for destructor blocks: fragmented = live & ~markingRetired
89 // - for non-destructor blocks:
90 //       empty = live & ~markingNotEmpty
91 //       fragmented = live & markingNotEmpty & ~markingRetired
92 // Snapshotting.
93 // - unswept |= eden
94 // Prepare for allocation.
95 // - clear eden
96 // Finish collection.
97 // Allocate in some block that had some free and some live objects.
98 // - clear the canAllocateButNotEmpty bit
99 // - clear the unswept bit
100 // - set the eden bit
101 // Finish allocating (set the allocated bit).
102 // Allocate in some block that was completely empty.
103 // - clear the empty bit
104 // - clear the unswept bit
105 // - set the eden bit.
106 // Finish allocating (set the allocated bit).
107 // Allocate in some block that was completely empty in another allocator.
108 // - clear the empty bit
109 // - clear all bits in that allocator
110 // - set the live bit in another allocator and the empty bit.
111 // - clear the empty, unswept bits.
112 // - set the eden bit.
113 // Finish allocating (set the allocated bit).
114 // Start a full collection.
115 // - beginMarking() clears markingNotEmpty, markingRetired
116 // - the heap version is incremented
117 // - marking rebuilds markingNotEmpty/markingretired bits.
118 // We do endMarking()
119 // - clear all allocated bits.
120 // - set canAllocateButNotEmpty/empty the same way as in eden collection.
121 // Snapshotting.
122 // - unswept = live
123 // prepare for allocation.
124 // - clear eden.
125 // Finish collection.
126 //
127 // Notice how in this scheme, the empty/canAllocateButNotEmpty state stays separate from the
128 // markingNotEmpty/markingRetired state. This is one step towards having separated allocation and
129 // marking state.
130
131 class MarkedAllocator {
132     friend class LLIntOffsetsExtractor;
133
134 public:
135     static ptrdiff_t offsetOfFreeList();
136     static ptrdiff_t offsetOfCellSize();
137
138     MarkedAllocator(Heap*, Subspace*, size_t cellSize);
139     void lastChanceToFinalize();
140     void prepareForAllocation();
141     void stopAllocating();
142     void resumeAllocating();
143     void beginMarkingForFullCollection();
144     void endMarking();
145     void snapshotUnsweptForEdenCollection();
146     void snapshotUnsweptForFullCollection();
147     void sweep();
148     void shrink();
149     void assertNoUnswept();
150     size_t cellSize() const { return m_cellSize; }
151     const AllocatorAttributes& attributes() const { return m_attributes; }
152     bool needsDestruction() const { return m_attributes.destruction == NeedsDestruction; }
153     DestructionMode destruction() const { return m_attributes.destruction; }
154     HeapCell::Kind cellKind() const { return m_attributes.cellKind; }
155     void* allocate(GCDeferralContext* = nullptr);
156     void* tryAllocate(GCDeferralContext* = nullptr);
157     Heap* heap() { return m_heap; }
158
159     template<typename Functor> void forEachBlock(const Functor&);
160     template<typename Functor> void forEachNotEmptyBlock(const Functor&);
161     
162     void addBlock(MarkedBlock::Handle*);
163     void removeBlock(MarkedBlock::Handle*);
164
165     bool isPagedOut(double deadline);
166     
167     static size_t blockSizeForBytes(size_t);
168     
169     Lock& bitvectorLock() { return m_bitvectorLock; }
170    
171 #define MARKED_ALLOCATOR_BIT_ACCESSORS(lowerBitName, capitalBitName)     \
172     bool is ## capitalBitName(const AbstractLocker&, size_t index) const { return m_ ## lowerBitName[index]; } \
173     bool is ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block) const { return is ## capitalBitName(locker, block->index()); } \
174     void setIs ## capitalBitName(const AbstractLocker&, size_t index, bool value) { m_ ## lowerBitName[index] = value; } \
175     void setIs ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block, bool value) { setIs ## capitalBitName(locker, block->index(), value); }
176     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_ACCESSORS)
177 #undef MARKED_ALLOCATOR_BIT_ACCESSORS
178
179     template<typename Func>
180     void forEachBitVector(const AbstractLocker&, const Func& func)
181     {
182 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
183         func(m_ ## lowerBitName);
184         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
185 #undef MARKED_ALLOCATOR_BIT_CALLBACK
186     }
187     
188     template<typename Func>
189     void forEachBitVectorWithName(const AbstractLocker&, const Func& func)
190     {
191 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
192         func(m_ ## lowerBitName, #capitalBitName);
193         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
194 #undef MARKED_ALLOCATOR_BIT_CALLBACK
195     }
196     
197     MarkedAllocator* nextAllocator() const { return m_nextAllocator; }
198     MarkedAllocator* nextAllocatorInSubspace() const { return m_nextAllocatorInSubspace; }
199     
200     void setNextAllocator(MarkedAllocator* allocator) { m_nextAllocator = allocator; }
201     void setNextAllocatorInSubspace(MarkedAllocator* allocator) { m_nextAllocatorInSubspace = allocator; }
202     
203     MarkedBlock::Handle* findEmptyBlockToSteal();
204     
205     MarkedBlock::Handle* findBlockToSweep();
206     
207     Subspace* subspace() const { return m_subspace; }
208     MarkedSpace& markedSpace() const;
209     
210     void dump(PrintStream&) const;
211     void dumpBits(PrintStream& = WTF::dataFile());
212     
213 private:
214     friend class MarkedBlock;
215     
216     bool shouldStealEmptyBlocksFromOtherAllocators() const;
217     
218     JS_EXPORT_PRIVATE void* allocateSlowCase(GCDeferralContext*);
219     JS_EXPORT_PRIVATE void* tryAllocateSlowCase(GCDeferralContext*);
220     void* allocateSlowCaseImpl(GCDeferralContext*, bool crashOnFailure);
221     void didConsumeFreeList();
222     void* tryAllocateWithoutCollecting();
223     MarkedBlock::Handle* tryAllocateBlock();
224     void* tryAllocateIn(MarkedBlock::Handle*);
225     void* allocateIn(MarkedBlock::Handle*);
226     ALWAYS_INLINE void doTestCollectionsIfNeeded(GCDeferralContext*);
227     
228     void setFreeList(const FreeList&);
229     
230     FreeList m_freeList;
231     
232     Vector<MarkedBlock::Handle*> m_blocks;
233     Vector<unsigned> m_freeBlockIndices;
234
235     // Mutator uses this to guard resizing the bitvectors. Those things in the GC that may run
236     // concurrently to the mutator must lock this when accessing the bitvectors.
237     Lock m_bitvectorLock;
238 #define MARKED_ALLOCATOR_BIT_DECLARATION(lowerBitName, capitalBitName) \
239     FastBitVector m_ ## lowerBitName;
240     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_DECLARATION)
241 #undef MARKED_ALLOCATOR_BIT_DECLARATION
242     
243     // After you do something to a block based on one of these cursors, you clear the bit in the
244     // corresponding bitvector and leave the cursor where it was.
245     size_t m_allocationCursor { 0 }; // Points to the next block that is a candidate for allocation.
246     size_t m_emptyCursor { 0 }; // Points to the next block that is a candidate for empty allocation (allocating in empty blocks).
247     size_t m_unsweptCursor { 0 }; // Points to the next block that is a candidate for incremental sweeping.
248     
249     MarkedBlock::Handle* m_currentBlock;
250     MarkedBlock::Handle* m_lastActiveBlock;
251
252     Lock m_lock;
253     unsigned m_cellSize;
254     AllocatorAttributes m_attributes;
255     // FIXME: All of these should probably be references.
256     // https://bugs.webkit.org/show_bug.cgi?id=166988
257     Heap* m_heap;
258     Subspace* m_subspace;
259     MarkedAllocator* m_nextAllocator { nullptr };
260     MarkedAllocator* m_nextAllocatorInSubspace { nullptr };
261 };
262
263 inline ptrdiff_t MarkedAllocator::offsetOfFreeList()
264 {
265     return OBJECT_OFFSETOF(MarkedAllocator, m_freeList);
266 }
267
268 inline ptrdiff_t MarkedAllocator::offsetOfCellSize()
269 {
270     return OBJECT_OFFSETOF(MarkedAllocator, m_cellSize);
271 }
272
273 } // namespace JSC