tor-browser

GC.cpp (176297B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* 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/. */

/*
* [SMDOC] Garbage Collector
*
* This code implements an incremental mark-and-sweep garbage collector, with
* most sweeping carried out in the background on a parallel thread.
*
* Full vs. zone GC
* ----------------
*
* The collector can collect all zones at once, or a subset. These types of
* collection are referred to as a full GC and a zone GC respectively.
*
* It is possible for an incremental collection that started out as a full GC to
* become a zone GC if new zones are created during the course of the
* collection.
*
* Incremental collection
* ----------------------
*
* For a collection to be carried out incrementally the following conditions
* must be met:
*  - the collection must be run by calling js::GCSlice() rather than js::GC()
*  - the GC parameter JSGC_INCREMENTAL_GC_ENABLED must be true.
*
* The last condition is an engine-internal mechanism to ensure that incremental
* collection is not carried out without the correct barriers being implemented.
* For more information see 'Incremental marking' below.
*
* If the collection is not incremental, all foreground activity happens inside
* a single call to GC() or GCSlice(). However the collection is not complete
* until the background sweeping activity has finished.
*
* An incremental collection proceeds as a series of slices, interleaved with
* mutator activity, i.e. running JavaScript code. Slices are limited by a time
* budget. The slice finishes as soon as possible after the requested time has
* passed.
*
* Collector states
* ----------------
*
* The collector proceeds through the following states, the current state being
* held in JSRuntime::gcIncrementalState:
*
*  - Prepare    - unmarks GC things, discards JIT code and other setup
*  - MarkRoots  - marks the stack and other roots
*  - Mark       - incrementally marks reachable things
*  - Sweep      - sweeps zones in groups and continues marking unswept zones
*  - Finalize   - performs background finalization, concurrent with mutator
*  - Compact    - incrementally compacts by zone
*  - Decommit   - performs background decommit and chunk removal
*
* Roots are marked in the first MarkRoots slice; this is the start of the GC
* proper. The following states can take place over one or more slices.
*
* In other words an incremental collection proceeds like this:
*
* Slice 1:   Prepare:    Starts background task to unmark GC things
*
*          ... JS code runs, background unmarking finishes ...
*
* Slice 2:   MarkRoots:  Roots are pushed onto the mark stack.
*            Mark:       The mark stack is processed by popping an element,
*                        marking it, and pushing its children.
*
*          ... JS code runs ...
*
* Slice 3:   Mark:       More mark stack processing.
*
*          ... JS code runs ...
*
* Slice n-1: Mark:       More mark stack processing.
*
*          ... JS code runs ...
*
* Slice n:   Mark:       Mark stack is completely drained.
*            Sweep:      Select first group of zones to sweep and sweep them.
*
*          ... JS code runs ...
*
* Slice n+1: Sweep:      Mark objects in unswept zones that were newly
*                        identified as alive (see below). Then sweep more zone
*                        sweep groups.
*
*          ... JS code runs ...
*
* Slice n+2: Sweep:      Mark objects in unswept zones that were newly
*                        identified as alive. Then sweep more zones.
*
*          ... JS code runs ...
*
* Slice m:   Sweep:      Sweeping is finished, and background sweeping
*                        started on the helper thread.
*
*          ... JS code runs, remaining sweeping done on background thread ...
*
* When background sweeping finishes the GC is complete.
*
* Incremental marking
* -------------------
*
* Incremental collection requires close collaboration with the mutator (i.e.,
* JS code) to guarantee correctness.
*
*  - During an incremental GC, if a memory location (except a root) is written
*    to, then the value it previously held must be marked. Write barriers
*    ensure this.
*
*  - Any object that is allocated during incremental GC must start out marked.
*
*  - Roots are marked in the first slice and hence don't need write barriers.
*    Roots are things like the C stack and the VM stack.
*
* The problem that write barriers solve is that between slices the mutator can
* change the object graph. We must ensure that it cannot do this in such a way
* that makes us fail to mark a reachable object (marking an unreachable object
* is tolerable).
*
* We use a snapshot-at-the-beginning algorithm to do this. This means that we
* promise to mark at least everything that is reachable at the beginning of
* collection. To implement it we mark the old contents of every non-root memory
* location written to by the mutator while the collection is in progress, using
* write barriers. This is described in gc/Barrier.h.
*
* Incremental sweeping
* --------------------
*
* Sweeping is difficult to do incrementally because object finalizers must be
* run at the start of sweeping, before any mutator code runs. The reason is
* that some objects use their finalizers to remove themselves from caches. If
* mutator code was allowed to run after the start of sweeping, it could observe
* the state of the cache and create a new reference to an object that was just
* about to be destroyed.
*
* Sweeping all finalizable objects in one go would introduce long pauses, so
* instead sweeping broken up into groups of zones. Zones which are not yet
* being swept are still marked, so the issue above does not apply.
*
* The order of sweeping is restricted by cross compartment pointers - for
* example say that object |a| from zone A points to object |b| in zone B and
* neither object was marked when we transitioned to the Sweep phase. Imagine we
* sweep B first and then return to the mutator. It's possible that the mutator
* could cause |a| to become alive through a read barrier (perhaps it was a
* shape that was accessed via a shape table). Then we would need to mark |b|,
* which |a| points to, but |b| has already been swept.
*
* So if there is such a pointer then marking of zone B must not finish before
* marking of zone A.  Pointers which form a cycle between zones therefore
* restrict those zones to being swept at the same time, and these are found
* using Tarjan's algorithm for finding the strongly connected components of a
* graph.
*
* GC things without finalizers, and things with finalizers that are able to run
* in the background, are swept on the background thread. This accounts for most
* of the sweeping work.
*
* Reset
* -----
*
* During incremental collection it is possible, although unlikely, for
* conditions to change such that incremental collection is no longer safe. In
* this case, the collection is 'reset' by resetIncrementalGC(). If we are in
* the mark state, this just stops marking, but if we have started sweeping
* already, we continue non-incrementally until we have swept the current sweep
* group. Following a reset, a new collection is started.
*
* Compacting GC
* -------------
*
* Compacting GC happens at the end of a major GC as part of the last slice.
* There are three parts:
*
*  - Arenas are selected for compaction.
*  - The contents of those arenas are moved to new arenas.
*  - All references to moved things are updated.
*
* Collecting Atoms
* ----------------
*
* Atoms are collected differently from other GC things. They are contained in
* a special zone and things in other zones may have pointers to them that are
* not recorded in the cross compartment pointer map. Each zone holds a bitmap
* with the atoms it might be keeping alive, and atoms are only collected if
* they are not included in any zone's atom bitmap. See AtomMarking.cpp for how
* this bitmap is managed.
*/

#include "gc/GC-inl.h"

#include "mozilla/glue/Debug.h"
#include "mozilla/ScopeExit.h"
#include "mozilla/TextUtils.h"
#include "mozilla/TimeStamp.h"

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <utility>

#include "jsapi.h"  // JS_AbortIfWrongThread
#include "jstypes.h"

#include "debugger/DebugAPI.h"
#include "gc/ClearEdgesTracer.h"
#include "gc/GCContext.h"
#include "gc/GCInternals.h"
#include "gc/GCLock.h"
#include "gc/GCProbes.h"
#include "gc/Memory.h"
#include "gc/ParallelMarking.h"
#include "gc/ParallelWork.h"
#include "gc/WeakMap.h"
#include "jit/ExecutableAllocator.h"
#include "jit/JitCode.h"
#include "jit/JitRuntime.h"
#include "jit/ProcessExecutableMemory.h"
#include "js/HeapAPI.h"  // JS::GCCellPtr
#include "js/Printer.h"
#include "js/SliceBudget.h"
#include "util/DifferentialTesting.h"
#include "vm/BigIntType.h"
#include "vm/EnvironmentObject.h"
#include "vm/GetterSetter.h"
#include "vm/HelperThreadState.h"
#include "vm/JitActivation.h"
#include "vm/JSObject.h"
#include "vm/JSScript.h"
#include "vm/Logging.h"
#include "vm/PropMap.h"
#include "vm/Realm.h"
#include "vm/Shape.h"
#include "vm/StringType.h"
#include "vm/SymbolType.h"
#include "vm/Time.h"

#include "gc/Heap-inl.h"
#include "gc/Nursery-inl.h"
#include "gc/ObjectKind-inl.h"
#include "gc/PrivateIterators-inl.h"
#include "vm/GeckoProfiler-inl.h"
#include "vm/JSContext-inl.h"
#include "vm/Realm-inl.h"
#include "vm/Stack-inl.h"
#include "vm/StringType-inl.h"

using namespace js;
using namespace js::gc;

using mozilla::EnumSet;
using mozilla::MakeScopeExit;
using mozilla::Maybe;
using mozilla::Nothing;
using mozilla::Some;
using mozilla::TimeDuration;
using mozilla::TimeStamp;

using JS::SliceBudget;
using JS::TimeBudget;
using JS::WorkBudget;

// A table converting an object size in "slots" (increments of
// sizeof(js::Value)) to the total number of bytes in the corresponding
// AllocKind. See gc::slotsToThingKind. This primarily allows wasm jit code to
// remain compliant with the AllocKind system.
//
// To use this table, subtract sizeof(NativeObject) from your desired allocation
// size, divide by sizeof(js::Value) to get the number of "slots", and then
// index into this table. See gc::GetGCObjectKindForBytes.
constexpr uint32_t gc::slotsToAllocKindBytes[] = {
   // These entries correspond exactly to gc::slotsToThingKind. The numeric
   // comments therefore indicate the number of slots that the "bytes" would
   // correspond to.
   // clang-format off
   /*  0 */ sizeof(JSObject_Slots0), sizeof(JSObject_Slots2), sizeof(JSObject_Slots2), sizeof(JSObject_Slots4),
   /*  4 */ sizeof(JSObject_Slots4), sizeof(JSObject_Slots6), sizeof(JSObject_Slots6), sizeof(JSObject_Slots8),
   /*  8 */ sizeof(JSObject_Slots8), sizeof(JSObject_Slots12), sizeof(JSObject_Slots12), sizeof(JSObject_Slots12),
   /* 12 */ sizeof(JSObject_Slots12), sizeof(JSObject_Slots16), sizeof(JSObject_Slots16), sizeof(JSObject_Slots16),
   /* 16 */ sizeof(JSObject_Slots16)
   // clang-format on
};

static_assert(std::size(slotsToAllocKindBytes) == std::size(slotsToThingKind));

MOZ_THREAD_LOCAL(JS::GCContext*) js::TlsGCContext;

JS::GCContext::GCContext(JSRuntime* runtime) : runtime_(runtime) {}

JS::GCContext::~GCContext() {
 MOZ_ASSERT(!hasJitCodeToPoison());
 MOZ_ASSERT(!isCollecting());
 MOZ_ASSERT(gcUse() == GCUse::None);
 MOZ_ASSERT(!gcSweepZone());
 MOZ_ASSERT(!isTouchingGrayThings());
 MOZ_ASSERT(isPreWriteBarrierAllowed());
}

void JS::GCContext::poisonJitCode() {
 if (hasJitCodeToPoison()) {
   jit::ExecutableAllocator::poisonCode(runtime(), jitPoisonRanges);
   jitPoisonRanges.clearAndFree();
 }
}

#ifdef DEBUG
void GCRuntime::verifyAllChunks() {
 AutoLockGC lock(this);
 fullChunks(lock).verifyChunks();
 availableChunks(lock).verifyChunks();
 emptyChunks(lock).verifyChunks();
 if (currentChunk_) {
   MOZ_ASSERT(currentChunk_->info.isCurrentChunk);
   currentChunk_->verify();
 } else {
   MOZ_ASSERT(pendingFreeCommittedArenas.ref().IsEmpty());
 }
}
#endif

void GCRuntime::setMinEmptyChunkCount(uint32_t value, const AutoLockGC& lock) {
 minEmptyChunkCount_ = value;
}

inline bool GCRuntime::tooManyEmptyChunks(const AutoLockGC& lock) {
 return emptyChunks(lock).count() > minEmptyChunkCount(lock);
}

ChunkPool GCRuntime::expireEmptyChunkPool(const AutoLockGC& lock) {
 MOZ_ASSERT(emptyChunks(lock).verify());

 ChunkPool expired;
 if (isShrinkingGC()) {
   std::swap(expired, emptyChunks(lock));
 } else {
   while (tooManyEmptyChunks(lock)) {
     ArenaChunk* chunk = emptyChunks(lock).pop();
     prepareToFreeChunk(chunk->info);
     expired.push(chunk);
   }
 }

 MOZ_ASSERT(expired.verify());
 MOZ_ASSERT(emptyChunks(lock).verify());
 MOZ_ASSERT(emptyChunks(lock).count() <= minEmptyChunkCount(lock));
 return expired;
}

static void FreeChunkPool(ChunkPool& pool) {
 for (ChunkPool::Iter iter(pool); !iter.done();) {
   ArenaChunk* chunk = iter.get();
   iter.next();
   pool.remove(chunk);
   MOZ_ASSERT(chunk->isEmpty());
   UnmapPages(static_cast<void*>(chunk), ChunkSize);
 }
 MOZ_ASSERT(pool.count() == 0);
}

void GCRuntime::freeEmptyChunks(const AutoLockGC& lock) {
 FreeChunkPool(emptyChunks(lock));
}

inline void GCRuntime::prepareToFreeChunk(ArenaChunkInfo& info) {
 MOZ_ASSERT(info.numArenasFree == ArenasPerChunk);
 stats().count(gcstats::COUNT_DESTROY_CHUNK);
#ifdef DEBUG
 // Let FreeChunkPool detect a missing prepareToFreeChunk call before it frees
 // chunk.
 info.numArenasFreeCommitted = 0;
#endif
}

void GCRuntime::releaseArenaList(ArenaList& arenaList, const AutoLockGC& lock) {
 releaseArenas(arenaList.release(), lock);
}

void GCRuntime::releaseArenas(Arena* arena, const AutoLockGC& lock) {
 Arena* next;
 for (; arena; arena = next) {
   next = arena->next;
   releaseArena(arena, lock);
 }
}

void GCRuntime::releaseArena(Arena* arena, const AutoLockGC& lock) {
 MOZ_ASSERT(arena->allocated());
 MOZ_ASSERT(!arena->onDelayedMarkingList());
 MOZ_ASSERT(TlsGCContext.get()->isFinalizing());

 arena->zone()->gcHeapSize.removeBytes(ArenaSize, true, heapSize);
 if (arena->zone()->isAtomsZone()) {
   arena->freeAtomMarkingBitmapIndex(this, lock);
 }
 arena->release();
 arena->chunk()->releaseArena(this, arena, lock);
}

GCRuntime::GCRuntime(JSRuntime* rt)
   : rt(rt),
     systemZone(nullptr),
     mainThreadContext(rt),
     heapState_(JS::HeapState::Idle),
     stats_(this),
     sweepingTracer(rt),
     fullGCRequested(false),
     helperThreadRatio(TuningDefaults::HelperThreadRatio),
     maxHelperThreads(TuningDefaults::MaxHelperThreads),
     helperThreadCount(1),
     maxMarkingThreads(TuningDefaults::MaxMarkingThreads),
     markingThreadCount(1),
     createBudgetCallback(nullptr),
     minEmptyChunkCount_(TuningDefaults::MinEmptyChunkCount),
     rootsHash(256),
     nextCellUniqueId_(LargestTaggedNullCellPointer +
                       1),  // Ensure disjoint from null tagged pointers.
     verifyPreData(nullptr),
     lastGCStartTime_(TimeStamp::Now()),
     lastGCEndTime_(TimeStamp::Now()),
     incrementalGCEnabled(TuningDefaults::IncrementalGCEnabled),
     perZoneGCEnabled(TuningDefaults::PerZoneGCEnabled),
     numActiveZoneIters(0),
     grayBitsValid(true),
     majorGCTriggerReason(JS::GCReason::NO_REASON),
     minorGCNumber(0),
     majorGCNumber(0),
     number(0),
     sliceNumber(0),
     isFull(false),
     incrementalState(gc::State::NotActive),
     initialState(gc::State::NotActive),
     useZeal(false),
     lastMarkSlice(false),
     safeToYield(true),
     markOnBackgroundThreadDuringSweeping(false),
     useBackgroundThreads(false),
#ifdef DEBUG
     hadShutdownGC(false),
#endif
     requestSliceAfterBackgroundTask(false),
     lifoBlocksToFree((size_t)JSContext::TEMP_LIFO_ALLOC_PRIMARY_CHUNK_SIZE,
                      js::BackgroundMallocArena),
     lifoBlocksToFreeAfterFullMinorGC(
         (size_t)JSContext::TEMP_LIFO_ALLOC_PRIMARY_CHUNK_SIZE,
         js::BackgroundMallocArena),
     lifoBlocksToFreeAfterNextMinorGC(
         (size_t)JSContext::TEMP_LIFO_ALLOC_PRIMARY_CHUNK_SIZE,
         js::BackgroundMallocArena),
     sweepGroupIndex(0),
     sweepGroups(nullptr),
     currentSweepGroup(nullptr),
     sweepZone(nullptr),
     abortSweepAfterCurrentGroup(false),
     sweepMarkResult(IncrementalProgress::NotFinished),
#ifdef DEBUG
     testMarkQueue(rt),
#endif
     startedCompacting(false),
     zonesCompacted(0),
#ifdef DEBUG
     relocatedArenasToRelease(nullptr),
#endif
#ifdef JS_GC_ZEAL
     markingValidator(nullptr),
#endif
     defaultTimeBudgetMS_(TuningDefaults::DefaultTimeBudgetMS),
     compactingEnabled(TuningDefaults::CompactingEnabled),
     nurseryEnabled(TuningDefaults::NurseryEnabled),
     parallelMarkingEnabled(TuningDefaults::ParallelMarkingEnabled),
     rootsRemoved(false),
#ifdef JS_GC_ZEAL
     zealModeBits(0),
     zealFrequency(0),
     nextScheduled(0),
     deterministicOnly(false),
     zealSliceBudget(0),
     selectedForMarking(rt),
#endif
     fullCompartmentChecks(false),
     gcCallbackDepth(0),
     alwaysPreserveCode(false),
     lowMemoryState(false),
     lock(mutexid::GCLock),
     storeBufferLock(mutexid::StoreBuffer),
     delayedMarkingLock(mutexid::GCDelayedMarkingLock),
     bufferAllocatorLock(mutexid::BufferAllocator),
     allocTask(this, emptyChunks_.ref()),
     unmarkTask(this),
     markTask(this),
     sweepTask(this),
     freeTask(this),
     decommitTask(this),
     nursery_(this),
     storeBuffer_(rt),
     lastAllocRateUpdateTime(TimeStamp::Now()) {
}

bool js::gc::SplitStringBy(const char* text, char delimiter,
                          CharRangeVector* result) {
 return SplitStringBy(CharRange(text, strlen(text)), delimiter, result);
}

bool js::gc::SplitStringBy(const CharRange& text, char delimiter,
                          CharRangeVector* result) {
 auto start = text.begin();
 for (auto ptr = start; ptr != text.end(); ptr++) {
   if (*ptr == delimiter) {
     if (!result->emplaceBack(start, ptr)) {
       return false;
     }
     start = ptr + 1;
   }
 }

 return result->emplaceBack(start, text.end());
}

static bool ParseTimeDuration(const CharRange& text,
                             TimeDuration* durationOut) {
 const char* str = text.begin().get();
 char* end;
 long millis = strtol(str, &end, 10);
 *durationOut = TimeDuration::FromMilliseconds(double(millis));
 return str != end && end == text.end().get();
}

static void PrintProfileHelpAndExit(const char* envName, const char* helpText) {
 fprintf(stderr, "%s=N[,(main|all)]\n", envName);
 fprintf(stderr, "%s", helpText);
 exit(0);
}

void js::gc::ReadProfileEnv(const char* envName, const char* helpText,
                           bool* enableOut, bool* workersOut,
                           TimeDuration* thresholdOut) {
 *enableOut = false;
 *workersOut = false;
 *thresholdOut = TimeDuration::Zero();

 const char* env = getenv(envName);
 if (!env) {
   return;
 }

 if (strcmp(env, "help") == 0) {
   PrintProfileHelpAndExit(envName, helpText);
 }

 CharRangeVector parts;
 if (!SplitStringBy(env, ',', &parts)) {
   MOZ_CRASH("OOM parsing environment variable");
 }

 if (parts.length() == 0 || parts.length() > 2) {
   PrintProfileHelpAndExit(envName, helpText);
 }

 *enableOut = true;

 if (!ParseTimeDuration(parts[0], thresholdOut)) {
   PrintProfileHelpAndExit(envName, helpText);
 }

 if (parts.length() == 2) {
   const char* threads = parts[1].begin().get();
   if (strcmp(threads, "all") == 0) {
     *workersOut = true;
   } else if (strcmp(threads, "main") != 0) {
     PrintProfileHelpAndExit(envName, helpText);
   }
 }
}

bool js::gc::ShouldPrintProfile(JSRuntime* runtime, bool enable,
                               bool profileWorkers, TimeDuration threshold,
                               TimeDuration duration) {
 return enable && (runtime->isMainRuntime() || profileWorkers) &&
        duration >= threshold;
}

#ifdef JS_GC_ZEAL

void GCRuntime::getZealBits(uint32_t* zealBits, uint32_t* frequency,
                           uint32_t* scheduled) {
 *zealBits = zealModeBits;
 *frequency = zealFrequency;
 *scheduled = nextScheduled;
}

// Please also update jit-test/tests/gc/gczeal.js when updating this help text.
// clang-format off
const char gc::ZealModeHelpText[] =
"  Specifies how zealous the garbage collector should be. Some of these modes\n"
"  can be set simultaneously, by passing multiple level options, e.g. \"2;4\"\n"
"  will activate both modes 2 and 4. Modes can be specified by name or\n"
"  number.\n"
"  \n"
"  Values:\n"
"    0:  (None) Normal amount of collection (resets all modes)\n"
"    1:  (RootsChange) Collect when roots are added or removed\n"
"    2:  (Alloc) Collect when every N allocations (default: 100)\n"
"    4:  (VerifierPre) Verify pre write barriers between instructions\n"
"    5:  (VerifierPost) Verify post write barriers after minor GC\n"
"    6:  (YieldBeforeRootMarking) Incremental GC in two slices that yields\n"
"        before root marking\n"
"    7:  (GenerationalGC) Collect the nursery every N nursery allocations\n"
"    8:  (YieldBeforeMarking) Incremental GC in two slices that yields\n"
"        between the root marking and marking phases\n"
"    9:  (YieldBeforeSweeping) Incremental GC in two slices that yields\n"
"        between the marking and sweeping phases\n"
"    10: (IncrementalMultipleSlices) Incremental GC in many slices\n"
"    11: (IncrementalMarkingValidator) Verify incremental marking\n"
"    12: (ElementsBarrier) Use the individual element post-write barrier\n"
"        regardless of elements size\n"
"    13: (CheckHashTablesOnMinorGC) Check internal hashtables on minor GC\n"
"    14: (Compact) Perform a shrinking collection every N allocations\n"
"    15: (CheckHeapAfterGC) Walk the heap to check its integrity after every\n"
"        GC\n"
"    17: (YieldBeforeSweepingAtoms) Incremental GC in two slices that yields\n"
"        before sweeping the atoms table\n"
"    18: (CheckGrayMarking) Check gray marking invariants after every GC\n"
"    19: (YieldBeforeSweepingCaches) Incremental GC in two slices that yields\n"
"        before sweeping weak caches\n"
"    21: (YieldBeforeSweepingObjects) Incremental GC that yields once per\n"
"        zone before sweeping foreground finalized objects\n"
"    22: (YieldBeforeSweepingNonObjects) Incremental GC that yields once per\n"
"        zone before sweeping non-object GC things\n"
"    23: (YieldBeforeSweepingPropMapTrees) Incremental GC that yields once\n"
"        per zone before sweeping shape trees\n"
"    24: (CheckWeakMapMarking) Check weak map marking invariants after every\n"
"        GC\n"
"    25: (YieldWhileGrayMarking) Incremental GC in two slices that yields\n"
"        during gray marking\n"
"    26: (CheckHeapBeforeMinorGC) Check for invariant violations before every\n"
"        minor GC\n";
// clang-format on

// The set of zeal modes that yield at specific points in collection.
static constexpr EnumSet<ZealMode> YieldPointZealModes = {
   ZealMode::YieldBeforeRootMarking,
   ZealMode::YieldBeforeMarking,
   ZealMode::YieldBeforeSweeping,
   ZealMode::YieldBeforeSweepingAtoms,
   ZealMode::YieldBeforeSweepingCaches,
   ZealMode::YieldBeforeSweepingObjects,
   ZealMode::YieldBeforeSweepingNonObjects,
   ZealMode::YieldBeforeSweepingPropMapTrees,
   ZealMode::YieldWhileGrayMarking};

// The set of zeal modes that control incremental slices.
static constexpr EnumSet<ZealMode> IncrementalSliceZealModes =
   YieldPointZealModes +
   EnumSet<ZealMode>{ZealMode::IncrementalMultipleSlices};

// The set of zeal modes that trigger GC periodically.
static constexpr EnumSet<ZealMode> PeriodicGCZealModes =
   IncrementalSliceZealModes +
   EnumSet<ZealMode>{ZealMode::Alloc, ZealMode::VerifierPost,
                     ZealMode::GenerationalGC, ZealMode::Compact};

// The set of zeal modes that are mutually exclusive. All of these trigger GC
// except VerifierPre.
static constexpr EnumSet<ZealMode> ExclusiveZealModes =
   PeriodicGCZealModes + EnumSet<ZealMode>{ZealMode::VerifierPre};

void GCRuntime::setZeal(uint8_t zeal, uint32_t frequency) {
 MOZ_ASSERT(zeal <= unsigned(ZealMode::Limit));

 if (verifyPreData) {
   VerifyBarriers(rt, PreBarrierVerifier);
 }

 if (zeal == 0) {
   if (hasZealMode(ZealMode::GenerationalGC)) {
     clearZealMode(ZealMode::GenerationalGC);
   }

   if (isIncrementalGCInProgress()) {
     finishGC(JS::GCReason::DEBUG_GC);
   }

   zealModeBits = 0;
   zealFrequency = 0;
   nextScheduled = 0;
   return;
 }

 // Modes that trigger periodically are mutually exclusive. If we're setting
 // one of those, we first reset all of them.
 ZealMode zealMode = ZealMode(zeal);
 if (ExclusiveZealModes.contains(zealMode)) {
   for (auto mode : ExclusiveZealModes) {
     if (hasZealMode(mode)) {
       clearZealMode(mode);
     }
   }
 }

 if (zealMode == ZealMode::GenerationalGC) {
   evictNursery(JS::GCReason::EVICT_NURSERY);
   nursery().enterZealMode();
 }

 zealModeBits |= 1 << zeal;
 zealFrequency = frequency;

 if (PeriodicGCZealModes.contains(zealMode)) {
   nextScheduled = frequency;
 }
}

void GCRuntime::unsetZeal(uint8_t zeal) {
 MOZ_ASSERT(zeal <= unsigned(ZealMode::Limit));
 ZealMode zealMode = ZealMode(zeal);

 if (!hasZealMode(zealMode)) {
   return;
 }

 if (verifyPreData) {
   VerifyBarriers(rt, PreBarrierVerifier);
 }

 clearZealMode(zealMode);

 if (zealModeBits == 0) {
   if (isIncrementalGCInProgress()) {
     finishGC(JS::GCReason::DEBUG_GC);
   }

   zealFrequency = 0;
   nextScheduled = 0;
 }
}

void GCRuntime::setNextScheduled(uint32_t count) { nextScheduled = count; }

static bool ParseZealModeName(const CharRange& text, uint32_t* modeOut) {
 struct ModeInfo {
   const char* name;
   size_t length;
   uint32_t value;
 };

 static const ModeInfo zealModes[] = {{"None", 0},
#  define ZEAL_MODE(name, value) {#name, strlen(#name), value},
                                      JS_FOR_EACH_ZEAL_MODE(ZEAL_MODE)
#  undef ZEAL_MODE
 };

 for (auto mode : zealModes) {
   if (text.length() == mode.length &&
       memcmp(text.begin().get(), mode.name, mode.length) == 0) {
     *modeOut = mode.value;
     return true;
   }
 }

 return false;
}

static bool ParseZealModeNumericParam(const CharRange& text,
                                     uint32_t* paramOut) {
 if (text.length() == 0) {
   return false;
 }

 for (auto c : text) {
   if (!mozilla::IsAsciiDigit(c)) {
     return false;
   }
 }

 *paramOut = atoi(text.begin().get());
 return true;
}

static bool PrintZealHelpAndFail() {
 fprintf(stderr, "Format: JS_GC_ZEAL=mode[;mode2;mode3...][,frequency]\n");
 fprintf(stderr, "  Examples: JS_GC_ZEAL=2 (mode 2 with default frequency)\n");
 fprintf(
     stderr,
     "            JS_GC_ZEAL=2;7 (modes 2 and 7 with default frequency)\n");
 fprintf(stderr, "            JS_GC_ZEAL=2,100 (mode 2 with frequency 100)\n");
 fprintf(stderr,
         "            JS_GC_ZEAL=2;7,100 (modes 2 and 7, both with frequency "
         "100)\n");
 fputs(ZealModeHelpText, stderr);
 return false;
}

bool GCRuntime::parseZeal(const char* str, size_t len, ZealSettings* zeal,
                         bool* invalid) {
 CharRange text(str, len);

 // The zeal mode setting is a string consisting of one or more mode
 // specifiers separated by ';', optionally followed by a ',' and the trigger
 // frequency. The mode specifiers can by a mode name or its number.

 *invalid = false;

 CharRangeVector parts;
 if (!SplitStringBy(text, ',', &parts)) {
   return false;
 }

 if (parts.length() == 0 || parts.length() > 2) {
   *invalid = true;
   return true;
 }

 uint32_t frequency = JS::ShellDefaultGCZealFrequency;
 if (parts.length() == 2 && !ParseZealModeNumericParam(parts[1], &frequency)) {
   *invalid = true;
   return true;
 }

 CharRangeVector modes;
 if (!SplitStringBy(parts[0], ';', &modes)) {
   return false;
 }

 for (const auto& descr : modes) {
   uint32_t mode;
   if (!ParseZealModeName(descr, &mode) &&
       !(ParseZealModeNumericParam(descr, &mode) &&
         mode <= unsigned(ZealMode::Limit))) {
     *invalid = true;
     return true;
   }

   if (!zeal->append(ZealSetting{uint8_t(mode), frequency})) {
     return false;
   }
 }

 return true;
}

bool GCRuntime::parseAndSetZeal(const char* str) {
 ZealSettings zeal;
 bool invalid = false;
 if (!parseZeal(str, strlen(str), &zeal, &invalid)) {
   return false;
 }

 if (invalid) {
   return PrintZealHelpAndFail();
 }

 for (auto [mode, frequency] : zeal) {
   setZeal(mode, frequency);
 }

 return true;
}

bool GCRuntime::needZealousGC() {
 if (nextScheduled > 0 && --nextScheduled == 0) {
   if (hasAnyZealModeOf(PeriodicGCZealModes)) {
     nextScheduled = zealFrequency;
   }
   return true;
 }
 return false;
}

bool GCRuntime::zealModeControlsYieldPoint() const {
 // Indicates whether a zeal mode is enabled that controls the point at which
 // the collector yields to the mutator. Yield can happen once per collection
 // or once per zone depending on the mode.
 return hasAnyZealModeOf(YieldPointZealModes);
}

bool GCRuntime::hasZealMode(ZealMode mode) const {
 static_assert(size_t(ZealMode::Limit) < sizeof(zealModeBits) * 8,
               "Zeal modes must fit in zealModeBits");
 return zealModeBits & (1 << uint32_t(mode));
}

bool GCRuntime::hasAnyZealModeOf(EnumSet<ZealMode> modes) const {
 return zealModeBits & modes.serialize();
}

void GCRuntime::clearZealMode(ZealMode mode) {
 MOZ_ASSERT(hasZealMode(mode));

 if (mode == ZealMode::GenerationalGC) {
   evictNursery();
   nursery().leaveZealMode();
 }

 zealModeBits &= ~(1 << uint32_t(mode));
 MOZ_ASSERT(!hasZealMode(mode));
}

void js::gc::DumpArenaInfo() {
 fprintf(stderr, "Arena header size: %zu\n\n", ArenaHeaderSize);

 fprintf(stderr, "GC thing kinds:\n");
 fprintf(stderr, "%25s %8s %8s %8s\n",
         "AllocKind:", "Size:", "Count:", "Padding:");
 for (auto kind : AllAllocKinds()) {
   fprintf(stderr, "%25s %8zu %8zu %8zu\n", AllocKindName(kind),
           Arena::thingSize(kind), Arena::thingsPerArena(kind),
           Arena::firstThingOffset(kind) - ArenaHeaderSize);
 }
}

#endif  // JS_GC_ZEAL
       //
const char* js::gc::AllocKindName(AllocKind kind) {
 static const char* const names[] = {
#define EXPAND_THING_NAME(allocKind, _1, _2, _3, _4, _5, _6) #allocKind,
     FOR_EACH_ALLOCKIND(EXPAND_THING_NAME)
#undef EXPAND_THING_NAME
 };
 static_assert(std::size(names) == AllocKindCount,
               "names array should have an entry for every AllocKind");

 size_t i = size_t(kind);
 MOZ_ASSERT(i < std::size(names));
 return names[i];
}

bool GCRuntime::init(uint32_t maxbytes) {
 MOZ_ASSERT(!wasInitialized());

 MOZ_ASSERT(SystemPageSize());
 Arena::staticAsserts();
 Arena::checkLookupTables();

 if (!TlsGCContext.init()) {
   return false;
 }
 TlsGCContext.set(&mainThreadContext.ref());

 updateHelperThreadCount();

#ifdef JS_GC_ZEAL
 const char* size = getenv("JSGC_MARK_STACK_LIMIT");
 if (size) {
   maybeMarkStackLimit = atoi(size);
 }
#endif

 if (!updateMarkersVector()) {
   return false;
 }

 {
   AutoLockGCBgAlloc lock(this);

   MOZ_ALWAYS_TRUE(tunables.setParameter(JSGC_MAX_BYTES, maxbytes));

   if (!nursery().init(lock)) {
     return false;
   }
 }

#ifdef JS_GC_ZEAL
 const char* zealSpec = getenv("JS_GC_ZEAL");
 if (zealSpec && zealSpec[0] && !parseAndSetZeal(zealSpec)) {
   return false;
 }
#endif

 for (auto& marker : markers) {
   if (!marker->init()) {
     return false;
   }
 }

 if (!initSweepActions()) {
   return false;
 }

 UniquePtr<Zone> zone = MakeUnique<Zone>(rt, Zone::AtomsZone);
 if (!zone || !zone->init()) {
   return false;
 }

 // The atoms zone is stored as the first element of the zones vector.
 MOZ_ASSERT(zone->isAtomsZone());
 MOZ_ASSERT(zones().empty());
 MOZ_ALWAYS_TRUE(zones().reserve(1));  // ZonesVector has inline capacity 4.
 zones().infallibleAppend(zone.release());

 gcprobes::Init(this);

 initialized = true;
 return true;
}

void GCRuntime::finish() {
 MOZ_ASSERT(inPageLoadCount == 0);
 MOZ_ASSERT(!sharedAtomsZone_);

 // Wait for nursery background free to end and disable it to release memory.
 if (nursery().isEnabled()) {
   nursery().disable();
 }

 // Wait until the background finalization and allocation stops and the
 // helper thread shuts down before we forcefully release any remaining GC
 // memory.
 sweepTask.join();
 markTask.join();
 freeTask.join();
 allocTask.cancelAndWait();
 decommitTask.cancelAndWait();
#ifdef DEBUG
 {
   MOZ_ASSERT(dispatchedParallelTasks == 0);
   AutoLockHelperThreadState lock;
   MOZ_ASSERT(queuedParallelTasks.ref().isEmpty(lock));
 }
#endif

 releaseMarkingThreads();

#ifdef JS_GC_ZEAL
 // Free memory associated with GC verification.
 finishVerifier();
#endif

 // Delete all remaining zones.
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   AutoSetThreadIsSweeping threadIsSweeping(rt->gcContext(), zone);
   for (CompartmentsInZoneIter comp(zone); !comp.done(); comp.next()) {
     for (RealmsInCompartmentIter realm(comp); !realm.done(); realm.next()) {
       js_delete(realm.get());
     }
     comp->realms().clear();
     js_delete(comp.get());
   }
   zone->compartments().clear();
   js_delete(zone.get());
 }

 zones().clear();

 {
   AutoLockGC lock(this);
   clearCurrentChunk(lock);
 }

 FreeChunkPool(fullChunks_.ref());
 FreeChunkPool(availableChunks_.ref());
 FreeChunkPool(emptyChunks_.ref());

 TlsGCContext.set(nullptr);

 gcprobes::Finish(this);

 nursery().printTotalProfileTimes();
 stats().printTotalProfileTimes();
}

