Bug 1028418 - Part 5: Minimize stack walking when capturing SavedFrame stacks with a cache; r=shu
☠☠ backed out by 55137da3de18 ☠ ☠
authorNick Fitzgerald <fitzgen@gmail.com>
Mon, 27 Jul 2015 16:33:34 -0700
changeset 286538 caf840e715905fa3cbaa2af397059bc4b83cdb47
parent 286537 ba47cb00a93839481fc8399636d8afe06b4803c4
child 286539 f6e78ff75f4b9bcadb0e583a455928ed970c23fc
push id5067
push userraliiev@mozilla.com
push dateMon, 21 Sep 2015 14:04:52 +0000
treeherdermozilla-beta@14221ffe5b2f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersshu
bugs1028418
milestone42.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 1028418 - Part 5: Minimize stack walking when capturing SavedFrame stacks with a cache; r=shu
js/public/RootingAPI.h
js/src/gc/Rooting.h
js/src/jsgc.cpp
js/src/vm/SavedFrame.h
js/src/vm/SavedStacks.cpp
js/src/vm/SavedStacks.h
js/src/vm/Stack-inl.h
js/src/vm/Stack.cpp
js/src/vm/Stack.h
--- a/js/public/RootingAPI.h
+++ b/js/public/RootingAPI.h
@@ -604,16 +604,20 @@ class DispatchWrapper
 #if JS_BITS_PER_WORD == 32
     uint32_t padding; // Ensure the storage fields have CellSize alignment.
 #endif
     T storage;
 
   public:
     // Mimic a pointer type, so that we can drop into Rooted.
     MOZ_IMPLICIT DispatchWrapper(const T& initial) : tracer(&T::trace), storage(initial) {}
