ab215e089b0dfb684abd47bede6506d4a95271ea
[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 void MarkedBlock::clearHasAnyMarked()
305 {
306     m_biasedMarkCount = m_markCountBias;
307 }
308
309 void MarkedBlock::noteMarkedSlow()
310 {
311     MarkedAllocator* allocator = handle().allocator();
312     allocator->setIsMarkingRetired(holdLock(allocator->bitvectorLock()), &handle(), true);
313 }
314
315 void MarkedBlock::Handle::removeFromAllocator()
316 {
317     if (!m_allocator)
318         return;
319     
320     m_allocator->removeBlock(this);
321 }
322
323 void MarkedBlock::Handle::didAddToAllocator(MarkedAllocator* allocator, size_t index)
324 {
325     ASSERT(m_index == std::numeric_limits<size_t>::max());
326     ASSERT(!m_allocator);
327     
328     RELEASE_ASSERT(allocator->subspace()->alignedMemoryAllocator() == m_alignedMemoryAllocator);
329     
330     m_index = index;
331     m_allocator = allocator;
332     
333     size_t cellSize = allocator->cellSize();
334     m_atomsPerCell = (cellSize + atomSize - 1) / atomSize;
335     m_endAtom = atomsPerBlock - m_atomsPerCell + 1;
336     
337     m_attributes = allocator->attributes();
338
339     if (m_attributes.cellKind != HeapCell::JSCell)
340         RELEASE_ASSERT(m_attributes.destruction == DoesNotNeedDestruction);
341     
342     double markCountBias = -(Options::minMarkedBlockUtilization() * cellsPerBlock());
343     
344     // The mark count bias should be comfortably within this range.
345     RELEASE_ASSERT(markCountBias > static_cast<double>(std::numeric_limits<int16_t>::min()));
346     RELEASE_ASSERT(markCountBias < 0);
347     
348     // This means we haven't marked anything yet.
349     block().m_biasedMarkCount = block().m_markCountBias = static_cast<int16_t>(markCountBias);
350 }
351
352 void MarkedBlock::Handle::didRemoveFromAllocator()
353 {
354     ASSERT(m_index != std::numeric_limits<size_t>::max());
355     ASSERT(m_allocator);
356     
357     m_index = std::numeric_limits<size_t>::max();
358     m_allocator = nullptr;
359 }
360
361 #if !ASSERT_DISABLED
362 void MarkedBlock::assertValidCell(VM& vm, HeapCell* cell) const
363 {
364     RELEASE_ASSERT(&vm == this->vm());
365     RELEASE_ASSERT(const_cast<MarkedBlock*>(this)->handle().cellAlign(cell) == cell);
366 }
367 #endif
368
369 void MarkedBlock::Handle::dumpState(PrintStream& out)
370 {
371     CommaPrinter comma;
372     allocator()->forEachBitVectorWithName(
373         holdLock(allocator()->bitvectorLock()),
374         [&] (FastBitVector& bitvector, const char* name) {
375             out.print(comma, name, ":", bitvector[index()] ? "YES" : "no");
376         });
377 }
378
379 Subspace* MarkedBlock::Handle::subspace() const
380 {
381     return allocator()->subspace();
382 }
383
384 void MarkedBlock::Handle::sweep(FreeList* freeList)
385 {
386     SweepingScope sweepingScope(*heap());
387     
388     SweepMode sweepMode = freeList ? SweepToFreeList : SweepOnly;
389     
390     m_allocator->setIsUnswept(NoLockingNecessary, this, false);
391     
392     m_weakSet.sweep();
393     
394     bool needsDestruction = m_attributes.destruction == NeedsDestruction
395         && m_allocator->isDestructible(NoLockingNecessary, this);
396
397     if (sweepMode == SweepOnly && !needsDestruction)
398         return;
399
400     RELEASE_ASSERT(!m_isFreeListed);
401     RELEASE_ASSERT(!isAllocated());
402     
403     if (space()->isMarking())
404         block().m_lock.lock();
405     
406     subspace()->didBeginSweepingToFreeList(this);
407     
408     if (needsDestruction) {
409         subspace()->finishSweep(*this, freeList);
410         return;
411     }
412     
413     // Handle the no-destructor specializations here, since we have the most of those. This
414     // ensures that they don't get re-specialized for every destructor space.
415     
416     EmptyMode emptyMode = this->emptyMode();
417     ScribbleMode scribbleMode = this->scribbleMode();
418     NewlyAllocatedMode newlyAllocatedMode = this->newlyAllocatedMode();
419     MarksMode marksMode = this->marksMode();
420     
421     auto trySpecialized = [&] () -> bool {
422         if (sweepMode != SweepToFreeList)
423             return false;
424         if (scribbleMode != DontScribble)
425             return false;
426         if (newlyAllocatedMode != DoesNotHaveNewlyAllocated)
427             return false;
428         
429         switch (emptyMode) {
430         case IsEmpty:
431             switch (marksMode) {
432             case MarksNotStale:
433                 specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, [] (VM&, JSCell*) { });
434                 return true;
435             case MarksStale:
436                 specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, [] (VM&, JSCell*) { });
437                 return true;
438             }
439             break;
440         case NotEmpty:
441             switch (marksMode) {
442             case MarksNotStale:
443                 specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, [] (VM&, JSCell*) { });
444                 return true;
445             case MarksStale:
446                 specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, [] (VM&, JSCell*) { });
447                 return true;
448             }
449             break;
450         }
451         
452         return false;
453     };
454     
455     if (trySpecialized())
456         return;
457
458     // The template arguments don't matter because the first one is false.
459     specializedSweep<false, IsEmpty, SweepOnly, BlockHasNoDestructors, DontScribble, HasNewlyAllocated, MarksStale>(freeList, emptyMode, sweepMode, BlockHasNoDestructors, scribbleMode, newlyAllocatedMode, marksMode, [] (VM&, JSCell*) { });
460 }
461
462 bool MarkedBlock::Handle::isFreeListedCell(const void* target) const
463 {
464     ASSERT(isFreeListed());
465     return m_allocator->isFreeListedCell(target);
466 }
467
468 } // namespace JSC
469
470 namespace WTF {
471
472 void printInternal(PrintStream& out, JSC::MarkedBlock::Handle::SweepMode mode)
473 {
474     switch (mode) {
475     case JSC::MarkedBlock::Handle::SweepToFreeList:
476         out.print("SweepToFreeList");
477         return;
478     case JSC::MarkedBlock::Handle::SweepOnly:
479         out.print("SweepOnly");
480         return;
481     }
482     RELEASE_ASSERT_NOT_REACHED();
483 }
484
485 } // namespace WTF
486