Bug 1164294 - Implement a linear-time ephemeron marking algorithm, r=terrence, r=jonco
authorSteve Fink <sfink@mozilla.com>
Wed, 12 Aug 2015 16:55:40 -0700
changeset 257894 b4a0665236823079c7caaf0516d493e9098287ee
parent 257893 9bea8fc16ae2f748d18e352524cc6a5e1c24775e
child 257895 23146a80594cf148f6d52696e36706de01abd817
push id29233
push userkwierso@gmail.com
push dateFri, 14 Aug 2015 23:32:11 +0000
treeherdermozilla-central@45bea43ad812 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersterrence, jonco
bugs1164294
milestone43.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 1164294 - Implement a linear-time ephemeron marking algorithm, r=terrence, r=jonco
js/public/TracingAPI.h
js/src/devtools/rootAnalysis/annotations.js
js/src/ds/OrderedHashTable.h
js/src/gc/Marking.cpp
js/src/gc/Marking.h
js/src/gc/Tracer.h
js/src/jit-test/tests/gc/weak-marking-01.js
js/src/jit-test/tests/gc/weak-marking-02.js
js/src/jsapi-tests/testWeakMap.cpp
js/src/jsgc.cpp
js/src/jswatchpoint.cpp
js/src/jswatchpoint.h
js/src/jsweakmap.cpp
js/src/jsweakmap.h
js/src/vm/Debugger.h
--- a/js/public/TracingAPI.h
+++ b/js/public/TracingAPI.h
@@ -22,51 +22,67 @@ template <typename T> class TenuredHeap;
 
 // Returns a static string equivalent of |kind|.
 JS_FRIEND_API(const char*)
 GCTraceKindToAscii(JS::TraceKind kind);
 
 } // namespace JS
 
 enum WeakMapTraceKind {
-    DoNotTraceWeakMaps = 0,
-    TraceWeakMapValues = 1,
-    TraceWeakMapKeysValues = 2
+    // Do true ephemeron marking with an iterative weak marking phase.
+    DoNotTraceWeakMaps,
+
+    // Do true ephemeron marking with a weak key lookup marking phase. This is
+    // expected to be constant for the lifetime of a JSTracer; it does not
+    // change when switching from "plain" marking to weak marking.
+    ExpandWeakMaps,
+
+    // Trace through to all values, irrespective of whether the keys are live
+    // or not. Used for non-marking tracers.
+    TraceWeakMapValues,
+
+    // Trace through to all keys and values, irrespective of whether the keys
+    // are live or not. Used for non-marking tracers.
+    TraceWeakMapKeysValues
 };
 
 class JS_PUBLIC_API(JSTracer)
 {
   public:
     // Return the runtime set on the tracer.
     JSRuntime* runtime() const { return runtime_; }
 
-    // Return the weak map tracing behavior set on this tracer.
-    WeakMapTraceKind eagerlyTraceWeakMaps() const { return eagerlyTraceWeakMaps_; }
+    // Return the weak map tracing behavior currently set on this tracer.
+    WeakMapTraceKind weakMapAction() const { return weakMapAction_; }
 
     // An intermediate state on the road from C to C++ style dispatch.
     enum class TracerKindTag {
         Marking,
+        WeakMarking, // In weak marking phase: looking up every marked obj/script.
         Tenuring,
         Callback
     };
-    bool isMarkingTracer() const { return tag_ == TracerKindTag::Marking; }
+    bool isMarkingTracer() const { return tag_ == TracerKindTag::Marking || tag_ == TracerKindTag::WeakMarking; }
+    bool isWeakMarkingTracer() const { return tag_ == TracerKindTag::WeakMarking; }
     bool isTenuringTracer() const { return tag_ == TracerKindTag::Tenuring; }
     bool isCallbackTracer() const { return tag_ == TracerKindTag::Callback; }
     inline JS::CallbackTracer* asCallbackTracer();
 
   protected:
     JSTracer(JSRuntime* rt, TracerKindTag tag,
              WeakMapTraceKind weakTraceKind = TraceWeakMapValues)
-      : runtime_(rt), tag_(tag), eagerlyTraceWeakMaps_(weakTraceKind)
+      : runtime_(rt), weakMapAction_(weakTraceKind), tag_(tag)
     {}
 
   private:
     JSRuntime*          runtime_;
+    WeakMapTraceKind    weakMapAction_;
+
+  protected:
     TracerKindTag       tag_;
-    WeakMapTraceKind    eagerlyTraceWeakMaps_;
 };
 
 namespace JS {
 
 class AutoTracingName;
 class AutoTracingIndex;
 class AutoTracingCallback;
 
--- a/js/src/devtools/rootAnalysis/annotations.js
+++ b/js/src/devtools/rootAnalysis/annotations.js
@@ -234,16 +234,20 @@ function ignoreGCFunction(mangled)
     // and rely on only the dynamic checks provided by AutoAssertCannotGC.
     if (isHeapSnapshotMockClass(fun) || isGTest(fun))
         return true;
 
     // Templatized function
     if (fun.indexOf("void nsCOMPtr<T>::Assert_NoQueryNeeded()") >= 0)
         return true;
 
+    // These call through an 'op' function pointer.
+    if (fun.indexOf("js::WeakMap<Key, Value, HashPolicy>::getDelegate(") >= 0)
+        return true;
+
     // XXX modify refillFreeList<NoGC> to not need data flow analysis to understand it cannot GC.
     if (/refillFreeList/.test(fun) && /\(js::AllowGC\)0u/.test(fun))
         return true;
     return false;
 }
 
 function stripUCSAndNamespace(name)
 {
--- a/js/src/ds/OrderedHashTable.h
+++ b/js/src/ds/OrderedHashTable.h
@@ -667,17 +667,18 @@ class OrderedHashMap
         void operator=(Entry&& rhs) {
             MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
             const_cast<Key&>(key) = Move(rhs.key);
             value = Move(rhs.value);
         }
 
       public:
         Entry() : key(), value() {}
-        Entry(const Key& k, const Value& v) : key(k), value(v) {}
+        template <typename V>
+        Entry(const Key& k, V&& v) : key(k), value(Forward<V>(v)) {}
         Entry(Entry&& rhs) : key(Move(rhs.key)), value(Move(rhs.value)) {}
 
         const Key key;
         Value value;
     };
 
   private:
     struct MapOps : OrderedHashPolicy
@@ -702,17 +703,18 @@ class OrderedHashMap
 
     explicit OrderedHashMap(AllocPolicy ap = AllocPolicy()) : impl(ap) {}
     bool init()                                     { return impl.init(); }
     uint32_t count() const                          { return impl.count(); }
     bool has(const Key& key) const                  { return impl.has(key); }
     Range all()                                     { return impl.all(); }
     const Entry* get(const Key& key) const          { return impl.get(key); }
     Entry* get(const Key& key)                      { return impl.get(key); }
