Bug 1463462 - Parition the mark stack into black and gray entries r=sfink
authorJon Coppeard <jcoppeard@mozilla.com>
Thu, 06 Dec 2018 16:27:22 -0500
changeset 450667 3e7a4e085ead5b20172ee33e4809770dd124a8f7
parent 450666 37a9521cad270889c718a62ccf048a14180b0172
child 450668 6ae14f44b4af53cb2ecf23eb5077ab90d1615ea9
push id110516
push userjcoppeard@mozilla.com
push dateFri, 14 Dec 2018 14:22:31 +0000
treeherdermozilla-inbound@fd4d12eb1b97 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1463462
milestone66.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1463462 - Parition the mark stack into black and gray entries r=sfink
js/src/gc/GC.cpp
js/src/gc/GCMarker.h
js/src/gc/Marking.cpp
--- a/js/src/gc/GC.cpp
+++ b/js/src/gc/GC.cpp
@@ -4456,16 +4456,18 @@ void GCRuntime::markWeakReferences(gcsta
 }
 
 void GCRuntime::markWeakReferencesInCurrentGroup(gcstats::PhaseKind phase) {
   markWeakReferences<SweepGroupZonesIter>(phase);
 }
 
 template <class ZoneIterT>
 void GCRuntime::markGrayReferences(gcstats::PhaseKind phase) {
+  MOZ_ASSERT(marker.markColor() == MarkColor::Gray);
+
   gcstats::AutoPhase ap(stats(), phase);
   if (hasValidGrayRootsBuffer()) {
     for (ZoneIterT zone(rt); !zone.done(); zone.next()) {
       markBufferedGrayRoots(zone);
     }
   } else {
     MOZ_ASSERT(!isIncremental);
     if (JSTraceDataOp op = grayRootTracer.op) {
@@ -5237,16 +5239,18 @@ static inline void MaybeCheckWeakMapMark
     }
   }
 
 #endif
 }
 
 IncrementalProgress GCRuntime::endMarkingSweepGroup(FreeOp* fop,
                                                     SliceBudget& budget) {
+  MOZ_ASSERT(marker.markColor() == MarkColor::Black);
+
   gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::SWEEP_MARK);
 
   // Mark any incoming black pointers from previously swept compartments
   // whose referents are not marked. This can occur when gray cells become
   // black by the action of UnmarkGray.
   markIncomingCrossCompartmentPointers(MarkColor::Black);
   markWeakReferencesInCurrentGroup(gcstats::PhaseKind::SWEEP_MARK_WEAK);
 
@@ -7087,16 +7091,17 @@ void GCRuntime::incrementalSlice(
 
     case State::Finish:
       finishCollection();
       incrementalState = State::NotActive;
       break;
   }
 
   MOZ_ASSERT(safeToYield);
