4e0b9bc7f1b4b2e4c721571bc4297c2d3df1ada4
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedBlockInlines.h
1 /*
2  * Copyright (C) 2016-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 #pragma once
27
28 #include "JSCell.h"
29 #include "MarkedAllocator.h"
30 #include "MarkedBlock.h"
31 #include "MarkedSpace.h"
32 #include "Operations.h"
33 #include "SuperSampler.h"
34 #include "VM.h"
35
36 namespace JSC {
37
38 inline unsigned MarkedBlock::Handle::cellsPerBlock()
39 {
40     return MarkedSpace::blockPayload / cellSize();
41 }
42
43 inline bool MarkedBlock::Handle::isNewlyAllocatedStale() const
44 {
45     return m_newlyAllocatedVersion != space()->newlyAllocatedVersion();
46 }
47
48 inline bool MarkedBlock::Handle::hasAnyNewlyAllocated()
49 {
50     return !isNewlyAllocatedStale();
51 }
52
53 inline Heap* MarkedBlock::heap() const
54 {
55     return &vm()->heap;
56 }
57
58 inline MarkedSpace* MarkedBlock::space() const
59 {
60     return &heap()->objectSpace();
61 }
62
63 inline MarkedSpace* MarkedBlock::Handle::space() const
64 {
65     return &heap()->objectSpace();
66 }
67
68 inline bool MarkedBlock::marksConveyLivenessDuringMarking(HeapVersion markingVersion)
69 {
70     // This returns true if any of these is true:
71     // - We just created the block and so the bits are clear already.
72     // - This block has objects marked during the last GC, and so its version was up-to-date just
73     //   before the current collection did beginMarking(). This means that any objects that have 
74     //   their mark bit set are valid objects that were never deleted, and so are candidates for
75     //   marking in any conservative scan. Using our jargon, they are "live".
76     // - We did ~2^32 collections and rotated the version back to null, so we needed to hard-reset
77     //   everything. If the marks had been stale, we would have cleared them. So, we can be sure that
78     //   any set mark bit reflects objects marked during last GC, i.e. "live" objects.
79     // It would be absurd to use this method when not collecting, since this special "one version
80     // back" state only makes sense when we're in a concurrent collection and have to be
81     // conservative.
82     ASSERT(space()->isMarking());
83     if (heap()->collectionScope() != CollectionScope::Full)
84         return false;
85     return m_markingVersion == MarkedSpace::nullVersion
86         || MarkedSpace::nextVersion(m_markingVersion) == markingVersion;
87 }
88
89 inline bool MarkedBlock::Handle::isLive(HeapVersion markingVersion, bool isMarking, const HeapCell* cell)
90 {
91     ASSERT(!isFreeListed());
92     
93     if (UNLIKELY(hasAnyNewlyAllocated())) {
94         if (isNewlyAllocated(cell))
95             return true;
96     }
97     
98     if (allocator()->isAllocated(NoLockingNecessary, this))
99         return true;
100     
101     MarkedBlock& block = this->block();
102     
103     if (block.areMarksStale()) {
104         if (!isMarking)
105             return false;
106         if (!block.marksConveyLivenessDuringMarking(markingVersion))
107             return false;
108     }
109
110     return block.m_marks.get(block.atomNumber(cell));
111 }
112
113 inline bool MarkedBlock::Handle::isLiveCell(HeapVersion markingVersion, bool isMarking, const void* p)
114 {
115     if (!m_block->isAtom(p))
116         return false;
117     return isLive(markingVersion, isMarking, static_cast<const HeapCell*>(p));
118 }
119
120 // The following has to be true for specialization to kick in:
121 //
122 // sweepMode == SweepToFreeList
123 // scribbleMode == DontScribble
124 // newlyAllocatedMode == DoesNotHaveNewlyAllocated
125 // destructionMode != BlockHasDestrictorsAndCollectorIsRunning
126 //
127 // emptyMode = IsEmpty
128 //     destructionMode = DoesNotNeedDestruction
129 //         marksMode = MarksNotStale (1)
130 //         marksMode = MarksStale (2)
131 // emptyMode = NotEmpty
132 //     destructionMode = DoesNotNeedDestruction
133 //         marksMode = MarksNotStale (3)
134 //         marksMode = MarksStale (4)
135 //     destructionMode = NeedsDestruction
136 //         marksMode = MarksNotStale (5)
137 //         marksMode = MarksStale (6)
138 //
139 // Only the DoesNotNeedDestruction one should be specialized by MarkedBlock.
140
141 template<bool specialize, MarkedBlock::Handle::EmptyMode specializedEmptyMode, MarkedBlock::Handle::SweepMode specializedSweepMode, MarkedBlock::Handle::SweepDestructionMode specializedDestructionMode, MarkedBlock::Handle::ScribbleMode specializedScribbleMode, MarkedBlock::Handle::NewlyAllocatedMode specializedNewlyAllocatedMode, MarkedBlock::Handle::MarksMode specializedMarksMode, typename DestroyFunc>
142 void MarkedBlock::Handle::specializedSweep(FreeList* freeList, MarkedBlock::Handle::EmptyMode emptyMode, MarkedBlock::Handle::SweepMode sweepMode, MarkedBlock::Handle::SweepDestructionMode destructionMode, MarkedBlock::Handle::ScribbleMode scribbleMode, MarkedBlock::Handle::NewlyAllocatedMode newlyAllocatedMode, MarkedBlock::Handle::MarksMode marksMode, const DestroyFunc& destroyFunc)
143 {
144     if (specialize) {
145         emptyMode = specializedEmptyMode;
146         sweepMode = specializedSweepMode;
147         destructionMode = specializedDestructionMode;
148         scribbleMode = specializedScribbleMode;
149         newlyAllocatedMode = specializedNewlyAllocatedMode;
150         marksMode = specializedMarksMode;
151     }
152     
153     RELEASE_ASSERT(!(destructionMode == BlockHasNoDestructors && sweepMode == SweepOnly));
154     
155     SuperSamplerScope superSamplerScope(false);
156
157     MarkedBlock& block = this->block();
158     
159     if (false)
160         dataLog(RawPointer(this), "/", RawPointer(&block), ": MarkedBlock::Handle::specializedSweep!\n");
161     
162     unsigned cellSize = this->cellSize();
163     
164     VM& vm = *this->vm();
165     auto destroy = [&] (void* cell) {
166         JSCell* jsCell = static_cast<JSCell*>(cell);
167         if (!jsCell->isZapped()) {
168             destroyFunc(vm, jsCell);
169             jsCell->zap();
170         }
171     };
172     
173     m_allocator->setIsDestructible(NoLockingNecessary, this, false);
174     
175     if (Options::useBumpAllocator()
176         && emptyMode == IsEmpty
177         && newlyAllocatedMode == DoesNotHaveNewlyAllocated) {
178         
179         // This is an incredibly powerful assertion that checks the sanity of our block bits.
180         if (marksMode == MarksNotStale && !block.m_marks.isEmpty()) {
181             WTF::dataFile().atomically(
182                 [&] (PrintStream& out) {
183                     out.print("Block ", RawPointer(&block), ": marks not empty!\n");
184                     out.print("Block lock is held: ", block.m_lock.isHeld(), "\n");
185                     out.print("Marking version of block: ", block.m_markingVersion, "\n");
186                     out.print("Marking version of heap: ", space()->markingVersion(), "\n");
187                     UNREACHABLE_FOR_PLATFORM();
188                 });
189         }
190         
191         char* startOfLastCell = static_cast<char*>(cellAlign(block.atoms() + m_endAtom - 1));
192         char* payloadEnd = startOfLastCell + cellSize;
193         RELEASE_ASSERT(payloadEnd - MarkedBlock::blockSize <= bitwise_cast<char*>(&block));
194         char* payloadBegin = bitwise_cast<char*>(block.atoms() + firstAtom());
195         
196         if (sweepMode == SweepToFreeList)
197             setIsFreeListed();
198         if (space()->isMarking())
199             block.m_lock.unlock();
200         if (destructionMode != BlockHasNoDestructors) {
201             for (char* cell = payloadBegin; cell < payloadEnd; cell += cellSize)
202                 destroy(cell);
203         }
204         if (sweepMode == SweepToFreeList) {
205             if (scribbleMode == Scribble)
206                 scribble(payloadBegin, payloadEnd - payloadBegin);
207             freeList->initializeBump(payloadEnd, payloadEnd - payloadBegin);
208         }
209         if (false)
210             dataLog("Quickly swept block ", RawPointer(this), " with cell size ", cellSize, " and attributes ", m_attributes, ": ", pointerDump(freeList), "\n");
211         return;
212     }
213
214     // This produces a free list that is ordered in reverse through the block.
215     // This is fine, since the allocation code makes no assumptions about the
216     // order of the free list.
217     FreeCell* head = 0;
218     size_t count = 0;
219     uintptr_t secret;
220     cryptographicallyRandomValues(&secret, sizeof(uintptr_t));
221     bool isEmpty = true;
222     Vector<size_t> deadCells;
223     auto handleDeadCell = [&] (size_t i) {
224         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&block.atoms()[i]);
225
226         if (destructionMode != BlockHasNoDestructors)
227             destroy(cell);
228
229         if (sweepMode == SweepToFreeList) {
230             FreeCell* freeCell = reinterpret_cast_ptr<FreeCell*>(cell);
231             if (scribbleMode == Scribble)
232                 scribble(freeCell, cellSize);
233             freeCell->setNext(head, secret);
234             head = freeCell;
235             ++count;
236         }
237     };
238     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
239         if (emptyMode == NotEmpty
240             && ((marksMode == MarksNotStale && block.m_marks.get(i))
241                 || (newlyAllocatedMode == HasNewlyAllocated && m_newlyAllocated.get(i)))) {
242             isEmpty = false;
243             continue;
244         }
245         
246         if (destructionMode == BlockHasDestructorsAndCollectorIsRunning)
247             deadCells.append(i);
248         else
249             handleDeadCell(i);
250     }
251     
252     // We only want to discard the newlyAllocated bits if we're creating a FreeList,
253     // otherwise we would lose information on what's currently alive.
254     if (sweepMode == SweepToFreeList && newlyAllocatedMode == HasNewlyAllocated)
255         m_newlyAllocatedVersion = MarkedSpace::nullVersion;
256     
257     if (space()->isMarking())
258         block.m_lock.unlock();
259     
260     if (destructionMode == BlockHasDestructorsAndCollectorIsRunning) {
261         for (size_t i : deadCells)
262             handleDeadCell(i);
263     }
264
265     if (sweepMode == SweepToFreeList) {
266         freeList->initializeList(head, secret, count * cellSize);
267         setIsFreeListed();
268     } else if (isEmpty)
269         m_allocator->setIsEmpty(NoLockingNecessary, this, true);
270     if (false)
271         dataLog("Slowly swept block ", RawPointer(&block), " with cell size ", cellSize, " and attributes ", m_attributes, ": ", pointerDump(freeList), "\n");
272 }
273
274 template<typename DestroyFunc>
275 void MarkedBlock::Handle::finishSweepKnowingHeapCellType(FreeList* freeList, const DestroyFunc& destroyFunc)
276 {
277     SweepMode sweepMode = freeList ? SweepToFreeList : SweepOnly;
278     SweepDestructionMode destructionMode = this->sweepDestructionMode();
279     EmptyMode emptyMode = this->emptyMode();
280     ScribbleMode scribbleMode = this->scribbleMode();
281     NewlyAllocatedMode newlyAllocatedMode = this->newlyAllocatedMode();
282     MarksMode marksMode = this->marksMode();
283
284     auto trySpecialized = [&] () -> bool {
285         if (scribbleMode != DontScribble)
286             return false;
287         if (newlyAllocatedMode != DoesNotHaveNewlyAllocated)
288             return false;
289         if (destructionMode != BlockHasDestructors)
290             return false;
291         
292         switch (emptyMode) {
293         case IsEmpty:
294             switch (sweepMode) {
295             case SweepOnly:
296                 switch (marksMode) {
297                 case MarksNotStale:
298                     specializedSweep<true, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
299                     return true;
300                 case MarksStale:
301                     specializedSweep<true, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
302                     return true;
303                 }
304             case SweepToFreeList:
305                 switch (marksMode) {
306                 case MarksNotStale:
307                     specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
308                     return true;
309                 case MarksStale:
310                     specializedSweep<true, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, IsEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
311                     return true;
312                 }
313             }
314         case NotEmpty:
315             switch (sweepMode) {
316             case SweepOnly:
317                 switch (marksMode) {
318                 case MarksNotStale:
319                     specializedSweep<true, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
320                     return true;
321                 case MarksStale:
322                     specializedSweep<true, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, NotEmpty, SweepOnly, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
323                     return true;
324                 }
325             case SweepToFreeList:
326                 switch (marksMode) {
327                 case MarksNotStale:
328                     specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale>(freeList, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksNotStale, destroyFunc);
329                     return true;
330                 case MarksStale:
331                     specializedSweep<true, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale>(freeList, NotEmpty, SweepToFreeList, BlockHasDestructors, DontScribble, DoesNotHaveNewlyAllocated, MarksStale, destroyFunc);
332                     return true;
333                 }
334             }
335         }
336         
337         return false;
338     };
339     
340     if (trySpecialized())
341         return;
342     
343     // The template arguments don't matter because the first one is false.
344     specializedSweep<false, IsEmpty, SweepOnly, BlockHasNoDestructors, DontScribble, HasNewlyAllocated, MarksStale>(freeList, emptyMode, sweepMode, destructionMode, scribbleMode, newlyAllocatedMode, marksMode, destroyFunc);
345 }
346
347 inline MarkedBlock::Handle::SweepDestructionMode MarkedBlock::Handle::sweepDestructionMode()
348 {
349     if (m_attributes.destruction == NeedsDestruction) {
350         if (space()->isMarking())
351             return BlockHasDestructorsAndCollectorIsRunning;
352         return BlockHasDestructors;
353     }
354     return BlockHasNoDestructors;
355 }
356
357 inline MarkedBlock::Handle::EmptyMode MarkedBlock::Handle::emptyMode()
358 {
359     // It's not obvious, but this is the only way to know if the block is empty. It's the only
360     // bit that captures these caveats:
361     // - It's true when the block is freshly allocated.
362     // - It's true if the block had been swept in the past, all destructors were called, and that
363     //   sweep proved that the block is empty.
364     return m_allocator->isEmpty(NoLockingNecessary, this) ? IsEmpty : NotEmpty;
365 }
366
367 inline MarkedBlock::Handle::ScribbleMode MarkedBlock::Handle::scribbleMode()
368 {
369     return scribbleFreeCells() ? Scribble : DontScribble;
370 }
371
372 inline MarkedBlock::Handle::NewlyAllocatedMode MarkedBlock::Handle::newlyAllocatedMode()
373 {
374     return hasAnyNewlyAllocated() ? HasNewlyAllocated : DoesNotHaveNewlyAllocated;
375 }
376
377 inline MarkedBlock::Handle::MarksMode MarkedBlock::Handle::marksMode()
378 {
379     HeapVersion markingVersion = space()->markingVersion();
380     bool marksAreUseful = !block().areMarksStale(markingVersion);
381     if (space()->isMarking())
382         marksAreUseful |= block().marksConveyLivenessDuringMarking(markingVersion);
383     return marksAreUseful ? MarksNotStale : MarksStale;
384 }
385
386 template <typename Functor>
387 inline IterationStatus MarkedBlock::Handle::forEachLiveCell(const Functor& functor)
388 {
389     HeapCell::Kind kind = m_attributes.cellKind;
390     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
391         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
392         if (!isLive(cell))
393             continue;
394
395         if (functor(cell, kind) == IterationStatus::Done)
396             return IterationStatus::Done;
397     }
398     return IterationStatus::Continue;
399 }
400
401 template <typename Functor>
402 inline IterationStatus MarkedBlock::Handle::forEachDeadCell(const Functor& functor)
403 {
404     HeapCell::Kind kind = m_attributes.cellKind;
405     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
406         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
407         if (isLive(cell))
408             continue;
409
410         if (functor(cell, kind) == IterationStatus::Done)
411             return IterationStatus::Done;
412     }
413     return IterationStatus::Continue;
414 }
415
416 template <typename Functor>
417 inline IterationStatus MarkedBlock::Handle::forEachMarkedCell(const Functor& functor)
418 {
419     HeapCell::Kind kind = m_attributes.cellKind;
420     MarkedBlock& block = this->block();
421     bool areMarksStale = block.areMarksStale();
422     WTF::loadLoadFence();
423     if (areMarksStale)
424         return IterationStatus::Continue;
425     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
426         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
427         if (!block.isMarkedRaw(cell))
428             continue;
429
430         if (functor(cell, kind) == IterationStatus::Done)
431             return IterationStatus::Done;
432     }
433     return IterationStatus::Continue;
434 }
435
436 } // namespace JSC
437