Heap.h

/* -*- 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/. */

#ifndef gc_Heap_h
#define gc_Heap_h

#include "mozilla/ArrayUtils.h"
#include "mozilla/Atomics.h"
#include "mozilla/Attributes.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/PodOperations.h"

#include <stddef.h>
#include <stdint.h>

#include "jsfriendapi.h"
#include "jspubtd.h"
#include "jstypes.h"
#include "jsutil.h"

#include "ds/BitArray.h"
#include "gc/AllocKind.h"
#include "gc/GCEnum.h"
#include "gc/Memory.h"
#include "js/HeapAPI.h"
#include "js/RootingAPI.h"
#include "js/TracingAPI.h"
#include "js/TypeDecls.h"

#include "vm/Printer.h"

namespace js {

class AutoLockGC;
class AutoLockGCBgAlloc;
class FreeOp;

namespace gc {

class Arena;
class ArenaCellSet;
class ArenaList;
class SortedArenaList;
class StoreBuffer;
class TenuredCell;
struct Chunk;

/*
 * This flag allows an allocation site to request a specific heap based upon the
 * estimated lifetime or lifetime requirements of objects allocated from that
 * site.
 */
enum InitialHeap : uint8_t { DefaultHeap, TenuredHeap };

// Cells are aligned to CellAlignShift, so the largest tagged null pointer is:
const uintptr_t LargestTaggedNullCellPointer = (1 << CellAlignShift) - 1;

/*
 * 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 MarkBitsPerCell = 2;
const size_t MinCellSize = CellBytesPerMarkBit * MarkBitsPerCell;

constexpr size_t DivideAndRoundUp(size_t numerator, size_t divisor) {
  return (numerator + divisor - 1) / divisor;
}

static_assert(ArenaSize % CellAlignBytes == 0,
              "Arena size must be a multiple of cell alignment");

/*
 * 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 = DivideAndRoundUp(ArenaBitmapBits, 8);
const size_t ArenaBitmapWords =
    DivideAndRoundUp(ArenaBitmapBits, JS_BITS_PER_WORD);

/*
 * A FreeSpan represents a contiguous sequence of free cells in an Arena. It
 * can take two forms.
 *
 * - In an empty span, |first| and |last| are both zero.
 *
 * - In a non-empty span, |first| is the address of the first free thing in the
 *   span, and |last| is the address of the last free thing in the span.
 *   Furthermore, the memory pointed to by |last| holds a FreeSpan structure
 *   that points to the next span (which may be empty); this works because
 *   sizeof(FreeSpan) is less than the smallest thingSize.
 */
class FreeSpan {
  friend class Arena;
  friend class ArenaCellIterImpl;
  friend class ArenaFreeCellIter;

  uint16_t first;
  uint16_t last;

 public:
  // This inits just |first| and |last|; if the span is non-empty it doesn't
  // do anything with the next span stored at |last|.
  void initBounds(uintptr_t firstArg, uintptr_t lastArg, const Arena* arena) {
    checkRange(firstArg, lastArg, arena);
    first = firstArg;
    last = lastArg;
  }

  void initAsEmpty() {
    first = 0;
    last = 0;
  }

  // This sets |first| and |last|, and also sets the next span stored at
  // |last| as empty. (As a result, |firstArg| and |lastArg| cannot represent
  // an empty span.)
  void initFinal(uintptr_t firstArg, uintptr_t lastArg, const Arena* arena) {
    initBounds(firstArg, lastArg, arena);
    FreeSpan* last = nextSpanUnchecked(arena);
    last->initAsEmpty();
    checkSpan(arena);
  }

  bool isEmpty() const { return !first; }

  Arena* getArenaUnchecked() { return reinterpret_cast<Arena*>(this); }
  inline Arena* getArena();

  static size_t offsetOfFirst() { return offsetof(FreeSpan, first); }

  static size_t offsetOfLast() { return offsetof(FreeSpan, last); }

  // Like nextSpan(), but no checking of the following span is done.
  FreeSpan* nextSpanUnchecked(const Arena* arena) const {
    MOZ_ASSERT(arena && !isEmpty());
    return reinterpret_cast<FreeSpan*>(uintptr_t(arena) + last);
  }

  const FreeSpan* nextSpan(const Arena* arena) const {
    checkSpan(arena);
    return nextSpanUnchecked(arena);
  }

