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

/*
 * Implementation of compacting GC.
 */

#include "mozilla/Maybe.h"

#include "debugger/DebugAPI.h"
#include "gc/ArenaList.h"
#include "gc/GCInternals.h"
#include "gc/GCLock.h"
#include "gc/ParallelWork.h"
#include "gc/Zone.h"
#include "jit/JitCode.h"
#include "jit/JitRuntime.h"
#include "jit/JitZone.h"
#include "js/GCAPI.h"
#include "vm/HelperThreads.h"
#include "vm/Realm.h"
#include "wasm/WasmGcObject.h"

#include "gc/Heap-inl.h"
#include "gc/Marking-inl.h"
#include "gc/PrivateIterators-inl.h"
#include "gc/StableCellHasher-inl.h"
#include "gc/TraceMethods-inl.h"
#include "vm/GeckoProfiler-inl.h"

using namespace js;
using namespace js::gc;

using mozilla::Maybe;

using JS::SliceBudget;

bool GCRuntime::canRelocateZone(Zone* zone) const {
  return !zone->isAtomsZone();
}

void GCRuntime::beginCompactPhase() {
  MOZ_ASSERT(!isBackgroundSweeping());
  assertBackgroundSweepingFinished();

  gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::COMPACT);

  MOZ_ASSERT(zonesToMaybeCompact.ref().isEmpty());
  for (GCZonesIter zone(this); !zone.done(); zone.next()) {
    if (canRelocateZone(zone)) {
      zonesToMaybeCompact.ref().append(zone);
    }
  }

  startedCompacting = true;
  zonesCompacted = 0;

#ifdef DEBUG
  AutoLockGC lock(this);
  MOZ_ASSERT(!relocatedArenasToRelease);
#endif
}

IncrementalProgress GCRuntime::compactPhase(SliceBudget& sliceBudget,
                                            AutoGCSession& session) {
  assertBackgroundSweepingFinished();
  MOZ_ASSERT(startedCompacting);

  AutoMajorGCProfilerEntry s(this);
  gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::COMPACT);

  // TODO: JSScripts can move. If the sampler interrupts the GC in the
  // middle of relocating an arena, invalid JSScript pointers may be
  // accessed. Suppress all sampling until a finer-grained solution can be
  // found. See bug 1295775.
  AutoSuppressProfilerSampling suppressSampling(rt->mainContextFromOwnThread());

  ZoneList relocatedZones;
  Arena* relocatedArenas = nullptr;
  while (!zonesToMaybeCompact.ref().isEmpty()) {
    Zone* zone = zonesToMaybeCompact.ref().front();
    zonesToMaybeCompact.ref().removeFront();

    MOZ_ASSERT(nursery().isEmpty());
    zone->changeGCState(this, Zone::Finished, Zone::Compact);

    if (relocateArenas(zone, relocatedArenas, sliceBudget)) {
      updateZonePointersToRelocatedCells(zone);
      relocatedZones.append(zone);
      zonesCompacted++;
    } else {
      zone->changeGCState(this, Zone::Compact, Zone::Finished);
    }

    if (sliceBudget.isOverBudget()) {
      break;
    }
  }

  if (!relocatedZones.isEmpty()) {
    updateRuntimePointersToRelocatedCells(session);

    do {
      Zone* zone = relocatedZones.front();
      relocatedZones.removeFront();
      zone->changeGCState(this, Zone::Compact, Zone::Finished);
    } while (!relocatedZones.isEmpty());
  }

  clearRelocatedArenas(relocatedArenas);

#ifdef DEBUG
  protectOrReleaseRelocatedArenas(relocatedArenas);
#else
  releaseRelocatedArenas(relocatedArenas);
#endif

  // Clear caches that can contain cell pointers.
  rt->caches().purgeForCompaction();

#ifdef DEBUG
  checkHashTablesAfterMovingGC();
#endif

  return zonesToMaybeCompact.ref().isEmpty() ? Finished : NotFinished;
}

void GCRuntime::endCompactPhase() { startedCompacting = false; }

static bool ShouldRelocateAllArenas(JS::GCReason reason) {
  return reason == JS::GCReason::DEBUG_GC;
}

/*
 * Choose which arenas to relocate all cells from.
 *
 * Return a pair of arena pointers indicating the arenas to relocate that can be
 * passed to removeRange(), or null pointers if nothing can be relocated.
 */
