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