bool GCRuntime::freezeSharedAtomsZone() {
 // This is called just after permanent atoms and well-known symbols have been
 // created. At this point all existing atoms and symbols are permanent.
 //
 // This method makes the current atoms zone into a shared atoms zone and
 // removes it from the zones list. Everything in it is marked black. A new
 // empty atoms zone is created, where all atoms local to this runtime will
 // live.
 //
 // The shared atoms zone will not be collected until shutdown when it is
 // returned to the zone list by restoreSharedAtomsZone().

 MOZ_ASSERT(rt->isMainRuntime());
 MOZ_ASSERT(!sharedAtomsZone_);
 MOZ_ASSERT(zones().length() == 1);
 MOZ_ASSERT(atomsZone());
 MOZ_ASSERT(!atomsZone()->wasGCStarted());
 MOZ_ASSERT(!atomsZone()->needsIncrementalBarrier());

 AutoAssertEmptyNursery nurseryIsEmpty(rt->mainContextFromOwnThread());

 atomsZone()->arenas.clearFreeLists();

 for (auto kind : AllAllocKinds()) {
   for (auto thing =
            atomsZone()->cellIterUnsafe<TenuredCell>(kind, nurseryIsEmpty);
        !thing.done(); thing.next()) {
     TenuredCell* cell = thing.getCell();
     MOZ_ASSERT((cell->is<JSString>() &&
                 cell->as<JSString>()->isPermanentAndMayBeShared()) ||
                (cell->is<JS::Symbol>() &&
                 cell->as<JS::Symbol>()->isPermanentAndMayBeShared()));
     cell->markBlack();
   }
 }

 sharedAtomsZone_ = atomsZone();
 zones().clear();

 UniquePtr<Zone> zone = MakeUnique<Zone>(rt, Zone::AtomsZone);
 if (!zone || !zone->init()) {
   return false;
 }

 MOZ_ASSERT(zone->isAtomsZone());
 zones().infallibleAppend(zone.release());

 return true;
}

void GCRuntime::restoreSharedAtomsZone() {
 // Return the shared atoms zone to the zone list. This allows the contents of
 // the shared atoms zone to be collected when the parent runtime is shut down.

 if (!sharedAtomsZone_) {
   return;
 }

 MOZ_ASSERT(rt->isMainRuntime());
 MOZ_ASSERT(rt->childRuntimeCount == 0);

 // Insert at start to preserve invariant that atoms zones come first.
 AutoEnterOOMUnsafeRegion oomUnsafe;
 if (!zones().insert(zones().begin(), sharedAtomsZone_)) {
   oomUnsafe.crash("restoreSharedAtomsZone");
 }

 sharedAtomsZone_ = nullptr;
}

bool GCRuntime::setParameter(JSContext* cx, JSGCParamKey key, uint32_t value) {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));

 AutoStopVerifyingBarriers pauseVerification(rt, false);
 FinishGC(cx);
 waitBackgroundSweepEnd();

 // Special case: if there is still an `AutoDisableGenerationalGC` active (eg
 // from the --no-ggc command-line flag), then do not allow controlling the
 // state of the nursery. Done here where cx is available.
 if (key == JSGC_NURSERY_ENABLED && cx->generationalDisabled > 0) {
   return false;
 }

 AutoLockGC lock(this);
 return setParameter(key, value, lock);
}

static bool IsGCThreadParameter(JSGCParamKey key) {
 return key == JSGC_HELPER_THREAD_RATIO || key == JSGC_MAX_HELPER_THREADS ||
        key == JSGC_MAX_MARKING_THREADS;
}

bool GCRuntime::setParameter(JSGCParamKey key, uint32_t value,
                            AutoLockGC& lock) {
 switch (key) {
   case JSGC_SLICE_TIME_BUDGET_MS:
     defaultTimeBudgetMS_ = value;
     break;
   case JSGC_INCREMENTAL_GC_ENABLED:
     setIncrementalGCEnabled(value != 0);
     break;
   case JSGC_PER_ZONE_GC_ENABLED:
     perZoneGCEnabled = value != 0;
     break;
   case JSGC_COMPACTING_ENABLED:
     compactingEnabled = value != 0;
     break;
   case JSGC_NURSERY_ENABLED: {
     AutoUnlockGC unlock(lock);
     setNurseryEnabled(value != 0);
     break;
   }
   case JSGC_PARALLEL_MARKING_ENABLED:
     setParallelMarkingEnabled(value != 0);
     break;
   case JSGC_INCREMENTAL_WEAKMAP_ENABLED:
     for (auto& marker : markers) {
       marker->incrementalWeakMapMarkingEnabled = value != 0;
     }
     break;
   case JSGC_SEMISPACE_NURSERY_ENABLED: {
     AutoUnlockGC unlock(lock);
     nursery().setSemispaceEnabled(value);
     break;
   }
   case JSGC_MIN_EMPTY_CHUNK_COUNT:
     setMinEmptyChunkCount(value, lock);
     break;
   default:
     if (IsGCThreadParameter(key)) {
       return setThreadParameter(key, value, lock);
     }

     if (!tunables.setParameter(key, value)) {
       return false;
     }
     updateAllGCStartThresholds();
 }

 return true;
}

bool GCRuntime::setThreadParameter(JSGCParamKey key, uint32_t value,
                                  AutoLockGC& lock) {
 if (rt->parentRuntime) {
   // Don't allow these to be set for worker runtimes.
   return false;
 }

 switch (key) {
   case JSGC_HELPER_THREAD_RATIO:
     if (value == 0) {
       return false;
     }
     helperThreadRatio = double(value) / 100.0;
     break;
   case JSGC_MAX_HELPER_THREADS:
     if (value == 0) {
       return false;
     }
     maxHelperThreads = value;
     break;
   case JSGC_MAX_MARKING_THREADS:
     maxMarkingThreads = std::min(size_t(value), MaxParallelWorkers);
     break;
   default:
     MOZ_CRASH("Unexpected parameter key");
 }

 updateHelperThreadCount();
 initOrDisableParallelMarking();

 return true;
}

void GCRuntime::resetParameter(JSContext* cx, JSGCParamKey key) {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));

 AutoStopVerifyingBarriers pauseVerification(rt, false);
 FinishGC(cx);
 waitBackgroundSweepEnd();

 AutoLockGC lock(this);
 resetParameter(key, lock);
}

void GCRuntime::resetParameter(JSGCParamKey key, AutoLockGC& lock) {
 switch (key) {
   case JSGC_SLICE_TIME_BUDGET_MS:
     defaultTimeBudgetMS_ = TuningDefaults::DefaultTimeBudgetMS;
     break;
   case JSGC_INCREMENTAL_GC_ENABLED:
     setIncrementalGCEnabled(TuningDefaults::IncrementalGCEnabled);
     break;
   case JSGC_PER_ZONE_GC_ENABLED:
     perZoneGCEnabled = TuningDefaults::PerZoneGCEnabled;
     break;
   case JSGC_COMPACTING_ENABLED:
     compactingEnabled = TuningDefaults::CompactingEnabled;
     break;
   case JSGC_NURSERY_ENABLED:
     setNurseryEnabled(TuningDefaults::NurseryEnabled);
     break;
   case JSGC_PARALLEL_MARKING_ENABLED:
     setParallelMarkingEnabled(TuningDefaults::ParallelMarkingEnabled);
     break;
   case JSGC_INCREMENTAL_WEAKMAP_ENABLED:
     for (auto& marker : markers) {
       marker->incrementalWeakMapMarkingEnabled =
           TuningDefaults::IncrementalWeakMapMarkingEnabled;
     }
     break;
   case JSGC_SEMISPACE_NURSERY_ENABLED: {
     AutoUnlockGC unlock(lock);
     nursery().setSemispaceEnabled(TuningDefaults::SemispaceNurseryEnabled);
     break;
   }
   case JSGC_MIN_EMPTY_CHUNK_COUNT:
     setMinEmptyChunkCount(TuningDefaults::MinEmptyChunkCount, lock);
     break;
   default:
     if (IsGCThreadParameter(key)) {
       resetThreadParameter(key, lock);
       return;
     }

     tunables.resetParameter(key);
     updateAllGCStartThresholds();
 }
}

void GCRuntime::resetThreadParameter(JSGCParamKey key, AutoLockGC& lock) {
 if (rt->parentRuntime) {
   return;
 }

 switch (key) {
   case JSGC_HELPER_THREAD_RATIO:
     helperThreadRatio = TuningDefaults::HelperThreadRatio;
     break;
   case JSGC_MAX_HELPER_THREADS:
     maxHelperThreads = TuningDefaults::MaxHelperThreads;
     break;
   case JSGC_MAX_MARKING_THREADS:
     maxMarkingThreads = TuningDefaults::MaxMarkingThreads;
     break;
   default:
     MOZ_CRASH("Unexpected parameter key");
 }

 updateHelperThreadCount();
 initOrDisableParallelMarking();
}

uint32_t GCRuntime::getParameter(JSGCParamKey key) {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));
 AutoLockGC lock(this);
 return getParameter(key, lock);
}

uint32_t GCRuntime::getParameter(JSGCParamKey key, const AutoLockGC& lock) {
 switch (key) {
   case JSGC_BYTES:
     return uint32_t(heapSize.bytes());
   case JSGC_NURSERY_BYTES:
     return nursery().capacity();
   case JSGC_NUMBER:
     return uint32_t(number);
   case JSGC_MAJOR_GC_NUMBER:
     return uint32_t(majorGCNumber);
   case JSGC_MINOR_GC_NUMBER:
     return uint32_t(minorGCNumber);
   case JSGC_SLICE_NUMBER:
     return uint32_t(sliceNumber);
   case JSGC_INCREMENTAL_GC_ENABLED:
     return incrementalGCEnabled;
   case JSGC_PER_ZONE_GC_ENABLED:
     return perZoneGCEnabled;
   case JSGC_UNUSED_CHUNKS:
     clearCurrentChunk(lock);
     return uint32_t(emptyChunks(lock).count());
   case JSGC_TOTAL_CHUNKS:
     clearCurrentChunk(lock);
     return uint32_t(fullChunks(lock).count() + availableChunks(lock).count() +
                     emptyChunks(lock).count());
   case JSGC_SLICE_TIME_BUDGET_MS:
     MOZ_RELEASE_ASSERT(defaultTimeBudgetMS_ >= 0);
     MOZ_RELEASE_ASSERT(defaultTimeBudgetMS_ <= UINT32_MAX);
     return uint32_t(defaultTimeBudgetMS_);
   case JSGC_MIN_EMPTY_CHUNK_COUNT:
     return minEmptyChunkCount(lock);
   case JSGC_COMPACTING_ENABLED:
     return compactingEnabled;
   case JSGC_NURSERY_ENABLED:
     return nursery().isEnabled();
   case JSGC_PARALLEL_MARKING_ENABLED:
     return parallelMarkingEnabled;
   case JSGC_INCREMENTAL_WEAKMAP_ENABLED:
     return marker().incrementalWeakMapMarkingEnabled;
   case JSGC_SEMISPACE_NURSERY_ENABLED:
     return nursery().semispaceEnabled();
   case JSGC_CHUNK_BYTES:
     return ChunkSize;
   case JSGC_HELPER_THREAD_RATIO:
     MOZ_ASSERT(helperThreadRatio > 0.0);
     return uint32_t(helperThreadRatio * 100.0);
   case JSGC_MAX_HELPER_THREADS:
     MOZ_ASSERT(maxHelperThreads <= UINT32_MAX);
     return maxHelperThreads;
   case JSGC_HELPER_THREAD_COUNT:
     return helperThreadCount;
   case JSGC_MAX_MARKING_THREADS:
     return maxMarkingThreads;
   case JSGC_MARKING_THREAD_COUNT:
     return markingThreadCount;
   case JSGC_SYSTEM_PAGE_SIZE_KB:
     return SystemPageSize() / 1024;
   case JSGC_HIGH_FREQUENCY_MODE:
     return schedulingState.inHighFrequencyGCMode();
   default:
     return tunables.getParameter(key);
 }
}

