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