std::pair<Arena*, Arena*> ArenaList::pickArenasToRelocate(
    AllocKind kind, size_t& arenaTotalOut, size_t& relocTotalOut) {
  // Relocate the greatest number of arenas such that the number of used cells
  // in relocated arenas is less than or equal to the number of free cells in
  // unrelocated arenas. In other words we only relocate cells we can move
  // into existing arenas, and we choose the least full areans to relocate.
  //
  // This is made easier by the fact that the start of the arena list has been
  // sorted in descending order of number of used cells, so we will always
  // relocate a sublist of the arena list. All we need to do is find the points
  // at which to start and end relocating.

  if (!hasNonFullArenas()) {
    // All arenas are full so no compacting is possible.
    return {nullptr, nullptr};
  }

  // Count non-full and full arenas and total used cells, and find the last
  // non-full arena.
  size_t fullArenaCount = 0;     // Number of full arenas (not relocated).
  size_t nonFullArenaCount = 0;  // Number of non-full arenas to consider.
  size_t totalUsedCells = 0;     // Total used cells in non-full arenas.
  Arena* lastNonFullArena = nullptr;

  Iterator arena = iter();
  for (; !arena.done(); arena.next()) {
    if (arena->isFull()) {
      break;
    }

    MOZ_ASSERT(!arena->isFull());
    nonFullArenaCount++;
    totalUsedCells += arena->countUsedCells();
    lastNonFullArena = arena.get();
  }
  for (; !arena.done(); arena.next()) {
    // It's likely that the final arena is not full but we ignore that.
    fullArenaCount++;
  }

  size_t previousFreeCells = 0;  // Total free cells before arena.
  size_t followingUsedCells =
      totalUsedCells;  // Total used cells in non full arenas afterwards.
  size_t relocCount = nonFullArenaCount;  // Number of arenas to relocate.
  Arena* prev = nullptr;                  // The previous arena considered.

  const size_t cellsPerArena = Arena::thingsPerArena(kind);

  // Examine the initial part of the list containing non-full arenas.
  for (arena = iter(); prev != lastNonFullArena;
       prev = arena.get(), arena.next()) {
    if (followingUsedCells <= previousFreeCells) {
      // We have found the point where cells in the following non-full arenas
      // can be relocated into the free space in previous arenas. We're done.
      break;
    }

    size_t freeCells = arena->countFreeCells();
    MOZ_ASSERT(freeCells != 0);
    size_t usedCells = cellsPerArena - freeCells;
    followingUsedCells -= usedCells;
    previousFreeCells += freeCells;
    MOZ_ASSERT(relocCount != 0);
    relocCount--;
  }

  MOZ_ASSERT((relocCount == 0) == (prev == lastNonFullArena));
  arenaTotalOut += fullArenaCount + nonFullArenaCount;
  relocTotalOut += relocCount;

  if (relocCount == 0) {
    return {nullptr, nullptr};
  }

  return {prev, lastNonFullArena};
}

#ifdef DEBUG
inline bool PtrIsInRange(const void* ptr, const void* start, size_t length) {
  return uintptr_t(ptr) - uintptr_t(start) < length;
}
#endif

static void RelocateCell(Zone* zone, TenuredCell* src, AllocKind thingKind,
                         size_t thingSize) {
  JS::AutoSuppressGCAnalysis nogc;

  // Allocate a new cell.
  MOZ_ASSERT(zone == src->zone());
  TenuredCell* dst =
      reinterpret_cast<TenuredCell*>(AllocateTenuredCellInGC(zone, thingKind));

  // Copy source cell contents to destination.
  memcpy(dst, src, thingSize);

  // Move any uid attached to the object.
  gc::TransferUniqueId(dst, src);

  if (IsObjectAllocKind(thingKind)) {
    auto* srcObj = static_cast<JSObject*>(static_cast<Cell*>(src));
    auto* dstObj = static_cast<JSObject*>(static_cast<Cell*>(dst));

    if (srcObj->is<NativeObject>()) {
      NativeObject* srcNative = &srcObj->as<NativeObject>();
      NativeObject* dstNative = &dstObj->as<NativeObject>();

      // Fixup the pointer to inline object elements if necessary.
      if (srcNative->hasFixedElements()) {
        uint32_t numShifted =
            srcNative->getElementsHeader()->numShiftedElements();
        dstNative->setFixedElements(numShifted);
      }
    } else if (srcObj->is<ProxyObject>()) {
      if (srcObj->as<ProxyObject>().usingInlineValueArray()) {
        dstObj->as<ProxyObject>().setInlineValueArray();
      }
    }

    // Call object moved hook if present.
    if (JSObjectMovedOp op = srcObj->getClass()->extObjectMovedOp()) {
      op(dstObj, srcObj);
    }

    MOZ_ASSERT_IF(
        dstObj->is<NativeObject>(),
        !PtrIsInRange(
            (const Value*)dstObj->as<NativeObject>().getDenseElements(), src,
            thingSize));
  }

  // Copy the mark bits.
  dst->copyMarkBitsFrom(src);

  // Poison the source cell contents except for the forwarding flag and pointer
  // which will be stored in the first word. We can't do this for buffer
  // allocations as these can be used as native object dynamic elements and this
  // would overwrite the elements flags which are needed when updating the
  // dynamic elements pointer.
#ifdef DEBUG
  bool poison = true;
  if (IsObjectAllocKind(thingKind)) {
    JSObject* srcObj = static_cast<JSObject*>(static_cast<Cell*>(src));
    poison = !(srcObj->is<WasmArrayObject>() &&
               srcObj->as<WasmArrayObject>().isDataInline());
  }
  if (poison) {
    AlwaysPoison(reinterpret_cast<uint8_t*>(src) + sizeof(uintptr_t),
                 JS_MOVED_TENURED_PATTERN, thingSize - sizeof(uintptr_t),
                 MemCheckKind::MakeNoAccess);
  }
#endif

  // Mark source cell as forwarded and leave a pointer to the destination.
  RelocationOverlay::forwardCell(src, dst);
}

