Unreviewed, rolling out r206314, r206316, and r206319.
[WebKit-https.git] / Source / JavaScriptCore / heap / SlotVisitor.cpp
1 /*
2  * Copyright (C) 2012, 2015-2016 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 "SlotVisitor.h"
28 #include "SlotVisitorInlines.h"
29
30 #include "ConservativeRoots.h"
31 #include "HeapCellInlines.h"
32 #include "HeapProfiler.h"
33 #include "HeapSnapshotBuilder.h"
34 #include "JSArray.h"
35 #include "JSDestructibleObject.h"
36 #include "JSObject.h"
37 #include "JSString.h"
38 #include "JSCInlines.h"
39 #include "SuperSampler.h"
40 #include "VM.h"
41 #include <wtf/Lock.h>
42
43 namespace JSC {
44
45 #if ENABLE(GC_VALIDATION)
46 static void validate(JSCell* cell)
47 {
48     RELEASE_ASSERT(cell);
49
50     if (!cell->structure()) {
51         dataLogF("cell at %p has a null structure\n" , cell);
52         CRASH();
53     }
54
55     // Both the cell's structure, and the cell's structure's structure should be the Structure Structure.
56     // I hate this sentence.
57     if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo()) {
58         const char* parentClassName = 0;
59         const char* ourClassName = 0;
60         if (cell->structure()->structure() && cell->structure()->structure()->JSCell::classInfo())
61             parentClassName = cell->structure()->structure()->JSCell::classInfo()->className;
62         if (cell->structure()->JSCell::classInfo())
63             ourClassName = cell->structure()->JSCell::classInfo()->className;
64         dataLogF("parent structure (%p <%s>) of cell at %p doesn't match cell's structure (%p <%s>)\n",
65             cell->structure()->structure(), parentClassName, cell, cell->structure(), ourClassName);
66         CRASH();
67     }
68
69     // Make sure we can walk the ClassInfo chain
70     const ClassInfo* info = cell->classInfo();
71     do { } while ((info = info->parentClass));
72 }
73 #endif
74
75 SlotVisitor::SlotVisitor(Heap& heap)
76     : m_stack()
77     , m_bytesVisited(0)
78     , m_bytesCopied(0)
79     , m_visitCount(0)
80     , m_isInParallelMode(false)
81     , m_markingVersion(MarkedSpace::initialVersion)
82     , m_heap(heap)
83 #if !ASSERT_DISABLED
84     , m_isCheckingForDefaultMarkViolation(false)
85     , m_isDraining(false)
86 #endif
87 {
88 }
89
90 SlotVisitor::~SlotVisitor()
91 {
92     clearMarkStack();
93 }
94
95 void SlotVisitor::didStartMarking()
96 {
97     if (heap()->operationInProgress() == FullCollection)
98         ASSERT(m_opaqueRoots.isEmpty()); // Should have merged by now.
99     else
100         reset();
101
102     if (HeapProfiler* heapProfiler = vm().heapProfiler())
103         m_heapSnapshotBuilder = heapProfiler->activeSnapshotBuilder();
104     
105     m_markingVersion = heap()->objectSpace().markingVersion();
106 }
107
108 void SlotVisitor::reset()
109 {
110     m_bytesVisited = 0;
111     m_bytesCopied = 0;
112     m_visitCount = 0;
113     m_heapSnapshotBuilder = nullptr;
114     ASSERT(!m_currentCell);
115 }
116
117 void SlotVisitor::clearMarkStack()
118 {
119     m_stack.clear();
120 }
121
122 void SlotVisitor::append(ConservativeRoots& conservativeRoots)
123 {
124     HeapCell** roots = conservativeRoots.roots();
125     size_t size = conservativeRoots.size();
126     for (size_t i = 0; i < size; ++i)
127         appendJSCellOrAuxiliary(roots[i]);
128 }
129
130 void SlotVisitor::appendJSCellOrAuxiliary(HeapCell* heapCell)
131 {
132     if (!heapCell)
133         return;
134     
135     ASSERT(!m_isCheckingForDefaultMarkViolation);
136     
137     if (Heap::testAndSetMarked(m_markingVersion, heapCell))
138         return;
139     
140     switch (heapCell->cellKind()) {
141     case HeapCell::JSCell: {
142         JSCell* jsCell = static_cast<JSCell*>(heapCell);
143         
144         if (!jsCell->structure()) {
145             ASSERT_NOT_REACHED();
146             return;
147         }
148         
149         jsCell->setCellState(CellState::NewGrey);
150
151         appendToMarkStack(jsCell);
152         return;
153     }
154         
155     case HeapCell::Auxiliary: {
156         noteLiveAuxiliaryCell(heapCell);
157         return;
158     } }
159 }
160
161 void SlotVisitor::append(JSValue value)
162 {
163     if (!value || !value.isCell())
164         return;
165
166     if (UNLIKELY(m_heapSnapshotBuilder))
167         m_heapSnapshotBuilder->appendEdge(m_currentCell, value.asCell());
168
169     setMarkedAndAppendToMarkStack(value.asCell());
170 }
171
172 void SlotVisitor::appendHidden(JSValue value)
173 {
174     if (!value || !value.isCell())
175         return;
176
177     setMarkedAndAppendToMarkStack(value.asCell());
178 }
179
180 void SlotVisitor::setMarkedAndAppendToMarkStack(JSCell* cell)
181 {
182     SuperSamplerScope superSamplerScope(false);
183     
184     ASSERT(!m_isCheckingForDefaultMarkViolation);
185     if (!cell)
186         return;
187
188 #if ENABLE(GC_VALIDATION)
189     validate(cell);
190 #endif
191     
192     //dataLog("    Marking ", RawPointer(cell), "\n");
193     
194     if (cell->isLargeAllocation())
195         setMarkedAndAppendToMarkStack(cell->largeAllocation(), cell);
196     else
197         setMarkedAndAppendToMarkStack(cell->markedBlock(), cell);
198 }
199
200 template<typename ContainerType>
201 ALWAYS_INLINE void SlotVisitor::setMarkedAndAppendToMarkStack(ContainerType& container, JSCell* cell)
202 {
203     container.aboutToMark(m_markingVersion);
204     
205     if (container.testAndSetMarked(cell))
206         return;
207     
208     ASSERT(cell->structure());
209     
210     // Indicate that the object is grey and that:
211     // In case of concurrent GC: it's the first time it is grey in this GC cycle.
212     // In case of eden collection: it's a new object that became grey rather than an old remembered object.
213     cell->setCellState(CellState::NewGrey);
214     
215     appendToMarkStack(container, cell);
216 }
217
218 void SlotVisitor::appendToMarkStack(JSCell* cell)
219 {
220     if (cell->isLargeAllocation())
221         appendToMarkStack(cell->largeAllocation(), cell);
222     else
223         appendToMarkStack(cell->markedBlock(), cell);
224 }
225
226 template<typename ContainerType>
227 ALWAYS_INLINE void SlotVisitor::appendToMarkStack(ContainerType& container, JSCell* cell)
228 {
229     ASSERT(Heap::isMarkedConcurrently(cell));
230     ASSERT(!cell->isZapped());
231     
232     container.noteMarked();
233     
234     // FIXME: These "just work" because the GC resets these fields before doing anything else. But
235     // that won't be the case when we do concurrent GC.
236     m_visitCount++;
237     m_bytesVisited += container.cellSize();
238     
239     m_stack.append(cell);
240
241     if (UNLIKELY(m_heapSnapshotBuilder))
242         m_heapSnapshotBuilder->appendNode(cell);
243 }
244
245 void SlotVisitor::markAuxiliary(const void* base)
246 {
247     HeapCell* cell = bitwise_cast<HeapCell*>(base);
248     
249     ASSERT(cell->heap() == heap());
250     
251     if (Heap::testAndSetMarked(m_markingVersion, cell))
252         return;
253     
254     noteLiveAuxiliaryCell(cell);
255 }
256
257 void SlotVisitor::noteLiveAuxiliaryCell(HeapCell* cell)
258 {
259     // We get here once per GC under these circumstances:
260     //
261     // Eden collection: if the cell was allocated since the last collection and is live somehow.
262     //
263     // Full collection: if the cell is live somehow.
264     
265     CellContainer container = cell->cellContainer();
266     
267     container.noteMarked();
268     
269     m_visitCount++;
270     m_bytesVisited += container.cellSize();
271 }
272
273 class SetCurrentCellScope {
274 public:
275     SetCurrentCellScope(SlotVisitor& visitor, const JSCell* cell)
276         : m_visitor(visitor)
277     {
278         ASSERT(!m_visitor.m_currentCell);
279         m_visitor.m_currentCell = const_cast<JSCell*>(cell);
280     }
281
282     ~SetCurrentCellScope()
283     {
284         ASSERT(m_visitor.m_currentCell);
285         m_visitor.m_currentCell = nullptr;
286     }
287
288 private:
289     SlotVisitor& m_visitor;
290 };
291
292
293 ALWAYS_INLINE void SlotVisitor::visitChildren(const JSCell* cell)
294 {
295     ASSERT(Heap::isMarkedConcurrently(cell));
296     
297     SetCurrentCellScope currentCellScope(*this, cell);
298     
299     m_currentObjectCellStateBeforeVisiting = cell->cellState();
300     cell->setCellState(CellState::OldBlack);
301     
302     if (isJSString(cell)) {
303         JSString::visitChildren(const_cast<JSCell*>(cell), *this);
304         return;
305     }
306
307     if (isJSFinalObject(cell)) {
308         JSFinalObject::visitChildren(const_cast<JSCell*>(cell), *this);
309         return;
310     }
311
312     if (isJSArray(cell)) {
313         JSArray::visitChildren(const_cast<JSCell*>(cell), *this);
314         return;
315     }
316
317     cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), *this);
318 }
319
320 void SlotVisitor::donateKnownParallel()
321 {
322     // NOTE: Because we re-try often, we can afford to be conservative, and
323     // assume that donating is not profitable.
324
325     // Avoid locking when a thread reaches a dead end in the object graph.
326     if (m_stack.size() < 2)
327         return;
328
329     // If there's already some shared work queued up, be conservative and assume
330     // that donating more is not profitable.
331     if (m_heap.m_sharedMarkStack.size())
332         return;
333
334     // If we're contending on the lock, be conservative and assume that another
335     // thread is already donating.
336     std::unique_lock<Lock> lock(m_heap.m_markingMutex, std::try_to_lock);
337     if (!lock.owns_lock())
338         return;
339
340     // Otherwise, assume that a thread will go idle soon, and donate.
341     m_stack.donateSomeCellsTo(m_heap.m_sharedMarkStack);
342
343     m_heap.m_markingConditionVariable.notifyAll();
344 }
345
346 void SlotVisitor::drain()
347 {
348     ASSERT(m_isInParallelMode);
349    
350     while (!m_stack.isEmpty()) {
351         m_stack.refill();
352         for (unsigned countdown = Options::minimumNumberOfScansBetweenRebalance(); m_stack.canRemoveLast() && countdown--;)
353             visitChildren(m_stack.removeLast());
354         donateKnownParallel();
355     }
356     
357     mergeOpaqueRootsIfNecessary();
358 }
359
360 void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
361 {
362     ASSERT(m_isInParallelMode);
363     
364     ASSERT(Options::numberOfGCMarkers());
365     
366     {
367         std::lock_guard<Lock> lock(m_heap.m_markingMutex);
368         m_heap.m_numberOfActiveParallelMarkers++;
369     }
370     while (true) {
371         {
372             std::unique_lock<Lock> lock(m_heap.m_markingMutex);
373             m_heap.m_numberOfActiveParallelMarkers--;
374             m_heap.m_numberOfWaitingParallelMarkers++;
375
376             // How we wait differs depending on drain mode.
377             if (sharedDrainMode == MasterDrain) {
378                 // Wait until either termination is reached, or until there is some work
379                 // for us to do.
380                 while (true) {
381                     // Did we reach termination?
382                     if (!m_heap.m_numberOfActiveParallelMarkers
383                         && m_heap.m_sharedMarkStack.isEmpty()) {
384                         // Let any sleeping slaves know it's time for them to return;
385                         m_heap.m_markingConditionVariable.notifyAll();
386                         return;
387                     }
388                     
389                     // Is there work to be done?
390                     if (!m_heap.m_sharedMarkStack.isEmpty())
391                         break;
392                     
393                     // Otherwise wait.
394                     m_heap.m_markingConditionVariable.wait(lock);
395                 }
396             } else {
397                 ASSERT(sharedDrainMode == SlaveDrain);
398                 
399                 // Did we detect termination? If so, let the master know.
400                 if (!m_heap.m_numberOfActiveParallelMarkers
401                     && m_heap.m_sharedMarkStack.isEmpty())
402                     m_heap.m_markingConditionVariable.notifyAll();
403
404                 m_heap.m_markingConditionVariable.wait(
405                     lock,
406                     [this] {
407                         return !m_heap.m_sharedMarkStack.isEmpty()
408                             || m_heap.m_parallelMarkersShouldExit;
409                     });
410                 
411                 // Is the current phase done? If so, return from this function.
412                 if (m_heap.m_parallelMarkersShouldExit)
413                     return;
414             }
415
416             m_stack.stealSomeCellsFrom(
417                 m_heap.m_sharedMarkStack, m_heap.m_numberOfWaitingParallelMarkers);
418             m_heap.m_numberOfActiveParallelMarkers++;
419             m_heap.m_numberOfWaitingParallelMarkers--;
420         }
421         
422         drain();
423     }
424 }
425
426 void SlotVisitor::addOpaqueRoot(void* root)
427 {
428     if (Options::numberOfGCMarkers() == 1) {
429         // Put directly into the shared HashSet.
430         m_heap.m_opaqueRoots.add(root);
431         return;
432     }
433     // Put into the local set, but merge with the shared one every once in
434     // a while to make sure that the local sets don't grow too large.
435     mergeOpaqueRootsIfProfitable();
436     m_opaqueRoots.add(root);
437 }
438
439 bool SlotVisitor::containsOpaqueRoot(void* root) const
440 {
441     ASSERT(!m_isInParallelMode);
442     ASSERT(m_opaqueRoots.isEmpty());
443     return m_heap.m_opaqueRoots.contains(root);
444 }
445
446 TriState SlotVisitor::containsOpaqueRootTriState(void* root) const
447 {
448     if (m_opaqueRoots.contains(root))
449         return TrueTriState;
450     std::lock_guard<Lock> lock(m_heap.m_opaqueRootsMutex);
451     if (m_heap.m_opaqueRoots.contains(root))
452         return TrueTriState;
453     return MixedTriState;
454 }
455
456 int SlotVisitor::opaqueRootCount()
457 {
458     ASSERT(!m_isInParallelMode);
459     ASSERT(m_opaqueRoots.isEmpty());
460     return m_heap.m_opaqueRoots.size();
461 }
462
463 void SlotVisitor::mergeOpaqueRootsIfNecessary()
464 {
465     if (m_opaqueRoots.isEmpty())
466         return;
467     mergeOpaqueRoots();
468 }
469     
470 void SlotVisitor::mergeOpaqueRootsIfProfitable()
471 {
472     if (static_cast<unsigned>(m_opaqueRoots.size()) < Options::opaqueRootMergeThreshold())
473         return;
474     mergeOpaqueRoots();
475 }
476     
477 void SlotVisitor::donate()
478 {
479     ASSERT(m_isInParallelMode);
480     if (Options::numberOfGCMarkers() == 1)
481         return;
482     
483     donateKnownParallel();
484 }
485
486 void SlotVisitor::donateAndDrain()
487 {
488     donate();
489     drain();
490 }
491
492 void SlotVisitor::mergeOpaqueRoots()
493 {
494     ASSERT(!m_opaqueRoots.isEmpty()); // Should only be called when opaque roots are non-empty.
495     {
496         std::lock_guard<Lock> lock(m_heap.m_opaqueRootsMutex);
497         for (auto* root : m_opaqueRoots)
498             m_heap.m_opaqueRoots.add(root);
499     }
500     m_opaqueRoots.clear();
501 }
502
503 void SlotVisitor::harvestWeakReferences()
504 {
505     for (WeakReferenceHarvester* current = m_heap.m_weakReferenceHarvesters.head(); current; current = current->next())
506         current->visitWeakReferences(*this);
507 }
508
509 void SlotVisitor::finalizeUnconditionalFinalizers()
510 {
511     while (m_heap.m_unconditionalFinalizers.hasNext())
512         m_heap.m_unconditionalFinalizers.removeNext()->finalizeUnconditionally();
513 }
514
515 void SlotVisitor::dump(PrintStream&) const
516 {
517     for (const JSCell* cell : markStack())
518         dataLog(*cell, "\n");
519 }
520
521 } // namespace JSC