Make opaque root scanning truly constraint-based
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedAllocator.cpp
1 /*
2  * Copyright (C) 2012-2017 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 "MarkedAllocator.h"
28
29 #include "AllocatingScope.h"
30 #include "GCActivityCallback.h"
31 #include "Heap.h"
32 #include "IncrementalSweeper.h"
33 #include "JSCInlines.h"
34 #include "MarkedAllocatorInlines.h"
35 #include "MarkedBlockInlines.h"
36 #include "SuperSampler.h"
37 #include "VM.h"
38 #include <wtf/CurrentTime.h>
39
40 namespace JSC {
41
42 MarkedAllocator::MarkedAllocator(Heap* heap, Subspace* subspace, size_t cellSize)
43     : m_currentBlock(0)
44     , m_lastActiveBlock(0)
45     , m_cellSize(static_cast<unsigned>(cellSize))
46     , m_attributes(subspace->attributes())
47     , m_heap(heap)
48     , m_subspace(subspace)
49 {
50 }
51
52 bool MarkedAllocator::isPagedOut(double deadline)
53 {
54     unsigned itersSinceLastTimeCheck = 0;
55     for (auto* block : m_blocks) {
56         if (block)
57             block->block().updateNeedsDestruction();
58         ++itersSinceLastTimeCheck;
59         if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
60             double currentTime = WTF::monotonicallyIncreasingTime();
61             if (currentTime > deadline)
62                 return true;
63             itersSinceLastTimeCheck = 0;
64         }
65     }
66     return false;
67 }
68
69 bool MarkedAllocator::shouldStealEmptyBlocksFromOtherAllocators() const
70 {
71     return !needsDestruction();
72 }
73
74 MarkedBlock::Handle* MarkedAllocator::findEmptyBlockToSteal()
75 {
76     // Don't allow others to steal from us, if we wouldn't steal from others.
77     if (!shouldStealEmptyBlocksFromOtherAllocators())
78         return nullptr;
79     
80     m_emptyCursor = m_empty.findBit(m_emptyCursor, true);
81     if (m_emptyCursor >= m_blocks.size())
82         return nullptr;
83     return m_blocks[m_emptyCursor];
84 }
85
86 void MarkedAllocator::didConsumeFreeList()
87 {
88     if (m_currentBlock)
89         m_currentBlock->didConsumeFreeList();
90     
91     setFreeList(FreeList());
92     m_currentBlock = nullptr;
93 }
94
95 void* MarkedAllocator::tryAllocateWithoutCollecting()
96 {
97     SuperSamplerScope superSamplerScope(false);
98     
99     ASSERT(!m_currentBlock);
100     ASSERT(!m_freeList);
101     
102     for (;;) {
103         m_allocationCursor = (m_canAllocateButNotEmpty | m_empty).findBit(m_allocationCursor, true);
104         if (m_allocationCursor >= m_blocks.size())
105             break;
106         
107         setIsCanAllocateButNotEmpty(NoLockingNecessary, m_allocationCursor, false);
108
109         if (void* result = tryAllocateIn(m_blocks[m_allocationCursor]))
110             return result;
111     }
112     
113     if (Options::stealEmptyBlocksFromOtherAllocators()
114         && shouldStealEmptyBlocksFromOtherAllocators()) {
115         if (MarkedBlock::Handle* block = markedSpace().findEmptyBlockToSteal()) {
116             block->sweep();
117             
118             // It's good that this clears canAllocateButNotEmpty as well as all other bits,
119             // because there is a remote chance that a block may have both canAllocateButNotEmpty
120             // and empty set at the same time.
121             block->removeFromAllocator();
122             addBlock(block);
123             return allocateIn(block);
124         }
125     }
126     
127     return nullptr;
128 }
129
130 void* MarkedAllocator::allocateIn(MarkedBlock::Handle* block)
131 {
132     void* result = tryAllocateIn(block);
133     RELEASE_ASSERT(result);
134     return result;
135 }
136
137 void* MarkedAllocator::tryAllocateIn(MarkedBlock::Handle* block)
138 {
139     ASSERT(block);
140     ASSERT(!block->isFreeListed());
141     
142     FreeList freeList = block->sweep(MarkedBlock::Handle::SweepToFreeList);
143     
144     // It's possible to stumble on a completely full block. Marking tries to retire these, but
145     // that algorithm is racy and may forget to do it sometimes.
146     if (freeList.allocationWillFail()) {
147         ASSERT(block->isFreeListed());
148         block->unsweepWithNoNewlyAllocated();
149         ASSERT(!block->isFreeListed());
150         ASSERT(!isEmpty(NoLockingNecessary, block));
151         ASSERT(!isCanAllocateButNotEmpty(NoLockingNecessary, block));
152         return nullptr;
153     }
154     
155     m_currentBlock = block;
156     setFreeList(freeList);
157     
158     void* result;
159     if (m_freeList.remaining) {
160         unsigned cellSize = m_cellSize;
161         m_freeList.remaining -= cellSize;
162         result = m_freeList.payloadEnd - m_freeList.remaining - cellSize;
163     } else {
164         FreeCell* head = m_freeList.head;
165         m_freeList.head = head->next;
166         result = head;
167     }
168     RELEASE_ASSERT(result);
169     setIsEden(NoLockingNecessary, m_currentBlock, true);
170     markedSpace().didAllocateInBlock(m_currentBlock);
171     return result;
172 }
173
174 ALWAYS_INLINE void MarkedAllocator::doTestCollectionsIfNeeded(GCDeferralContext* deferralContext)
175 {
176     if (!Options::slowPathAllocsBetweenGCs())
177         return;
178
179     static unsigned allocationCount = 0;
180     if (!allocationCount) {
181         if (!m_heap->isDeferred()) {
182             if (deferralContext)
183                 deferralContext->m_shouldGC = true;
184             else
185                 m_heap->collectAllGarbage();
186         }
187     }
188     if (++allocationCount >= Options::slowPathAllocsBetweenGCs())
189         allocationCount = 0;
190 }
191
192 void* MarkedAllocator::allocateSlowCase(GCDeferralContext* deferralContext)
193 {
194     bool crashOnFailure = true;
195     return allocateSlowCaseImpl(deferralContext, crashOnFailure);
196 }
197
198 void* MarkedAllocator::tryAllocateSlowCase(GCDeferralContext* deferralContext)
199 {
200     bool crashOnFailure = false;
201     return allocateSlowCaseImpl(deferralContext, crashOnFailure);
202 }
203
204 void* MarkedAllocator::allocateSlowCaseImpl(GCDeferralContext* deferralContext, bool crashOnFailure)
205 {
206     SuperSamplerScope superSamplerScope(false);
207     ASSERT(m_heap->vm()->currentThreadIsHoldingAPILock());
208     doTestCollectionsIfNeeded(deferralContext);
209
210     ASSERT(!markedSpace().isIterating());
211     m_heap->didAllocate(m_freeList.originalSize);
212     
213     didConsumeFreeList();
214     
215     AllocatingScope helpingHeap(*m_heap);
216
217     m_heap->collectIfNecessaryOrDefer(deferralContext);
218     
219     void* result = tryAllocateWithoutCollecting();
220     
221     if (LIKELY(result != 0))
222         return result;
223     
224     MarkedBlock::Handle* block = tryAllocateBlock();
225     if (!block) {
226         if (crashOnFailure)
227             RELEASE_ASSERT_NOT_REACHED();
228         else
229             return nullptr;
230     }
231     addBlock(block);
232     result = allocateIn(block);
233     ASSERT(result);
234     return result;
235 }
236
237 static size_t blockHeaderSize()
238 {
239     return WTF::roundUpToMultipleOf<MarkedBlock::atomSize>(sizeof(MarkedBlock));
240 }
241
242 size_t MarkedAllocator::blockSizeForBytes(size_t bytes)
243 {
244     size_t minBlockSize = MarkedBlock::blockSize;
245     size_t minAllocationSize = blockHeaderSize() + WTF::roundUpToMultipleOf<MarkedBlock::atomSize>(bytes);
246     minAllocationSize = WTF::roundUpToMultipleOf(WTF::pageSize(), minAllocationSize);
247     return std::max(minBlockSize, minAllocationSize);
248 }
249
250 MarkedBlock::Handle* MarkedAllocator::tryAllocateBlock()
251 {
252     SuperSamplerScope superSamplerScope(false);
253     
254     MarkedBlock::Handle* handle = MarkedBlock::tryCreate(*m_heap);
255     if (!handle)
256         return nullptr;
257     
258     markedSpace().didAddBlock(handle);
259     
260     return handle;
261 }
262
263 void MarkedAllocator::addBlock(MarkedBlock::Handle* block)
264 {
265     size_t index;
266     if (m_freeBlockIndices.isEmpty()) {
267         index = m_blocks.size();
268
269         size_t oldCapacity = m_blocks.capacity();
270         m_blocks.append(block);
271         if (m_blocks.capacity() != oldCapacity) {
272             forEachBitVector(
273                 NoLockingNecessary,
274                 [&] (FastBitVector& vector) {
275                     ASSERT_UNUSED(vector, vector.numBits() == oldCapacity);
276                 });
277             
278             ASSERT(m_blocks.capacity() > oldCapacity);
279             
280             LockHolder locker(m_bitvectorLock);
281             forEachBitVector(
282                 locker,
283                 [&] (FastBitVector& vector) {
284                     vector.resize(m_blocks.capacity());
285                 });
286         }
287     } else {
288         index = m_freeBlockIndices.takeLast();
289         ASSERT(!m_blocks[index]);
290         m_blocks[index] = block;
291     }
292     
293     forEachBitVector(
294         NoLockingNecessary,
295         [&] (FastBitVector& vector) {
296             ASSERT_UNUSED(vector, !vector[index]);
297         });
298
299     // This is the point at which the block learns of its cellSize() and attributes().
300     block->didAddToAllocator(this, index);
301     
302     setIsLive(NoLockingNecessary, index, true);
303     setIsEmpty(NoLockingNecessary, index, true);
304 }
305
306 void MarkedAllocator::removeBlock(MarkedBlock::Handle* block)
307 {
308     ASSERT(block->allocator() == this);
309     ASSERT(m_blocks[block->index()] == block);
310
311     m_blocks[block->index()] = nullptr;
312     m_freeBlockIndices.append(block->index());
313     
314     forEachBitVector(
315         holdLock(m_bitvectorLock),
316         [&] (FastBitVector& vector) {
317             vector[block->index()] = false;
318         });
319     
320     block->didRemoveFromAllocator();
321 }
322
323 void MarkedAllocator::stopAllocating()
324 {
325     if (false)
326         dataLog(RawPointer(this), ": MarkedAllocator::stopAllocating!\n");
327     ASSERT(!m_lastActiveBlock);
328     if (!m_currentBlock) {
329         ASSERT(!m_freeList);
330         return;
331     }
332     
333     m_currentBlock->stopAllocating(m_freeList);
334     m_lastActiveBlock = m_currentBlock;
335     m_currentBlock = 0;
336     m_freeList = FreeList();
337 }
338
339 void MarkedAllocator::prepareForAllocation()
340 {
341     m_lastActiveBlock = nullptr;
342     m_currentBlock = nullptr;
343     setFreeList(FreeList());
344
345     m_allocationCursor = 0;
346     m_emptyCursor = 0;
347     m_unsweptCursor = 0;
348     
349     m_eden.clearAll();
350
351     if (UNLIKELY(Options::useImmortalObjects())) {
352         // FIXME: Make this work again.
353         // https://bugs.webkit.org/show_bug.cgi?id=162296
354         RELEASE_ASSERT_NOT_REACHED();
355     }
356 }
357
358 void MarkedAllocator::lastChanceToFinalize()
359 {
360     forEachBlock(
361         [&] (MarkedBlock::Handle* block) {
362             block->lastChanceToFinalize();
363         });
364 }
365
366 void MarkedAllocator::setFreeList(const FreeList& freeList)
367 {
368     m_freeList = freeList;
369 }
370
371 void MarkedAllocator::resumeAllocating()
372 {
373     if (!m_lastActiveBlock)
374         return;
375
376     m_freeList = m_lastActiveBlock->resumeAllocating();
377     m_currentBlock = m_lastActiveBlock;
378     m_lastActiveBlock = nullptr;
379 }
380
381 void MarkedAllocator::beginMarkingForFullCollection()
382 {
383     // Mark bits are sticky and so is our summary of mark bits. We only clear these during full
384     // collections, so if you survived the last collection you will survive the next one so long
385     // as the next one is eden.
386     m_markingNotEmpty.clearAll();
387     m_markingRetired.clearAll();
388 }
389
390 void MarkedAllocator::endMarking()
391 {
392     m_allocated.clearAll();
393     
394     // It's surprising and frustrating to comprehend, but the end-of-marking flip does not need to
395     // know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ
396     // vectors.
397     
398     if (needsDestruction()) {
399         // If blocks need destruction then nothing is empty! This is a correct assertion but may
400         // become wrong once we go full concurrent: when we create a new block, it will flicker
401         // into the empty set for a tiny moment. On the other hand, this code is likely to be run
402         // in stopTheWorld.
403         ASSERT(m_empty.isEmpty());
404         m_canAllocateButNotEmpty = m_live & ~m_markingRetired;
405         return;
406     }
407     
408     m_empty = m_live & ~m_markingNotEmpty;
409     m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
410     
411     if (false) {
412         dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n");
413         dumpBits(WTF::dataFile());
414     }
415 }
416
417 void MarkedAllocator::snapshotUnsweptForEdenCollection()
418 {
419     m_unswept |= m_eden;
420 }
421
422 void MarkedAllocator::snapshotUnsweptForFullCollection()
423 {
424     m_unswept = m_live;
425 }
426
427 MarkedBlock::Handle* MarkedAllocator::findBlockToSweep()
428 {
429     m_unsweptCursor = m_unswept.findBit(m_unsweptCursor, true);
430     if (m_unsweptCursor >= m_blocks.size())
431         return nullptr;
432     return m_blocks[m_unsweptCursor];
433 }
434
435 void MarkedAllocator::sweep()
436 {
437     m_unswept.forEachSetBit(
438         [&] (size_t index) {
439             MarkedBlock::Handle* block = m_blocks[index];
440             block->sweep();
441         });
442 }
443
444 void MarkedAllocator::shrink()
445 {
446     m_empty.forEachSetBit(
447         [&] (size_t index) {
448             markedSpace().freeBlock(m_blocks[index]);
449         });
450 }
451
452 void MarkedAllocator::assertNoUnswept()
453 {
454     if (ASSERT_DISABLED)
455         return;
456     
457     if (m_unswept.isEmpty())
458         return;
459     
460     dataLog("Assertion failed: unswept not empty in ", *this, ".\n");
461     dumpBits();
462     ASSERT_NOT_REACHED();
463 }
464
465 void MarkedAllocator::dump(PrintStream& out) const
466 {
467     out.print(RawPointer(this), ":", m_cellSize, "/", m_attributes);
468 }
469
470 void MarkedAllocator::dumpBits(PrintStream& out)
471 {
472     unsigned maxNameLength = 0;
473     forEachBitVectorWithName(
474         NoLockingNecessary,
475         [&] (FastBitVector&, const char* name) {
476             unsigned length = strlen(name);
477             maxNameLength = std::max(maxNameLength, length);
478         });
479     
480     forEachBitVectorWithName(
481         NoLockingNecessary,
482         [&] (FastBitVector& vector, const char* name) {
483             out.print("    ", name, ": ");
484             for (unsigned i = maxNameLength - strlen(name); i--;)
485                 out.print(" ");
486             out.print(vector, "\n");
487         });
488 }
489
490 MarkedSpace& MarkedAllocator::markedSpace() const
491 {
492     return m_subspace->space();
493 }
494
495 } // namespace JSC
496