summaryrefslogtreecommitdiffstats
path: root/js/src/gc/GCMarker.h
blob: 1baec84e49cbfd9e3927a743296f63486aa9155a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * 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 gc_GCMarker_h
#define gc_GCMarker_h

#include "mozilla/Maybe.h"
#include "mozilla/Variant.h"

#include "ds/OrderedHashTable.h"
#include "gc/Barrier.h"
#include "js/TracingAPI.h"
#include "js/TypeDecls.h"
#include "threading/ProtectedData.h"

class JSRope;

namespace js {

class GCMarker;
class SliceBudget;
class WeakMapBase;

static const size_t MARK_STACK_BASE_CAPACITY = 4096;

enum class SlotsOrElementsKind {
  Unused = 0,  // Must match SlotsOrElementsRangeTag
  Elements,
  FixedSlots,
  DynamicSlots
};

namespace gc {

enum IncrementalProgress { NotFinished = 0, Finished };

class AutoSetMarkColor;
class AutoUpdateMarkStackRanges;
struct Cell;
class MarkStackIter;
class ParallelMarker;
class UnmarkGrayTracer;

struct EphemeronEdgeTableHashPolicy {
  using Lookup = Cell*;
  static HashNumber hash(const Lookup& v,
                         const mozilla::HashCodeScrambler& hcs) {
    return hcs.scramble(mozilla::HashGeneric(v));
  }
  static bool match(Cell* const& k, const Lookup& l) { return k == l; }
  static bool isEmpty(Cell* const& v) { return !v; }
  static void makeEmpty(Cell** vp) { *vp = nullptr; }
};

// Ephemeron edges have two source nodes and one target, and mark the target
// with the minimum (least-marked) color of the sources. Currently, one of
// those sources will always be a WeakMapBase, so this will refer to its color
// at the time the edge is traced through. The other source's color will be
// given by the current mark color of the GCMarker.
struct EphemeronEdge {
  CellColor color;
  Cell* target;

