/* 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 js_HeapAPI_h
#define js_HeapAPI_h

#include "mozilla/Atomics.h"
#include "mozilla/BitSet.h"

#include <limits.h>
#include <type_traits>

#include "js/AllocPolicy.h"
#include "js/GCAnnotations.h"
#include "js/HashTable.h"
#include "js/shadow/String.h"  // JS::shadow::String
#include "js/shadow/Symbol.h"  // JS::shadow::Symbol
#include "js/shadow/Zone.h"    // JS::shadow::Zone
#include "js/TraceKind.h"
#include "js/TypeDecls.h"

/* These values are private to the JS engine. */
namespace js {

JS_PUBLIC_API bool CurrentThreadCanAccessZone(JS::Zone* zone);

// To prevent false sharing, some data structures are aligned to a typical cache
// line size.
static constexpr size_t TypicalCacheLineSize = 64;

namespace gc {

class Arena;
class Cell;
class ArenaChunk;
class StoreBuffer;
class TenuredCell;

const size_t ArenaShift = 12;
const size_t ArenaSize = size_t(1) << ArenaShift;
const size_t ArenaMask = ArenaSize - 1;

#if defined(XP_DARWIN) && defined(__aarch64__)
const size_t PageShift = 14;
#else
const size_t PageShift = 12;
#endif
// Expected page size, so we could initialze ArenasPerPage at compile-time.
// The actual system page size should be queried by SystemPageSize().
const size_t PageSize = size_t(1) << PageShift;
const size_t PageMask = PageSize - 1;
constexpr size_t ArenasPerPage = PageSize / ArenaSize;

const size_t ChunkShift = 20;
const size_t ChunkSize = size_t(1) << ChunkShift;
const size_t ChunkMask = ChunkSize - 1;

const size_t CellAlignShift = 3;
const size_t CellAlignBytes = size_t(1) << CellAlignShift;
const size_t CellAlignMask = CellAlignBytes - 1;

const size_t CellBytesPerMarkBit = CellAlignBytes;
const size_t MarkBitsPerCell = 2;

/*
 * The minimum cell size ends up as twice the cell alignment because the mark
 * bitmap contains one bit per CellBytesPerMarkBit bytes (which is equal to
 * CellAlignBytes) and we need two mark bits per cell.
 */
const size_t MinCellSize = CellBytesPerMarkBit * MarkBitsPerCell;

/*
 * The mark bitmap has one bit per each possible cell start position. This
 * wastes some space for larger GC things but allows us to avoid division by the
 * cell's size when accessing the bitmap.
 */
const size_t ArenaBitmapBits = ArenaSize / CellBytesPerMarkBit;
const size_t ArenaBitmapBytes = HowMany(ArenaBitmapBits, 8);
const size_t ArenaBitmapWords = HowMany(ArenaBitmapBits, JS_BITS_PER_WORD);

enum class ChunkKind : uint8_t {
  Invalid = 0,
  TenuredArenas,
  Buffers,
  NurseryToSpace,
  NurseryFromSpace
};

// The base class for all GC chunks, either in the nursery or in the tenured
// heap memory. This structure is locatable from any GC pointer by aligning to
// the chunk size.
class ChunkBase {
 protected:
  // Initialize a tenured heap chunk.
  explicit ChunkBase(JSRuntime* rt) {
    MOZ_ASSERT((uintptr_t(this) & ChunkMask) == 0);
    initBaseForArenaChunk(rt);
  }

  void initBaseForArenaChunk(JSRuntime* rt) {
    runtime = rt;
    storeBuffer = nullptr;
    kind = ChunkKind::TenuredArenas;
    nurseryChunkIndex = UINT8_MAX;
  }

  // Initialize a nursery chunk.
  ChunkBase(JSRuntime* rt, StoreBuffer* sb, ChunkKind kind, uint8_t chunkIndex)
      : storeBuffer(sb),
        runtime(rt),
        kind(kind),
        nurseryChunkIndex(chunkIndex) {
    MOZ_ASSERT(isNurseryChunk());
    MOZ_ASSERT((uintptr_t(this) & ChunkMask) == 0);
    MOZ_ASSERT(storeBuffer);
  }

  ChunkBase(JSRuntime* rt, ChunkKind kind)
      : storeBuffer(nullptr),
        runtime(rt),
        kind(kind),
        nurseryChunkIndex(UINT8_MAX) {}

 public:
  ChunkKind getKind() const {
    MOZ_ASSERT_IF(storeBuffer, isNurseryChunk());
    MOZ_ASSERT_IF(!storeBuffer, isTenuredChunk());
    return kind;
  }

  bool isNurseryChunk() const {
    return kind == ChunkKind::NurseryToSpace ||
           kind == ChunkKind::NurseryFromSpace;
  }

  bool isTenuredChunk() const {
    return kind == ChunkKind::TenuredArenas || kind == ChunkKind::Buffers;
  }

  // The store buffer for pointers from tenured things to things in this
  // chunk. Will be non-null if and only if this is a nursery chunk.
  StoreBuffer* storeBuffer;

