d45c381aac444a76ae56619b1360fb3bb8b600b0
[WebKit-https.git] / Source / JavaScriptCore / heap / SlotVisitor.cpp
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
17 namespace JSC {
18
19 SlotVisitor::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
34 SlotVisitor::~SlotVisitor()
35 {
36     clearMarkStack();
37 }
38
39 void 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
57 void 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
69 void SlotVisitor::clearMarkStack()
70 {
71     m_stack.clear();
72 }
73
74 void 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
83 ALWAYS_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
107 void 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
135 void 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
161 void 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
238 void 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
250 ALWAYS_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
275 ALWAYS_INLINE void JSString::releaseHashConsLock()
276 {
277 #if ENABLE(PARALLEL_GC)
278     WTF::memoryBarrierBeforeUnlock();
279 #endif
280     m_flags &= ~HashConsLock;
281 }
282
283 ALWAYS_INLINE bool JSString::shouldTryHashCons()
284 {
285     return ((length() > 1) && !isRope() && !isHashConsSingleton());
286 }
287
288 ALWAYS_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
328 void 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
335 void 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)
343 void 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
371 void SlotVisitor::validate(JSCell*)
372 {
373 }
374 #endif
375
376 void SlotVisitor::dump(PrintStream&) const
377 {
378     for (const JSCell* cell : markStack())
379         dataLog(*cell, "\n");
380 }
381
382 } // namespace JSC