Support slots recording for compaction during incremental marking.

src/mark-compact.cc

 // 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 39 matching lines @@
 const char* Marking::kImpossibleBitPattern = "01";
 
 
 // -------------------------------------------------------------------------
 // MarkCompactCollector
 
 MarkCompactCollector::MarkCompactCollector() :  // NOLINT
 #ifdef DEBUG
       state_(IDLE),
 #endif
+      sweep_precisely_(false),
+      compacting_(false),
       tracer_(NULL),
 #ifdef DEBUG
       live_young_objects_size_(0),
       live_old_pointer_objects_size_(0),
       live_old_data_objects_size_(0),
       live_code_objects_size_(0),
       live_map_objects_size_(0),
       live_cell_objects_size_(0),
       live_lo_objects_size_(0),
       live_bytes_(0),
@@ skipping 77 matching lines @@
 }
 
 
 class VerifyEvacuationVisitor: public ObjectVisitor {
  public:
   void VisitPointers(Object** start, Object** end) {
     for (Object** current = start; current < end; current++) {
       if ((*current)->IsHeapObject()) {
         HeapObject* object = HeapObject::cast(*current);
         if (MarkCompactCollector::IsOnEvacuationCandidate(object)) {
-          HEAP->TracePathToObject(source_);
           CHECK(false);
         }
       }
     }
   }
 
   HeapObject* source_;
 };
 
 
@@ skipping 50 matching lines @@
 }
 #endif
 
 
 void MarkCompactCollector::AddEvacuationCandidate(Page* p) {
   p->MarkEvacuationCandidate();
   evacuation_candidates_.Add(p);
 }
 
 
+bool MarkCompactCollector::StartCompaction() {
+  // Don't start compaction if we are in the middle of incremental
+  // marking cycle. We did not collect any slots.
+  if (!compacting_ && !heap_->incremental_marking()->IsMarking()) {
+    ASSERT(evacuation_candidates_.length() == 0);
+
+    // TODO(gc) Shrink slots buffer when we receive low memory notification.
+    slots_buffer_.Clear();
+
+    CollectEvacuationCandidates(heap()->old_pointer_space());
+    CollectEvacuationCandidates(heap()->old_data_space());
+
+    heap()->old_pointer_space()->EvictEvacuationCandidatesFromFreeLists();
+    heap()->old_data_space()->EvictEvacuationCandidatesFromFreeLists();
+
+    compacting_ = evacuation_candidates_.length() > 0;
+  }
+
+  return compacting_;
+}
+
+
 void MarkCompactCollector::CollectGarbage() {
   // Make sure that Prepare() has been called. The individual steps below will
   // update the state as they proceed.
   ASSERT(state_ == PREPARE_GC);
 
   MarkLiveObjects();
   ASSERT(heap_->incremental_marking()->IsStopped());
 
   if (FLAG_collect_maps) ClearNonLiveTransitions();
 
@@ skipping 125 matching lines @@
     Page* p = it.next();
     if (space->IsFragmented(p)) {
       AddEvacuationCandidate(p);
     } else {
       p->ClearEvacuationCandidate();
     }
   }
 }
 
 
