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