michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "gc/Marking.h"
michael@0: 
michael@0: #include "mozilla/DebugOnly.h"
michael@0: 
michael@0: #include "jit/IonCode.h"
michael@0: #include "js/SliceBudget.h"
michael@0: #include "vm/ArgumentsObject.h"
michael@0: #include "vm/ScopeObject.h"
michael@0: #include "vm/Shape.h"
michael@0: #include "vm/TypedArrayObject.h"
michael@0: 
michael@0: #include "jscompartmentinlines.h"
michael@0: #include "jsinferinlines.h"
michael@0: #include "jsobjinlines.h"
michael@0: 
michael@0: #ifdef JSGC_GENERATIONAL
michael@0: # include "gc/Nursery-inl.h"
michael@0: #endif
michael@0: #include "vm/String-inl.h"
michael@0: 
michael@0: using namespace js;
michael@0: using namespace js::gc;
michael@0: 
michael@0: using mozilla::DebugOnly;
michael@0: 
michael@0: void * const js::NullPtr::constNullValue = nullptr;
michael@0: 
michael@0: JS_PUBLIC_DATA(void * const) JS::NullPtr::constNullValue = nullptr;
michael@0: 
michael@0: /*
michael@0:  * There are two mostly separate mark paths. The first is a fast path used
michael@0:  * internally in the GC. The second is a slow path used for root marking and
michael@0:  * for API consumers like the cycle collector or Class::trace implementations.
michael@0:  *
michael@0:  * The fast path uses explicit stacks. The basic marking process during a GC is
michael@0:  * that all roots are pushed on to a mark stack, and then each item on the
michael@0:  * stack is scanned (possibly pushing more stuff) until the stack is empty.
michael@0:  *
michael@0:  * PushMarkStack pushes a GC thing onto the mark stack. In some cases (shapes
michael@0:  * or strings) it eagerly marks the object rather than pushing it. Popping and
michael@0:  * scanning is done by the processMarkStackTop method. For efficiency reasons
michael@0:  * like tail recursion elimination that method also implements the scanning of
michael@0:  * objects. For other GC things it uses helper methods.
michael@0:  *
michael@0:  * Most of the marking code outside Marking.cpp uses functions like MarkObject,
michael@0:  * MarkString, etc. These functions check if an object is in the compartment
michael@0:  * currently being GCed. If it is, they call PushMarkStack. Roots are pushed
michael@0:  * this way as well as pointers traversed inside trace hooks (for things like
michael@0:  * PropertyIteratorObjects). It is always valid to call a MarkX function
michael@0:  * instead of PushMarkStack, although it may be slower.
michael@0:  *
michael@0:  * The MarkX functions also handle non-GC object traversal. In this case, they
michael@0:  * call a callback for each object visited. This is a recursive process; the
michael@0:  * mark stacks are not involved. These callbacks may ask for the outgoing
michael@0:  * pointers to be visited. Eventually, this leads to the MarkChildren functions
michael@0:  * being called. These functions duplicate much of the functionality of
michael@0:  * scanning functions, but they don't push onto an explicit stack.
michael@0:  */
michael@0: 
michael@0: static inline void
michael@0: PushMarkStack(GCMarker *gcmarker, ObjectImpl *thing);
michael@0: 
michael@0: static inline void
michael@0: PushMarkStack(GCMarker *gcmarker, JSFunction *thing);
michael@0: 
michael@0: static inline void
michael@0: PushMarkStack(GCMarker *gcmarker, JSScript *thing);
michael@0: 
michael@0: static inline void
michael@0: PushMarkStack(GCMarker *gcmarker, Shape *thing);
michael@0: 
michael@0: static inline void
michael@0: PushMarkStack(GCMarker *gcmarker, JSString *thing);
michael@0: 
michael@0: static inline void
michael@0: PushMarkStack(GCMarker *gcmarker, types::TypeObject *thing);
michael@0: 
michael@0: namespace js {
michael@0: namespace gc {
michael@0: 
michael@0: static void MarkChildren(JSTracer *trc, JSString *str);
michael@0: static void MarkChildren(JSTracer *trc, JSScript *script);
michael@0: static void MarkChildren(JSTracer *trc, LazyScript *lazy);
michael@0: static void MarkChildren(JSTracer *trc, Shape *shape);
michael@0: static void MarkChildren(JSTracer *trc, BaseShape *base);
michael@0: static void MarkChildren(JSTracer *trc, types::TypeObject *type);
michael@0: static void MarkChildren(JSTracer *trc, jit::JitCode *code);
michael@0: 
michael@0: } /* namespace gc */
michael@0: } /* namespace js */
michael@0: 
michael@0: /*** Object Marking ***/
michael@0: 
michael@0: #if defined(DEBUG)
michael@0: template<typename T>
michael@0: static inline bool
michael@0: IsThingPoisoned(T *thing)
michael@0: {
michael@0:     static_assert(sizeof(T) >= sizeof(FreeSpan) + sizeof(uint32_t),
michael@0:                   "Ensure it is well defined to look past any free span that "
michael@0:                   "may be embedded in the thing's header when freed.");
michael@0:     const uint8_t poisonBytes[] = {
michael@0:         JS_FRESH_NURSERY_PATTERN,
michael@0:         JS_SWEPT_NURSERY_PATTERN,
michael@0:         JS_ALLOCATED_NURSERY_PATTERN,
michael@0:         JS_FRESH_TENURED_PATTERN,
michael@0:         JS_SWEPT_TENURED_PATTERN,
michael@0:         JS_ALLOCATED_TENURED_PATTERN,
michael@0:         JS_SWEPT_CODE_PATTERN,
michael@0:         JS_SWEPT_FRAME_PATTERN
michael@0:     };
michael@0:     const int numPoisonBytes = sizeof(poisonBytes) / sizeof(poisonBytes[0]);
michael@0:     uint32_t *p = reinterpret_cast<uint32_t *>(reinterpret_cast<FreeSpan *>(thing) + 1);
michael@0:     // Note: all free patterns are odd to make the common, not-poisoned case a single test.
michael@0:     if ((*p & 1) == 0)
michael@0:         return false;
michael@0:     for (int i = 0; i < numPoisonBytes; ++i) {
michael@0:         const uint8_t pb = poisonBytes[i];
michael@0:         const uint32_t pw = pb | (pb << 8) | (pb << 16) | (pb << 24);
michael@0:         if (*p == pw)
michael@0:             return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: static GCMarker *
michael@0: AsGCMarker(JSTracer *trc)
michael@0: {
michael@0:     JS_ASSERT(IS_GC_MARKING_TRACER(trc));
michael@0:     return static_cast<GCMarker *>(trc);
michael@0: }
michael@0: 
michael@0: template <typename T> bool ThingIsPermanentAtom(T *thing) { return false; }
michael@0: template <> bool ThingIsPermanentAtom<JSString>(JSString *str) { return str->isPermanentAtom(); }
michael@0: template <> bool ThingIsPermanentAtom<JSFlatString>(JSFlatString *str) { return str->isPermanentAtom(); }
michael@0: template <> bool ThingIsPermanentAtom<JSLinearString>(JSLinearString *str) { return str->isPermanentAtom(); }
michael@0: template <> bool ThingIsPermanentAtom<JSAtom>(JSAtom *atom) { return atom->isPermanent(); }
michael@0: template <> bool ThingIsPermanentAtom<PropertyName>(PropertyName *name) { return name->isPermanent(); }
michael@0: 
michael@0: template<typename T>
michael@0: static inline void
michael@0: CheckMarkedThing(JSTracer *trc, T *thing)
michael@0: {
michael@0: #ifdef DEBUG
michael@0:     JS_ASSERT(trc);
michael@0:     JS_ASSERT(thing);
michael@0: 
michael@0:     /* This function uses data that's not available in the nursery. */
michael@0:     if (IsInsideNursery(trc->runtime(), thing))
michael@0:         return;
michael@0: 
michael@0:     /*
michael@0:      * Permanent atoms are not associated with this runtime, but will be ignored
michael@0:      * during marking.
michael@0:      */
michael@0:     if (ThingIsPermanentAtom(thing))
michael@0:         return;
michael@0: 
michael@0:     JS_ASSERT(thing->zone());
michael@0:     JS_ASSERT(thing->zone()->runtimeFromMainThread() == trc->runtime());
michael@0:     JS_ASSERT(trc->hasTracingDetails());
michael@0: 
michael@0:     DebugOnly<JSRuntime *> rt = trc->runtime();
michael@0: 
michael@0:     JS_ASSERT_IF(IS_GC_MARKING_TRACER(trc) && rt->gcManipulatingDeadZones,
michael@0:                  !thing->zone()->scheduledForDestruction);
michael@0: 
michael@0:     JS_ASSERT(CurrentThreadCanAccessRuntime(rt));
michael@0: 
michael@0:     JS_ASSERT_IF(thing->zone()->requireGCTracer(),
michael@0:                  IS_GC_MARKING_TRACER(trc));
michael@0: 
michael@0:     JS_ASSERT(thing->isAligned());
michael@0: 
michael@0:     JS_ASSERT(MapTypeToTraceKind<T>::kind == GetGCThingTraceKind(thing));
michael@0: 
michael@0:     JS_ASSERT_IF(rt->gcStrictCompartmentChecking,
michael@0:                  thing->zone()->isCollecting() || rt->isAtomsZone(thing->zone()));
michael@0: 
michael@0:     JS_ASSERT_IF(IS_GC_MARKING_TRACER(trc) && AsGCMarker(trc)->getMarkColor() == GRAY,
michael@0:                  !thing->zone()->isGCMarkingBlack() || rt->isAtomsZone(thing->zone()));
michael@0: 
michael@0:     JS_ASSERT_IF(IS_GC_MARKING_TRACER(trc),
michael@0:                  !(thing->zone()->isGCSweeping() || thing->zone()->isGCFinished()));
michael@0: 
michael@0:     /*
michael@0:      * Try to assert that the thing is allocated.  This is complicated by the
michael@0:      * fact that allocated things may still contain the poison pattern if that
michael@0:      * part has not been overwritten, and that the free span list head in the
michael@0:      * ArenaHeader may not be synced with the real one in ArenaLists.
michael@0:      */
michael@0:     JS_ASSERT_IF(IsThingPoisoned(thing) && rt->isHeapBusy(),
michael@0:                  !InFreeList(thing->arenaHeader(), thing));
michael@0: #endif
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: static void
michael@0: MarkInternal(JSTracer *trc, T **thingp)
michael@0: {
michael@0:     JS_ASSERT(thingp);
michael@0:     T *thing = *thingp;
michael@0: 
michael@0:     CheckMarkedThing(trc, thing);
michael@0: 
michael@0:     if (!trc->callback) {
michael@0:         /*
michael@0:          * We may mark a Nursery thing outside the context of the
michael@0:          * MinorCollectionTracer because of a pre-barrier. The pre-barrier is
michael@0:          * not needed in this case because we perform a minor collection before
michael@0:          * each incremental slice.
michael@0:          */
michael@0:         if (IsInsideNursery(trc->runtime(), thing))
michael@0:             return;
michael@0: 
michael@0:         /*
michael@0:          * Don't mark permanent atoms, as they may be associated with another
michael@0:          * runtime. Note that PushMarkStack() also checks this, but the tests
michael@0:          * and maybeAlive write below should only be done on the main thread.
michael@0:          */
michael@0:         if (ThingIsPermanentAtom(thing))
michael@0:             return;
michael@0: 
michael@0:         /*
michael@0:          * Don't mark things outside a compartment if we are in a
michael@0:          * per-compartment GC.
michael@0:          */
michael@0:         if (!thing->zone()->isGCMarking())
michael@0:             return;
michael@0: 
michael@0:         PushMarkStack(AsGCMarker(trc), thing);
michael@0:         thing->zone()->maybeAlive = true;
michael@0:     } else {
michael@0:         trc->callback(trc, (void **)thingp, MapTypeToTraceKind<T>::kind);
michael@0:         trc->unsetTracingLocation();
michael@0:     }
michael@0: 
michael@0:     trc->clearTracingDetails();
michael@0: }
michael@0: 
michael@0: #define JS_ROOT_MARKING_ASSERT(trc)                                     \
michael@0:     JS_ASSERT_IF(IS_GC_MARKING_TRACER(trc),                             \
michael@0:                  trc->runtime()->gcIncrementalState == NO_INCREMENTAL ||  \
michael@0:                  trc->runtime()->gcIncrementalState == MARK_ROOTS);
michael@0: 
michael@0: namespace js {
michael@0: namespace gc {
michael@0: 
michael@0: template <typename T>
michael@0: void
michael@0: MarkUnbarriered(JSTracer *trc, T **thingp, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkInternal(trc, thingp);
michael@0: }
michael@0: 
michael@0: template <typename T>
michael@0: static void
michael@0: Mark(JSTracer *trc, BarrieredPtr<T> *thing, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkInternal(trc, thing->unsafeGet());
michael@0: }
michael@0: 
michael@0: void
michael@0: MarkPermanentAtom(JSTracer *trc, JSAtom *atom, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0: 
michael@0:     JS_ASSERT(atom->isPermanent());
michael@0: 
michael@0:     CheckMarkedThing(trc, atom);
michael@0: 
michael@0:     if (!trc->callback) {
michael@0:         // Atoms do not refer to other GC things so don't need to go on the mark stack.
michael@0:         // Additionally, PushMarkStack will ignore permanent atoms.
michael@0:         atom->markIfUnmarked();
michael@0:     } else {
michael@0:         void *thing = atom;
michael@0:         trc->callback(trc, &thing, JSTRACE_STRING);
michael@0:         JS_ASSERT(thing == atom);
michael@0:         trc->unsetTracingLocation();
michael@0:     }
michael@0: 
michael@0:     trc->clearTracingDetails();
michael@0: }
michael@0: 
michael@0: } /* namespace gc */
michael@0: } /* namespace js */
michael@0: 
michael@0: template <typename T>
michael@0: static void
michael@0: MarkRoot(JSTracer *trc, T **thingp, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     trc->setTracingName(name);
michael@0:     MarkInternal(trc, thingp);
michael@0: }
michael@0: 
michael@0: template <typename T>
michael@0: static void
michael@0: MarkRange(JSTracer *trc, size_t len, HeapPtr<T> *vec, const char *name)
michael@0: {
michael@0:     for (size_t i = 0; i < len; ++i) {
michael@0:         if (vec[i].get()) {
michael@0:             trc->setTracingIndex(name, i);
michael@0:             MarkInternal(trc, vec[i].unsafeGet());
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: template <typename T>
michael@0: static void
michael@0: MarkRootRange(JSTracer *trc, size_t len, T **vec, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     for (size_t i = 0; i < len; ++i) {
michael@0:         if (vec[i]) {
michael@0:             trc->setTracingIndex(name, i);
michael@0:             MarkInternal(trc, &vec[i]);
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: namespace js {
michael@0: namespace gc {
michael@0: 
michael@0: template <typename T>
michael@0: static bool
michael@0: IsMarked(T **thingp)
michael@0: {
michael@0:     JS_ASSERT(thingp);
michael@0:     JS_ASSERT(*thingp);
michael@0: #ifdef JSGC_GENERATIONAL
michael@0:     Nursery &nursery = (*thingp)->runtimeFromMainThread()->gcNursery;
michael@0:     if (nursery.isInside(*thingp))
michael@0:         return nursery.getForwardedPointer(thingp);
michael@0: #endif
michael@0:     Zone *zone = (*thingp)->tenuredZone();
michael@0:     if (!zone->isCollecting() || zone->isGCFinished())
michael@0:         return true;
michael@0:     return (*thingp)->isMarked();
michael@0: }
michael@0: 
michael@0: template <typename T>
michael@0: static bool
michael@0: IsAboutToBeFinalized(T **thingp)
michael@0: {
michael@0:     JS_ASSERT(thingp);
michael@0:     JS_ASSERT(*thingp);
michael@0: 
michael@0:     T *thing = *thingp;
michael@0:     JSRuntime *rt = thing->runtimeFromAnyThread();
michael@0: 
michael@0:     /* Permanent atoms are never finalized by non-owning runtimes. */
michael@0:     if (ThingIsPermanentAtom(thing) && !TlsPerThreadData.get()->associatedWith(rt))
michael@0:         return false;
michael@0: 
michael@0: #ifdef JSGC_GENERATIONAL
michael@0:     Nursery &nursery = rt->gcNursery;
michael@0:     JS_ASSERT_IF(!rt->isHeapMinorCollecting(), !nursery.isInside(thing));
michael@0:     if (rt->isHeapMinorCollecting()) {
michael@0:         if (nursery.isInside(thing))
michael@0:             return !nursery.getForwardedPointer(thingp);
michael@0:         return false;
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     if (!thing->tenuredZone()->isGCSweeping())
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * We should return false for things that have been allocated during
michael@0:      * incremental sweeping, but this possibility doesn't occur at the moment
michael@0:      * because this function is only called at the very start of the sweeping a
michael@0:      * compartment group and during minor gc. Rather than do the extra check,
michael@0:      * we just assert that it's not necessary.
michael@0:      */
michael@0:     JS_ASSERT_IF(!rt->isHeapMinorCollecting(), !thing->arenaHeader()->allocatedDuringIncremental);
michael@0: 
michael@0:     return !thing->isMarked();
michael@0: }
michael@0: 
michael@0: template <typename T>
michael@0: T *
michael@0: UpdateIfRelocated(JSRuntime *rt, T **thingp)
michael@0: {
michael@0:     JS_ASSERT(thingp);
michael@0: #ifdef JSGC_GENERATIONAL
michael@0:     if (*thingp && rt->isHeapMinorCollecting() && rt->gcNursery.isInside(*thingp))
michael@0:         rt->gcNursery.getForwardedPointer(thingp);
michael@0: #endif
michael@0:     return *thingp;
michael@0: }
michael@0: 
michael@0: #define DeclMarkerImpl(base, type)                                                                \
michael@0: void                                                                                              \
michael@0: Mark##base(JSTracer *trc, BarrieredPtr<type> *thing, const char *name)                            \
michael@0: {                                                                                                 \
michael@0:     Mark<type>(trc, thing, name);                                                                 \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: void                                                                                              \
michael@0: Mark##base##Root(JSTracer *trc, type **thingp, const char *name)                                  \
michael@0: {                                                                                                 \
michael@0:     MarkRoot<type>(trc, thingp, name);                                                            \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: void                                                                                              \
michael@0: Mark##base##Unbarriered(JSTracer *trc, type **thingp, const char *name)                           \
michael@0: {                                                                                                 \
michael@0:     MarkUnbarriered<type>(trc, thingp, name);                                                     \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: /* Explicitly instantiate MarkUnbarriered<type>. It is referenced from */                         \
michael@0: /* other translation units and the instantiation might otherwise get */                           \
michael@0: /* inlined away. */                                                                               \
michael@0: template void MarkUnbarriered<type>(JSTracer *, type **, const char *);                           \
michael@0:                                                                                                   \
michael@0: void                                                                                              \
michael@0: Mark##base##Range(JSTracer *trc, size_t len, HeapPtr<type> *vec, const char *name)                \
michael@0: {                                                                                                 \
michael@0:     MarkRange<type>(trc, len, vec, name);                                                         \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: void                                                                                              \
michael@0: Mark##base##RootRange(JSTracer *trc, size_t len, type **vec, const char *name)                    \
michael@0: {                                                                                                 \
michael@0:     MarkRootRange<type>(trc, len, vec, name);                                                     \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: bool                                                                                              \
michael@0: Is##base##Marked(type **thingp)                                                                   \
michael@0: {                                                                                                 \
michael@0:     return IsMarked<type>(thingp);                                                                \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: bool                                                                                              \
michael@0: Is##base##Marked(BarrieredPtr<type> *thingp)                                                      \
michael@0: {                                                                                                 \
michael@0:     return IsMarked<type>(thingp->unsafeGet());                                                   \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: bool                                                                                              \
michael@0: Is##base##AboutToBeFinalized(type **thingp)                                                       \
michael@0: {                                                                                                 \
michael@0:     return IsAboutToBeFinalized<type>(thingp);                                                    \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: bool                                                                                              \
michael@0: Is##base##AboutToBeFinalized(BarrieredPtr<type> *thingp)                                          \
michael@0: {                                                                                                 \
michael@0:     return IsAboutToBeFinalized<type>(thingp->unsafeGet());                                       \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: type *                                                                                            \
michael@0: Update##base##IfRelocated(JSRuntime *rt, BarrieredPtr<type> *thingp)                              \
michael@0: {                                                                                                 \
michael@0:     return UpdateIfRelocated<type>(rt, thingp->unsafeGet());                                      \
michael@0: }                                                                                                 \
michael@0:                                                                                                   \
michael@0: type *                                                                                            \
michael@0: Update##base##IfRelocated(JSRuntime *rt, type **thingp)                                           \
michael@0: {                                                                                                 \
michael@0:     return UpdateIfRelocated<type>(rt, thingp);                                                   \
michael@0: }
michael@0: 
michael@0: 
michael@0: DeclMarkerImpl(BaseShape, BaseShape)
michael@0: DeclMarkerImpl(BaseShape, UnownedBaseShape)
michael@0: DeclMarkerImpl(JitCode, jit::JitCode)
michael@0: DeclMarkerImpl(Object, ArgumentsObject)
michael@0: DeclMarkerImpl(Object, ArrayBufferObject)
michael@0: DeclMarkerImpl(Object, ArrayBufferViewObject)
michael@0: DeclMarkerImpl(Object, SharedArrayBufferObject)
michael@0: DeclMarkerImpl(Object, DebugScopeObject)
michael@0: DeclMarkerImpl(Object, GlobalObject)
michael@0: DeclMarkerImpl(Object, JSObject)
michael@0: DeclMarkerImpl(Object, JSFunction)
michael@0: DeclMarkerImpl(Object, ObjectImpl)
michael@0: DeclMarkerImpl(Object, ScopeObject)
michael@0: DeclMarkerImpl(Script, JSScript)
michael@0: DeclMarkerImpl(LazyScript, LazyScript)
michael@0: DeclMarkerImpl(Shape, Shape)
michael@0: DeclMarkerImpl(String, JSAtom)
michael@0: DeclMarkerImpl(String, JSString)
michael@0: DeclMarkerImpl(String, JSFlatString)
michael@0: DeclMarkerImpl(String, JSLinearString)
michael@0: DeclMarkerImpl(String, PropertyName)
michael@0: DeclMarkerImpl(TypeObject, js::types::TypeObject)
michael@0: 
michael@0: } /* namespace gc */
michael@0: } /* namespace js */
michael@0: 
michael@0: /*** Externally Typed Marking ***/
michael@0: 
michael@0: void
michael@0: gc::MarkKind(JSTracer *trc, void **thingp, JSGCTraceKind kind)
michael@0: {
michael@0:     JS_ASSERT(thingp);
michael@0:     JS_ASSERT(*thingp);
michael@0:     DebugOnly<Cell *> cell = static_cast<Cell *>(*thingp);
michael@0:     JS_ASSERT_IF(cell->isTenured(), kind == MapAllocToTraceKind(cell->tenuredGetAllocKind()));
michael@0:     switch (kind) {
michael@0:       case JSTRACE_OBJECT:
michael@0:         MarkInternal(trc, reinterpret_cast<JSObject **>(thingp));
michael@0:         break;
michael@0:       case JSTRACE_STRING:
michael@0:         MarkInternal(trc, reinterpret_cast<JSString **>(thingp));
michael@0:         break;
michael@0:       case JSTRACE_SCRIPT:
michael@0:         MarkInternal(trc, reinterpret_cast<JSScript **>(thingp));
michael@0:         break;
michael@0:       case JSTRACE_LAZY_SCRIPT:
michael@0:         MarkInternal(trc, reinterpret_cast<LazyScript **>(thingp));
michael@0:         break;
michael@0:       case JSTRACE_SHAPE:
michael@0:         MarkInternal(trc, reinterpret_cast<Shape **>(thingp));
michael@0:         break;
michael@0:       case JSTRACE_BASE_SHAPE:
michael@0:         MarkInternal(trc, reinterpret_cast<BaseShape **>(thingp));
michael@0:         break;
michael@0:       case JSTRACE_TYPE_OBJECT:
michael@0:         MarkInternal(trc, reinterpret_cast<types::TypeObject **>(thingp));
michael@0:         break;
michael@0:       case JSTRACE_JITCODE:
michael@0:         MarkInternal(trc, reinterpret_cast<jit::JitCode **>(thingp));
michael@0:         break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void
michael@0: MarkGCThingInternal(JSTracer *trc, void **thingp, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     JS_ASSERT(thingp);
michael@0:     if (!*thingp)
michael@0:         return;
michael@0:     MarkKind(trc, thingp, GetGCThingTraceKind(*thingp));
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkGCThingRoot(JSTracer *trc, void **thingp, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     MarkGCThingInternal(trc, thingp, name);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkGCThingUnbarriered(JSTracer *trc, void **thingp, const char *name)
michael@0: {
michael@0:     MarkGCThingInternal(trc, thingp, name);
michael@0: }
michael@0: 
michael@0: /*** ID Marking ***/
michael@0: 
michael@0: static inline void
michael@0: MarkIdInternal(JSTracer *trc, jsid *id)
michael@0: {
michael@0:     if (JSID_IS_STRING(*id)) {
michael@0:         JSString *str = JSID_TO_STRING(*id);
michael@0:         trc->setTracingLocation((void *)id);
michael@0:         MarkInternal(trc, &str);
michael@0:         *id = NON_INTEGER_ATOM_TO_JSID(reinterpret_cast<JSAtom *>(str));
michael@0:     } else if (MOZ_UNLIKELY(JSID_IS_OBJECT(*id))) {
michael@0:         JSObject *obj = JSID_TO_OBJECT(*id);
michael@0:         trc->setTracingLocation((void *)id);
michael@0:         MarkInternal(trc, &obj);
michael@0:         *id = OBJECT_TO_JSID(obj);
michael@0:     } else {
michael@0:         /* Unset realLocation manually if we do not call MarkInternal. */
michael@0:         trc->unsetTracingLocation();
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkId(JSTracer *trc, BarrieredId *id, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkIdInternal(trc, id->unsafeGet());
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkIdRoot(JSTracer *trc, jsid *id, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     trc->setTracingName(name);
michael@0:     MarkIdInternal(trc, id);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkIdUnbarriered(JSTracer *trc, jsid *id, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkIdInternal(trc, id);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkIdRange(JSTracer *trc, size_t len, HeapId *vec, const char *name)
michael@0: {
michael@0:     for (size_t i = 0; i < len; ++i) {
michael@0:         trc->setTracingIndex(name, i);
michael@0:         MarkIdInternal(trc, vec[i].unsafeGet());
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkIdRootRange(JSTracer *trc, size_t len, jsid *vec, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     for (size_t i = 0; i < len; ++i) {
michael@0:         trc->setTracingIndex(name, i);
michael@0:         MarkIdInternal(trc, &vec[i]);
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*** Value Marking ***/
michael@0: 
michael@0: static inline void
michael@0: MarkValueInternal(JSTracer *trc, Value *v)
michael@0: {
michael@0:     if (v->isMarkable()) {
michael@0:         JS_ASSERT(v->toGCThing());
michael@0:         void *thing = v->toGCThing();
michael@0:         trc->setTracingLocation((void *)v);
michael@0:         MarkKind(trc, &thing, v->gcKind());
michael@0:         if (v->isString())
michael@0:             v->setString((JSString *)thing);
michael@0:         else
michael@0:             v->setObjectOrNull((JSObject *)thing);
michael@0:     } else {
michael@0:         /* Unset realLocation manually if we do not call MarkInternal. */
michael@0:         trc->unsetTracingLocation();
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkValue(JSTracer *trc, BarrieredValue *v, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkValueInternal(trc, v->unsafeGet());
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkValueRoot(JSTracer *trc, Value *v, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     trc->setTracingName(name);
michael@0:     MarkValueInternal(trc, v);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkTypeRoot(JSTracer *trc, types::Type *v, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     trc->setTracingName(name);
michael@0:     if (v->isSingleObject()) {
michael@0:         JSObject *obj = v->singleObject();
michael@0:         MarkInternal(trc, &obj);
michael@0:         *v = types::Type::ObjectType(obj);
michael@0:     } else if (v->isTypeObject()) {
michael@0:         types::TypeObject *typeObj = v->typeObject();
michael@0:         MarkInternal(trc, &typeObj);
michael@0:         *v = types::Type::ObjectType(typeObj);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkValueRange(JSTracer *trc, size_t len, BarrieredValue *vec, const char *name)
michael@0: {
michael@0:     for (size_t i = 0; i < len; ++i) {
michael@0:         trc->setTracingIndex(name, i);
michael@0:         MarkValueInternal(trc, vec[i].unsafeGet());
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkValueRootRange(JSTracer *trc, size_t len, Value *vec, const char *name)
michael@0: {
michael@0:     JS_ROOT_MARKING_ASSERT(trc);
michael@0:     for (size_t i = 0; i < len; ++i) {
michael@0:         trc->setTracingIndex(name, i);
michael@0:         MarkValueInternal(trc, &vec[i]);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool
michael@0: gc::IsValueMarked(Value *v)
michael@0: {
michael@0:     JS_ASSERT(v->isMarkable());
michael@0:     bool rv;
michael@0:     if (v->isString()) {
michael@0:         JSString *str = (JSString *)v->toGCThing();
michael@0:         rv = IsMarked<JSString>(&str);
michael@0:         v->setString(str);
michael@0:     } else {
michael@0:         JSObject *obj = (JSObject *)v->toGCThing();
michael@0:         rv = IsMarked<JSObject>(&obj);
michael@0:         v->setObject(*obj);
michael@0:     }
michael@0:     return rv;
michael@0: }
michael@0: 
michael@0: bool
michael@0: gc::IsValueAboutToBeFinalized(Value *v)
michael@0: {
michael@0:     JS_ASSERT(v->isMarkable());
michael@0:     bool rv;
michael@0:     if (v->isString()) {
michael@0:         JSString *str = (JSString *)v->toGCThing();
michael@0:         rv = IsAboutToBeFinalized<JSString>(&str);
michael@0:         v->setString(str);
michael@0:     } else {
michael@0:         JSObject *obj = (JSObject *)v->toGCThing();
michael@0:         rv = IsAboutToBeFinalized<JSObject>(&obj);
michael@0:         v->setObject(*obj);
michael@0:     }
michael@0:     return rv;
michael@0: }
michael@0: 
michael@0: /*** Slot Marking ***/
michael@0: 
michael@0: bool
michael@0: gc::IsSlotMarked(HeapSlot *s)
michael@0: {
michael@0:     return IsMarked(s);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkSlot(JSTracer *trc, HeapSlot *s, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkValueInternal(trc, s->unsafeGet());
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkArraySlots(JSTracer *trc, size_t len, HeapSlot *vec, const char *name)
michael@0: {
michael@0:     for (size_t i = 0; i < len; ++i) {
michael@0:         trc->setTracingIndex(name, i);
michael@0:         MarkValueInternal(trc, vec[i].unsafeGet());
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkObjectSlots(JSTracer *trc, JSObject *obj, uint32_t start, uint32_t nslots)
michael@0: {
michael@0:     JS_ASSERT(obj->isNative());
michael@0:     for (uint32_t i = start; i < (start + nslots); ++i) {
michael@0:         trc->setTracingDetails(js_GetObjectSlotName, obj, i);
michael@0:         MarkValueInternal(trc, obj->nativeGetSlotRef(i).unsafeGet());
michael@0:     }
michael@0: }
michael@0: 
michael@0: static bool
michael@0: ShouldMarkCrossCompartment(JSTracer *trc, JSObject *src, Cell *cell)
michael@0: {
michael@0:     if (!IS_GC_MARKING_TRACER(trc))
michael@0:         return true;
michael@0: 
michael@0:     uint32_t color = AsGCMarker(trc)->getMarkColor();
michael@0:     JS_ASSERT(color == BLACK || color == GRAY);
michael@0: 
michael@0:     if (IsInsideNursery(trc->runtime(), cell)) {
michael@0:         JS_ASSERT(color == BLACK);
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     JS::Zone *zone = cell->tenuredZone();
michael@0:     if (color == BLACK) {
michael@0:         /*
michael@0:          * Having black->gray edges violates our promise to the cycle
michael@0:          * collector. This can happen if we're collecting a compartment and it
michael@0:          * has an edge to an uncollected compartment: it's possible that the
michael@0:          * source and destination of the cross-compartment edge should be gray,
michael@0:          * but the source was marked black by the conservative scanner.
michael@0:          */
michael@0:         if (cell->isMarked(GRAY)) {
michael@0:             JS_ASSERT(!zone->isCollecting());
michael@0:             trc->runtime()->gcFoundBlackGrayEdges = true;
michael@0:         }
michael@0:         return zone->isGCMarking();
michael@0:     } else {
michael@0:         if (zone->isGCMarkingBlack()) {
michael@0:             /*
michael@0:              * The destination compartment is being not being marked gray now,
michael@0:              * but it will be later, so record the cell so it can be marked gray
michael@0:              * at the appropriate time.
michael@0:              */
michael@0:             if (!cell->isMarked())
michael@0:                 DelayCrossCompartmentGrayMarking(src);
michael@0:             return false;
michael@0:         }
michael@0:         return zone->isGCMarkingGray();
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkCrossCompartmentObjectUnbarriered(JSTracer *trc, JSObject *src, JSObject **dst, const char *name)
michael@0: {
michael@0:     if (ShouldMarkCrossCompartment(trc, src, *dst))
michael@0:         MarkObjectUnbarriered(trc, dst, name);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkCrossCompartmentScriptUnbarriered(JSTracer *trc, JSObject *src, JSScript **dst,
michael@0:                                           const char *name)
michael@0: {
michael@0:     if (ShouldMarkCrossCompartment(trc, src, *dst))
michael@0:         MarkScriptUnbarriered(trc, dst, name);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkCrossCompartmentSlot(JSTracer *trc, JSObject *src, HeapSlot *dst, const char *name)
michael@0: {
michael@0:     if (dst->isMarkable() && ShouldMarkCrossCompartment(trc, src, (Cell *)dst->toGCThing()))
michael@0:         MarkSlot(trc, dst, name);
michael@0: }
michael@0: 
michael@0: /*** Special Marking ***/
michael@0: 
michael@0: void
michael@0: gc::MarkObject(JSTracer *trc, HeapPtr<GlobalObject, JSScript *> *thingp, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkInternal(trc, thingp->unsafeGet());
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkValueUnbarriered(JSTracer *trc, Value *v, const char *name)
michael@0: {
michael@0:     trc->setTracingName(name);
michael@0:     MarkValueInternal(trc, v);
michael@0: }
michael@0: 
michael@0: bool
michael@0: gc::IsCellMarked(Cell **thingp)
michael@0: {
michael@0:     return IsMarked<Cell>(thingp);
michael@0: }
michael@0: 
michael@0: bool
michael@0: gc::IsCellAboutToBeFinalized(Cell **thingp)
michael@0: {
michael@0:     return IsAboutToBeFinalized<Cell>(thingp);
michael@0: }
michael@0: 
michael@0: /*** Push Mark Stack ***/
michael@0: 
michael@0: #define JS_COMPARTMENT_ASSERT(rt, thing)                                \
michael@0:     JS_ASSERT((thing)->zone()->isGCMarking())
michael@0: 
michael@0: #define JS_COMPARTMENT_ASSERT_STR(rt, thing)                            \
michael@0:     JS_ASSERT((thing)->zone()->isGCMarking() ||                         \
michael@0:               (rt)->isAtomsZone((thing)->zone()));
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, ObjectImpl *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         gcmarker->pushObject(thing);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * PushMarkStack for BaseShape unpacks its children directly onto the mark
michael@0:  * stack. For a pre-barrier between incremental slices, this may result in
michael@0:  * objects in the nursery getting pushed onto the mark stack. It is safe to
michael@0:  * ignore these objects because they will be marked by the matching
michael@0:  * post-barrier during the minor GC at the start of each incremental slice.
michael@0:  */
michael@0: static void
michael@0: MaybePushMarkStackBetweenSlices(GCMarker *gcmarker, JSObject *thing)
michael@0: {
michael@0:     JSRuntime *rt = gcmarker->runtime();
michael@0:     JS_COMPARTMENT_ASSERT(rt, thing);
michael@0:     JS_ASSERT_IF(rt->isHeapBusy(), !IsInsideNursery(rt, thing));
michael@0: 
michael@0:     if (!IsInsideNursery(rt, thing) && thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         gcmarker->pushObject(thing);
michael@0: }
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, JSFunction *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         gcmarker->pushObject(thing);
michael@0: }
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, types::TypeObject *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         gcmarker->pushType(thing);
michael@0: }
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, JSScript *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     /*
michael@0:      * We mark scripts directly rather than pushing on the stack as they can
michael@0:      * refer to other scripts only indirectly (like via nested functions) and
michael@0:      * we cannot get to deep recursion.
michael@0:      */
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         MarkChildren(gcmarker, thing);
michael@0: }
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, LazyScript *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     /*
michael@0:      * We mark lazy scripts directly rather than pushing on the stack as they
michael@0:      * only refer to normal scripts and to strings, and cannot recurse.
michael@0:      */
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         MarkChildren(gcmarker, thing);
michael@0: }
michael@0: 
michael@0: static void
michael@0: ScanShape(GCMarker *gcmarker, Shape *shape);
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, Shape *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     /* We mark shapes directly rather than pushing on the stack. */
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         ScanShape(gcmarker, thing);
michael@0: }
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, jit::JitCode *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         gcmarker->pushJitCode(thing);
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: ScanBaseShape(GCMarker *gcmarker, BaseShape *base);
michael@0: 
michael@0: static void
michael@0: PushMarkStack(GCMarker *gcmarker, BaseShape *thing)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT(gcmarker->runtime(), thing);
michael@0:     JS_ASSERT(!IsInsideNursery(gcmarker->runtime(), thing));
michael@0: 
michael@0:     /* We mark base shapes directly rather than pushing on the stack. */
michael@0:     if (thing->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         ScanBaseShape(gcmarker, thing);
michael@0: }
michael@0: 
michael@0: static void
michael@0: ScanShape(GCMarker *gcmarker, Shape *shape)
michael@0: {
michael@0:   restart:
michael@0:     PushMarkStack(gcmarker, shape->base());
michael@0: 
michael@0:     const BarrieredId &id = shape->propidRef();
michael@0:     if (JSID_IS_STRING(id))
michael@0:         PushMarkStack(gcmarker, JSID_TO_STRING(id));
michael@0:     else if (MOZ_UNLIKELY(JSID_IS_OBJECT(id)))
michael@0:         PushMarkStack(gcmarker, JSID_TO_OBJECT(id));
michael@0: 
michael@0:     shape = shape->previous();
michael@0:     if (shape && shape->markIfUnmarked(gcmarker->getMarkColor()))
michael@0:         goto restart;
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: ScanBaseShape(GCMarker *gcmarker, BaseShape *base)
michael@0: {
michael@0:     base->assertConsistency();
michael@0: 
michael@0:     base->compartment()->mark();
michael@0: 
michael@0:     if (base->hasGetterObject())
michael@0:         MaybePushMarkStackBetweenSlices(gcmarker, base->getterObject());
michael@0: 
michael@0:     if (base->hasSetterObject())
michael@0:         MaybePushMarkStackBetweenSlices(gcmarker, base->setterObject());
michael@0: 
michael@0:     if (JSObject *parent = base->getObjectParent()) {
michael@0:         MaybePushMarkStackBetweenSlices(gcmarker, parent);
michael@0:     } else if (GlobalObject *global = base->compartment()->maybeGlobal()) {
michael@0:         PushMarkStack(gcmarker, global);
michael@0:     }
michael@0: 
michael@0:     if (JSObject *metadata = base->getObjectMetadata())
michael@0:         MaybePushMarkStackBetweenSlices(gcmarker, metadata);
michael@0: 
michael@0:     /*
michael@0:      * All children of the owned base shape are consistent with its
michael@0:      * unowned one, thus we do not need to trace through children of the
michael@0:      * unowned base shape.
michael@0:      */
michael@0:     if (base->isOwned()) {
michael@0:         UnownedBaseShape *unowned = base->baseUnowned();
michael@0:         JS_ASSERT(base->compartment() == unowned->compartment());
michael@0:         unowned->markIfUnmarked(gcmarker->getMarkColor());
michael@0:     }
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: ScanLinearString(GCMarker *gcmarker, JSLinearString *str)
michael@0: {
michael@0:     JS_COMPARTMENT_ASSERT_STR(gcmarker->runtime(), str);
michael@0:     JS_ASSERT(str->isMarked());
michael@0: 
michael@0:     /*
michael@0:      * Add extra asserts to confirm the static type to detect incorrect string
michael@0:      * mutations.
michael@0:      */
michael@0:     JS_ASSERT(str->JSString::isLinear());
michael@0:     while (str->hasBase()) {
michael@0:         str = str->base();
michael@0:         JS_ASSERT(str->JSString::isLinear());
michael@0:         if (str->isPermanentAtom())
michael@0:             break;
michael@0:         JS_COMPARTMENT_ASSERT_STR(gcmarker->runtime(), str);
michael@0:         if (!str->markIfUnmarked())
michael@0:             break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * The function tries to scan the whole rope tree using the marking stack as
michael@0:  * temporary storage. If that becomes full, the unscanned ropes are added to
michael@0:  * the delayed marking list. When the function returns, the marking stack is
michael@0:  * at the same depth as it was on entry. This way we avoid using tags when
michael@0:  * pushing ropes to the stack as ropes never leaks to other users of the
michael@0:  * stack. This also assumes that a rope can only point to other ropes or
michael@0:  * linear strings, it cannot refer to GC things of other types.
michael@0:  */
michael@0: static void
michael@0: ScanRope(GCMarker *gcmarker, JSRope *rope)
michael@0: {
michael@0:     ptrdiff_t savedPos = gcmarker->stack.position();
michael@0:     JS_DIAGNOSTICS_ASSERT(GetGCThingTraceKind(rope) == JSTRACE_STRING);
michael@0:     for (;;) {
michael@0:         JS_DIAGNOSTICS_ASSERT(GetGCThingTraceKind(rope) == JSTRACE_STRING);
michael@0:         JS_DIAGNOSTICS_ASSERT(rope->JSString::isRope());
michael@0:         JS_COMPARTMENT_ASSERT_STR(gcmarker->runtime(), rope);
michael@0:         JS_ASSERT(rope->isMarked());
michael@0:         JSRope *next = nullptr;
michael@0: 
michael@0:         JSString *right = rope->rightChild();
michael@0:         if (!right->isPermanentAtom() && right->markIfUnmarked()) {
michael@0:             if (right->isLinear())
michael@0:                 ScanLinearString(gcmarker, &right->asLinear());
michael@0:             else
michael@0:                 next = &right->asRope();
michael@0:         }
michael@0: 
michael@0:         JSString *left = rope->leftChild();
michael@0:         if (!left->isPermanentAtom() && left->markIfUnmarked()) {
michael@0:             if (left->isLinear()) {
michael@0:                 ScanLinearString(gcmarker, &left->asLinear());
michael@0:             } else {
michael@0:                 /*
michael@0:                  * When both children are ropes, set aside the right one to
michael@0:                  * scan it later.
michael@0:                  */
michael@0:                 if (next && !gcmarker->stack.push(reinterpret_cast<uintptr_t>(next)))
michael@0:                     gcmarker->delayMarkingChildren(next);
michael@0:                 next = &left->asRope();
michael@0:             }
michael@0:         }
michael@0:         if (next) {
michael@0:             rope = next;
michael@0:         } else if (savedPos != gcmarker->stack.position()) {
michael@0:             JS_ASSERT(savedPos < gcmarker->stack.position());
michael@0:             rope = reinterpret_cast<JSRope *>(gcmarker->stack.pop());
michael@0:         } else {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     JS_ASSERT(savedPos == gcmarker->stack.position());
michael@0:  }
michael@0: 
michael@0: static inline void
michael@0: ScanString(GCMarker *gcmarker, JSString *str)
michael@0: {
michael@0:     if (str->isLinear())
michael@0:         ScanLinearString(gcmarker, &str->asLinear());
michael@0:     else
michael@0:         ScanRope(gcmarker, &str->asRope());
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: PushMarkStack(GCMarker *gcmarker, JSString *str)
michael@0: {
michael@0:     // Permanent atoms might not be associated with this runtime.
michael@0:     if (str->isPermanentAtom())
michael@0:         return;
michael@0: 
michael@0:     JS_COMPARTMENT_ASSERT_STR(gcmarker->runtime(), str);
michael@0: 
michael@0:     /*
michael@0:      * As string can only refer to other strings we fully scan its GC graph
michael@0:      * using the explicit stack when navigating the rope tree to avoid
michael@0:      * dealing with strings on the stack in drainMarkStack.
michael@0:      */
michael@0:     if (str->markIfUnmarked())
michael@0:         ScanString(gcmarker, str);
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::MarkChildren(JSTracer *trc, JSObject *obj)
michael@0: {
michael@0:     obj->markChildren(trc);
michael@0: }
michael@0: 
michael@0: static void
michael@0: gc::MarkChildren(JSTracer *trc, JSString *str)
michael@0: {
michael@0:     if (str->hasBase())
michael@0:         str->markBase(trc);
michael@0:     else if (str->isRope())
michael@0:         str->asRope().markChildren(trc);
michael@0: }
michael@0: 
michael@0: static void
michael@0: gc::MarkChildren(JSTracer *trc, JSScript *script)
michael@0: {
michael@0:     script->markChildren(trc);
michael@0: }
michael@0: 
michael@0: static void
michael@0: gc::MarkChildren(JSTracer *trc, LazyScript *lazy)
michael@0: {
michael@0:     lazy->markChildren(trc);
michael@0: }
michael@0: 
michael@0: static void
michael@0: gc::MarkChildren(JSTracer *trc, Shape *shape)
michael@0: {
michael@0:     shape->markChildren(trc);
michael@0: }
michael@0: 
michael@0: static void
michael@0: gc::MarkChildren(JSTracer *trc, BaseShape *base)
michael@0: {
michael@0:     base->markChildren(trc);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This function is used by the cycle collector to trace through the
michael@0:  * children of a BaseShape (and its baseUnowned(), if any). The cycle
michael@0:  * collector does not directly care about BaseShapes, so only the
michael@0:  * getter, setter, and parent are marked. Furthermore, the parent is
michael@0:  * marked only if it isn't the same as prevParent, which will be
michael@0:  * updated to the current shape's parent.
michael@0:  */
michael@0: static inline void
michael@0: MarkCycleCollectorChildren(JSTracer *trc, BaseShape *base, JSObject **prevParent)
michael@0: {
michael@0:     JS_ASSERT(base);
michael@0: 
michael@0:     /*
michael@0:      * The cycle collector does not need to trace unowned base shapes,
michael@0:      * as they have the same getter, setter and parent as the original
michael@0:      * base shape.
michael@0:      */
michael@0:     base->assertConsistency();
michael@0: 
michael@0:     if (base->hasGetterObject()) {
michael@0:         JSObject *tmp = base->getterObject();
michael@0:         MarkObjectUnbarriered(trc, &tmp, "getter");
michael@0:         JS_ASSERT(tmp == base->getterObject());
michael@0:     }
michael@0: 
michael@0:     if (base->hasSetterObject()) {
michael@0:         JSObject *tmp = base->setterObject();
michael@0:         MarkObjectUnbarriered(trc, &tmp, "setter");
michael@0:         JS_ASSERT(tmp == base->setterObject());
michael@0:     }
michael@0: 
michael@0:     JSObject *parent = base->getObjectParent();
michael@0:     if (parent && parent != *prevParent) {
michael@0:         MarkObjectUnbarriered(trc, &parent, "parent");
michael@0:         JS_ASSERT(parent == base->getObjectParent());
michael@0:         *prevParent = parent;
michael@0:     }
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This function is used by the cycle collector to trace through a
michael@0:  * shape. The cycle collector does not care about shapes or base
michael@0:  * shapes, so those are not marked. Instead, any shapes or base shapes
michael@0:  * that are encountered have their children marked. Stack space is
michael@0:  * bounded. If two shapes in a row have the same parent pointer, the
michael@0:  * parent pointer will only be marked once.
michael@0:  */
michael@0: void
michael@0: gc::MarkCycleCollectorChildren(JSTracer *trc, Shape *shape)
michael@0: {
michael@0:     JSObject *prevParent = nullptr;
michael@0:     do {
michael@0:         MarkCycleCollectorChildren(trc, shape->base(), &prevParent);
michael@0:         MarkId(trc, &shape->propidRef(), "propid");
michael@0:         shape = shape->previous();
michael@0:     } while (shape);
michael@0: }
michael@0: 
michael@0: static void
michael@0: ScanTypeObject(GCMarker *gcmarker, types::TypeObject *type)
michael@0: {
michael@0:     unsigned count = type->getPropertyCount();
michael@0:     for (unsigned i = 0; i < count; i++) {
michael@0:         types::Property *prop = type->getProperty(i);
michael@0:         if (prop && JSID_IS_STRING(prop->id))
michael@0:             PushMarkStack(gcmarker, JSID_TO_STRING(prop->id));
michael@0:     }
michael@0: 
michael@0:     if (type->proto().isObject())
michael@0:         PushMarkStack(gcmarker, type->proto().toObject());
michael@0: 
michael@0:     if (type->singleton() && !type->lazy())
michael@0:         PushMarkStack(gcmarker, type->singleton());
michael@0: 
michael@0:     if (type->hasNewScript()) {
michael@0:         PushMarkStack(gcmarker, type->newScript()->fun);
michael@0:         PushMarkStack(gcmarker, type->newScript()->templateObject);
michael@0:     } else if (type->hasTypedObject()) {
michael@0:         PushMarkStack(gcmarker, type->typedObject()->descrHeapPtr());
michael@0:     }
michael@0: 
michael@0:     if (type->interpretedFunction)
michael@0:         PushMarkStack(gcmarker, type->interpretedFunction);
michael@0: }
michael@0: 
michael@0: static void
michael@0: gc::MarkChildren(JSTracer *trc, types::TypeObject *type)
michael@0: {
michael@0:     unsigned count = type->getPropertyCount();
michael@0:     for (unsigned i = 0; i < count; i++) {
michael@0:         types::Property *prop = type->getProperty(i);
michael@0:         if (prop)
michael@0:             MarkId(trc, &prop->id, "type_prop");
michael@0:     }
michael@0: 
michael@0:     if (type->proto().isObject())
michael@0:         MarkObject(trc, &type->protoRaw(), "type_proto");
michael@0: 
michael@0:     if (type->singleton() && !type->lazy())
michael@0:         MarkObject(trc, &type->singletonRaw(), "type_singleton");
michael@0: 
michael@0:     if (type->hasNewScript()) {
michael@0:         MarkObject(trc, &type->newScript()->fun, "type_new_function");
michael@0:         MarkObject(trc, &type->newScript()->templateObject, "type_new_template");
michael@0:     } else if (type->hasTypedObject()) {
michael@0:         MarkObject(trc, &type->typedObject()->descrHeapPtr(), "type_heap_ptr");
michael@0:     }
michael@0: 
michael@0:     if (type->interpretedFunction)
michael@0:         MarkObject(trc, &type->interpretedFunction, "type_function");
michael@0: }
michael@0: 
michael@0: static void
michael@0: gc::MarkChildren(JSTracer *trc, jit::JitCode *code)
michael@0: {
michael@0: #ifdef JS_ION
michael@0:     code->trace(trc);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: template<typename T>
michael@0: static void
michael@0: PushArenaTyped(GCMarker *gcmarker, ArenaHeader *aheader)
michael@0: {
michael@0:     for (CellIterUnderGC i(aheader); !i.done(); i.next())
michael@0:         PushMarkStack(gcmarker, i.get<T>());
michael@0: }
michael@0: 
michael@0: void
michael@0: gc::PushArena(GCMarker *gcmarker, ArenaHeader *aheader)
michael@0: {
michael@0:     switch (MapAllocToTraceKind(aheader->getAllocKind())) {
michael@0:       case JSTRACE_OBJECT:
michael@0:         PushArenaTyped<JSObject>(gcmarker, aheader);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_STRING:
michael@0:         PushArenaTyped<JSString>(gcmarker, aheader);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_SCRIPT:
michael@0:         PushArenaTyped<JSScript>(gcmarker, aheader);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_LAZY_SCRIPT:
michael@0:         PushArenaTyped<LazyScript>(gcmarker, aheader);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_SHAPE:
michael@0:         PushArenaTyped<js::Shape>(gcmarker, aheader);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_BASE_SHAPE:
michael@0:         PushArenaTyped<js::BaseShape>(gcmarker, aheader);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_TYPE_OBJECT:
michael@0:         PushArenaTyped<js::types::TypeObject>(gcmarker, aheader);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_JITCODE:
michael@0:         PushArenaTyped<js::jit::JitCode>(gcmarker, aheader);
michael@0:         break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: struct SlotArrayLayout
michael@0: {
michael@0:     union {
michael@0:         HeapSlot *end;
michael@0:         uintptr_t kind;
michael@0:     };
michael@0:     union {
michael@0:         HeapSlot *start;
michael@0:         uintptr_t index;
michael@0:     };
michael@0:     JSObject *obj;
michael@0: 
michael@0:     static void staticAsserts() {
michael@0:         /* This should have the same layout as three mark stack items. */
michael@0:         JS_STATIC_ASSERT(sizeof(SlotArrayLayout) == 3 * sizeof(uintptr_t));
michael@0:     }
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * During incremental GC, we return from drainMarkStack without having processed
michael@0:  * the entire stack. At that point, JS code can run and reallocate slot arrays
michael@0:  * that are stored on the stack. To prevent this from happening, we replace all
michael@0:  * ValueArrayTag stack items with SavedValueArrayTag. In the latter, slots
michael@0:  * pointers are replaced with slot indexes, and slot array end pointers are
michael@0:  * replaced with the kind of index (properties vs. elements).
michael@0:  */
michael@0: void
michael@0: GCMarker::saveValueRanges()
michael@0: {
michael@0:     for (uintptr_t *p = stack.tos_; p > stack.stack_; ) {
michael@0:         uintptr_t tag = *--p & StackTagMask;
michael@0:         if (tag == ValueArrayTag) {
michael@0:             *p &= ~StackTagMask;
michael@0:             p -= 2;
michael@0:             SlotArrayLayout *arr = reinterpret_cast<SlotArrayLayout *>(p);
michael@0:             JSObject *obj = arr->obj;
michael@0:             JS_ASSERT(obj->isNative());
michael@0: 
michael@0:             HeapSlot *vp = obj->getDenseElements();
michael@0:             if (arr->end == vp + obj->getDenseInitializedLength()) {
michael@0:                 JS_ASSERT(arr->start >= vp);
michael@0:                 arr->index = arr->start - vp;
michael@0:                 arr->kind = HeapSlot::Element;
michael@0:             } else {
michael@0:                 HeapSlot *vp = obj->fixedSlots();
michael@0:                 unsigned nfixed = obj->numFixedSlots();
michael@0:                 if (arr->start == arr->end) {
michael@0:                     arr->index = obj->slotSpan();
michael@0:                 } else if (arr->start >= vp && arr->start < vp + nfixed) {
michael@0:                     JS_ASSERT(arr->end == vp + Min(nfixed, obj->slotSpan()));
michael@0:                     arr->index = arr->start - vp;
michael@0:                 } else {
michael@0:                     JS_ASSERT(arr->start >= obj->slots &&
michael@0:                               arr->end == obj->slots + obj->slotSpan() - nfixed);
michael@0:                     arr->index = (arr->start - obj->slots) + nfixed;
michael@0:                 }
michael@0:                 arr->kind = HeapSlot::Slot;
michael@0:             }
michael@0:             p[2] |= SavedValueArrayTag;
michael@0:         } else if (tag == SavedValueArrayTag) {
michael@0:             p -= 2;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool
michael@0: GCMarker::restoreValueArray(JSObject *obj, void **vpp, void **endp)
michael@0: {
michael@0:     uintptr_t start = stack.pop();
michael@0:     HeapSlot::Kind kind = (HeapSlot::Kind) stack.pop();
michael@0: 
michael@0:     if (kind == HeapSlot::Element) {
michael@0:         if (!obj->is<ArrayObject>())
michael@0:             return false;
michael@0: 
michael@0:         uint32_t initlen = obj->getDenseInitializedLength();
michael@0:         HeapSlot *vp = obj->getDenseElements();
michael@0:         if (start < initlen) {
michael@0:             *vpp = vp + start;
michael@0:             *endp = vp + initlen;
michael@0:         } else {
michael@0:             /* The object shrunk, in which case no scanning is needed. */
michael@0:             *vpp = *endp = vp;
michael@0:         }
michael@0:     } else {
michael@0:         JS_ASSERT(kind == HeapSlot::Slot);
michael@0:         HeapSlot *vp = obj->fixedSlots();
michael@0:         unsigned nfixed = obj->numFixedSlots();
michael@0:         unsigned nslots = obj->slotSpan();
michael@0:         if (start < nslots) {
michael@0:             if (start < nfixed) {
michael@0:                 *vpp = vp + start;
michael@0:                 *endp = vp + Min(nfixed, nslots);
michael@0:             } else {
michael@0:                 *vpp = obj->slots + start - nfixed;
michael@0:                 *endp = obj->slots + nslots - nfixed;
michael@0:             }
michael@0:         } else {
michael@0:             /* The object shrunk, in which case no scanning is needed. */
michael@0:             *vpp = *endp = vp;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     JS_ASSERT(*vpp <= *endp);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: GCMarker::processMarkStackOther(uintptr_t tag, uintptr_t addr)
michael@0: {
michael@0:     if (tag == TypeTag) {
michael@0:         ScanTypeObject(this, reinterpret_cast<types::TypeObject *>(addr));
michael@0:     } else if (tag == SavedValueArrayTag) {
michael@0:         JS_ASSERT(!(addr & CellMask));
michael@0:         JSObject *obj = reinterpret_cast<JSObject *>(addr);
michael@0:         HeapValue *vp, *end;
michael@0:         if (restoreValueArray(obj, (void **)&vp, (void **)&end))
michael@0:             pushValueArray(obj, vp, end);
michael@0:         else
michael@0:             pushObject(obj);
michael@0:     } else if (tag == JitCodeTag) {
michael@0:         MarkChildren(this, reinterpret_cast<jit::JitCode *>(addr));
michael@0:     }
michael@0: }
michael@0: 
michael@0: inline void
michael@0: GCMarker::processMarkStackTop(SliceBudget &budget)
michael@0: {
michael@0:     /*
michael@0:      * The function uses explicit goto and implements the scanning of the
michael@0:      * object directly. It allows to eliminate the tail recursion and
michael@0:      * significantly improve the marking performance, see bug 641025.
michael@0:      */
michael@0:     HeapSlot *vp, *end;
michael@0:     JSObject *obj;
michael@0: 
michael@0:     uintptr_t addr = stack.pop();
michael@0:     uintptr_t tag = addr & StackTagMask;
michael@0:     addr &= ~StackTagMask;
michael@0: 
michael@0:     if (tag == ValueArrayTag) {
michael@0:         JS_STATIC_ASSERT(ValueArrayTag == 0);
michael@0:         JS_ASSERT(!(addr & CellMask));
michael@0:         obj = reinterpret_cast<JSObject *>(addr);
michael@0:         uintptr_t addr2 = stack.pop();
michael@0:         uintptr_t addr3 = stack.pop();
michael@0:         JS_ASSERT(addr2 <= addr3);
michael@0:         JS_ASSERT((addr3 - addr2) % sizeof(Value) == 0);
michael@0:         vp = reinterpret_cast<HeapSlot *>(addr2);
michael@0:         end = reinterpret_cast<HeapSlot *>(addr3);
michael@0:         goto scan_value_array;
michael@0:     }
michael@0: 
michael@0:     if (tag == ObjectTag) {
michael@0:         obj = reinterpret_cast<JSObject *>(addr);
michael@0:         JS_COMPARTMENT_ASSERT(runtime(), obj);
michael@0:         goto scan_obj;
michael@0:     }
michael@0: 
michael@0:     processMarkStackOther(tag, addr);
michael@0:     return;
michael@0: 
michael@0:   scan_value_array:
michael@0:     JS_ASSERT(vp <= end);
michael@0:     while (vp != end) {
michael@0:         const Value &v = *vp++;
michael@0:         if (v.isString()) {
michael@0:             JSString *str = v.toString();
michael@0:             if (!str->isPermanentAtom()) {
michael@0:                 JS_COMPARTMENT_ASSERT_STR(runtime(), str);
michael@0:                 JS_ASSERT(runtime()->isAtomsZone(str->zone()) || str->zone() == obj->zone());
michael@0:                 if (str->markIfUnmarked())
michael@0:                     ScanString(this, str);
michael@0:             }
michael@0:         } else if (v.isObject()) {
michael@0:             JSObject *obj2 = &v.toObject();
michael@0:             JS_COMPARTMENT_ASSERT(runtime(), obj2);
michael@0:             JS_ASSERT(obj->compartment() == obj2->compartment());
michael@0:             if (obj2->markIfUnmarked(getMarkColor())) {
michael@0:                 pushValueArray(obj, vp, end);
michael@0:                 obj = obj2;
michael@0:                 goto scan_obj;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     return;
michael@0: 
michael@0:   scan_obj:
michael@0:     {
michael@0:         JS_COMPARTMENT_ASSERT(runtime(), obj);
michael@0: 
michael@0:         budget.step();
michael@0:         if (budget.isOverBudget()) {
michael@0:             pushObject(obj);
michael@0:             return;
michael@0:         }
michael@0: 
michael@0:         types::TypeObject *type = obj->typeFromGC();
michael@0:         PushMarkStack(this, type);
michael@0: 
michael@0:         Shape *shape = obj->lastProperty();
michael@0:         PushMarkStack(this, shape);
michael@0: 
michael@0:         /* Call the trace hook if necessary. */
michael@0:         const Class *clasp = type->clasp();
michael@0:         if (clasp->trace) {
michael@0:             // Global objects all have the same trace hook. That hook is safe without barriers
michael@0:             // if the gloal has no custom trace hook of it's own, or has been moved to a different
michael@0:             // compartment, and so can't have one.
michael@0:             JS_ASSERT_IF(runtime()->gcMode() == JSGC_MODE_INCREMENTAL &&
michael@0:                          runtime()->gcIncrementalEnabled &&
michael@0:                          !(clasp->trace == JS_GlobalObjectTraceHook &&
michael@0:                            (!obj->compartment()->options().getTrace() ||
michael@0:                             !obj->isOwnGlobal())),
michael@0:                          clasp->flags & JSCLASS_IMPLEMENTS_BARRIERS);
michael@0:             clasp->trace(this, obj);
michael@0:         }
michael@0: 
michael@0:         if (!shape->isNative())
michael@0:             return;
michael@0: 
michael@0:         unsigned nslots = obj->slotSpan();
michael@0: 
michael@0:         if (!obj->hasEmptyElements()) {
michael@0:             vp = obj->getDenseElements();
michael@0:             end = vp + obj->getDenseInitializedLength();
michael@0:             if (!nslots)
michael@0:                 goto scan_value_array;
michael@0:             pushValueArray(obj, vp, end);
michael@0:         }
michael@0: 
michael@0:         vp = obj->fixedSlots();
michael@0:         if (obj->slots) {
michael@0:             unsigned nfixed = obj->numFixedSlots();
michael@0:             if (nslots > nfixed) {
michael@0:                 pushValueArray(obj, vp, vp + nfixed);
michael@0:                 vp = obj->slots;
michael@0:                 end = vp + (nslots - nfixed);
michael@0:                 goto scan_value_array;
michael@0:             }
michael@0:         }
michael@0:         JS_ASSERT(nslots <= obj->numFixedSlots());
michael@0:         end = vp + nslots;
michael@0:         goto scan_value_array;
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool
michael@0: GCMarker::drainMarkStack(SliceBudget &budget)
michael@0: {
michael@0: #ifdef DEBUG
michael@0:     JSRuntime *rt = runtime();
michael@0: 
michael@0:     struct AutoCheckCompartment {
michael@0:         JSRuntime *runtime;
michael@0:         AutoCheckCompartment(JSRuntime *rt) : runtime(rt) {
michael@0:             JS_ASSERT(!rt->gcStrictCompartmentChecking);
michael@0:             runtime->gcStrictCompartmentChecking = true;
michael@0:         }
michael@0:         ~AutoCheckCompartment() { runtime->gcStrictCompartmentChecking = false; }
michael@0:     } acc(rt);
michael@0: #endif
michael@0: 
michael@0:     if (budget.isOverBudget())
michael@0:         return false;
michael@0: 
michael@0:     for (;;) {
michael@0:         while (!stack.isEmpty()) {
michael@0:             processMarkStackTop(budget);
michael@0:             if (budget.isOverBudget()) {
michael@0:                 saveValueRanges();
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (!hasDelayedChildren())
michael@0:             break;
michael@0: 
michael@0:         /*
michael@0:          * Mark children of things that caused too deep recursion during the
michael@0:          * above tracing. Don't do this until we're done with everything
michael@0:          * else.
michael@0:          */
michael@0:         if (!markDelayedChildren(budget)) {
michael@0:             saveValueRanges();
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: js::TraceChildren(JSTracer *trc, void *thing, JSGCTraceKind kind)
michael@0: {
michael@0:     switch (kind) {
michael@0:       case JSTRACE_OBJECT:
michael@0:         MarkChildren(trc, static_cast<JSObject *>(thing));
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_STRING:
michael@0:         MarkChildren(trc, static_cast<JSString *>(thing));
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_SCRIPT:
michael@0:         MarkChildren(trc, static_cast<JSScript *>(thing));
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_LAZY_SCRIPT:
michael@0:         MarkChildren(trc, static_cast<LazyScript *>(thing));
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_SHAPE:
michael@0:         MarkChildren(trc, static_cast<Shape *>(thing));
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_JITCODE:
michael@0:         MarkChildren(trc, (js::jit::JitCode *)thing);
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_BASE_SHAPE:
michael@0:         MarkChildren(trc, static_cast<BaseShape *>(thing));
michael@0:         break;
michael@0: 
michael@0:       case JSTRACE_TYPE_OBJECT:
michael@0:         MarkChildren(trc, (types::TypeObject *)thing);
michael@0:         break;
michael@0:     }
michael@0: }
michael@0: 
michael@0: static void
michael@0: UnmarkGrayGCThing(void *thing)
michael@0: {
michael@0:     static_cast<js::gc::Cell *>(thing)->unmark(js::gc::GRAY);
michael@0: }
michael@0: 
michael@0: static void
michael@0: UnmarkGrayChildren(JSTracer *trc, void **thingp, JSGCTraceKind kind);
michael@0: 
michael@0: struct UnmarkGrayTracer : public JSTracer
michael@0: {
michael@0:     /*
michael@0:      * We set eagerlyTraceWeakMaps to false because the cycle collector will fix
michael@0:      * up any color mismatches involving weakmaps when it runs.
michael@0:      */
michael@0:     UnmarkGrayTracer(JSRuntime *rt)
michael@0:       : JSTracer(rt, UnmarkGrayChildren, DoNotTraceWeakMaps),
michael@0:         tracingShape(false),
michael@0:         previousShape(nullptr),
michael@0:         unmarkedAny(false)
michael@0:     {}
michael@0: 
michael@0:     UnmarkGrayTracer(JSTracer *trc, bool tracingShape)
michael@0:       : JSTracer(trc->runtime(), UnmarkGrayChildren, DoNotTraceWeakMaps),
michael@0:         tracingShape(tracingShape),
michael@0:         previousShape(nullptr),
michael@0:         unmarkedAny(false)
michael@0:     {}
michael@0: 
michael@0:     /* True iff we are tracing the immediate children of a shape. */
michael@0:     bool tracingShape;
michael@0: 
michael@0:     /* If tracingShape, shape child or nullptr. Otherwise, nullptr. */
michael@0:     void *previousShape;
michael@0: 
michael@0:     /* Whether we unmarked anything. */
michael@0:     bool unmarkedAny;
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * The GC and CC are run independently. Consequently, the following sequence of
michael@0:  * events can occur:
michael@0:  * 1. GC runs and marks an object gray.
michael@0:  * 2. Some JS code runs that creates a pointer from a JS root to the gray
michael@0:  *    object. If we re-ran a GC at this point, the object would now be black.
michael@0:  * 3. Now we run the CC. It may think it can collect the gray object, even
michael@0:  *    though it's reachable from the JS heap.
michael@0:  *
michael@0:  * To prevent this badness, we unmark the gray bit of an object when it is
michael@0:  * accessed by callers outside XPConnect. This would cause the object to go
michael@0:  * black in step 2 above. This must be done on everything reachable from the
michael@0:  * object being returned. The following code takes care of the recursive
michael@0:  * re-coloring.
michael@0:  *
michael@0:  * There is an additional complication for certain kinds of edges that are not
michael@0:  * contained explicitly in the source object itself, such as from a weakmap key
michael@0:  * to its value, and from an object being watched by a watchpoint to the
michael@0:  * watchpoint's closure. These "implicit edges" are represented in some other
michael@0:  * container object, such as the weakmap or the watchpoint itself. In these
michael@0:  * cases, calling unmark gray on an object won't find all of its children.
michael@0:  *
michael@0:  * Handling these implicit edges has two parts:
michael@0:  * - A special pass enumerating all of the containers that know about the
michael@0:  *   implicit edges to fix any black-gray edges that have been created. This
michael@0:  *   is implemented in nsXPConnect::FixWeakMappingGrayBits.
michael@0:  * - To prevent any incorrectly gray objects from escaping to live JS outside
michael@0:  *   of the containers, we must add unmark-graying read barriers to these
michael@0:  *   containers.
michael@0:  */
michael@0: static void
michael@0: UnmarkGrayChildren(JSTracer *trc, void **thingp, JSGCTraceKind kind)
michael@0: {
michael@0:     void *thing = *thingp;
michael@0:     int stackDummy;
michael@0:     if (!JS_CHECK_STACK_SIZE(trc->runtime()->mainThread.nativeStackLimit[StackForSystemCode], &stackDummy)) {
michael@0:         /*
michael@0:          * If we run out of stack, we take a more drastic measure: require that
michael@0:          * we GC again before the next CC.
michael@0:          */
michael@0:         trc->runtime()->gcGrayBitsValid = false;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     UnmarkGrayTracer *tracer = static_cast<UnmarkGrayTracer *>(trc);
michael@0:     if (!IsInsideNursery(trc->runtime(), thing)) {
michael@0:         if (!JS::GCThingIsMarkedGray(thing))
michael@0:             return;
michael@0: 
michael@0:         UnmarkGrayGCThing(thing);
michael@0:         tracer->unmarkedAny = true;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Trace children of |thing|. If |thing| and its parent are both shapes,
michael@0:      * |thing| will get saved to mPreviousShape without being traced. The parent
michael@0:      * will later trace |thing|. This is done to avoid increasing the stack
michael@0:      * depth during shape tracing. It is safe to do because a shape can only
michael@0:      * have one child that is a shape.
michael@0:      */
michael@0:     UnmarkGrayTracer childTracer(tracer, kind == JSTRACE_SHAPE);
michael@0: 
michael@0:     if (kind != JSTRACE_SHAPE) {
michael@0:         JS_TraceChildren(&childTracer, thing, kind);
michael@0:         JS_ASSERT(!childTracer.previousShape);
michael@0:         tracer->unmarkedAny |= childTracer.unmarkedAny;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     if (tracer->tracingShape) {
michael@0:         JS_ASSERT(!tracer->previousShape);
michael@0:         tracer->previousShape = thing;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     do {
michael@0:         JS_ASSERT(!JS::GCThingIsMarkedGray(thing));
michael@0:         JS_TraceChildren(&childTracer, thing, JSTRACE_SHAPE);
michael@0:         thing = childTracer.previousShape;
michael@0:         childTracer.previousShape = nullptr;
michael@0:     } while (thing);
michael@0:     tracer->unmarkedAny |= childTracer.unmarkedAny;
michael@0: }
michael@0: 
michael@0: JS_FRIEND_API(bool)
michael@0: JS::UnmarkGrayGCThingRecursively(void *thing, JSGCTraceKind kind)
michael@0: {
michael@0:     JS_ASSERT(kind != JSTRACE_SHAPE);
michael@0: 
michael@0:     JSRuntime *rt = static_cast<Cell *>(thing)->runtimeFromMainThread();
michael@0: 
michael@0:     bool unmarkedArg = false;
michael@0:     if (!IsInsideNursery(rt, thing)) {
michael@0:         if (!JS::GCThingIsMarkedGray(thing))
michael@0:             return false;
michael@0: 
michael@0:         UnmarkGrayGCThing(thing);
michael@0:         unmarkedArg = true;
michael@0:     }
michael@0: 
michael@0:     UnmarkGrayTracer trc(rt);
michael@0:     JS_TraceChildren(&trc, thing, kind);
michael@0: 
michael@0:     return unmarkedArg || trc.unmarkedAny;
michael@0: }