static void RelocateArena(Arena* arena, SliceBudget& sliceBudget) {
  MOZ_ASSERT(arena->allocated());
  MOZ_ASSERT(!arena->onDelayedMarkingList());
  MOZ_ASSERT(arena->bufferedCells()->isEmpty());

  Zone* zone = arena->zone();

  AllocKind thingKind = arena->getAllocKind();
  size_t thingSize = arena->getThingSize();

  for (ArenaCellIterUnderGC cell(arena); !cell.done(); cell.next()) {
    RelocateCell(zone, cell, thingKind, thingSize);
    sliceBudget.step();
  }

#ifdef DEBUG
  for (ArenaCellIterUnderGC cell(arena); !cell.done(); cell.next()) {
    TenuredCell* src = cell;
    MOZ_ASSERT(src->isForwarded());
    TenuredCell* dest = Forwarded(src);
    MOZ_ASSERT(src->isMarkedBlack() == dest->isMarkedBlack());
    MOZ_ASSERT(src->isMarkedGray() == dest->isMarkedGray());
  }
#endif
}

/*
 * Relocate all arenas identified by pickArenasToRelocate: for each arena,
 * relocate each cell within it, then add it to a list of relocated arenas.
 */
Arena* ArenaList::relocateArenas(Arena* toRelocate, Arena* relocated,
                                 SliceBudget& sliceBudget,
                                 gcstats::Statistics& stats) {
  while (Arena* arena = toRelocate) {
    toRelocate = arena->next;
    RelocateArena(arena, sliceBudget);
    // Prepend to list of relocated arenas
    arena->next = relocated;
    relocated = arena;
    stats.count(gcstats::COUNT_ARENA_RELOCATED);
  }

  return relocated;
}

// Skip compacting zones unless we can free a certain proportion of their GC
// heap memory.
static const double MIN_ZONE_RECLAIM_PERCENT = 2.0;

static bool ShouldRelocateZone(size_t arenaCount, size_t relocCount,
                               JS::GCReason reason) {
  if (relocCount == 0) {
    return false;
  }

  if (IsOOMReason(reason)) {
    return true;
  }

  double relocFraction = double(relocCount) / double(arenaCount);
  return relocFraction * 100.0 >= MIN_ZONE_RECLAIM_PERCENT;
}

static AllocKinds CompactingAllocKinds() {
  AllocKinds result;
  for (AllocKind kind : AllAllocKinds()) {
    if (IsCompactingKind(kind)) {
      result += kind;
    }
  }
  return result;
}

