mark-compact.h 16.9 KB
Newer Older
1
// Copyright 2006-2008 the V8 project authors. All rights reserved.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
//       copyright notice, this list of conditions and the following
//       disclaimer in the documentation and/or other materials provided
//       with the distribution.
//     * Neither the name of Google Inc. nor the names of its
//       contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef V8_MARK_COMPACT_H_
#define V8_MARK_COMPACT_H_

31 32
namespace v8 {
namespace internal {
33 34 35 36 37 38 39 40 41 42

// Callback function, returns whether an object is alive. The heap size
// of the object is returned in size. It optionally updates the offset
// to the first live object in the page (only used for old and map objects).
typedef bool (*IsAliveFunction)(HeapObject* obj, int* size, int* offset);

// Callback function for non-live blocks in the old generation.
typedef void (*DeallocateFunction)(Address start, int size_in_bytes);


43 44
// Forward declarations.
class RootMarkingVisitor;
45 46
class MarkingVisitor;

47

48
// -------------------------------------------------------------------------
49 50 51 52
// Mark-Compact collector
//
// All methods are static.

53
class MarkCompactCollector: public AllStatic {
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
 public:
  // Type of functions to compute forwarding addresses of objects in
  // compacted spaces.  Given an object and its size, return a (non-failure)
  // Object* that will be the object after forwarding.  There is a separate
  // allocation function for each (compactable) space based on the location
  // of the object before compaction.
  typedef Object* (*AllocationFunction)(HeapObject* object, int object_size);

  // Type of functions to encode the forwarding address for an object.
  // Given the object, its size, and the new (non-failure) object it will be
  // forwarded to, encode the forwarding address.  For paged spaces, the
  // 'offset' input/output parameter contains the offset of the forwarded
  // object from the forwarding address of the previous live object in the
  // page as input, and is updated to contain the offset to be used for the
  // next live object in the same page.  For spaces using a different
  // encoding (ie, contiguous spaces), the offset parameter is ignored.
  typedef void (*EncodingFunction)(HeapObject* old_object,
                                   int object_size,
                                   Object* new_object,
                                   int* offset);

  // Type of functions to process non-live objects.
  typedef void (*ProcessNonLiveFunction)(HeapObject* object);

78 79 80 81 82 83
  // Set the global force_compaction flag, it must be called before Prepare
  // to take effect.
  static void SetForceCompaction(bool value) {
    force_compaction_ = value;
  }

84 85 86 87
  // Prepares for GC by resetting relocation info in old and map spaces and
  // choosing spaces to compact.
  static void Prepare(GCTracer* tracer);

88
  // Performs a global garbage collection.
89
  static void CollectGarbage();
90 91 92 93 94

  // True if the last full GC performed heap compaction.
  static bool HasCompacted() { return compacting_collection_; }

  // True after the Prepare phase if the compaction is taking place.
95 96 97 98 99 100 101 102 103
  static bool IsCompacting() {
#ifdef DEBUG
    // For the purposes of asserts we don't want this to keep returning true
    // after the collection is completed.
    return state_ != IDLE && compacting_collection_;
#else
    return compacting_collection_;
#endif
  }
104

105 106 107 108 109 110 111 112
  // The count of the number of objects left marked at the end of the last
  // completed full GC (expected to be zero).
  static int previous_marked_count() { return previous_marked_count_; }

  // During a full GC, there is a stack-allocated GCTracer that is used for
  // bookkeeping information.  Return a pointer to that tracer.
  static GCTracer* tracer() { return tracer_; }

113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
#ifdef DEBUG
  // Checks whether performing mark-compact collection.
  static bool in_use() { return state_ > PREPARE_GC; }
#endif

 private:
#ifdef DEBUG
  enum CollectorState {
    IDLE,
    PREPARE_GC,
    MARK_LIVE_OBJECTS,
    SWEEP_SPACES,
    ENCODE_FORWARDING_ADDRESSES,
    UPDATE_POINTERS,
    RELOCATE_OBJECTS,
    REBUILD_RSETS
  };