  // Provide quick access to the runtime from absolutely anywhere.
  JSRuntime* runtime;

  ChunkKind kind;

  uint8_t nurseryChunkIndex;
};

// Information about tenured heap chunks containing arenas.
struct ArenaChunkInfo {
 private:
  friend class ArenaChunk;
  friend class ChunkPool;
  ArenaChunk* next = nullptr;
  ArenaChunk* prev = nullptr;

 public:
  /* Number of free arenas, either committed or decommitted. */
  uint32_t numArenasFree;

  /* Number of free, committed arenas. */
  uint32_t numArenasFreeCommitted;

  /* Whether this chunk is the chunk currently being allocated from. */
  bool isCurrentChunk = false;

  // The zone this chunk is associated with, or nullptr for empty chunks.
  JS::Zone* zone = nullptr;
};

/*
 * Calculating ArenasPerChunk:
 *
 * To figure out how many Arenas will fit in a chunk we need to know how much
 * extra space is available after we allocate the header data. This is a problem
 * because the header size depends on the number of arenas in the chunk.
 *
 * The dependent fields are markBits, decommittedPages and
 * freeCommittedArenas. markBits needs ArenaBitmapBytes bytes per arena,
 * decommittedPages needs one bit per page and freeCommittedArenas needs one
 * bit per arena.
 *
 * We can calculate an approximate value by dividing the number of bits of free
 * space in the chunk by the number of bits needed per arena. This is an
 * approximation because it doesn't take account of the fact that the variable
 * sized fields must be rounded up to a whole number of words, or any padding
 * the compiler adds between fields.
 *
 * Fortunately, for the chunk and arena size parameters we use this
 * approximation turns out to be correct. If it were not we might need to adjust
 * the arena count down by one to allow more space for the padding.
 */
const size_t BitsPerPageWithHeaders =
    (ArenaSize + ArenaBitmapBytes) * ArenasPerPage * CHAR_BIT + ArenasPerPage +
    1;
const size_t ChunkBitsAvailable =
    (ChunkSize - sizeof(ChunkBase) - sizeof(ArenaChunkInfo)) * CHAR_BIT;
const size_t PagesPerChunk = ChunkBitsAvailable / BitsPerPageWithHeaders;
const size_t ArenasPerChunk = PagesPerChunk * ArenasPerPage;
const size_t FreeCommittedBits = ArenasPerChunk;
const size_t DecommitBits = PagesPerChunk;
const size_t BitsPerArenaWithHeaders =
    (ArenaSize + ArenaBitmapBytes) * CHAR_BIT +
    (DecommitBits / ArenasPerChunk) + 1;

const size_t CalculatedChunkSizeRequired =
    sizeof(ChunkBase) + sizeof(ArenaChunkInfo) +
    RoundUp(ArenasPerChunk * ArenaBitmapBytes, sizeof(uintptr_t)) +
    RoundUp(FreeCommittedBits, sizeof(uint32_t) * CHAR_BIT) / CHAR_BIT +
    RoundUp(DecommitBits, sizeof(uint32_t) * CHAR_BIT) / CHAR_BIT +
    ArenasPerChunk * ArenaSize;
static_assert(CalculatedChunkSizeRequired <= ChunkSize,
              "Calculated ArenasPerChunk is too large");

const size_t CalculatedChunkPadSize = ChunkSize - CalculatedChunkSizeRequired;
static_assert(CalculatedChunkPadSize * CHAR_BIT < BitsPerArenaWithHeaders,
              "Calculated ArenasPerChunk is too small");

static_assert(ArenasPerChunk == 252,
              "Do not accidentally change our heap's density.");

const size_t FirstArenaOffset = ChunkSize - ArenasPerChunk * ArenaSize;

using AtomicBitmapWord = mozilla::Atomic<uintptr_t, mozilla::Relaxed>;

// A bitmap backed by atomic storage.
template <size_t N>
class AtomicBitmap {
 public:
  static constexpr size_t BitCount = N;

  using Word = AtomicBitmapWord;
  static constexpr size_t BitsPerWord = sizeof(Word) * CHAR_BIT;

  static_assert(N % BitsPerWord == 0);
  static constexpr size_t WordCount = N / BitsPerWord;

 private:
  Word bitmap[WordCount];

  static uintptr_t BitMask(size_t bit) {
    MOZ_ASSERT(bit < N);
    return uintptr_t(1) << (bit % BitsPerWord);
  }

 public:
  bool getBit(size_t bit) const {
    return getWord(bit / BitsPerWord) & BitMask(bit);
  }

  void setBit(size_t bit, bool value) {
    Word& word = wordRef(bit / BitsPerWord);
    if (value) {
      word |= BitMask(bit);
    } else {
      word &= ~BitMask(bit);
    }
  }

  uintptr_t getWord(size_t index) const {
    MOZ_ASSERT(index < WordCount);
    return bitmap[index];
  }
  Word& wordRef(size_t index) {
    MOZ_ASSERT(index < WordCount);
    return bitmap[index];
  }

  inline bool isEmpty() const;
  inline void clear();
  inline void copyFrom(const AtomicBitmap& other);

