diff options
Diffstat (limited to 'js/src/gc/Tenuring.cpp')
| -rw-r--r-- | js/src/gc/Tenuring.cpp | 1081 |
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; +} |