#ifdef JS_GC_ZEAL
void GCRuntime::setMarkStackLimit(size_t limit, AutoLockGC& lock) {
 MOZ_ASSERT(!JS::RuntimeHeapIsBusy());

 maybeMarkStackLimit = limit;

 AutoUnlockGC unlock(lock);
 AutoStopVerifyingBarriers pauseVerification(rt, false);
 for (auto& marker : markers) {
   marker->setMaxCapacity(limit);
 }
}
#endif

void GCRuntime::setIncrementalGCEnabled(bool enabled) {
 incrementalGCEnabled = enabled;
}

void GCRuntime::setNurseryEnabled(bool enabled) {
 if (enabled) {
   nursery().enable();
 } else {
   if (nursery().isEnabled()) {
     minorGC(JS::GCReason::EVICT_NURSERY);
     nursery().disable();
   }
 }
}

void GCRuntime::updateHelperThreadCount() {
 if (!CanUseExtraThreads()) {
   // startTask will run the work on the main thread if the count is 1.
   MOZ_ASSERT(helperThreadCount == 1);
   markingThreadCount = 1;

   AutoLockHelperThreadState lock;
   maxParallelThreads = 1;
   return;
 }

 // Number of extra threads required during parallel marking to ensure we can
 // start the necessary marking tasks. Background free and background
 // allocation may already be running and we want to avoid these tasks blocking
 // marking. In real configurations there will be enough threads that this
 // won't affect anything.
 static constexpr size_t SpareThreadsDuringParallelMarking = 2;

 // Calculate the target thread count for GC parallel tasks.
 size_t cpuCount = GetHelperThreadCPUCount();
 helperThreadCount =
     std::clamp(size_t(double(cpuCount) * helperThreadRatio.ref()), size_t(1),
                maxHelperThreads.ref());

 // Calculate the target thread count for parallel marking, which uses separate
 // parameters to let us adjust this independently.
 markingThreadCount = std::min(cpuCount / 2, maxMarkingThreads.ref());

 // Calculate the overall target thread count taking into account the separate
 // target for parallel marking threads. Add spare threads to avoid blocking
 // parallel marking when there is other GC work happening.
 size_t targetCount =
     std::max(helperThreadCount.ref(),
              markingThreadCount.ref() + SpareThreadsDuringParallelMarking);

 // Attempt to create extra threads if possible. This is not supported when
 // using an external thread pool.
 AutoLockHelperThreadState lock;
 (void)HelperThreadState().ensureThreadCount(targetCount, lock);

 // Limit all thread counts based on the number of threads available, which may
 // be fewer than requested.
 size_t availableThreadCount = GetHelperThreadCount();
 MOZ_ASSERT(availableThreadCount != 0);
 targetCount = std::min(targetCount, availableThreadCount);
 helperThreadCount = std::min(helperThreadCount.ref(), availableThreadCount);
 if (availableThreadCount < SpareThreadsDuringParallelMarking) {
   markingThreadCount = 1;
 } else {
   markingThreadCount =
       std::min(markingThreadCount.ref(),
                availableThreadCount - SpareThreadsDuringParallelMarking);
 }

 // Update the maximum number of threads that will be used for GC work.
 maxParallelThreads = targetCount;
}

size_t GCRuntime::markingWorkerCount() const {
 if (!CanUseExtraThreads() || !parallelMarkingEnabled) {
   return 1;
 }

 if (markingThreadCount) {
   return markingThreadCount;
 }

 // Limit parallel marking to use at most two threads initially.
 return 2;
}

#ifdef DEBUG
void GCRuntime::assertNoMarkingWork() const {
 for (const auto& marker : markers) {
   MOZ_ASSERT(marker->isDrained());
 }
 MOZ_ASSERT(!hasDelayedMarking());
}
#endif

bool GCRuntime::setParallelMarkingEnabled(bool enabled) {
 if (enabled == parallelMarkingEnabled) {
   return true;
 }

 parallelMarkingEnabled = enabled;
 return initOrDisableParallelMarking();
}

bool GCRuntime::initOrDisableParallelMarking() {
 // Attempt to initialize parallel marking state or disable it on failure. This
 // is called when parallel marking is enabled or disabled.

 MOZ_ASSERT(markers.length() != 0);

 if (updateMarkersVector()) {
   return true;
 }

 // Failed to initialize parallel marking so disable it instead.
 MOZ_ASSERT(parallelMarkingEnabled);
 parallelMarkingEnabled = false;
 MOZ_ALWAYS_TRUE(updateMarkersVector());
 return false;
}

void GCRuntime::releaseMarkingThreads() {
 MOZ_ALWAYS_TRUE(reserveMarkingThreads(0));
}

bool GCRuntime::reserveMarkingThreads(size_t newCount) {
 if (reservedMarkingThreads == newCount) {
   return true;
 }

 // Update the helper thread system's global count by subtracting this
 // runtime's current contribution |reservedMarkingThreads| and adding the new
 // contribution |newCount|.

 AutoLockHelperThreadState lock;
 auto& globalCount = HelperThreadState().gcParallelMarkingThreads;
 MOZ_ASSERT(globalCount >= reservedMarkingThreads);
 size_t newGlobalCount = globalCount - reservedMarkingThreads + newCount;
 if (newGlobalCount > HelperThreadState().threadCount) {
   // Not enough total threads.
   return false;
 }

 globalCount = newGlobalCount;
 reservedMarkingThreads = newCount;
 return true;
}

size_t GCRuntime::getMaxParallelThreads() const {
 AutoLockHelperThreadState lock;
 return maxParallelThreads.ref();
}

bool GCRuntime::updateMarkersVector() {
 MOZ_ASSERT(helperThreadCount >= 1,
            "There must always be at least one mark task");
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));
 assertNoMarkingWork();

 // Limit worker count to number of GC parallel tasks that can run
 // concurrently, otherwise one thread can deadlock waiting on another.
 size_t targetCount = std::min(markingWorkerCount(), getMaxParallelThreads());

 if (rt->isMainRuntime()) {
   // For the main runtime, reserve helper threads as long as parallel marking
   // is enabled. Worker runtimes may not mark in parallel if there are
   // insufficient threads available at the time.
   size_t threadsToReserve = targetCount > 1 ? targetCount : 0;
   if (!reserveMarkingThreads(threadsToReserve)) {
     return false;
   }
 }

 if (markers.length() > targetCount) {
   return markers.resize(targetCount);
 }

 while (markers.length() < targetCount) {
   auto marker = MakeUnique<GCMarker>(rt);
   if (!marker) {
     return false;
   }

#ifdef JS_GC_ZEAL
   if (maybeMarkStackLimit) {
     marker->setMaxCapacity(maybeMarkStackLimit);
   }
#endif

   if (!marker->init()) {
     return false;
   }

   if (!markers.emplaceBack(std::move(marker))) {
     return false;
   }
 }

 return true;
}

template <typename F>
static bool EraseCallback(CallbackVector<F>& vector, F callback) {
 for (Callback<F>* p = vector.begin(); p != vector.end(); p++) {
   if (p->op == callback) {
     vector.erase(p);
     return true;
   }
 }

 return false;
}

template <typename F>
static bool EraseCallback(CallbackVector<F>& vector, F callback, void* data) {
 for (Callback<F>* p = vector.begin(); p != vector.end(); p++) {
   if (p->op == callback && p->data == data) {
     vector.erase(p);
     return true;
   }
 }

 return false;
}

bool GCRuntime::addBlackRootsTracer(JSTraceDataOp traceOp, void* data) {
 AssertHeapIsIdle();
 return blackRootTracers.ref().append(Callback<JSTraceDataOp>(traceOp, data));
}

void GCRuntime::removeBlackRootsTracer(JSTraceDataOp traceOp, void* data) {
 // Can be called from finalizers
 MOZ_ALWAYS_TRUE(EraseCallback(blackRootTracers.ref(), traceOp, data));
}

void GCRuntime::setGrayRootsTracer(JSGrayRootsTracer traceOp, void* data) {
 AssertHeapIsIdle();
 grayRootTracer.ref() = {traceOp, data};
}

void GCRuntime::clearBlackAndGrayRootTracers() {
 MOZ_ASSERT(rt->isBeingDestroyed());
 blackRootTracers.ref().clear();
 setGrayRootsTracer(nullptr, nullptr);
}

void GCRuntime::setGCCallback(JSGCCallback callback, void* data) {
 gcCallback.ref() = {callback, data};
}

void GCRuntime::callGCCallback(JSGCStatus status, JS::GCReason reason) const {
 const auto& callback = gcCallback.ref();
 MOZ_ASSERT(callback.op);
 callback.op(rt->mainContextFromOwnThread(), status, reason, callback.data);
}

void GCRuntime::setObjectsTenuredCallback(JSObjectsTenuredCallback callback,
                                         void* data) {
 tenuredCallback.ref() = {callback, data};
}

void GCRuntime::callObjectsTenuredCallback() {
 JS::AutoSuppressGCAnalysis nogc;
 const auto& callback = tenuredCallback.ref();
 if (callback.op) {
   callback.op(&mainThreadContext.ref(), callback.data);
 }
}

bool GCRuntime::addFinalizeCallback(JSFinalizeCallback callback, void* data) {
 return finalizeCallbacks.ref().append(
     Callback<JSFinalizeCallback>(callback, data));
}

void GCRuntime::removeFinalizeCallback(JSFinalizeCallback callback) {
 MOZ_ALWAYS_TRUE(EraseCallback(finalizeCallbacks.ref(), callback));
}

void GCRuntime::callFinalizeCallbacks(JS::GCContext* gcx,
                                     JSFinalizeStatus status) const {
 for (const auto& p : finalizeCallbacks.ref()) {
   p.op(gcx, status, p.data);
 }
}

void GCRuntime::setHostCleanupFinalizationRegistryCallback(
   JSHostCleanupFinalizationRegistryCallback callback, void* data) {
 hostCleanupFinalizationRegistryCallback.ref() = {callback, data};
}

void GCRuntime::callHostCleanupFinalizationRegistryCallback(
   JSFunction* doCleanup, JSObject* hostDefinedData) {
 JS::AutoSuppressGCAnalysis nogc;
 const auto& callback = hostCleanupFinalizationRegistryCallback.ref();
 if (callback.op) {
   callback.op(doCleanup, hostDefinedData, callback.data);
 }
}

bool GCRuntime::addWeakPointerZonesCallback(JSWeakPointerZonesCallback callback,
                                           void* data) {
 return updateWeakPointerZonesCallbacks.ref().append(
     Callback<JSWeakPointerZonesCallback>(callback, data));
}

void GCRuntime::removeWeakPointerZonesCallback(
   JSWeakPointerZonesCallback callback) {
 MOZ_ALWAYS_TRUE(
     EraseCallback(updateWeakPointerZonesCallbacks.ref(), callback));
}

void GCRuntime::callWeakPointerZonesCallbacks(JSTracer* trc) const {
 for (auto const& p : updateWeakPointerZonesCallbacks.ref()) {
   p.op(trc, p.data);
 }
}

bool GCRuntime::addWeakPointerCompartmentCallback(
   JSWeakPointerCompartmentCallback callback, void* data) {
 return updateWeakPointerCompartmentCallbacks.ref().append(
     Callback<JSWeakPointerCompartmentCallback>(callback, data));
}

void GCRuntime::removeWeakPointerCompartmentCallback(
   JSWeakPointerCompartmentCallback callback) {
 MOZ_ALWAYS_TRUE(
     EraseCallback(updateWeakPointerCompartmentCallbacks.ref(), callback));
}

void GCRuntime::callWeakPointerCompartmentCallbacks(
   JSTracer* trc, JS::Compartment* comp) const {
 for (auto const& p : updateWeakPointerCompartmentCallbacks.ref()) {
   p.op(trc, comp, p.data);
 }
}

JS::GCSliceCallback GCRuntime::setSliceCallback(JS::GCSliceCallback callback) {
 return stats().setSliceCallback(callback);
}

bool GCRuntime::addNurseryCollectionCallback(
   JS::GCNurseryCollectionCallback callback, void* data) {
 return nurseryCollectionCallbacks.ref().append(
     Callback<JS::GCNurseryCollectionCallback>(callback, data));
}

void GCRuntime::removeNurseryCollectionCallback(
   JS::GCNurseryCollectionCallback callback, void* data) {
 MOZ_ALWAYS_TRUE(
     EraseCallback(nurseryCollectionCallbacks.ref(), callback, data));
}

void GCRuntime::callNurseryCollectionCallbacks(JS::GCNurseryProgress progress,
                                              JS::GCReason reason) {
 for (auto const& p : nurseryCollectionCallbacks.ref()) {
   p.op(rt->mainContextFromOwnThread(), progress, reason, p.data);
 }
}

JS::DoCycleCollectionCallback GCRuntime::setDoCycleCollectionCallback(
   JS::DoCycleCollectionCallback callback) {
 const auto prior = gcDoCycleCollectionCallback.ref();
 gcDoCycleCollectionCallback.ref() = {callback, nullptr};
 return prior.op;
}

void GCRuntime::callDoCycleCollectionCallback(JSContext* cx) {
 const auto& callback = gcDoCycleCollectionCallback.ref();
 if (callback.op) {
   callback.op(cx);
 }
}

bool GCRuntime::addRoot(Value* vp, const char* name) {
 /*
  * Sometimes Firefox will hold weak references to objects and then convert
  * them to strong references by calling AddRoot (e.g., via PreserveWrapper,
  * or ModifyBusyCount in workers). We need a read barrier to cover these
  * cases.
  */
 MOZ_ASSERT(vp);
 Value value = *vp;
 if (value.isGCThing()) {
   ValuePreWriteBarrier(value);
 }

 return rootsHash.ref().put(vp, name);
}

void GCRuntime::removeRoot(Value* vp) {
 rootsHash.ref().remove(vp);
 notifyRootsRemoved();
}

/* Compacting GC */

bool js::gc::IsCurrentlyAnimating(const TimeStamp& lastAnimationTime,
                                 const TimeStamp& currentTime) {
 // Assume that we're currently animating if js::NotifyAnimationActivity has
 // been called in the last second.
 static const auto oneSecond = TimeDuration::FromSeconds(1);
 return !lastAnimationTime.IsNull() &&
        currentTime < (lastAnimationTime + oneSecond);
}

static bool DiscardedCodeRecently(Zone* zone, const TimeStamp& currentTime) {
 static const auto thirtySeconds = TimeDuration::FromSeconds(30);
 return !zone->lastDiscardedCodeTime().IsNull() &&
        currentTime < (zone->lastDiscardedCodeTime() + thirtySeconds);
}

bool GCRuntime::shouldCompact() {
 // Compact on shrinking GC if enabled.  Skip compacting in incremental GCs
 // if we are currently animating, unless the user is inactive or we're
 // responding to memory pressure.

 if (!isShrinkingGC() || !isCompactingGCEnabled()) {
   return false;
 }

 if (initialReason == JS::GCReason::USER_INACTIVE ||
     initialReason == JS::GCReason::MEM_PRESSURE) {
   return true;
 }

 return !isIncremental ||
        !IsCurrentlyAnimating(rt->lastAnimationTime, TimeStamp::Now());
}

bool GCRuntime::isCompactingGCEnabled() const {
 return compactingEnabled &&
        rt->mainContextFromOwnThread()->compactingDisabledCount == 0;
}

JS_PUBLIC_API void JS::SetCreateGCSliceBudgetCallback(
   JSContext* cx, JS::CreateSliceBudgetCallback cb) {
 cx->runtime()->gc.createBudgetCallback = cb;
}

void TimeBudget::setDeadlineFromNow() { deadline = TimeStamp::Now() + budget; }

SliceBudget::SliceBudget(TimeBudget time, InterruptRequestFlag* interrupt)
   : counter(StepsPerExpensiveCheck),
     interruptRequested(interrupt),
     budget(TimeBudget(time)) {
 budget.as<TimeBudget>().setDeadlineFromNow();
}

SliceBudget::SliceBudget(WorkBudget work)
   : counter(work.budget), interruptRequested(nullptr), budget(work) {}

int SliceBudget::describe(char* buffer, size_t maxlen) const {
 if (isUnlimited()) {
   return snprintf(buffer, maxlen, "unlimited");
 }

 const char* nonstop = "";
 if (keepGoing) {
   nonstop = "nonstop ";
 }

 if (isWorkBudget()) {
   return snprintf(buffer, maxlen, "%swork(%" PRId64 ")", nonstop,
                   workBudget());
 }

 const char* interruptStr = "";
 if (interruptRequested) {
   interruptStr = interrupted ? "INTERRUPTED " : "interruptible ";
 }
 const char* extra = "";
 if (idle) {
   extra = extended ? " (started idle but extended)" : " (idle)";
 }
 return snprintf(buffer, maxlen, "%s%s%" PRId64 "ms%s", nonstop, interruptStr,
                 timeBudget(), extra);
}

bool SliceBudget::checkOverBudget() {
 MOZ_ASSERT(counter <= 0);
 MOZ_ASSERT(!isUnlimited());

 if (isWorkBudget()) {
   return true;
 }

 if (interruptRequested && *interruptRequested) {
   interrupted = true;
 }

 if (interrupted) {
   return true;
 }

 if (TimeStamp::Now() >= budget.as<TimeBudget>().deadline) {
   return true;
 }

 counter = StepsPerExpensiveCheck;
 return false;
}

void GCRuntime::requestMajorGC(JS::GCReason reason) {
 MOZ_ASSERT_IF(reason != JS::GCReason::BG_TASK_FINISHED,
               !CurrentThreadIsPerformingGC());

 if (majorGCRequested()) {
   return;
 }

 majorGCTriggerReason = reason;
 rt->mainContextFromAnyThread()->requestInterrupt(InterruptReason::MajorGC);
}

bool GCRuntime::triggerGC(JS::GCReason reason) {
 /*
  * Don't trigger GCs if this is being called off the main thread from
  * onTooMuchMalloc().
  */
 if (!CurrentThreadCanAccessRuntime(rt)) {
   return false;
 }

 /* GC is already running. */
 if (JS::RuntimeHeapIsCollecting()) {
   return false;
 }

 JS::PrepareForFullGC(rt->mainContextFromOwnThread());
 requestMajorGC(reason);
 return true;
}

void GCRuntime::maybeTriggerGCAfterAlloc(Zone* zone) {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));
 MOZ_ASSERT(!JS::RuntimeHeapIsCollecting());

 TriggerResult trigger =
     checkHeapThreshold(zone, zone->gcHeapSize, zone->gcHeapThreshold);

 if (trigger.shouldTrigger) {
   // Start or continue an in progress incremental GC. We do this to try to
   // avoid performing non-incremental GCs on zones which allocate a lot of
   // data, even when incremental slices can't be triggered via scheduling in
   // the event loop.
   triggerZoneGC(zone, JS::GCReason::ALLOC_TRIGGER, trigger.usedBytes,
                 trigger.thresholdBytes);
 }
}

void js::gc::MaybeMallocTriggerZoneGC(JSRuntime* rt, ZoneAllocator* zoneAlloc,
                                     const HeapSize& heap,
                                     const HeapThreshold& threshold,
                                     JS::GCReason reason) {
 rt->gc.maybeTriggerGCAfterMalloc(Zone::from(zoneAlloc), heap, threshold,
                                  reason);
}

void GCRuntime::maybeTriggerGCAfterMalloc(Zone* zone) {
 if (maybeTriggerGCAfterMalloc(zone, zone->mallocHeapSize,
                               zone->mallocHeapThreshold,
                               JS::GCReason::TOO_MUCH_MALLOC)) {
   return;
 }

 maybeTriggerGCAfterMalloc(zone, zone->jitHeapSize, zone->jitHeapThreshold,
                           JS::GCReason::TOO_MUCH_JIT_CODE);
}

bool GCRuntime::maybeTriggerGCAfterMalloc(Zone* zone, const HeapSize& heap,
                                         const HeapThreshold& threshold,
                                         JS::GCReason reason) {
 // Ignore malloc during sweeping, for example when we resize hash tables.
 if (heapState() != JS::HeapState::Idle) {
   return false;
 }

 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));

 TriggerResult trigger = checkHeapThreshold(zone, heap, threshold);
 if (!trigger.shouldTrigger) {
   return false;
 }

 // Trigger a zone GC. budgetIncrementalGC() will work out whether to do an
 // incremental or non-incremental collection.
 triggerZoneGC(zone, reason, trigger.usedBytes, trigger.thresholdBytes);
 return true;
}

TriggerResult GCRuntime::checkHeapThreshold(
   Zone* zone, const HeapSize& heapSize, const HeapThreshold& heapThreshold) {
 MOZ_ASSERT_IF(heapThreshold.hasSliceThreshold(), zone->wasGCStarted());

 size_t usedBytes = heapSize.bytes();
 size_t thresholdBytes = heapThreshold.hasSliceThreshold()
                             ? heapThreshold.sliceBytes()
                             : heapThreshold.startBytes();

 // The incremental limit will be checked if we trigger a GC slice.
 MOZ_ASSERT(thresholdBytes <= heapThreshold.incrementalLimitBytes());

 return TriggerResult{usedBytes >= thresholdBytes, usedBytes, thresholdBytes};
}

bool GCRuntime::triggerZoneGC(Zone* zone, JS::GCReason reason, size_t used,
                             size_t threshold) {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));

 /* GC is already running. */
 if (JS::RuntimeHeapIsBusy()) {
   return false;
 }

#ifdef JS_GC_ZEAL
 if (hasZealMode(ZealMode::Alloc)) {
   MOZ_RELEASE_ASSERT(triggerGC(reason));
   return true;
 }
#endif

 if (zone->isAtomsZone()) {
   stats().recordTrigger(used, threshold);
   MOZ_RELEASE_ASSERT(triggerGC(reason));
   return true;
 }

 stats().recordTrigger(used, threshold);
 zone->scheduleGC();
 requestMajorGC(reason);
 return true;
}

void GCRuntime::maybeGC() {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));

#ifdef JS_GC_ZEAL
 if (hasZealMode(ZealMode::Alloc) || hasZealMode(ZealMode::RootsChange)) {
   JS::PrepareForFullGC(rt->mainContextFromOwnThread());
   gc(JS::GCOptions::Normal, JS::GCReason::DEBUG_GC);
   return;
 }
#endif

 (void)gcIfRequestedImpl(/* eagerOk = */ true);
}

JS::GCReason GCRuntime::wantMajorGC(bool eagerOk) {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));

 if (majorGCRequested()) {
   return majorGCTriggerReason;
 }

 if (isIncrementalGCInProgress() || !eagerOk) {
   return JS::GCReason::NO_REASON;
 }

 JS::GCReason reason = JS::GCReason::NO_REASON;
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   if (checkEagerAllocTrigger(zone->gcHeapSize, zone->gcHeapThreshold) ||
       checkEagerAllocTrigger(zone->mallocHeapSize,
                              zone->mallocHeapThreshold)) {
     zone->scheduleGC();
     reason = JS::GCReason::EAGER_ALLOC_TRIGGER;
   }
 }

 return reason;
}

