js/src/gc/Tenuring.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /*
   8  * Implementation of nursery eviction (tenuring).
   9  */
  10
  11 #include "gc/Tenuring.h"
  12
  13 #include "mozilla/PodOperations.h"
  14
  15 #include "gc/Cell.h"
  16 #include "gc/GCInternals.h"
  17 #include "gc/GCProbes.h"
  18 #include "gc/Pretenuring.h"
  19 #include "gc/Zone.h"
  20 #include "jit/JitCode.h"
  21 #include "proxy/Proxy.h"
  22 #include "vm/BigIntType.h"
  23 #include "vm/JSScript.h"
  24 #include "vm/NativeObject.h"
  25 #include "vm/Runtime.h"
  26 #include "vm/TypedArrayObject.h"
  27
  28 #include "gc/Heap-inl.h"
  29 #include "gc/Marking-inl.h"
  30 #include "gc/ObjectKind-inl.h"
  31 #include "gc/StoreBuffer-inl.h"
  32 #include "gc/TraceMethods-inl.h"
  33 #include "vm/JSObject-inl.h"
  34 #include "vm/PlainObject-inl.h"
  35 #include "vm/StringType-inl.h"
  36 #ifdef ENABLE_RECORD_TUPLE
  37 #  include "vm/TupleType.h"
  38 #endif
  39
  40 using namespace js;
  41 using namespace js::gc;
  42
  43 using mozilla::PodCopy;
  44
  45 constexpr size_t MAX_DEDUPLICATABLE_STRING_LENGTH = 500;
  46
  47 TenuringTracer::TenuringTracer(JSRuntime* rt, Nursery* nursery)
  48     : JSTracer(rt, JS::TracerKind::Tenuring,
  49                JS::WeakMapTraceAction::TraceKeysAndValues),
  50       nursery_(*nursery) {
  51   stringDeDupSet.emplace();
  52 }
  53
  54 size_t TenuringTracer::getTenuredSize() const {
  55   return tenuredSize + tenuredCells * sizeof(NurseryCellHeader);
  56 }
  57
  58 size_t TenuringTracer::getTenuredCells() const { return tenuredCells; }
  59
  60 static inline void UpdateAllocSiteOnTenure(Cell* cell) {
  61   AllocSite* site = NurseryCellHeader::from(cell)->allocSite();
  62   site->incTenuredCount();
  63 }
  64
  65 void TenuringTracer::onObjectEdge(JSObject** objp, const char* name) {
  66   JSObject* obj = *objp;
  67   if (!IsInsideNursery(obj)) {
  68     return;
  69   }
  70
  71   if (obj->isForwarded()) {
  72     const gc::RelocationOverlay* overlay = gc::RelocationOverlay::fromCell(obj);
  73     *objp = static_cast<JSObject*>(overlay->forwardingAddress());
  74     return;
  75   }
  76
  77   UpdateAllocSiteOnTenure(obj);
  78
  79   // Take a fast path for tenuring a plain object which is by far the most
  80   // common case.
  81   if (obj->is<PlainObject>()) {
  82     *objp = movePlainObjectToTenured(&obj->as<PlainObject>());
  83     return;
  84   }
  85
  86   *objp = moveToTenuredSlow(obj);
  87 }
  88
  89 void TenuringTracer::onStringEdge(JSString** strp, const char* name) {
  90   JSString* str = *strp;
  91   if (!IsInsideNursery(str)) {
  92     return;
  93   }
  94
  95   if (str->isForwarded()) {
  96     const gc::RelocationOverlay* overlay = gc::RelocationOverlay::fromCell(str);
  97     *strp = static_cast<JSString*>(overlay->forwardingAddress());
  98     return;
  99   }
 100
 101   UpdateAllocSiteOnTenure(str);
 102
 103   *strp = moveToTenured(str);
 104 }
 105
 106 void TenuringTracer::onBigIntEdge(JS::BigInt** bip, const char* name) {
 107   JS::BigInt* bi = *bip;
 108   if (!IsInsideNursery(bi)) {
 109     return;
 110   }
 111
 112   if (bi->isForwarded()) {
 113     const gc::RelocationOverlay* overlay = gc::RelocationOverlay::fromCell(bi);
 114     *bip = static_cast<JS::BigInt*>(overlay->forwardingAddress());
 115     return;
 116   }
 117
 118   UpdateAllocSiteOnTenure(bi);
 119
 120   *bip = moveToTenured(bi);
 121 }
 122
 123 void TenuringTracer::onSymbolEdge(JS::Symbol** symp, const char* name) {}
 124 void TenuringTracer::onScriptEdge(BaseScript** scriptp, const char* name) {}
 125 void TenuringTracer::onShapeEdge(Shape** shapep, const char* name) {}
 126 void TenuringTracer::onRegExpSharedEdge(RegExpShared** sharedp,
 127                                         const char* name) {}
 128 void TenuringTracer::onBaseShapeEdge(BaseShape** basep, const char* name) {}
 129 void TenuringTracer::onGetterSetterEdge(GetterSetter** gsp, const char* name) {}
 130 void TenuringTracer::onPropMapEdge(PropMap** mapp, const char* name) {}
 131 void TenuringTracer::onJitCodeEdge(jit::JitCode** codep, const char* name) {}
 132 void TenuringTracer::onScopeEdge(Scope** scopep, const char* name) {}
 133
 134 void TenuringTracer::traverse(JS::Value* thingp) {
 135   MOZ_ASSERT(!nursery().isInside(thingp));
 136
 137   Value value = *thingp;
 138   CheckTracedThing(this, value);
 139
 140   // We only care about a few kinds of GC thing here and this generates much
 141   // tighter code than using MapGCThingTyped.
 142   Value post;
 143   if (value.isObject()) {
 144     JSObject* obj = &value.toObject();
 145     onObjectEdge(&obj, "value");
 146     post = JS::ObjectValue(*obj);
 147   }
 148 #ifdef ENABLE_RECORD_TUPLE
 149   else if (value.isExtendedPrimitive()) {
 150     JSObject* obj = &value.toExtendedPrimitive();
 151     onObjectEdge(&obj, "value");
 152     post = JS::ExtendedPrimitiveValue(*obj);
 153   }
 154 #endif
 155   else if (value.isString()) {
 156     JSString* str = value.toString();
 157     onStringEdge(&str, "value");
 158     post = JS::StringValue(str);
 159   } else if (value.isBigInt()) {
 160     JS::BigInt* bi = value.toBigInt();
 161     onBigIntEdge(&bi, "value");
 162     post = JS::BigIntValue(bi);
 163   } else {
 164     MOZ_ASSERT_IF(value.isGCThing(), !IsInsideNursery(value.toGCThing()));
 165     return;
 166   }
 167
 168   if (post != value) {
 169     *thingp = post;
 170   }
 171 }
 172
 173 void TenuringTracer::traverse(wasm::AnyRef* thingp) {
 174   MOZ_ASSERT(!nursery().isInside(thingp));
 175
 176   wasm::AnyRef value = *thingp;
 177   CheckTracedThing(this, value);
 178
 179   wasm::AnyRef post = wasm::AnyRef::invalid();
 180   switch (value.kind()) {
 181     case wasm::AnyRefKind::Object: {
 182       JSObject* obj = &value.toJSObject();
 183       onObjectEdge(&obj, "value");
 184       post = wasm::AnyRef::fromJSObject(*obj);
 185       break;
 186     }
 187     case wasm::AnyRefKind::String: {
 188       JSString* str = value.toJSString();
 189       onStringEdge(&str, "string");
 190       post = wasm::AnyRef::fromJSString(str);
 191       break;
 192     }
 193     case wasm::AnyRefKind::I31:
 194     case wasm::AnyRefKind::Null: {
 195       // This function must only be called for GC things.
 196       MOZ_CRASH();
 197     }
 198   }
 199
 200   if (post != value) {
 201     *thingp = post;
 202   }
 203 }
 204
 205 template <typename T>
 206 void js::gc::StoreBuffer::MonoTypeBuffer<T>::trace(TenuringTracer& mover,
 207                                                    StoreBuffer* owner) {
 208   mozilla::ReentrancyGuard g(*owner);
 209   MOZ_ASSERT(owner->isEnabled());
 210
 211   if (last_) {
 212     last_.trace(mover);
 213   }
 214
 215   for (typename StoreSet::Range r = stores_.all(); !r.empty(); r.popFront()) {
 216     r.front().trace(mover);
 217   }
 218 }
 219
 220 namespace js::gc {
 221 template void StoreBuffer::MonoTypeBuffer<StoreBuffer::ValueEdge>::trace(
 222     TenuringTracer&, StoreBuffer* owner);
 223 template void StoreBuffer::MonoTypeBuffer<StoreBuffer::SlotsEdge>::trace(
 224     TenuringTracer&, StoreBuffer* owner);
 225 template void StoreBuffer::MonoTypeBuffer<StoreBuffer::WasmAnyRefEdge>::trace(
 226     TenuringTracer&, StoreBuffer* owner);
 227 template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::StringPtrEdge>;
 228 template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::BigIntPtrEdge>;
 229 template struct StoreBuffer::MonoTypeBuffer<StoreBuffer::ObjectPtrEdge>;
 230 }  // namespace js::gc
 231
 232 void js::gc::StoreBuffer::SlotsEdge::trace(TenuringTracer& mover) const {
 233   NativeObject* obj = object();
 234   MOZ_ASSERT(IsCellPointerValid(obj));
 235
 236   // Beware JSObject::swap exchanging a native object for a non-native one.
 237   if (!obj->is<NativeObject>()) {
 238     return;
 239   }
 240
 241   MOZ_ASSERT(!IsInsideNursery(obj), "obj shouldn't live in nursery.");
 242
 243   if (kind() == ElementKind) {
 244     uint32_t initLen = obj->getDenseInitializedLength();
 245     uint32_t numShifted = obj->getElementsHeader()->numShiftedElements();
 246     uint32_t clampedStart = start_;
 247     clampedStart = numShifted < clampedStart ? clampedStart - numShifted : 0;
 248     clampedStart = std::min(clampedStart, initLen);
 249     uint32_t clampedEnd = start_ + count_;
 250     clampedEnd = numShifted < clampedEnd ? clampedEnd - numShifted : 0;
 251     clampedEnd = std::min(clampedEnd, initLen);
 252     MOZ_ASSERT(clampedStart <= clampedEnd);
 253     mover.traceSlots(
 254         static_cast<HeapSlot*>(obj->getDenseElements() + clampedStart)
 255             ->unbarrieredAddress(),
 256         clampedEnd - clampedStart);
 257   } else {
 258     uint32_t start = std::min(start_, obj->slotSpan());
 259     uint32_t end = std::min(start_ + count_, obj->slotSpan());
 260     MOZ_ASSERT(start <= end);
 261     mover.traceObjectSlots(obj, start, end);
 262   }
 263 }
 264
 265 static inline void TraceWholeCell(TenuringTracer& mover, JSObject* object) {
 266   MOZ_ASSERT_IF(object->storeBuffer(),
 267                 !object->storeBuffer()->markingNondeduplicatable);
 268   mover.traceObject(object);
 269 }
 270
 271 // Non-deduplicatable marking is necessary because of the following 2 reasons:
 272 //
 273 // 1. Tenured string chars cannot be updated:
 274 //
 275 //    If any of the tenured string's bases were deduplicated during tenuring,
 276 //    the tenured string's chars pointer would need to be adjusted. This would
 277 //    then require updating any other tenured strings that are dependent on the
 278 //    first tenured string, and we have no way to find them without scanning
 279 //    the entire tenured heap.
 280 //
 281 // 2. Tenured string cannot store its nursery base or base's chars:
 282 //
 283 //    Tenured strings have no place to stash a pointer to their nursery base or
 284 //    its chars. You need to be able to traverse any dependent string's chain
 285 //    of bases up to a nursery "root base" that points to the malloced chars
 286 //    that the dependent strings started out pointing to, so that you can
 287 //    calculate the offset of any dependent string and update the ptr+offset if
 288 //    the root base gets deduplicated to a different allocation. Tenured
 289 //    strings in this base chain will stop you from reaching the nursery
 290 //    version of the root base; you can only get to the tenured version, and it
 291 //    has no place to store the original chars pointer.
 292 static inline void PreventDeduplicationOfReachableStrings(JSString* str) {
 293   MOZ_ASSERT(str->isTenured());
 294   MOZ_ASSERT(!str->isForwarded());
 295
 296   JSLinearString* baseOrRelocOverlay = str->nurseryBaseOrRelocOverlay();
 297
 298   // Walk along the chain of dependent strings' base string pointers
 299   // to mark them all non-deduplicatable.
 300   while (true) {
 301     // baseOrRelocOverlay can be one of the three cases:
 302     // 1. forwarded nursery string:
 303     //    The forwarded string still retains the flag that can tell whether
 304     //    this string is a dependent string with a base. Its
 305     //    StringRelocationOverlay holds a saved pointer to its base in the
 306     //    nursery.
 307     // 2. not yet forwarded nursery string:
 308     //    Retrieve the base field directly from the string.
 309     // 3. tenured string:
 310     //    The nursery base chain ends here, so stop traversing.
 311     if (baseOrRelocOverlay->isForwarded()) {
 312       JSLinearString* tenuredBase = Forwarded(baseOrRelocOverlay);
 313       if (!tenuredBase->hasBase()) {
 314         break;
 315       }
 316       baseOrRelocOverlay = StringRelocationOverlay::fromCell(baseOrRelocOverlay)
 317                                ->savedNurseryBaseOrRelocOverlay();
 318     } else {
 319       JSLinearString* base = baseOrRelocOverlay;
 320       if (base->isTenured()) {
 321         break;
 322       }
 323       if (base->isDeduplicatable()) {
 324         base->setNonDeduplicatable();
 325       }
 326       if (!base->hasBase()) {
 327         break;
 328       }
 329       baseOrRelocOverlay = base->nurseryBaseOrRelocOverlay();
 330     }
 331   }
 332 }
 333
 334 static inline void TraceWholeCell(TenuringTracer& mover, JSString* str) {
 335   MOZ_ASSERT_IF(str->storeBuffer(),
 336                 str->storeBuffer()->markingNondeduplicatable);
 337
 338   // Mark all strings reachable from the tenured string `str` as
 339   // non-deduplicatable. These strings are the bases of the tenured dependent
 340   // string.
 341   if (str->hasBase()) {
 342     PreventDeduplicationOfReachableStrings(str);
 343   }
 344
 345   str->traceChildren(&mover);
 346 }
 347
 348 static inline void TraceWholeCell(TenuringTracer& mover, BaseScript* script) {
 349   script->traceChildren(&mover);
 350 }
 351
 352 static inline void TraceWholeCell(TenuringTracer& mover,
 353                                   jit::JitCode* jitcode) {
 354   jitcode->traceChildren(&mover);
 355 }
 356
 357 template <typename T>
 358 static void TraceBufferedCells(TenuringTracer& mover, Arena* arena,
 359                                ArenaCellSet* cells) {
 360   for (size_t i = 0; i < MaxArenaCellIndex; i += cells->BitsPerWord) {
 361     ArenaCellSet::WordT bitset = cells->getWord(i / cells->BitsPerWord);
 362     while (bitset) {
 363       size_t bit = i + js::detail::CountTrailingZeroes(bitset);
 364       auto cell =
 365           reinterpret_cast<T*>(uintptr_t(arena) + ArenaCellIndexBytes * bit);
 366       TraceWholeCell(mover, cell);
 367       bitset &= bitset - 1;  // Clear the low bit.
 368     }
 369   }
 370 }
 371
 372 void ArenaCellSet::trace(TenuringTracer& mover) {
 373   for (ArenaCellSet* cells = this; cells; cells = cells->next) {
 374     cells->check();
 375
 376     Arena* arena = cells->arena;
 377     arena->bufferedCells() = &ArenaCellSet::Empty;
 378
 379     JS::TraceKind kind = MapAllocToTraceKind(arena->getAllocKind());
 380     switch (kind) {
 381       case JS::TraceKind::Object:
 382         TraceBufferedCells<JSObject>(mover, arena, cells);
 383         break;
 384       case JS::TraceKind::String:
 385         TraceBufferedCells<JSString>(mover, arena, cells);
 386         break;
 387       case JS::TraceKind::Script:
 388         TraceBufferedCells<BaseScript>(mover, arena, cells);
 389         break;
 390       case JS::TraceKind::JitCode:
 391         TraceBufferedCells<jit::JitCode>(mover, arena, cells);
 392         break;
 393       default:
 394         MOZ_CRASH("Unexpected trace kind");
 395     }
 396   }
 397 }
 398
 399 void js::gc::StoreBuffer::WholeCellBuffer::trace(TenuringTracer& mover,
 400                                                  StoreBuffer* owner) {
 401   MOZ_ASSERT(owner->isEnabled());
 402
 403 #ifdef DEBUG
 404   // Verify that all string whole cells are traced first before any other
 405   // strings are visited for any reason.
 406   MOZ_ASSERT(!owner->markingNondeduplicatable);
 407   owner->markingNondeduplicatable = true;
 408 #endif
 409   // Trace all of the strings to mark the non-deduplicatable bits, then trace
 410   // all other whole cells.
 411   if (stringHead_) {
 412     stringHead_->trace(mover);
 413   }
 414 #ifdef DEBUG
 415   owner->markingNondeduplicatable = false;
 416 #endif
 417   if (nonStringHead_) {
 418     nonStringHead_->trace(mover);
 419   }
 420
 421   stringHead_ = nonStringHead_ = nullptr;
 422 }
 423
 424 template <typename T>
 425 void js::gc::StoreBuffer::CellPtrEdge<T>::trace(TenuringTracer& mover) const {
 426   static_assert(std::is_base_of_v<Cell, T>, "T must be a Cell type");
 427   static_assert(!GCTypeIsTenured<T>(), "T must not be a tenured Cell type");
 428
 429   T* thing = *edge;
 430   if (!thing) {
 431     return;
 432   }
 433
 434   MOZ_ASSERT(IsCellPointerValid(thing));
 435   MOZ_ASSERT(thing->getTraceKind() == JS::MapTypeToTraceKind<T>::kind);
 436
 437   if (std::is_same_v<JSString, T>) {
 438     // Nursery string deduplication requires all tenured string -> nursery
 439     // string edges to be registered with the whole cell buffer in order to
 440     // correctly set the non-deduplicatable bit.
 441     MOZ_ASSERT(!mover.runtime()->gc.isPointerWithinTenuredCell(
 442         edge, JS::TraceKind::String));
 443   }
 444
 445   DispatchToOnEdge(&mover, edge, "CellPtrEdge");
 446 }
 447
 448 void js::gc::StoreBuffer::ValueEdge::trace(TenuringTracer& mover) const {
 449   if (deref()) {
 450     mover.traverse(edge);
 451   }
 452 }
 453
 454 void js::gc::StoreBuffer::WasmAnyRefEdge::trace(TenuringTracer& mover) const {
 455   if (deref()) {
 456     mover.traverse(edge);
 457   }
 458 }
 459
 460 // Visit all object children of the object and trace them.
 461 void js::gc::TenuringTracer::traceObject(JSObject* obj) {
 462   const JSClass* clasp = obj->getClass();
 463   MOZ_ASSERT(clasp);
 464
 465   if (clasp->hasTrace()) {
 466     clasp->doTrace(this, obj);
 467   }
 468
 469   if (!obj->is<NativeObject>()) {
 470     return;
 471   }
 472
 473   NativeObject* nobj = &obj->as<NativeObject>();
 474   if (!nobj->hasEmptyElements()) {
 475     HeapSlotArray elements = nobj->getDenseElements();
 476     Value* elems = elements.begin()->unbarrieredAddress();
 477     traceSlots(elems, elems + nobj->getDenseInitializedLength());
 478   }
 479
 480   traceObjectSlots(nobj, 0, nobj->slotSpan());
 481 }
 482
 483 void js::gc::TenuringTracer::traceObjectSlots(NativeObject* nobj,
 484                                               uint32_t start, uint32_t end) {
 485   auto traceRange = [this](HeapSlot* slotStart, HeapSlot* slotEnd) {
 486     traceSlots(slotStart->unbarrieredAddress(), slotEnd->unbarrieredAddress());
 487   };
 488   nobj->forEachSlotRange(start, end, traceRange);
 489 }
 490
 491 void js::gc::TenuringTracer::traceSlots(Value* vp, Value* end) {
 492   for (; vp != end; ++vp) {
 493     traverse(vp);
 494   }
 495 }
 496
 497 inline void js::gc::TenuringTracer::traceSlots(JS::Value* vp, uint32_t nslots) {
 498   traceSlots(vp, vp + nslots);
 499 }
 500
 501 void js::gc::TenuringTracer::traceString(JSString* str) {
 502   str->traceChildren(this);
 503 }
 504
 505 void js::gc::TenuringTracer::traceBigInt(JS::BigInt* bi) {
 506   bi->traceChildren(this);
 507 }
 508
 509 #ifdef DEBUG
 510 static inline uintptr_t OffsetFromChunkStart(void* p) {
 511   return uintptr_t(p) & gc::ChunkMask;
 512 }
 513 static inline size_t OffsetToChunkEnd(void* p) {
 514   uintptr_t offsetFromStart = OffsetFromChunkStart(p);
 515   MOZ_ASSERT(offsetFromStart < ChunkSize);
 516   return ChunkSize - offsetFromStart;
 517 }
 518 #endif
 519
 520 /* Insert the given relocation entry into the list of things to visit. */
 521 inline void js::gc::TenuringTracer::insertIntoObjectFixupList(
 522     RelocationOverlay* entry) {
 523   entry->setNext(objHead);
 524   objHead = entry;
 525 }
 526
 527 template <typename T>
 528 inline T* js::gc::TenuringTracer::allocTenured(Zone* zone, AllocKind kind) {
 529   return static_cast<T*>(static_cast<Cell*>(AllocateCellInGC(zone, kind)));
 530 }
 531
 532 JSString* js::gc::TenuringTracer::allocTenuredString(JSString* src, Zone* zone,
 533                                                      AllocKind dstKind) {
 534   JSString* dst = allocTenured<JSString>(zone, dstKind);
 535   tenuredSize += moveStringToTenured(dst, src, dstKind);
 536   tenuredCells++;
 537
 538   return dst;
 539 }
 540
 541 JSObject* js::gc::TenuringTracer::moveToTenuredSlow(JSObject* src) {
 542   MOZ_ASSERT(IsInsideNursery(src));
 543   MOZ_ASSERT(!src->is<PlainObject>());
 544
 545   AllocKind dstKind = src->allocKindForTenure(nursery());
 546   auto* dst = allocTenured<JSObject>(src->nurseryZone(), dstKind);
 547
 548   size_t srcSize = Arena::thingSize(dstKind);
 549
 550   // Arrays and Tuples do not necessarily have the same AllocKind between src
 551   // and dst. We deal with this by copying elements manually, possibly
 552   // re-inlining them if there is adequate room inline in dst.
 553   //
 554   // For Arrays and Tuples we're reducing tenuredSize to the smaller srcSize
 555   // because moveElementsToTenured() accounts for all Array or Tuple elements,
 556   // even if they are inlined.
 557   if (src->is<FixedLengthTypedArrayObject>()) {
 558     auto* tarray = &src->as<FixedLengthTypedArrayObject>();
 559     // Typed arrays with inline data do not necessarily have the same
 560     // AllocKind between src and dst. The nursery does not allocate an
 561     // inline data buffer that has the same size as the slow path will do.
 562     // In the slow path, the Typed Array Object stores the inline data
 563     // in the allocated space that fits the AllocKind. In the fast path,
 564     // the nursery will allocate another buffer that is directly behind the
 565     // minimal JSObject. That buffer size plus the JSObject size is not
 566     // necessarily as large as the slow path's AllocKind size.
 567     if (tarray->hasInlineElements()) {
 568       AllocKind srcKind =
 569           GetGCObjectKind(FixedLengthTypedArrayObject::FIXED_DATA_START);
 570       size_t headerSize = Arena::thingSize(srcKind);
 571       srcSize = headerSize + tarray->byteLength();
 572     }
 573   } else if (src->canHaveFixedElements()) {
 574     srcSize = sizeof(NativeObject);
 575   }
 576
 577   tenuredSize += srcSize;
 578   tenuredCells++;
 579
 580   // Copy the Cell contents.
 581   MOZ_ASSERT(OffsetFromChunkStart(src) >= sizeof(ChunkBase));
 582   MOZ_ASSERT(OffsetToChunkEnd(src) >= srcSize);
 583   js_memcpy(dst, src, srcSize);
 584
 585   // Move the slots and elements, if we need to.
 586   if (src->is<NativeObject>()) {
 587     NativeObject* ndst = &dst->as<NativeObject>();
 588     NativeObject* nsrc = &src->as<NativeObject>();
 589     tenuredSize += moveSlotsToTenured(ndst, nsrc);
 590     tenuredSize += moveElementsToTenured(ndst, nsrc, dstKind);
 591   }
 592
 593   JSObjectMovedOp op = dst->getClass()->extObjectMovedOp();
 594   MOZ_ASSERT_IF(src->is<ProxyObject>(), op == proxy_ObjectMoved);
 595   if (op) {
 596     // Tell the hazard analysis that the object moved hook can't GC.
 597     JS::AutoSuppressGCAnalysis nogc;
 598     tenuredSize += op(dst, src);
 599   } else {
 600     MOZ_ASSERT_IF(src->getClass()->hasFinalize(),
 601                   CanNurseryAllocateFinalizedClass(src->getClass()));
 602   }
 603
 604   RelocationOverlay* overlay = RelocationOverlay::forwardCell(src, dst);
 605   insertIntoObjectFixupList(overlay);
 606
 607   gcprobes::PromoteToTenured(src, dst);
 608   return dst;
 609 }
 610
 611 inline JSObject* js::gc::TenuringTracer::movePlainObjectToTenured(
 612     PlainObject* src) {
 613   // Fast path version of moveToTenuredSlow() for specialized for PlainObject.
 614
 615   MOZ_ASSERT(IsInsideNursery(src));
 616
 617   AllocKind dstKind = src->allocKindForTenure();
 618   auto* dst = allocTenured<PlainObject>(src->nurseryZone(), dstKind);
 619
 620   size_t srcSize = Arena::thingSize(dstKind);
 621   tenuredSize += srcSize;
 622   tenuredCells++;
 623
 624   // Copy the Cell contents.
 625   MOZ_ASSERT(OffsetFromChunkStart(src) >= sizeof(ChunkBase));
 626   MOZ_ASSERT(OffsetToChunkEnd(src) >= srcSize);
 627   js_memcpy(dst, src, srcSize);
 628
 629   // Move the slots and elements.
 630   tenuredSize += moveSlotsToTenured(dst, src);
 631   tenuredSize += moveElementsToTenured(dst, src, dstKind);
 632
 633   MOZ_ASSERT(!dst->getClass()->extObjectMovedOp());
 634
 635   RelocationOverlay* overlay = RelocationOverlay::forwardCell(src, dst);
 636   insertIntoObjectFixupList(overlay);
 637
 638   gcprobes::PromoteToTenured(src, dst);
 639   return dst;
 640 }
 641
 642 size_t js::gc::TenuringTracer::moveSlotsToTenured(NativeObject* dst,
 643                                                   NativeObject* src) {
 644   /* Fixed slots have already been copied over. */
 645   if (!src->hasDynamicSlots()) {
 646     return 0;
 647   }
 648
 649   size_t count = src->numDynamicSlots();
 650   size_t allocSize = ObjectSlots::allocSize(count);
 651
 652   ObjectSlots* header = src->getSlotsHeader();
 653   Nursery::WasBufferMoved result = nursery().maybeMoveBufferOnPromotion(
 654       &header, dst, allocSize, MemoryUse::ObjectSlots);
 655   if (result == Nursery::BufferNotMoved) {
 656     return 0;
 657   }
 658
 659   dst->slots_ = header->slots();
 660   if (count) {
 661     nursery().setSlotsForwardingPointer(src->slots_, dst->slots_, count);
 662   }
 663   return allocSize;
 664 }
 665
 666 size_t js::gc::TenuringTracer::moveElementsToTenured(NativeObject* dst,
 667                                                      NativeObject* src,
 668                                                      AllocKind dstKind) {
 669   if (src->hasEmptyElements()) {
 670     return 0;
 671   }
 672
 673   ObjectElements* srcHeader = src->getElementsHeader();
 674   size_t nslots = srcHeader->numAllocatedElements();
 675   size_t allocSize = nslots * sizeof(HeapSlot);
 676
 677   // Shifted elements are copied too.
 678   uint32_t numShifted = srcHeader->numShiftedElements();
 679
 680   void* unshiftedHeader = src->getUnshiftedElementsHeader();
 681
 682   /* Unlike other objects, Arrays and Tuples can have fixed elements. */
 683   if (src->canHaveFixedElements() && nslots <= GetGCKindSlots(dstKind)) {
 684     dst->as<NativeObject>().setFixedElements();
 685     js_memcpy(dst->getElementsHeader(), unshiftedHeader, allocSize);
 686     dst->elements_ += numShifted;
 687     dst->getElementsHeader()->flags |= ObjectElements::FIXED;
 688     nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
 689                                            srcHeader->capacity);
 690     return allocSize;
 691   }
 692
 693   /* TODO Bug 874151: Prefer to put element data inline if we have space. */
 694
 695   Nursery::WasBufferMoved result = nursery().maybeMoveBufferOnPromotion(
 696       &unshiftedHeader, dst, allocSize, MemoryUse::ObjectElements);
 697   if (result == Nursery::BufferNotMoved) {
 698     return 0;
 699   }
 700
 701   dst->elements_ =
 702       static_cast<ObjectElements*>(unshiftedHeader)->elements() + numShifted;
 703   dst->getElementsHeader()->flags &= ~ObjectElements::FIXED;
 704   nursery().setElementsForwardingPointer(srcHeader, dst->getElementsHeader(),
 705                                          srcHeader->capacity);
 706   return allocSize;
 707 }
 708
 709 inline void js::gc::TenuringTracer::insertIntoStringFixupList(
 710     StringRelocationOverlay* entry) {
 711   entry->setNext(stringHead);
 712   stringHead = entry;
 713 }
 714
 715 JSString* js::gc::TenuringTracer::moveToTenured(JSString* src) {
 716   MOZ_ASSERT(IsInsideNursery(src));
 717   MOZ_ASSERT(!src->isExternal());
 718
 719   AllocKind dstKind = src->getAllocKind();
 720   Zone* zone = src->nurseryZone();
 721
 722   // If this string is in the StringToAtomCache, try to deduplicate it by using
 723   // the atom. Don't do this for dependent strings because they're more
 724   // complicated. See StringRelocationOverlay and DeduplicationStringHasher
 725   // comments.
 726   if (src->isLinear() && src->inStringToAtomCache() &&
 727       src->isDeduplicatable() && !src->hasBase()) {
 728     JSLinearString* linear = &src->asLinear();
 729     JSAtom* atom = runtime()->caches().stringToAtomCache.lookupInMap(linear);
 730     MOZ_ASSERT(atom, "Why was the cache purged before minor GC?");
 731
 732     // Only deduplicate if both strings have the same encoding, to not confuse
 733     // dependent strings.
 734     if (src->hasTwoByteChars() == atom->hasTwoByteChars()) {
 735       // The StringToAtomCache isn't used for inline strings (due to the minimum
 736       // length) so canOwnDependentChars must be true for both src and atom.
 737       // This means if there are dependent strings floating around using str's
 738       // chars, they will be able to use the chars from the atom.
 739       static_assert(StringToAtomCache::MinStringLength >
 740                     JSFatInlineString::MAX_LENGTH_LATIN1);
 741       static_assert(StringToAtomCache::MinStringLength >
 742                     JSFatInlineString::MAX_LENGTH_TWO_BYTE);
 743       MOZ_ASSERT(src->canOwnDependentChars());
 744       MOZ_ASSERT(atom->canOwnDependentChars());
 745
 746       StringRelocationOverlay::forwardCell(src, atom);
 747       gcprobes::PromoteToTenured(src, atom);
 748       return atom;
 749     }
 750   }
 751
 752   JSString* dst;
 753
 754   // A live nursery string can only get deduplicated when:
 755   // 1. Its length is smaller than MAX_DEDUPLICATABLE_STRING_LENGTH:
 756   //    Hashing a long string can affect performance.
 757   // 2. It is linear:
 758   //    Deduplicating every node in it would end up doing O(n^2) hashing work.
 759   // 3. It is deduplicatable:
 760   //    The JSString NON_DEDUP_BIT flag is unset.
 761   // 4. It matches an entry in stringDeDupSet.
 762
 763   if (src->length() < MAX_DEDUPLICATABLE_STRING_LENGTH && src->isLinear() &&
 764       src->isDeduplicatable() && stringDeDupSet.isSome()) {
 765     auto p = stringDeDupSet->lookupForAdd(src);
 766     if (p) {
 767       // Deduplicate to the looked-up string!
 768       dst = *p;
 769       zone->stringStats.ref().noteDeduplicated(src->length(), src->allocSize());
 770       StringRelocationOverlay::forwardCell(src, dst);
 771       gcprobes::PromoteToTenured(src, dst);
 772       return dst;
 773     }
 774
 775     dst = allocTenuredString(src, zone, dstKind);
 776
 777     using DedupHasher [[maybe_unused]] = DeduplicationStringHasher<JSString*>;
 778     MOZ_ASSERT(DedupHasher::hash(src) == DedupHasher::hash(dst),
 779                "src and dst must have the same hash for lookupForAdd");
 780
 781     if (!stringDeDupSet->add(p, dst)) {
 782       // When there is oom caused by the stringDeDupSet, stop deduplicating
 783       // strings.
 784       stringDeDupSet.reset();
 785     }
 786   } else {
 787     dst = allocTenuredString(src, zone, dstKind);
 788     dst->clearNonDeduplicatable();
 789   }
 790
 791   zone->stringStats.ref().noteTenured(src->allocSize());
 792
 793   auto* overlay = StringRelocationOverlay::forwardCell(src, dst);
 794   MOZ_ASSERT(dst->isDeduplicatable());
 795
 796   if (dst->hasBase() || dst->isRope()) {
 797     // dst or one of its leaves might have a base that will be deduplicated.
 798     // Insert the overlay into the fixup list to relocate it later.
 799     insertIntoStringFixupList(overlay);
 800   }
 801
 802   gcprobes::PromoteToTenured(src, dst);
 803   return dst;
 804 }
 805
 806 template <typename CharT>
 807 void js::gc::TenuringTracer::relocateDependentStringChars(
 808     JSDependentString* tenuredDependentStr, JSLinearString* baseOrRelocOverlay,
 809     size_t* offset, bool* rootBaseNotYetForwarded, JSLinearString** rootBase) {
 810   MOZ_ASSERT(*offset == 0);
 811   MOZ_ASSERT(*rootBaseNotYetForwarded == false);
 812   MOZ_ASSERT(*rootBase == nullptr);
 813
 814   JS::AutoCheckCannotGC nogc;
 815
 816   const CharT* dependentStrChars =
 817       tenuredDependentStr->nonInlineChars<CharT>(nogc);
 818
 819   // Traverse the dependent string nursery base chain to find the base that
 820   // it's using chars from.
 821   while (true) {
 822     if (baseOrRelocOverlay->isForwarded()) {
 823       JSLinearString* tenuredBase = Forwarded(baseOrRelocOverlay);
 824       StringRelocationOverlay* relocOverlay =
 825           StringRelocationOverlay::fromCell(baseOrRelocOverlay);
 826
 827       if (!tenuredBase->hasBase()) {
 828         // The nursery root base is relocOverlay, it is tenured to tenuredBase.
 829         // Relocate tenuredDependentStr chars and reassign the tenured root base
 830         // as its base.
 831         JSLinearString* tenuredRootBase = tenuredBase;
 832         const CharT* rootBaseChars = relocOverlay->savedNurseryChars<CharT>();
 833         *offset = dependentStrChars - rootBaseChars;
 834         MOZ_ASSERT(*offset < tenuredRootBase->length());
 835         tenuredDependentStr->relocateNonInlineChars<const CharT*>(
 836             tenuredRootBase->nonInlineChars<CharT>(nogc), *offset);
 837         tenuredDependentStr->setBase(tenuredRootBase);
 838         return;
 839       }
 840
 841       baseOrRelocOverlay = relocOverlay->savedNurseryBaseOrRelocOverlay();
 842
 843     } else {
 844       JSLinearString* base = baseOrRelocOverlay;
 845
 846       if (!base->hasBase()) {
 847         // The root base is not forwarded yet, it is simply base.
 848         *rootBase = base;
 849
 850         // The root base can be in either the nursery or the tenured heap.
 851         // dependentStr chars needs to be relocated after traceString if the
 852         // root base is in the nursery.
 853         if (!(*rootBase)->isTenured()) {
 854           *rootBaseNotYetForwarded = true;
 855           const CharT* rootBaseChars = (*rootBase)->nonInlineChars<CharT>(nogc);
 856           *offset = dependentStrChars - rootBaseChars;
 857           MOZ_ASSERT(*offset < base->length(), "Tenured root base");
 858         }
 859
 860         tenuredDependentStr->setBase(*rootBase);
 861
 862         return;
 863       }
 864
 865       baseOrRelocOverlay = base->nurseryBaseOrRelocOverlay();
 866     }
 867   }
 868 }
 869
 870 JS::BigInt* js::gc::TenuringTracer::moveToTenured(JS::BigInt* src) {
 871   MOZ_ASSERT(IsInsideNursery(src));
 872
 873   AllocKind dstKind = src->getAllocKind();
 874   Zone* zone = src->nurseryZone();
 875
 876   JS::BigInt* dst = allocTenured<JS::BigInt>(zone, dstKind);
 877   tenuredSize += moveBigIntToTenured(dst, src, dstKind);
 878   tenuredCells++;
 879
 880   RelocationOverlay::forwardCell(src, dst);
 881
 882   gcprobes::PromoteToTenured(src, dst);
 883   return dst;
 884 }
 885
 886 void js::gc::TenuringTracer::collectToObjectFixedPoint() {
 887   while (RelocationOverlay* p = objHead) {
 888     objHead = objHead->next();
 889     auto* obj = static_cast<JSObject*>(p->forwardingAddress());
 890     traceObject(obj);
 891   }
 892 }
 893
 894 void js::gc::TenuringTracer::collectToStringFixedPoint() {
 895   while (StringRelocationOverlay* p = stringHead) {
 896     stringHead = stringHead->next();
 897
 898     auto* tenuredStr = static_cast<JSString*>(p->forwardingAddress());
 899     // To ensure the NON_DEDUP_BIT was reset properly.
 900     MOZ_ASSERT(tenuredStr->isDeduplicatable());
 901
 902     // The nursery root base might not be forwarded before
 903     // traceString(tenuredStr). traceString(tenuredStr) will forward the root
 904     // base if that's the case. Dependent string chars needs to be relocated
 905     // after traceString if root base was not forwarded.
 906     size_t offset = 0;
 907     bool rootBaseNotYetForwarded = false;
 908     JSLinearString* rootBase = nullptr;
 909
 910     if (tenuredStr->isDependent()) {
 911       if (tenuredStr->hasTwoByteChars()) {
 912         relocateDependentStringChars<char16_t>(
 913             &tenuredStr->asDependent(), p->savedNurseryBaseOrRelocOverlay(),
 914             &offset, &rootBaseNotYetForwarded, &rootBase);
 915       } else {
 916         relocateDependentStringChars<JS::Latin1Char>(
 917             &tenuredStr->asDependent(), p->savedNurseryBaseOrRelocOverlay(),
 918             &offset, &rootBaseNotYetForwarded, &rootBase);
 919       }
 920     }
 921
 922     traceString(tenuredStr);
 923
 924     if (rootBaseNotYetForwarded) {
 925       MOZ_ASSERT(rootBase->isForwarded(),
 926                  "traceString() should make it forwarded");
 927       JS::AutoCheckCannotGC nogc;
 928
 929       JSLinearString* tenuredRootBase = Forwarded(rootBase);
 930       MOZ_ASSERT(offset < tenuredRootBase->length());
 931
 932       if (tenuredStr->hasTwoByteChars()) {
 933         tenuredStr->asDependent().relocateNonInlineChars<const char16_t*>(
 934             tenuredRootBase->twoByteChars(nogc), offset);
 935       } else {
 936         tenuredStr->asDependent().relocateNonInlineChars<const JS::Latin1Char*>(
 937             tenuredRootBase->latin1Chars(nogc), offset);
 938       }
 939       tenuredStr->setBase(tenuredRootBase);
 940     }
 941   }
 942 }
 943
 944 size_t js::gc::TenuringTracer::moveStringToTenured(JSString* dst, JSString* src,
 945                                                    AllocKind dstKind) {
 946   size_t size = Arena::thingSize(dstKind);
 947
 948   // At the moment, strings always have the same AllocKind between src and
 949   // dst. This may change in the future.
 950   MOZ_ASSERT(dst->asTenured().getAllocKind() == src->getAllocKind());
 951
 952   // Copy the Cell contents.
 953   MOZ_ASSERT(OffsetToChunkEnd(src) >= size);
 954   js_memcpy(dst, src, size);
 955
 956   if (!src->hasOutOfLineChars()) {
 957     return size;
 958   }
 959
 960   if (src->ownsMallocedChars()) {
 961     void* chars = src->asLinear().nonInlineCharsRaw();
 962     nursery().removeMallocedBufferDuringMinorGC(chars);
 963     AddCellMemory(dst, dst->asLinear().allocSize(), MemoryUse::StringContents);
 964     return size;
 965   }
 966
 967   // String data is in the nursery and needs to be moved to the malloc heap.
 968
 969   MOZ_ASSERT(nursery().isInside(src->asLinear().nonInlineCharsRaw()));
 970
 971   if (src->hasLatin1Chars()) {
 972     size += dst->asLinear().maybeMallocCharsOnPromotion<Latin1Char>(&nursery());
 973   } else {
 974     size += dst->asLinear().maybeMallocCharsOnPromotion<char16_t>(&nursery());
 975   }
 976
 977   return size;
 978 }
 979
 980 size_t js::gc::TenuringTracer::moveBigIntToTenured(JS::BigInt* dst,
 981                                                    JS::BigInt* src,
 982                                                    AllocKind dstKind) {
 983   size_t size = Arena::thingSize(dstKind);
 984
 985   // At the moment, BigInts always have the same AllocKind between src and
 986   // dst. This may change in the future.
 987   MOZ_ASSERT(dst->asTenured().getAllocKind() == src->getAllocKind());
 988
 989   // Copy the Cell contents.
 990   MOZ_ASSERT(OffsetToChunkEnd(src) >= size);
 991   js_memcpy(dst, src, size);
 992
 993   MOZ_ASSERT(dst->zone() == src->nurseryZone());
 994
 995   if (!src->hasHeapDigits()) {
 996     return size;
 997   }
 998
 999   size_t length = dst->digitLength();
1000   size_t nbytes = length * sizeof(JS::BigInt::Digit);
1001
1002   Nursery::WasBufferMoved result = nursery().maybeMoveBufferOnPromotion(
1003       &dst->heapDigits_, dst, nbytes, MemoryUse::BigIntDigits);
1004   if (result == Nursery::BufferMoved) {
1005     nursery().setDirectForwardingPointer(src->heapDigits_, dst->heapDigits_);
1006     size += nbytes;
1007   }
1008
1009   return size;
1010 }
1011
1012 template <typename Key>
1013 /* static */
1014 inline HashNumber DeduplicationStringHasher<Key>::hash(const Lookup& lookup) {
1015   JS::AutoCheckCannotGC nogc;
1016   HashNumber strHash;
1017
1018   // Include flags in the hash. A string relocation overlay stores either the
1019   // nursery root base chars or the dependent string nursery base, but does not
1020   // indicate which one. If strings with different string types were
1021   // deduplicated, for example, a dependent string gets deduplicated into an
1022   // extensible string, the base chain would be broken and the root base would
1023   // be unreachable.
1024
1025   if (lookup->asLinear().hasLatin1Chars()) {
1026     strHash = mozilla::HashString(lookup->asLinear().latin1Chars(nogc),
1027                                   lookup->length());
1028   } else {
1029     MOZ_ASSERT(lookup->asLinear().hasTwoByteChars());
1030     strHash = mozilla::HashString(lookup->asLinear().twoByteChars(nogc),
1031                                   lookup->length());
1032   }
1033
1034   return mozilla::HashGeneric(strHash, lookup->zone(), lookup->flags());
1035 }
1036
1037 template <typename Key>
1038 /* static */
1039 MOZ_ALWAYS_INLINE bool DeduplicationStringHasher<Key>::match(
1040     const Key& key, const Lookup& lookup) {
1041   if (!key->sameLengthAndFlags(*lookup) ||
1042       key->asTenured().zone() != lookup->zone() ||
1043       key->asTenured().getAllocKind() != lookup->getAllocKind()) {
1044     return false;
1045   }
1046
1047   JS::AutoCheckCannotGC nogc;
1048
1049   if (key->asLinear().hasLatin1Chars()) {
1050     MOZ_ASSERT(lookup->asLinear().hasLatin1Chars());
1051     return EqualChars(key->asLinear().latin1Chars(nogc),
1052                       lookup->asLinear().latin1Chars(nogc), lookup->length());
1053   }
1054
1055   MOZ_ASSERT(key->asLinear().hasTwoByteChars());
1056   MOZ_ASSERT(lookup->asLinear().hasTwoByteChars());
1057   return EqualChars(key->asLinear().twoByteChars(nogc),
1058                     lookup->asLinear().twoByteChars(nogc), lookup->length());
1059 }
1060
1061 MinorSweepingTracer::MinorSweepingTracer(JSRuntime* rt)
1062     : GenericTracerImpl(rt, JS::TracerKind::MinorSweeping,
1063                         JS::WeakMapTraceAction::TraceKeysAndValues) {
1064   MOZ_ASSERT(CurrentThreadCanAccessRuntime(runtime()));
1065   MOZ_ASSERT(JS::RuntimeHeapIsMinorCollecting());
1066 }
1067
1068 template <typename T>
1069 inline void MinorSweepingTracer::onEdge(T** thingp, const char* name) {
1070   T* thing = *thingp;
1071   if (thing->isTenured()) {
1072     return;
1073   }
1074
1075   if (IsForwarded(thing)) {
1076     *thingp = Forwarded(thing);
1077     return;
1078   }
1079
1080   *thingp = nullptr;
1081 }