Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1016 insertions, 0 deletions

diff --git a/js/src/gc/Tenuring.cpp b/js/src/gc/Tenuring.cpp
new file mode 100644
index 0000000000..457aa4876c
--- /dev/null
+++ b/js/src/gc/Tenuring.cpp
@@ -0,0 +1,1016 @@
+/* -*- 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 nursery eviction (tenuring).
+ */
+
+#include "gc/Tenuring.h"
+
+#include "mozilla/PodOperations.h"
+
+#include "gc/Cell.h"
+#include "gc/GCInternals.h"
+#include "gc/GCProbes.h"
+#include "gc/Pretenuring.h"
+#include "gc/Zone.h"
+#include "jit/JitCode.h"
+#include "proxy/Proxy.h"
+#include "vm/BigIntType.h"
+#include "vm/JSScript.h"
+#include "vm/NativeObject.h"
+#include "vm/Runtime.h"
+#include "vm/TypedArrayObject.h"
+
+#include "gc/Heap-inl.h"
+#include "gc/Marking-inl.h"
+#include "gc/ObjectKind-inl.h"
+#include "gc/StoreBuffer-inl.h"
+#include "gc/TraceMethods-inl.h"
+#include "vm/JSObject-inl.h"
+#include "vm/PlainObject-inl.h"
+#ifdef ENABLE_RECORD_TUPLE
+#  include "vm/TupleType.h"
+#endif
+
+using namespace js;
+using namespace js::gc;
+
+using mozilla::PodCopy;
+
+constexpr size_t MAX_DEDUPLICATABLE_STRING_LENGTH = 500;
+
+TenuringTracer::TenuringTracer(JSRuntime* rt, Nursery* nursery)
+    : JSTracer(rt, JS::TracerKind::Tenuring,
+               JS::WeakMapTraceAction::TraceKeysAndValues),
+      nursery_(*nursery) {
+  stringDeDupSet.emplace();
+}
+
+size_t TenuringTracer::getTenuredSize() const {
+  return tenuredSize + tenuredCells * sizeof(NurseryCellHeader);
+}
+
+size_t TenuringTracer::getTenuredCells() const { return tenuredCells; }
+
+static inline void UpdateAllocSiteOnTenure(Cell* cell) {
+  AllocSite* site = NurseryCellHeader::from(cell)->allocSite();
+  site->incTenuredCount();
+}
+
+void TenuringTracer::onObjectEdge(JSObject** objp, const char* name) {
+  JSObject* obj = *objp;
+  if (!IsInsideNursery(obj)) {
+    return;
+  }
+
+  if (obj->isForwarded()) {
+    const gc::RelocationOverlay* overlay = gc::RelocationOverlay::fromCell(obj);
+    *objp = static_cast<JSObject*>(overlay->forwardingAddress());
+    return;
+  }
+
+  UpdateAllocSiteOnTenure(obj);
+
+  // Take a fast path for tenuring a plain object which is by far the most
+  // common case.
+  if (obj->is<PlainObject>()) {
+    *objp = movePlainObjectToTenured(&obj->as<PlainObject>());
+    return;
+  }
+
+  *objp = moveToTenuredSlow(obj);
+}
+
+void TenuringTracer::onStringEdge(JSString** strp, const char* name) {
+  JSString* str = *strp;
+  if (!IsInsideNursery(str)) {
+    return;
+  }
+
+  if (str->isForwarded()) {
+    const gc::RelocationOverlay* overlay = gc::RelocationOverlay::fromCell(str);
+    *strp = static_cast<JSString*>(overlay->forwardingAddress());
+    return;
+  }
+
+  UpdateAllocSiteOnTenure(str);
+
+  *strp = moveToTenured(str);
+}
+
+void TenuringTracer::onBigIntEdge(JS::BigInt** bip, const char* name) {
+  JS::BigInt* bi = *bip;
+  if (!IsInsideNursery(bi)) {
+    return;
+  }
+
+  if (bi->isForwarded()) {
+    const gc::RelocationOverlay* overlay = gc::RelocationOverlay::fromCell(bi);
+    *bip = static_cast<JS::BigInt*>(overlay->forwardingAddress());
+    return;
+  }
+
+  UpdateAllocSiteOnTenure(bi);
+
+  *bip = moveToTenured(bi);
+}
+
+void TenuringTracer::onSymbolEdge(JS::Symbol** symp, const char* name) {}
+void TenuringTracer::onScriptEdge(BaseScript** scriptp, const char* name) {}
+void TenuringTracer::onShapeEdge(Shape** shapep, const char* name) {}
+void TenuringTracer::onRegExpSharedEdge(RegExpShared** sharedp,
+                                        const char* name) {}
+void TenuringTracer::onBaseShapeEdge(BaseShape** basep, const char* name) {}
+void TenuringTracer::onGetterSetterEdge(GetterSetter** gsp, const char* name) {}
+void TenuringTracer::onPropMapEdge(PropMap** mapp, const char* name) {}
+void TenuringTracer::onJitCodeEdge(jit::JitCode** codep, const char* name) {}
+void TenuringTracer::onScopeEdge(Scope** scopep, const char* name) {}
+
+void TenuringTracer::traverse(JS::Value* thingp) {
+  MOZ_ASSERT(!nursery().isInside(thingp));
+
+  Value value = *thingp;
+  CheckTracedThing(this, value);
+
+  // We only care about a few kinds of GC thing here and this generates much
+  // tighter code than using MapGCThingTyped.
+  Value post;
+  if (value.isObject()) {
+    JSObject* obj = &value.toObject();
+    onObjectEdge(&obj, "value");
+    post = JS::ObjectValue(*obj);
+  }
+#ifdef ENABLE_RECORD_TUPLE
+  else if (value.isExtendedPrimitive()) {
+    JSObject* obj = &value.toExtendedPrimitive();
+    onObjectEdge(&obj, "value");
+    post = JS::ExtendedPrimitiveValue(*obj);
+  }
+#endif
+  else if (value.isString()) {
+    JSString* str = value.toString();
+    onStringEdge(&str, "value");
+    post = JS::StringValue(str);
+  } else if (value.isBigInt()) {
+    JS::BigInt* bi = value.toBigInt();
+    onBigIntEdge(&bi, "value");
+    post = JS::BigIntValue(bi);
+  } else {
+    MOZ_ASSERT_IF(value.isGCThing(), !IsInsideNursery(value.toGCThing()));
+    return;
+  }
+
+  if (post != value) {
+    *thingp = post;
+  }
+}
+
+template <typename T>
+void js::gc::StoreBuffer::MonoTypeBuffer<T>::trace(TenuringTracer& mover) {
+  mozilla::ReentrancyGuard g(*owner_);
+  MOZ_ASSERT(owner_->isEnabled());
+  if (last_) {
+    last_.trace(mover);
+  }
+  for (typename StoreSet::Range r = stores_.all(); !r.empty(); r.popFront()) {
+    r.front().trace(mover);
+  }
+}
+
+namespace js {
+namespace gc {
+template void StoreBuffer::MonoTypeBuffer<StoreBuffer::ValueEdge>::trace(
+    TenuringTracer&);
+template void StoreBuffer::MonoTypeBuffer<StoreBuffer::SlotsEdge>::trace(
+    TenuringTracer&);
+template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::StringPtrEdge>;
+template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::BigIntPtrEdge>;
+template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::ObjectPtrEdge>;
+}  // namespace gc
+}  // namespace js
+
+void js::gc::StoreBuffer::SlotsEdge::trace(TenuringTracer& mover) const {
+  NativeObject* obj = object();
+  MOZ_ASSERT(IsCellPointerValid(obj));
+
+  // Beware JSObject::swap exchanging a native object for a non-native one.
+  if (!obj->is<NativeObject>()) {
+    return;
+  }
+
+  MOZ_ASSERT(!IsInsideNursery(obj), "obj shouldn't live in nursery.");
+
+  if (kind() == ElementKind) {
+    uint32_t initLen = obj->getDenseInitializedLength();
+    uint32_t numShifted = obj->getElementsHeader()->numShiftedElements();
+    uint32_t clampedStart = start_;
+    clampedStart = numShifted < clampedStart ? clampedStart - numShifted : 0;
+    clampedStart = std::min(clampedStart, initLen);
+    uint32_t clampedEnd = start_ + count_;
+    clampedEnd = numShifted < clampedEnd ? clampedEnd - numShifted : 0;
+    clampedEnd = std::min(clampedEnd, initLen);
+    MOZ_ASSERT(clampedStart <= clampedEnd);
+    mover.traceSlots(
+        static_cast<HeapSlot*>(obj->getDenseElements() + clampedStart)
+            ->unbarrieredAddress(),
+        clampedEnd - clampedStart);
+  } else {
+    uint32_t start = std::min(start_, obj->slotSpan());
+    uint32_t end = std::min(start_ + count_, obj->slotSpan());
+    MOZ_ASSERT(start <= end);
+    mover.traceObjectSlots(obj, start, end);
+  }
+}
+
+static inline void TraceWholeCell(TenuringTracer& mover, JSObject* object) {
+  MOZ_ASSERT_IF(object->storeBuffer(),
+                !object->storeBuffer()->markingNondeduplicatable);
+  mover.traceObject(object);
+}
+
+// Non-deduplicatable marking is necessary because of the following 2 reasons:
+//
+// 1. Tenured string chars cannot be updated:
+//
+//    If any of the tenured string's bases were deduplicated during tenuring,
+//    the tenured string's chars pointer would need to be adjusted. This would
+//    then require updating any other tenured strings that are dependent on the
+//    first tenured string, and we have no way to find them without scanning
+//    the entire tenured heap.
+//
+// 2. Tenured string cannot store its nursery base or base's chars:
+//
+//    Tenured strings have no place to stash a pointer to their nursery base or
+//    its chars. You need to be able to traverse any dependent string's chain
+//    of bases up to a nursery "root base" that points to the malloced chars
+//    that the dependent strings started out pointing to, so that you can
+//    calculate the offset of any dependent string and update the ptr+offset if
+//    the root base gets deduplicated to a different allocation. Tenured
+//    strings in this base chain will stop you from reaching the nursery
+//    version of the root base; you can only get to the tenured version, and it
+//    has no place to store the original chars pointer.
+static inline void PreventDeduplicationOfReachableStrings(JSString* str) {
+  MOZ_ASSERT(str->isTenured());
+  MOZ_ASSERT(!str->isForwarded());
+
+  JSLinearString* baseOrRelocOverlay = str->nurseryBaseOrRelocOverlay();
+
+  // Walk along the chain of dependent strings' base string pointers
+  // to mark them all non-deduplicatable.
+  while (true) {
+    // baseOrRelocOverlay can be one of the three cases:
+    // 1. forwarded nursery string:
+    //    The forwarded string still retains the flag that can tell whether
+    //    this string is a dependent string with a base. Its
+    //    StringRelocationOverlay holds a saved pointer to its base in the
+    //    nursery.
+    // 2. not yet forwarded nursery string:
+    //    Retrieve the base field directly from the string.
+    // 3. tenured string:
+    //    The nursery base chain ends here, so stop traversing.
+    if (baseOrRelocOverlay->isForwarded()) {
+      JSLinearString* tenuredBase = Forwarded(baseOrRelocOverlay);
+      if (!tenuredBase->hasBase()) {
+        break;
+      }
+      baseOrRelocOverlay = StringRelocationOverlay::fromCell(baseOrRelocOverlay)
+                               ->savedNurseryBaseOrRelocOverlay();
+    } else {
+      JSLinearString* base = baseOrRelocOverlay;
+      if (base->isTenured()) {
+        break;
+      }
+      if (base->isDeduplicatable()) {
+        base->setNonDeduplicatable();
+      }
+      if (!base->hasBase()) {
+        break;
+      }
+      baseOrRelocOverlay = base->nurseryBaseOrRelocOverlay();
+    }
+  }
+}
+
+static inline void TraceWholeCell(TenuringTracer& mover, JSString* str) {
+  MOZ_ASSERT_IF(str->storeBuffer(),
+                str->storeBuffer()->markingNondeduplicatable);
+
+  // Mark all strings reachable from the tenured string `str` as
+  // non-deduplicatable. These strings are the bases of the tenured dependent
+  // string.
+  if (str->hasBase()) {
+    PreventDeduplicationOfReachableStrings(str);
+  }
+
+  str->traceChildren(&mover);
+}
+
+static inline void TraceWholeCell(TenuringTracer& mover, BaseScript* script) {
+  script->traceChildren(&mover);
+}
+
+static inline void TraceWholeCell(TenuringTracer& mover,
+                                  jit::JitCode* jitcode) {
+  jitcode->traceChildren(&mover);
+}
+
+template <typename T>
+static void TraceBufferedCells(TenuringTracer& mover, Arena* arena,
+                               ArenaCellSet* cells) {
+  for (size_t i = 0; i < MaxArenaCellIndex; i += cells->BitsPerWord) {
+    ArenaCellSet::WordT bitset = cells->getWord(i / cells->BitsPerWord);
+    while (bitset) {
+      size_t bit = i + js::detail::CountTrailingZeroes(bitset);
+      auto cell =
+          reinterpret_cast<T*>(uintptr_t(arena) + ArenaCellIndexBytes * bit);
+      TraceWholeCell(mover, cell);
+      bitset &= bitset - 1;  // Clear the low bit.
+    }
+  }
+}
+
+void ArenaCellSet::trace(TenuringTracer& mover) {
+  for (ArenaCellSet* cells = this; cells; cells = cells->next) {
+    cells->check();
+
+    Arena* arena = cells->arena;
+    arena->bufferedCells() = &ArenaCellSet::Empty;
+
+    JS::TraceKind kind = MapAllocToTraceKind(arena->getAllocKind());
+    switch (kind) {
+      case JS::TraceKind::Object:
+        TraceBufferedCells<JSObject>(mover, arena, cells);
+        break;
+      case JS::TraceKind::String:
+        TraceBufferedCells<JSString>(mover, arena, cells);
+        break;
+      case JS::TraceKind::Script:
+        TraceBufferedCells<BaseScript>(mover, arena, cells);
+        break;
+      case JS::TraceKind::JitCode:
+        TraceBufferedCells<jit::JitCode>(mover, arena, cells);
+        break;
+      default:
+        MOZ_CRASH("Unexpected trace kind");
+    }
+  }
+}
+
+void js::gc::StoreBuffer::WholeCellBuffer::trace(TenuringTracer& mover) {
+  MOZ_ASSERT(owner_->isEnabled());
+
+#ifdef DEBUG
+  // Verify that all string whole cells are traced first before any other
+  // strings are visited for any reason.
+  MOZ_ASSERT(!owner_->markingNondeduplicatable);
+  owner_->markingNondeduplicatable = true;
+#endif
+  // Trace all of the strings to mark the non-deduplicatable bits, then trace
+  // all other whole cells.
+  if (stringHead_) {
+    stringHead_->trace(mover);
+  }
+#ifdef DEBUG
+  owner_->markingNondeduplicatable = false;
+#endif
+  if (nonStringHead_) {
+    nonStringHead_->trace(mover);
+  }
+
+  stringHead_ = nonStringHead_ = nullptr;
+}
+
+template <typename T>
+void js::gc::StoreBuffer::CellPtrEdge<T>::trace(TenuringTracer& mover) const {
+  static_assert(std::is_base_of_v<Cell, T>, "T must be a Cell type");
+  static_assert(!GCTypeIsTenured<T>(), "T must not be a tenured Cell type");
+
+  T* thing = *edge;
+  if (!thing) {
+    return;
+  }
+
+  MOZ_ASSERT(IsCellPointerValid(thing));
+  MOZ_ASSERT(thing->getTraceKind() == JS::MapTypeToTraceKind<T>::kind);
+
+  if (std::is_same_v<JSString, T>) {
+    // Nursery string deduplication requires all tenured string -> nursery
+    // string edges to be registered with the whole cell buffer in order to
+    // correctly set the non-deduplicatable bit.
+    MOZ_ASSERT(!mover.runtime()->gc.isPointerWithinTenuredCell(
+        edge, JS::TraceKind::String));
+  }
+
+  DispatchToOnEdge(&mover, edge, "CellPtrEdge");
+}
+
+void js::gc::StoreBuffer::ValueEdge::trace(TenuringTracer& mover) const {
+  if (deref()) {
+    mover.traverse(edge);
+  }
+}
+
+// Visit all object children of the object and trace them.
+void js::gc::TenuringTracer::traceObject(JSObject* obj) {
+  const JSClass* clasp = obj->getClass();
+  MOZ_ASSERT(clasp);
+
+  if (clasp->hasTrace()) {
+    clasp->doTrace(this, obj);
+  }
+
+  if (!obj->is<NativeObject>()) {
+    return;
+  }
+
+  NativeObject* nobj = &obj->as<NativeObject>();
+  if (!nobj->hasEmptyElements()) {
+    HeapSlotArray elements = nobj->getDenseElements();
+    Value* elems = elements.begin()->unbarrieredAddress();
+    traceSlots(elems, elems + nobj->getDenseInitializedLength());
+  }
+
+  traceObjectSlots(nobj, 0, nobj->slotSpan());
+}
+
+void js::gc::TenuringTracer::traceObjectSlots(NativeObject* nobj,
+                                              uint32_t start, uint32_t end) {
+  auto traceRange = [this](HeapSlot* slotStart, HeapSlot* slotEnd) {
+    traceSlots(slotStart->unbarrieredAddress(), slotEnd->unbarrieredAddress());
+  };
+  nobj->forEachSlotRange(start, end, traceRange);
+}
+
+void js::gc::TenuringTracer::traceSlots(Value* vp, Value* end) {
+  for (; vp != end; ++vp) {
+    traverse(vp);
+  }
+}
+
+inline void js::gc::TenuringTracer::traceSlots(JS::Value* vp, uint32_t nslots) {
+  traceSlots(vp, vp + nslots);
+}
+
+void js::gc::TenuringTracer::traceString(JSString* str) {
+  str->traceChildren(this);
+}
+
+void js::gc::TenuringTracer::traceBigInt(JS::BigInt* bi) {
+  bi->traceChildren(this);
+}
+
+#ifdef DEBUG
+static inline uintptr_t OffsetFromChunkStart(void* p) {
+  return uintptr_t(p) & gc::ChunkMask;
+}
+static inline ptrdiff_t OffsetToChunkEnd(void* p) {
+  return ChunkSize - (uintptr_t(p) & gc::ChunkMask);
+}
+#endif
+
+/* Insert the given relocation entry into the list of things to visit. */
+inline void js::gc::TenuringTracer::insertIntoObjectFixupList(
+    RelocationOverlay* entry) {
+  entry->setNext(objHead);
+  objHead = entry;
+}
+
+template <typename T>
+inline T* js::gc::TenuringTracer::allocTenured(Zone* zone, AllocKind kind) {
+  return static_cast<T*>(static_cast<Cell*>(AllocateCellInGC(zone, kind)));
+}
+
+JSString* js::gc::TenuringTracer::allocTenuredString(JSString* src, Zone* zone,
+                                                     AllocKind dstKind) {
+  JSString* dst = allocTenured<JSString>(zone, dstKind);
+  tenuredSize += moveStringToTenured(dst, src, dstKind);
+  tenuredCells++;
+
+  return dst;
+}
+
+JSObject* js::gc::TenuringTracer::moveToTenuredSlow(JSObject* src) {
+  MOZ_ASSERT(IsInsideNursery(src));
+  MOZ_ASSERT(!src->is<PlainObject>());
+
+  AllocKind dstKind = src->allocKindForTenure(nursery());
+  auto dst = allocTenured<JSObject>(src->nurseryZone(), dstKind);
+
+  size_t srcSize = Arena::thingSize(dstKind);
+
+  // Arrays and Tuples do not necessarily have the same AllocKind between src
+  // and dst. We deal with this by copying elements manually, possibly
+  // re-inlining them if there is adequate room inline in dst.
+  //
+  // For Arrays and Tuples we're reducing tenuredSize to the smaller srcSize
+  // because moveElementsToTenured() accounts for all Array or Tuple elements,
+  // even if they are inlined.
+  if (src->is<TypedArrayObject>()) {
+    TypedArrayObject* tarray = &src->as<TypedArrayObject>();
+    // Typed arrays with inline data do not necessarily have the same
+    // AllocKind between src and dst. The nursery does not allocate an
+    // inline data buffer that has the same size as the slow path will do.
+    // In the slow path, the Typed Array Object stores the inline data
+    // in the allocated space that fits the AllocKind. In the fast path,
+    // the nursery will allocate another buffer that is directly behind the
+    // minimal JSObject. That buffer size plus the JSObject size is not
+    // necessarily as large as the slow path's AllocKind size.
+    if (tarray->hasInlineElements()) {
+      AllocKind srcKind = GetGCObjectKind(TypedArrayObject::FIXED_DATA_START);
+      size_t headerSize = Arena::thingSize(srcKind);
+      srcSize = headerSize + tarray->byteLength();
+    }
+  } else if (src->canHaveFixedElements()) {
+    srcSize = sizeof(NativeObject);
+  }
+
+  tenuredSize += srcSize;
+  tenuredCells++;
+
+  // Copy the Cell contents.
+  MOZ_ASSERT(OffsetFromChunkStart(src) >= sizeof(ChunkBase));
+  MOZ_ASSERT(OffsetToChunkEnd(src) >= ptrdiff_t(srcSize));
+  js_memcpy(dst, src, srcSize);
+
+  // Move the slots and elements, if we need to.
+  if (src->is<NativeObject>()) {
+    NativeObject* ndst = &dst->as<NativeObject>();
+    NativeObject* nsrc = &src->as<NativeObject>();
+    tenuredSize += moveSlotsToTenured(ndst, nsrc);
+    tenuredSize += moveElementsToTenured(ndst, nsrc, dstKind);
+  }
+
+  JSObjectMovedOp op = dst->getClass()->extObjectMovedOp();
+  MOZ_ASSERT_IF(src->is<ProxyObject>(), op == proxy_ObjectMoved);
+  if (op) {
+    // Tell the hazard analysis that the object moved hook can't GC.
+    JS::AutoSuppressGCAnalysis nogc;
+    tenuredSize += op(dst, src);
+  } else {
+    MOZ_ASSERT_IF(src->getClass()->hasFinalize(),
+                  CanNurseryAllocateFinalizedClass(src->getClass()));
+  }
+
+  RelocationOverlay* overlay = RelocationOverlay::forwardCell(src, dst);
+  insertIntoObjectFixupList(overlay);
+
+  gcprobes::PromoteToTenured(src, dst);
+  return dst;
+}
+
+inline JSObject* js::gc::TenuringTracer::movePlainObjectToTenured(
+    PlainObject* src) {
+  // Fast path version of moveToTenuredSlow() for specialized for PlainObject.
+
+  MOZ_ASSERT(IsInsideNursery(src));
+
+  AllocKind dstKind = src->allocKindForTenure();
+  auto dst = allocTenured<PlainObject>(src->nurseryZone(), dstKind);
+
+  size_t srcSize = Arena::thingSize(dstKind);
+  tenuredSize += srcSize;
+  tenuredCells++;
+
+  // Copy the Cell contents.
+  MOZ_ASSERT(OffsetFromChunkStart(src) >= sizeof(ChunkBase));
+  MOZ_ASSERT(OffsetToChunkEnd(src) >= ptrdiff_t(srcSize));
+  js_memcpy(dst, src, srcSize);
+
+  // Move the slots and elements.
+  tenuredSize += moveSlotsToTenured(dst, src);
+  tenuredSize += moveElementsToTenured(dst, src, dstKind);
+
+  MOZ_ASSERT(!dst->getClass()->extObjectMovedOp());
+
+  RelocationOverlay* overlay = RelocationOverlay::forwardCell(src, dst);
+  insertIntoObjectFixupList(overlay);
+
+  gcprobes::PromoteToTenured(src, dst);
+  return dst;
+}
+
+size_t js::gc::TenuringTracer::moveSlotsToTenured(NativeObject* dst,
+                                                  NativeObject* src) {
+  /* Fixed slots have already been copied over. */
+  if (!src->hasDynamicSlots()) {
+    return 0;
+  }
+
+  Zone* zone = src->nurseryZone();
+  size_t count = src->numDynamicSlots();
+
+  uint64_t uid = src->maybeUniqueId();
+
+  size_t allocSize = ObjectSlots::allocSize(count);
+
+  ObjectSlots* srcHeader = src->getSlotsHeader();
+  if (!nursery().isInside(srcHeader)) {
+    AddCellMemory(dst, allocSize, MemoryUse::ObjectSlots);
+    nursery().removeMallocedBufferDuringMinorGC(srcHeader);
+    return 0;
+  }
+
+  {
+    AutoEnterOOMUnsafeRegion oomUnsafe;
+    HeapSlot* allocation =
+        zone->pod_malloc<HeapSlot>(ObjectSlots::allocCount(count));
+    if (!allocation) {
+      oomUnsafe.crash(allocSize, "Failed to allocate slots while tenuring.");
+    }
+
+    ObjectSlots* slotsHeader = new (allocation)
+        ObjectSlots(count, srcHeader->dictionarySlotSpan(), uid);
+    dst->slots_ = slotsHeader->slots();
+  }
+
+  AddCellMemory(dst, allocSize, MemoryUse::ObjectSlots);
+
+  PodCopy(dst->slots_, src->slots_, count);
+  if (count) {
+    nursery().setSlotsForwardingPointer(src->slots_, dst->slots_, count);
+  }
+
+  return allocSize;
+}
+
+size_t js::gc::TenuringTracer::moveElementsToTenured(NativeObject* dst,
+                                                     NativeObject* src,
+                                                     AllocKind dstKind) {
+  if (src->hasEmptyElements()) {
+    return 0;
+  }
+
+  Zone* zone = src->nurseryZone();
+
+  ObjectElements* srcHeader = src->getElementsHeader();
+  size_t nslots = srcHeader->numAllocatedElements();
+  size_t allocSize = nslots * sizeof(HeapSlot);
+
+  void* srcAllocatedHeader = src->getUnshiftedElementsHeader();
+
+  /* TODO Bug 874151: Prefer to put element data inline if we have space. */
+  if (!nursery().isInside(srcAllocatedHeader)) {
+    MOZ_ASSERT(src->elements_ == dst->elements_);
+    nursery().removeMallocedBufferDuringMinorGC(srcAllocatedHeader);
+
+    AddCellMemory(dst, allocSize, MemoryUse::ObjectElements);
+
+    return 0;
+  }
+
+  // Shifted elements are copied too.
+  uint32_t numShifted = srcHeader->numShiftedElements();
+
+  /* Unlike other objects, Arrays and Tuples can have fixed elements. */
+  if (src->canHaveFixedElements() && nslots <= GetGCKindSlots(dstKind)) {
+    dst->as<NativeObject>().setFixedElements();
+    js_memcpy(dst->getElementsHeader(), srcAllocatedHeader, allocSize);
+    dst->elements_ += numShifted;
+    dst->getElementsHeader()->flags |= ObjectElements::FIXED;
+    nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
+                                           srcHeader->capacity);
+    return allocSize;
+  }
+
+  MOZ_ASSERT(nslots >= 2);
+
+  ObjectElements* dstHeader;
+  {
+    AutoEnterOOMUnsafeRegion oomUnsafe;
+    dstHeader =
+        reinterpret_cast<ObjectElements*>(zone->pod_malloc<HeapSlot>(nslots));
+    if (!dstHeader) {
+      oomUnsafe.crash(allocSize, "Failed to allocate elements while tenuring.");
+    }
+  }
+
+  AddCellMemory(dst, allocSize, MemoryUse::ObjectElements);
+
+  js_memcpy(dstHeader, srcAllocatedHeader, allocSize);
+  dst->elements_ = dstHeader->elements() + numShifted;
+  dst->getElementsHeader()->flags &= ~ObjectElements::FIXED;
+  nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
+                                         srcHeader->capacity);
+  return allocSize;
+}
+
+inline void js::gc::TenuringTracer::insertIntoStringFixupList(
+    StringRelocationOverlay* entry) {
+  entry->setNext(stringHead);
+  stringHead = entry;
+}
+
+JSString* js::gc::TenuringTracer::moveToTenured(JSString* src) {
+  MOZ_ASSERT(IsInsideNursery(src));
+  MOZ_ASSERT(!src->isExternal());
+
+  AllocKind dstKind = src->getAllocKind();
+  Zone* zone = src->nurseryZone();
+
+  // If this string is in the StringToAtomCache, try to deduplicate it by using
+  // the atom. Don't do this for dependent strings because they're more
+  // complicated. See StringRelocationOverlay and DeduplicationStringHasher
+  // comments.
+  if (src->isLinear() && src->inStringToAtomCache() &&
+      src->isDeduplicatable() && !src->hasBase()) {
+    JSLinearString* linear = &src->asLinear();
+    JSAtom* atom = runtime()->caches().stringToAtomCache.lookupInMap(linear);
+    MOZ_ASSERT(atom, "Why was the cache purged before minor GC?");
+
+    // Only deduplicate if both strings have the same encoding, to not confuse
+    // dependent strings.
+    if (src->hasTwoByteChars() == atom->hasTwoByteChars()) {
+      // The StringToAtomCache isn't used for inline strings (due to the minimum
+      // length) so canOwnDependentChars must be true for both src and atom.
+      // This means if there are dependent strings floating around using str's
+      // chars, they will be able to use the chars from the atom.
+      static_assert(StringToAtomCache::MinStringLength >
+                    JSFatInlineString::MAX_LENGTH_LATIN1);
+      static_assert(StringToAtomCache::MinStringLength >
+                    JSFatInlineString::MAX_LENGTH_TWO_BYTE);
+      MOZ_ASSERT(src->canOwnDependentChars());
+      MOZ_ASSERT(atom->canOwnDependentChars());
+
+      StringRelocationOverlay::forwardCell(src, atom);
+      gcprobes::PromoteToTenured(src, atom);
+      return atom;
+    }
+  }
+
+  JSString* dst;
+
+  // A live nursery string can only get deduplicated when:
+  // 1. Its length is smaller than MAX_DEDUPLICATABLE_STRING_LENGTH:
+  //    Hashing a long string can affect performance.
+  // 2. It is linear:
+  //    Deduplicating every node in it would end up doing O(n^2) hashing work.
+  // 3. It is deduplicatable:
+  //    The JSString NON_DEDUP_BIT flag is unset.
+  // 4. It matches an entry in stringDeDupSet.
+
+  if (src->length() < MAX_DEDUPLICATABLE_STRING_LENGTH && src->isLinear() &&
+      src->isDeduplicatable() && stringDeDupSet.isSome()) {
+    if (auto p = stringDeDupSet->lookup(src)) {
+      // Deduplicate to the looked-up string!
+      dst = *p;
+      zone->stringStats.ref().noteDeduplicated(src->length(), src->allocSize());
+      StringRelocationOverlay::forwardCell(src, dst);
+      gcprobes::PromoteToTenured(src, dst);
+      return dst;
+    }
+
+    dst = allocTenuredString(src, zone, dstKind);
+
+    if (!stringDeDupSet->putNew(dst)) {
+      // When there is oom caused by the stringDeDupSet, stop deduplicating
+      // strings.
+      stringDeDupSet.reset();
+    }
+  } else {
+    dst = allocTenuredString(src, zone, dstKind);
+    dst->clearNonDeduplicatable();
+  }
+
+  zone->stringStats.ref().noteTenured(src->allocSize());
+
+  auto* overlay = StringRelocationOverlay::forwardCell(src, dst);
+  MOZ_ASSERT(dst->isDeduplicatable());
+
+  if (dst->hasBase() || dst->isRope()) {
+    // dst or one of its leaves might have a base that will be deduplicated.
+    // Insert the overlay into the fixup list to relocate it later.
+    insertIntoStringFixupList(overlay);
+  }
+
+  gcprobes::PromoteToTenured(src, dst);
+  return dst;
+}
+
+template <typename CharT>
+void js::gc::TenuringTracer::relocateDependentStringChars(
+    JSDependentString* tenuredDependentStr, JSLinearString* baseOrRelocOverlay,
+    size_t* offset, bool* rootBaseNotYetForwarded, JSLinearString** rootBase) {
+  MOZ_ASSERT(*offset == 0);
+  MOZ_ASSERT(*rootBaseNotYetForwarded == false);
+  MOZ_ASSERT(*rootBase == nullptr);
+
+  JS::AutoCheckCannotGC nogc;
+
+  const CharT* dependentStrChars =
+      tenuredDependentStr->nonInlineChars<CharT>(nogc);
+
+  // Traverse the dependent string nursery base chain to find the base that
+  // it's using chars from.
+  while (true) {
+    if (baseOrRelocOverlay->isForwarded()) {
+      JSLinearString* tenuredBase = Forwarded(baseOrRelocOverlay);
+      StringRelocationOverlay* relocOverlay =
+          StringRelocationOverlay::fromCell(baseOrRelocOverlay);
+
+      if (!tenuredBase->hasBase()) {
+        // The nursery root base is relocOverlay, it is tenured to tenuredBase.
+        // Relocate tenuredDependentStr chars and reassign the tenured root base
+        // as its base.
+        JSLinearString* tenuredRootBase = tenuredBase;
+        const CharT* rootBaseChars = relocOverlay->savedNurseryChars<CharT>();
+        *offset = dependentStrChars - rootBaseChars;
+        MOZ_ASSERT(*offset < tenuredRootBase->length());
+        tenuredDependentStr->relocateNonInlineChars<const CharT*>(
+            tenuredRootBase->nonInlineChars<CharT>(nogc), *offset);
+        tenuredDependentStr->setBase(tenuredRootBase);
+        return;
+      }
+
+      baseOrRelocOverlay = relocOverlay->savedNurseryBaseOrRelocOverlay();
+
+    } else {
+      JSLinearString* base = baseOrRelocOverlay;
+
+      if (!base->hasBase()) {
+        // The root base is not forwarded yet, it is simply base.
+        *rootBase = base;
+
+        // The root base can be in either the nursery or the tenured heap.
+        // dependentStr chars needs to be relocated after traceString if the
+        // root base is in the nursery.
+        if (!(*rootBase)->isTenured()) {
+          *rootBaseNotYetForwarded = true;
+          const CharT* rootBaseChars = (*rootBase)->nonInlineChars<CharT>(nogc);
+          *offset = dependentStrChars - rootBaseChars;
+          MOZ_ASSERT(*offset < base->length(), "Tenured root base");
+        }
+
+        tenuredDependentStr->setBase(*rootBase);
+
+        return;
+      }
+
+      baseOrRelocOverlay = base->nurseryBaseOrRelocOverlay();
+    }
+  }
+}
+
+JS::BigInt* js::gc::TenuringTracer::moveToTenured(JS::BigInt* src) {
+  MOZ_ASSERT(IsInsideNursery(src));
+
+  AllocKind dstKind = src->getAllocKind();
+  Zone* zone = src->nurseryZone();
+  zone->tenuredBigInts++;
+
+  JS::BigInt* dst = allocTenured<JS::BigInt>(zone, dstKind);
+  tenuredSize += moveBigIntToTenured(dst, src, dstKind);
+  tenuredCells++;
+
+  RelocationOverlay::forwardCell(src, dst);
+
+  gcprobes::PromoteToTenured(src, dst);
+  return dst;
+}
+
+void js::gc::TenuringTracer::collectToObjectFixedPoint() {
+  while (RelocationOverlay* p = objHead) {
+    objHead = objHead->next();
+    auto* obj = static_cast<JSObject*>(p->forwardingAddress());
+    traceObject(obj);
+  }
+}
+
+void js::gc::TenuringTracer::collectToStringFixedPoint() {
+  while (StringRelocationOverlay* p = stringHead) {
+    stringHead = stringHead->next();
+
+    auto* tenuredStr = static_cast<JSString*>(p->forwardingAddress());
+    // To ensure the NON_DEDUP_BIT was reset properly.
+    MOZ_ASSERT(tenuredStr->isDeduplicatable());
+
+    // The nursery root base might not be forwarded before
+    // traceString(tenuredStr). traceString(tenuredStr) will forward the root
+    // base if that's the case. Dependent string chars needs to be relocated
+    // after traceString if root base was not forwarded.
+    size_t offset = 0;
+    bool rootBaseNotYetForwarded = false;
+    JSLinearString* rootBase = nullptr;
+
+    if (tenuredStr->isDependent()) {
+      if (tenuredStr->hasTwoByteChars()) {
+        relocateDependentStringChars<char16_t>(
+            &tenuredStr->asDependent(), p->savedNurseryBaseOrRelocOverlay(),
+            &offset, &rootBaseNotYetForwarded, &rootBase);
+      } else {
+        relocateDependentStringChars<JS::Latin1Char>(
+            &tenuredStr->asDependent(), p->savedNurseryBaseOrRelocOverlay(),
+            &offset, &rootBaseNotYetForwarded, &rootBase);
+      }
+    }
+
+    traceString(tenuredStr);
+
+    if (rootBaseNotYetForwarded) {
+      MOZ_ASSERT(rootBase->isForwarded(),
+                 "traceString() should make it forwarded");
+      JS::AutoCheckCannotGC nogc;
+
+      JSLinearString* tenuredRootBase = Forwarded(rootBase);
+      MOZ_ASSERT(offset < tenuredRootBase->length());
+
+      if (tenuredStr->hasTwoByteChars()) {
+        tenuredStr->asDependent().relocateNonInlineChars<const char16_t*>(
+            tenuredRootBase->twoByteChars(nogc), offset);
+      } else {
+        tenuredStr->asDependent().relocateNonInlineChars<const JS::Latin1Char*>(
+            tenuredRootBase->latin1Chars(nogc), offset);
+      }
+      tenuredStr->setBase(tenuredRootBase);
+    }
+  }
+}
+
+size_t js::gc::TenuringTracer::moveStringToTenured(JSString* dst, JSString* src,
+                                                   AllocKind dstKind) {
+  size_t size = Arena::thingSize(dstKind);
+
+  // At the moment, strings always have the same AllocKind between src and
+  // dst. This may change in the future.
+  MOZ_ASSERT(dst->asTenured().getAllocKind() == src->getAllocKind());
+
+  // Copy the Cell contents.
+  MOZ_ASSERT(OffsetToChunkEnd(src) >= ptrdiff_t(size));
+  js_memcpy(dst, src, size);
+
+  if (src->ownsMallocedChars()) {
+    void* chars = src->asLinear().nonInlineCharsRaw();
+    nursery().removeMallocedBufferDuringMinorGC(chars);
+    AddCellMemory(dst, dst->asLinear().allocSize(), MemoryUse::StringContents);
+  }
+
+  return size;
+}
+
+size_t js::gc::TenuringTracer::moveBigIntToTenured(JS::BigInt* dst,
+                                                   JS::BigInt* src,
+                                                   AllocKind dstKind) {
+  size_t size = Arena::thingSize(dstKind);
+
+  // At the moment, BigInts always have the same AllocKind between src and
+  // dst. This may change in the future.
+  MOZ_ASSERT(dst->asTenured().getAllocKind() == src->getAllocKind());
+
+  // Copy the Cell contents.
+  MOZ_ASSERT(OffsetToChunkEnd(src) >= ptrdiff_t(size));
+  js_memcpy(dst, src, size);
+
+  MOZ_ASSERT(dst->zone() == src->nurseryZone());
+
+  if (src->hasHeapDigits()) {
+    size_t length = dst->digitLength();
+    if (!nursery().isInside(src->heapDigits_)) {
+      nursery().removeMallocedBufferDuringMinorGC(src->heapDigits_);
+    } else {
+      Zone* zone = src->nurseryZone();
+      {
+        AutoEnterOOMUnsafeRegion oomUnsafe;
+        dst->heapDigits_ = zone->pod_malloc<JS::BigInt::Digit>(length);
+        if (!dst->heapDigits_) {
+          oomUnsafe.crash(sizeof(JS::BigInt::Digit) * length,
+                          "Failed to allocate digits while tenuring.");
+        }
+      }
+
+      PodCopy(dst->heapDigits_, src->heapDigits_, length);
+      nursery().setDirectForwardingPointer(src->heapDigits_, dst->heapDigits_);
+
+      size += length * sizeof(JS::BigInt::Digit);
+    }
+
+    AddCellMemory(dst, length * sizeof(JS::BigInt::Digit),
+                  MemoryUse::BigIntDigits);
+  }
+
+  return size;
+}
+
+MinorSweepingTracer::MinorSweepingTracer(JSRuntime* rt)
+    : GenericTracerImpl(rt, JS::TracerKind::MinorSweeping,
+                        JS::WeakMapTraceAction::TraceKeysAndValues) {
+  MOZ_ASSERT(CurrentThreadCanAccessRuntime(runtime()));
+  MOZ_ASSERT(JS::RuntimeHeapIsMinorCollecting());
+}
+
+template <typename T>
+inline void MinorSweepingTracer::onEdge(T** thingp, const char* name) {
+  T* thing = *thingp;
+  if (thing->isTenured()) {
+    return;
+  }
+
+  if (IsForwarded(thing)) {
+    *thingp = Forwarded(thing);
+    return;
+  }
+
+  *thingp = nullptr;
+}