  class Iter;
};

/*
 * Live objects are marked black or gray. Everything reachable from a JS root is
 * marked black. Objects marked gray are eligible for cycle collection.
 *
 *    BlackBit:     GrayOrBlackBit:  Color:
 *       0               0           white
 *       0               1           gray
 *       1               0           black
 *       1               1           black
 */
enum class ColorBit : uint32_t { BlackBit = 0, GrayOrBlackBit = 1 };

// Mark colors. Order is important here: the greater value the 'more marked' a
// cell is.
enum class MarkColor : uint8_t { Gray = 1, Black = 2 };

static constexpr size_t ChunkMarkBitCount =
    (ChunkSize - FirstArenaOffset) / CellBytesPerMarkBit;

// Mark bitmap for a tenured heap chunk.
//
// Mark bitmaps are atomic because they can be written by gray unmarking on the
// main thread while read by sweeping on a background thread. The former does
// not affect the result of the latter.
class alignas(TypicalCacheLineSize) ChunkMarkBitmap
    : protected AtomicBitmap<ChunkMarkBitCount> {
  using Bitmap = AtomicBitmap<ChunkMarkBitCount>;

 public:
  using Bitmap::BitsPerWord;
  using Bitmap::WordCount;

  static constexpr size_t FirstThingAdjustmentBits =
      FirstArenaOffset / CellBytesPerMarkBit;
  static_assert(FirstThingAdjustmentBits % BitsPerWord == 0);
  static constexpr size_t FirstThingAdjustmentWords =
      FirstThingAdjustmentBits / BitsPerWord;

  MOZ_ALWAYS_INLINE void getMarkWordAndMask(const void* cell, ColorBit colorBit,
                                            Word** wordp, uintptr_t* maskp) {
    // Note: the JIT inlines this code. Update MacroAssembler::loadMarkBits and
    // its callers when making changes here!

    MOZ_ASSERT(size_t(colorBit) < MarkBitsPerCell);

    size_t offset = uintptr_t(cell) & ChunkMask;
    MOZ_ASSERT(offset >= FirstArenaOffset);

    const size_t bit = offset / CellBytesPerMarkBit + size_t(colorBit);
    size_t word = bit / BitsPerWord - FirstThingAdjustmentWords;
    MOZ_ASSERT(word < WordCount);
    *wordp = &wordRef(word);
    *maskp = uintptr_t(1) << (bit % BitsPerWord);
  }

  // The following are not exported and are defined in gc/Heap.h:
  MOZ_ALWAYS_INLINE bool markBit(const void* cell, ColorBit colorBit) {
    Word* word;
    uintptr_t mask;
    getMarkWordAndMask(cell, colorBit, &word, &mask);
    return *word & mask;
  }

  MOZ_ALWAYS_INLINE bool isMarkedAny(const void* cell) {
    return markBit(cell, ColorBit::BlackBit) ||
           markBit(cell, ColorBit::GrayOrBlackBit);
  }

  MOZ_ALWAYS_INLINE bool isMarkedBlack(const void* cell) {
    // Return true if BlackBit is set.
    return markBit(cell, ColorBit::BlackBit);
  }

  MOZ_ALWAYS_INLINE bool isMarkedGray(const void* cell) {
    // Return true if GrayOrBlackBit is set and BlackBit is not set.
    return !markBit(cell, ColorBit::BlackBit) &&
           markBit(cell, ColorBit::GrayOrBlackBit);
  }

  inline bool markIfUnmarked(const void* cell, MarkColor color);
  inline bool markIfUnmarkedThreadSafe(const void* cell, MarkColor color);
  inline void markBlack(const void* cell);
  inline void markBlackAtomic(const void* cell);
  inline void copyMarkBit(TenuredCell* dst, const TenuredCell* src,
                          ColorBit colorBit);
  inline void unmark(const void* cell);
  inline void unmarkOneBit(const void* cell, ColorBit colorBit);
  inline AtomicBitmapWord* arenaBits(Arena* arena);

  inline void copyFrom(const ChunkMarkBitmap& other);
  using Bitmap::clear;
};

// Bitmap with one bit per page used for decommitted page set.
using ChunkPageBitmap = mozilla::BitSet<PagesPerChunk, uint32_t>;

// Bitmap with one bit per arena used for free committed arena set.
using ChunkArenaBitmap = mozilla::BitSet<ArenasPerChunk, uint32_t>;

// Base class for a tenured heap chunk containing fixed size arenas.
class ArenaChunkBase : public ChunkBase {
 public:
  ArenaChunkInfo info;
  ChunkMarkBitmap markBits;
  ChunkArenaBitmap freeCommittedArenas;
  ChunkPageBitmap decommittedPages;

 protected:
  explicit ArenaChunkBase(JSRuntime* runtime) : ChunkBase(runtime) {
    static_assert(sizeof(markBits) == ArenaBitmapBytes * ArenasPerChunk,
                  "Ensure our MarkBitmap actually covers all arenas.");
    info.numArenasFree = ArenasPerChunk;
  }

