1// Copyright 2011 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_INCREMENTAL_MARKING_H_
29#define V8_INCREMENTAL_MARKING_H_
30
31
32#include "execution.h"
33#include "mark-compact.h"
34#include "objects.h"
35
36namespace v8 {
37namespace internal {
38
39
40class IncrementalMarking {
41 public:
42  enum State {
43    STOPPED,
44    SWEEPING,
45    MARKING,
46    COMPLETE
47  };
48
49  enum CompletionAction {
50    GC_VIA_STACK_GUARD,
51    NO_GC_VIA_STACK_GUARD
52  };
53
54  explicit IncrementalMarking(Heap* heap);
55
56  void TearDown();
57
58  State state() {
59    ASSERT(state_ == STOPPED || FLAG_incremental_marking);
60    return state_;
61  }
62
63  bool should_hurry() { return should_hurry_; }
64  void set_should_hurry(bool val) { should_hurry_ = val; }
65
66  inline bool IsStopped() { return state() == STOPPED; }
67
68  INLINE(bool IsMarking()) { return state() >= MARKING; }
69
70  inline bool IsMarkingIncomplete() { return state() == MARKING; }
71
72  inline bool IsComplete() { return state() == COMPLETE; }
73
74  bool WorthActivating();
75
76  void Start();
77
78  void Stop();
79
80  void PrepareForScavenge();
81
82  void UpdateMarkingDequeAfterScavenge();
83
84  void Hurry();
85
86  void Finalize();
87
88  void Abort();
89
90  void MarkingComplete(CompletionAction action);
91
92  // It's hard to know how much work the incremental marker should do to make
93  // progress in the face of the mutator creating new work for it.  We start
94  // of at a moderate rate of work and gradually increase the speed of the
95  // incremental marker until it completes.
96  // Do some marking every time this much memory has been allocated.
97  static const intptr_t kAllocatedThreshold = 65536;
98  // Start off by marking this many times more memory than has been allocated.
99  static const intptr_t kInitialAllocationMarkingFactor = 1;
100  // But if we are promoting a lot of data we need to mark faster to keep up
101  // with the data that is entering the old space through promotion.
102  static const intptr_t kFastMarking = 3;
103  // After this many steps we increase the marking/allocating factor.
104  static const intptr_t kAllocationMarkingFactorSpeedupInterval = 1024;
105  // This is how much we increase the marking/allocating factor by.
106  static const intptr_t kAllocationMarkingFactorSpeedup = 2;
107  static const intptr_t kMaxAllocationMarkingFactor = 1000;
108
109  void OldSpaceStep(intptr_t allocated) {
110    Step(allocated * kFastMarking / kInitialAllocationMarkingFactor,
111         GC_VIA_STACK_GUARD);
112  }
113
114  void Step(intptr_t allocated, CompletionAction action);
115
116  inline void RestartIfNotMarking() {
117    if (state_ == COMPLETE) {
118      state_ = MARKING;
119      if (FLAG_trace_incremental_marking) {
120        PrintF("[IncrementalMarking] Restarting (new grey objects)\n");
121      }
122    }
123  }
124
125  static void RecordWriteFromCode(HeapObject* obj,
126                                  Object* value,
127                                  Isolate* isolate);
128
129  static void RecordWriteForEvacuationFromCode(HeapObject* obj,
130                                               Object** slot,
131                                               Isolate* isolate);
132
133  INLINE(bool BaseRecordWrite(HeapObject* obj, Object** slot, Object* value));
134  INLINE(void RecordWrite(HeapObject* obj, Object** slot, Object* value));
135  INLINE(void RecordWriteIntoCode(HeapObject* obj,
136                                  RelocInfo* rinfo,
137                                  Object* value));
138  INLINE(void RecordWriteOfCodeEntry(JSFunction* host,
139                                     Object** slot,
140                                     Code* value));
141
142
143  void RecordWriteSlow(HeapObject* obj, Object** slot, Object* value);
144  void RecordWriteIntoCodeSlow(HeapObject* obj,
145                               RelocInfo* rinfo,
146                               Object* value);
147  void RecordWriteOfCodeEntrySlow(JSFunction* host, Object** slot, Code* value);
148  void RecordCodeTargetPatch(Code* host, Address pc, HeapObject* value);
149  void RecordCodeTargetPatch(Address pc, HeapObject* value);
150
151  inline void RecordWrites(HeapObject* obj);
152
153  inline void BlackToGreyAndUnshift(HeapObject* obj, MarkBit mark_bit);
154
155  inline void WhiteToGreyAndPush(HeapObject* obj, MarkBit mark_bit);
156
157  inline void WhiteToGrey(HeapObject* obj, MarkBit mark_bit);
158
159  // Does white->black or keeps gray or black color. Returns true if converting
160  // white to black.
161  inline bool MarkBlackOrKeepGrey(MarkBit mark_bit) {
162    ASSERT(!Marking::IsImpossible(mark_bit));
163    if (mark_bit.Get()) {
164      // Grey or black: Keep the color.
165      return false;
166    }
167    mark_bit.Set();
168    ASSERT(Marking::IsBlack(mark_bit));
169    return true;
170  }
171
172  inline int steps_count() {
173    return steps_count_;
174  }
175
176  inline double steps_took() {
177    return steps_took_;
178  }
179
180  inline double longest_step() {
181    return longest_step_;
182  }
183
184  inline int steps_count_since_last_gc() {
185    return steps_count_since_last_gc_;
186  }
187
188  inline double steps_took_since_last_gc() {
189    return steps_took_since_last_gc_;
190  }
191
192  inline void SetOldSpacePageFlags(MemoryChunk* chunk) {
193    SetOldSpacePageFlags(chunk, IsMarking(), IsCompacting());
194  }
195
196  inline void SetNewSpacePageFlags(NewSpacePage* chunk) {
197    SetNewSpacePageFlags(chunk, IsMarking());
198  }
199
200  MarkingDeque* marking_deque() { return &marking_deque_; }
201
202  bool IsCompacting() { return IsMarking() && is_compacting_; }
203
204  void ActivateGeneratedStub(Code* stub);
205
206  void NotifyOfHighPromotionRate() {
207    if (IsMarking()) {
208      if (allocation_marking_factor_ < kFastMarking) {
209        if (FLAG_trace_gc) {
210          PrintF("Increasing marking speed to %d due to high promotion rate\n",
211                 static_cast<int>(kFastMarking));
212        }
213        allocation_marking_factor_ = kFastMarking;
214      }
215    }
216  }
217
218  void EnterNoMarkingScope() {
219    no_marking_scope_depth_++;
220  }
221
222  void LeaveNoMarkingScope() {
223    no_marking_scope_depth_--;
224  }
225
226  void UncommitMarkingDeque();
227
228 private:
229  int64_t SpaceLeftInOldSpace();
230
231  void ResetStepCounters();
232
233  enum CompactionFlag { ALLOW_COMPACTION, PREVENT_COMPACTION };
234
235  void StartMarking(CompactionFlag flag);
236
237  void ActivateIncrementalWriteBarrier(PagedSpace* space);
238  static void ActivateIncrementalWriteBarrier(NewSpace* space);
239  void ActivateIncrementalWriteBarrier();
240
241  static void DeactivateIncrementalWriteBarrierForSpace(PagedSpace* space);
242  static void DeactivateIncrementalWriteBarrierForSpace(NewSpace* space);
243  void DeactivateIncrementalWriteBarrier();
244
245  static void SetOldSpacePageFlags(MemoryChunk* chunk,
246                                   bool is_marking,
247                                   bool is_compacting);
248
249  static void SetNewSpacePageFlags(NewSpacePage* chunk, bool is_marking);
250
251  void EnsureMarkingDequeIsCommitted();
252
253  void VisitGlobalContext(Context* ctx, ObjectVisitor* v);
254
255  Heap* heap_;
256
257  State state_;
258  bool is_compacting_;
259
260  VirtualMemory* marking_deque_memory_;
261  bool marking_deque_memory_committed_;
262  MarkingDeque marking_deque_;
263
264  int steps_count_;
265  double steps_took_;
266  double longest_step_;
267  int64_t old_generation_space_available_at_start_of_incremental_;
268  int64_t old_generation_space_used_at_start_of_incremental_;
269  int steps_count_since_last_gc_;
270  double steps_took_since_last_gc_;
271  int64_t bytes_rescanned_;
272  bool should_hurry_;
273  int allocation_marking_factor_;
274  intptr_t bytes_scanned_;
275  intptr_t allocated_;
276
277  int no_marking_scope_depth_;
278
279  DISALLOW_IMPLICIT_CONSTRUCTORS(IncrementalMarking);
280};
281
282} }  // namespace v8::internal
283
284#endif  // V8_INCREMENTAL_MARKING_H_
285