  MOZ_ALWAYS_INLINE TenuredCell* allocate(size_t thingSize) {
    // Eschew the usual checks, because this might be the placeholder span.
    // If this is somehow an invalid, non-empty span, checkSpan() will catch it.
    Arena* arena = getArenaUnchecked();
    checkSpan(arena);
    uintptr_t thing = uintptr_t(arena) + first;
    if (first < last) {
      // We have space for at least two more things, so do a simple
      // bump-allocate.
      first += thingSize;
    } else if (MOZ_LIKELY(first)) {
      // The last space points to the next free span (which may be empty).
      const FreeSpan* next = nextSpan(arena);
      first = next->first;
      last = next->last;
    } else {
      return nullptr;  // The span is empty.
    }
    checkSpan(arena);
    DebugOnlyPoison(reinterpret_cast<void*>(thing),
                    JS_ALLOCATED_TENURED_PATTERN, thingSize,
                    MemCheckKind::MakeUndefined);
    return reinterpret_cast<TenuredCell*>(thing);
  }

  inline void checkSpan(const Arena* arena) const;
  inline void checkRange(uintptr_t first, uintptr_t last,
                         const Arena* arena) const;
};

/*
 * Arenas are the allocation units of the tenured heap in the GC. An arena
 * is 4kiB in size and 4kiB-aligned. It starts with several header fields
 * followed by some bytes of padding. The remainder of the arena is filled
 * with GC things of a particular AllocKind. The padding ensures that the
 * GC thing array ends exactly at the end of the arena:
 *
 * <----------------------------------------------> = ArenaSize bytes
 * +---------------+---------+----+----+-----+----+
 * | header fields | padding | T0 | T1 | ... | Tn |
 * +---------------+---------+----+----+-----+----+
 * <-------------------------> = first thing offset
 */
class Arena {
  static JS_FRIEND_DATA const uint32_t ThingSizes[];
  static JS_FRIEND_DATA const uint32_t FirstThingOffsets[];
  static JS_FRIEND_DATA const uint32_t ThingsPerArena[];

  /*
   * The first span of free things in the arena. Most of these spans are
   * stored as offsets in free regions of the data array, and most operations
   * on FreeSpans take an Arena pointer for safety. However, the FreeSpans
   * used for allocation are stored here, at the start of an Arena, and use
   * their own address to grab the next span within the same Arena.
   */
  FreeSpan firstFreeSpan;

 public:
  /*
   * The zone that this Arena is contained within, when allocated. The offset
   * of this field must match the ArenaZoneOffset stored in js/HeapAPI.h,
   * as is statically asserted below.
   */
  JS::Zone* zone;

  /*
   * Arena::next has two purposes: when unallocated, it points to the next
   * available Arena. When allocated, it points to the next Arena in the same
   * zone and with the same alloc kind.
   */
  Arena* next;

 private:
  /*
   * One of the AllocKind constants or AllocKind::LIMIT when the arena does
   * not contain any GC things and is on the list of empty arenas in the GC
   * chunk.
   *
   * We use 8 bits for the alloc kind so the compiler can use byte-level
   * memory instructions to access it.
   */
  size_t allocKind : 8;

 private:
  /*
   * When recursive marking uses too much stack we delay marking of
   * arenas and link them into a list for later processing. This
   * uses the following fields.
   */
  static const size_t DELAYED_MARKING_FLAG_BITS = 3;
  static const size_t DELAYED_MARKING_ARENA_BITS =
      JS_BITS_PER_WORD - 8 - DELAYED_MARKING_FLAG_BITS;
  size_t onDelayedMarkingList_ : 1;
  size_t hasDelayedBlackMarking_ : 1;
  size_t hasDelayedGrayMarking_ : 1;
  size_t nextDelayedMarkingArena_ : DELAYED_MARKING_ARENA_BITS;
  static_assert(
      DELAYED_MARKING_ARENA_BITS >= JS_BITS_PER_WORD - ArenaShift,
      "Arena::nextDelayedMarkingArena_ packing assumes that ArenaShift has "
      "enough bits to cover allocKind and delayed marking state.");

  union {
    /*
     * For arenas in zones other than the atoms zone, if non-null, points
     * to an ArenaCellSet that represents the set of cells in this arena
     * that are in the nursery's store buffer.
     */
    ArenaCellSet* bufferedCells_;