  void initAsCommitted();
  void initAsDecommitted();
};
static_assert(FirstArenaOffset ==
              RoundUp(sizeof(gc::ArenaChunkBase), ArenaSize));

/*
 * We sometimes use an index to refer to a cell in an arena. The index for a
 * cell is found by dividing by the cell alignment so not all indices refer to
 * valid cells.
 */
const size_t ArenaCellIndexBytes = CellAlignBytes;
const size_t MaxArenaCellIndex = ArenaSize / CellAlignBytes;

const size_t ChunkStoreBufferOffset = offsetof(ChunkBase, storeBuffer);
const size_t ChunkMarkBitmapOffset = offsetof(ArenaChunkBase, markBits);
const size_t ChunkZoneOffset =
    offsetof(ArenaChunkBase, info) + offsetof(ArenaChunkInfo, zone);

// Hardcoded offsets into Arena class.
const size_t ArenaHeaderSize = 2 * sizeof(uint32_t) + 1 * sizeof(uintptr_t) +
                               sizeof(size_t) + sizeof(uintptr_t);

// The first word of a GC thing has certain requirements from the GC and is used
// to store flags in the low bits.
const size_t CellFlagBitsReservedForGC = 3;

// The first word can be used to store JSClass pointers for some thing kinds, so
// these must be suitably aligned.
const size_t JSClassAlignBytes = size_t(1) << CellFlagBitsReservedForGC;

#ifdef JS_DEBUG
/* When downcasting, ensure we are actually the right type. */
extern JS_PUBLIC_API void AssertGCThingHasType(js::gc::Cell* cell,
                                               JS::TraceKind kind);
#else
inline void AssertGCThingHasType(js::gc::Cell* cell, JS::TraceKind kind) {}
#endif

MOZ_ALWAYS_INLINE bool IsInsideNursery(const js::gc::Cell* cell);
MOZ_ALWAYS_INLINE bool IsInsideNursery(const js::gc::TenuredCell* cell);

} /* namespace gc */
} /* namespace js */

namespace JS {

enum class HeapState {
  Idle,             // doing nothing with the GC heap
  Tracing,          // tracing the GC heap without collecting, e.g.
                    // IterateCompartments()
  MajorCollecting,  // doing a GC of the major heap
  MinorCollecting,  // doing a GC of the minor heap (nursery)
  CycleCollecting   // in the "Unlink" phase of cycle collection
};

JS_PUBLIC_API HeapState RuntimeHeapState();

static inline bool RuntimeHeapIsBusy() {
  return RuntimeHeapState() != HeapState::Idle;
}

static inline bool RuntimeHeapIsTracing() {
  return RuntimeHeapState() == HeapState::Tracing;
}

static inline bool RuntimeHeapIsMajorCollecting() {
  return RuntimeHeapState() == HeapState::MajorCollecting;
}

static inline bool RuntimeHeapIsMinorCollecting() {
  return RuntimeHeapState() == HeapState::MinorCollecting;
}

static inline bool RuntimeHeapIsCollecting(HeapState state) {
  return state == HeapState::MajorCollecting ||
         state == HeapState::MinorCollecting;
}

static inline bool RuntimeHeapIsCollecting() {
  return RuntimeHeapIsCollecting(RuntimeHeapState());
}

static inline bool RuntimeHeapIsCycleCollecting() {
  return RuntimeHeapState() == HeapState::CycleCollecting;
}

/*
 * This list enumerates the different types of conceptual stacks we have in
 * SpiderMonkey. In reality, they all share the C stack, but we allow different
 * stack limits depending on the type of code running.
 */
enum StackKind {
  StackForSystemCode,       // C++, such as the GC, running on behalf of the VM.
  StackForTrustedScript,    // Script running with trusted principals.
  StackForUntrustedScript,  // Script running with untrusted principals.
  StackKindCount
};

/*
 * Default maximum size for the generational nursery in bytes. This is the
 * initial value. In the browser this configured by the
 * javascript.options.mem.nursery.max_kb pref.
 */
const uint32_t DefaultNurseryMaxBytes = 64 * js::gc::ChunkSize;

/* Default maximum heap size in bytes to pass to JS_NewContext(). */
const uint32_t DefaultHeapMaxBytes = 32 * 1024 * 1024;

/**
 * A GC pointer, tagged with the trace kind.
 *
 * In general, a GC pointer should be stored with an exact type. This class
 * is for use when that is not possible because a single pointer must point
 * to several kinds of GC thing.
 */
class JS_PUBLIC_API GCCellPtr {
 public:
  GCCellPtr() : GCCellPtr(nullptr) {}

  // Construction from a void* and trace kind.
  GCCellPtr(void* gcthing, JS::TraceKind traceKind)
      : ptr(checkedCast(gcthing, traceKind)) {}

  // Automatically construct a null GCCellPtr from nullptr.
  MOZ_IMPLICIT GCCellPtr(decltype(nullptr))
      : ptr(checkedCast(nullptr, JS::TraceKind::Null)) {}