  EphemeronEdge(CellColor color_, Cell* cell) : color(color_), target(cell) {}
};

using EphemeronEdgeVector = Vector<EphemeronEdge, 2, js::SystemAllocPolicy>;

using EphemeronEdgeTable =
    OrderedHashMap<Cell*, EphemeronEdgeVector, EphemeronEdgeTableHashPolicy,
                   js::SystemAllocPolicy>;

/*
 * The mark stack. Pointers in this stack are "gray" in the GC sense, but
 * their references may be marked either black or gray (in the CC sense).
 *
 * When the mark stack is full, 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 when the mark stack is empty.
 *
 * To implement such delayed marking of the children with minimal overhead for
 * the normal case of sufficient stack, we link arenas into a list using
 * Arena::setNextDelayedMarkingArena(). The head of the list is stored in
 * GCMarker::delayedMarkingList. GCMarker::delayMarkingChildren() adds arenas
 * to the list as necessary while markAllDelayedChildren() pops the arenas from
 * the stack until it is empty.
 */
class MarkStack {
 public:
  /*
   * 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 Tag {
    SlotsOrElementsRangeTag = 0,  // Must match SlotsOrElementsKind::Unused.
    ObjectTag,
    JitCodeTag,
    ScriptTag,
    TempRopeTag,

    LastTag = TempRopeTag
  };

  static const uintptr_t TagMask = 7;
  static_assert(TagMask >= uintptr_t(LastTag),
                "The tag mask must subsume the tags.");
  static_assert(TagMask <= gc::CellAlignMask,
                "The tag mask must be embeddable in a Cell*.");

  class TaggedPtr {
    uintptr_t bits;

    Cell* ptr() const;

   public:
    TaggedPtr() = default;
    TaggedPtr(Tag tag, Cell* ptr);
    uintptr_t asBits() const;
    Tag tag() const;
    uintptr_t tagUnchecked() const;
    template <typename T>
    T* as() const;

    JSObject* asRangeObject() const;
    JSRope* asTempRope() const;

    void assertValid() const;
  };

  struct SlotsOrElementsRange {
    SlotsOrElementsRange(SlotsOrElementsKind kind, JSObject* obj, size_t start);
    void assertValid() const;

    SlotsOrElementsKind kind() const;
    size_t start() const;
    TaggedPtr ptr() const;

    void setStart(size_t newStart);
    void setEmpty();

   private:
    static constexpr size_t StartShift = 2;
    static constexpr size_t KindMask = (1 << StartShift) - 1;

    uintptr_t startAndKind_;
    TaggedPtr ptr_;
  };

  MarkStack();
  ~MarkStack();

  explicit MarkStack(const MarkStack& other);
  MarkStack& operator=(const MarkStack& other);

  MarkStack(MarkStack&& other);
  MarkStack& operator=(MarkStack&& other);

  // The unit for MarkStack::capacity() is mark stack words.
  size_t capacity() { return stack().length(); }

  size_t position() const { return topIndex_; }

  [[nodiscard]] bool init();
  [[nodiscard]] bool resetStackCapacity();

#ifdef JS_GC_ZEAL
  void setMaxCapacity(size_t maxCapacity);
#endif

  template <typename T>
  [[nodiscard]] bool push(T* ptr);

  [[nodiscard]] bool push(JSObject* obj, SlotsOrElementsKind kind,
                          size_t start);
  [[nodiscard]] bool push(const TaggedPtr& ptr);
  [[nodiscard]] bool push(const SlotsOrElementsRange& array);
  void infalliblePush(const TaggedPtr& ptr);
  void infalliblePush(const SlotsOrElementsRange& array);

  // GCMarker::eagerlyMarkChildren uses unused marking stack as temporary
  // storage to hold rope pointers.
  [[nodiscard]] bool pushTempRope(JSRope* ptr);

  bool isEmpty() const { return position() == 0; }
  bool hasEntries() const { return !isEmpty(); }

  Tag peekTag() const;
  TaggedPtr popPtr();
  SlotsOrElementsRange popSlotsOrElementsRange();

  void clearAndResetCapacity();
  void clearAndFreeStack();

  void poisonUnused();

  [[nodiscard]] bool ensureSpace(size_t count);

  static void moveWork(MarkStack& dst, MarkStack& src);

  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const;

 private:
  using StackVector = Vector<TaggedPtr, 0, SystemAllocPolicy>;
  const StackVector& stack() const { return stack_.ref(); }
  StackVector& stack() { return stack_.ref(); }

  /* Grow the stack, ensuring there is space for at least count elements. */
  [[nodiscard]] bool enlarge(size_t count);

  [[nodiscard]] bool resize(size_t newCapacity);

  TaggedPtr* topPtr();

  const TaggedPtr& peekPtr() const;
  [[nodiscard]] bool pushTaggedPtr(Tag tag, Cell* ptr);

  bool indexIsEntryBase(size_t index) const;

  // Vector containing allocated stack memory. Unused beyond topIndex_.
  MainThreadOrGCTaskData<StackVector> stack_;

  // Index of the top of the stack.
  MainThreadOrGCTaskData<size_t> topIndex_;

#ifdef JS_GC_ZEAL
  // The maximum stack capacity to grow to.
  MainThreadOrGCTaskData<size_t> maxCapacity_{SIZE_MAX};
#endif

#ifdef DEBUG
  MainThreadOrGCTaskData<bool> elementsRangesAreValid;
  friend class js::GCMarker;
#endif

  friend class MarkStackIter;
};

static_assert(unsigned(SlotsOrElementsKind::Unused) ==
                  unsigned(MarkStack::SlotsOrElementsRangeTag),
              "To split the mark stack we depend on being able to tell the "
              "difference between SlotsOrElementsRange::startAndKind_ and a "
              "tagged SlotsOrElementsRange");

class MOZ_STACK_CLASS MarkStackIter {
  MarkStack& stack_;
  size_t pos_;

 public:
  explicit MarkStackIter(MarkStack& stack);

  bool done() const;
  void next();

  MarkStack::Tag peekTag() const;
  bool isSlotsOrElementsRange() const;
  MarkStack::SlotsOrElementsRange& slotsOrElementsRange();

 private:
  size_t position() const;
  MarkStack::TaggedPtr peekPtr() const;
};

// Bitmask of options to parameterize MarkingTracerT.
namespace MarkingOptions {
enum : uint32_t {
  // Set the compartment's hasMarkedCells flag for roots.
  MarkRootCompartments = 1,