    /*
     * For arenas in the atoms zone, the starting index into zone atom
     * marking bitmaps (see AtomMarking.h) of the things in this zone.
     * Atoms never refer to nursery things, so no store buffer index is
     * needed.
     */
    size_t atomBitmapStart_;
  };

 public:
  /*
   * The size of data should be |ArenaSize - offsetof(data)|, but the offset
   * is not yet known to the compiler, so we do it by hand. |firstFreeSpan|
   * takes up 8 bytes on 64-bit due to alignment requirements; the rest are
   * obvious. This constant is stored in js/HeapAPI.h.
   */
  uint8_t data[ArenaSize - ArenaHeaderSize];

  void init(JS::Zone* zoneArg, AllocKind kind, const AutoLockGC& lock);

  // Sets |firstFreeSpan| to the Arena's entire valid range, and
  // also sets the next span stored at |firstFreeSpan.last| as empty.
  void setAsFullyUnused() {
    AllocKind kind = getAllocKind();
    firstFreeSpan.first = firstThingOffset(kind);
    firstFreeSpan.last = lastThingOffset(kind);
    FreeSpan* last = firstFreeSpan.nextSpanUnchecked(this);
    last->initAsEmpty();
  }

  // Initialize an arena to its unallocated state. For arenas that were
  // previously allocated for some zone, use release() instead.
  void setAsNotAllocated() {
    firstFreeSpan.initAsEmpty();
    zone = nullptr;
    allocKind = size_t(AllocKind::LIMIT);
    onDelayedMarkingList_ = 0;
    hasDelayedBlackMarking_ = 0;
    hasDelayedGrayMarking_ = 0;
    nextDelayedMarkingArena_ = 0;
    bufferedCells_ = nullptr;
  }

  // Return an allocated arena to its unallocated state.
  inline void release(const AutoLockGC& lock);

  uintptr_t address() const {
    checkAddress();
    return uintptr_t(this);
  }

  inline void checkAddress() const;

  inline Chunk* chunk() const;

  bool allocated() const {
    MOZ_ASSERT(IsAllocKind(AllocKind(allocKind)));
    return IsValidAllocKind(AllocKind(allocKind));
  }

  AllocKind getAllocKind() const {
    MOZ_ASSERT(allocated());
    return AllocKind(allocKind);
  }

  FreeSpan* getFirstFreeSpan() { return &firstFreeSpan; }

  static size_t thingSize(AllocKind kind) { return ThingSizes[size_t(kind)]; }
  static size_t thingsPerArena(AllocKind kind) {
    return ThingsPerArena[size_t(kind)];
  }
  static size_t thingsSpan(AllocKind kind) {
    return thingsPerArena(kind) * thingSize(kind);
  }

  static size_t firstThingOffset(AllocKind kind) {
    return FirstThingOffsets[size_t(kind)];
  }
  static size_t lastThingOffset(AllocKind kind) {
    return ArenaSize - thingSize(kind);
  }

  size_t getThingSize() const { return thingSize(getAllocKind()); }
  size_t getThingsPerArena() const { return thingsPerArena(getAllocKind()); }
  size_t getThingsSpan() const { return getThingsPerArena() * getThingSize(); }
  size_t getFirstThingOffset() const {
    return firstThingOffset(getAllocKind());
  }

  uintptr_t thingsStart() const { return address() + getFirstThingOffset(); }
  uintptr_t thingsEnd() const { return address() + ArenaSize; }

  bool isEmpty() const {
    // Arena is empty if its first span covers the whole arena.
    firstFreeSpan.checkSpan(this);
    AllocKind kind = getAllocKind();
    return firstFreeSpan.first == firstThingOffset(kind) &&
           firstFreeSpan.last == lastThingOffset(kind);
  }

  bool hasFreeThings() const { return !firstFreeSpan.isEmpty(); }

  size_t numFreeThings(size_t thingSize) const {
    firstFreeSpan.checkSpan(this);
    size_t numFree = 0;
    const FreeSpan* span = &firstFreeSpan;
    for (; !span->isEmpty(); span = span->nextSpan(this)) {
      numFree += (span->last - span->first) / thingSize + 1;
    }
    return numFree;
  }

  size_t countFreeCells() { return numFreeThings(getThingSize()); }
  size_t countUsedCells() { return getThingsPerArena() - countFreeCells(); }