  // Construction from an explicit type.
  template <typename T>
  explicit GCCellPtr(T* p)
      : ptr(checkedCast(p, JS::MapTypeToTraceKind<T>::kind)) {}
  explicit GCCellPtr(JSFunction* p)
      : ptr(checkedCast(p, JS::TraceKind::Object)) {}
  explicit GCCellPtr(JSScript* p)
      : ptr(checkedCast(p, JS::TraceKind::Script)) {}
  explicit GCCellPtr(const Value& v);

  JS::TraceKind kind() const {
    uintptr_t kindBits = ptr & OutOfLineTraceKindMask;
    if (kindBits != OutOfLineTraceKindMask) {
      return JS::TraceKind(kindBits);
    }
    return outOfLineKind();
  }

  // Allow GCCellPtr to be used in a boolean context.
  explicit operator bool() const {
    MOZ_ASSERT(bool(asCell()) == (kind() != JS::TraceKind::Null));
    return asCell();
  }

  bool operator==(const GCCellPtr other) const { return ptr == other.ptr; }
  bool operator!=(const GCCellPtr other) const { return ptr != other.ptr; }

  // Simplify checks to the kind.
  template <typename T, typename = std::enable_if_t<JS::IsBaseTraceType_v<T>>>
  bool is() const {
    return kind() == JS::MapTypeToTraceKind<T>::kind;
  }

  // Conversions to more specific types must match the kind. Access to
  // further refined types is not allowed directly from a GCCellPtr.
  template <typename T, typename = std::enable_if_t<JS::IsBaseTraceType_v<T>>>
  T& as() const {
    MOZ_ASSERT(kind() == JS::MapTypeToTraceKind<T>::kind);
    // We can't use static_cast here, because the fact that JSObject
    // inherits from js::gc::Cell is not part of the public API.
    return *reinterpret_cast<T*>(asCell());
  }

  // Return a pointer to the cell this |GCCellPtr| refers to, or |nullptr|.
  // (It would be more symmetrical with |to| for this to return a |Cell&|, but
  // the result can be |nullptr|, and null references are undefined behavior.)
  js::gc::Cell* asCell() const {
    return reinterpret_cast<js::gc::Cell*>(ptr & ~OutOfLineTraceKindMask);
  }

  // The CC's trace logger needs an identity that is XPIDL serializable.
  uint64_t unsafeAsInteger() const {
    return static_cast<uint64_t>(unsafeAsUIntPtr());
  }
  // Inline mark bitmap access requires direct pointer arithmetic.
  uintptr_t unsafeAsUIntPtr() const {
    MOZ_ASSERT(asCell());
    MOZ_ASSERT(!js::gc::IsInsideNursery(asCell()));
    return reinterpret_cast<uintptr_t>(asCell());
  }

  MOZ_ALWAYS_INLINE bool mayBeOwnedByOtherRuntime() const {
    if (!is<JSString>() && !is<JS::Symbol>()) {
      return false;
    }
    if (is<JSString>()) {
      return JS::shadow::String::isPermanentAtom(asCell());
    }
    MOZ_ASSERT(is<JS::Symbol>());
    return JS::shadow::Symbol::isWellKnownSymbol(asCell());
  }

  GCCellPtr atomicGet() const {
    return GCCellPtr(__atomic_load_n(&ptr, __ATOMIC_RELAXED));
  }

  void atomicSet(const GCCellPtr& value) {
    __atomic_store_n(&ptr, value.ptr, __ATOMIC_RELAXED);
  }

 private:
  explicit GCCellPtr(uintptr_t ptr) : ptr(ptr) {}

  static uintptr_t checkedCast(void* p, JS::TraceKind traceKind) {
    auto* cell = static_cast<js::gc::Cell*>(p);
    MOZ_ASSERT((uintptr_t(p) & OutOfLineTraceKindMask) == 0);
    AssertGCThingHasType(cell, traceKind);
    // Store trace in the bottom bits of pointer for common kinds.
    uintptr_t kindBits = uintptr_t(traceKind);
    if (kindBits >= OutOfLineTraceKindMask) {
      kindBits = OutOfLineTraceKindMask;
    }
    return uintptr_t(p) | kindBits;
  }

  JS::TraceKind outOfLineKind() const;

  uintptr_t ptr;
} JS_HAZ_GC_POINTER;

// Unwraps the given GCCellPtr, calls the functor |f| with a template argument
// of the actual type of the pointer, and returns the result.
template <typename F>
auto MapGCThingTyped(GCCellPtr thing, F&& f) {
  switch (thing.kind()) {
#define JS_EXPAND_DEF(name, type, _, _1) \
  case JS::TraceKind::name:              \
    return f(&thing.as<type>());
    JS_FOR_EACH_TRACEKIND(JS_EXPAND_DEF);
#undef JS_EXPAND_DEF
    default:
      MOZ_CRASH("Invalid trace kind in MapGCThingTyped for GCCellPtr.");
  }
}

// Unwraps the given GCCellPtr and calls the functor |f| with a template
// argument of the actual type of the pointer. Doesn't return anything.
template <typename F>
void ApplyGCThingTyped(GCCellPtr thing, F&& f) {
  // This function doesn't do anything but is supplied for symmetry with other
  // MapGCThingTyped/ApplyGCThingTyped implementations that have to wrap the
  // functor to return a dummy value that is ignored.
  MapGCThingTyped(thing, f);
}

} /* namespace JS */