bool GCRuntime::checkEagerAllocTrigger(const HeapSize& size,
                                      const HeapThreshold& threshold) {
 size_t thresholdBytes =
     threshold.eagerAllocTrigger(schedulingState.inHighFrequencyGCMode());
 size_t usedBytes = size.bytes();
 if (usedBytes <= 1024 * 1024 || usedBytes < thresholdBytes) {
   return false;
 }

 stats().recordTrigger(usedBytes, thresholdBytes);
 return true;
}

bool GCRuntime::shouldDecommit() const {
 switch (gcOptions()) {
   case JS::GCOptions::Normal:
     // If we are allocating heavily enough to trigger "high frequency" GC then
     // skip decommit so that we do not compete with the mutator.
     return !schedulingState.inHighFrequencyGCMode();
   case JS::GCOptions::Shrink:
     // If we're doing a shrinking GC we always decommit to release as much
     // memory as possible.
     return true;
   case JS::GCOptions::Shutdown:
     // There's no point decommitting as we are about to free everything.
     return false;
 }

 MOZ_CRASH("Unexpected GCOptions value");
}

void GCRuntime::startDecommit() {
 gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::DECOMMIT);

#ifdef DEBUG
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));
 MOZ_ASSERT(decommitTask.isIdle());

 {
   AutoLockGC lock(this);
   MOZ_ASSERT(fullChunks(lock).verify());
   MOZ_ASSERT(availableChunks(lock).verify());
   MOZ_ASSERT(emptyChunks(lock).verify());

   // Verify that all entries in the empty chunks pool are unused.
   for (ChunkPool::Iter chunk(emptyChunks(lock)); !chunk.done();
        chunk.next()) {
     MOZ_ASSERT(chunk->isEmpty());
   }
 }
#endif

 if (!shouldDecommit()) {
   return;
 }

 {
   AutoLockGC lock(this);
   if (availableChunks(lock).empty() && !tooManyEmptyChunks(lock) &&
       emptyChunks(lock).empty()) {
     return;  // Nothing to do.
   }
 }

#ifdef DEBUG
 {
   AutoLockHelperThreadState lock;
   MOZ_ASSERT(!requestSliceAfterBackgroundTask);
 }
#endif

 if (useBackgroundThreads) {
   decommitTask.start();
   return;
 }

 decommitTask.runFromMainThread();
}

BackgroundDecommitTask::BackgroundDecommitTask(GCRuntime* gc)
   : GCParallelTask(gc, gcstats::PhaseKind::DECOMMIT) {}

void js::gc::BackgroundDecommitTask::run(AutoLockHelperThreadState& lock) {
 {
   AutoUnlockHelperThreadState unlock(lock);

   ChunkPool emptyChunksToFree;
   {
     AutoLockGC gcLock(gc);
     emptyChunksToFree = gc->expireEmptyChunkPool(gcLock);
   }

   FreeChunkPool(emptyChunksToFree);

   {
     AutoLockGC gcLock(gc);

     // To help minimize the total number of chunks needed over time, sort the
     // available chunks list so that we allocate into more-used chunks first.
     gc->availableChunks(gcLock).sort();

     if (DecommitEnabled()) {
       gc->decommitEmptyChunks(cancel_, gcLock);
       gc->decommitFreeArenas(cancel_, gcLock);
     }
   }
 }

 gc->maybeRequestGCAfterBackgroundTask(lock);
}

static inline bool CanDecommitWholeChunk(ArenaChunk* chunk) {
 return chunk->isEmpty() && chunk->info.numArenasFreeCommitted != 0;
}

// Called from a background thread to decommit free arenas. Releases the GC
// lock.
void GCRuntime::decommitEmptyChunks(const bool& cancel, AutoLockGC& lock) {
 Vector<ArenaChunk*, 0, SystemAllocPolicy> chunksToDecommit;
 for (ChunkPool::Iter chunk(emptyChunks(lock)); !chunk.done(); chunk.next()) {
   if (CanDecommitWholeChunk(chunk) && !chunksToDecommit.append(chunk)) {
     onOutOfMallocMemory(lock);
     return;
   }
 }

 for (ArenaChunk* chunk : chunksToDecommit) {
   if (cancel) {
     break;
   }

   // Check whether something used the chunk while lock was released.
   if (!CanDecommitWholeChunk(chunk)) {
     continue;
   }

   // Temporarily remove the chunk while decommitting its memory so that the
   // mutator doesn't start allocating from it when we drop the lock.
   emptyChunks(lock).remove(chunk);

   {
     AutoUnlockGC unlock(lock);
     chunk->decommitAllArenas();
     MOZ_ASSERT(chunk->info.numArenasFreeCommitted == 0);
   }

   emptyChunks(lock).push(chunk);
 }
}

// Called from a background thread to decommit free arenas. Releases the GC
// lock.
void GCRuntime::decommitFreeArenas(const bool& cancel, AutoLockGC& lock) {
 MOZ_ASSERT(DecommitEnabled());

 // Since we release the GC lock while doing the decommit syscall below,
 // it is dangerous to iterate the available list directly, as the active
 // thread could modify it concurrently. Instead, we build and pass an
 // explicit Vector containing the Chunks we want to visit.
 Vector<ArenaChunk*, 0, SystemAllocPolicy> chunksToDecommit;
 for (ChunkPool::Iter chunk(availableChunks(lock)); !chunk.done();
      chunk.next()) {
   if (chunk->info.numArenasFreeCommitted != 0 &&
       !chunksToDecommit.append(chunk)) {
     onOutOfMallocMemory(lock);
     return;
   }
 }

 for (ArenaChunk* chunk : chunksToDecommit) {
   MOZ_ASSERT(chunk->getKind() == ChunkKind::TenuredArenas);
   MOZ_ASSERT(!chunk->isEmpty());

   if (chunk->info.isCurrentChunk) {
     // Chunk has become current chunk while lock was released.
     continue;
   }

   if (!chunk->hasAvailableArenas()) {
     // Chunk has become full while lock was released.
     continue;
   }

   MOZ_ASSERT(availableChunks(lock).contains(chunk));
   chunk->decommitFreeArenas(this, cancel, lock);
 }
}

// Do all possible decommit immediately from the current thread without
// releasing the GC lock or allocating any memory.
void GCRuntime::decommitFreeArenasWithoutUnlocking(const AutoLockGC& lock) {
 MOZ_ASSERT(DecommitEnabled());
 for (ChunkPool::Iter chunk(availableChunks(lock)); !chunk.done();
      chunk.next()) {
   chunk->decommitFreeArenasWithoutUnlocking(lock);
 }
 MOZ_ASSERT(availableChunks(lock).verify());
}

void GCRuntime::maybeRequestGCAfterBackgroundTask(
   const AutoLockHelperThreadState& lock) {
 if (requestSliceAfterBackgroundTask) {
   // Request a slice. The main thread may continue the collection immediately
   // or it may yield to let the embedding schedule a slice.
   requestSliceAfterBackgroundTask = false;
   requestMajorGC(JS::GCReason::BG_TASK_FINISHED);
 }
}

void GCRuntime::cancelRequestedGCAfterBackgroundTask() {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt));

#ifdef DEBUG
 {
   AutoLockHelperThreadState lock;
   MOZ_ASSERT(!requestSliceAfterBackgroundTask);
 }
#endif

 majorGCTriggerReason.compareExchange(JS::GCReason::BG_TASK_FINISHED,
                                      JS::GCReason::NO_REASON);
}

bool GCRuntime::isWaitingOnBackgroundTask() const {
 AutoLockHelperThreadState lock;
 return requestSliceAfterBackgroundTask;
}

void GCRuntime::queueUnusedLifoBlocksForFree(LifoAlloc* lifo) {
 MOZ_ASSERT(JS::RuntimeHeapIsBusy());
 AutoLockHelperThreadState lock;
 lifoBlocksToFree.ref().transferUnusedFrom(lifo);
}

void GCRuntime::queueAllLifoBlocksForFreeAfterMinorGC(LifoAlloc* lifo) {
 lifoBlocksToFreeAfterFullMinorGC.ref().transferFrom(lifo);
}

void GCRuntime::queueBuffersForFreeAfterMinorGC(
   Nursery::BufferSet& buffers, Nursery::StringBufferVector& stringBuffers) {
 AutoLockHelperThreadState lock;

 if (!buffersToFreeAfterMinorGC.ref().empty() ||
     !stringBuffersToReleaseAfterMinorGC.ref().empty()) {
   // In the rare case that this hasn't processed the buffers from a previous
   // minor GC we have to wait here.
   MOZ_ASSERT(!freeTask.isIdle(lock));
   freeTask.joinWithLockHeld(lock);
 }

 MOZ_ASSERT(buffersToFreeAfterMinorGC.ref().empty());
 std::swap(buffersToFreeAfterMinorGC.ref(), buffers);

 MOZ_ASSERT(stringBuffersToReleaseAfterMinorGC.ref().empty());
 std::swap(stringBuffersToReleaseAfterMinorGC.ref(), stringBuffers);
}

void Realm::destroy(JS::GCContext* gcx) {
 JSRuntime* rt = gcx->runtime();
 if (auto callback = rt->destroyRealmCallback) {
   callback(gcx, this);
 }
 if (principals()) {
   JS_DropPrincipals(rt->mainContextFromOwnThread(), principals());
 }
 // Bug 1560019: Malloc memory associated with a zone but not with a specific
 // GC thing is not currently tracked.
 gcx->deleteUntracked(this);
}

void Compartment::destroy(JS::GCContext* gcx) {
 JSRuntime* rt = gcx->runtime();
 if (auto callback = rt->destroyCompartmentCallback) {
   callback(gcx, this);
 }
 // Bug 1560019: Malloc memory associated with a zone but not with a specific
 // GC thing is not currently tracked.
 gcx->deleteUntracked(this);
 rt->gc.stats().sweptCompartment();
}

void Zone::destroy(JS::GCContext* gcx) {
 MOZ_ASSERT(compartments().empty());
 JSRuntime* rt = gcx->runtime();
 if (auto callback = rt->destroyZoneCallback) {
   callback(gcx, this);
 }
 // Bug 1560019: Malloc memory associated with a zone but not with a specific
 // GC thing is not currently tracked.
 gcx->deleteUntracked(this);
 gcx->runtime()->gc.stats().sweptZone();
}

/*
* It's simpler if we preserve the invariant that every zone (except atoms
* zones) has at least one compartment, and every compartment has at least one
* realm. If we know we're deleting the entire zone, then sweepCompartments is
* allowed to delete all compartments. In this case, |keepAtleastOne| is false.
* If any cells remain alive in the zone, set |keepAtleastOne| true to prohibit
* sweepCompartments from deleting every compartment. Instead, it preserves an
* arbitrary compartment in the zone.
*/
void Zone::sweepCompartments(JS::GCContext* gcx, bool keepAtleastOne,
                            bool destroyingRuntime) {
 MOZ_ASSERT_IF(!isAtomsZone(), !compartments().empty());
 MOZ_ASSERT_IF(destroyingRuntime, !keepAtleastOne);

 Compartment** read = compartments().begin();
 Compartment** end = compartments().end();
 Compartment** write = read;
 while (read < end) {
   Compartment* comp = *read++;

   /*
    * Don't delete the last compartment and realm if keepAtleastOne is
    * still true, meaning all the other compartments were deleted.
    */
   bool keepAtleastOneRealm = read == end && keepAtleastOne;
   comp->sweepRealms(gcx, keepAtleastOneRealm, destroyingRuntime);

   if (!comp->realms().empty()) {
     *write++ = comp;
     keepAtleastOne = false;
   } else {
     comp->destroy(gcx);
   }
 }
 compartments().shrinkTo(write - compartments().begin());
 MOZ_ASSERT_IF(keepAtleastOne, !compartments().empty());
 MOZ_ASSERT_IF(destroyingRuntime, compartments().empty());
}

void Compartment::sweepRealms(JS::GCContext* gcx, bool keepAtleastOne,
                             bool destroyingRuntime) {
 MOZ_ASSERT(!realms().empty());
 MOZ_ASSERT_IF(destroyingRuntime, !keepAtleastOne);

 Realm** read = realms().begin();
 Realm** end = realms().end();
 Realm** write = read;
 while (read < end) {
   Realm* realm = *read++;

   /*
    * Don't delete the last realm if keepAtleastOne is still true, meaning
    * all the other realms were deleted.
    */
   bool dontDelete = read == end && keepAtleastOne;
   if ((realm->marked() || dontDelete) && !destroyingRuntime) {
     *write++ = realm;
     keepAtleastOne = false;
   } else {
     realm->destroy(gcx);
   }
 }
 realms().shrinkTo(write - realms().begin());
 MOZ_ASSERT_IF(keepAtleastOne, !realms().empty());
 MOZ_ASSERT_IF(destroyingRuntime, realms().empty());
}

void GCRuntime::sweepZones(JS::GCContext* gcx, bool destroyingRuntime) {
 MOZ_ASSERT_IF(destroyingRuntime, numActiveZoneIters == 0);
 MOZ_ASSERT(foregroundFinalizedArenas.ref().isNothing());

 if (numActiveZoneIters) {
   return;
 }

 assertBackgroundSweepingFinished();

 // Host destroy callbacks can access the store buffer, e.g. when resizing hash
 // tables containing nursery pointers.
 AutoLockStoreBuffer lock(rt);

 // Sweep zones following the atoms zone.
 MOZ_ASSERT(zones()[0]->isAtomsZone());
 Zone** read = zones().begin() + 1;
 Zone** end = zones().end();
 Zone** write = read;

 while (read < end) {
   Zone* zone = *read++;

   if (zone->wasGCStarted()) {
     MOZ_ASSERT(!zone->isQueuedForBackgroundSweep());
     AutoSetThreadIsSweeping threadIsSweeping(zone);
     const bool zoneIsDead = zone->arenas.arenaListsAreEmpty() &&
                             zone->bufferAllocator.isEmpty() &&
                             !zone->hasMarkedRealms();
     MOZ_ASSERT_IF(destroyingRuntime, zoneIsDead);
     if (zoneIsDead) {
       zone->arenas.checkEmptyFreeLists();
       zone->sweepCompartments(gcx, false, destroyingRuntime);
       MOZ_ASSERT(zone->compartments().empty());
       zone->destroy(gcx);
       continue;
     }
     zone->sweepCompartments(gcx, true, destroyingRuntime);
   }
   *write++ = zone;
 }
 zones().shrinkTo(write - zones().begin());
}

void ArenaLists::checkEmptyArenaList(AllocKind kind) {
 MOZ_ASSERT(arenaList(kind).isEmpty());
}

void GCRuntime::purgeRuntimeForMinorGC() {
 for (ZonesIter zone(this, SkipAtoms); !zone.done(); zone.next()) {
   zone->externalStringCache().purge();
   zone->functionToStringCache().purge();
 }
}

void GCRuntime::purgeRuntime() {
 gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::PURGE);

 for (GCRealmsIter realm(rt); !realm.done(); realm.next()) {
   realm->purge();
 }

 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   zone->purgeAtomCache();
   zone->externalStringCache().purge();
   zone->functionToStringCache().purge();
   zone->boundPrefixCache().clearAndCompact();
   zone->shapeZone().purgeShapeCaches(rt->gcContext());
 }

 JSContext* cx = rt->mainContextFromOwnThread();
 queueUnusedLifoBlocksForFree(&cx->tempLifoAlloc());
 cx->interpreterStack().purge(rt);
 cx->frontendCollectionPool().purge();

 rt->caches().purge();

 if (rt->isMainRuntime()) {
   SharedImmutableStringsCache::getSingleton().purge();
 }

 MOZ_ASSERT(marker().unmarkGrayStack.empty());
 marker().unmarkGrayStack.clearAndFree();
}

bool GCRuntime::shouldPreserveJITCode(Realm* realm,
                                     const TimeStamp& currentTime,
                                     JS::GCReason reason,
                                     bool canAllocateMoreCode,
                                     bool isActiveCompartment) {
 // During shutdown, we must clean everything up, for the sake of leak
 // detection.
 if (isShutdownGC()) {
   return false;
 }

 // A shrinking GC is trying to clear out as much as it can, and so we should
 // not preserve JIT code here!
 if (isShrinkingGC()) {
   return false;
 }

 // We are close to our allocatable code limit, so let's try to clean it out.
 if (!canAllocateMoreCode) {
   return false;
 }

 // The topmost frame of JIT code is in this compartment, and so we should
 // try to preserve this zone's code.
 if (isActiveCompartment) {
   return true;
 }

 // The gcPreserveJitCode testing function was used.
 if (alwaysPreserveCode) {
   return true;
 }

 // This realm explicitly requested we try to preserve its JIT code.
 if (realm->preserveJitCode()) {
   return true;
 }

 // If we're currently animating, and we've already discarded code recently
 // we can preserve jit code; however we shouldn't hold onto JIT code forever
 // during animation.
 if (IsCurrentlyAnimating(realm->lastAnimationTime, currentTime) &&
     DiscardedCodeRecently(realm->zone(), currentTime)) {
   return true;
 }

 // GC Invoked via a testing function.
 if (reason == JS::GCReason::DEBUG_GC) {
   return true;
 }

 return false;
}

#ifdef DEBUG
class CompartmentCheckTracer final : public JS::CallbackTracer {
 void onChild(JS::GCCellPtr thing, const char* name) override;
 bool edgeIsInCrossCompartmentMap(JS::GCCellPtr dst);

public:
 explicit CompartmentCheckTracer(JSRuntime* rt)
     : JS::CallbackTracer(rt, JS::TracerKind::CompartmentCheck,
                          JS::WeakEdgeTraceAction::Skip) {}

 Cell* src = nullptr;
 JS::TraceKind srcKind = JS::TraceKind::Null;
 Zone* zone = nullptr;
 Compartment* compartment = nullptr;
};

static bool InCrossCompartmentMap(JSRuntime* rt, JSObject* src,
                                 JS::GCCellPtr dst) {
 // Cross compartment edges are either in the cross compartment map or in a
 // debugger weakmap.

 Compartment* srccomp = src->compartment();

 if (dst.is<JSObject>()) {
   if (ObjectWrapperMap::Ptr p = srccomp->lookupWrapper(&dst.as<JSObject>())) {
     if (*p->value().unsafeGet() == src) {
       return true;
     }
   }
 }

 if (DebugAPI::edgeIsInDebuggerWeakmap(rt, src, dst)) {
   return true;
 }

 return false;
}

void CompartmentCheckTracer::onChild(JS::GCCellPtr thing, const char* name) {
 Compartment* comp =
     MapGCThingTyped(thing, [](auto t) { return t->maybeCompartment(); });
 if (comp && compartment) {
   MOZ_ASSERT(comp == compartment || edgeIsInCrossCompartmentMap(thing));
 } else {
   TenuredCell* tenured = &thing.asCell()->asTenured();
   Zone* thingZone = tenured->zoneFromAnyThread();
   MOZ_ASSERT(thingZone == zone || thingZone->isAtomsZone());
 }
}

bool CompartmentCheckTracer::edgeIsInCrossCompartmentMap(JS::GCCellPtr dst) {
 return srcKind == JS::TraceKind::Object &&
        InCrossCompartmentMap(runtime(), static_cast<JSObject*>(src), dst);
}

void GCRuntime::checkForCompartmentMismatches() {
 JSContext* cx = rt->mainContextFromOwnThread();
 if (cx->disableStrictProxyCheckingCount) {
   return;
 }

 CompartmentCheckTracer trc(rt);
 AutoAssertEmptyNursery empty(cx);
 for (ZonesIter zone(this, SkipAtoms); !zone.done(); zone.next()) {
   trc.zone = zone;
   for (auto thingKind : AllAllocKinds()) {
     for (auto i = zone->cellIterUnsafe<TenuredCell>(thingKind, empty);
          !i.done(); i.next()) {
       trc.src = i.getCell();
       trc.srcKind = MapAllocToTraceKind(thingKind);
       trc.compartment = MapGCThingTyped(
           trc.src, trc.srcKind, [](auto t) { return t->maybeCompartment(); });
       JS::TraceChildren(&trc, JS::GCCellPtr(trc.src, trc.srcKind));
     }
   }
 }
}
#endif

static bool ShouldUseBackgroundThreads(bool isIncremental,
                                      JS::GCReason reason) {
 bool shouldUse = isIncremental && CanUseExtraThreads();
 MOZ_ASSERT_IF(reason == JS::GCReason::DESTROY_RUNTIME, !shouldUse);
 return shouldUse;
}

void GCRuntime::startCollection(JS::GCReason reason) {
 checkGCStateNotInUse();
 MOZ_ASSERT_IF(
     isShuttingDown(),
     isShutdownGC() ||
         reason == JS::GCReason::XPCONNECT_SHUTDOWN /* Bug 1650075 */);

 initialReason = reason;
 isCompacting = shouldCompact();
 rootsRemoved = false;
 sweepGroupIndex = 0;

#ifdef DEBUG
 if (isShutdownGC()) {
   hadShutdownGC = true;
 }

 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   zone->gcSweepGroupIndex = 0;
 }
#endif
}

static void RelazifyFunctions(Zone* zone, AllocKind kind) {
 MOZ_ASSERT(kind == AllocKind::FUNCTION ||
            kind == AllocKind::FUNCTION_EXTENDED);

 JSRuntime* rt = zone->runtimeFromMainThread();
 AutoAssertEmptyNursery empty(rt->mainContextFromOwnThread());

 for (auto i = zone->cellIterUnsafe<JSObject>(kind, empty); !i.done();
      i.next()) {
   JSFunction* fun = &i->as<JSFunction>();
   // When iterating over the GC-heap, we may encounter function objects that
   // are incomplete (missing a BaseScript when we expect one). We must check
   // for this case before we can call JSFunction::hasBytecode().
   if (fun->isIncomplete()) {
     continue;
   }
   if (fun->hasBytecode()) {
     fun->maybeRelazify(rt);
   }
 }
}

static bool ShouldCollectZone(Zone* zone, JS::GCReason reason) {
 // If we are repeating a GC because we noticed dead compartments haven't
 // been collected, then only collect zones containing those compartments.
 if (reason == JS::GCReason::COMPARTMENT_REVIVED) {
   for (CompartmentsInZoneIter comp(zone); !comp.done(); comp.next()) {
     if (comp->gcState.scheduledForDestruction) {
       return true;
     }
   }

   return false;
 }

 // Otherwise we only collect scheduled zones.
 return zone->isGCScheduled();
}

bool GCRuntime::prepareZonesForCollection(JS::GCReason reason,
                                         bool* isFullOut) {
#ifdef DEBUG
 /* Assert that zone state is as we expect */
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   MOZ_ASSERT(!zone->isCollecting());
   MOZ_ASSERT_IF(!zone->isAtomsZone(), !zone->compartments().empty());
   for (auto i : AllAllocKinds()) {
     MOZ_ASSERT(zone->arenas.collectingArenaList(i).isEmpty());
   }
 }
#endif

 *isFullOut = true;
 bool any = false;

 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   /* Set up which zones will be collected. */
   bool shouldCollect = ShouldCollectZone(zone, reason);
   if (shouldCollect) {
     any = true;
     zone->changeGCState(Zone::NoGC, Zone::Prepare);
   } else {
     *isFullOut = false;
   }

   zone->setWasCollected(shouldCollect);
 }

 /* Check that at least one zone is scheduled for collection. */
 return any;
}

