Source/JavaScriptCore/heap/SlotVisitor.cpp

   1 /*
   2  * Copyright (C) 2012, 2015-2016 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  23  * THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "SlotVisitor.h"
  28
  29 #include "ConservativeRoots.h"
  30 #include "GCSegmentedArrayInlines.h"
  31 #include "HeapCellInlines.h"
  32 #include "HeapProfiler.h"
  33 #include "HeapSnapshotBuilder.h"
  34 #include "JSArray.h"
  35 #include "JSDestructibleObject.h"
  36 #include "JSObject.h"
  37 #include "JSString.h"
  38 #include "JSCInlines.h"
  39 #include "SlotVisitorInlines.h"
  40 #include "SuperSampler.h"
  41 #include "VM.h"
  42 #include <wtf/Lock.h>
  43
  44 namespace JSC {
  45
  46 #if ENABLE(GC_VALIDATION)
  47 static void validate(JSCell* cell)
  48 {
  49     RELEASE_ASSERT(cell);
  50
  51     if (!cell->structure()) {
  52         dataLogF("cell at %p has a null structure\n" , cell);
  53         CRASH();
  54     }
  55
  56     // Both the cell's structure, and the cell's structure's structure should be the Structure Structure.
  57     // I hate this sentence.
  58     if (cell->structure()->structure()->JSCell::classInfo() != cell->structure()->JSCell::classInfo()) {
  59         const char* parentClassName = 0;
  60         const char* ourClassName = 0;
  61         if (cell->structure()->structure() && cell->structure()->structure()->JSCell::classInfo())
  62             parentClassName = cell->structure()->structure()->JSCell::classInfo()->className;
  63         if (cell->structure()->JSCell::classInfo())
  64             ourClassName = cell->structure()->JSCell::classInfo()->className;
  65         dataLogF("parent structure (%p <%s>) of cell at %p doesn't match cell's structure (%p <%s>)\n",
  66             cell->structure()->structure(), parentClassName, cell, cell->structure(), ourClassName);
  67         CRASH();
  68     }
  69
  70     // Make sure we can walk the ClassInfo chain
  71     const ClassInfo* info = cell->classInfo();
  72     do { } while ((info = info->parentClass));
  73 }
  74 #endif
  75
  76 SlotVisitor::SlotVisitor(Heap& heap)
  77     : m_stack()
  78     , m_bytesVisited(0)
  79     , m_bytesCopied(0)
  80     , m_visitCount(0)
  81     , m_isInParallelMode(false)
  82     , m_markingVersion(MarkedSpace::initialVersion)
  83     , m_heap(heap)
  84 #if !ASSERT_DISABLED
  85     , m_isCheckingForDefaultMarkViolation(false)
  86     , m_isDraining(false)
  87 #endif
  88 {
  89 }
  90
  91 SlotVisitor::~SlotVisitor()
  92 {
  93     clearMarkStack();
  94 }
  95
  96 void SlotVisitor::didStartMarking()
  97 {
  98     if (heap()->operationInProgress() == FullCollection)
  99         ASSERT(m_opaqueRoots.isEmpty()); // Should have merged by now.
 100     else
 101         reset();
 102
 103     if (HeapProfiler* heapProfiler = vm().heapProfiler())
 104         m_heapSnapshotBuilder = heapProfiler->activeSnapshotBuilder();
 105
 106     m_markingVersion = heap()->objectSpace().markingVersion();
 107 }
 108
 109 void SlotVisitor::reset()
 110 {
 111     m_bytesVisited = 0;
 112     m_bytesCopied = 0;
 113     m_visitCount = 0;
 114     m_heapSnapshotBuilder = nullptr;
 115     ASSERT(!m_currentCell);
 116 }
 117
 118 void SlotVisitor::clearMarkStack()
 119 {
 120     m_stack.clear();
 121 }
 122
 123 void SlotVisitor::append(ConservativeRoots& conservativeRoots)
 124 {
 125     HeapCell** roots = conservativeRoots.roots();
 126     size_t size = conservativeRoots.size();
 127     for (size_t i = 0; i < size; ++i)
 128         appendJSCellOrAuxiliary(roots[i]);
 129 }
 130
 131 void SlotVisitor::appendJSCellOrAuxiliary(HeapCell* heapCell)
 132 {
 133     if (!heapCell)
 134         return;
 135
 136     ASSERT(!m_isCheckingForDefaultMarkViolation);
 137
 138     if (Heap::testAndSetMarked(m_markingVersion, heapCell))
 139         return;
 140
 141     switch (heapCell->cellKind()) {
 142     case HeapCell::JSCell: {
 143         JSCell* jsCell = static_cast<JSCell*>(heapCell);
 144
 145         if (!jsCell->structure()) {
 146             ASSERT_NOT_REACHED();
 147             return;
 148         }
 149
 150         jsCell->setCellState(CellState::NewGrey);
 151
 152         appendToMarkStack(jsCell);
 153         return;
 154     }
 155
 156     case HeapCell::Auxiliary: {
 157         noteLiveAuxiliaryCell(heapCell);
 158         return;
 159     } }
 160 }
 161
 162 void SlotVisitor::append(JSValue value)
 163 {
 164     if (!value || !value.isCell())
 165         return;
 166
 167     if (UNLIKELY(m_heapSnapshotBuilder))
 168         m_heapSnapshotBuilder->appendEdge(m_currentCell, value.asCell());
 169
 170     setMarkedAndAppendToMarkStack(value.asCell());
 171 }
 172
 173 void SlotVisitor::appendHidden(JSValue value)
 174 {
 175     if (!value || !value.isCell())
 176         return;
 177
 178     setMarkedAndAppendToMarkStack(value.asCell());
 179 }
 180
 181 void SlotVisitor::setMarkedAndAppendToMarkStack(JSCell* cell)
 182 {
 183     SuperSamplerScope superSamplerScope(false);
 184
 185     ASSERT(!m_isCheckingForDefaultMarkViolation);
 186     if (!cell)
 187         return;
 188
 189 #if ENABLE(GC_VALIDATION)
 190     validate(cell);
 191 #endif
 192
 193     //dataLog("    Marking ", RawPointer(cell), "\n");
 194
 195     if (cell->isLargeAllocation())
 196         setMarkedAndAppendToMarkStack(cell->largeAllocation(), cell);
 197     else
 198         setMarkedAndAppendToMarkStack(cell->markedBlock(), cell);
 199 }
 200
 201 template<typename ContainerType>
 202 ALWAYS_INLINE void SlotVisitor::setMarkedAndAppendToMarkStack(ContainerType& container, JSCell* cell)
 203 {
 204     container.aboutToMark(m_markingVersion);
 205
 206     if (container.testAndSetMarked(cell))
 207         return;
 208
 209     ASSERT(cell->structure());
 210
 211     // Indicate that the object is grey and that:
 212     // In case of concurrent GC: it's the first time it is grey in this GC cycle.
 213     // In case of eden collection: it's a new object that became grey rather than an old remembered object.
 214     cell->setCellState(CellState::NewGrey);
 215
 216     appendToMarkStack(container, cell);
 217 }
 218
 219 void SlotVisitor::appendToMarkStack(JSCell* cell)
 220 {
 221     if (cell->isLargeAllocation())
 222         appendToMarkStack(cell->largeAllocation(), cell);
 223     else
 224         appendToMarkStack(cell->markedBlock(), cell);
 225 }
 226
 227 template<typename ContainerType>
 228 ALWAYS_INLINE void SlotVisitor::appendToMarkStack(ContainerType& container, JSCell* cell)
 229 {
 230     ASSERT(Heap::isMarkedConcurrently(cell));
 231     ASSERT(!cell->isZapped());
 232
 233     container.noteMarked();
 234
 235     // FIXME: These "just work" because the GC resets these fields before doing anything else. But
 236     // that won't be the case when we do concurrent GC.
 237     m_visitCount++;
 238     m_bytesVisited += container.cellSize();
 239
 240     m_stack.append(cell);
 241
 242     if (UNLIKELY(m_heapSnapshotBuilder))
 243         m_heapSnapshotBuilder->appendNode(cell);
 244 }
 245
 246 void SlotVisitor::markAuxiliary(const void* base)
 247 {
 248     HeapCell* cell = bitwise_cast<HeapCell*>(base);
 249
 250     ASSERT(cell->heap() == heap());
 251
 252     if (Heap::testAndSetMarked(m_markingVersion, cell))
 253         return;
 254
 255     noteLiveAuxiliaryCell(cell);
 256 }
 257
 258 void SlotVisitor::noteLiveAuxiliaryCell(HeapCell* cell)
 259 {
 260     // We get here once per GC under these circumstances:
 261     //
 262     // Eden collection: if the cell was allocated since the last collection and is live somehow.
 263     //
 264     // Full collection: if the cell is live somehow.
 265
 266     CellContainer container = cell->cellContainer();
 267
 268     container.noteMarked();
 269
 270     m_visitCount++;
 271     m_bytesVisited += container.cellSize();
 272 }
 273
 274 class SetCurrentCellScope {
 275 public:
 276     SetCurrentCellScope(SlotVisitor& visitor, const JSCell* cell)
 277         : m_visitor(visitor)
 278     {
 279         ASSERT(!m_visitor.m_currentCell);
 280         m_visitor.m_currentCell = const_cast<JSCell*>(cell);
 281     }
 282
 283     ~SetCurrentCellScope()
 284     {
 285         ASSERT(m_visitor.m_currentCell);
 286         m_visitor.m_currentCell = nullptr;
 287     }
 288
 289 private:
 290     SlotVisitor& m_visitor;
 291 };
 292
 293
 294 ALWAYS_INLINE void SlotVisitor::visitChildren(const JSCell* cell)
 295 {
 296     ASSERT(Heap::isMarkedConcurrently(cell));
 297
 298     SetCurrentCellScope currentCellScope(*this, cell);
 299
 300     cell->setCellState(blacken(cell->cellState()));
 301
 302     // FIXME: Make this work on ARM also.
 303     // https://bugs.webkit.org/show_bug.cgi?id=162461
 304     if (isX86())
 305         WTF::storeLoadFence();
 306
 307     switch (cell->type()) {
 308     case StringType:
 309         JSString::visitChildren(const_cast<JSCell*>(cell), *this);
 310         break;
 311
 312     case FinalObjectType:
 313         JSFinalObject::visitChildren(const_cast<JSCell*>(cell), *this);
 314         break;
 315
 316     case ArrayType:
 317         JSArray::visitChildren(const_cast<JSCell*>(cell), *this);
 318         break;
 319
 320     default:
 321         // FIXME: This could be so much better.
 322         // https://bugs.webkit.org/show_bug.cgi?id=162462
 323         cell->methodTable()->visitChildren(const_cast<JSCell*>(cell), *this);
 324         break;
 325     }
 326 }
 327
 328 void SlotVisitor::donateKnownParallel()
 329 {
 330     // NOTE: Because we re-try often, we can afford to be conservative, and
 331     // assume that donating is not profitable.
 332
 333     // Avoid locking when a thread reaches a dead end in the object graph.
 334     if (m_stack.size() < 2)
 335         return;
 336
 337     // If there's already some shared work queued up, be conservative and assume
 338     // that donating more is not profitable.
 339     if (m_heap.m_sharedMarkStack.size())
 340         return;
 341
 342     // If we're contending on the lock, be conservative and assume that another
 343     // thread is already donating.
 344     std::unique_lock<Lock> lock(m_heap.m_markingMutex, std::try_to_lock);
 345     if (!lock.owns_lock())
 346         return;
 347
 348     // Otherwise, assume that a thread will go idle soon, and donate.
 349     m_stack.donateSomeCellsTo(m_heap.m_sharedMarkStack);
 350
 351     m_heap.m_markingConditionVariable.notifyAll();
 352 }
 353
 354 void SlotVisitor::drain()
 355 {
 356     ASSERT(m_isInParallelMode);
 357
 358     while (!m_stack.isEmpty()) {
 359         m_stack.refill();
 360         for (unsigned countdown = Options::minimumNumberOfScansBetweenRebalance(); m_stack.canRemoveLast() && countdown--;)
 361             visitChildren(m_stack.removeLast());
 362         donateKnownParallel();
 363     }
 364
 365     mergeOpaqueRootsIfNecessary();
 366 }
 367
 368 void SlotVisitor::drainFromShared(SharedDrainMode sharedDrainMode)
 369 {
 370     ASSERT(m_isInParallelMode);
 371
 372     ASSERT(Options::numberOfGCMarkers());
 373
 374     {
 375         std::lock_guard<Lock> lock(m_heap.m_markingMutex);
 376         m_heap.m_numberOfActiveParallelMarkers++;
 377     }
 378     while (true) {
 379         {
 380             std::unique_lock<Lock> lock(m_heap.m_markingMutex);
 381             m_heap.m_numberOfActiveParallelMarkers--;
 382             m_heap.m_numberOfWaitingParallelMarkers++;
 383
 384             // How we wait differs depending on drain mode.
 385             if (sharedDrainMode == MasterDrain) {
 386                 // Wait until either termination is reached, or until there is some work
 387                 // for us to do.
 388                 while (true) {
 389                     // Did we reach termination?
 390                     if (!m_heap.m_numberOfActiveParallelMarkers
 391                         && m_heap.m_sharedMarkStack.isEmpty()) {
 392                         // Let any sleeping slaves know it's time for them to return;
 393                         m_heap.m_markingConditionVariable.notifyAll();
 394                         return;
 395                     }
 396
 397                     // Is there work to be done?
 398                     if (!m_heap.m_sharedMarkStack.isEmpty())
 399                         break;
 400
 401                     // Otherwise wait.
 402                     m_heap.m_markingConditionVariable.wait(lock);
 403                 }
 404             } else {
 405                 ASSERT(sharedDrainMode == SlaveDrain);
 406
 407                 // Did we detect termination? If so, let the master know.
 408                 if (!m_heap.m_numberOfActiveParallelMarkers
 409                     && m_heap.m_sharedMarkStack.isEmpty())
 410                     m_heap.m_markingConditionVariable.notifyAll();
 411
 412                 m_heap.m_markingConditionVariable.wait(
 413                     lock,
 414                     [this] {
 415                         return !m_heap.m_sharedMarkStack.isEmpty()
 416                             || m_heap.m_parallelMarkersShouldExit;
 417                     });
 418
 419                 // Is the current phase done? If so, return from this function.
 420                 if (m_heap.m_parallelMarkersShouldExit)
 421                     return;
 422             }
 423
 424             m_stack.stealSomeCellsFrom(
 425                 m_heap.m_sharedMarkStack, m_heap.m_numberOfWaitingParallelMarkers);
 426             m_heap.m_numberOfActiveParallelMarkers++;
 427             m_heap.m_numberOfWaitingParallelMarkers--;
 428         }
 429
 430         drain();
 431     }
 432 }
 433
 434 void SlotVisitor::addOpaqueRoot(void* root)
 435 {
 436     if (Options::numberOfGCMarkers() == 1) {
 437         // Put directly into the shared HashSet.
 438         m_heap.m_opaqueRoots.add(root);
 439         return;
 440     }
 441     // Put into the local set, but merge with the shared one every once in
 442     // a while to make sure that the local sets don't grow too large.
 443     mergeOpaqueRootsIfProfitable();
 444     m_opaqueRoots.add(root);
 445 }
 446
 447 bool SlotVisitor::containsOpaqueRoot(void* root) const
 448 {
 449     ASSERT(!m_isInParallelMode);
 450     ASSERT(m_opaqueRoots.isEmpty());
 451     return m_heap.m_opaqueRoots.contains(root);
 452 }
 453
 454 TriState SlotVisitor::containsOpaqueRootTriState(void* root) const
 455 {
 456     if (m_opaqueRoots.contains(root))
 457         return TrueTriState;
 458     std::lock_guard<Lock> lock(m_heap.m_opaqueRootsMutex);
 459     if (m_heap.m_opaqueRoots.contains(root))
 460         return TrueTriState;
 461     return MixedTriState;
 462 }
 463
 464 int SlotVisitor::opaqueRootCount()
 465 {
 466     ASSERT(!m_isInParallelMode);
 467     ASSERT(m_opaqueRoots.isEmpty());
 468     return m_heap.m_opaqueRoots.size();
 469 }
 470
 471 void SlotVisitor::mergeOpaqueRootsIfNecessary()
 472 {
 473     if (m_opaqueRoots.isEmpty())
 474         return;
 475     mergeOpaqueRoots();
 476 }
 477
 478 void SlotVisitor::mergeOpaqueRootsIfProfitable()
 479 {
 480     if (static_cast<unsigned>(m_opaqueRoots.size()) < Options::opaqueRootMergeThreshold())
 481         return;
 482     mergeOpaqueRoots();
 483 }
 484
 485 void SlotVisitor::donate()
 486 {
 487     ASSERT(m_isInParallelMode);
 488     if (Options::numberOfGCMarkers() == 1)
 489         return;
 490
 491     donateKnownParallel();
 492 }
 493
 494 void SlotVisitor::donateAndDrain()
 495 {
 496     donate();
 497     drain();
 498 }
 499
 500 void SlotVisitor::mergeOpaqueRoots()
 501 {
 502     ASSERT(!m_opaqueRoots.isEmpty()); // Should only be called when opaque roots are non-empty.
 503     {
 504         std::lock_guard<Lock> lock(m_heap.m_opaqueRootsMutex);
 505         for (auto* root : m_opaqueRoots)
 506             m_heap.m_opaqueRoots.add(root);
 507     }
 508     m_opaqueRoots.clear();
 509 }
 510
 511 void SlotVisitor::harvestWeakReferences()
 512 {
 513     for (WeakReferenceHarvester* current = m_heap.m_weakReferenceHarvesters.head(); current; current = current->next())
 514         current->visitWeakReferences(*this);
 515 }
 516
 517 void SlotVisitor::finalizeUnconditionalFinalizers()
 518 {
 519     while (m_heap.m_unconditionalFinalizers.hasNext())
 520         m_heap.m_unconditionalFinalizers.removeNext()->finalizeUnconditionally();
 521 }
 522
 523 void SlotVisitor::dump(PrintStream&) const
 524 {
 525     for (const JSCell* cell : markStack())
 526         dataLog(*cell, "\n");
 527 }
 528
 529 } // namespace JSC