5f0491e866355a872e0f835c01d42e65766db0f5
[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-2017 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 Subspace;
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 = 2; // The version that the heap starts out with. Set to make sure that nextVersion(nullVersion) != initialVersion.
70     
71     static HeapVersion nextVersion(HeapVersion version)
72     {
73         version++;
74         if (version == nullVersion)
75             version = initialVersion;
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     MarkedSpace(Heap*);
91     ~MarkedSpace();
92     
93     Heap* heap() const { return m_heap; }
94     
95     void lastChanceToFinalize(); // You must call stopAllocating before you call this.
96
97     static size_t optimalSizeFor(size_t);
98     
99     void prepareForAllocation();
100
101     void visitWeakSets(SlotVisitor&);
102     void reapWeakSets();
103
104     MarkedBlockSet& blocks() { return m_blocks; }
105
106     void willStartIterating();
107     bool isIterating() const { return m_isIterating; }
108     void didFinishIterating();
109
110     void stopAllocating();
111     void resumeAllocating(); // If we just stopped allocation but we didn't do a collection, we need to resume allocation.
112     
113     void prepareForMarking();
114     
115     void prepareForConservativeScan();
116
117     typedef HashSet<MarkedBlock*>::iterator BlockIterator;
118
119     template<typename Functor> void forEachLiveCell(HeapIterationScope&, const Functor&);
120     template<typename Functor> void forEachDeadCell(HeapIterationScope&, const Functor&);
121     template<typename Functor> void forEachBlock(const Functor&);
122
123     void shrink();
124     void freeBlock(MarkedBlock::Handle*);
125     void freeOrShrinkBlock(MarkedBlock::Handle*);
126
127     void didAddBlock(MarkedBlock::Handle*);
128     void didConsumeFreeList(MarkedBlock::Handle*);
129     void didAllocateInBlock(MarkedBlock::Handle*);
130
131     void beginMarking();
132     void endMarking();
133     void snapshotUnswept();
134     void clearNewlyAllocated();
135     void sweep();
136     void sweepLargeAllocations();
137     void assertNoUnswept();
138     size_t objectCount();
139     size_t size();
140     size_t capacity();
141
142     bool isPagedOut(double deadline);
143     
144     HeapVersion markingVersion() const { return m_markingVersion; }
145     HeapVersion newlyAllocatedVersion() const { return m_newlyAllocatedVersion; }
146
147     const Vector<LargeAllocation*>& largeAllocations() const { return m_largeAllocations; }
148     unsigned largeAllocationsNurseryOffset() const { return m_largeAllocationsNurseryOffset; }
149     unsigned largeAllocationsOffsetForThisCollection() const { return m_largeAllocationsOffsetForThisCollection; }
150     
151     // These are cached pointers and offsets for quickly searching the large allocations that are
152     // relevant to this collection.
153     LargeAllocation** largeAllocationsForThisCollectionBegin() const { return m_largeAllocationsForThisCollectionBegin; }
154     LargeAllocation** largeAllocationsForThisCollectionEnd() const { return m_largeAllocationsForThisCollectionEnd; }
155     unsigned largeAllocationsForThisCollectionSize() const { return m_largeAllocationsForThisCollectionSize; }
156     
157     MarkedAllocator* firstAllocator() const { return m_firstAllocator; }
158     MarkedAllocator* allocatorForEmptyAllocation() const { return m_allocatorForEmptyAllocation; }
159     
160     MarkedBlock::Handle* findEmptyBlockToSteal();
161     
162     Lock& allocatorLock() { return m_allocatorLock; }
163     MarkedAllocator* addMarkedAllocator(const AbstractLocker&, Subspace*, size_t cellSize);
164     
165     // When this is true it means that we have flipped but the mark bits haven't converged yet.
166     bool isMarking() const { return m_isMarking; }
167     
168     void dumpBits(PrintStream& = WTF::dataFile());
169     
170     JS_EXPORT_PRIVATE static std::array<size_t, numSizeClasses> s_sizeClassForSizeStep;
171     
172 private:
173     friend class LLIntOffsetsExtractor;
174     friend class JIT;
175     friend class WeakSet;
176     friend class Subspace;
177     
178     void* allocateSlow(Subspace&, GCDeferralContext*, size_t);
179     void* tryAllocateSlow(Subspace&, GCDeferralContext*, size_t);
180
181     // Use this version when calling from within the GC where we know that the allocators
182     // have already been stopped.
183     template<typename Functor> void forEachLiveCell(const Functor&);
184
185     static void initializeSizeClassForStepSize();
186     
187     void initializeSubspace(Subspace&);
188
189     template<typename Functor> inline void forEachAllocator(const Functor&);
190     
191     void addActiveWeakSet(WeakSet*);
192
193     Vector<Subspace*> m_subspaces;
194
195     Vector<LargeAllocation*> m_largeAllocations;
196     unsigned m_largeAllocationsNurseryOffset { 0 };
197     unsigned m_largeAllocationsOffsetForThisCollection { 0 };
198     unsigned m_largeAllocationsNurseryOffsetForSweep { 0 };
199     LargeAllocation** m_largeAllocationsForThisCollectionBegin { nullptr };
200     LargeAllocation** m_largeAllocationsForThisCollectionEnd { nullptr };
201     unsigned m_largeAllocationsForThisCollectionSize { 0 };
202
203     Heap* m_heap;
204     HeapVersion m_markingVersion { initialVersion };
205     HeapVersion m_newlyAllocatedVersion { initialVersion };
206     size_t m_capacity;
207     bool m_isIterating;
208     bool m_isMarking { false };
209     MarkedBlockSet m_blocks;
210     
211     SentinelLinkedList<WeakSet, BasicRawSentinelNode<WeakSet>> m_activeWeakSets;
212     SentinelLinkedList<WeakSet, BasicRawSentinelNode<WeakSet>> m_newActiveWeakSets;
213
214     Lock m_allocatorLock;
215     Bag<MarkedAllocator> m_bagOfAllocators;
216     MarkedAllocator* m_firstAllocator { nullptr };
217     MarkedAllocator* m_lastAllocator { nullptr };
218     MarkedAllocator* m_allocatorForEmptyAllocation { nullptr };
219
220     friend class HeapVerifier;
221 };
222
223 template <typename Functor> inline void MarkedSpace::forEachBlock(const Functor& functor)
224 {
225     forEachAllocator(
226         [&] (MarkedAllocator& allocator) -> IterationStatus {
227             allocator.forEachBlock(functor);
228             return IterationStatus::Continue;
229         });
230 }
231
232 template <typename Functor>
233 void MarkedSpace::forEachAllocator(const Functor& functor)
234 {
235     for (MarkedAllocator* allocator = m_firstAllocator; allocator; allocator = allocator->nextAllocator()) {
236         if (functor(*allocator) == IterationStatus::Done)
237             return;
238     }
239 }
240
241 ALWAYS_INLINE size_t MarkedSpace::optimalSizeFor(size_t bytes)
242 {
243     ASSERT(bytes);
244     if (bytes <= preciseCutoff)
245         return WTF::roundUpToMultipleOf<sizeStep>(bytes);
246     if (bytes <= largeCutoff)
247         return s_sizeClassForSizeStep[sizeClassToIndex(bytes)];
248     return bytes;
249 }
250
251 } // namespace JSC