// Update JIT Code state for GC: A few different actions are combined here to
// minimize the number of iterations over zones & scripts that required.
void GCRuntime::maybeDiscardJitCodeForGC() {
 size_t nurserySiteResetCount = 0;
 size_t pretenuredSiteResetCount = 0;

 js::CancelOffThreadCompile(rt, JS::Zone::Prepare);
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::MARK_DISCARD_CODE);

   // We may need to reset allocation sites and discard JIT code to recover if
   // we find object lifetimes have changed.
   PretenuringZone& pz = zone->pretenuring;
   bool resetNurserySites = pz.shouldResetNurseryAllocSites();
   bool resetPretenuredSites = pz.shouldResetPretenuredAllocSites();

   if (!zone->isPreservingCode()) {
     Zone::JitDiscardOptions options;
     options.discardJitScripts = true;
     options.resetNurseryAllocSites = resetNurserySites;
     options.resetPretenuredAllocSites = resetPretenuredSites;
     zone->forceDiscardJitCode(rt->gcContext(), options);
   } else if (resetNurserySites || resetPretenuredSites) {
     zone->resetAllocSitesAndInvalidate(resetNurserySites,
                                        resetPretenuredSites);
   }

   if (resetNurserySites) {
     nurserySiteResetCount++;
   }
   if (resetPretenuredSites) {
     pretenuredSiteResetCount++;
   }
 }

 if (nursery().reportPretenuring()) {
   if (nurserySiteResetCount) {
     fprintf(
         stderr,
         "GC reset nursery alloc sites and invalidated code in %zu zones\n",
         nurserySiteResetCount);
   }
   if (pretenuredSiteResetCount) {
     fprintf(
         stderr,
         "GC reset pretenured alloc sites and invalidated code in %zu zones\n",
         pretenuredSiteResetCount);
   }
 }
}

void GCRuntime::relazifyFunctionsForShrinkingGC() {
 gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::RELAZIFY_FUNCTIONS);
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   RelazifyFunctions(zone, AllocKind::FUNCTION);
   RelazifyFunctions(zone, AllocKind::FUNCTION_EXTENDED);
 }
}

void GCRuntime::purgePropMapTablesForShrinkingGC() {
 gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::PURGE_PROP_MAP_TABLES);
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   if (!canRelocateZone(zone) || zone->keepPropMapTables()) {
     continue;
   }

   // Note: CompactPropMaps never have a table.
   for (auto map = zone->cellIterUnsafe<NormalPropMap>(); !map.done();
        map.next()) {
     if (map->asLinked()->hasTable()) {
       map->asLinked()->purgeTable(rt->gcContext());
     }
   }
   for (auto map = zone->cellIterUnsafe<DictionaryPropMap>(); !map.done();
        map.next()) {
     if (map->asLinked()->hasTable()) {
       map->asLinked()->purgeTable(rt->gcContext());
     }
   }
 }
}

// The debugger keeps track of the URLs for the sources of each realm's scripts.
// These URLs are purged on shrinking GCs.
void GCRuntime::purgeSourceURLsForShrinkingGC() {
 gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::PURGE_SOURCE_URLS);
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   // URLs are not tracked for realms in the system zone.
   if (!canRelocateZone(zone) || zone->isSystemZone()) {
     continue;
   }
   for (CompartmentsInZoneIter comp(zone); !comp.done(); comp.next()) {
     for (RealmsInCompartmentIter realm(comp); !realm.done(); realm.next()) {
       GlobalObject* global = realm.get()->unsafeUnbarrieredMaybeGlobal();
       if (global) {
         global->clearSourceURLSHolder();
       }
     }
   }
 }
}

void GCRuntime::purgePendingWrapperPreservationBuffersForShrinkingGC() {
 gcstats::AutoPhase ap(stats(),
                       gcstats::PhaseKind::PURGE_WRAPPER_PRESERVATION);
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   zone->purgePendingWrapperPreservationBuffer();
 }
}

void GCRuntime::unmarkWeakMaps() {
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   /* Unmark all weak maps in the zones being collected. */
   WeakMapBase::unmarkZone(zone);
 }
}

bool GCRuntime::beginPreparePhase(JS::GCReason reason, AutoGCSession& session) {
 gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::PREPARE);

 if (!prepareZonesForCollection(reason, &isFull.ref())) {
   return false;
 }

 /*
  * Start a parallel task to clear all mark state for the zones we are
  * collecting. This is linear in the size of the heap we are collecting and so
  * can be slow. This usually happens concurrently with the mutator and GC
  * proper does not start until this is complete.
  */
 unmarkTask.initZones();
 if (useBackgroundThreads) {
   unmarkTask.start();
 } else {
   unmarkTask.runFromMainThread();
 }

 /*
  * Process any queued source compressions during the start of a major
  * GC.
  *
  * Bug 1650075: When we start passing GCOptions::Shutdown for
  * GCReason::XPCONNECT_SHUTDOWN GCs we can remove the extra check.
  */
 if (!isShutdownGC() && reason != JS::GCReason::XPCONNECT_SHUTDOWN) {
   StartOffThreadCompressionsOnGC(rt, isShrinkingGC());
 }

 return true;
}

BackgroundUnmarkTask::BackgroundUnmarkTask(GCRuntime* gc)
   : GCParallelTask(gc, gcstats::PhaseKind::UNMARK) {}

void BackgroundUnmarkTask::initZones() {
 MOZ_ASSERT(isIdle());
 MOZ_ASSERT(zones.empty());
 MOZ_ASSERT(!isCancelled());

 // We can't safely iterate the zones vector from another thread so we copy the
 // zones to be collected into another vector.
 AutoEnterOOMUnsafeRegion oomUnsafe;
 for (GCZonesIter zone(gc); !zone.done(); zone.next()) {
   if (!zones.append(zone.get())) {
     oomUnsafe.crash("BackgroundUnmarkTask::initZones");
   }

   zone->arenas.clearFreeLists();
   zone->arenas.moveArenasToCollectingLists();
 }
}

void BackgroundUnmarkTask::run(AutoLockHelperThreadState& lock) {
 {
   AutoUnlockHelperThreadState unlock(lock);
   unmark();
   zones.clear();
 }

 gc->maybeRequestGCAfterBackgroundTask(lock);
}

void BackgroundUnmarkTask::unmark() {
 for (Zone* zone : zones) {
   for (auto kind : AllAllocKinds()) {
     ArenaList& arenas = zone->arenas.collectingArenaList(kind);
     for (auto arena = arenas.iter(); !arena.done(); arena.next()) {
       arena->unmarkAll();
       if (isCancelled()) {
         return;
       }
     }
   }
 }
}

void GCRuntime::endPreparePhase(JS::GCReason reason) {
 MOZ_ASSERT(unmarkTask.isIdle());

 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   zone->setPreservingCode(false);
 }

 // Discard JIT code more aggressively if the process is approaching its
 // executable code limit.
 bool canAllocateMoreCode = jit::CanLikelyAllocateMoreExecutableMemory();
 auto currentTime = TimeStamp::Now();

 Compartment* activeCompartment = nullptr;
 jit::JitActivationIterator activation(rt->mainContextFromOwnThread());
 if (!activation.done()) {
   activeCompartment = activation->compartment();
 }

 for (CompartmentsIter c(rt); !c.done(); c.next()) {
   c->gcState.scheduledForDestruction = false;
   c->gcState.maybeAlive = false;
   c->gcState.hasEnteredRealm = false;
   if (c->invisibleToDebugger()) {
     c->gcState.maybeAlive = true;  // Presumed to be a system compartment.
   }
   bool isActiveCompartment = c == activeCompartment;
   for (RealmsInCompartmentIter r(c); !r.done(); r.next()) {
     if (r->shouldTraceGlobal() || !r->zone()->isGCScheduled()) {
       c->gcState.maybeAlive = true;
     }
     if (shouldPreserveJITCode(r, currentTime, reason, canAllocateMoreCode,
                               isActiveCompartment)) {
       r->zone()->setPreservingCode(true);
     }
     if (r->hasBeenEnteredIgnoringJit()) {
       c->gcState.hasEnteredRealm = true;
     }
   }
 }

 /*
  * Perform remaining preparation work that must take place in the first true
  * GC slice.
  */

 {
   gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::PREPARE);

   AutoLockHelperThreadState helperLock;

   /* Clear mark state for WeakMaps in parallel with other work. */
   AutoRunParallelTask unmarkWeakMaps(this, &GCRuntime::unmarkWeakMaps,
                                      gcstats::PhaseKind::UNMARK_WEAKMAPS,
                                      GCUse::Unspecified, helperLock);

   AutoUnlockHelperThreadState unlock(helperLock);

   maybeDiscardJitCodeForGC();

   /*
    * We must purge the runtime at the beginning of an incremental GC. The
    * danger if we purge later is that the snapshot invariant of
    * incremental GC will be broken, as follows. If some object is
    * reachable only through some cache (say the dtoaCache) then it will
    * not be part of the snapshot.  If we purge after root marking, then
    * the mutator could obtain a pointer to the object and start using
    * it. This object might never be marked, so a GC hazard would exist.
    */
   purgeRuntime();
 }

 // This will start background free for lifo blocks queued by purgeRuntime,
 // even if there's nothing in the nursery. Record the number of the minor GC
 // so we can check whether we need to wait for it to finish or whether a
 // subsequent minor GC already did this.
 collectNurseryFromMajorGC(reason);
 initialMinorGCNumber = minorGCNumber;

 {
   gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::PREPARE);
   // Relazify functions after discarding JIT code (we can't relazify functions
   // with JIT code) and before the actual mark phase, so that the current GC
   // can collect the JSScripts we're unlinking here.  We do this only when
   // we're performing a shrinking GC, as too much relazification can cause
   // performance issues when we have to reparse the same functions over and
   // over.
   if (isShrinkingGC()) {
     relazifyFunctionsForShrinkingGC();
     purgePropMapTablesForShrinkingGC();
     purgeSourceURLsForShrinkingGC();
     {
       AutoGCSession commitSession(this, JS::HeapState::Idle);
       rt->commitPendingWrapperPreservations();
     }
     purgePendingWrapperPreservationBuffersForShrinkingGC();
   }

   if (isShutdownGC()) {
     /* Clear any engine roots that may hold external data live. */
     for (GCZonesIter zone(this); !zone.done(); zone.next()) {
       zone->clearRootsForShutdownGC();
     }

#ifdef DEBUG
     testMarkQueue.clear();
     queuePos = 0;
#endif
   }
 }

#ifdef DEBUG
 if (fullCompartmentChecks) {
   checkForCompartmentMismatches();
 }
#endif
}

AutoUpdateLiveCompartments::AutoUpdateLiveCompartments(GCRuntime* gc) : gc(gc) {
 for (GCCompartmentsIter c(gc->rt); !c.done(); c.next()) {
   c->gcState.hasMarkedCells = false;
 }
}

AutoUpdateLiveCompartments::~AutoUpdateLiveCompartments() {
 for (GCCompartmentsIter c(gc->rt); !c.done(); c.next()) {
   if (c->gcState.hasMarkedCells) {
     c->gcState.maybeAlive = true;
   }
 }
}

Zone::GCState Zone::initialMarkingState() const {
 if (isAtomsZone()) {
   // Don't delay gray marking in the atoms zone like we do in other zones.
   return MarkBlackAndGray;
 }

 return MarkBlackOnly;
}

static bool HasUncollectedNonAtomZones(GCRuntime* gc) {
 for (ZonesIter zone(gc, SkipAtoms); !zone.done(); zone.next()) {
   if (!zone->wasGCStarted()) {
     return true;
   }
 }
 return false;
}

void GCRuntime::beginMarkPhase(AutoGCSession& session) {
 /*
  * Mark phase.
  */
 gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::MARK);

 // This is the slice we actually start collecting. The number can be used to
 // check whether a major GC has started so we must not increment it until we
 // get here.
 incMajorGcNumber();

#ifdef DEBUG
 queuePos = 0;
 queueMarkColor.reset();
#endif

 {
   BufferAllocator::MaybeLock lock;
   for (GCZonesIter zone(this); !zone.done(); zone.next()) {
     MOZ_ASSERT(zone->cellsToAssertNotGray().empty());

     // In an incremental GC, clear the arena free lists to ensure that
     // subsequent allocations refill them and end up marking new cells black.
     // See arenaAllocatedDuringGC().
     zone->arenas.clearFreeLists();

#ifdef JS_GC_ZEAL
     if (hasZealMode(ZealMode::YieldBeforeRootMarking)) {
       for (auto kind : AllAllocKinds()) {
         for (ArenaIter arena(zone, kind); !arena.done(); arena.next()) {
           arena->checkNoMarkedCells();
         }
       }
     }
#endif

     // Incremental marking barriers are enabled at this point.
     zone->changeGCState(Zone::Prepare, zone->initialMarkingState());

     // Merge arenas allocated during the prepare phase, then move all arenas
     // to the collecting arena lists.
     zone->arenas.mergeArenasFromCollectingLists();
     zone->arenas.moveArenasToCollectingLists();

     // Prepare sized allocator for major GC.
     zone->bufferAllocator.startMajorCollection(lock);

     for (RealmsInZoneIter realm(zone); !realm.done(); realm.next()) {
       realm->clearAllocatedDuringGC();
     }
   }
 }

 updateSchedulingStateOnGCStart();
 stats().measureInitialHeapSizes();

 useParallelMarking = SingleThreadedMarking;
 if (canMarkInParallel() && initParallelMarking()) {
   useParallelMarking = AllowParallelMarking;
 }

 MOZ_ASSERT(!hasDelayedMarking());
 for (auto& marker : markers) {
   marker->start();
 }

 if (rt->isBeingDestroyed()) {
   checkNoRuntimeRoots(session);
 } else {
   AutoUpdateLiveCompartments updateLive(this);
#ifdef DEBUG
   AutoSetThreadIsMarking threadIsMarking;
#endif  // DEBUG

   marker().setRootMarkingMode(true);
   traceRuntimeForMajorGC(marker().tracer(), session);
   marker().setRootMarkingMode(false);

   if (atomsZone()->wasGCStarted() && HasUncollectedNonAtomZones(this)) {
     atomsUsedByUncollectedZones =
         atomMarking.getOrMarkAtomsUsedByUncollectedZones(this);
   }
 }
}

void GCRuntime::findDeadCompartments() {
 gcstats::AutoPhase ap1(stats(), gcstats::PhaseKind::FIND_DEAD_COMPARTMENTS);

 /*
  * This code ensures that if a compartment is "dead", then it will be
  * collected in this GC. A compartment is considered dead if its maybeAlive
  * flag is false. The maybeAlive flag is set if:
  *
  *   (1) the compartment has been entered (set in beginMarkPhase() above)
  *   (2) the compartment's zone is not being collected (set in
  *       endPreparePhase() above)
  *   (3) an object in the compartment was marked during root marking, either
  *       as a black root or a gray root. This is arranged by
  *       SetCompartmentHasMarkedCells and AutoUpdateLiveCompartments.
  *   (4) the compartment has incoming cross-compartment edges from another
  *       compartment that has maybeAlive set (set by this method).
  *   (5) the compartment has the invisibleToDebugger flag set, as it is
  *       presumed to be a system compartment (set in endPreparePhase() above)
  *
  * If the maybeAlive is false, then we set the scheduledForDestruction flag.
  * At the end of the GC, we look for compartments where
  * scheduledForDestruction is true. These are compartments that were somehow
  * "revived" during the incremental GC. If any are found, we do a special,
  * non-incremental GC of those compartments to try to collect them.
  *
  * Compartments can be revived for a variety of reasons, including:
  *
  *   (1) A dead reflector can be revived by DOM code that still refers to the
  *       underlying DOM node (see bug 811587).
  *   (2) JS_TransplantObject iterates over all compartments, live or dead, and
  *       operates on their objects. This can trigger read barriers and mark
  *       unreachable objects. See bug 803376 for details on this problem. To
  *       avoid the problem, we try to avoid allocation and read barriers
  *       during JS_TransplantObject and the like.
  *   (3) Read barriers. A compartment may only have weak roots and reading one
  *       of these will cause the compartment to stay alive even though the GC
  *       thought it should die. An example of this is Gecko's unprivileged
  *       junk scope, which is handled by ignoring system compartments (see bug
  *       1868437).
  */

 // Propagate the maybeAlive flag via cross-compartment edges.

 Vector<Compartment*, 0, js::SystemAllocPolicy> workList;

 for (CompartmentsIter comp(rt); !comp.done(); comp.next()) {
   if (comp->gcState.maybeAlive) {
     if (!workList.append(comp)) {
       return;
     }
   }
 }

 while (!workList.empty()) {
   Compartment* comp = workList.popCopy();
   for (Compartment::WrappedObjectCompartmentEnum e(comp); !e.empty();
        e.popFront()) {
     Compartment* dest = e.front();
     if (!dest->gcState.maybeAlive) {
       dest->gcState.maybeAlive = true;
       if (!workList.append(dest)) {
         return;
       }
     }
   }
 }

 // Set scheduledForDestruction based on maybeAlive.

 for (GCCompartmentsIter comp(rt); !comp.done(); comp.next()) {
   MOZ_ASSERT(!comp->gcState.scheduledForDestruction);
   if (!comp->gcState.maybeAlive) {
     comp->gcState.scheduledForDestruction = true;
   }
 }
}

void GCRuntime::updateSchedulingStateOnGCStart() {
 heapSize.updateOnGCStart();

 // Update memory counters for the zones we are collecting.
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   zone->updateSchedulingStateOnGCStart();
 }
}

inline bool GCRuntime::canMarkInParallel() const {
 MOZ_ASSERT(state() >= gc::State::MarkRoots);

#if defined(DEBUG) || defined(JS_OOM_BREAKPOINT)
 // OOM testing limits the engine to using a single helper thread.
 if (oom::simulator.targetThread() == THREAD_TYPE_GCPARALLEL) {
   return false;
 }
#endif

 return markers.length() > 1 && stats().initialCollectedBytes() >=
                                    tunables.parallelMarkingThresholdBytes();
}

bool GCRuntime::initParallelMarking() {
 // This is called at the start of collection.

 MOZ_ASSERT(canMarkInParallel());

 // Reserve/release helper threads for worker runtimes. These are released at
 // the end of sweeping. If there are not enough helper threads because
 // other runtimes are marking in parallel then parallel marking will not be
 // used.
 if (!rt->isMainRuntime() && !reserveMarkingThreads(markers.length())) {
   return false;
 }

 // Allocate stack for parallel markers. The first marker always has stack
 // allocated. Other markers have their stack freed in
 // GCRuntime::finishCollection.
 for (size_t i = 1; i < markers.length(); i++) {
   if (!markers[i]->initStack()) {
     return false;
   }
 }

 return true;
}

IncrementalProgress GCRuntime::markUntilBudgetExhausted(
   SliceBudget& sliceBudget, ParallelMarking allowParallelMarking,
   ShouldReportMarkTime reportTime) {
 // Run a marking slice and return whether the stack is now empty.

 AutoMajorGCProfilerEntry s(this);

 if (initialState != State::Mark) {
   sliceBudget.forceCheck();
   if (sliceBudget.isOverBudget()) {
     return NotFinished;
   }
 }

#ifdef DEBUG
 AutoSetThreadIsMarking threadIsMarking;
#endif  // DEBUG

 if (processTestMarkQueue() == QueueYielded) {
   return NotFinished;
 }

 if (allowParallelMarking) {
   MOZ_ASSERT(canMarkInParallel());
   MOZ_ASSERT(parallelMarkingEnabled);
   MOZ_ASSERT(reportTime);
   MOZ_ASSERT(!isBackgroundMarking());

   if (!ParallelMarker::mark(this, sliceBudget)) {
     return NotFinished;
   }

   assertNoMarkingWork();
   return Finished;
 }

 return marker().markUntilBudgetExhausted(sliceBudget, reportTime)
            ? Finished
            : NotFinished;
}

void GCRuntime::drainMarkStack() {
 auto unlimited = SliceBudget::unlimited();
 MOZ_RELEASE_ASSERT(marker().markUntilBudgetExhausted(unlimited));
}

#ifdef DEBUG

const GCVector<HeapPtr<JS::Value>, 0, SystemAllocPolicy>&
GCRuntime::getTestMarkQueue() const {
 return testMarkQueue.get();
}

bool GCRuntime::appendTestMarkQueue(const JS::Value& value) {
 return testMarkQueue.append(value);
}

void GCRuntime::clearTestMarkQueue() {
 testMarkQueue.clear();
 queuePos = 0;
}

size_t GCRuntime::testMarkQueuePos() const { return queuePos; }

size_t GCRuntime::testMarkQueueRemaining() const {
 MOZ_ASSERT(queuePos <= testMarkQueue.length());
 return testMarkQueue.length() - queuePos;
}

#endif

GCRuntime::MarkQueueProgress GCRuntime::processTestMarkQueue() {
#ifdef DEBUG
 if (testMarkQueue.empty()) {
   return QueueComplete;
 }

 if (queueMarkColor == mozilla::Some(MarkColor::Gray) &&
     state() != State::Sweep) {
   return QueueSuspended;
 }

 // If the queue wants to be gray marking, but we've pushed a black object
 // since set-color-gray was processed, then we can't switch to gray and must
 // again wait until gray marking is possible.
 //
 // Remove this code if the restriction against marking gray during black is
 // relaxed.
 if (queueMarkColor == mozilla::Some(MarkColor::Gray) &&
     marker().hasBlackEntries()) {
   return QueueSuspended;
 }

 // If the queue wants to be marking a particular color, switch to that color.
 // In any case, restore the mark color to whatever it was when we entered
 // this function.
 bool willRevertToGray = marker().markColor() == MarkColor::Gray;
 AutoSetMarkColor autoRevertColor(
     marker(), queueMarkColor.valueOr(marker().markColor()));

 // Process the mark queue by taking each object in turn, pushing it onto the
 // mark stack, and processing just the top element with processMarkStackTop
 // without recursing into reachable objects.
 while (queuePos < testMarkQueue.length()) {
   Value val = testMarkQueue[queuePos++].get();
   if (val.isObject()) {
     JSObject* obj = &val.toObject();
     JS::Zone* zone = obj->zone();
     if (!zone->isGCMarking() || obj->isMarkedAtLeast(marker().markColor())) {
       continue;
     }

     // If we have started sweeping, obey sweep group ordering. But note that
     // we will first be called during the initial sweep slice, when the sweep
     // group indexes have not yet been computed. In that case, we can mark
     // freely.
     if (state() == State::Sweep && initialState != State::Sweep) {
       if (zone->gcSweepGroupIndex < getCurrentSweepGroupIndex()) {
         // Too late. This must have been added after we started collecting,
         // and we've already processed its sweep group. Skip it.
         continue;
       }
       if (zone->gcSweepGroupIndex > getCurrentSweepGroupIndex()) {
         // Not ready yet. Wait until we reach the object's sweep group.
         queuePos--;
         return QueueSuspended;
       }
     }

     if (marker().markColor() == MarkColor::Gray &&
         zone->isGCMarkingBlackOnly()) {
       // Have not yet reached the point where we can mark this object, so
       // continue with the GC.
       queuePos--;
       return QueueSuspended;
     }

     if (marker().markColor() == MarkColor::Black && willRevertToGray) {
       // If we put any black objects on the stack, we wouldn't be able to
       // return to gray marking. So delay the marking until we're back to
       // black marking.
       queuePos--;
       return QueueSuspended;
     }

     // Mark the object.
     if (!marker().markOneObjectForTest(obj)) {
       // If we overflowed the stack here and delayed marking, then we won't be
       // testing what we think we're testing.
       MOZ_ASSERT(obj->asTenured().arena()->onDelayedMarkingList());
       printf_stderr(
           "Hit mark stack limit while marking test queue; test results may "
           "be invalid");
     }
   } else if (val.isString()) {
     JSLinearString* str = &val.toString()->asLinear();
     if (js::StringEqualsLiteral(str, "yield") && isIncrementalGc()) {
       return QueueYielded;
     }

     if (js::StringEqualsLiteral(str, "enter-weak-marking-mode") ||
         js::StringEqualsLiteral(str, "abort-weak-marking-mode")) {
       if (marker().isRegularMarking()) {
         // We can't enter weak marking mode at just any time, so instead
         // we'll stop processing the queue and continue on with the GC. Once
         // we enter weak marking mode, we can continue to the rest of the
         // queue. Note that we will also suspend for aborting, and then abort
         // the earliest following weak marking mode.
         queuePos--;
         return QueueSuspended;
       }
       if (js::StringEqualsLiteral(str, "abort-weak-marking-mode")) {
         marker().abortLinearWeakMarking();
       }
     } else if (js::StringEqualsLiteral(str, "drain")) {
       auto unlimited = SliceBudget::unlimited();
       MOZ_RELEASE_ASSERT(
           marker().markUntilBudgetExhausted(unlimited, DontReportMarkTime));
     } else if (js::StringEqualsLiteral(str, "set-color-gray")) {
       queueMarkColor = mozilla::Some(MarkColor::Gray);
       if (state() != State::Sweep || marker().hasBlackEntries()) {
         // Cannot mark gray yet, so continue with the GC.
         queuePos--;
         return QueueSuspended;
       }
       marker().setMarkColor(MarkColor::Gray);
     } else if (js::StringEqualsLiteral(str, "set-color-black")) {
       queueMarkColor = mozilla::Some(MarkColor::Black);
       marker().setMarkColor(MarkColor::Black);
     } else if (js::StringEqualsLiteral(str, "unset-color")) {
       queueMarkColor.reset();
     }
   }
 }

 // Once the queue is complete, do not force a mark color (since the next time
 // the queue is processed, it should not be forcing one.)
 queueMarkColor.reset();
#endif

 return QueueComplete;
}