  bool inFreeList(uintptr_t thing) {
    uintptr_t base = address();
    const FreeSpan* span = &firstFreeSpan;
    for (; !span->isEmpty(); span = span->nextSpan(this)) {
      /* If the thing comes before the current span, it's not free. */
      if (thing < base + span->first) {
        return false;
      }

      /* If we find it before the end of the span, it's free. */
      if (thing <= base + span->last) {
        return true;
      }
    }
    return false;
  }

  static bool isAligned(uintptr_t thing, size_t thingSize) {
    /* Things ends at the arena end. */
    uintptr_t tailOffset = ArenaSize - (thing & ArenaMask);
    return tailOffset % thingSize == 0;
  }

  bool onDelayedMarkingList() const { return onDelayedMarkingList_; }

  Arena* getNextDelayedMarking() const {
    MOZ_ASSERT(onDelayedMarkingList_);
    return reinterpret_cast<Arena*>(nextDelayedMarkingArena_ << ArenaShift);
  }

  void setNextDelayedMarkingArena(Arena* arena) {
    MOZ_ASSERT(!(uintptr_t(arena) & ArenaMask));
    MOZ_ASSERT(!onDelayedMarkingList_);
    MOZ_ASSERT(!hasDelayedBlackMarking_);
    MOZ_ASSERT(!hasDelayedGrayMarking_);
    MOZ_ASSERT(!nextDelayedMarkingArena_);
    onDelayedMarkingList_ = 1;
    if (arena) {
      nextDelayedMarkingArena_ = arena->address() >> ArenaShift;
    }
  }

  void updateNextDelayedMarkingArena(Arena* arena) {
    MOZ_ASSERT(!(uintptr_t(arena) & ArenaMask));
    MOZ_ASSERT(onDelayedMarkingList_);
    nextDelayedMarkingArena_ = arena ? arena->address() >> ArenaShift : 0;
  }

  bool hasDelayedMarking(MarkColor color) const {
    MOZ_ASSERT(onDelayedMarkingList_);
    return color == MarkColor::Black ? hasDelayedBlackMarking_
                                     : hasDelayedGrayMarking_;
  }

  bool hasAnyDelayedMarking() const {
    MOZ_ASSERT(onDelayedMarkingList_);
    return hasDelayedBlackMarking_ || hasDelayedGrayMarking_;
  }

  void setHasDelayedMarking(MarkColor color, bool value) {
    MOZ_ASSERT(onDelayedMarkingList_);
    if (color == MarkColor::Black) {
      hasDelayedBlackMarking_ = value;
    } else {
      hasDelayedGrayMarking_ = value;
    }
  }

  void clearDelayedMarkingState() {
    MOZ_ASSERT(onDelayedMarkingList_);
    onDelayedMarkingList_ = 0;
    hasDelayedBlackMarking_ = 0;
    hasDelayedGrayMarking_ = 0;
    nextDelayedMarkingArena_ = 0;
  }

  inline ArenaCellSet*& bufferedCells();
  inline size_t& atomBitmapStart();

  template <typename T>
  size_t finalize(FreeOp* fop, AllocKind thingKind, size_t thingSize);

  static void staticAsserts();

  void unmarkAll();
  void unmarkPreMarkedFreeCells();

  void arenaAllocatedDuringGC();

#ifdef DEBUG
  void checkNoMarkedFreeCells();
#endif
};

static_assert(ArenaZoneOffset == offsetof(Arena, zone),
              "The hardcoded API zone offset must match the actual offset.");

static_assert(sizeof(Arena) == ArenaSize,
              "ArenaSize must match the actual size of the Arena structure.");

static_assert(
    offsetof(Arena, data) == ArenaHeaderSize,
    "ArenaHeaderSize must match the actual size of the header fields.");

inline Arena* FreeSpan::getArena() {
  Arena* arena = getArenaUnchecked();
  arena->checkAddress();
  return arena;
}

inline void FreeSpan::checkSpan(const Arena* arena) const {
#ifdef DEBUG
  if (!first) {
    MOZ_ASSERT(!first && !last);
    return;
  }

  arena->checkAddress();
  checkRange(first, last, arena);

  // If there's a following span, it must have a higher address,
  // and the gap must be at least 2 * thingSize.
  const FreeSpan* next = nextSpanUnchecked(arena);
  if (next->first) {
    checkRange(next->first, next->last, arena);
    size_t thingSize = arena->getThingSize();
    MOZ_ASSERT(last + 2 * thingSize <= next->first);
  }
#endif
}

inline void FreeSpan::checkRange(uintptr_t first, uintptr_t last,
                                 const Arena* arena) const {
#ifdef DEBUG
  MOZ_ASSERT(arena);
  MOZ_ASSERT(first <= last);
  AllocKind thingKind = arena->getAllocKind();
  MOZ_ASSERT(first >= Arena::firstThingOffset(thingKind));
  MOZ_ASSERT(last <= Arena::lastThingOffset(thingKind));
  MOZ_ASSERT((last - first) % Arena::thingSize(thingKind) == 0);
#endif
}

/*
 * The tail of the chunk info is shared between all chunks in the system, both
 * nursery and tenured. This structure is locatable from any GC pointer by
 * aligning to 1MiB.
 */
struct ChunkTrailer {
  // Construct a Nursery ChunkTrailer.
  ChunkTrailer(JSRuntime* rt, StoreBuffer* sb)
      : location(ChunkLocation::Nursery), storeBuffer(sb), runtime(rt) {}

