ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 1 | // Copyright 2006-2008 the V8 project authors. All rights reserved. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 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_MARK_COMPACT_H_ |
| 29 | #define V8_MARK_COMPACT_H_ |
| 30 | |
| 31 | namespace v8 { namespace internal { |
| 32 | |
| 33 | // Callback function, returns whether an object is alive. The heap size |
| 34 | // of the object is returned in size. It optionally updates the offset |
| 35 | // to the first live object in the page (only used for old and map objects). |
| 36 | typedef bool (*IsAliveFunction)(HeapObject* obj, int* size, int* offset); |
| 37 | |
| 38 | // Callback function for non-live blocks in the old generation. |
| 39 | typedef void (*DeallocateFunction)(Address start, int size_in_bytes); |
| 40 | |
| 41 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 42 | // Forward declarations. |
| 43 | class RootMarkingVisitor; |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 44 | class MarkingVisitor; |
| 45 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 46 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 47 | // ---------------------------------------------------------------------------- |
| 48 | // Mark-Compact collector |
| 49 | // |
| 50 | // All methods are static. |
| 51 | |
| 52 | class MarkCompactCollector : public AllStatic { |
| 53 | public: |
| 54 | // Type of functions to compute forwarding addresses of objects in |
| 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 |
| 57 | // allocation function for each (compactable) space based on the location |
| 58 | // of the object before compaction. |
| 59 | typedef Object* (*AllocationFunction)(HeapObject* object, int object_size); |
| 60 | |
| 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 |
| 63 | // forwarded to, encode the forwarding address. For paged spaces, the |
| 64 | // 'offset' input/output parameter contains the offset of the forwarded |
| 65 | // object from the forwarding address of the previous live object in the |
| 66 | // page as input, and is updated to contain the offset to be used for the |
| 67 | // next live object in the same page. For spaces using a different |
| 68 | // encoding (ie, contiguous spaces), the offset parameter is ignored. |
| 69 | typedef void (*EncodingFunction)(HeapObject* old_object, |
| 70 | int object_size, |
| 71 | Object* new_object, |
| 72 | int* offset); |
| 73 | |
| 74 | // Type of functions to process non-live objects. |
| 75 | typedef void (*ProcessNonLiveFunction)(HeapObject* object); |
| 76 | |
| 77 | // Performs a global garbage collection. |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 78 | static void CollectGarbage(GCTracer* tracer); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 79 | |
| 80 | // True if the last full GC performed heap compaction. |
| 81 | static bool HasCompacted() { return compacting_collection_; } |
| 82 | |
| 83 | // True after the Prepare phase if the compaction is taking place. |
| 84 | static bool IsCompacting() { return compacting_collection_; } |
| 85 | |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 86 | // The count of the number of objects left marked at the end of the last |
| 87 | // completed full GC (expected to be zero). |
| 88 | static int previous_marked_count() { return previous_marked_count_; } |
| 89 | |
| 90 | // During a full GC, there is a stack-allocated GCTracer that is used for |
| 91 | // bookkeeping information. Return a pointer to that tracer. |
| 92 | static GCTracer* tracer() { return tracer_; } |
| 93 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 94 | #ifdef DEBUG |
| 95 | // Checks whether performing mark-compact collection. |
| 96 | static bool in_use() { return state_ > PREPARE_GC; } |
| 97 | #endif |
| 98 | |
| 99 | private: |
| 100 | #ifdef DEBUG |
| 101 | enum CollectorState { |
| 102 | IDLE, |
| 103 | PREPARE_GC, |
| 104 | MARK_LIVE_OBJECTS, |
| 105 | SWEEP_SPACES, |
| 106 | ENCODE_FORWARDING_ADDRESSES, |
| 107 | UPDATE_POINTERS, |
| 108 | RELOCATE_OBJECTS, |
| 109 | REBUILD_RSETS |
| 110 | }; |
| 111 | |
| 112 | // The current stage of the collector. |
| 113 | static CollectorState state_; |
| 114 | #endif |
| 115 | // Global flag indicating whether spaces were compacted on the last GC. |
| 116 | static bool compacting_collection_; |
| 117 | |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 118 | // The number of objects left marked at the end of the last completed full |
| 119 | // GC (expected to be zero). |
| 120 | static int previous_marked_count_; |
| 121 | |
| 122 | // A pointer to the current stack-allocated GC tracer object during a full |
| 123 | // collection (NULL before and after). |
| 124 | static GCTracer* tracer_; |
| 125 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 126 | // Prepares for GC by resetting relocation info in old and map spaces and |
| 127 | // choosing spaces to compact. |
| 128 | static void Prepare(); |
| 129 | |
| 130 | // Finishes GC, performs heap verification. |
| 131 | static void Finish(); |
| 132 | |
| 133 | // -------------------------------------------------------------------------- |
| 134 | // Phase 1: functions related to marking phase. |
| 135 | // before: Heap is in normal state, collector is 'IDLE'. |
| 136 | // |
| 137 | // The first word of a page in old spaces has the end of |
| 138 | // allocation address of the page. |
| 139 | // |
| 140 | // The word at Chunk::high_ address has the address of the |
| 141 | // first page in the next chunk. (The address is tagged to |
| 142 | // distinguish it from end-of-allocation address). |
| 143 | // |
| 144 | // after: live objects are marked. |
| 145 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 146 | friend class RootMarkingVisitor; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 147 | friend class MarkingVisitor; |
| 148 | |
| 149 | // Marking operations for objects reachable from roots. |
| 150 | static void MarkLiveObjects(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 151 | |
| 152 | static void MarkUnmarkedObject(HeapObject* obj); |
| 153 | |
| 154 | static inline void MarkObject(HeapObject* obj) { |
ager@chromium.org | 3bf7b91 | 2008-11-17 09:09:45 +0000 | [diff] [blame] | 155 | if (!obj->IsMarked()) MarkUnmarkedObject(obj); |
| 156 | } |
| 157 | |
| 158 | static inline void SetMark(HeapObject* obj) { |
| 159 | tracer_->increment_marked_count(); |
| 160 | #ifdef DEBUG |
| 161 | UpdateLiveObjectCount(obj); |
| 162 | #endif |
| 163 | obj->SetMark(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 164 | } |
| 165 | |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 166 | // Creates back pointers for all map transitions, stores them in |
| 167 | // the prototype field. The original prototype pointers are restored |
| 168 | // in ClearNonLiveTransitions(). All JSObject maps |
| 169 | // connected by map transitions have the same prototype object, which |
| 170 | // is why we can use this field temporarily for back pointers. |
| 171 | static void CreateBackPointers(); |
| 172 | |
| 173 | // Mark a Map and its DescriptorArray together, skipping transitions. |
| 174 | static void MarkMapContents(Map* map); |
| 175 | static void MarkDescriptorArray(DescriptorArray* descriptors); |
| 176 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 177 | // Mark the heap roots and all objects reachable from them. |
| 178 | static void ProcessRoots(RootMarkingVisitor* visitor); |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 179 | |
| 180 | // Mark objects in object groups that have at least one object in the |
| 181 | // group marked. |
| 182 | static void MarkObjectGroups(); |
| 183 | |
| 184 | // Mark all objects in an object group with at least one marked |
| 185 | // object, then all objects reachable from marked objects in object |
| 186 | // groups, and repeat. |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 187 | static void ProcessObjectGroups(MarkingVisitor* visitor); |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 188 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 189 | // Mark objects reachable (transitively) from objects in the marking stack |
| 190 | // or overflowed in the heap. |
| 191 | static void ProcessMarkingStack(MarkingVisitor* visitor); |
| 192 | |
| 193 | // Mark objects reachable (transitively) from objects in the marking |
| 194 | // stack. This function empties the marking stack, but may leave |
| 195 | // overflowed objects in the heap, in which case the marking stack's |
| 196 | // overflow flag will be set. |
| 197 | static void EmptyMarkingStack(MarkingVisitor* visitor); |
| 198 | |
| 199 | // Refill the marking stack with overflowed objects from the heap. This |
| 200 | // function either leaves the marking stack full or clears the overflow |
| 201 | // flag on the marking stack. |
| 202 | static void RefillMarkingStack(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 203 | |
| 204 | // Callback function for telling whether the object *p must be marked. |
| 205 | static bool MustBeMarked(Object** p); |
| 206 | |
| 207 | #ifdef DEBUG |
| 208 | static void UpdateLiveObjectCount(HeapObject* obj); |
| 209 | static void VerifyHeapAfterMarkingPhase(); |
| 210 | #endif |
| 211 | |
| 212 | // 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. |
| 214 | static void SweepLargeObjectSpace(); |
| 215 | |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 216 | // Test whether a (possibly marked) object is a Map. |
| 217 | static inline bool SafeIsMap(HeapObject* object); |
| 218 | |
| 219 | // 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. |
| 221 | static void ClearNonLiveTransitions(); |
| 222 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 223 | // -------------------------------------------------------------------------- |
| 224 | // Phase 2: functions related to computing and encoding forwarding pointers |
| 225 | // before: live objects' map pointers are marked as '00' |
| 226 | // after: Map pointers of live old and map objects have encoded |
| 227 | // forwarding pointers and map pointers |
| 228 | // |
| 229 | // The 3rd word of a page has the page top offset after compaction. |
| 230 | // |
| 231 | // The 4th word of a page in the map space has the map index |
| 232 | // of this page in the map table. This word is not used in |
| 233 | // the old space. |
| 234 | // |
| 235 | // The 5th and 6th words of a page have the start and end |
| 236 | // addresses of the first free region in the page. |
| 237 | // |
| 238 | // The 7th word of a page in old spaces has the forwarding address |
| 239 | // of the first live object in the page. |
| 240 | // |
| 241 | // Live young objects have their forwarding pointers in |
| 242 | // the from space at the same offset to the beginning of the space. |
| 243 | |
| 244 | // Encodes forwarding addresses of objects in compactable parts of the |
| 245 | // heap. |
| 246 | static void EncodeForwardingAddresses(); |
| 247 | |
| 248 | // Encodes the forwarding addresses of objects in new space. |
| 249 | static void EncodeForwardingAddressesInNewSpace(); |
| 250 | |
| 251 | // Function template to encode the forwarding addresses of objects in |
| 252 | // paged spaces, parameterized by allocation and non-live processing |
| 253 | // functions. |
| 254 | template<AllocationFunction Alloc, ProcessNonLiveFunction ProcessNonLive> |
| 255 | static void EncodeForwardingAddressesInPagedSpace(PagedSpace* space); |
| 256 | |
| 257 | // Iterates live objects in a space, passes live objects |
| 258 | // to a callback function which returns the heap size of the object. |
| 259 | // Returns the number of live objects iterated. |
| 260 | static int IterateLiveObjects(NewSpace* space, HeapObjectCallback size_f); |
| 261 | static int IterateLiveObjects(PagedSpace* space, HeapObjectCallback size_f); |
| 262 | |
| 263 | // Iterates the live objects between a range of addresses, returning the |
| 264 | // number of live objects. |
| 265 | static int IterateLiveObjectsInRange(Address start, Address end, |
| 266 | HeapObjectCallback size_func); |
| 267 | |
| 268 | // Callback functions for deallocating non-live blocks in the old |
| 269 | // generation. |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 270 | static void DeallocateOldPointerBlock(Address start, int size_in_bytes); |
| 271 | static void DeallocateOldDataBlock(Address start, int size_in_bytes); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 272 | static void DeallocateCodeBlock(Address start, int size_in_bytes); |
| 273 | static void DeallocateMapBlock(Address start, int size_in_bytes); |
| 274 | |
| 275 | // Phase 2: If we are not compacting the heap, we simply sweep the spaces |
| 276 | // except for the large object space, clearing mark bits and adding |
| 277 | // unmarked regions to each space's free list. |
| 278 | static void SweepSpaces(); |
| 279 | |
| 280 | #ifdef DEBUG |
| 281 | static void VerifyHeapAfterEncodingForwardingAddresses(); |
| 282 | #endif |
| 283 | |
| 284 | // -------------------------------------------------------------------------- |
| 285 | // Phase 3: function related to updating pointers and decode map pointers |
| 286 | // before: see after phase 2 |
| 287 | // after: all pointers are updated to forwarding addresses. |
| 288 | |
| 289 | friend class UpdatingVisitor; // helper for updating visited objects |
| 290 | |
| 291 | // Updates pointers in all spaces. |
| 292 | static void UpdatePointers(); |
| 293 | |
| 294 | // Updates pointers in an object in new space. |
| 295 | // Returns the heap size of the object. |
| 296 | static int UpdatePointersInNewObject(HeapObject* obj); |
| 297 | |
| 298 | // Updates pointers in an object in old spaces. |
| 299 | // Returns the heap size of the object. |
| 300 | static int UpdatePointersInOldObject(HeapObject* obj); |
| 301 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 302 | // Calculates the forwarding address of an object in an old space. |
| 303 | static Address GetForwardingAddressInOldSpace(HeapObject* obj); |
| 304 | |
| 305 | #ifdef DEBUG |
| 306 | static void VerifyHeapAfterUpdatingPointers(); |
| 307 | #endif |
| 308 | |
| 309 | // -------------------------------------------------------------------------- |
| 310 | // Phase 4: functions related to relocating objects |
| 311 | // before: see after phase 3 |
| 312 | // after: heap is in a normal state, except remembered set is not built |
| 313 | |
| 314 | // Relocates objects in all spaces. |
| 315 | static void RelocateObjects(); |
| 316 | |
| 317 | // Converts a code object's inline target to addresses, convention from |
| 318 | // address to target happens in the marking phase. |
| 319 | static int ConvertCodeICTargetToAddress(HeapObject* obj); |
| 320 | |
| 321 | // Relocate a map object. |
| 322 | static int RelocateMapObject(HeapObject* obj); |
| 323 | |
| 324 | // Relocates an old object. |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 325 | static int RelocateOldPointerObject(HeapObject* obj); |
| 326 | static int RelocateOldDataObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 327 | |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 328 | // Helper function. |
| 329 | static inline int RelocateOldNonCodeObject(HeapObject* obj, OldSpace* space); |
| 330 | |
| 331 | // Relocates an object in the code space. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 332 | static int RelocateCodeObject(HeapObject* obj); |
| 333 | |
| 334 | // Copy a new object. |
| 335 | static int RelocateNewObject(HeapObject* obj); |
| 336 | |
| 337 | #ifdef DEBUG |
| 338 | static void VerifyHeapAfterRelocatingObjects(); |
| 339 | #endif |
| 340 | |
| 341 | // --------------------------------------------------------------------------- |
| 342 | // Phase 5: functions related to rebuilding remembered sets |
| 343 | |
| 344 | // Rebuild remembered set in old and map spaces. |
| 345 | static void RebuildRSets(); |
| 346 | |
| 347 | #ifdef DEBUG |
| 348 | // --------------------------------------------------------------------------- |
| 349 | // Debugging variables, functions and classes |
| 350 | // Counters used for debugging the marking phase of mark-compact or |
| 351 | // mark-sweep collection. |
| 352 | |
| 353 | // Number of live objects in Heap::to_space_. |
| 354 | static int live_young_objects_; |
| 355 | |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 356 | // Number of live objects in Heap::old_pointer_space_. |
| 357 | static int live_old_pointer_objects_; |
| 358 | |
| 359 | // Number of live objects in Heap::old_data_space_. |
| 360 | static int live_old_data_objects_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 361 | |
| 362 | // Number of live objects in Heap::code_space_. |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 363 | static int live_code_objects_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 364 | |
| 365 | // Number of live objects in Heap::map_space_. |
| 366 | static int live_map_objects_; |
| 367 | |
| 368 | // Number of live objects in Heap::lo_space_. |
| 369 | static int live_lo_objects_; |
| 370 | |
| 371 | // Number of live bytes in this collection. |
| 372 | static int live_bytes_; |
| 373 | |
| 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; |
| 381 | static void VisitObject(HeapObject* obj); |
| 382 | |
| 383 | friend class UnmarkObjectVisitor; |
| 384 | static void UnmarkObject(HeapObject* obj); |
| 385 | #endif |
| 386 | }; |
| 387 | |
| 388 | |
| 389 | } } // namespace v8::internal |
| 390 | |
| 391 | #endif // V8_MARK_COMPACT_H_ |