CodeBlocks should be in IsoSubspaces
[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             subspace()->didResizeBits(m_blocks.capacity());
265             forEachBitVector(
266                 locker,
267                 [&] (FastBitVector& vector) {
268                     vector.resize(m_blocks.capacity());
269                 });
270         }
271     } else {
272         index = m_freeBlockIndices.takeLast();
273         ASSERT(!m_blocks[index]);
274         m_blocks[index] = block;
275     }
276     
277     forEachBitVector(
278         NoLockingNecessary,
279         [&] (FastBitVector& vector) {
280             ASSERT_UNUSED(vector, !vector[index]);
281         });
282
283     // This is the point at which the block learns of its cellSize() and attributes().
284     block->didAddToAllocator(this, index);
285     
286     setIsLive(NoLockingNecessary, index, true);
287     setIsEmpty(NoLockingNecessary, index, true);
288 }
289
290 void MarkedAllocator::removeBlock(MarkedBlock::Handle* block)
291 {
292     ASSERT(block->allocator() == this);
293     ASSERT(m_blocks[block->index()] == block);
294     
295     subspace()->didRemoveBlock(block->index());
296     
297     m_blocks[block->index()] = nullptr;
298     m_freeBlockIndices.append(block->index());
299     
300     forEachBitVector(
301         holdLock(m_bitvectorLock),
302         [&] (FastBitVector& vector) {
303             vector[block->index()] = false;
304         });
305     
306     block->didRemoveFromAllocator();
307 }
308
309 void MarkedAllocator::stopAllocating()
310 {
311     if (false)
312         dataLog(RawPointer(this), ": MarkedAllocator::stopAllocating!\n");
313     ASSERT(!m_lastActiveBlock);
314     if (!m_currentBlock) {
315         ASSERT(m_freeList.allocationWillFail());
316         return;
317     }
318     
319     m_currentBlock->stopAllocating(m_freeList);
320     m_lastActiveBlock = m_currentBlock;
321     m_currentBlock = 0;
322     m_freeList.clear();
323 }
324
325 void MarkedAllocator::prepareForAllocation()
326 {
327     m_lastActiveBlock = nullptr;
328     m_currentBlock = nullptr;
329     m_freeList.clear();
330
331     m_allocationCursor = 0;
332     m_emptyCursor = 0;
333     m_unsweptCursor = 0;
334     
335     m_eden.clearAll();
336
337     if (UNLIKELY(Options::useImmortalObjects())) {
338         // FIXME: Make this work again.
339         // https://bugs.webkit.org/show_bug.cgi?id=162296
340         RELEASE_ASSERT_NOT_REACHED();
341     }
342 }
343
344 void MarkedAllocator::lastChanceToFinalize()
345 {
346     forEachBlock(
347         [&] (MarkedBlock::Handle* block) {
348             block->lastChanceToFinalize();
349         });
350 }
351
352 void MarkedAllocator::resumeAllocating()
353 {
354     if (!m_lastActiveBlock)
355         return;
356
357     m_lastActiveBlock->resumeAllocating(m_freeList);
358     m_currentBlock = m_lastActiveBlock;
359     m_lastActiveBlock = nullptr;
360 }
361
362 void MarkedAllocator::beginMarkingForFullCollection()
363 {
364     // Mark bits are sticky and so is our summary of mark bits. We only clear these during full
365     // collections, so if you survived the last collection you will survive the next one so long
366     // as the next one is eden.
367     m_markingNotEmpty.clearAll();
368     m_markingRetired.clearAll();
369 }
370
371 void MarkedAllocator::endMarking()
372 {
373     m_allocated.clearAll();
374     
375     // It's surprising and frustrating to comprehend, but the end-of-marking flip does not need to
376     // know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ
377     // vectors.
378     
379     if (!tradeDestructorBlocks && needsDestruction()) {
380         ASSERT(m_empty.isEmpty());
381         m_canAllocateButNotEmpty = m_live & ~m_markingRetired;
382     } else {
383         m_empty = m_live & ~m_markingNotEmpty;
384         m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
385     }
386     
387     if (needsDestruction()) {
388         // There are some blocks that we didn't allocate out of in the last cycle, but we swept them. This
389         // will forget that we did that and we will end up sweeping them again and attempting to call their
390         // destructors again. That's fine because of zapping. The only time when we cannot forget is when
391         // we just allocate a block or when we move a block from one size class to another. That doesn't
392         // happen here.
393         m_destructible = m_live;
394     }
395     
396     if (false) {
397         dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n");
398         dumpBits(WTF::dataFile());
399     }
400 }
401
402 void MarkedAllocator::snapshotUnsweptForEdenCollection()
403 {
404     m_unswept |= m_eden;
405 }
406
407 void MarkedAllocator::snapshotUnsweptForFullCollection()
408 {
409     m_unswept = m_live;
410 }
411
412 MarkedBlock::Handle* MarkedAllocator::findBlockToSweep()
413 {
414     m_unsweptCursor = m_unswept.findBit(m_unsweptCursor, true);
415     if (m_unsweptCursor >= m_blocks.size())
416         return nullptr;
417     return m_blocks[m_unsweptCursor];
418 }
419
420 void MarkedAllocator::sweep()
421 {
422     m_unswept.forEachSetBit(
423         [&] (size_t index) {
424             MarkedBlock::Handle* block = m_blocks[index];
425             block->sweep(nullptr);
426         });
427 }
428
429 void MarkedAllocator::shrink()
430 {
431     (m_empty & ~m_destructible).forEachSetBit(
432         [&] (size_t index) {
433             markedSpace().freeBlock(m_blocks[index]);
434         });
435 }
436
437 void MarkedAllocator::assertNoUnswept()
438 {
439     if (ASSERT_DISABLED)
440         return;
441     
442     if (m_unswept.isEmpty())
443         return;
444     
445     dataLog("Assertion failed: unswept not empty in ", *this, ".\n");
446     dumpBits();
447     ASSERT_NOT_REACHED();
448 }
449
450 RefPtr<SharedTask<MarkedBlock::Handle*()>> MarkedAllocator::parallelNotEmptyBlockSource()
451 {
452     class Task : public SharedTask<MarkedBlock::Handle*()> {
453     public:
454         Task(MarkedAllocator& allocator)
455             : m_allocator(allocator)
456         {
457         }
458         
459         MarkedBlock::Handle* run() override
460         {
461             if (m_done)
462                 return nullptr;
463             auto locker = holdLock(m_lock);
464             m_index = m_allocator.m_markingNotEmpty.findBit(m_index, true);
465             if (m_index >= m_allocator.m_blocks.size()) {
466                 m_done = true;
467                 return nullptr;
468             }
469             return m_allocator.m_blocks[m_index++];
470         }
471         
472     private:
473         MarkedAllocator& m_allocator;
474         size_t m_index { 0 };
475         Lock m_lock;
476         bool m_done { false };
477     };
478     
479     return adoptRef(new Task(*this));
480 }
481
482 void MarkedAllocator::dump(PrintStream& out) const
483 {
484     out.print(RawPointer(this), ":", m_cellSize, "/", m_attributes);
485 }
486
487 void MarkedAllocator::dumpBits(PrintStream& out)
488 {
489     unsigned maxNameLength = 0;
490     forEachBitVectorWithName(
491         NoLockingNecessary,
492         [&] (FastBitVector&, const char* name) {
493             unsigned length = strlen(name);
494             maxNameLength = std::max(maxNameLength, length);
495         });
496     
497     forEachBitVectorWithName(
498         NoLockingNecessary,
499         [&] (FastBitVector& vector, const char* name) {
500             out.print("    ", name, ": ");
501             for (unsigned i = maxNameLength - strlen(name); i--;)
502                 out.print(" ");
503             out.print(vector, "\n");
504         });
505 }
506
507 MarkedSpace& MarkedAllocator::markedSpace() const
508 {
509     return m_subspace->space();
510 }
511
512 } // namespace JSC
513