  // Construct a Tenured heap ChunkTrailer.
  explicit ChunkTrailer(JSRuntime* rt)
      : location(ChunkLocation::TenuredHeap),
        storeBuffer(nullptr),
        runtime(rt) {}

 public:
  // The index of the chunk in the nursery, or LocationTenuredHeap.
  ChunkLocation location;
  uint32_t : 32;  // padding

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

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

static_assert(sizeof(ChunkTrailer) == ChunkTrailerSize,
              "ChunkTrailer size must match the API defined size.");

// The chunk header (located at the end of the chunk to preserve arena
// alignment).
struct ChunkInfo {
  void init() { next = prev = nullptr; }

 private:
  friend class ChunkPool;
  Chunk* next;
  Chunk* prev;

 public:
  /* Free arenas are linked together with arena.next. */
  Arena* freeArenasHead;

#if JS_BITS_PER_WORD == 32
  /*
   * Calculating sizes and offsets is simpler if sizeof(ChunkInfo) is
   * architecture-independent.
   */
  char padding[24];
#endif

  /*
   * Decommitted arenas are tracked by a bitmap in the chunk header. We use
   * this offset to start our search iteration close to a decommitted arena
   * that we can allocate.
   */
  uint32_t lastDecommittedArenaOffset;

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

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

/*
 * Calculating ArenasPerChunk:
 *
 * In order 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 two dependent fields are bitmap and decommittedArenas.
 *
 * For the mark bitmap, we know that each arena will use a fixed number of full
 * bytes: ArenaBitmapBytes. The full size of the header data is this number
 * multiplied by the eventual number of arenas we have in the header. We,
 * conceptually, distribute this header data among the individual arenas and do
 * not include it in the header. This way we do not have to worry about its
 * variable size: it gets attached to the variable number we are computing.
 *
 * For the decommitted arena bitmap, we only have 1 bit per arena, so this
 * technique will not work. Instead, we observe that we do not have enough
 * header info to fill 8 full arenas: it is currently 4 on 64bit, less on
 * 32bit. Thus, with current numbers, we need 64 bytes for decommittedArenas.
 * This will not become 63 bytes unless we double the data required in the
 * header. Therefore, we just compute the number of bytes required to track
 * every possible arena and do not worry about slop bits, since there are too
 * few to usefully allocate.
 *
 * To actually compute the number of arenas we can allocate in a chunk, we
 * divide the amount of available space less the header info (not including
 * the mark bitmap which is distributed into the arena size) by the size of
 * the arena (with the mark bitmap bytes it uses).
 */
const size_t BytesPerArenaWithHeader = ArenaSize + ArenaBitmapBytes;
const size_t ChunkDecommitBitmapBytes = ChunkSize / ArenaSize / CHAR_BIT;
const size_t ChunkBytesAvailable = ChunkSize - sizeof(ChunkTrailer) -
                                   sizeof(ChunkInfo) - ChunkDecommitBitmapBytes;
const size_t ArenasPerChunk = ChunkBytesAvailable / BytesPerArenaWithHeader;

#ifdef JS_GC_SMALL_CHUNK_SIZE
static_assert(ArenasPerChunk == 62,
              "Do not accidentally change our heap's density.");
#else
static_assert(ArenasPerChunk == 252,
              "Do not accidentally change our heap's density.");
#endif

/* A chunk bitmap contains enough mark bits for all the cells in a chunk. */
struct ChunkBitmap {
  volatile uintptr_t bitmap[ArenaBitmapWords * ArenasPerChunk];