bool ArenaLists::relocateArenas(Arena*& relocatedListOut, JS::GCReason reason,
                                SliceBudget& sliceBudget,
                                gcstats::Statistics& stats) {
  // This is only called from the main thread while we are doing a GC, so
  // there is no need to lock.
  MOZ_ASSERT(CurrentThreadCanAccessRuntime(runtime()));
  MOZ_ASSERT(runtime()->gc.isHeapCompacting());
  MOZ_ASSERT(!runtime()->gc.isBackgroundSweeping());

  // Relocate all compatible kinds
  AllocKinds allocKindsToRelocate = CompactingAllocKinds();

  // Clear all the free lists.
  clearFreeLists();

  if (ShouldRelocateAllArenas(reason)) {
    zone_->prepareForMovingGC();
    for (auto kind : allocKindsToRelocate) {
      ArenaList& al = arenaList(kind);
      Arena* allArenas = al.release();
      relocatedListOut =
          al.relocateArenas(allArenas, relocatedListOut, sliceBudget, stats);
    }
  } else {
    size_t arenaCount = 0;
    size_t relocCount = 0;
    AllAllocKindArray<std::pair<Arena*, Arena*>> rangeToRelocate;

    for (auto kind : allocKindsToRelocate) {
      rangeToRelocate[kind] =
          arenaList(kind).pickArenasToRelocate(kind, arenaCount, relocCount);
    }

    if (!ShouldRelocateZone(arenaCount, relocCount, reason)) {
      return false;
    }

    zone_->prepareForMovingGC();
    for (auto kind : allocKindsToRelocate) {
      if (rangeToRelocate[kind].first) {
        ArenaList& al = arenaList(kind);
        const auto& range = rangeToRelocate[kind];
        Arena* arenas = al.removeRange(range.first, range.second);
        relocatedListOut =
            al.relocateArenas(arenas, relocatedListOut, sliceBudget, stats);
      }
    }
  }

  return true;
}

bool GCRuntime::relocateArenas(Zone* zone, Arena*& relocatedListOut,
                               SliceBudget& sliceBudget) {
  gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::COMPACT_MOVE);

  MOZ_ASSERT(!zone->isPreservingCode());
  MOZ_ASSERT(canRelocateZone(zone));

  js::CancelOffThreadCompile(rt, JS::Zone::Compact);

  if (!zone->arenas.relocateArenas(relocatedListOut, sliceReason, sliceBudget,
                                   stats())) {
    return false;
  }

#ifdef DEBUG
  // Check that we did as much compaction as we should have. There
  // should always be less than one arena's worth of free cells.
  for (auto kind : CompactingAllocKinds()) {
    ArenaList& al = zone->arenas.arenaList(kind);
    size_t freeCells = 0;
    for (auto arena = al.iter(); !arena.done(); arena.next()) {
      if (arena->isFull()) {
        break;
      }
      freeCells += arena->countFreeCells();
    }
    MOZ_ASSERT(freeCells < Arena::thingsPerArena(kind));
  }
#endif

  return true;
}

MovingTracer::MovingTracer(JSRuntime* rt)
    : GenericTracerImpl(rt, JS::TracerKind::Moving,
                        JS::WeakMapTraceAction::TraceKeysAndValues) {}

template <typename T>
inline void MovingTracer::onEdge(T** thingp, const char* name) {
  T* thing = *thingp;
  if (IsForwarded(thing)) {
    MOZ_ASSERT(thing->runtimeFromAnyThread() == runtime());
    *thingp = Forwarded(thing);
  }
}

void GCRuntime::sweepZoneAfterCompacting(MovingTracer* trc, Zone* zone) {
  MOZ_ASSERT(zone->isGCCompacting());

  zone->traceWeakMaps(trc);
  zone->sweepObjectsWithWeakPointers(trc);

  // Must happen after tracing weak maps above.
  traceWeakFinalizationObserverEdges(trc, zone);

  for (auto* cache : zone->weakCaches()) {
    cache->traceWeak(trc, JS::detail::WeakCacheBase::DontLock);
  }

  if (jit::JitZone* jitZone = zone->jitZone()) {
    jitZone->traceWeak(trc, zone);
  }

  for (CompartmentsInZoneIter c(zone); !c.done(); c.next()) {
    c->traceWeakNativeIterators(trc);

    for (RealmsInCompartmentIter r(c); !r.done(); r.next()) {
      r->traceWeakSavedStacks(trc);
      r->traceWeakGlobalEdge(trc);
      r->traceWeakDebugEnvironmentEdges(trc);
    }
  }
}

template <typename T>
static inline void UpdateCellPointers(MovingTracer* trc, T* cell) {
  // We only update unmoved GC things or the new copy of moved GC things, never
  // the old copy. If this happened it could clear the forwarded flag which
  // could lead to pointers to the old copy not being updated.
  MOZ_ASSERT(!cell->isForwarded());

  cell->fixupAfterMovingGC();
  cell->traceChildren(trc);
}

