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