de617faca066795ca052dc02a70202800bd4aa9f
[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     bool isFreeListedCell(const void* target) const;
160
161     template<typename Functor> void forEachBlock(const Functor&);
162     template<typename Functor> void forEachNotEmptyBlock(const Functor&);
163     
164     void addBlock(MarkedBlock::Handle*);
165     void removeBlock(MarkedBlock::Handle*);
166
167     bool isPagedOut(double deadline);
168     
169     static size_t blockSizeForBytes(size_t);
170     
171     Lock& bitvectorLock() { return m_bitvectorLock; }
172    
173 #define MARKED_ALLOCATOR_BIT_ACCESSORS(lowerBitName, capitalBitName)     \
174     bool is ## capitalBitName(const AbstractLocker&, size_t index) const { return m_ ## lowerBitName[index]; } \
175     bool is ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block) const { return is ## capitalBitName(locker, block->index()); } \
176     void setIs ## capitalBitName(const AbstractLocker&, size_t index, bool value) { m_ ## lowerBitName[index] = value; } \
177     void setIs ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block, bool value) { setIs ## capitalBitName(locker, block->index(), value); }
178     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_ACCESSORS)
179 #undef MARKED_ALLOCATOR_BIT_ACCESSORS
180
181     template<typename Func>
182     void forEachBitVector(const AbstractLocker&, const Func& func)
183     {
184 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
185         func(m_ ## lowerBitName);
186         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
187 #undef MARKED_ALLOCATOR_BIT_CALLBACK
188     }
189     
190     template<typename Func>
191     void forEachBitVectorWithName(const AbstractLocker&, const Func& func)
192     {
193 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
194         func(m_ ## lowerBitName, #capitalBitName);
195         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
196 #undef MARKED_ALLOCATOR_BIT_CALLBACK
197     }
198     
199     MarkedAllocator* nextAllocator() const { return m_nextAllocator; }
200     MarkedAllocator* nextAllocatorInSubspace() const { return m_nextAllocatorInSubspace; }
201     
202     void setNextAllocator(MarkedAllocator* allocator) { m_nextAllocator = allocator; }
203     void setNextAllocatorInSubspace(MarkedAllocator* allocator) { m_nextAllocatorInSubspace = allocator; }
204     
205     MarkedBlock::Handle* findEmptyBlockToSteal();
206     
207     MarkedBlock::Handle* findBlockToSweep();
208     
209     Subspace* subspace() const { return m_subspace; }
210     MarkedSpace& markedSpace() const;
211     
212     const FreeList& freeList() const { return m_freeList; }
213     
214     void dump(PrintStream&) const;
215     void dumpBits(PrintStream& = WTF::dataFile());
216     
217 private:
218     friend class MarkedBlock;
219     
220     bool shouldStealEmptyBlocksFromOtherAllocators() const;
221     
222     JS_EXPORT_PRIVATE void* allocateSlowCase(GCDeferralContext*);
223     JS_EXPORT_PRIVATE void* tryAllocateSlowCase(GCDeferralContext*);
224     void* allocateSlowCaseImpl(GCDeferralContext*, bool crashOnFailure);
225     void didConsumeFreeList();
226     void* tryAllocateWithoutCollecting();
227     MarkedBlock::Handle* tryAllocateBlock();
228     void* tryAllocateIn(MarkedBlock::Handle*);
229     void* allocateIn(MarkedBlock::Handle*);
230     ALWAYS_INLINE void doTestCollectionsIfNeeded(GCDeferralContext*);
231     
232     FreeList m_freeList;
233     
234     Vector<MarkedBlock::Handle*> m_blocks;
235     Vector<unsigned> m_freeBlockIndices;
236
237     // Mutator uses this to guard resizing the bitvectors. Those things in the GC that may run
238     // concurrently to the mutator must lock this when accessing the bitvectors.
239     Lock m_bitvectorLock;
240 #define MARKED_ALLOCATOR_BIT_DECLARATION(lowerBitName, capitalBitName) \
241     FastBitVector m_ ## lowerBitName;
242     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_DECLARATION)
243 #undef MARKED_ALLOCATOR_BIT_DECLARATION
244     
245     // After you do something to a block based on one of these cursors, you clear the bit in the
246     // corresponding bitvector and leave the cursor where it was.
247     size_t m_allocationCursor { 0 }; // Points to the next block that is a candidate for allocation.
248     size_t m_emptyCursor { 0 }; // Points to the next block that is a candidate for empty allocation (allocating in empty blocks).
249     size_t m_unsweptCursor { 0 }; // Points to the next block that is a candidate for incremental sweeping.
250     
251     MarkedBlock::Handle* m_currentBlock;
252     MarkedBlock::Handle* m_lastActiveBlock;
253
254     Lock m_lock;
255     unsigned m_cellSize;
256     AllocatorAttributes m_attributes;
257     // FIXME: All of these should probably be references.
258     // https://bugs.webkit.org/show_bug.cgi?id=166988
259     Heap* m_heap;
260     Subspace* m_subspace;
261     MarkedAllocator* m_nextAllocator { nullptr };
262     MarkedAllocator* m_nextAllocatorInSubspace { nullptr };
263 };
264
265 inline ptrdiff_t MarkedAllocator::offsetOfFreeList()
266 {
267     return OBJECT_OFFSETOF(MarkedAllocator, m_freeList);
268 }
269
270 inline ptrdiff_t MarkedAllocator::offsetOfCellSize()
271 {
272     return OBJECT_OFFSETOF(MarkedAllocator, m_cellSize);
273 }
274
275 } // namespace JSC