GC constraint solving should be parallel
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedBlock.cpp
1 /*
2  * Copyright (C) 2011-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. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "MarkedBlock.h"
28
29 #include "AlignedMemoryAllocator.h"
30 #include "FreeListInlines.h"
31 #include "JSCell.h"
32 #include "JSDestructibleObject.h"
33 #include "JSCInlines.h"
34 #include "MarkedAllocatorInlines.h"
35 #include "MarkedBlockInlines.h"
36 #include "SuperSampler.h"
37 #include "SweepingScope.h"
38 #include <wtf/CommaPrinter.h>
39
40 namespace JSC {
41
42 const size_t MarkedBlock::blockSize;
43
44 static const bool computeBalance = false;
45 static size_t balance;
46
47 MarkedBlock::Handle* MarkedBlock::tryCreate(Heap& heap, AlignedMemoryAllocator* alignedMemoryAllocator)
48 {
49     if (computeBalance) {
50         balance++;
51         if (!(balance % 10))
52             dataLog("MarkedBlock Balance: ", balance, "\n");
53     }
54     void* blockSpace = alignedMemoryAllocator->tryAllocateAlignedMemory(blockSize, blockSize);
55     if (!blockSpace)
56         return nullptr;
57     if (scribbleFreeCells())
58         scribble(blockSpace, blockSize);
59     return new Handle(heap, alignedMemoryAllocator, blockSpace);
60 }
61
62 MarkedBlock::Handle::Handle(Heap& heap, AlignedMemoryAllocator* alignedMemoryAllocator, void* blockSpace)
63     : m_alignedMemoryAllocator(alignedMemoryAllocator)
64     , m_weakSet(heap.vm(), CellContainer())
65     , m_newlyAllocatedVersion(MarkedSpace::nullVersion)
66 {
67     m_block = new (NotNull, blockSpace) MarkedBlock(*heap.vm(), *this);
68     
69     m_weakSet.setContainer(*m_block);
70     
71     heap.didAllocateBlock(blockSize);
72 }
73
74 MarkedBlock::Handle::~Handle()
75 {
76     Heap& heap = *this->heap();
77     if (computeBalance) {
78         balance--;
79         if (!(balance % 10))
80             dataLog("MarkedBlock Balance: ", balance, "\n");
81     }
82     removeFromAllocator();
83     m_block->~MarkedBlock();
84     m_alignedMemoryAllocator->freeAlignedMemory(m_block);
85     heap.didFreeBlock(blockSize);
86 }
87
88 MarkedBlock::MarkedBlock(VM& vm, Handle& handle)
89     : m_handle(handle)
90     , m_vm(&vm)
91     , m_markingVersion(MarkedSpace::nullVersion)
92 {
93     if (false)
94         dataLog(RawPointer(this), ": Allocated.\n");
95 }
96
97 void MarkedBlock::Handle::unsweepWithNoNewlyAllocated()
98 {
99     RELEASE_ASSERT(m_isFreeListed);
100     m_isFreeListed = false;
101 }
102
103 void MarkedBlock::Handle::setIsFreeListed()
104 {
105     m_allocator->setIsEmpty(NoLockingNecessary, this, false);
106     m_isFreeListed = true;
107 }
108
109 void MarkedBlock::Handle::stopAllocating(const FreeList& freeList)
110 {
111     auto locker = holdLock(block().m_lock);
112     
113     if (false)
114         dataLog(RawPointer(this), ": MarkedBlock::Handle::stopAllocating!\n");
115     ASSERT(!allocator()->isAllocated(NoLockingNecessary, this));
116
117     if (!isFreeListed()) {
118         if (false)
119             dataLog("There ain't no newly allocated.\n");
120         // This means that we either didn't use this block at all for allocation since last GC,
121         // or someone had already done stopAllocating() before.
122         ASSERT(freeList.allocationWillFail());
123         return;
124     }
125     
126     if (false)
127         dataLog("Free list: ", freeList, "\n");
128     
129     // Roll back to a coherent state for Heap introspection. Cells newly
130     // allocated from our free list are not currently marked, so we need another
131     // way to tell what's live vs dead. 
132     
133     m_newlyAllocated.clearAll();
134     m_newlyAllocatedVersion = heap()->objectSpace().newlyAllocatedVersion();
135
136     forEachCell(
137         [&] (HeapCell* cell, HeapCell::Kind) -> IterationStatus {
138             setNewlyAllocated(cell);
139             return IterationStatus::Continue;
140         });
141
142     freeList.forEach(
143         [&] (HeapCell* cell) {
144             if (false)
145                 dataLog("Free cell: ", RawPointer(cell), "\n");
146             if (m_attributes.destruction == NeedsDestruction)
147                 cell->zap();
148             clearNewlyAllocated(cell);
149         });
150     
151     m_isFreeListed = false;
152 }
153
154 void MarkedBlock::Handle::lastChanceToFinalize()
155 {
156     allocator()->setIsAllocated(NoLockingNecessary, this, false);
157     allocator()->setIsDestructible(NoLockingNecessary, this, true);
158     m_block->m_marks.clearAll();
159     m_block->clearHasAnyMarked();
160     m_block->m_markingVersion = heap()->objectSpace().markingVersion();
161     m_weakSet.lastChanceToFinalize();
162     m_newlyAllocated.clearAll();
163     m_newlyAllocatedVersion = heap()->objectSpace().newlyAllocatedVersion();
164     sweep(nullptr);
165 }
166
167 void MarkedBlock::Handle::resumeAllocating(FreeList& freeList)
168 {
169     {
170         auto locker = holdLock(block().m_lock);
171         
172         if (false)
173             dataLog(RawPointer(this), ": MarkedBlock::Handle::resumeAllocating!\n");
174         ASSERT(!allocator()->isAllocated(NoLockingNecessary, this));
175         ASSERT(!isFreeListed());
176         
177         if (!hasAnyNewlyAllocated()) {
178             if (false)
179                 dataLog("There ain't no newly allocated.\n");
180             // This means we had already exhausted the block when we stopped allocation.
181             freeList.clear();
182             return;
183         }
184     }
185
186     // Re-create our free list from before stopping allocation. Note that this may return an empty
187     // freelist, in which case the block will still be Marked!
188     sweep(&freeList);
189 }
190
191 void MarkedBlock::Handle::zap(const FreeList& freeList)
192 {
193     freeList.forEach(
194         [&] (HeapCell* cell) {
195             if (m_attributes.destruction == NeedsDestruction)
196                 cell->zap();
197         });
198 }
199
200 void MarkedBlock::aboutToMarkSlow(HeapVersion markingVersion)
201 {
202     ASSERT(vm()->heap.objectSpace().isMarking());
203     auto locker = holdLock(m_lock);
204     
205     if (!areMarksStale(markingVersion))
206         return;
207     
208     MarkedAllocator* allocator = handle().allocator();
209
210     if (handle().allocator()->isAllocated(holdLock(allocator->bitvectorLock()), &handle())
211         || !marksConveyLivenessDuringMarking(markingVersion)) {
212         if (false)
213             dataLog(RawPointer(this), ": Clearing marks without doing anything else.\n");
214         // We already know that the block is full and is already recognized as such, or that the
215         // block did not survive the previous GC. So, we can clear mark bits the old fashioned
216         // way. Note that it's possible for such a block to have newlyAllocated with an up-to-
217         // date version! If it does, then we want to leave the newlyAllocated alone, since that
218         // means that we had allocated in this previously empty block but did not fill it up, so
219         // we created a newlyAllocated.
220         m_marks.clearAll();
221     } else {
222         if (false)
223             dataLog(RawPointer(this), ": Doing things.\n");
224         HeapVersion newlyAllocatedVersion = space()->newlyAllocatedVersion();
225         if (handle().m_newlyAllocatedVersion == newlyAllocatedVersion) {
226             // When do we get here? The block could not have been filled up. The newlyAllocated bits would
227             // have had to be created since the end of the last collection. The only things that create
228             // them are aboutToMarkSlow, lastChanceToFinalize, and stopAllocating. If it had been
229             // aboutToMarkSlow, then we shouldn't be here since the marks wouldn't be stale anymore. It
230             // cannot be lastChanceToFinalize. So it must be stopAllocating. That means that we just
231             // computed the newlyAllocated bits just before the start of an increment. When we are in that
232             // mode, it seems as if newlyAllocated should subsume marks.
233             ASSERT(handle().m_newlyAllocated.subsumes(m_marks));
234             m_marks.clearAll();
235         } else {
236             handle().m_newlyAllocated.setAndClear(m_marks);
237             handle().m_newlyAllocatedVersion = newlyAllocatedVersion;
238         }
239     }
240     clearHasAnyMarked();
241     WTF::storeStoreFence();
242     m_markingVersion = markingVersion;
243     
244     // This means we're the first ones to mark any object in this block.
245     allocator->setIsMarkingNotEmpty(holdLock(allocator->bitvectorLock()), &handle(), true);
246 }
247
248 void MarkedBlock::Handle::resetAllocated()
249 {
250     m_newlyAllocated.clearAll();
251     m_newlyAllocatedVersion = MarkedSpace::nullVersion;
252 }
253
254 void MarkedBlock::resetMarks()
255 {
256     // We want aboutToMarkSlow() to see what the mark bits were after the last collection. It uses
257     // the version number to distinguish between the marks having already been stale before
258     // beginMarking(), or just stale now that beginMarking() bumped the version. If we have a version
259     // wraparound, then we will call this method before resetting the version to null. When the
260     // version is null, aboutToMarkSlow() will assume that the marks were not stale as of before
261     // beginMarking(). Hence the need to whip the marks into shape.
262     if (areMarksStale())
263         m_marks.clearAll();
264     m_markingVersion = MarkedSpace::nullVersion;
265 }
266
267 #if !ASSERT_DISABLED
268 void MarkedBlock::assertMarksNotStale()
269 {
270     ASSERT(m_markingVersion == vm()->heap.objectSpace().markingVersion());
271 }
272 #endif // !ASSERT_DISABLED
273
274 bool MarkedBlock::areMarksStale()
275 {
276     return areMarksStale(vm()->heap.objectSpace().markingVersion());
277 }
278
279 bool MarkedBlock::Handle::areMarksStale()
280 {
281     return m_block->areMarksStale();
282 }
283
284 bool MarkedBlock::isMarked(const void* p)
285 {
286     return isMarked(vm()->heap.objectSpace().markingVersion(), p);
287 }
288
289 void MarkedBlock::Handle::didConsumeFreeList()
290 {
291     auto locker = holdLock(block().m_lock);
292     if (false)
293         dataLog(RawPointer(this), ": MarkedBlock::Handle::didConsumeFreeList!\n");
294     ASSERT(isFreeListed());
295     m_isFreeListed = false;
296     allocator()->setIsAllocated(NoLockingNecessary, this, true);
297 }
298
299 size_t MarkedBlock::markCount()
300 {
301     return areMarksStale() ? 0 : m_marks.count();
302 }
303
304 bool MarkedBlock::Handle::isEmpty()
305 {
306     return m_allocator->isEmpty(NoLockingNecessary, this);
307 }
308
309 void MarkedBlock::clearHasAnyMarked()
310 {
311     m_biasedMarkCount = m_markCountBias;
312 }
313
314 void MarkedBlock::noteMarkedSlow()
315 {
316     MarkedAllocator* allocator = handle().allocator();
317     allocator->setIsMarkingRetired(holdLock(allocator->bitvectorLock()), &handle(), true);
318 }
319
320 void MarkedBlock::Handle::removeFromAllocator()
321 {
322     if (!m_allocator)
323         return;
324     
325     m_allocator->removeBlock(this);
326 }
327
328 void MarkedBlock::Handle::didAddToAllocator(MarkedAllocator* allocator, size_t index)
329 {
330     ASSERT(m_index == std::numeric_limits<size_t>::max());
331     ASSERT(!m_allocator);
332     
333     RELEASE_ASSERT(allocator->subspace()->alignedMemoryAllocator() == m_alignedMemoryAllocator);
334     
335     m_index = index;
336     m_allocator = allocator;
337     
338     size_t cellSize = allocator->cellSize();
339     m_atomsPerCell = (cellSize + atomSize - 1) / atomSize;
340     m_endAtom = atomsPerBlock - m_atomsPerCell + 1;
341     
342     m_attributes = allocator->attributes();
343
344     if (m_attributes.cellKind != HeapCell::JSCell)
345         RELEASE_ASSERT(m_attributes.destruction == DoesNotNeedDestruction);
346     
347     double markCountBias = -(Options::minMarkedBlockUtilization() * cellsPerBlock());
348     
349     // The mark count bias should be comfortably within this range.
350     RELEASE_ASSERT(markCountBias > static_cast<double>(std::numeric_limits<int16_t>::min()));
351     RELEASE_ASSERT(markCountBias < 0);
352     
353     // This means we haven't marked anything yet.
354     block().m_biasedMarkCount = block().m_markCountBias = static_cast<int16_t>(markCountBias);
355 }
356
357 void MarkedBlock::Handle::didRemoveFromAllocator()
358 {
359     ASSERT(m_index != std::numeric_limits<size_t>::max());
360     ASSERT(m_allocator);
361     
362     m_index = std::numeric_limits<size_t>::max();
363     m_allocator = nullptr;
364 }
365
366 #if !ASSERT_DISABLED
367 void MarkedBlock::assertValidCell(VM& vm, HeapCell* cell) const
368 {
369     RELEASE_ASSERT(&vm == this->vm());
370     RELEASE_ASSERT(const_cast<MarkedBlock*>(this)->handle().cellAlign(cell) == cell);
371 }
372 #endif
373
374 void MarkedBlock::Handle::dumpState(PrintStream& out)
375 {
376     CommaPrinter comma;
377     allocator()->forEachBitVectorWithName(
378         holdLock(allocator()->bitvectorLock()),
379         [&] (FastBitVector& bitvector, const char* name) {
380             out.print(comma, name, ":", bitvector[index()] ? "YES" : "no");
381         });
382 }
383
384 Subspace* MarkedBlock::Handle::subspace() const
385 {
386     return allocator()->subspace();
387 }
388
389 void MarkedBlock::Handle::sweep(FreeList* freeList)
390 {
391     SweepingScope sweepingScope(*heap());
392     
393     SweepMode sweepMode = freeList ? SweepToFreeList : SweepOnly;
394     
395     m_allocator->setIsUnswept(NoLockingNecessary, this, false);
396     
397     m_weakSet.sweep();
398     
399     bool needsDestruction = m_attributes.destruction == NeedsDestruction
400         && m_allocator->isDestructible(NoLockingNecessary, this);
401
402     if (sweepMode == SweepOnly && !needsDestruction)
403         return;
404
405     if (UNLIKELY(m_isFreeListed)) {
406         RELEASE_ASSERT(sweepMode == SweepToFreeList);
407         return;
408     }
409     
410     ASSERT(!m_allocator->isAllocated(NoLockingNecessary, this));
411     
412     if (space()->isMarking())
413         block().m_lock.lock();
414     
415     if (needsDestruction) {
416         subspace()->finishSweep(*this, freeList);
417         return;
418     }
419     
420     // Handle the no-destructor specializations here, since we have the most of those. This
421     // ensures that they don't get re-specialized for every destructor space.
422     
423     EmptyMode emptyMode = this->emptyMode();
424     ScribbleMode scribbleMode = this->scribbleMode();
425     NewlyAllocatedMode newlyAllocatedMode = this->newlyAllocatedMode();
426     MarksMode marksMode = this->marksMode();
427     
428     auto trySpecialized = [&] () -> bool {
429         if (sweepMode != SweepToFreeList)
430             return false;
431         if (scribbleMode != DontScribble)
432             return false;
433         if (newlyAllocatedMode != DoesNotHaveNewlyAllocated)
434             return false;
435         
436         switch (emptyMode) {
437         case IsEmpty:
438             switch (marksMode) {
439             case MarksNotStale:
440                 specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, [] (VM&, JSCell*) { });
441                 return true;
442             case MarksStale:
443                 specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, [] (VM&, JSCell*) { });
444                 return true;
445             }
446             break;
447         case NotEmpty:
448             switch (marksMode) {
449             case MarksNotStale:
450                 specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, [] (VM&, JSCell*) { });
451                 return true;
452             case MarksStale:
453                 specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, [] (VM&, JSCell*) { });
454                 return true;
455             }
456             break;
457         }
458         
459         return false;
460     };
461     
462     if (trySpecialized())
463         return;
464
465     // The template arguments don't matter because the first one is false.
466     specializedSweep<false, IsEmpty, SweepOnly, BlockHasNoDestructors, DontScribble, HasNewlyAllocated, MarksStale>(freeList, emptyMode, sweepMode, BlockHasNoDestructors, scribbleMode, newlyAllocatedMode, marksMode, [] (VM&, JSCell*) { });
467 }
468
469 bool MarkedBlock::Handle::isFreeListedCell(const void* target) const
470 {
471     ASSERT(isFreeListed());
472     return m_allocator->isFreeListedCell(target);
473 }
474
475 } // namespace JSC
476
477 namespace WTF {
478
479 void printInternal(PrintStream& out, JSC::MarkedBlock::Handle::SweepMode mode)
480 {
481     switch (mode) {
482     case JSC::MarkedBlock::Handle::SweepToFreeList:
483         out.print("SweepToFreeList");
484         return;
485     case JSC::MarkedBlock::Handle::SweepOnly:
486         out.print("SweepOnly");
487         return;
488     }
489     RELEASE_ASSERT_NOT_REACHED();
490 }
491
492 } // namespace WTF
493