1 // Copyright 2012 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_INCREMENTAL_MARKING_H_
6 #define V8_HEAP_INCREMENTAL_MARKING_H_
7 
8 #include "src/cancelable-task.h"
9 #include "src/execution.h"
10 #include "src/heap/incremental-marking-job.h"
11 #include "src/heap/spaces.h"
12 #include "src/objects.h"
13 
14 namespace v8 {
15 namespace internal {
16 
17 // Forward declarations.
18 class MarkBit;
19 class PagedSpace;
20 
21 class IncrementalMarking {
22  public:
23   enum State { STOPPED, SWEEPING, MARKING, COMPLETE };
24 
25   enum CompletionAction { GC_VIA_STACK_GUARD, NO_GC_VIA_STACK_GUARD };
26 
27   enum ForceMarkingAction { FORCE_MARKING, DO_NOT_FORCE_MARKING };
28 
29   enum ForceCompletionAction { FORCE_COMPLETION, DO_NOT_FORCE_COMPLETION };
30 
31   enum GCRequestType { COMPLETE_MARKING, FINALIZATION };
32 
33   struct StepActions {
StepActionsStepActions34     StepActions(CompletionAction complete_action_,
35                 ForceMarkingAction force_marking_,
36                 ForceCompletionAction force_completion_)
37         : completion_action(complete_action_),
38           force_marking(force_marking_),
39           force_completion(force_completion_) {}
40 
41     CompletionAction completion_action;
42     ForceMarkingAction force_marking;
43     ForceCompletionAction force_completion;
44   };
45 
46   static StepActions IdleStepActions();
47 
48   explicit IncrementalMarking(Heap* heap);
49 
50   static void Initialize();
51 
state()52   State state() {
53     DCHECK(state_ == STOPPED || FLAG_incremental_marking);
54     return state_;
55   }
56 
should_hurry()57   bool should_hurry() { return should_hurry_; }
set_should_hurry(bool val)58   void set_should_hurry(bool val) { should_hurry_ = val; }
59 
finalize_marking_completed()60   bool finalize_marking_completed() const {
61     return finalize_marking_completed_;
62   }
63 
SetWeakClosureWasOverApproximatedForTesting(bool val)64   void SetWeakClosureWasOverApproximatedForTesting(bool val) {
65     finalize_marking_completed_ = val;
66   }
67 
IsStopped()68   inline bool IsStopped() { return state() == STOPPED; }
69 
INLINE(bool IsMarking ())70   INLINE(bool IsMarking()) { return state() >= MARKING; }
71 
IsMarkingIncomplete()72   inline bool IsMarkingIncomplete() { return state() == MARKING; }
73 
IsComplete()74   inline bool IsComplete() { return state() == COMPLETE; }
75 
IsReadyToOverApproximateWeakClosure()76   inline bool IsReadyToOverApproximateWeakClosure() const {
77     return request_type_ == FINALIZATION && !finalize_marking_completed_;
78   }
79 
request_type()80   GCRequestType request_type() const { return request_type_; }
81 
82   bool CanBeActivated();
83 
84   bool ShouldActivateEvenWithoutIdleNotification();
85 
86   bool WasActivated();
87 
88   void Start(const char* reason = nullptr);
89 
90   void FinalizeIncrementally();
91 
92   void UpdateMarkingDequeAfterScavenge();
93 
94   void Hurry();
95 
96   void Finalize();
97 
98   void Stop();
99 
100   void FinalizeMarking(CompletionAction action);
101 
102   void MarkingComplete(CompletionAction action);
103 
104   void Epilogue();
105 
106   // Performs incremental marking steps of step_size_in_bytes as long as
107   // deadline_ins_ms is not reached. step_size_in_bytes can be 0 to compute
108   // an estimate increment. Returns the remaining time that cannot be used
109   // for incremental marking anymore because a single step would exceed the
110   // deadline.
111   double AdvanceIncrementalMarking(intptr_t step_size_in_bytes,
112                                    double deadline_in_ms,
113                                    StepActions step_actions);
114 
115   // It's hard to know how much work the incremental marker should do to make
116   // progress in the face of the mutator creating new work for it.  We start
117   // of at a moderate rate of work and gradually increase the speed of the
118   // incremental marker until it completes.
119   // Do some marking every time this much memory has been allocated or that many
120   // heavy (color-checking) write barriers have been invoked.
121   static const intptr_t kAllocatedThreshold = 65536;
122   static const intptr_t kWriteBarriersInvokedThreshold = 32768;
123   // Start off by marking this many times more memory than has been allocated.
124   static const intptr_t kInitialMarkingSpeed = 1;
125   // But if we are promoting a lot of data we need to mark faster to keep up
126   // with the data that is entering the old space through promotion.
127   static const intptr_t kFastMarking = 3;
128   // After this many steps we increase the marking/allocating factor.
129   static const intptr_t kMarkingSpeedAccellerationInterval = 1024;
130   // This is how much we increase the marking/allocating factor by.
131   static const intptr_t kMarkingSpeedAccelleration = 2;
132   static const intptr_t kMaxMarkingSpeed = 1000;
133 
134   // This is the upper bound for how many times we allow finalization of
135   // incremental marking to be postponed.
136   static const size_t kMaxIdleMarkingDelayCounter = 3;
137 
138   void OldSpaceStep(intptr_t allocated);
139 
140   intptr_t Step(intptr_t allocated, CompletionAction action,
141                 ForceMarkingAction marking = DO_NOT_FORCE_MARKING,
142                 ForceCompletionAction completion = FORCE_COMPLETION);
143 
RestartIfNotMarking()144   inline void RestartIfNotMarking() {
145     if (state_ == COMPLETE) {
146       state_ = MARKING;
147       if (FLAG_trace_incremental_marking) {
148         PrintF("[IncrementalMarking] Restarting (new grey objects)\n");
149       }
150     }
151   }
152 
153   static void RecordWriteFromCode(HeapObject* obj, Object** slot,
154                                   Isolate* isolate);
155 
156   // Record a slot for compaction.  Returns false for objects that are
157   // guaranteed to be rescanned or not guaranteed to survive.
158   //
159   // No slots in white objects should be recorded, as some slots are typed and
160   // cannot be interpreted correctly if the underlying object does not survive
161   // the incremental cycle (stays white).
162   INLINE(bool BaseRecordWrite(HeapObject* obj, Object* value));
163   INLINE(void RecordWrite(HeapObject* obj, Object** slot, Object* value));
164   INLINE(void RecordWriteIntoCode(HeapObject* obj, RelocInfo* rinfo,
165                                   Object* value));
166   INLINE(void RecordWriteOfCodeEntry(JSFunction* host, Object** slot,
167                                      Code* value));
168 
169 
170   void RecordWriteSlow(HeapObject* obj, Object** slot, Object* value);
171   void RecordWriteIntoCodeSlow(HeapObject* obj, RelocInfo* rinfo,
172                                Object* value);
173   void RecordWriteOfCodeEntrySlow(JSFunction* host, Object** slot, Code* value);
174   void RecordCodeTargetPatch(Code* host, Address pc, HeapObject* value);
175   void RecordCodeTargetPatch(Address pc, HeapObject* value);
176 
177   void RecordWrites(HeapObject* obj);
178 
179   void BlackToGreyAndUnshift(HeapObject* obj, MarkBit mark_bit);
180 
181   void WhiteToGreyAndPush(HeapObject* obj, MarkBit mark_bit);
182 
SetOldSpacePageFlags(MemoryChunk * chunk)183   inline void SetOldSpacePageFlags(MemoryChunk* chunk) {
184     SetOldSpacePageFlags(chunk, IsMarking(), IsCompacting());
185   }
186 
SetNewSpacePageFlags(MemoryChunk * chunk)187   inline void SetNewSpacePageFlags(MemoryChunk* chunk) {
188     SetNewSpacePageFlags(chunk, IsMarking());
189   }
190 
IsCompacting()191   bool IsCompacting() { return IsMarking() && is_compacting_; }
192 
193   void ActivateGeneratedStub(Code* stub);
194 
195   void NotifyOfHighPromotionRate();
196 
EnterNoMarkingScope()197   void EnterNoMarkingScope() { no_marking_scope_depth_++; }
198 
LeaveNoMarkingScope()199   void LeaveNoMarkingScope() { no_marking_scope_depth_--; }
200 
NotifyIncompleteScanOfObject(int unscanned_bytes)201   void NotifyIncompleteScanOfObject(int unscanned_bytes) {
202     unscanned_bytes_of_large_object_ = unscanned_bytes;
203   }
204 
205   void ClearIdleMarkingDelayCounter();
206 
207   bool IsIdleMarkingDelayCounterLimitReached();
208 
209   INLINE(static void MarkObject(Heap* heap, HeapObject* object));
210 
heap()211   Heap* heap() const { return heap_; }
212 
incremental_marking_job()213   IncrementalMarkingJob* incremental_marking_job() {
214     return &incremental_marking_job_;
215   }
216 
217  private:
218   class Observer : public InlineAllocationObserver {
219    public:
Observer(IncrementalMarking & incremental_marking,intptr_t step_size)220     Observer(IncrementalMarking& incremental_marking, intptr_t step_size)
221         : InlineAllocationObserver(step_size),
222           incremental_marking_(incremental_marking) {}
223 
Step(int bytes_allocated,Address,size_t)224     void Step(int bytes_allocated, Address, size_t) override {
225       incremental_marking_.Step(bytes_allocated,
226                                 IncrementalMarking::GC_VIA_STACK_GUARD);
227     }
228 
229    private:
230     IncrementalMarking& incremental_marking_;
231   };
232 
233   int64_t SpaceLeftInOldSpace();
234 
235   void SpeedUp();
236 
237   void ResetStepCounters();
238 
239   void StartMarking();
240 
241   void MarkRoots();
242   void MarkObjectGroups();
243   void ProcessWeakCells();
244   // Retain dying maps for <FLAG_retain_maps_for_n_gc> garbage collections to
245   // increase chances of reusing of map transition tree in future.
246   void RetainMaps();
247 
248   void ActivateIncrementalWriteBarrier(PagedSpace* space);
249   static void ActivateIncrementalWriteBarrier(NewSpace* space);
250   void ActivateIncrementalWriteBarrier();
251 
252   static void DeactivateIncrementalWriteBarrierForSpace(PagedSpace* space);
253   static void DeactivateIncrementalWriteBarrierForSpace(NewSpace* space);
254   void DeactivateIncrementalWriteBarrier();
255 
256   static void SetOldSpacePageFlags(MemoryChunk* chunk, bool is_marking,
257                                    bool is_compacting);
258 
259   static void SetNewSpacePageFlags(MemoryChunk* chunk, bool is_marking);
260 
261   INLINE(void ProcessMarkingDeque());
262 
263   INLINE(intptr_t ProcessMarkingDeque(intptr_t bytes_to_process));
264 
265   INLINE(void VisitObject(Map* map, HeapObject* obj, int size));
266 
267   void IncrementIdleMarkingDelayCounter();
268 
269   Heap* heap_;
270 
271   Observer observer_;
272 
273   State state_;
274   bool is_compacting_;
275 
276   int steps_count_;
277   int64_t old_generation_space_available_at_start_of_incremental_;
278   int64_t old_generation_space_used_at_start_of_incremental_;
279   int64_t bytes_rescanned_;
280   bool should_hurry_;
281   int marking_speed_;
282   intptr_t bytes_scanned_;
283   intptr_t allocated_;
284   intptr_t write_barriers_invoked_since_last_step_;
285   size_t idle_marking_delay_counter_;
286 
287   int no_marking_scope_depth_;
288 
289   int unscanned_bytes_of_large_object_;
290 
291   bool was_activated_;
292 
293   bool finalize_marking_completed_;
294 
295   int incremental_marking_finalization_rounds_;
296 
297   GCRequestType request_type_;
298 
299   IncrementalMarkingJob incremental_marking_job_;
300 
301   DISALLOW_IMPLICIT_CONSTRUCTORS(IncrementalMarking);
302 };
303 }  // namespace internal
304 }  // namespace v8
305 
306 #endif  // V8_HEAP_INCREMENTAL_MARKING_H_
307