static bool IsEmergencyGC(JS::GCReason reason) {
 return reason == JS::GCReason::LAST_DITCH ||
        reason == JS::GCReason::MEM_PRESSURE;
}

void GCRuntime::finishCollection(JS::GCReason reason) {
 assertBackgroundSweepingFinished();

 MOZ_ASSERT(!hasDelayedMarking());
 for (size_t i = 0; i < markers.length(); i++) {
   const auto& marker = markers[i];
   marker->stop();
   if (i == 0) {
     marker->resetStackCapacity();
   } else {
     marker->freeStack();
   }
 }

 maybeStopPretenuring();

 if (IsEmergencyGC(reason)) {
   waitBackgroundFreeEnd();
 }

 TimeStamp currentTime = TimeStamp::Now();

 updateSchedulingStateOnGCEnd(currentTime);

 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   zone->changeGCState(Zone::Finished, Zone::NoGC);
   zone->notifyObservingDebuggers();
   zone->gcNextGraphNode = nullptr;
   zone->gcNextGraphComponent = nullptr;
 }

 atomsUsedByUncollectedZones.ref().reset();

#ifdef JS_GC_ZEAL
 clearSelectedForMarking();
#endif

 lastGCEndTime_ = currentTime;

 checkGCStateNotInUse();
}

void GCRuntime::checkGCStateNotInUse() {
#ifdef DEBUG
 for (auto& marker : markers) {
   MOZ_ASSERT(!marker->isActive());
   MOZ_ASSERT(marker->isDrained());
 }
 MOZ_ASSERT(!hasDelayedMarking());
 MOZ_ASSERT(!lastMarkSlice);

 MOZ_ASSERT(!disableBarriersForSweeping);
 MOZ_ASSERT(foregroundFinalizedArenas.ref().isNothing());

 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   if (zone->wasCollected()) {
     zone->arenas.checkGCStateNotInUse();
   }
   MOZ_ASSERT(!zone->wasGCStarted());
   MOZ_ASSERT(!zone->needsIncrementalBarrier());
   MOZ_ASSERT(!zone->isOnList());
   MOZ_ASSERT(!zone->gcNextGraphNode);
   MOZ_ASSERT(!zone->gcNextGraphComponent);
   MOZ_ASSERT(zone->cellsToAssertNotGray().empty());
   zone->bufferAllocator.checkGCStateNotInUse();
 }

 MOZ_ASSERT(zonesToMaybeCompact.ref().isEmpty());

 MOZ_ASSERT(!atomsUsedByUncollectedZones.ref());

 AutoLockHelperThreadState lock;
 MOZ_ASSERT(!requestSliceAfterBackgroundTask);
 MOZ_ASSERT(unmarkTask.isIdle(lock));
 MOZ_ASSERT(markTask.isIdle(lock));
 MOZ_ASSERT(sweepTask.isIdle(lock));
 MOZ_ASSERT(decommitTask.isIdle(lock));
#endif
}

void GCRuntime::maybeStopPretenuring() {
 nursery().maybeStopPretenuring(this);

 size_t zonesWhereStringsEnabled = 0;
 size_t zonesWhereBigIntsEnabled = 0;

 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   if (zone->nurseryStringsDisabled || zone->nurseryBigIntsDisabled) {
     // We may need to reset allocation sites and discard JIT code to recover
     // if we find object lifetimes have changed.
     if (zone->pretenuring.shouldResetPretenuredAllocSites()) {
       zone->unknownAllocSite(JS::TraceKind::String)->maybeResetState();
       zone->unknownAllocSite(JS::TraceKind::BigInt)->maybeResetState();
       if (zone->nurseryStringsDisabled) {
         zone->nurseryStringsDisabled = false;
         zonesWhereStringsEnabled++;
       }
       if (zone->nurseryBigIntsDisabled) {
         zone->nurseryBigIntsDisabled = false;
         zonesWhereBigIntsEnabled++;
       }
       nursery().updateAllocFlagsForZone(zone);
     }
   }
 }

 if (nursery().reportPretenuring()) {
   if (zonesWhereStringsEnabled) {
     fprintf(stderr, "GC re-enabled nursery string allocation in %zu zones\n",
             zonesWhereStringsEnabled);
   }
   if (zonesWhereBigIntsEnabled) {
     fprintf(stderr, "GC re-enabled nursery big int allocation in %zu zones\n",
             zonesWhereBigIntsEnabled);
   }
 }
}

void GCRuntime::updateSchedulingStateOnGCEnd(TimeStamp currentTime) {
 TimeDuration totalGCTime = stats().totalGCTime();
 size_t totalInitialBytes = stats().initialCollectedBytes();

 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   if (tunables.balancedHeapLimitsEnabled() && totalInitialBytes != 0) {
     zone->updateCollectionRate(totalGCTime, totalInitialBytes);
   }
   zone->clearGCSliceThresholds();
   zone->updateGCStartThresholds(*this);
 }
}

void GCRuntime::updateAllGCStartThresholds() {
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   zone->updateGCStartThresholds(*this);
 }
}

void GCRuntime::updateAllocationRates() {
 // Calculate mutator time since the last update. This ignores the fact that
 // the zone could have been created since the last update.

 TimeStamp currentTime = TimeStamp::Now();
 TimeDuration totalTime = currentTime - lastAllocRateUpdateTime;
 if (collectorTimeSinceAllocRateUpdate >= totalTime) {
   // It shouldn't happen but occasionally we see collector time being larger
   // than total time. Skip the update in that case.
   return;
 }

 TimeDuration mutatorTime = totalTime - collectorTimeSinceAllocRateUpdate;

 for (AllZonesIter zone(this); !zone.done(); zone.next()) {
   zone->updateAllocationRate(mutatorTime);
   zone->updateGCStartThresholds(*this);
 }

 lastAllocRateUpdateTime = currentTime;
 collectorTimeSinceAllocRateUpdate = TimeDuration::Zero();
}

static const char* GCHeapStateToLabel(JS::HeapState heapState) {
 switch (heapState) {
   case JS::HeapState::MinorCollecting:
     return "Minor GC";
   case JS::HeapState::MajorCollecting:
     return "Major GC";
   default:
     MOZ_CRASH("Unexpected heap state when pushing GC profiling stack frame");
 }
 MOZ_ASSERT_UNREACHABLE("Should have exhausted every JS::HeapState variant!");
 return nullptr;
}

static JS::ProfilingCategoryPair GCHeapStateToProfilingCategory(
   JS::HeapState heapState) {
 return heapState == JS::HeapState::MinorCollecting
            ? JS::ProfilingCategoryPair::GCCC_MinorGC
            : JS::ProfilingCategoryPair::GCCC_MajorGC;
}

/* Start a new heap session. */
AutoHeapSession::AutoHeapSession(GCRuntime* gc, JS::HeapState heapState)
   : gc(gc), prevState(gc->heapState_) {
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(gc->rt));
 MOZ_ASSERT(prevState == JS::HeapState::Idle ||
            (prevState == JS::HeapState::MajorCollecting &&
             heapState == JS::HeapState::Idle) ||
            (prevState == JS::HeapState::MajorCollecting &&
             heapState == JS::HeapState::MinorCollecting));

 gc->heapState_ = heapState;

 if (heapState == JS::HeapState::MinorCollecting ||
     heapState == JS::HeapState::MajorCollecting) {
   profilingStackFrame.emplace(
       gc->rt->mainContextFromOwnThread(), GCHeapStateToLabel(heapState),
       GCHeapStateToProfilingCategory(heapState),
       uint32_t(ProfilingStackFrame::Flags::RELEVANT_FOR_JS));
 }
}

AutoHeapSession::~AutoHeapSession() { gc->heapState_ = prevState; }

AutoTraceSession::AutoTraceSession(JSRuntime* rt)
   : AutoHeapSession(&rt->gc, JS::HeapState::Tracing),
     JS::AutoCheckCannotGC() {}

static const char* MajorGCStateToLabel(State state) {
 switch (state) {
   case State::Mark:
     return "js::GCRuntime::markUntilBudgetExhausted";
   case State::Sweep:
     return "js::GCRuntime::performSweepActions";
   case State::Compact:
     return "js::GCRuntime::compactPhase";
   default:
     MOZ_CRASH("Unexpected heap state when pushing GC profiling stack frame");
 }

 MOZ_ASSERT_UNREACHABLE("Should have exhausted every State variant!");
 return nullptr;
}

static JS::ProfilingCategoryPair MajorGCStateToProfilingCategory(State state) {
 switch (state) {
   case State::Mark:
     return JS::ProfilingCategoryPair::GCCC_MajorGC_Mark;
   case State::Sweep:
     return JS::ProfilingCategoryPair::GCCC_MajorGC_Sweep;
   case State::Compact:
     return JS::ProfilingCategoryPair::GCCC_MajorGC_Compact;
   default:
     MOZ_CRASH("Unexpected heap state when pushing GC profiling stack frame");
 }
}

AutoMajorGCProfilerEntry::AutoMajorGCProfilerEntry(GCRuntime* gc)
   : AutoGeckoProfilerEntry(gc->rt->mainContextFromAnyThread(),
                            MajorGCStateToLabel(gc->state()),
                            MajorGCStateToProfilingCategory(gc->state())) {
 MOZ_ASSERT(gc->heapState() == JS::HeapState::MajorCollecting);
}

GCRuntime::IncrementalResult GCRuntime::resetIncrementalGC(
   GCAbortReason reason) {
 MOZ_ASSERT(reason != GCAbortReason::None);

 // Drop as much work as possible from an ongoing incremental GC so
 // we can start a new GC after it has finished.
 if (incrementalState == State::NotActive) {
   return IncrementalResult::Ok;
 }

 AutoGCSession session(this, JS::HeapState::MajorCollecting);

 switch (incrementalState) {
   case State::NotActive:
   case State::Finish:
     MOZ_CRASH("Unexpected GC state in resetIncrementalGC");
     break;

   case State::Prepare:
     unmarkTask.cancelAndWait();
     cancelRequestedGCAfterBackgroundTask();
     [[fallthrough]];

   case State::MarkRoots:
     // We haven't done any marking yet at this point.
     for (GCZonesIter zone(this); !zone.done(); zone.next()) {
       zone->changeGCState(zone->gcState(), Zone::NoGC);
       zone->clearGCSliceThresholds();
       zone->arenas.clearFreeLists();
       zone->arenas.mergeArenasFromCollectingLists();
     }

     // The gray marking state may not be valid. We don't do gray unmarking
     // when zones are in the Prepare state.
     setGrayBitsInvalid();

     incrementalState = State::NotActive;
     checkGCStateNotInUse();
     break;

   case State::Mark: {
     // Cancel any ongoing marking.
     for (auto& marker : markers) {
       marker->reset();
     }
     resetDelayedMarking();

     for (GCCompartmentsIter c(rt); !c.done(); c.next()) {
       resetGrayList(c);
     }

     // The gray marking state may not be valid. We depend on the mark stack to
     // do gray unmarking in zones that are being marked by the GC and we've
     // just cancelled that part way through.
     setGrayBitsInvalid();

     // Wait for sweeping of nursery owned sized allocations to finish.
     nursery().joinSweepTask();

     {
       BufferAllocator::AutoLock lock(this);
       for (GCZonesIter zone(this); !zone.done(); zone.next()) {
         zone->changeGCState(zone->initialMarkingState(), Zone::NoGC);
         zone->clearGCSliceThresholds();
         zone->arenas.unmarkPreMarkedFreeCells();
         zone->arenas.mergeArenasFromCollectingLists();

         // Merge sized alloc data structures back without sweeping them.
         zone->bufferAllocator.finishMajorCollection(lock);
       }
     }

     atomsUsedByUncollectedZones.ref().reset();

     {
       AutoLockHelperThreadState lock;
       lifoBlocksToFree.ref().freeAll();
     }

     lastMarkSlice = false;
     incrementalState = State::Finish;

#ifdef DEBUG
     for (auto& marker : markers) {
       MOZ_ASSERT(!marker->shouldCheckCompartments());
     }
#endif

     break;
   }

   case State::Sweep: {
     // Finish sweeping the current sweep group, then abort.
     for (CompartmentsIter c(rt); !c.done(); c.next()) {
       c->gcState.scheduledForDestruction = false;
     }

     abortSweepAfterCurrentGroup = true;
     isCompacting = false;

     break;
   }

   case State::Finalize: {
     isCompacting = false;
     break;
   }

   case State::Compact: {
     // Skip any remaining zones that would have been compacted.
     MOZ_ASSERT(isCompacting);
     startedCompacting = true;
     zonesToMaybeCompact.ref().clear();
     break;
   }

   case State::Decommit: {
     break;
   }
 }

 stats().reset(reason);

 if (reason == GCAbortReason::AbortRequested) {
   return IncrementalResult::Abort;
 }

 return IncrementalResult::Reset;
}

void GCRuntime::setGrayBitsInvalid() {
 grayBitsValid = false;
 atomMarking.unmarkAllGrayReferences(this);
}

void GCRuntime::disableIncrementalBarriers() {
 // Clear needsIncrementalBarrier so we don't do any write barriers during
 // foreground finalization. This would otherwise happen when destroying
 // HeapPtr<>s to GC things in zones which are still marking.

 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   if (zone->isGCMarking()) {
     MOZ_ASSERT(zone->needsIncrementalBarrier());
     zone->setNeedsIncrementalBarrier(false);
   }
   MOZ_ASSERT(!zone->needsIncrementalBarrier());
 }
}

void GCRuntime::enableIncrementalBarriers() {
 for (GCZonesIter zone(this); !zone.done(); zone.next()) {
   MOZ_ASSERT(!zone->needsIncrementalBarrier());
   if (zone->isGCMarking()) {
     zone->setNeedsIncrementalBarrier(true);
   }
 }
}

static bool NeedToCollectNursery(GCRuntime* gc) {
 return !gc->nursery().isEmpty() || !gc->storeBuffer().isEmpty();
}

static bool ShouldPauseMutatorWhileWaiting(const SliceBudget& budget,
                                          JS::GCReason reason,
                                          bool budgetWasIncreased) {
 // When we're nearing the incremental limit at which we will finish the
 // collection synchronously, pause the main thread if there is only background
 // GC work happening. This allows the GC to catch up and avoid hitting the
 // limit.
 return budget.isTimeBudget() &&
        (reason == JS::GCReason::ALLOC_TRIGGER ||
         reason == JS::GCReason::TOO_MUCH_MALLOC) &&
        budgetWasIncreased;
}

void GCRuntime::incrementalSlice(SliceBudget& budget, JS::GCReason reason,
                                bool budgetWasIncreased) {
 MOZ_ASSERT_IF(isIncrementalGCInProgress(), isIncremental);

 AutoSetThreadIsPerformingGC performingGC(rt->gcContext());

 AutoGCSession session(this, JS::HeapState::MajorCollecting);

 bool destroyingRuntime = (reason == JS::GCReason::DESTROY_RUNTIME);

 initialState = incrementalState;
 isIncremental = !budget.isUnlimited();
 useBackgroundThreads = ShouldUseBackgroundThreads(isIncremental, reason);

#ifdef JS_GC_ZEAL
 // Do the incremental collection type specified by zeal mode if the collection
 // was triggered by runDebugGC() and incremental GC has not been cancelled by
 // resetIncrementalGC().
 useZeal = isIncremental && reason == JS::GCReason::DEBUG_GC;
#endif

 if (useZeal && zealModeControlsYieldPoint()) {
   // Yields between slices occurs at predetermined points in these modes; the
   // budget is not used. |isIncremental| is still true.
   budget = SliceBudget::unlimited();
 }

 bool shouldPauseMutator =
     ShouldPauseMutatorWhileWaiting(budget, reason, budgetWasIncreased);

 switch (incrementalState) {
   case State::NotActive:
     startCollection(reason);

     incrementalState = State::Prepare;
     if (!beginPreparePhase(reason, session)) {
       incrementalState = State::NotActive;
       break;
     }

     if (useZeal && hasZealMode(ZealMode::YieldBeforeRootMarking)) {
       break;
     }

     [[fallthrough]];

   case State::Prepare:
     if (waitForBackgroundTask(unmarkTask, budget, shouldPauseMutator) ==
         NotFinished) {
       break;
     }

     incrementalState = State::MarkRoots;

     if (isIncremental && initialState == State::Prepare &&
         reason == JS::GCReason::BG_TASK_FINISHED) {
       // The next slice may be long so wait for the embedding to schedule it
       // rather than doing it as soon as unmarking finishes. This can happen
       // when the embedding's GC callback sees this slice end with work
       // available.
       MOZ_ASSERT(hasForegroundWork());
       break;
     }

     [[fallthrough]];

   case State::MarkRoots:
     endPreparePhase(reason);

     {
       AutoGCSession commitSession(this, JS::HeapState::Idle);
       rt->commitPendingWrapperPreservations();
     }

     beginMarkPhase(session);
     incrementalState = State::Mark;

     if (useZeal && hasZealMode(ZealMode::YieldBeforeMarking) &&
         isIncremental) {
       break;
     }

     [[fallthrough]];

   case State::Mark:
     if (mightSweepInThisSlice(budget.isUnlimited())) {
       prepareForSweepSlice(reason);

       // Incremental marking validation re-runs all marking non-incrementally,
       // which requires collecting the nursery. If that might happen in this
       // slice, do it now while it's safe to do so.
       if (isIncremental &&
           hasZealMode(ZealMode::IncrementalMarkingValidator)) {
         collectNurseryFromMajorGC(JS::GCReason::EVICT_NURSERY);
       }
     }

     {
       gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::MARK);
       if (markUntilBudgetExhausted(budget, useParallelMarking) ==
           NotFinished) {
         break;
       }
     }

     assertNoMarkingWork();

     /*
      * There are a number of reasons why we break out of collection here,
      * either ending the slice or to run a new interation of the loop in
      * GCRuntime::collect()
      */

     /*
      * In incremental GCs where we have already performed more than one
      * slice we yield after marking with the aim of starting the sweep in
      * the next slice, since the first slice of sweeping can be expensive.
      *
      * This is modified by the various zeal modes.  We don't yield in
      * YieldBeforeMarking mode and we always yield in YieldBeforeSweeping
      * mode.
      *
      * We will need to mark anything new on the stack when we resume, so
      * we stay in Mark state.
      */
     if (isIncremental && !lastMarkSlice) {
       if ((initialState == State::Mark &&
            !(useZeal && hasZealMode(ZealMode::YieldBeforeMarking))) ||
           (useZeal && hasZealMode(ZealMode::YieldBeforeSweeping))) {
         lastMarkSlice = true;
         break;
       }
     }

     incrementalState = State::Sweep;
     lastMarkSlice = false;

     beginSweepPhase(reason, session);

     [[fallthrough]];

   case State::Sweep:
     if (initialState == State::Sweep) {
       prepareForSweepSlice(reason);
     }

     if (performSweepActions(budget) == NotFinished) {
       break;
     }

     endSweepPhase(destroyingRuntime);

     incrementalState = State::Finalize;

     [[fallthrough]];

   case State::Finalize:
     if (waitForBackgroundTask(sweepTask, budget, shouldPauseMutator) ==
         NotFinished) {
       break;
     }

     for (GCZonesIter zone(this); !zone.done(); zone.next()) {
       zone->arenas.mergeBackgroundSweptArenas();
     }

     {
       BufferAllocator::AutoLock lock(this);
       for (GCZonesIter zone(this); !zone.done(); zone.next()) {
         zone->bufferAllocator.finishMajorCollection(lock);
       }
     }

     atomMarking.mergePendingFreeArenaIndexes(this);

     {
       AutoLockGC lock(this);
       clearCurrentChunk(lock);
     }

     assertBackgroundSweepingFinished();

     // Ensure freeing of nursery owned sized allocations from the initial
     // minor GC has finished.
     MOZ_ASSERT(minorGCNumber >= initialMinorGCNumber);
     if (minorGCNumber == initialMinorGCNumber) {
       MOZ_ASSERT(nursery().sweepTaskIsIdle());
     }

     {
       // Sweep the zones list now that background finalization is finished to
       // remove and free dead zones, compartments and realms.
       gcstats::AutoPhase ap1(stats(), gcstats::PhaseKind::SWEEP);
       gcstats::AutoPhase ap2(stats(), gcstats::PhaseKind::DESTROY);
       sweepZones(rt->gcContext(), destroyingRuntime);
     }

     MOZ_ASSERT(!startedCompacting);
     incrementalState = State::Compact;

     // Always yield before compacting since it is not incremental.
     if (isCompacting && !budget.isUnlimited()) {
       break;
     }

     [[fallthrough]];

   case State::Compact:
     if (isCompacting) {
       {
         AutoGCSession commitSession(this, JS::HeapState::Idle);
         rt->commitPendingWrapperPreservations();
       }

       if (NeedToCollectNursery(this)) {
         collectNurseryFromMajorGC(reason);
       }

       storeBuffer().checkEmpty();
       if (!startedCompacting) {
         beginCompactPhase();
       }

       nursery().joinSweepTask();
       if (compactPhase(reason, budget, session) == NotFinished) {
         break;
       }

       endCompactPhase();
     }

     startDecommit();
     incrementalState = State::Decommit;

     [[fallthrough]];

   case State::Decommit:
     if (waitForBackgroundTask(decommitTask, budget, shouldPauseMutator) ==
         NotFinished) {
       break;
     }

     incrementalState = State::Finish;

     [[fallthrough]];

   case State::Finish:
     finishCollection(reason);
     incrementalState = State::NotActive;
     break;
 }

#ifdef DEBUG
 MOZ_ASSERT(safeToYield);
 for (auto& marker : markers) {
   MOZ_ASSERT(marker->markColor() == MarkColor::Black);
 }
 MOZ_ASSERT(!rt->gcContext()->hasJitCodeToPoison());
#endif
}

void GCRuntime::collectNurseryFromMajorGC(JS::GCReason reason) {
 collectNursery(gcOptions(), JS::GCReason::EVICT_NURSERY,
                gcstats::PhaseKind::EVICT_NURSERY_FOR_MAJOR_GC);

 MOZ_ASSERT(nursery().isEmpty());
 MOZ_ASSERT(storeBuffer().isEmpty());
}

bool GCRuntime::hasForegroundWork() const {
 switch (incrementalState) {
   case State::NotActive:
     // Incremental GC is not running and no work is pending.
     return false;
   case State::Prepare:
     // We yield in the Prepare state after starting unmarking.
     return !unmarkTask.wasStarted();
   case State::Finalize:
     // We yield in the Finalize state to wait for background sweeping.
     return !isBackgroundSweeping();
   case State::Decommit:
     // We yield in the Decommit state to wait for background decommit.
     return !decommitTask.wasStarted();
   default:
     // In all other states there is still work to do.
     return true;
 }
}

