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