-    bool put(const Key& key, const Value& value)    { return impl.put(Entry(key, value)); }
+    template <typename V>
+    bool put(const Key& key, V&& value)             { return impl.put(Entry(key, Forward<V>(value))); }
     bool remove(const Key& key, bool* foundp)       { return impl.remove(key, foundp); }
     bool clear()                                    { return impl.clear(); }
 
     void rekeyOneEntry(const Key& current, const Key& newKey) {
         const Entry* e = get(current);
         if (!e)
             return;
         return impl.rekeyOneEntry(current, newKey, Entry(newKey, e->value));
--- a/js/src/gc/Marking.cpp
+++ b/js/src/gc/Marking.cpp
@@ -597,16 +597,84 @@ DispatchToTracer(JSTracer* trc, T* thing
         return static_cast<TenuringTracer*>(trc)->traverse(thingp);
     MOZ_ASSERT(trc->isCallbackTracer());
     DoCallback(trc->asCallbackTracer(), thingp, name);
 }
 
 
 /*** GC Marking Interface *************************************************************************/
 
+namespace js {
+
+typedef bool DoNothingMarkingType;
+
+template <typename T>
+struct LinearlyMarkedEphemeronKeyType {
+    typedef DoNothingMarkingType Type;
+};
+
+// For now, we only handle JSObject* keys, but the linear time algorithm can be
+// easily extended by adding in more types here, then making
+// GCMarker::traverse<T> call markPotentialEphemeronKey.
+template <>
+struct LinearlyMarkedEphemeronKeyType<JSObject*> {
+    typedef JSObject* Type;
+};
+
+template <>
+struct LinearlyMarkedEphemeronKeyType<JSScript*> {
+    typedef JSScript* Type;
+};
+
+void
+GCMarker::markEphemeronValues(gc::Cell* markedCell, WeakEntryVector& values)
+{
+    size_t initialLen = values.length();
+    for (size_t i = 0; i < initialLen; i++)
+        values[i].weakmap->maybeMarkEntry(this, markedCell, values[i].key);
+
+    // The vector should not be appended to during iteration because the key is
+    // already marked, and even in cases where we have a multipart key, we
+    // should only be inserting entries for the unmarked portions.
+    MOZ_ASSERT(values.length() == initialLen);
+}
+
+template <typename T>
+void
+GCMarker::markPotentialEphemeronKeyHelper(T markedThing)
+{
+    if (!isWeakMarkingTracer())
+        return;
+
+    MOZ_ASSERT(gc::TenuredCell::fromPointer(markedThing)->zone()->isGCMarking());
+    MOZ_ASSERT(!gc::TenuredCell::fromPointer(markedThing)->zone()->isGCSweeping());
+
+    auto weakValues = weakKeys.get(JS::GCCellPtr(markedThing));
+    if (!weakValues)
+        return;
+
+    markEphemeronValues(markedThing, weakValues->value);
+    weakValues->value.clear(); // If key address is reused, it should do nothing
+}
+
+template <>
+void
+GCMarker::markPotentialEphemeronKeyHelper(bool)
+{
+}
+
+template <typename T>
+void
+GCMarker::markPotentialEphemeronKey(T* thing)
+{
+    markPotentialEphemeronKeyHelper<typename LinearlyMarkedEphemeronKeyType<T*>::Type>(thing);
+}
+
+} // namespace js
+
 template <typename T>
 static inline bool
 MustSkipMarking(T thing)
 {
     // Don't mark things outside a zone if we are in a per-zone GC.
     return !thing->zone()->isGCMarking();
 }
 
@@ -695,17 +763,16 @@ js::GCMarker::markAndTraceChildren(T* th
     if (ThingIsPermanentAtomOrWellKnownSymbol(thing))
         return;
     if (mark(thing))
         thing->traceChildren(this);
 }
 namespace js {
 template <> void GCMarker::traverse(BaseShape* thing) { markAndTraceChildren(thing); }
 template <> void GCMarker::traverse(JS::Symbol* thing) { markAndTraceChildren(thing); }
-template <> void GCMarker::traverse(JSScript* thing) { markAndTraceChildren(thing); }
 } // namespace js
 
 // Shape, BaseShape, String, and Symbol are extremely common, but have simple
 // patterns of recursion. We traverse trees of these edges immediately, with
 // aggressive, manual inlining, implemented by eagerlyTraceChildren.
 template <typename T>
 void
 js::GCMarker::markAndScan(T* thing)
@@ -719,28 +786,32 @@ namespace js {
 template <> void GCMarker::traverse(JSString* thing) { markAndScan(thing); }
 template <> void GCMarker::traverse(LazyScript* thing) { markAndScan(thing); }
 template <> void GCMarker::traverse(Shape* thing) { markAndScan(thing); }
 } // namespace 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.
+// 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)
 {
-    if (mark(thing))
-        pushTaggedPtr(tag, thing);
+    if (!mark(thing))
+        return;
+    pushTaggedPtr(tag, thing);
+    markPotentialEphemeronKey(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); }
 } // namespace js
 
 namespace js {
 template <>
 void
 GCMarker::traverse(AccessorShape* thing) {
     MOZ_CRASH("AccessorShape must be marked as a Shape");
 }
@@ -1269,16 +1340,20 @@ GCMarker::processMarkStackTop(SliceBudge
       case GroupTag: {
         return lazilyMarkChildren(reinterpret_cast<ObjectGroup*>(addr));
       }
 
       case JitCodeTag: {
         return reinterpret_cast<jit::JitCode*>(addr)->traceChildren(this);
       }
 
+      case ScriptTag: {
+        return reinterpret_cast<JSScript*>(addr)->traceChildren(this);
+      }
+
       case 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
@@ -1322,16 +1397,17 @@ GCMarker::processMarkStackTop(SliceBudge
         AssertZoneIsMarking(obj);
 
         budget.step();
         if (budget.isOverBudget()) {
             repush(obj);
             return;
         }
 
+        markPotentialEphemeronKey(obj);
         ObjectGroup* group = obj->groupFromGC();
         traverseEdge(obj, group);
 
         NativeObject *nobj = CallTraceHook(TraverseObjectFunctor(), this, obj,
                                            CheckGeneration::DoChecks, this, obj);
         if (!nobj)
             return;
 
@@ -1586,61 +1662,64 @@ MarkStack::sizeOfExcludingThis(mozilla::
 {
     return mallocSizeOf(stack_);
 }
 
 
 /*** GCMarker *************************************************************************************/
 
 /*
- * DoNotTraceWeakMaps: the GC is recomputing the liveness of WeakMap entries,
- * so we delay visting entries.
+ * ExpandWeakMaps: the GC is recomputing the liveness of WeakMap entries by
+ * expanding each live WeakMap into its constituent key->value edges, a table
+ * of which will be consulted in a later phase whenever marking a potential
+ * key.
  */
 GCMarker::GCMarker(JSRuntime* rt)
-  : JSTracer(rt, JSTracer::TracerKindTag::Marking, DoNotTraceWeakMaps),
+  : JSTracer(rt, JSTracer::TracerKindTag::Marking, ExpandWeakMaps),
     stack(size_t(-1)),
     color(BLACK),
     unmarkedArenaStackTop(nullptr),
     markLaterArenas(0),
     started(false),
     strictCompartmentChecking(false)
 {
 }
 
 bool
 GCMarker::init(JSGCMode gcMode)
 {
-    return stack.init(gcMode);
+    return stack.init(gcMode) && weakKeys.init();
 }
 
 void
 GCMarker::start()
 {
     MOZ_ASSERT(!started);
     started = true;
     color = BLACK;
+    linearWeakMarkingDisabled_ = false;
 
     MOZ_ASSERT(!unmarkedArenaStackTop);
     MOZ_ASSERT(markLaterArenas == 0);
-
 }
 
 void
 GCMarker::stop()
 {
     MOZ_ASSERT(isDrained());
 
     MOZ_ASSERT(started);
     started = false;
 
     MOZ_ASSERT(!unmarkedArenaStackTop);
     MOZ_ASSERT(markLaterArenas == 0);
 
     /* Free non-ballast stack memory. */
     stack.reset();
+    weakKeys.clear();
 }
 
 void
 GCMarker::reset()
 {
     color = BLACK;
 
     stack.reset();
@@ -1656,16 +1735,37 @@ GCMarker::reset()
         aheader->allocatedDuringIncremental = 0;
         markLaterArenas--;
     }
     MOZ_ASSERT(isDrained());
     MOZ_ASSERT(!markLaterArenas);
 }
 
 void
+GCMarker::enterWeakMarkingMode()
+{
+    MOZ_ASSERT(tag_ == TracerKindTag::Marking);
+    if (linearWeakMarkingDisabled_)
+        return;
+
+    // During weak marking mode, we maintain a table mapping weak keys to
+    // entries in known-live weakmaps.
+    if (weakMapAction() == ExpandWeakMaps) {
+        tag_ = TracerKindTag::WeakMarking;
+
+        for (GCCompartmentGroupIter c(runtime()); !c.done(); c.next()) {
+            for (WeakMapBase* m = c->gcWeakMapList; m; m = m->next) {
+                if (m->marked)
+                    m->markEphemeronEntries(this);
+            }
+        }
+    }
+}
+
+void
 GCMarker::markDelayedChildren(ArenaHeader* aheader)
 {
     if (aheader->markOverflow) {
         bool always = aheader->allocatedDuringIncremental;
         aheader->markOverflow = 0;
 
         for (ArenaCellIterUnderGC i(aheader); !i.done(); i.next()) {
             TenuredCell* t = i.getCell();
@@ -2346,18 +2446,18 @@ struct AssertNonGrayTracer : public JS::
                       !thing.asCell()->asTenured().isMarked(js::gc::GRAY));
     }
 };
 #endif
 
 struct UnmarkGrayTracer : public JS::CallbackTracer
 {
     /*
-     * We set eagerlyTraceWeakMaps to false because the cycle collector will fix
-     * up any color mismatches involving weakmaps when it runs.
+     * 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),
         tracingShape(false),
         previousShape(nullptr),
         unmarkedAny(false)
     {}
 
--- a/js/src/gc/Marking.h
+++ b/js/src/gc/Marking.h
@@ -3,22 +3,26 @@
  * 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 gc_Marking_h
 #define gc_Marking_h
 
 #include "mozilla/DebugOnly.h"
+#include "mozilla/HashFunctions.h"
+#include "mozilla/Move.h"
 
 #include "jsfriendapi.h"
 
+#include "ds/OrderedHashTable.h"
 #include "gc/Heap.h"
 #include "gc/Tracer.h"
 #include "js/GCAPI.h"
+#include "js/HeapAPI.h"
 #include "js/SliceBudget.h"
 #include "js/TracingAPI.h"
 
 class JSLinearString;
 class JSRope;
 namespace js {
 class BaseShape;
 class GCMarker;
@@ -127,16 +131,45 @@ class MarkStack
     /* Grow the stack, ensuring there is space for at least count elements. */
     bool enlarge(unsigned count);
 
     void setGCMode(JSGCMode gcMode);
 
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
 };
 
+class WeakMapBase;
+
+namespace gc {
+
+struct WeakKeyTableHashPolicy {
+    typedef JS::GCCellPtr Lookup;
+    static HashNumber hash(const Lookup& v) { 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; }
+};
+
+struct WeakMarkable {
+    WeakMapBase* weakmap;
+    JS::GCCellPtr key;
+
+    WeakMarkable(WeakMapBase* weakmapArg, JS::GCCellPtr keyArg)
+      : weakmap(weakmapArg), key(keyArg) {}
+};
+
+typedef Vector<WeakMarkable, 2, js::SystemAllocPolicy> WeakEntryVector;
+
+typedef OrderedHashMap<JS::GCCellPtr,
+                       WeakEntryVector,
+                       WeakKeyTableHashPolicy,
+                       js::SystemAllocPolicy> WeakKeyTable;
+
+} /* namespace gc */
+
 class GCMarker : public JSTracer
 {
   public:
     explicit GCMarker(JSRuntime* rt);
     bool init(JSGCMode gcMode);
 
     void setMaxCapacity(size_t maxCap) { stack.setMaxCapacity(maxCap); }
     size_t maxCapacity() const { return stack.maxCapacity(); }
@@ -168,16 +201,33 @@ class GCMarker : public JSTracer
     }
     void setMarkColorBlack() {
         MOZ_ASSERT(isDrained());
         MOZ_ASSERT(color == gc::GRAY);
         color = gc::BLACK;
     }
     uint32_t markColor() const { return color; }
 
+    void enterWeakMarkingMode();
+
+    void leaveWeakMarkingMode() {
+        MOZ_ASSERT_IF(weakMapAction() == ExpandWeakMaps && !linearWeakMarkingDisabled_, tag_ == TracerKindTag::WeakMarking);
+        tag_ = TracerKindTag::Marking;
+
+        // Table is expensive to maintain when not in weak marking mode, so
+        // we'll rebuild it upon entry rather than allow it to contain stale
+        // data.
+        weakKeys.clear();
+    }
+
+    void abortLinearWeakMarking() {
+        leaveWeakMarkingMode();
+        linearWeakMarkingDisabled_ = true;
+    }
+
     void delayMarkingArena(gc::ArenaHeader* aheader);
     void delayMarkingChildren(const void* thing);
     void markDelayedChildren(gc::ArenaHeader* aheader);
     bool markDelayedChildren(SliceBudget& budget);
     bool hasDelayedChildren() const {
         return !!unmarkedArenaStackTop;
     }
 
@@ -190,16 +240,24 @@ class GCMarker : public JSTracer
     void setGCMode(JSGCMode mode) { stack.setGCMode(mode); }
 
     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
 
 #ifdef DEBUG
     bool shouldCheckCompartments() { return strictCompartmentChecking; }
 #endif
 
+    void markEphemeronValues(gc::Cell* markedCell, gc::WeakEntryVector& entry);
+
+    /*
+     * Mapping from not yet marked keys to a vector of all values that the key
+     * maps to in any live weak map.
+     */
+    gc::WeakKeyTable weakKeys;
+
   private:
 #ifdef DEBUG
     void checkZone(void* p);
 #else
     void checkZone(void* p) {}
 #endif
 
     /*
@@ -208,16 +266,17 @@ class GCMarker : public JSTracer
      * 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
@@ -225,16 +284,18 @@ class GCMarker : public JSTracer
     void repush(JSObject* obj) {
         MOZ_ASSERT(gc::TenuredCell::fromPointer(obj)->isMarked(markColor()));
         pushTaggedPtr(ObjectTag, obj);
     }
 
     template <typename T> void markAndTraceChildren(T* thing);
     template <typename T> void markAndPush(StackTag tag, T* thing);
     template <typename T> void markAndScan(T* thing);
+    template <typename T> void markPotentialEphemeronKeyHelper(T oldThing);
+    template <typename T> void markPotentialEphemeronKey(T* oldThing);
     void eagerlyMarkChildren(JSLinearString* str);
     void eagerlyMarkChildren(JSRope* rope);
     void eagerlyMarkChildren(JSString* str);
     void eagerlyMarkChildren(LazyScript *thing);
     void eagerlyMarkChildren(Shape* shape);
     void lazilyMarkChildren(ObjectGroup* group);
 
     // We may not have concrete types yet, so this has to be out of the header.
@@ -282,16 +343,22 @@ class GCMarker : public JSTracer
     MarkStack stack;
 
     /* The color is only applied to objects and functions. */
     uint32_t color;
 
     /* Pointer to the top of the stack of arenas we are delaying marking on. */
     js::gc::ArenaHeader* unmarkedArenaStackTop;
 
+    /*
+     * If the weakKeys table OOMs, disable the linear algorithm and fall back
+     * to iterating until the next GC.
+     */
+    bool linearWeakMarkingDisabled_;
+
     /* Count of arenas that are currently in the stack. */
     mozilla::DebugOnly<size_t> markLaterArenas;
 
     /* Assert that start and stop are called with correct ordering. */
     mozilla::DebugOnly<bool> started;
 
     /*
      * If this is true, all marked objects must belong to a compartment being
--- a/js/src/gc/Tracer.h
+++ b/js/src/gc/Tracer.h
@@ -18,21 +18,21 @@ namespace js {
 //
 // Tracing is an abstract visitation of each edge in a JS heap graph.[1] The
 // most common (and performance sensitive) use of this infrastructure is for GC
 // "marking" as part of the mark-and-sweep collector; however, this
 // infrastructure is much more general than that and is used for many other
 // purposes as well.
 //
 // One commonly misunderstood subtlety of the tracing architecture is the role
-// of graph verticies versus graph edges. Graph verticies are the heap
+// of graph vertices versus graph edges. Graph vertices are the heap
 // allocations -- GC things -- that are returned by Allocate. Graph edges are
 // pointers -- including tagged pointers like Value and jsid -- that link the
 // allocations into a complex heap. The tracing API deals *only* with edges.
-// Any action taken on the target of a graph edge is independent to the tracing
+// Any action taken on the target of a graph edge is independent of the tracing
 // itself.
 //
 // Another common misunderstanding relates to the role of the JSTracer. The
 // JSTracer instance determines what tracing does when visiting an edge; it
 // does not itself participate in the tracing process, other than to be passed
 // through as opaque data. It works like a closure in that respect.
 //
 // Tracing implementations internal to SpiderMonkey should use these interfaces
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/gc/weak-marking-01.js
@@ -0,0 +1,193 @@
+// These tests will be using object literals as keys, and we want some of them
+// to be dead after being inserted into a WeakMap. That means we must wrap
+// everything in functions because it seems like the toplevel script hangs onto
+// its object literals.
+
+// All reachable keys should be found, and the rest should be swept.
+function basicSweeping() {
+  var wm1 = new WeakMap();
+  wm1.set({'name': 'obj1'}, {'name': 'val1'});
+  var hold = {'name': 'obj2'};
+  wm1.set(hold, {'name': 'val2'});
+  wm1.set({'name': 'obj3'}, {'name': 'val3'});
+
+  startgc(100000, 'shrinking');
+  gcslice();
+
+  assertEq(wm1.get(hold).name, 'val2');
+  assertEq(nondeterministicGetWeakMapKeys(wm1).length, 1);
+}
+
+basicSweeping();
+
+// Keep values alive even when they are only referenced by (live) WeakMap values.
+function weakGraph() {
+  var wm1 = new WeakMap();
+  var obj1 = {'name': 'obj1'};
+  var obj2 = {'name': 'obj2'};
+  var obj3 = {'name': 'obj3'};
+  var obj4 = {'name': 'obj4'};
+  var clear = {'name': ''}; // Make the interpreter forget about the last obj created
+
+  wm1.set(obj2, obj3);
+  wm1.set(obj3, obj1);
+  wm1.set(obj4, obj1); // This edge will be cleared
+  obj1 = obj3 = obj4 = undefined;
+
+  startgc(100000, 'shrinking');
+  gcslice();
+
+  assertEq(obj2.name, "obj2");
+  assertEq(wm1.get(obj2).name, "obj3");
+  assertEq(wm1.get(wm1.get(obj2)).name, "obj1");
+  print(nondeterministicGetWeakMapKeys(wm1).map(o => o.name).join(","));
+  assertEq(nondeterministicGetWeakMapKeys(wm1).length, 2);
+}
+
+weakGraph();
+
+// ...but the weakmap itself has to stay alive, too.
+function deadWeakMap() {
+  var wm1 = new WeakMap();
+  var obj1 = makeFinalizeObserver();
+  var obj2 = {'name': 'obj2'};
+  var obj3 = {'name': 'obj3'};
+  var obj4 = {'name': 'obj4'};
+  var clear = {'name': ''}; // Make the interpreter forget about the last obj created
+
+  wm1.set(obj2, obj3);
+  wm1.set(obj3, obj1);
+  wm1.set(obj4, obj1); // This edge will be cleared
+  var initialCount = finalizeCount();
+  obj1 = obj3 = obj4 = undefined;
+  wm1 = undefined;
+
+  startgc(100000, 'shrinking');
+  gcslice();
+
+  assertEq(obj2.name, "obj2");
+  assertEq(finalizeCount(), initialCount + 1);
+}
+
+deadWeakMap();
+
+// WeakMaps do not strongly reference their keys or values. (WeakMaps hold a
+// collection of (strong) references to *edges* from keys to values. If the
+// WeakMap is not live, then its edges are of course not live either. An edge
+// holds neither its key nor its value live; it just holds a strong ref from
+// the key to the value. So if the key is live, the value is live too, but the
+// edge itself has no references to anything.)
+function deadKeys() {
+  var wm1 = new WeakMap();
+  var obj1 = makeFinalizeObserver();
+  var obj2 = {'name': 'obj2'};
+  var obj3 = makeFinalizeObserver();
+  var clear = {}; // Make the interpreter forget about the last obj created
+
+  wm1.set(obj1, obj1);
+  wm1.set(obj3, obj2);
+  obj1 = obj3 = undefined;
+  var initialCount = finalizeCount();
+
+  startgc(100000, 'shrinking');
+  gcslice();
+
+  assertEq(finalizeCount(), initialCount + 2);
+  assertEq(nondeterministicGetWeakMapKeys(wm1).length, 0);
+}
+
+deadKeys();
+
+// The weakKeys table has to grow if it encounters enough new unmarked weakmap
+// keys. Trigger this to happen during weakmap marking.
+//
+// There's some trickiness involved in getting it to test the right thing,
+// because if a key is marked before the weakmap, then it won't get entered
+// into the weakKeys table. This chains through multiple weakmap layers to
+// ensure that the objects can't get marked before the weakmaps.
+function weakKeysRealloc() {
+  var wm1 = new WeakMap;
+  var wm2 = new WeakMap;
+  var wm3 = new WeakMap;
+  var obj1 = {'name': 'obj1'};
+  var obj2 = {'name': 'obj2'};
+  wm1.set(obj1, wm2);
+  wm2.set(obj2, wm3);
+  for (var i = 0; i < 10000; i++) {
+    wm3.set(Object.create(null), wm2);
+  }
+  wm3.set(Object.create(null), makeFinalizeObserver());
+  wm2 = undefined;
+  wm3 = undefined;
+  obj2 = undefined;
+
+  var initialCount = finalizeCount();
+  startgc(100000, 'shrinking');
+  gcslice();
+  assertEq(finalizeCount(), initialCount + 1);
+}
+
+weakKeysRealloc();
+
+// The weakKeys table is populated during regular marking. When a key is later
+// deleted, both it and its delegate should be removed from weakKeys.
+// Otherwise, it will hold its value live if it gets marked, and our table
+// traversals will include non-keys, etc.
+function deletedKeys() {
+  var wm = new WeakMap;
+  var g = newGlobal();
+
+  for (var i = 0; i < 1000; i++)
+    wm.set(g.Object.create(null), i);
+
+  startgc(100, 'shrinking');
+  for (var key of nondeterministicGetWeakMapKeys(wm)) {
+    if (wm.get(key) % 2)
+      wm.delete(key);
+  }
+
+  gc();
+}
+
+deletedKeys();
+
+// Test adding keys during incremental GC.
+function incrementalAdds() {
+  var initialCount = finalizeCount();
+
+  var wm1 = new WeakMap;
+  var wm2 = new WeakMap;
+  var wm3 = new WeakMap;
+  var obj1 = {'name': 'obj1'};
+  var obj2 = {'name': 'obj2'};
+  wm1.set(obj1, wm2);
+  wm2.set(obj2, wm3);
+  for (var i = 0; i < 10000; i++) {
+    wm3.set(Object.create(null), wm2);
+  }
+  wm3.set(Object.create(null), makeFinalizeObserver());
+  obj2 = undefined;
+
+  var obj3 = [];
+  startgc(100, 'shrinking');
+  var M = 10;
+  var N = 800;
+  for (var j = 0; j < M; j++) {
+    for (var i = 0; i < N; i++)
+      wm3.set(Object.create(null), makeFinalizeObserver()); // Should be swept
+    for (var i = 0; i < N; i++) {
+      obj3.push({'name': 'obj3'});
+      wm1.set(obj3[obj3.length - 1], makeFinalizeObserver()); // Should not be swept
+    }
+    gcslice();
+  }
+
+  wm2 = undefined;
+  wm3 = undefined;
+
+  gc();
+  print("initialCount = " + initialCount);
+  assertEq(finalizeCount(), initialCount + 1 + M * N);
+}
+
+incrementalAdds();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/gc/weak-marking-02.js
@@ -0,0 +1,128 @@
+// These tests will be using object literals as keys, and we want some of them
+// to be dead after being inserted into a WeakMap. That means we must wrap
+// everything in functions because it seems like the toplevel script hangs onto
+// its object literals.
+
+// Cross-compartment WeakMap keys work by storing a cross-compartment wrapper
+// in the WeakMap, and the actual "delegate" object in the target compartment
+// is the thing whose liveness is checked.
+
+var g2 = newGlobal();
+g2.eval('function genObj(name) { return {"name": name} }');
+
+function basicSweeping() {
+  var wm1 = new WeakMap();
+  wm1.set({'name': 'obj1'}, {'name': 'val1'});
+  var hold = g2.genObj('obj2');
+  wm1.set(hold, {'name': 'val2'});
+  wm1.set({'name': 'obj3'}, {'name': 'val3'});
+  var obj4 = g2.genObj('obj4');
+  wm1.set(obj4, {'name': 'val3'});
+  obj4 = undefined;
+
+  startgc(100000, 'shrinking');
+  gcslice();
+  assertEq(wm1.get(hold).name, 'val2');
+  assertEq(nondeterministicGetWeakMapKeys(wm1).length, 1);
+}
+
+basicSweeping();
+
+// Same, but behind an additional WM layer, to avoid ordering problems (not
+// that I've checked that basicSweeping even has any problems.)
+
+function basicSweeping2() {
+  var wm1 = new WeakMap();
+  wm1.set({'name': 'obj1'}, {'name': 'val1'});
+  var hold = g2.genObj('obj2');
+  wm1.set(hold, {'name': 'val2'});
+  wm1.set({'name': 'obj3'}, {'name': 'val3'});
+  var obj4 = g2.genObj('obj4');
+  wm1.set(obj4, {'name': 'val3'});
+  obj4 = undefined;
+
+  var base1 = {'name': 'base1'};
+  var base2 = {'name': 'base2'};
+  var wm_base1 = new WeakMap();
+  var wm_base2 = new WeakMap();
+  wm_base1.set(base1, wm_base2);
+  wm_base2.set(base2, wm1);
+  wm1 = wm_base2 = undefined;
+
+  startgc(100000, 'shrinking');
+  gcslice();
+
+  assertEq(nondeterministicGetWeakMapKeys(wm_base1).length, 1);
+  wm_base2 = wm_base1.get(base1);
+  assertEq(nondeterministicGetWeakMapKeys(wm_base2).length, 1);
+  assertEq(nondeterministicGetWeakMapKeys(wm_base1)[0], base1);
+  assertEq(nondeterministicGetWeakMapKeys(wm_base2)[0], base2);
+  wm_base2 = wm_base1.get(base1);
+  wm1 = wm_base2.get(base2);
+  assertEq(wm1.get(hold).name, 'val2');
+  assertEq(nondeterministicGetWeakMapKeys(wm1).length, 1);
+}
+
+basicSweeping2();
+
+// Scatter the weakmap, the keys, and the values among different compartments.
+
+function tripleZoneMarking() {
+  var g1 = newGlobal();
+  var g2 = newGlobal();
+  var g3 = newGlobal();
+
+  var wm = g1.eval("new WeakMap()");
+  var key = g2.eval("({'name': 'obj1'})");
+  var value = g3.eval("({'name': 'val1'})");
+  g1 = g2 = g3 = undefined;
+  wm.set(key, value);
+
+  // Make all of it only reachable via a weakmap in the main test compartment,
+  // so that all of this happens during weak marking mode. Use the weakmap as
+  // its own key, so we know that the weakmap will get traced before the key
+  // and therefore will populate the weakKeys table and all of that jazz.
+  var base_wm = new WeakMap();
+  base_wm.set(base_wm, [ wm, key ]);
+
+  wm = key = value = undefined;
+
+  startgc(100000, 'shrinking');
+  gcslice();
+
+  var keys = nondeterministicGetWeakMapKeys(base_wm);
+  assertEq(keys.length, 1);
+  var [ wm, key ] = base_wm.get(keys[0]);
+  assertEq(key.name, "obj1");
+  value = wm.get(key);
+  assertEq(value.name, "val1");
+}
+
+tripleZoneMarking();
+
+function enbugger() {
+  var g = newGlobal();
+  var dbg = new Debugger;
+  g.eval("function debuggee_f() { return 1; }");
+  g.eval("function debuggee_g() { return 1; }");
+  dbg.addDebuggee(g);
+  var [ s ] = dbg.findScripts({global: g}).filter(s => s.displayName == "debuggee_f");
+  var [ s2 ] = dbg.findScripts({global: g}).filter(s => s.displayName == "debuggee_g");
+  g.eval("debuggee_f = null");
+  gc();
+  dbg.removeAllDebuggees();
+  gc();
+  assertEq(s.displayName, "debuggee_f");
+
+  var wm = new WeakMap;
+  var obj = Object.create(null);
+  var obj2 = Object.create(null);
+  wm.set(obj, s);
+  wm.set(obj2, obj);
+  wm.set(s2, obj2);
+  s = s2 = obj = obj2 = null;
+
+  gc();
+}
+
+enbugger();
--- a/js/src/jsapi-tests/testWeakMap.cpp
+++ b/js/src/jsapi-tests/testWeakMap.cpp
@@ -65,62 +65,71 @@ checkSize(JS::HandleObject map, uint32_t
     return true;
 }
 END_TEST(testWeakMap_basicOperations)
 
 BEGIN_TEST(testWeakMap_keyDelegates)
 {
     JS_SetGCParameter(rt, JSGC_MODE, JSGC_MODE_INCREMENTAL);
     JS_GC(rt);
-
     JS::RootedObject map(cx, JS::NewWeakMapObject(cx));
     CHECK(map);
 
     JS::RootedObject key(cx, newKey());
     CHECK(key);
 
     JS::RootedObject delegate(cx, newDelegate());
     CHECK(delegate);
     keyDelegate = delegate;
 
+    JS::RootedObject delegateRoot(cx);
+    {
+        JSAutoCompartment ac(cx, delegate);
+        delegateRoot = JS_NewPlainObject(cx);
+        CHECK(delegateRoot);
+        JS::RootedValue delegateValue(cx, ObjectValue(*delegate));
+        CHECK(JS_DefineProperty(cx, delegateRoot, "delegate", delegateValue, 0));
+    }
+    delegate = nullptr;
+
     /*
      * Perform an incremental GC, introducing an unmarked CCW to force the map
      * zone to finish marking before the delegate zone.
      */
-    CHECK(newCCW(map, delegate));
+    CHECK(newCCW(map, delegateRoot));
     js::SliceBudget budget(js::WorkBudget(1000000));
     rt->gc.startDebugGC(GC_NORMAL, budget);
     CHECK(!JS::IsIncrementalGCInProgress(rt));
 #ifdef DEBUG
-    CHECK(map->zone()->lastZoneGroupIndex() < delegate->zone()->lastZoneGroupIndex());
+    CHECK(map->zone()->lastZoneGroupIndex() < delegateRoot->zone()->lastZoneGroupIndex());
 #endif
 
     /* Add our entry to the weakmap. */
     JS::RootedValue val(cx, JS::Int32Value(1));
     CHECK(SetWeakMapEntry(cx, map, key, val));
     CHECK(checkSize(map, 1));
 
     /* Check the delegate keeps the entry alive even if the key is not reachable. */
     key = nullptr;
-    CHECK(newCCW(map, delegate));
+    CHECK(newCCW(map, delegateRoot));
     budget = js::SliceBudget(js::WorkBudget(100000));
     rt->gc.startDebugGC(GC_NORMAL, budget);
     CHECK(!JS::IsIncrementalGCInProgress(rt));
     CHECK(checkSize(map, 1));
 
     /*
      * Check that the zones finished marking at the same time, which is
-     * neccessary because of the presence of the delegate and the CCW.
+     * necessary because of the presence of the delegate and the CCW.
      */
 #ifdef DEBUG
-    CHECK(map->zone()->lastZoneGroupIndex() == delegate->zone()->lastZoneGroupIndex());
+    CHECK(map->zone()->lastZoneGroupIndex() == delegateRoot->zone()->lastZoneGroupIndex());
 #endif
 
     /* Check that when the delegate becomes unreachable the entry is removed. */
-    delegate = nullptr;
+    delegateRoot = nullptr;
     keyDelegate = nullptr;
     JS_GC(rt);
     CHECK(checkSize(map, 0));
 
     return true;
 }
 
 static void DelegateObjectMoved(JSObject* obj, const JSObject* old)
--- a/js/src/jsgc.cpp
+++ b/js/src/jsgc.cpp
@@ -4018,32 +4018,42 @@ GCRuntime::beginMarkPhase(JS::gcreason::
 template <class CompartmentIterT>
 void
 GCRuntime::markWeakReferences(gcstats::Phase phase)
 {
     MOZ_ASSERT(marker.isDrained());
 
     gcstats::AutoPhase ap1(stats, phase);
 
+    marker.enterWeakMarkingMode();
+
+    // TODO bug 1167452: Make weak marking incremental
+    SliceBudget budget = SliceBudget::unlimited();
+    marker.drainMarkStack(budget);
+
     for (;;) {
         bool markedAny = false;
         for (CompartmentIterT c(rt); !c.done(); c.next()) {
-            markedAny |= WatchpointMap::markCompartmentIteratively(c, &marker);
-            markedAny |= WeakMapBase::markCompartmentIteratively(c, &marker);
+            if (c->watchpointMap)
+                markedAny |= c->watchpointMap->markIteratively(&marker);
+            if (marker.weakMapAction() != ExpandWeakMaps)
+                markedAny |= WeakMapBase::markCompartmentIteratively(c, &marker);
         }
         markedAny |= Debugger::markAllIteratively(&marker);
         markedAny |= jit::JitRuntime::MarkJitcodeGlobalTableIteratively(&marker);
 
         if (!markedAny)
             break;
 
         auto unlimited = SliceBudget::unlimited();
         marker.drainMarkStack(unlimited);
     }
     MOZ_ASSERT(marker.isDrained());
+
+    marker.leaveWeakMarkingMode();
 }
 
 void
 GCRuntime::markWeakReferencesInCurrentGroup(gcstats::Phase phase)
 {
     markWeakReferences<GCCompartmentGroupIter>(phase);
 }
 
@@ -4176,22 +4186,33 @@ js::gc::MarkingValidator::nonIncremental
     if (!markedWeakMaps.init())
         return;
 
     for (GCCompartmentsIter c(runtime); !c.done(); c.next()) {
         if (!WeakMapBase::saveCompartmentMarkedWeakMaps(c, markedWeakMaps))
             return;
     }
 
+    gc::WeakKeyTable savedWeakKeys;
+    if (!savedWeakKeys.init())
+        return;
+
+    for (gc::WeakKeyTable::Range r = gc->marker.weakKeys.all(); !r.empty(); r.popFront()) {
+        if (!savedWeakKeys.put(Move(r.front().key), Move(r.front().value)))
+            CrashAtUnhandlableOOM("saving weak keys table for validator");
+    }
+
     /*
      * After this point, the function should run to completion, so we shouldn't
      * do anything fallible.
      */
     initialized = true;
 
+    gc->marker.weakKeys.clear();
+
     /* Re-do all the marking, but non-incrementally. */
     js::gc::State state = gc->incrementalState;
     gc->incrementalState = MARK_ROOTS;
 
     {
         gcstats::AutoPhase ap(gc->stats, gcstats::PHASE_MARK);
 
         {
@@ -4244,17 +4265,23 @@ js::gc::MarkingValidator::nonIncremental
     for (auto chunk = gc->allNonEmptyChunks(); !chunk.done(); chunk.next()) {
         ChunkBitmap* bitmap = &chunk->bitmap;
         ChunkBitmap* entry = map.lookup(chunk)->value();
         Swap(*entry, *bitmap);
     }
 
     for (GCCompartmentsIter c(runtime); !c.done(); c.next())
         WeakMapBase::unmarkCompartment(c);
-    WeakMapBase::restoreCompartmentMarkedWeakMaps(markedWeakMaps);
+    WeakMapBase::restoreMarkedWeakMaps(markedWeakMaps);
+
+    gc->marker.weakKeys.clear();
+    for (gc::WeakKeyTable::Range r = savedWeakKeys.all(); !r.empty(); r.popFront()) {
+        if (!gc->marker.weakKeys.put(Move(r.front().key), Move(r.front().value)))
+            CrashAtUnhandlableOOM("restoring weak keys table for validator");
+    }
 
     gc->incrementalState = state;
 }
 
 void
 js::gc::MarkingValidator::validate()
 {
     /*
@@ -4749,17 +4776,16 @@ GCRuntime::endMarkingZoneGroup()
     gcstats::AutoPhase ap(stats, gcstats::PHASE_SWEEP_MARK);
 
     /*
      * Mark any incoming black pointers from previously swept compartments
      * whose referents are not marked. This can occur when gray cells become
      * black by the action of UnmarkGray.
      */
     MarkIncomingCrossCompartmentPointers(rt, BLACK);
-
     markWeakReferencesInCurrentGroup(gcstats::PHASE_SWEEP_MARK_WEAK);
 
     /*
      * Change state of current group to MarkGray to restrict marking to this
      * group.  Note that there may be pointers to the atoms compartment, and
      * these will be marked through, as they are not marked with
      * MarkCrossCompartmentXXX.
      */
@@ -4910,16 +4936,27 @@ GCRuntime::beginSweepingZoneGroup()
         if (rt->sweepZoneCallback)
             rt->sweepZoneCallback(zone);
 
         zone->gcLastZoneGroupIndex = zoneGroupIndex;
     }
 
     validateIncrementalMarking();
 
+    /* Clear out this zone group's keys from the weakKeys table, to prevent later accesses. */
+    for (WeakKeyTable::Range r = marker.weakKeys.all(); !r.empty(); ) {
+        auto key(r.front().key);
+        r.popFront();
+        if (gc::TenuredCell::fromPointer(key.asCell())->zone()->isGCSweeping()) {
+            bool found;
+            marker.weakKeys.remove(key, &found);
+            MOZ_ASSERT(found);
+        }
+    }
+
     FreeOp fop(rt);
     SweepAtomsTask sweepAtomsTask(rt);
     SweepInnerViewsTask sweepInnerViewsTask(rt);
     SweepCCWrappersTask sweepCCWrappersTask(rt);
     SweepBaseShapesTask sweepBaseShapesTask(rt);
     SweepInitialShapesTask sweepInitialShapesTask(rt);
     SweepObjectGroupsTask sweepObjectGroupsTask(rt);
     SweepRegExpsTask sweepRegExpsTask(rt);
--- a/js/src/jswatchpoint.cpp
+++ b/js/src/jswatchpoint.cpp
@@ -140,24 +140,16 @@ WatchpointMap::triggerWatchpoint(JSConte
     // watchpoint. See the comment before UnmarkGrayChildren in gc/Marking.cpp
     JS::ExposeObjectToActiveJS(closure);
 
     /* Call the handler. */
     return handler(cx, obj, id, old, vp.address(), closure);
 }
 
 bool
-WatchpointMap::markCompartmentIteratively(JSCompartment* c, JSTracer* trc)
-{
-    if (!c->watchpointMap)
-        return false;
-    return c->watchpointMap->markIteratively(trc);
-}
-
-bool
 WatchpointMap::markIteratively(JSTracer* trc)
 {
     bool marked = false;
     for (Map::Enum e(map); !e.empty(); e.popFront()) {
         Map::Entry& entry = e.front();
         JSObject* priorKeyObj = entry.key().object;
         jsid priorKeyId(entry.key().id.get());
         bool objectIsLive =
--- a/js/src/jswatchpoint.h
+++ b/js/src/jswatchpoint.h
@@ -65,17 +65,16 @@ class WatchpointMap {
                JSWatchPointHandler handler, HandleObject closure);
     void unwatch(JSObject* obj, jsid id,
                  JSWatchPointHandler* handlerp, JSObject** closurep);
     void unwatchObject(JSObject* obj);
     void clear();
 
     bool triggerWatchpoint(JSContext* cx, HandleObject obj, HandleId id, MutableHandleValue vp);
 
-    static bool markCompartmentIteratively(JSCompartment* c, JSTracer* trc);
     bool markIteratively(JSTracer* trc);
     void markAll(JSTracer* trc);
     static void sweepAll(JSRuntime* rt);
     void sweep();
 
     static void traceAll(WeakMapTracer* trc);
     void trace(WeakMapTracer* trc);
 
--- a/js/src/jsweakmap.cpp
+++ b/js/src/jsweakmap.cpp
@@ -45,47 +45,51 @@ WeakMapBase::~WeakMapBase()
         removeWeakMapFromList(this);
 }
 
 void
 WeakMapBase::trace(JSTracer* tracer)
 {
     MOZ_ASSERT(isInList());
     if (tracer->isMarkingTracer()) {
-        // We don't trace any of the WeakMap entries at this time, just record
-        // record the fact that the WeakMap has been marked. Entries are marked
-        // in the iterative marking phase by markAllIteratively(), which happens
-        // when as many keys as possible have been marked already.
-        MOZ_ASSERT(tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps);
         marked = true;
+        if (tracer->weakMapAction() == DoNotTraceWeakMaps) {
+            // Do not trace any WeakMap entries at this time. Just record the
+            // fact that the WeakMap has been marked. Entries are marked in the
+            // iterative marking phase by markAllIteratively(), after as many
+            // keys as possible have been marked already.
+        } else {
+            MOZ_ASSERT(tracer->weakMapAction() == ExpandWeakMaps);
+            markEphemeronEntries(tracer);
+        }
     } else {
         // If we're not actually doing garbage collection, the keys won't be marked
         // nicely as needed by the true ephemeral marking algorithm --- custom tracers
         // such as the cycle collector must use their own means for cycle detection.
         // So here we do a conservative approximation: pretend all keys are live.
-        if (tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps)
+        if (tracer->weakMapAction() == DoNotTraceWeakMaps)
             return;
 
         nonMarkingTraceValues(tracer);
-        if (tracer->eagerlyTraceWeakMaps() == TraceWeakMapKeysValues)
+        if (tracer->weakMapAction() == TraceWeakMapKeysValues)
             nonMarkingTraceKeys(tracer);
     }
 }
 
 void
 WeakMapBase::unmarkCompartment(JSCompartment* c)
 {
     for (WeakMapBase* m = c->gcWeakMapList; m; m = m->next)
         m->marked = false;
 }
 
 void
 WeakMapBase::markAll(JSCompartment* c, JSTracer* tracer)
 {
-    MOZ_ASSERT(tracer->eagerlyTraceWeakMaps() != DoNotTraceWeakMaps);
+    MOZ_ASSERT(tracer->weakMapAction() != DoNotTraceWeakMaps);
     for (WeakMapBase* m = c->gcWeakMapList; m; m = m->next) {
         m->trace(tracer);
         if (m->memberOf)
             TraceEdge(tracer, &m->memberOf, "memberOf");
     }
 }
 
 bool
@@ -153,17 +157,17 @@ WeakMapBase::saveCompartmentMarkedWeakMa
     for (WeakMapBase* m = c->gcWeakMapList; m; m = m->next) {
         if (m->marked && !markedWeakMaps.put(m))
             return false;
     }
     return true;
 }
 
 void
-WeakMapBase::restoreCompartmentMarkedWeakMaps(WeakMapSet& markedWeakMaps)
+WeakMapBase::restoreMarkedWeakMaps(WeakMapSet& markedWeakMaps)
 {
     for (WeakMapSet::Range r = markedWeakMaps.all(); !r.empty(); r.popFront()) {
         WeakMapBase* map = r.front();
         MOZ_ASSERT(map->compartment->zone()->isGCMarking());
         MOZ_ASSERT(!map->marked);
         map->marked = true;
     }
 }
@@ -181,17 +185,17 @@ WeakMapBase::removeWeakMapFromList(WeakM
     }
 }
 
 bool
 ObjectValueMap::findZoneEdges()
 {
     /*
      * For unmarked weakmap keys with delegates in a different zone, add a zone
-     * edge to ensure that the delegate zone does finish marking after the key
+     * edge to ensure that the delegate zone finishes marking before the key
      * zone.
      */
     JS::AutoSuppressGCAnalysis nogc;
     Zone* mapZone = compartment->zone();
     for (Range r = all(); !r.empty(); r.popFront()) {
         JSObject* key = r.front().key();
         if (key->asTenured().isMarked(BLACK) && !key->asTenured().isMarked(GRAY))
             continue;
--- a/js/src/jsweakmap.h
+++ b/js/src/jsweakmap.h
@@ -2,16 +2,18 @@
  * 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 jsweakmap_h
 #define jsweakmap_h
 
+#include "mozilla/Move.h"
+
 #include "jscompartment.h"
 #include "jsfriendapi.h"
 #include "jsobj.h"
 
 #include "gc/Marking.h"
 #include "gc/StoreBuffer.h"
 #include "js/HashTable.h"
 
@@ -34,16 +36,18 @@ namespace js {
 // The value for the next pointer for maps not in the map list.
 static WeakMapBase * const WeakMapNotInList = reinterpret_cast<WeakMapBase*>(1);
 
 typedef HashSet<WeakMapBase*, DefaultHasher<WeakMapBase*>, SystemAllocPolicy> WeakMapSet;
 
 // Common base class for all WeakMap specializations. The collector uses this to call
 // their markIteratively and sweep methods.
 class WeakMapBase {
+    friend void js::GCMarker::enterWeakMarkingMode();
+
   public:
     WeakMapBase(JSObject* memOf, JSCompartment* c);
     virtual ~WeakMapBase();
 
     void trace(JSTracer* tracer);
 
     // Garbage collector entry points.
 
@@ -70,21 +74,27 @@ class WeakMapBase {
     static void traceAllMappings(WeakMapTracer* tracer);
 
     bool isInList() { return next != WeakMapNotInList; }
 
     // Save information about which weak maps are marked for a compartment.
     static bool saveCompartmentMarkedWeakMaps(JSCompartment* c, WeakMapSet& markedWeakMaps);
 
     // Restore information about which weak maps are marked for many compartments.
-    static void restoreCompartmentMarkedWeakMaps(WeakMapSet& markedWeakMaps);
+    static void restoreMarkedWeakMaps(WeakMapSet& markedWeakMaps);
 
     // Remove a weakmap from its compartment's weakmaps list.
     static void removeWeakMapFromList(WeakMapBase* weakmap);
 
+    // Any weakmap key types that want to participate in the non-iterative
+    // ephemeron marking must override this method.
+    virtual void maybeMarkEntry(JSTracer* trc, gc::Cell* markedCell, JS::GCCellPtr l) = 0;
+
+    virtual void markEphemeronEntries(JSTracer* trc) = 0;
+
   protected:
     // Instance member functions called by the above. Instantiations of WeakMap override
     // these with definitions appropriate for their Key and Value types.
     virtual void nonMarkingTraceKeys(JSTracer* tracer) = 0;
     virtual void nonMarkingTraceValues(JSTracer* tracer) = 0;
     virtual bool markIteratively(JSTracer* tracer) = 0;
     virtual bool findZoneEdges() = 0;
     virtual void sweep() = 0;
@@ -101,16 +111,27 @@ class WeakMapBase {
     // JSCompartment::gcWeakMapList. The last element of the list has nullptr as
     // its next. Maps not in the list have WeakMapNotInList as their next.
     WeakMapBase* next;
 
     // Whether this object has been traced during garbage collection.
     bool marked;
 };
 
+template <typename T>
+static T extractUnbarriered(BarrieredBase<T> v)
+{
+    return v.get();
+}
+template <typename T>
+static T* extractUnbarriered(T* v)
+{
+    return v;
+}
+
 template <class Key, class Value,
           class HashPolicy = DefaultHasher<Key> >
 class WeakMap : public HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy>, public WeakMapBase
 {
   public:
     typedef HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy> Base;
     typedef typename Base::Enum Enum;
     typedef typename Base::Lookup Lookup;
@@ -149,125 +170,201 @@ class WeakMap : public HashMap<Key, Valu
 
     Ptr lookupWithDefault(const Key& k, const Value& defaultValue) {
         Ptr p = Base::lookupWithDefault(k, defaultValue);
         if (p)
             exposeGCThingToActiveJS(p->value());
         return p;
     }
 
+    // The WeakMap and some part of the key are marked. If the entry is marked
+    // according to the exact semantics of this WeakMap, then mark the value.
+    // (For a standard WeakMap, the entry is marked if either the key its
+    // delegate is marked.)
+    void maybeMarkEntry(JSTracer* trc, gc::Cell* markedCell, JS::GCCellPtr origKey) override
+    {
+        MOZ_ASSERT(marked);
+
+        gc::Cell* l = origKey.asCell();
+        Ptr p = Base::lookup(reinterpret_cast<Lookup&>(l));
+        MOZ_ASSERT(p.found());
+
+        Key key(p->key());
+        if (gc::IsMarked(&key)) {
+            TraceEdge(trc, &p->value(), "ephemeron value");
+        } else if (keyNeedsMark(key)) {
+            TraceEdge(trc, &p->value(), "WeakMap ephemeron value");
+            TraceEdge(trc, &key, "proxy-preserved WeakMap ephemeron key");
+            MOZ_ASSERT(key == p->key()); // No moving
+        }
+        key.unsafeSet(nullptr); // Prevent destructor from running barriers.
+    }
+
+  protected:
+    static void addWeakEntry(JSTracer* trc, JS::GCCellPtr key, gc::WeakMarkable markable)
+    {
+        GCMarker& marker = *static_cast<GCMarker*>(trc);
+
+        auto p = marker.weakKeys.get(key);
+        if (p) {
+            gc::WeakEntryVector& weakEntries = p->value;
+            if (!weakEntries.append(Move(markable)))
+                marker.abortLinearWeakMarking();
+        } else {
+            gc::WeakEntryVector weakEntries;
+            MOZ_ALWAYS_TRUE(weakEntries.append(Move(markable)));
+            if (!marker.weakKeys.put(JS::GCCellPtr(key), Move(weakEntries)))
+                marker.abortLinearWeakMarking();
+        }
+    }
+
+    void markEphemeronEntries(JSTracer* trc) override {
+        MOZ_ASSERT(marked);
+        for (Enum e(*this); !e.empty(); e.popFront()) {
+            Key key(e.front().key());
+
+            // If the entry is live, ensure its key and value are marked.
+            if (gc::IsMarked(&key)) {
+                (void) markValue(trc, &e.front().value());
+                MOZ_ASSERT(key == e.front().key()); // No moving
+            } else if (keyNeedsMark(key)) {
+                TraceEdge(trc, &e.front().value(), "WeakMap entry value");
+                TraceEdge(trc, &key, "proxy-preserved WeakMap entry key");
+                MOZ_ASSERT(key == e.front().key()); // No moving
+            } else if (trc->isWeakMarkingTracer()) {
+                // Entry is not yet known to be live. Record it in the list of
+                // weak keys. Or rather, record this weakmap and the lookup key
+                // so we can repeat the lookup when we need to (to allow
+                // incremental weak marking, we can't just store a pointer to
+                // the entry.) Also record the delegate, if any, because
+                // marking the delegate must also mark the entry.
+                JS::GCCellPtr weakKey(extractUnbarriered(key));
+                gc::WeakMarkable markable(this, weakKey);
+                addWeakEntry(trc, weakKey, markable);
+                if (JSObject* delegate = getDelegate(key))
+                    addWeakEntry(trc, JS::GCCellPtr(delegate), markable);
+            }
+            key.unsafeSet(nullptr); // Prevent destructor from running barriers.
+        }
+    }
+
   private:
     void exposeGCThingToActiveJS(const JS::Value& v) const { JS::ExposeValueToActiveJS(v); }
     void exposeGCThingToActiveJS(JSObject* obj) const { JS::ExposeObjectToActiveJS(obj); }
 
     bool markValue(JSTracer* trc, Value* x) {
         if (gc::IsMarked(x))
             return false;
         TraceEdge(trc, x, "WeakMap entry value");
         MOZ_ASSERT(gc::IsMarked(x));
         return true;
     }
 
-    void nonMarkingTraceKeys(JSTracer* trc) {
+    void nonMarkingTraceKeys(JSTracer* trc) override {
         for (Enum e(*this); !e.empty(); e.popFront()) {
             Key key(e.front().key());
             TraceEdge(trc, &key, "WeakMap entry key");
             if (key != e.front().key())
                 entryMoved(e, key);
         }
     }
 
-    void nonMarkingTraceValues(JSTracer* trc) {
+    void nonMarkingTraceValues(JSTracer* trc) override {
         for (Range r = Base::all(); !r.empty(); r.popFront())
             TraceEdge(trc, &r.front().value(), "WeakMap entry value");
     }
 
-    bool keyNeedsMark(JSObject* key) {
-        if (JSWeakmapKeyDelegateOp op = key->getClass()->ext.weakmapKeyDelegateOp) {
-            JSObject* delegate = op(key);
-            /*
-             * Check if the delegate is marked with any color to properly handle
-             * gray marking when the key's delegate is black and the map is
-             * gray.
-             */
-            return delegate && gc::IsMarkedUnbarriered(&delegate);
-        }
+    JSObject* getDelegate(JSObject* key) const {
+        JSWeakmapKeyDelegateOp op = key->getClass()->ext.weakmapKeyDelegateOp;
+        return op ? op(key) : nullptr;
+    }
+
+    JSObject* getDelegate(gc::Cell* cell) const {
+        return nullptr;
+    }
+
+    bool keyNeedsMark(JSObject* key) const {
+        JSObject* delegate = getDelegate(key);
+        /*
+         * Check if the delegate is marked with any color to properly handle
+         * gray marking when the key's delegate is black and the map is gray.
+         */
+        return delegate && gc::IsMarkedUnbarriered(&delegate);
+    }
+
+    bool keyNeedsMark(gc::Cell* cell) const {
         return false;
     }
 
-    bool keyNeedsMark(gc::Cell* cell) {
-        return false;
-    }
-
-    bool markIteratively(JSTracer* trc) {
+    bool markIteratively(JSTracer* trc) override {
         bool markedAny = false;
         for (Enum e(*this); !e.empty(); e.popFront()) {
             /* If the entry is live, ensure its key and value are marked. */
             Key key(e.front().key());
             if (gc::IsMarked(const_cast<Key*>(&key))) {
                 if (markValue(trc, &e.front().value()))
                     markedAny = true;
                 if (e.front().key() != key)
                     entryMoved(e, key);
             } else if (keyNeedsMark(key)) {
                 TraceEdge(trc, &e.front().value(), "WeakMap entry value");
                 TraceEdge(trc, &key, "proxy-preserved WeakMap entry key");
                 if (e.front().key() != key)
                     entryMoved(e, key);
                 markedAny = true;
             }
-            key.unsafeSet(nullptr);
+            key.unsafeSet(nullptr); // Prevent destructor from running barriers.
         }
         return markedAny;
     }
 
-    bool findZoneEdges() {
+    bool findZoneEdges() override {
         // This is overridden by ObjectValueMap.
         return true;
     }
 
-    void sweep() {
+    void sweep() override {
         /* Remove all entries whose keys remain unmarked. */
         for (Enum e(*this); !e.empty(); e.popFront()) {
             Key k(e.front().key());
             if (gc::IsAboutToBeFinalized(&k))
                 e.removeFront();
             else if (k != e.front().key())
                 entryMoved(e, k);
         }
         /*
          * Once we've swept, all remaining edges should stay within the
          * known-live part of the graph.
          */
         assertEntriesNotAboutToBeFinalized();
     }
 
-    void finish() {
+    void finish() override {
         Base::finish();
     }
 
     /* memberOf can be nullptr, which means that the map is not part of a JSObject. */
-    void traceMappings(WeakMapTracer* tracer) {
+    void traceMappings(WeakMapTracer* tracer) override {
         for (Range r = Base::all(); !r.empty(); r.popFront()) {
             gc::Cell* key = gc::ToMarkable(r.front().key());
             gc::Cell* value = gc::ToMarkable(r.front().value());
             if (key && value) {
                 tracer->trace(memberOf,
                               JS::GCCellPtr(r.front().key().get()),
                               JS::GCCellPtr(r.front().value().get()));
             }
         }
     }
 
     /* Rekey an entry when moved, ensuring we do not trigger barriers. */
     void entryMoved(Enum& e, const Key& k) {
         e.rekeyFront(k);
     }
 
-protected:
+  protected:
     void assertEntriesNotAboutToBeFinalized() {
 #if DEBUG
         for (Range r = Base::all(); !r.empty(); r.popFront()) {
             Key k(r.front().key());
             MOZ_ASSERT(!gc::IsAboutToBeFinalized(&k));
             MOZ_ASSERT(!gc::IsAboutToBeFinalized(&r.front().value()));
             MOZ_ASSERT(k == r.front().key());
         }
--- a/js/src/vm/Debugger.h
+++ b/js/src/vm/Debugger.h
@@ -46,28 +46,33 @@ typedef HashSet<ReadBarrieredGlobalObjec
                 SystemAllocPolicy> WeakGlobalObjectSet;
 
 /*
  * A weakmap from GC thing keys to JSObject values that supports the keys being
  * in different compartments to the values. All values must be in the same
  * compartment.
  *
  * The purpose of this is to allow the garbage collector to easily find edges
- * from debugee object compartments to debugger compartments when calculating
+ * from debuggee object compartments to debugger compartments when calculating
  * the compartment groups.  Note that these edges are the inverse of the edges
  * stored in the cross compartment map.
  *
  * The current implementation results in all debuggee object compartments being
  * swept in the same group as the debugger.  This is a conservative approach,
  * and compartments may be unnecessarily grouped, however it results in a
  * simpler and faster implementation.
  *
  * If InvisibleKeysOk is true, then the map can have keys in invisible-to-
  * debugger compartments. If it is false, we assert that such entries are never
  * created.
+ *
+ * Also note that keys in these weakmaps can be in any compartment, debuggee or
+ * not, because they cannot be deleted when a compartment is no longer a
+ * debuggee: the values need to maintain object identity across add/remove/add
+ * transitions.
  */
 template <class UnbarrieredKey, bool InvisibleKeysOk=false>
 class DebuggerWeakMap : private WeakMap<PreBarriered<UnbarrieredKey>, RelocatablePtrObject>
 {
   private:
     typedef PreBarriered<UnbarrieredKey> Key;
     typedef RelocatablePtrObject Value;