 public:
  ChunkBitmap() {}

  MOZ_ALWAYS_INLINE void getMarkWordAndMask(const TenuredCell* cell,
                                            ColorBit colorBit,
                                            uintptr_t** wordp,
                                            uintptr_t* maskp) {
    MOZ_ASSERT(size_t(colorBit) < MarkBitsPerCell);
    detail::GetGCThingMarkWordAndMask(uintptr_t(cell), colorBit, wordp, maskp);
  }

  MOZ_ALWAYS_INLINE MOZ_TSAN_BLACKLIST bool markBit(const TenuredCell* cell,
                                                    ColorBit colorBit) {
    uintptr_t *word, mask;
    getMarkWordAndMask(cell, colorBit, &word, &mask);
    return *word & mask;
  }

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

  MOZ_ALWAYS_INLINE MOZ_TSAN_BLACKLIST bool isMarkedBlack(
      const TenuredCell* cell) {
    return markBit(cell, ColorBit::BlackBit);
  }

  MOZ_ALWAYS_INLINE MOZ_TSAN_BLACKLIST bool isMarkedGray(
      const TenuredCell* cell) {
    return !markBit(cell, ColorBit::BlackBit) &&
           markBit(cell, ColorBit::GrayOrBlackBit);
  }

  // The return value indicates if the cell went from unmarked to marked.
  MOZ_ALWAYS_INLINE bool markIfUnmarked(const TenuredCell* cell,
                                        MarkColor color) {
    uintptr_t *word, mask;
    getMarkWordAndMask(cell, ColorBit::BlackBit, &word, &mask);
    if (*word & mask) {
      return false;
    }
    if (color == MarkColor::Black) {
      *word |= mask;
    } else {
      /*
       * We use getMarkWordAndMask to recalculate both mask and word as
       * doing just mask << color may overflow the mask.
       */
      getMarkWordAndMask(cell, ColorBit::GrayOrBlackBit, &word, &mask);
      if (*word & mask) {
        return false;
      }
      *word |= mask;
    }
    return true;
  }

  MOZ_ALWAYS_INLINE void markBlack(const TenuredCell* cell) {
    uintptr_t *word, mask;
    getMarkWordAndMask(cell, ColorBit::BlackBit, &word, &mask);
    *word |= mask;
  }

  MOZ_ALWAYS_INLINE void copyMarkBit(TenuredCell* dst, const TenuredCell* src,
                                     ColorBit colorBit) {
    uintptr_t *srcWord, srcMask;
    getMarkWordAndMask(src, colorBit, &srcWord, &srcMask);

    uintptr_t *dstWord, dstMask;
    getMarkWordAndMask(dst, colorBit, &dstWord, &dstMask);

    *dstWord &= ~dstMask;
    if (*srcWord & srcMask) {
      *dstWord |= dstMask;
    }
  }

  MOZ_ALWAYS_INLINE void unmark(const TenuredCell* cell) {
    uintptr_t *word, mask;
    getMarkWordAndMask(cell, ColorBit::BlackBit, &word, &mask);
    *word &= ~mask;
    getMarkWordAndMask(cell, ColorBit::GrayOrBlackBit, &word, &mask);
    *word &= ~mask;
  }

  void clear() { memset((void*)bitmap, 0, sizeof(bitmap)); }

  uintptr_t* arenaBits(Arena* arena) {
    static_assert(
        ArenaBitmapBits == ArenaBitmapWords * JS_BITS_PER_WORD,
        "We assume that the part of the bitmap corresponding to the arena "
        "has the exact number of words so we do not need to deal with a word "
        "that covers bits from two arenas.");

    uintptr_t *word, unused;
    getMarkWordAndMask(reinterpret_cast<TenuredCell*>(arena->address()),
                       ColorBit::BlackBit, &word, &unused);
    return word;
  }
};

static_assert(ArenaBitmapBytes * ArenasPerChunk == sizeof(ChunkBitmap),
              "Ensure our ChunkBitmap actually covers all arenas.");
static_assert(js::gc::ChunkMarkBitmapBits == ArenaBitmapBits * ArenasPerChunk,
              "Ensure that the mark bitmap has the right number of bits.");

typedef BitArray<ArenasPerChunk> PerArenaBitmap;

const size_t ChunkPadSize = ChunkSize - (sizeof(Arena) * ArenasPerChunk) -
                            sizeof(ChunkBitmap) - sizeof(PerArenaBitmap) -
                            sizeof(ChunkInfo) - sizeof(ChunkTrailer);
static_assert(ChunkPadSize < BytesPerArenaWithHeader,
              "If the chunk padding is larger than an arena, we should have "
              "one more arena.");

/*
 * Chunks contain arenas and associated data structures (mark bitmap, delayed
 * marking state).
 */
struct Chunk {
  Arena arenas[ArenasPerChunk];

