017db7aad817e33d7e9530468fb8eaf2dbafbbb3
[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-2018 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 "BlockDirectory.h"
25 #include "IterationStatus.h"
26 #include "LargeAllocation.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/SinglyLinkedListWithTail.h>
36 #include <wtf/Vector.h>
37
38 namespace JSC {
39
40 class CompleteSubspace;
41 class Heap;
42 class HeapCell;
43 class HeapIterationScope;
44 class IsoSubspace;
45 class LLIntOffsetsExtractor;
46 class Subspace;
47 class WeakSet;
48
49 typedef uint32_t HeapVersion;
50
51 class MarkedSpace {
52     WTF_MAKE_NONCOPYABLE(MarkedSpace);
53 public:
54     // sizeStep is really a synonym for atomSize; it's no accident that they are the same.
55     static constexpr size_t sizeStep = MarkedBlock::atomSize;
56     
57     // Sizes up to this amount get a size class for each size step.
58     static constexpr size_t preciseCutoff = 80;
59     
60     // The amount of available payload in a block is the block's size minus the footer.
61     static constexpr size_t blockPayload = MarkedBlock::payloadSize;
62     
63     // The largest cell we're willing to allocate in a MarkedBlock the "normal way" (i.e. using size
64     // classes, rather than a large allocation) is half the size of the payload, rounded down. This
65     // ensures that we only use the size class approach if it means being able to pack two things
66     // into one block.
67     static constexpr size_t largeCutoff = (blockPayload / 2) & ~(sizeStep - 1);
68
69     // We have an extra size class for size zero.
70     static constexpr size_t numSizeClasses = largeCutoff / sizeStep + 1;
71     
72     static constexpr HeapVersion nullVersion = 0; // The version of freshly allocated blocks.
73     static constexpr HeapVersion initialVersion = 2; // The version that the heap starts out with. Set to make sure that nextVersion(nullVersion) != initialVersion.
74     
75     static HeapVersion nextVersion(HeapVersion version)
76     {
77         version++;
78         if (version == nullVersion)
79             version = initialVersion;
80         return version;
81     }
82     
83     static size_t sizeClassToIndex(size_t size)
84     {
85         return (size + sizeStep - 1) / sizeStep;
86     }
87     
88     static size_t indexToSizeClass(size_t index)
89     {
90         size_t result = index * sizeStep;
91         ASSERT(sizeClassToIndex(result) == index);
92         return result;
93     }
94     
95     MarkedSpace(Heap*);
96     ~MarkedSpace();
97     
98     Heap* heap() const { return m_heap; }
99     
100     void lastChanceToFinalize(); // Must call stopAllocatingForGood first.
101     void freeMemory();
102
103     static size_t optimalSizeFor(size_t);
104     
105     void prepareForAllocation();
106
107     void visitWeakSets(SlotVisitor&);
108     void reapWeakSets();
109
110     MarkedBlockSet& blocks() { return m_blocks; }
111
112     void willStartIterating();
113     bool isIterating() const { return m_isIterating; }
114     void didFinishIterating();
115
116     void stopAllocating();
117     void stopAllocatingForGood();
118     void resumeAllocating(); // If we just stopped allocation but we didn't do a collection, we need to resume allocation.
119     
120     void prepareForMarking();
121     
122     void prepareForConservativeScan();
123
124     typedef HashSet<MarkedBlock*>::iterator BlockIterator;
125
126     template<typename Functor> void forEachLiveCell(HeapIterationScope&, const Functor&);
127     template<typename Functor> void forEachDeadCell(HeapIterationScope&, const Functor&);
128     template<typename Functor> void forEachBlock(const Functor&);
129     template<typename Functor> void forEachSubspace(const Functor&);
130
131     void shrink();
132     void freeBlock(MarkedBlock::Handle*);
133     void freeOrShrinkBlock(MarkedBlock::Handle*);
134
135     void didAddBlock(MarkedBlock::Handle*);
136     void didConsumeFreeList(MarkedBlock::Handle*);
137     void didAllocateInBlock(MarkedBlock::Handle*);
138
139     void beginMarking();
140     void endMarking();
141     void snapshotUnswept();
142     void clearNewlyAllocated();
143     void sweep();
144     void sweepLargeAllocations();
145     void assertNoUnswept();
146     size_t objectCount();
147     size_t size();
148     size_t capacity();
149
150     bool isPagedOut(MonotonicTime deadline);
151     
152     HeapVersion markingVersion() const { return m_markingVersion; }
153     HeapVersion newlyAllocatedVersion() const { return m_newlyAllocatedVersion; }
154
155     const Vector<LargeAllocation*>& largeAllocations() const { return m_largeAllocations; }
156     unsigned largeAllocationsNurseryOffset() const { return m_largeAllocationsNurseryOffset; }
157     unsigned largeAllocationsOffsetForThisCollection() const { return m_largeAllocationsOffsetForThisCollection; }
158     HashSet<HeapCell*>* largeAllocationSet() const { return m_largeAllocationSet.get(); }
159
160     void enableLargeAllocationTracking();
161     
162     // These are cached pointers and offsets for quickly searching the large allocations that are
163     // relevant to this collection.
164     LargeAllocation** largeAllocationsForThisCollectionBegin() const { return m_largeAllocationsForThisCollectionBegin; }
165     LargeAllocation** largeAllocationsForThisCollectionEnd() const { return m_largeAllocationsForThisCollectionEnd; }
166     unsigned largeAllocationsForThisCollectionSize() const { return m_largeAllocationsForThisCollectionSize; }
167     
168     BlockDirectory* firstDirectory() const { return m_directories.first(); }
169     
170     Lock& directoryLock() { return m_directoryLock; }
171     void addBlockDirectory(const AbstractLocker&, BlockDirectory*);
172     
173     // When this is true it means that we have flipped but the mark bits haven't converged yet.
174     bool isMarking() const { return m_isMarking; }
175     
176     WeakSet* activeWeakSetsBegin() { return m_activeWeakSets.begin(); }
177     WeakSet* activeWeakSetsEnd() { return m_activeWeakSets.end(); }
178     WeakSet* newActiveWeakSetsBegin() { return m_newActiveWeakSets.begin(); }
179     WeakSet* newActiveWeakSetsEnd() { return m_newActiveWeakSets.end(); }
180     
181     void dumpBits(PrintStream& = WTF::dataFile());
182     
183     JS_EXPORT_PRIVATE static std::array<size_t, numSizeClasses> s_sizeClassForSizeStep;
184     
185 private:
186     friend class CompleteSubspace;
187     friend class LLIntOffsetsExtractor;
188     friend class JIT;
189     friend class WeakSet;
190     friend class Subspace;
191     friend class IsoSubspace;
192     
193     // Use this version when calling from within the GC where we know that the directories
194     // have already been stopped.
195     template<typename Functor> void forEachLiveCell(const Functor&);
196
197     static void initializeSizeClassForStepSize();
198     
199     void initializeSubspace(Subspace&);
200
201     template<typename Functor> inline void forEachDirectory(const Functor&);
202     
203     void addActiveWeakSet(WeakSet*);
204
205     Vector<Subspace*> m_subspaces;
206
207     std::unique_ptr<HashSet<HeapCell*>> m_largeAllocationSet;
208     Vector<LargeAllocation*> m_largeAllocations;
209     unsigned m_largeAllocationsNurseryOffset { 0 };
210     unsigned m_largeAllocationsOffsetForThisCollection { 0 };
211     unsigned m_largeAllocationsNurseryOffsetForSweep { 0 };
212     unsigned m_largeAllocationsForThisCollectionSize { 0 };
213     LargeAllocation** m_largeAllocationsForThisCollectionBegin { nullptr };
214     LargeAllocation** m_largeAllocationsForThisCollectionEnd { nullptr };
215
216     Heap* m_heap;
217     size_t m_capacity { 0 };
218     HeapVersion m_markingVersion { initialVersion };
219     HeapVersion m_newlyAllocatedVersion { initialVersion };
220     bool m_isIterating { false };
221     bool m_isMarking { false };
222     Lock m_directoryLock;
223     MarkedBlockSet m_blocks;
224     
225     SentinelLinkedList<WeakSet, BasicRawSentinelNode<WeakSet>> m_activeWeakSets;
226     SentinelLinkedList<WeakSet, BasicRawSentinelNode<WeakSet>> m_newActiveWeakSets;
227
228     SinglyLinkedListWithTail<BlockDirectory> m_directories;
229
230     friend class HeapVerifier;
231 };
232
233 template <typename Functor> inline void MarkedSpace::forEachBlock(const Functor& functor)
234 {
235     forEachDirectory(
236         [&] (BlockDirectory& directory) -> IterationStatus {
237             directory.forEachBlock(functor);
238             return IterationStatus::Continue;
239         });
240 }
241
242 template <typename Functor>
243 void MarkedSpace::forEachDirectory(const Functor& functor)
244 {
245     for (BlockDirectory* directory = m_directories.first(); directory; directory = directory->nextDirectory()) {
246         if (functor(*directory) == IterationStatus::Done)
247             return;
248     }
249 }
250
251 template<typename Functor>
252 void MarkedSpace::forEachSubspace(const Functor& functor)
253 {
254     for (auto subspace : m_subspaces) {
255         if (functor(*subspace) == IterationStatus::Done)
256             return;
257     }
258 }
259
260
261 ALWAYS_INLINE size_t MarkedSpace::optimalSizeFor(size_t bytes)
262 {
263     ASSERT(bytes);
264     if (bytes <= preciseCutoff)
265         return WTF::roundUpToMultipleOf<sizeStep>(bytes);
266     if (bytes <= largeCutoff)
267         return s_sizeClassForSizeStep[sizeClassToIndex(bytes)];
268     return bytes;
269 }
270
271 } // namespace JSC