Bug 1259730 - Make UnmarkGray use an explicit mark stack instead of recursion r=sfink
authorJon Coppeard <jcoppeard@mozilla.com>
Sat, 04 Mar 2017 08:59:42 +0000
changeset 394986 e68394fb539542f291d2804d4d08811cef02534a
parent 394985 7a20a634742e88d1f364987ddc8b9221bf6e4697
child 394987 b2caae037c26ad8e4106ef7562523aead73a8a21
push id1468
push userasasaki@mozilla.com
push dateMon, 05 Jun 2017 19:31:07 +0000
treeherdermozilla-release@0641fc6ee9d1 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1259730
milestone54.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 1259730 - Make UnmarkGray use an explicit mark stack instead of recursion r=sfink
js/src/gc/GCRuntime.h
js/src/gc/Marking.cpp
js/src/jsapi-tests/testGCGrayMarking.cpp
js/src/jsgc.cpp
--- a/js/src/gc/GCRuntime.h
+++ b/js/src/gc/GCRuntime.h
@@ -1041,16 +1041,18 @@ class GCRuntime
 
   private:
     UnprotectedData<gcstats::Statistics> stats_;
   public:
     gcstats::Statistics& stats() { return stats_.ref(); }
 
     GCMarker marker;
 
+    Vector<JS::GCCellPtr, 0, SystemAllocPolicy> unmarkGrayStack;
+
     /* Track heap usage for this runtime. */
     HeapUsage usage;
 
     /* GC scheduling state and parameters. */
     GCSchedulingTunables tunables;
     GCSchedulingState schedulingState;
 
     MemProfiler mMemProfiler;
--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -3226,51 +3226,16 @@ FOR_EACH_PUBLIC_TAGGED_GC_POINTER_TYPE(I
 #undef INSTANTIATE_ALL_VALID_TRACE_FUNCTIONS
 
 } /* namespace gc */
 } /* namespace js */
 
 
 /*** Cycle Collector Barrier Implementation *******************************************************/
 
-#ifdef DEBUG
-struct AssertNonGrayTracer : public JS::CallbackTracer {
-    explicit AssertNonGrayTracer(JSRuntime* rt) : JS::CallbackTracer(rt) {}
-    void onChild(const JS::GCCellPtr& thing) override {
-        MOZ_ASSERT_IF(thing.asCell()->isTenured(),
-                      !thing.asCell()->asTenured().isMarked(js::gc::GRAY));
-    }
-};
-#endif
-
-struct UnmarkGrayTracer : public JS::CallbackTracer
-{
-    /*
-     * We set weakMapAction to DoNotTraceWeakMaps because the cycle collector
-     * will fix up any color mismatches involving weakmaps when it runs.
-     */
-    explicit UnmarkGrayTracer(JSRuntime *rt, bool tracingShape = false)
-      : JS::CallbackTracer(rt, DoNotTraceWeakMaps)
-      , tracingShape(tracingShape)
-      , previousShape(nullptr)
-      , unmarkedAny(false)
-    {}
-
-    void onChild(const JS::GCCellPtr& thing) override;
-
-    /* True iff we are tracing the immediate children of a shape. */
-    bool tracingShape;
-
-    /* If tracingShape, shape child or nullptr. Otherwise, nullptr. */
-    Shape* previousShape;
-
-    /* Whether we unmarked anything. */
-    bool unmarkedAny;
-};
-
 /*
  * The GC and CC are run independently. Consequently, the following sequence of
  * events can occur:
  * 1. GC runs and marks an object gray.
  * 2. The mutator runs (specifically, some C++ code with access to gray
  *    objects) and creates a pointer from a JS root or other black object to
  *    the gray object. If we re-ran a GC at this point, the object would now be
  *    black.
@@ -3293,105 +3258,114 @@ struct UnmarkGrayTracer : public JS::Cal
  * Handling these implicit edges has two parts:
  * - A special pass enumerating all of the containers that know about the
  *   implicit edges to fix any black-gray edges that have been created. This
  *   is implemented in nsXPConnect::FixWeakMappingGrayBits.
  * - To prevent any incorrectly gray objects from escaping to live JS outside
  *   of the containers, we must add unmark-graying read barriers to these
  *   containers.
  */
