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