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