Bug 1341355 - Refactor the mark stack r=sfink
authorJon Coppeard <jcoppeard@mozilla.com>
Tue, 21 Feb 2017 17:53:21 +0000
changeset 344001 a6aebb9814445268db688d5dbcb5cac511f23686
parent 344000 c7a4c2e34e6e1c888976fd9857fe816804f83550
child 344002 80f3a16286b0d4ef6896853d02087c44c93e0857
push id87255
push userjcoppeard@mozilla.com
push dateTue, 21 Feb 2017 17:58:35 +0000
treeherdermozilla-inbound@80f3a16286b0 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1341355
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 1341355 - Refactor the mark stack r=sfink
js/src/gc/Marking.cpp
js/src/gc/Marking.h
--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -892,28 +892,28 @@ template <> void GCMarker::traverse(js::
 
 // Object and ObjectGroup are extremely common and can contain arbitrarily
 // nested graphs, so are not trivially inlined. In this case we use a mark
 // stack to control recursion. JitCode shares none of these properties, but is
 // included for historical reasons. JSScript normally cannot recurse, but may
 // be used as a weakmap key and thereby recurse into weakmapped values.
 template <typename T>
 void
-js::GCMarker::markAndPush(StackTag tag, T* thing)
+js::GCMarker::markAndPush(T* thing)
 {
     if (!mark(thing))
         return;
-    pushTaggedPtr(tag, thing);
+    pushTaggedPtr(thing);
     markImplicitEdges(thing);
 }
 namespace js {
-template <> void GCMarker::traverse(JSObject* thing) { markAndPush(ObjectTag, thing); }
-template <> void GCMarker::traverse(ObjectGroup* thing) { markAndPush(GroupTag, thing); }
-template <> void GCMarker::traverse(jit::JitCode* thing) { markAndPush(JitCodeTag, thing); }
-template <> void GCMarker::traverse(JSScript* thing) { markAndPush(ScriptTag, thing); }
+template <> void GCMarker::traverse(JSObject* thing) { markAndPush(thing); }
+template <> void GCMarker::traverse(ObjectGroup* thing) { markAndPush(thing); }
+template <> void GCMarker::traverse(jit::JitCode* thing) { markAndPush(thing); }
+template <> void GCMarker::traverse(JSScript* thing) { markAndPush(thing); }
 } // namespace js
 
 namespace js {
 template <>
 void
 GCMarker::traverse(AccessorShape* thing) {
     MOZ_CRASH("AccessorShape must be marked as a Shape");
 }
@@ -1187,26 +1187,28 @@ js::GCMarker::eagerlyMarkChildren(JSRope
         if (!left->isPermanentAtom() &&
             mark(left))
         {
             if (left->isLinear()) {
                 eagerlyMarkChildren(&left->asLinear());
             } else {
                 // When both children are ropes, set aside the right one to
                 // scan it later.
-                if (next && !stack.push(reinterpret_cast<uintptr_t>(next)))
+                if (next && !stack.pushTempRope(next))
                     delayMarkingChildren(next);
                 next = &left->asRope();
             }
         }
         if (next) {
             rope = next;
         } else if (savedPos != stack.position()) {
             MOZ_ASSERT(savedPos < stack.position());
-            rope = reinterpret_cast<JSRope*>(stack.pop());
+            uintptr_t ptr = stack.pop();
+            MOZ_ASSERT((ptr & MarkStack::TagMask) == MarkStack::TempRopeTag);
+            rope = reinterpret_cast<JSRope*>(ptr &~ MarkStack::TempRopeTag);
         } else {
             break;
         }
     }
     MOZ_ASSERT(savedPos == stack.position());
 }
 
 static inline void
@@ -1641,53 +1643,53 @@ GCMarker::processMarkStackTop(SliceBudge
      * significantly improve the marking performance, see bug 641025.
      */
     HeapSlot* vp;
     HeapSlot* end;
     JSObject* obj;
 
     // Decode
     uintptr_t addr = stack.pop();
-    uintptr_t tag = addr & StackTagMask;
-    addr &= ~StackTagMask;
+    uintptr_t tag = addr & MarkStack::TagMask;
+    addr &= ~MarkStack::TagMask;
 
     // Dispatch
     switch (tag) {
-      case ValueArrayTag: {
-        JS_STATIC_ASSERT(ValueArrayTag == 0);
+      case MarkStack::ValueArrayTag: {
+        JS_STATIC_ASSERT(MarkStack::ValueArrayTag == 0);
         MOZ_ASSERT(!(addr & CellMask));
         obj = reinterpret_cast<JSObject*>(addr);
         uintptr_t addr2 = stack.pop();
         uintptr_t addr3 = stack.pop();
         MOZ_ASSERT(addr2 <= addr3);
         MOZ_ASSERT((addr3 - addr2) % sizeof(Value) == 0);
         vp = reinterpret_cast<HeapSlot*>(addr2);
         end = reinterpret_cast<HeapSlot*>(addr3);
         goto scan_value_array;
       }
 
-      case ObjectTag: {
+      case MarkStack::ObjectTag: {
         obj = reinterpret_cast<JSObject*>(addr);
         AssertZoneIsMarking(obj);
         goto scan_obj;
       }
 
-      case GroupTag: {
+      case MarkStack::GroupTag: {
         return lazilyMarkChildren(reinterpret_cast<ObjectGroup*>(addr));
       }
 
-      case JitCodeTag: {
+      case MarkStack::JitCodeTag: {
         return reinterpret_cast<jit::JitCode*>(addr)->traceChildren(this);
       }
 
-      case ScriptTag: {
+      case MarkStack::ScriptTag: {
         return reinterpret_cast<JSScript*>(addr)->traceChildren(this);
       }
 
-      case SavedValueArrayTag: {
+      case MarkStack::SavedValueArrayTag: {
         MOZ_ASSERT(!(addr & CellMask));
         JSObject* obj = reinterpret_cast<JSObject*>(addr);
         HeapSlot* vp;
         HeapSlot* end;
         if (restoreValueArray(obj, (void**)&vp, (void**)&end))
             pushValueArray(&obj->as<NativeObject>(), vp, end);
         else
             repush(obj);
@@ -1814,20 +1816,20 @@ struct SlotArrayLayout
  * that are stored on the stack. To prevent this from happening, we replace all
  * ValueArrayTag stack items with SavedValueArrayTag. In the latter, slots
  * pointers are replaced with slot indexes, and slot array end pointers are
  * replaced with the kind of index (properties vs. elements).
  */
 void
 GCMarker::saveValueRanges()
 {
-    for (uintptr_t* p = stack.tos_; p > stack.stack_; ) {
-        uintptr_t tag = *--p & StackTagMask;
-        if (tag == ValueArrayTag) {
-            *p &= ~StackTagMask;
+    for (uintptr_t* p = stack.top(); p > stack.base(); ) {
+        uintptr_t tag = *--p & MarkStack::TagMask;
+        if (tag == MarkStack::ValueArrayTag) {
+            *p &= ~MarkStack::TagMask;
             p -= 2;
             SlotArrayLayout* arr = reinterpret_cast<SlotArrayLayout*>(p);
             NativeObject* obj = arr->obj;
             MOZ_ASSERT(obj->isNative());
 
             HeapSlot* vp = obj->getDenseElementsAllowCopyOnWrite();
             if (arr->end == vp + obj->getDenseInitializedLength()) {
                 MOZ_ASSERT(arr->start >= vp);
@@ -1843,18 +1845,18 @@ GCMarker::saveValueRanges()
                     arr->index = arr->start - vp;
                 } else {
                     MOZ_ASSERT(arr->start >= obj->slots_ &&
                                arr->end == obj->slots_ + obj->slotSpan() - nfixed);
                     arr->index = (arr->start - obj->slots_) + nfixed;
                 }
                 arr->kind = HeapSlot::Slot;
             }
-            p[2] |= SavedValueArrayTag;
-        } else if (tag == SavedValueArrayTag) {
+            p[2] |= MarkStack::SavedValueArrayTag;
+        } else if (tag == MarkStack::SavedValueArrayTag) {
             p -= 2;
         }
     }
 }
 
 bool
 GCMarker::restoreValueArray(JSObject* objArg, void** vpp, void** endp)
 {
@@ -1899,16 +1901,36 @@ GCMarker::restoreValueArray(JSObject* ob
 
     MOZ_ASSERT(*vpp <= *endp);
     return true;
 }
 
 
 /*** Mark Stack ***********************************************************************************/
 
+template <typename T>
+struct MapTypeToMarkStackTag {};
+
+template <>
+struct MapTypeToMarkStackTag<JSObject*> { static const auto value = MarkStack::ObjectTag; };
+template <>
+struct MapTypeToMarkStackTag<ObjectGroup*> { static const auto value = MarkStack::GroupTag; };
+template <>
+struct MapTypeToMarkStackTag<jit::JitCode*> { static const auto value = MarkStack::JitCodeTag; };
+template <>
+struct MapTypeToMarkStackTag<JSScript*> { static const auto value = MarkStack::ScriptTag; };
+
+MarkStack::MarkStack(size_t maxCapacity)
+  : stack_(nullptr),
+    tos_(nullptr),
+    end_(nullptr),
+    baseCapacity_(0),
+    maxCapacity_(maxCapacity)
+{}
+
 bool
 MarkStack::init(JSGCMode gcMode)
 {
     setBaseCapacity(gcMode);
 
     MOZ_ASSERT(!stack_);
     uintptr_t* newStack = js_pod_malloc<uintptr_t>(baseCapacity_);
     if (!newStack)
@@ -1944,16 +1966,61 @@ MarkStack::setMaxCapacity(size_t maxCapa
     MOZ_ASSERT(isEmpty());
     maxCapacity_ = maxCapacity;
     if (baseCapacity_ > maxCapacity_)
         baseCapacity_ = maxCapacity_;
 
     reset();
 }
 
+template <typename T>
+inline bool
+MarkStack::push(T* ptr)
+{
+    uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
+    MOZ_ASSERT(!(addr & TagMask));
+    auto tag = MapTypeToMarkStackTag<T*>::value;
+    return pushTaggedPtr(addr | uintptr_t(tag));
+}
+
+inline bool
+MarkStack::pushTempRope(JSRope* rope)
+{
+    return pushTaggedPtr(uintptr_t(rope) | TempRopeTag);
+}
+
+inline bool
+MarkStack::pushTaggedPtr(uintptr_t item)
+{
+    if (tos_ == end_) {
+        if (!enlarge(1))
+            return false;
+    }
+    MOZ_ASSERT(tos_ < end_);
+    *tos_++ = item;
+    return true;
+}
+
+inline bool
+MarkStack::push(uintptr_t item1, uintptr_t item2, uintptr_t item3)
+{
+    uintptr_t* nextTos = tos_ + 3;
+    if (nextTos > end_) {
+        if (!enlarge(3))
+            return false;
+        nextTos = tos_ + 3;
+    }
+    MOZ_ASSERT(nextTos <= end_);
+    tos_[0] = item1;
+    tos_[1] = item2;
+    tos_[2] = item3;
+    tos_ = nextTos;
+    return true;
+}
+
 void
 MarkStack::reset()
 {
     if (capacity() == baseCapacity_) {
         // No size change; keep the current stack.
         setStack(stack_, 0, baseCapacity_);
         return;
     }
@@ -2084,16 +2151,51 @@ GCMarker::reset()
 #ifdef DEBUG
         markLaterArenas--;
 #endif
     }
     MOZ_ASSERT(isDrained());
     MOZ_ASSERT(!markLaterArenas);
 }
 
+
+template <typename T>
+void
+GCMarker::pushTaggedPtr(T* ptr)
+{
+    checkZone(ptr);
+    if (!stack.push(ptr))
+        delayMarkingChildren(ptr);
+}
+
+void
+GCMarker::pushValueArray(JSObject* obj, HeapSlot* start, HeapSlot* end)
+{
+    checkZone(obj);
+
+    MOZ_ASSERT(start <= end);
+    uintptr_t tagged = reinterpret_cast<uintptr_t>(obj) | MarkStack::ValueArrayTag;
+    uintptr_t startAddr = reinterpret_cast<uintptr_t>(start);
+    uintptr_t endAddr = reinterpret_cast<uintptr_t>(end);
+
+    /*
+     * Push in the reverse order so obj will be on top. If we cannot push
+     * the array, we trigger delay marking for the whole object.
+     */
+    if (!stack.push(endAddr, startAddr, tagged))
+        delayMarkingChildren(obj);
+}
+
+void
+GCMarker::repush(JSObject* obj)
+{
+    MOZ_ASSERT(gc::TenuredCell::fromPointer(obj)->isMarked(markColor()));
+    pushTaggedPtr(obj);
+}
+
 void
 GCMarker::enterWeakMarkingMode()
 {
     MOZ_ASSERT(tag_ == TracerKindTag::Marking);
     if (linearWeakMarkingDisabled_)
         return;
 
     // During weak marking mode, we maintain a table mapping weak keys to
--- a/js/src/gc/Marking.h
+++ b/js/src/gc/Marking.h
@@ -36,48 +36,63 @@ class Arena;
 } // namespace gc
 namespace jit {
 class JitCode;
 } // namespace jit
 
 static const size_t NON_INCREMENTAL_MARK_STACK_BASE_CAPACITY = 4096;
 static const size_t INCREMENTAL_MARK_STACK_BASE_CAPACITY = 32768;
 
+namespace gc {
+
 /*
  * When the native stack is low, 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.
  *
  * 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.
  */
 class MarkStack
 {
-    friend class GCMarker;
-
     ActiveThreadData<uintptr_t*> stack_;
     ActiveThreadData<uintptr_t*> tos_;
     ActiveThreadData<uintptr_t*> end_;
 
     // The capacity we start with and reset() to.
     ActiveThreadData<size_t> baseCapacity_;
     ActiveThreadData<size_t> maxCapacity_;
 
   public:
-    explicit MarkStack(size_t maxCapacity)
-      : stack_(nullptr),
-        tos_(nullptr),
-        end_(nullptr),
-        baseCapacity_(0),
-        maxCapacity_(maxCapacity)
-    {}
+    /*
+     * 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.
+     */
+    enum Tag {
+        ValueArrayTag,
+        ObjectTag,
+        GroupTag,
+        SavedValueArrayTag,
+        JitCodeTag,
+        ScriptTag,
+        TempRopeTag,
+
+        LastTag = TempRopeTag
+    };
+
+    static const uintptr_t TagMask = 7;
+    static_assert(TagMask >= uintptr_t(LastTag), "The tag mask must subsume the tags.");
+    static_assert(TagMask <= gc::CellMask, "The tag mask must be embeddable in a Cell*.");
+
+    explicit MarkStack(size_t maxCapacity);
 
     ~MarkStack() {
         js_free(stack_);
     }
 
     size_t capacity() { return end_ - stack_; }
 
     ptrdiff_t position() const { return tos_ - stack_; }
@@ -89,40 +104,26 @@ class MarkStack
     }
 
     MOZ_MUST_USE bool init(JSGCMode gcMode);
 
     void setBaseCapacity(JSGCMode mode);
     size_t maxCapacity() const { return maxCapacity_; }
     void setMaxCapacity(size_t maxCapacity);
 
-    MOZ_MUST_USE bool push(uintptr_t item) {
-        if (tos_ == end_) {
-            if (!enlarge(1))
-                return false;
-        }
-        MOZ_ASSERT(tos_ < end_);
-        *tos_++ = item;
-        return true;
-    }
+    uintptr_t* base() { return stack_; }
+    uintptr_t* top() { return tos_; }
 
-    MOZ_MUST_USE bool push(uintptr_t item1, uintptr_t item2, uintptr_t item3) {
-        uintptr_t* nextTos = tos_ + 3;
-        if (nextTos > end_) {
-            if (!enlarge(3))
-                return false;
-            nextTos = tos_ + 3;
-        }
-        MOZ_ASSERT(nextTos <= end_);
-        tos_[0] = item1;
-        tos_[1] = item2;
-        tos_[2] = item3;
-        tos_ = nextTos;
-        return true;
-    }
+    template <typename T>
+    MOZ_MUST_USE bool push(T* ptr);
+    MOZ_MUST_USE bool push(uintptr_t item1, uintptr_t item2, uintptr_t item3);
+
+    // GCMarker::eagerlyMarkChildren uses unused marking stack as temporary
+    // storage to hold rope pointers.
+    MOZ_MUST_USE bool pushTempRope(JSRope* ptr);
 
     bool isEmpty() const {
         return tos_ == stack_;
     }
 
     uintptr_t pop() {
         MOZ_ASSERT(!isEmpty());
         return *--tos_;
@@ -131,20 +132,21 @@ class MarkStack
     void reset();
 
     /* Grow the stack, ensuring there is space for at least count elements. */
     MOZ_MUST_USE bool enlarge(unsigned count);
 
     void setGCMode(JSGCMode gcMode);
 
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
+
+  private:
+    MOZ_MUST_USE bool pushTaggedPtr(uintptr_t item);
 };
 
-namespace gc {
-
 struct WeakKeyTableHashPolicy {
     typedef JS::GCCellPtr Lookup;
     static HashNumber hash(const Lookup& v, const mozilla::HashCodeScrambler&) {
         return mozilla::HashGeneric(v.asCell());
     }
     static bool match(const JS::GCCellPtr& k, const Lookup& l) { return k == l; }
     static bool isEmpty(const JS::GCCellPtr& v) { return !v; }
     static void makeEmpty(JS::GCCellPtr* vp) { *vp = nullptr; }
@@ -247,44 +249,22 @@ class GCMarker : public JSTracer
 
   private:
 #ifdef DEBUG
     void checkZone(void* p);
 #else
     void checkZone(void* p) {}
 #endif
 
-    /*
-     * 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.
-     */
-    enum StackTag {
-        ValueArrayTag,
-        ObjectTag,
-        GroupTag,
-        SavedValueArrayTag,
-        JitCodeTag,
-        ScriptTag,
-        LastTag = JitCodeTag
-    };
-
-    static const uintptr_t StackTagMask = 7;
-    static_assert(StackTagMask >= uintptr_t(LastTag), "The tag mask must subsume the tags.");
-    static_assert(StackTagMask <= gc::CellMask, "The tag mask must be embeddable in a Cell*.");
-
     // Push an object onto the stack for later tracing and assert that it has
     // already been marked.
-    void repush(JSObject* obj) {
-        MOZ_ASSERT(gc::TenuredCell::fromPointer(obj)->isMarked(markColor()));
-        pushTaggedPtr(ObjectTag, obj);
-    }
+    inline void repush(JSObject* obj);
 
     template <typename T> void markAndTraceChildren(T* thing);
-    template <typename T> void markAndPush(StackTag tag, T* thing);
+    template <typename T> void markAndPush(T* thing);
     template <typename T> void markAndScan(T* thing);
     template <typename T> void markImplicitEdgesHelper(T oldThing);
     template <typename T> void markImplicitEdges(T* oldThing);
     void eagerlyMarkChildren(JSLinearString* str);
     void eagerlyMarkChildren(JSRope* rope);
     void eagerlyMarkChildren(JSString* str);
     void eagerlyMarkChildren(LazyScript *thing);
     void eagerlyMarkChildren(Shape* shape);
@@ -295,50 +275,31 @@ class GCMarker : public JSTracer
     template <typename T>
     void dispatchToTraceChildren(T* thing);
 
     // Mark the given GC thing, but do not trace its children. Return true
     // if the thing became marked.
     template <typename T>
     MOZ_MUST_USE bool mark(T* thing);
 
-    void pushTaggedPtr(StackTag tag, void* ptr) {
-        checkZone(ptr);
-        uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
-        MOZ_ASSERT(!(addr & StackTagMask));
-        if (!stack.push(addr | uintptr_t(tag)))
-            delayMarkingChildren(ptr);
-    }
-
-    void pushValueArray(JSObject* obj, HeapSlot* start, HeapSlot* end) {
-        checkZone(obj);
+    template <typename T>
+    inline void pushTaggedPtr(T* ptr);
 
-        MOZ_ASSERT(start <= end);
-        uintptr_t tagged = reinterpret_cast<uintptr_t>(obj) | GCMarker::ValueArrayTag;
-        uintptr_t startAddr = reinterpret_cast<uintptr_t>(start);
-        uintptr_t endAddr = reinterpret_cast<uintptr_t>(end);
-
-        /*
-         * Push in the reverse order so obj will be on top. If we cannot push
-         * the array, we trigger delay marking for the whole object.
-         */
-        if (!stack.push(endAddr, startAddr, tagged))
-            delayMarkingChildren(obj);
-    }
+    inline void pushValueArray(JSObject* obj, HeapSlot* start, HeapSlot* end);
 
     bool isMarkStackEmpty() {
         return stack.isEmpty();
     }
 
     MOZ_MUST_USE bool restoreValueArray(JSObject* obj, void** vpp, void** endp);
     void saveValueRanges();
     inline void processMarkStackTop(SliceBudget& budget);
 
     /* The mark stack. Pointers in this stack are "gray" in the GC sense. */
-    MarkStack stack;
+    gc::MarkStack stack;
 
     /* The color is only applied to objects and functions. */
     ActiveThreadData<uint32_t> color;
 
     /* Pointer to the top of the stack of arenas we are delaying marking on. */
     ActiveThreadData<js::gc::Arena*> unmarkedArenaStackTop;
 
     /*