-static void ClearEvacuationCandidates(PagedSpace* space) {
-  ASSERT(space->identity() == OLD_POINTER_SPACE ||
-         space->identity() == OLD_DATA_SPACE);
-
-  PageIterator it(space);
-  while (it.has_next()) {
-    Page* p = it.next();
-    p->ClearEvacuationCandidate();
-  }
-}
-
-
 void MarkCompactCollector::Prepare(GCTracer* tracer) {
   // TODO(gc) re-enable code flushing.
   FLAG_flush_code = false;
   FLAG_always_compact = false;
 
   // Disable collection of maps if incremental marking is enabled.
   // TODO(gc) improve maps collection algorithm to work with incremental
   // marking.
   if (FLAG_incremental_marking) FLAG_collect_maps = false;
 
   // Rather than passing the tracer around we stash it in a static member
   // variable.
   tracer_ = tracer;
 
 #ifdef DEBUG
   ASSERT(state_ == IDLE);
   state_ = PREPARE_GC;
 #endif
   ASSERT(!FLAG_always_compact || !FLAG_never_compact);
 
   if (FLAG_collect_maps) CreateBackPointers();
 #ifdef ENABLE_GDB_JIT_INTERFACE
   if (FLAG_gdbjit) {
     // If GDBJIT interface is active disable compaction.
     compacting_collection_ = false;
   }
 #endif
 
-  if (!FLAG_never_compact) {
-    slots_buffer_.Clear();
-    evacuation_candidates_.Rewind(0);
-
-    if (!heap()->incremental_marking()->IsMarking()) {
-      CollectEvacuationCandidates(heap()->old_pointer_space());
-      CollectEvacuationCandidates(heap()->old_data_space());
-    } else {
-      ClearEvacuationCandidates(heap()->old_pointer_space());
-      ClearEvacuationCandidates(heap()->old_data_space());
-    }
-  }
+  if (!FLAG_never_compact) StartCompaction();
 
   PagedSpaces spaces;
   for (PagedSpace* space = spaces.next();
        space != NULL;
        space = spaces.next()) {
     space->PrepareForMarkCompact();
   }
 
   if (!heap()->incremental_marking()->IsMarking()) {
     ClearMarkbits(heap_);
@@ skipping 1820 matching lines @@
   }
 
   heap_->IncrementYoungSurvivorsCounter(survivors_size);
   new_space->set_age_mark(new_space->top());
 }
 
 
 void MarkCompactCollector::EvacuateLiveObjectsFromPage(Page* p) {
   AlwaysAllocateScope always_allocate;
 
+  ASSERT(p->IsEvacuationCandidate() && !p->WasEvacuated());
+
   PagedSpace* space = static_cast<PagedSpace*>(p->owner());
 
   MarkBit::CellType* cells = p->markbits()->cells();
 
   int last_cell_index =
       Bitmap::IndexToCell(
           Bitmap::CellAlignIndex(
               p->AddressToMarkbitIndex(p->ObjectAreaEnd())));
 
   int cell_index = Page::kFirstUsedCell;
@@ skipping 32 matching lines @@
 
 void MarkCompactCollector::EvacuatePages() {
   int npages = evacuation_candidates_.length();
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
     EvacuateLiveObjectsFromPage(p);
   }
 }
 
 
+class EvacuationWeakObjectRetainer : public WeakObjectRetainer {
+ public:
+  virtual Object* RetainAs(Object* object) {
+    if (object->IsHeapObject()) {
+      HeapObject* heap_object = HeapObject::cast(object);
+      MapWord map_word = heap_object->map_word();
+      if (map_word.IsForwardingAddress()) {
+        return map_word.ToForwardingAddress();
+      }
+    }
+    return object;
+  }
+};
+
+
 void MarkCompactCollector::EvacuateNewSpaceAndCandidates() {
   EvacuateNewSpace();
   EvacuatePages();
 
   // Second pass: find pointers to new space and update them.
   PointersUpdatingVisitor updating_visitor(heap());
 
   // Update pointers in to space.
   SemiSpaceIterator to_it(heap()->new_space()->bottom(),
                           heap()->new_space()->top());
   for (HeapObject* object = to_it.Next();
        object != NULL;
        object = to_it.Next()) {
     Map* map = object->map();
     object->IterateBody(map->instance_type(),
                         object->SizeFromMap(map),
                         &updating_visitor);
   }
 
   // Update roots.
   heap_->IterateRoots(&updating_visitor, VISIT_ALL_IN_SWEEP_NEWSPACE);
   LiveObjectList::IterateElements(&updating_visitor);
 
   {
     StoreBufferRebuildScope scope(heap_,
                                   heap_->store_buffer(),
                                   &Heap::ScavengeStoreBufferCallback);
     heap_->store_buffer()->IteratePointersToNewSpace(&UpdatePointer);
   }
-  slots_buffer_.Iterate(&updating_visitor);
+  slots_buffer_.Update();
 
   // Update pointers from cells.
   HeapObjectIterator cell_iterator(heap_->cell_space());
   for (HeapObject* cell = cell_iterator.Next();
        cell != NULL;
        cell = cell_iterator.Next()) {
     if (cell->IsJSGlobalPropertyCell()) {
       Address value_address =
           reinterpret_cast<Address>(cell) +
           (JSGlobalPropertyCell::kValueOffset - kHeapObjectTag);
       updating_visitor.VisitPointer(reinterpret_cast<Object**>(value_address));
     }
   }
 
   // Update pointer from the global contexts list.
   updating_visitor.VisitPointer(heap_->global_contexts_list_address());
 
   heap_->symbol_table()->Iterate(&updating_visitor);
 
   // Update pointers from external string table.
   heap_->UpdateReferencesInExternalStringTable(
       &UpdateReferenceInExternalStringTableEntry);
 
   // Update JSFunction pointers from the runtime profiler.
   heap_->isolate()->runtime_profiler()->UpdateSamplesAfterScavenge();
 
+  EvacuationWeakObjectRetainer evacuation_object_retainer;
+  heap()->ProcessWeakReferences(&evacuation_object_retainer);
+
 #ifdef DEBUG
   if (FLAG_verify_heap) {
     VerifyEvacuation(heap_);
   }
 #endif
 
   int npages = evacuation_candidates_.length();
+  ASSERT(compacting_ == (npages > 0));
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
+    ASSERT(p->IsEvacuationCandidate() && !p->WasEvacuated());
     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
     space->Free(p->ObjectAreaStart(), Page::kObjectAreaSize);
     p->set_scan_on_scavenge(false);
-
-    // We are not clearing evacuation candidate flag here
-    // because it is required to notify lazy sweeper to skip
-    // these pages.
+    p->ClearEvacuationCandidate();
+    p->SetFlag(MemoryChunk::EVACUATED);
+    p->ClearFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
   }