  // The marking tracer is operating in parallel. Use appropriate atomic
  // accesses to update the mark bits correctly.
  ParallelMarking = 2,

  // Mark any implicit edges if we are in weak marking mode.
  MarkImplicitEdges = 4,
};
}  // namespace MarkingOptions

constexpr uint32_t NormalMarkingOptions = MarkingOptions::MarkImplicitEdges;

template <uint32_t markingOptions>
class MarkingTracerT
    : public GenericTracerImpl<MarkingTracerT<markingOptions>> {
 public:
  MarkingTracerT(JSRuntime* runtime, GCMarker* marker);
  virtual ~MarkingTracerT() = default;

  template <typename T>
  void onEdge(T** thingp, const char* name);
  friend class GenericTracerImpl<MarkingTracerT<markingOptions>>;

  GCMarker* getMarker();
};

using MarkingTracer = MarkingTracerT<NormalMarkingOptions>;
using RootMarkingTracer = MarkingTracerT<MarkingOptions::MarkRootCompartments>;
using ParallelMarkingTracer = MarkingTracerT<MarkingOptions::ParallelMarking>;

enum ShouldReportMarkTime : bool {
  ReportMarkTime = true,
  DontReportMarkTime = false
};

} /* namespace gc */

class GCMarker {
  enum MarkingState : uint8_t {
    // Have not yet started marking.
    NotActive,

    // Root marking mode. This sets the hasMarkedCells flag on compartments
    // containing objects and scripts, which is used to make sure we clean up
    // dead compartments.
    RootMarking,

    // Main marking mode. Weakmap marking will be populating the
    // gcEphemeronEdges tables but not consulting them. The state will
    // transition to WeakMarking until it is done, then back to RegularMarking.
    RegularMarking,

    // Like RegularMarking but with multiple threads running in parallel.
    ParallelMarking,

    // Same as RegularMarking except now every marked obj/script is immediately
    // looked up in the gcEphemeronEdges table to find edges generated by
    // weakmap keys, and traversing them to their values. Transitions back to
    // RegularMarking when done.
    WeakMarking,
  };

 public:
  explicit GCMarker(JSRuntime* rt);
  [[nodiscard]] bool init();

  JSRuntime* runtime() { return runtime_; }
  JSTracer* tracer() {
    return tracer_.match([](auto& t) -> JSTracer* { return &t; });
  }

#ifdef JS_GC_ZEAL
  void setMaxCapacity(size_t maxCap) { stack.setMaxCapacity(maxCap); }
#endif

  bool isActive() const { return state != NotActive; }
  bool isRegularMarking() const { return state == RegularMarking; }
  bool isParallelMarking() const { return state == ParallelMarking; }
  bool isWeakMarking() const { return state == WeakMarking; }

  gc::MarkColor markColor() const { return markColor_; }

  bool isDrained() const { return stack.isEmpty() && otherStack.isEmpty(); }

  bool hasEntriesForCurrentColor() { return stack.hasEntries(); }
  bool hasBlackEntries() const { return hasEntries(gc::MarkColor::Black); }
  bool hasGrayEntries() const { return hasEntries(gc::MarkColor::Gray); }
  bool hasEntries(gc::MarkColor color) const;

  bool canDonateWork() const;

  void start();
  void stop();
  void reset();

  [[nodiscard]] bool markUntilBudgetExhausted(
      SliceBudget& budget,
      gc::ShouldReportMarkTime reportTime = gc::ReportMarkTime);

  void setRootMarkingMode(bool newState);

  bool enterWeakMarkingMode();
  void leaveWeakMarkingMode();

  void enterParallelMarkingMode(gc::ParallelMarker* pm);
  void leaveParallelMarkingMode();

  // Do not use linear-time weak marking for the rest of this collection.
  // Currently, this will only be triggered by an OOM when updating needed data
  // structures.
  void abortLinearWeakMarking();

  // 'delegate' is no longer the delegate of 'key'.
  void severWeakDelegate(JSObject* key, JSObject* delegate);

  // 'delegate' is now the delegate of 'key'. Update weakmap marking state.
  void restoreWeakDelegate(JSObject* key, JSObject* delegate);

#ifdef DEBUG
  // We can't check atom marking if the helper thread lock is already held by
  // the current thread. This allows us to disable the check.
  void setCheckAtomMarking(bool check);

