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