+  MOZ_ASSERT(marker.markColor() == MarkColor::Black);
 }
 
 gc::AbortReason gc::IsIncrementalGCUnsafe(JSRuntime* rt) {
   MOZ_ASSERT(!rt->mainContextFromOwnThread()->suppressGC);
 
   if (!rt->gc.isIncrementalGCAllowed()) {
     return gc::AbortReason::IncrementalDisabled;
   }
--- a/js/src/gc/GCMarker.h
+++ b/js/src/gc/GCMarker.h
@@ -44,26 +44,26 @@ struct WeakMarkable {
 
 using WeakEntryVector = Vector<WeakMarkable, 2, js::SystemAllocPolicy>;
 
 using WeakKeyTable =
     OrderedHashMap<JS::GCCellPtr, WeakEntryVector, WeakKeyTableHashPolicy,
                    js::SystemAllocPolicy>;
 
 /*
- * When the native stack is low, the GC does not call js::TraceChildren to mark
+ * When the mark stack is full, the GC does not call js::TraceChildren to mark
  * the reachable "children" of the thing. Rather the thing is put aside and
- * js::TraceChildren is called later with more space on the C stack.
+ * js::TraceChildren is called later when the mark stack is empty.
  *
  * To implement such delayed marking of the children with minimal overhead for
- * the normal case of sufficient native stack, the code adds a field per arena.
- * The field markingDelay->link links all arenas with delayed things into a
- * stack list with the pointer to stack top in GCMarker::unmarkedArenaStackTop.
- * GCMarker::delayMarkingChildren adds arenas to the stack as necessary while
- * markDelayedChildren pops the arenas from the stack until it empties.
+ * the normal case of sufficient stack, we link arenas into a list using
+ * Arena::setNextDelayedMarking(). The head of the list is stored in
+ * GCMarker::unmarkedArenaStackTop. GCMarker::delayMarkingChildren() adds arenas
+ * to the list as necessary while markAllDelayedChildren() pops the arenas from
+ * the stack until it is empty.
  */
 class MarkStack {
  public:
   /*
    * We use a common mark stack to mark GC things of different types and use
    * the explicit tags to distinguish them when it cannot be deduced from
    * the context of push or pop operation.
    */
@@ -275,18 +275,20 @@ class GCMarker : public JSTracer {
   void leaveWeakMarkingMode();
   void abortLinearWeakMarking() {
     leaveWeakMarkingMode();
     linearWeakMarkingDisabled_ = true;
   }
 
   void delayMarkingArena(gc::Arena* arena);
   void delayMarkingChildren(const void* thing);
-  void markDelayedChildren(gc::Arena* arena);
-  MOZ_MUST_USE bool markDelayedChildren(SliceBudget& budget);
+  void markDelayedChildren(gc::Arena* arena, gc::MarkColor color);
+  MOZ_MUST_USE bool markAllDelayedChildren(SliceBudget& budget);
+  bool processDelayedMarkingList(gc::Arena** outputList, gc::MarkColor color,
+                                 bool shouldYield, SliceBudget& budget);
   bool hasDelayedChildren() const { return !!unmarkedArenaStackTop; }
 
   bool isDrained() { return isMarkStackEmpty() && !unmarkedArenaStackTop; }
 
   MOZ_MUST_USE bool markUntilBudgetExhausted(SliceBudget& budget);
 
   void setGCMode(JSGCMode mode) { stack.setGCMode(mode); }
 
@@ -343,31 +345,38 @@ class GCMarker : public JSTracer {
 
   template <typename T>
   inline void pushTaggedPtr(T* ptr);
 
   inline void pushValueArray(JSObject* obj, HeapSlot* start, HeapSlot* end);
 
   bool isMarkStackEmpty() { return stack.isEmpty(); }
 
+  bool hasBlackEntries() const { return stack.position() > grayPosition; }
+
+  bool hasGrayEntries() const { return grayPosition > 0 && !stack.isEmpty(); }
+
   MOZ_MUST_USE bool restoreValueArray(
       const gc::MarkStack::SavedValueArray& array, HeapSlot** vpp,
       HeapSlot** endp);
   gc::MarkStack::ValueArray restoreValueArray(
       const gc::MarkStack::SavedValueArray& savedArray);
 
   void saveValueRanges();
   gc::MarkStack::SavedValueArray saveValueRange(
       const gc::MarkStack::ValueArray& array);
 
   inline void processMarkStackTop(SliceBudget& budget);
 
   /* The mark stack. Pointers in this stack are "gray" in the GC sense. */
   gc::MarkStack stack;
 
+  /* Stack entries at positions below this are considered gray. */
+  MainThreadData<size_t> grayPosition;
+
   /* The color is only applied to objects and functions. */
   MainThreadData<gc::MarkColor> color;
 
   /* Pointer to the top of the stack of arenas we are delaying marking on. */
   MainThreadData<js::gc::Arena*> unmarkedArenaStackTop;
 
   /*
    * If the weakKeys table OOMs, disable the linear algorithm and fall back
--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -1577,36 +1577,53 @@ bool GCMarker::markUntilBudgetExhausted(
   strictCompartmentChecking = true;
   auto acc = mozilla::MakeScopeExit([&] { strictCompartmentChecking = false; });
 #endif
 
   if (budget.isOverBudget()) {
     return false;
   }
 
+  // This method leaves the mark color as it found it.
+  AutoSetMarkColor autoSetBlack(*this, MarkColor::Black);
+
+  // Change representation of value arrays on the stack while the mutator
+  // runs.
+  auto svr = mozilla::MakeScopeExit([&] { saveValueRanges(); });
+
   for (;;) {
-    while (!stack.isEmpty()) {
+    while (hasBlackEntries()) {
+      MOZ_ASSERT(markColor() == MarkColor::Black);
       processMarkStackTop(budget);
       if (budget.isOverBudget()) {
-        saveValueRanges();
         return false;
       }
     }
 
+    if (hasGrayEntries()) {
+      AutoSetMarkColor autoSetGray(*this, MarkColor::Gray);
+      do {
+        processMarkStackTop(budget);
+        if (budget.isOverBudget()) {
+          MOZ_CRASH("Incremental gray marking NYI");
+          return false;
+        }
+      } while (hasGrayEntries());
+    }
+
     if (!hasDelayedChildren()) {
       break;
     }
 
     /*
      * Mark children of things that caused too deep recursion during the
      * above tracing. Don't do this until we're done with everything
      * else.
      */
-    if (!markDelayedChildren(budget)) {
-      saveValueRanges();
+    if (!markAllDelayedChildren(budget)) {
       return false;
     }
   }
 
   return true;
 }
 
 inline static bool ObjectDenseElementsMayBeMarkable(NativeObject* nobj) {
@@ -2328,16 +2345,17 @@ void MarkStackIter::saveValueArray(
  * ExpandWeakMaps: the GC is recomputing the liveness of WeakMap entries by
  * expanding each live WeakMap into its constituent key->value edges, a table
  * of which will be consulted in a later phase whenever marking a potential
  * key.
  */
 GCMarker::GCMarker(JSRuntime* rt)
     : JSTracer(rt, JSTracer::TracerKindTag::Marking, ExpandWeakMaps),
       stack(),
+      grayPosition(0),
       color(MarkColor::Black),
       unmarkedArenaStackTop(nullptr)
 #ifdef DEBUG
       ,
       markLaterArenas(0),
       started(false),
       strictCompartmentChecking(false)
 #endif
@@ -2407,29 +2425,31 @@ void GCMarker::setMarkColor(gc::MarkColo
   if (newColor == gc::MarkColor::Black) {
     setMarkColorBlack();
   } else {
     setMarkColorGray();
   }
 }
 
 void GCMarker::setMarkColorGray() {
-  MOZ_ASSERT(isDrained());
+  MOZ_ASSERT(!hasBlackEntries());
   MOZ_ASSERT(color == gc::MarkColor::Black);
   MOZ_ASSERT(runtime()->gc.state() == State::Sweep);
 
   color = gc::MarkColor::Gray;
+  grayPosition = SIZE_MAX;
 }
 
 void GCMarker::setMarkColorBlack() {
-  MOZ_ASSERT(isDrained());
+  MOZ_ASSERT(!hasBlackEntries());
   MOZ_ASSERT(color == gc::MarkColor::Gray);
   MOZ_ASSERT(runtime()->gc.state() == State::Sweep);
 
   color = gc::MarkColor::Black;
+  grayPosition = stack.position();
 }
 
 template <typename T>
 void GCMarker::pushTaggedPtr(T* ptr) {
   checkZone(ptr);
   if (!stack.push(ptr)) {
     delayMarkingChildren(ptr);
   }
@@ -2491,62 +2511,122 @@ void GCMarker::leaveWeakMarkingMode() {
   AutoEnterOOMUnsafeRegion oomUnsafe;
   for (GCZonesIter zone(runtime()); !zone.done(); zone.next()) {
     if (!zone->gcWeakKeys().clear()) {
       oomUnsafe.crash("clearing weak keys in GCMarker::leaveWeakMarkingMode()");
     }
   }
 }
 
-void GCMarker::markDelayedChildren(Arena* arena) {
+void GCMarker::markDelayedChildren(Arena* arena, MarkColor color) {
   JS::TraceKind kind = MapAllocToTraceKind(arena->getAllocKind());
-
-  // Whether we need to mark children of gray or black cells in the arena
-  // depends on which kind of marking we were doing when the arena as pushed
-  // onto the list.  We never change mark color without draining the mark
-  // stack though so this is the same as the current color.
-  bool markGrayCells =
-      markColor() == MarkColor::Gray && TraceKindParticipatesInCC(kind);
+  MOZ_ASSERT_IF(color == MarkColor::Gray, TraceKindParticipatesInCC(kind));
 
   for (ArenaCellIterUnderGC i(arena); !i.done(); i.next()) {
     TenuredCell* t = i.getCell();
-    if ((markGrayCells && t->isMarkedGray()) ||
-        (!markGrayCells && t->isMarkedBlack())) {
+    if ((color == MarkColor::Gray && t->isMarkedGray()) ||
+        (color == MarkColor::Black && t->isMarkedBlack())) {
       js::TraceChildren(this, t, kind);
     }
   }
 }
 
-bool GCMarker::markDelayedChildren(SliceBudget& budget) {
+static inline bool ArenaCanHaveGrayThings(Arena* arena) {
+  JS::TraceKind kind = MapAllocToTraceKind(arena->getAllocKind());
+  return TraceKindParticipatesInCC(kind);
+}
+
+/*
+ * Process arenas from |unmarkedArenaStackTop| and move them to
+ * |*output| (if non-null) marking the unmarked children of marked
+ * cells of color |color| if |shouldMarkArena| returns true. If
+ * |shouldYield|, return early if the |budget| is exceeded.
+ *
+ * This is called twice, first to mark gray children and then to mark
+ * black children.
+ */
+bool GCMarker::processDelayedMarkingList(Arena** outputList, MarkColor color,
+                                         bool shouldYield,
+                                         SliceBudget& budget) {
+  // If marking gets delayed at the same arena again, we must repeat marking
+  // of its things. Therefore we pop arena from the stack and clear its
+  // hasDelayedMarking flag before we begin the marking.
+
+  while (unmarkedArenaStackTop) {
+    Arena* arena = unmarkedArenaStackTop;
+    unmarkedArenaStackTop = arena->getNextDelayedMarking();
+
+    arena->unsetDelayedMarking();
+
+#ifdef DEBUG
+    MOZ_ASSERT(markLaterArenas);
+    if (!outputList) {
+      markLaterArenas--;
+    }
+#endif
+
+    if (color == MarkColor::Black ||
+        (color == MarkColor::Gray && ArenaCanHaveGrayThings(arena))) {
+      markDelayedChildren(arena, color);
+      budget.step(150);
+      if (shouldYield && budget.isOverBudget()) {
+        return false;
+      }
+    }
+
+    if (outputList) {
+      arena->setNextDelayedMarking(*outputList);
+      *outputList = arena;
+    }
+  }
+
+  return true;
+}
+
+bool GCMarker::markAllDelayedChildren(SliceBudget& budget) {
+  MOZ_ASSERT(!hasBlackEntries());
+  MOZ_ASSERT(markColor() == MarkColor::Black);
+
   GCRuntime& gc = runtime()->gc;
   gcstats::AutoPhase ap(gc.stats(), gc.state() == State::Mark,
                         gcstats::PhaseKind::MARK_DELAYED);
 
+  // We don't know which mark color we were using when an arena was
+  // pushed onto the list so we mark children of marked things both
+  // colors in two passes over the list. Gray marking must be done
+  // first as gray entries always sit before black entries on the
+  // mark stack.
+  //
+  // In order to guarantee progress here, the fist pass (gray
+  // marking) is done non-incrementally. We can't remove anything
+  // from the list until the second pass so if we yield during the
+  // first pass we will have to restart and process all the arenas
+  // over again. If there are enough arenas we may never finish
+  // during our timeslice. Disallowing yield during the first pass
+  // ensures that the list will at least shrink by one arena every
+  // time.
+
   MOZ_ASSERT(unmarkedArenaStackTop);
-  do {
-    /*
-     * If marking gets delayed at the same arena again, we must repeat
-     * marking of its things. For that we pop arena from the stack and
-     * clear its hasDelayedMarking flag before we begin the marking.
-     */
-    Arena* arena = unmarkedArenaStackTop;
-    MOZ_ASSERT(arena->hasDelayedMarking);
-    MOZ_ASSERT(markLaterArenas);
-    unmarkedArenaStackTop = arena->getNextDelayedMarking();
-    arena->unsetDelayedMarking();
-#ifdef DEBUG
-    markLaterArenas--;
-#endif
-    markDelayedChildren(arena);
-
-    budget.step(150);
-    if (budget.isOverBudget()) {
-      return false;
-    }
-  } while (unmarkedArenaStackTop);
+
+  Arena* processedList = nullptr;
+  bool finished;
+  finished = processDelayedMarkingList(&processedList, MarkColor::Gray,
+                                       false, /* don't yield */
+                                       budget);
+  MOZ_ASSERT(finished);
+
+  unmarkedArenaStackTop = processedList;
+  finished = processDelayedMarkingList(nullptr, MarkColor::Black,
+                                       true, /* yield if over budget */
+                                       budget);
+  if (!finished) {
+    return false;
+  }
+
+  MOZ_ASSERT(!unmarkedArenaStackTop);
   MOZ_ASSERT(!markLaterArenas);
 
   return true;
 }
 
 template <typename T>
 static void PushArenaTyped(GCMarker* gcmarker, Arena* arena) {
   for (ArenaCellIterUnderGC i(arena); !i.done(); i.next()) {