  // The current stage of the collector.
  static CollectorState state_;
#endif
134 135 136 137

  // Global flag that forces a compaction.
  static bool force_compaction_;

138 139 140
  // Global flag indicating whether spaces were compacted on the last GC.
  static bool compacting_collection_;

141 142 143
  // Global flag indicating whether spaces will be compacted on the next GC.
  static bool compact_on_next_gc_;

144 145 146 147 148 149 150 151
  // The number of objects left marked at the end of the last completed full
  // GC (expected to be zero).
  static int previous_marked_count_;

  // A pointer to the current stack-allocated GC tracer object during a full
  // collection (NULL before and after).
  static GCTracer* tracer_;

152
  // Finishes GC, performs heap verification if enabled.
153 154
  static void Finish();

155 156
  // -----------------------------------------------------------------------
  // Phase 1: Marking live objects.
157
  //
158 159 160
  //  Before: The heap has been prepared for garbage collection by
  //          MarkCompactCollector::Prepare() and is otherwise in its
  //          normal state.
161
  //
162 163
  //   After: Live objects are marked and non-live objects are unmarked.

164

165
  friend class RootMarkingVisitor;
166 167 168 169 170 171 172 173
  friend class MarkingVisitor;

  // Marking operations for objects reachable from roots.
  static void MarkLiveObjects();

  static void MarkUnmarkedObject(HeapObject* obj);

  static inline void MarkObject(HeapObject* obj) {
174 175 176 177 178 179
    if (!obj->IsMarked()) MarkUnmarkedObject(obj);
  }

  static inline void SetMark(HeapObject* obj) {
    tracer_->increment_marked_count();
#ifdef DEBUG
180
    UpdateLiveObjectCount(obj);
181 182
#endif
    obj->SetMark();
183 184
  }

185 186 187 188 189 190 191 192 193 194 195
  // Creates back pointers for all map transitions, stores them in
  // the prototype field.  The original prototype pointers are restored
  // in ClearNonLiveTransitions().  All JSObject maps
  // connected by map transitions have the same prototype object, which
  // is why we can use this field temporarily for back pointers.
  static void CreateBackPointers();

  // Mark a Map and its DescriptorArray together, skipping transitions.
  static void MarkMapContents(Map* map);
  static void MarkDescriptorArray(DescriptorArray* descriptors);

196
  // Mark the heap roots and all objects reachable from them.
197 198
  static void MarkRoots(RootMarkingVisitor* visitor);

199 200
  // Mark the symbol table specially.  References to symbols from the
  // symbol table are weak.
201
  static void MarkSymbolTable();
202 203 204 205 206 207 208 209

  // Mark objects in object groups that have at least one object in the
  // group marked.
  static void MarkObjectGroups();

  // Mark all objects in an object group with at least one marked
  // object, then all objects reachable from marked objects in object
  // groups, and repeat.
210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
  static void ProcessObjectGroups(MarkingVisitor* visitor);

  // Mark objects reachable (transitively) from objects in the marking stack
  // or overflowed in the heap.
  static void ProcessMarkingStack(MarkingVisitor* visitor);

  // Mark objects reachable (transitively) from objects in the marking
  // stack.  This function empties the marking stack, but may leave
  // overflowed objects in the heap, in which case the marking stack's
  // overflow flag will be set.
  static void EmptyMarkingStack(MarkingVisitor* visitor);

  // Refill the marking stack with overflowed objects from the heap.  This
  // function either leaves the marking stack full or clears the overflow
  // flag on the marking stack.
  static void RefillMarkingStack();
226

227 228 229
  // Callback function for telling whether the object *p is an unmarked
  // heap object.
  static bool IsUnmarkedHeapObject(Object** p);
230 231

#ifdef DEBUG
232
  static void UpdateLiveObjectCount(HeapObject* obj);
233 234 235 236 237 238
#endif

