45d886e46d1947a9333361c36ebf9ba0bfd3d7c1
[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 "CopiedBlockInlines.h"
32 #include "CopiedSpace.h"
33 #include "CopiedSpaceInlines.h"
34 #include "HeapCellInlines.h"
35 #include "HeapProfiler.h"
36 #include "HeapSnapshotBuilder.h"
37 #include "JSArray.h"
38 #include "JSDestructibleObject.h"
39 #include "JSObject.h"
40 #include "JSString.h"
41 #include "JSCInlines.h"
42 #include "SuperSampler.h"
43 #include "VM.h"
44 #include <wtf/Lock.h>
45
46 namespace JSC {
47
48 #if ENABLE(GC_VALIDATION)
49 static void validate(JSCell* cell)
50 {
51     RELEASE_ASSERT(cell);
52
53     if (!cell->structure()) {
54         dataLogF("cell at %p has a null structure\n" , cell);
55         CRASH();
56     }
57
58     // Both the cell's structure, and the cell's structure's structure should be the Structure Structure.
59     // I hate this sentence.
60     if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo()) {
61         const char* parentClassName = 0;
62         const char* ourClassName = 0;
63         if (cell->structure()->structure() && cell->structure()->structure()->JSCell::classInfo())
64             parentClassName = cell->structure()->structure()->JSCell::classInfo()->className;
65         if (cell->structure()->JSCell::classInfo())
66             ourClassName = cell->structure()->JSCell::classInfo()->className;
67         dataLogF("parent structure (%p <%s>) of cell at %p doesn't match cell's structure (%p <%s>)\n",
68             cell->structure()->structure(), parentClassName, cell, cell->structure(), ourClassName);
69         CRASH();
70     }
71
72     // Make sure we can walk the ClassInfo chain
73     const ClassInfo* info = cell->classInfo();
74     do { } while ((info = info->parentClass));
75 }
76 #endif
77
78 SlotVisitor::SlotVisitor(Heap& heap)
79     : m_stack()
80     , m_bytesVisited(0)
81     , m_bytesCopied(0)
82     , m_visitCount(0)
83     , m_isInParallelMode(false)
84     , m_version(42)
85     , m_heap(heap)
86 #if !ASSERT_DISABLED
87     , m_isCheckingForDefaultMarkViolation(false)
88     , m_isDraining(false)
89 #endif
90 {
91 }
92
93 SlotVisitor::~SlotVisitor()
94 {
95     clearMarkStack();
96 }
97
98 void SlotVisitor::didStartMarking()
99 {
100     if (heap()->operationInProgress() == FullCollection)
101         ASSERT(m_opaqueRoots.isEmpty()); // Should have merged by now.
102     else
103         reset();
104
105     if (HeapProfiler* heapProfiler = vm().heapProfiler())
106         m_heapSnapshotBuilder = heapProfiler->activeSnapshotBuilder();
107     
108     m_version = heap()->objectSpace().version();
109 }
110
111 void SlotVisitor::reset()
112 {
113     m_bytesVisited = 0;
114     m_bytesCopied = 0;
115     m_visitCount = 0;
116     m_heapSnapshotBuilder = nullptr;
117     ASSERT(!m_currentCell);
118 }
119
120 void SlotVisitor::clearMarkStack()
121 {
122     m_stack.clear();
123 }
124
125 void SlotVisitor::append(ConservativeRoots& conservativeRoots)
126 {
127     HeapCell** roots = conservativeRoots.roots();
128     size_t size = conservativeRoots.size();
129     for (size_t i = 0; i < size; ++i)
130         appendJSCellOrAuxiliary(roots[i]);
131 }
132
133 void SlotVisitor::appendJSCellOrAuxiliary(HeapCell* heapCell)
134 {
135     if (!heapCell)
136         return;
137     
138     ASSERT(!m_isCheckingForDefaultMarkViolation);
139     
140     if (Heap::testAndSetMarked(m_version, heapCell))
141         return;
142     
143     switch (heapCell->cellKind()) {
144     case HeapCell::JSCell: {
145         JSCell* jsCell = static_cast<JSCell*>(heapCell);
146         
147         if (!jsCell->structure()) {
148             ASSERT_NOT_REACHED();
149             return;
150         }
151         
152         jsCell->setCellState(CellState::NewGrey);
153
154         appendToMarkStack(jsCell);
155         return;
156     }
157         
158     case HeapCell::Auxiliary: {
159         noteLiveAuxiliaryCell(heapCell);
160         return;
161     } }
162 }
163
164 void SlotVisitor::append(JSValue value)
165 {
166     if (!value || !value.isCell())
167         return;
168
169     if (UNLIKELY(m_heapSnapshotBuilder))
170         m_heapSnapshotBuilder->appendEdge(m_currentCell, value.asCell());
171
172     setMarkedAndAppendToMarkStack(value.asCell());
173 }
174
175 void SlotVisitor::appendHidden(JSValue value)
176 {
177     if (!value || !value.isCell())
178         return;
179
180     setMarkedAndAppendToMarkStack(value.asCell());
181 }
182
183 void SlotVisitor::setMarkedAndAppendToMarkStack(JSCell* cell)
184 {
185     SuperSamplerScope superSamplerScope(false);
186     
187     ASSERT(!m_isCheckingForDefaultMarkViolation);
188     if (!cell)
189         return;
190
191 #if ENABLE(GC_VALIDATION)
192     validate(cell);
193 #endif
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.flipIfNecessaryConcurrently(m_version);
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::isMarked(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     if (Heap::testAndSetMarked(m_version, cell)) {
251         RELEASE_ASSERT(Heap::isMarked(cell));
252         return;
253     }
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::isMarked(cell));
297     
298     SetCurrentCellScope currentCellScope(*this, cell);
299     
300     m_currentObjectCellStateBeforeVisiting = cell->cellState();
301     cell->setCellState(CellState::OldBlack);
302     
303     if (isJSString(cell)) {
304         JSString::visitChildren(const_cast<JSCell*>(cell), *this);
305         return;
306     }
307
308     if (isJSFinalObject(cell)) {
309         JSFinalObject::visitChildren(const_cast<JSCell*>(cell), *this);
310         return;
311     }
312
313     if (isJSArray(cell)) {
314         JSArray::visitChildren(const_cast<JSCell*>(cell), *this);
315         return;
316     }
317
318     cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), *this);
319 }
320
321 void SlotVisitor::donateKnownParallel()
322 {
323     // NOTE: Because we re-try often, we can afford to be conservative, and
324     // assume that donating is not profitable.
325
326     // Avoid locking when a thread reaches a dead end in the object graph.
327     if (m_stack.size() < 2)
328         return;
329
330     // If there's already some shared work queued up, be conservative and assume
331     // that donating more is not profitable.
332     if (m_heap.m_sharedMarkStack.size())
333         return;
334
335     // If we're contending on the lock, be conservative and assume that another
336     // thread is already donating.
337     std::unique_lock<Lock> lock(m_heap.m_markingMutex, std::try_to_lock);
338     if (!lock.owns_lock())
339         return;
340
341     // Otherwise, assume that a thread will go idle soon, and donate.
342     m_stack.donateSomeCellsTo(m_heap.m_sharedMarkStack);
343
344     m_heap.m_markingConditionVariable.notifyAll();
345 }
346
347 void SlotVisitor::drain()
348 {
349     ASSERT(m_isInParallelMode);
350    
351     while (!m_stack.isEmpty()) {
352         m_stack.refill();
353         for (unsigned countdown = Options::minimumNumberOfScansBetweenRebalance(); m_stack.canRemoveLast() && countdown--;)
354             visitChildren(m_stack.removeLast());
355         donateKnownParallel();
356     }
357     
358     mergeOpaqueRootsIfNecessary();
359 }
360
361 void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
362 {
363     ASSERT(m_isInParallelMode);
364     
365     ASSERT(Options::numberOfGCMarkers());
366     
367     {
368         std::lock_guard<Lock> lock(m_heap.m_markingMutex);
369         m_heap.m_numberOfActiveParallelMarkers++;
370     }
371     while (true) {
372         {
373             std::unique_lock<Lock> lock(m_heap.m_markingMutex);
374             m_heap.m_numberOfActiveParallelMarkers--;
375             m_heap.m_numberOfWaitingParallelMarkers++;
376
377             // How we wait differs depending on drain mode.
378             if (sharedDrainMode == MasterDrain) {
379                 // Wait until either termination is reached, or until there is some work
380                 // for us to do.
381                 while (true) {
382                     // Did we reach termination?
383                     if (!m_heap.m_numberOfActiveParallelMarkers
384                         && m_heap.m_sharedMarkStack.isEmpty()) {
385                         // Let any sleeping slaves know it's time for them to return;
386                         m_heap.m_markingConditionVariable.notifyAll();
387                         return;
388                     }
389                     
390                     // Is there work to be done?
391                     if (!m_heap.m_sharedMarkStack.isEmpty())
392                         break;
393                     
394                     // Otherwise wait.
395                     m_heap.m_markingConditionVariable.wait(lock);
396                 }
397             } else {
398                 ASSERT(sharedDrainMode == SlaveDrain);
399                 
400                 // Did we detect termination? If so, let the master know.
401                 if (!m_heap.m_numberOfActiveParallelMarkers
402                     && m_heap.m_sharedMarkStack.isEmpty())
403                     m_heap.m_markingConditionVariable.notifyAll();
404
405                 m_heap.m_markingConditionVariable.wait(
406                     lock,
407                     [this] {
408                         return !m_heap.m_sharedMarkStack.isEmpty()
409                             || m_heap.m_parallelMarkersShouldExit;
410                     });
411                 
412                 // Is the current phase done? If so, return from this function.
413                 if (m_heap.m_parallelMarkersShouldExit)
414                     return;
415             }
416
417             m_stack.stealSomeCellsFrom(
418                 m_heap.m_sharedMarkStack, m_heap.m_numberOfWaitingParallelMarkers);
419             m_heap.m_numberOfActiveParallelMarkers++;
420             m_heap.m_numberOfWaitingParallelMarkers--;
421         }
422         
423         drain();
424     }
425 }
426
427 void SlotVisitor::addOpaqueRoot(void* root)
428 {
429     if (Options::numberOfGCMarkers() == 1) {
430         // Put directly into the shared HashSet.
431         m_heap.m_opaqueRoots.add(root);
432         return;
433     }
434     // Put into the local set, but merge with the shared one every once in
435     // a while to make sure that the local sets don't grow too large.
436     mergeOpaqueRootsIfProfitable();
437     m_opaqueRoots.add(root);
438 }
439
440 bool SlotVisitor::containsOpaqueRoot(void* root) const
441 {
442     ASSERT(!m_isInParallelMode);
443     ASSERT(m_opaqueRoots.isEmpty());
444     return m_heap.m_opaqueRoots.contains(root);
445 }
446
447 TriState SlotVisitor::containsOpaqueRootTriState(void* root) const
448 {
449     if (m_opaqueRoots.contains(root))
450         return TrueTriState;
451     std::lock_guard<Lock> lock(m_heap.m_opaqueRootsMutex);
452     if (m_heap.m_opaqueRoots.contains(root))
453         return TrueTriState;
454     return MixedTriState;
455 }
456
457 int SlotVisitor::opaqueRootCount()
458 {
459     ASSERT(!m_isInParallelMode);
460     ASSERT(m_opaqueRoots.isEmpty());
461     return m_heap.m_opaqueRoots.size();
462 }
463
464 void SlotVisitor::mergeOpaqueRootsIfNecessary()
465 {
466     if (m_opaqueRoots.isEmpty())
467         return;
468     mergeOpaqueRoots();
469 }
470     
471 void SlotVisitor::mergeOpaqueRootsIfProfitable()
472 {
473     if (static_cast<unsigned>(m_opaqueRoots.size()) < Options::opaqueRootMergeThreshold())
474         return;
475     mergeOpaqueRoots();
476 }
477     
478 void SlotVisitor::donate()
479 {
480     ASSERT(m_isInParallelMode);
481     if (Options::numberOfGCMarkers() == 1)
482         return;
483     
484     donateKnownParallel();
485 }
486
487 void SlotVisitor::donateAndDrain()
488 {
489     donate();
490     drain();
491 }
492
493 void SlotVisitor::copyLater(JSCell* owner, CopyToken token, void* ptr, size_t bytes)
494 {
495     ASSERT(bytes);
496     CopiedBlock* block = CopiedSpace::blockFor(ptr);
497     if (block->isOversize()) {
498         ASSERT(bytes <= block->size());
499         // FIXME: We should be able to shrink the allocation if bytes went below the block size.
500         // For now, we just make sure that our accounting of how much memory we are actually using
501         // is correct.
502         // https://bugs.webkit.org/show_bug.cgi?id=144749
503         bytes = block->size();
504         m_heap.m_storageSpace.pin(block);
505     }
506
507     ASSERT(heap()->m_storageSpace.contains(block));
508
509     LockHolder locker(&block->workListLock());
510     // We always report live bytes, except if during an eden collection we see an old object pointing to an
511     // old backing store and the old object is being marked because of the remembered set. Note that if we
512     // ask the object itself, it will always tell us that it's an old black object - because even during an
513     // eden collection we have already indicated that the object is old. That's why we use the
514     // SlotVisitor's cache of the object's old state.
515     if (heap()->operationInProgress() == FullCollection
516         || !block->isOld()
517         || m_currentObjectCellStateBeforeVisiting != CellState::OldGrey) {
518         m_bytesCopied += bytes;
519         block->reportLiveBytes(locker, owner, token, bytes);
520     }
521 }
522     
523 void SlotVisitor::mergeOpaqueRoots()
524 {
525     ASSERT(!m_opaqueRoots.isEmpty()); // Should only be called when opaque roots are non-empty.
526     {
527         std::lock_guard<Lock> lock(m_heap.m_opaqueRootsMutex);
528         for (auto* root : m_opaqueRoots)
529             m_heap.m_opaqueRoots.add(root);
530     }
531     m_opaqueRoots.clear();
532 }
533
534 void SlotVisitor::harvestWeakReferences()
535 {
536     for (WeakReferenceHarvester* current = m_heap.m_weakReferenceHarvesters.head(); current; current = current->next())
537         current->visitWeakReferences(*this);
538 }
539
540 void SlotVisitor::finalizeUnconditionalFinalizers()
541 {
542     while (m_heap.m_unconditionalFinalizers.hasNext())
543         m_heap.m_unconditionalFinalizers.removeNext()->finalizeUnconditionally();
544 }
545
546 void SlotVisitor::dump(PrintStream&) const
547 {
548     for (const JSCell* cell : markStack())
549         dataLog(*cell, "\n");
550 }
551
552 } // namespace JSC