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