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 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 31 | #include "spaces.h" |
| 32 | |
kasperl@chromium.org | 71affb5 | 2009-05-26 05:44:31 +0000 | [diff] [blame] | 33 | namespace v8 { |
| 34 | namespace internal { |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 35 | |
| 36 | // Callback function, returns whether an object is alive. The heap size |
| 37 | // of the object is returned in size. It optionally updates the offset |
| 38 | // to the first live object in the page (only used for old and map objects). |
| 39 | typedef bool (*IsAliveFunction)(HeapObject* obj, int* size, int* offset); |
| 40 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 41 | // Forward declarations. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 42 | class CodeFlusher; |
| 43 | class GCTracer; |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 44 | class MarkingVisitor; |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 45 | class RootMarkingVisitor; |
| 46 | |
| 47 | |
| 48 | // ---------------------------------------------------------------------------- |
| 49 | // Marking stack for tracing live objects. |
| 50 | |
| 51 | class MarkingStack { |
| 52 | public: |
| 53 | MarkingStack() : low_(NULL), top_(NULL), high_(NULL), overflowed_(false) { } |
| 54 | |
| 55 | void Initialize(Address low, Address high) { |
| 56 | top_ = low_ = reinterpret_cast<HeapObject**>(low); |
| 57 | high_ = reinterpret_cast<HeapObject**>(high); |
| 58 | overflowed_ = false; |
| 59 | } |
| 60 | |
| 61 | bool is_full() const { return top_ >= high_; } |
| 62 | |
| 63 | bool is_empty() const { return top_ <= low_; } |
| 64 | |
| 65 | bool overflowed() const { return overflowed_; } |
| 66 | |
| 67 | void clear_overflowed() { overflowed_ = false; } |
| 68 | |
| 69 | // Push the (marked) object on the marking stack if there is room, |
| 70 | // otherwise mark the object as overflowed and wait for a rescan of the |
| 71 | // heap. |
| 72 | void Push(HeapObject* object) { |
| 73 | CHECK(object->IsHeapObject()); |
| 74 | if (is_full()) { |
| 75 | object->SetOverflow(); |
| 76 | overflowed_ = true; |
| 77 | } else { |
| 78 | *(top_++) = object; |
| 79 | } |
| 80 | } |
| 81 | |
| 82 | HeapObject* Pop() { |
| 83 | ASSERT(!is_empty()); |
| 84 | HeapObject* object = *(--top_); |
| 85 | CHECK(object->IsHeapObject()); |
| 86 | return object; |
| 87 | } |
| 88 | |
| 89 | private: |
| 90 | HeapObject** low_; |
| 91 | HeapObject** top_; |
| 92 | HeapObject** high_; |
| 93 | bool overflowed_; |
| 94 | |
| 95 | DISALLOW_COPY_AND_ASSIGN(MarkingStack); |
| 96 | }; |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 97 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 98 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 99 | // ------------------------------------------------------------------------- |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 100 | // Mark-Compact collector |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 101 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 102 | class OverflowedObjectsScanner; |
| 103 | |
| 104 | class MarkCompactCollector { |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 105 | public: |
| 106 | // Type of functions to compute forwarding addresses of objects in |
| 107 | // compacted spaces. Given an object and its size, return a (non-failure) |
| 108 | // Object* that will be the object after forwarding. There is a separate |
| 109 | // allocation function for each (compactable) space based on the location |
| 110 | // of the object before compaction. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 111 | typedef MaybeObject* (*AllocationFunction)(Heap* heap, |
| 112 | HeapObject* object, |
lrn@chromium.org | 303ada7 | 2010-10-27 09:33:13 +0000 | [diff] [blame] | 113 | int object_size); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 114 | |
| 115 | // Type of functions to encode the forwarding address for an object. |
| 116 | // Given the object, its size, and the new (non-failure) object it will be |
| 117 | // forwarded to, encode the forwarding address. For paged spaces, the |
| 118 | // 'offset' input/output parameter contains the offset of the forwarded |
| 119 | // object from the forwarding address of the previous live object in the |
| 120 | // page as input, and is updated to contain the offset to be used for the |
| 121 | // next live object in the same page. For spaces using a different |
| 122 | // encoding (ie, contiguous spaces), the offset parameter is ignored. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 123 | typedef void (*EncodingFunction)(Heap* heap, |
| 124 | HeapObject* old_object, |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 125 | int object_size, |
| 126 | Object* new_object, |
| 127 | int* offset); |
| 128 | |
| 129 | // Type of functions to process non-live objects. |
kmillikin@chromium.org | c36ce6e | 2011-04-04 08:25:31 +0000 | [diff] [blame] | 130 | typedef void (*ProcessNonLiveFunction)(HeapObject* object, Isolate* isolate); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 131 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 132 | // Pointer to member function, used in IterateLiveObjects. |
| 133 | typedef int (MarkCompactCollector::*LiveObjectCallback)(HeapObject* obj); |
| 134 | |
sgjesse@chromium.org | c81c894 | 2009-08-21 10:54:26 +0000 | [diff] [blame] | 135 | // Set the global force_compaction flag, it must be called before Prepare |
| 136 | // to take effect. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 137 | void SetForceCompaction(bool value) { |
sgjesse@chromium.org | c81c894 | 2009-08-21 10:54:26 +0000 | [diff] [blame] | 138 | force_compaction_ = value; |
| 139 | } |
| 140 | |
ager@chromium.org | ea4f62e | 2010-08-16 16:28:43 +0000 | [diff] [blame] | 141 | |
| 142 | static void Initialize(); |
| 143 | |
kasperl@chromium.org | 061ef74 | 2009-02-27 12:16:20 +0000 | [diff] [blame] | 144 | // Prepares for GC by resetting relocation info in old and map spaces and |
| 145 | // choosing spaces to compact. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 146 | void Prepare(GCTracer* tracer); |
kasperl@chromium.org | 061ef74 | 2009-02-27 12:16:20 +0000 | [diff] [blame] | 147 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 148 | // Performs a global garbage collection. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 149 | void CollectGarbage(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 150 | |
| 151 | // True if the last full GC performed heap compaction. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 152 | bool HasCompacted() { return compacting_collection_; } |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 153 | |
| 154 | // True after the Prepare phase if the compaction is taking place. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 155 | bool IsCompacting() { |
fschneider@chromium.org | 0c20e67 | 2010-01-14 15:28:53 +0000 | [diff] [blame] | 156 | #ifdef DEBUG |
| 157 | // For the purposes of asserts we don't want this to keep returning true |
| 158 | // after the collection is completed. |
| 159 | return state_ != IDLE && compacting_collection_; |
| 160 | #else |
| 161 | return compacting_collection_; |
| 162 | #endif |
| 163 | } |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 164 | |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 165 | // The count of the number of objects left marked at the end of the last |
| 166 | // completed full GC (expected to be zero). |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 167 | int previous_marked_count() { return previous_marked_count_; } |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 168 | |
| 169 | // During a full GC, there is a stack-allocated GCTracer that is used for |
| 170 | // bookkeeping information. Return a pointer to that tracer. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 171 | GCTracer* tracer() { return tracer_; } |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 172 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 173 | #ifdef DEBUG |
| 174 | // Checks whether performing mark-compact collection. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 175 | bool in_use() { return state_ > PREPARE_GC; } |
| 176 | bool are_map_pointers_encoded() { return state_ == UPDATE_POINTERS; } |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 177 | #endif |
| 178 | |
sgjesse@chromium.org | b302e56 | 2010-02-03 11:26:59 +0000 | [diff] [blame] | 179 | // Determine type of object and emit deletion log event. |
kmillikin@chromium.org | c36ce6e | 2011-04-04 08:25:31 +0000 | [diff] [blame] | 180 | static void ReportDeleteIfNeeded(HeapObject* obj, Isolate* isolate); |
sgjesse@chromium.org | b302e56 | 2010-02-03 11:26:59 +0000 | [diff] [blame] | 181 | |
erik.corry@gmail.com | 4a6c327 | 2010-11-18 12:04:40 +0000 | [diff] [blame] | 182 | // Returns size of a possibly marked object. |
| 183 | static int SizeOfMarkedObject(HeapObject* obj); |
| 184 | |
ricow@chromium.org | d236f4d | 2010-09-01 06:52:08 +0000 | [diff] [blame] | 185 | // Distinguishable invalid map encodings (for single word and multiple words) |
| 186 | // that indicate free regions. |
| 187 | static const uint32_t kSingleFreeEncoding = 0; |
| 188 | static const uint32_t kMultiFreeEncoding = 1; |
| 189 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 190 | inline Heap* heap() const { return heap_; } |
| 191 | |
| 192 | CodeFlusher* code_flusher() { return code_flusher_; } |
| 193 | inline bool is_code_flushing_enabled() const { return code_flusher_ != NULL; } |
| 194 | void EnableCodeFlushing(bool enable); |
| 195 | |
kmillikin@chromium.org | 7c2628c | 2011-08-10 11:27:35 +0000 | [diff] [blame] | 196 | inline Object* encountered_weak_maps() { return encountered_weak_maps_; } |
| 197 | inline void set_encountered_weak_maps(Object* weak_map) { |
| 198 | encountered_weak_maps_ = weak_map; |
| 199 | } |
| 200 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 201 | private: |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 202 | MarkCompactCollector(); |
| 203 | ~MarkCompactCollector(); |
| 204 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 205 | #ifdef DEBUG |
| 206 | enum CollectorState { |
| 207 | IDLE, |
| 208 | PREPARE_GC, |
| 209 | MARK_LIVE_OBJECTS, |
| 210 | SWEEP_SPACES, |
| 211 | ENCODE_FORWARDING_ADDRESSES, |
| 212 | UPDATE_POINTERS, |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 213 | RELOCATE_OBJECTS |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 214 | }; |
| 215 | |
| 216 | // The current stage of the collector. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 217 | CollectorState state_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 218 | #endif |
sgjesse@chromium.org | c81c894 | 2009-08-21 10:54:26 +0000 | [diff] [blame] | 219 | |
| 220 | // Global flag that forces a compaction. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 221 | bool force_compaction_; |
sgjesse@chromium.org | c81c894 | 2009-08-21 10:54:26 +0000 | [diff] [blame] | 222 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 223 | // Global flag indicating whether spaces were compacted on the last GC. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 224 | bool compacting_collection_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 225 | |
ager@chromium.org | a1645e2 | 2009-09-09 19:27:10 +0000 | [diff] [blame] | 226 | // Global flag indicating whether spaces will be compacted on the next GC. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 227 | bool compact_on_next_gc_; |
ager@chromium.org | a1645e2 | 2009-09-09 19:27:10 +0000 | [diff] [blame] | 228 | |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 229 | // The number of objects left marked at the end of the last completed full |
| 230 | // GC (expected to be zero). |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 231 | int previous_marked_count_; |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 232 | |
| 233 | // A pointer to the current stack-allocated GC tracer object during a full |
| 234 | // collection (NULL before and after). |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 235 | GCTracer* tracer_; |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 236 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 237 | // Finishes GC, performs heap verification if enabled. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 238 | void Finish(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 239 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 240 | // ----------------------------------------------------------------------- |
| 241 | // Phase 1: Marking live objects. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 242 | // |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 243 | // Before: The heap has been prepared for garbage collection by |
| 244 | // MarkCompactCollector::Prepare() and is otherwise in its |
| 245 | // normal state. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 246 | // |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 247 | // After: Live objects are marked and non-live objects are unmarked. |
| 248 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 249 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 250 | friend class RootMarkingVisitor; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 251 | friend class MarkingVisitor; |
ager@chromium.org | ea4f62e | 2010-08-16 16:28:43 +0000 | [diff] [blame] | 252 | friend class StaticMarkingVisitor; |
ricow@chromium.org | 0b9f850 | 2010-08-18 07:45:01 +0000 | [diff] [blame] | 253 | friend class CodeMarkingVisitor; |
| 254 | friend class SharedFunctionInfoMarkingVisitor; |
| 255 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 256 | void PrepareForCodeFlushing(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 257 | |
| 258 | // Marking operations for objects reachable from roots. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 259 | void MarkLiveObjects(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 260 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 261 | void MarkUnmarkedObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 262 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 263 | inline void MarkObject(HeapObject* obj) { |
ager@chromium.org | 3bf7b91 | 2008-11-17 09:09:45 +0000 | [diff] [blame] | 264 | if (!obj->IsMarked()) MarkUnmarkedObject(obj); |
| 265 | } |
| 266 | |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 267 | inline void SetMark(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 268 | |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 269 | // Creates back pointers for all map transitions, stores them in |
| 270 | // the prototype field. The original prototype pointers are restored |
| 271 | // in ClearNonLiveTransitions(). All JSObject maps |
| 272 | // connected by map transitions have the same prototype object, which |
| 273 | // is why we can use this field temporarily for back pointers. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 274 | void CreateBackPointers(); |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 275 | |
| 276 | // Mark a Map and its DescriptorArray together, skipping transitions. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 277 | void MarkMapContents(Map* map); |
| 278 | void MarkDescriptorArray(DescriptorArray* descriptors); |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 279 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 280 | // Mark the heap roots and all objects reachable from them. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 281 | void MarkRoots(RootMarkingVisitor* visitor); |
ager@chromium.org | 5ec4892 | 2009-05-05 07:25:34 +0000 | [diff] [blame] | 282 | |
| 283 | // Mark the symbol table specially. References to symbols from the |
| 284 | // symbol table are weak. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 285 | void MarkSymbolTable(); |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 286 | |
| 287 | // Mark objects in object groups that have at least one object in the |
| 288 | // group marked. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 289 | void MarkObjectGroups(); |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 290 | |
ricow@chromium.org | badaffc | 2011-03-17 12:15:27 +0000 | [diff] [blame] | 291 | // Mark objects in implicit references groups if their parent object |
| 292 | // is marked. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 293 | void MarkImplicitRefGroups(); |
ricow@chromium.org | badaffc | 2011-03-17 12:15:27 +0000 | [diff] [blame] | 294 | |
| 295 | // Mark all objects which are reachable due to host application |
| 296 | // logic like object groups or implicit references' groups. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 297 | void ProcessExternalMarking(); |
kasper.lund | 7276f14 | 2008-07-30 08:49:36 +0000 | [diff] [blame] | 298 | |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 299 | // Mark objects reachable (transitively) from objects in the marking stack |
| 300 | // or overflowed in the heap. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 301 | void ProcessMarkingStack(); |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 302 | |
| 303 | // Mark objects reachable (transitively) from objects in the marking |
| 304 | // stack. This function empties the marking stack, but may leave |
| 305 | // overflowed objects in the heap, in which case the marking stack's |
| 306 | // overflow flag will be set. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 307 | void EmptyMarkingStack(); |
mads.s.ager | 31e7138 | 2008-08-13 09:32:07 +0000 | [diff] [blame] | 308 | |
| 309 | // Refill the marking stack with overflowed objects from the heap. This |
| 310 | // function either leaves the marking stack full or clears the overflow |
| 311 | // flag on the marking stack. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 312 | void RefillMarkingStack(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 313 | |
ricow@chromium.org | 4f693d6 | 2011-07-04 14:01:31 +0000 | [diff] [blame] | 314 | // After reachable maps have been marked process per context object |
| 315 | // literal map caches removing unmarked entries. |
| 316 | void ProcessMapCaches(); |
| 317 | |
ager@chromium.org | 9085a01 | 2009-05-11 19:22:57 +0000 | [diff] [blame] | 318 | // Callback function for telling whether the object *p is an unmarked |
| 319 | // heap object. |
| 320 | static bool IsUnmarkedHeapObject(Object** p); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 321 | |
| 322 | #ifdef DEBUG |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 323 | void UpdateLiveObjectCount(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 324 | #endif |
| 325 | |
| 326 | // We sweep the large object space in the same way whether we are |
| 327 | // compacting or not, because the large object space is never compacted. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 328 | void SweepLargeObjectSpace(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 329 | |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 330 | // Test whether a (possibly marked) object is a Map. |
| 331 | static inline bool SafeIsMap(HeapObject* object); |
| 332 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 333 | // Map transitions from a live map to a dead map must be killed. |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 334 | // We replace them with a null descriptor, with the same key. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 335 | void ClearNonLiveTransitions(); |
kasperl@chromium.org | 9bbf968 | 2008-10-30 11:53:07 +0000 | [diff] [blame] | 336 | |
kmillikin@chromium.org | 7c2628c | 2011-08-10 11:27:35 +0000 | [diff] [blame] | 337 | // Mark all values associated with reachable keys in weak maps encountered |
| 338 | // so far. This might push new object or even new weak maps onto the |
| 339 | // marking stack. |
| 340 | void ProcessWeakMaps(); |
| 341 | |
| 342 | // After all reachable objects have been marked those weak map entries |
| 343 | // with an unreachable key are removed from all encountered weak maps. |
| 344 | // The linked list of all encountered weak maps is destroyed. |
| 345 | void ClearWeakMaps(); |
| 346 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 347 | // ----------------------------------------------------------------------- |
| 348 | // Phase 2: Sweeping to clear mark bits and free non-live objects for |
| 349 | // a non-compacting collection, or else computing and encoding |
| 350 | // forwarding addresses for a compacting collection. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 351 | // |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 352 | // Before: Live objects are marked and non-live objects are unmarked. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 353 | // |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 354 | // After: (Non-compacting collection.) Live objects are unmarked, |
| 355 | // non-live regions have been added to their space's free |
| 356 | // list. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 357 | // |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 358 | // After: (Compacting collection.) The forwarding address of live |
| 359 | // objects in the paged spaces is encoded in their map word |
| 360 | // along with their (non-forwarded) map pointer. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 361 | // |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 362 | // The forwarding address of live objects in the new space is |
| 363 | // written to their map word's offset in the inactive |
| 364 | // semispace. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 365 | // |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 366 | // Bookkeeping data is written to the page header of |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 367 | // eached paged-space page that contains live objects after |
| 368 | // compaction: |
| 369 | // |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 370 | // The allocation watermark field is used to track the |
| 371 | // relocation top address, the address of the first word |
| 372 | // after the end of the last live object in the page after |
| 373 | // compaction. |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 374 | // |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 375 | // The Page::mc_page_index field contains the zero-based index of the |
| 376 | // page in its space. This word is only used for map space pages, in |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 377 | // order to encode the map addresses in 21 bits to free 11 |
| 378 | // bits per map word for the forwarding address. |
| 379 | // |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 380 | // The Page::mc_first_forwarded field contains the (nonencoded) |
| 381 | // forwarding address of the first live object in the page. |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 382 | // |
| 383 | // In both the new space and the paged spaces, a linked list |
| 384 | // of live regions is constructructed (linked through |
| 385 | // pointers in the non-live region immediately following each |
| 386 | // live region) to speed further passes of the collector. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 387 | |
| 388 | // Encodes forwarding addresses of objects in compactable parts of the |
| 389 | // heap. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 390 | void EncodeForwardingAddresses(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 391 | |
| 392 | // Encodes the forwarding addresses of objects in new space. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 393 | void EncodeForwardingAddressesInNewSpace(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 394 | |
| 395 | // Function template to encode the forwarding addresses of objects in |
| 396 | // paged spaces, parameterized by allocation and non-live processing |
| 397 | // functions. |
| 398 | template<AllocationFunction Alloc, ProcessNonLiveFunction ProcessNonLive> |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 399 | void EncodeForwardingAddressesInPagedSpace(PagedSpace* space); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 400 | |
| 401 | // Iterates live objects in a space, passes live objects |
| 402 | // to a callback function which returns the heap size of the object. |
| 403 | // Returns the number of live objects iterated. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 404 | int IterateLiveObjects(NewSpace* space, LiveObjectCallback size_f); |
| 405 | int IterateLiveObjects(PagedSpace* space, LiveObjectCallback size_f); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 406 | |
| 407 | // Iterates the live objects between a range of addresses, returning the |
| 408 | // number of live objects. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 409 | int IterateLiveObjectsInRange(Address start, Address end, |
| 410 | LiveObjectCallback size_func); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 411 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 412 | // If we are not compacting the heap, we simply sweep the spaces except |
| 413 | // for the large object space, clearing mark bits and adding unmarked |
| 414 | // regions to each space's free list. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 415 | void SweepSpaces(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 416 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 417 | // ----------------------------------------------------------------------- |
| 418 | // Phase 3: Updating pointers in live objects. |
| 419 | // |
| 420 | // Before: Same as after phase 2 (compacting collection). |
| 421 | // |
| 422 | // After: All pointers in live objects, including encoded map |
| 423 | // pointers, are updated to point to their target's new |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 424 | // location. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 425 | |
| 426 | friend class UpdatingVisitor; // helper for updating visited objects |
| 427 | |
| 428 | // Updates pointers in all spaces. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 429 | void UpdatePointers(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 430 | |
| 431 | // Updates pointers in an object in new space. |
| 432 | // Returns the heap size of the object. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 433 | int UpdatePointersInNewObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 434 | |
| 435 | // Updates pointers in an object in old spaces. |
| 436 | // Returns the heap size of the object. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 437 | int UpdatePointersInOldObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 438 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 439 | // Calculates the forwarding address of an object in an old space. |
| 440 | static Address GetForwardingAddressInOldSpace(HeapObject* obj); |
| 441 | |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 442 | // ----------------------------------------------------------------------- |
| 443 | // Phase 4: Relocating objects. |
| 444 | // |
| 445 | // Before: Pointers to live objects are updated to point to their |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 446 | // target's new location. |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 447 | // |
ricow@chromium.org | 30ce411 | 2010-05-31 10:38:25 +0000 | [diff] [blame] | 448 | // After: Objects have been moved to their new addresses. |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 449 | |
| 450 | // Relocates objects in all spaces. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 451 | void RelocateObjects(); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 452 | |
| 453 | // Converts a code object's inline target to addresses, convention from |
| 454 | // address to target happens in the marking phase. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 455 | int ConvertCodeICTargetToAddress(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 456 | |
| 457 | // Relocate a map object. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 458 | int RelocateMapObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 459 | |
| 460 | // Relocates an old object. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 461 | int RelocateOldPointerObject(HeapObject* obj); |
| 462 | int RelocateOldDataObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 463 | |
kasperl@chromium.org | defbd10 | 2009-07-13 14:04:26 +0000 | [diff] [blame] | 464 | // Relocate a property cell object. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 465 | int RelocateCellObject(HeapObject* obj); |
kasperl@chromium.org | defbd10 | 2009-07-13 14:04:26 +0000 | [diff] [blame] | 466 | |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 467 | // Helper function. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 468 | inline int RelocateOldNonCodeObject(HeapObject* obj, |
| 469 | PagedSpace* space); |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 470 | |
| 471 | // Relocates an object in the code space. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 472 | int RelocateCodeObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 473 | |
| 474 | // Copy a new object. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 475 | int RelocateNewObject(HeapObject* obj); |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 476 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 477 | #ifdef DEBUG |
ager@chromium.org | ddb913d | 2009-01-27 10:01:48 +0000 | [diff] [blame] | 478 | // ----------------------------------------------------------------------- |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 479 | // Debugging variables, functions and classes |
| 480 | // Counters used for debugging the marking phase of mark-compact or |
| 481 | // mark-sweep collection. |
| 482 | |
whesse@chromium.org | b6e43bb | 2010-04-14 09:36:28 +0000 | [diff] [blame] | 483 | // Size of live objects in Heap::to_space_. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 484 | int live_young_objects_size_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 485 | |
whesse@chromium.org | b6e43bb | 2010-04-14 09:36:28 +0000 | [diff] [blame] | 486 | // Size of live objects in Heap::old_pointer_space_. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 487 | int live_old_pointer_objects_size_; |
ager@chromium.org | 9258b6b | 2008-09-11 09:11:10 +0000 | [diff] [blame] | 488 | |
whesse@chromium.org | b6e43bb | 2010-04-14 09:36:28 +0000 | [diff] [blame] | 489 | // Size of live objects in Heap::old_data_space_. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 490 | int live_old_data_objects_size_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 491 | |
whesse@chromium.org | b6e43bb | 2010-04-14 09:36:28 +0000 | [diff] [blame] | 492 | // Size of live objects in Heap::code_space_. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 493 | int live_code_objects_size_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 494 | |
whesse@chromium.org | b6e43bb | 2010-04-14 09:36:28 +0000 | [diff] [blame] | 495 | // Size of live objects in Heap::map_space_. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 496 | int live_map_objects_size_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 497 | |
whesse@chromium.org | b6e43bb | 2010-04-14 09:36:28 +0000 | [diff] [blame] | 498 | // Size of live objects in Heap::cell_space_. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 499 | int live_cell_objects_size_; |
kasperl@chromium.org | defbd10 | 2009-07-13 14:04:26 +0000 | [diff] [blame] | 500 | |
whesse@chromium.org | b6e43bb | 2010-04-14 09:36:28 +0000 | [diff] [blame] | 501 | // Size of live objects in Heap::lo_space_. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 502 | int live_lo_objects_size_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 503 | |
| 504 | // Number of live bytes in this collection. |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 505 | int live_bytes_; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 506 | |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 507 | friend class MarkObjectVisitor; |
| 508 | static void VisitObject(HeapObject* obj); |
| 509 | |
| 510 | friend class UnmarkObjectVisitor; |
| 511 | static void UnmarkObject(HeapObject* obj); |
| 512 | #endif |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 513 | |
| 514 | Heap* heap_; |
| 515 | MarkingStack marking_stack_; |
| 516 | CodeFlusher* code_flusher_; |
kmillikin@chromium.org | 7c2628c | 2011-08-10 11:27:35 +0000 | [diff] [blame] | 517 | Object* encountered_weak_maps_; |
sgjesse@chromium.org | ea88ce9 | 2011-03-23 11:19:56 +0000 | [diff] [blame] | 518 | |
| 519 | friend class Heap; |
| 520 | friend class OverflowedObjectsScanner; |
christian.plesner.hansen | 43d26ec | 2008-07-03 15:10:15 +0000 | [diff] [blame] | 521 | }; |
| 522 | |
| 523 | |
| 524 | } } // namespace v8::internal |
| 525 | |
| 526 | #endif // V8_MARK_COMPACT_H_ |