  // We sweep the large object space in the same way whether we are
  // compacting or not, because the large object space is never compacted.
  static void SweepLargeObjectSpace();

239 240 241
  // Test whether a (possibly marked) object is a Map.
  static inline bool SafeIsMap(HeapObject* object);

242
  // Map transitions from a live map to a dead map must be killed.
243 244 245
  // We replace them with a null descriptor, with the same key.
  static void ClearNonLiveTransitions();

246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
  // -----------------------------------------------------------------------
  // Phase 2: Sweeping to clear mark bits and free non-live objects for
  // a non-compacting collection, or else computing and encoding
  // forwarding addresses for a compacting collection.
  //
  //  Before: Live objects are marked and non-live objects are unmarked.
  //
  //   After: (Non-compacting collection.)  Live objects are unmarked,
  //          non-live regions have been added to their space's free
  //          list.
  //
  //   After: (Compacting collection.)  The forwarding address of live
  //          objects in the paged spaces is encoded in their map word
  //          along with their (non-forwarded) map pointer.
  //
  //          The forwarding address of live objects in the new space is
  //          written to their map word's offset in the inactive
  //          semispace.
264
  //
265 266 267
  //          Bookkeeping data is written to the remembered-set are of
  //          eached paged-space page that contains live objects after
  //          compaction:
268
  //
269 270 271 272
  //          The 3rd word of the page (first word of the remembered
  //          set) contains the relocation top address, the address of
  //          the first word after the end of the last live object in
  //          the page after compaction.
273
  //
274 275 276 277
  //          The 4th word contains the zero-based index of the page in
  //          its space.  This word is only used for map space pages, in
  //          order to encode the map addresses in 21 bits to free 11
  //          bits per map word for the forwarding address.
278
  //
279 280
  //          The 5th word contains the (nonencoded) forwarding address
  //          of the first live object in the page.
281
  //
282 283 284 285
  //          In both the new space and the paged spaces, a linked list
  //          of live regions is constructructed (linked through
  //          pointers in the non-live region immediately following each
  //          live region) to speed further passes of the collector.
286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312

  // Encodes forwarding addresses of objects in compactable parts of the
  // heap.
  static void EncodeForwardingAddresses();

  // Encodes the forwarding addresses of objects in new space.
  static void EncodeForwardingAddressesInNewSpace();

  // Function template to encode the forwarding addresses of objects in
  // paged spaces, parameterized by allocation and non-live processing
  // functions.
  template<AllocationFunction Alloc, ProcessNonLiveFunction ProcessNonLive>
  static void EncodeForwardingAddressesInPagedSpace(PagedSpace* space);

  // Iterates live objects in a space, passes live objects
  // to a callback function which returns the heap size of the object.
  // Returns the number of live objects iterated.
  static int IterateLiveObjects(NewSpace* space, HeapObjectCallback size_f);
  static int IterateLiveObjects(PagedSpace* space, HeapObjectCallback size_f);

  // Iterates the live objects between a range of addresses, returning the
  // number of live objects.
  static int IterateLiveObjectsInRange(Address start, Address end,
                                       HeapObjectCallback size_func);

  // Callback functions for deallocating non-live blocks in the old
  // generation.
313 314
  static void DeallocateOldPointerBlock(Address start, int size_in_bytes);
  static void DeallocateOldDataBlock(Address start, int size_in_bytes);
315 316
  static void DeallocateCodeBlock(Address start, int size_in_bytes);
  static void DeallocateMapBlock(Address start, int size_in_bytes);
317
  static void DeallocateCellBlock(Address start, int size_in_bytes);
318

319 320 321
  // If we are not compacting the heap, we simply sweep the spaces except
  // for the large object space, clearing mark bits and adding unmarked
  // regions to each space's free list.
322 323
  static void SweepSpaces();

324 325 326 327 328 329 330 331 332 333
  // -----------------------------------------------------------------------
  // Phase 3: Updating pointers in live objects.
  //
  //  Before: Same as after phase 2 (compacting collection).
  //
  //   After: All pointers in live objects, including encoded map
  //          pointers, are updated to point to their target's new
  //          location.  The remembered set area of each paged-space
  //          page containing live objects still contains bookkeeping
  //          information.
334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350

