Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
#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, Cell* cell)
: taggedTarget(uintptr_t(cell) | uintptr_t(color)) {
MOZ_ASSERT((uintptr_t(cell) & ColorMask) == 0);
}
MarkColor color() const { return MarkColor(taggedTarget & ColorMask); }
Cell* target() const {
return reinterpret_cast<Cell*>(taggedTarget & ~ColorMask);
}
};
using EphemeronEdgeVector = Vector<EphemeronEdge, 2, js::SystemAllocPolicy>;
using EphemeronEdgeTable = HashMap<Cell*, EphemeronEdgeVector,
PointerHasher<Cell*>, 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 */