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 23 matching lines...) Expand all Loading... |
34 // Callback function, returns whether an object is alive. The heap size | 34 // Callback function, returns whether an object is alive. The heap size |
35 // of the object is returned in size. It optionally updates the offset | 35 // of the object is returned in size. It optionally updates the offset |
36 // to the first live object in the page (only used for old and map objects). | 36 // to the first live object in the page (only used for old and map objects). |
37 typedef bool (*IsAliveFunction)(HeapObject* obj, int* size, int* offset); | 37 typedef bool (*IsAliveFunction)(HeapObject* obj, int* size, int* offset); |
38 | 38 |
39 // Callback function for non-live blocks in the old generation. | 39 // Callback function for non-live blocks in the old generation. |
40 // If add_to_freelist is false then just accounting stats are updated and | 40 // If add_to_freelist is false then just accounting stats are updated and |
41 // no attempt to add area to free list is made. | 41 // no attempt to add area to free list is made. |
42 typedef void (*DeallocateFunction)(Address start, | 42 typedef void (*DeallocateFunction)(Address start, |
43 int size_in_bytes, | 43 int size_in_bytes, |
44 bool add_to_freelist); | 44 bool add_to_freelist, |
| 45 bool last_on_page); |
45 | 46 |
46 | 47 |
47 // Forward declarations. | 48 // Forward declarations. |
48 class RootMarkingVisitor; | 49 class RootMarkingVisitor; |
49 class MarkingVisitor; | 50 class MarkingVisitor; |
50 | 51 |
51 | 52 |
52 // ------------------------------------------------------------------------- | 53 // ------------------------------------------------------------------------- |
53 // Mark-Compact collector | 54 // Mark-Compact collector |
54 // | 55 // |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
124 | 125 |
125 private: | 126 private: |
126 #ifdef DEBUG | 127 #ifdef DEBUG |
127 enum CollectorState { | 128 enum CollectorState { |
128 IDLE, | 129 IDLE, |
129 PREPARE_GC, | 130 PREPARE_GC, |
130 MARK_LIVE_OBJECTS, | 131 MARK_LIVE_OBJECTS, |
131 SWEEP_SPACES, | 132 SWEEP_SPACES, |
132 ENCODE_FORWARDING_ADDRESSES, | 133 ENCODE_FORWARDING_ADDRESSES, |
133 UPDATE_POINTERS, | 134 UPDATE_POINTERS, |
134 RELOCATE_OBJECTS, | 135 RELOCATE_OBJECTS |
135 REBUILD_RSETS | |
136 }; | 136 }; |
137 | 137 |
138 // The current stage of the collector. | 138 // The current stage of the collector. |
139 static CollectorState state_; | 139 static CollectorState state_; |
140 #endif | 140 #endif |
141 | 141 |
142 // Global flag that forces a compaction. | 142 // Global flag that forces a compaction. |
143 static bool force_compaction_; | 143 static bool force_compaction_; |
144 | 144 |
145 // Global flag indicating whether spaces were compacted on the last GC. | 145 // Global flag indicating whether spaces were compacted on the last GC. |
(...skipping 116 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
262 // list. | 262 // list. |
263 // | 263 // |
264 // After: (Compacting collection.) The forwarding address of live | 264 // After: (Compacting collection.) The forwarding address of live |
265 // objects in the paged spaces is encoded in their map word | 265 // objects in the paged spaces is encoded in their map word |
266 // along with their (non-forwarded) map pointer. | 266 // along with their (non-forwarded) map pointer. |
267 // | 267 // |
268 // The forwarding address of live objects in the new space is | 268 // The forwarding address of live objects in the new space is |
269 // written to their map word's offset in the inactive | 269 // written to their map word's offset in the inactive |
270 // semispace. | 270 // semispace. |
271 // | 271 // |
272 // Bookkeeping data is written to the remembered-set are of | 272 // Bookkeeping data is written to the page header of |
273 // eached paged-space page that contains live objects after | 273 // eached paged-space page that contains live objects after |
274 // compaction: | 274 // compaction: |
275 // | 275 // |
276 // The 3rd word of the page (first word of the remembered | 276 // The allocation watermark field is used to track the |
277 // set) contains the relocation top address, the address of | 277 // relocation top address, the address of the first word |
278 // the first word after the end of the last live object in | 278 // after the end of the last live object in the page after |
279 // the page after compaction. | 279 // compaction. |
280 // | 280 // |
281 // The 4th word contains the zero-based index of the page in | 281 // The Page::mc_page_index field contains the zero-based index of the |
282 // its space. This word is only used for map space pages, in | 282 // page in its space. This word is only used for map space pages, in |
283 // order to encode the map addresses in 21 bits to free 11 | 283 // order to encode the map addresses in 21 bits to free 11 |
284 // bits per map word for the forwarding address. | 284 // bits per map word for the forwarding address. |
285 // | 285 // |
286 // The 5th word contains the (nonencoded) forwarding address | 286 // The Page::mc_first_forwarded field contains the (nonencoded) |
287 // of the first live object in the page. | 287 // forwarding address of the first live object in the page. |
288 // | 288 // |
289 // In both the new space and the paged spaces, a linked list | 289 // In both the new space and the paged spaces, a linked list |
290 // of live regions is constructructed (linked through | 290 // of live regions is constructructed (linked through |
291 // pointers in the non-live region immediately following each | 291 // pointers in the non-live region immediately following each |
292 // live region) to speed further passes of the collector. | 292 // live region) to speed further passes of the collector. |
293 | 293 |
294 // Encodes forwarding addresses of objects in compactable parts of the | 294 // Encodes forwarding addresses of objects in compactable parts of the |
295 // heap. | 295 // heap. |
296 static void EncodeForwardingAddresses(); | 296 static void EncodeForwardingAddresses(); |
297 | 297 |
(...skipping 14 matching lines...) Expand all Loading... |
312 | 312 |
313 // Iterates the live objects between a range of addresses, returning the | 313 // Iterates the live objects between a range of addresses, returning the |
314 // number of live objects. | 314 // number of live objects. |
315 static int IterateLiveObjectsInRange(Address start, Address end, | 315 static int IterateLiveObjectsInRange(Address start, Address end, |
316 HeapObjectCallback size_func); | 316 HeapObjectCallback size_func); |
317 | 317 |
318 // Callback functions for deallocating non-live blocks in the old | 318 // Callback functions for deallocating non-live blocks in the old |
319 // generation. | 319 // generation. |
320 static void DeallocateOldPointerBlock(Address start, | 320 static void DeallocateOldPointerBlock(Address start, |
321 int size_in_bytes, | 321 int size_in_bytes, |
322 bool add_to_freelist); | 322 bool add_to_freelist, |
| 323 bool last_on_page); |
323 | 324 |
324 static void DeallocateOldDataBlock(Address start, | 325 static void DeallocateOldDataBlock(Address start, |
325 int size_in_bytes, | 326 int size_in_bytes, |
326 bool add_to_freelist); | 327 bool add_to_freelist, |
| 328 bool last_on_page); |
327 | 329 |
328 static void DeallocateCodeBlock(Address start, | 330 static void DeallocateCodeBlock(Address start, |
329 int size_in_bytes, | 331 int size_in_bytes, |
330 bool add_to_freelist); | 332 bool add_to_freelist, |
| 333 bool last_on_page); |
331 | 334 |
332 static void DeallocateMapBlock(Address start, | 335 static void DeallocateMapBlock(Address start, |
333 int size_in_bytes, | 336 int size_in_bytes, |
334 bool add_to_freelist); | 337 bool add_to_freelist, |
| 338 bool last_on_page); |
335 | 339 |
336 static void DeallocateCellBlock(Address start, | 340 static void DeallocateCellBlock(Address start, |
337 int size_in_bytes, | 341 int size_in_bytes, |
338 bool add_to_freelist); | 342 bool add_to_freelist, |
| 343 bool last_on_page); |
339 | 344 |
340 // If we are not compacting the heap, we simply sweep the spaces except | 345 // If we are not compacting the heap, we simply sweep the spaces except |
341 // for the large object space, clearing mark bits and adding unmarked | 346 // for the large object space, clearing mark bits and adding unmarked |
342 // regions to each space's free list. | 347 // regions to each space's free list. |
343 static void SweepSpaces(); | 348 static void SweepSpaces(); |
344 | 349 |
345 // ----------------------------------------------------------------------- | 350 // ----------------------------------------------------------------------- |
346 // Phase 3: Updating pointers in live objects. | 351 // Phase 3: Updating pointers in live objects. |
347 // | 352 // |
348 // Before: Same as after phase 2 (compacting collection). | 353 // Before: Same as after phase 2 (compacting collection). |
349 // | 354 // |
350 // After: All pointers in live objects, including encoded map | 355 // After: All pointers in live objects, including encoded map |
351 // pointers, are updated to point to their target's new | 356 // pointers, are updated to point to their target's new |
352 // location. The remembered set area of each paged-space | 357 // location. |
353 // page containing live objects still contains bookkeeping | |
354 // information. | |
355 | 358 |
356 friend class UpdatingVisitor; // helper for updating visited objects | 359 friend class UpdatingVisitor; // helper for updating visited objects |
357 | 360 |
358 // Updates pointers in all spaces. | 361 // Updates pointers in all spaces. |
359 static void UpdatePointers(); | 362 static void UpdatePointers(); |
360 | 363 |
361 // Updates pointers in an object in new space. | 364 // Updates pointers in an object in new space. |
362 // Returns the heap size of the object. | 365 // Returns the heap size of the object. |
363 static int UpdatePointersInNewObject(HeapObject* obj); | 366 static int UpdatePointersInNewObject(HeapObject* obj); |
364 | 367 |
365 // Updates pointers in an object in old spaces. | 368 // Updates pointers in an object in old spaces. |
366 // Returns the heap size of the object. | 369 // Returns the heap size of the object. |
367 static int UpdatePointersInOldObject(HeapObject* obj); | 370 static int UpdatePointersInOldObject(HeapObject* obj); |
368 | 371 |
369 // Calculates the forwarding address of an object in an old space. | 372 // Calculates the forwarding address of an object in an old space. |
370 static Address GetForwardingAddressInOldSpace(HeapObject* obj); | 373 static Address GetForwardingAddressInOldSpace(HeapObject* obj); |
371 | 374 |
372 // ----------------------------------------------------------------------- | 375 // ----------------------------------------------------------------------- |
373 // Phase 4: Relocating objects. | 376 // Phase 4: Relocating objects. |
374 // | 377 // |
375 // Before: Pointers to live objects are updated to point to their | 378 // Before: Pointers to live objects are updated to point to their |
376 // target's new location. The remembered set area of each | 379 // target's new location. |
377 // paged-space page containing live objects still contains | |
378 // bookkeeping information. | |
379 // | 380 // |
380 // After: Objects have been moved to their new addresses. The | 381 // After: Objects have been moved to their new addresses. |
381 // remembered set area of each paged-space page containing | |
382 // live objects still contains bookkeeping information. | |
383 | 382 |
384 // Relocates objects in all spaces. | 383 // Relocates objects in all spaces. |
385 static void RelocateObjects(); | 384 static void RelocateObjects(); |
386 | 385 |
387 // Converts a code object's inline target to addresses, convention from | 386 // Converts a code object's inline target to addresses, convention from |
388 // address to target happens in the marking phase. | 387 // address to target happens in the marking phase. |
389 static int ConvertCodeICTargetToAddress(HeapObject* obj); | 388 static int ConvertCodeICTargetToAddress(HeapObject* obj); |
390 | 389 |
391 // Relocate a map object. | 390 // Relocate a map object. |
392 static int RelocateMapObject(HeapObject* obj); | 391 static int RelocateMapObject(HeapObject* obj); |
393 | 392 |
394 // Relocates an old object. | 393 // Relocates an old object. |
395 static int RelocateOldPointerObject(HeapObject* obj); | 394 static int RelocateOldPointerObject(HeapObject* obj); |
396 static int RelocateOldDataObject(HeapObject* obj); | 395 static int RelocateOldDataObject(HeapObject* obj); |
397 | 396 |
398 // Relocate a property cell object. | 397 // Relocate a property cell object. |
399 static int RelocateCellObject(HeapObject* obj); | 398 static int RelocateCellObject(HeapObject* obj); |
400 | 399 |
401 // Helper function. | 400 // Helper function. |
402 static inline int RelocateOldNonCodeObject(HeapObject* obj, | 401 static inline int RelocateOldNonCodeObject(HeapObject* obj, |
403 PagedSpace* space); | 402 PagedSpace* space); |
404 | 403 |
405 // Relocates an object in the code space. | 404 // Relocates an object in the code space. |
406 static int RelocateCodeObject(HeapObject* obj); | 405 static int RelocateCodeObject(HeapObject* obj); |
407 | 406 |
408 // Copy a new object. | 407 // Copy a new object. |
409 static int RelocateNewObject(HeapObject* obj); | 408 static int RelocateNewObject(HeapObject* obj); |
410 | 409 |
411 // ----------------------------------------------------------------------- | |
412 // Phase 5: Rebuilding remembered sets. | |
413 // | |
414 // Before: The heap is in a normal state except that remembered sets | |
415 // in the paged spaces are not correct. | |
416 // | |
417 // After: The heap is in a normal state. | |
418 | |
419 // Rebuild remembered set in old and map spaces. | |
420 static void RebuildRSets(); | |
421 | |
422 #ifdef DEBUG | 410 #ifdef DEBUG |
423 // ----------------------------------------------------------------------- | 411 // ----------------------------------------------------------------------- |
424 // Debugging variables, functions and classes | 412 // Debugging variables, functions and classes |
425 // Counters used for debugging the marking phase of mark-compact or | 413 // Counters used for debugging the marking phase of mark-compact or |
426 // mark-sweep collection. | 414 // mark-sweep collection. |
427 | 415 |
428 // Size of live objects in Heap::to_space_. | 416 // Size of live objects in Heap::to_space_. |
429 static int live_young_objects_size_; | 417 static int live_young_objects_size_; |
430 | 418 |
431 // Size of live objects in Heap::old_pointer_space_. | 419 // Size of live objects in Heap::old_pointer_space_. |
(...skipping 22 matching lines...) Expand all Loading... |
454 | 442 |
455 friend class UnmarkObjectVisitor; | 443 friend class UnmarkObjectVisitor; |
456 static void UnmarkObject(HeapObject* obj); | 444 static void UnmarkObject(HeapObject* obj); |
457 #endif | 445 #endif |
458 }; | 446 }; |
459 | 447 |
460 | 448 |
461 } } // namespace v8::internal | 449 } } // namespace v8::internal |
462 | 450 |
463 #endif // V8_MARK_COMPACT_H_ | 451 #endif // V8_MARK_COMPACT_H_ |
OLD | NEW |