Rename MarkedSpace::version/MarkedBlock::version to MarkedSpace::markingVersion/Marke...
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedSpace.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, 2011, 2016 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 MarkedSpace_h
23 #define MarkedSpace_h
24
25 #include "IterationStatus.h"
26 #include "LargeAllocation.h"
27 #include "MarkedAllocator.h"
28 #include "MarkedBlock.h"
29 #include "MarkedBlockSet.h"
30 #include <array>
31 #include <wtf/Bag.h>
32 #include <wtf/HashSet.h>
33 #include <wtf/Noncopyable.h>
34 #include <wtf/RetainPtr.h>
35 #include <wtf/SentinelLinkedList.h>
36 #include <wtf/Vector.h>
37
38 namespace JSC {
39
40 class Heap;
41 class HeapIterationScope;
42 class LLIntOffsetsExtractor;
43 class WeakSet;
44
45 typedef uint32_t HeapVersion;
46
47 class MarkedSpace {
48     WTF_MAKE_NONCOPYABLE(MarkedSpace);
49 public:
50     // sizeStep is really a synonym for atomSize; it's no accident that they are the same.
51     static const size_t sizeStep = MarkedBlock::atomSize;
52     
53     // Sizes up to this amount get a size class for each size step.
54     static const size_t preciseCutoff = 80;
55     
56     // The amount of available payload in a block is the block's size minus the header. But the
57     // header size might not be atom size aligned, so we round down the result accordingly.
58     static const size_t blockPayload = (MarkedBlock::blockSize - sizeof(MarkedBlock)) & ~(MarkedBlock::atomSize - 1);
59     
60     // The largest cell we're willing to allocate in a MarkedBlock the "normal way" (i.e. using size
61     // classes, rather than a large allocation) is half the size of the payload, rounded down. This
62     // ensures that we only use the size class approach if it means being able to pack two things
63     // into one block.
64     static const size_t largeCutoff = (blockPayload / 2) & ~(sizeStep - 1);
65
66     static const size_t numSizeClasses = largeCutoff / sizeStep;
67     
68     static const HeapVersion nullVersion = 0; // The version of freshly allocated blocks.
69     static const HeapVersion initialVersion = 1; // The version that the heap starts out with.
70     
71     HeapVersion nextVersion(HeapVersion version)
72     {
73         version++;
74         if (version == nullVersion)
75             version++;
76         return version;
77     }
78     
79     static size_t sizeClassToIndex(size_t size)
80     {
81         ASSERT(size);
82         return (size + sizeStep - 1) / sizeStep - 1;
83     }
84     
85     static size_t indexToSizeClass(size_t index)
86     {
87         return (index + 1) * sizeStep;
88     }
89     
90     // Each Subspace corresponds to all of the blocks for all of the sizes for some "class" of
91     // objects. There are three classes: non-destructor JSCells, destructor JSCells, and auxiliary.
92     // MarkedSpace is set up to make it relatively easy to add new Subspaces.
93     struct Subspace {
94         std::array<MarkedAllocator*, numSizeClasses> allocatorForSizeStep;
95         
96         // Each MarkedAllocator is a size class.
97         Bag<MarkedAllocator> bagOfAllocators;
98         
99         AllocatorAttributes attributes;
100     };
101     
102     MarkedSpace(Heap*);
103     ~MarkedSpace();
104     void lastChanceToFinalize();
105
106     static size_t optimalSizeFor(size_t);
107     
108     static MarkedAllocator* allocatorFor(Subspace&, size_t);
109
110     MarkedAllocator* allocatorFor(size_t);
111     MarkedAllocator* destructorAllocatorFor(size_t);
112     MarkedAllocator* auxiliaryAllocatorFor(size_t);
113
114     JS_EXPORT_PRIVATE void* allocate(Subspace&, size_t);
115     JS_EXPORT_PRIVATE void* tryAllocate(Subspace&, size_t);
116     
117     void* allocateWithDestructor(size_t);
118     void* allocateWithoutDestructor(size_t);
119     void* allocateAuxiliary(size_t);
120     void* tryAllocateAuxiliary(size_t);
121     
122     Subspace& subspaceForObjectsWithDestructor() { return m_destructorSpace; }
123     Subspace& subspaceForObjectsWithoutDestructor() { return m_normalSpace; }
124     Subspace& subspaceForAuxiliaryData() { return m_auxiliarySpace; }
125     
126     void prepareForAllocation();
127
128     void visitWeakSets(HeapRootVisitor&);
129     void reapWeakSets();
130
131     MarkedBlockSet& blocks() { return m_blocks; }
132
133     void willStartIterating();
134     bool isIterating() const { return m_isIterating; }
135     void didFinishIterating();
136
137     void stopAllocating();
138     void resumeAllocating(); // If we just stopped allocation but we didn't do a collection, we need to resume allocation.
139     
140     void prepareForMarking();
141
142     typedef HashSet<MarkedBlock*>::iterator BlockIterator;
143
144     template<typename Functor> void forEachLiveCell(HeapIterationScope&, const Functor&);
145     template<typename Functor> void forEachDeadCell(HeapIterationScope&, const Functor&);
146     template<typename Functor> void forEachBlock(const Functor&);
147
148     void shrink();
149     void freeBlock(MarkedBlock::Handle*);
150     void freeOrShrinkBlock(MarkedBlock::Handle*);
151
152     void didAddBlock(MarkedBlock::Handle*);
153     void didConsumeFreeList(MarkedBlock::Handle*);
154     void didAllocateInBlock(MarkedBlock::Handle*);
155
156     void beginMarking();
157     void endMarking();
158     void snapshotUnswept();
159     void clearNewlyAllocated();
160     void sweep();
161     void sweepLargeAllocations();
162     void assertNoUnswept();
163     size_t objectCount();
164     size_t size();
165     size_t capacity();
166
167     bool isPagedOut(double deadline);
168     
169     HeapVersion markingVersion() const { return m_markingVersion; }
170
171     const Vector<LargeAllocation*>& largeAllocations() const { return m_largeAllocations; }
172     unsigned largeAllocationsNurseryOffset() const { return m_largeAllocationsNurseryOffset; }
173     unsigned largeAllocationsOffsetForThisCollection() const { return m_largeAllocationsOffsetForThisCollection; }
174     
175     // These are cached pointers and offsets for quickly searching the large allocations that are
176     // relevant to this collection.
177     LargeAllocation** largeAllocationsForThisCollectionBegin() const { return m_largeAllocationsForThisCollectionBegin; }
178     LargeAllocation** largeAllocationsForThisCollectionEnd() const { return m_largeAllocationsForThisCollectionEnd; }
179     unsigned largeAllocationsForThisCollectionSize() const { return m_largeAllocationsForThisCollectionSize; }
180     
181     MarkedAllocator* firstAllocator() const { return m_firstAllocator; }
182     MarkedAllocator* allocatorForEmptyAllocation() const { return m_allocatorForEmptyAllocation; }
183     
184     MarkedBlock::Handle* findEmptyBlockToSteal();
185     
186     // When this is true it means that we have flipped but the mark bits haven't converged yet.
187     bool isMarking() const { return m_isMarking; }
188     
189     void dumpBits(PrintStream& = WTF::dataFile());
190     
191 private:
192     friend class LLIntOffsetsExtractor;
193     friend class JIT;
194     friend class WeakSet;
195     
196     JS_EXPORT_PRIVATE static std::array<size_t, numSizeClasses> s_sizeClassForSizeStep;
197     
198     JS_EXPORT_PRIVATE void* allocateLarge(Subspace&, size_t);
199     JS_EXPORT_PRIVATE void* tryAllocateLarge(Subspace&, size_t);
200
201     static void initializeSizeClassForStepSize();
202     
203     void initializeSubspace(Subspace&);
204
205     template<typename Functor> inline void forEachAllocator(const Functor&);
206     template<typename Functor> inline void forEachSubspace(const Functor&);
207     
208     void addActiveWeakSet(WeakSet*);
209
210     Subspace m_destructorSpace;
211     Subspace m_normalSpace;
212     Subspace m_auxiliarySpace;
213
214     Heap* m_heap;
215     HeapVersion m_markingVersion { initialVersion };
216     size_t m_capacity;
217     bool m_isIterating;
218     bool m_isMarking { false };
219     MarkedBlockSet m_blocks;
220     Vector<LargeAllocation*> m_largeAllocations;
221     unsigned m_largeAllocationsNurseryOffset { 0 };
222     unsigned m_largeAllocationsOffsetForThisCollection { 0 };
223     unsigned m_largeAllocationsNurseryOffsetForSweep { 0 };
224     LargeAllocation** m_largeAllocationsForThisCollectionBegin { nullptr };
225     LargeAllocation** m_largeAllocationsForThisCollectionEnd { nullptr };
226     unsigned m_largeAllocationsForThisCollectionSize { 0 };
227     SentinelLinkedList<WeakSet, BasicRawSentinelNode<WeakSet>> m_activeWeakSets;
228     SentinelLinkedList<WeakSet, BasicRawSentinelNode<WeakSet>> m_newActiveWeakSets;
229     
230     MarkedAllocator* m_firstAllocator { nullptr };
231     MarkedAllocator* m_allocatorForEmptyAllocation { nullptr };
232 };
233
234 inline MarkedAllocator* MarkedSpace::allocatorFor(Subspace& space, size_t bytes)
235 {
236     ASSERT(bytes);
237     if (bytes <= largeCutoff)
238         return space.allocatorForSizeStep[sizeClassToIndex(bytes)];
239     return nullptr;
240 }
241
242 inline MarkedAllocator* MarkedSpace::allocatorFor(size_t bytes)
243 {
244     return allocatorFor(m_normalSpace, bytes);
245 }
246
247 inline MarkedAllocator* MarkedSpace::destructorAllocatorFor(size_t bytes)
248 {
249     return allocatorFor(m_destructorSpace, bytes);
250 }
251
252 inline MarkedAllocator* MarkedSpace::auxiliaryAllocatorFor(size_t bytes)
253 {
254     return allocatorFor(m_auxiliarySpace, bytes);
255 }
256
257 inline void* MarkedSpace::allocateWithoutDestructor(size_t bytes)
258 {
259     return allocate(m_normalSpace, bytes);
260 }
261
262 inline void* MarkedSpace::allocateWithDestructor(size_t bytes)
263 {
264     return allocate(m_destructorSpace, bytes);
265 }
266
267 inline void* MarkedSpace::allocateAuxiliary(size_t bytes)
268 {
269     return allocate(m_auxiliarySpace, bytes);
270 }
271
272 inline void* MarkedSpace::tryAllocateAuxiliary(size_t bytes)
273 {
274     return tryAllocate(m_auxiliarySpace, bytes);
275 }
276
277 template <typename Functor> inline void MarkedSpace::forEachBlock(const Functor& functor)
278 {
279     forEachAllocator(
280         [&] (MarkedAllocator& allocator) -> IterationStatus {
281             allocator.forEachBlock(functor);
282             return IterationStatus::Continue;
283         });
284 }
285
286 template <typename Functor>
287 void MarkedSpace::forEachAllocator(const Functor& functor)
288 {
289     for (MarkedAllocator* allocator = m_firstAllocator; allocator; allocator = allocator->nextAllocator()) {
290         if (functor(*allocator) == IterationStatus::Done)
291             return;
292     }
293 }
294
295 template<typename Functor>
296 inline void MarkedSpace::forEachSubspace(const Functor& func)
297 {
298     AllocatorAttributes attributes;
299     
300     attributes.destruction = NeedsDestruction;
301     attributes.cellKind = HeapCell::JSCell;
302     if (func(m_destructorSpace, attributes) == IterationStatus::Done)
303         return;
304     
305     attributes.destruction = DoesNotNeedDestruction;
306     attributes.cellKind = HeapCell::JSCell;
307     if (func(m_normalSpace, attributes) == IterationStatus::Done)
308         return;
309
310     attributes.destruction = DoesNotNeedDestruction;
311     attributes.cellKind = HeapCell::Auxiliary;
312     func(m_auxiliarySpace, attributes);
313 }
314
315 ALWAYS_INLINE size_t MarkedSpace::optimalSizeFor(size_t bytes)
316 {
317     ASSERT(bytes);
318     if (bytes <= preciseCutoff)
319         return WTF::roundUpToMultipleOf<sizeStep>(bytes);
320     if (bytes <= largeCutoff)
321         return s_sizeClassForSizeStep[sizeClassToIndex(bytes)];
322     return bytes;
323 }
324
325 } // namespace JSC
326
327 #endif // MarkedSpace_h