tor-browser

GCMarker.h (21285B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* vim: set ts=8 sts=2 et sw=2 tw=80:
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef gc_GCMarker_h
#define gc_GCMarker_h

#include "mozilla/Variant.h"
#include "mozilla/XorShift128PlusRNG.h"

#include "gc/Barrier.h"
#include "js/HashTable.h"
#include "js/TracingAPI.h"
#include "js/TypeDecls.h"
#include "threading/ProtectedData.h"

class JSRope;

namespace JS {
class SliceBudget;
}

namespace js {

class GCMarker;
class WeakMapBase;

#ifdef DEBUG
// Force stack resizing to ensure OOM test coverage in debug builds.
static const size_t MARK_STACK_BASE_CAPACITY = 4;
#else
static const size_t MARK_STACK_BASE_CAPACITY = 4096;
#endif

enum class SlotsOrElementsKind {
 Unused = 0,  // Must match SlotsOrElementsRangeTag
 Elements,
 FixedSlots,
 DynamicSlots
};

namespace gc {

enum IncrementalProgress { NotFinished = 0, Finished };

class AutoSetMarkColor;
class AutoUpdateMarkStackRanges;
struct Cell;
class MarkStackIter;
class ParallelMarkTask;
class UnmarkGrayTracer;

// Ephemerons are edges from a source to a target that are only materialized
// into a table when the owner is marked. (The owner is something like a
// WeakMap, which contains a set of ephemerons each going from a WeakMap key to
// its value.) When marking a ephemeron, only the color of the owner is needed:
// the target is marked with the minimum (least-marked) color of the owner and
// source. So an EphemeronEdge need store only the owner color and the target
// pointer, which can fit into a tagged pointer since targets are aligned Cells.
//
// Note: if the owner's color changes, new EphemeronEdges will be created for
// it.
class EphemeronEdge {
 static constexpr uintptr_t ColorMask = 0x3;
 static_assert(uintptr_t(MarkColor::Gray) <= ColorMask);
 static_assert(uintptr_t(MarkColor::Black) <= ColorMask);
 static_assert(ColorMask < CellAlignBytes);

 uintptr_t taggedTarget;

public:
 EphemeronEdge(MarkColor color, TenuredCell* cell)
     : taggedTarget(uintptr_t(cell) | uintptr_t(color)) {
   MOZ_ASSERT((uintptr_t(cell) & ColorMask) == 0);
 }

 MarkColor color() const { return MarkColor(taggedTarget & ColorMask); }
 TenuredCell* target() const {
   return reinterpret_cast<TenuredCell*>(taggedTarget & ~ColorMask);
 }
};

using EphemeronEdgeVector = Vector<EphemeronEdge, 2, js::SystemAllocPolicy>;

using EphemeronEdgeTable =
   HashMap<TenuredCell*, EphemeronEdgeVector, PointerHasher<TenuredCell*>,
           js::SystemAllocPolicy>;

/*
* The mark stack. Pointers in this stack are "gray" in the GC sense, but
* their references may be marked either black or gray (in the CC sense).
*
* When the mark stack is full, the GC does not call js::TraceChildren to mark
* the reachable "children" of the thing. Rather the thing is put aside and
* js::TraceChildren is called later when the mark stack is empty.
*
* To implement such delayed marking of the children with minimal overhead for
* the normal case of sufficient stack, we link arenas into a list using
* Arena::setNextDelayedMarkingArena(). The head of the list is stored in
* GCMarker::delayedMarkingList. GCMarker::delayMarkingChildren() adds arenas
* to the list as necessary while markAllDelayedChildren() pops the arenas from
* the stack until it is empty.
*/
class MarkStack {
public:
 /*
  * We use a common mark stack to mark GC things of different types and use
  * the explicit tags to distinguish them when it cannot be deduced from
  * the context of push or pop operation.
  */
 enum Tag {
   SlotsOrElementsRangeTag = 0,  // Must match SlotsOrElementsKind::Unused.
   ObjectTag,
   SymbolTag,
   JitCodeTag,
   ScriptTag,
   TempRopeTag,

   LastTag = TempRopeTag
 };

 static const uintptr_t TagMask = 7;
 static_assert(TagMask >= uintptr_t(LastTag),
               "The tag mask must subsume the tags.");
 static_assert(TagMask <= gc::CellAlignMask,
               "The tag mask must be embeddable in a Cell*.");

 class TaggedPtr {
   uintptr_t bits;

   Cell* ptr() const;

   explicit TaggedPtr(uintptr_t bits);

  public:
   TaggedPtr(Tag tag, Cell* ptr);
   static TaggedPtr fromBits(uintptr_t bits);

   uintptr_t asBits() const;
   Tag tag() const;
   template <typename T>
   T* as() const;

   JSObject* asRangeObject() const;
   JSRope* asTempRope() const;

   void assertValid() const;
 };

 class SlotsOrElementsRange {
   uintptr_t startAndKind_;
   TaggedPtr ptr_;

   static constexpr size_t StartShift = 2;
   static constexpr size_t KindMask = (1 << StartShift) - 1;

   SlotsOrElementsRange(uintptr_t startAndKind, uintptr_t ptr);

  public:
   SlotsOrElementsRange(SlotsOrElementsKind kind, JSObject* obj, size_t start);
   static SlotsOrElementsRange fromBits(uintptr_t startAndKind, uintptr_t ptr);

   void assertValid() const;

   uintptr_t asBits0() const;
   uintptr_t asBits1() const;

   SlotsOrElementsKind kind() const;
   size_t start() const;
   TaggedPtr ptr() const;

   void setStart(size_t newStart);
   void setEmpty();
 };

 MarkStack();
 ~MarkStack();

 MarkStack(const MarkStack& other) = delete;
 MarkStack& operator=(const MarkStack& other) = delete;

 void swap(MarkStack& other);

 // The unit for capacity is mark stack words.
 size_t capacity() const { return capacity_; }
#ifdef JS_GC_ZEAL
 void setMaxCapacity(size_t maxCapacity);
#endif

 size_t position() const { return topIndex_; }

 [[nodiscard]] bool init();
 [[nodiscard]] bool resetStackCapacity();

 template <typename T>
 [[nodiscard]] bool push(T* ptr);
 void infalliblePush(const SlotsOrElementsRange& range);
 void infalliblePush(JSObject* obj, SlotsOrElementsKind kind, size_t start);
 [[nodiscard]] bool push(const TaggedPtr& ptr);
 void infalliblePush(const TaggedPtr& ptr);

 // GCMarker::eagerlyMarkChildren uses unused marking stack as temporary
 // storage to hold rope pointers.
 [[nodiscard]] bool pushTempRope(JSRope* rope);

 bool isEmpty() const { return position() == 0; }
 bool hasEntries() const { return !isEmpty(); }

 Tag peekTag() const;
 TaggedPtr popPtr();
 SlotsOrElementsRange popSlotsOrElementsRange();

 void clearAndResetCapacity();
 void clearAndFreeStack();

 void poisonUnused();

 [[nodiscard]] bool ensureSpace(size_t count);

 static size_t moveWork(GCMarker* marker, MarkStack& dst, MarkStack& src,
                        bool allowDistribute);

 size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;

private:
 uintptr_t at(size_t index) const {
   MOZ_ASSERT(topIndex_ <= capacity_);
   MOZ_ASSERT(index < topIndex_);
   return stack_[index];
 }
 uintptr_t* ptr(size_t index) {
   MOZ_ASSERT(topIndex_ <= capacity_);
   MOZ_ASSERT(index <= topIndex_);
   return stack_ + index;
 }

 // Return a pointer to the first unused word beyond the top of the stack.
 uintptr_t* end() { return ptr(topIndex_); }

 // Grow the stack, ensuring there is space to push |count| more words.
 [[nodiscard]] bool enlarge(size_t count);

 [[nodiscard]] bool resize(size_t newCapacity);

 TaggedPtr peekPtr() const;

 [[nodiscard]] bool pushTaggedPtr(Tag tag, Cell* ptr);

 bool indexIsEntryBase(size_t index) const;

 // Area of memory containing the stack.
 MainThreadOrGCTaskData<uintptr_t*> stack_;

 // Size of the stack in words.
 MainThreadOrGCTaskData<size_t> capacity_;

 // Index of the top of the stack.
 MainThreadOrGCTaskData<size_t> topIndex_;

#ifdef JS_GC_ZEAL
 // The maximum stack capacity to grow to.
 MainThreadOrGCTaskData<size_t> maxCapacity_{SIZE_MAX};
#endif

#ifdef DEBUG
 MainThreadOrGCTaskData<bool> elementsRangesAreValid;
 friend class js::GCMarker;
#endif

 friend class MarkStackIter;
};

static_assert(unsigned(SlotsOrElementsKind::Unused) ==
                 unsigned(MarkStack::SlotsOrElementsRangeTag),
             "To split the mark stack we depend on being able to tell the "
             "difference between SlotsOrElementsRange::startAndKind_ and a "
             "tagged SlotsOrElementsRange");

class MOZ_STACK_CLASS MarkStackIter {
 MarkStack& stack_;
 size_t pos_;

public:
 explicit MarkStackIter(MarkStack& stack);

 bool done() const;
 void next();

 MarkStack::Tag peekTag() const;
 MarkStack::TaggedPtr peekPtr() const;
 bool isSlotsOrElementsRange() const;
 MarkStack::SlotsOrElementsRange slotsOrElementsRange() const;
 void setSlotsOrElementsRange(const MarkStack::SlotsOrElementsRange& range);

private:
 size_t position() const;
};

// Bitmask of options to parameterize MarkingTracerT.
namespace MarkingOptions {
enum : uint32_t {
 None = 0,

 // Set the compartment's hasMarkedCells flag for roots.
 MarkRootCompartments = 1,

 // The marking tracer is operating in parallel. Use appropriate atomic
 // accesses to update the mark bits correctly.
 ParallelMarking = 2,

 // Mark any implicit edges if we are in weak marking mode.
 MarkImplicitEdges = 4,
};
}  // namespace MarkingOptions

// A default set of marking options that works during normal marking and weak
// marking modes. Used for barriers and testing code.
constexpr uint32_t NormalMarkingOptions = MarkingOptions::MarkImplicitEdges;

template <uint32_t markingOptions>
class MarkingTracerT
   : public GenericTracerImpl<MarkingTracerT<markingOptions>> {
public:
 MarkingTracerT(JSRuntime* runtime, GCMarker* marker);
 virtual ~MarkingTracerT() = default;

 template <typename T>
 void onEdge(T** thingp, const char* name);
 friend class GenericTracerImpl<MarkingTracerT<markingOptions>>;

 GCMarker* getMarker();
};

using MarkingTracer = MarkingTracerT<MarkingOptions::None>;
using RootMarkingTracer = MarkingTracerT<MarkingOptions::MarkRootCompartments>;
using WeakMarkingTracer = MarkingTracerT<MarkingOptions::MarkImplicitEdges>;
using ParallelMarkingTracer = MarkingTracerT<MarkingOptions::ParallelMarking>;

enum ShouldReportMarkTime : bool {
 ReportMarkTime = true,
 DontReportMarkTime = false
};

} /* namespace gc */

class GCMarker {
 enum MarkingState : uint8_t {
   // Have not yet started marking.
   NotActive,

   // Root marking mode. This sets the hasMarkedCells flag on compartments
   // containing objects and scripts, which is used to make sure we clean up
   // dead compartments.
   RootMarking,

   // Main marking mode. Weakmap marking will be populating the
   // gcEphemeronEdges tables but not consulting them. The state will
   // transition to WeakMarking until it is done, then back to RegularMarking.
   RegularMarking,

   // Like RegularMarking but with multiple threads running in parallel.
   ParallelMarking,

   // Same as RegularMarking except now every marked obj/script is immediately
   // looked up in the gcEphemeronEdges table to find edges generated by
   // weakmap keys, and traversing them to their values. Transitions back to
   // RegularMarking when done.
   WeakMarking,
 };

public:
 explicit GCMarker(JSRuntime* rt);
 [[nodiscard]] bool init();

 JSRuntime* runtime() { return runtime_; }
 JSTracer* tracer() {
   return tracer_.match([](auto& t) -> JSTracer* { return &t; });
 }

#ifdef JS_GC_ZEAL
 void setMaxCapacity(size_t maxCap) { stack.setMaxCapacity(maxCap); }
#endif

 bool isActive() const { return state != NotActive; }
 bool isRegularMarking() const { return state == RegularMarking; }
 bool isParallelMarking() const { return state == ParallelMarking; }
 bool isWeakMarking() const { return state == WeakMarking; }

 gc::MarkColor markColor() const { return markColor_; }

 bool isDrained() const { return stack.isEmpty() && otherStack.isEmpty(); }

 bool hasEntriesForCurrentColor() { return stack.hasEntries(); }
 bool hasBlackEntries() const { return hasEntries(gc::MarkColor::Black); }
 bool hasGrayEntries() const { return hasEntries(gc::MarkColor::Gray); }
 bool hasEntries(gc::MarkColor color) const;

 bool canDonateWork() const;
 bool shouldDonateWork() const;

 void start();
 void stop();
 void reset();

 [[nodiscard]] bool markUntilBudgetExhausted(
     JS::SliceBudget& budget,
     gc::ShouldReportMarkTime reportTime = gc::ReportMarkTime);

 void setRootMarkingMode(bool newState);

 bool enterWeakMarkingMode();
 void leaveWeakMarkingMode();

 void enterParallelMarkingMode();
 void leaveParallelMarkingMode();

 // Do not use linear-time weak marking for the rest of this collection.
 // Currently, this will only be triggered by an OOM when updating needed data
 // structures.
 void abortLinearWeakMarking();

#ifdef DEBUG
 // We can't check atom marking if the helper thread lock is already held by
 // the current thread. This allows us to disable the check.
 void setCheckAtomMarking(bool check);

 bool shouldCheckCompartments() { return strictCompartmentChecking; }

 bool markOneObjectForTest(JSObject* obj);
#endif

 bool markCurrentColorInParallel(gc::ParallelMarkTask* task,
                                 JS::SliceBudget& budget);

 template <uint32_t markingOptions, gc::MarkColor>
 bool markOneColor(JS::SliceBudget& budget);

 static size_t moveWork(GCMarker* dst, GCMarker* src, bool allowDistribute);

 [[nodiscard]] bool initStack();
 void resetStackCapacity();
 void freeStack();

 size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const;

 static GCMarker* fromTracer(JSTracer* trc) {
   MOZ_ASSERT(trc->isMarkingTracer());
   auto* marker = reinterpret_cast<GCMarker*>(uintptr_t(trc) -
                                              offsetof(GCMarker, tracer_));
   MOZ_ASSERT(marker->tracer() == trc);
   return marker;
 }

 // Internal public methods, for ease of use by the rest of the GC:

 // If |thing| is unmarked, mark it and then traverse its children.
 template <uint32_t, typename T>
 void markAndTraverse(T* thing);

 template <typename T>
 void markImplicitEdges(T* markedThing);

private:
 /*
  * Care must be taken changing the mark color from gray to black. The cycle
  * collector depends on the invariant that there are no black to gray edges
  * in the GC heap. This invariant lets the CC not trace through black
  * objects. If this invariant is violated, the cycle collector may free
  * objects that are still reachable.
  */
 void setMarkColor(gc::MarkColor newColor);
 friend class js::gc::AutoSetMarkColor;

 template <typename Tracer>
 void setMarkingStateAndTracer(MarkingState prev, MarkingState next);

 // The mutator can shift object elements which could invalidate any elements
 // index on the mark stack. Change the index to be relative to the elements
 // allocation (to ignore shifted elements) while the mutator is running.
 void updateRangesAtStartOfSlice();
 void updateRangesAtEndOfSlice();
 friend class gc::AutoUpdateMarkStackRanges;

 template <uint32_t markingOptions>
 bool processMarkStackTop(JS::SliceBudget& budget);
 friend class gc::GCRuntime;

 // Helper methods that coerce their second argument to the base pointer
 // type.
 template <uint32_t markingOptions, typename S>
 void markAndTraverseObjectEdge(S source, JSObject* target) {
   markAndTraverseEdge<markingOptions>(source, target);
 }
 template <uint32_t markingOptions, typename S>
 void markAndTraverseStringEdge(S source, JSString* target) {
   markAndTraverseEdge<markingOptions>(source, target);
 }

 template <uint32_t markingOptions, typename S, typename T>
 void markAndTraverseEdge(S* source, T* target);
 template <uint32_t markingOptions, typename S, typename T>
 void markAndTraverseEdge(S* source, const T& target);

 template <uint32_t markingOptions>
 bool markAndTraversePrivateGCThing(JSObject* source, gc::Cell* target);

 template <uint32_t markingOptions>
 bool markAndTraverseSymbol(JSObject* source, JS::Symbol* target);

 template <typename S, typename T>
 void checkTraversedEdge(S source, T* target);

 // Mark the given GC thing, but do not trace its children. Return true
 // if the thing became marked.
 template <uint32_t markingOptions, typename T>
 [[nodiscard]] bool mark(T* thing);

 // Traverse a GC thing's children, using a strategy depending on the type.
 // This can either processing them immediately or push them onto the mark
 // stack for later.
#define DEFINE_TRAVERSE_METHOD(_1, Type, _2, _3) \
 template <uint32_t>                            \
 void traverse(Type* thing);
 JS_FOR_EACH_TRACEKIND(DEFINE_TRAVERSE_METHOD)
#undef DEFINE_TRAVERSE_METHOD

 // Process a marked thing's children by calling T::traceChildren().
 template <uint32_t markingOptions, typename T>
 void traceChildren(T* thing);

 // Process a marked thing's children recursively using an iterative loop and
 // manual dispatch, for kinds where this is possible.
 template <uint32_t markingOptions, typename T>
 void scanChildren(T* thing);

 // Push a marked thing onto the mark stack. Its children will be marked later.
 template <uint32_t markingOptions, typename T>
 void pushThing(T* thing);

 template <uint32_t markingOptions>
 void eagerlyMarkChildren(JSLinearString* str);
 template <uint32_t markingOptions>
 void eagerlyMarkChildren(JSRope* rope);
 template <uint32_t markingOptions>
 void eagerlyMarkChildren(JSString* str);
 template <uint32_t markingOptions>
 void eagerlyMarkChildren(Shape* shape);
 template <uint32_t markingOptions>
 void eagerlyMarkChildren(PropMap* map);
 template <uint32_t markingOptions>
 void eagerlyMarkChildren(Scope* scope);

 template <typename T>
 inline void pushTaggedPtr(T* ptr);

 inline void pushValueRange(JSObject* obj, SlotsOrElementsKind kind,
                            size_t start, size_t end);

 // Mark through edges whose target color depends on the colors of two source
 // entities (eg a WeakMap and one of its keys), and push the target onto the
 // mark stack.
 void markEphemeronEdges(gc::EphemeronEdgeVector& edges,
                         gc::MarkColor srcColor);
 friend class JS::Zone;

#ifdef DEBUG
 void checkZone(gc::Cell* cell);
#else
 void checkZone(gc::Cell* cell) {}
#endif

 template <uint32_t markingOptions>
 bool doMarking(JS::SliceBudget& budget, gc::ShouldReportMarkTime reportTime);

 void delayMarkingChildrenOnOOM(gc::Cell* cell);

 /*
  * The JSTracer used for marking. This can change depending on the current
  * state.
  */
 mozilla::Variant<gc::MarkingTracer, gc::RootMarkingTracer,
                  gc::WeakMarkingTracer, gc::ParallelMarkingTracer>
     tracer_;

 JSRuntime* const runtime_;

 // The main mark stack, holding entries of color |markColor_|.
 gc::MarkStack stack;

 // The auxiliary mark stack, which may contain entries of the other color.
 gc::MarkStack otherStack;

 // Track whether we're using the main or auxiliary stack.
 MainThreadOrGCTaskData<bool> haveSwappedStacks;

 // The current mark stack color.
 MainThreadOrGCTaskData<gc::MarkColor> markColor_;

 Vector<JS::GCCellPtr, 0, SystemAllocPolicy> unmarkGrayStack;
 friend class gc::UnmarkGrayTracer;

 /* Track the state of marking. */
 MainThreadOrGCTaskData<MarkingState> state;

 /* Whether we successfully added all edges to the implicit edges table. */
 MainThreadOrGCTaskData<bool> haveAllImplicitEdges;

public:
 /*
  * Whether weakmaps can be marked incrementally.
  *
  * JSGC_INCREMENTAL_WEAKMAP_ENABLED
  * pref: javascript.options.mem.incremental_weakmap
  */
 MainThreadOrGCTaskData<bool> incrementalWeakMapMarkingEnabled;

 /* Random number generator state. */
 MainThreadOrGCTaskData<mozilla::non_crypto::XorShift128PlusRNG> random;

#ifdef DEBUG
private:
 /* Assert that start and stop are called with correct ordering. */
 MainThreadOrGCTaskData<bool> started;

 /*
  * Whether to check that atoms traversed are present in atom marking
  * bitmap.
  */
 MainThreadOrGCTaskData<bool> checkAtomMarking;

 /*
  * If this is true, all marked objects must belong to a compartment being
  * GCed. This is used to look for compartment bugs.
  */
 MainThreadOrGCTaskData<bool> strictCompartmentChecking;

public:
 /*
  * The compartment and zone of the object whose trace hook is currently being
  * called, if any. Used to catch cross-compartment edges traced without use of
  * TraceCrossCompartmentEdge.
  */
 MainThreadOrGCTaskData<Compartment*> tracingCompartment;
 MainThreadOrGCTaskData<Zone*> tracingZone;
#endif  // DEBUG
};

namespace gc {

/*
* Temporarily change the mark color while this class is on the stack.
*
* During incremental sweeping this also transitions zones in the
* current sweep group into the Mark or MarkGray state as appropriate.
*/
class MOZ_RAII AutoSetMarkColor {
 GCMarker& marker_;
 MarkColor initialColor_;

public:
 AutoSetMarkColor(GCMarker& marker, MarkColor newColor)
     : marker_(marker), initialColor_(marker.markColor()) {
   marker_.setMarkColor(newColor);
 }

 AutoSetMarkColor(GCMarker& marker, CellColor newColor)
     : AutoSetMarkColor(marker, AsMarkColor(newColor)) {}

 ~AutoSetMarkColor() { marker_.setMarkColor(initialColor_); }
};

} /* namespace gc */

} /* namespace js */

#endif /* gc_GCMarker_h */