--- a/xpcom/base/CycleCollectedJSRuntime.cpp
+++ b/xpcom/base/CycleCollectedJSRuntime.cpp
@@ -60,16 +60,17 @@
 
 #include "js/Debug.h"
 #include "js/friend/DumpFunctions.h"  // js::DumpHeap
 #include "js/GCAPI.h"
 #include "js/HeapAPI.h"
 #include "js/Object.h"  // JS::GetClass, JS::GetCompartment, JS::GetPrivate
 #include "js/PropertyAndElement.h"  // JS_DefineProperty
 #include "js/Warnings.h"            // JS::SetWarningReporter
+#include "js/SliceBudget.h"
 #include "jsfriendapi.h"
 #include "mozilla/ArrayUtils.h"
 #include "mozilla/AutoRestore.h"
 #include "mozilla/CycleCollectedJSContext.h"
 #include "mozilla/DebuggerOnGCRunnable.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/ProfilerLabels.h"
 #include "mozilla/ProfilerMarkers.h"
@@ -516,26 +517,32 @@ JSHolderMap::Iter::Iter(JSHolderMap& aMa
 }
 
 void JSHolderMap::Iter::Settle() {
   while (mIter.Done()) {
     if (mZone && mIter.Vector().IsEmpty()) {
       mHolderMap.mPerZoneJSHolders.remove(mZone);
     }
 
+    mZone = nullptr;
     if (mZones.empty()) {
       break;
     }
 
     mZone = mZones.popCopy();
     EntryVector& vector = *mHolderMap.mPerZoneJSHolders.lookup(mZone)->value();
     new (&mIter) EntryVectorIter(mHolderMap, vector);
   }
 }
 
