js/public/HeapAPI.h

   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 #ifndef js_HeapAPI_h
   8 #define js_HeapAPI_h
   9
  10 #include "mozilla/Atomics.h"
  11 #include "mozilla/BitSet.h"
  12
  13 #include <limits.h>
  14 #include <type_traits>
  15
  16 #include "js/AllocPolicy.h"
  17 #include "js/GCAnnotations.h"
  18 #include "js/HashTable.h"
  19 #include "js/shadow/String.h"  // JS::shadow::String
  20 #include "js/shadow/Symbol.h"  // JS::shadow::Symbol
  21 #include "js/shadow/Zone.h"    // JS::shadow::Zone
  22 #include "js/TraceKind.h"
  23 #include "js/TypeDecls.h"
  24
  25 /* These values are private to the JS engine. */
  26 namespace js {
  27
  28 class NurseryDecommitTask;
  29
  30 JS_PUBLIC_API bool CurrentThreadCanAccessZone(JS::Zone* zone);
  31
  32 // To prevent false sharing, some data structures are aligned to a typical cache
  33 // line size.
  34 static constexpr size_t TypicalCacheLineSize = 64;
  35
  36 namespace gc {
  37
  38 class Arena;
  39 struct Cell;
  40 class TenuredChunk;
  41 class StoreBuffer;
  42 class TenuredCell;
  43
  44 const size_t ArenaShift = 12;
  45 const size_t ArenaSize = size_t(1) << ArenaShift;
  46 const size_t ArenaMask = ArenaSize - 1;
  47
  48 #if defined(XP_DARWIN) && defined(__aarch64__)
  49 const size_t PageShift = 14;
  50 #else
  51 const size_t PageShift = 12;
  52 #endif
  53 // Expected page size, so we could initialze ArenasPerPage at compile-time.
  54 // The actual system page size should be queried by SystemPageSize().
  55 const size_t PageSize = size_t(1) << PageShift;
  56 constexpr size_t ArenasPerPage = PageSize / ArenaSize;
  57
  58 const size_t ChunkShift = 20;
  59 const size_t ChunkSize = size_t(1) << ChunkShift;
  60 const size_t ChunkMask = ChunkSize - 1;
  61
  62 const size_t CellAlignShift = 3;
  63 const size_t CellAlignBytes = size_t(1) << CellAlignShift;
  64 const size_t CellAlignMask = CellAlignBytes - 1;
  65
  66 const size_t CellBytesPerMarkBit = CellAlignBytes;
  67 const size_t MarkBitsPerCell = 2;
  68
  69 /*
  70  * The minimum cell size ends up as twice the cell alignment because the mark
  71  * bitmap contains one bit per CellBytesPerMarkBit bytes (which is equal to
  72  * CellAlignBytes) and we need two mark bits per cell.
  73  */
  74 const size_t MinCellSize = CellBytesPerMarkBit * MarkBitsPerCell;
  75
  76 /*
  77  * The mark bitmap has one bit per each possible cell start position. This
  78  * wastes some space for larger GC things but allows us to avoid division by the
  79  * cell's size when accessing the bitmap.
  80  */
  81 const size_t ArenaBitmapBits = ArenaSize / CellBytesPerMarkBit;
  82 const size_t ArenaBitmapBytes = HowMany(ArenaBitmapBits, 8);
  83 const size_t ArenaBitmapWords = HowMany(ArenaBitmapBits, JS_BITS_PER_WORD);
  84
  85 enum class ChunkKind : uint8_t {
  86   Invalid = 0,
  87   TenuredHeap,
  88   NurseryToSpace,
  89   NurseryFromSpace
  90 };
  91
  92 // The base class for all GC chunks, either in the nursery or in the tenured
  93 // heap memory. This structure is locatable from any GC pointer by aligning to
  94 // the chunk size.
  95 class ChunkBase {
  96  protected:
  97   // Initialize a tenured heap chunk.
  98   explicit ChunkBase(JSRuntime* rt) {
  99     MOZ_ASSERT((uintptr_t(this) & ChunkMask) == 0);
 100     initBaseForTenuredChunk(rt);
 101   }
 102
 103   void initBaseForTenuredChunk(JSRuntime* rt) {
 104     runtime = rt;
 105     storeBuffer = nullptr;
 106     kind = ChunkKind::TenuredHeap;
 107     nurseryChunkIndex = UINT8_MAX;
 108   }
 109
 110   // Initialize a nursery chunk.
 111   ChunkBase(JSRuntime* rt, StoreBuffer* sb, ChunkKind kind, uint8_t chunkIndex)
 112       : storeBuffer(sb),
 113         runtime(rt),
 114         kind(kind),
 115         nurseryChunkIndex(chunkIndex) {
 116     MOZ_ASSERT(kind == ChunkKind::NurseryFromSpace ||
 117                kind == ChunkKind::NurseryToSpace);
 118     MOZ_ASSERT((uintptr_t(this) & ChunkMask) == 0);
 119     MOZ_ASSERT(storeBuffer);
 120   }
 121
 122  public:
 123   ChunkKind getKind() const {
 124     MOZ_ASSERT_IF(storeBuffer, kind == ChunkKind::NurseryToSpace ||
 125                                    kind == ChunkKind::NurseryFromSpace);
 126     MOZ_ASSERT_IF(!storeBuffer, kind == ChunkKind::TenuredHeap);
 127     return kind;
 128   }
 129
 130   // The store buffer for pointers from tenured things to things in this
 131   // chunk. Will be non-null if and only if this is a nursery chunk.
 132   StoreBuffer* storeBuffer;
 133
 134   // Provide quick access to the runtime from absolutely anywhere.
 135   JSRuntime* runtime;
 136
 137   ChunkKind kind;
 138
 139   uint8_t nurseryChunkIndex;
 140 };
 141
 142 // Information about tenured heap chunks.
 143 struct TenuredChunkInfo {
 144  private:
 145   friend class ChunkPool;
 146   TenuredChunk* next = nullptr;
 147   TenuredChunk* prev = nullptr;
 148
 149  public:
 150   /* Number of free arenas, either committed or decommitted. */
 151   uint32_t numArenasFree;
 152
 153   /* Number of free, committed arenas. */
 154   uint32_t numArenasFreeCommitted;
 155 };
 156
 157 /*
 158  * Calculating ArenasPerChunk:
 159  *
 160  * To figure out how many Arenas will fit in a chunk we need to know how much
 161  * extra space is available after we allocate the header data. This is a problem
 162  * because the header size depends on the number of arenas in the chunk.
 163  *
 164  * The dependent fields are markBits, decommittedPages and
 165  * freeCommittedArenas. markBits needs ArenaBitmapBytes bytes per arena,
 166  * decommittedPages needs one bit per page and freeCommittedArenas needs one
 167  * bit per arena.
 168  *
 169  * We can calculate an approximate value by dividing the number of bits of free
 170  * space in the chunk by the number of bits needed per arena. This is an
 171  * approximation because it doesn't take account of the fact that the variable
 172  * sized fields must be rounded up to a whole number of words, or any padding
 173  * the compiler adds between fields.
 174  *
 175  * Fortunately, for the chunk and arena size parameters we use this
 176  * approximation turns out to be correct. If it were not we might need to adjust
 177  * the arena count down by one to allow more space for the padding.
 178  */
 179 const size_t BitsPerPageWithHeaders =
 180     (ArenaSize + ArenaBitmapBytes) * ArenasPerPage * CHAR_BIT + ArenasPerPage +
 181     1;
 182 const size_t ChunkBitsAvailable =
 183     (ChunkSize - sizeof(ChunkBase) - sizeof(TenuredChunkInfo)) * CHAR_BIT;
 184 const size_t PagesPerChunk = ChunkBitsAvailable / BitsPerPageWithHeaders;
 185 const size_t ArenasPerChunk = PagesPerChunk * ArenasPerPage;
 186 const size_t FreeCommittedBits = ArenasPerChunk;
 187 const size_t DecommitBits = PagesPerChunk;
 188 const size_t BitsPerArenaWithHeaders =
 189     (ArenaSize + ArenaBitmapBytes) * CHAR_BIT +
 190     (DecommitBits / ArenasPerChunk) + 1;
 191
 192 const size_t CalculatedChunkSizeRequired =
 193     sizeof(ChunkBase) + sizeof(TenuredChunkInfo) +
 194     RoundUp(ArenasPerChunk * ArenaBitmapBytes, sizeof(uintptr_t)) +
 195     RoundUp(FreeCommittedBits, sizeof(uint32_t) * CHAR_BIT) / CHAR_BIT +
 196     RoundUp(DecommitBits, sizeof(uint32_t) * CHAR_BIT) / CHAR_BIT +
 197     ArenasPerChunk * ArenaSize;
 198 static_assert(CalculatedChunkSizeRequired <= ChunkSize,
 199               "Calculated ArenasPerChunk is too large");
 200
 201 const size_t CalculatedChunkPadSize = ChunkSize - CalculatedChunkSizeRequired;
 202 static_assert(CalculatedChunkPadSize * CHAR_BIT < BitsPerArenaWithHeaders,
 203               "Calculated ArenasPerChunk is too small");
 204
 205 static_assert(ArenasPerChunk == 252,
 206               "Do not accidentally change our heap's density.");
 207
 208 // Mark bitmaps are atomic because they can be written by gray unmarking on the
 209 // main thread while read by sweeping on a background thread. The former does
 210 // not affect the result of the latter.
 211 using MarkBitmapWord = mozilla::Atomic<uintptr_t, mozilla::Relaxed>;
 212
 213 /*
 214  * Live objects are marked black or gray. Everything reachable from a JS root is
 215  * marked black. Objects marked gray are eligible for cycle collection.
 216  *
 217  *    BlackBit:     GrayOrBlackBit:  Color:
 218  *       0               0           white
 219  *       0               1           gray
 220  *       1               0           black
 221  *       1               1           black
 222  */
 223 enum class ColorBit : uint32_t { BlackBit = 0, GrayOrBlackBit = 1 };
 224
 225 // Mark colors. Order is important here: the greater value the 'more marked' a
 226 // cell is.
 227 enum class MarkColor : uint8_t { Gray = 1, Black = 2 };
 228
 229 // Mark bitmap for a tenured heap chunk.
 230 struct alignas(TypicalCacheLineSize) MarkBitmap {
 231   static constexpr size_t WordCount = ArenaBitmapWords * ArenasPerChunk;
 232   MarkBitmapWord bitmap[WordCount];
 233
 234   inline void getMarkWordAndMask(const TenuredCell* cell, ColorBit colorBit,
 235                                  MarkBitmapWord** wordp, uintptr_t* maskp);
 236
 237   // The following are not exported and are defined in gc/Heap.h:
 238   inline bool markBit(const TenuredCell* cell, ColorBit colorBit);
 239   inline bool isMarkedAny(const TenuredCell* cell);
 240   inline bool isMarkedBlack(const TenuredCell* cell);
 241   inline bool isMarkedGray(const TenuredCell* cell);
 242   inline bool markIfUnmarked(const TenuredCell* cell, MarkColor color);
 243   inline bool markIfUnmarkedAtomic(const TenuredCell* cell, MarkColor color);
 244   inline void markBlack(const TenuredCell* cell);
 245   inline void markBlackAtomic(const TenuredCell* cell);
 246   inline void copyMarkBit(TenuredCell* dst, const TenuredCell* src,
 247                           ColorBit colorBit);
 248   inline void unmark(const TenuredCell* cell);
 249   inline MarkBitmapWord* arenaBits(Arena* arena);
 250 };
 251
 252 static_assert(ArenaBitmapBytes * ArenasPerChunk == sizeof(MarkBitmap),
 253               "Ensure our MarkBitmap actually covers all arenas.");
 254
 255 // Bitmap with one bit per page used for decommitted page set.
 256 using ChunkPageBitmap = mozilla::BitSet<PagesPerChunk, uint32_t>;
 257
 258 // Bitmap with one bit per arena used for free committed arena set.
 259 using ChunkArenaBitmap = mozilla::BitSet<ArenasPerChunk, uint32_t>;
 260
 261 // Base class containing data members for a tenured heap chunk.
 262 class TenuredChunkBase : public ChunkBase {
 263  public:
 264   TenuredChunkInfo info;
 265   MarkBitmap markBits;
 266   ChunkArenaBitmap freeCommittedArenas;
 267   ChunkPageBitmap decommittedPages;
 268
 269  protected:
 270   explicit TenuredChunkBase(JSRuntime* runtime) : ChunkBase(runtime) {
 271     info.numArenasFree = ArenasPerChunk;
 272   }
 273
 274   void initAsDecommitted();
 275 };
 276
 277 /*
 278  * We sometimes use an index to refer to a cell in an arena. The index for a
 279  * cell is found by dividing by the cell alignment so not all indices refer to
 280  * valid cells.
 281  */
 282 const size_t ArenaCellIndexBytes = CellAlignBytes;
 283 const size_t MaxArenaCellIndex = ArenaSize / CellAlignBytes;
 284
 285 const size_t MarkBitmapWordBits = sizeof(MarkBitmapWord) * CHAR_BIT;
 286
 287 constexpr size_t FirstArenaAdjustmentBits =
 288     RoundUp(sizeof(gc::TenuredChunkBase), ArenaSize) / gc::CellBytesPerMarkBit;
 289
 290 static_assert((FirstArenaAdjustmentBits % MarkBitmapWordBits) == 0);
 291 constexpr size_t FirstArenaAdjustmentWords =
 292     FirstArenaAdjustmentBits / MarkBitmapWordBits;
 293
 294 const size_t ChunkStoreBufferOffset = offsetof(ChunkBase, storeBuffer);
 295 const size_t ChunkMarkBitmapOffset = offsetof(TenuredChunkBase, markBits);
 296
 297 // Hardcoded offsets into Arena class.
 298 const size_t ArenaZoneOffset = 2 * sizeof(uint32_t);
 299 const size_t ArenaHeaderSize = ArenaZoneOffset + 2 * sizeof(uintptr_t) +
 300                                sizeof(size_t) + sizeof(uintptr_t);
 301
 302 // The first word of a GC thing has certain requirements from the GC and is used
 303 // to store flags in the low bits.
 304 const size_t CellFlagBitsReservedForGC = 3;
 305
 306 // The first word can be used to store JSClass pointers for some thing kinds, so
 307 // these must be suitably aligned.
 308 const size_t JSClassAlignBytes = size_t(1) << CellFlagBitsReservedForGC;
 309
 310 #ifdef JS_DEBUG
 311 /* When downcasting, ensure we are actually the right type. */
 312 extern JS_PUBLIC_API void AssertGCThingHasType(js::gc::Cell* cell,
 313                                                JS::TraceKind kind);
 314 #else
 315 inline void AssertGCThingHasType(js::gc::Cell* cell, JS::TraceKind kind) {}
 316 #endif
 317
 318 MOZ_ALWAYS_INLINE bool IsInsideNursery(const js::gc::Cell* cell);
 319 MOZ_ALWAYS_INLINE bool IsInsideNursery(const js::gc::TenuredCell* cell);
 320
 321 } /* namespace gc */
 322 } /* namespace js */
 323
 324 namespace JS {
 325
 326 enum class HeapState {
 327   Idle,             // doing nothing with the GC heap
 328   Tracing,          // tracing the GC heap without collecting, e.g.
 329                     // IterateCompartments()
 330   MajorCollecting,  // doing a GC of the major heap
 331   MinorCollecting,  // doing a GC of the minor heap (nursery)
 332   CycleCollecting   // in the "Unlink" phase of cycle collection
 333 };
 334
 335 JS_PUBLIC_API HeapState RuntimeHeapState();
 336
 337 static inline bool RuntimeHeapIsBusy() {
 338   return RuntimeHeapState() != HeapState::Idle;
 339 }
 340
 341 static inline bool RuntimeHeapIsTracing() {
 342   return RuntimeHeapState() == HeapState::Tracing;
 343 }
 344
 345 static inline bool RuntimeHeapIsMajorCollecting() {
 346   return RuntimeHeapState() == HeapState::MajorCollecting;
 347 }
 348
 349 static inline bool RuntimeHeapIsMinorCollecting() {
 350   return RuntimeHeapState() == HeapState::MinorCollecting;
 351 }
 352
 353 static inline bool RuntimeHeapIsCollecting(HeapState state) {
 354   return state == HeapState::MajorCollecting ||
 355          state == HeapState::MinorCollecting;
 356 }
 357
 358 static inline bool RuntimeHeapIsCollecting() {
 359   return RuntimeHeapIsCollecting(RuntimeHeapState());
 360 }
 361
 362 static inline bool RuntimeHeapIsCycleCollecting() {
 363   return RuntimeHeapState() == HeapState::CycleCollecting;
 364 }
 365
 366 /*
 367  * This list enumerates the different types of conceptual stacks we have in
 368  * SpiderMonkey. In reality, they all share the C stack, but we allow different
 369  * stack limits depending on the type of code running.
 370  */
 371 enum StackKind {
 372   StackForSystemCode,       // C++, such as the GC, running on behalf of the VM.
 373   StackForTrustedScript,    // Script running with trusted principals.
 374   StackForUntrustedScript,  // Script running with untrusted principals.
 375   StackKindCount
 376 };
 377
 378 /*
 379  * Default maximum size for the generational nursery in bytes. This is the
 380  * initial value. In the browser this configured by the
 381  * javascript.options.mem.nursery.max_kb pref.
 382  */
 383 const uint32_t DefaultNurseryMaxBytes = 64 * js::gc::ChunkSize;
 384
 385 /* Default maximum heap size in bytes to pass to JS_NewContext(). */
 386 const uint32_t DefaultHeapMaxBytes = 32 * 1024 * 1024;
 387
 388 /**
 389  * A GC pointer, tagged with the trace kind.
 390  *
 391  * In general, a GC pointer should be stored with an exact type. This class
 392  * is for use when that is not possible because a single pointer must point
 393  * to several kinds of GC thing.
 394  */
 395 class JS_PUBLIC_API GCCellPtr {
 396  public:
 397   GCCellPtr() : GCCellPtr(nullptr) {}
 398
 399   // Construction from a void* and trace kind.
 400   GCCellPtr(void* gcthing, JS::TraceKind traceKind)
 401       : ptr(checkedCast(gcthing, traceKind)) {}
 402
 403   // Automatically construct a null GCCellPtr from nullptr.
 404   MOZ_IMPLICIT GCCellPtr(decltype(nullptr))
 405       : ptr(checkedCast(nullptr, JS::TraceKind::Null)) {}
 406
 407   // Construction from an explicit type.
 408   template <typename T>
 409   explicit GCCellPtr(T* p)
 410       : ptr(checkedCast(p, JS::MapTypeToTraceKind<T>::kind)) {}
 411   explicit GCCellPtr(JSFunction* p)
 412       : ptr(checkedCast(p, JS::TraceKind::Object)) {}
 413   explicit GCCellPtr(JSScript* p)
 414       : ptr(checkedCast(p, JS::TraceKind::Script)) {}
 415   explicit GCCellPtr(const Value& v);
 416
 417   JS::TraceKind kind() const {
 418     uintptr_t kindBits = ptr & OutOfLineTraceKindMask;
 419     if (kindBits != OutOfLineTraceKindMask) {
 420       return JS::TraceKind(kindBits);
 421     }
 422     return outOfLineKind();
 423   }
 424
 425   // Allow GCCellPtr to be used in a boolean context.
 426   explicit operator bool() const {
 427     MOZ_ASSERT(bool(asCell()) == (kind() != JS::TraceKind::Null));
 428     return asCell();
 429   }
 430
 431   // Simplify checks to the kind.
 432   template <typename T, typename = std::enable_if_t<JS::IsBaseTraceType_v<T>>>
 433   bool is() const {
 434     return kind() == JS::MapTypeToTraceKind<T>::kind;
 435   }
 436
 437   // Conversions to more specific types must match the kind. Access to
 438   // further refined types is not allowed directly from a GCCellPtr.
 439   template <typename T, typename = std::enable_if_t<JS::IsBaseTraceType_v<T>>>
 440   T& as() const {
 441     MOZ_ASSERT(kind() == JS::MapTypeToTraceKind<T>::kind);
 442     // We can't use static_cast here, because the fact that JSObject
 443     // inherits from js::gc::Cell is not part of the public API.
 444     return *reinterpret_cast<T*>(asCell());
 445   }
 446
 447   // Return a pointer to the cell this |GCCellPtr| refers to, or |nullptr|.
 448   // (It would be more symmetrical with |to| for this to return a |Cell&|, but
 449   // the result can be |nullptr|, and null references are undefined behavior.)
 450   js::gc::Cell* asCell() const {
 451     return reinterpret_cast<js::gc::Cell*>(ptr & ~OutOfLineTraceKindMask);
 452   }
 453
 454   // The CC's trace logger needs an identity that is XPIDL serializable.
 455   uint64_t unsafeAsInteger() const {
 456     return static_cast<uint64_t>(unsafeAsUIntPtr());
 457   }
 458   // Inline mark bitmap access requires direct pointer arithmetic.
 459   uintptr_t unsafeAsUIntPtr() const {
 460     MOZ_ASSERT(asCell());
 461     MOZ_ASSERT(!js::gc::IsInsideNursery(asCell()));
 462     return reinterpret_cast<uintptr_t>(asCell());
 463   }
 464
 465   MOZ_ALWAYS_INLINE bool mayBeOwnedByOtherRuntime() const {
 466     if (!is<JSString>() && !is<JS::Symbol>()) {
 467       return false;
 468     }
 469     if (is<JSString>()) {
 470       return JS::shadow::String::isPermanentAtom(asCell());
 471     }
 472     MOZ_ASSERT(is<JS::Symbol>());
 473     return JS::shadow::Symbol::isWellKnownSymbol(asCell());
 474   }
 475
 476  private:
 477   static uintptr_t checkedCast(void* p, JS::TraceKind traceKind) {
 478     auto* cell = static_cast<js::gc::Cell*>(p);
 479     MOZ_ASSERT((uintptr_t(p) & OutOfLineTraceKindMask) == 0);
 480     AssertGCThingHasType(cell, traceKind);
 481     // Store trace in the bottom bits of pointer for common kinds.
 482     uintptr_t kindBits = uintptr_t(traceKind);
 483     if (kindBits >= OutOfLineTraceKindMask) {
 484       kindBits = OutOfLineTraceKindMask;
 485     }
 486     return uintptr_t(p) | kindBits;
 487   }
 488
 489   JS::TraceKind outOfLineKind() const;
 490
 491   uintptr_t ptr;
 492 } JS_HAZ_GC_POINTER;
 493
 494 // Unwraps the given GCCellPtr, calls the functor |f| with a template argument
 495 // of the actual type of the pointer, and returns the result.
 496 template <typename F>
 497 auto MapGCThingTyped(GCCellPtr thing, F&& f) {
 498   switch (thing.kind()) {
 499 #define JS_EXPAND_DEF(name, type, _, _1) \
 500   case JS::TraceKind::name:              \
 501     return f(&thing.as<type>());
 502     JS_FOR_EACH_TRACEKIND(JS_EXPAND_DEF);
 503 #undef JS_EXPAND_DEF
 504     default:
 505       MOZ_CRASH("Invalid trace kind in MapGCThingTyped for GCCellPtr.");
 506   }
 507 }
 508
 509 // Unwraps the given GCCellPtr and calls the functor |f| with a template
 510 // argument of the actual type of the pointer. Doesn't return anything.
 511 template <typename F>
 512 void ApplyGCThingTyped(GCCellPtr thing, F&& f) {
 513   // This function doesn't do anything but is supplied for symmetry with other
 514   // MapGCThingTyped/ApplyGCThingTyped implementations that have to wrap the
 515   // functor to return a dummy value that is ignored.
 516   MapGCThingTyped(thing, f);
 517 }
 518
 519 } /* namespace JS */
 520
 521 // These are defined in the toplevel namespace instead of within JS so that
 522 // they won't shadow other operator== overloads (see bug 1456512.)
 523
 524 inline bool operator==(JS::GCCellPtr ptr1, JS::GCCellPtr ptr2) {
 525   return ptr1.asCell() == ptr2.asCell();
 526 }
 527
 528 inline bool operator!=(JS::GCCellPtr ptr1, JS::GCCellPtr ptr2) {
 529   return !(ptr1 == ptr2);
 530 }
 531
 532 namespace js {
 533 namespace gc {
 534
 535 /* static */
 536 MOZ_ALWAYS_INLINE void MarkBitmap::getMarkWordAndMask(const TenuredCell* cell,
 537                                                       ColorBit colorBit,
 538                                                       MarkBitmapWord** wordp,
 539                                                       uintptr_t* maskp) {
 540   // Note: the JIT pre-barrier trampolines inline this code. Update
 541   // MacroAssembler::emitPreBarrierFastPath code too when making changes here!
 542
 543   MOZ_ASSERT(size_t(colorBit) < MarkBitsPerCell);
 544
 545   size_t offset = uintptr_t(cell) & ChunkMask;
 546   const size_t bit = offset / CellBytesPerMarkBit + size_t(colorBit);
 547   size_t word = bit / MarkBitmapWordBits - FirstArenaAdjustmentWords;
 548   MOZ_ASSERT(word < WordCount);
 549   *wordp = &bitmap[word];
 550   *maskp = uintptr_t(1) << (bit % MarkBitmapWordBits);
 551 }
 552
 553 namespace detail {
 554
 555 static MOZ_ALWAYS_INLINE ChunkBase* GetCellChunkBase(const Cell* cell) {
 556   MOZ_ASSERT(cell);
 557   auto* chunk = reinterpret_cast<ChunkBase*>(uintptr_t(cell) & ~ChunkMask);
 558   MOZ_ASSERT(chunk->runtime);
 559   MOZ_ASSERT(chunk->kind != ChunkKind::Invalid);
 560   return chunk;
 561 }
 562
 563 static MOZ_ALWAYS_INLINE TenuredChunkBase* GetCellChunkBase(
 564     const TenuredCell* cell) {
 565   MOZ_ASSERT(cell);
 566   auto* chunk =
 567       reinterpret_cast<TenuredChunkBase*>(uintptr_t(cell) & ~ChunkMask);
 568   MOZ_ASSERT(chunk->runtime);
 569   MOZ_ASSERT(chunk->kind == ChunkKind::TenuredHeap);
 570   return chunk;
 571 }
 572
 573 static MOZ_ALWAYS_INLINE JS::Zone* GetTenuredGCThingZone(const void* ptr) {
 574   // This takes a void* because the compiler can't see type relationships in
 575   // this header. |ptr| must be a pointer to a tenured GC thing.
 576   MOZ_ASSERT(ptr);
 577   const uintptr_t zone_addr = (uintptr_t(ptr) & ~ArenaMask) | ArenaZoneOffset;
 578   return *reinterpret_cast<JS::Zone**>(zone_addr);
 579 }
 580
 581 static MOZ_ALWAYS_INLINE bool TenuredCellIsMarkedBlack(
 582     const TenuredCell* cell) {
 583   // Return true if BlackBit is set.
 584
 585   MOZ_ASSERT(cell);
 586   MOZ_ASSERT(!js::gc::IsInsideNursery(cell));
 587
 588   MarkBitmapWord* blackWord;
 589   uintptr_t blackMask;
 590   TenuredChunkBase* chunk = GetCellChunkBase(cell);
 591   chunk->markBits.getMarkWordAndMask(cell, js::gc::ColorBit::BlackBit,
 592                                      &blackWord, &blackMask);
 593   return *blackWord & blackMask;
 594 }
 595
 596 static MOZ_ALWAYS_INLINE bool NonBlackCellIsMarkedGray(
 597     const TenuredCell* cell) {
 598   // Return true if GrayOrBlackBit is set. Callers should check BlackBit first.
 599
 600   MOZ_ASSERT(cell);
 601   MOZ_ASSERT(!js::gc::IsInsideNursery(cell));
 602   MOZ_ASSERT(!TenuredCellIsMarkedBlack(cell));
 603
 604   MarkBitmapWord* grayWord;
 605   uintptr_t grayMask;
 606   TenuredChunkBase* chunk = GetCellChunkBase(cell);
 607   chunk->markBits.getMarkWordAndMask(cell, js::gc::ColorBit::GrayOrBlackBit,
 608                                      &grayWord, &grayMask);
 609   return *grayWord & grayMask;
 610 }
 611
 612 static MOZ_ALWAYS_INLINE bool TenuredCellIsMarkedGray(const TenuredCell* cell) {
 613   return !TenuredCellIsMarkedBlack(cell) && NonBlackCellIsMarkedGray(cell);
 614 }
 615
 616 static MOZ_ALWAYS_INLINE bool CellIsMarkedGray(const Cell* cell) {
 617   MOZ_ASSERT(cell);
 618   if (js::gc::IsInsideNursery(cell)) {
 619     return false;
 620   }
 621   return TenuredCellIsMarkedGray(reinterpret_cast<const TenuredCell*>(cell));
 622 }
 623
 624 extern JS_PUBLIC_API bool CanCheckGrayBits(const TenuredCell* cell);
 625
 626 extern JS_PUBLIC_API bool CellIsMarkedGrayIfKnown(const TenuredCell* cell);
 627
 628 #ifdef DEBUG
 629 extern JS_PUBLIC_API void AssertCellIsNotGray(const Cell* cell);
 630
 631 extern JS_PUBLIC_API bool ObjectIsMarkedBlack(const JSObject* obj);
 632 #endif
 633
 634 MOZ_ALWAYS_INLINE bool CellHasStoreBuffer(const Cell* cell) {
 635   return GetCellChunkBase(cell)->storeBuffer;
 636 }
 637
 638 } /* namespace detail */
 639
 640 MOZ_ALWAYS_INLINE bool IsInsideNursery(const Cell* cell) {
 641   MOZ_ASSERT(cell);
 642   return detail::CellHasStoreBuffer(cell);
 643 }
 644
 645 MOZ_ALWAYS_INLINE bool IsInsideNursery(const TenuredCell* cell) {
 646   MOZ_ASSERT(cell);
 647   MOZ_ASSERT(!IsInsideNursery(reinterpret_cast<const Cell*>(cell)));
 648   return false;
 649 }
 650
 651 // Allow use before the compiler knows the derivation of JSObject, JSString, and
 652 // JS::BigInt.
 653 MOZ_ALWAYS_INLINE bool IsInsideNursery(const JSObject* obj) {
 654   return IsInsideNursery(reinterpret_cast<const Cell*>(obj));
 655 }
 656 MOZ_ALWAYS_INLINE bool IsInsideNursery(const JSString* str) {
 657   return IsInsideNursery(reinterpret_cast<const Cell*>(str));
 658 }
 659 MOZ_ALWAYS_INLINE bool IsInsideNursery(const JS::BigInt* bi) {
 660   return IsInsideNursery(reinterpret_cast<const Cell*>(bi));
 661 }
 662
 663 MOZ_ALWAYS_INLINE bool IsCellPointerValid(const void* ptr) {
 664   auto addr = uintptr_t(ptr);
 665   if (addr < ChunkSize || addr % CellAlignBytes != 0) {
 666     return false;
 667   }
 668
 669   auto* cell = reinterpret_cast<const Cell*>(ptr);
 670   if (!IsInsideNursery(cell)) {
 671     return detail::GetTenuredGCThingZone(cell) != nullptr;
 672   }
 673
 674   return true;
 675 }
 676
 677 MOZ_ALWAYS_INLINE bool IsCellPointerValidOrNull(const void* cell) {
 678   if (!cell) {
 679     return true;
 680   }
 681   return IsCellPointerValid(cell);
 682 }
 683
 684 } /* namespace gc */
 685 } /* namespace js */
 686
 687 namespace JS {
 688
 689 extern JS_PUBLIC_API Zone* GetTenuredGCThingZone(GCCellPtr thing);
 690
 691 extern JS_PUBLIC_API Zone* GetNurseryCellZone(js::gc::Cell* cell);
 692
 693 static MOZ_ALWAYS_INLINE Zone* GetGCThingZone(GCCellPtr thing) {
 694   if (!js::gc::IsInsideNursery(thing.asCell())) {
 695     return js::gc::detail::GetTenuredGCThingZone(thing.asCell());
 696   }
 697
 698   return GetNurseryCellZone(thing.asCell());
 699 }
 700
 701 static MOZ_ALWAYS_INLINE Zone* GetStringZone(JSString* str) {
 702   if (!js::gc::IsInsideNursery(str)) {
 703     return js::gc::detail::GetTenuredGCThingZone(str);
 704   }
 705
 706   return GetNurseryCellZone(reinterpret_cast<js::gc::Cell*>(str));
 707 }
 708
 709 extern JS_PUBLIC_API Zone* GetObjectZone(JSObject* obj);
 710
 711 static MOZ_ALWAYS_INLINE bool GCThingIsMarkedGray(GCCellPtr thing) {
 712   js::gc::Cell* cell = thing.asCell();
 713   if (IsInsideNursery(cell)) {
 714     return false;
 715   }
 716
 717   auto* tenuredCell = reinterpret_cast<js::gc::TenuredCell*>(cell);
 718   return js::gc::detail::CellIsMarkedGrayIfKnown(tenuredCell);
 719 }
 720
 721 // Specialised gray marking check for use by the cycle collector. This is not
 722 // called during incremental GC or when the gray bits are invalid.
 723 static MOZ_ALWAYS_INLINE bool GCThingIsMarkedGrayInCC(GCCellPtr thing) {
 724   js::gc::Cell* cell = thing.asCell();
 725   if (IsInsideNursery(cell)) {
 726     return false;
 727   }
 728
 729   auto* tenuredCell = reinterpret_cast<js::gc::TenuredCell*>(cell);
 730   if (!js::gc::detail::TenuredCellIsMarkedGray(tenuredCell)) {
 731     return false;
 732   }
 733
 734   MOZ_ASSERT(js::gc::detail::CanCheckGrayBits(tenuredCell));
 735
 736   return true;
 737 }
 738
 739 extern JS_PUBLIC_API JS::TraceKind GCThingTraceKind(void* thing);
 740
 741 extern JS_PUBLIC_API void EnableNurseryStrings(JSContext* cx);
 742
 743 extern JS_PUBLIC_API void DisableNurseryStrings(JSContext* cx);
 744
 745 extern JS_PUBLIC_API void EnableNurseryBigInts(JSContext* cx);
 746
 747 extern JS_PUBLIC_API void DisableNurseryBigInts(JSContext* cx);
 748
 749 /*
 750  * Returns true when writes to GC thing pointers (and reads from weak pointers)
 751  * must call an incremental barrier. This is generally only true when running
 752  * mutator code in-between GC slices. At other times, the barrier may be elided
 753  * for performance.
 754  */
 755 extern JS_PUBLIC_API bool IsIncrementalBarrierNeeded(JSContext* cx);
 756
 757 /*
 758  * Notify the GC that a reference to a JSObject is about to be overwritten.
 759  * This method must be called if IsIncrementalBarrierNeeded.
 760  */
 761 extern JS_PUBLIC_API void IncrementalPreWriteBarrier(JSObject* obj);
 762
 763 /*
 764  * Notify the GC that a reference to a tenured GC cell is about to be
 765  * overwritten. This method must be called if IsIncrementalBarrierNeeded.
 766  */
 767 extern JS_PUBLIC_API void IncrementalPreWriteBarrier(GCCellPtr thing);
 768
 769 /**
 770  * Unsets the gray bit for anything reachable from |thing|. |kind| should not be
 771  * JS::TraceKind::Shape. |thing| should be non-null. The return value indicates
 772  * if anything was unmarked.
 773  */
 774 extern JS_PUBLIC_API bool UnmarkGrayGCThingRecursively(GCCellPtr thing);
 775
 776 }  // namespace JS
 777
 778 namespace js {
 779 namespace gc {
 780
 781 extern JS_PUBLIC_API void PerformIncrementalReadBarrier(JS::GCCellPtr thing);
 782
 783 static MOZ_ALWAYS_INLINE void ExposeGCThingToActiveJS(JS::GCCellPtr thing) {
 784   // TODO: I'd like to assert !RuntimeHeapIsBusy() here but this gets
 785   // called while we are tracing the heap, e.g. during memory reporting
 786   // (see bug 1313318).
 787   MOZ_ASSERT(!JS::RuntimeHeapIsCollecting());
 788
 789   // GC things residing in the nursery cannot be gray: they have no mark bits.
 790   // All live objects in the nursery are moved to tenured at the beginning of
 791   // each GC slice, so the gray marker never sees nursery things.
 792   if (IsInsideNursery(thing.asCell())) {
 793     return;
 794   }
 795
 796   auto* cell = reinterpret_cast<TenuredCell*>(thing.asCell());
 797   if (detail::TenuredCellIsMarkedBlack(cell)) {
 798     return;
 799   }
 800
 801   // GC things owned by other runtimes are always black.
 802   MOZ_ASSERT(!thing.mayBeOwnedByOtherRuntime());
 803
 804   auto* zone = JS::shadow::Zone::from(detail::GetTenuredGCThingZone(cell));
 805   if (zone->needsIncrementalBarrier()) {
 806     PerformIncrementalReadBarrier(thing);
 807   } else if (!zone->isGCPreparing() && detail::NonBlackCellIsMarkedGray(cell)) {
 808     MOZ_ALWAYS_TRUE(JS::UnmarkGrayGCThingRecursively(thing));
 809   }
 810
 811   MOZ_ASSERT_IF(!zone->isGCPreparing(), !detail::TenuredCellIsMarkedGray(cell));
 812 }
 813
 814 static MOZ_ALWAYS_INLINE void IncrementalReadBarrier(JS::GCCellPtr thing) {
 815   // This is a lighter version of ExposeGCThingToActiveJS that doesn't do gray
 816   // unmarking.
 817
 818   if (IsInsideNursery(thing.asCell())) {
 819     return;
 820   }
 821
 822   auto* cell = reinterpret_cast<TenuredCell*>(thing.asCell());
 823   auto* zone = JS::shadow::Zone::from(detail::GetTenuredGCThingZone(cell));
 824   if (zone->needsIncrementalBarrier() &&
 825       !detail::TenuredCellIsMarkedBlack(cell)) {
 826     // GC things owned by other runtimes are always black.
 827     MOZ_ASSERT(!thing.mayBeOwnedByOtherRuntime());
 828     PerformIncrementalReadBarrier(thing);
 829   }
 830 }
 831
 832 template <typename T>
 833 extern JS_PUBLIC_API bool EdgeNeedsSweepUnbarrieredSlow(T* thingp);
 834
 835 static MOZ_ALWAYS_INLINE bool EdgeNeedsSweepUnbarriered(JSObject** objp) {
 836   // This function does not handle updating nursery pointers. Raw JSObject
 837   // pointers should be updated separately or replaced with
 838   // JS::Heap<JSObject*> which handles this automatically.
 839   MOZ_ASSERT(!JS::RuntimeHeapIsMinorCollecting());
 840   if (IsInsideNursery(*objp)) {
 841     return false;
 842   }
 843
 844   auto zone = JS::shadow::Zone::from(detail::GetTenuredGCThingZone(*objp));
 845   if (!zone->isGCSweepingOrCompacting()) {
 846     return false;
 847   }
 848
 849   return EdgeNeedsSweepUnbarrieredSlow(objp);
 850 }
 851
 852 }  // namespace gc
 853 }  // namespace js
 854
 855 namespace JS {
 856
 857 /*
 858  * This should be called when an object that is marked gray is exposed to the JS
 859  * engine (by handing it to running JS code or writing it into live JS
 860  * data). During incremental GC, since the gray bits haven't been computed yet,
 861  * we conservatively mark the object black.
 862  */
 863 static MOZ_ALWAYS_INLINE void ExposeObjectToActiveJS(JSObject* obj) {
 864   MOZ_ASSERT(obj);
 865   MOZ_ASSERT(!js::gc::EdgeNeedsSweepUnbarrieredSlow(&obj));
 866   js::gc::ExposeGCThingToActiveJS(GCCellPtr(obj));
 867 }
 868
 869 } /* namespace JS */
 870
 871 #endif /* js_HeapAPI_h */