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: #ifndef js_Tracer_h
michael@0: #define js_Tracer_h
michael@0: 
michael@0: #include "mozilla/DebugOnly.h"
michael@0: 
michael@0: #include "js/GCAPI.h"
michael@0: #include "js/SliceBudget.h"
michael@0: #include "js/TracingAPI.h"
michael@0: 
michael@0: namespace js {
michael@0: class GCMarker;
michael@0: class ObjectImpl;
michael@0: namespace gc {
michael@0: class ArenaHeader;
michael@0: }
michael@0: namespace jit {
michael@0: class JitCode;
michael@0: }
michael@0: namespace types {
michael@0: class TypeObject;
michael@0: }
michael@0: 
michael@0: static const size_t NON_INCREMENTAL_MARK_STACK_BASE_CAPACITY = 4096;
michael@0: static const size_t INCREMENTAL_MARK_STACK_BASE_CAPACITY = 32768;
michael@0: 
michael@0: /*
michael@0:  * When the native stack is low, the GC does not call JS_TraceChildren to mark
michael@0:  * the reachable "children" of the thing. Rather the thing is put aside and
michael@0:  * JS_TraceChildren is called later with more space on the C stack.
michael@0:  *
michael@0:  * To implement such delayed marking of the children with minimal overhead for
michael@0:  * the normal case of sufficient native stack, the code adds a field per arena.
michael@0:  * The field markingDelay->link links all arenas with delayed things into a
michael@0:  * stack list with the pointer to stack top in GCMarker::unmarkedArenaStackTop.
michael@0:  * GCMarker::delayMarkingChildren adds arenas to the stack as necessary while
michael@0:  * markDelayedChildren pops the arenas from the stack until it empties.
michael@0:  */
michael@0: class MarkStack
michael@0: {
michael@0:     friend class GCMarker;
michael@0: 
michael@0:     uintptr_t *stack_;
michael@0:     uintptr_t *tos_;
michael@0:     uintptr_t *end_;
michael@0: 
michael@0:     // The capacity we start with and reset() to.
michael@0:     size_t baseCapacity_;
michael@0:     size_t maxCapacity_;
michael@0: 
michael@0:   public:
michael@0:     MarkStack(size_t maxCapacity)
michael@0:       : stack_(nullptr),
michael@0:         tos_(nullptr),
michael@0:         end_(nullptr),
michael@0:         baseCapacity_(0),
michael@0:         maxCapacity_(maxCapacity)
michael@0:     {}
michael@0: 
michael@0:     ~MarkStack() {
michael@0:         js_free(stack_);
michael@0:     }
michael@0: 
michael@0:     size_t capacity() { return end_ - stack_; }
michael@0: 
michael@0:     ptrdiff_t position() const { return tos_ - stack_; }
michael@0: 
michael@0:     void setStack(uintptr_t *stack, size_t tosIndex, size_t capacity) {
michael@0:         stack_ = stack;
michael@0:         tos_ = stack + tosIndex;
michael@0:         end_ = stack + capacity;
michael@0:     }
michael@0: 
michael@0:     bool init(JSGCMode gcMode);
michael@0: 
michael@0:     void setBaseCapacity(JSGCMode mode);
michael@0:     size_t maxCapacity() const { return maxCapacity_; }
michael@0:     void setMaxCapacity(size_t maxCapacity);
michael@0: 
michael@0:     bool push(uintptr_t item) {
michael@0:         if (tos_ == end_) {
michael@0:             if (!enlarge(1))
michael@0:                 return false;
michael@0:         }
michael@0:         JS_ASSERT(tos_ < end_);
michael@0:         *tos_++ = item;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     bool push(uintptr_t item1, uintptr_t item2, uintptr_t item3) {
michael@0:         uintptr_t *nextTos = tos_ + 3;
michael@0:         if (nextTos > end_) {
michael@0:             if (!enlarge(3))
michael@0:                 return false;
michael@0:             nextTos = tos_ + 3;
michael@0:         }
michael@0:         JS_ASSERT(nextTos <= end_);
michael@0:         tos_[0] = item1;
michael@0:         tos_[1] = item2;
michael@0:         tos_[2] = item3;
michael@0:         tos_ = nextTos;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     bool isEmpty() const {
michael@0:         return tos_ == stack_;
michael@0:     }
michael@0: 
michael@0:     uintptr_t pop() {
michael@0:         JS_ASSERT(!isEmpty());
michael@0:         return *--tos_;
michael@0:     }
michael@0: 
michael@0:     void reset();
michael@0: 
michael@0:     /* Grow the stack, ensuring there is space for at least count elements. */
michael@0:     bool enlarge(unsigned count);
michael@0: 
michael@0:     void setGCMode(JSGCMode gcMode);
michael@0: 
michael@0:     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
michael@0: };
michael@0: 
michael@0: class GCMarker : public JSTracer
michael@0: {
michael@0:   public:
michael@0:     explicit GCMarker(JSRuntime *rt);
michael@0:     bool init(JSGCMode gcMode);
michael@0: 
michael@0:     void setMaxCapacity(size_t maxCap) { stack.setMaxCapacity(maxCap); }
michael@0:     size_t maxCapacity() const { return stack.maxCapacity(); }
michael@0: 
michael@0:     void start();
michael@0:     void stop();
michael@0:     void reset();
michael@0: 
michael@0:     void pushObject(ObjectImpl *obj) {
michael@0:         pushTaggedPtr(ObjectTag, obj);
michael@0:     }
michael@0: 
michael@0:     void pushType(types::TypeObject *type) {
michael@0:         pushTaggedPtr(TypeTag, type);
michael@0:     }
michael@0: 
michael@0:     void pushJitCode(jit::JitCode *code) {
michael@0:         pushTaggedPtr(JitCodeTag, code);
michael@0:     }
michael@0: 
michael@0:     uint32_t getMarkColor() const {
michael@0:         return color;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Care must be taken changing the mark color from gray to black. The cycle
michael@0:      * collector depends on the invariant that there are no black to gray edges
michael@0:      * in the GC heap. This invariant lets the CC not trace through black
michael@0:      * objects. If this invariant is violated, the cycle collector may free
michael@0:      * objects that are still reachable.
michael@0:      */
michael@0:     void setMarkColorGray() {
michael@0:         JS_ASSERT(isDrained());
michael@0:         JS_ASSERT(color == gc::BLACK);
michael@0:         color = gc::GRAY;
michael@0:     }
michael@0: 
michael@0:     void setMarkColorBlack() {
michael@0:         JS_ASSERT(isDrained());
michael@0:         JS_ASSERT(color == gc::GRAY);
michael@0:         color = gc::BLACK;
michael@0:     }
michael@0: 
michael@0:     inline void delayMarkingArena(gc::ArenaHeader *aheader);
michael@0:     void delayMarkingChildren(const void *thing);
michael@0:     void markDelayedChildren(gc::ArenaHeader *aheader);
michael@0:     bool markDelayedChildren(SliceBudget &budget);
michael@0:     bool hasDelayedChildren() const {
michael@0:         return !!unmarkedArenaStackTop;
michael@0:     }
michael@0: 
michael@0:     bool isDrained() {
michael@0:         return isMarkStackEmpty() && !unmarkedArenaStackTop;
michael@0:     }
michael@0: 
michael@0:     bool drainMarkStack(SliceBudget &budget);
michael@0: 
michael@0:     /*
michael@0:      * Gray marking must be done after all black marking is complete. However,
michael@0:      * we do not have write barriers on XPConnect roots. Therefore, XPConnect
michael@0:      * roots must be accumulated in the first slice of incremental GC. We
michael@0:      * accumulate these roots in the each compartment's gcGrayRoots vector and
michael@0:      * then mark them later, after black marking is complete for each
michael@0:      * compartment. This accumulation can fail, but in that case we switch to
michael@0:      * non-incremental GC.
michael@0:      */
michael@0:     bool hasBufferedGrayRoots() const;
michael@0:     void startBufferingGrayRoots();
michael@0:     void endBufferingGrayRoots();
michael@0:     void resetBufferedGrayRoots();
michael@0:     void markBufferedGrayRoots(JS::Zone *zone);
michael@0: 
michael@0:     static void GrayCallback(JSTracer *trc, void **thing, JSGCTraceKind kind);
michael@0: 
michael@0:     void setGCMode(JSGCMode mode) { stack.setGCMode(mode); }
michael@0: 
michael@0:     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
michael@0: 
michael@0:     /* This is public exclusively for ScanRope. */
michael@0:     MarkStack stack;
michael@0: 
michael@0:   private:
michael@0: #ifdef DEBUG
michael@0:     void checkZone(void *p);
michael@0: #else
michael@0:     void checkZone(void *p) {}
michael@0: #endif
michael@0: 
michael@0:     /*
michael@0:      * We use a common mark stack to mark GC things of different types and use
michael@0:      * the explicit tags to distinguish them when it cannot be deduced from
michael@0:      * the context of push or pop operation.
michael@0:      */
michael@0:     enum StackTag {
michael@0:         ValueArrayTag,
michael@0:         ObjectTag,
michael@0:         TypeTag,
michael@0:         XmlTag,
michael@0:         SavedValueArrayTag,
michael@0:         JitCodeTag,
michael@0:         LastTag = JitCodeTag
michael@0:     };
michael@0: 
michael@0:     static const uintptr_t StackTagMask = 7;
michael@0:     static_assert(StackTagMask >= uintptr_t(LastTag), "The tag mask must subsume the tags.");
michael@0:     static_assert(StackTagMask <= gc::CellMask, "The tag mask must be embeddable in a Cell*.");
michael@0: 
michael@0:     void pushTaggedPtr(StackTag tag, void *ptr) {
michael@0:         checkZone(ptr);
michael@0:         uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
michael@0:         JS_ASSERT(!(addr & StackTagMask));
michael@0:         if (!stack.push(addr | uintptr_t(tag)))
michael@0:             delayMarkingChildren(ptr);
michael@0:     }
michael@0: 
michael@0:     void pushValueArray(JSObject *obj, void *start, void *end) {
michael@0:         checkZone(obj);
michael@0: 
michael@0:         JS_ASSERT(start <= end);
michael@0:         uintptr_t tagged = reinterpret_cast<uintptr_t>(obj) | GCMarker::ValueArrayTag;
michael@0:         uintptr_t startAddr = reinterpret_cast<uintptr_t>(start);
michael@0:         uintptr_t endAddr = reinterpret_cast<uintptr_t>(end);
michael@0: 
michael@0:         /*
michael@0:          * Push in the reverse order so obj will be on top. If we cannot push
michael@0:          * the array, we trigger delay marking for the whole object.
michael@0:          */
michael@0:         if (!stack.push(endAddr, startAddr, tagged))
michael@0:             delayMarkingChildren(obj);
michael@0:     }
michael@0: 
michael@0:     bool isMarkStackEmpty() {
michael@0:         return stack.isEmpty();
michael@0:     }
michael@0: 
michael@0:     bool restoreValueArray(JSObject *obj, void **vpp, void **endp);
michael@0:     void saveValueRanges();
michael@0:     inline void processMarkStackTop(SliceBudget &budget);
michael@0:     void processMarkStackOther(uintptr_t tag, uintptr_t addr);
michael@0: 
michael@0:     void appendGrayRoot(void *thing, JSGCTraceKind kind);
michael@0: 
michael@0:     /* The color is only applied to objects and functions. */
michael@0:     uint32_t color;
michael@0: 
michael@0:     /* Pointer to the top of the stack of arenas we are delaying marking on. */
michael@0:     js::gc::ArenaHeader *unmarkedArenaStackTop;
michael@0: 
michael@0:     /* Count of arenas that are currently in the stack. */
michael@0:     mozilla::DebugOnly<size_t> markLaterArenas;
michael@0: 
michael@0:     enum GrayBufferState {
michael@0:         GRAY_BUFFER_UNUSED,
michael@0:         GRAY_BUFFER_OK,
michael@0:         GRAY_BUFFER_FAILED
michael@0:     };
michael@0:     GrayBufferState grayBufferState;
michael@0: 
michael@0:     /* Assert that start and stop are called with correct ordering. */
michael@0:     mozilla::DebugOnly<bool> started;
michael@0: };
michael@0: 
michael@0: void
michael@0: SetMarkStackLimit(JSRuntime *rt, size_t limit);
michael@0: 
michael@0: } /* namespace js */
michael@0: 
michael@0: /*
michael@0:  * Macro to test if a traversal is the marking phase of the GC.
michael@0:  */
michael@0: #define IS_GC_MARKING_TRACER(trc) \
michael@0:     ((trc)->callback == nullptr || (trc)->callback == GCMarker::GrayCallback)
michael@0: 
michael@0: #endif /* js_Tracer_h */