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