+  evacuation_candidates_.Rewind(0);
+  compacting_ = false;
 }
 
 
 INLINE(static uint32_t SweepFree(PagedSpace* space,
                                  Page* p,
                                  uint32_t free_start,
                                  uint32_t region_end,
                                  uint32_t* cells));
 
 
@@ skipping 307 matching lines @@
 
 
 // Sweeps a space conservatively.  After this has been done the larger free
 // spaces have been put on the free list and the smaller ones have been
 // ignored and left untouched.  A free space is always either ignored or put
 // on the free list, never split up into two parts.  This is important
 // because it means that any FreeSpace maps left actually describe a region of
 // memory that can be ignored when scanning.  Dead objects other than free
 // spaces will not contain the free space map.
 int MarkCompactCollector::SweepConservatively(PagedSpace* space, Page* p) {
-  // We might start advancing sweeper before evacuation happened.
-  if (p->IsEvacuationCandidate()) return 0;
+  ASSERT(!p->IsEvacuationCandidate() && !p->WasEvacuated());
 
   int freed_bytes = 0;
 
   MarkBit::CellType* cells = p->markbits()->cells();
 
   p->SetFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
 
   // This is the start of the 32 word block that we are currently looking at.
   Address block_address = p->ObjectAreaStart();
 
@@ skipping 67 matching lines @@
   return freed_bytes;
 }
 
 
 // Sweep a space precisely.  After this has been done the space can
 // be iterated precisely, hitting only the live objects.  Code space
 // is always swept precisely because we want to be able to iterate
 // over it.  Map space is swept precisely, because it is not compacted.
 static void SweepPrecisely(PagedSpace* space,
                            Page* p) {
+  ASSERT(!p->IsEvacuationCandidate() && !p->WasEvacuated());
   MarkBit::CellType* cells = p->markbits()->cells();
 
   p->ClearFlag(MemoryChunk::WAS_SWEPT_CONSERVATIVELY);
 
   int last_cell_index =
       Bitmap::IndexToCell(
           Bitmap::CellAlignIndex(
               p->AddressToMarkbitIndex(p->ObjectAreaEnd())));
 
   int cell_index = Page::kFirstUsedCell;
@@ skipping 235 matching lines @@
     if (buffer_idx_ == buffers_.length()) {
       buffers_.Add(new ObjectSlot[kBufferSize]);
     }
     buffer_ = buffers_[buffer_idx_];
   }
 
   buffer_[idx_++] = slot;
 }
 
 
-void SlotsBuffer::Iterate(ObjectVisitor* visitor) {
+static inline void UpdateSlot(Object** slot) {
+  Object* obj = *slot;
+  if (!obj->IsHeapObject()) return;
+
+  HeapObject* heap_obj = HeapObject::cast(obj);
+
+  MapWord map_word = heap_obj->map_word();
+  if (map_word.IsForwardingAddress()) {
+    ASSERT(MarkCompactCollector::IsOnEvacuationCandidate(*slot));
+    *slot = map_word.ToForwardingAddress();
+    ASSERT(!MarkCompactCollector::IsOnEvacuationCandidate(*slot));
+  }
+}
+
+
+void SlotsBuffer::Update() {
   if (buffer_idx_ < 0) return;
 
   for (int buffer_index = 0; buffer_index < buffer_idx_; ++buffer_index) {
     ObjectSlot* buffer = buffers_[buffer_index];
     for (int slot_idx = 0; slot_idx < kBufferSize; ++slot_idx) {
-      visitor->VisitPointer(buffer[slot_idx]);
+      UpdateSlot(buffer[slot_idx]);
     }
   }
 
   ObjectSlot* last_buffer = buffers_[buffer_idx_];
   for (int slot_idx = 0; slot_idx < idx_; ++slot_idx) {
-    visitor->VisitPointer(last_buffer[slot_idx]);
+    UpdateSlot(last_buffer[slot_idx]);
   }
 }
 
 
 void SlotsBuffer::Report() {
 }
 
 
 } }  // namespace v8::internal