+
+#ifdef DEBUG
+struct AssertNonGrayTracer : public JS::CallbackTracer {
+    explicit AssertNonGrayTracer(JSRuntime* rt) : JS::CallbackTracer(rt) {}
+    void onChild(const JS::GCCellPtr& thing) override {
+        MOZ_ASSERT_IF(thing.asCell()->isTenured(),
+                      !thing.asCell()->asTenured().isMarked(js::gc::GRAY));
+    }
+};
+#endif
+
+class UnmarkGrayTracer : public JS::CallbackTracer
+{
+  public:
+    // We set weakMapAction to DoNotTraceWeakMaps because the cycle collector
+    // will fix up any color mismatches involving weakmaps when it runs.
+    explicit UnmarkGrayTracer(JSRuntime *rt)
+      : JS::CallbackTracer(rt, DoNotTraceWeakMaps)
+      , unmarkedAny(false)
+      , oom(false)
+      , stack(rt->gc.unmarkGrayStack)
+    {}
+
+    void unmark(JS::GCCellPtr cell);
+
+    // Whether we unmarked anything.
+    bool unmarkedAny;
+
+    // Whether we ran out of memory.
+    bool oom;
+
+  private:
+    // Stack of cells to traverse.
+    Vector<JS::GCCellPtr, 0, SystemAllocPolicy>& stack;
+
+    void onChild(const JS::GCCellPtr& thing) override;
+};
+
 void
 UnmarkGrayTracer::onChild(const JS::GCCellPtr& thing)
 {
-    int stackDummy;
-    JSContext* cx = TlsContext.get();
-    if (!JS_CHECK_STACK_SIZE(cx->nativeStackLimit[JS::StackForSystemCode], &stackDummy)) {
-        /*
-         * If we run out of stack, we take a more drastic measure: require that
-         * we GC again before the next CC.
-         */
-        runtime()->gc.setGrayBitsInvalid();
-        return;
-    }
-
     Cell* cell = thing.asCell();
 
     // Cells in the nursery cannot be gray, and therefore must necessarily point
     // to only black edges.
     if (!cell->isTenured()) {
 #ifdef DEBUG
         AssertNonGrayTracer nongray(runtime());
         TraceChildren(&nongray, cell, thing.kind());
 #endif
         return;
     }
 
     TenuredCell& tenured = cell->asTenured();
-    if (!tenured.isMarked(js::gc::GRAY))
+    if (!tenured.isMarked(GRAY))
         return;
-    tenured.unmark(js::gc::GRAY);
-
+
+    tenured.unmark(GRAY);
     unmarkedAny = true;
 
-    // Trace children of |tenured|. If |tenured| and its parent are both
-    // shapes, |tenured| will get saved to mPreviousShape without being traced.
-    // The parent will later trace |tenured|. This is done to avoid increasing
-    // the stack depth during shape tracing. It is safe to do because a shape
-    // can only have one child that is a shape.
-    UnmarkGrayTracer childTracer(runtime(), thing.kind() == JS::TraceKind::Shape);
-
-    if (thing.kind() != JS::TraceKind::Shape) {
-        TraceChildren(&childTracer, &tenured, thing.kind());
-        MOZ_ASSERT(!childTracer.previousShape);
-        unmarkedAny |= childTracer.unmarkedAny;
+    if (!stack.append(thing))
+        oom = true;
+}
+
+void
+UnmarkGrayTracer::unmark(JS::GCCellPtr cell)
+{
+    MOZ_ASSERT(stack.empty());
+
+    onChild(cell);
+
+    while (!stack.empty() && !oom)
+        TraceChildren(this, stack.popCopy());
+
+    if (oom) {
+         // If we run out of memory, we take a drastic measure: require that we
+         // GC again before the next CC.
+        stack.clear();
+        runtime()->gc.setGrayBitsInvalid();
         return;
     }
-
-    MOZ_ASSERT(thing.kind() == JS::TraceKind::Shape);
-    Shape* shape = static_cast<Shape*>(&tenured);
-    if (tracingShape) {
-        MOZ_ASSERT(!previousShape);
-        previousShape = shape;
-        return;
-    }
-
-    do {
-        MOZ_ASSERT(!shape->isMarked(js::gc::GRAY));
-        shape->traceChildren(&childTracer);
-        shape = childTracer.previousShape;
-        childTracer.previousShape = nullptr;
-    } while (shape);
-    unmarkedAny |= childTracer.unmarkedAny;
 }
 
 template <typename T>
 static bool
 TypedUnmarkGrayCellRecursively(T* t)
 {
     MOZ_ASSERT(t);
 
     JSRuntime* rt = t->runtimeFromActiveCooperatingThread();
     MOZ_ASSERT(!JS::CurrentThreadIsHeapCollecting());
     MOZ_ASSERT(!JS::CurrentThreadIsHeapCycleCollecting());
 
-    bool unmarkedArg = false;
-    if (t->isTenured()) {
-        if (!t->asTenured().isMarked(GRAY))
-            return false;
-
-        t->asTenured().unmark(GRAY);
-        unmarkedArg = true;
-    }
-
-    UnmarkGrayTracer trc(rt);
+    UnmarkGrayTracer unmarker(rt);
     gcstats::AutoPhase outerPhase(rt->gc.stats(), gcstats::PHASE_BARRIER);
     gcstats::AutoPhase innerPhase(rt->gc.stats(), gcstats::PHASE_UNMARK_GRAY);
-    t->traceChildren(&trc);
-
-    return unmarkedArg || trc.unmarkedAny;
+    unmarker.unmark(JS::GCCellPtr(t, MapTypeToTraceKind<T>::kind));
+    return unmarker.unmarkedAny;
 }
 
 struct UnmarkGrayCellRecursivelyFunctor {
     template <typename T> bool operator()(T* t) { return TypedUnmarkGrayCellRecursively(t); }
 };
 
 bool
 js::UnmarkGrayCellRecursively(Cell* cell, JS::TraceKind kind)
--- a/js/src/jsapi-tests/testGCGrayMarking.cpp
+++ b/js/src/jsapi-tests/testGCGrayMarking.cpp
@@ -51,17 +51,18 @@ BEGIN_TEST(testGCGrayMarking)
 
     InitGrayRootTracer();
 
     bool ok =
         TestMarking() &&
         TestWeakMaps() &&
         TestUnassociatedWeakMaps() &&
         TestWatchpoints() &&
-        TestCCWs();
+        TestCCWs() &&
+        TestGrayUnmarking();
 
     global1 = nullptr;
     global2 = nullptr;
     RemoveGrayRootTracer();
 
     return ok;
 }
 
