GC constraint solving should be parallel
[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 static constexpr bool tradeDestructorBlocks = true;
43
44 MarkedAllocator::MarkedAllocator(Heap* heap, size_t cellSize)
45     : m_freeList(cellSize)
46     , m_currentBlock(0)
47     , m_lastActiveBlock(0)
48     , m_cellSize(static_cast<unsigned>(cellSize))
49     , m_heap(heap)
50 {
51 }
52
53 void MarkedAllocator::setSubspace(Subspace* subspace)
54 {
55     m_attributes = subspace->attributes();
56     m_subspace = subspace;
57 }
58
59 bool MarkedAllocator::isPagedOut(double 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             double currentTime = WTF::monotonicallyIncreasingTime();
68             if (currentTime > deadline)
69                 return true;
70             itersSinceLastTimeCheck = 0;
71         }
72     }
73     return false;
74 }
75
76 MarkedBlock::Handle* MarkedAllocator::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 void MarkedAllocator::didConsumeFreeList()
85 {
86     if (m_currentBlock)
87         m_currentBlock->didConsumeFreeList();
88     
89     m_freeList.clear();
90     m_currentBlock = nullptr;
91 }
92
93 void* MarkedAllocator::tryAllocateWithoutCollecting()
94 {
95     SuperSamplerScope superSamplerScope(false);
96     
97     ASSERT(!m_currentBlock);
98     ASSERT(m_freeList.allocationWillFail());
99     
100     for (;;) {
101         m_allocationCursor = (m_canAllocateButNotEmpty | m_empty).findBit(m_allocationCursor, true);
102         if (m_allocationCursor >= m_blocks.size())
103             break;
104         
105         setIsCanAllocateButNotEmpty(NoLockingNecessary, m_allocationCursor, false);
106
107         if (void* result = tryAllocateIn(m_blocks[m_allocationCursor]))
108             return result;
109     }
110     
111     if (Options::stealEmptyBlocksFromOtherAllocators()
112         && (tradeDestructorBlocks || !needsDestruction())) {
113         if (MarkedBlock::Handle* block = m_subspace->findEmptyBlockToSteal()) {
114             RELEASE_ASSERT(block->alignedMemoryAllocator() == m_subspace->alignedMemoryAllocator());
115             
116             block->sweep(nullptr);
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     block->sweep(&m_freeList);
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 (m_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     
157     void* result = m_freeList.allocate(
158         [] () -> HeapCell* { RELEASE_ASSERT_NOT_REACHED(); return nullptr; });
159     setIsEden(NoLockingNecessary, m_currentBlock, true);
160     markedSpace().didAllocateInBlock(m_currentBlock);
161     return result;
162 }
163
164 ALWAYS_INLINE void MarkedAllocator::doTestCollectionsIfNeeded(GCDeferralContext* deferralContext)
165 {
166     if (!Options::slowPathAllocsBetweenGCs())
167         return;
168
169     static unsigned allocationCount = 0;
170     if (!allocationCount) {
171         if (!m_heap->isDeferred()) {
172             if (deferralContext)
173                 deferralContext->m_shouldGC = true;
174             else
175                 m_heap->collectNow(Sync, CollectionScope::Full);
176         }
177     }
178     if (++allocationCount >= Options::slowPathAllocsBetweenGCs())
179         allocationCount = 0;
180 }
181
182 void* MarkedAllocator::allocateSlowCase(GCDeferralContext* deferralContext, AllocationFailureMode failureMode)
183 {
184     SuperSamplerScope superSamplerScope(false);
185     ASSERT(m_heap->vm()->currentThreadIsHoldingAPILock());
186     doTestCollectionsIfNeeded(deferralContext);
187
188     ASSERT(!markedSpace().isIterating());
189     m_heap->didAllocate(m_freeList.originalSize());
190     
191     didConsumeFreeList();
192     
193     AllocatingScope helpingHeap(*m_heap);
194
195     m_heap->collectIfNecessaryOrDefer(deferralContext);
196     
197     // Goofy corner case: the GC called a callback and now this allocator has a currentBlock. This only
198     // happens when running WebKit tests, which inject a callback into the GC's finalization.
199     if (UNLIKELY(m_currentBlock))
200         return allocate(deferralContext, failureMode);
201     
202     void* result = tryAllocateWithoutCollecting();
203     
204     if (LIKELY(result != 0))
205         return result;
206     
207     MarkedBlock::Handle* block = tryAllocateBlock();
208     if (!block) {
209         if (failureMode == AllocationFailureMode::Assert)
210             RELEASE_ASSERT_NOT_REACHED();
211         else
212             return nullptr;
213     }
214     addBlock(block);
215     result = allocateIn(block);
216     ASSERT(result);
217     return result;
218 }
219
220 static size_t blockHeaderSize()
221 {
222     return WTF::roundUpToMultipleOf<MarkedBlock::atomSize>(sizeof(MarkedBlock));
223 }
224
225 size_t MarkedAllocator::blockSizeForBytes(size_t bytes)
226 {
227     size_t minBlockSize = MarkedBlock::blockSize;
228     size_t minAllocationSize = blockHeaderSize() + WTF::roundUpToMultipleOf<MarkedBlock::atomSize>(bytes);
229     minAllocationSize = WTF::roundUpToMultipleOf(WTF::pageSize(), minAllocationSize);
230     return std::max(minBlockSize, minAllocationSize);
231 }
232
233 MarkedBlock::Handle* MarkedAllocator::tryAllocateBlock()
234 {
235     SuperSamplerScope superSamplerScope(false);
236     
237     MarkedBlock::Handle* handle = MarkedBlock::tryCreate(*m_heap, subspace()->alignedMemoryAllocator());
238     if (!handle)
239         return nullptr;
240     
241     markedSpace().didAddBlock(handle);
242     
243     return handle;
244 }
245
246 void MarkedAllocator::addBlock(MarkedBlock::Handle* block)
247 {
248     size_t index;
249     if (m_freeBlockIndices.isEmpty()) {
250         index = m_blocks.size();
251
252         size_t oldCapacity = m_blocks.capacity();
253         m_blocks.append(block);
254         if (m_blocks.capacity() != oldCapacity) {
255             forEachBitVector(
256                 NoLockingNecessary,
257                 [&] (FastBitVector& vector) {
258                     ASSERT_UNUSED(vector, vector.numBits() == oldCapacity);
259                 });
260             
261             ASSERT(m_blocks.capacity() > oldCapacity);
262             
263             LockHolder locker(m_bitvectorLock);
264             forEachBitVector(
265                 locker,
266                 [&] (FastBitVector& vector) {
267                     vector.resize(m_blocks.capacity());
268                 });
269         }
270     } else {
271         index = m_freeBlockIndices.takeLast();
272         ASSERT(!m_blocks[index]);
273         m_blocks[index] = block;
274     }
275     
276     forEachBitVector(
277         NoLockingNecessary,
278         [&] (FastBitVector& vector) {
279             ASSERT_UNUSED(vector, !vector[index]);
280         });
281
282     // This is the point at which the block learns of its cellSize() and attributes().
283     block->didAddToAllocator(this, index);
284     
285     setIsLive(NoLockingNecessary, index, true);
286     setIsEmpty(NoLockingNecessary, index, true);
287 }
288
289 void MarkedAllocator::removeBlock(MarkedBlock::Handle* block)
290 {
291     ASSERT(block->allocator() == this);
292     ASSERT(m_blocks[block->index()] == block);
293
294     m_blocks[block->index()] = nullptr;
295     m_freeBlockIndices.append(block->index());
296     
297     forEachBitVector(
298         holdLock(m_bitvectorLock),
299         [&] (FastBitVector& vector) {
300             vector[block->index()] = false;
301         });
302     
303     block->didRemoveFromAllocator();
304 }
305
306 void MarkedAllocator::stopAllocating()
307 {
308     if (false)
309         dataLog(RawPointer(this), ": MarkedAllocator::stopAllocating!\n");
310     ASSERT(!m_lastActiveBlock);
311     if (!m_currentBlock) {
312         ASSERT(m_freeList.allocationWillFail());
313         return;
314     }
315     
316     m_currentBlock->stopAllocating(m_freeList);
317     m_lastActiveBlock = m_currentBlock;
318     m_currentBlock = 0;
319     m_freeList.clear();
320 }
321
322 void MarkedAllocator::prepareForAllocation()
323 {
324     m_lastActiveBlock = nullptr;
325     m_currentBlock = nullptr;
326     m_freeList.clear();
327
328     m_allocationCursor = 0;
329     m_emptyCursor = 0;
330     m_unsweptCursor = 0;
331     
332     m_eden.clearAll();
333
334     if (UNLIKELY(Options::useImmortalObjects())) {
335         // FIXME: Make this work again.
336         // https://bugs.webkit.org/show_bug.cgi?id=162296
337         RELEASE_ASSERT_NOT_REACHED();
338     }
339 }
340
341 void MarkedAllocator::lastChanceToFinalize()
342 {
343     forEachBlock(
344         [&] (MarkedBlock::Handle* block) {
345             block->lastChanceToFinalize();
346         });
347 }
348
349 void MarkedAllocator::resumeAllocating()
350 {
351     if (!m_lastActiveBlock)
352         return;
353
354     m_lastActiveBlock->resumeAllocating(m_freeList);
355     m_currentBlock = m_lastActiveBlock;
356     m_lastActiveBlock = nullptr;
357 }
358
359 void MarkedAllocator::beginMarkingForFullCollection()
360 {
361     // Mark bits are sticky and so is our summary of mark bits. We only clear these during full
362     // collections, so if you survived the last collection you will survive the next one so long
363     // as the next one is eden.
364     m_markingNotEmpty.clearAll();
365     m_markingRetired.clearAll();
366 }
367
368 void MarkedAllocator::endMarking()
369 {
370     m_allocated.clearAll();
371     
372     // It's surprising and frustrating to comprehend, but the end-of-marking flip does not need to
373     // know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ
374     // vectors.
375     
376     if (!tradeDestructorBlocks && needsDestruction()) {
377         ASSERT(m_empty.isEmpty());
378         m_canAllocateButNotEmpty = m_live & ~m_markingRetired;
379     } else {
380         m_empty = m_live & ~m_markingNotEmpty;
381         m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
382     }
383     
384     if (needsDestruction()) {
385         // There are some blocks that we didn't allocate out of in the last cycle, but we swept them. This
386         // will forget that we did that and we will end up sweeping them again and attempting to call their
387         // destructors again. That's fine because of zapping. The only time when we cannot forget is when
388         // we just allocate a block or when we move a block from one size class to another. That doesn't
389         // happen here.
390         m_destructible = m_live;
391     }
392     
393     if (false) {
394         dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n");
395         dumpBits(WTF::dataFile());
396     }
397 }
398
399 void MarkedAllocator::snapshotUnsweptForEdenCollection()
400 {
401     m_unswept |= m_eden;
402 }
403
404 void MarkedAllocator::snapshotUnsweptForFullCollection()
405 {
406     m_unswept = m_live;
407 }
408
409 MarkedBlock::Handle* MarkedAllocator::findBlockToSweep()
410 {
411     m_unsweptCursor = m_unswept.findBit(m_unsweptCursor, true);
412     if (m_unsweptCursor >= m_blocks.size())
413         return nullptr;
414     return m_blocks[m_unsweptCursor];
415 }
416
417 void MarkedAllocator::sweep()
418 {
419     m_unswept.forEachSetBit(
420         [&] (size_t index) {
421             MarkedBlock::Handle* block = m_blocks[index];
422             block->sweep(nullptr);
423         });
424 }
425
426 void MarkedAllocator::shrink()
427 {
428     (m_empty & ~m_destructible).forEachSetBit(
429         [&] (size_t index) {
430             markedSpace().freeBlock(m_blocks[index]);
431         });
432 }
433
434 void MarkedAllocator::assertNoUnswept()
435 {
436     if (ASSERT_DISABLED)
437         return;
438     
439     if (m_unswept.isEmpty())
440         return;
441     
442     dataLog("Assertion failed: unswept not empty in ", *this, ".\n");
443     dumpBits();
444     ASSERT_NOT_REACHED();
445 }
446
447 RefPtr<SharedTask<MarkedBlock::Handle*()>> MarkedAllocator::parallelNotEmptyBlockSource()
448 {
449     class Task : public SharedTask<MarkedBlock::Handle*()> {
450     public:
451         Task(MarkedAllocator& allocator)
452             : m_allocator(allocator)
453         {
454         }
455         
456         MarkedBlock::Handle* run() override
457         {
458             auto locker = holdLock(m_lock);
459             m_index = m_allocator.m_markingNotEmpty.findBit(m_index, true);
460             if (m_index >= m_allocator.m_blocks.size())
461                 return nullptr;
462             return m_allocator.m_blocks[m_index++];
463         }
464         
465     private:
466         MarkedAllocator& m_allocator;
467         size_t m_index { 0 };
468         Lock m_lock;
469     };
470     
471     return adoptRef(new Task(*this));
472 }
473
474 void MarkedAllocator::dump(PrintStream& out) const
475 {
476     out.print(RawPointer(this), ":", m_cellSize, "/", m_attributes);
477 }
478
479 void MarkedAllocator::dumpBits(PrintStream& out)
480 {
481     unsigned maxNameLength = 0;
482     forEachBitVectorWithName(
483         NoLockingNecessary,
484         [&] (FastBitVector&, const char* name) {
485             unsigned length = strlen(name);
486             maxNameLength = std::max(maxNameLength, length);
487         });
488     
489     forEachBitVectorWithName(
490         NoLockingNecessary,
491         [&] (FastBitVector& vector, const char* name) {
492             out.print("    ", name, ": ");
493             for (unsigned i = maxNameLength - strlen(name); i--;)
494                 out.print(" ");
495             out.print(vector, "\n");
496         });
497 }
498
499 MarkedSpace& MarkedAllocator::markedSpace() const
500 {
501     return m_subspace->space();
502 }
503
504 } // namespace JSC
505