  /* Pad to full size to ensure cache alignment of ChunkInfo. */
  uint8_t padding[ChunkPadSize];

  ChunkBitmap bitmap;
  PerArenaBitmap decommittedArenas;
  ChunkInfo info;
  ChunkTrailer trailer;

  static Chunk* fromAddress(uintptr_t addr) {
    addr &= ~ChunkMask;
    return reinterpret_cast<Chunk*>(addr);
  }

  static bool withinValidRange(uintptr_t addr) {
    uintptr_t offset = addr & ChunkMask;
    return Chunk::fromAddress(addr)->isNurseryChunk()
               ? offset < ChunkSize - sizeof(ChunkTrailer)
               : offset < ArenasPerChunk * ArenaSize;
  }

  static size_t arenaIndex(uintptr_t addr) {
    MOZ_ASSERT(!Chunk::fromAddress(addr)->isNurseryChunk());
    MOZ_ASSERT(withinValidRange(addr));
    return (addr & ChunkMask) >> ArenaShift;
  }

  uintptr_t address() const {
    uintptr_t addr = reinterpret_cast<uintptr_t>(this);
    MOZ_ASSERT(!(addr & ChunkMask));
    return addr;
  }

  bool unused() const { return info.numArenasFree == ArenasPerChunk; }

  bool hasAvailableArenas() const { return info.numArenasFree != 0; }

  bool isNurseryChunk() const { return trailer.storeBuffer; }

  Arena* allocateArena(JSRuntime* rt, JS::Zone* zone, AllocKind kind,
                       const AutoLockGC& lock);

  void releaseArena(JSRuntime* rt, Arena* arena, const AutoLockGC& lock);
  void recycleArena(Arena* arena, SortedArenaList& dest, size_t thingsPerArena);

  MOZ_MUST_USE bool decommitOneFreeArena(JSRuntime* rt, AutoLockGC& lock);
  void decommitAllArenasWithoutUnlocking(const AutoLockGC& lock);

  static Chunk* allocate(JSRuntime* rt);
  void init(JSRuntime* rt);

 private:
  void decommitAllArenas();

  /* Search for a decommitted arena to allocate. */
  unsigned findDecommittedArenaOffset();
  Arena* fetchNextDecommittedArena();

  void addArenaToFreeList(JSRuntime* rt, Arena* arena);
  void addArenaToDecommittedList(const Arena* arena);

  void updateChunkListAfterAlloc(JSRuntime* rt, const AutoLockGC& lock);
  void updateChunkListAfterFree(JSRuntime* rt, const AutoLockGC& lock);

 public:
  /* Unlink and return the freeArenasHead. */
  Arena* fetchNextFreeArena(JSRuntime* rt);
};

static_assert(
    sizeof(Chunk) == ChunkSize,
    "Ensure the hardcoded chunk size definition actually matches the struct.");
static_assert(js::gc::ChunkMarkBitmapOffset == offsetof(Chunk, bitmap),
              "The hardcoded API bitmap offset must match the actual offset.");
static_assert(js::gc::ChunkRuntimeOffset ==
                  offsetof(Chunk, trailer) + offsetof(ChunkTrailer, runtime),
              "The hardcoded API runtime offset must match the actual offset.");
static_assert(
    js::gc::ChunkLocationOffset ==
        offsetof(Chunk, trailer) + offsetof(ChunkTrailer, location),
    "The hardcoded API location offset must match the actual offset.");
static_assert(
    js::gc::ChunkStoreBufferOffset ==
        offsetof(Chunk, trailer) + offsetof(ChunkTrailer, storeBuffer),
    "The hardcoded API storeBuffer offset must match the actual offset.");

/*
 * Tracks the used sizes for owned heap data and automatically maintains the
 * memory usage relationship between GCRuntime and Zones.
 */
class HeapSize {
  /*
   * A heap usage that contains our parent's heap usage, or null if this is
   * the top-level usage container.
   */
  HeapSize* const parent_;

