9e589b9f7aadf24b402b8f3e96e94ffce30a25d2
[WebKit-https.git] / Source / JavaScriptCore / heap / BlockDirectory.cpp
1 /*
2  * Copyright (C) 2012-2018 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 #include "config.h"
27 #include "BlockDirectory.h"
28
29 #include "BlockDirectoryInlines.h"
30 #include "GCActivityCallback.h"
31 #include "Heap.h"
32 #include "IncrementalSweeper.h"
33 #include "JSCInlines.h"
34 #include "MarkedBlockInlines.h"
35 #include "SuperSampler.h"
36 #include "ThreadLocalCacheInlines.h"
37 #include "VM.h"
38 #include <wtf/CurrentTime.h>
39
40 namespace JSC {
41
42 BlockDirectory::BlockDirectory(Heap* heap, size_t cellSize)
43     : m_cellSize(static_cast<unsigned>(cellSize))
44     , m_heap(heap)
45 {
46     heap->threadLocalCacheLayout().allocateOffset(this);
47 }
48
49 BlockDirectory::~BlockDirectory()
50 {
51 }
52
53 void BlockDirectory::setSubspace(Subspace* subspace)
54 {
55     m_attributes = subspace->attributes();
56     m_subspace = subspace;
57 }
58
59 bool BlockDirectory::isPagedOut(MonotonicTime deadline)
60 {
61     unsigned itersSinceLastTimeCheck = 0;
62     for (auto* block : m_blocks) {
63         if (block)
64             holdLock(block->block().lock());
65         ++itersSinceLastTimeCheck;
66         if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
67             MonotonicTime currentTime = MonotonicTime::now();
68             if (currentTime > deadline)
69                 return true;
70             itersSinceLastTimeCheck = 0;
71         }
72     }
73     return false;
74 }
75
76 MarkedBlock::Handle* BlockDirectory::findEmptyBlockToSteal()
77 {
78     m_emptyCursor = m_empty.findBit(m_emptyCursor, true);
79     if (m_emptyCursor >= m_blocks.size())
80         return nullptr;
81     return m_blocks[m_emptyCursor];
82 }
83
84 MarkedBlock::Handle* BlockDirectory::findBlockForAllocation(LocalAllocator& allocator)
85 {
86     for (;;) {
87         allocator.m_allocationCursor = (m_canAllocateButNotEmpty | m_empty).findBit(allocator.m_allocationCursor, true);
88         if (allocator.m_allocationCursor >= m_blocks.size())
89             return nullptr;
90         
91         size_t blockIndex = allocator.m_allocationCursor++;
92         MarkedBlock::Handle* result = m_blocks[blockIndex];
93         if (result->securityOriginToken() == allocator.tlc()->securityOriginToken()) {
94             setIsCanAllocateButNotEmpty(NoLockingNecessary, blockIndex, false);
95             return result;
96         }
97     }
98 }
99
100 MarkedBlock::Handle* BlockDirectory::tryAllocateBlock()
101 {
102     SuperSamplerScope superSamplerScope(false);
103     
104     MarkedBlock::Handle* handle = MarkedBlock::tryCreate(*m_heap, subspace()->alignedMemoryAllocator());
105     if (!handle)
106         return nullptr;
107     
108     markedSpace().didAddBlock(handle);
109     
110     return handle;
111 }
112
113 void BlockDirectory::addBlock(MarkedBlock::Handle* block, SecurityOriginToken securityOriginToken)
114 {
115     size_t index;
116     if (m_freeBlockIndices.isEmpty()) {
117         index = m_blocks.size();
118
119         size_t oldCapacity = m_blocks.capacity();
120         m_blocks.append(block);
121         if (m_blocks.capacity() != oldCapacity) {
122             forEachBitVector(
123                 NoLockingNecessary,
124                 [&] (FastBitVector& vector) {
125                     ASSERT_UNUSED(vector, vector.numBits() == oldCapacity);
126                 });
127             
128             ASSERT(m_blocks.capacity() > oldCapacity);
129             
130             LockHolder locker(m_bitvectorLock);
131             subspace()->didResizeBits(m_blocks.capacity());
132             forEachBitVector(
133                 locker,
134                 [&] (FastBitVector& vector) {
135                     vector.resize(m_blocks.capacity());
136                 });
137         }
138     } else {
139         index = m_freeBlockIndices.takeLast();
140         ASSERT(!m_blocks[index]);
141         m_blocks[index] = block;
142     }
143     
144     forEachBitVector(
145         NoLockingNecessary,
146         [&] (FastBitVector& vector) {
147             ASSERT_UNUSED(vector, !vector[index]);
148         });
149
150     // This is the point at which the block learns of its cellSize() and attributes().
151     block->didAddToDirectory(this, index, securityOriginToken);
152     
153     setIsLive(NoLockingNecessary, index, true);
154     setIsEmpty(NoLockingNecessary, index, true);
155 }
156
157 void BlockDirectory::removeBlock(MarkedBlock::Handle* block)
158 {
159     ASSERT(block->directory() == this);
160     ASSERT(m_blocks[block->index()] == block);
161     
162     subspace()->didRemoveBlock(block->index());
163     
164     m_blocks[block->index()] = nullptr;
165     m_freeBlockIndices.append(block->index());
166     
167     forEachBitVector(
168         holdLock(m_bitvectorLock),
169         [&] (FastBitVector& vector) {
170             vector[block->index()] = false;
171         });
172     
173     block->didRemoveFromDirectory();
174 }
175
176 void BlockDirectory::stopAllocating()
177 {
178     if (false)
179         dataLog(RawPointer(this), ": BlockDirectory::stopAllocating!\n");
180     m_localAllocators.forEach(
181         [&] (LocalAllocator* allocator) {
182             allocator->stopAllocating();
183         });
184 }
185
186 void BlockDirectory::prepareForAllocation()
187 {
188     m_localAllocators.forEach(
189         [&] (LocalAllocator* allocator) {
190             allocator->prepareForAllocation();
191         });
192     
193     m_unsweptCursor = 0;
194     
195     m_eden.clearAll();
196
197     if (UNLIKELY(Options::useImmortalObjects())) {
198         // FIXME: Make this work again.
199         // https://bugs.webkit.org/show_bug.cgi?id=162296
200         RELEASE_ASSERT_NOT_REACHED();
201     }
202 }
203
204 void BlockDirectory::stopAllocatingForGood()
205 {
206     if (false)
207         dataLog(RawPointer(this), ": BlockDirectory::stopAllocatingForGood!\n");
208     
209     m_localAllocators.forEach(
210         [&] (LocalAllocator* allocator) {
211             allocator->stopAllocatingForGood();
212         });
213
214     auto locker = holdLock(m_localAllocatorsLock);
215     while (!m_localAllocators.isEmpty())
216         m_localAllocators.begin()->remove();
217 }
218
219 void BlockDirectory::lastChanceToFinalize()
220 {
221     forEachBlock(
222         [&] (MarkedBlock::Handle* block) {
223             block->lastChanceToFinalize();
224         });
225 }
226
227 void BlockDirectory::resumeAllocating()
228 {
229     m_localAllocators.forEach(
230         [&] (LocalAllocator* allocator) {
231             allocator->resumeAllocating();
232         });
233 }
234
235 void BlockDirectory::beginMarkingForFullCollection()
236 {
237     // Mark bits are sticky and so is our summary of mark bits. We only clear these during full
238     // collections, so if you survived the last collection you will survive the next one so long
239     // as the next one is eden.
240     m_markingNotEmpty.clearAll();
241     m_markingRetired.clearAll();
242 }
243
244 void BlockDirectory::endMarking()
245 {
246     m_allocated.clearAll();
247     
248     // It's surprising and frustrating to comprehend, but the end-of-marking flip does not need to
249     // know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ
250     // vectors.
251     
252     if (!Options::tradeDestructorBlocks() && needsDestruction()) {
253         ASSERT(m_empty.isEmpty());
254         m_canAllocateButNotEmpty = m_live & ~m_markingRetired;
255     } else {
256         m_empty = m_live & ~m_markingNotEmpty;
257         m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
258     }
259     
260     if (needsDestruction()) {
261         // There are some blocks that we didn't allocate out of in the last cycle, but we swept them. This
262         // will forget that we did that and we will end up sweeping them again and attempting to call their
263         // destructors again. That's fine because of zapping. The only time when we cannot forget is when
264         // we just allocate a block or when we move a block from one size class to another. That doesn't
265         // happen here.
266         m_destructible = m_live;
267     }
268     
269     if (false) {
270         dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n");
271         dumpBits(WTF::dataFile());
272     }
273 }
274
275 void BlockDirectory::snapshotUnsweptForEdenCollection()
276 {
277     m_unswept |= m_eden;
278 }
279
280 void BlockDirectory::snapshotUnsweptForFullCollection()
281 {
282     m_unswept = m_live;
283 }
284
285 MarkedBlock::Handle* BlockDirectory::findBlockToSweep()
286 {
287     m_unsweptCursor = m_unswept.findBit(m_unsweptCursor, true);
288     if (m_unsweptCursor >= m_blocks.size())
289         return nullptr;
290     return m_blocks[m_unsweptCursor];
291 }
292
293 void BlockDirectory::sweep()
294 {
295     m_unswept.forEachSetBit(
296         [&] (size_t index) {
297             MarkedBlock::Handle* block = m_blocks[index];
298             block->sweep(nullptr);
299         });
300 }
301
302 void BlockDirectory::shrink()
303 {
304     (m_empty & ~m_destructible).forEachSetBit(
305         [&] (size_t index) {
306             markedSpace().freeBlock(m_blocks[index]);
307         });
308 }
309
310 void BlockDirectory::assertNoUnswept()
311 {
312     if (ASSERT_DISABLED)
313         return;
314     
315     if (m_unswept.isEmpty())
316         return;
317     
318     dataLog("Assertion failed: unswept not empty in ", *this, ".\n");
319     dumpBits();
320     ASSERT_NOT_REACHED();
321 }
322
323 RefPtr<SharedTask<MarkedBlock::Handle*()>> BlockDirectory::parallelNotEmptyBlockSource()
324 {
325     class Task : public SharedTask<MarkedBlock::Handle*()> {
326     public:
327         Task(BlockDirectory& directory)
328             : m_directory(directory)
329         {
330         }
331         
332         MarkedBlock::Handle* run() override
333         {
334             if (m_done)
335                 return nullptr;
336             auto locker = holdLock(m_lock);
337             m_index = m_directory.m_markingNotEmpty.findBit(m_index, true);
338             if (m_index >= m_directory.m_blocks.size()) {
339                 m_done = true;
340                 return nullptr;
341             }
342             return m_directory.m_blocks[m_index++];
343         }
344         
345     private:
346         BlockDirectory& m_directory;
347         size_t m_index { 0 };
348         Lock m_lock;
349         bool m_done { false };
350     };
351     
352     return adoptRef(new Task(*this));
353 }
354
355 void BlockDirectory::dump(PrintStream& out) const
356 {
357     out.print(RawPointer(this), ":", m_cellSize, "/", m_attributes);
358 }
359
360 void BlockDirectory::dumpBits(PrintStream& out)
361 {
362     unsigned maxNameLength = 0;
363     forEachBitVectorWithName(
364         NoLockingNecessary,
365         [&] (FastBitVector&, const char* name) {
366             unsigned length = strlen(name);
367             maxNameLength = std::max(maxNameLength, length);
368         });
369     
370     forEachBitVectorWithName(
371         NoLockingNecessary,
372         [&] (FastBitVector& vector, const char* name) {
373             out.print("    ", name, ": ");
374             for (unsigned i = maxNameLength - strlen(name); i--;)
375                 out.print(" ");
376             out.print(vector, "\n");
377         });
378 }
379
380 MarkedSpace& BlockDirectory::markedSpace() const
381 {
382     return m_subspace->space();
383 }
384
385 bool BlockDirectory::isFreeListedCell(const void* target)
386 {
387     bool result = false;
388     m_localAllocators.forEach(
389         [&] (LocalAllocator* allocator) {
390             result |= allocator->isFreeListedCell(target);
391         });
392     return result;
393 }
394
395 } // namespace JSC
396