template <typename T>
static void UpdateArenaPointersTyped(MovingTracer* trc, Arena* arena) {
  for (ArenaCellIterUnderGC cell(arena); !cell.done(); cell.next()) {
    UpdateCellPointers(trc, cell.as<T>());
  }
}

static bool CanUpdateKindInBackground(AllocKind kind) {
  // We try to update as many GC things in parallel as we can, but there are
  // kinds for which this might not be safe:
  //  - we assume JSObjects that are foreground finalized are not safe to
  //    update in parallel
  //  - updating a SharedPropMap touches child maps in
  //    SharedPropMap::fixupAfterMovingGC
  return js::gc::IsBackgroundFinalized(kind) && !IsShapeAllocKind(kind) &&
         kind != AllocKind::BASE_SHAPE;
}

/*
 * Update the internal pointers for all cells in an arena.
 */
static void UpdateArenaPointers(MovingTracer* trc, Arena* arena) {
  AllocKind kind = arena->getAllocKind();

  MOZ_ASSERT_IF(!CanUpdateKindInBackground(kind),
                CurrentThreadCanAccessRuntime(trc->runtime()));

  switch (kind) {
#define EXPAND_CASE(allocKind, traceKind, type, sizedType, bgFinal, nursery, \
                    compact)                                                 \
  case AllocKind::allocKind:                                                 \
    UpdateArenaPointersTyped<type>(trc, arena);                              \
    return;
    FOR_EACH_ALLOCKIND(EXPAND_CASE)
#undef EXPAND_CASE

    default:
      MOZ_CRASH("Invalid alloc kind for UpdateArenaPointers");
  }
}

struct ArenaListSegment {
  Arena* begin;
  Arena* end;
};

/*
 * Update the internal pointers for all arenas in a segment of an arena list.
 *
 * Returns the number of steps to count against the slice budget.
 */
static size_t UpdateArenaListSegmentPointers(GCRuntime* gc,
                                             const ArenaListSegment& arenas) {
  MOZ_ASSERT(arenas.begin);
  MovingTracer trc(gc->rt);
  size_t count = 0;
  Arena* arena = arenas.begin;
  do {
    UpdateArenaPointers(&trc, arena);
    count++;
    arena = arena->next;
  } while (arena != arenas.end);
  return count * 256;
}

class ArenasToUpdate {
  // Maximum number of arenas to update in one block.
#ifdef DEBUG
  static const unsigned MaxArenasToProcess = 16;
#else
  static const unsigned MaxArenasToProcess = 256;
#endif

 public:
  ArenasToUpdate(Zone* zone, const AllocKinds& kinds)
      : kinds(kinds), zone(zone) {
    settle();
  }

  bool done() const {
    MOZ_ASSERT_IF(!segmentBegin, endOfArenaList);
    return !segmentBegin;
  }

  ArenaListSegment get() const {
    MOZ_ASSERT(!done());
    return {segmentBegin, segmentEnd};
  }

  void next();

 private:
  AllocKinds kinds;                   // Selects which thing kinds to update.
  Zone* zone;                         // Zone to process.
  AllocKind kind = AllocKind::FIRST;  // Current alloc kind to process.
  Arena* segmentBegin = nullptr;
  Arena* segmentEnd = nullptr;
  bool endOfArenaList = true;

  static AllocKind nextAllocKind(AllocKind i) {
    return AllocKind(uint8_t(i) + 1);
  }

  void settle();
  void findSegmentEnd();
};

void ArenasToUpdate::settle() {
  // Called when we have set |kind| to a new kind. Sets |arena| to the next
  // arena or null if there are no more arenas to update.

  MOZ_ASSERT(!segmentBegin);
  MOZ_ASSERT(endOfArenaList);

  for (; kind < AllocKind::LIMIT; kind = nextAllocKind(kind)) {
    if (!kinds.contains(kind)) {
      continue;
    }

    Arena* arena = zone->arenas.getFirstArena(kind);
    if (arena) {
      segmentBegin = arena;
      endOfArenaList = false;
      findSegmentEnd();
      break;
    }
  }
}

void ArenasToUpdate::findSegmentEnd() {
  // Take up to MaxArenasToProcess arenas from the list starting at
  // |segmentBegin| and set |segmentEnd| and |endOfArenaList|.
  MOZ_ASSERT(segmentBegin);
  MOZ_ASSERT(!endOfArenaList);

  Arena* arena = segmentBegin;
  Arena* firstArena = zone->arenas.getFirstArena(kind);
  for (size_t i = 0; i < MaxArenasToProcess; i++) {
    arena = arena->next;
    if (arena == firstArena) {
      // We have reached the end of the circular linked list.
      endOfArenaList = true;
      break;
    }
  }
  segmentEnd = arena;
}