+void JSHolderMap::Iter::UpdateForRemovals() {
+  mIter.Settle();
+  Settle();
+}
+
 JSHolderMap::JSHolderMap() : mJSHolderMap(256) {}
 
 bool JSHolderMap::RemoveEntry(EntryVector& aJSHolders, Entry* aEntry) {
   MOZ_ASSERT(aEntry);
   MOZ_ASSERT(!aEntry->mHolder);
 
   // Remove all dead entries from the end of the vector.
   while (!aJSHolders.GetLast().mHolder && &aJSHolders.GetLast() != aEntry) {
@@ -578,17 +585,18 @@ nsScriptObjectTracer* JSHolderMap::Extra
   if (!ptr) {
     return nullptr;
   }
 
   Entry* entry = ptr->value();
   MOZ_ASSERT(entry->mHolder == aHolder);
   nsScriptObjectTracer* tracer = entry->mTracer;
 
-  // Clear the entry's contents. It will be removed during the next iteration.
+  // Clear the entry's contents. It will be removed the next time iteration
+  // visits this entry.
   *entry = Entry();
 
   mJSHolderMap.remove(ptr);
 
   return tracer;
 }
 
 void JSHolderMap::Put(void* aHolder, nsScriptObjectTracer* aTracer,
@@ -736,17 +744,17 @@ void CycleCollectedJSRuntime::Shutdown(J
   mErrorInterceptor.Shutdown(mJSRuntime);
 #endif  // MOZ_JS_DEV_ERROR_INTERCEPTOR
 
   // There should not be any roots left to trace at this point. Ensure any that
   // remain are flagged as leaks.
 #ifdef NS_BUILD_REFCNT_LOGGING
   JSLeakTracer tracer(Runtime());
   TraceNativeBlackRoots(&tracer);
-  TraceNativeGrayRoots(&tracer, JSHolderMap::AllHolders);
+  TraceAllNativeGrayRoots(&tracer);
 #endif
 
 #ifdef DEBUG
   mShutdownCalled = true;
 #endif
 
   JS_SetDestroyZoneCallback(cx, nullptr);
 }
@@ -989,19 +997,17 @@ bool CycleCollectedJSRuntime::TraceGrayJ
   // Mark these roots as gray so the CC can walk them later.
 
   JSHolderMap::WhichHolders which = JSHolderMap::HoldersRequiredForGrayMarking;
   if (JS::AtomsZoneIsCollecting(self->Runtime())) {
     // Any holder may point into the atoms zone.
     which = JSHolderMap::AllHolders;
   }
 
-  self->TraceNativeGrayRoots(aTracer, which);
-
-  return true;
+  return self->TraceNativeGrayRoots(aTracer, which, budget);
 }
 
 /* static */
 void CycleCollectedJSRuntime::GCCallback(JSContext* aContext,
                                          JSGCStatus aStatus,
                                          JS::GCReason aReason, void* aData) {
   CycleCollectedJSRuntime* self = static_cast<CycleCollectedJSRuntime*>(aData);
 
@@ -1397,38 +1403,73 @@ static inline bool ShouldCheckSingleZone
 #elif defined(NIGHTLY_BUILD) || defined(MOZ_DEV_EDITION)
   // Don't check every time to avoid performance impact.
   return rand() % 256 == 0;
 #else
   return false;
 #endif
 }
 
-void CycleCollectedJSRuntime::TraceNativeGrayRoots(
-    JSTracer* aTracer, JSHolderMap::WhichHolders aWhich) {
-  // NB: This is here just to preserve the existing XPConnect order. I doubt it
-  // would hurt to do this after the JS holders.
-  TraceAdditionalNativeGrayRoots(aTracer);
+#ifdef NS_BUILD_REFCNT_LOGGING
+void CycleCollectedJSRuntime::TraceAllNativeGrayRoots(JSTracer* aTracer) {
+  MOZ_RELEASE_ASSERT(mHolderIter.isNothing());
+  js::SliceBudget budget = js::SliceBudget::unlimited();
+  MOZ_ALWAYS_TRUE(
+      TraceNativeGrayRoots(aTracer, JSHolderMap::AllHolders, budget));
+}
+#endif
+
+bool CycleCollectedJSRuntime::TraceNativeGrayRoots(
+    JSTracer* aTracer, JSHolderMap::WhichHolders aWhich,
+    js::SliceBudget& aBudget) {
+  if (!mHolderIter) {
+    // NB: This is here just to preserve the existing XPConnect order. I doubt
+    // it would hurt to do this after the JS holders.
+    TraceAdditionalNativeGrayRoots(aTracer);
 
+    mHolderIter.emplace(mJSHolders, aWhich);
+    aBudget.stepAndForceCheck();
+  } else {
+    // Holders may have been removed between slices, so we may need to update
+    // the iterator.
+    mHolderIter->UpdateForRemovals();
+  }
+
+  bool finished = TraceJSHolders(aTracer, *mHolderIter, aBudget);
+  if (finished) {
+    mHolderIter.reset();
+  }
+
+  return finished;
+}
+
+bool CycleCollectedJSRuntime::TraceJSHolders(JSTracer* aTracer,
+                                             JSHolderMap::Iter& aIter,
+                                             js::SliceBudget& aBudget) {
   bool checkSingleZoneHolders = ShouldCheckSingleZoneHolders();
-  for (JSHolderMap::Iter entry(mJSHolders, aWhich); !entry.Done();
-       entry.Next()) {
-    void* holder = entry->mHolder;
-    nsScriptObjectTracer* tracer = entry->mTracer;
+
+  while (!aIter.Done() && !aBudget.isOverBudget()) {
+    void* holder = aIter->mHolder;
+    nsScriptObjectTracer* tracer = aIter->mTracer;
 
 #ifdef CHECK_SINGLE_ZONE_JS_HOLDERS
     if (checkSingleZoneHolders && !tracer->IsMultiZoneJSHolder()) {
-      CheckHolderIsSingleZone(holder, tracer, entry.Zone());
+      CheckHolderIsSingleZone(holder, tracer, aIter.Zone());
     }
 #else
     Unused << checkSingleZoneHolders;
 #endif
 
     tracer->Trace(holder, JsGcTracer(), aTracer);
+
+    aIter.Next();
+    aBudget.step();
   }
+
+  return aIter.Done();
 }
 
 void CycleCollectedJSRuntime::AddJSHolder(void* aHolder,
                                           nsScriptObjectTracer* aTracer,
                                           JS::Zone* aZone) {
   mJSHolders.Put(aHolder, aTracer, aZone);
 }
 
@@ -1784,20 +1825,22 @@ void CycleCollectedJSRuntime::AnnotateAn
   CrashReporter::AnnotateCrashReport(
       annotation, nsDependentCString(OOMStateToString(aNewState)));
 }
 
 void CycleCollectedJSRuntime::OnGC(JSContext* aContext, JSGCStatus aStatus,
                                    JS::GCReason aReason) {
   switch (aStatus) {
     case JSGC_BEGIN:
+      MOZ_RELEASE_ASSERT(mHolderIter.isNothing());
       nsCycleCollector_prepareForGarbageCollection();
       PrepareWaitingZonesForGC();
       break;
     case JSGC_END: {
+      MOZ_RELEASE_ASSERT(mHolderIter.isNothing());
       if (mOutOfMemoryState == OOMState::Reported) {
         AnnotateAndSetOutOfMemory(&mOutOfMemoryState, OOMState::Recovered);
       }
       if (mLargeAllocationFailureState == OOMState::Reported) {
         AnnotateAndSetOutOfMemory(&mLargeAllocationFailureState,
                                   OOMState::Recovered);
       }
 

--- a/xpcom/base/CycleCollectedJSRuntime.h
+++ b/xpcom/base/CycleCollectedJSRuntime.h
@@ -164,16 +164,17 @@ class JSHolderMap::EntryVectorIter {
     Settle();
   }
 
   operator const Entry*() const { return &Get(); }
   const Entry* operator->() const { return &Get(); }
 
  private:
   void Settle();
+  friend class JSHolderMap::Iter;
 
   JSHolderMap& mHolderMap;
   EntryVector& mVector;
   EntryVector::IterImpl mIter;
 };
 
 class JSHolderMap::Iter {
  public:
@@ -186,16 +187,21 @@ class JSHolderMap::Iter {
 
   bool Done() const { return mIter.Done(); }
   const Entry& Get() const { return mIter.Get(); }
   void Next() {
     mIter.Next();
     Settle();
   }
 
+  // If the holders have been removed from the map while the iterator is live,
+  // then the iterator may point to a removed entry. Update the iterator to make
+  // sure it points to a valid entry or is done.
+  void UpdateForRemovals();
+
   operator const Entry*() const { return &Get(); }
   const Entry* operator->() const { return &Get(); }
 
   JS::Zone* Zone() const { return mZone; }
 
  private:
   void Settle();
 
@@ -279,18 +285,25 @@ class CycleCollectedJSRuntime {
   static void OutOfMemoryCallback(JSContext* aContext, void* aData);
 
   static bool ContextCallback(JSContext* aCx, unsigned aOperation, void* aData);
 
   static void* BeforeWaitCallback(uint8_t* aMemory);
   static void AfterWaitCallback(void* aCookie);
 
   virtual void TraceNativeBlackRoots(JSTracer* aTracer){};
-  void TraceNativeGrayRoots(JSTracer* aTracer,
-                            JSHolderMap::WhichHolders aWhich);
+
+#ifdef NS_BUILD_REFCNT_LOGGING
+  void TraceAllNativeGrayRoots(JSTracer* aTracer);
+#endif
+
+  bool TraceNativeGrayRoots(JSTracer* aTracer, JSHolderMap::WhichHolders aWhich,
+                            js::SliceBudget& aBudget);
+  bool TraceJSHolders(JSTracer* aTracer, JSHolderMap::Iter& aIter,
+                      js::SliceBudget& aBudget);
 
  public:
   void FinalizeDeferredThings(
       CycleCollectedJSContext::DeferredFinalizeType aType);
 
   virtual void PrepareForForgetSkippable() = 0;
   virtual void BeginCycleCollectionCallback() = 0;
   virtual void EndCycleCollectionCallback(CycleCollectorResults& aResults) = 0;
@@ -433,16 +446,17 @@ class CycleCollectedJSRuntime {
   bool mHasPendingIdleGCTask;
 
   JS::GCSliceCallback mPrevGCSliceCallback;
   JS::GCNurseryCollectionCallback mPrevGCNurseryCollectionCallback;
 
   mozilla::TimeStamp mLatestNurseryCollectionStart;
 
   JSHolderMap mJSHolders;
+  Maybe<JSHolderMap::Iter> mHolderIter;
 
   typedef nsTHashMap<nsFuncPtrHashKey<DeferredFinalizeFunction>, void*>
       DeferredFinalizerTable;
   DeferredFinalizerTable mDeferredFinalizerTable;
 
   RefPtr<IncrementalFinalizeRunnable> mFinalizeRunnable;
 
   OOMState mOutOfMemoryState;