@@ -562,16 +563,80 @@ TestCCWs()
     CHECK(IsMarkedBlack(target));
 
     grayRoots.grayRoot1 = nullptr;
     grayRoots.grayRoot2 = nullptr;
 
     return true;
 }
 
+bool
+TestGrayUnmarking()
+{
+    const size_t length = 2000;
+
+    JSObject* chain = AllocObjectChain(length);
+    CHECK(chain);
+
+    RootedObject blackRoot(cx, chain);
+    JS_GC(cx);
+    size_t count;
+    CHECK(IterateObjectChain(chain, ColorCheckFunctor(BLACK, &count)));
+    CHECK(count == length);
+
+    blackRoot = nullptr;
+    grayRoots.grayRoot1 = chain;
+    JS_GC(cx);
+    CHECK(cx->runtime()->gc.areGrayBitsValid());
+    CHECK(IterateObjectChain(chain, ColorCheckFunctor(GRAY, &count)));
+    CHECK(count == length);
+
+    JS::ExposeObjectToActiveJS(chain);
+    CHECK(cx->runtime()->gc.areGrayBitsValid());
+    CHECK(IterateObjectChain(chain, ColorCheckFunctor(BLACK, &count)));
+    CHECK(count == length);
+
+    grayRoots.grayRoot1 = nullptr;
+
+    return true;
+}
+
+struct ColorCheckFunctor
+{
+    uint32_t color;
+    size_t& count;
+
+    ColorCheckFunctor(uint32_t colorArg, size_t* countArg)
+      : color(colorArg), count(*countArg)
+    {
+        count = 0;
+    }
+
+    bool operator()(JSObject* obj) {
+        if (!CheckCellColor(obj, color))
+            return false;
+
+        NativeObject& nobj = obj->as<NativeObject>();
+        if (!CheckCellColor(nobj.shape(), color))
+            return false;
+
+        Shape* shape = nobj.shape();
+        if (!CheckCellColor(shape, color))
+            return false;
+
+        // Shapes and symbols are never marked gray.
+        jsid id = shape->propid();
+        if (JSID_IS_GCTHING(id) && !CheckCellColor(JSID_TO_GCTHING(id).asCell(), BLACK))
+            return false;
+
+        count++;
+        return true;
+    }
+};
+
 JS::PersistentRootedObject global1;
 JS::PersistentRootedObject global2;
 
 struct GrayRoots
 {
     JS::Heap<JSObject*> grayRoot1;
     JS::Heap<JSObject*> grayRoot2;
 };