namespace js {
namespace gc {

namespace detail {

// `addr` must be an address within GC-controlled memory. Note that it cannot
// point just past GC-controlled memory.
static MOZ_ALWAYS_INLINE ChunkBase* GetGCAddressChunkBase(const void* addr) {
  MOZ_ASSERT(addr);
  auto* chunk = reinterpret_cast<ChunkBase*>(uintptr_t(addr) & ~ChunkMask);
  MOZ_ASSERT(chunk->runtime);
  MOZ_ASSERT(chunk->kind != ChunkKind::Invalid);
  return chunk;
}

static MOZ_ALWAYS_INLINE ChunkBase* GetCellChunkBase(const Cell* cell) {
  return GetGCAddressChunkBase(cell);
}

static MOZ_ALWAYS_INLINE ArenaChunkBase* GetCellChunkBase(
    const TenuredCell* cell) {
  MOZ_ASSERT(cell);
  auto* chunk = reinterpret_cast<ArenaChunkBase*>(uintptr_t(cell) & ~ChunkMask);
  MOZ_ASSERT(chunk->runtime);
  MOZ_ASSERT(chunk->kind == ChunkKind::TenuredArenas);
  return chunk;
}

static MOZ_ALWAYS_INLINE JS::Zone* GetTenuredGCThingZone(const void* ptr) {
  // This takes a void* because the compiler can't see type relationships in
  // this header. |ptr| must be a pointer to a tenured GC thing.
  ChunkBase* chunk = GetGCAddressChunkBase(ptr);
  MOZ_ASSERT(chunk->kind == ChunkKind::TenuredArenas);
  return static_cast<ArenaChunkBase*>(chunk)->info.zone;
}

static MOZ_ALWAYS_INLINE bool TenuredCellIsMarkedBlack(
    const TenuredCell* cell) {
  MOZ_ASSERT(cell);
  MOZ_ASSERT(!js::gc::IsInsideNursery(cell));

  ArenaChunkBase* chunk = GetCellChunkBase(cell);
  return chunk->markBits.isMarkedBlack(cell);
}

static MOZ_ALWAYS_INLINE bool NonBlackCellIsMarkedGray(
    const TenuredCell* cell) {
  // Return true if GrayOrBlackBit is set. Callers should check BlackBit first.

  MOZ_ASSERT(cell);
  MOZ_ASSERT(!js::gc::IsInsideNursery(cell));
  MOZ_ASSERT(!TenuredCellIsMarkedBlack(cell));

  ArenaChunkBase* chunk = GetCellChunkBase(cell);
  return chunk->markBits.markBit(cell, ColorBit::GrayOrBlackBit);
}

static MOZ_ALWAYS_INLINE bool TenuredCellIsMarkedGray(const TenuredCell* cell) {
  MOZ_ASSERT(cell);
  MOZ_ASSERT(!js::gc::IsInsideNursery(cell));
  ArenaChunkBase* chunk = GetCellChunkBase(cell);
  return chunk->markBits.isMarkedGray(cell);
}

static MOZ_ALWAYS_INLINE bool CellIsMarkedGray(const Cell* cell) {
  MOZ_ASSERT(cell);
  if (js::gc::IsInsideNursery(cell)) {
    return false;
  }
  return TenuredCellIsMarkedGray(reinterpret_cast<const TenuredCell*>(cell));
}

extern JS_PUBLIC_API bool CanCheckGrayBits(const TenuredCell* cell);

extern JS_PUBLIC_API bool CellIsMarkedGrayIfKnown(const TenuredCell* cell);

#ifdef DEBUG
extern JS_PUBLIC_API void AssertCellIsNotGray(const Cell* cell);

extern JS_PUBLIC_API bool ObjectIsMarkedBlack(const JSObject* obj);
#endif

MOZ_ALWAYS_INLINE bool ChunkPtrHasStoreBuffer(const void* ptr) {
  return GetGCAddressChunkBase(ptr)->storeBuffer;
}

} /* namespace detail */

MOZ_ALWAYS_INLINE bool IsInsideNursery(const Cell* cell) {
  MOZ_ASSERT(cell);
  return detail::ChunkPtrHasStoreBuffer(cell);
}

MOZ_ALWAYS_INLINE bool IsInsideNursery(const TenuredCell* cell) {
  MOZ_ASSERT(cell);
  MOZ_ASSERT(!IsInsideNursery(reinterpret_cast<const Cell*>(cell)));
  return false;
}

// Return whether |cell| is in the region of the nursery currently being
// collected.
MOZ_ALWAYS_INLINE bool InCollectedNurseryRegion(const Cell* cell) {
  MOZ_ASSERT(cell);
  return detail::GetCellChunkBase(cell)->getKind() ==
         ChunkKind::NurseryFromSpace;
}

// Allow use before the compiler knows the derivation of JSObject, JSString,
// JS::BigInt, and js::GetterSetter.
MOZ_ALWAYS_INLINE bool IsInsideNursery(const JSObject* obj) {
  return IsInsideNursery(reinterpret_cast<const Cell*>(obj));
}
MOZ_ALWAYS_INLINE bool IsInsideNursery(const JSString* str) {
  return IsInsideNursery(reinterpret_cast<const Cell*>(str));
}
MOZ_ALWAYS_INLINE bool IsInsideNursery(const JS::BigInt* bi) {
  return IsInsideNursery(reinterpret_cast<const Cell*>(bi));
}
MOZ_ALWAYS_INLINE bool IsInsideNursery(const js::GetterSetter* gs) {
  return IsInsideNursery(reinterpret_cast<const Cell*>(gs));
}
MOZ_ALWAYS_INLINE bool InCollectedNurseryRegion(const JSObject* obj) {
  return InCollectedNurseryRegion(reinterpret_cast<const Cell*>(obj));
}

// Helper function to convert GC cell types to the base Cell pointer as
// consumers can't see the inheritance relationship externally.
#define EXPAND_TO_CELL(_1, type, _2, _3)        \
  MOZ_ALWAYS_INLINE Cell* ToCell(type* thing) { \
    return reinterpret_cast<Cell*>(thing);      \
  }
JS_FOR_EACH_TRACEKIND(EXPAND_TO_CELL)
#undef EXPAND_TO_CELL

MOZ_ALWAYS_INLINE bool IsCellPointerValid(const void* ptr) {
  auto addr = uintptr_t(ptr);
  if (addr < ChunkSize || addr % CellAlignBytes != 0) {
    return false;
  }

  auto* cell = reinterpret_cast<const Cell*>(ptr);
  if (!IsInsideNursery(cell)) {
    return detail::GetTenuredGCThingZone(cell) != nullptr;
  }

  return true;
}

MOZ_ALWAYS_INLINE bool IsCellPointerValidOrNull(const void* cell) {
  if (!cell) {
    return true;
  }
  return IsCellPointerValid(cell);
}

} /* namespace gc */
} /* namespace js */

