summaryrefslogtreecommitdiffstats
path: root/js/src/gc/Tenuring.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/gc/Tenuring.cpp')
-rw-r--r--js/src/gc/Tenuring.cpp1081
1 files changed, 1081 insertions, 0 deletions
diff --git a/js/src/gc/Tenuring.cpp b/js/src/gc/Tenuring.cpp
new file mode 100644
index 0000000000..84526e2109
--- /dev/null
+++ b/js/src/gc/Tenuring.cpp
@@ -0,0 +1,1081 @@
+/* -*- 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"
+#include "vm/StringType-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;
+ }
+}
+
+void TenuringTracer::traverse(wasm::AnyRef* thingp) {
+ MOZ_ASSERT(!nursery().isInside(thingp));
+
+ wasm::AnyRef value = *thingp;
+ CheckTracedThing(this, value);
+
+ wasm::AnyRef post = wasm::AnyRef::invalid();
+ switch (value.kind()) {
+ case wasm::AnyRefKind::Object: {
+ JSObject* obj = &value.toJSObject();
+ onObjectEdge(&obj, "value");
+ post = wasm::AnyRef::fromJSObject(*obj);
+ break;
+ }
+ case wasm::AnyRefKind::String: {
+ JSString* str = value.toJSString();
+ onStringEdge(&str, "string");
+ post = wasm::AnyRef::fromJSString(str);
+ break;
+ }
+ case wasm::AnyRefKind::I31:
+ case wasm::AnyRefKind::Null: {
+ // This function must only be called for GC things.
+ MOZ_CRASH();
+ }
+ }
+
+ if (post != value) {
+ *thingp = post;
+ }
+}
+
+template <typename T>
+void js::gc::StoreBuffer::MonoTypeBuffer<T>::trace(TenuringTracer& mover,
+ StoreBuffer* owner) {
+ 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::gc {
+template void StoreBuffer::MonoTypeBuffer<StoreBuffer::ValueEdge>::trace(
+ TenuringTracer&, StoreBuffer* owner);
+template void StoreBuffer::MonoTypeBuffer<StoreBuffer::SlotsEdge>::trace(
+ TenuringTracer&, StoreBuffer* owner);
+template void StoreBuffer::MonoTypeBuffer<StoreBuffer::WasmAnyRefEdge>::trace(
+ TenuringTracer&, StoreBuffer* owner);
+template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::StringPtrEdge>;
+template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::BigIntPtrEdge>;
+template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::ObjectPtrEdge>;
+} // namespace js::gc
+
+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,
+ StoreBuffer* owner) {
+ 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);
+ }
+}
+
+void js::gc::StoreBuffer::WasmAnyRefEdge::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 size_t OffsetToChunkEnd(void* p) {
+ uintptr_t offsetFromStart = OffsetFromChunkStart(p);
+ MOZ_ASSERT(offsetFromStart < ChunkSize);
+ return ChunkSize - offsetFromStart;
+}
+#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<FixedLengthTypedArrayObject>()) {
+ auto* tarray = &src->as<FixedLengthTypedArrayObject>();
+ // 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(FixedLengthTypedArrayObject::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) >= 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) >= 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;
+ }
+
+ size_t count = src->numDynamicSlots();
+ size_t allocSize = ObjectSlots::allocSize(count);
+
+ ObjectSlots* header = src->getSlotsHeader();
+ Nursery::WasBufferMoved result = nursery().maybeMoveBufferOnPromotion(
+ &header, dst, allocSize, MemoryUse::ObjectSlots);
+ if (result == Nursery::BufferNotMoved) {
+ return 0;
+ }
+
+ dst->slots_ = header->slots();
+ 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;
+ }
+
+ ObjectElements* srcHeader = src->getElementsHeader();
+ size_t nslots = srcHeader->numAllocatedElements();
+ size_t allocSize = nslots * sizeof(HeapSlot);
+
+ // Shifted elements are copied too.
+ uint32_t numShifted = srcHeader->numShiftedElements();
+
+ void* unshiftedHeader = src->getUnshiftedElementsHeader();
+
+ /* Unlike other objects, Arrays and Tuples can have fixed elements. */
+ if (src->canHaveFixedElements() && nslots <= GetGCKindSlots(dstKind)) {
+ dst->as<NativeObject>().setFixedElements();
+ js_memcpy(dst->getElementsHeader(), unshiftedHeader, allocSize);
+ dst->elements_ += numShifted;
+ dst->getElementsHeader()->flags |= ObjectElements::FIXED;
+ nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
+ srcHeader->capacity);
+ return allocSize;
+ }
+
+ /* TODO Bug 874151: Prefer to put element data inline if we have space. */
+
+ Nursery::WasBufferMoved result = nursery().maybeMoveBufferOnPromotion(
+ &unshiftedHeader, dst, allocSize, MemoryUse::ObjectElements);
+ if (result == Nursery::BufferNotMoved) {
+ return 0;
+ }
+
+ dst->elements_ =
+ static_cast<ObjectElements*>(unshiftedHeader)->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()) {
+ auto p = stringDeDupSet->lookupForAdd(src);
+ if (p) {
+ // 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);
+
+ using DedupHasher [[maybe_unused]] = DeduplicationStringHasher<JSString*>;
+ MOZ_ASSERT(DedupHasher::hash(src) == DedupHasher::hash(dst),
+ "src and dst must have the same hash for lookupForAdd");
+
+ if (!stringDeDupSet->add(p, 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();
+
+ 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) >= size);
+ js_memcpy(dst, src, size);
+
+ if (!src->hasOutOfLineChars()) {
+ return size;
+ }
+
+ if (src->ownsMallocedChars()) {
+ void* chars = src->asLinear().nonInlineCharsRaw();
+ nursery().removeMallocedBufferDuringMinorGC(chars);
+ AddCellMemory(dst, dst->asLinear().allocSize(), MemoryUse::StringContents);
+ return size;
+ }
+
+ // String data is in the nursery and needs to be moved to the malloc heap.
+
+ MOZ_ASSERT(nursery().isInside(src->asLinear().nonInlineCharsRaw()));
+
+ if (src->hasLatin1Chars()) {
+ size += dst->asLinear().maybeMallocCharsOnPromotion<Latin1Char>(&nursery());
+ } else {
+ size += dst->asLinear().maybeMallocCharsOnPromotion<char16_t>(&nursery());
+ }
+
+ 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) >= size);
+ js_memcpy(dst, src, size);
+
+ MOZ_ASSERT(dst->zone() == src->nurseryZone());
+
+ if (!src->hasHeapDigits()) {
+ return size;
+ }
+
+ size_t length = dst->digitLength();
+ size_t nbytes = length * sizeof(JS::BigInt::Digit);
+
+ Nursery::WasBufferMoved result = nursery().maybeMoveBufferOnPromotion(
+ &dst->heapDigits_, dst, nbytes, MemoryUse::BigIntDigits);
+ if (result == Nursery::BufferMoved) {
+ nursery().setDirectForwardingPointer(src->heapDigits_, dst->heapDigits_);
+ size += nbytes;
+ }
+
+ return size;
+}
+
+template <typename Key>
+/* static */
+inline HashNumber DeduplicationStringHasher<Key>::hash(const Lookup& lookup) {
+ JS::AutoCheckCannotGC nogc;
+ HashNumber strHash;
+
+ // Include flags in the hash. A string relocation overlay stores either the
+ // nursery root base chars or the dependent string nursery base, but does not
+ // indicate which one. If strings with different string types were
+ // deduplicated, for example, a dependent string gets deduplicated into an
+ // extensible string, the base chain would be broken and the root base would
+ // be unreachable.
+
+ if (lookup->asLinear().hasLatin1Chars()) {
+ strHash = mozilla::HashString(lookup->asLinear().latin1Chars(nogc),
+ lookup->length());
+ } else {
+ MOZ_ASSERT(lookup->asLinear().hasTwoByteChars());
+ strHash = mozilla::HashString(lookup->asLinear().twoByteChars(nogc),
+ lookup->length());
+ }
+
+ return mozilla::HashGeneric(strHash, lookup->zone(), lookup->flags());
+}
+
+template <typename Key>
+/* static */
+MOZ_ALWAYS_INLINE bool DeduplicationStringHasher<Key>::match(
+ const Key& key, const Lookup& lookup) {
+ if (!key->sameLengthAndFlags(*lookup) ||
+ key->asTenured().zone() != lookup->zone() ||
+ key->asTenured().getAllocKind() != lookup->getAllocKind()) {
+ return false;
+ }
+
+ JS::AutoCheckCannotGC nogc;
+
+ if (key->asLinear().hasLatin1Chars()) {
+ MOZ_ASSERT(lookup->asLinear().hasLatin1Chars());
+ return EqualChars(key->asLinear().latin1Chars(nogc),
+ lookup->asLinear().latin1Chars(nogc), lookup->length());
+ }
+
+ MOZ_ASSERT(key->asLinear().hasTwoByteChars());
+ MOZ_ASSERT(lookup->asLinear().hasTwoByteChars());
+ return EqualChars(key->asLinear().twoByteChars(nogc),
+ lookup->asLinear().twoByteChars(nogc), lookup->length());
+}
+
+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;
+}