1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/gc/Tracer.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,307 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef js_Tracer_h
1.11 +#define js_Tracer_h
1.12 +
1.13 +#include "mozilla/DebugOnly.h"
1.14 +
1.15 +#include "js/GCAPI.h"
1.16 +#include "js/SliceBudget.h"
1.17 +#include "js/TracingAPI.h"
1.18 +
1.19 +namespace js {
1.20 +class GCMarker;
1.21 +class ObjectImpl;
1.22 +namespace gc {
1.23 +class ArenaHeader;
1.24 +}
1.25 +namespace jit {
1.26 +class JitCode;
1.27 +}
1.28 +namespace types {
1.29 +class TypeObject;
1.30 +}
1.31 +
1.32 +static const size_t NON_INCREMENTAL_MARK_STACK_BASE_CAPACITY = 4096;
1.33 +static const size_t INCREMENTAL_MARK_STACK_BASE_CAPACITY = 32768;
1.34 +
1.35 +/*
1.36 + * When the native stack is low, the GC does not call JS_TraceChildren to mark
1.37 + * the reachable "children" of the thing. Rather the thing is put aside and
1.38 + * JS_TraceChildren is called later with more space on the C stack.
1.39 + *
1.40 + * To implement such delayed marking of the children with minimal overhead for
1.41 + * the normal case of sufficient native stack, the code adds a field per arena.
1.42 + * The field markingDelay->link links all arenas with delayed things into a
1.43 + * stack list with the pointer to stack top in GCMarker::unmarkedArenaStackTop.
1.44 + * GCMarker::delayMarkingChildren adds arenas to the stack as necessary while
1.45 + * markDelayedChildren pops the arenas from the stack until it empties.
1.46 + */
1.47 +class MarkStack
1.48 +{
1.49 + friend class GCMarker;
1.50 +
1.51 + uintptr_t *stack_;
1.52 + uintptr_t *tos_;
1.53 + uintptr_t *end_;
1.54 +
1.55 + // The capacity we start with and reset() to.
1.56 + size_t baseCapacity_;
1.57 + size_t maxCapacity_;
1.58 +
1.59 + public:
1.60 + MarkStack(size_t maxCapacity)
1.61 + : stack_(nullptr),
1.62 + tos_(nullptr),
1.63 + end_(nullptr),
1.64 + baseCapacity_(0),
1.65 + maxCapacity_(maxCapacity)
1.66 + {}
1.67 +
1.68 + ~MarkStack() {
1.69 + js_free(stack_);
1.70 + }
1.71 +
1.72 + size_t capacity() { return end_ - stack_; }
1.73 +
1.74 + ptrdiff_t position() const { return tos_ - stack_; }
1.75 +
1.76 + void setStack(uintptr_t *stack, size_t tosIndex, size_t capacity) {
1.77 + stack_ = stack;
1.78 + tos_ = stack + tosIndex;
1.79 + end_ = stack + capacity;
1.80 + }
1.81 +
1.82 + bool init(JSGCMode gcMode);
1.83 +
1.84 + void setBaseCapacity(JSGCMode mode);
1.85 + size_t maxCapacity() const { return maxCapacity_; }
1.86 + void setMaxCapacity(size_t maxCapacity);
1.87 +
1.88 + bool push(uintptr_t item) {
1.89 + if (tos_ == end_) {
1.90 + if (!enlarge(1))
1.91 + return false;
1.92 + }
1.93 + JS_ASSERT(tos_ < end_);
1.94 + *tos_++ = item;
1.95 + return true;
1.96 + }
1.97 +
1.98 + bool push(uintptr_t item1, uintptr_t item2, uintptr_t item3) {
1.99 + uintptr_t *nextTos = tos_ + 3;
1.100 + if (nextTos > end_) {
1.101 + if (!enlarge(3))
1.102 + return false;
1.103 + nextTos = tos_ + 3;
1.104 + }
1.105 + JS_ASSERT(nextTos <= end_);
1.106 + tos_[0] = item1;
1.107 + tos_[1] = item2;
1.108 + tos_[2] = item3;
1.109 + tos_ = nextTos;
1.110 + return true;
1.111 + }
1.112 +
1.113 + bool isEmpty() const {
1.114 + return tos_ == stack_;
1.115 + }
1.116 +
1.117 + uintptr_t pop() {
1.118 + JS_ASSERT(!isEmpty());
1.119 + return *--tos_;
1.120 + }
1.121 +
1.122 + void reset();
1.123 +
1.124 + /* Grow the stack, ensuring there is space for at least count elements. */
1.125 + bool enlarge(unsigned count);
1.126 +
1.127 + void setGCMode(JSGCMode gcMode);
1.128 +
1.129 + size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
1.130 +};
1.131 +
1.132 +class GCMarker : public JSTracer
1.133 +{
1.134 + public:
1.135 + explicit GCMarker(JSRuntime *rt);
1.136 + bool init(JSGCMode gcMode);
1.137 +
1.138 + void setMaxCapacity(size_t maxCap) { stack.setMaxCapacity(maxCap); }
1.139 + size_t maxCapacity() const { return stack.maxCapacity(); }
1.140 +
1.141 + void start();
1.142 + void stop();
1.143 + void reset();
1.144 +
1.145 + void pushObject(ObjectImpl *obj) {
1.146 + pushTaggedPtr(ObjectTag, obj);
1.147 + }
1.148 +
1.149 + void pushType(types::TypeObject *type) {
1.150 + pushTaggedPtr(TypeTag, type);
1.151 + }
1.152 +
1.153 + void pushJitCode(jit::JitCode *code) {
1.154 + pushTaggedPtr(JitCodeTag, code);
1.155 + }
1.156 +
1.157 + uint32_t getMarkColor() const {
1.158 + return color;
1.159 + }
1.160 +
1.161 + /*
1.162 + * Care must be taken changing the mark color from gray to black. The cycle
1.163 + * collector depends on the invariant that there are no black to gray edges
1.164 + * in the GC heap. This invariant lets the CC not trace through black
1.165 + * objects. If this invariant is violated, the cycle collector may free
1.166 + * objects that are still reachable.
1.167 + */
1.168 + void setMarkColorGray() {
1.169 + JS_ASSERT(isDrained());
1.170 + JS_ASSERT(color == gc::BLACK);
1.171 + color = gc::GRAY;
1.172 + }
1.173 +
1.174 + void setMarkColorBlack() {
1.175 + JS_ASSERT(isDrained());
1.176 + JS_ASSERT(color == gc::GRAY);
1.177 + color = gc::BLACK;
1.178 + }
1.179 +
1.180 + inline void delayMarkingArena(gc::ArenaHeader *aheader);
1.181 + void delayMarkingChildren(const void *thing);
1.182 + void markDelayedChildren(gc::ArenaHeader *aheader);
1.183 + bool markDelayedChildren(SliceBudget &budget);
1.184 + bool hasDelayedChildren() const {
1.185 + return !!unmarkedArenaStackTop;
1.186 + }
1.187 +
1.188 + bool isDrained() {
1.189 + return isMarkStackEmpty() && !unmarkedArenaStackTop;
1.190 + }
1.191 +
1.192 + bool drainMarkStack(SliceBudget &budget);
1.193 +
1.194 + /*
1.195 + * Gray marking must be done after all black marking is complete. However,
1.196 + * we do not have write barriers on XPConnect roots. Therefore, XPConnect
1.197 + * roots must be accumulated in the first slice of incremental GC. We
1.198 + * accumulate these roots in the each compartment's gcGrayRoots vector and
1.199 + * then mark them later, after black marking is complete for each
1.200 + * compartment. This accumulation can fail, but in that case we switch to
1.201 + * non-incremental GC.
1.202 + */
1.203 + bool hasBufferedGrayRoots() const;
1.204 + void startBufferingGrayRoots();
1.205 + void endBufferingGrayRoots();
1.206 + void resetBufferedGrayRoots();
1.207 + void markBufferedGrayRoots(JS::Zone *zone);
1.208 +
1.209 + static void GrayCallback(JSTracer *trc, void **thing, JSGCTraceKind kind);
1.210 +
1.211 + void setGCMode(JSGCMode mode) { stack.setGCMode(mode); }
1.212 +
1.213 + size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
1.214 +
1.215 + /* This is public exclusively for ScanRope. */
1.216 + MarkStack stack;
1.217 +
1.218 + private:
1.219 +#ifdef DEBUG
1.220 + void checkZone(void *p);
1.221 +#else
1.222 + void checkZone(void *p) {}
1.223 +#endif
1.224 +
1.225 + /*
1.226 + * We use a common mark stack to mark GC things of different types and use
1.227 + * the explicit tags to distinguish them when it cannot be deduced from
1.228 + * the context of push or pop operation.
1.229 + */
1.230 + enum StackTag {
1.231 + ValueArrayTag,
1.232 + ObjectTag,
1.233 + TypeTag,
1.234 + XmlTag,
1.235 + SavedValueArrayTag,
1.236 + JitCodeTag,
1.237 + LastTag = JitCodeTag
1.238 + };
1.239 +
1.240 + static const uintptr_t StackTagMask = 7;
1.241 + static_assert(StackTagMask >= uintptr_t(LastTag), "The tag mask must subsume the tags.");
1.242 + static_assert(StackTagMask <= gc::CellMask, "The tag mask must be embeddable in a Cell*.");
1.243 +
1.244 + void pushTaggedPtr(StackTag tag, void *ptr) {
1.245 + checkZone(ptr);
1.246 + uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
1.247 + JS_ASSERT(!(addr & StackTagMask));
1.248 + if (!stack.push(addr | uintptr_t(tag)))
1.249 + delayMarkingChildren(ptr);
1.250 + }
1.251 +
1.252 + void pushValueArray(JSObject *obj, void *start, void *end) {
1.253 + checkZone(obj);
1.254 +
1.255 + JS_ASSERT(start <= end);
1.256 + uintptr_t tagged = reinterpret_cast<uintptr_t>(obj) | GCMarker::ValueArrayTag;
1.257 + uintptr_t startAddr = reinterpret_cast<uintptr_t>(start);
1.258 + uintptr_t endAddr = reinterpret_cast<uintptr_t>(end);
1.259 +
1.260 + /*
1.261 + * Push in the reverse order so obj will be on top. If we cannot push
1.262 + * the array, we trigger delay marking for the whole object.
1.263 + */
1.264 + if (!stack.push(endAddr, startAddr, tagged))
1.265 + delayMarkingChildren(obj);
1.266 + }
1.267 +
1.268 + bool isMarkStackEmpty() {
1.269 + return stack.isEmpty();
1.270 + }
1.271 +
1.272 + bool restoreValueArray(JSObject *obj, void **vpp, void **endp);
1.273 + void saveValueRanges();
1.274 + inline void processMarkStackTop(SliceBudget &budget);
1.275 + void processMarkStackOther(uintptr_t tag, uintptr_t addr);
1.276 +
1.277 + void appendGrayRoot(void *thing, JSGCTraceKind kind);
1.278 +
1.279 + /* The color is only applied to objects and functions. */
1.280 + uint32_t color;
1.281 +
1.282 + /* Pointer to the top of the stack of arenas we are delaying marking on. */
1.283 + js::gc::ArenaHeader *unmarkedArenaStackTop;
1.284 +
1.285 + /* Count of arenas that are currently in the stack. */
1.286 + mozilla::DebugOnly<size_t> markLaterArenas;
1.287 +
1.288 + enum GrayBufferState {
1.289 + GRAY_BUFFER_UNUSED,
1.290 + GRAY_BUFFER_OK,
1.291 + GRAY_BUFFER_FAILED
1.292 + };
1.293 + GrayBufferState grayBufferState;
1.294 +
1.295 + /* Assert that start and stop are called with correct ordering. */
1.296 + mozilla::DebugOnly<bool> started;
1.297 +};
1.298 +
1.299 +void
1.300 +SetMarkStackLimit(JSRuntime *rt, size_t limit);
1.301 +
1.302 +} /* namespace js */
1.303 +
1.304 +/*
1.305 + * Macro to test if a traversal is the marking phase of the GC.
1.306 + */
1.307 +#define IS_GC_MARKING_TRACER(trc) \
1.308 + ((trc)->callback == nullptr || (trc)->callback == GCMarker::GrayCallback)
1.309 +
1.310 +#endif /* js_Tracer_h */
