1// Copyright 2019 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_HEAP_MARKING_VISITOR_H_
6#define V8_HEAP_MARKING_VISITOR_H_
7
8#include "src/common/globals.h"
9#include "src/heap/marking-worklist.h"
10#include "src/heap/marking.h"
11#include "src/heap/memory-chunk.h"
12#include "src/heap/objects-visiting.h"
13#include "src/heap/spaces.h"
14#include "src/heap/weak-object-worklists.h"
15
16namespace v8 {
17namespace internal {
18
19struct EphemeronMarking {
20  std::vector<HeapObject> newly_discovered;
21  bool newly_discovered_overflowed;
22  size_t newly_discovered_limit;
23};
24
25template <typename ConcreteState, AccessMode access_mode>
26class MarkingStateBase {
27 public:
28  // Declares that this marking state is not collecting retainers, so the
29  // marking visitor may update the heap state to store information about
30  // progress, and may avoid fully visiting an object if it is safe to do so.
31  static constexpr bool kCollectRetainers = false;
32
33  explicit MarkingStateBase(PtrComprCageBase cage_base)
34#if V8_COMPRESS_POINTERS
35      : cage_base_(cage_base)
36#endif
37  {
38  }
39
40  // The pointer compression cage base value used for decompression of all
41  // tagged values except references to Code objects.
42  V8_INLINE PtrComprCageBase cage_base() const {
43#if V8_COMPRESS_POINTERS
44    return cage_base_;
45#else
46    return PtrComprCageBase{};
47#endif  // V8_COMPRESS_POINTERS
48  }
49
50  V8_INLINE MarkBit MarkBitFrom(HeapObject obj) {
51    return MarkBitFrom(BasicMemoryChunk::FromHeapObject(obj), obj.ptr());
52  }
53
54  // {addr} may be tagged or aligned.
55  V8_INLINE MarkBit MarkBitFrom(BasicMemoryChunk* p, Address addr) {
56    return static_cast<ConcreteState*>(this)->bitmap(p)->MarkBitFromIndex(
57        p->AddressToMarkbitIndex(addr));
58  }
59
60  Marking::ObjectColor Color(HeapObject obj) {
61    return Marking::Color(MarkBitFrom(obj));
62  }
63
64  V8_INLINE bool IsImpossible(HeapObject obj) {
65    return Marking::IsImpossible<access_mode>(MarkBitFrom(obj));
66  }
67
68  V8_INLINE bool IsBlack(HeapObject obj) {
69    return Marking::IsBlack<access_mode>(MarkBitFrom(obj));
70  }
71
72  V8_INLINE bool IsWhite(HeapObject obj) {
73    return Marking::IsWhite<access_mode>(MarkBitFrom(obj));
74  }
75
76  V8_INLINE bool IsGrey(HeapObject obj) {
77    return Marking::IsGrey<access_mode>(MarkBitFrom(obj));
78  }
79
80  V8_INLINE bool IsBlackOrGrey(HeapObject obj) {
81    return Marking::IsBlackOrGrey<access_mode>(MarkBitFrom(obj));
82  }
83
84  V8_INLINE bool WhiteToGrey(HeapObject obj) {
85    return Marking::WhiteToGrey<access_mode>(MarkBitFrom(obj));
86  }
87
88  V8_INLINE bool WhiteToBlack(HeapObject obj) {
89    return WhiteToGrey(obj) && GreyToBlack(obj);
90  }
91
92  V8_INLINE bool GreyToBlack(HeapObject obj) {
93    BasicMemoryChunk* chunk = BasicMemoryChunk::FromHeapObject(obj);
94    MarkBit markbit = MarkBitFrom(chunk, obj.address());
95    if (!Marking::GreyToBlack<access_mode>(markbit)) return false;
96    static_cast<ConcreteState*>(this)->IncrementLiveBytes(
97        MemoryChunk::cast(chunk), obj.Size(cage_base()));
98    return true;
99  }
100
101  V8_INLINE bool GreyToBlackUnaccounted(HeapObject obj) {
102    return Marking::GreyToBlack<access_mode>(MarkBitFrom(obj));
103  }
104
105  void ClearLiveness(MemoryChunk* chunk) {
106    static_cast<ConcreteState*>(this)->bitmap(chunk)->Clear();
107    static_cast<ConcreteState*>(this)->SetLiveBytes(chunk, 0);
108  }
109
110  void AddStrongReferenceForReferenceSummarizer(HeapObject host,
111                                                HeapObject obj) {
112    // This is not a reference summarizer, so there is nothing to do here.
113  }
114
115  void AddWeakReferenceForReferenceSummarizer(HeapObject host, HeapObject obj) {
116    // This is not a reference summarizer, so there is nothing to do here.
117  }
118
119 private:
120#if V8_COMPRESS_POINTERS
121  const PtrComprCageBase cage_base_;
122#endif  // V8_COMPRESS_POINTERS
123};
124
125// The base class for all marking visitors. It implements marking logic with
126// support of bytecode flushing, embedder tracing, weak and references.
127//
128// Derived classes are expected to provide the following:
129// - ConcreteVisitor::marking_state method,
130// - ConcreteVisitor::retaining_path_mode method,
131// - ConcreteVisitor::RecordSlot method,
132// - ConcreteVisitor::RecordRelocSlot method,
133// - ConcreteVisitor::SynchronizePageAccess method,
134// - ConcreteVisitor::VisitJSObjectSubclass method,
135// - ConcreteVisitor::VisitLeftTrimmableArray method.
136// These methods capture the difference between the concurrent and main thread
137// marking visitors. For example, the concurrent visitor has to use the
138// snapshotting protocol to visit JSObject and left-trimmable FixedArrays.
139
140template <typename ConcreteVisitor, typename MarkingState>
141class MarkingVisitorBase : public HeapVisitor<int, ConcreteVisitor> {
142 public:
143  MarkingVisitorBase(MarkingWorklists::Local* local_marking_worklists,
144                     WeakObjects::Local* local_weak_objects, Heap* heap,
145                     unsigned mark_compact_epoch,
146                     base::EnumSet<CodeFlushMode> code_flush_mode,
147                     bool is_embedder_tracing_enabled,
148                     bool should_keep_ages_unchanged)
149      : HeapVisitor<int, ConcreteVisitor>(heap),
150        local_marking_worklists_(local_marking_worklists),
151        local_weak_objects_(local_weak_objects),
152        heap_(heap),
153        mark_compact_epoch_(mark_compact_epoch),
154        code_flush_mode_(code_flush_mode),
155        is_embedder_tracing_enabled_(is_embedder_tracing_enabled),
156        should_keep_ages_unchanged_(should_keep_ages_unchanged),
157        is_shared_heap_(heap->IsShared())
158#ifdef V8_SANDBOXED_EXTERNAL_POINTERS
159        ,
160        external_pointer_table_(&heap->isolate()->external_pointer_table())
161#endif  // V8_SANDBOXED_EXTERNAL_POINTERS
162  {
163  }
164
165  V8_INLINE int VisitBytecodeArray(Map map, BytecodeArray object);
166  V8_INLINE int VisitDescriptorArray(Map map, DescriptorArray object);
167  V8_INLINE int VisitEphemeronHashTable(Map map, EphemeronHashTable object);
168  V8_INLINE int VisitFixedArray(Map map, FixedArray object);
169  V8_INLINE int VisitFixedDoubleArray(Map map, FixedDoubleArray object);
170  V8_INLINE int VisitJSApiObject(Map map, JSObject object);
171  V8_INLINE int VisitJSArrayBuffer(Map map, JSArrayBuffer object);
172  V8_INLINE int VisitJSDataView(Map map, JSDataView object);
173  V8_INLINE int VisitJSFunction(Map map, JSFunction object);
174  V8_INLINE int VisitJSTypedArray(Map map, JSTypedArray object);
175  V8_INLINE int VisitJSWeakRef(Map map, JSWeakRef object);
176  V8_INLINE int VisitMap(Map map, Map object);
177  V8_INLINE int VisitSharedFunctionInfo(Map map, SharedFunctionInfo object);
178  V8_INLINE int VisitTransitionArray(Map map, TransitionArray object);
179  V8_INLINE int VisitWeakCell(Map map, WeakCell object);
180
181  // ObjectVisitor overrides.
182  void VisitMapPointer(HeapObject host) final {
183    Map map = host.map(ObjectVisitorWithCageBases::cage_base());
184    MarkObject(host, map);
185    concrete_visitor()->RecordSlot(host, host.map_slot(), map);
186  }
187  V8_INLINE void VisitPointer(HeapObject host, ObjectSlot p) final {
188    VisitPointersImpl(host, p, p + 1);
189  }
190  V8_INLINE void VisitPointer(HeapObject host, MaybeObjectSlot p) final {
191    VisitPointersImpl(host, p, p + 1);
192  }
193  V8_INLINE void VisitPointers(HeapObject host, ObjectSlot start,
194                               ObjectSlot end) final {
195    VisitPointersImpl(host, start, end);
196  }
197  V8_INLINE void VisitPointers(HeapObject host, MaybeObjectSlot start,
198                               MaybeObjectSlot end) final {
199    VisitPointersImpl(host, start, end);
200  }
201  V8_INLINE void VisitCodePointer(HeapObject host, CodeObjectSlot slot) final {
202    VisitCodePointerImpl(host, slot);
203  }
204  V8_INLINE void VisitEmbeddedPointer(Code host, RelocInfo* rinfo) final;
205  V8_INLINE void VisitCodeTarget(Code host, RelocInfo* rinfo) final;
206  void VisitCustomWeakPointers(HeapObject host, ObjectSlot start,
207                               ObjectSlot end) final {
208    // Weak list pointers should be ignored during marking. The lists are
209    // reconstructed after GC.
210  }
211
212  V8_INLINE void VisitExternalPointer(HeapObject host,
213                                      ExternalPointer_t ptr) final {
214#ifdef V8_SANDBOXED_EXTERNAL_POINTERS
215    uint32_t index = ptr >> kExternalPointerIndexShift;
216    external_pointer_table_->Mark(index);
217#endif  // V8_SANDBOXED_EXTERNAL_POINTERS
218  }
219
220 protected:
221  ConcreteVisitor* concrete_visitor() {
222    return static_cast<ConcreteVisitor*>(this);
223  }
224  template <typename THeapObjectSlot>
225  void ProcessStrongHeapObject(HeapObject host, THeapObjectSlot slot,
226                               HeapObject heap_object);
227  template <typename THeapObjectSlot>
228  void ProcessWeakHeapObject(HeapObject host, THeapObjectSlot slot,
229                             HeapObject heap_object);
230
231  template <typename TSlot>
232  V8_INLINE void VisitPointerImpl(HeapObject host, TSlot p);
233
234  template <typename TSlot>
235  V8_INLINE void VisitPointersImpl(HeapObject host, TSlot start, TSlot end);
236
237  // Similar to VisitPointersImpl() but using code cage base for loading from
238  // the slot.
239  V8_INLINE void VisitCodePointerImpl(HeapObject host, CodeObjectSlot slot);
240
241  V8_INLINE void VisitDescriptors(DescriptorArray descriptors,
242                                  int number_of_own_descriptors);
243
244  V8_INLINE int VisitDescriptorsForMap(Map map);
245
246  template <typename T>
247  int VisitEmbedderTracingSubclass(Map map, T object);
248  template <typename T>
249  int VisitEmbedderTracingSubClassWithEmbedderTracing(Map map, T object);
250  template <typename T>
251  int VisitEmbedderTracingSubClassNoEmbedderTracing(Map map, T object);
252
253  V8_INLINE int VisitFixedArrayWithProgressBar(Map map, FixedArray object,
254                                               ProgressBar& progress_bar);
255  // Marks the descriptor array black without pushing it on the marking work
256  // list and visits its header. Returns the size of the descriptor array
257  // if it was successully marked as black.
258  V8_INLINE int MarkDescriptorArrayBlack(DescriptorArray descriptors);
259  // Marks the object grey and pushes it on the marking work list.
260  V8_INLINE void MarkObject(HeapObject host, HeapObject obj);
261
262  V8_INLINE void AddStrongReferenceForReferenceSummarizer(HeapObject host,
263                                                          HeapObject obj) {
264    concrete_visitor()
265        ->marking_state()
266        ->AddStrongReferenceForReferenceSummarizer(host, obj);
267  }
268
269  V8_INLINE void AddWeakReferenceForReferenceSummarizer(HeapObject host,
270                                                        HeapObject obj) {
271    concrete_visitor()->marking_state()->AddWeakReferenceForReferenceSummarizer(
272        host, obj);
273  }
274
275  constexpr bool CanUpdateValuesInHeap() {
276    return !MarkingState::kCollectRetainers;
277  }
278
279  MarkingWorklists::Local* const local_marking_worklists_;
280  WeakObjects::Local* const local_weak_objects_;
281  Heap* const heap_;
282  const unsigned mark_compact_epoch_;
283  const base::EnumSet<CodeFlushMode> code_flush_mode_;
284  const bool is_embedder_tracing_enabled_;
285  const bool should_keep_ages_unchanged_;
286  const bool is_shared_heap_;
287#ifdef V8_SANDBOXED_EXTERNAL_POINTERS
288  ExternalPointerTable* const external_pointer_table_;
289#endif  // V8_SANDBOXED_EXTERNAL_POINTERS
290};
291
292}  // namespace internal
293}  // namespace v8
294
295#endif  // V8_HEAP_MARKING_VISITOR_H_
296