IncrementalProgress GCRuntime::waitForBackgroundTask(GCParallelTask& task,
                                                    const SliceBudget& budget,
                                                    bool shouldPauseMutator) {
 // Wait here in non-incremental collections, or if we want to pause the
 // mutator to let the GC catch up.
 if (budget.isUnlimited() || shouldPauseMutator) {
   gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::WAIT_BACKGROUND_THREAD);
   Maybe<TimeStamp> deadline;
   if (budget.isTimeBudget()) {
     deadline.emplace(budget.deadline());
   }
   task.join(deadline);
 }

 // In incremental collections, yield if the task has not finished and request
 // a slice to notify us when this happens.
 if (!budget.isUnlimited()) {
   AutoLockHelperThreadState lock;
   if (task.wasStarted(lock)) {
     requestSliceAfterBackgroundTask = true;
     return NotFinished;
   }

   task.joinWithLockHeld(lock);
 }

 MOZ_ASSERT(task.isIdle());

 cancelRequestedGCAfterBackgroundTask();

 return Finished;
}

inline void GCRuntime::checkZoneIsScheduled(Zone* zone, JS::GCReason reason,
                                           const char* trigger) {
#ifdef DEBUG
 if (zone->isGCScheduled()) {
   return;
 }

 fprintf(stderr,
         "checkZoneIsScheduled: Zone %p not scheduled as expected in %s GC "
         "for %s trigger\n",
         zone, JS::ExplainGCReason(reason), trigger);
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   fprintf(stderr, "  Zone %p:%s%s\n", zone.get(),
           zone->isAtomsZone() ? " atoms" : "",
           zone->isGCScheduled() ? " scheduled" : "");
 }
 fflush(stderr);
 MOZ_CRASH("Zone not scheduled");
#endif
}

GCRuntime::IncrementalResult GCRuntime::budgetIncrementalGC(
   bool nonincrementalByAPI, JS::GCReason reason, SliceBudget& budget) {
 if (nonincrementalByAPI) {
   stats().nonincremental(GCAbortReason::NonIncrementalRequested);
   budget = SliceBudget::unlimited();

   // Reset any in progress incremental GC if this was triggered via the
   // API. This isn't required for correctness, but sometimes during tests
   // the caller expects this GC to collect certain objects, and we need
   // to make sure to collect everything possible.
   if (reason != JS::GCReason::ALLOC_TRIGGER) {
     return resetIncrementalGC(GCAbortReason::NonIncrementalRequested);
   }

   return IncrementalResult::Ok;
 }

 if (reason == JS::GCReason::ABORT_GC) {
   budget = SliceBudget::unlimited();
   stats().nonincremental(GCAbortReason::AbortRequested);
   return resetIncrementalGC(GCAbortReason::AbortRequested);
 }

 if (!budget.isUnlimited()) {
   GCAbortReason unsafeReason = GCAbortReason::None;
   if (reason == JS::GCReason::COMPARTMENT_REVIVED) {
     unsafeReason = GCAbortReason::CompartmentRevived;
   } else if (!incrementalGCEnabled) {
     unsafeReason = GCAbortReason::ModeChange;
   }

   if (unsafeReason != GCAbortReason::None) {
     budget = SliceBudget::unlimited();
     stats().nonincremental(unsafeReason);
     return resetIncrementalGC(unsafeReason);
   }
 }

 GCAbortReason resetReason = GCAbortReason::None;
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   if (zone->gcHeapSize.bytes() >=
       zone->gcHeapThreshold.incrementalLimitBytes()) {
     checkZoneIsScheduled(zone, reason, "GC bytes");
     budget = SliceBudget::unlimited();
     stats().nonincremental(GCAbortReason::GCBytesTrigger);
     if (zone->wasGCStarted() && zone->gcState() > Zone::Sweep) {
       resetReason = GCAbortReason::GCBytesTrigger;
     }
   }

   if (zone->mallocHeapSize.bytes() >=
       zone->mallocHeapThreshold.incrementalLimitBytes()) {
     checkZoneIsScheduled(zone, reason, "malloc bytes");
     budget = SliceBudget::unlimited();
     stats().nonincremental(GCAbortReason::MallocBytesTrigger);
     if (zone->wasGCStarted() && zone->gcState() > Zone::Sweep) {
       resetReason = GCAbortReason::MallocBytesTrigger;
     }
   }

   if (zone->jitHeapSize.bytes() >=
       zone->jitHeapThreshold.incrementalLimitBytes()) {
     checkZoneIsScheduled(zone, reason, "JIT code bytes");
     budget = SliceBudget::unlimited();
     stats().nonincremental(GCAbortReason::JitCodeBytesTrigger);
     if (zone->wasGCStarted() && zone->gcState() > Zone::Sweep) {
       resetReason = GCAbortReason::JitCodeBytesTrigger;
     }
   }

   if (isIncrementalGCInProgress() &&
       zone->isGCScheduled() != zone->wasGCStarted()) {
     budget = SliceBudget::unlimited();
     resetReason = GCAbortReason::ZoneChange;
   }
 }

 if (resetReason != GCAbortReason::None) {
   return resetIncrementalGC(resetReason);
 }

 return IncrementalResult::Ok;
}

bool GCRuntime::maybeIncreaseSliceBudget(SliceBudget& budget,
                                        TimeStamp sliceStartTime,
                                        TimeStamp gcStartTime) {
 if (js::SupportDifferentialTesting()) {
   return false;
 }

 if (!budget.isTimeBudget() || !isIncrementalGCInProgress()) {
   return false;
 }

 bool wasIncreasedForLongCollections =
     maybeIncreaseSliceBudgetForLongCollections(budget, sliceStartTime,
                                                gcStartTime);
 bool wasIncreasedForUgentCollections =
     maybeIncreaseSliceBudgetForUrgentCollections(budget);

 return wasIncreasedForLongCollections || wasIncreasedForUgentCollections;
}

// Return true if the budget is actually extended after rounding.
static bool ExtendBudget(SliceBudget& budget, double newDuration) {
 long millis = lround(newDuration);
 if (millis <= budget.timeBudget()) {
   return false;
 }

 bool idleTriggered = budget.idle;
 budget = SliceBudget(TimeBudget(millis), nullptr);  // Uninterruptible.
 budget.idle = idleTriggered;
 budget.extended = true;
 return true;
}

bool GCRuntime::maybeIncreaseSliceBudgetForLongCollections(
   SliceBudget& budget, TimeStamp sliceStartTime, TimeStamp gcStartTime) {
 // For long-running collections, enforce a minimum time budget that increases
 // linearly with time up to a maximum.

 // All times are in milliseconds.
 struct BudgetAtTime {
   double time;
   double budget;
 };
 const BudgetAtTime MinBudgetStart{1500, 0.0};
 const BudgetAtTime MinBudgetEnd{2500, 100.0};

 double totalTime = (sliceStartTime - gcStartTime).ToMilliseconds();

 double minBudget =
     LinearInterpolate(totalTime, MinBudgetStart.time, MinBudgetStart.budget,
                       MinBudgetEnd.time, MinBudgetEnd.budget);

 return ExtendBudget(budget, minBudget);
}

bool GCRuntime::maybeIncreaseSliceBudgetForUrgentCollections(
   SliceBudget& budget) {
 // Enforce a minimum time budget based on how close we are to the incremental
 // limit.

 size_t minBytesRemaining = SIZE_MAX;
 for (AllZonesIter zone(this); !zone.done(); zone.next()) {
   if (!zone->wasGCStarted()) {
     continue;
   }
   size_t gcBytesRemaining =
       zone->gcHeapThreshold.incrementalBytesRemaining(zone->gcHeapSize);
   minBytesRemaining = std::min(minBytesRemaining, gcBytesRemaining);
   size_t mallocBytesRemaining =
       zone->mallocHeapThreshold.incrementalBytesRemaining(
           zone->mallocHeapSize);
   minBytesRemaining = std::min(minBytesRemaining, mallocBytesRemaining);
 }

 if (minBytesRemaining < tunables.urgentThresholdBytes() &&
     minBytesRemaining != 0) {
   // Increase budget based on the reciprocal of the fraction remaining.
   double fractionRemaining =
       double(minBytesRemaining) / double(tunables.urgentThresholdBytes());
   double minBudget = double(defaultSliceBudgetMS()) / fractionRemaining;
   return ExtendBudget(budget, minBudget);
 }

 return false;
}

static void ScheduleZones(GCRuntime* gc, JS::GCReason reason) {
 for (ZonesIter zone(gc, WithAtoms); !zone.done(); zone.next()) {
   // Re-check heap threshold for alloc-triggered zones that were not
   // previously collected. Now we have allocation rate data, the heap limit
   // may have been increased beyond the current size.
   if (gc->tunables.balancedHeapLimitsEnabled() && zone->isGCScheduled() &&
       zone->smoothedCollectionRate.ref().isNothing() &&
       reason == JS::GCReason::ALLOC_TRIGGER &&
       zone->gcHeapSize.bytes() < zone->gcHeapThreshold.startBytes()) {
     zone->unscheduleGC();  // May still be re-scheduled below.
   }

   if (gc->isShutdownGC()) {
     zone->scheduleGC();
   }

   if (!gc->isPerZoneGCEnabled()) {
     zone->scheduleGC();
   }

   // To avoid resets, continue to collect any zones that were being
   // collected in a previous slice.
   if (gc->isIncrementalGCInProgress() && zone->wasGCStarted()) {
     zone->scheduleGC();
   }

   // This is a heuristic to reduce the total number of collections.
   bool inHighFrequencyMode = gc->schedulingState.inHighFrequencyGCMode();
   if (zone->gcHeapSize.bytes() >=
           zone->gcHeapThreshold.eagerAllocTrigger(inHighFrequencyMode) ||
       zone->mallocHeapSize.bytes() >=
           zone->mallocHeapThreshold.eagerAllocTrigger(inHighFrequencyMode) ||
       zone->jitHeapSize.bytes() >= zone->jitHeapThreshold.startBytes()) {
     zone->scheduleGC();
   }
 }
}

static void UnscheduleZones(GCRuntime* gc) {
 for (ZonesIter zone(gc->rt, WithAtoms); !zone.done(); zone.next()) {
   zone->unscheduleGC();
 }
}

class js::gc::AutoCallGCCallbacks {
 GCRuntime& gc_;
 JS::GCReason reason_;

public:
 explicit AutoCallGCCallbacks(GCRuntime& gc, JS::GCReason reason)
     : gc_(gc), reason_(reason) {
   gc_.maybeCallGCCallback(JSGC_BEGIN, reason);
 }
 ~AutoCallGCCallbacks() { gc_.maybeCallGCCallback(JSGC_END, reason_); }
};

void GCRuntime::maybeCallGCCallback(JSGCStatus status, JS::GCReason reason) {
 if (!gcCallback.ref().op) {
   return;
 }

 if (isIncrementalGCInProgress()) {
   return;
 }

 if (gcCallbackDepth == 0) {
   // Save scheduled zone information in case the callback clears it.
   for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
     zone->gcScheduledSaved_ = zone->gcScheduled_;
   }
 }

 // Save and clear GC options and state in case the callback reenters GC.
 JS::GCOptions options = gcOptions();
 maybeGcOptions = Nothing();
 bool savedFullGCRequested = fullGCRequested;
 fullGCRequested = false;

 gcCallbackDepth++;

 callGCCallback(status, reason);

 MOZ_ASSERT(gcCallbackDepth != 0);
 gcCallbackDepth--;

 // Restore the original GC options.
 maybeGcOptions = Some(options);

 // At the end of a GC, clear out the fullGCRequested state. At the start,
 // restore the previous setting.
 fullGCRequested = savedFullGCRequested;

 if (gcCallbackDepth == 0) {
   // Ensure any zone that was originally scheduled stays scheduled.
   for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
     zone->gcScheduled_ = zone->gcScheduled_ || zone->gcScheduledSaved_;
   }
 }
}

/*
* We disable inlining to ensure that the bottom of the stack with possible GC
* roots recorded in MarkRuntime excludes any pointers we use during the marking
* implementation.
*/
MOZ_NEVER_INLINE GCRuntime::IncrementalResult GCRuntime::gcCycle(
   bool nonincrementalByAPI, const SliceBudget& budgetArg,
   JS::GCReason reason) {
 // Assert if this is a GC unsafe region.
 rt->mainContextFromOwnThread()->verifyIsSafeToGC();

 // It's ok if threads other than the main thread have suppressGC set, as
 // they are operating on zones which will not be collected from here.
 MOZ_ASSERT(!rt->mainContextFromOwnThread()->suppressGC);

 // This reason is used internally. See below.
 MOZ_ASSERT(reason != JS::GCReason::RESET);

 // Background finalization and decommit are finished by definition before we
 // can start a new major GC.  Background allocation may still be running, but
 // that's OK because chunk pools are protected by the GC lock.
 bool firstSlice = !isIncrementalGCInProgress();
 if (firstSlice) {
   assertBackgroundSweepingFinished();
   MOZ_ASSERT(decommitTask.isIdle());
 }

 // Note that GC callbacks are allowed to re-enter GC.
 AutoCallGCCallbacks callCallbacks(*this, reason);

 // Reset the fullGCRequested flag at the end of GC.
 auto resetFullFlag = MakeScopeExit([&] {
   if (!isIncrementalGCInProgress()) {
     fullGCRequested = false;
   }
 });

 // Record GC start time and update global scheduling state.
 TimeStamp now = TimeStamp::Now();
 if (firstSlice) {
   schedulingState.updateHighFrequencyModeOnGCStart(
       gcOptions(), lastGCStartTime_, now, tunables);
   lastGCStartTime_ = now;
 }
 schedulingState.updateHighFrequencyModeOnSliceStart(gcOptions(), reason);

 // Increase slice budget for long running collections before it is recorded by
 // AutoGCSlice.
 SliceBudget budget(budgetArg);
 bool budgetWasIncreased =
     maybeIncreaseSliceBudget(budget, now, lastGCStartTime_);

 ScheduleZones(this, reason);

 auto updateCollectorTime = MakeScopeExit([&] {
   if (const gcstats::Statistics::SliceData* slice = stats().lastSlice()) {
     collectorTimeSinceAllocRateUpdate += slice->duration();
   }
 });

 gcstats::AutoGCSlice agc(stats(), scanZonesBeforeGC(), gcOptions(), budget,
                          reason, budgetWasIncreased);

 IncrementalResult result =
     budgetIncrementalGC(nonincrementalByAPI, reason, budget);

 if (result != IncrementalResult::Ok && incrementalState == State::NotActive) {
   // The collection was reset or aborted and has finished.
   return result;
 }

 if (result == IncrementalResult::Reset) {
   // The collection was reset but we must finish up some remaining work. This
   // happens with the reset reason, after which a new collection will be
   // started.
   reason = JS::GCReason::RESET;
 }

 majorGCTriggerReason = JS::GCReason::NO_REASON;
 MOZ_ASSERT(!stats().hasTrigger());

 incGcNumber();
 incGcSliceNumber();

 gcprobes::MajorGCStart();
 incrementalSlice(budget, reason, budgetWasIncreased);
 gcprobes::MajorGCEnd();

 MOZ_ASSERT_IF(result == IncrementalResult::Reset,
               !isIncrementalGCInProgress());
 return result;
}

inline bool GCRuntime::mightSweepInThisSlice(bool nonIncremental) {
 MOZ_ASSERT(incrementalState < State::Sweep);
 return nonIncremental || lastMarkSlice || zealModeControlsYieldPoint();
}

#ifdef JS_GC_ZEAL
static bool IsDeterministicGCReason(JS::GCReason reason) {
 switch (reason) {
   case JS::GCReason::API:
   case JS::GCReason::DESTROY_RUNTIME:
   case JS::GCReason::LAST_DITCH:
   case JS::GCReason::TOO_MUCH_MALLOC:
   case JS::GCReason::TOO_MUCH_WASM_MEMORY:
   case JS::GCReason::TOO_MUCH_JIT_CODE:
   case JS::GCReason::ALLOC_TRIGGER:
   case JS::GCReason::DEBUG_GC:
   case JS::GCReason::CC_FORCED:
   case JS::GCReason::SHUTDOWN_CC:
   case JS::GCReason::ABORT_GC:
   case JS::GCReason::DISABLE_GENERATIONAL_GC:
   case JS::GCReason::FINISH_GC:
   case JS::GCReason::PREPARE_FOR_TRACING:
     return true;

   default:
     return false;
 }
}
#endif

gcstats::ZoneGCStats GCRuntime::scanZonesBeforeGC() {
 gcstats::ZoneGCStats zoneStats;
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   zoneStats.zoneCount++;
   zoneStats.compartmentCount += zone->compartments().length();
   for (CompartmentsInZoneIter comp(zone); !comp.done(); comp.next()) {
     zoneStats.realmCount += comp->realms().length();
   }
   if (zone->isGCScheduled()) {
     zoneStats.collectedZoneCount++;
     zoneStats.collectedCompartmentCount += zone->compartments().length();
   }
 }

 return zoneStats;
}

// The GC can only clean up scheduledForDestruction realms that were marked live
// by a barrier (e.g. by RemapWrappers from a navigation event). It is also
// common to have realms held live because they are part of a cycle in gecko,
// e.g. involving the HTMLDocument wrapper. In this case, we need to run the
// CycleCollector in order to remove these edges before the realm can be freed.
void GCRuntime::maybeDoCycleCollection() {
 const static float ExcessiveGrayRealms = 0.8f;
 const static size_t LimitGrayRealms = 200;

 size_t realmsTotal = 0;
 size_t realmsGray = 0;
 for (RealmsIter realm(rt); !realm.done(); realm.next()) {
   ++realmsTotal;
   GlobalObject* global = realm->unsafeUnbarrieredMaybeGlobal();
   if (global && global->isMarkedGray()) {
     ++realmsGray;
   }
 }
 float grayFraction = float(realmsGray) / float(realmsTotal);
 if (grayFraction > ExcessiveGrayRealms || realmsGray > LimitGrayRealms) {
   callDoCycleCollectionCallback(rt->mainContextFromOwnThread());
 }
}

void GCRuntime::checkCanCallAPI() {
 MOZ_RELEASE_ASSERT(CurrentThreadCanAccessRuntime(rt));

 /* If we attempt to invoke the GC while we are running in the GC, assert. */
 MOZ_RELEASE_ASSERT(!JS::RuntimeHeapIsBusy());
}

bool GCRuntime::checkIfGCAllowedInCurrentState(JS::GCReason reason) {
 if (rt->mainContextFromOwnThread()->suppressGC) {
   return false;
 }

 // This detects coding errors where we are trying to run a GC when GC is
 // supposed to be impossible. Do this check here, before any other early
 // returns that might miss bugs. (Do not do this check first thing, because it
 // is legal to call GC() if you know GC is suppressed.)
 rt->mainContextFromOwnThread()->verifyIsSafeToGC();

 // Only allow shutdown GCs when we're destroying the runtime. This keeps
 // the GC callback from triggering a nested GC and resetting global state.
 if (rt->isBeingDestroyed() && !isShutdownGC()) {
   return false;
 }

#ifdef JS_GC_ZEAL
 if (deterministicOnly && !IsDeterministicGCReason(reason)) {
   return false;
 }
#endif

 return true;
}

bool GCRuntime::shouldRepeatForDeadZone(JS::GCReason reason) {
 MOZ_ASSERT_IF(reason == JS::GCReason::COMPARTMENT_REVIVED, !isIncremental);
 MOZ_ASSERT(!isIncrementalGCInProgress());

 if (!isIncremental) {
   return false;
 }

 for (CompartmentsIter c(rt); !c.done(); c.next()) {
   if (c->gcState.scheduledForDestruction) {
     return true;
   }
 }

 return false;
}

struct MOZ_RAII AutoSetZoneSliceThresholds {
 explicit AutoSetZoneSliceThresholds(GCRuntime* gc) : gc(gc) {
   // On entry, zones that are already collecting should have a slice threshold
   // set.
   for (ZonesIter zone(gc, WithAtoms); !zone.done(); zone.next()) {
     MOZ_ASSERT(zone->wasGCStarted() ==
                zone->gcHeapThreshold.hasSliceThreshold());
     MOZ_ASSERT(zone->wasGCStarted() ==
                zone->mallocHeapThreshold.hasSliceThreshold());
   }
 }

 ~AutoSetZoneSliceThresholds() {
   // On exit, update the thresholds for all collecting zones.
   bool waitingOnBGTask = gc->isWaitingOnBackgroundTask();
   for (ZonesIter zone(gc, WithAtoms); !zone.done(); zone.next()) {
     if (zone->wasGCStarted()) {
       zone->setGCSliceThresholds(*gc, waitingOnBGTask);
     } else {
       MOZ_ASSERT(!zone->gcHeapThreshold.hasSliceThreshold());
       MOZ_ASSERT(!zone->mallocHeapThreshold.hasSliceThreshold());
     }
   }
 }

 GCRuntime* gc;
};

void GCRuntime::collect(bool nonincrementalByAPI, const SliceBudget& budget,
                       JS::GCReason reason) {
 auto clearGCOptions = MakeScopeExit([&] {
   if (!isIncrementalGCInProgress()) {
     maybeGcOptions = Nothing();
   }
 });

 MOZ_ASSERT(reason != JS::GCReason::NO_REASON);

 // Checks run for each request, even if we do not actually GC.
 checkCanCallAPI();

 // Check if we are allowed to GC at this time before proceeding.
 if (!checkIfGCAllowedInCurrentState(reason)) {
   return;
 }

 JS_LOG(gc, Info, "begin slice for reason %s in state %s",
        ExplainGCReason(reason), StateName(incrementalState));

 AutoStopVerifyingBarriers av(rt, isShutdownGC());
 AutoMaybeLeaveAtomsZone leaveAtomsZone(rt->mainContextFromOwnThread());
 AutoSetZoneSliceThresholds sliceThresholds(this);

 if (!isIncrementalGCInProgress() && tunables.balancedHeapLimitsEnabled()) {
   updateAllocationRates();
 }

 bool repeat;
 do {
   IncrementalResult cycleResult =
       gcCycle(nonincrementalByAPI, budget, reason);

   if (cycleResult == IncrementalResult::Abort) {
     MOZ_ASSERT(reason == JS::GCReason::ABORT_GC);
     MOZ_ASSERT(!isIncrementalGCInProgress());
     JS_LOG(gc, Info, "aborted by request");
     break;
   }

   /*
    * Sometimes when we finish a GC we need to immediately start a new one.
    * This happens in the following cases:
    *  - when we reset the current GC
    *  - when finalizers drop roots during shutdown
    *  - when zones that we thought were dead at the start of GC are
    *    not collected (see the large comment in beginMarkPhase)
    */
   repeat = false;
   if (!isIncrementalGCInProgress()) {
     if (cycleResult == IncrementalResult::Reset) {
       repeat = true;
     } else if (rootsRemoved && isShutdownGC()) {
       /* Need to re-schedule all zones for GC. */
       JS::PrepareForFullGC(rt->mainContextFromOwnThread());
       repeat = true;
       reason = JS::GCReason::ROOTS_REMOVED;
     } else if (shouldRepeatForDeadZone(reason)) {
       repeat = true;
       reason = JS::GCReason::COMPARTMENT_REVIVED;
     }
   }
 } while (repeat);

 if (reason == JS::GCReason::COMPARTMENT_REVIVED) {
   maybeDoCycleCollection();
 }

#ifdef JS_GC_ZEAL
 if (!isIncrementalGCInProgress()) {
   if (hasZealMode(ZealMode::CheckHeapAfterGC)) {
     gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::TRACE_HEAP);
     CheckHeapAfterGC(rt);
   }
   if (hasZealMode(ZealMode::CheckGrayMarking)) {
     MOZ_RELEASE_ASSERT(CheckGrayMarkingState(rt));
   }
 }
#endif
 JS_LOG(gc, Info, "end slice in state %s", StateName(incrementalState));

 UnscheduleZones(this);
}

SliceBudget GCRuntime::defaultBudget(JS::GCReason reason, int64_t millis) {
 // millis == 0 means use internal GC scheduling logic to come up with
 // a duration for the slice budget. This may end up still being zero
 // based on preferences.
 if (millis == 0) {
   millis = defaultSliceBudgetMS();
 }

 // If the embedding has registered a callback for creating SliceBudgets,
 // then use it.
 if (createBudgetCallback) {
   return createBudgetCallback(reason, millis);
 }

 // Otherwise, the preference can request an unlimited duration slice.
 if (millis == 0) {
   return SliceBudget::unlimited();
 }

 return SliceBudget(TimeBudget(millis));
}

