OLD | NEW |
---|---|
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 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 |
(...skipping 26 matching lines...) Expand all Loading... | |
37 | 37 |
38 // Callback function for non-live blocks in the old generation. | 38 // Callback function for non-live blocks in the old generation. |
39 typedef void (*DeallocateFunction)(Address start, int size_in_bytes); | 39 typedef void (*DeallocateFunction)(Address start, int size_in_bytes); |
40 | 40 |
41 | 41 |
42 // Forward declarations. | 42 // Forward declarations. |
43 class RootMarkingVisitor; | 43 class RootMarkingVisitor; |
44 class MarkingVisitor; | 44 class MarkingVisitor; |
45 | 45 |
46 | 46 |
47 // ---------------------------------------------------------------------------- | 47 // ------------------------------------------------------------------------- |
48 // Mark-Compact collector | 48 // Mark-Compact collector |
49 // | 49 // |
50 // All methods are static. | 50 // All methods are static. |
51 | 51 |
52 class MarkCompactCollector : public AllStatic { | 52 class MarkCompactCollector: public AllStatic { |
53 public: | 53 public: |
54 // Type of functions to compute forwarding addresses of objects in | 54 // Type of functions to compute forwarding addresses of objects in |
55 // compacted spaces. Given an object and its size, return a (non-failure) | 55 // compacted spaces. Given an object and its size, return a (non-failure) |
56 // Object* that will be the object after forwarding. There is a separate | 56 // Object* that will be the object after forwarding. There is a separate |
57 // allocation function for each (compactable) space based on the location | 57 // allocation function for each (compactable) space based on the location |
58 // of the object before compaction. | 58 // of the object before compaction. |
59 typedef Object* (*AllocationFunction)(HeapObject* object, int object_size); | 59 typedef Object* (*AllocationFunction)(HeapObject* object, int object_size); |
60 | 60 |
61 // Type of functions to encode the forwarding address for an object. | 61 // Type of functions to encode the forwarding address for an object. |
62 // Given the object, its size, and the new (non-failure) object it will be | 62 // Given the object, its size, and the new (non-failure) object it will be |
(...skipping 57 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
120 static int previous_marked_count_; | 120 static int previous_marked_count_; |
121 | 121 |
122 // A pointer to the current stack-allocated GC tracer object during a full | 122 // A pointer to the current stack-allocated GC tracer object during a full |
123 // collection (NULL before and after). | 123 // collection (NULL before and after). |
124 static GCTracer* tracer_; | 124 static GCTracer* tracer_; |
125 | 125 |
126 // Prepares for GC by resetting relocation info in old and map spaces and | 126 // Prepares for GC by resetting relocation info in old and map spaces and |
127 // choosing spaces to compact. | 127 // choosing spaces to compact. |
128 static void Prepare(); | 128 static void Prepare(); |
129 | 129 |
130 // Finishes GC, performs heap verification. | 130 // Finishes GC, performs heap verification if enabled. |
131 static void Finish(); | 131 static void Finish(); |
132 | 132 |
133 // -------------------------------------------------------------------------- | 133 // ----------------------------------------------------------------------- |
134 // Phase 1: functions related to marking phase. | 134 // Phase 1: Marking live objects. |
135 // before: Heap is in normal state, collector is 'IDLE'. | |
136 // | 135 // |
137 // The first word of a page in old spaces has the end of | 136 // Before: The heap has been prepared for garbage collection by |
138 // allocation address of the page. | 137 // MarkCompactCollector::Prepare() and is otherwise in its |
138 // normal state. | |
139 // | 139 // |
140 // The word at Chunk::high_ address has the address of the | 140 // After: Live objects are marked and non-live objects are unmarked. |
141 // first page in the next chunk. (The address is tagged to | 141 |
142 // distinguish it from end-of-allocation address). | |
143 // | |
144 // after: live objects are marked. | |
145 | 142 |
146 friend class RootMarkingVisitor; | 143 friend class RootMarkingVisitor; |
147 friend class MarkingVisitor; | 144 friend class MarkingVisitor; |
148 | 145 |
149 // Marking operations for objects reachable from roots. | 146 // Marking operations for objects reachable from roots. |
150 static void MarkLiveObjects(); | 147 static void MarkLiveObjects(); |
151 | 148 |
152 static void MarkUnmarkedObject(HeapObject* obj); | 149 static void MarkUnmarkedObject(HeapObject* obj); |
153 | 150 |
154 static inline void MarkObject(HeapObject* obj) { | 151 static inline void MarkObject(HeapObject* obj) { |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
199 // Refill the marking stack with overflowed objects from the heap. This | 196 // Refill the marking stack with overflowed objects from the heap. This |
200 // function either leaves the marking stack full or clears the overflow | 197 // function either leaves the marking stack full or clears the overflow |
201 // flag on the marking stack. | 198 // flag on the marking stack. |
202 static void RefillMarkingStack(); | 199 static void RefillMarkingStack(); |
203 | 200 |
204 // Callback function for telling whether the object *p must be marked. | 201 // Callback function for telling whether the object *p must be marked. |
205 static bool MustBeMarked(Object** p); | 202 static bool MustBeMarked(Object** p); |
206 | 203 |
207 #ifdef DEBUG | 204 #ifdef DEBUG |
208 static void UpdateLiveObjectCount(HeapObject* obj); | 205 static void UpdateLiveObjectCount(HeapObject* obj); |
209 static void VerifyHeapAfterMarkingPhase(); | |
210 #endif | 206 #endif |
211 | 207 |
212 // We sweep the large object space in the same way whether we are | 208 // We sweep the large object space in the same way whether we are |
213 // compacting or not, because the large object space is never compacted. | 209 // compacting or not, because the large object space is never compacted. |
214 static void SweepLargeObjectSpace(); | 210 static void SweepLargeObjectSpace(); |
215 | 211 |
216 // Test whether a (possibly marked) object is a Map. | 212 // Test whether a (possibly marked) object is a Map. |
217 static inline bool SafeIsMap(HeapObject* object); | 213 static inline bool SafeIsMap(HeapObject* object); |
218 | 214 |
219 // Map transitions from a live map to a dead map must be killed. | 215 // Map transitions from a live map to a dead map must be killed. |
220 // We replace them with a null descriptor, with the same key. | 216 // We replace them with a null descriptor, with the same key. |
221 static void ClearNonLiveTransitions(); | 217 static void ClearNonLiveTransitions(); |
222 | 218 |
223 // -------------------------------------------------------------------------- | 219 // ----------------------------------------------------------------------- |
224 // Phase 2: functions related to computing and encoding forwarding pointers | 220 // Phase 2: Sweeping to clear mark bits and free non-live objects for |
225 // before: live objects' map pointers are marked as '00' | 221 // a non-compacting collection, or else computing and encoding |
226 // after: Map pointers of live old and map objects have encoded | 222 // forwarding addresses for a compacting collection. |
227 // forwarding pointers and map pointers | |
228 // | 223 // |
229 // The 3rd word of a page has the page top offset after compaction. | 224 // Before: Live objects are marked and non-live objects are unmarked. |
230 // | 225 // |
231 // The 4th word of a page in the map space has the map index | 226 // After: (Non-compacting collection.) Live objects are unmarked, |
232 // of this page in the map table. This word is not used in | 227 // non-live regions have been added to their space's free |
233 // the old space. | 228 // list. |
234 // | 229 // |
235 // The 5th and 6th words of a page have the start and end | 230 // After: (Compacting collection.) The forwarding address of live |
236 // addresses of the first free region in the page. | 231 // objects in the paged spaces is encoded in their map word |
232 // along with their (non-forwarded) map pointer. | |
237 // | 233 // |
238 // The 7th word of a page in old spaces has the forwarding address | 234 // The forwarding address of live objects in the new space is |
239 // of the first live object in the page. | 235 // written to their map word's offset in the inactive |
236 // semispace. | |
240 // | 237 // |
241 // Live young objects have their forwarding pointers in | 238 // Bookkeeping data is written to the remembered-set are of |
Mads Ager (chromium)
2009/01/22 18:37:23
are of eached -> of each
| |
242 // the from space at the same offset to the beginning of the space. | 239 // eached paged-space page that contains live objects after |
240 // compaction: | |
241 // | |
242 // The 3rd word of the page (first word of the remembered | |
243 // set) contains the relocation top address, the address of | |
244 // the first word after the end of the last live object in | |
245 // the page after compaction. | |
246 // | |
247 // The 4th word contains the zero-based index of the page in | |
248 // its space. This word is only used for map space pages, in | |
249 // order to encode the map addresses in 21 bits to free 11 | |
250 // bits per map word for the forwarding address. | |
251 // | |
252 // The 5th word contains the (nonencoded) forwarding address | |
253 // of the first live object in the page. | |
254 // | |
255 // In both the new space and the paged spaces, a linked list | |
256 // of live regions is constructructed (linked through | |
257 // pointers in the non-live region immediately following each | |
258 // live region) to speed further passes of the collector. | |
243 | 259 |
244 // Encodes forwarding addresses of objects in compactable parts of the | 260 // Encodes forwarding addresses of objects in compactable parts of the |
245 // heap. | 261 // heap. |
246 static void EncodeForwardingAddresses(); | 262 static void EncodeForwardingAddresses(); |
247 | 263 |
248 // Encodes the forwarding addresses of objects in new space. | 264 // Encodes the forwarding addresses of objects in new space. |
249 static void EncodeForwardingAddressesInNewSpace(); | 265 static void EncodeForwardingAddressesInNewSpace(); |
250 | 266 |
251 // Function template to encode the forwarding addresses of objects in | 267 // Function template to encode the forwarding addresses of objects in |
252 // paged spaces, parameterized by allocation and non-live processing | 268 // paged spaces, parameterized by allocation and non-live processing |
(...skipping 12 matching lines...) Expand all Loading... | |
265 static int IterateLiveObjectsInRange(Address start, Address end, | 281 static int IterateLiveObjectsInRange(Address start, Address end, |
266 HeapObjectCallback size_func); | 282 HeapObjectCallback size_func); |
267 | 283 |
268 // Callback functions for deallocating non-live blocks in the old | 284 // Callback functions for deallocating non-live blocks in the old |
269 // generation. | 285 // generation. |
270 static void DeallocateOldPointerBlock(Address start, int size_in_bytes); | 286 static void DeallocateOldPointerBlock(Address start, int size_in_bytes); |
271 static void DeallocateOldDataBlock(Address start, int size_in_bytes); | 287 static void DeallocateOldDataBlock(Address start, int size_in_bytes); |
272 static void DeallocateCodeBlock(Address start, int size_in_bytes); | 288 static void DeallocateCodeBlock(Address start, int size_in_bytes); |
273 static void DeallocateMapBlock(Address start, int size_in_bytes); | 289 static void DeallocateMapBlock(Address start, int size_in_bytes); |
274 | 290 |
275 // Phase 2: If we are not compacting the heap, we simply sweep the spaces | 291 // If we are not compacting the heap, we simply sweep the spaces except |
276 // except for the large object space, clearing mark bits and adding | 292 // for the large object space, clearing mark bits and adding unmarked |
277 // unmarked regions to each space's free list. | 293 // regions to each space's free list. |
278 static void SweepSpaces(); | 294 static void SweepSpaces(); |
279 | 295 |
280 #ifdef DEBUG | 296 // ----------------------------------------------------------------------- |
281 static void VerifyHeapAfterEncodingForwardingAddresses(); | 297 // Phase 3: Updating pointers in live objects. |
282 #endif | 298 // |
283 | 299 // Before: Same as after phase 2 (compacting collection). |
284 // -------------------------------------------------------------------------- | 300 // |
285 // Phase 3: function related to updating pointers and decode map pointers | 301 // After: All pointers in live objects, including encoded map |
286 // before: see after phase 2 | 302 // pointers, are updated to point to their target's new |
287 // after: all pointers are updated to forwarding addresses. | 303 // location. The remembered set area of each paged-space |
304 // page containing live objects still contains bookkeeping | |
305 // information. | |
288 | 306 |
289 friend class UpdatingVisitor; // helper for updating visited objects | 307 friend class UpdatingVisitor; // helper for updating visited objects |
290 | 308 |
291 // Updates pointers in all spaces. | 309 // Updates pointers in all spaces. |
292 static void UpdatePointers(); | 310 static void UpdatePointers(); |
293 | 311 |
294 // Updates pointers in an object in new space. | 312 // Updates pointers in an object in new space. |
295 // Returns the heap size of the object. | 313 // Returns the heap size of the object. |
296 static int UpdatePointersInNewObject(HeapObject* obj); | 314 static int UpdatePointersInNewObject(HeapObject* obj); |
297 | 315 |
298 // Updates pointers in an object in old spaces. | 316 // Updates pointers in an object in old spaces. |
299 // Returns the heap size of the object. | 317 // Returns the heap size of the object. |
300 static int UpdatePointersInOldObject(HeapObject* obj); | 318 static int UpdatePointersInOldObject(HeapObject* obj); |
301 | 319 |
302 // Calculates the forwarding address of an object in an old space. | 320 // Calculates the forwarding address of an object in an old space. |
303 static Address GetForwardingAddressInOldSpace(HeapObject* obj); | 321 static Address GetForwardingAddressInOldSpace(HeapObject* obj); |
304 | 322 |
305 #ifdef DEBUG | 323 // ----------------------------------------------------------------------- |
306 static void VerifyHeapAfterUpdatingPointers(); | 324 // Phase 4: Relocating objects. |
307 #endif | 325 // |
308 | 326 // Before: Pointers to live objects are updated to point to their |
309 // -------------------------------------------------------------------------- | 327 // target's new location. The remembered set area of each |
310 // Phase 4: functions related to relocating objects | 328 // paged-space page containing live objects still contains |
311 // before: see after phase 3 | 329 // bookkeeping information. |
312 // after: heap is in a normal state, except remembered set is not built | 330 // |
331 // After: Objects have been moved to their new addresses. The | |
332 // remembered set area of each paged-space page containing | |
333 // live objects still contains bookkeeping information. | |
313 | 334 |
314 // Relocates objects in all spaces. | 335 // Relocates objects in all spaces. |
315 static void RelocateObjects(); | 336 static void RelocateObjects(); |
316 | 337 |
317 // Converts a code object's inline target to addresses, convention from | 338 // Converts a code object's inline target to addresses, convention from |
318 // address to target happens in the marking phase. | 339 // address to target happens in the marking phase. |
319 static int ConvertCodeICTargetToAddress(HeapObject* obj); | 340 static int ConvertCodeICTargetToAddress(HeapObject* obj); |
320 | 341 |
321 // Relocate a map object. | 342 // Relocate a map object. |
322 static int RelocateMapObject(HeapObject* obj); | 343 static int RelocateMapObject(HeapObject* obj); |
323 | 344 |
324 // Relocates an old object. | 345 // Relocates an old object. |
325 static int RelocateOldPointerObject(HeapObject* obj); | 346 static int RelocateOldPointerObject(HeapObject* obj); |
326 static int RelocateOldDataObject(HeapObject* obj); | 347 static int RelocateOldDataObject(HeapObject* obj); |
327 | 348 |
328 // Helper function. | 349 // Helper function. |
329 static inline int RelocateOldNonCodeObject(HeapObject* obj, OldSpace* space); | 350 static inline int RelocateOldNonCodeObject(HeapObject* obj, OldSpace* space); |
330 | 351 |
331 // Relocates an object in the code space. | 352 // Relocates an object in the code space. |
332 static int RelocateCodeObject(HeapObject* obj); | 353 static int RelocateCodeObject(HeapObject* obj); |
333 | 354 |
334 // Copy a new object. | 355 // Copy a new object. |
335 static int RelocateNewObject(HeapObject* obj); | 356 static int RelocateNewObject(HeapObject* obj); |
336 | 357 |
337 #ifdef DEBUG | 358 // ----------------------------------------------------------------------- |
338 static void VerifyHeapAfterRelocatingObjects(); | 359 // Phase 5: Rebuilding remembered sets. |
339 #endif | 360 // |
340 | 361 // Before: The heap is in a normal state except that remembered sets |
341 // --------------------------------------------------------------------------- | 362 // in the paged spaces are not correct. |
342 // Phase 5: functions related to rebuilding remembered sets | 363 // |
364 // After: The heap is in a normal state. | |
343 | 365 |
344 // Rebuild remembered set in old and map spaces. | 366 // Rebuild remembered set in old and map spaces. |
345 static void RebuildRSets(); | 367 static void RebuildRSets(); |
346 | 368 |
347 #ifdef DEBUG | 369 #ifdef DEBUG |
348 // --------------------------------------------------------------------------- | 370 // ----------------------------------------------------------------------- |
349 // Debugging variables, functions and classes | 371 // Debugging variables, functions and classes |
350 // Counters used for debugging the marking phase of mark-compact or | 372 // Counters used for debugging the marking phase of mark-compact or |
351 // mark-sweep collection. | 373 // mark-sweep collection. |
352 | 374 |
353 // Number of live objects in Heap::to_space_. | 375 // Number of live objects in Heap::to_space_. |
354 static int live_young_objects_; | 376 static int live_young_objects_; |
355 | 377 |
356 // Number of live objects in Heap::old_pointer_space_. | 378 // Number of live objects in Heap::old_pointer_space_. |
357 static int live_old_pointer_objects_; | 379 static int live_old_pointer_objects_; |
358 | 380 |
359 // Number of live objects in Heap::old_data_space_. | 381 // Number of live objects in Heap::old_data_space_. |
360 static int live_old_data_objects_; | 382 static int live_old_data_objects_; |
361 | 383 |
362 // Number of live objects in Heap::code_space_. | 384 // Number of live objects in Heap::code_space_. |
363 static int live_code_objects_; | 385 static int live_code_objects_; |
364 | 386 |
365 // Number of live objects in Heap::map_space_. | 387 // Number of live objects in Heap::map_space_. |
366 static int live_map_objects_; | 388 static int live_map_objects_; |
367 | 389 |
368 // Number of live objects in Heap::lo_space_. | 390 // Number of live objects in Heap::lo_space_. |
369 static int live_lo_objects_; | 391 static int live_lo_objects_; |
370 | 392 |
371 // Number of live bytes in this collection. | 393 // Number of live bytes in this collection. |
372 static int live_bytes_; | 394 static int live_bytes_; |
373 | 395 |
374 static void VerifyPageHeaders(PagedSpace* space); | |
375 | |
376 // Verification functions when relocating objects. | |
377 friend class VerifyCopyingVisitor; | |
378 static void VerifyCopyingObjects(Object** p); | |
379 | |
380 friend class MarkObjectVisitor; | 396 friend class MarkObjectVisitor; |
381 static void VisitObject(HeapObject* obj); | 397 static void VisitObject(HeapObject* obj); |
382 | 398 |
383 friend class UnmarkObjectVisitor; | 399 friend class UnmarkObjectVisitor; |
384 static void UnmarkObject(HeapObject* obj); | 400 static void UnmarkObject(HeapObject* obj); |
385 #endif | 401 #endif |
386 }; | 402 }; |
387 | 403 |
388 | 404 |
389 } } // namespace v8::internal | 405 } } // namespace v8::internal |
390 | 406 |
391 #endif // V8_MARK_COMPACT_H_ | 407 #endif // V8_MARK_COMPACT_H_ |
OLD | NEW |