void ArenasToUpdate::next() {
  MOZ_ASSERT(!done());

  if (!endOfArenaList) {
    segmentBegin = segmentEnd;
    findSegmentEnd();
    return;
  }

  segmentBegin = nullptr;
  kind = nextAllocKind(kind);
  settle();
}

static AllocKinds ForegroundUpdateKinds(AllocKinds kinds) {
  AllocKinds result;
  for (AllocKind kind : kinds) {
    if (!CanUpdateKindInBackground(kind)) {
      result += kind;
    }
  }
  return result;
}

void GCRuntime::updateCellPointers(Zone* zone, AllocKinds kinds) {
  AllocKinds fgKinds = ForegroundUpdateKinds(kinds);
  AllocKinds bgKinds = kinds - fgKinds;

  ArenasToUpdate fgArenas(zone, fgKinds);
  ArenasToUpdate bgArenas(zone, bgKinds);

  AutoLockHelperThreadState lock;

  AutoRunParallelWork bgTasks(this, UpdateArenaListSegmentPointers,
                              gcstats::PhaseKind::COMPACT_UPDATE_CELLS,
                              GCUse::Unspecified, bgArenas,
                              SliceBudget::unlimited(), lock);

  AutoUnlockHelperThreadState unlock(lock);

  for (; !fgArenas.done(); fgArenas.next()) {
    UpdateArenaListSegmentPointers(this, fgArenas.get());
  }
}

// After cells have been relocated any pointers to a cell's old locations must
// be updated to point to the new location. This happens by iterating through
// all cells in heap and tracing their children (non-recursively) to update
// them.
//
// This is complicated by the fact that updating a GC thing sometimes depends on
// making use of other GC things. After a moving GC these things may not be in a
// valid state since they may contain pointers which have not been updated yet.
//
// The main remaining dependency is:
//
//   - Updating a JSObject makes use of its shape
//
// This means we require at least two phases for update:
//
//  1) a phase including shapes
//  2) a phase including all JS objects
//
// Also, there can be data races calling IsForwarded() on the new location of a
// cell whose first word is being updated in parallel on another thread. This
// easiest way to avoid this is to not store a GC pointer in the first word of a
// cell. Otherwise this can be avoided by updating different kinds of cell in
// different phases.
//
// Since we want to minimize the number of phases, arrange kinds into two
// arbitrary phases.

static constexpr AllocKinds UpdatePhaseOne{AllocKind::SCRIPT,
                                           AllocKind::BASE_SHAPE,
                                           AllocKind::SHAPE,
                                           AllocKind::STRING,
                                           AllocKind::JITCODE,
                                           AllocKind::REGEXP_SHARED,
                                           AllocKind::SCOPE,
                                           AllocKind::GETTER_SETTER,
                                           AllocKind::COMPACT_PROP_MAP,
                                           AllocKind::NORMAL_PROP_MAP,
                                           AllocKind::DICT_PROP_MAP};

static constexpr AllocKinds UpdatePhaseTwo{AllocKind::FUNCTION,
                                           AllocKind::FUNCTION_EXTENDED,
                                           AllocKind::OBJECT0,
                                           AllocKind::OBJECT0_FOREGROUND,
                                           AllocKind::OBJECT0_BACKGROUND,
                                           AllocKind::OBJECT2,
                                           AllocKind::OBJECT2_FOREGROUND,
                                           AllocKind::OBJECT2_BACKGROUND,
                                           AllocKind::ARRAYBUFFER4,
                                           AllocKind::OBJECT4,
                                           AllocKind::OBJECT4_FOREGROUND,
                                           AllocKind::OBJECT4_BACKGROUND,
                                           AllocKind::ARRAYBUFFER6,
                                           AllocKind::OBJECT6,
                                           AllocKind::OBJECT6_FOREGROUND,
                                           AllocKind::OBJECT6_BACKGROUND,
                                           AllocKind::ARRAYBUFFER8,
                                           AllocKind::OBJECT8,
                                           AllocKind::OBJECT8_FOREGROUND,
                                           AllocKind::OBJECT8_BACKGROUND,
                                           AllocKind::ARRAYBUFFER12,
                                           AllocKind::OBJECT12,
                                           AllocKind::OBJECT12_FOREGROUND,
                                           AllocKind::OBJECT12_BACKGROUND,
                                           AllocKind::ARRAYBUFFER16,
                                           AllocKind::OBJECT16,
                                           AllocKind::OBJECT16_FOREGROUND,
                                           AllocKind::OBJECT16_BACKGROUND};