  friend class UpdatingVisitor;  // helper for updating visited objects

  // Updates pointers in all spaces.
  static void UpdatePointers();

  // Updates pointers in an object in new space.
  // Returns the heap size of the object.
  static int UpdatePointersInNewObject(HeapObject* obj);

  // Updates pointers in an object in old spaces.
  // Returns the heap size of the object.
  static int UpdatePointersInOldObject(HeapObject* obj);

  // Calculates the forwarding address of an object in an old space.
  static Address GetForwardingAddressInOldSpace(HeapObject* obj);

351 352 353 354 355 356 357 358 359 360 361
  // -----------------------------------------------------------------------
  // Phase 4: Relocating objects.
  //
  //  Before: Pointers to live objects are updated to point to their
  //          target's new location.  The remembered set area of each
  //          paged-space page containing live objects still contains
  //          bookkeeping information.
  //
  //   After: Objects have been moved to their new addresses. The
  //          remembered set area of each paged-space page containing
  //          live objects still contains bookkeeping information.
362 363 364 365 366 367 368 369 370 371 372 373

  // Relocates objects in all spaces.
  static void RelocateObjects();

  // Converts a code object's inline target to addresses, convention from
  // address to target happens in the marking phase.
  static int ConvertCodeICTargetToAddress(HeapObject* obj);

  // Relocate a map object.
  static int RelocateMapObject(HeapObject* obj);

  // Relocates an old object.
374 375
  static int RelocateOldPointerObject(HeapObject* obj);
  static int RelocateOldDataObject(HeapObject* obj);
376

377 378 379
  // Relocate a property cell object.
  static int RelocateCellObject(HeapObject* obj);

380
  // Helper function.
381 382
  static inline int RelocateOldNonCodeObject(HeapObject* obj,
                                             PagedSpace* space);
383 384

  // Relocates an object in the code space.
385 386 387 388 389
  static int RelocateCodeObject(HeapObject* obj);

  // Copy a new object.
  static int RelocateNewObject(HeapObject* obj);

390 391 392 393 394 395 396
  // -----------------------------------------------------------------------
  // Phase 5: Rebuilding remembered sets.
  //
  //  Before: The heap is in a normal state except that remembered sets
  //          in the paged spaces are not correct.
  //
  //   After: The heap is in a normal state.
397 398 399 400 401

  // Rebuild remembered set in old and map spaces.
  static void RebuildRSets();

#ifdef DEBUG
402
  // -----------------------------------------------------------------------
403 404 405 406 407 408 409
  // Debugging variables, functions and classes
  // Counters used for debugging the marking phase of mark-compact or
  // mark-sweep collection.

  // Number of live objects in Heap::to_space_.
  static int live_young_objects_;

410 411 412 413 414
  // Number of live objects in Heap::old_pointer_space_.
  static int live_old_pointer_objects_;

  // Number of live objects in Heap::old_data_space_.
  static int live_old_data_objects_;
415 416

  // Number of live objects in Heap::code_space_.
417
  static int live_code_objects_;
418 419 420 421

  // Number of live objects in Heap::map_space_.
  static int live_map_objects_;

422 423 424
  // Number of live objects in Heap::cell_space_.
  static int live_cell_objects_;

425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442
  // Number of live objects in Heap::lo_space_.
  static int live_lo_objects_;

  // Number of live bytes in this collection.
  static int live_bytes_;

  friend class MarkObjectVisitor;
  static void VisitObject(HeapObject* obj);

  friend class UnmarkObjectVisitor;
  static void UnmarkObject(HeapObject* obj);
#endif
};


} }  // namespace v8::internal

#endif  // V8_MARK_COMPACT_H_