1 // Copyright 2006-2008 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_MARK_COMPACT_H_ 29 #define V8_MARK_COMPACT_H_ 30 31 namespace v8 { 32 namespace internal { 33 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 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); 38 39 // Callback function for non-live blocks in the old generation. 40 typedef void (*DeallocateFunction)(Address start, int size_in_bytes); 41 42 43 // Forward declarations. 44 class RootMarkingVisitor; 45 class MarkingVisitor; 46 47 48 // ------------------------------------------------------------------------- 49 // Mark-Compact collector 50 // 51 // All methods are static. 52 53 class MarkCompactCollector: public AllStatic { 54 public: 55 // Type of functions to compute forwarding addresses of objects in 56 // compacted spaces. Given an object and its size, return a (non-failure) 57 // Object* that will be the object after forwarding. There is a separate 58 // allocation function for each (compactable) space based on the location 59 // of the object before compaction. 60 typedef Object* (*AllocationFunction)(HeapObject* object, int object_size); 61 62 // Type of functions to encode the forwarding address for an object. 63 // Given the object, its size, and the new (non-failure) object it will be 64 // forwarded to, encode the forwarding address. For paged spaces, the 65 // 'offset' input/output parameter contains the offset of the forwarded 66 // object from the forwarding address of the previous live object in the 67 // page as input, and is updated to contain the offset to be used for the 68 // next live object in the same page. For spaces using a different 69 // encoding (ie, contiguous spaces), the offset parameter is ignored. 70 typedef void (*EncodingFunction)(HeapObject* old_object, 71 int object_size, 72 Object* new_object, 73 int* offset); 74 75 // Type of functions to process non-live objects. 76 typedef void (*ProcessNonLiveFunction)(HeapObject* object); 77 78 // Set the global force_compaction flag, it must be called before Prepare 79 // to take effect. 80 static void SetForceCompaction(bool value) { 81 force_compaction_ = value; 82 } 83 84 // Prepares for GC by resetting relocation info in old and map spaces and 85 // choosing spaces to compact. 86 static void Prepare(GCTracer* tracer); 87 88 // Performs a global garbage collection. 89 static void CollectGarbage(); 90 91 // True if the last full GC performed heap compaction. 92 static bool HasCompacted() { return compacting_collection_; } 93 94 // True after the Prepare phase if the compaction is taking place. 95 static bool IsCompacting() { 96 #ifdef DEBUG 97 // For the purposes of asserts we don't want this to keep returning true 98 // after the collection is completed. 99 return state_ != IDLE && compacting_collection_; 100 #else 101 return compacting_collection_; 102 #endif 103 } 104 105 // The count of the number of objects left marked at the end of the last 106 // completed full GC (expected to be zero). 107 static int previous_marked_count() { return previous_marked_count_; } 108 109 // During a full GC, there is a stack-allocated GCTracer that is used for 110 // bookkeeping information. Return a pointer to that tracer. 111 static GCTracer* tracer() { return tracer_; } 112 113 #ifdef DEBUG 114 // Checks whether performing mark-compact collection. 115 static bool in_use() { return state_ > PREPARE_GC; } 116 #endif 117 118 // Determine type of object and emit deletion log event. 119 static void ReportDeleteIfNeeded(HeapObject* obj); 120 121 private: 122 #ifdef DEBUG 123 enum CollectorState { 124 IDLE, 125 PREPARE_GC, 126 MARK_LIVE_OBJECTS, 127 SWEEP_SPACES, 128 ENCODE_FORWARDING_ADDRESSES, 129 UPDATE_POINTERS, 130 RELOCATE_OBJECTS, 131 REBUILD_RSETS 132 }; 133 134 // The current stage of the collector. 135 static CollectorState state_; 136 #endif 137 138 // Global flag that forces a compaction. 139 static bool force_compaction_; 140 141 // Global flag indicating whether spaces were compacted on the last GC. 142 static bool compacting_collection_; 143 144 // Global flag indicating whether spaces will be compacted on the next GC. 145 static bool compact_on_next_gc_; 146 147 // The number of objects left marked at the end of the last completed full 148 // GC (expected to be zero). 149 static int previous_marked_count_; 150 151 // A pointer to the current stack-allocated GC tracer object during a full 152 // collection (NULL before and after). 153 static GCTracer* tracer_; 154 155 // Finishes GC, performs heap verification if enabled. 156 static void Finish(); 157 158 // ----------------------------------------------------------------------- 159 // Phase 1: Marking live objects. 160 // 161 // Before: The heap has been prepared for garbage collection by 162 // MarkCompactCollector::Prepare() and is otherwise in its 163 // normal state. 164 // 165 // After: Live objects are marked and non-live objects are unmarked. 166 167 168 friend class RootMarkingVisitor; 169 friend class MarkingVisitor; 170 171 // Marking operations for objects reachable from roots. 172 static void MarkLiveObjects(); 173 174 static void MarkUnmarkedObject(HeapObject* obj); 175 176 static inline void MarkObject(HeapObject* obj) { 177 if (!obj->IsMarked()) MarkUnmarkedObject(obj); 178 } 179 180 static inline void SetMark(HeapObject* obj) { 181 tracer_->increment_marked_count(); 182 #ifdef DEBUG 183 UpdateLiveObjectCount(obj); 184 #endif 185 obj->SetMark(); 186 } 187 188 // Creates back pointers for all map transitions, stores them in 189 // the prototype field. The original prototype pointers are restored 190 // in ClearNonLiveTransitions(). All JSObject maps 191 // connected by map transitions have the same prototype object, which 192 // is why we can use this field temporarily for back pointers. 193 static void CreateBackPointers(); 194 195 // Mark a Map and its DescriptorArray together, skipping transitions. 196 static void MarkMapContents(Map* map); 197 static void MarkDescriptorArray(DescriptorArray* descriptors); 198 199 // Mark the heap roots and all objects reachable from them. 200 static void MarkRoots(RootMarkingVisitor* visitor); 201 202 // Mark the symbol table specially. References to symbols from the 203 // symbol table are weak. 204 static void MarkSymbolTable(); 205 206 // Mark objects in object groups that have at least one object in the 207 // group marked. 208 static void MarkObjectGroups(); 209 210 // Mark all objects in an object group with at least one marked 211 // object, then all objects reachable from marked objects in object 212 // groups, and repeat. 213 static void ProcessObjectGroups(MarkingVisitor* visitor); 214 215 // Mark objects reachable (transitively) from objects in the marking stack 216 // or overflowed in the heap. 217 static void ProcessMarkingStack(MarkingVisitor* visitor); 218 219 // Mark objects reachable (transitively) from objects in the marking 220 // stack. This function empties the marking stack, but may leave 221 // overflowed objects in the heap, in which case the marking stack's 222 // overflow flag will be set. 223 static void EmptyMarkingStack(MarkingVisitor* visitor); 224 225 // Refill the marking stack with overflowed objects from the heap. This 226 // function either leaves the marking stack full or clears the overflow 227 // flag on the marking stack. 228 static void RefillMarkingStack(); 229 230 // Callback function for telling whether the object *p is an unmarked 231 // heap object. 232 static bool IsUnmarkedHeapObject(Object** p); 233 234 #ifdef DEBUG 235 static void UpdateLiveObjectCount(HeapObject* obj); 236 #endif 237 238 // We sweep the large object space in the same way whether we are 239 // compacting or not, because the large object space is never compacted. 240 static void SweepLargeObjectSpace(); 241 242 // Test whether a (possibly marked) object is a Map. 243 static inline bool SafeIsMap(HeapObject* object); 244 245 // Map transitions from a live map to a dead map must be killed. 246 // We replace them with a null descriptor, with the same key. 247 static void ClearNonLiveTransitions(); 248 249 // ----------------------------------------------------------------------- 250 // Phase 2: Sweeping to clear mark bits and free non-live objects for 251 // a non-compacting collection, or else computing and encoding 252 // forwarding addresses for a compacting collection. 253 // 254 // Before: Live objects are marked and non-live objects are unmarked. 255 // 256 // After: (Non-compacting collection.) Live objects are unmarked, 257 // non-live regions have been added to their space's free 258 // list. 259 // 260 // After: (Compacting collection.) The forwarding address of live 261 // objects in the paged spaces is encoded in their map word 262 // along with their (non-forwarded) map pointer. 263 // 264 // The forwarding address of live objects in the new space is 265 // written to their map word's offset in the inactive 266 // semispace. 267 // 268 // Bookkeeping data is written to the remembered-set are of 269 // eached paged-space page that contains live objects after 270 // compaction: 271 // 272 // The 3rd word of the page (first word of the remembered 273 // set) contains the relocation top address, the address of 274 // the first word after the end of the last live object in 275 // the page after compaction. 276 // 277 // The 4th word contains the zero-based index of the page in 278 // its space. This word is only used for map space pages, in 279 // order to encode the map addresses in 21 bits to free 11 280 // bits per map word for the forwarding address. 281 // 282 // The 5th word contains the (nonencoded) forwarding address 283 // of the first live object in the page. 284 // 285 // In both the new space and the paged spaces, a linked list 286 // of live regions is constructructed (linked through 287 // pointers in the non-live region immediately following each 288 // live region) to speed further passes of the collector. 289 290 // Encodes forwarding addresses of objects in compactable parts of the 291 // heap. 292 static void EncodeForwardingAddresses(); 293 294 // Encodes the forwarding addresses of objects in new space. 295 static void EncodeForwardingAddressesInNewSpace(); 296 297 // Function template to encode the forwarding addresses of objects in 298 // paged spaces, parameterized by allocation and non-live processing 299 // functions. 300 template<AllocationFunction Alloc, ProcessNonLiveFunction ProcessNonLive> 301 static void EncodeForwardingAddressesInPagedSpace(PagedSpace* space); 302 303 // Iterates live objects in a space, passes live objects 304 // to a callback function which returns the heap size of the object. 305 // Returns the number of live objects iterated. 306 static int IterateLiveObjects(NewSpace* space, HeapObjectCallback size_f); 307 static int IterateLiveObjects(PagedSpace* space, HeapObjectCallback size_f); 308 309 // Iterates the live objects between a range of addresses, returning the 310 // number of live objects. 311 static int IterateLiveObjectsInRange(Address start, Address end, 312 HeapObjectCallback size_func); 313 314 // Callback functions for deallocating non-live blocks in the old 315 // generation. 316 static void DeallocateOldPointerBlock(Address start, int size_in_bytes); 317 static void DeallocateOldDataBlock(Address start, int size_in_bytes); 318 static void DeallocateCodeBlock(Address start, int size_in_bytes); 319 static void DeallocateMapBlock(Address start, int size_in_bytes); 320 static void DeallocateCellBlock(Address start, int size_in_bytes); 321 322 // If we are not compacting the heap, we simply sweep the spaces except 323 // for the large object space, clearing mark bits and adding unmarked 324 // regions to each space's free list. 325 static void SweepSpaces(); 326 327 // ----------------------------------------------------------------------- 328 // Phase 3: Updating pointers in live objects. 329 // 330 // Before: Same as after phase 2 (compacting collection). 331 // 332 // After: All pointers in live objects, including encoded map 333 // pointers, are updated to point to their target's new 334 // location. The remembered set area of each paged-space 335 // page containing live objects still contains bookkeeping 336 // information. 337 338 friend class UpdatingVisitor; // helper for updating visited objects 339 340 // Updates pointers in all spaces. 341 static void UpdatePointers(); 342 343 // Updates pointers in an object in new space. 344 // Returns the heap size of the object. 345 static int UpdatePointersInNewObject(HeapObject* obj); 346 347 // Updates pointers in an object in old spaces. 348 // Returns the heap size of the object. 349 static int UpdatePointersInOldObject(HeapObject* obj); 350 351 // Calculates the forwarding address of an object in an old space. 352 static Address GetForwardingAddressInOldSpace(HeapObject* obj); 353 354 // ----------------------------------------------------------------------- 355 // Phase 4: Relocating objects. 356 // 357 // Before: Pointers to live objects are updated to point to their 358 // target's new location. The remembered set area of each 359 // paged-space page containing live objects still contains 360 // bookkeeping information. 361 // 362 // After: Objects have been moved to their new addresses. The 363 // remembered set area of each paged-space page containing 364 // live objects still contains bookkeeping information. 365 366 // Relocates objects in all spaces. 367 static void RelocateObjects(); 368 369 // Converts a code object's inline target to addresses, convention from 370 // address to target happens in the marking phase. 371 static int ConvertCodeICTargetToAddress(HeapObject* obj); 372 373 // Relocate a map object. 374 static int RelocateMapObject(HeapObject* obj); 375 376 // Relocates an old object. 377 static int RelocateOldPointerObject(HeapObject* obj); 378 static int RelocateOldDataObject(HeapObject* obj); 379 380 // Relocate a property cell object. 381 static int RelocateCellObject(HeapObject* obj); 382 383 // Helper function. 384 static inline int RelocateOldNonCodeObject(HeapObject* obj, 385 PagedSpace* space); 386 387 // Relocates an object in the code space. 388 static int RelocateCodeObject(HeapObject* obj); 389 390 // Copy a new object. 391 static int RelocateNewObject(HeapObject* obj); 392 393 // ----------------------------------------------------------------------- 394 // Phase 5: Rebuilding remembered sets. 395 // 396 // Before: The heap is in a normal state except that remembered sets 397 // in the paged spaces are not correct. 398 // 399 // After: The heap is in a normal state. 400 401 // Rebuild remembered set in old and map spaces. 402 static void RebuildRSets(); 403 404 #ifdef DEBUG 405 // ----------------------------------------------------------------------- 406 // Debugging variables, functions and classes 407 // Counters used for debugging the marking phase of mark-compact or 408 // mark-sweep collection. 409 410 // Number of live objects in Heap::to_space_. 411 static int live_young_objects_; 412 413 // Number of live objects in Heap::old_pointer_space_. 414 static int live_old_pointer_objects_; 415 416 // Number of live objects in Heap::old_data_space_. 417 static int live_old_data_objects_; 418 419 // Number of live objects in Heap::code_space_. 420 static int live_code_objects_; 421 422 // Number of live objects in Heap::map_space_. 423 static int live_map_objects_; 424 425 // Number of live objects in Heap::cell_space_. 426 static int live_cell_objects_; 427 428 // Number of live objects in Heap::lo_space_. 429 static int live_lo_objects_; 430 431 // Number of live bytes in this collection. 432 static int live_bytes_; 433 434 friend class MarkObjectVisitor; 435 static void VisitObject(HeapObject* obj); 436 437 friend class UnmarkObjectVisitor; 438 static void UnmarkObject(HeapObject* obj); 439 #endif 440 }; 441 442 443 } } // namespace v8::internal 444 445 #endif // V8_MARK_COMPACT_H_ 446