@@ -689,32 +754,90 @@ AllocDelegateForKey(JSObject* key)
 {
     JS::RootedObject obj(cx, JS_NewPlainObject(cx));
     EvictNursery();
 
     key->as<NativeObject>().setPrivate(obj);
     return obj;
 }
 
-bool
-IsMarkedBlack(JSObject* obj)
+JSObject*
+AllocObjectChain(size_t length)
 {
-    TenuredCell* cell = &obj->asTenured();
-    return cell->isMarked(BLACK) && !cell->isMarked(GRAY);
+    // Allocate a chain of linked JSObjects.
+
+    // Use a unique property name so the shape is not shared with any other
+    // objects.
+    RootedString nextPropName(cx, JS_NewStringCopyZ(cx, "unique14142135"));
+    RootedId nextId(cx);
+    if (!JS_StringToId(cx, nextPropName, &nextId))
+        return nullptr;
+
+    RootedObject head(cx);
+    for (size_t i = 0; i < length; i++) {
+        RootedValue next(cx, ObjectOrNullValue(head));
+        head = AllocPlainObject();
+        if (!head)
+            return nullptr;
+        if (!JS_DefinePropertyById(cx, head, nextId, next, 0))
+            return nullptr;
+    }
+
+    return head;
 }
 
-bool
-IsMarkedGray(JSObject* obj)
+template <typename F>
+bool IterateObjectChain(JSObject* chain, F f)
+{
+    RootedObject obj(cx, chain);
+    while (obj) {
+        if (!f(obj))
+            return false;
+
+        // Access the 'next' property via the object's slots to avoid triggering
+        // gray marking assertions when calling JS_GetPropertyById.
+        NativeObject& nobj = obj->as<NativeObject>();
+        MOZ_ASSERT(nobj.slotSpan() == 1);
+        obj = nobj.getSlot(0).toObjectOrNull();
+    }
+
+    return true;
+}
+
+static bool
+IsMarkedBlack(Cell* cell)
 {
-    TenuredCell* cell = &obj->asTenured();
-    bool isGray = cell->isMarked(GRAY);
-    MOZ_ASSERT_IF(isGray, cell->isMarked(BLACK));
+    TenuredCell* tc = &cell->asTenured();
+    return tc->isMarked(BLACK) && !tc->isMarked(GRAY);
+}
+
+static bool
+IsMarkedGray(Cell* cell)
+{
+    TenuredCell* tc = &cell->asTenured();
+    bool isGray = tc->isMarked(GRAY);
+    MOZ_ASSERT_IF(isGray, tc->isMarked(BLACK));
     return isGray;
 }
 
+static bool
+CheckCellColor(Cell* cell, uint32_t color)
+{
+    MOZ_ASSERT(color == BLACK || color == GRAY);
+    if (color == BLACK && !IsMarkedBlack(cell)) {
+        printf("Found non-black cell: %p\n", cell);
+        return false;
+    } else if (color == GRAY && !IsMarkedGray(cell)) {
+        printf("Found non-gray cell: %p\n", cell);
+        return false;
+    }
+
+    return true;
+}
+
 void
 EvictNursery()
 {
     cx->runtime()->gc.evictNursery();
 }
 
 bool
 ZoneGC(JS::Zone* zone)
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -3606,16 +3606,19 @@ GCRuntime::purgeRuntime(AutoLockForExclu
     rt->caches().uncompressedSourceCache.purge();
     if (rt->caches().evalCache.initialized())
         rt->caches().evalCache.clear();
 
     if (auto cache = rt->maybeThisRuntimeSharedImmutableStrings())
         cache->purge();
 
     rt->promiseTasksToDestroy.lock()->clear();
+
+    MOZ_ASSERT(unmarkGrayStack.empty());
+    unmarkGrayStack.clearAndFree();
 }
 
 bool
 GCRuntime::shouldPreserveJITCode(JSCompartment* comp, int64_t currentTime,
                                  JS::gcreason::Reason reason, bool canAllocateMoreCode)
 {
     if (cleanUpEverything)
         return false;