  bool shouldCheckCompartments() { return strictCompartmentChecking; }

  bool markOneObjectForTest(JSObject* obj);
#endif

  bool markCurrentColorInParallel(SliceBudget& budget);

  template <uint32_t markingOptions, gc::MarkColor>
  bool markOneColor(SliceBudget& budget);

  static void moveWork(GCMarker* dst, GCMarker* src);

  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const;

  static GCMarker* fromTracer(JSTracer* trc) {
    MOZ_ASSERT(trc->isMarkingTracer());
    auto* marker = reinterpret_cast<GCMarker*>(uintptr_t(trc) -
                                               offsetof(GCMarker, tracer_));
    MOZ_ASSERT(marker->tracer() == trc);
    return marker;
  }

  // Internal public methods, for ease of use by the rest of the GC:

  // If |thing| is unmarked, mark it and then traverse its children.
  template <uint32_t, typename T>
  void markAndTraverse(T* thing);

  template <typename T>
  void markImplicitEdges(T* oldThing);

 private:
  /*
   * 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 setMarkColor(gc::MarkColor newColor);
  friend class js::gc::AutoSetMarkColor;

  template <typename Tracer>
  void setMarkingStateAndTracer(MarkingState prev, MarkingState next);

  // The mutator can shift object elements which could invalidate any elements
  // index on the mark stack. Change the index to be relative to the elements
  // allocation (to ignore shifted elements) while the mutator is running.
  void updateRangesAtStartOfSlice();
  void updateRangesAtEndOfSlice();
  friend class gc::AutoUpdateMarkStackRanges;

  template <uint32_t markingOptions>
  bool processMarkStackTop(SliceBudget& budget);
  friend class gc::GCRuntime;

  // Helper methods that coerce their second argument to the base pointer
  // type.
  template <uint32_t markingOptions, typename S>
  void markAndTraverseObjectEdge(S source, JSObject* target) {
    markAndTraverseEdge<markingOptions>(source, target);
  }
  template <uint32_t markingOptions, typename S>
  void markAndTraverseStringEdge(S source, JSString* target) {
    markAndTraverseEdge<markingOptions>(source, target);
  }

  template <uint32_t markingOptions, typename S, typename T>
  void markAndTraverseEdge(S source, T* target);
  template <uint32_t markingOptions, typename S, typename T>
  void markAndTraverseEdge(S source, const T& target);

  template <typename S, typename T>
  void checkTraversedEdge(S source, T* target);

  // Mark the given GC thing, but do not trace its children. Return true
  // if the thing became marked.
  template <uint32_t markingOptions, typename T>
  [[nodiscard]] bool mark(T* thing);

  // Traverse a GC thing's children, using a strategy depending on the type.
  // This can either processing them immediately or push them onto the mark
  // stack for later.
#define DEFINE_TRAVERSE_METHOD(_1, Type, _2, _3) \
  template <uint32_t>                            \
  void traverse(Type* thing);
  JS_FOR_EACH_TRACEKIND(DEFINE_TRAVERSE_METHOD)
#undef DEFINE_TRAVERSE_METHOD

  // Process a marked thing's children by calling T::traceChildren().
  template <uint32_t markingOptions, typename T>
  void traceChildren(T* thing);

  // Process a marked thing's children recursively using an iterative loop and
  // manual dispatch, for kinds where this is possible.
  template <uint32_t markingOptions, typename T>
  void scanChildren(T* thing);

  // Push a marked thing onto the mark stack. Its children will be marked later.
  template <uint32_t markingOptions, typename T>
  void pushThing(T* thing);

  template <uint32_t markingOptions>
  void eagerlyMarkChildren(JSLinearString* str);
  template <uint32_t markingOptions>
  void eagerlyMarkChildren(JSRope* rope);
  template <uint32_t markingOptions>
  void eagerlyMarkChildren(JSString* str);
  template <uint32_t markingOptions>
  void eagerlyMarkChildren(Shape* shape);
  template <uint32_t markingOptions>
  void eagerlyMarkChildren(PropMap* map);
  template <uint32_t markingOptions>
  void eagerlyMarkChildren(Scope* scope);

  template <typename T>
  inline void pushTaggedPtr(T* ptr);

  inline void pushValueRange(JSObject* obj, SlotsOrElementsKind kind,
                             size_t start, size_t end);

  // Push an object onto the stack for later tracing and assert that it has
  // already been marked.
  inline void repush(JSObject* obj);

  template <typename T>
  void markImplicitEdgesHelper(T oldThing);

  // Mark through edges whose target color depends on the colors of two source
  // entities (eg a WeakMap and one of its keys), and push the target onto the
  // mark stack.
  void markEphemeronEdges(gc::EphemeronEdgeVector& edges,
                          gc::CellColor srcColor);
  friend class JS::Zone;

#ifdef DEBUG
  void checkZone(void* p);
#else
  void checkZone(void* p) {}
#endif

  template <uint32_t markingOptions>
  bool doMarking(SliceBudget& budget, gc::ShouldReportMarkTime reportTime);

  void delayMarkingChildrenOnOOM(gc::Cell* cell);

  /*
   * The JSTracer used for marking. This can change depending on the current
   * state.
   */
  mozilla::Variant<gc::MarkingTracer, gc::RootMarkingTracer,
                   gc::ParallelMarkingTracer>
      tracer_;

