a7c85938e8529c80af31f2fd8519c6c3fc74138c
[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 "FreeListInlines.h"
30 #include "JSCell.h"
31 #include "JSDestructibleObject.h"
32 #include "JSCInlines.h"
33 #include "MarkedAllocatorInlines.h"
34 #include "MarkedBlockInlines.h"
35 #include "SuperSampler.h"
36 #include "SweepingScope.h"
37 #include <wtf/CommaPrinter.h>
38
39 namespace JSC {
40
41 const size_t MarkedBlock::blockSize;
42
43 static const bool computeBalance = false;
44 static size_t balance;
45
46 MarkedBlock::Handle* MarkedBlock::tryCreate(Heap& heap, Subspace* subspace)
47 {
48     if (computeBalance) {
49         balance++;
50         if (!(balance % 10))
51             dataLog("MarkedBlock Balance: ", balance, "\n");
52     }
53     void* blockSpace = subspace->tryAllocateAlignedMemory(blockSize, blockSize);
54     if (!blockSpace)
55         return nullptr;
56     if (scribbleFreeCells())
57         scribble(blockSpace, blockSize);
58     return new Handle(heap, subspace, blockSpace);
59 }
60
61 MarkedBlock::Handle::Handle(Heap& heap, Subspace* subspace, void* blockSpace)
62     : m_subspace(subspace)
63     , m_weakSet(heap.vm(), CellContainer())
64     , m_newlyAllocatedVersion(MarkedSpace::nullVersion)
65 {
66     m_block = new (NotNull, blockSpace) MarkedBlock(*heap.vm(), *this);
67     
68     m_weakSet.setContainer(*m_block);
69     
70     heap.didAllocateBlock(blockSize);
71 }
72
73 MarkedBlock::Handle::~Handle()
74 {
75     Heap& heap = *this->heap();
76     Subspace* subspace = this->subspace();
77     if (computeBalance) {
78         balance--;
79         if (!(balance % 10))
80             dataLog("MarkedBlock Balance: ", balance, "\n");
81     }
82     removeFromAllocator();
83     m_block->~MarkedBlock();
84     subspace->freeAlignedMemory(m_block);
85     heap.didFreeBlock(blockSize);
86 }
87
88 MarkedBlock::MarkedBlock(VM& vm, Handle& handle)
89     : m_markingVersion(MarkedSpace::nullVersion)
90     , m_handle(handle)
91     , m_vm(&vm)
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     LockHolder locker(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             // Merge the contents of marked into newlyAllocated. If we get the full set of bits
227             // then invalidate newlyAllocated and set allocated.
228             handle().m_newlyAllocated.mergeAndClear(m_marks);
229         } else {
230             // Replace the contents of newlyAllocated with marked. If we get the full set of
231             // bits then invalidate newlyAllocated and set allocated.
232             handle().m_newlyAllocated.setAndClear(m_marks);
233         }
234         handle().m_newlyAllocatedVersion = newlyAllocatedVersion;
235     }
236     clearHasAnyMarked();
237     WTF::storeStoreFence();
238     m_markingVersion = markingVersion;
239     
240     // This means we're the first ones to mark any object in this block.
241     allocator->setIsMarkingNotEmpty(holdLock(allocator->bitvectorLock()), &handle(), true);
242 }
243
244 void MarkedBlock::Handle::resetAllocated()
245 {
246     m_newlyAllocated.clearAll();
247     m_newlyAllocatedVersion = MarkedSpace::nullVersion;
248 }
249
250 void MarkedBlock::resetMarks()
251 {
252     // We want aboutToMarkSlow() to see what the mark bits were after the last collection. It uses
253     // the version number to distinguish between the marks having already been stale before
254     // beginMarking(), or just stale now that beginMarking() bumped the version. If we have a version
255     // wraparound, then we will call this method before resetting the version to null. When the
256     // version is null, aboutToMarkSlow() will assume that the marks were not stale as of before
257     // beginMarking(). Hence the need to whip the marks into shape.
258     if (areMarksStale())
259         m_marks.clearAll();
260     m_markingVersion = MarkedSpace::nullVersion;
261 }
262
263 #if !ASSERT_DISABLED
264 void MarkedBlock::assertMarksNotStale()
265 {
266     ASSERT(m_markingVersion == vm()->heap.objectSpace().markingVersion());
267 }
268 #endif // !ASSERT_DISABLED
269
270 bool MarkedBlock::areMarksStale()
271 {
272     return areMarksStale(vm()->heap.objectSpace().markingVersion());
273 }
274
275 bool MarkedBlock::Handle::areMarksStale()
276 {
277     return m_block->areMarksStale();
278 }
279
280 bool MarkedBlock::isMarked(const void* p)
281 {
282     return isMarked(vm()->heap.objectSpace().markingVersion(), p);
283 }
284
285 void MarkedBlock::Handle::didConsumeFreeList()
286 {
287     auto locker = holdLock(block().m_lock);
288     if (false)
289         dataLog(RawPointer(this), ": MarkedBlock::Handle::didConsumeFreeList!\n");
290     ASSERT(isFreeListed());
291     m_isFreeListed = false;
292     allocator()->setIsAllocated(NoLockingNecessary, this, true);
293 }
294
295 size_t MarkedBlock::markCount()
296 {
297     return areMarksStale() ? 0 : m_marks.count();
298 }
299
300 bool MarkedBlock::Handle::isEmpty()
301 {
302     return m_allocator->isEmpty(NoLockingNecessary, this);
303 }
304
305 void MarkedBlock::clearHasAnyMarked()
306 {
307     m_biasedMarkCount = m_markCountBias;
308 }
309
310 void MarkedBlock::noteMarkedSlow()
311 {
312     MarkedAllocator* allocator = handle().allocator();
313     allocator->setIsMarkingRetired(holdLock(allocator->bitvectorLock()), &handle(), true);
314 }
315
316 void MarkedBlock::Handle::removeFromAllocator()
317 {
318     if (!m_allocator)
319         return;
320     
321     m_allocator->removeBlock(this);
322 }
323
324 void MarkedBlock::updateNeedsDestruction()
325 {
326     m_needsDestruction = handle().needsDestruction();
327 }
328
329 void MarkedBlock::Handle::didAddToAllocator(MarkedAllocator* allocator, size_t index)
330 {
331     ASSERT(m_index == std::numeric_limits<size_t>::max());
332     ASSERT(!m_allocator);
333     
334     m_index = index;
335     m_allocator = allocator;
336     
337     RELEASE_ASSERT(m_subspace->canTradeBlocksWith(allocator->subspace()));
338     RELEASE_ASSERT(allocator->subspace()->canTradeBlocksWith(m_subspace));
339     
340     m_subspace = allocator->subspace();
341     
342     size_t cellSize = allocator->cellSize();
343     m_atomsPerCell = (cellSize + atomSize - 1) / atomSize;
344     m_endAtom = atomsPerBlock - m_atomsPerCell + 1;
345     
346     m_attributes = allocator->attributes();
347
348     if (m_attributes.cellKind != HeapCell::JSCell)
349         RELEASE_ASSERT(m_attributes.destruction == DoesNotNeedDestruction);
350     
351     block().updateNeedsDestruction();
352     
353     double markCountBias = -(Options::minMarkedBlockUtilization() * cellsPerBlock());
354     
355     // The mark count bias should be comfortably within this range.
356     RELEASE_ASSERT(markCountBias > static_cast<double>(std::numeric_limits<int16_t>::min()));
357     RELEASE_ASSERT(markCountBias < 0);
358     
359     // This means we haven't marked anything yet.
360     block().m_biasedMarkCount = block().m_markCountBias = static_cast<int16_t>(markCountBias);
361 }
362
363 void MarkedBlock::Handle::didRemoveFromAllocator()
364 {
365     ASSERT(m_index != std::numeric_limits<size_t>::max());
366     ASSERT(m_allocator);
367     
368     m_index = std::numeric_limits<size_t>::max();
369     m_allocator = nullptr;
370 }
371
372 bool MarkedBlock::Handle::isLive(const HeapCell* cell)
373 {
374     return isLive(space()->markingVersion(), space()->isMarking(), cell);
375 }
376
377 bool MarkedBlock::Handle::isLiveCell(const void* p)
378 {
379     return isLiveCell(space()->markingVersion(), space()->isMarking(), p);
380 }
381
382 #if !ASSERT_DISABLED
383 void MarkedBlock::assertValidCell(VM& vm, HeapCell* cell) const
384 {
385     RELEASE_ASSERT(&vm == this->vm());
386     RELEASE_ASSERT(const_cast<MarkedBlock*>(this)->handle().cellAlign(cell) == cell);
387 }
388 #endif
389
390 void MarkedBlock::Handle::dumpState(PrintStream& out)
391 {
392     CommaPrinter comma;
393     allocator()->forEachBitVectorWithName(
394         holdLock(allocator()->bitvectorLock()),
395         [&] (FastBitVector& bitvector, const char* name) {
396             out.print(comma, name, ":", bitvector[index()] ? "YES" : "no");
397         });
398 }
399
400 void MarkedBlock::Handle::sweep(FreeList* freeList)
401 {
402     SweepingScope sweepingScope(*heap());
403     
404     SweepMode sweepMode = freeList ? SweepToFreeList : SweepOnly;
405     
406     m_allocator->setIsUnswept(NoLockingNecessary, this, false);
407     
408     m_weakSet.sweep();
409     
410     bool needsDestruction = m_attributes.destruction == NeedsDestruction
411         && m_allocator->isDestructible(NoLockingNecessary, this);
412
413     if (sweepMode == SweepOnly && !needsDestruction)
414         return;
415
416     if (UNLIKELY(m_isFreeListed)) {
417         RELEASE_ASSERT(sweepMode == SweepToFreeList);
418         return;
419     }
420     
421     ASSERT(!m_allocator->isAllocated(NoLockingNecessary, this));
422     
423     if (space()->isMarking())
424         block().m_lock.lock();
425     
426     if (needsDestruction) {
427         subspace()->finishSweep(*this, freeList);
428         return;
429     }
430     
431     // Handle the no-destructor specializations here, since we have the most of those. This
432     // ensures that they don't get re-specialized for every destructor space.
433     
434     EmptyMode emptyMode = this->emptyMode();
435     ScribbleMode scribbleMode = this->scribbleMode();
436     NewlyAllocatedMode newlyAllocatedMode = this->newlyAllocatedMode();
437     MarksMode marksMode = this->marksMode();
438     
439     auto trySpecialized = [&] () -> bool {
440         if (sweepMode != SweepToFreeList)
441             return false;
442         if (scribbleMode != DontScribble)
443             return false;
444         if (newlyAllocatedMode != DoesNotHaveNewlyAllocated)
445             return false;
446         
447         switch (emptyMode) {
448         case IsEmpty:
449             switch (marksMode) {
450             case MarksNotStale:
451                 specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, [] (VM&, JSCell*) { });
452                 return true;
453             case MarksStale:
454                 specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, [] (VM&, JSCell*) { });
455                 return true;
456             }
457             break;
458         case NotEmpty:
459             switch (marksMode) {
460             case MarksNotStale:
461                 specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, [] (VM&, JSCell*) { });
462                 return true;
463             case MarksStale:
464                 specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasNoDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, [] (VM&, JSCell*) { });
465                 return true;
466             }
467             break;
468         }
469         
470         return false;
471     };
472     
473     if (trySpecialized())
474         return;
475
476     // The template arguments don't matter because the first one is false.
477     specializedSweep<false, IsEmpty, SweepOnly, BlockHasNoDestructors, DontScribble, HasNewlyAllocated, MarksStale>(freeList, emptyMode, sweepMode, BlockHasNoDestructors, scribbleMode, newlyAllocatedMode, marksMode, [] (VM&, JSCell*) { });
478 }
479
480 bool MarkedBlock::Handle::isFreeListedCell(const void* target) const
481 {
482     ASSERT(isFreeListed());
483     return m_allocator->isFreeListedCell(target);
484 }
485
486 } // namespace JSC
487
488 namespace WTF {
489
490 void printInternal(PrintStream& out, JSC::MarkedBlock::Handle::SweepMode mode)
491 {
492     switch (mode) {
493     case JSC::MarkedBlock::Handle::SweepToFreeList:
494         out.print("SweepToFreeList");
495         return;
496     case JSC::MarkedBlock::Handle::SweepOnly:
497         out.print("SweepOnly");
498         return;
499     }
500     RELEASE_ASSERT_NOT_REACHED();
501 }
502
503 } // namespace WTF
504