+    MOZ_IMPLICIT DispatchWrapper(T&& initial)
+      : tracer(&T::trace),
+        storage(mozilla::Forward<T>(initial))
+    { }
     T* operator &() { return &storage; }
     const T* operator &() const { return &storage; }
     operator T&() { return storage; }
     operator const T&() const { return storage; }
 
     // Trace the contained storage (of unknown type) using the trace function
     // we set aside when we did know the type.
     static void TraceWrapped(JSTracer* trc, JS::StaticTraceable* thingp, const char* name) {
--- a/js/src/gc/Rooting.h
+++ b/js/src/gc/Rooting.h
@@ -15,42 +15,46 @@ class JSLinearString;
 namespace js {
 
 class PropertyName;
 class NativeObject;
 class ArrayObject;
 class GlobalObject;
 class PlainObject;
 class ScriptSourceObject;
+class SavedFrame;
 class Shape;
 class ObjectGroup;
 
 // These are internal counterparts to the public types such as HandleObject.
 
 typedef JS::Handle<NativeObject*>      HandleNativeObject;
 typedef JS::Handle<Shape*>             HandleShape;
 typedef JS::Handle<ObjectGroup*>       HandleObjectGroup;
 typedef JS::Handle<JSAtom*>            HandleAtom;
 typedef JS::Handle<JSLinearString*>    HandleLinearString;
 typedef JS::Handle<PropertyName*>      HandlePropertyName;
 typedef JS::Handle<ArrayObject*>       HandleArrayObject;
 typedef JS::Handle<PlainObject*>       HandlePlainObject;
+typedef JS::Handle<SavedFrame*>        HandleSavedFrame;
 typedef JS::Handle<ScriptSourceObject*> HandleScriptSource;
 
 typedef JS::MutableHandle<Shape*>      MutableHandleShape;
 typedef JS::MutableHandle<JSAtom*>     MutableHandleAtom;
 typedef JS::MutableHandle<NativeObject*> MutableHandleNativeObject;
 typedef JS::MutableHandle<PlainObject*> MutableHandlePlainObject;
+typedef JS::MutableHandle<SavedFrame*> MutableHandleSavedFrame;
 
 typedef JS::Rooted<NativeObject*>      RootedNativeObject;
 typedef JS::Rooted<Shape*>             RootedShape;
 typedef JS::Rooted<ObjectGroup*>       RootedObjectGroup;
 typedef JS::Rooted<JSAtom*>            RootedAtom;
 typedef JS::Rooted<JSLinearString*>    RootedLinearString;
 typedef JS::Rooted<PropertyName*>      RootedPropertyName;
 typedef JS::Rooted<ArrayObject*>       RootedArrayObject;
 typedef JS::Rooted<GlobalObject*>      RootedGlobalObject;
 typedef JS::Rooted<PlainObject*>       RootedPlainObject;
+typedef JS::Rooted<SavedFrame*>        RootedSavedFrame;
 typedef JS::Rooted<ScriptSourceObject*> RootedScriptSource;
 
 } /* namespace js */
 
 #endif /* gc_Rooting_h */
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -2605,16 +2605,17 @@ GCRuntime::updatePointersToRelocatedCell
     {
         markRuntime(&trc, MarkRuntime);
 
         gcstats::AutoPhase ap(stats, gcstats::PHASE_MARK_ROOTS);
         Debugger::markAll(&trc);
         Debugger::markIncomingCrossCompartmentEdges(&trc);
 
         for (CompartmentsInZoneIter c(zone); !c.done(); c.next()) {
+            c->trace(&trc);
             WeakMapBase::markAll(c, &trc);
             if (c->watchpointMap)
                 c->watchpointMap->markAll(&trc);
         }
 
         // Mark all gray roots, making sure we call the trace callback to get the
         // current set.
         if (JSTraceDataOp op = grayRootTracer.op)
new file mode 100644
--- /dev/null
+++ b/js/src/vm/SavedFrame.h
@@ -0,0 +1,124 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef vm_SavedFrame_h
+#define vm_SavedFrame_h
+
+namespace js {
+
+class SavedFrame : public NativeObject {
+    friend class SavedStacks;
+
+  public:
+    static const Class          class_;
+    static const JSPropertySpec protoAccessors[];
+    static const JSFunctionSpec protoFunctions[];
+    static const JSFunctionSpec staticFunctions[];
+
+    // Prototype methods and properties to be exposed to JS.
+    static bool construct(JSContext* cx, unsigned argc, Value* vp);
+    static bool sourceProperty(JSContext* cx, unsigned argc, Value* vp);
+    static bool lineProperty(JSContext* cx, unsigned argc, Value* vp);
+    static bool columnProperty(JSContext* cx, unsigned argc, Value* vp);
+    static bool functionDisplayNameProperty(JSContext* cx, unsigned argc, Value* vp);
+    static bool asyncCauseProperty(JSContext* cx, unsigned argc, Value* vp);
+    static bool asyncParentProperty(JSContext* cx, unsigned argc, Value* vp);
+    static bool parentProperty(JSContext* cx, unsigned argc, Value* vp);
+    static bool toStringMethod(JSContext* cx, unsigned argc, Value* vp);
+
+    static void finalize(FreeOp* fop, JSObject* obj);
+
+    // Convenient getters for SavedFrame's reserved slots for use from C++.
+    JSAtom*      getSource();
+    uint32_t     getLine();
+    uint32_t     getColumn();
+    JSAtom*      getFunctionDisplayName();
+    JSAtom*      getAsyncCause();
+    SavedFrame*  getParent();
+    JSPrincipals* getPrincipals();
+
+    bool         isSelfHosted();
+
+    static bool isSavedFrameAndNotProto(JSObject& obj) {
+        return obj.is<SavedFrame>() &&
+               !obj.as<SavedFrame>().getReservedSlot(JSSLOT_SOURCE).isNull();
+    }
+
+    struct Lookup;
+    struct HashPolicy;
+
+    typedef HashSet<js::ReadBarriered<SavedFrame*>,
+                    HashPolicy,
+                    SystemAllocPolicy> Set;
+
+    class AutoLookupVector;
+
+    class MOZ_STACK_CLASS HandleLookup {
+        friend class AutoLookupVector;
+
+        Lookup& lookup;
+
+        explicit HandleLookup(Lookup& lookup) : lookup(lookup) { }
+
+      public:
+        inline Lookup& get() { return lookup; }
+        inline Lookup* operator->() { return &lookup; }
+    };
+
+  private:
+    static bool finishSavedFrameInit(JSContext* cx, HandleObject ctor, HandleObject proto);
+    void initFromLookup(HandleLookup lookup);
+
+    enum {
+        // The reserved slots in the SavedFrame class.
+        JSSLOT_SOURCE,
+        JSSLOT_LINE,
+        JSSLOT_COLUMN,
+        JSSLOT_FUNCTIONDISPLAYNAME,
+        JSSLOT_ASYNCCAUSE,
+        JSSLOT_PARENT,
+        JSSLOT_PRINCIPALS,
+        JSSLOT_PRIVATE_PARENT,
+
+        // The total number of reserved slots in the SavedFrame class.
+        JSSLOT_COUNT
+    };
+
+    // Because we hash the parent pointer, we need to rekey a saved frame
+    // whenever its parent was relocated by the GC. However, the GC doesn't
+    // notify us when this occurs. As a work around, we keep a duplicate copy of
+    // the parent pointer as a private value in a reserved slot. Whenever the
+    // private value parent pointer doesn't match the regular parent pointer, we
+    // know that GC moved the parent and we need to update our private value and
+    // rekey the saved frame in its hash set. These two methods are helpers for
+    // this process.
+    bool parentMoved();
+    void updatePrivateParent();
+
+    static bool checkThis(JSContext* cx, CallArgs& args, const char* fnName,
+                          MutableHandleObject frame);
+};
+
+struct SavedFrame::HashPolicy
+{
+    typedef SavedFrame::Lookup              Lookup;
+    typedef PointerHasher<SavedFrame*, 3>   SavedFramePtrHasher;
+    typedef PointerHasher<JSPrincipals*, 3> JSPrincipalsPtrHasher;
+
+    static HashNumber hash(const Lookup& lookup);
+    static bool       match(SavedFrame* existing, const Lookup& lookup);
+
+    typedef ReadBarriered<SavedFrame*> Key;
+    static void rekey(Key& key, const Key& newKey);
+};
+
+// Assert that if the given object is not null, that it must be either a
+// SavedFrame object or wrapper (Xray or CCW) around a SavedFrame object.
+inline void AssertObjectIsSavedFrameOrWrapper(JSContext* cx, HandleObject stack);
+
+} // namespace js
+
+#endif // vm_SavedFrame_h
--- a/js/src/vm/SavedStacks.cpp
+++ b/js/src/vm/SavedStacks.cpp
@@ -3,23 +3,22 @@
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "vm/SavedStacks.h"
 
 #include "mozilla/Attributes.h"
 #include "mozilla/DebugOnly.h"
-#include "mozilla/Maybe.h"
+#include "mozilla/Move.h"
 
 #include <algorithm>
 #include <math.h>
 
 #include "jsapi.h"
-#include "jscntxt.h"
 #include "jscompartment.h"
 #include "jsfriendapi.h"
 #include "jshashutil.h"
 #include "jsmath.h"
 #include "jsnum.h"
 #include "jsscript.h"
 #include "prmjtime.h"
 
@@ -28,64 +27,168 @@
 #include "js/Vector.h"
 #include "vm/Debugger.h"
 #include "vm/StringBuffer.h"
 #include "vm/WrapperObject.h"
 
 #include "jscntxtinlines.h"
 
 #include "vm/NativeObject-inl.h"
+#include "vm/Stack-inl.h"
 
 using mozilla::AddToHash;
 using mozilla::DebugOnly;
 using mozilla::HashString;
 using mozilla::Maybe;
+using mozilla::Move;
+using mozilla::Nothing;
+using mozilla::Some;
 
 namespace js {
 
 /**
  * Maximum number of saved frames returned for an async stack.
  */
 const unsigned ASYNC_STACK_MAX_FRAME_COUNT = 60;
 
+/* static */ Maybe<LiveSavedFrameCache::FramePtr>
+LiveSavedFrameCache::getFramePtr(FrameIter& iter)
+{
+    if (iter.hasUsableAbstractFramePtr())
+        return Some(FramePtr(iter.abstractFramePtr()));
+
+    if (iter.isPhysicalIonFrame())
+        return Some(FramePtr(iter.physicalIonFrame()));
+
+    return Nothing();
+}
+
+/* static */ void
+LiveSavedFrameCache::trace(LiveSavedFrameCache* cache, JSTracer* trc)
+{
+    if (!cache->initialized())
+        return;
+
+    for (auto* entry = cache->frames->begin(); entry < cache->frames->end(); entry++) {
+        TraceEdge(trc,
+                  &entry->savedFrame,
+                  "LiveSavedFrameCache::frames SavedFrame");
+    }
+}
+
+bool
+LiveSavedFrameCache::insert(JSContext* cx, FramePtr& framePtr, jsbytecode* pc,
+                            HandleSavedFrame savedFrame)
+{
+    MOZ_ASSERT(initialized());
+
+    if (!frames->emplaceBack(framePtr, pc, savedFrame)) {
+        ReportOutOfMemory(cx);
+        return false;
+    }
+
+    // Safe to dereference the cache key because the stack frames are still
+    // live. After this point, they should never be dereferenced again.
+    if (framePtr.is<AbstractFramePtr>())
+        framePtr.as<AbstractFramePtr>().setHasCachedSavedFrame();
+    else
+        framePtr.as<jit::CommonFrameLayout*>()->setHasCachedSavedFrame();
+
+    return true;
+}
+
+void
+LiveSavedFrameCache::find(JSContext* cx, FrameIter& frameIter, MutableHandleSavedFrame frame) const
+{
+    MOZ_ASSERT(initialized());
+    MOZ_ASSERT(!frameIter.done());
+    MOZ_ASSERT(frameIter.hasCachedSavedFrame());
+
+    Maybe<FramePtr> maybeFramePtr = getFramePtr(frameIter);
+    MOZ_ASSERT(maybeFramePtr.isSome());
+
+    FramePtr framePtr(*maybeFramePtr);
+    jsbytecode* pc = frameIter.pc();
+    size_t numberStillValid = 0;
+
+    frame.set(nullptr);
+    for (auto* p = frames->begin(); p < frames->end(); p++) {
+        numberStillValid++;
+        if (framePtr == p->framePtr && pc == p->pc) {
+            frame.set(p->savedFrame);
+            break;
+        }
+    }
+
+    if (!frame) {
+        frames->clear();
+        return;
+    }
+
+    MOZ_ASSERT(0 < numberStillValid && numberStillValid <= frames->length());
+
+    if (frame->compartment() != cx->compartment()) {
+        frame.set(nullptr);
+        numberStillValid--;
+    }
+
+    // Everything after the cached SavedFrame are stale younger frames we have
+    // since popped.
+    frames->shrinkBy(frames->length() - numberStillValid);
+}
+
 struct SavedFrame::Lookup {
     Lookup(JSAtom* source, uint32_t line, uint32_t column,
            JSAtom* functionDisplayName, JSAtom* asyncCause, SavedFrame* parent,
-           JSPrincipals* principals)
+           JSPrincipals* principals, Maybe<LiveSavedFrameCache::FramePtr> framePtr, jsbytecode* pc,
+           Activation* activation)
       : source(source),
         line(line),
         column(column),
         functionDisplayName(functionDisplayName),
         asyncCause(asyncCause),
         parent(parent),
-        principals(principals)
+        principals(principals),
+        framePtr(framePtr),
+        pc(pc),
+        activation(activation)
     {
         MOZ_ASSERT(source);
+        MOZ_ASSERT(activation);
     }
 
     explicit Lookup(SavedFrame& savedFrame)
       : source(savedFrame.getSource()),
         line(savedFrame.getLine()),
         column(savedFrame.getColumn()),
         functionDisplayName(savedFrame.getFunctionDisplayName()),
         asyncCause(savedFrame.getAsyncCause()),
         parent(savedFrame.getParent()),
-        principals(savedFrame.getPrincipals())
+        principals(savedFrame.getPrincipals()),
+        framePtr(Nothing()),
+        pc(nullptr),
+        activation(nullptr)
     {
         MOZ_ASSERT(source);
     }
 
-    JSAtom*      source;
-    uint32_t     line;
-    uint32_t     column;
-    JSAtom*      functionDisplayName;
-    JSAtom*      asyncCause;
-    SavedFrame*  parent;
+    JSAtom*       source;
+    uint32_t      line;
+    uint32_t      column;
+    JSAtom*       functionDisplayName;
+    JSAtom*       asyncCause;
+    SavedFrame*   parent;
     JSPrincipals* principals;
 
+    // These are used only by the LiveSavedFrameCache and not used for identity or
+    // hashing.
+    Maybe<LiveSavedFrameCache::FramePtr> framePtr;
+    jsbytecode*                          pc;
+    Activation*                          activation;
+
     void trace(JSTracer* trc) {
         TraceManuallyBarrieredEdge(trc, &source, "SavedFrame::Lookup::source");
         if (functionDisplayName) {
             TraceManuallyBarrieredEdge(trc, &functionDisplayName,
                                        "SavedFrame::Lookup::functionDisplayName");
         }
         if (asyncCause)
             TraceManuallyBarrieredEdge(trc, &asyncCause, "SavedFrame::Lookup::asyncCause");
@@ -394,18 +497,17 @@ GetFirstSubsumedSavedFrame(JSContext* cx
 
 /* static */ bool
 SavedFrame::checkThis(JSContext* cx, CallArgs& args, const char* fnName,
                       MutableHandleObject frame)
 {
     const Value& thisValue = args.thisv();
 
     if (!thisValue.isObject()) {
-        JS_ReportErrorNumber(cx, GetErrorMessage, nullptr, JSMSG_NOT_NONNULL_OBJECT,
-                             InformalValueTypeName(thisValue));
+        JS_ReportErrorNumber(cx, GetErrorMessage, nullptr, JSMSG_NOT_NONNULL_OBJECT, InformalValueTypeName(thisValue));
         return false;
     }
 
     JSObject* thisObject = CheckedUnwrap(&thisValue.toObject());
     if (!thisObject || !thisObject->is<SavedFrame>()) {
         JS_ReportErrorNumber(cx, GetErrorMessage, nullptr, JSMSG_INCOMPATIBLE_PROTO,
                              SavedFrame::class_.name, fnName,
                              thisObject ? thisObject->getClass()->name : "object");
@@ -809,17 +911,17 @@ SavedStacks::init()
 }
 
 bool
 SavedStacks::saveCurrentStack(JSContext* cx, MutableHandleSavedFrame frame, unsigned maxFrameCount)
 {
     MOZ_ASSERT(initialized());
     assertSameCompartment(cx, this);
 
-    if (creatingSavedFrame) {
+    if (creatingSavedFrame || cx->isExceptionPending()) {
         frame.set(nullptr);
         return true;
     }
 
     FrameIter iter(cx, FrameIter::ALL_CONTEXTS, FrameIter::GO_THROUGH_SAVED);
     return insertFrames(cx, iter, frame, maxFrameCount);
 }
 
@@ -850,23 +952,22 @@ SavedStacks::sweep(JSRuntime* rt)
     }
 
     sweepPCLocationMap();
 }
 
 void
 SavedStacks::trace(JSTracer* trc)
 {
-    if (!pcLocationMap.initialized())
-        return;
-
-    // Mark each of the source strings in our pc to location cache.
-    for (PCLocationMap::Enum e(pcLocationMap); !e.empty(); e.popFront()) {
-        LocationValue& loc = e.front().value();
-        TraceEdge(trc, &loc.source, "SavedStacks::PCLocationMap's memoized script source name");
+    if (pcLocationMap.initialized()) {
+        // Mark each of the source strings in our pc to location cache.
+        for (PCLocationMap::Enum e(pcLocationMap); !e.empty(); e.popFront()) {
+            LocationValue& loc = e.front().value();
+            TraceEdge(trc, &loc.source, "SavedStacks::PCLocationMap's memoized script source name");
+        }
     }
 }
 
 uint32_t
 SavedStacks::count()
 {
     MOZ_ASSERT(initialized());
     return frames.count();
@@ -901,16 +1002,18 @@ SavedStacks::insertFrames(JSContext* cx,
     // only contain the FrameIter data we need. The `SavedFrame::Lookup`
     // objects are partially initialized with everything except their parent
     // pointers on the first pass, and then we fill in the parent pointers as we
     // return in the second pass.
 
     Activation* asyncActivation = nullptr;
     RootedSavedFrame asyncStack(cx, nullptr);
     RootedString asyncCause(cx, nullptr);
+    bool parentIsInCache = false;
+    RootedSavedFrame cachedFrame(cx, nullptr);
 
     // Accumulate the vector of Lookup objects in |stackChain|.
     SavedFrame::AutoLookupVector stackChain(cx);
     while (!iter.done()) {
         Activation& activation = *iter.activation();
 
         if (asyncActivation && asyncActivation != &activation) {
             // We found an async stack in the previous activation, and we
@@ -938,60 +1041,86 @@ SavedStacks::insertFrames(JSContext* cx,
 
         AutoLocationValueRooter location(cx);
         {
             AutoCompartment ac(cx, iter.compartment());
             if (!cx->compartment()->savedStacks().getLocation(cx, iter, &location))
                 return false;
         }
 
+        // The bit set means that the next older parent (frame, pc) pair *must*
+        // be in the cache.
+        if (maxFrameCount == 0)
+            parentIsInCache = iter.hasCachedSavedFrame();
+
         auto displayAtom = iter.isNonEvalFunctionFrame() ? iter.functionDisplayAtom() : nullptr;
         if (!stackChain->emplaceBack(location->source,
                                      location->line,
                                      location->column,
                                      displayAtom,
                                      nullptr,
                                      nullptr,
-                                     iter.compartment()->principals()))
+                                     iter.compartment()->principals(),
+                                     LiveSavedFrameCache::getFramePtr(iter),
+                                     iter.pc(),
+                                     &activation))
         {
             ReportOutOfMemory(cx);
             return false;
         }
 
         ++iter;
 
-        // If maxFrameCount is zero there's no limit on the number of frames.
-        if (maxFrameCount == 0)
-            continue;
-
         if (maxFrameCount == 1) {
             // The frame we just saved was the last one we were asked to save.
             // If we had an async stack, ensure we don't use any of its frames.
             asyncStack.set(nullptr);
             break;
         }
 
+        if (parentIsInCache &&
+            !iter.done() &&
+            (iter.hasUsableAbstractFramePtr() || iter.isPhysicalIonFrame()))
+        {
+            auto* cache = activation.getLiveSavedFrameCache(cx);
+            if (!cache)
+                return false;
+            cache->find(cx, iter, &cachedFrame);
+            if (cachedFrame)
+                break;
+        }
+
+        // If maxFrameCount is zero there's no limit on the number of frames.
+        if (maxFrameCount == 0)
+            continue;
+
         maxFrameCount--;
     }
 
     // Limit the depth of the async stack, if any, and ensure that the
     // SavedFrame instances we use are stored in the same compartment as the
     // rest of the synchronous stack chain.
-    RootedSavedFrame parentFrame(cx, nullptr);
+    RootedSavedFrame parentFrame(cx, cachedFrame);
     if (asyncStack && !adoptAsyncStack(cx, asyncStack, asyncCause, &parentFrame, maxFrameCount))
         return false;
 
     // Iterate through |stackChain| in reverse order and get or create the
     // actual SavedFrame instances.
     for (size_t i = stackChain->length(); i != 0; i--) {
         SavedFrame::HandleLookup lookup = stackChain[i-1];
         lookup->parent = parentFrame;
         parentFrame.set(getOrCreateSavedFrame(cx, lookup));
         if (!parentFrame)
             return false;
+
+        if (maxFrameCount == 0 && lookup->framePtr && parentFrame != cachedFrame) {
+            auto* cache = lookup->activation->getLiveSavedFrameCache(cx);
+            if (!cache || !cache->insert(cx, *lookup->framePtr, lookup->pc, parentFrame))
+                return false;
+        }
     }
 
     frame.set(parentFrame);
     return true;
 }
 
 bool
 SavedStacks::adoptAsyncStack(JSContext* cx, HandleSavedFrame asyncStack,
--- a/js/src/vm/SavedStacks.h
+++ b/js/src/vm/SavedStacks.h
@@ -6,18 +6,21 @@
 
 #ifndef vm_SavedStacks_h
 #define vm_SavedStacks_h
 
 #include "jscntxt.h"
 #include "jsmath.h"
 #include "jswrapper.h"
 #include "js/HashTable.h"
+#include "vm/SavedFrame.h"
 #include "vm/Stack.h"
 
+namespace js {
+
 // # Saved Stacks
 //
 // The `SavedStacks` class provides a compact way to capture and save JS stacks
 // as `SavedFrame` `JSObject` subclasses. A single `SavedFrame` object
 // represents one frame that was on the stack, and has a strong reference to its
 // parent `SavedFrame` (the next youngest frame). This reference is null when
 // the `SavedFrame` object is the oldest frame that was on the stack.
 //
@@ -137,133 +140,16 @@
 // frames.
 //
 // In the case of z, the `SavedFrame` accessors are called with the `SavedFrame`
 // object in the `this` value, and the content compartment as the cx's current
 // compartment. Similar to the case of y, only the B and C frames are exposed
 // because the cx's current compartment's principals do not subsume A's captured
 // principals.
 
-
-namespace js {
-
-class SavedFrame;
-typedef JS::Handle<SavedFrame*> HandleSavedFrame;
-typedef JS::MutableHandle<SavedFrame*> MutableHandleSavedFrame;
-typedef JS::Rooted<SavedFrame*> RootedSavedFrame;
-
-class SavedFrame : public NativeObject {
-    friend class SavedStacks;
-
-  public:
-    static const Class          class_;
-    static void finalize(FreeOp* fop, JSObject* obj);
-    static const JSPropertySpec protoAccessors[];
-    static const JSFunctionSpec protoFunctions[];
-    static const JSFunctionSpec staticFunctions[];
-
-    // Prototype methods and properties to be exposed to JS.
-    static bool construct(JSContext* cx, unsigned argc, Value* vp);
-    static bool sourceProperty(JSContext* cx, unsigned argc, Value* vp);
-    static bool lineProperty(JSContext* cx, unsigned argc, Value* vp);
-    static bool columnProperty(JSContext* cx, unsigned argc, Value* vp);
-    static bool functionDisplayNameProperty(JSContext* cx, unsigned argc, Value* vp);
-    static bool asyncCauseProperty(JSContext* cx, unsigned argc, Value* vp);
-    static bool asyncParentProperty(JSContext* cx, unsigned argc, Value* vp);
-    static bool parentProperty(JSContext* cx, unsigned argc, Value* vp);
-    static bool toStringMethod(JSContext* cx, unsigned argc, Value* vp);
-
-    // Convenient getters for SavedFrame's reserved slots for use from C++.
-    JSAtom*      getSource();
-    uint32_t     getLine();
-    uint32_t     getColumn();
-    JSAtom*      getFunctionDisplayName();
-    JSAtom*      getAsyncCause();
-    SavedFrame*  getParent();
-    JSPrincipals* getPrincipals();
-
-    bool         isSelfHosted();
-
-    static bool isSavedFrameAndNotProto(JSObject& obj) {
-        return obj.is<SavedFrame>() &&
-               !obj.as<SavedFrame>().getReservedSlot(JSSLOT_SOURCE).isNull();
-    }
-
-    struct Lookup;
-    struct HashPolicy;
-
-    typedef HashSet<js::ReadBarriered<SavedFrame*>,
-                    HashPolicy,
-                    SystemAllocPolicy> Set;
-
-    class AutoLookupVector;
-
-    class MOZ_STACK_CLASS HandleLookup {
-        friend class AutoLookupVector;
-
-        Lookup& lookup;
-
-        explicit HandleLookup(Lookup& lookup) : lookup(lookup) { }
-
-      public:
-        inline Lookup& get() { return lookup; }
-        inline Lookup* operator->() { return &lookup; }
-    };
-
-  private:
-    static bool finishSavedFrameInit(JSContext* cx, HandleObject ctor, HandleObject proto);
-    void initFromLookup(HandleLookup lookup);
-
-    enum {
-        // The reserved slots in the SavedFrame class.
-        JSSLOT_SOURCE,
-        JSSLOT_LINE,
-        JSSLOT_COLUMN,
-        JSSLOT_FUNCTIONDISPLAYNAME,
-        JSSLOT_ASYNCCAUSE,
-        JSSLOT_PARENT,
-        JSSLOT_PRINCIPALS,
-        JSSLOT_PRIVATE_PARENT,
-
-        // The total number of reserved slots in the SavedFrame class.
-        JSSLOT_COUNT
-    };
-
-    // Because we hash the parent pointer, we need to rekey a saved frame
-    // whenever its parent was relocated by the GC. However, the GC doesn't
-    // notify us when this occurs. As a work around, we keep a duplicate copy of
-    // the parent pointer as a private value in a reserved slot. Whenever the
-    // private value parent pointer doesn't match the regular parent pointer, we
-    // know that GC moved the parent and we need to update our private value and
-    // rekey the saved frame in its hash set. These two methods are helpers for
-    // this process.
-    bool parentMoved();
-    void updatePrivateParent();
-
-    static bool checkThis(JSContext* cx, CallArgs& args, const char* fnName,
-                          MutableHandleObject frame);
-};
-
-struct SavedFrame::HashPolicy
-{
-    typedef SavedFrame::Lookup               Lookup;
-    typedef PointerHasher<SavedFrame*, 3>   SavedFramePtrHasher;
-    typedef PointerHasher<JSPrincipals*, 3> JSPrincipalsPtrHasher;
-
-    static HashNumber hash(const Lookup& lookup);
-    static bool       match(SavedFrame* existing, const Lookup& lookup);
-
-    typedef ReadBarriered<SavedFrame*> Key;
-    static void rekey(Key& key, const Key& newKey);
-};
-
-// Assert that if the given object is not null, that it must be either a
-// SavedFrame object or wrapper (Xray or CCW) around a SavedFrame object.
-inline void AssertObjectIsSavedFrameOrWrapper(JSContext* cx, HandleObject stack);
-
 class SavedStacks {
     friend JSObject* SavedStacksMetadataCallback(JSContext* cx, JSObject* target);
 
   public:
     SavedStacks()
       : frames(),
         allocationSamplingProbability(1.0),
         allocationSkipCount(0),
@@ -304,25 +190,25 @@ class SavedStacks {
         }
 
         ~AutoReentrancyGuard()
         {
             stacks.creatingSavedFrame = false;
         }
     };
 
-    bool       insertFrames(JSContext* cx, FrameIter& iter, MutableHandleSavedFrame frame,
-                            unsigned maxFrameCount = 0);
-    bool       adoptAsyncStack(JSContext* cx, HandleSavedFrame asyncStack,
-                               HandleString asyncCause,
-                               MutableHandleSavedFrame adoptedStack,
-                               unsigned maxFrameCount);
+    bool        insertFrames(JSContext* cx, FrameIter& iter, MutableHandleSavedFrame frame,
+                             unsigned maxFrameCount = 0);
+    bool        adoptAsyncStack(JSContext* cx, HandleSavedFrame asyncStack,
+                                HandleString asyncCause,
+                                MutableHandleSavedFrame adoptedStack,
+                                unsigned maxFrameCount);
     SavedFrame* getOrCreateSavedFrame(JSContext* cx, SavedFrame::HandleLookup lookup);
     SavedFrame* createFrameFromLookup(JSContext* cx, SavedFrame::HandleLookup lookup);
-    void       chooseSamplingProbability(JSContext* cx);
+    void        chooseSamplingProbability(JSContext* cx);
 
     // Cache for memoizing PCToLineNumber lookups.
 
     struct PCKey {
         PCKey(JSScript* script, jsbytecode* pc) : script(script), pc(pc) { }
 
         PreBarrieredScript script;
         jsbytecode*        pc;
--- a/js/src/vm/Stack-inl.h
+++ b/js/src/vm/Stack-inl.h
@@ -882,16 +882,17 @@ AbstractFramePtr::popWith(JSContext* cx)
 
 Activation::Activation(JSContext* cx, Kind kind)
   : cx_(cx),
     compartment_(cx->compartment()),
     prev_(cx->runtime_->activation_),
     prevProfiling_(prev_ ? prev_->mostRecentProfiling() : nullptr),
     savedFrameChain_(0),
     hideScriptedCallerCount_(0),
+    frameCache_(cx),
     asyncStack_(cx, cx->runtime_->asyncStackForNewActivations),
     asyncCause_(cx, cx->runtime_->asyncCauseForNewActivations),
     asyncCallIsExplicit_(cx->runtime_->asyncCallIsExplicit),
     entryMonitor_(cx->runtime_->entryMonitor),
     kind_(kind)
 {
     cx->runtime_->asyncStackForNewActivations = nullptr;
     cx->runtime_->asyncCauseForNewActivations = nullptr;
@@ -928,16 +929,23 @@ Activation::isProfiling() const
 Activation*
 Activation::mostRecentProfiling()
 {
     if (isProfiling())
         return this;
     return prevProfiling_;
 }
 
+inline LiveSavedFrameCache*
+Activation::getLiveSavedFrameCache(JSContext* cx) {
+    if (!frameCache_.get().initialized() && !frameCache_.get().init(cx))
+        return nullptr;
+    return frameCache_.address();
+}
+
 InterpreterActivation::InterpreterActivation(RunState& state, JSContext* cx,
                                              InterpreterFrame* entryFrame)
   : Activation(cx, Interpreter),
     entryFrame_(entryFrame),
     opMask_(0)
 #ifdef DEBUG
   , oldFrameCount_(cx->runtime()->interpreterStack().frameCount_)
 #endif
@@ -1005,11 +1013,41 @@ InterpreterActivation::resumeGeneratorFr
 }
 
 inline JSContext*
 AsmJSActivation::cx()
 {
     return cx_->asJSContext();
 }
 
+inline bool
+FrameIter::hasCachedSavedFrame() const
+{
+    if (isAsmJS())
+        return false;
+
+    if (hasUsableAbstractFramePtr())
+        return abstractFramePtr().hasCachedSavedFrame();
+
+    MOZ_ASSERT(data_.jitFrames_.isIonScripted());
+    // SavedFrame caching is done at the physical frame granularity (rather than
+    // for each inlined frame) for ion. Therefore, it is impossible to have a
+    // cached SavedFrame if this frame is not a physical frame.
+    return isPhysicalIonFrame() && data_.jitFrames_.current()->hasCachedSavedFrame();
+}
+
+inline void
+FrameIter::setHasCachedSavedFrame()
+{
+    MOZ_ASSERT(!isAsmJS());
+
+    if (hasUsableAbstractFramePtr()) {
+        abstractFramePtr().setHasCachedSavedFrame();
+        return;
+    }
+
+    MOZ_ASSERT(isPhysicalIonFrame());
+    data_.jitFrames_.current()->setHasCachedSavedFrame();
+}
+
 } /* namespace js */
 
 #endif /* vm_Stack_inl_h */
--- a/js/src/vm/Stack.cpp
+++ b/js/src/vm/Stack.cpp
@@ -466,25 +466,16 @@ InterpreterStack::pushExecuteFrame(JSCon
     fp->initExecuteFrame(cx, script, evalInFrame, thisv, newTargetValue, scopeChain, type);
     fp->initLocals();
 
     return fp;
 }
 
 /*****************************************************************************/
 
-bool
-FrameIter::hasCachedSavedFrame(JSContext* cx, bool* hasCachedSavedFramep)
-{
-    if (isIon() && !ensureHasRematerializedFrame(cx))
-        return false;
-    *hasCachedSavedFramep = abstractFramePtr().hasCachedSavedFrame();
-    return true;
-}
-
 void
 FrameIter::popActivation()
 {
     ++data_.activations_;
     settleOnActivation();
 }
 
 void
--- a/js/src/vm/Stack.h
+++ b/js/src/vm/Stack.h
@@ -3,52 +3,62 @@
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef vm_Stack_h
 #define vm_Stack_h
 
 #include "mozilla/Atomics.h"
+#include "mozilla/Maybe.h"
 #include "mozilla/MemoryReporting.h"
+#include "mozilla/Variant.h"
 
 #include "jsfun.h"
 #include "jsscript.h"
 #include "jsutil.h"
 
 #include "asmjs/AsmJSFrameIterator.h"
+#include "gc/Rooting.h"
 #include "jit/JitFrameIterator.h"
 #ifdef CHECK_OSIPOINT_REGISTERS
 #include "jit/Registers.h" // for RegisterDump
 #endif
+#include "js/RootingAPI.h"
+#include "vm/SavedFrame.h"
 
 struct JSCompartment;
 
 namespace JS {
 namespace dbg {
 class AutoEntryMonitor;
 } // namespace dbg
 } // namespace JS
 
 namespace js {
 
 class ArgumentsObject;
 class AsmJSModule;
 class InterpreterRegs;
 class CallObject;
+class FrameIter;
 class ScopeObject;
 class ScriptFrameIter;
 class SPSProfiler;
 class InterpreterFrame;
 class StaticBlockObject;
 
 class ScopeCoordinate;
 
 class SavedFrame;
 
+namespace jit {
+class CommonFrameLayout;
+}
+
 // VM stack layout
 //
 // A JSRuntime's stack consists of a linked list of activations. Every activation
 // contains a number of scripted frames that are either running in the interpreter
 // (InterpreterActivation) or JIT code (JitActivation). The frames inside a single
 // activation are contiguous: whenever C++ calls back into JS, a new activation is
 // pushed.
 //
@@ -1103,16 +1113,138 @@ struct DefaultHasher<AbstractFramePtr> {
 
     static bool match(const AbstractFramePtr& k, const Lookup& l) {
         return k == l;
     }
 };
 
 /*****************************************************************************/
 
+// SavedFrame caching to minimize stack walking.
+//
+// SavedFrames are hash consed to minimize expensive (with regards to both space
+// and time) allocations in the face of many stack frames that tend to share the
+// same older tail frames. Despite that, in scenarios where we are frequently
+// saving the same or similar stacks, such as when the Debugger's allocation
+// site tracking is enabled, these older stack frames still get walked
+// repeatedly just to create the lookup structs to find their corresponding
+// SavedFrames in the hash table. This stack walking is slow, and we would like
+// to minimize it.
+//
+// We have reserved a bit on most of SpiderMonkey's various frame
+// representations (the exceptions being asm and inlined ion frames). As we
+// create SavedFrame objects for live stack frames in SavedStacks::insertFrames,
+// we set this bit and append the SavedFrame object to the cache. As we walk the
+// stack, if we encounter a frame that has this bit set, that indicates that we
+// have already captured a SavedFrame object for the given stack frame (but not
+// necessarily the current pc) during a previous call to insertFrames. We know
+// that the frame's parent was also captured and has its bit set as well, but
+// additionally we know the parent was captured at its current pc. For the
+// parent, rather than continuing the expensive stack walk, we do a quick and
+// cache-friendly linear search through the frame cache. Upon finishing search
+// through the frame cache, stale entries are removed.
+//
+// The frame cache maintains the invariant that its first E[0] .. E[j-1]
+// entries are live and sorted from oldest to younger frames, where 0 < j < n
+// and n = the length of the cache. When searching the cache, we require
+// that we are considering the youngest live frame whose bit is set. Every
+// cache entry E[i] where i >= j is a stale entry. Consider the following
+// scenario:
+//
+//     P  >  Q  >  R  >  S          Initial stack, bits not set.
+//     P* >  Q* >  R* >  S*         Capture a SavedFrame stack, set bits.
+//     P* >  Q* >  R*               Return from S.
+//     P* >  Q*                     Return from R.
+//     P* >  Q* >  T                Call T, its bit is not set.
+//
+// The frame cache was populated with [P, Q, R, S] when we captured a
+// SavedFrame stack, but because we returned from frames R and S, their
+// entries in the frame cache are now stale. This fact is unbeknownst to us
+// because we do not observe frame pops. Upon capturing a second stack, we
+// start stack walking at the youngest frame T, which does not have its bit
+// set and must take the hash table lookup slow path rather than the frame
+// cache short circuit. Next we proceed to Q and find that it has its bit
+// set, and it is therefore the youngest live frame with its bit set. We
+// search through the frame cache from oldest to youngest and find the cache
+// entry matching Q. We know that T is the next younger live frame from Q
+// and that T does not have an entry in the frame cache because its bit was
+// not set. Therefore, we have found entry E[j-1] and the subsequent entries
+// are stale and should be purged from the frame cache.
+//
+// We have a LiveSavedFrameCache for each activation to minimize the number of
+// entries that must be scanned through, and to avoid the headaches of
+// maintaining a cache for each compartment and invalidating stale cache entries
+// in the presence of cross-compartment calls.
+class LiveSavedFrameCache : public JS::StaticTraceable
+{
+  public:
+    using FramePtr = mozilla::Variant<AbstractFramePtr, jit::CommonFrameLayout*>;
+
+  private:
+    struct Entry
+    {
+        FramePtr                    framePtr;
+        jsbytecode*                 pc;
+        RelocatablePtr<SavedFrame*> savedFrame;
+
+        Entry(FramePtr& framePtr, jsbytecode* pc, SavedFrame* savedFrame)
+          : framePtr(framePtr)
+          , pc(pc)
+          , savedFrame(savedFrame)
+        { }
+    };
+
+    using EntryVector = Vector<Entry, 0, SystemAllocPolicy>;
+    EntryVector* frames;
+
+    LiveSavedFrameCache(const LiveSavedFrameCache&) = delete;
+    LiveSavedFrameCache& operator=(const LiveSavedFrameCache&) = delete;
+
+  public:
+    explicit LiveSavedFrameCache() : frames(nullptr) { }
+
+    LiveSavedFrameCache(LiveSavedFrameCache&& rhs)
+        : frames(rhs.frames)
+    {
+        MOZ_ASSERT(this != &rhs, "self-move disallowed");
+        rhs.frames = nullptr;
+    }
+
+    ~LiveSavedFrameCache() {
+        if (frames) {
+            js_delete(frames);
+            frames = nullptr;
+        }
+    }
+
+    bool initialized() const { return !!frames; }
+    bool init(JSContext* cx) {
+        frames = js_new<EntryVector>();
+        if (!frames) {
+            JS_ReportOutOfMemory(cx);
+            return false;
+        }
+        return true;
+    }
+
+    static mozilla::Maybe<FramePtr> getFramePtr(FrameIter& iter);
+    static void trace(LiveSavedFrameCache* cache, JSTracer* trc);
+
+    void find(JSContext* cx, FrameIter& frameIter, MutableHandleSavedFrame frame) const;
+    bool insert(JSContext* cx, FramePtr& framePtr, jsbytecode* pc, HandleSavedFrame savedFrame);
+};
+
+static_assert(sizeof(LiveSavedFrameCache) == sizeof(uintptr_t),
+              "Every js::Activation has a LiveSavedFrameCache, so we need to be pretty careful "
+              "about avoiding bloat. If you're adding members to LiveSavedFrameCache, maybe you "
+              "should consider figuring out a way to make js::Activation have a "
+              "LiveSavedFrameCache* instead of a Rooted<LiveSavedFrameCache>.");
+
+/*****************************************************************************/
+
 class InterpreterActivation;
 class AsmJSActivation;
 
 namespace jit {
     class JitActivation;
 } // namespace jit
 
 class Activation
@@ -1131,16 +1263,20 @@ class Activation
 
     // Counter incremented by JS::HideScriptedCaller and decremented by
     // JS::UnhideScriptedCaller. If > 0 for the top activation,
     // DescribeScriptedCaller will return null instead of querying that
     // activation, which should prompt the caller to consult embedding-specific
     // data structures instead.
     size_t hideScriptedCallerCount_;
 
+    // The cache of SavedFrame objects we have already captured when walking
+    // this activation's stack.
+    Rooted<LiveSavedFrameCache> frameCache_;
+
     // Youngest saved frame of an async stack that will be iterated during stack
     // capture in place of the actual stack of previous activations. Note that
     // the stack of this activation is captured entirely before this is used.
     //
     // Usually this is nullptr, meaning that normal stack capture will occur.
     // When this is set, the stack of any previous activation is ignored.
     Rooted<SavedFrame*> asyncStack_;
 
@@ -1235,16 +1371,18 @@ class Activation
     JSString* asyncCause() {
         return asyncCause_;
     }
 
     bool asyncCallIsExplicit() const {
         return asyncCallIsExplicit_;
     }
 
+    inline LiveSavedFrameCache* getLiveSavedFrameCache(JSContext* cx);
+
   private:
     Activation(const Activation& other) = delete;
     void operator=(const Activation& other) = delete;
 };
 
 // This variable holds a special opcode value which is greater than all normal
 // opcodes, and is chosen such that the bitwise or of this value with any
 // opcode is this value.
@@ -1725,24 +1863,27 @@ class FrameIter
     JSCompartment* compartment() const;
     Activation* activation() const { return data_.activations_.activation(); }
 
     bool isInterp() const { MOZ_ASSERT(!done()); return data_.state_ == INTERP;  }
     bool isJit() const { MOZ_ASSERT(!done()); return data_.state_ == JIT; }
     bool isAsmJS() const { MOZ_ASSERT(!done()); return data_.state_ == ASMJS; }
     inline bool isIon() const;
     inline bool isBaseline() const;
+    inline bool isPhysicalIonFrame() const;
 
     bool isFunctionFrame() const;
     bool isGlobalFrame() const;
     bool isEvalFrame() const;
     bool isNonEvalFunctionFrame() const;
     bool hasArgs() const { return isNonEvalFunctionFrame(); }
 
-    bool hasCachedSavedFrame(JSContext* cx, bool* hasCachedSavedFramep);
+    // These two methods may not be called with asm frames.
+    inline bool hasCachedSavedFrame() const;
+    inline void setHasCachedSavedFrame();
 
     ScriptSource* scriptSource() const;
     const char* scriptFilename() const;
     const char16_t* scriptDisplayURL() const;
     unsigned computeLine(uint32_t* column = nullptr) const;
     JSAtom* functionDisplayAtom() const;
     bool mutedErrors() const;
 
@@ -1821,16 +1962,19 @@ class FrameIter
 
     AbstractFramePtr abstractFramePtr() const;
     AbstractFramePtr copyDataAsAbstractFramePtr() const;
     Data* copyData() const;
 
     // This can only be called when isInterp():
     inline InterpreterFrame* interpFrame() const;
 
+    // This can only be called when isPhysicalIonFrame():
+    inline jit::CommonFrameLayout* physicalIonFrame() const;
+
   private:
     Data data_;
     jit::InlineFrameIterator ionInlineFrames_;
 
     void popActivation();
     void popInterpreterFrame();
     void nextJitFrame();
     void popJitFrame();
@@ -2029,10 +2173,25 @@ FrameIter::isBaseline() const
 
 inline InterpreterFrame*
 FrameIter::interpFrame() const
 {
     MOZ_ASSERT(data_.state_ == INTERP);
     return data_.interpFrames_.frame();
 }
 
+inline bool
+FrameIter::isPhysicalIonFrame() const
+{
+    return isJit() &&
+           data_.jitFrames_.isIonScripted() &&
+           ionInlineFrames_.frameNo() == 0;
+}
+
+inline jit::CommonFrameLayout*
+FrameIter::physicalIonFrame() const
+{
+    MOZ_ASSERT(isPhysicalIonFrame());
+    return data_.jitFrames_.current();
+}
+
 }  /* namespace js */
 #endif /* vm_Stack_h */