namespace JS {

extern JS_PUBLIC_API Zone* GetTenuredGCThingZone(GCCellPtr thing);

extern JS_PUBLIC_API Zone* GetNurseryCellZone(js::gc::Cell* cell);

static MOZ_ALWAYS_INLINE Zone* GetGCThingZone(GCCellPtr thing) {
  if (!js::gc::IsInsideNursery(thing.asCell())) {
    return js::gc::detail::GetTenuredGCThingZone(thing.asCell());
  }

  return GetNurseryCellZone(thing.asCell());
}

static MOZ_ALWAYS_INLINE Zone* GetStringZone(JSString* str) {
  if (!js::gc::IsInsideNursery(str)) {
    return js::gc::detail::GetTenuredGCThingZone(str);
  }

  return GetNurseryCellZone(reinterpret_cast<js::gc::Cell*>(str));
}

extern JS_PUBLIC_API Zone* GetObjectZone(JSObject* obj);

// Check whether a GC thing is gray. If the gray marking state is unknown
// (e.g. due to OOM during gray unmarking) this returns false.
static MOZ_ALWAYS_INLINE bool GCThingIsMarkedGray(GCCellPtr thing) {
  js::gc::Cell* cell = thing.asCell();
  if (IsInsideNursery(cell)) {
    return false;
  }

  auto* tenuredCell = reinterpret_cast<js::gc::TenuredCell*>(cell);
  return js::gc::detail::CellIsMarkedGrayIfKnown(tenuredCell);
}

// Specialised gray marking checks for use by the cycle collector. These are not
// called during incremental GC or when the gray bits are invalid.
static MOZ_ALWAYS_INLINE bool GCThingIsMarkedGrayInCC(js::gc::Cell* cell) {
  if (IsInsideNursery(cell)) {
    return false;
  }

  auto* tenuredCell = reinterpret_cast<js::gc::TenuredCell*>(cell);
  MOZ_ASSERT(js::gc::detail::CanCheckGrayBits(tenuredCell));
  return js::gc::detail::TenuredCellIsMarkedGray(tenuredCell);
}
static MOZ_ALWAYS_INLINE bool GCThingIsMarkedGrayInCC(GCCellPtr thing) {
  return GCThingIsMarkedGrayInCC(thing.asCell());
}

extern JS_PUBLIC_API JS::TraceKind GCThingTraceKind(void* thing);

/*
 * Returns true when writes to GC thing pointers (and reads from weak pointers)
 * must call an incremental barrier. This is generally only true when running
 * mutator code in-between GC slices. At other times, the barrier may be elided
 * for performance.
 */
extern JS_PUBLIC_API bool IsIncrementalBarrierNeeded(JSContext* cx);

/*
 * Notify the GC that a reference to a JSObject is about to be overwritten.
 * This method must be called if IsIncrementalBarrierNeeded.
 */
extern JS_PUBLIC_API void IncrementalPreWriteBarrier(JSObject* obj);

/*
 * Notify the GC that a reference to a tenured GC cell is about to be
 * overwritten. This method must be called if IsIncrementalBarrierNeeded.
 */
extern JS_PUBLIC_API void IncrementalPreWriteBarrier(GCCellPtr thing);

/**
 * Unsets the gray bit for anything reachable from |thing|. |kind| should not be
 * JS::TraceKind::Shape. |thing| should be non-null. The return value indicates
 * if anything was unmarked.
 */
extern JS_PUBLIC_API bool UnmarkGrayGCThingRecursively(GCCellPtr thing);

}  // namespace JS

