Bug 1341355 - Refactor the mark stack r=sfink
authorJon Coppeard <jcoppeard@mozilla.com>
Tue, 21 Feb 2017 17:53:21 +0000
changeset 373174 a6aebb9814445268db688d5dbcb5cac511f23686
parent 373117 c7a4c2e34e6e1c888976fd9857fe816804f83550
child 373175 80f3a16286b0d4ef6896853d02087c44c93e0857
push id10863
push userjlorenzo@mozilla.com
push dateMon, 06 Mar 2017 23:02:23 +0000
treeherdermozilla-aurora@0931190cd725 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1341355
milestone54.0a1
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;
 
     /*