Adopt #pragma once in JavaScriptCore
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedAllocator.h
1 /*
2  * Copyright (C) 2012, 2013, 2016 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 Heap;
38 class MarkedSpace;
39 class LLIntOffsetsExtractor;
40
41 #define FOR_EACH_MARKED_ALLOCATOR_BIT(macro) \
42     macro(live, Live) /* The set of block indices that have actual blocks. */\
43     macro(empty, Empty) /* The set of all blocks that have no live objects and nothing to destroy. */ \
44     macro(allocated, Allocated) /* The set of allblocks that are full of live objects. */\
45     macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
46     macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
47     macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
48     \
49     /* These are computed during marking. */\
50     macro(markingNotEmpty, MarkingNotEmpty) /* The set of all blocks that are not empty. */ \
51     macro(markingRetired, MarkingRetired) /* The set of all blocks that are retired. */
52
53 // FIXME: We defined canAllocateButNotEmpty and empty to be exclusive:
54 //
55 //     canAllocateButNotEmpty & empty == 0
56 //
57 // Instead of calling it canAllocate and making it inclusive:
58 //
59 //     canAllocate & empty == empty
60 //
61 // The latter is probably better. I'll leave it to a future bug to fix that, since breathing on
62 // this code leads to regressions for days, and it's not clear that making this change would
63 // improve perf since it would not change the collector's behavior, and either way the allocator
64 // has to look at both bitvectors.
65 // https://bugs.webkit.org/show_bug.cgi?id=162121
66
67 // Note that this collector supports overlapping allocator state with marking state, since in a
68 // concurrent collector you allow allocation while marking is running. So it's best to visualize a
69 // full mutable->eden collect->mutate->full collect cycle and see how the bits above get affected.
70 // The example below tries to be exhaustive about what happens to the bits, but omits a lot of
71 // things that happen to other state.
72 //
73 // Create allocator
74 // - all bits are empty
75 // Start allocating in some block
76 // - allocate the block and set the live bit.
77 // - the empty bit for the block flickers on and then gets immediately cleared by sweeping.
78 // - set the eden bit.
79 // Finish allocating in that block
80 // - set the allocated bit.
81 // Do that to a lot of blocks and then start an eden collection.
82 // - beginMarking() has nothing to do.
83 // - by default we have cleared markingNotEmpty/markingRetired bits.
84 // - marking builds up markingNotEmpty/markingRetired bits.
85 // We do endMarking()
86 // - clear all allocated bits.
87 // - for destructor blocks: fragmented = live & ~markingRetired
88 // - for non-destructor blocks:
89 //       empty = live & ~markingNotEmpty
90 //       fragmented = live & markingNotEmpty & ~markingRetired
91 // Snapshotting.
92 // - unswept |= eden
93 // Prepare for allocation.
94 // - clear eden
95 // Finish collection.
96 // Allocate in some block that had some free and some live objects.
97 // - clear the canAllocateButNotEmpty bit
98 // - clear the unswept bit
99 // - set the eden bit
100 // Finish allocating (set the allocated bit).
101 // Allocate in some block that was completely empty.
102 // - clear the empty bit
103 // - clear the unswept bit
104 // - set the eden bit.
105 // Finish allocating (set the allocated bit).
106 // Allocate in some block that was completely empty in another allocator.
107 // - clear the empty bit
108 // - clear all bits in that allocator
109 // - set the live bit in another allocator and the empty bit.
110 // - clear the empty, unswept bits.
111 // - set the eden bit.
112 // Finish allocating (set the allocated bit).
113 // Start a full collection.
114 // - beginMarking() clears markingNotEmpty, markingRetired
115 // - the heap version is incremented
116 // - marking rebuilds markingNotEmpty/markingretired bits.
117 // We do endMarking()
118 // - clear all allocated bits.
119 // - set canAllocateButNotEmpty/empty the same way as in eden collection.
120 // Snapshotting.
121 // - unswept = live
122 // prepare for allocation.
123 // - clear eden.
124 // Finish collection.
125 //
126 // Notice how in this scheme, the empty/canAllocateButNotEmpty state stays separate from the
127 // markingNotEmpty/markingRetired state. This is one step towards having separated allocation and
128 // marking state.
129
130 class MarkedAllocator {
131     friend class LLIntOffsetsExtractor;
132
133 public:
134     static ptrdiff_t offsetOfFreeList();
135     static ptrdiff_t offsetOfCellSize();
136
137     MarkedAllocator(Heap*, MarkedSpace*, size_t cellSize, const AllocatorAttributes&);
138     void lastChanceToFinalize();
139     void prepareForAllocation();
140     void stopAllocating();
141     void resumeAllocating();
142     void beginMarkingForFullCollection();
143     void endMarking();
144     void snapshotUnsweptForEdenCollection();
145     void snapshotUnsweptForFullCollection();
146     void sweep();
147     void shrink();
148     void assertNoUnswept();
149     size_t cellSize() const { return m_cellSize; }
150     const AllocatorAttributes& attributes() const { return m_attributes; }
151     bool needsDestruction() const { return m_attributes.destruction == NeedsDestruction; }
152     DestructionMode destruction() const { return m_attributes.destruction; }
153     HeapCell::Kind cellKind() const { return m_attributes.cellKind; }
154     void* allocate();
155     void* tryAllocate();
156     Heap* heap() { return m_heap; }
157     MarkedBlock::Handle* takeLastActiveBlock()
158     {
159         MarkedBlock::Handle* block = m_lastActiveBlock;
160         m_lastActiveBlock = 0;
161         return block;
162     }
163     
164     template<typename Functor> void forEachBlock(const Functor&);
165     
166     void addBlock(MarkedBlock::Handle*);
167     void removeBlock(MarkedBlock::Handle*);
168
169     bool isPagedOut(double deadline);
170     
171     static size_t blockSizeForBytes(size_t);
172     
173 #define MARKED_ALLOCATOR_BIT_ACCESSORS(lowerBitName, capitalBitName)     \
174     bool is ## capitalBitName(size_t index) const { return m_ ## lowerBitName[index]; } \
175     bool is ## capitalBitName(MarkedBlock::Handle* block) const { return is ## capitalBitName(block->index()); } \
176     void setIs ## capitalBitName(size_t index, bool value) { m_ ## lowerBitName[index] = value; } \
177     void setIs ## capitalBitName(MarkedBlock::Handle* block, bool value) { setIs ## capitalBitName(block->index(), value); } \
178     bool atomicSetAndCheckIs ## capitalBitName(size_t index, bool value) { return m_ ## lowerBitName.atomicSetAndCheck(index, value); } \
179     bool atomicSetAndCheckIs ## capitalBitName(MarkedBlock::Handle* block, bool value) { return m_ ## lowerBitName.atomicSetAndCheck(block->index(), value); }
180     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_ACCESSORS)
181 #undef MARKED_ALLOCATOR_BIT_ACCESSORS
182
183     template<typename Func>
184     void forEachBitVector(const Func& func)
185     {
186 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
187         func(m_ ## lowerBitName);
188         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
189 #undef MARKED_ALLOCATOR_BIT_CALLBACK
190     }
191     
192     template<typename Func>
193     void forEachBitVectorWithName(const Func& func)
194     {
195 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
196         func(m_ ## lowerBitName, #capitalBitName);
197         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
198 #undef MARKED_ALLOCATOR_BIT_CALLBACK
199     }
200     
201     MarkedAllocator* nextAllocator() const { return m_nextAllocator; }
202     
203     // MarkedSpace calls this during init.
204     void setNextAllocator(MarkedAllocator* allocator) { m_nextAllocator = allocator; }
205     
206     MarkedBlock::Handle* findEmptyBlockToSteal();
207     
208     MarkedBlock::Handle* findBlockToSweep();
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();
219     JS_EXPORT_PRIVATE void* tryAllocateSlowCase();
220     void* allocateSlowCaseImpl(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();
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 #define MARKED_ALLOCATOR_BIT_DECLARATION(lowerBitName, capitalBitName) \
236     FastBitVector m_ ## lowerBitName;
237     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_DECLARATION)
238 #undef MARKED_ALLOCATOR_BIT_DECLARATION
239     
240     // After you do something to a block based on one of these cursors, you clear the bit in the
241     // corresponding bitvector and leave the cursor where it was.
242     size_t m_allocationCursor { 0 }; // Points to the next block that is a candidate for allocation.
243     size_t m_emptyCursor { 0 }; // Points to the next block that is a candidate for empty allocation (allocating in empty blocks).
244     size_t m_unsweptCursor { 0 }; // Points to the next block that is a candidate for incremental sweeping.
245     
246     MarkedBlock::Handle* m_currentBlock;
247     MarkedBlock::Handle* m_lastActiveBlock;
248
249     Lock m_lock;
250     unsigned m_cellSize;
251     AllocatorAttributes m_attributes;
252     Heap* m_heap;
253     MarkedSpace* m_markedSpace;
254     MarkedAllocator* m_nextAllocator;
255 };
256
257 inline ptrdiff_t MarkedAllocator::offsetOfFreeList()
258 {
259     return OBJECT_OFFSETOF(MarkedAllocator, m_freeList);
260 }
261
262 inline ptrdiff_t MarkedAllocator::offsetOfCellSize()
263 {
264     return OBJECT_OFFSETOF(MarkedAllocator, m_cellSize);
265 }
266
267 ALWAYS_INLINE void* MarkedAllocator::tryAllocate()
268 {
269     unsigned remaining = m_freeList.remaining;
270     if (remaining) {
271         unsigned cellSize = m_cellSize;
272         remaining -= cellSize;
273         m_freeList.remaining = remaining;
274         return m_freeList.payloadEnd - remaining - cellSize;
275     }
276     
277     FreeCell* head = m_freeList.head;
278     if (UNLIKELY(!head))
279         return tryAllocateSlowCase();
280     
281     m_freeList.head = head->next;
282     return head;
283 }
284
285 ALWAYS_INLINE void* MarkedAllocator::allocate()
286 {
287     unsigned remaining = m_freeList.remaining;
288     if (remaining) {
289         unsigned cellSize = m_cellSize;
290         remaining -= cellSize;
291         m_freeList.remaining = remaining;
292         return m_freeList.payloadEnd - remaining - cellSize;
293     }
294     
295     FreeCell* head = m_freeList.head;
296     if (UNLIKELY(!head))
297         return allocateSlowCase();
298     
299     m_freeList.head = head->next;
300     return head;
301 }
302
303 template <typename Functor> inline void MarkedAllocator::forEachBlock(const Functor& functor)
304 {
305     m_live.forEachSetBit(
306         [&] (size_t index) {
307             functor(m_blocks[index]);
308         });
309 }
310
311 } // namespace JSC