Unreviewed, rolling out r161540.
[WebKit.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 "Operations.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     ASSERT(m_stack.isEmpty());
37 }
38
39 void SlotVisitor::setup()
40 {
41     m_shared.m_shouldHashCons = m_shared.m_vm->haveEnoughNewStringsToHashCons();
42     m_shouldHashCons = m_shared.m_shouldHashCons;
43 #if ENABLE(PARALLEL_GC)
44     for (unsigned i = 0; i < m_shared.m_gcThreads.size(); ++i)
45         m_shared.m_gcThreads[i]->slotVisitor()->m_shouldHashCons = m_shared.m_shouldHashCons;
46 #endif
47 }
48
49 void SlotVisitor::reset()
50 {
51     m_bytesVisited = 0;
52     m_bytesCopied = 0;
53     m_visitCount = 0;
54     ASSERT(m_stack.isEmpty());
55 #if ENABLE(PARALLEL_GC)
56     ASSERT(m_opaqueRoots.isEmpty()); // Should have merged by now.
57 #else
58     m_opaqueRoots.clear();
59 #endif
60     if (m_shouldHashCons) {
61         m_uniqueStrings.clear();
62         m_shouldHashCons = false;
63     }
64 }
65
66 void SlotVisitor::append(ConservativeRoots& conservativeRoots)
67 {
68     StackStats::probe();
69     JSCell** roots = conservativeRoots.roots();
70     size_t size = conservativeRoots.size();
71     for (size_t i = 0; i < size; ++i)
72         internalAppend(0, roots[i]);
73 }
74
75 ALWAYS_INLINE static void visitChildren(SlotVisitor& visitor, const JSCell* cell)
76 {
77     StackStats::probe();
78
79     ASSERT(Heap::isMarked(cell));
80     
81     if (isJSString(cell)) {
82         JSString::visitChildren(const_cast<JSCell*>(cell), visitor);
83         return;
84     }
85
86     if (isJSFinalObject(cell)) {
87         JSFinalObject::visitChildren(const_cast<JSCell*>(cell), visitor);
88         return;
89     }
90
91     if (isJSArray(cell)) {
92         JSArray::visitChildren(const_cast<JSCell*>(cell), visitor);
93         return;
94     }
95
96     cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), visitor);
97 }
98
99 void SlotVisitor::donateKnownParallel()
100 {
101     StackStats::probe();
102     // NOTE: Because we re-try often, we can afford to be conservative, and
103     // assume that donating is not profitable.
104
105     // Avoid locking when a thread reaches a dead end in the object graph.
106     if (m_stack.size() < 2)
107         return;
108
109     // If there's already some shared work queued up, be conservative and assume
110     // that donating more is not profitable.
111     if (m_shared.m_sharedMarkStack.size())
112         return;
113
114     // If we're contending on the lock, be conservative and assume that another
115     // thread is already donating.
116     MutexTryLocker locker(m_shared.m_markingLock);
117     if (!locker.locked())
118         return;
119
120     // Otherwise, assume that a thread will go idle soon, and donate.
121     m_stack.donateSomeCellsTo(m_shared.m_sharedMarkStack);
122
123     if (m_shared.m_numberOfActiveParallelMarkers < Options::numberOfGCMarkers())
124         m_shared.m_markingCondition.broadcast();
125 }
126
127 void SlotVisitor::drain()
128 {
129     StackStats::probe();
130     ASSERT(m_isInParallelMode);
131    
132 #if ENABLE(PARALLEL_GC)
133     if (Options::numberOfGCMarkers() > 1) {
134         while (!m_stack.isEmpty()) {
135             m_stack.refill();
136             for (unsigned countdown = Options::minimumNumberOfScansBetweenRebalance(); m_stack.canRemoveLast() && countdown--;)
137                 visitChildren(*this, m_stack.removeLast());
138             donateKnownParallel();
139         }
140         
141         mergeOpaqueRootsIfNecessary();
142         return;
143     }
144 #endif
145     
146     while (!m_stack.isEmpty()) {
147         m_stack.refill();
148         while (m_stack.canRemoveLast())
149             visitChildren(*this, m_stack.removeLast());
150     }
151 }
152
153 void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
154 {
155     StackStats::probe();
156     ASSERT(m_isInParallelMode);
157     
158     ASSERT(Options::numberOfGCMarkers());
159     
160     bool shouldBeParallel;
161
162 #if ENABLE(PARALLEL_GC)
163     shouldBeParallel = Options::numberOfGCMarkers() > 1;
164 #else
165     ASSERT(Options::numberOfGCMarkers() == 1);
166     shouldBeParallel = false;
167 #endif
168     
169     if (!shouldBeParallel) {
170         // This call should be a no-op.
171         ASSERT_UNUSED(sharedDrainMode, sharedDrainMode == MasterDrain);
172         ASSERT(m_stack.isEmpty());
173         ASSERT(m_shared.m_sharedMarkStack.isEmpty());
174         return;
175     }
176     
177 #if ENABLE(PARALLEL_GC)
178     {
179         MutexLocker locker(m_shared.m_markingLock);
180         m_shared.m_numberOfActiveParallelMarkers++;
181     }
182     while (true) {
183         {
184             MutexLocker locker(m_shared.m_markingLock);
185             m_shared.m_numberOfActiveParallelMarkers--;
186
187             // How we wait differs depending on drain mode.
188             if (sharedDrainMode == MasterDrain) {
189                 // Wait until either termination is reached, or until there is some work
190                 // for us to do.
191                 while (true) {
192                     // Did we reach termination?
193                     if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty()) {
194                         // Let any sleeping slaves know it's time for them to return;
195                         m_shared.m_markingCondition.broadcast();
196                         return;
197                     }
198                     
199                     // Is there work to be done?
200                     if (!m_shared.m_sharedMarkStack.isEmpty())
201                         break;
202                     
203                     // Otherwise wait.
204                     m_shared.m_markingCondition.wait(m_shared.m_markingLock);
205                 }
206             } else {
207                 ASSERT(sharedDrainMode == SlaveDrain);
208                 
209                 // Did we detect termination? If so, let the master know.
210                 if (!m_shared.m_numberOfActiveParallelMarkers && m_shared.m_sharedMarkStack.isEmpty())
211                     m_shared.m_markingCondition.broadcast();
212                 
213                 while (m_shared.m_sharedMarkStack.isEmpty() && !m_shared.m_parallelMarkersShouldExit)
214                     m_shared.m_markingCondition.wait(m_shared.m_markingLock);
215                 
216                 // Is the current phase done? If so, return from this function.
217                 if (m_shared.m_parallelMarkersShouldExit)
218                     return;
219             }
220            
221             size_t idleThreadCount = Options::numberOfGCMarkers() - m_shared.m_numberOfActiveParallelMarkers;
222             m_stack.stealSomeCellsFrom(m_shared.m_sharedMarkStack, idleThreadCount);
223             m_shared.m_numberOfActiveParallelMarkers++;
224         }
225         
226         drain();
227     }
228 #endif
229 }
230
231 void SlotVisitor::mergeOpaqueRoots()
232 {
233     StackStats::probe();
234     ASSERT(!m_opaqueRoots.isEmpty()); // Should only be called when opaque roots are non-empty.
235     {
236         MutexLocker locker(m_shared.m_opaqueRootsLock);
237         HashSet<void*>::iterator begin = m_opaqueRoots.begin();
238         HashSet<void*>::iterator end = m_opaqueRoots.end();
239         for (HashSet<void*>::iterator iter = begin; iter != end; ++iter)
240             m_shared.m_opaqueRoots.add(*iter);
241     }
242     m_opaqueRoots.clear();
243 }
244
245 ALWAYS_INLINE bool JSString::tryHashConsLock()
246 {
247 #if ENABLE(PARALLEL_GC)
248     unsigned currentFlags = m_flags;
249
250     if (currentFlags & HashConsLock)
251         return false;
252
253     unsigned newFlags = currentFlags | HashConsLock;
254
255     if (!WTF::weakCompareAndSwap(&m_flags, currentFlags, newFlags))
256         return false;
257
258     WTF::memoryBarrierAfterLock();
259     return true;
260 #else
261     if (isHashConsSingleton())
262         return false;
263
264     m_flags |= HashConsLock;
265
266     return true;
267 #endif
268 }
269
270 ALWAYS_INLINE void JSString::releaseHashConsLock()
271 {
272 #if ENABLE(PARALLEL_GC)
273     WTF::memoryBarrierBeforeUnlock();
274 #endif
275     m_flags &= ~HashConsLock;
276 }
277
278 ALWAYS_INLINE bool JSString::shouldTryHashCons()
279 {
280     return ((length() > 1) && !isRope() && !isHashConsSingleton());
281 }
282
283 ALWAYS_INLINE void SlotVisitor::internalAppend(void* from, JSValue* slot)
284 {
285     // This internalAppend is only intended for visits to object and array backing stores.
286     // as it can change the JSValue pointed to be the argument when the original JSValue
287     // is a string that contains the same contents as another string.
288
289     StackStats::probe();
290     ASSERT(slot);
291     JSValue value = *slot;
292     ASSERT(value);
293     if (!value.isCell())
294         return;
295
296     JSCell* cell = value.asCell();
297     if (!cell)
298         return;
299
300     validate(cell);
301
302     if (m_shouldHashCons && cell->isString()) {
303         JSString* string = jsCast<JSString*>(cell);
304         if (string->shouldTryHashCons() && string->tryHashConsLock()) {
305             UniqueStringMap::AddResult addResult = m_uniqueStrings.add(string->string().impl(), value);
306             if (addResult.isNewEntry)
307                 string->setHashConsSingleton();
308             else {
309                 JSValue existingJSValue = addResult.iterator->value;
310                 if (value != existingJSValue)
311                     jsCast<JSString*>(existingJSValue.asCell())->clearHashConsSingleton();
312                 *slot = existingJSValue;
313                 string->releaseHashConsLock();
314                 return;
315             }
316             string->releaseHashConsLock();
317         }
318     }
319
320     internalAppend(from, cell);
321 }
322
323 void SlotVisitor::harvestWeakReferences()
324 {
325     StackStats::probe();
326     for (WeakReferenceHarvester* current = m_shared.m_weakReferenceHarvesters.head(); current; current = current->next())
327         current->visitWeakReferences(*this);
328 }
329
330 void SlotVisitor::finalizeUnconditionalFinalizers()
331 {
332     StackStats::probe();
333     while (m_shared.m_unconditionalFinalizers.hasNext())
334         m_shared.m_unconditionalFinalizers.removeNext()->finalizeUnconditionally();
335 }
336
337 #if ENABLE(GC_VALIDATION)
338 void SlotVisitor::validate(JSCell* cell)
339 {
340     RELEASE_ASSERT(cell);
341
342     if (!cell->structure()) {
343         dataLogF("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         dataLogF("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