  /*
   * The approximate number of bytes in use on the GC heap, to the nearest
   * ArenaSize. This does not include any malloc data. It also does not
   * include not-actively-used addresses that are still reserved at the OS
   * level for GC usage. It is atomic because it is updated by both the active
   * and GC helper threads.
   */
  mozilla::Atomic<size_t, mozilla::ReleaseAcquire,
                  mozilla::recordreplay::Behavior::DontPreserve>
      gcBytes_;

 public:
  explicit HeapSize(HeapSize* parent) : parent_(parent), gcBytes_(0) {}

  size_t gcBytes() const { return gcBytes_; }

  void addGCArena() {
    gcBytes_ += ArenaSize;
    if (parent_) {
      parent_->addGCArena();
    }
  }
  void removeGCArena() {
    MOZ_ASSERT(gcBytes_ >= ArenaSize);
    gcBytes_ -= ArenaSize;
    if (parent_) {
      parent_->removeGCArena();
    }
  }

  /* Pair to adoptArenas. Adopts the attendant usage statistics. */
  void adopt(HeapSize& other) {
    gcBytes_ += other.gcBytes_;
    other.gcBytes_ = 0;
  }
};

inline void Arena::checkAddress() const {
  mozilla::DebugOnly<uintptr_t> addr = uintptr_t(this);
  MOZ_ASSERT(addr);
  MOZ_ASSERT(!(addr & ArenaMask));
  MOZ_ASSERT(Chunk::withinValidRange(addr));
}

inline Chunk* Arena::chunk() const { return Chunk::fromAddress(address()); }

inline bool InFreeList(Arena* arena, void* thing) {
  uintptr_t addr = reinterpret_cast<uintptr_t>(thing);
  MOZ_ASSERT(Arena::isAligned(addr, arena->getThingSize()));
  return arena->inFreeList(addr);
}

static const int32_t ChunkLocationOffsetFromLastByte =
    int32_t(gc::ChunkLocationOffset) - int32_t(gc::ChunkMask);
static const int32_t ChunkStoreBufferOffsetFromLastByte =
    int32_t(gc::ChunkStoreBufferOffset) - int32_t(gc::ChunkMask);

} /* namespace gc */

namespace debug {

// Utility functions meant to be called from an interactive debugger.
enum class MarkInfo : int {
  BLACK = 0,
  GRAY = 1,
  UNMARKED = -1,
  NURSERY = -2,
};

// Get the mark color for a cell, in a way easily usable from a debugger.
MOZ_NEVER_INLINE MarkInfo GetMarkInfo(js::gc::Cell* cell);

// Sample usage from gdb:
//
//   (gdb) p $word = js::debug::GetMarkWordAddress(obj)
//   $1 = (uintptr_t *) 0x7fa56d5fe360
//   (gdb) p/x $mask = js::debug::GetMarkMask(obj, js::gc::GRAY)
//   $2 = 0x200000000
//   (gdb) watch *$word
//   Hardware watchpoint 7: *$word
//   (gdb) cond 7 *$word & $mask
//   (gdb) cont
//
// Note that this is *not* a watchpoint on a single bit. It is a watchpoint on
// the whole word, which will trigger whenever the word changes and the
// selected bit is set after the change.
//
// So if the bit changing is the desired one, this is exactly what you want.
// But if a different bit changes (either set or cleared), you may still stop
// execution if the $mask bit happened to already be set. gdb does not expose
// enough information to restrict the watchpoint to just a single bit.

// Return the address of the word containing the mark bits for the given cell,
// or nullptr if the cell is in the nursery.
MOZ_NEVER_INLINE uintptr_t* GetMarkWordAddress(js::gc::Cell* cell);

// Return the mask for the given cell and color bit, or 0 if the cell is in the
// nursery.
MOZ_NEVER_INLINE uintptr_t GetMarkMask(js::gc::Cell* cell, uint32_t colorBit);

} /* namespace debug */
} /* namespace js */

#endif /* gc_Heap_h */