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