  JSRuntime* const runtime_;

  // The main mark stack, holding entries of color |markColor_|.
  gc::MarkStack stack;

  // The auxiliary mark stack, which may contain entries of the other color.
  gc::MarkStack otherStack;

  // Track whether we're using the main or auxiliary stack.
  MainThreadOrGCTaskData<bool> haveSwappedStacks;

  // The current mark stack color.
  MainThreadOrGCTaskData<gc::MarkColor> markColor_;

  MainThreadOrGCTaskData<gc::ParallelMarker*> parallelMarker_;

  Vector<JS::GCCellPtr, 0, SystemAllocPolicy> unmarkGrayStack;
  friend class gc::UnmarkGrayTracer;

  /* Track the state of marking. */
  MainThreadOrGCTaskData<MarkingState> state;

  /* Whether we successfully added all edges to the implicit edges table. */
  MainThreadOrGCTaskData<bool> haveAllImplicitEdges;

 public:
  /*
   * Whether weakmaps can be marked incrementally.
   *
   * JSGC_INCREMENTAL_WEAKMAP_ENABLED
   * pref: javascript.options.mem.incremental_weakmap
   */
  MainThreadOrGCTaskData<bool> incrementalWeakMapMarkingEnabled;

#ifdef DEBUG
 private:
  /* Assert that start and stop are called with correct ordering. */
  MainThreadOrGCTaskData<bool> started;

  /*
   * Whether to check that atoms traversed are present in atom marking
   * bitmap.
   */
  MainThreadOrGCTaskData<bool> checkAtomMarking;

  /*
   * If this is true, all marked objects must belong to a compartment being
   * GCed. This is used to look for compartment bugs.
   */
  MainThreadOrGCTaskData<bool> strictCompartmentChecking;

 public:
  /*
   * The compartment and zone of the object whose trace hook is currently being
   * called, if any. Used to catch cross-compartment edges traced without use of
   * TraceCrossCompartmentEdge.
   */
  MainThreadOrGCTaskData<Compartment*> tracingCompartment;
  MainThreadOrGCTaskData<Zone*> tracingZone;
#endif  // DEBUG
};

namespace gc {

/*
 * Temporarily change the mark color while this class is on the stack.
 *
 * During incremental sweeping this also transitions zones in the
 * current sweep group into the Mark or MarkGray state as appropriate.
 */
class MOZ_RAII AutoSetMarkColor {
  GCMarker& marker_;
  MarkColor initialColor_;

 public:
  AutoSetMarkColor(GCMarker& marker, MarkColor newColor)
      : marker_(marker), initialColor_(marker.markColor()) {
    marker_.setMarkColor(newColor);
  }

  AutoSetMarkColor(GCMarker& marker, CellColor newColor)
      : AutoSetMarkColor(marker, newColor.asMarkColor()) {}

  ~AutoSetMarkColor() { marker_.setMarkColor(initialColor_); }
};

} /* namespace gc */

} /* namespace js */

#endif /* gc_GCMarker_h */