Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
3 : * This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef gc_Marking_h
8 : #define gc_Marking_h
9 :
10 : #include "mozilla/HashFunctions.h"
11 : #include "mozilla/Move.h"
12 :
13 : #include "jsfriendapi.h"
14 :
15 : #include "ds/OrderedHashTable.h"
16 : #include "gc/Heap.h"
17 : #include "gc/Tracer.h"
18 : #include "js/GCAPI.h"
19 : #include "js/HeapAPI.h"
20 : #include "js/SliceBudget.h"
21 : #include "js/TracingAPI.h"
22 : #include "threading/ProtectedData.h"
23 : #include "vm/TaggedProto.h"
24 :
25 : class JSLinearString;
26 : class JSRope;
27 : namespace js {
28 : class BaseShape;
29 : class GCMarker;
30 : class LazyScript;
31 : class NativeObject;
32 : class ObjectGroup;
33 : class WeakMapBase;
34 : namespace gc {
35 : class Arena;
36 : } // namespace gc
37 : namespace jit {
38 : class JitCode;
39 : } // namespace jit
40 :
41 : static const size_t NON_INCREMENTAL_MARK_STACK_BASE_CAPACITY = 4096;
42 : static const size_t INCREMENTAL_MARK_STACK_BASE_CAPACITY = 32768;
43 :
44 : namespace gc {
45 :
46 : class MarkStackIter;
47 :
48 : /*
49 : * When the native stack is low, the GC does not call js::TraceChildren to mark
50 : * the reachable "children" of the thing. Rather the thing is put aside and
51 : * js::TraceChildren is called later with more space on the C stack.
52 : *
53 : * To implement such delayed marking of the children with minimal overhead for
54 : * the normal case of sufficient native stack, the code adds a field per arena.
55 : * The field markingDelay->link links all arenas with delayed things into a
56 : * stack list with the pointer to stack top in GCMarker::unmarkedArenaStackTop.
57 : * GCMarker::delayMarkingChildren adds arenas to the stack as necessary while
58 : * markDelayedChildren pops the arenas from the stack until it empties.
59 : */
60 : class MarkStack
61 : {
62 : public:
63 : /*
64 : * We use a common mark stack to mark GC things of different types and use
65 : * the explicit tags to distinguish them when it cannot be deduced from
66 : * the context of push or pop operation.
67 : */
68 : enum Tag {
69 : ValueArrayTag,
70 : ObjectTag,
71 : GroupTag,
72 : SavedValueArrayTag,
73 : JitCodeTag,
74 : ScriptTag,
75 : TempRopeTag,
76 :
77 : LastTag = TempRopeTag
78 : };
79 :
80 : static const uintptr_t TagMask = 7;
81 : static_assert(TagMask >= uintptr_t(LastTag), "The tag mask must subsume the tags.");
82 : static_assert(TagMask <= gc::CellAlignMask, "The tag mask must be embeddable in a Cell*.");
83 :
84 : class TaggedPtr
85 : {
86 : uintptr_t bits;
87 :
88 : Cell* ptr() const;
89 :
90 : public:
91 : TaggedPtr(Tag tag, Cell* ptr);
92 : Tag tag() const;
93 : template <typename T> T* as() const;
94 : JSObject* asValueArrayObject() const;
95 : JSObject* asSavedValueArrayObject() const;
96 : JSRope* asTempRope() const;
97 : };
98 :
99 : struct ValueArray
100 : {
101 : ValueArray(JSObject* obj, HeapSlot* start, HeapSlot* end);
102 :
103 : HeapSlot* end;
104 : HeapSlot* start;
105 : TaggedPtr ptr;
106 : };
107 :
108 : struct SavedValueArray
109 : {
110 : SavedValueArray(JSObject* obj, size_t index, HeapSlot::Kind kind);
111 :
112 : uintptr_t kind;
113 : uintptr_t index;
114 : TaggedPtr ptr;
115 : };
116 :
117 : explicit MarkStack(size_t maxCapacity);
118 : ~MarkStack();
119 :
120 0 : size_t capacity() { return end_ - stack_; }
121 :
122 995 : size_t position() const {
123 995 : auto result = tos_ - stack_;
124 995 : MOZ_ASSERT(result >= 0);
125 995 : return size_t(result);
126 : }
127 :
128 : void setStack(TaggedPtr* stack, size_t tosIndex, size_t capacity);
129 :
130 : MOZ_MUST_USE bool init(JSGCMode gcMode);
131 :
132 : void setBaseCapacity(JSGCMode mode);
133 0 : size_t maxCapacity() const { return maxCapacity_; }
134 : void setMaxCapacity(size_t maxCapacity);
135 :
136 : template <typename T>
137 : MOZ_MUST_USE bool push(T* ptr);
138 : MOZ_MUST_USE bool push(JSObject* obj, HeapSlot* start, HeapSlot* end);
139 : MOZ_MUST_USE bool push(const ValueArray& array);
140 : MOZ_MUST_USE bool push(const SavedValueArray& array);
141 :
142 : // GCMarker::eagerlyMarkChildren uses unused marking stack as temporary
143 : // storage to hold rope pointers.
144 : MOZ_MUST_USE bool pushTempRope(JSRope* ptr);
145 :
146 9407 : bool isEmpty() const {
147 9407 : return tos_ == stack_;
148 : }
149 :
150 : Tag peekTag() const;
151 : TaggedPtr popPtr();
152 : ValueArray popValueArray();
153 : SavedValueArray popSavedValueArray();
154 :
155 : void reset();
156 :
157 : void setGCMode(JSGCMode gcMode);
158 :
159 : size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
160 :
161 : private:
162 : MOZ_MUST_USE bool ensureSpace(size_t count);
163 :
164 : /* Grow the stack, ensuring there is space for at least count elements. */
165 : MOZ_MUST_USE bool enlarge(size_t count);
166 :
167 : const TaggedPtr& peekPtr() const;
168 : MOZ_MUST_USE bool pushTaggedPtr(Tag tag, Cell* ptr);
169 :
170 : ActiveThreadData<TaggedPtr*> stack_;
171 : ActiveThreadData<TaggedPtr*> tos_;
172 : ActiveThreadData<TaggedPtr*> end_;
173 :
174 : // The capacity we start with and reset() to.
175 : ActiveThreadData<size_t> baseCapacity_;
176 : ActiveThreadData<size_t> maxCapacity_;
177 :
178 : #ifdef DEBUG
179 : mutable size_t iteratorCount_;
180 : #endif
181 :
182 : friend class MarkStackIter;
183 : };
184 :
185 : class MarkStackIter
186 : {
187 : const MarkStack& stack_;
188 : MarkStack::TaggedPtr* pos_;
189 :
190 : public:
191 : explicit MarkStackIter(const MarkStack& stack);
192 : ~MarkStackIter();
193 :
194 : bool done() const;
195 : MarkStack::Tag peekTag() const;
196 : MarkStack::TaggedPtr peekPtr() const;
197 : MarkStack::ValueArray peekValueArray() const;
198 : void next();
199 : void nextPtr();
200 : void nextArray();
201 :
202 : // Mutate the current ValueArray to a SavedValueArray.
203 : void saveValueArray(NativeObject* obj, uintptr_t index, HeapSlot::Kind kind);
204 :
205 : private:
206 : size_t position() const;
207 : };
208 :
209 : struct WeakKeyTableHashPolicy {
210 : typedef JS::GCCellPtr Lookup;
211 0 : static HashNumber hash(const Lookup& v, const mozilla::HashCodeScrambler&) {
212 0 : return mozilla::HashGeneric(v.asCell());
213 : }
214 0 : static bool match(const JS::GCCellPtr& k, const Lookup& l) { return k == l; }
215 0 : static bool isEmpty(const JS::GCCellPtr& v) { return !v; }
216 : static void makeEmpty(JS::GCCellPtr* vp) { *vp = nullptr; }
217 : };
218 :
219 : struct WeakMarkable {
220 : WeakMapBase* weakmap;
221 : JS::GCCellPtr key;
222 :
223 0 : WeakMarkable(WeakMapBase* weakmapArg, JS::GCCellPtr keyArg)
224 0 : : weakmap(weakmapArg), key(keyArg) {}
225 : };
226 :
227 : using WeakEntryVector = Vector<WeakMarkable, 2, js::SystemAllocPolicy>;
228 :
229 : using WeakKeyTable = OrderedHashMap<JS::GCCellPtr,
230 : WeakEntryVector,
231 : WeakKeyTableHashPolicy,
232 : js::SystemAllocPolicy>;
233 :
234 : } /* namespace gc */
235 :
236 0 : class GCMarker : public JSTracer
237 : {
238 : public:
239 : explicit GCMarker(JSRuntime* rt);
240 : MOZ_MUST_USE bool init(JSGCMode gcMode);
241 :
242 0 : void setMaxCapacity(size_t maxCap) { stack.setMaxCapacity(maxCap); }
243 0 : size_t maxCapacity() const { return stack.maxCapacity(); }
244 :
245 : void start();
246 : void stop();
247 : void reset();
248 :
249 : // Mark the given GC thing and traverse its children at some point.
250 : template <typename T> void traverse(T thing);
251 :
252 : // Calls traverse on target after making additional assertions.
253 : template <typename S, typename T> void traverseEdge(S source, T* target);
254 : template <typename S, typename T> void traverseEdge(S source, const T& target);
255 :
256 : // Notes a weak graph edge for later sweeping.
257 : template <typename T> void noteWeakEdge(T* edge);
258 :
259 : /*
260 : * Care must be taken changing the mark color from gray to black. The cycle
261 : * collector depends on the invariant that there are no black to gray edges
262 : * in the GC heap. This invariant lets the CC not trace through black
263 : * objects. If this invariant is violated, the cycle collector may free
264 : * objects that are still reachable.
265 : */
266 0 : void setMarkColorGray() {
267 0 : MOZ_ASSERT(isDrained());
268 0 : MOZ_ASSERT(color == gc::MarkColor::Black);
269 0 : color = gc::MarkColor::Gray;
270 0 : }
271 0 : void setMarkColorBlack() {
272 0 : MOZ_ASSERT(isDrained());
273 0 : MOZ_ASSERT(color == gc::MarkColor::Gray);
274 0 : color = gc::MarkColor::Black;
275 0 : }
276 82944 : gc::MarkColor markColor() const { return color; }
277 :
278 : void enterWeakMarkingMode();
279 : void leaveWeakMarkingMode();
280 0 : void abortLinearWeakMarking() {
281 0 : leaveWeakMarkingMode();
282 0 : linearWeakMarkingDisabled_ = true;
283 0 : }
284 :
285 : void delayMarkingArena(gc::Arena* arena);
286 : void delayMarkingChildren(const void* thing);
287 : void markDelayedChildren(gc::Arena* arena);
288 : MOZ_MUST_USE bool markDelayedChildren(SliceBudget& budget);
289 0 : bool hasDelayedChildren() const {
290 0 : return !!unmarkedArenaStackTop;
291 : }
292 :
293 0 : bool isDrained() {
294 0 : return isMarkStackEmpty() && !unmarkedArenaStackTop;
295 : }
296 :
297 : MOZ_MUST_USE bool drainMarkStack(SliceBudget& budget);
298 :
299 4 : void setGCMode(JSGCMode mode) { stack.setGCMode(mode); }
300 :
301 : size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
302 :
303 : #ifdef DEBUG
304 :
305 41837 : bool shouldCheckCompartments() { return strictCompartmentChecking; }
306 :
307 : Zone* stackContainsCrossZonePointerTo(const gc::Cell* cell) const;
308 :
309 : #endif
310 :
311 : void markEphemeronValues(gc::Cell* markedCell, gc::WeakEntryVector& entry);
312 :
313 75883 : static GCMarker* fromTracer(JSTracer* trc) {
314 75883 : MOZ_ASSERT(trc->isMarkingTracer());
315 75883 : return static_cast<GCMarker*>(trc);
316 : }
317 :
318 : private:
319 : #ifdef DEBUG
320 : void checkZone(void* p);
321 : #else
322 : void checkZone(void* p) {}
323 : #endif
324 :
325 : // Push an object onto the stack for later tracing and assert that it has
326 : // already been marked.
327 : inline void repush(JSObject* obj);
328 :
329 : template <typename T> void markAndTraceChildren(T* thing);
330 : template <typename T> void markAndPush(T* thing);
331 : template <typename T> void markAndScan(T* thing);
332 : template <typename T> void markImplicitEdgesHelper(T oldThing);
333 : template <typename T> void markImplicitEdges(T* oldThing);
334 : void eagerlyMarkChildren(JSLinearString* str);
335 : void eagerlyMarkChildren(JSRope* rope);
336 : void eagerlyMarkChildren(JSString* str);
337 : void eagerlyMarkChildren(LazyScript *thing);
338 : void eagerlyMarkChildren(Shape* shape);
339 : void eagerlyMarkChildren(Scope* scope);
340 : void lazilyMarkChildren(ObjectGroup* group);
341 :
342 : // We may not have concrete types yet, so this has to be outside the header.
343 : template <typename T>
344 : void dispatchToTraceChildren(T* thing);
345 :
346 : // Mark the given GC thing, but do not trace its children. Return true
347 : // if the thing became marked.
348 : template <typename T>
349 : MOZ_MUST_USE bool mark(T* thing);
350 :
351 : template <typename T>
352 : inline void pushTaggedPtr(T* ptr);
353 :
354 : inline void pushValueArray(JSObject* obj, HeapSlot* start, HeapSlot* end);
355 :
356 0 : bool isMarkStackEmpty() {
357 0 : return stack.isEmpty();
358 : }
359 :
360 : MOZ_MUST_USE bool restoreValueArray(const gc::MarkStack::SavedValueArray& array,
361 : HeapSlot** vpp, HeapSlot** endp);
362 : void saveValueRanges();
363 : inline void processMarkStackTop(SliceBudget& budget);
364 :
365 : /* The mark stack. Pointers in this stack are "gray" in the GC sense. */
366 : gc::MarkStack stack;
367 :
368 : /* The color is only applied to objects and functions. */
369 : ActiveThreadData<gc::MarkColor> color;
370 :
371 : /* Pointer to the top of the stack of arenas we are delaying marking on. */
372 : ActiveThreadData<js::gc::Arena*> unmarkedArenaStackTop;
373 :
374 : /*
375 : * If the weakKeys table OOMs, disable the linear algorithm and fall back
376 : * to iterating until the next GC.
377 : */
378 : ActiveThreadData<bool> linearWeakMarkingDisabled_;
379 :
380 : #ifdef DEBUG
381 : /* Count of arenas that are currently in the stack. */
382 : ActiveThreadData<size_t> markLaterArenas;
383 :
384 : /* Assert that start and stop are called with correct ordering. */
385 : ActiveThreadData<bool> started;
386 :
387 : /*
388 : * If this is true, all marked objects must belong to a compartment being
389 : * GCed. This is used to look for compartment bugs.
390 : */
391 : ActiveThreadData<bool> strictCompartmentChecking;
392 : #endif // DEBUG
393 : };
394 :
395 : #ifdef DEBUG
396 : // Return true if this trace is happening on behalf of gray buffering during
397 : // the marking phase of incremental GC.
398 : bool
399 : IsBufferGrayRootsTracer(JSTracer* trc);
400 : #endif
401 :
402 : namespace gc {
403 :
404 : /*** Special Cases ***/
405 :
406 : void
407 : PushArena(GCMarker* gcmarker, Arena* arena);
408 :
409 : /*** Liveness ***/
410 :
411 : // Report whether a thing has been marked. Things which are in zones that are
412 : // not currently being collected or are owned by another runtime are always
413 : // reported as being marked.
414 : template <typename T>
415 : bool
416 : IsMarkedUnbarriered(JSRuntime* rt, T* thingp);
417 :
418 : // Report whether a thing has been marked. Things which are in zones that are
419 : // not currently being collected or are owned by another runtime are always
420 : // reported as being marked.
421 : template <typename T>
422 : bool
423 : IsMarked(JSRuntime* rt, WriteBarrieredBase<T>* thingp);
424 :
425 : template <typename T>
426 : bool
427 : IsAboutToBeFinalizedUnbarriered(T* thingp);
428 :
429 : template <typename T>
430 : bool
431 : IsAboutToBeFinalized(WriteBarrieredBase<T>* thingp);
432 :
433 : template <typename T>
434 : bool
435 : IsAboutToBeFinalized(ReadBarrieredBase<T>* thingp);
436 :
437 : bool
438 : IsAboutToBeFinalizedDuringSweep(TenuredCell& tenured);
439 :
440 : inline Cell*
441 0 : ToMarkable(const Value& v)
442 : {
443 0 : if (v.isGCThing())
444 0 : return (Cell*)v.toGCThing();
445 0 : return nullptr;
446 : }
447 :
448 : inline Cell*
449 0 : ToMarkable(Cell* cell)
450 : {
451 0 : return cell;
452 : }
453 :
454 : // Wrap a GC thing pointer into a new Value or jsid. The type system enforces
455 : // that the thing pointer is a wrappable type.
456 : template <typename S, typename T>
457 : struct RewrapTaggedPointer{};
458 : #define DECLARE_REWRAP(S, T, method, prefix) \
459 : template <> struct RewrapTaggedPointer<S, T> { \
460 : static S wrap(T* thing) { return method ( prefix thing ); } \
461 : }
462 42671 : DECLARE_REWRAP(JS::Value, JSObject, JS::ObjectOrNullValue, );
463 6046 : DECLARE_REWRAP(JS::Value, JSString, JS::StringValue, );
464 3 : DECLARE_REWRAP(JS::Value, JS::Symbol, JS::SymbolValue, );
465 44 : DECLARE_REWRAP(jsid, JSString, NON_INTEGER_ATOM_TO_JSID, (JSAtom*));
466 0 : DECLARE_REWRAP(jsid, JS::Symbol, SYMBOL_TO_JSID, );
467 0 : DECLARE_REWRAP(js::TaggedProto, JSObject, js::TaggedProto, );
468 : #undef DECLARE_REWRAP
469 :
470 : template <typename T>
471 : struct IsPrivateGCThingInValue
472 : : public mozilla::EnableIf<mozilla::IsBaseOf<Cell, T>::value &&
473 : !mozilla::IsBaseOf<JSObject, T>::value &&
474 : !mozilla::IsBaseOf<JSString, T>::value &&
475 : !mozilla::IsBaseOf<JS::Symbol, T>::value, T>
476 : {
477 : static_assert(!mozilla::IsSame<Cell, T>::value && !mozilla::IsSame<TenuredCell, T>::value,
478 : "T must not be Cell or TenuredCell");
479 : };
480 :
481 : template <typename T>
482 : struct RewrapTaggedPointer<Value, T>
483 : {
484 1143 : static Value wrap(typename IsPrivateGCThingInValue<T>::Type* thing) {
485 1143 : return JS::PrivateGCThingValue(thing);
486 : }
487 : };
488 :
489 : } /* namespace gc */
490 :
491 : // The return value indicates if anything was unmarked.
492 : bool
493 : UnmarkGrayShapeRecursively(Shape* shape);
494 :
495 : template<typename T>
496 : void
497 : CheckTracedThing(JSTracer* trc, T* thing);
498 :
499 : template<typename T>
500 : void
501 : CheckTracedThing(JSTracer* trc, T thing);
502 :
503 : } /* namespace js */
504 :
505 : namespace JS {
506 : class Symbol;
507 : }
508 :
509 : // Exported for Tracer.cpp
510 1340885 : inline bool ThingIsPermanentAtomOrWellKnownSymbol(js::gc::Cell* thing) { return false; }
511 : bool ThingIsPermanentAtomOrWellKnownSymbol(JSString*);
512 : bool ThingIsPermanentAtomOrWellKnownSymbol(JSFlatString*);
513 : bool ThingIsPermanentAtomOrWellKnownSymbol(JSLinearString*);
514 : bool ThingIsPermanentAtomOrWellKnownSymbol(JSAtom*);
515 : bool ThingIsPermanentAtomOrWellKnownSymbol(js::PropertyName*);
516 : bool ThingIsPermanentAtomOrWellKnownSymbol(JS::Symbol*);
517 :
518 : #endif /* gc_Marking_h */
|