namespace js {
namespace gc {

extern JS_PUBLIC_API void PerformIncrementalReadBarrier(JS::GCCellPtr thing);

static MOZ_ALWAYS_INLINE void ExposeGCThingToActiveJS(JS::GCCellPtr thing) {
  // js::jit::WeakMapValueReadBarrier inlines a specialized version of this
  // function designed to be called from jitcode. If this code is changed, it
  // should be kept in sync.

  // TODO: I'd like to assert !RuntimeHeapIsBusy() here but this gets
  // called while we are tracing the heap, e.g. during memory reporting
  // (see bug 1313318).
  MOZ_ASSERT(!JS::RuntimeHeapIsCollecting());

  // GC things residing in the nursery cannot be gray: they have no mark bits.
  // All live objects in the nursery are moved to tenured at the beginning of
  // each GC slice, so the gray marker never sees nursery things.
  if (IsInsideNursery(thing.asCell())) {
    return;
  }

  auto* cell = reinterpret_cast<TenuredCell*>(thing.asCell());
  if (detail::TenuredCellIsMarkedBlack(cell)) {
    return;
  }

  // GC things owned by other runtimes are always black.
  MOZ_ASSERT(!thing.mayBeOwnedByOtherRuntime());

  auto* zone = JS::shadow::Zone::from(detail::GetTenuredGCThingZone(cell));
  if (zone->needsMarkingBarrier()) {
    PerformIncrementalReadBarrier(thing);
  } else if (!zone->isGCPreparing() && detail::NonBlackCellIsMarkedGray(cell)) {
    MOZ_ALWAYS_TRUE(JS::UnmarkGrayGCThingRecursively(thing));
  }

  MOZ_ASSERT_IF(!zone->isGCPreparing(), !detail::TenuredCellIsMarkedGray(cell));
}

static MOZ_ALWAYS_INLINE void IncrementalReadBarrier(JS::GCCellPtr thing) {
  // This is a lighter version of ExposeGCThingToActiveJS that doesn't do gray
  // unmarking.

  if (IsInsideNursery(thing.asCell())) {
    return;
  }

  auto* cell = reinterpret_cast<TenuredCell*>(thing.asCell());
  auto* zone = JS::shadow::Zone::from(detail::GetTenuredGCThingZone(cell));
  if (zone->needsMarkingBarrier() && !detail::TenuredCellIsMarkedBlack(cell)) {
    // GC things owned by other runtimes are always black.
    MOZ_ASSERT(!thing.mayBeOwnedByOtherRuntime());
    PerformIncrementalReadBarrier(thing);
  }
}

template <typename T>
extern JS_PUBLIC_API bool EdgeNeedsSweepUnbarrieredSlow(T* thingp);

static MOZ_ALWAYS_INLINE bool EdgeNeedsSweepUnbarriered(JSObject** objp) {
  // This function does not handle updating nursery pointers. Raw JSObject
  // pointers should be updated separately or replaced with
  // JS::Heap<JSObject*> which handles this automatically.
  MOZ_ASSERT(!JS::RuntimeHeapIsMinorCollecting());
  if (IsInsideNursery(*objp)) {
    return false;
  }

  auto zone = JS::shadow::Zone::from(detail::GetTenuredGCThingZone(*objp));
  if (!zone->isGCSweepingOrCompacting()) {
    return false;
  }

  return EdgeNeedsSweepUnbarrieredSlow(objp);
}

/*
 * Sample data about internally mapped memory. This includes all GC heap
 * allocations (and excludes js_alloc allocations).
 */
struct ProfilerMemoryCounts {
  size_t bytes = 0;
  uint64_t operations = 0;
};
JS_PUBLIC_API ProfilerMemoryCounts GetProfilerMemoryCounts();

}  // namespace gc
}  // namespace js

namespace JS {

/*
 * This should be called when an object that is marked gray is exposed to the JS
 * engine (by handing it to running JS code or writing it into live JS
 * data). During incremental GC, since the gray bits haven't been computed yet,
 * we conservatively mark the object black.
 */
static MOZ_ALWAYS_INLINE void ExposeObjectToActiveJS(JSObject* obj) {
  MOZ_ASSERT(obj);
  MOZ_ASSERT(!js::gc::EdgeNeedsSweepUnbarrieredSlow(&obj));
  js::gc::ExposeGCThingToActiveJS(GCCellPtr(obj));
}

} /* namespace JS */

#endif /* js_HeapAPI_h */