void GCRuntime::gc(JS::GCOptions options, JS::GCReason reason) {
 if (!isIncrementalGCInProgress()) {
   setGCOptions(options);
 }

 collect(true, SliceBudget::unlimited(), reason);
}

void GCRuntime::startGC(JS::GCOptions options, JS::GCReason reason,
                       const SliceBudget& budget) {
 MOZ_ASSERT(!isIncrementalGCInProgress());
 setGCOptions(options);

 if (!JS::IsIncrementalGCEnabled(rt->mainContextFromOwnThread())) {
   collect(true, SliceBudget::unlimited(), reason);
   return;
 }

 collect(false, budget, reason);
}

void GCRuntime::setGCOptions(JS::GCOptions options) {
 MOZ_ASSERT(maybeGcOptions == Nothing());
 maybeGcOptions = Some(options);
}

void GCRuntime::gcSlice(JS::GCReason reason, const SliceBudget& budget) {
 MOZ_ASSERT(isIncrementalGCInProgress());
 collect(false, budget, reason);
}

void GCRuntime::finishGC(JS::GCReason reason) {
 MOZ_ASSERT(isIncrementalGCInProgress());

 // If we're not collecting because we're out of memory then skip the
 // compacting phase if we need to finish an ongoing incremental GC
 // non-incrementally to avoid janking the browser.
 if (!IsOOMReason(initialReason)) {
   if (incrementalState == State::Compact) {
     abortGC();
     return;
   }

   isCompacting = false;
 }

 collect(false, SliceBudget::unlimited(), reason);
}

void GCRuntime::abortGC() {
 MOZ_ASSERT(isIncrementalGCInProgress());
 checkCanCallAPI();
 MOZ_ASSERT(!rt->mainContextFromOwnThread()->suppressGC);

 collect(false, SliceBudget::unlimited(), JS::GCReason::ABORT_GC);
}

static bool ZonesSelected(GCRuntime* gc) {
 for (ZonesIter zone(gc, WithAtoms); !zone.done(); zone.next()) {
   if (zone->isGCScheduled()) {
     return true;
   }
 }
 return false;
}

void GCRuntime::startDebugGC(JS::GCOptions options, const SliceBudget& budget) {
 MOZ_ASSERT(!isIncrementalGCInProgress());
 setGCOptions(options);

 if (!ZonesSelected(this)) {
   JS::PrepareForFullGC(rt->mainContextFromOwnThread());
 }

 collect(false, budget, JS::GCReason::DEBUG_GC);
}

void GCRuntime::debugGCSlice(const SliceBudget& budget) {
 MOZ_ASSERT(isIncrementalGCInProgress());

 if (!ZonesSelected(this)) {
   JS::PrepareForIncrementalGC(rt->mainContextFromOwnThread());
 }

 collect(false, budget, JS::GCReason::DEBUG_GC);
}

void js::PrepareForDebugGC(JSRuntime* rt) {
 // If zones have already been scheduled then use them.
 if (ZonesSelected(&rt->gc)) {
   return;
 }

 // If we already started a GC then continue with the same set of zones. This
 // prevents resetting an ongoing GC when new zones are added.
 JSContext* cx = rt->mainContextFromOwnThread();
 if (JS::IsIncrementalGCInProgress(cx)) {
   JS::PrepareForIncrementalGC(cx);
   return;
 }

 // Otherwise schedule all zones.
 JS::PrepareForFullGC(rt->mainContextFromOwnThread());
}

void GCRuntime::onOutOfMallocMemory() {
 // Stop allocating new chunks.
 allocTask.cancelAndWait();

 // Make sure we release anything queued for release.
 decommitTask.join();
 nursery().joinDecommitTask();

 // Wait for background free of nursery huge slots to finish.
 sweepTask.join();

 AutoLockGC lock(this);
 onOutOfMallocMemory(lock);
}

void GCRuntime::onOutOfMallocMemory(const AutoLockGC& lock) {
#ifdef DEBUG
 // Release any relocated arenas we may be holding on to, without releasing
 // the GC lock.
 releaseHeldRelocatedArenasWithoutUnlocking(lock);
#endif

 // Throw away any excess chunks we have lying around.
 freeEmptyChunks(lock);

 // Immediately decommit as many arenas as possible in the hopes that this
 // might let the OS scrape together enough pages to satisfy the failing
 // malloc request.
 if (DecommitEnabled()) {
   decommitFreeArenasWithoutUnlocking(lock);
 }
}

void GCRuntime::minorGC(JS::GCReason reason, gcstats::PhaseKind phase) {
 MOZ_ASSERT(!JS::RuntimeHeapIsBusy());

 MOZ_ASSERT_IF(reason == JS::GCReason::EVICT_NURSERY,
               !rt->mainContextFromOwnThread()->suppressGC);
 if (rt->mainContextFromOwnThread()->suppressGC) {
   return;
 }

 incGcNumber();

 collectNursery(JS::GCOptions::Normal, reason, phase);

#ifdef JS_GC_ZEAL
 if (hasZealMode(ZealMode::CheckHeapAfterGC)) {
   gcstats::AutoPhase ap(stats(), phase);
   waitBackgroundSweepEnd();
   waitBackgroundDecommitEnd();
   CheckHeapAfterGC(rt);
 }
#endif

 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   maybeTriggerGCAfterAlloc(zone);
   maybeTriggerGCAfterMalloc(zone);
 }
}

void GCRuntime::collectNursery(JS::GCOptions options, JS::GCReason reason,
                              gcstats::PhaseKind phase) {
 AutoMaybeLeaveAtomsZone leaveAtomsZone(rt->mainContextFromOwnThread());

 uint32_t numAllocs = 0;
 for (ZonesIter zone(this, WithAtoms); !zone.done(); zone.next()) {
   numAllocs += zone->getAndResetTenuredAllocsSinceMinorGC();
 }
 stats().setAllocsSinceMinorGCTenured(numAllocs);

 gcstats::AutoPhase ap(stats(), phase);

 nursery().collect(options, reason);

 startBackgroundFreeAfterMinorGC();

 // We ignore gcMaxBytes when allocating for minor collection. However, if we
 // overflowed, we disable the nursery. The next time we allocate, we'll fail
 // because bytes >= gcMaxBytes.
 if (heapSize.bytes() >= tunables.gcMaxBytes()) {
   if (!nursery().isEmpty()) {
     nursery().collect(options, JS::GCReason::DISABLE_GENERATIONAL_GC);
     MOZ_ASSERT(nursery().isEmpty());
     startBackgroundFreeAfterMinorGC();
   }

   // Disabling the nursery triggers pre-barriers when we discard JIT
   // code. Normally we don't allow any barriers in a major GC and there is an
   // assertion to check this in PreWriteBarrier. For the case where we disable
   // the nursery during a major GC, set up a minor GC session to silence the
   // assertion.
   AutoGCSession session(this, JS::HeapState::MinorCollecting);

   nursery().disable();
 }
}

void GCRuntime::startBackgroundFreeAfterMinorGC() {
 // Called after nursery collection. Free whatever blocks are safe to free now.

 AutoLockHelperThreadState lock;

 lifoBlocksToFree.ref().transferFrom(&lifoBlocksToFreeAfterNextMinorGC.ref());

 if (nursery().tenuredEverything) {
   lifoBlocksToFree.ref().transferFrom(
       &lifoBlocksToFreeAfterFullMinorGC.ref());
 } else {
   lifoBlocksToFreeAfterNextMinorGC.ref().transferFrom(
       &lifoBlocksToFreeAfterFullMinorGC.ref());
 }

 if (!hasBuffersForBackgroundFree()) {
   return;
 }

 freeTask.startOrRunIfIdle(lock);
}

bool GCRuntime::gcIfRequestedImpl(bool eagerOk) {
 // This method returns whether a major GC was performed.

 if (nursery().minorGCRequested()) {
   minorGC(nursery().minorGCTriggerReason());
 }

 JS::GCReason reason = wantMajorGC(eagerOk);
 if (reason == JS::GCReason::NO_REASON) {
   return false;
 }

 SliceBudget budget = defaultBudget(reason, 0);
 if (!isIncrementalGCInProgress()) {
   startGC(JS::GCOptions::Normal, reason, budget);
 } else {
   gcSlice(reason, budget);
 }
 return true;
}

void js::gc::FinishGC(JSContext* cx, JS::GCReason reason) {
 // Calling this when GC is suppressed won't have any effect.
 MOZ_ASSERT(!cx->suppressGC);

 // GC callbacks may run arbitrary code, including JS. Check this regardless of
 // whether we GC for this invocation.
 MOZ_ASSERT(cx->isNurseryAllocAllowed());

 if (JS::IsIncrementalGCInProgress(cx)) {
   JS::PrepareForIncrementalGC(cx);
   JS::FinishIncrementalGC(cx, reason);
 }
}

void js::gc::WaitForBackgroundTasks(JSContext* cx) {
 cx->runtime()->gc.waitForBackgroundTasks();
}

void GCRuntime::waitForBackgroundTasks() {
 MOZ_ASSERT(!isIncrementalGCInProgress());
 MOZ_ASSERT(sweepTask.isIdle());
 MOZ_ASSERT(decommitTask.isIdle());
 MOZ_ASSERT(markTask.isIdle());

 allocTask.join();
 freeTask.join();
 nursery().joinDecommitTask();
}

Realm* js::NewRealm(JSContext* cx, JSPrincipals* principals,
                   const JS::RealmOptions& options) {
 JSRuntime* rt = cx->runtime();
 JS_AbortIfWrongThread(cx);

 UniquePtr<Zone> zoneHolder;
 UniquePtr<Compartment> compHolder;

 Compartment* comp = nullptr;
 Zone* zone = nullptr;
 JS::CompartmentSpecifier compSpec =
     options.creationOptions().compartmentSpecifier();
 switch (compSpec) {
   case JS::CompartmentSpecifier::NewCompartmentInSystemZone:
     // systemZone might be null here, in which case we'll make a zone and
     // set this field below.
     zone = rt->gc.systemZone;
     break;
   case JS::CompartmentSpecifier::NewCompartmentInExistingZone:
     zone = options.creationOptions().zone();
     MOZ_ASSERT(zone);
     break;
   case JS::CompartmentSpecifier::ExistingCompartment:
     comp = options.creationOptions().compartment();
     zone = comp->zone();
     break;
   case JS::CompartmentSpecifier::NewCompartmentAndZone:
     break;
 }

 if (!zone) {
   Zone::Kind kind = Zone::NormalZone;
   const JSPrincipals* trusted = rt->trustedPrincipals();
   if (compSpec == JS::CompartmentSpecifier::NewCompartmentInSystemZone ||
       (principals && principals == trusted)) {
     kind = Zone::SystemZone;
   }

   zoneHolder = MakeUnique<Zone>(cx->runtime(), kind);
   if (!zoneHolder || !zoneHolder->init()) {
     ReportOutOfMemory(cx);
     return nullptr;
   }

   zone = zoneHolder.get();
 }

 bool invisibleToDebugger = options.creationOptions().invisibleToDebugger();
 if (comp) {
   // Debugger visibility is per-compartment, not per-realm, so make sure the
   // new realm's visibility matches its compartment's.
   MOZ_ASSERT(comp->invisibleToDebugger() == invisibleToDebugger);
 } else {
   compHolder = cx->make_unique<JS::Compartment>(zone, invisibleToDebugger);
   if (!compHolder) {
     return nullptr;
   }

   comp = compHolder.get();
 }

 UniquePtr<Realm> realm(cx->new_<Realm>(comp, options));
 if (!realm) {
   return nullptr;
 }
 realm->init(cx, principals);

 // Make sure we don't put system and non-system realms in the same
 // compartment.
 if (!compHolder) {
   MOZ_RELEASE_ASSERT(realm->isSystem() == IsSystemCompartment(comp));
 }

 AutoLockGC lock(rt);

 // Reserve space in the Vectors before we start mutating them.
 if (!comp->realms().reserve(comp->realms().length() + 1) ||
     (compHolder &&
      !zone->compartments().reserve(zone->compartments().length() + 1)) ||
     (zoneHolder && !rt->gc.zones().reserve(rt->gc.zones().length() + 1))) {
   ReportOutOfMemory(cx);
   return nullptr;
 }

 // After this everything must be infallible.

 comp->realms().infallibleAppend(realm.get());

 if (compHolder) {
   zone->compartments().infallibleAppend(compHolder.release());
 }

 if (zoneHolder) {
   rt->gc.zones().infallibleAppend(zoneHolder.release());

   // Lazily set the runtime's system zone.
   if (compSpec == JS::CompartmentSpecifier::NewCompartmentInSystemZone) {
     MOZ_RELEASE_ASSERT(!rt->gc.systemZone);
     MOZ_ASSERT(zone->isSystemZone());
     rt->gc.systemZone = zone;
   }
 }

 return realm.release();
}

void GCRuntime::runDebugGC() {
#ifdef JS_GC_ZEAL
 if (rt->mainContextFromOwnThread()->suppressGC) {
   return;
 }

 if (hasZealMode(ZealMode::VerifierPost) ||
     hasZealMode(ZealMode::GenerationalGC)) {
   return minorGC(JS::GCReason::DEBUG_GC);
 }

 PrepareForDebugGC(rt);

 auto budget = SliceBudget::unlimited();
 if (hasZealMode(ZealMode::IncrementalMultipleSlices)) {
   /*
    * Start with a small slice limit and double it every slice. This
    * ensure that we get multiple slices, and collection runs to
    * completion.
    */
   if (!isIncrementalGCInProgress()) {
     zealSliceBudget = zealFrequency / 2;
   } else {
     zealSliceBudget *= 2;
   }
   budget = SliceBudget(WorkBudget(zealSliceBudget));

   js::gc::State initialState = incrementalState;
   if (!isIncrementalGCInProgress()) {
     setGCOptions(JS::GCOptions::Shrink);
   }
   collect(false, budget, JS::GCReason::DEBUG_GC);

   /* Reset the slice size when we get to the sweep or compact phases. */
   if ((initialState == State::Mark && incrementalState == State::Sweep) ||
       (initialState == State::Sweep && incrementalState == State::Compact)) {
     zealSliceBudget = zealFrequency / 2;
   }
 } else if (zealModeControlsYieldPoint()) {
   // These modes trigger incremental GC that happens in two slices and the
   // supplied budget is ignored by incrementalSlice.
   budget = SliceBudget(WorkBudget(1));

   if (!isIncrementalGCInProgress()) {
     setGCOptions(JS::GCOptions::Normal);
   }
   collect(false, budget, JS::GCReason::DEBUG_GC);
 } else if (hasZealMode(ZealMode::Compact)) {
   gc(JS::GCOptions::Shrink, JS::GCReason::DEBUG_GC);
 } else {
   gc(JS::GCOptions::Normal, JS::GCReason::DEBUG_GC);
 }

#endif
}

void GCRuntime::setFullCompartmentChecks(bool enabled) {
 MOZ_ASSERT(!JS::RuntimeHeapIsMajorCollecting());
 fullCompartmentChecks = enabled;
}

void GCRuntime::notifyRootsRemoved() {
 rootsRemoved = true;

#ifdef JS_GC_ZEAL
 /* Schedule a GC to happen "soon". */
 if (hasZealMode(ZealMode::RootsChange)) {
   nextScheduled = 1;
 }
#endif
}

#ifdef JS_GC_ZEAL
bool GCRuntime::selectForMarking(JSObject* object) {
 MOZ_ASSERT(!JS::RuntimeHeapIsMajorCollecting());
 return selectedForMarking.ref().get().append(object);
}

void GCRuntime::clearSelectedForMarking() {
 selectedForMarking.ref().get().clearAndFree();
}

void GCRuntime::setDeterministic(bool enabled) {
 MOZ_ASSERT(!JS::RuntimeHeapIsMajorCollecting());
 deterministicOnly = enabled;
}
#endif

#ifdef DEBUG

AutoAssertNoNurseryAlloc::AutoAssertNoNurseryAlloc() {
 TlsContext.get()->disallowNurseryAlloc();
}

AutoAssertNoNurseryAlloc::~AutoAssertNoNurseryAlloc() {
 TlsContext.get()->allowNurseryAlloc();
}

#endif  // DEBUG

#ifdef JSGC_HASH_TABLE_CHECKS
void GCRuntime::checkHashTablesAfterMovingGC() {
 waitBackgroundSweepEnd();
 waitBackgroundDecommitEnd();

 /*
  * Check that internal hash tables no longer have any pointers to things
  * that have been moved.
  */
 rt->geckoProfiler().checkStringsMapAfterMovingGC();
 if (rt->hasJitRuntime() && rt->jitRuntime()->hasInterpreterEntryMap()) {
   rt->jitRuntime()->getInterpreterEntryMap()->checkScriptsAfterMovingGC();
 }
 for (ZonesIter zone(this, SkipAtoms); !zone.done(); zone.next()) {
   zone->checkUniqueIdTableAfterMovingGC();
   zone->shapeZone().checkTablesAfterMovingGC(zone);
   zone->checkAllCrossCompartmentWrappersAfterMovingGC();
   zone->checkScriptMapsAfterMovingGC();

   // Note: CompactPropMaps never have a table.
   JS::AutoCheckCannotGC nogc;
   for (auto map = zone->cellIterUnsafe<NormalPropMap>(); !map.done();
        map.next()) {
     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
       table->checkAfterMovingGC(zone);
     }
   }
   for (auto map = zone->cellIterUnsafe<DictionaryPropMap>(); !map.done();
        map.next()) {
     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
       table->checkAfterMovingGC(zone);
     }
   }

   WeakMapBase::checkWeakMapsAfterMovingGC(zone);
 }

 for (CompartmentsIter c(this); !c.done(); c.next()) {
   for (RealmsInCompartmentIter r(c); !r.done(); r.next()) {
     r->dtoaCache.checkCacheAfterMovingGC();
     if (r->debugEnvs()) {
       r->debugEnvs()->checkHashTablesAfterMovingGC();
     }
   }
 }
}
#endif

#ifdef DEBUG
bool GCRuntime::hasZone(Zone* target) {
 for (AllZonesIter zone(this); !zone.done(); zone.next()) {
   if (zone == target) {
     return true;
   }
 }
 return false;
}
#endif

void AutoAssertEmptyNursery::checkCondition(JSContext* cx) {
 if (!noAlloc) {
   noAlloc.emplace();
 }
 this->cx = cx;
 MOZ_ASSERT(cx->nursery().isEmpty());
}

AutoEmptyNursery::AutoEmptyNursery(JSContext* cx) {
 MOZ_ASSERT(!cx->suppressGC);
 cx->runtime()->gc.stats().suspendPhases();
 cx->runtime()->gc.evictNursery(JS::GCReason::EVICT_NURSERY);
 cx->runtime()->gc.stats().resumePhases();
 checkCondition(cx);
}

#ifdef DEBUG

namespace js {

// We don't want jsfriendapi.h to depend on GenericPrinter,
// so these functions are declared directly in the cpp.

extern JS_PUBLIC_API void DumpString(JSString* str, js::GenericPrinter& out);

}  // namespace js

void js::gc::Cell::dump(js::GenericPrinter& out) const {
 switch (getTraceKind()) {
   case JS::TraceKind::Object:
     reinterpret_cast<const JSObject*>(this)->dump(out);
     break;

   case JS::TraceKind::String:
     js::DumpString(reinterpret_cast<JSString*>(const_cast<Cell*>(this)), out);
     break;

   case JS::TraceKind::Shape:
     reinterpret_cast<const Shape*>(this)->dump(out);
     break;

   default:
     out.printf("%s(%p)\n", JS::GCTraceKindToAscii(getTraceKind()),
                (void*)this);
 }
}

// For use in a debugger.
void js::gc::Cell::dump() const {
 js::Fprinter out(stderr);
 dump(out);
}
#endif

JS_PUBLIC_API bool js::gc::detail::CanCheckGrayBits(const TenuredCell* cell) {
 // We do not check the gray marking state of cells in the following cases:
 //
 // 1) When OOM has caused us to clear the gcGrayBitsValid_ flag.
 //
 // 2) When we are in an incremental GC and examine a cell that is in a zone
 // that is not being collected. Gray targets of CCWs that are marked black
 // by a barrier will eventually be marked black in a later GC slice.
 //
 // 3) When mark bits are being cleared concurrently by a helper thread.

 MOZ_ASSERT(cell);

 JS::Zone* zone = cell->zoneFromAnyThread();
 if (zone->isAtomsZone() && cell->isMarkedBlack()) {
   // This could be a shared atom in the parent runtime. Skip this check.
   return true;
 }

 auto* runtime = cell->runtimeFromAnyThread();
 MOZ_ASSERT(CurrentThreadCanAccessRuntime(runtime));

 if (!runtime->gc.areGrayBitsValid()) {
   return false;
 }

 if (runtime->gc.isIncrementalGCInProgress() && !zone->wasGCStarted()) {
   return false;
 }

 return !zone->isGCPreparing();
}

JS_PUBLIC_API bool js::gc::detail::CellIsMarkedGrayIfKnown(
   const TenuredCell* cell) {
 MOZ_ASSERT_IF(cell->isPermanentAndMayBeShared(), cell->isMarkedBlack());
 if (!cell->isMarkedGray()) {
   return false;
 }

 return CanCheckGrayBits(cell);
}

#ifdef DEBUG

JS_PUBLIC_API void js::gc::detail::AssertCellIsNotGray(const Cell* cell) {
 if (!cell->isTenured()) {
   return;
 }

 // Check that a cell is not marked gray.
 //
 // Since this is a debug-only check, take account of the eventual mark state
 // of cells that will be marked black by the next GC slice in an incremental
 // GC. For performance reasons we don't do this in CellIsMarkedGrayIfKnown.

 const auto* tc = &cell->asTenured();
 if (!tc->isMarkedGray() || !CanCheckGrayBits(tc)) {
   return;
 }

 // TODO: I'd like to AssertHeapIsIdle() here, but this ends up getting
 // called during GC and while iterating the heap for memory reporting.
 MOZ_ASSERT(!JS::RuntimeHeapIsCycleCollecting());

 Zone* zone = tc->zone();
 if (zone->isGCMarkingBlackAndGray()) {
   // We are doing gray marking in the cell's zone. Even if the cell is
   // currently marked gray it may eventually be marked black. Delay checking
   // non-black cells until we finish gray marking.

   if (!tc->isMarkedBlack()) {
     AutoEnterOOMUnsafeRegion oomUnsafe;
     if (!zone->cellsToAssertNotGray().append(cell)) {
       oomUnsafe.crash("Can't append to delayed gray checks list");
     }
   }
   return;
 }

 MOZ_ASSERT(!tc->isMarkedGray());
}

extern JS_PUBLIC_API bool js::gc::detail::ObjectIsMarkedBlack(
   const JSObject* obj) {
 return obj->isMarkedBlack();
}

#endif

js::gc::ClearEdgesTracer::ClearEdgesTracer(JSRuntime* rt)
   : GenericTracerImpl(rt, JS::TracerKind::ClearEdges,
                       JS::WeakMapTraceAction::TraceKeysAndValues) {}

template <typename T>
void js::gc::ClearEdgesTracer::onEdge(T** thingp, const char* name) {
 // We don't handle removing pointers to nursery edges from the store buffer
 // with this tracer. Check that this doesn't happen.
 T* thing = *thingp;
 MOZ_ASSERT(!IsInsideNursery(thing));

 // Fire the pre-barrier since we're removing an edge from the graph.
 InternalBarrierMethods<T*>::preBarrier(thing);

 *thingp = nullptr;
}

void GCRuntime::setPerformanceHint(PerformanceHint hint) {
 if (hint == PerformanceHint::InPageLoad) {
   inPageLoadCount++;
 } else {
   MOZ_ASSERT(inPageLoadCount);
   inPageLoadCount--;
 }
}