void GCRuntime::updateAllCellPointers(MovingTracer* trc, Zone* zone) {
  updateCellPointers(zone, UpdatePhaseOne);
  updateCellPointers(zone, UpdatePhaseTwo);
}

/*
 * Update pointers to relocated cells in a single zone by doing a traversal of
 * that zone's arenas and calling per-zone sweep hooks.
 *
 * The latter is necessary to update weak references which are not marked as
 * part of the traversal.
 */
void GCRuntime::updateZonePointersToRelocatedCells(Zone* zone) {
  MOZ_ASSERT(!rt->isBeingDestroyed());
  MOZ_ASSERT(zone->isGCCompacting());

  AutoTouchingGrayThings tgt;

  gcstats::AutoPhase ap(stats(), gcstats::PhaseKind::COMPACT_UPDATE);
  MovingTracer trc(rt);

  zone->fixupAfterMovingGC();
  zone->fixupScriptMapsAfterMovingGC(&trc);

  // Fixup compartment global pointers as these get accessed during marking.
  for (CompartmentsInZoneIter comp(zone); !comp.done(); comp.next()) {
    comp->fixupAfterMovingGC(&trc);
  }

  zone->externalStringCache().purge();
  zone->functionToStringCache().purge();
  zone->shapeZone().purgeShapeCaches(rt->gcContext());
  rt->caches().stringToAtomCache.purge();

  // Iterate through all cells that can contain relocatable pointers to update
  // them. Since updating each cell is independent we try to parallelize this
  // as much as possible.
  updateAllCellPointers(&trc, zone);

  // Sweep everything to fix up weak pointers.
  sweepZoneAfterCompacting(&trc, zone);

  // Call callbacks to get the rest of the system to fixup other untraced
  // pointers.
  for (CompartmentsInZoneIter comp(zone); !comp.done(); comp.next()) {
    callWeakPointerCompartmentCallbacks(&trc, comp);
  }
}

/*
 * Update runtime-wide pointers to relocated cells.
 */
void GCRuntime::updateRuntimePointersToRelocatedCells(AutoGCSession& session) {
  MOZ_ASSERT(!rt->isBeingDestroyed());

  gcstats::AutoPhase ap1(stats(), gcstats::PhaseKind::COMPACT_UPDATE);
  MovingTracer trc(rt);

  Zone::fixupAllCrossCompartmentWrappersAfterMovingGC(&trc);

  rt->geckoProfiler().fixupStringsMapAfterMovingGC();

  // Mark roots to update them.

  traceRuntimeForMajorGC(&trc, session);

  jit::UpdateJitActivationsForCompactingGC(rt);

  {
    gcstats::AutoPhase ap2(stats(), gcstats::PhaseKind::MARK_ROOTS);
    DebugAPI::traceAllForMovingGC(&trc);
    DebugAPI::traceCrossCompartmentEdges(&trc);

    // Mark all gray roots.
    traceEmbeddingGrayRoots(&trc);
    Compartment::traceIncomingCrossCompartmentEdgesForZoneGC(
        &trc, Compartment::GrayEdges);
  }

  // Sweep everything to fix up weak pointers.
  jit::JitRuntime::TraceWeakJitcodeGlobalTable(rt, &trc);
  for (JS::detail::WeakCacheBase* cache : weakCaches()) {
    cache->traceWeak(&trc, JS::detail::WeakCacheBase::DontLock);
  }

  if (rt->hasJitRuntime() && rt->jitRuntime()->hasInterpreterEntryMap()) {
    rt->jitRuntime()->getInterpreterEntryMap()->updateScriptsAfterMovingGC();
  }

  // Type inference may put more blocks here to free.
  {
    AutoLockHelperThreadState lock;
    lifoBlocksToFree.ref().freeAll();
  }

  // Call callbacks to get the rest of the system to fixup other untraced
  // pointers.
  callWeakPointerZonesCallbacks(&trc);
}

