Simple non-incremental compaction by evacuation.

src/mark-compact.h

 // Copyright 2011 the V8 project authors. All rights reserved.
 // 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
@@ skipping 238 matching lines @@
   // (mod mask + 1).
   int top_;
   int bottom_;
   int mask_;
   bool overflowed_;
 
   DISALLOW_COPY_AND_ASSIGN(MarkingDeque);
 };
 
 
+class SlotsBuffer {
+ public:
+  typedef Object** ObjectSlot;
+
+  SlotsBuffer();
+  ~SlotsBuffer();
+
+  void Clear();
+  void Add(ObjectSlot slot);
+  void Iterate(ObjectVisitor* visitor);
+  void Report();
+ private:

[Erik Corry, 2011/06/20 20:41:26]

missing blank line before private:

[Vyacheslav Egorov (Chromium), 2011/06/21 11:44:48]

Done.

+  static const int kBufferSize = 1024;
+
+  List<ObjectSlot*> buffers_;
+  ObjectSlot* buffer_;
+
+  int idx_;
+  int buffer_idx_;
+};
+
+
 // -------------------------------------------------------------------------
 // Mark-Compact collector
 class MarkCompactCollector {
  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 MaybeObject* (*AllocationFunction)(Heap* heap,
@@ skipping 23 matching lines @@
   // Set the global force_compaction flag, it must be called before Prepare
   // to take effect.
   inline void SetFlags(int flags);
 
   inline bool PreciseSweepingRequired() {
     return sweep_precisely_;
   }
 
   static void Initialize();
 
+  void CollectEvacuationCandidates(PagedSpace* space);
+
+  void AddEvacuationCandidate(Page* p);
+
   // Prepares for GC by resetting relocation info in old and map spaces and
   // choosing spaces to compact.
   void Prepare(GCTracer* tracer);
 
   // Performs a global garbage collection.
   void CollectGarbage();
 
-  // True if the last full GC performed heap compaction.
-  bool HasCompacted() { return compacting_collection_; }
-
-  // True after the Prepare phase if the compaction is taking place.
-  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
-  }
-
   // During a full GC, there is a stack-allocated GCTracer that is used for
   // bookkeeping information.  Return a pointer to that tracer.
   GCTracer* tracer() { return tracer_; }
 
 #ifdef DEBUG
   // Checks whether performing mark-compact collection.
   bool in_use() { return state_ > PREPARE_GC; }
   bool are_map_pointers_encoded() { return state_ == UPDATE_POINTERS; }
 #endif
 
   // Determine type of object and emit deletion log event.
   static void ReportDeleteIfNeeded(HeapObject* obj, Isolate* isolate);
 
   // Distinguishable invalid map encodings (for single word and multiple words)
   // that indicate free regions.
   static const uint32_t kSingleFreeEncoding = 0;
   static const uint32_t kMultiFreeEncoding = 1;
 
-  inline bool IsMarked(Object* obj);
+  static inline bool IsMarked(Object* obj);
 
   inline Heap* heap() const { return heap_; }
 
   CodeFlusher* code_flusher() { return code_flusher_; }
   inline bool is_code_flushing_enabled() const { return code_flusher_ != NULL; }
   void EnableCodeFlushing(bool enable);
 
   enum SweeperType {
     CONSERVATIVE,
     LAZY_CONSERVATIVE,
     PRECISE
   };
 
   // Sweep a single page from the given space conservatively.
   // Return a number of reclaimed bytes.
   static int SweepConservatively(PagedSpace* space, Page* p);
 
+  INLINE(static bool IsOnEvacuationCandidateOrInNewSpace(Address anchor)) {
+    return Page::FromAddress(anchor)->IsEvacuationCandidateOrNewSpace();
+  }
+
+  INLINE(static bool IsOnEvacuationCandidate(Object* obj)) {
+    return Page::FromAddress(reinterpret_cast<Address>(obj))->
+        IsEvacuationCandidate();
+  }
+
+  INLINE(void RecordSlot(Address anchor, Object** slot, Object* object)) {
+    if (IsOnEvacuationCandidate(object) &&
+        !IsOnEvacuationCandidateOrInNewSpace(anchor)) {
+      slots_buffer_.Add(slot);
+    }
+  }
+
+  void MigrateObject(Address dst,
+                     Address src,
+                     int size,
+                     AllocationSpace to_old_space);
+
+  bool TryPromoteObject(HeapObject* object, int object_size);
+
  private:
   MarkCompactCollector();
   ~MarkCompactCollector();
 
 #ifdef DEBUG
   enum CollectorState {
     IDLE,
     PREPARE_GC,
     MARK_LIVE_OBJECTS,
     SWEEP_SPACES,
     ENCODE_FORWARDING_ADDRESSES,
     UPDATE_POINTERS,
     RELOCATE_OBJECTS
   };
 
   // The current stage of the collector.
   CollectorState state_;
 #endif
 
-  // Global flag that forces a compaction.
-  bool force_compaction_;
-
   // Global flag that forces sweeping to be precise, so we can traverse the
   // heap.
   bool sweep_precisely_;
 
-  // Global flag indicating whether spaces were compacted on the last GC.
-  bool compacting_collection_;
-
-  // Global flag indicating whether spaces will be compacted on the next GC.
-  bool compact_on_next_gc_;
-
-  // The number of objects left marked at the end of the last completed full
-  // GC (expected to be zero).
-  int previous_marked_count_;
-
   // A pointer to the current stack-allocated GC tracer object during a full
   // collection (NULL before and after).
   GCTracer* tracer_;
 
+  SlotsBuffer slots_buffer_;
+
   // Finishes GC, performs heap verification if enabled.
   void Finish();
 
   // -----------------------------------------------------------------------
   // Phase 1: Marking live objects.
   //
   //  Before: The heap has been prepared for garbage collection by
   //          MarkCompactCollector::Prepare() and is otherwise in its
   //          normal state.
   //
@@ skipping 65 matching lines @@
   void RefillMarkingDeque();
 
   // Callback function for telling whether the object *p is an unmarked
   // heap object.
   static bool IsUnmarkedHeapObject(Object** p);
 
 #ifdef DEBUG
   void UpdateLiveObjectCount(HeapObject* obj);
 #endif
 
-  // Test whether a (possibly marked) object is a Map.
-  static inline bool SafeIsMap(HeapObject* object);
-
   // Map transitions from a live map to a dead map must be killed.
   // We replace them with a null descriptor, with the same key.
   void ClearNonLiveTransitions();
 
   // -----------------------------------------------------------------------
   // Phase 2: Sweeping to clear mark bits and free non-live objects for
   // a non-compacting collection.
   //
   //  Before: Live objects are marked and non-live objects are unmarked.
   //
@@ skipping 12 matching lines @@
   // Iterates the live objects between a range of addresses, returning the
   // number of live objects.
   int IterateLiveObjectsInRange(Address start, Address end,
                                 LiveObjectCallback size_func);
 
   // 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.
   void SweepSpaces();
 
-  void SweepNewSpace(NewSpace* space);
+  void EvacuateNewSpace();
 
+  void EvacuateLiveObjectsFromPage(Page* p);
+
+  void EvacuatePages();
+
+  void EvacuateNewSpaceAndCandidates();
 
   void SweepSpace(PagedSpace* space, SweeperType sweeper);
 
 
 #ifdef DEBUG
   // -----------------------------------------------------------------------
   // Debugging variables, functions and classes
   // Counters used for debugging the marking phase of mark-compact or
   // mark-sweep collection.
 
@@ skipping 25 matching lines @@
   static void VisitObject(HeapObject* obj);
 
   friend class UnmarkObjectVisitor;
   static void UnmarkObject(HeapObject* obj);
 #endif
 
   Heap* heap_;
   MarkingDeque marking_deque_;
   CodeFlusher* code_flusher_;
 
+  List<Page*> evacuation_candidates_;
+
   friend class Heap;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_MARK_COMPACT_H_