diff options
Diffstat (limited to 'js/src/gc/Marking.cpp')
| -rw-r--r-- | js/src/gc/Marking.cpp | 3019 |
1 files changed, 3019 insertions, 0 deletions
diff --git a/js/src/gc/Marking.cpp b/js/src/gc/Marking.cpp new file mode 100644 index 000000000..d9235f9ac --- /dev/null +++ b/js/src/gc/Marking.cpp @@ -0,0 +1,3019 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * 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/. */ + +#include "gc/Marking.h" + +#include "mozilla/DebugOnly.h" +#include "mozilla/IntegerRange.h" +#include "mozilla/ReentrancyGuard.h" +#include "mozilla/ScopeExit.h" +#include "mozilla/TypeTraits.h" + +#include "jsgc.h" +#include "jsprf.h" + +#include "builtin/ModuleObject.h" +#include "gc/GCInternals.h" +#include "gc/Policy.h" +#include "jit/IonCode.h" +#include "js/SliceBudget.h" +#include "vm/ArgumentsObject.h" +#include "vm/ArrayObject.h" +#include "vm/Debugger.h" +#include "vm/EnvironmentObject.h" +#include "vm/Scope.h" +#include "vm/Shape.h" +#include "vm/Symbol.h" +#include "vm/TypedArrayObject.h" +#include "vm/UnboxedObject.h" +#include "wasm/WasmJS.h" + +#include "jscompartmentinlines.h" +#include "jsgcinlines.h" +#include "jsobjinlines.h" + +#include "gc/Nursery-inl.h" +#include "vm/String-inl.h" +#include "vm/UnboxedObject-inl.h" + +using namespace js; +using namespace js::gc; + +using JS::MapTypeToTraceKind; + +using mozilla::ArrayLength; +using mozilla::DebugOnly; +using mozilla::IsBaseOf; +using mozilla::IsSame; +using mozilla::MakeRange; +using mozilla::PodCopy; + +// Tracing Overview +// ================ +// +// Tracing, in this context, refers to an abstract visitation of some or all of +// the GC-controlled heap. The effect of tracing an edge of the graph depends +// on the subclass of the JSTracer on whose behalf we are tracing. +// +// Marking +// ------- +// +// The primary JSTracer is the GCMarker. The marking tracer causes the target +// of each traversed edge to be marked black and the target edge's children to +// be marked either gray (in the gc algorithm sense) or immediately black. +// +// Callback +// -------- +// +// The secondary JSTracer is the CallbackTracer. This simply invokes a callback +// on each edge in a child. +// +// The following is a rough outline of the general struture of the tracing +// internals. +// +// // +// .---------. .---------. .--------------------------. .----------. // +// |TraceEdge| |TraceRoot| |TraceManuallyBarrieredEdge| ... |TraceRange| ... etc. // +// '---------' '---------' '--------------------------' '----------' // +// \ \ / / // +// \ \ .----------------. / / // +// o------------->o-|DispatchToTracer|-o<-----------------------o // +// '----------------' // +// / \ // +// / \ // +// .---------. .----------. .-----------------. // +// |DoMarking| |DoCallback|-------> |<JSTraceCallback>|-----------> // +// '---------' '----------' '-----------------' // +// | // +// | // +// .--------. // +// o---------------->|traverse| . // +// /_\ '--------' ' . // +// | . . ' . // +// | . . ' . // +// | . . ' . // +// | .-----------. .-----------. ' . .--------------------. // +// | |markAndScan| |markAndPush| ' - |markAndTraceChildren|----> // +// | '-----------' '-----------' '--------------------' // +// | | \ // +// | | \ // +// | .----------------------. .----------------. // +// | |T::eagerlyMarkChildren| |pushMarkStackTop|<===Oo // +// | '----------------------' '----------------' || // +// | | || || // +// | | || || // +// | | || || // +// o<-----------------o<========================OO============Oo // +// // +// // +// Legend: // +// ------ Direct calls // +// . . . Static dispatch // +// ====== Dispatch through a manual stack. // +// // + + +/*** Tracing Invariants **************************************************************************/ + +#if defined(DEBUG) +template<typename T> +static inline bool +IsThingPoisoned(T* thing) +{ + const uint8_t poisonBytes[] = { + JS_FRESH_NURSERY_PATTERN, + JS_SWEPT_NURSERY_PATTERN, + JS_ALLOCATED_NURSERY_PATTERN, + JS_FRESH_TENURED_PATTERN, + JS_MOVED_TENURED_PATTERN, + JS_SWEPT_TENURED_PATTERN, + JS_ALLOCATED_TENURED_PATTERN, + JS_SWEPT_CODE_PATTERN + }; + const int numPoisonBytes = sizeof(poisonBytes) / sizeof(poisonBytes[0]); + uint32_t* p = reinterpret_cast<uint32_t*>(reinterpret_cast<FreeSpan*>(thing) + 1); + // Note: all free patterns are odd to make the common, not-poisoned case a single test. + if ((*p & 1) == 0) + return false; + for (int i = 0; i < numPoisonBytes; ++i) { + const uint8_t pb = poisonBytes[i]; + const uint32_t pw = pb | (pb << 8) | (pb << 16) | (pb << 24); + if (*p == pw) + return true; + } + return false; +} + +static bool +IsMovingTracer(JSTracer *trc) +{ + return trc->isCallbackTracer() && + trc->asCallbackTracer()->getTracerKind() == JS::CallbackTracer::TracerKind::Moving; +} +#endif + +template <typename T> bool ThingIsPermanentAtomOrWellKnownSymbol(T* thing) { return false; } +template <> bool ThingIsPermanentAtomOrWellKnownSymbol<JSString>(JSString* str) { + return str->isPermanentAtom(); +} +template <> bool ThingIsPermanentAtomOrWellKnownSymbol<JSFlatString>(JSFlatString* str) { + return str->isPermanentAtom(); +} +template <> bool ThingIsPermanentAtomOrWellKnownSymbol<JSLinearString>(JSLinearString* str) { + return str->isPermanentAtom(); +} +template <> bool ThingIsPermanentAtomOrWellKnownSymbol<JSAtom>(JSAtom* atom) { + return atom->isPermanent(); +} +template <> bool ThingIsPermanentAtomOrWellKnownSymbol<PropertyName>(PropertyName* name) { + return name->isPermanent(); +} +template <> bool ThingIsPermanentAtomOrWellKnownSymbol<JS::Symbol>(JS::Symbol* sym) { + return sym->isWellKnownSymbol(); +} + +template <typename T> +static inline bool +IsOwnedByOtherRuntime(JSRuntime* rt, T thing) +{ + bool other = thing->runtimeFromAnyThread() != rt; + MOZ_ASSERT_IF(other, + ThingIsPermanentAtomOrWellKnownSymbol(thing) || + thing->zoneFromAnyThread()->isSelfHostingZone()); + return other; +} + +template<typename T> +void +js::CheckTracedThing(JSTracer* trc, T* thing) +{ +#ifdef DEBUG + MOZ_ASSERT(trc); + MOZ_ASSERT(thing); + + if (!trc->checkEdges()) + return; + + if (IsForwarded(thing)) + thing = Forwarded(thing); + + /* This function uses data that's not available in the nursery. */ + if (IsInsideNursery(thing)) + return; + + MOZ_ASSERT_IF(!IsMovingTracer(trc) && !trc->isTenuringTracer(), !IsForwarded(thing)); + + /* + * Permanent atoms and things in the self-hosting zone are not associated + * with this runtime, but will be ignored during marking. + */ + if (IsOwnedByOtherRuntime(trc->runtime(), thing)) + return; + + Zone* zone = thing->zoneFromAnyThread(); + JSRuntime* rt = trc->runtime(); + + MOZ_ASSERT_IF(!IsMovingTracer(trc), CurrentThreadCanAccessZone(zone)); + MOZ_ASSERT_IF(!IsMovingTracer(trc), CurrentThreadCanAccessRuntime(rt)); + + MOZ_ASSERT(zone->runtimeFromAnyThread() == trc->runtime()); + + MOZ_ASSERT(thing->isAligned()); + MOZ_ASSERT(MapTypeToTraceKind<typename mozilla::RemovePointer<T>::Type>::kind == + thing->getTraceKind()); + + /* + * Do not check IsMarkingTracer directly -- it should only be used in paths + * where we cannot be the gray buffering tracer. + */ + bool isGcMarkingTracer = trc->isMarkingTracer(); + + MOZ_ASSERT_IF(zone->requireGCTracer(), isGcMarkingTracer || IsBufferGrayRootsTracer(trc)); + + if (isGcMarkingTracer) { + GCMarker* gcMarker = static_cast<GCMarker*>(trc); + MOZ_ASSERT_IF(gcMarker->shouldCheckCompartments(), + zone->isCollecting() || zone->isAtomsZone()); + + MOZ_ASSERT_IF(gcMarker->markColor() == GRAY, + !zone->isGCMarkingBlack() || zone->isAtomsZone()); + + MOZ_ASSERT(!(zone->isGCSweeping() || zone->isGCFinished() || zone->isGCCompacting())); + } + + /* + * Try to assert that the thing is allocated. + * + * We would like to assert that the thing is not in the free list, but this + * check is very slow. Instead we check whether the thing has been poisoned: + * if it has not then we assume it is allocated, but if it has then it is + * either free or uninitialized in which case we check the free list. + * + * Further complications are that background sweeping may be running and + * concurrently modifiying the free list and that tracing is done off main + * thread during compacting GC and reading the contents of the thing by + * IsThingPoisoned would be racy in this case. + */ + MOZ_ASSERT_IF(rt->isHeapBusy() && !zone->isGCCompacting() && !rt->gc.isBackgroundSweeping(), + !IsThingPoisoned(thing) || !InFreeList(thing->asTenured().arena(), thing)); +#endif +} + +template <typename S> +struct CheckTracedFunctor : public VoidDefaultAdaptor<S> { + template <typename T> void operator()(T* t, JSTracer* trc) { CheckTracedThing(trc, t); } +}; + +template<typename T> +void +js::CheckTracedThing(JSTracer* trc, T thing) +{ + DispatchTyped(CheckTracedFunctor<T>(), thing, trc); +} + +namespace js { +#define IMPL_CHECK_TRACED_THING(_, type, __) \ + template void CheckTracedThing<type>(JSTracer*, type*); +JS_FOR_EACH_TRACEKIND(IMPL_CHECK_TRACED_THING); +#undef IMPL_CHECK_TRACED_THING +} // namespace js + +static bool +ShouldMarkCrossCompartment(JSTracer* trc, JSObject* src, Cell* cell) +{ + if (!trc->isMarkingTracer()) + return true; + + uint32_t color = static_cast<GCMarker*>(trc)->markColor(); + MOZ_ASSERT(color == BLACK || color == GRAY); + + if (!cell->isTenured()) { + MOZ_ASSERT(color == BLACK); + return false; + } + TenuredCell& tenured = cell->asTenured(); + + JS::Zone* zone = tenured.zone(); + if (color == BLACK) { + /* + * Having black->gray edges violates our promise to the cycle + * collector. This can happen if we're collecting a compartment and it + * has an edge to an uncollected compartment: it's possible that the + * source and destination of the cross-compartment edge should be gray, + * but the source was marked black by the conservative scanner. + */ + if (tenured.isMarked(GRAY)) { + MOZ_ASSERT(!zone->isCollecting()); + trc->runtime()->gc.setFoundBlackGrayEdges(tenured); + } + return zone->isGCMarking(); + } else { + if (zone->isGCMarkingBlack()) { + /* + * The destination compartment is being not being marked gray now, + * but it will be later, so record the cell so it can be marked gray + * at the appropriate time. + */ + if (!tenured.isMarked()) + DelayCrossCompartmentGrayMarking(src); + return false; + } + return zone->isGCMarkingGray(); + } +} + +static bool +ShouldMarkCrossCompartment(JSTracer* trc, JSObject* src, const Value& val) +{ + return val.isMarkable() && ShouldMarkCrossCompartment(trc, src, (Cell*)val.toGCThing()); +} + +static void +AssertZoneIsMarking(Cell* thing) +{ + MOZ_ASSERT(TenuredCell::fromPointer(thing)->zone()->isGCMarking()); +} + +static void +AssertZoneIsMarking(JSString* str) +{ +#ifdef DEBUG + Zone* zone = TenuredCell::fromPointer(str)->zone(); + MOZ_ASSERT(zone->isGCMarking() || zone->isAtomsZone()); +#endif +} + +static void +AssertZoneIsMarking(JS::Symbol* sym) +{ +#ifdef DEBUG + Zone* zone = TenuredCell::fromPointer(sym)->zone(); + MOZ_ASSERT(zone->isGCMarking() || zone->isAtomsZone()); +#endif +} + +static void +AssertRootMarkingPhase(JSTracer* trc) +{ + MOZ_ASSERT_IF(trc->isMarkingTracer(), + trc->runtime()->gc.state() == State::NotActive || + trc->runtime()->gc.state() == State::MarkRoots); +} + + +/*** Tracing Interface ***************************************************************************/ + +// The second parameter to BaseGCType is derived automatically based on T. The +// relation here is that for any T, the TraceKind will automatically, +// statically select the correct Cell layout for marking. Below, we instantiate +// each override with a declaration of the most derived layout type. +// +// The use of TraceKind::Null for the case where the type is not matched +// generates a compile error as no template instantiated for that kind. +// +// Usage: +// BaseGCType<T>::type +// +// Examples: +// BaseGCType<JSFunction>::type => JSObject +// BaseGCType<UnownedBaseShape>::type => BaseShape +// etc. +template <typename T, JS::TraceKind = +#define EXPAND_MATCH_TYPE(name, type, _) \ + IsBaseOf<type, T>::value ? JS::TraceKind::name : +JS_FOR_EACH_TRACEKIND(EXPAND_MATCH_TYPE) +#undef EXPAND_MATCH_TYPE + JS::TraceKind::Null> + +struct BaseGCType; +#define IMPL_BASE_GC_TYPE(name, type_, _) \ + template <typename T> struct BaseGCType<T, JS::TraceKind:: name> { typedef type_ type; }; +JS_FOR_EACH_TRACEKIND(IMPL_BASE_GC_TYPE); +#undef IMPL_BASE_GC_TYPE + +// Our barrier templates are parameterized on the pointer types so that we can +// share the definitions with Value and jsid. Thus, we need to strip the +// pointer before sending the type to BaseGCType and re-add it on the other +// side. As such: +template <typename T> struct PtrBaseGCType { typedef T type; }; +template <typename T> struct PtrBaseGCType<T*> { typedef typename BaseGCType<T>::type* type; }; + +template <typename T> +typename PtrBaseGCType<T>::type* +ConvertToBase(T* thingp) +{ + return reinterpret_cast<typename PtrBaseGCType<T>::type*>(thingp); +} + +template <typename T> void DispatchToTracer(JSTracer* trc, T* thingp, const char* name); +template <typename T> T DoCallback(JS::CallbackTracer* trc, T* thingp, const char* name); +template <typename T> void DoMarking(GCMarker* gcmarker, T* thing); +template <typename T> void DoMarking(GCMarker* gcmarker, const T& thing); +template <typename T> void NoteWeakEdge(GCMarker* gcmarker, T** thingp); +template <typename T> void NoteWeakEdge(GCMarker* gcmarker, T* thingp); + +template <typename T> +void +js::TraceEdge(JSTracer* trc, WriteBarrieredBase<T>* thingp, const char* name) +{ + DispatchToTracer(trc, ConvertToBase(thingp->unsafeUnbarrieredForTracing()), name); +} + +template <typename T> +void +js::TraceEdge(JSTracer* trc, ReadBarriered<T>* thingp, const char* name) +{ + DispatchToTracer(trc, ConvertToBase(thingp->unsafeGet()), name); +} + +template <typename T> +void +js::TraceNullableEdge(JSTracer* trc, WriteBarrieredBase<T>* thingp, const char* name) +{ + if (InternalBarrierMethods<T>::isMarkable(thingp->get())) + DispatchToTracer(trc, ConvertToBase(thingp->unsafeUnbarrieredForTracing()), name); +} + +template <typename T> +JS_PUBLIC_API(void) +JS::TraceEdge(JSTracer* trc, JS::Heap<T>* thingp, const char* name) +{ + MOZ_ASSERT(thingp); + if (InternalBarrierMethods<T>::isMarkable(*thingp->unsafeGet())) + DispatchToTracer(trc, ConvertToBase(thingp->unsafeGet()), name); +} + +JS_PUBLIC_API(void) +JS::TraceEdge(JSTracer* trc, JS::TenuredHeap<JSObject*>* thingp, const char* name) +{ + MOZ_ASSERT(thingp); + if (JSObject* ptr = thingp->unbarrieredGetPtr()) { + DispatchToTracer(trc, &ptr, name); + thingp->setPtr(ptr); + } +} + +template <typename T> +void +js::TraceManuallyBarrieredEdge(JSTracer* trc, T* thingp, const char* name) +{ + DispatchToTracer(trc, ConvertToBase(thingp), name); +} + +template <typename T> +JS_PUBLIC_API(void) +js::UnsafeTraceManuallyBarrieredEdge(JSTracer* trc, T* thingp, const char* name) +{ + DispatchToTracer(trc, ConvertToBase(thingp), name); +} + +template <typename T> +void +js::TraceWeakEdge(JSTracer* trc, WeakRef<T>* thingp, const char* name) +{ + // Non-marking tracers treat the edge strongly. + if (!trc->isMarkingTracer()) + return DispatchToTracer(trc, ConvertToBase(thingp->unsafeUnbarrieredForTracing()), name); + + NoteWeakEdge(static_cast<GCMarker*>(trc), + ConvertToBase(thingp->unsafeUnbarrieredForTracing())); +} + +template <typename T> +void +js::TraceRoot(JSTracer* trc, T* thingp, const char* name) +{ + AssertRootMarkingPhase(trc); + DispatchToTracer(trc, ConvertToBase(thingp), name); +} + +template <typename T> +void +js::TraceRoot(JSTracer* trc, ReadBarriered<T>* thingp, const char* name) +{ + TraceRoot(trc, thingp->unsafeGet(), name); +} + +template <typename T> +void +js::TraceNullableRoot(JSTracer* trc, T* thingp, const char* name) +{ + AssertRootMarkingPhase(trc); + if (InternalBarrierMethods<T>::isMarkableTaggedPointer(*thingp)) + DispatchToTracer(trc, ConvertToBase(thingp), name); +} + +template <typename T> +void +js::TraceNullableRoot(JSTracer* trc, ReadBarriered<T>* thingp, const char* name) +{ + TraceNullableRoot(trc, thingp->unsafeGet(), name); +} + +template <typename T> +JS_PUBLIC_API(void) +JS::UnsafeTraceRoot(JSTracer* trc, T* thingp, const char* name) +{ + MOZ_ASSERT(thingp); + js::TraceNullableRoot(trc, thingp, name); +} + +template <typename T> +void +js::TraceRange(JSTracer* trc, size_t len, WriteBarrieredBase<T>* vec, const char* name) +{ + JS::AutoTracingIndex index(trc); + for (auto i : MakeRange(len)) { + if (InternalBarrierMethods<T>::isMarkable(vec[i].get())) + DispatchToTracer(trc, ConvertToBase(vec[i].unsafeUnbarrieredForTracing()), name); + ++index; + } +} + +template <typename T> +void +js::TraceRootRange(JSTracer* trc, size_t len, T* vec, const char* name) +{ + AssertRootMarkingPhase(trc); + JS::AutoTracingIndex index(trc); + for (auto i : MakeRange(len)) { + if (InternalBarrierMethods<T>::isMarkable(vec[i])) + DispatchToTracer(trc, ConvertToBase(&vec[i]), name); + ++index; + } +} + +// Instantiate a copy of the Tracing templates for each derived type. +#define INSTANTIATE_ALL_VALID_TRACE_FUNCTIONS(type) \ + template void js::TraceEdge<type>(JSTracer*, WriteBarrieredBase<type>*, const char*); \ + template void js::TraceEdge<type>(JSTracer*, ReadBarriered<type>*, const char*); \ + template void js::TraceNullableEdge<type>(JSTracer*, WriteBarrieredBase<type>*, const char*); \ + template void js::TraceManuallyBarrieredEdge<type>(JSTracer*, type*, const char*); \ + template void js::TraceWeakEdge<type>(JSTracer*, WeakRef<type>*, const char*); \ + template void js::TraceRoot<type>(JSTracer*, type*, const char*); \ + template void js::TraceRoot<type>(JSTracer*, ReadBarriered<type>*, const char*); \ + template void js::TraceNullableRoot<type>(JSTracer*, type*, const char*); \ + template void js::TraceNullableRoot<type>(JSTracer*, ReadBarriered<type>*, const char*); \ + template void js::TraceRange<type>(JSTracer*, size_t, WriteBarrieredBase<type>*, const char*); \ + template void js::TraceRootRange<type>(JSTracer*, size_t, type*, const char*); +FOR_EACH_GC_POINTER_TYPE(INSTANTIATE_ALL_VALID_TRACE_FUNCTIONS) +#undef INSTANTIATE_ALL_VALID_TRACE_FUNCTIONS + +#define INSTANTIATE_PUBLIC_TRACE_FUNCTIONS(type) \ + template JS_PUBLIC_API(void) JS::TraceEdge<type>(JSTracer*, JS::Heap<type>*, const char*); \ + template JS_PUBLIC_API(void) JS::UnsafeTraceRoot<type>(JSTracer*, type*, const char*); \ + template JS_PUBLIC_API(void) js::UnsafeTraceManuallyBarrieredEdge<type>(JSTracer*, type*, \ + const char*); +FOR_EACH_PUBLIC_GC_POINTER_TYPE(INSTANTIATE_PUBLIC_TRACE_FUNCTIONS) +FOR_EACH_PUBLIC_TAGGED_GC_POINTER_TYPE(INSTANTIATE_PUBLIC_TRACE_FUNCTIONS) +#undef INSTANTIATE_PUBLIC_TRACE_FUNCTIONS + +template <typename T> +void +js::TraceManuallyBarrieredCrossCompartmentEdge(JSTracer* trc, JSObject* src, T* dst, + const char* name) +{ + if (ShouldMarkCrossCompartment(trc, src, *dst)) + DispatchToTracer(trc, dst, name); +} +template void js::TraceManuallyBarrieredCrossCompartmentEdge<JSObject*>(JSTracer*, JSObject*, + JSObject**, const char*); +template void js::TraceManuallyBarrieredCrossCompartmentEdge<JSScript*>(JSTracer*, JSObject*, + JSScript**, const char*); + +template <typename T> +void +js::TraceCrossCompartmentEdge(JSTracer* trc, JSObject* src, WriteBarrieredBase<T>* dst, + const char* name) +{ + if (ShouldMarkCrossCompartment(trc, src, dst->get())) + DispatchToTracer(trc, dst->unsafeUnbarrieredForTracing(), name); +} +template void js::TraceCrossCompartmentEdge<Value>(JSTracer*, JSObject*, + WriteBarrieredBase<Value>*, const char*); + +template <typename T> +void +js::TraceProcessGlobalRoot(JSTracer* trc, T* thing, const char* name) +{ + AssertRootMarkingPhase(trc); + MOZ_ASSERT(ThingIsPermanentAtomOrWellKnownSymbol(thing)); + + // We have to mark permanent atoms and well-known symbols through a special + // method because the default DoMarking implementation automatically skips + // them. Fortunately, atoms (permanent and non) cannot refer to other GC + // things so they do not need to go through the mark stack and may simply + // be marked directly. Moreover, well-known symbols can refer only to + // permanent atoms, so likewise require no subsquent marking. + CheckTracedThing(trc, *ConvertToBase(&thing)); + if (trc->isMarkingTracer()) + thing->markIfUnmarked(gc::BLACK); + else + DoCallback(trc->asCallbackTracer(), ConvertToBase(&thing), name); +} +template void js::TraceProcessGlobalRoot<JSAtom>(JSTracer*, JSAtom*, const char*); +template void js::TraceProcessGlobalRoot<JS::Symbol>(JSTracer*, JS::Symbol*, const char*); + +// A typed functor adaptor for TraceRoot. +struct TraceRootFunctor { + template <typename T> + void operator()(JSTracer* trc, Cell** thingp, const char* name) { + TraceRoot(trc, reinterpret_cast<T**>(thingp), name); + } +}; + +void +js::TraceGenericPointerRoot(JSTracer* trc, Cell** thingp, const char* name) +{ + MOZ_ASSERT(thingp); + if (!*thingp) + return; + TraceRootFunctor f; + DispatchTraceKindTyped(f, (*thingp)->getTraceKind(), trc, thingp, name); +} + +// A typed functor adaptor for TraceManuallyBarrieredEdge. +struct TraceManuallyBarrieredEdgeFunctor { + template <typename T> + void operator()(JSTracer* trc, Cell** thingp, const char* name) { + TraceManuallyBarrieredEdge(trc, reinterpret_cast<T**>(thingp), name); + } +}; + +void +js::TraceManuallyBarrieredGenericPointerEdge(JSTracer* trc, Cell** thingp, const char* name) +{ + MOZ_ASSERT(thingp); + if (!*thingp) + return; + TraceManuallyBarrieredEdgeFunctor f; + DispatchTraceKindTyped(f, (*thingp)->getTraceKind(), trc, thingp, name); +} + +// This method is responsible for dynamic dispatch to the real tracer +// implementation. Consider replacing this choke point with virtual dispatch: +// a sufficiently smart C++ compiler may be able to devirtualize some paths. +template <typename T> +void +DispatchToTracer(JSTracer* trc, T* thingp, const char* name) +{ +#define IS_SAME_TYPE_OR(name, type, _) mozilla::IsSame<type*, T>::value || + static_assert( + JS_FOR_EACH_TRACEKIND(IS_SAME_TYPE_OR) + mozilla::IsSame<T, JS::Value>::value || + mozilla::IsSame<T, jsid>::value || + mozilla::IsSame<T, TaggedProto>::value, + "Only the base cell layout types are allowed into marking/tracing internals"); +#undef IS_SAME_TYPE_OR + if (trc->isMarkingTracer()) + return DoMarking(static_cast<GCMarker*>(trc), *thingp); + if (trc->isTenuringTracer()) + return static_cast<TenuringTracer*>(trc)->traverse(thingp); + MOZ_ASSERT(trc->isCallbackTracer()); + DoCallback(trc->asCallbackTracer(), thingp, name); +} + + +/*** GC Marking Interface *************************************************************************/ + +namespace js { + +typedef bool HasNoImplicitEdgesType; + +template <typename T> +struct ImplicitEdgeHolderType { + typedef HasNoImplicitEdgesType Type; +}; + +// For now, we only handle JSObject* and JSScript* keys, but the linear time +// algorithm can be easily extended by adding in more types here, then making +// GCMarker::traverse<T> call markPotentialEphemeronKey. +template <> +struct ImplicitEdgeHolderType<JSObject*> { + typedef JSObject* Type; +}; + +template <> +struct ImplicitEdgeHolderType<JSScript*> { + typedef JSScript* Type; +}; + +void +GCMarker::markEphemeronValues(gc::Cell* markedCell, WeakEntryVector& values) +{ + size_t initialLen = values.length(); + for (size_t i = 0; i < initialLen; i++) + values[i].weakmap->traceEntry(this, markedCell, values[i].key); + + // The vector should not be appended to during iteration because the key is + // already marked, and even in cases where we have a multipart key, we + // should only be inserting entries for the unmarked portions. + MOZ_ASSERT(values.length() == initialLen); +} + +template <typename T> +void +GCMarker::markImplicitEdgesHelper(T markedThing) +{ + if (!isWeakMarkingTracer()) + return; + + Zone* zone = gc::TenuredCell::fromPointer(markedThing)->zone(); + MOZ_ASSERT(zone->isGCMarking()); + MOZ_ASSERT(!zone->isGCSweeping()); + + auto p = zone->gcWeakKeys.get(JS::GCCellPtr(markedThing)); + if (!p) + return; + WeakEntryVector& markables = p->value; + + markEphemeronValues(markedThing, markables); + markables.clear(); // If key address is reused, it should do nothing +} + +template <> +void +GCMarker::markImplicitEdgesHelper(HasNoImplicitEdgesType) +{ +} + +template <typename T> +void +GCMarker::markImplicitEdges(T* thing) +{ + markImplicitEdgesHelper<typename ImplicitEdgeHolderType<T*>::Type>(thing); +} + +} // namespace js + +template <typename T> +static inline bool +MustSkipMarking(GCMarker* gcmarker, T thing) +{ + // Don't trace things that are owned by another runtime. + if (IsOwnedByOtherRuntime(gcmarker->runtime(), thing)) + return true; + + // Don't mark things outside a zone if we are in a per-zone GC. + return !thing->zone()->isGCMarking(); +} + +template <> +bool +MustSkipMarking<JSObject*>(GCMarker* gcmarker, JSObject* obj) +{ + // Don't trace things that are owned by another runtime. + if (IsOwnedByOtherRuntime(gcmarker->runtime(), obj)) + return true; + + // We may mark a Nursery thing outside the context of the + // MinorCollectionTracer because of a pre-barrier. The pre-barrier is not + // needed in this case because we perform a minor collection before each + // incremental slice. + if (IsInsideNursery(obj)) + return true; + + // Don't mark things outside a zone if we are in a per-zone GC. It is + // faster to check our own arena, which we can do since we know that + // the object is tenured. + return !TenuredCell::fromPointer(obj)->zone()->isGCMarking(); +} + +template <typename T> +void +DoMarking(GCMarker* gcmarker, T* thing) +{ + // Do per-type marking precondition checks. + if (MustSkipMarking(gcmarker, thing)) + return; + + CheckTracedThing(gcmarker, thing); + gcmarker->traverse(thing); + + // Mark the compartment as live. + SetMaybeAliveFlag(thing); +} + +template <typename S> +struct DoMarkingFunctor : public VoidDefaultAdaptor<S> { + template <typename T> void operator()(T* t, GCMarker* gcmarker) { DoMarking(gcmarker, t); } +}; + +template <typename T> +void +DoMarking(GCMarker* gcmarker, const T& thing) +{ + DispatchTyped(DoMarkingFunctor<T>(), thing, gcmarker); +} + +template <typename T> +void +NoteWeakEdge(GCMarker* gcmarker, T** thingp) +{ + // Do per-type marking precondition checks. + if (MustSkipMarking(gcmarker, *thingp)) + return; + + CheckTracedThing(gcmarker, *thingp); + + // If the target is already marked, there's no need to store the edge. + if (IsMarkedUnbarriered(gcmarker->runtime(), thingp)) + return; + + gcmarker->noteWeakEdge(thingp); +} + +template <typename T> +void +NoteWeakEdge(GCMarker* gcmarker, T* thingp) +{ + MOZ_CRASH("the gc does not support tagged pointers as weak edges"); +} + +template <typename T> +void +js::GCMarker::noteWeakEdge(T* edge) +{ + static_assert(IsBaseOf<Cell, typename mozilla::RemovePointer<T>::Type>::value, + "edge must point to a GC pointer"); + MOZ_ASSERT((*edge)->isTenured()); + + // Note: we really want the *source* Zone here. The edge may start in a + // non-gc heap location, however, so we use the fact that cross-zone weak + // references are not allowed and use the *target's* zone. + JS::Zone::WeakEdges &weakRefs = (*edge)->asTenured().zone()->gcWeakRefs; + AutoEnterOOMUnsafeRegion oomUnsafe; + if (!weakRefs.append(reinterpret_cast<TenuredCell**>(edge))) + oomUnsafe.crash("Failed to record a weak edge for sweeping."); +} + +// The simplest traversal calls out to the fully generic traceChildren function +// to visit the child edges. In the absence of other traversal mechanisms, this +// function will rapidly grow the stack past its bounds and crash the process. +// Thus, this generic tracing should only be used in cases where subsequent +// tracing will not recurse. +template <typename T> +void +js::GCMarker::markAndTraceChildren(T* thing) +{ + if (ThingIsPermanentAtomOrWellKnownSymbol(thing)) + return; + if (mark(thing)) + thing->traceChildren(this); +} +namespace js { +template <> void GCMarker::traverse(BaseShape* thing) { markAndTraceChildren(thing); } +template <> void GCMarker::traverse(JS::Symbol* thing) { markAndTraceChildren(thing); } +} // namespace js + +// Strings, LazyScripts, Shapes, and Scopes are extremely common, but have +// simple patterns of recursion. We traverse trees of these edges immediately, +// with aggressive, manual inlining, implemented by eagerlyTraceChildren. +template <typename T> +void +js::GCMarker::markAndScan(T* thing) +{ + if (ThingIsPermanentAtomOrWellKnownSymbol(thing)) + return; + if (mark(thing)) + eagerlyMarkChildren(thing); +} +namespace js { +template <> void GCMarker::traverse(JSString* thing) { markAndScan(thing); } +template <> void GCMarker::traverse(LazyScript* thing) { markAndScan(thing); } +template <> void GCMarker::traverse(Shape* thing) { markAndScan(thing); } +template <> void GCMarker::traverse(js::Scope* thing) { markAndScan(thing); } +} // namespace js + +// Object and ObjectGroup are extremely common and can contain arbitrarily +// nested graphs, so are not trivially inlined. In this case we use a mark +// stack to control recursion. JitCode shares none of these properties, but is +// included for historical reasons. JSScript normally cannot recurse, but may +// be used as a weakmap key and thereby recurse into weakmapped values. +template <typename T> +void +js::GCMarker::markAndPush(StackTag tag, T* thing) +{ + if (!mark(thing)) + return; + pushTaggedPtr(tag, thing); + markImplicitEdges(thing); +} +namespace js { +template <> void GCMarker::traverse(JSObject* thing) { markAndPush(ObjectTag, thing); } +template <> void GCMarker::traverse(ObjectGroup* thing) { markAndPush(GroupTag, thing); } +template <> void GCMarker::traverse(jit::JitCode* thing) { markAndPush(JitCodeTag, thing); } +template <> void GCMarker::traverse(JSScript* thing) { markAndPush(ScriptTag, thing); } +} // namespace js + +namespace js { +template <> +void +GCMarker::traverse(AccessorShape* thing) { + MOZ_CRASH("AccessorShape must be marked as a Shape"); +} +} // namespace js + +template <typename S, typename T> +static void +CheckTraversedEdge(S source, T* target) +{ + // Atoms and Symbols do not have or mark their internal pointers, respectively. + MOZ_ASSERT(!ThingIsPermanentAtomOrWellKnownSymbol(source)); + + // The Zones must match, unless the target is an atom. + MOZ_ASSERT_IF(!ThingIsPermanentAtomOrWellKnownSymbol(target), + target->zone()->isAtomsZone() || target->zone() == source->zone()); + + // Atoms and Symbols do not have access to a compartment pointer, or we'd need + // to adjust the subsequent check to catch that case. + MOZ_ASSERT_IF(ThingIsPermanentAtomOrWellKnownSymbol(target), !target->maybeCompartment()); + MOZ_ASSERT_IF(target->zoneFromAnyThread()->isAtomsZone(), !target->maybeCompartment()); + // If we have access to a compartment pointer for both things, they must match. + MOZ_ASSERT_IF(source->maybeCompartment() && target->maybeCompartment(), + source->maybeCompartment() == target->maybeCompartment()); +} + +template <typename S, typename T> +void +js::GCMarker::traverseEdge(S source, T* target) +{ + CheckTraversedEdge(source, target); + traverse(target); +} + +template <typename V, typename S> struct TraverseEdgeFunctor : public VoidDefaultAdaptor<V> { + template <typename T> void operator()(T t, GCMarker* gcmarker, S s) { + return gcmarker->traverseEdge(s, t); + } +}; + +template <typename S, typename T> +void +js::GCMarker::traverseEdge(S source, const T& thing) +{ + DispatchTyped(TraverseEdgeFunctor<T, S>(), thing, this, source); +} + +template <typename T> +bool +js::GCMarker::mark(T* thing) +{ + AssertZoneIsMarking(thing); + MOZ_ASSERT(!IsInsideNursery(gc::TenuredCell::fromPointer(thing))); + return gc::ParticipatesInCC<T>::value + ? gc::TenuredCell::fromPointer(thing)->markIfUnmarked(markColor()) + : gc::TenuredCell::fromPointer(thing)->markIfUnmarked(gc::BLACK); +} + + +/*** Inline, Eager GC Marking *********************************************************************/ + +// Each of the eager, inline marking paths is directly preceeded by the +// out-of-line, generic tracing code for comparison. Both paths must end up +// traversing equivalent subgraphs. + +void +LazyScript::traceChildren(JSTracer* trc) +{ + if (script_) + TraceWeakEdge(trc, &script_, "script"); + + if (function_) + TraceEdge(trc, &function_, "function"); + + if (sourceObject_) + TraceEdge(trc, &sourceObject_, "sourceObject"); + + if (enclosingScope_) + TraceEdge(trc, &enclosingScope_, "enclosingScope"); + + // We rely on the fact that atoms are always tenured. + JSAtom** closedOverBindings = this->closedOverBindings(); + for (auto i : MakeRange(numClosedOverBindings())) { + if (closedOverBindings[i]) + TraceManuallyBarrieredEdge(trc, &closedOverBindings[i], "closedOverBinding"); + } + + GCPtrFunction* innerFunctions = this->innerFunctions(); + for (auto i : MakeRange(numInnerFunctions())) + TraceEdge(trc, &innerFunctions[i], "lazyScriptInnerFunction"); +} +inline void +js::GCMarker::eagerlyMarkChildren(LazyScript *thing) +{ + if (thing->script_) + noteWeakEdge(thing->script_.unsafeUnbarrieredForTracing()); + + if (thing->function_) + traverseEdge(thing, static_cast<JSObject*>(thing->function_)); + + if (thing->sourceObject_) + traverseEdge(thing, static_cast<JSObject*>(thing->sourceObject_)); + + if (thing->enclosingScope_) + traverseEdge(thing, static_cast<Scope*>(thing->enclosingScope_)); + + // We rely on the fact that atoms are always tenured. + JSAtom** closedOverBindings = thing->closedOverBindings(); + for (auto i : MakeRange(thing->numClosedOverBindings())) { + if (closedOverBindings[i]) + traverseEdge(thing, static_cast<JSString*>(closedOverBindings[i])); + } + + GCPtrFunction* innerFunctions = thing->innerFunctions(); + for (auto i : MakeRange(thing->numInnerFunctions())) + traverseEdge(thing, static_cast<JSObject*>(innerFunctions[i])); +} + +void +Shape::traceChildren(JSTracer* trc) +{ + TraceEdge(trc, &base_, "base"); + TraceEdge(trc, &propidRef(), "propid"); + if (parent) + TraceEdge(trc, &parent, "parent"); + + if (hasGetterObject()) + TraceManuallyBarrieredEdge(trc, &asAccessorShape().getterObj, "getter"); + if (hasSetterObject()) + TraceManuallyBarrieredEdge(trc, &asAccessorShape().setterObj, "setter"); +} +inline void +js::GCMarker::eagerlyMarkChildren(Shape* shape) +{ + MOZ_ASSERT(shape->isMarked(this->markColor())); + do { + // Special case: if a base shape has a shape table then all its pointers + // must point to this shape or an anscestor. Since these pointers will + // be traced by this loop they do not need to be traced here as well. + BaseShape* base = shape->base(); + CheckTraversedEdge(shape, base); + if (mark(base)) { + MOZ_ASSERT(base->canSkipMarkingShapeTable(shape)); + base->traceChildrenSkipShapeTable(this); + } + + traverseEdge(shape, shape->propidRef().get()); + + // When triggered between slices on belhalf of a barrier, these + // objects may reside in the nursery, so require an extra check. + // FIXME: Bug 1157967 - remove the isTenured checks. + if (shape->hasGetterObject() && shape->getterObject()->isTenured()) + traverseEdge(shape, shape->getterObject()); + if (shape->hasSetterObject() && shape->setterObject()->isTenured()) + traverseEdge(shape, shape->setterObject()); + + shape = shape->previous(); + } while (shape && mark(shape)); +} + +void +JSString::traceChildren(JSTracer* trc) +{ + if (hasBase()) + traceBase(trc); + else if (isRope()) + asRope().traceChildren(trc); +} +inline void +GCMarker::eagerlyMarkChildren(JSString* str) +{ + if (str->isLinear()) + eagerlyMarkChildren(&str->asLinear()); + else + eagerlyMarkChildren(&str->asRope()); +} + +void +JSString::traceBase(JSTracer* trc) +{ + MOZ_ASSERT(hasBase()); + TraceManuallyBarrieredEdge(trc, &d.s.u3.base, "base"); +} +inline void +js::GCMarker::eagerlyMarkChildren(JSLinearString* linearStr) +{ + AssertZoneIsMarking(linearStr); + MOZ_ASSERT(linearStr->isMarked()); + MOZ_ASSERT(linearStr->JSString::isLinear()); + + // Use iterative marking to avoid blowing out the stack. + while (linearStr->hasBase()) { + linearStr = linearStr->base(); + MOZ_ASSERT(linearStr->JSString::isLinear()); + if (linearStr->isPermanentAtom()) + break; + AssertZoneIsMarking(linearStr); + if (!mark(static_cast<JSString*>(linearStr))) + break; + } +} + +void +JSRope::traceChildren(JSTracer* trc) { + js::TraceManuallyBarrieredEdge(trc, &d.s.u2.left, "left child"); + js::TraceManuallyBarrieredEdge(trc, &d.s.u3.right, "right child"); +} +inline void +js::GCMarker::eagerlyMarkChildren(JSRope* rope) +{ + // This function tries to scan the whole rope tree using the marking stack + // as temporary storage. If that becomes full, the unscanned ropes are + // added to the delayed marking list. When the function returns, the + // marking stack is at the same depth as it was on entry. This way we avoid + // using tags when pushing ropes to the stack as ropes never leak to other + // users of the stack. This also assumes that a rope can only point to + // other ropes or linear strings, it cannot refer to GC things of other + // types. + ptrdiff_t savedPos = stack.position(); + JS_DIAGNOSTICS_ASSERT(rope->getTraceKind() == JS::TraceKind::String); +#ifdef JS_DEBUG + static const size_t DEEP_ROPE_THRESHOLD = 100000; + static const size_t ROPE_CYCLE_HISTORY = 100; + DebugOnly<size_t> ropeDepth = 0; + JSRope* history[ROPE_CYCLE_HISTORY]; +#endif + while (true) { +#ifdef JS_DEBUG + if (++ropeDepth >= DEEP_ROPE_THRESHOLD) { + // Bug 1011786 comment 294 - detect cyclic ropes. There are some + // legitimate deep ropes, at least in tests. So if we hit a deep + // rope, start recording the nodes we visit and check whether we + // repeat. But do it on a finite window size W so that we're not + // scanning the full history for every node. And only check every + // Wth push, to add only constant overhead per node. This will only + // catch cycles of size up to W (but it seems most likely that any + // cycles will be size 1 or maybe 2.) + if ((ropeDepth > DEEP_ROPE_THRESHOLD + ROPE_CYCLE_HISTORY) && + (ropeDepth % ROPE_CYCLE_HISTORY) == 0) + { + for (size_t i = 0; i < ROPE_CYCLE_HISTORY; i++) + MOZ_ASSERT(history[i] != rope, "cycle detected in rope"); + } + history[ropeDepth % ROPE_CYCLE_HISTORY] = rope; + } +#endif + + JS_DIAGNOSTICS_ASSERT(rope->getTraceKind() == JS::TraceKind::String); + JS_DIAGNOSTICS_ASSERT(rope->JSString::isRope()); + AssertZoneIsMarking(rope); + MOZ_ASSERT(rope->isMarked()); + JSRope* next = nullptr; + + JSString* right = rope->rightChild(); + if (!right->isPermanentAtom() && + mark(right)) + { + if (right->isLinear()) + eagerlyMarkChildren(&right->asLinear()); + else + next = &right->asRope(); + } + + JSString* left = rope->leftChild(); + if (!left->isPermanentAtom() && + mark(left)) + { + if (left->isLinear()) { + eagerlyMarkChildren(&left->asLinear()); + } else { + // When both children are ropes, set aside the right one to + // scan it later. + if (next && !stack.push(reinterpret_cast<uintptr_t>(next))) + delayMarkingChildren(next); + next = &left->asRope(); + } + } + if (next) { + rope = next; + } else if (savedPos != stack.position()) { + MOZ_ASSERT(savedPos < stack.position()); + rope = reinterpret_cast<JSRope*>(stack.pop()); + } else { + break; + } + } + MOZ_ASSERT(savedPos == stack.position()); +} + +static inline void +TraceBindingNames(JSTracer* trc, BindingName* names, uint32_t length) +{ + for (uint32_t i = 0; i < length; i++) { + JSAtom* name = names[i].name(); + MOZ_ASSERT(name); + TraceManuallyBarrieredEdge(trc, &name, "scope name"); + } +}; +static inline void +TraceNullableBindingNames(JSTracer* trc, BindingName* names, uint32_t length) +{ + for (uint32_t i = 0; i < length; i++) { + if (JSAtom* name = names[i].name()) + TraceManuallyBarrieredEdge(trc, &name, "scope name"); + } +}; +void +BindingName::trace(JSTracer* trc) +{ + if (JSAtom* atom = name()) + TraceManuallyBarrieredEdge(trc, &atom, "binding name"); +} +void +BindingIter::trace(JSTracer* trc) +{ + TraceNullableBindingNames(trc, names_, length_); +} +void +LexicalScope::Data::trace(JSTracer* trc) +{ + TraceBindingNames(trc, names, length); +} +void +FunctionScope::Data::trace(JSTracer* trc) +{ + TraceNullableEdge(trc, &canonicalFunction, "scope canonical function"); + TraceNullableBindingNames(trc, names, length); +} +void +VarScope::Data::trace(JSTracer* trc) +{ + TraceBindingNames(trc, names, length); +} +void +GlobalScope::Data::trace(JSTracer* trc) +{ + TraceBindingNames(trc, names, length); +} +void +EvalScope::Data::trace(JSTracer* trc) +{ + TraceBindingNames(trc, names, length); +} +void +ModuleScope::Data::trace(JSTracer* trc) +{ + TraceNullableEdge(trc, &module, "scope module"); + TraceBindingNames(trc, names, length); +} +void +Scope::traceChildren(JSTracer* trc) +{ + TraceNullableEdge(trc, &enclosing_, "scope enclosing"); + TraceNullableEdge(trc, &environmentShape_, "scope env shape"); + switch (kind_) { + case ScopeKind::Function: + reinterpret_cast<FunctionScope::Data*>(data_)->trace(trc); + break; + case ScopeKind::FunctionBodyVar: + case ScopeKind::ParameterExpressionVar: + reinterpret_cast<VarScope::Data*>(data_)->trace(trc); + break; + case ScopeKind::Lexical: + case ScopeKind::SimpleCatch: + case ScopeKind::Catch: + case ScopeKind::NamedLambda: + case ScopeKind::StrictNamedLambda: + reinterpret_cast<LexicalScope::Data*>(data_)->trace(trc); + break; + case ScopeKind::Global: + case ScopeKind::NonSyntactic: + reinterpret_cast<GlobalScope::Data*>(data_)->trace(trc); + break; + case ScopeKind::Eval: + case ScopeKind::StrictEval: + reinterpret_cast<EvalScope::Data*>(data_)->trace(trc); + break; + case ScopeKind::Module: + reinterpret_cast<ModuleScope::Data*>(data_)->trace(trc); + break; + case ScopeKind::With: + break; + } +} +inline void +js::GCMarker::eagerlyMarkChildren(Scope* scope) +{ + if (scope->enclosing_) + traverseEdge(scope, static_cast<Scope*>(scope->enclosing_)); + if (scope->environmentShape_) + traverseEdge(scope, static_cast<Shape*>(scope->environmentShape_)); + BindingName* names = nullptr; + uint32_t length = 0; + switch (scope->kind_) { + case ScopeKind::Function: { + FunctionScope::Data* data = reinterpret_cast<FunctionScope::Data*>(scope->data_); + traverseEdge(scope, static_cast<JSObject*>(data->canonicalFunction)); + names = data->names; + length = data->length; + break; + } + + case ScopeKind::FunctionBodyVar: + case ScopeKind::ParameterExpressionVar: { + VarScope::Data* data = reinterpret_cast<VarScope::Data*>(scope->data_); + names = data->names; + length = data->length; + break; + } + + case ScopeKind::Lexical: + case ScopeKind::SimpleCatch: + case ScopeKind::Catch: + case ScopeKind::NamedLambda: + case ScopeKind::StrictNamedLambda: { + LexicalScope::Data* data = reinterpret_cast<LexicalScope::Data*>(scope->data_); + names = data->names; + length = data->length; + break; + } + + case ScopeKind::Global: + case ScopeKind::NonSyntactic: { + GlobalScope::Data* data = reinterpret_cast<GlobalScope::Data*>(scope->data_); + names = data->names; + length = data->length; + break; + } + + case ScopeKind::Eval: + case ScopeKind::StrictEval: { + EvalScope::Data* data = reinterpret_cast<EvalScope::Data*>(scope->data_); + names = data->names; + length = data->length; + break; + } + + case ScopeKind::Module: { + ModuleScope::Data* data = reinterpret_cast<ModuleScope::Data*>(scope->data_); + traverseEdge(scope, static_cast<JSObject*>(data->module)); + names = data->names; + length = data->length; + break; + } + + case ScopeKind::With: + break; + } + if (scope->kind_ == ScopeKind::Function) { + for (uint32_t i = 0; i < length; i++) { + if (JSAtom* name = names[i].name()) + traverseEdge(scope, static_cast<JSString*>(name)); + } + } else { + for (uint32_t i = 0; i < length; i++) + traverseEdge(scope, static_cast<JSString*>(names[i].name())); + } +} + +void +js::ObjectGroup::traceChildren(JSTracer* trc) +{ + unsigned count = getPropertyCount(); + for (unsigned i = 0; i < count; i++) { + if (ObjectGroup::Property* prop = getProperty(i)) + TraceEdge(trc, &prop->id, "group_property"); + } + + if (proto().isObject()) + TraceEdge(trc, &proto(), "group_proto"); + + if (trc->isMarkingTracer()) + compartment()->mark(); + + if (JSObject* global = compartment()->unsafeUnbarrieredMaybeGlobal()) + TraceManuallyBarrieredEdge(trc, &global, "group_global"); + + + if (newScript()) + newScript()->trace(trc); + + if (maybePreliminaryObjects()) + maybePreliminaryObjects()->trace(trc); + + if (maybeUnboxedLayout()) + unboxedLayout().trace(trc); + + if (ObjectGroup* unboxedGroup = maybeOriginalUnboxedGroup()) { + TraceManuallyBarrieredEdge(trc, &unboxedGroup, "group_original_unboxed_group"); + setOriginalUnboxedGroup(unboxedGroup); + } + + if (JSObject* descr = maybeTypeDescr()) { + TraceManuallyBarrieredEdge(trc, &descr, "group_type_descr"); + setTypeDescr(&descr->as<TypeDescr>()); + } + + if (JSObject* fun = maybeInterpretedFunction()) { + TraceManuallyBarrieredEdge(trc, &fun, "group_function"); + setInterpretedFunction(&fun->as<JSFunction>()); + } +} +void +js::GCMarker::lazilyMarkChildren(ObjectGroup* group) +{ + unsigned count = group->getPropertyCount(); + for (unsigned i = 0; i < count; i++) { + if (ObjectGroup::Property* prop = group->getProperty(i)) + traverseEdge(group, prop->id.get()); + } + + if (group->proto().isObject()) + traverseEdge(group, group->proto().toObject()); + + group->compartment()->mark(); + + if (GlobalObject* global = group->compartment()->unsafeUnbarrieredMaybeGlobal()) + traverseEdge(group, static_cast<JSObject*>(global)); + + if (group->newScript()) + group->newScript()->trace(this); + + if (group->maybePreliminaryObjects()) + group->maybePreliminaryObjects()->trace(this); + + if (group->maybeUnboxedLayout()) + group->unboxedLayout().trace(this); + + if (ObjectGroup* unboxedGroup = group->maybeOriginalUnboxedGroup()) + traverseEdge(group, unboxedGroup); + + if (TypeDescr* descr = group->maybeTypeDescr()) + traverseEdge(group, static_cast<JSObject*>(descr)); + + if (JSFunction* fun = group->maybeInterpretedFunction()) + traverseEdge(group, static_cast<JSObject*>(fun)); +} + +struct TraverseObjectFunctor +{ + template <typename T> + void operator()(T* thing, GCMarker* gcmarker, JSObject* src) { + gcmarker->traverseEdge(src, *thing); + } +}; + +// Call the trace hook set on the object, if present. If further tracing of +// NativeObject fields is required, this will return the native object. +enum class CheckGeneration { DoChecks, NoChecks}; +template <typename Functor, typename... Args> +static inline NativeObject* +CallTraceHook(Functor f, JSTracer* trc, JSObject* obj, CheckGeneration check, Args&&... args) +{ + const Class* clasp = obj->getClass(); + MOZ_ASSERT(clasp); + MOZ_ASSERT(obj->isNative() == clasp->isNative()); + + if (!clasp->hasTrace()) + return &obj->as<NativeObject>(); + + if (clasp->isTrace(InlineTypedObject::obj_trace)) { + Shape** pshape = obj->as<InlineTypedObject>().addressOfShapeFromGC(); + f(pshape, mozilla::Forward<Args>(args)...); + + InlineTypedObject& tobj = obj->as<InlineTypedObject>(); + if (tobj.typeDescr().hasTraceList()) { + VisitTraceList(f, tobj.typeDescr().traceList(), tobj.inlineTypedMemForGC(), + mozilla::Forward<Args>(args)...); + } + + return nullptr; + } + + if (clasp == &UnboxedPlainObject::class_) { + JSObject** pexpando = obj->as<UnboxedPlainObject>().addressOfExpando(); + if (*pexpando) + f(pexpando, mozilla::Forward<Args>(args)...); + + UnboxedPlainObject& unboxed = obj->as<UnboxedPlainObject>(); + const UnboxedLayout& layout = check == CheckGeneration::DoChecks + ? unboxed.layout() + : unboxed.layoutDontCheckGeneration(); + if (layout.traceList()) { + VisitTraceList(f, layout.traceList(), unboxed.data(), + mozilla::Forward<Args>(args)...); + } + + return nullptr; + } + + clasp->doTrace(trc, obj); + + if (!clasp->isNative()) + return nullptr; + return &obj->as<NativeObject>(); +} + +template <typename F, typename... Args> +static void +VisitTraceList(F f, const int32_t* traceList, uint8_t* memory, Args&&... args) +{ + while (*traceList != -1) { + f(reinterpret_cast<JSString**>(memory + *traceList), mozilla::Forward<Args>(args)...); + traceList++; + } + traceList++; + while (*traceList != -1) { + JSObject** objp = reinterpret_cast<JSObject**>(memory + *traceList); + if (*objp) + f(objp, mozilla::Forward<Args>(args)...); + traceList++; + } + traceList++; + while (*traceList != -1) { + f(reinterpret_cast<Value*>(memory + *traceList), mozilla::Forward<Args>(args)...); + traceList++; + } +} + + +/*** Mark-stack Marking ***************************************************************************/ + +bool +GCMarker::drainMarkStack(SliceBudget& budget) +{ +#ifdef DEBUG + MOZ_ASSERT(!strictCompartmentChecking); + strictCompartmentChecking = true; + auto acc = mozilla::MakeScopeExit([&] {strictCompartmentChecking = false;}); +#endif + + if (budget.isOverBudget()) + return false; + + for (;;) { + while (!stack.isEmpty()) { + processMarkStackTop(budget); + if (budget.isOverBudget()) { + saveValueRanges(); + return false; + } + } + + if (!hasDelayedChildren()) + break; + + /* + * Mark children of things that caused too deep recursion during the + * above tracing. Don't do this until we're done with everything + * else. + */ + if (!markDelayedChildren(budget)) { + saveValueRanges(); + return false; + } + } + + return true; +} + +inline static bool +ObjectDenseElementsMayBeMarkable(NativeObject* nobj) +{ + /* + * For arrays that are large enough it's worth checking the type information + * to see if the object's elements contain any GC pointers. If not, we + * don't need to trace them. + */ + const unsigned MinElementsLength = 32; + if (nobj->getDenseInitializedLength() < MinElementsLength || nobj->isSingleton()) + return true; + + ObjectGroup* group = nobj->group(); + if (group->needsSweep() || group->unknownProperties()) + return true; + + HeapTypeSet* typeSet = group->maybeGetProperty(JSID_VOID); + if (!typeSet) + return true; + + static const uint32_t flagMask = + TYPE_FLAG_STRING | TYPE_FLAG_SYMBOL | TYPE_FLAG_LAZYARGS | TYPE_FLAG_ANYOBJECT; + bool mayBeMarkable = typeSet->hasAnyFlag(flagMask) || typeSet->getObjectCount() != 0; + +#ifdef DEBUG + if (!mayBeMarkable) { + const Value* elements = nobj->getDenseElementsAllowCopyOnWrite(); + for (unsigned i = 0; i < nobj->getDenseInitializedLength(); i++) + MOZ_ASSERT(!elements[i].isMarkable()); + } +#endif + + return mayBeMarkable; +} + +inline void +GCMarker::processMarkStackTop(SliceBudget& budget) +{ + /* + * The function uses explicit goto and implements the scanning of the + * object directly. It allows to eliminate the tail recursion and + * significantly improve the marking performance, see bug 641025. + */ + HeapSlot* vp; + HeapSlot* end; + JSObject* obj; + + // Decode + uintptr_t addr = stack.pop(); + uintptr_t tag = addr & StackTagMask; + addr &= ~StackTagMask; + + // Dispatch + switch (tag) { + case ValueArrayTag: { + JS_STATIC_ASSERT(ValueArrayTag == 0); + MOZ_ASSERT(!(addr & CellMask)); + obj = reinterpret_cast<JSObject*>(addr); + uintptr_t addr2 = stack.pop(); + uintptr_t addr3 = stack.pop(); + MOZ_ASSERT(addr2 <= addr3); + MOZ_ASSERT((addr3 - addr2) % sizeof(Value) == 0); + vp = reinterpret_cast<HeapSlot*>(addr2); + end = reinterpret_cast<HeapSlot*>(addr3); + goto scan_value_array; + } + + case ObjectTag: { + obj = reinterpret_cast<JSObject*>(addr); + AssertZoneIsMarking(obj); + goto scan_obj; + } + + case GroupTag: { + return lazilyMarkChildren(reinterpret_cast<ObjectGroup*>(addr)); + } + + case JitCodeTag: { + return reinterpret_cast<jit::JitCode*>(addr)->traceChildren(this); + } + + case ScriptTag: { + return reinterpret_cast<JSScript*>(addr)->traceChildren(this); + } + + case SavedValueArrayTag: { + MOZ_ASSERT(!(addr & CellMask)); + JSObject* obj = reinterpret_cast<JSObject*>(addr); + HeapSlot* vp; + HeapSlot* end; + if (restoreValueArray(obj, (void**)&vp, (void**)&end)) + pushValueArray(&obj->as<NativeObject>(), vp, end); + else + repush(obj); + return; + } + + default: MOZ_CRASH("Invalid tag in mark stack"); + } + return; + + scan_value_array: + MOZ_ASSERT(vp <= end); + while (vp != end) { + budget.step(); + if (budget.isOverBudget()) { + pushValueArray(obj, vp, end); + return; + } + + const Value& v = *vp++; + if (v.isString()) { + traverseEdge(obj, v.toString()); + } else if (v.isObject()) { + JSObject* obj2 = &v.toObject(); + MOZ_ASSERT(obj->compartment() == obj2->compartment()); + if (mark(obj2)) { + // Save the rest of this value array for later and start scanning obj2's children. + pushValueArray(obj, vp, end); + obj = obj2; + goto scan_obj; + } + } else if (v.isSymbol()) { + traverseEdge(obj, v.toSymbol()); + } else if (v.isPrivateGCThing()) { + traverseEdge(obj, v.toGCCellPtr()); + } + } + return; + + scan_obj: + { + AssertZoneIsMarking(obj); + + budget.step(); + if (budget.isOverBudget()) { + repush(obj); + return; + } + + markImplicitEdges(obj); + ObjectGroup* group = obj->groupFromGC(); + traverseEdge(obj, group); + + NativeObject *nobj = CallTraceHook(TraverseObjectFunctor(), this, obj, + CheckGeneration::DoChecks, this, obj); + if (!nobj) + return; + + Shape* shape = nobj->lastProperty(); + traverseEdge(obj, shape); + + unsigned nslots = nobj->slotSpan(); + + do { + if (nobj->hasEmptyElements()) + break; + + if (nobj->denseElementsAreCopyOnWrite()) { + JSObject* owner = nobj->getElementsHeader()->ownerObject(); + if (owner != nobj) { + traverseEdge(obj, owner); + break; + } + } + + if (!ObjectDenseElementsMayBeMarkable(nobj)) + break; + + vp = nobj->getDenseElementsAllowCopyOnWrite(); + end = vp + nobj->getDenseInitializedLength(); + + if (!nslots) + goto scan_value_array; + pushValueArray(nobj, vp, end); + } while (false); + + vp = nobj->fixedSlots(); + if (nobj->slots_) { + unsigned nfixed = nobj->numFixedSlots(); + if (nslots > nfixed) { + pushValueArray(nobj, vp, vp + nfixed); + vp = nobj->slots_; + end = vp + (nslots - nfixed); + goto scan_value_array; + } + } + MOZ_ASSERT(nslots <= nobj->numFixedSlots()); + end = vp + nslots; + goto scan_value_array; + } +} + +struct SlotArrayLayout +{ + union { + HeapSlot* end; + uintptr_t kind; + }; + union { + HeapSlot* start; + uintptr_t index; + }; + NativeObject* obj; + + static void staticAsserts() { + /* This should have the same layout as three mark stack items. */ + JS_STATIC_ASSERT(sizeof(SlotArrayLayout) == 3 * sizeof(uintptr_t)); + } +}; + +/* + * During incremental GC, we return from drainMarkStack without having processed + * the entire stack. At that point, JS code can run and reallocate slot arrays + * that are stored on the stack. To prevent this from happening, we replace all + * ValueArrayTag stack items with SavedValueArrayTag. In the latter, slots + * pointers are replaced with slot indexes, and slot array end pointers are + * replaced with the kind of index (properties vs. elements). + */ +void +GCMarker::saveValueRanges() +{ + for (uintptr_t* p = stack.tos_; p > stack.stack_; ) { + uintptr_t tag = *--p & StackTagMask; + if (tag == ValueArrayTag) { + *p &= ~StackTagMask; + p -= 2; + SlotArrayLayout* arr = reinterpret_cast<SlotArrayLayout*>(p); + NativeObject* obj = arr->obj; + MOZ_ASSERT(obj->isNative()); + + HeapSlot* vp = obj->getDenseElementsAllowCopyOnWrite(); + if (arr->end == vp + obj->getDenseInitializedLength()) { + MOZ_ASSERT(arr->start >= vp); + arr->index = arr->start - vp; + arr->kind = HeapSlot::Element; + } else { + HeapSlot* vp = obj->fixedSlots(); + unsigned nfixed = obj->numFixedSlots(); + if (arr->start == arr->end) { + arr->index = obj->slotSpan(); + } else if (arr->start >= vp && arr->start < vp + nfixed) { + MOZ_ASSERT(arr->end == vp + Min(nfixed, obj->slotSpan())); + arr->index = arr->start - vp; + } else { + MOZ_ASSERT(arr->start >= obj->slots_ && + arr->end == obj->slots_ + obj->slotSpan() - nfixed); + arr->index = (arr->start - obj->slots_) + nfixed; + } + arr->kind = HeapSlot::Slot; + } + p[2] |= SavedValueArrayTag; + } else if (tag == SavedValueArrayTag) { + p -= 2; + } + } +} + +bool +GCMarker::restoreValueArray(JSObject* objArg, void** vpp, void** endp) +{ + uintptr_t start = stack.pop(); + HeapSlot::Kind kind = (HeapSlot::Kind) stack.pop(); + + if (!objArg->isNative()) + return false; + NativeObject* obj = &objArg->as<NativeObject>(); + + if (kind == HeapSlot::Element) { + if (!obj->is<ArrayObject>()) + return false; + + uint32_t initlen = obj->getDenseInitializedLength(); + HeapSlot* vp = obj->getDenseElementsAllowCopyOnWrite(); + if (start < initlen) { + *vpp = vp + start; + *endp = vp + initlen; + } else { + /* The object shrunk, in which case no scanning is needed. */ + *vpp = *endp = vp; + } + } else { + MOZ_ASSERT(kind == HeapSlot::Slot); + HeapSlot* vp = obj->fixedSlots(); + unsigned nfixed = obj->numFixedSlots(); + unsigned nslots = obj->slotSpan(); + if (start < nslots) { + if (start < nfixed) { + *vpp = vp + start; + *endp = vp + Min(nfixed, nslots); + } else { + *vpp = obj->slots_ + start - nfixed; + *endp = obj->slots_ + nslots - nfixed; + } + } else { + /* The object shrunk, in which case no scanning is needed. */ + *vpp = *endp = vp; + } + } + + MOZ_ASSERT(*vpp <= *endp); + return true; +} + + +/*** Mark Stack ***********************************************************************************/ + +bool +MarkStack::init(JSGCMode gcMode) +{ + setBaseCapacity(gcMode); + + MOZ_ASSERT(!stack_); + uintptr_t* newStack = js_pod_malloc<uintptr_t>(baseCapacity_); + if (!newStack) + return false; + + setStack(newStack, 0, baseCapacity_); + return true; +} + +void +MarkStack::setBaseCapacity(JSGCMode mode) +{ + switch (mode) { + case JSGC_MODE_GLOBAL: + case JSGC_MODE_ZONE: + baseCapacity_ = NON_INCREMENTAL_MARK_STACK_BASE_CAPACITY; + break; + case JSGC_MODE_INCREMENTAL: + baseCapacity_ = INCREMENTAL_MARK_STACK_BASE_CAPACITY; + break; + default: + MOZ_CRASH("bad gc mode"); + } + + if (baseCapacity_ > maxCapacity_) + baseCapacity_ = maxCapacity_; +} + +void +MarkStack::setMaxCapacity(size_t maxCapacity) +{ + MOZ_ASSERT(maxCapacity != 0); + MOZ_ASSERT(isEmpty()); + maxCapacity_ = maxCapacity; + if (baseCapacity_ > maxCapacity_) + baseCapacity_ = maxCapacity_; + + reset(); +} + +void +MarkStack::reset() +{ + if (capacity() == baseCapacity_) { + // No size change; keep the current stack. + setStack(stack_, 0, baseCapacity_); + return; + } + + MOZ_ASSERT(baseCapacity_ != 0); + uintptr_t* newStack = (uintptr_t*)js_realloc(stack_, sizeof(uintptr_t) * baseCapacity_); + if (!newStack) { + // If the realloc fails, just keep using the existing stack; it's + // not ideal but better than failing. + newStack = stack_; + baseCapacity_ = capacity(); + } + setStack(newStack, 0, baseCapacity_); +} + +bool +MarkStack::enlarge(unsigned count) +{ + size_t newCapacity = Min(maxCapacity_, capacity() * 2); + if (newCapacity < capacity() + count) + return false; + + size_t tosIndex = position(); + + MOZ_ASSERT(newCapacity != 0); + uintptr_t* newStack = (uintptr_t*)js_realloc(stack_, sizeof(uintptr_t) * newCapacity); + if (!newStack) + return false; + + setStack(newStack, tosIndex, newCapacity); + return true; +} + +void +MarkStack::setGCMode(JSGCMode gcMode) +{ + // The mark stack won't be resized until the next call to reset(), but + // that will happen at the end of the next GC. + setBaseCapacity(gcMode); +} + +size_t +MarkStack::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const +{ + return mallocSizeOf(stack_); +} + + +/*** GCMarker *************************************************************************************/ + +/* + * ExpandWeakMaps: the GC is recomputing the liveness of WeakMap entries by + * expanding each live WeakMap into its constituent key->value edges, a table + * of which will be consulted in a later phase whenever marking a potential + * key. + */ +GCMarker::GCMarker(JSRuntime* rt) + : JSTracer(rt, JSTracer::TracerKindTag::Marking, ExpandWeakMaps), + stack(size_t(-1)), + color(BLACK), + unmarkedArenaStackTop(nullptr) +#ifdef DEBUG + , markLaterArenas(0) + , started(false) + , strictCompartmentChecking(false) +#endif +{ +} + +bool +GCMarker::init(JSGCMode gcMode) +{ + return stack.init(gcMode); +} + +void +GCMarker::start() +{ +#ifdef DEBUG + MOZ_ASSERT(!started); + started = true; +#endif + color = BLACK; + linearWeakMarkingDisabled_ = false; + + MOZ_ASSERT(!unmarkedArenaStackTop); + MOZ_ASSERT(markLaterArenas == 0); +} + +void +GCMarker::stop() +{ +#ifdef DEBUG + MOZ_ASSERT(isDrained()); + + MOZ_ASSERT(started); + started = false; + + MOZ_ASSERT(!unmarkedArenaStackTop); + MOZ_ASSERT(markLaterArenas == 0); +#endif + + /* Free non-ballast stack memory. */ + stack.reset(); + AutoEnterOOMUnsafeRegion oomUnsafe; + for (GCZonesIter zone(runtime()); !zone.done(); zone.next()) { + if (!zone->gcWeakKeys.clear()) + oomUnsafe.crash("clearing weak keys in GCMarker::stop()"); + } +} + +void +GCMarker::reset() +{ + color = BLACK; + + stack.reset(); + MOZ_ASSERT(isMarkStackEmpty()); + + while (unmarkedArenaStackTop) { + Arena* arena = unmarkedArenaStackTop; + MOZ_ASSERT(arena->hasDelayedMarking); + MOZ_ASSERT(markLaterArenas); + unmarkedArenaStackTop = arena->getNextDelayedMarking(); + arena->unsetDelayedMarking(); + arena->markOverflow = 0; + arena->allocatedDuringIncremental = 0; +#ifdef DEBUG + markLaterArenas--; +#endif + } + MOZ_ASSERT(isDrained()); + MOZ_ASSERT(!markLaterArenas); +} + +void +GCMarker::enterWeakMarkingMode() +{ + MOZ_ASSERT(tag_ == TracerKindTag::Marking); + if (linearWeakMarkingDisabled_) + return; + + // During weak marking mode, we maintain a table mapping weak keys to + // entries in known-live weakmaps. Initialize it with the keys of marked + // weakmaps -- or more precisely, the keys of marked weakmaps that are + // mapped to not yet live values. (Once bug 1167452 implements incremental + // weakmap marking, this initialization step will become unnecessary, as + // the table will already hold all such keys.) + if (weakMapAction() == ExpandWeakMaps) { + tag_ = TracerKindTag::WeakMarking; + + for (GCZoneGroupIter zone(runtime()); !zone.done(); zone.next()) { + for (WeakMapBase* m : zone->gcWeakMapList) { + if (m->marked) + (void) m->traceEntries(this); + } + } + } +} + +void +GCMarker::leaveWeakMarkingMode() +{ + MOZ_ASSERT_IF(weakMapAction() == ExpandWeakMaps && !linearWeakMarkingDisabled_, + tag_ == TracerKindTag::WeakMarking); + tag_ = TracerKindTag::Marking; + + // Table is expensive to maintain when not in weak marking mode, so we'll + // rebuild it upon entry rather than allow it to contain stale data. + AutoEnterOOMUnsafeRegion oomUnsafe; + for (GCZonesIter zone(runtime()); !zone.done(); zone.next()) { + if (!zone->gcWeakKeys.clear()) + oomUnsafe.crash("clearing weak keys in GCMarker::leaveWeakMarkingMode()"); + } +} + +void +GCMarker::markDelayedChildren(Arena* arena) +{ + if (arena->markOverflow) { + bool always = arena->allocatedDuringIncremental; + arena->markOverflow = 0; + + for (ArenaCellIterUnderGC i(arena); !i.done(); i.next()) { + TenuredCell* t = i.getCell(); + if (always || t->isMarked()) { + t->markIfUnmarked(); + js::TraceChildren(this, t, MapAllocToTraceKind(arena->getAllocKind())); + } + } + } else { + MOZ_ASSERT(arena->allocatedDuringIncremental); + PushArena(this, arena); + } + arena->allocatedDuringIncremental = 0; + /* + * Note that during an incremental GC we may still be allocating into + * the arena. However, prepareForIncrementalGC sets the + * allocatedDuringIncremental flag if we continue marking. + */ +} + +bool +GCMarker::markDelayedChildren(SliceBudget& budget) +{ + GCRuntime& gc = runtime()->gc; + gcstats::AutoPhase ap(gc.stats, gc.state() == State::Mark, gcstats::PHASE_MARK_DELAYED); + + MOZ_ASSERT(unmarkedArenaStackTop); + do { + /* + * If marking gets delayed at the same arena again, we must repeat + * marking of its things. For that we pop arena from the stack and + * clear its hasDelayedMarking flag before we begin the marking. + */ + Arena* arena = unmarkedArenaStackTop; + MOZ_ASSERT(arena->hasDelayedMarking); + MOZ_ASSERT(markLaterArenas); + unmarkedArenaStackTop = arena->getNextDelayedMarking(); + arena->unsetDelayedMarking(); +#ifdef DEBUG + markLaterArenas--; +#endif + markDelayedChildren(arena); + + budget.step(150); + if (budget.isOverBudget()) + return false; + } while (unmarkedArenaStackTop); + MOZ_ASSERT(!markLaterArenas); + + return true; +} + +template<typename T> +static void +PushArenaTyped(GCMarker* gcmarker, Arena* arena) +{ + for (ArenaCellIterUnderGC i(arena); !i.done(); i.next()) + gcmarker->traverse(i.get<T>()); +} + +struct PushArenaFunctor { + template <typename T> void operator()(GCMarker* gcmarker, Arena* arena) { + PushArenaTyped<T>(gcmarker, arena); + } +}; + +void +gc::PushArena(GCMarker* gcmarker, Arena* arena) +{ + DispatchTraceKindTyped(PushArenaFunctor(), + MapAllocToTraceKind(arena->getAllocKind()), gcmarker, arena); +} + +#ifdef DEBUG +void +GCMarker::checkZone(void* p) +{ + MOZ_ASSERT(started); + DebugOnly<Cell*> cell = static_cast<Cell*>(p); + MOZ_ASSERT_IF(cell->isTenured(), cell->asTenured().zone()->isCollecting()); +} +#endif + +size_t +GCMarker::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const +{ + size_t size = stack.sizeOfExcludingThis(mallocSizeOf); + for (ZonesIter zone(runtime(), WithAtoms); !zone.done(); zone.next()) + size += zone->gcGrayRoots.sizeOfExcludingThis(mallocSizeOf); + return size; +} + + +/*** Tenuring Tracer *****************************************************************************/ + +namespace js { +template <typename T> +void +TenuringTracer::traverse(T** tp) +{ +} + +template <> +void +TenuringTracer::traverse(JSObject** objp) +{ + // We only ever visit the internals of objects after moving them to tenured. + MOZ_ASSERT(!nursery().isInside(objp)); + + if (IsInsideNursery(*objp) && !nursery().getForwardedPointer(objp)) + *objp = moveToTenured(*objp); +} + +template <typename S> +struct TenuringTraversalFunctor : public IdentityDefaultAdaptor<S> { + template <typename T> S operator()(T* t, TenuringTracer* trc) { + trc->traverse(&t); + return js::gc::RewrapTaggedPointer<S, T>::wrap(t); + } +}; + +template <typename T> +void +TenuringTracer::traverse(T* thingp) +{ + *thingp = DispatchTyped(TenuringTraversalFunctor<T>(), *thingp, this); +} +} // namespace js + +template <typename T> +void +js::gc::StoreBuffer::MonoTypeBuffer<T>::trace(StoreBuffer* owner, TenuringTracer& mover) +{ + mozilla::ReentrancyGuard g(*owner); + MOZ_ASSERT(owner->isEnabled()); + MOZ_ASSERT(stores_.initialized()); + if (last_) + last_.trace(mover); + for (typename StoreSet::Range r = stores_.all(); !r.empty(); r.popFront()) + r.front().trace(mover); +} + +namespace js { +namespace gc { +template void +StoreBuffer::MonoTypeBuffer<StoreBuffer::ValueEdge>::trace(StoreBuffer*, TenuringTracer&); +template void +StoreBuffer::MonoTypeBuffer<StoreBuffer::SlotsEdge>::trace(StoreBuffer*, TenuringTracer&); +template void +StoreBuffer::MonoTypeBuffer<StoreBuffer::CellPtrEdge>::trace(StoreBuffer*, TenuringTracer&); +} // namespace gc +} // namespace js + +void +js::gc::StoreBuffer::SlotsEdge::trace(TenuringTracer& mover) const +{ + NativeObject* obj = object(); + + // Beware JSObject::swap exchanging a native object for a non-native one. + if (!obj->isNative()) + return; + + if (IsInsideNursery(obj)) + return; + + if (kind() == ElementKind) { + int32_t initLen = obj->getDenseInitializedLength(); + int32_t clampedStart = Min(start_, initLen); + int32_t clampedEnd = Min(start_ + count_, initLen); + mover.traceSlots(static_cast<HeapSlot*>(obj->getDenseElements() + clampedStart) + ->unsafeUnbarrieredForTracing(), clampedEnd - clampedStart); + } else { + int32_t start = Min(uint32_t(start_), obj->slotSpan()); + int32_t end = Min(uint32_t(start_) + count_, obj->slotSpan()); + MOZ_ASSERT(end >= start); + mover.traceObjectSlots(obj, start, end - start); + } +} + +static inline void +TraceWholeCell(TenuringTracer& mover, JSObject* object) +{ + mover.traceObject(object); + + // Additionally trace the expando object attached to any unboxed plain + // objects. Baseline and Ion can write properties to the expando while + // only adding a post barrier to the owning unboxed object. Note that + // it isn't possible for a nursery unboxed object to have a tenured + // expando, so that adding a post barrier on the original object will + // capture any tenured->nursery edges in the expando as well. + + if (object->is<UnboxedPlainObject>()) { + if (UnboxedExpandoObject* expando = object->as<UnboxedPlainObject>().maybeExpando()) + expando->traceChildren(&mover); + } +} + +static inline void +TraceWholeCell(TenuringTracer& mover, JSScript* script) +{ + script->traceChildren(&mover); +} + +static inline void +TraceWholeCell(TenuringTracer& mover, jit::JitCode* jitcode) +{ + jitcode->traceChildren(&mover); +} + +template <typename T> +static void +TraceBufferedCells(TenuringTracer& mover, Arena* arena, ArenaCellSet* cells) +{ + for (size_t i = 0; i < ArenaCellCount; i++) { + if (cells->hasCell(i)) { + auto cell = reinterpret_cast<T*>(uintptr_t(arena) + CellSize * i); + TraceWholeCell(mover, cell); + } + } +} + +void +js::gc::StoreBuffer::traceWholeCells(TenuringTracer& mover) +{ + for (ArenaCellSet* cells = bufferWholeCell; cells; cells = cells->next) { + Arena* arena = cells->arena; + + MOZ_ASSERT(arena->bufferedCells == cells); + arena->bufferedCells = &ArenaCellSet::Empty; + + JS::TraceKind kind = MapAllocToTraceKind(arena->getAllocKind()); + switch (kind) { + case JS::TraceKind::Object: + TraceBufferedCells<JSObject>(mover, arena, cells); + break; + case JS::TraceKind::Script: + TraceBufferedCells<JSScript>(mover, arena, cells); + break; + case JS::TraceKind::JitCode: + TraceBufferedCells<jit::JitCode>(mover, arena, cells); + break; + default: + MOZ_CRASH("Unexpected trace kind"); + } + } + + bufferWholeCell = nullptr; +} + +void +js::gc::StoreBuffer::CellPtrEdge::trace(TenuringTracer& mover) const +{ + if (!*edge) + return; + + MOZ_ASSERT((*edge)->getTraceKind() == JS::TraceKind::Object); + mover.traverse(reinterpret_cast<JSObject**>(edge)); +} + +void +js::gc::StoreBuffer::ValueEdge::trace(TenuringTracer& mover) const +{ + if (deref()) + mover.traverse(edge); +} + +/* Insert the given relocation entry into the list of things to visit. */ +void +js::TenuringTracer::insertIntoFixupList(RelocationOverlay* entry) { + *tail = entry; + tail = &entry->nextRef(); + *tail = nullptr; +} + +JSObject* +js::TenuringTracer::moveToTenured(JSObject* src) +{ + MOZ_ASSERT(IsInsideNursery(src)); + MOZ_ASSERT(!src->zone()->usedByExclusiveThread); + + AllocKind dstKind = src->allocKindForTenure(nursery()); + Zone* zone = src->zone(); + + TenuredCell* t = zone->arenas.allocateFromFreeList(dstKind, Arena::thingSize(dstKind)); + if (!t) { + AutoEnterOOMUnsafeRegion oomUnsafe; + t = runtime()->gc.refillFreeListInGC(zone, dstKind); + if (!t) + oomUnsafe.crash(ChunkSize, "Failed to allocate object while tenuring."); + } + JSObject* dst = reinterpret_cast<JSObject*>(t); + tenuredSize += moveObjectToTenured(dst, src, dstKind); + + RelocationOverlay* overlay = RelocationOverlay::fromCell(src); + overlay->forwardTo(dst); + insertIntoFixupList(overlay); + + TracePromoteToTenured(src, dst); + MemProfiler::MoveNurseryToTenured(src, dst); + return dst; +} + +void +js::Nursery::collectToFixedPoint(TenuringTracer& mover, TenureCountCache& tenureCounts) +{ + for (RelocationOverlay* p = mover.head; p; p = p->next()) { + JSObject* obj = static_cast<JSObject*>(p->forwardingAddress()); + mover.traceObject(obj); + + TenureCount& entry = tenureCounts.findEntry(obj->groupRaw()); + if (entry.group == obj->groupRaw()) { + entry.count++; + } else if (!entry.group) { + entry.group = obj->groupRaw(); + entry.count = 1; + } + } +} + +struct TenuringFunctor +{ + template <typename T> + void operator()(T* thing, TenuringTracer& mover) { + mover.traverse(thing); + } +}; + +// Visit all object children of the object and trace them. +void +js::TenuringTracer::traceObject(JSObject* obj) +{ + NativeObject *nobj = CallTraceHook(TenuringFunctor(), this, obj, + CheckGeneration::NoChecks, *this); + if (!nobj) + return; + + // Note: the contents of copy on write elements pointers are filled in + // during parsing and cannot contain nursery pointers. + if (!nobj->hasEmptyElements() && + !nobj->denseElementsAreCopyOnWrite() && + ObjectDenseElementsMayBeMarkable(nobj)) + { + Value* elems = static_cast<HeapSlot*>(nobj->getDenseElements())->unsafeUnbarrieredForTracing(); + traceSlots(elems, elems + nobj->getDenseInitializedLength()); + } + + traceObjectSlots(nobj, 0, nobj->slotSpan()); +} + +void +js::TenuringTracer::traceObjectSlots(NativeObject* nobj, uint32_t start, uint32_t length) +{ + HeapSlot* fixedStart; + HeapSlot* fixedEnd; + HeapSlot* dynStart; + HeapSlot* dynEnd; + nobj->getSlotRange(start, length, &fixedStart, &fixedEnd, &dynStart, &dynEnd); + if (fixedStart) + traceSlots(fixedStart->unsafeUnbarrieredForTracing(), fixedEnd->unsafeUnbarrieredForTracing()); + if (dynStart) + traceSlots(dynStart->unsafeUnbarrieredForTracing(), dynEnd->unsafeUnbarrieredForTracing()); +} + +void +js::TenuringTracer::traceSlots(Value* vp, Value* end) +{ + for (; vp != end; ++vp) + traverse(vp); +} + +#ifdef DEBUG +static inline ptrdiff_t +OffsetToChunkEnd(void* p) +{ + return ChunkLocationOffset - (uintptr_t(p) & gc::ChunkMask); +} +#endif + +size_t +js::TenuringTracer::moveObjectToTenured(JSObject* dst, JSObject* src, AllocKind dstKind) +{ + size_t srcSize = Arena::thingSize(dstKind); + size_t tenuredSize = srcSize; + + /* + * Arrays do not necessarily have the same AllocKind between src and dst. + * We deal with this by copying elements manually, possibly re-inlining + * them if there is adequate room inline in dst. + * + * For Arrays we're reducing tenuredSize to the smaller srcSize + * because moveElementsToTenured() accounts for all Array elements, + * even if they are inlined. + */ + if (src->is<ArrayObject>()) { + tenuredSize = srcSize = sizeof(NativeObject); + } else if (src->is<TypedArrayObject>()) { + TypedArrayObject* tarray = &src->as<TypedArrayObject>(); + // Typed arrays with inline data do not necessarily have the same + // AllocKind between src and dst. The nursery does not allocate an + // inline data buffer that has the same size as the slow path will do. + // In the slow path, the Typed Array Object stores the inline data + // in the allocated space that fits the AllocKind. In the fast path, + // the nursery will allocate another buffer that is directly behind the + // minimal JSObject. That buffer size plus the JSObject size is not + // necessarily as large as the slow path's AllocKind size. + if (tarray->hasInlineElements()) { + AllocKind srcKind = GetGCObjectKind(TypedArrayObject::FIXED_DATA_START); + size_t headerSize = Arena::thingSize(srcKind); + srcSize = headerSize + tarray->byteLength(); + } + } + + // Copy the Cell contents. + MOZ_ASSERT(OffsetToChunkEnd(src) >= ptrdiff_t(srcSize)); + js_memcpy(dst, src, srcSize); + + // Move any hash code attached to the object. + src->zone()->transferUniqueId(dst, src); + + // Move the slots and elements, if we need to. + if (src->isNative()) { + NativeObject* ndst = &dst->as<NativeObject>(); + NativeObject* nsrc = &src->as<NativeObject>(); + tenuredSize += moveSlotsToTenured(ndst, nsrc, dstKind); + tenuredSize += moveElementsToTenured(ndst, nsrc, dstKind); + + // The shape's list head may point into the old object. This can only + // happen for dictionaries, which are native objects. + if (&nsrc->shape_ == ndst->shape_->listp) { + MOZ_ASSERT(nsrc->shape_->inDictionary()); + ndst->shape_->listp = &ndst->shape_; + } + } + + if (src->is<InlineTypedObject>()) { + InlineTypedObject::objectMovedDuringMinorGC(this, dst, src); + } else if (src->is<TypedArrayObject>()) { + tenuredSize += TypedArrayObject::objectMovedDuringMinorGC(this, dst, src, dstKind); + } else if (src->is<UnboxedArrayObject>()) { + tenuredSize += UnboxedArrayObject::objectMovedDuringMinorGC(this, dst, src, dstKind); + } else if (src->is<ArgumentsObject>()) { + tenuredSize += ArgumentsObject::objectMovedDuringMinorGC(this, dst, src); + } else if (src->is<ProxyObject>()) { + tenuredSize += ProxyObject::objectMovedDuringMinorGC(this, dst, src); + } else if (JSObjectMovedOp op = dst->getClass()->extObjectMovedOp()) { + op(dst, src); + } else if (src->getClass()->hasFinalize()) { + // Such objects need to be handled specially above to ensure any + // additional nursery buffers they hold are moved. + MOZ_RELEASE_ASSERT(CanNurseryAllocateFinalizedClass(src->getClass())); + MOZ_CRASH("Unhandled JSCLASS_SKIP_NURSERY_FINALIZE Class"); + } + + return tenuredSize; +} + +size_t +js::TenuringTracer::moveSlotsToTenured(NativeObject* dst, NativeObject* src, AllocKind dstKind) +{ + /* Fixed slots have already been copied over. */ + if (!src->hasDynamicSlots()) + return 0; + + if (!nursery().isInside(src->slots_)) { + nursery().removeMallocedBuffer(src->slots_); + return 0; + } + + Zone* zone = src->zone(); + size_t count = src->numDynamicSlots(); + + { + AutoEnterOOMUnsafeRegion oomUnsafe; + dst->slots_ = zone->pod_malloc<HeapSlot>(count); + if (!dst->slots_) + oomUnsafe.crash(sizeof(HeapSlot) * count, "Failed to allocate slots while tenuring."); + } + + PodCopy(dst->slots_, src->slots_, count); + nursery().setSlotsForwardingPointer(src->slots_, dst->slots_, count); + return count * sizeof(HeapSlot); +} + +size_t +js::TenuringTracer::moveElementsToTenured(NativeObject* dst, NativeObject* src, AllocKind dstKind) +{ + if (src->hasEmptyElements() || src->denseElementsAreCopyOnWrite()) + return 0; + + Zone* zone = src->zone(); + ObjectElements* srcHeader = src->getElementsHeader(); + ObjectElements* dstHeader; + + /* TODO Bug 874151: Prefer to put element data inline if we have space. */ + if (!nursery().isInside(srcHeader)) { + MOZ_ASSERT(src->elements_ == dst->elements_); + nursery().removeMallocedBuffer(srcHeader); + return 0; + } + + size_t nslots = ObjectElements::VALUES_PER_HEADER + srcHeader->capacity; + + /* Unlike other objects, Arrays can have fixed elements. */ + if (src->is<ArrayObject>() && nslots <= GetGCKindSlots(dstKind)) { + dst->as<ArrayObject>().setFixedElements(); + dstHeader = dst->as<ArrayObject>().getElementsHeader(); + js_memcpy(dstHeader, srcHeader, nslots * sizeof(HeapSlot)); + nursery().setElementsForwardingPointer(srcHeader, dstHeader, nslots); + return nslots * sizeof(HeapSlot); + } + + MOZ_ASSERT(nslots >= 2); + + { + AutoEnterOOMUnsafeRegion oomUnsafe; + dstHeader = reinterpret_cast<ObjectElements*>(zone->pod_malloc<HeapSlot>(nslots)); + if (!dstHeader) { + oomUnsafe.crash(sizeof(HeapSlot) * nslots, + "Failed to allocate elements while tenuring."); + } + } + + js_memcpy(dstHeader, srcHeader, nslots * sizeof(HeapSlot)); + nursery().setElementsForwardingPointer(srcHeader, dstHeader, nslots); + dst->elements_ = dstHeader->elements(); + return nslots * sizeof(HeapSlot); +} + + +/*** IsMarked / IsAboutToBeFinalized **************************************************************/ + +template <typename T> +static inline void +CheckIsMarkedThing(T* thingp) +{ +#define IS_SAME_TYPE_OR(name, type, _) mozilla::IsSame<type*, T>::value || + static_assert( + JS_FOR_EACH_TRACEKIND(IS_SAME_TYPE_OR) + false, "Only the base cell layout types are allowed into marking/tracing internals"); +#undef IS_SAME_TYPE_OR + +#ifdef DEBUG + MOZ_ASSERT(thingp); + MOZ_ASSERT(*thingp); + JSRuntime* rt = (*thingp)->runtimeFromAnyThread(); + MOZ_ASSERT_IF(!ThingIsPermanentAtomOrWellKnownSymbol(*thingp), + CurrentThreadCanAccessRuntime(rt) || + (rt->isHeapCollecting() && rt->gc.state() == State::Sweep)); +#endif +} + +template <typename T> +static bool +IsMarkedInternalCommon(T* thingp) +{ + CheckIsMarkedThing(thingp); + MOZ_ASSERT(!IsInsideNursery(*thingp)); + + Zone* zone = (*thingp)->asTenured().zoneFromAnyThread(); + if (!zone->isCollectingFromAnyThread() || zone->isGCFinished()) + return true; + if (zone->isGCCompacting() && IsForwarded(*thingp)) + *thingp = Forwarded(*thingp); + return (*thingp)->asTenured().isMarked(); +} + +template <typename T> +static bool +IsMarkedInternal(JSRuntime* rt, T** thingp) +{ + if (IsOwnedByOtherRuntime(rt, *thingp)) + return true; + + return IsMarkedInternalCommon(thingp); +} + +template <> +/* static */ bool +IsMarkedInternal(JSRuntime* rt, JSObject** thingp) +{ + if (IsOwnedByOtherRuntime(rt, *thingp)) + return true; + + if (IsInsideNursery(*thingp)) { + MOZ_ASSERT(CurrentThreadCanAccessRuntime(rt)); + return rt->gc.nursery.getForwardedPointer(thingp); + } + return IsMarkedInternalCommon(thingp); +} + +template <typename S> +struct IsMarkedFunctor : public IdentityDefaultAdaptor<S> { + template <typename T> S operator()(T* t, JSRuntime* rt, bool* rv) { + *rv = IsMarkedInternal(rt, &t); + return js::gc::RewrapTaggedPointer<S, T>::wrap(t); + } +}; + +template <typename T> +static bool +IsMarkedInternal(JSRuntime* rt, T* thingp) +{ + bool rv = true; + *thingp = DispatchTyped(IsMarkedFunctor<T>(), *thingp, rt, &rv); + return rv; +} + +bool +js::gc::IsAboutToBeFinalizedDuringSweep(TenuredCell& tenured) +{ + MOZ_ASSERT(!IsInsideNursery(&tenured)); + MOZ_ASSERT(tenured.zoneFromAnyThread()->isGCSweeping()); + if (tenured.arena()->allocatedDuringIncremental) + return false; + return !tenured.isMarked(); +} + +template <typename T> +static bool +IsAboutToBeFinalizedInternal(T** thingp) +{ + CheckIsMarkedThing(thingp); + T* thing = *thingp; + JSRuntime* rt = thing->runtimeFromAnyThread(); + + /* Permanent atoms are never finalized by non-owning runtimes. */ + if (ThingIsPermanentAtomOrWellKnownSymbol(thing) && !TlsPerThreadData.get()->associatedWith(rt)) + return false; + + Nursery& nursery = rt->gc.nursery; + if (IsInsideNursery(thing)) { + MOZ_ASSERT(rt->isHeapMinorCollecting()); + return !nursery.getForwardedPointer(reinterpret_cast<JSObject**>(thingp)); + } + + Zone* zone = thing->asTenured().zoneFromAnyThread(); + if (zone->isGCSweeping()) { + return IsAboutToBeFinalizedDuringSweep(thing->asTenured()); + } else if (zone->isGCCompacting() && IsForwarded(thing)) { + *thingp = Forwarded(thing); + return false; + } + + return false; +} + +template <typename S> +struct IsAboutToBeFinalizedFunctor : public IdentityDefaultAdaptor<S> { + template <typename T> S operator()(T* t, bool* rv) { + *rv = IsAboutToBeFinalizedInternal(&t); + return js::gc::RewrapTaggedPointer<S, T>::wrap(t); + } +}; + +template <typename T> +static bool +IsAboutToBeFinalizedInternal(T* thingp) +{ + bool rv = false; + *thingp = DispatchTyped(IsAboutToBeFinalizedFunctor<T>(), *thingp, &rv); + return rv; +} + +namespace js { +namespace gc { + +template <typename T> +bool +IsMarkedUnbarriered(JSRuntime* rt, T* thingp) +{ + return IsMarkedInternal(rt, ConvertToBase(thingp)); +} + +template <typename T> +bool +IsMarked(JSRuntime* rt, WriteBarrieredBase<T>* thingp) +{ + return IsMarkedInternal(rt, ConvertToBase(thingp->unsafeUnbarrieredForTracing())); +} + +template <typename T> +bool +IsAboutToBeFinalizedUnbarriered(T* thingp) +{ + return IsAboutToBeFinalizedInternal(ConvertToBase(thingp)); +} + +template <typename T> +bool +IsAboutToBeFinalized(WriteBarrieredBase<T>* thingp) +{ + return IsAboutToBeFinalizedInternal(ConvertToBase(thingp->unsafeUnbarrieredForTracing())); +} + +template <typename T> +bool +IsAboutToBeFinalized(ReadBarrieredBase<T>* thingp) +{ + return IsAboutToBeFinalizedInternal(ConvertToBase(thingp->unsafeUnbarrieredForTracing())); +} + +template <typename T> +JS_PUBLIC_API(bool) +EdgeNeedsSweep(JS::Heap<T>* thingp) +{ + return IsAboutToBeFinalizedInternal(ConvertToBase(thingp->unsafeGet())); +} + +// Instantiate a copy of the Tracing templates for each derived type. +#define INSTANTIATE_ALL_VALID_TRACE_FUNCTIONS(type) \ + template bool IsMarkedUnbarriered<type>(JSRuntime*, type*); \ + template bool IsMarked<type>(JSRuntime*, WriteBarrieredBase<type>*); \ + template bool IsAboutToBeFinalizedUnbarriered<type>(type*); \ + template bool IsAboutToBeFinalized<type>(WriteBarrieredBase<type>*); \ + template bool IsAboutToBeFinalized<type>(ReadBarrieredBase<type>*); +#define INSTANTIATE_ALL_VALID_HEAP_TRACE_FUNCTIONS(type) \ + template JS_PUBLIC_API(bool) EdgeNeedsSweep<type>(JS::Heap<type>*); +FOR_EACH_GC_POINTER_TYPE(INSTANTIATE_ALL_VALID_TRACE_FUNCTIONS) +FOR_EACH_PUBLIC_GC_POINTER_TYPE(INSTANTIATE_ALL_VALID_HEAP_TRACE_FUNCTIONS) +FOR_EACH_PUBLIC_TAGGED_GC_POINTER_TYPE(INSTANTIATE_ALL_VALID_HEAP_TRACE_FUNCTIONS) +#undef INSTANTIATE_ALL_VALID_TRACE_FUNCTIONS + +} /* namespace gc */ +} /* namespace js */ + + +/*** Cycle Collector Barrier Implementation *******************************************************/ + +#ifdef DEBUG +struct AssertNonGrayTracer : public JS::CallbackTracer { + explicit AssertNonGrayTracer(JSRuntime* rt) : JS::CallbackTracer(rt) {} + void onChild(const JS::GCCellPtr& thing) override { + MOZ_ASSERT_IF(thing.asCell()->isTenured(), + !thing.asCell()->asTenured().isMarked(js::gc::GRAY)); + } +}; +#endif + +struct UnmarkGrayTracer : public JS::CallbackTracer +{ + /* + * We set weakMapAction to DoNotTraceWeakMaps because the cycle collector + * will fix up any color mismatches involving weakmaps when it runs. + */ + explicit UnmarkGrayTracer(JSRuntime *rt, bool tracingShape = false) + : JS::CallbackTracer(rt, DoNotTraceWeakMaps) + , tracingShape(tracingShape) + , previousShape(nullptr) + , unmarkedAny(false) + {} + + void onChild(const JS::GCCellPtr& thing) override; + + /* True iff we are tracing the immediate children of a shape. */ + bool tracingShape; + + /* If tracingShape, shape child or nullptr. Otherwise, nullptr. */ + Shape* previousShape; + + /* Whether we unmarked anything. */ + bool unmarkedAny; +}; + +/* + * The GC and CC are run independently. Consequently, the following sequence of + * events can occur: + * 1. GC runs and marks an object gray. + * 2. The mutator runs (specifically, some C++ code with access to gray + * objects) and creates a pointer from a JS root or other black object to + * the gray object. If we re-ran a GC at this point, the object would now be + * black. + * 3. Now we run the CC. It may think it can collect the gray object, even + * though it's reachable from the JS heap. + * + * To prevent this badness, we unmark the gray bit of an object when it is + * accessed by callers outside XPConnect. This would cause the object to go + * black in step 2 above. This must be done on everything reachable from the + * object being returned. The following code takes care of the recursive + * re-coloring. + * + * There is an additional complication for certain kinds of edges that are not + * contained explicitly in the source object itself, such as from a weakmap key + * to its value, and from an object being watched by a watchpoint to the + * watchpoint's closure. These "implicit edges" are represented in some other + * container object, such as the weakmap or the watchpoint itself. In these + * cases, calling unmark gray on an object won't find all of its children. + * + * Handling these implicit edges has two parts: + * - A special pass enumerating all of the containers that know about the + * implicit edges to fix any black-gray edges that have been created. This + * is implemented in nsXPConnect::FixWeakMappingGrayBits. + * - To prevent any incorrectly gray objects from escaping to live JS outside + * of the containers, we must add unmark-graying read barriers to these + * containers. + */ +void +UnmarkGrayTracer::onChild(const JS::GCCellPtr& thing) +{ + int stackDummy; + JSContext* cx = runtime()->contextFromMainThread(); + if (!JS_CHECK_STACK_SIZE(cx->nativeStackLimit[StackForSystemCode], &stackDummy)) { + /* + * If we run out of stack, we take a more drastic measure: require that + * we GC again before the next CC. + */ + runtime()->setGCGrayBitsValid(false); + return; + } + + Cell* cell = thing.asCell(); + + // Cells in the nursery cannot be gray, and therefore must necessarily point + // to only black edges. + if (!cell->isTenured()) { +#ifdef DEBUG + AssertNonGrayTracer nongray(runtime()); + TraceChildren(&nongray, cell, thing.kind()); +#endif + return; + } + + TenuredCell& tenured = cell->asTenured(); + if (!tenured.isMarked(js::gc::GRAY)) + return; + tenured.unmark(js::gc::GRAY); + + unmarkedAny = true; + + // Trace children of |tenured|. If |tenured| and its parent are both + // shapes, |tenured| will get saved to mPreviousShape without being traced. + // The parent will later trace |tenured|. This is done to avoid increasing + // the stack depth during shape tracing. It is safe to do because a shape + // can only have one child that is a shape. + UnmarkGrayTracer childTracer(runtime(), thing.kind() == JS::TraceKind::Shape); + + if (thing.kind() != JS::TraceKind::Shape) { + TraceChildren(&childTracer, &tenured, thing.kind()); + MOZ_ASSERT(!childTracer.previousShape); + unmarkedAny |= childTracer.unmarkedAny; + return; + } + + MOZ_ASSERT(thing.kind() == JS::TraceKind::Shape); + Shape* shape = static_cast<Shape*>(&tenured); + if (tracingShape) { + MOZ_ASSERT(!previousShape); + previousShape = shape; + return; + } + + do { + MOZ_ASSERT(!shape->isMarked(js::gc::GRAY)); + shape->traceChildren(&childTracer); + shape = childTracer.previousShape; + childTracer.previousShape = nullptr; + } while (shape); + unmarkedAny |= childTracer.unmarkedAny; +} + +template <typename T> +static bool +TypedUnmarkGrayCellRecursively(T* t) +{ + MOZ_ASSERT(t); + + JSRuntime* rt = t->runtimeFromMainThread(); + MOZ_ASSERT(!rt->isHeapCollecting()); + MOZ_ASSERT(!rt->isCycleCollecting()); + + bool unmarkedArg = false; + if (t->isTenured()) { + if (!t->asTenured().isMarked(GRAY)) + return false; + + t->asTenured().unmark(GRAY); + unmarkedArg = true; + } + + UnmarkGrayTracer trc(rt); + gcstats::AutoPhase outerPhase(rt->gc.stats, gcstats::PHASE_BARRIER); + gcstats::AutoPhase innerPhase(rt->gc.stats, gcstats::PHASE_UNMARK_GRAY); + t->traceChildren(&trc); + + return unmarkedArg || trc.unmarkedAny; +} + +struct UnmarkGrayCellRecursivelyFunctor { + template <typename T> bool operator()(T* t) { return TypedUnmarkGrayCellRecursively(t); } +}; + +bool +js::UnmarkGrayCellRecursively(Cell* cell, JS::TraceKind kind) +{ + return DispatchTraceKindTyped(UnmarkGrayCellRecursivelyFunctor(), cell, kind); +} + +bool +js::UnmarkGrayShapeRecursively(Shape* shape) +{ + return TypedUnmarkGrayCellRecursively(shape); +} + +JS_FRIEND_API(bool) +JS::UnmarkGrayGCThingRecursively(JS::GCCellPtr thing) +{ + return js::UnmarkGrayCellRecursively(thing.asCell(), thing.kind()); +} |