void GCRuntime::clearRelocatedArenas(Arena* arenaList) {
  AutoLockGC lock(this);

  // Clear the relocated arenas, now containing only forwarding pointers
  while (arenaList) {
    Arena* arena = arenaList;
    arenaList = arenaList->next;

    // Clear the mark bits
    arena->unmarkAll();

    // Mark arena as empty
    arena->setAsFullyUnused();

#ifdef DEBUG
    // The cell contents have been partially marked no access in RelocateCell,
    // so we need to mark the region as undefined again so we can poison it.
    SetMemCheckKind(reinterpret_cast<void*>(arena->thingsStart()),
                    arena->getThingsSpan(), MemCheckKind::MakeUndefined);
#endif

    AlwaysPoison(reinterpret_cast<void*>(arena->thingsStart()),
                 JS_MOVED_TENURED_PATTERN, arena->getThingsSpan(),
                 MemCheckKind::MakeNoAccess);

    // Don't count emptied arenas as being freed by the current GC:
    //  - if we purposely moved everything to new arenas, as that will already
    //    have allocated a similar number of arenas. (This only happens for
    //    collections triggered by GC zeal.)
    //  - if they were allocated since the start of the GC.
    bool allArenasRelocated = ShouldRelocateAllArenas(sliceReason);
    bool updateRetainedSize = !allArenasRelocated && !arena->isNewlyCreated();
    Zone* zone = arena->zone();
    zone->gcHeapSize.removeBytes(ArenaSize, updateRetainedSize, heapSize);

    // There is no atom marking bitmap index to free.
    MOZ_ASSERT(!zone->isAtomsZone());

    // Release the arena but don't return it to the chunk yet.
    arena->release();
  }
}

#ifdef DEBUG

// In debug mode we don't always release relocated arenas straight away.
// Sometimes protect them instead and hold onto them until the next GC sweep
// phase to catch any pointers to them that didn't get forwarded.

static inline bool CanProtectArenas() {
  // On some systems the page size is larger than the size of an arena so we
  // can't change the mapping permissions per arena.
  return SystemPageSize() <= ArenaSize;
}

static inline bool ShouldProtectRelocatedArenas(JS::GCReason reason) {
  // For zeal mode collections we don't release the relocated arenas
  // immediately. Instead we protect them and keep them around until the next
  // collection so we can catch any stray accesses to them.
  return reason == JS::GCReason::DEBUG_GC && CanProtectArenas();
}

void GCRuntime::protectOrReleaseRelocatedArenas(Arena* arenaList) {
  if (ShouldProtectRelocatedArenas(sliceReason)) {
    protectAndHoldArenas(arenaList);
    return;
  }

  releaseRelocatedArenas(arenaList);
}

void GCRuntime::protectAndHoldArenas(Arena* arenaList) {
  for (Arena* arena = arenaList; arena;) {
    MOZ_ASSERT(!arena->allocated());
    Arena* next = arena->next;
    if (!next) {
      // Prepend to hold list before we protect the memory.
      AutoLockGC lock(this);
      arena->next = relocatedArenasToRelease;
      relocatedArenasToRelease = arenaList;
    }
    ProtectPages(arena, ArenaSize);
    arena = next;
  }
}

void GCRuntime::unprotectHeldRelocatedArenas(const AutoLockGC& lock) {
  for (Arena* arena = relocatedArenasToRelease; arena; arena = arena->next) {
    UnprotectPages(arena, ArenaSize);
    MOZ_ASSERT(!arena->allocated());
  }
}

void GCRuntime::releaseHeldRelocatedArenas() {
  AutoLockGC lock(this);
  unprotectHeldRelocatedArenas(lock);
  Arena* arenas = relocatedArenasToRelease;
  relocatedArenasToRelease = nullptr;
  releaseRelocatedArenasWithoutUnlocking(arenas, lock);
}

void GCRuntime::releaseHeldRelocatedArenasWithoutUnlocking(
    const AutoLockGC& lock) {
  unprotectHeldRelocatedArenas(lock);
  releaseRelocatedArenasWithoutUnlocking(relocatedArenasToRelease, lock);
  relocatedArenasToRelease = nullptr;
}

#endif

void GCRuntime::releaseRelocatedArenas(Arena* arenaList) {
  AutoLockGC lock(this);
  releaseRelocatedArenasWithoutUnlocking(arenaList, lock);
}

void GCRuntime::releaseRelocatedArenasWithoutUnlocking(Arena* arenaList,
                                                       const AutoLockGC& lock) {
  // Release relocated arenas previously cleared with clearRelocatedArenas().
  while (arenaList) {
    Arena* arena = arenaList;
    arenaList = arenaList->next;

    // We already updated the memory accounting so just call
    // Chunk::releaseArena.
    arena->chunk()->releaseArena(this, arena, lock);
  }
}