src/third_party/mozjs-45/js/src/gc/Zone.h - cobalt - Git at Google

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #ifndef gc_Zone_h
 #define gc_Zone_h

 #include "mozilla/Atomics.h"
 #include "mozilla/DebugOnly.h"
 #include "mozilla/MemoryReporting.h"

 #include "jscntxt.h"

 #include "ds/SplayTree.h"
 #include "gc/FindSCCs.h"
 #include "gc/GCRuntime.h"
 #include "js/GCHashTable.h"
 #include "js/TracingAPI.h"
 #include "vm/MallocProvider.h"
 #include "vm/TypeInference.h"

 namespace js {

 namespace jit {
 class JitZone;
 } // namespace jit

 namespace gc {

 // This class encapsulates the data that determines when we need to do a zone GC.
 class ZoneHeapThreshold
 {
     // The "growth factor" for computing our next thresholds after a GC.
     double gcHeapGrowthFactor_;

     // GC trigger threshold for allocations on the GC heap.
     size_t gcTriggerBytes_;

   public:
     ZoneHeapThreshold()
       : gcHeapGrowthFactor_(3.0),
         gcTriggerBytes_(0)
     {}

     double gcHeapGrowthFactor() const { return gcHeapGrowthFactor_; }
     size_t gcTriggerBytes() const { return gcTriggerBytes_; }
     double allocTrigger(bool highFrequencyGC) const;

     void updateAfterGC(size_t lastBytes, JSGCInvocationKind gckind,
                        const GCSchedulingTunables& tunables, const GCSchedulingState& state,
                        const AutoLockGC& lock);
     void updateForRemovedArena(const GCSchedulingTunables& tunables);

   private:
     static double computeZoneHeapGrowthFactorForHeapSize(size_t lastBytes,
                                                          const GCSchedulingTunables& tunables,
                                                          const GCSchedulingState& state);
     static size_t computeZoneTriggerBytes(double growthFactor, size_t lastBytes,
                                           JSGCInvocationKind gckind,
                                           const GCSchedulingTunables& tunables,
                                           const AutoLockGC& lock);
 };

 struct UniqueIdGCPolicy {
     static bool needsSweep(Cell** cell, uint64_t* value);
 };

 // Maps a Cell* to a unique, 64bit id.
 using UniqueIdMap = GCHashMap<Cell*,
                               uint64_t,
                               PointerHasher<Cell*, 3>,
                               SystemAllocPolicy,
                               UniqueIdGCPolicy>;

 extern uint64_t NextCellUniqueId(JSRuntime* rt);

 } // namespace gc
 } // namespace js

 namespace JS {

 // A zone is a collection of compartments. Every compartment belongs to exactly
 // one zone. In Firefox, there is roughly one zone per tab along with a system
 // zone for everything else. Zones mainly serve as boundaries for garbage
 // collection. Unlike compartments, they have no special security properties.
 //
 // Every GC thing belongs to exactly one zone. GC things from the same zone but
 // different compartments can share an arena (4k page). GC things from different
 // zones cannot be stored in the same arena. The garbage collector is capable of
 // collecting one zone at a time; it cannot collect at the granularity of
 // compartments.
 //
 // GC things are tied to zones and compartments as follows:
 //
 // - JSObjects belong to a compartment and cannot be shared between
 //   compartments. If an object needs to point to a JSObject in a different
 //   compartment, regardless of zone, it must go through a cross-compartment
 //   wrapper. Each compartment keeps track of its outgoing wrappers in a table.
 //
 // - JSStrings do not belong to any particular compartment, but they do belong
 //   to a zone. Thus, two different compartments in the same zone can point to a
 //   JSString. When a string needs to be wrapped, we copy it if it's in a
 //   different zone and do nothing if it's in the same zone. Thus, transferring
 //   strings within a zone is very efficient.
 //
 // - Shapes and base shapes belong to a compartment and cannot be shared between
 //   compartments. A base shape holds a pointer to its compartment. Shapes find
 //   their compartment via their base shape. JSObjects find their compartment
 //   via their shape.
 //
 // - Scripts are also compartment-local and cannot be shared. A script points to
 //   its compartment.
 //
 // - Type objects and JitCode objects belong to a compartment and cannot be
 //   shared. However, there is no mechanism to obtain their compartments.
 //
 // A zone remains alive as long as any GC things in the zone are alive. A
 // compartment remains alive as long as any JSObjects, scripts, shapes, or base
 // shapes within it are alive.
 //
 // We always guarantee that a zone has at least one live compartment by refusing
 // to delete the last compartment in a live zone.
 struct Zone : public JS::shadow::Zone,
               public js::gc::GraphNodeBase<JS::Zone>,
               public js::MallocProvider<JS::Zone>
 {
     explicit Zone(JSRuntime* rt);
     ~Zone();
     bool init(bool isSystem);

     void findOutgoingEdges(js::gc::ComponentFinder<JS::Zone>& finder);

     void discardJitCode(js::FreeOp* fop);

     void addSizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf,
                                 size_t* typePool,
                                 size_t* baselineStubsOptimized,
                                 size_t* uniqueIdMap);

     void resetGCMallocBytes();
     void setGCMaxMallocBytes(size_t value);
     void updateMallocCounter(size_t nbytes) {
         // Note: this code may be run from worker threads. We tolerate any
         // thread races when updating gcMallocBytes.
         gcMallocBytes -= ptrdiff_t(nbytes);
         if (MOZ_UNLIKELY(isTooMuchMalloc()))
             onTooMuchMalloc();
     }

     bool isTooMuchMalloc() const { return gcMallocBytes <= 0; }
     void onTooMuchMalloc();

     void* onOutOfMemory(js::AllocFunction allocFunc, size_t nbytes, void* reallocPtr = nullptr) {
         if (!js::CurrentThreadCanAccessRuntime(runtime_))
             return nullptr;
         return runtimeFromMainThread()->onOutOfMemory(allocFunc, nbytes, reallocPtr);
     }
     void reportAllocationOverflow() { js::ReportAllocationOverflow(nullptr); }

     void beginSweepTypes(js::FreeOp* fop, bool releaseTypes);

     bool hasMarkedCompartments();

     void scheduleGC() { MOZ_ASSERT(!runtimeFromMainThread()->isHeapBusy()); gcScheduled_ = true; }
     void unscheduleGC() { gcScheduled_ = false; }
     bool isGCScheduled() { return gcScheduled_ && canCollect(); }

     void setPreservingCode(bool preserving) { gcPreserveCode_ = preserving; }
     bool isPreservingCode() const { return gcPreserveCode_; }

     bool canCollect();

     void notifyObservingDebuggers();

     enum GCState {
         NoGC,
         Mark,
         MarkGray,
         Sweep,
         Finished,
         Compact
     };
     void setGCState(GCState state) {
         MOZ_ASSERT(runtimeFromMainThread()->isHeapBusy());
         MOZ_ASSERT_IF(state != NoGC, canCollect());
         gcState_ = state;
         if (state == Finished)
             notifyObservingDebuggers();
     }

     bool isCollecting() const {
         if (runtimeFromMainThread()->isHeapCollecting())
             return gcState_ != NoGC;
         else
             return needsIncrementalBarrier();
     }

     bool isCollectingFromAnyThread() const {
         if (runtimeFromAnyThread()->isHeapCollecting())
             return gcState_ != NoGC;
         else
             return needsIncrementalBarrier();
     }

     // If this returns true, all object tracing must be done with a GC marking
     // tracer.
     bool requireGCTracer() const {
         JSRuntime* rt = runtimeFromAnyThread();
         return rt->isHeapMajorCollecting() && !rt->gc.isHeapCompacting() && gcState_ != NoGC;
     }

     bool isGCMarking() {
         if (runtimeFromMainThread()->isHeapCollecting())
             return gcState_ == Mark || gcState_ == MarkGray;
         else
             return needsIncrementalBarrier();
     }

     bool wasGCStarted() const { return gcState_ != NoGC; }
     bool isGCMarkingBlack() { return gcState_ == Mark; }
     bool isGCMarkingGray() { return gcState_ == MarkGray; }
     bool isGCSweeping() { return gcState_ == Sweep; }
     bool isGCFinished() { return gcState_ == Finished; }
     bool isGCCompacting() { return gcState_ == Compact; }
     bool isGCSweepingOrCompacting() { return gcState_ == Sweep || gcState_ == Compact; }

     // Get a number that is incremented whenever this zone is collected, and
     // possibly at other times too.
     uint64_t gcNumber();

     bool compileBarriers() const { return compileBarriers(needsIncrementalBarrier()); }
     bool compileBarriers(bool needsIncrementalBarrier) const {
         return needsIncrementalBarrier ||
                runtimeFromMainThread()->gcZeal() == js::gc::ZealVerifierPreValue;
     }

     enum ShouldUpdateJit { DontUpdateJit, UpdateJit };
     void setNeedsIncrementalBarrier(bool needs, ShouldUpdateJit updateJit);
     const bool* addressOfNeedsIncrementalBarrier() const { return &needsIncrementalBarrier_; }

     js::jit::JitZone* getJitZone(JSContext* cx) { return jitZone_ ? jitZone_ : createJitZone(cx); }
     js::jit::JitZone* jitZone() { return jitZone_; }

     bool isAtomsZone() const { return runtimeFromAnyThread()->isAtomsZone(this); }
     bool isSelfHostingZone() const { return runtimeFromAnyThread()->isSelfHostingZone(this); }

     void prepareForCompacting();

 #ifdef DEBUG
     // For testing purposes, return the index of the zone group which this zone
     // was swept in in the last GC.
     unsigned lastZoneGroupIndex() { return gcLastZoneGroupIndex; }
 #endif

     using DebuggerVector = js::Vector<js::Debugger*, 0, js::SystemAllocPolicy>;

   private:
     DebuggerVector* debuggers;

     using LogTenurePromotionQueue = js::Vector<JSObject*, 0, js::SystemAllocPolicy>;
     LogTenurePromotionQueue awaitingTenureLogging;

     void sweepBreakpoints(js::FreeOp* fop);
     void sweepUniqueIds(js::FreeOp* fop);
     void sweepWeakMaps();
     void sweepCompartments(js::FreeOp* fop, bool keepAtleastOne, bool lastGC);

     js::jit::JitZone* createJitZone(JSContext* cx);

     bool isQueuedForBackgroundSweep() {
         return isOnList();
     }

     // Side map for storing a unique ids for cells, independent of address.
     js::gc::UniqueIdMap uniqueIds_;

   public:
     bool hasDebuggers() const { return debuggers && debuggers->length(); }
     DebuggerVector* getDebuggers() const { return debuggers; }
     DebuggerVector* getOrCreateDebuggers(JSContext* cx);

     void enqueueForPromotionToTenuredLogging(JSObject& obj) {
         MOZ_ASSERT(hasDebuggers());
         MOZ_ASSERT(!IsInsideNursery(&obj));
         js::AutoEnterOOMUnsafeRegion oomUnsafe;
         if (!awaitingTenureLogging.append(&obj))
             oomUnsafe.crash("Zone::enqueueForPromotionToTenuredLogging");
     }
     void logPromotionsToTenured();

     js::gc::ArenaLists arenas;

     js::TypeZone types;

     /* Live weakmaps in this zone. */
     mozilla::LinkedList<js::WeakMapBase> gcWeakMapList;

     // The set of compartments in this zone.
     typedef js::Vector<JSCompartment*, 1, js::SystemAllocPolicy> CompartmentVector;
     CompartmentVector compartments;

     // This zone's gray roots.
     typedef js::Vector<js::gc::Cell*, 0, js::SystemAllocPolicy> GrayRootVector;
     GrayRootVector gcGrayRoots;

     // This zone's weak edges found via graph traversal during marking,
     // preserved for re-scanning during sweeping.
     using WeakEdges = js::Vector<js::gc::TenuredCell**, 0, js::SystemAllocPolicy>;
     WeakEdges gcWeakRefs;

     /*
      * Mapping from not yet marked keys to a vector of all values that the key
      * maps to in any live weak map.
      */
     js::gc::WeakKeyTable gcWeakKeys;

     // A set of edges from this zone to other zones.
     //
     // This is used during GC while calculating zone groups to record edges that
     // can't be determined by examining this zone by itself.
     ZoneSet gcZoneGroupEdges;

     // Malloc counter to measure memory pressure for GC scheduling. It runs from
     // gcMaxMallocBytes down to zero. This counter should be used only when it's
     // not possible to know the size of a free.
     mozilla::Atomic<ptrdiff_t, mozilla::ReleaseAcquire> gcMallocBytes;

     // GC trigger threshold for allocations on the C heap.
     size_t gcMaxMallocBytes;

     // Whether a GC has been triggered as a result of gcMallocBytes falling
     // below zero.
     //
     // This should be a bool, but Atomic only supports 32-bit and pointer-sized
     // types.
     mozilla::Atomic<uint32_t, mozilla::ReleaseAcquire> gcMallocGCTriggered;

     // Track heap usage under this Zone.
     js::gc::HeapUsage usage;

     // Thresholds used to trigger GC.
     js::gc::ZoneHeapThreshold threshold;

     // Amount of data to allocate before triggering a new incremental slice for
     // the current GC.
     size_t gcDelayBytes;

     // Per-zone data for use by an embedder.
     void* data;

     bool isSystem;

     bool usedByExclusiveThread;

     // True when there are active frames.
     bool active;

     mozilla::DebugOnly<unsigned> gcLastZoneGroupIndex;

     // Creates a HashNumber based on getUniqueId. Returns false on OOM.
     bool getHashCode(js::gc::Cell* cell, js::HashNumber* hashp) {
         uint64_t uid;
         if (!getUniqueId(cell, &uid))
             return false;
         *hashp = js::HashNumber(uid >> 32) ^ js::HashNumber(uid & 0xFFFFFFFF);
         return true;
     }

     // Puts an existing UID in |uidp|, or creates a new UID for this Cell and
     // puts that into |uidp|. Returns false on OOM.
     bool getUniqueId(js::gc::Cell* cell, uint64_t* uidp) {
         MOZ_ASSERT(uidp);
         MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));

         // Get an existing uid, if one has been set.
         auto p = uniqueIds_.lookupForAdd(cell);
         if (p) {
             *uidp = p->value();
             return true;
         }

         // Set a new uid on the cell.
         *uidp = js::gc::NextCellUniqueId(runtimeFromAnyThread());
         if (!uniqueIds_.add(p, cell, *uidp))
             return false;

         // If the cell was in the nursery, hopefully unlikely, then we need to
         // tell the nursery about it so that it can sweep the uid if the thing
         // does not get tenured.
         js::AutoEnterOOMUnsafeRegion oomUnsafe;
         if (!runtimeFromAnyThread()->gc.nursery.addedUniqueIdToCell(cell))
             oomUnsafe.crash("failed to allocate tracking data for a nursery uid");
         return true;
     }

     // Return true if this cell has a UID associated with it.
     bool hasUniqueId(js::gc::Cell* cell) {
         MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));
         return uniqueIds_.has(cell);
     }

     // Transfer an id from another cell. This must only be called on behalf of a
     // moving GC. This method is infallible.
     void transferUniqueId(js::gc::Cell* tgt, js::gc::Cell* src) {
         MOZ_ASSERT(src != tgt);
         MOZ_ASSERT(!IsInsideNursery(tgt));
         MOZ_ASSERT(CurrentThreadCanAccessRuntime(runtimeFromMainThread()));
         MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));
         uniqueIds_.rekeyIfMoved(src, tgt);
     }

     // Remove any unique id associated with this Cell.
     void removeUniqueId(js::gc::Cell* cell) {
         MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));
         uniqueIds_.remove(cell);
     }

     // Off-thread parsing should not result in any UIDs being created.
     void assertNoUniqueIdsInZone() const {
         MOZ_ASSERT(uniqueIds_.count() == 0);
     }

 #ifdef JSGC_HASH_TABLE_CHECKS
     // Assert that the UniqueId table has been redirected successfully.
     void checkUniqueIdTableAfterMovingGC();
 #endif

   private:
     js::jit::JitZone* jitZone_;

     GCState gcState_;
     bool gcScheduled_;
     bool gcPreserveCode_;
     bool jitUsingBarriers_;

     // Allow zones to be linked into a list
     friend class js::gc::ZoneList;
     static Zone * const NotOnList;
     Zone* listNext_;
     bool isOnList() const;
     Zone* nextZone() const;

     friend bool js::CurrentThreadCanAccessZone(Zone* zone);
     friend class js::gc::GCRuntime;
 };

 } // namespace JS

 namespace js {

 // Using the atoms zone without holding the exclusive access lock is dangerous
 // because worker threads may be using it simultaneously. Therefore, it's
 // better to skip the atoms zone when iterating over zones. If you need to
 // iterate over the atoms zone, consider taking the exclusive access lock first.
 enum ZoneSelector {
     WithAtoms,
     SkipAtoms
 };

 class ZonesIter
 {
     gc::AutoEnterIteration iterMarker;
     JS::Zone** it;
     JS::Zone** end;

   public:
     ZonesIter(JSRuntime* rt, ZoneSelector selector) : iterMarker(&rt->gc) {
         it = rt->gc.zones.begin();
         end = rt->gc.zones.end();

         if (selector == SkipAtoms) {
             MOZ_ASSERT(atAtomsZone(rt));
             it++;
         }
     }

     bool atAtomsZone(JSRuntime* rt);

     bool done() const { return it == end; }

     void next() {
         MOZ_ASSERT(!done());
         do {
             it++;
         } while (!done() && (*it)->usedByExclusiveThread);
     }

     JS::Zone* get() const {
         MOZ_ASSERT(!done());
         return *it;
     }

     operator JS::Zone*() const { return get(); }
     JS::Zone* operator->() const { return get(); }
 };

 struct CompartmentsInZoneIter
 {
     explicit CompartmentsInZoneIter(JS::Zone* zone) : zone(zone) {
         it = zone->compartments.begin();
     }

     bool done() const {
         MOZ_ASSERT(it);
         return it < zone->compartments.begin() ||
                it >= zone->compartments.end();
     }
     void next() {
         MOZ_ASSERT(!done());
         it++;
     }

     JSCompartment* get() const {
         MOZ_ASSERT(it);
         return *it;
     }

     operator JSCompartment*() const { return get(); }
     JSCompartment* operator->() const { return get(); }

   private:
     JS::Zone* zone;
     JSCompartment** it;

     CompartmentsInZoneIter()
       : zone(nullptr), it(nullptr)
     {}

     // This is for the benefit of CompartmentsIterT::comp.
     friend class mozilla::Maybe<CompartmentsInZoneIter>;
 };

 // This iterator iterates over all the compartments in a given set of zones. The
 // set of zones is determined by iterating ZoneIterT.
 template<class ZonesIterT>
 class CompartmentsIterT
 {
     gc::AutoEnterIteration iterMarker;
     ZonesIterT zone;
     mozilla::Maybe<CompartmentsInZoneIter> comp;

   public:
     explicit CompartmentsIterT(JSRuntime* rt)
       : iterMarker(&rt->gc), zone(rt)
     {
         if (zone.done())
             comp.emplace();
         else
             comp.emplace(zone);
     }

     CompartmentsIterT(JSRuntime* rt, ZoneSelector selector)
       : iterMarker(&rt->gc), zone(rt, selector)
     {
         if (zone.done())
             comp.emplace();
         else
             comp.emplace(zone);
     }

     bool done() const { return zone.done(); }

     void next() {
         MOZ_ASSERT(!done());
         MOZ_ASSERT(!comp.ref().done());
         comp->next();
         if (comp->done()) {
             comp.reset();
             zone.next();
             if (!zone.done())
                 comp.emplace(zone);
         }
     }

     JSCompartment* get() const {
         MOZ_ASSERT(!done());
         return *comp;
     }

     operator JSCompartment*() const { return get(); }
     JSCompartment* operator->() const { return get(); }
 };

 typedef CompartmentsIterT<ZonesIter> CompartmentsIter;

 /*
  * Allocation policy that uses Zone::pod_malloc and friends, so that memory
  * pressure is accounted for on the zone. This is suitable for memory associated
  * with GC things allocated in the zone.
  *
  * Since it doesn't hold a JSContext (those may not live long enough), it can't
  * report out-of-memory conditions itself; the caller must check for OOM and
  * take the appropriate action.
  *
  * FIXME bug 647103 - replace these *AllocPolicy names.
  */
 class ZoneAllocPolicy
 {
     Zone* const zone;

   public:
     MOZ_IMPLICIT ZoneAllocPolicy(Zone* zone) : zone(zone) {}

     template <typename T>
     T* maybe_pod_malloc(size_t numElems) {
         return zone->maybe_pod_malloc<T>(numElems);
     }

     template <typename T>
     T* maybe_pod_calloc(size_t numElems) {
         return zone->maybe_pod_calloc<T>(numElems);
     }

     template <typename T>
     T* maybe_pod_realloc(T* p, size_t oldSize, size_t newSize) {
         return zone->maybe_pod_realloc<T>(p, oldSize, newSize);
     }

     template <typename T>
     T* pod_malloc(size_t numElems) {
         return zone->pod_malloc<T>(numElems);
     }

     template <typename T>
     T* pod_calloc(size_t numElems) {
         return zone->pod_calloc<T>(numElems);
     }

     template <typename T>
     T* pod_realloc(T* p, size_t oldSize, size_t newSize) {
         return zone->pod_realloc<T>(p, oldSize, newSize);
     }

     void free_(void* p) { js_free(p); }
     void reportAllocOverflow() const {}

     bool checkSimulatedOOM() const {
         return !js::oom::ShouldFailWithOOM();
     }
 };

 } // namespace js

 #endif // gc_Zone_h
	/* -- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 --
	* vim: set ts=8 sts=4 et sw=4 tw=99:
	* This Source Code Form is subject to the terms of the Mozilla Public
	* License, v. 2.0. If a copy of the MPL was not distributed with this
	* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

	#ifndef gc_Zone_h
	#define gc_Zone_h

	#include "mozilla/Atomics.h"
	#include "mozilla/DebugOnly.h"
	#include "mozilla/MemoryReporting.h"

	#include "jscntxt.h"

	#include "ds/SplayTree.h"
	#include "gc/FindSCCs.h"
	#include "gc/GCRuntime.h"
	#include "js/GCHashTable.h"
	#include "js/TracingAPI.h"
	#include "vm/MallocProvider.h"
	#include "vm/TypeInference.h"

	namespace js {

	namespace jit {
	class JitZone;
	} // namespace jit

	namespace gc {

	// This class encapsulates the data that determines when we need to do a zone GC.
	class ZoneHeapThreshold
	{
	// The "growth factor" for computing our next thresholds after a GC.
	double gcHeapGrowthFactor_;

	// GC trigger threshold for allocations on the GC heap.
	size_t gcTriggerBytes_;

	public:
	ZoneHeapThreshold()
	: gcHeapGrowthFactor_(3.0),
	gcTriggerBytes_(0)
	{}

	double gcHeapGrowthFactor() const { return gcHeapGrowthFactor_; }
	size_t gcTriggerBytes() const { return gcTriggerBytes_; }
	double allocTrigger(bool highFrequencyGC) const;

	void updateAfterGC(size_t lastBytes, JSGCInvocationKind gckind,
	const GCSchedulingTunables& tunables, const GCSchedulingState& state,
	const AutoLockGC& lock);
	void updateForRemovedArena(const GCSchedulingTunables& tunables);

	private:
	static double computeZoneHeapGrowthFactorForHeapSize(size_t lastBytes,
	const GCSchedulingTunables& tunables,
	const GCSchedulingState& state);
	static size_t computeZoneTriggerBytes(double growthFactor, size_t lastBytes,
	JSGCInvocationKind gckind,
	const GCSchedulingTunables& tunables,
	const AutoLockGC& lock);
	};

	struct UniqueIdGCPolicy {
	static bool needsSweep(Cell** cell, uint64_t* value);
	};

	// Maps a Cell* to a unique, 64bit id.
	using UniqueIdMap = GCHashMap<Cell*,
	uint64_t,
	PointerHasher<Cell*, 3>,
	SystemAllocPolicy,
	UniqueIdGCPolicy>;

	extern uint64_t NextCellUniqueId(JSRuntime* rt);

	} // namespace gc
	} // namespace js

	namespace JS {

	// A zone is a collection of compartments. Every compartment belongs to exactly
	// one zone. In Firefox, there is roughly one zone per tab along with a system
	// zone for everything else. Zones mainly serve as boundaries for garbage
	// collection. Unlike compartments, they have no special security properties.
	//
	// Every GC thing belongs to exactly one zone. GC things from the same zone but
	// different compartments can share an arena (4k page). GC things from different
	// zones cannot be stored in the same arena. The garbage collector is capable of
	// collecting one zone at a time; it cannot collect at the granularity of
	// compartments.
	//
	// GC things are tied to zones and compartments as follows:
	//
	// - JSObjects belong to a compartment and cannot be shared between
	// compartments. If an object needs to point to a JSObject in a different
	// compartment, regardless of zone, it must go through a cross-compartment
	// wrapper. Each compartment keeps track of its outgoing wrappers in a table.
	//
	// - JSStrings do not belong to any particular compartment, but they do belong
	// to a zone. Thus, two different compartments in the same zone can point to a
	// JSString. When a string needs to be wrapped, we copy it if it's in a
	// different zone and do nothing if it's in the same zone. Thus, transferring
	// strings within a zone is very efficient.
	//
	// - Shapes and base shapes belong to a compartment and cannot be shared between
	// compartments. A base shape holds a pointer to its compartment. Shapes find
	// their compartment via their base shape. JSObjects find their compartment
	// via their shape.
	//
	// - Scripts are also compartment-local and cannot be shared. A script points to
	// its compartment.
	//
	// - Type objects and JitCode objects belong to a compartment and cannot be
	// shared. However, there is no mechanism to obtain their compartments.
	//
	// A zone remains alive as long as any GC things in the zone are alive. A
	// compartment remains alive as long as any JSObjects, scripts, shapes, or base
	// shapes within it are alive.
	//
	// We always guarantee that a zone has at least one live compartment by refusing
	// to delete the last compartment in a live zone.
	struct Zone : public JS::shadow::Zone,
	public js::gc::GraphNodeBase<JS::Zone>,
	public js::MallocProvider<JS::Zone>
	{
	explicit Zone(JSRuntime* rt);
	~Zone();
	bool init(bool isSystem);

	void findOutgoingEdges(js::gc::ComponentFinder<JS::Zone>& finder);

	void discardJitCode(js::FreeOp* fop);

	void addSizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf,
	size_t* typePool,
	size_t* baselineStubsOptimized,
	size_t* uniqueIdMap);

	void resetGCMallocBytes();
	void setGCMaxMallocBytes(size_t value);
	void updateMallocCounter(size_t nbytes) {
	// Note: this code may be run from worker threads. We tolerate any
	// thread races when updating gcMallocBytes.
	gcMallocBytes -= ptrdiff_t(nbytes);
	if (MOZ_UNLIKELY(isTooMuchMalloc()))
	onTooMuchMalloc();
	}

	bool isTooMuchMalloc() const { return gcMallocBytes <= 0; }
	void onTooMuchMalloc();

	void* onOutOfMemory(js::AllocFunction allocFunc, size_t nbytes, void* reallocPtr = nullptr) {
	if (!js::CurrentThreadCanAccessRuntime(runtime_))
	return nullptr;
	return runtimeFromMainThread()->onOutOfMemory(allocFunc, nbytes, reallocPtr);
	}
	void reportAllocationOverflow() { js::ReportAllocationOverflow(nullptr); }

	void beginSweepTypes(js::FreeOp* fop, bool releaseTypes);

	bool hasMarkedCompartments();

	void scheduleGC() { MOZ_ASSERT(!runtimeFromMainThread()->isHeapBusy()); gcScheduled_ = true; }
	void unscheduleGC() { gcScheduled_ = false; }
	bool isGCScheduled() { return gcScheduled_ && canCollect(); }

	void setPreservingCode(bool preserving) { gcPreserveCode_ = preserving; }
	bool isPreservingCode() const { return gcPreserveCode_; }

	bool canCollect();

	void notifyObservingDebuggers();

	enum GCState {
	NoGC,
	Mark,
	MarkGray,
	Sweep,
	Finished,
	Compact
	};
	void setGCState(GCState state) {
	MOZ_ASSERT(runtimeFromMainThread()->isHeapBusy());
	MOZ_ASSERT_IF(state != NoGC, canCollect());
	gcState_ = state;
	if (state == Finished)
	notifyObservingDebuggers();
	}

	bool isCollecting() const {
	if (runtimeFromMainThread()->isHeapCollecting())
	return gcState_ != NoGC;
	else
	return needsIncrementalBarrier();
	}

	bool isCollectingFromAnyThread() const {
	if (runtimeFromAnyThread()->isHeapCollecting())
	return gcState_ != NoGC;
	else
	return needsIncrementalBarrier();
	}

	// If this returns true, all object tracing must be done with a GC marking
	// tracer.
	bool requireGCTracer() const {
	JSRuntime* rt = runtimeFromAnyThread();
	return rt->isHeapMajorCollecting() && !rt->gc.isHeapCompacting() && gcState_ != NoGC;
	}

	bool isGCMarking() {
	if (runtimeFromMainThread()->isHeapCollecting())
	return gcState_ == Mark \|\| gcState_ == MarkGray;
	else
	return needsIncrementalBarrier();
	}

	bool wasGCStarted() const { return gcState_ != NoGC; }
	bool isGCMarkingBlack() { return gcState_ == Mark; }
	bool isGCMarkingGray() { return gcState_ == MarkGray; }
	bool isGCSweeping() { return gcState_ == Sweep; }
	bool isGCFinished() { return gcState_ == Finished; }
	bool isGCCompacting() { return gcState_ == Compact; }
	bool isGCSweepingOrCompacting() { return gcState_ == Sweep \|\| gcState_ == Compact; }

	// Get a number that is incremented whenever this zone is collected, and
	// possibly at other times too.
	uint64_t gcNumber();

	bool compileBarriers() const { return compileBarriers(needsIncrementalBarrier()); }
	bool compileBarriers(bool needsIncrementalBarrier) const {
	return needsIncrementalBarrier \|\|
	runtimeFromMainThread()->gcZeal() == js::gc::ZealVerifierPreValue;
	}

	enum ShouldUpdateJit { DontUpdateJit, UpdateJit };
	void setNeedsIncrementalBarrier(bool needs, ShouldUpdateJit updateJit);
	const bool* addressOfNeedsIncrementalBarrier() const { return &needsIncrementalBarrier_; }

	js::jit::JitZone* getJitZone(JSContext* cx) { return jitZone_ ? jitZone_ : createJitZone(cx); }
	js::jit::JitZone* jitZone() { return jitZone_; }

	bool isAtomsZone() const { return runtimeFromAnyThread()->isAtomsZone(this); }
	bool isSelfHostingZone() const { return runtimeFromAnyThread()->isSelfHostingZone(this); }

	void prepareForCompacting();

	#ifdef DEBUG
	// For testing purposes, return the index of the zone group which this zone
	// was swept in in the last GC.
	unsigned lastZoneGroupIndex() { return gcLastZoneGroupIndex; }
	#endif

	using DebuggerVector = js::Vector<js::Debugger*, 0, js::SystemAllocPolicy>;

	private:
	DebuggerVector* debuggers;

	using LogTenurePromotionQueue = js::Vector<JSObject*, 0, js::SystemAllocPolicy>;
	LogTenurePromotionQueue awaitingTenureLogging;

	void sweepBreakpoints(js::FreeOp* fop);
	void sweepUniqueIds(js::FreeOp* fop);
	void sweepWeakMaps();
	void sweepCompartments(js::FreeOp* fop, bool keepAtleastOne, bool lastGC);

	js::jit::JitZone* createJitZone(JSContext* cx);

	bool isQueuedForBackgroundSweep() {
	return isOnList();
	}

	// Side map for storing a unique ids for cells, independent of address.
	js::gc::UniqueIdMap uniqueIds_;

	public:
	bool hasDebuggers() const { return debuggers && debuggers->length(); }
	DebuggerVector* getDebuggers() const { return debuggers; }
	DebuggerVector* getOrCreateDebuggers(JSContext* cx);

	void enqueueForPromotionToTenuredLogging(JSObject& obj) {
	MOZ_ASSERT(hasDebuggers());
	MOZ_ASSERT(!IsInsideNursery(&obj));
	js::AutoEnterOOMUnsafeRegion oomUnsafe;
	if (!awaitingTenureLogging.append(&obj))
	oomUnsafe.crash("Zone::enqueueForPromotionToTenuredLogging");
	}
	void logPromotionsToTenured();

	js::gc::ArenaLists arenas;

	js::TypeZone types;

	/* Live weakmaps in this zone. */
	mozilla::LinkedList<js::WeakMapBase> gcWeakMapList;

	// The set of compartments in this zone.
	typedef js::Vector<JSCompartment*, 1, js::SystemAllocPolicy> CompartmentVector;
	CompartmentVector compartments;

	// This zone's gray roots.
	typedef js::Vector<js::gc::Cell*, 0, js::SystemAllocPolicy> GrayRootVector;
	GrayRootVector gcGrayRoots;

	// This zone's weak edges found via graph traversal during marking,
	// preserved for re-scanning during sweeping.
	using WeakEdges = js::Vector<js::gc::TenuredCell**, 0, js::SystemAllocPolicy>;
	WeakEdges gcWeakRefs;

	/*
	* Mapping from not yet marked keys to a vector of all values that the key
	* maps to in any live weak map.
	*/
	js::gc::WeakKeyTable gcWeakKeys;

	// A set of edges from this zone to other zones.
	//
	// This is used during GC while calculating zone groups to record edges that
	// can't be determined by examining this zone by itself.
	ZoneSet gcZoneGroupEdges;

	// Malloc counter to measure memory pressure for GC scheduling. It runs from
	// gcMaxMallocBytes down to zero. This counter should be used only when it's
	// not possible to know the size of a free.
	mozilla::Atomic<ptrdiff_t, mozilla::ReleaseAcquire> gcMallocBytes;

	// GC trigger threshold for allocations on the C heap.
	size_t gcMaxMallocBytes;

	// Whether a GC has been triggered as a result of gcMallocBytes falling
	// below zero.
	//
	// This should be a bool, but Atomic only supports 32-bit and pointer-sized
	// types.
	mozilla::Atomic<uint32_t, mozilla::ReleaseAcquire> gcMallocGCTriggered;

	// Track heap usage under this Zone.
	js::gc::HeapUsage usage;

	// Thresholds used to trigger GC.
	js::gc::ZoneHeapThreshold threshold;

	// Amount of data to allocate before triggering a new incremental slice for
	// the current GC.
	size_t gcDelayBytes;

	// Per-zone data for use by an embedder.
	void* data;

	bool isSystem;

	bool usedByExclusiveThread;

	// True when there are active frames.
	bool active;

	mozilla::DebugOnly<unsigned> gcLastZoneGroupIndex;

	// Creates a HashNumber based on getUniqueId. Returns false on OOM.
	bool getHashCode(js::gc::Cell* cell, js::HashNumber* hashp) {
	uint64_t uid;
	if (!getUniqueId(cell, &uid))
	return false;
	*hashp = js::HashNumber(uid >> 32) ^ js::HashNumber(uid & 0xFFFFFFFF);
	return true;
	}

	// Puts an existing UID in \|uidp\|, or creates a new UID for this Cell and
	// puts that into \|uidp\|. Returns false on OOM.
	bool getUniqueId(js::gc::Cell* cell, uint64_t* uidp) {
	MOZ_ASSERT(uidp);
	MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));

	// Get an existing uid, if one has been set.
	auto p = uniqueIds_.lookupForAdd(cell);
	if (p) {
	*uidp = p->value();
	return true;
	}

	// Set a new uid on the cell.
	*uidp = js::gc::NextCellUniqueId(runtimeFromAnyThread());
	if (!uniqueIds_.add(p, cell, *uidp))
	return false;

	// If the cell was in the nursery, hopefully unlikely, then we need to
	// tell the nursery about it so that it can sweep the uid if the thing
	// does not get tenured.
	js::AutoEnterOOMUnsafeRegion oomUnsafe;
	if (!runtimeFromAnyThread()->gc.nursery.addedUniqueIdToCell(cell))
	oomUnsafe.crash("failed to allocate tracking data for a nursery uid");
	return true;
	}

	// Return true if this cell has a UID associated with it.
	bool hasUniqueId(js::gc::Cell* cell) {
	MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));
	return uniqueIds_.has(cell);
	}

	// Transfer an id from another cell. This must only be called on behalf of a
	// moving GC. This method is infallible.
	void transferUniqueId(js::gc::Cell* tgt, js::gc::Cell* src) {
	MOZ_ASSERT(src != tgt);
	MOZ_ASSERT(!IsInsideNursery(tgt));
	MOZ_ASSERT(CurrentThreadCanAccessRuntime(runtimeFromMainThread()));
	MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));
	uniqueIds_.rekeyIfMoved(src, tgt);
	}

	// Remove any unique id associated with this Cell.
	void removeUniqueId(js::gc::Cell* cell) {
	MOZ_ASSERT(js::CurrentThreadCanAccessZone(this));
	uniqueIds_.remove(cell);
	}

	// Off-thread parsing should not result in any UIDs being created.
	void assertNoUniqueIdsInZone() const {
	MOZ_ASSERT(uniqueIds_.count() == 0);
	}

	#ifdef JSGC_HASH_TABLE_CHECKS
	// Assert that the UniqueId table has been redirected successfully.
	void checkUniqueIdTableAfterMovingGC();
	#endif

	private:
	js::jit::JitZone* jitZone_;

	GCState gcState_;
	bool gcScheduled_;
	bool gcPreserveCode_;
	bool jitUsingBarriers_;

	// Allow zones to be linked into a list
	friend class js::gc::ZoneList;
	static Zone * const NotOnList;
	Zone* listNext_;
	bool isOnList() const;
	Zone* nextZone() const;

	friend bool js::CurrentThreadCanAccessZone(Zone* zone);
	friend class js::gc::GCRuntime;
	};

	} // namespace JS

	namespace js {

	// Using the atoms zone without holding the exclusive access lock is dangerous
	// because worker threads may be using it simultaneously. Therefore, it's
	// better to skip the atoms zone when iterating over zones. If you need to
	// iterate over the atoms zone, consider taking the exclusive access lock first.
	enum ZoneSelector {
	WithAtoms,
	SkipAtoms
	};

	class ZonesIter
	{
	gc::AutoEnterIteration iterMarker;
	JS::Zone** it;
	JS::Zone** end;

	public:
	ZonesIter(JSRuntime* rt, ZoneSelector selector) : iterMarker(&rt->gc) {
	it = rt->gc.zones.begin();
	end = rt->gc.zones.end();

	if (selector == SkipAtoms) {
	MOZ_ASSERT(atAtomsZone(rt));
	it++;
	}
	}

	bool atAtomsZone(JSRuntime* rt);

	bool done() const { return it == end; }

	void next() {
	MOZ_ASSERT(!done());
	do {
	it++;
	} while (!done() && (*it)->usedByExclusiveThread);
	}

	JS::Zone* get() const {
	MOZ_ASSERT(!done());
	return *it;
	}

	operator JS::Zone*() const { return get(); }
	JS::Zone* operator->() const { return get(); }
	};

	struct CompartmentsInZoneIter
	{
	explicit CompartmentsInZoneIter(JS::Zone* zone) : zone(zone) {
	it = zone->compartments.begin();
	}

	bool done() const {
	MOZ_ASSERT(it);
	return it < zone->compartments.begin() \|\|
	it >= zone->compartments.end();
	}
	void next() {
	MOZ_ASSERT(!done());
	it++;
	}

	JSCompartment* get() const {
	MOZ_ASSERT(it);
	return *it;
	}

	operator JSCompartment*() const { return get(); }
	JSCompartment* operator->() const { return get(); }

	private:
	JS::Zone* zone;
	JSCompartment** it;

	CompartmentsInZoneIter()
	: zone(nullptr), it(nullptr)
	{}

	// This is for the benefit of CompartmentsIterT::comp.
	friend class mozilla::Maybe<CompartmentsInZoneIter>;
	};

	// This iterator iterates over all the compartments in a given set of zones. The
	// set of zones is determined by iterating ZoneIterT.
	template<class ZonesIterT>
	class CompartmentsIterT
	{
	gc::AutoEnterIteration iterMarker;
	ZonesIterT zone;
	mozilla::Maybe<CompartmentsInZoneIter> comp;

	public:
	explicit CompartmentsIterT(JSRuntime* rt)
	: iterMarker(&rt->gc), zone(rt)
	{
	if (zone.done())
	comp.emplace();
	else
	comp.emplace(zone);
	}

	CompartmentsIterT(JSRuntime* rt, ZoneSelector selector)
	: iterMarker(&rt->gc), zone(rt, selector)
	{
	if (zone.done())
	comp.emplace();
	else
	comp.emplace(zone);
	}

	bool done() const { return zone.done(); }

	void next() {
	MOZ_ASSERT(!done());
	MOZ_ASSERT(!comp.ref().done());
	comp->next();
	if (comp->done()) {
	comp.reset();
	zone.next();
	if (!zone.done())
	comp.emplace(zone);
	}
	}

	JSCompartment* get() const {
	MOZ_ASSERT(!done());
	return *comp;
	}

	operator JSCompartment*() const { return get(); }
	JSCompartment* operator->() const { return get(); }
	};

	typedef CompartmentsIterT<ZonesIter> CompartmentsIter;

	/*
	* Allocation policy that uses Zone::pod_malloc and friends, so that memory
	* pressure is accounted for on the zone. This is suitable for memory associated
	* with GC things allocated in the zone.
	*
	* Since it doesn't hold a JSContext (those may not live long enough), it can't
	* report out-of-memory conditions itself; the caller must check for OOM and
	* take the appropriate action.
	*
	* FIXME bug 647103 - replace these *AllocPolicy names.
	*/
	class ZoneAllocPolicy
	{
	Zone* const zone;

	public:
	MOZ_IMPLICIT ZoneAllocPolicy(Zone* zone) : zone(zone) {}

	template <typename T>
	T* maybe_pod_malloc(size_t numElems) {
	return zone->maybe_pod_malloc<T>(numElems);
	}

	template <typename T>
	T* maybe_pod_calloc(size_t numElems) {
	return zone->maybe_pod_calloc<T>(numElems);
	}

	template <typename T>
	T* maybe_pod_realloc(T* p, size_t oldSize, size_t newSize) {
	return zone->maybe_pod_realloc<T>(p, oldSize, newSize);
	}

	template <typename T>
	T* pod_malloc(size_t numElems) {
	return zone->pod_malloc<T>(numElems);
	}

	template <typename T>
	T* pod_calloc(size_t numElems) {
	return zone->pod_calloc<T>(numElems);
	}

	template <typename T>
	T* pod_realloc(T* p, size_t oldSize, size_t newSize) {
	return zone->pod_realloc<T>(p, oldSize, newSize);
	}

	void free_(void* p) { js_free(p); }
	void reportAllocOverflow() const {}

	bool checkSimulatedOOM() const {
	return !js::oom::ShouldFailWithOOM();
	}
	};

	} // namespace js

	#endif // gc_Zone_h