1#include "config.h"
2#include "SlotVisitor.h"
3#include "SlotVisitorInlines.h"
4
5#include "ConservativeRoots.h"
6#include "CopiedSpace.h"
7#include "CopiedSpaceInlines.h"
8#include "GCThread.h"
9#include "JSArray.h"
10#include "JSDestructibleObject.h"
11#include "VM.h"
12#include "JSObject.h"
13#include "JSString.h"
14#include "JSCInlines.h"
15#include <wtf/StackStats.h>
16
17namespace JSC {
18
19SlotVisitor::SlotVisitor(GCThreadSharedData& shared)
20    : m_stack(shared.m_vm->heap.blockAllocator())
21    , m_bytesVisited(0)
22    , m_bytesCopied(0)
23    , m_visitCount(0)
24    , m_isInParallelMode(false)
25    , m_shared(shared)
26    , m_shouldHashCons(false)
27#if !ASSERT_DISABLED
28    , m_isCheckingForDefaultMarkViolation(false)
29    , m_isDraining(false)
30#endif
31{
32}
33
34SlotVisitor::~SlotVisitor()
35{
36    clearMarkStack();
37}
38
39void SlotVisitor::didStartMarking()
40{
41    if (heap()->operationInProgress() == FullCollection) {
42#if ENABLE(PARALLEL_GC)
43        ASSERT(m_opaqueRoots.isEmpty()); // Should have merged by now.
44#else
45        m_opaqueRoots.clear();
46#endif
47    }
48
49    m_shared.m_shouldHashCons = m_shared.m_vm->haveEnoughNewStringsToHashCons();
50    m_shouldHashCons = m_shared.m_shouldHashCons;
51#if ENABLE(PARALLEL_GC)
52    for (unsigned i = 0; i < m_shared.m_gcThreads.size(); ++i)
53        m_shared.m_gcThreads[i]->slotVisitor()->m_shouldHashCons = m_shared.m_shouldHashCons;
54#endif
55}
56
57void SlotVisitor::reset()
58{
59    m_bytesVisited = 0;
60    m_bytesCopied = 0;
61    m_visitCount = 0;
62    ASSERT(m_stack.isEmpty());
63    if (m_shouldHashCons) {
64        m_uniqueStrings.clear();
65        m_shouldHashCons = false;
66    }
67}
68
69void SlotVisitor::clearMarkStack()
70{
71    m_stack.clear();
72}
73
74void SlotVisitor::append(ConservativeRoots& conservativeRoots)
75{
76    StackStats::probe();
77    JSCell** roots = conservativeRoots.roots();
78    size_t size = conservativeRoots.size();
79    for (size_t i = 0; i < size; ++i)
80        internalAppend(0, roots[i]);
81}
82
83ALWAYS_INLINE static void visitChildren(SlotVisitor& visitor, const JSCell* cell)
84{
85    StackStats::probe();
86
87    ASSERT(Heap::isMarked(cell));
88
89    if (isJSString(cell)) {
90        JSString::visitChildren(const_cast<JSCell*>(cell), visitor);
91        return;
92    }
93
94    if (isJSFinalObject(cell)) {
95        JSFinalObject::visitChildren(const_cast<JSCell*>(cell), visitor);
96        return;
97    }
98
99    if (isJSArray(cell)) {
100        JSArray::visitChildren(const_cast<JSCell*>(cell), visitor);
101        return;
102    }
103
104    cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), visitor);
105}
106
107void SlotVisitor::donateKnownParallel()
108{
109    StackStats::probe();
110    // NOTE: Because we re-try often, we can afford to be conservative, and
111    // assume that donating is not profitable.
112
113    // Avoid locking when a thread reaches a dead end in the object graph.
114    if (m_stack.size() < 2)
115        return;
116
117    // If there's already some shared work queued up, be conservative and assume
118    // that donating more is not profitable.
119    if (m_shared.m_sharedMarkStack.size())
120        return;
121
122    // If we're contending on the lock, be conservative and assume that another
123    // thread is already donating.
124    std::unique_lock<std::mutex> lock(m_shared.m_markingMutex, std::try_to_lock);
125    if (!lock.owns_lock())
126        return;
127
128    // Otherwise, assume that a thread will go idle soon, and donate.
129    m_stack.donateSomeCellsTo(m_shared.m_sharedMarkStack);
130
131    if (m_shared.m_numberOfActiveParallelMarkers < Options::numberOfGCMarkers())
132        m_shared.m_markingConditionVariable.notify_all();
133}
134
135void SlotVisitor::drain()
136{
137    StackStats::probe();
138    ASSERT(m_isInParallelMode);
139
140#if ENABLE(PARALLEL_GC)
141    if (Options::numberOfGCMarkers() > 1) {
142        while (!m_stack.isEmpty()) {
143            m_stack.refill();
144            for (unsigned countdown = Options::minimumNumberOfScansBetweenRebalance(); m_stack.canRemoveLast() && countdown--;)
145                visitChildren(*this, m_stack.removeLast());
146            donateKnownParallel();
147        }
148
149        mergeOpaqueRootsIfNecessary();
150        return;
151    }
152#endif
153
154    while (!m_stack.isEmpty()) {
155        m_stack.refill();
156        while (m_stack.canRemoveLast())
157            visitChildren(*this, m_stack.removeLast());
158    }
159}
160
161void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
162{
163    StackStats::probe();
164    ASSERT(m_isInParallelMode);
165
166    ASSERT(Options::numberOfGCMarkers());
167
168    bool shouldBeParallel;
169
170#if ENABLE(PARALLEL_GC)
171    shouldBeParallel = Options::numberOfGCMarkers() > 1;
172#else
173    ASSERT(Options::numberOfGCMarkers() == 1);
174    shouldBeParallel = false;
175#endif
176
177    if (!shouldBeParallel) {
178        // This call should be a no-op.
179        ASSERT_UNUSED(sharedDrainMode, sharedDrainMode == MasterDrain);
180        ASSERT(m_stack.isEmpty());
181        ASSERT(m_shared.m_sharedMarkStack.isEmpty());
182        return;
183    }
184
185#if ENABLE(PARALLEL_GC)
186    {
187        std::lock_guard<std::mutex> lock(m_shared.m_markingMutex);
188        m_shared.m_numberOfActiveParallelMarkers++;
189    }
190    while (true) {
191        {
192            std::unique_lock<std::mutex> lock(m_shared.m_markingMutex);
193            m_shared.m_numberOfActiveParallelMarkers--;
194
195            // How we wait differs depending on drain mode.
196            if (sharedDrainMode == MasterDrain) {
197                // Wait until either termination is reached, or until there is some work
198                // for us to do.
199                while (true) {
200                    // Did we reach termination?
201                    if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty()) {
202                        // Let any sleeping slaves know it's time for them to return;
203                        m_shared.m_markingConditionVariable.notify_all();
204                        return;
205                    }
206
207                    // Is there work to be done?
208                    if (!m_shared.m_sharedMarkStack.isEmpty())
209                        break;
210
211                    // Otherwise wait.
212                    m_shared.m_markingConditionVariable.wait(lock);
213                }
214            } else {
215                ASSERT(sharedDrainMode == SlaveDrain);
216
217                // Did we detect termination? If so, let the master know.
218                if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty())
219                    m_shared.m_markingConditionVariable.notify_all();
220
221                m_shared.m_markingConditionVariable.wait(lock, [this] { return !m_shared.m_sharedMarkStack.isEmpty() || m_shared.m_parallelMarkersShouldExit; });
222
223                // Is the current phase done? If so, return from this function.
224                if (m_shared.m_parallelMarkersShouldExit)
225                    return;
226            }
227
228            size_t idleThreadCount = Options::numberOfGCMarkers() - m_shared.m_numberOfActiveParallelMarkers;
229            m_stack.stealSomeCellsFrom(m_shared.m_sharedMarkStack, idleThreadCount);
230            m_shared.m_numberOfActiveParallelMarkers++;
231        }
232
233        drain();
234    }
235#endif
236}
237
238void SlotVisitor::mergeOpaqueRoots()
239{
240    StackStats::probe();
241    ASSERT(!m_opaqueRoots.isEmpty()); // Should only be called when opaque roots are non-empty.
242    {
243        std::lock_guard<std::mutex> lock(m_shared.m_opaqueRootsMutex);
244        for (auto* root : m_opaqueRoots)
245            m_shared.m_opaqueRoots.add(root);
246    }
247    m_opaqueRoots.clear();
248}
249
250ALWAYS_INLINE bool JSString::tryHashConsLock()
251{
252#if ENABLE(PARALLEL_GC)
253    unsigned currentFlags = m_flags;
254
255    if (currentFlags & HashConsLock)
256        return false;
257
258    unsigned newFlags = currentFlags | HashConsLock;
259
260    if (!WTF::weakCompareAndSwap(&m_flags, currentFlags, newFlags))
261        return false;
262
263    WTF::memoryBarrierAfterLock();
264    return true;
265#else
266    if (isHashConsSingleton())
267        return false;
268
269    m_flags |= HashConsLock;
270
271    return true;
272#endif
273}
274
275ALWAYS_INLINE void JSString::releaseHashConsLock()
276{
277#if ENABLE(PARALLEL_GC)
278    WTF::memoryBarrierBeforeUnlock();
279#endif
280    m_flags &= ~HashConsLock;
281}
282
283ALWAYS_INLINE bool JSString::shouldTryHashCons()
284{
285    return ((length() > 1) && !isRope() && !isHashConsSingleton());
286}
287
288ALWAYS_INLINE void SlotVisitor::internalAppend(void* from, JSValue* slot)
289{
290    // This internalAppend is only intended for visits to object and array backing stores.
291    // as it can change the JSValue pointed to be the argument when the original JSValue
292    // is a string that contains the same contents as another string.
293
294    StackStats::probe();
295    ASSERT(slot);
296    JSValue value = *slot;
297    ASSERT(value);
298    if (!value.isCell())
299        return;
300
301    JSCell* cell = value.asCell();
302    if (!cell)
303        return;
304
305    validate(cell);
306
307    if (m_shouldHashCons && cell->isString()) {
308        JSString* string = jsCast<JSString*>(cell);
309        if (string->shouldTryHashCons() && string->tryHashConsLock()) {
310            UniqueStringMap::AddResult addResult = m_uniqueStrings.add(string->string().impl(), value);
311            if (addResult.isNewEntry)
312                string->setHashConsSingleton();
313            else {
314                JSValue existingJSValue = addResult.iterator->value;
315                if (value != existingJSValue)
316                    jsCast<JSString*>(existingJSValue.asCell())->clearHashConsSingleton();
317                *slot = existingJSValue;
318                string->releaseHashConsLock();
319                return;
320            }
321            string->releaseHashConsLock();
322        }
323    }
324
325    internalAppend(from, cell);
326}
327
328void SlotVisitor::harvestWeakReferences()
329{
330    StackStats::probe();
331    for (WeakReferenceHarvester* current = m_shared.m_weakReferenceHarvesters.head(); current; current = current->next())
332        current->visitWeakReferences(*this);
333}
334
335void SlotVisitor::finalizeUnconditionalFinalizers()
336{
337    StackStats::probe();
338    while (m_shared.m_unconditionalFinalizers.hasNext())
339        m_shared.m_unconditionalFinalizers.removeNext()->finalizeUnconditionally();
340}
341
342#if ENABLE(GC_VALIDATION)
343void SlotVisitor::validate(JSCell* cell)
344{
345    RELEASE_ASSERT(cell);
346
347    if (!cell->structure()) {
348        dataLogF("cell at %p has a null structure\n" , cell);
349        CRASH();
350    }
351
352    // Both the cell's structure, and the cell's structure's structure should be the Structure Structure.
353    // I hate this sentence.
354    if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo()) {
355        const char* parentClassName = 0;
356        const char* ourClassName = 0;
357        if (cell->structure()->structure() && cell->structure()->structure()->JSCell::classInfo())
358            parentClassName = cell->structure()->structure()->JSCell::classInfo()->className;
359        if (cell->structure()->JSCell::classInfo())
360            ourClassName = cell->structure()->JSCell::classInfo()->className;
361        dataLogF("parent structure (%p <%s>) of cell at %p doesn't match cell's structure (%p <%s>)\n",
362                cell->structure()->structure(), parentClassName, cell, cell->structure(), ourClassName);
363        CRASH();
364    }
365
366    // Make sure we can walk the ClassInfo chain
367    const ClassInfo* info = cell->classInfo();
368    do { } while ((info = info->parentClass));
369}
370#else
371void SlotVisitor::validate(JSCell*)
372{
373}
374#endif
375
376void SlotVisitor::dump(PrintStream&) const
377{
378    for (const JSCell* cell : markStack())
379        dataLog(*cell, "\n");
380}
381
382} // namespace JSC
383