[heap] Parallel newspace evacuation, semispace copy, and compaction \o/

src/heap/mark-compact.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/heap/mark-compact.h"
 
 #include "src/base/atomicops.h"
 #include "src/base/bits.h"
 #include "src/base/sys-info.h"
 #include "src/code-stubs.h"
 #include "src/compilation-cache.h"
 #include "src/deoptimizer.h"
 #include "src/execution.h"
 #include "src/frames-inl.h"
 #include "src/gdb-jit.h"
 #include "src/global-handles.h"
 #include "src/heap/array-buffer-tracker.h"
 #include "src/heap/gc-tracer.h"
 #include "src/heap/incremental-marking.h"
 #include "src/heap/mark-compact-inl.h"
 #include "src/heap/object-stats.h"
 #include "src/heap/objects-visiting.h"
 #include "src/heap/objects-visiting-inl.h"
 #include "src/heap/slots-buffer.h"
 #include "src/heap/spaces-inl.h"
 #include "src/ic/ic.h"
 #include "src/ic/stub-cache.h"
 #include "src/profiler/cpu-profiler.h"
+#include "src/utils-inl.h"
 #include "src/v8.h"
 
 namespace v8 {
 namespace internal {
 
 
 const char* Marking::kWhiteBitPattern = "00";
 const char* Marking::kBlackBitPattern = "11";
 const char* Marking::kGreyBitPattern = "10";
 const char* Marking::kImpossibleBitPattern = "01";
@@ skipping 274 matching lines @@
 void MarkCompactCollector::ClearInvalidStoreAndSlotsBufferEntries() {
   {
     GCTracer::Scope gc_scope(heap()->tracer(),
                              GCTracer::Scope::MC_CLEAR_STORE_BUFFER);
     heap_->store_buffer()->ClearInvalidStoreBufferEntries();
   }
 
   {
     GCTracer::Scope gc_scope(heap()->tracer(),
                              GCTracer::Scope::MC_CLEAR_SLOTS_BUFFER);
-    int number_of_pages = evacuation_candidates_.length();
-    for (int i = 0; i < number_of_pages; i++) {
-      Page* p = evacuation_candidates_[i];
+    for (Page* p : evacuation_candidates_) {
       SlotsBuffer::RemoveInvalidSlots(heap_, p->slots_buffer());
     }
   }
 #ifdef VERIFY_HEAP
   if (FLAG_verify_heap) {
     VerifyValidStoreAndSlotsBufferEntries();
   }
 #endif
 }
 
@@ skipping 135 matching lines @@
 
   LargeObjectIterator it(heap_->lo_space());
   for (HeapObject* obj = it.Next(); obj != NULL; obj = it.Next()) {
     Marking::MarkWhite(Marking::MarkBitFrom(obj));
     Page::FromAddress(obj->address())->ResetProgressBar();
     Page::FromAddress(obj->address())->ResetLiveBytes();
   }
 }
 
 
-class MarkCompactCollector::CompactionTask : public CancelableTask {
- public:
-  explicit CompactionTask(Heap* heap, CompactionSpaceCollection* spaces)
-      : CancelableTask(heap->isolate()), spaces_(spaces) {}
-
-  virtual ~CompactionTask() {}
-
- private:
-  // v8::internal::CancelableTask overrides.
-  void RunInternal() override {
-    MarkCompactCollector* mark_compact =
-        isolate()->heap()->mark_compact_collector();
-    SlotsBuffer* evacuation_slots_buffer = nullptr;
-    mark_compact->EvacuatePages(spaces_, &evacuation_slots_buffer);
-    mark_compact->AddEvacuationSlotsBufferSynchronized(evacuation_slots_buffer);
-    mark_compact->pending_compaction_tasks_semaphore_.Signal();
-  }
-
-  CompactionSpaceCollection* spaces_;
-
-  DISALLOW_COPY_AND_ASSIGN(CompactionTask);
-};
-
-
 class MarkCompactCollector::SweeperTask : public v8::Task {
  public:
   SweeperTask(Heap* heap, PagedSpace* space) : heap_(heap), space_(space) {}
 
   virtual ~SweeperTask() {}
 
  private:
   // v8::Task overrides.
   void Run() override {
     heap_->mark_compact_collector()->SweepInParallel(space_, 0);
@@ skipping 309 matching lines @@
                  "compaction-selection: space=%s reduce_memory=%d pages=%d "
                  "total_live_bytes=%d\n",
                  AllocationSpaceName(space->identity()), reduce_memory,
                  candidate_count, total_live_bytes / KB);
   }
 }
 
 
 void MarkCompactCollector::AbortCompaction() {
   if (compacting_) {
-    int npages = evacuation_candidates_.length();
-    for (int i = 0; i < npages; i++) {
-      Page* p = evacuation_candidates_[i];
+    for (Page* p : evacuation_candidates_) {
       slots_buffer_allocator_->DeallocateChain(p->slots_buffer_address());
       p->ClearEvacuationCandidate();
       p->ClearFlag(MemoryChunk::RESCAN_ON_EVACUATION);
     }
     compacting_ = false;
     evacuation_candidates_.Rewind(0);
   }
   DCHECK_EQ(0, evacuation_candidates_.length());
 }
 
@@ skipping 694 matching lines @@
 class MarkCompactCollector::HeapObjectVisitor {
  public:
   virtual ~HeapObjectVisitor() {}
   virtual bool Visit(HeapObject* object) = 0;
 };
 
 
 class MarkCompactCollector::EvacuateVisitorBase
     : public MarkCompactCollector::HeapObjectVisitor {
  public:
-  EvacuateVisitorBase(Heap* heap, SlotsBuffer** evacuation_slots_buffer)
-      : heap_(heap), evacuation_slots_buffer_(evacuation_slots_buffer) {}
+  EvacuateVisitorBase(Heap* heap, CompactionSpaceCollection* compaction_spaces,
+                      SlotsBuffer** evacuation_slots_buffer,
+                      LocalStoreBuffer* local_store_buffer)
+      : heap_(heap),
+        evacuation_slots_buffer_(evacuation_slots_buffer),
+        compaction_spaces_(compaction_spaces),
+        local_store_buffer_(local_store_buffer) {}
 
   bool TryEvacuateObject(PagedSpace* target_space, HeapObject* object,
                          HeapObject** target_object) {
     int size = object->Size();
     AllocationAlignment alignment = object->RequiredAlignment();
     AllocationResult allocation = target_space->AllocateRaw(size, alignment);
     if (allocation.To(target_object)) {
       heap_->mark_compact_collector()->MigrateObject(
           *target_object, object, size, target_space->identity(),
-          evacuation_slots_buffer_);
+          evacuation_slots_buffer_, local_store_buffer_);
       return true;
     }
     return false;
   }
 
  protected:
   Heap* heap_;
   SlotsBuffer** evacuation_slots_buffer_;
+  CompactionSpaceCollection* compaction_spaces_;
+  LocalStoreBuffer* local_store_buffer_;
 };
 
 
 class MarkCompactCollector::EvacuateNewSpaceVisitor final
     : public MarkCompactCollector::EvacuateVisitorBase {
  public:
   static const intptr_t kLabSize = 4 * KB;
   static const intptr_t kMaxLabObjectSize = 256;
 
   explicit EvacuateNewSpaceVisitor(Heap* heap,
+                                   CompactionSpaceCollection* compaction_spaces,
                                    SlotsBuffer** evacuation_slots_buffer,
+                                   LocalStoreBuffer* local_store_buffer,
                                    HashMap* local_pretenuring_feedback)
-      : EvacuateVisitorBase(heap, evacuation_slots_buffer),
+      : EvacuateVisitorBase(heap, compaction_spaces, evacuation_slots_buffer,
+                            local_store_buffer),
         buffer_(LocalAllocationBuffer::InvalidBuffer()),
         space_to_allocate_(NEW_SPACE),
         promoted_size_(0),
         semispace_copied_size_(0),
         local_pretenuring_feedback_(local_pretenuring_feedback) {}
 
   bool Visit(HeapObject* object) override {
     heap_->UpdateAllocationSite(object, local_pretenuring_feedback_);
     int size = object->Size();
     HeapObject* target_object = nullptr;
     if (heap_->ShouldBePromoted(object->address(), size) &&
-        TryEvacuateObject(heap_->old_space(), object, &target_object)) {
+        TryEvacuateObject(compaction_spaces_->Get(OLD_SPACE), object,
+                          &target_object)) {
       // If we end up needing more special cases, we should factor this out.
       if (V8_UNLIKELY(target_object->IsJSArrayBuffer())) {
         heap_->array_buffer_tracker()->Promote(
             JSArrayBuffer::cast(target_object));
       }
       promoted_size_ += size;
       return true;
     }
     HeapObject* target = nullptr;
     AllocationSpace space = AllocateTargetObject(object, &target);
     heap_->mark_compact_collector()->MigrateObject(
         HeapObject::cast(target), object, size, space,
-        (space == NEW_SPACE) ? nullptr : evacuation_slots_buffer_);
+        (space == NEW_SPACE) ? nullptr : evacuation_slots_buffer_,
+        local_store_buffer_);

[Hannes Payer (out of office), 2016/01/25 16:04:13]

Symmetrically to the slots buffer we should only pass in the store buffer when
moving to an old space.

[Michael Lippautz, 2016/01/25 16:26:14]

Done.

     if (V8_UNLIKELY(target->IsJSArrayBuffer())) {
       heap_->array_buffer_tracker()->MarkLive(JSArrayBuffer::cast(target));
     }
     semispace_copied_size_ += size;
     return true;
   }
 
   intptr_t promoted_size() { return promoted_size_; }
   intptr_t semispace_copied_size() { return semispace_copied_size_; }
 
@@ skipping 51 matching lines @@
         if (allocation.IsRetry()) {
           if (mode == kStickyBailoutOldSpace) space_to_allocate_ = OLD_SPACE;
         }
       }
     }
     return allocation;
   }
 
   inline AllocationResult AllocateInOldSpace(int size_in_bytes,
                                              AllocationAlignment alignment) {
-    AllocationResult allocation =
-        heap_->old_space()->AllocateRaw(size_in_bytes, alignment);
+    AllocationResult allocation = compaction_spaces_->Get(OLD_SPACE)
+                                      ->AllocateRaw(size_in_bytes, alignment);
     if (allocation.IsRetry()) {
       FatalProcessOutOfMemory(
           "MarkCompactCollector: semi-space copy, fallback in old gen\n");
     }
     return allocation;
   }
 
   inline AllocationResult AllocateInLab(int size_in_bytes,
                                         AllocationAlignment alignment) {
     AllocationResult allocation;
@@ skipping 25 matching lines @@
   intptr_t semispace_copied_size_;
   HashMap* local_pretenuring_feedback_;
 };
 
 
 class MarkCompactCollector::EvacuateOldSpaceVisitor final
     : public MarkCompactCollector::EvacuateVisitorBase {
  public:
   EvacuateOldSpaceVisitor(Heap* heap,
                           CompactionSpaceCollection* compaction_spaces,
-                          SlotsBuffer** evacuation_slots_buffer)
-      : EvacuateVisitorBase(heap, evacuation_slots_buffer),
-        compaction_spaces_(compaction_spaces) {}
+                          SlotsBuffer** evacuation_slots_buffer,
+                          LocalStoreBuffer* local_store_buffer)
+      : EvacuateVisitorBase(heap, compaction_spaces, evacuation_slots_buffer,
+                            local_store_buffer) {}
 
   bool Visit(HeapObject* object) override {
     CompactionSpace* target_space = compaction_spaces_->Get(
         Page::FromAddress(object->address())->owner()->identity());
     HeapObject* target_object = nullptr;
     if (TryEvacuateObject(target_space, object, &target_object)) {
       DCHECK(object->map_word().IsForwardingAddress());
       return true;
     }
     return false;
   }
-
- private:
-  CompactionSpaceCollection* compaction_spaces_;
 };
 
 
 void MarkCompactCollector::DiscoverGreyObjectsInSpace(PagedSpace* space) {
   PageIterator it(space);
   while (it.has_next()) {
     Page* p = it.next();
     DiscoverGreyObjectsOnPage(p);
     if (marking_deque()->IsFull()) return;
   }
@@ skipping 789 matching lines @@
   while (obj != Smi::FromInt(0)) {
     TransitionArray* array = TransitionArray::cast(obj);
     obj = array->next_link();
     array->set_next_link(undefined, SKIP_WRITE_BARRIER);
   }
   heap()->set_encountered_transition_arrays(Smi::FromInt(0));
 }
 
 
 void MarkCompactCollector::RecordMigratedSlot(
-    Object* value, Address slot, SlotsBuffer** evacuation_slots_buffer) {
+    Object* value, Address slot, SlotsBuffer** evacuation_slots_buffer,
+    LocalStoreBuffer* local_store_buffer) {
   // When parallel compaction is in progress, store and slots buffer entries
   // require synchronization.
   if (heap_->InNewSpace(value)) {
     if (compaction_in_progress_) {
-      heap_->store_buffer()->MarkSynchronized(slot);
+      local_store_buffer->Record(slot);
     } else {
       heap_->store_buffer()->Mark(slot);
     }
   } else if (value->IsHeapObject() && IsOnEvacuationCandidate(value)) {
     SlotsBuffer::AddTo(slots_buffer_allocator_, evacuation_slots_buffer,
                        reinterpret_cast<Object**>(slot),
                        SlotsBuffer::IGNORE_OVERFLOW);
   }
 }
 
@@ skipping 61 matching lines @@
     if (!success) {
       EvictPopularEvacuationCandidate(target_page);
     }
   }
 }
 
 
 class RecordMigratedSlotVisitor final : public ObjectVisitor {
  public:
   RecordMigratedSlotVisitor(MarkCompactCollector* collector,
-                            SlotsBuffer** evacuation_slots_buffer)
+                            SlotsBuffer** evacuation_slots_buffer,
+                            LocalStoreBuffer* local_store_buffer)
       : collector_(collector),
-        evacuation_slots_buffer_(evacuation_slots_buffer) {}
+        evacuation_slots_buffer_(evacuation_slots_buffer),
+        local_store_buffer_(local_store_buffer) {}
 
   V8_INLINE void VisitPointer(Object** p) override {
     collector_->RecordMigratedSlot(*p, reinterpret_cast<Address>(p),
-                                   evacuation_slots_buffer_);
+                                   evacuation_slots_buffer_,
+                                   local_store_buffer_);
   }
 
   V8_INLINE void VisitPointers(Object** start, Object** end) override {
     while (start < end) {
       collector_->RecordMigratedSlot(*start, reinterpret_cast<Address>(start),
-                                     evacuation_slots_buffer_);
+                                     evacuation_slots_buffer_,
+                                     local_store_buffer_);
       ++start;
     }
   }
 
   V8_INLINE void VisitCodeEntry(Address code_entry_slot) override {
     if (collector_->compacting_) {
       Address code_entry = Memory::Address_at(code_entry_slot);
       collector_->RecordMigratedCodeEntrySlot(code_entry, code_entry_slot,
                                               evacuation_slots_buffer_);
     }
   }
 
  private:
   MarkCompactCollector* collector_;
   SlotsBuffer** evacuation_slots_buffer_;
+  LocalStoreBuffer* local_store_buffer_;
 };
 
 
 // We scavenge new space simultaneously with sweeping. This is done in two
 // passes.
 //
 // The first pass migrates all alive objects from one semispace to another or
 // promotes them to old space.  Forwarding address is written directly into
 // first word of object without any encoding.  If object is dead we write
 // NULL as a forwarding address.
 //
 // The second pass updates pointers to new space in all spaces.  It is possible
 // to encounter pointers to dead new space objects during traversal of pointers
 // to new space.  We should clear them to avoid encountering them during next
 // pointer iteration.  This is an issue if the store buffer overflows and we
 // have to scan the entire old space, including dead objects, looking for
 // pointers to new space.
-void MarkCompactCollector::MigrateObject(
-    HeapObject* dst, HeapObject* src, int size, AllocationSpace dest,
-    SlotsBuffer** evacuation_slots_buffer) {
+void MarkCompactCollector::MigrateObject(HeapObject* dst, HeapObject* src,
+                                         int size, AllocationSpace dest,
+                                         SlotsBuffer** evacuation_slots_buffer,
+                                         LocalStoreBuffer* local_store_buffer) {
   Address dst_addr = dst->address();
   Address src_addr = src->address();
   DCHECK(heap()->AllowedToBeMigrated(src, dest));
   DCHECK(dest != LO_SPACE);
   if (dest == OLD_SPACE) {
     DCHECK_OBJECT_SIZE(size);
     DCHECK(evacuation_slots_buffer != nullptr);
     DCHECK(IsAligned(size, kPointerSize));
 
     heap()->MoveBlock(dst->address(), src->address(), size);
-    RecordMigratedSlotVisitor visitor(this, evacuation_slots_buffer);
+    RecordMigratedSlotVisitor visitor(this, evacuation_slots_buffer,
+                                      local_store_buffer);
     dst->IterateBody(&visitor);
   } else if (dest == CODE_SPACE) {
     DCHECK_CODEOBJECT_SIZE(size, heap()->code_space());
     DCHECK(evacuation_slots_buffer != nullptr);
     PROFILE(isolate(), CodeMoveEvent(src_addr, dst_addr));
     heap()->MoveBlock(dst_addr, src_addr, size);
     RecordMigratedCodeObjectSlot(dst_addr, evacuation_slots_buffer);
     Code::cast(dst)->Relocate(dst_addr - src_addr);
   } else {
     DCHECK_OBJECT_SIZE(size);
@@ skipping 341 matching lines @@
   CHECK(Marking::IsBlack(Marking::MarkBitFrom(object)));
 
   // The target object is black but we don't know if the source slot is black.
   // The source object could have died and the slot could be part of a free
   // space. Use the mark bit iterator to find out about liveness of the slot.
   CHECK(IsSlotInBlackObjectSlow(Page::FromAddress(slot), slot));
 }
 
 
 void MarkCompactCollector::EvacuateNewSpacePrologue() {
-  // There are soft limits in the allocation code, designed trigger a mark
-  // sweep collection by failing allocations.  But since we are already in
-  // a mark-sweep allocation, there is no sense in trying to trigger one.
-  AlwaysAllocateScope scope(isolate());
-
   NewSpace* new_space = heap()->new_space();
-
-  // Store allocation range before flipping semispaces.
-  Address from_bottom = new_space->bottom();
-  Address from_top = new_space->top();
-
-  // Flip the semispaces.  After flipping, to space is empty, from space has
-  // live objects.
-  new_space->Flip();
-  new_space->ResetAllocationInfo();
-
-  newspace_evacuation_candidates_.Clear();
-  NewSpacePageIterator it(from_bottom, from_top);
+  NewSpacePageIterator it(new_space->bottom(), new_space->top());
+  // Append the list of new space pages to be processed.
   while (it.has_next()) {
     newspace_evacuation_candidates_.Add(it.next());
   }
+  new_space->Flip();
+  new_space->ResetAllocationInfo();
 }
 
 
-HashMap* MarkCompactCollector::EvacuateNewSpaceInParallel() {
-  HashMap* local_pretenuring_feedback = new HashMap(
-      HashMap::PointersMatch, kInitialLocalPretenuringFeedbackCapacity);
-  EvacuateNewSpaceVisitor new_space_visitor(heap(), &migration_slots_buffer_,
-                                            local_pretenuring_feedback);
-  // First pass: traverse all objects in inactive semispace, remove marks,
-  // migrate live objects and write forwarding addresses.  This stage puts
-  // new entries in the store buffer and may cause some pages to be marked
-  // scan-on-scavenge.
-  for (int i = 0; i < newspace_evacuation_candidates_.length(); i++) {
-    NewSpacePage* p =
-        reinterpret_cast<NewSpacePage*>(newspace_evacuation_candidates_[i]);
-    bool ok = VisitLiveObjects(p, &new_space_visitor, kClearMarkbits);
-    USE(ok);
-    DCHECK(ok);
-  }
-  heap_->IncrementPromotedObjectsSize(
-      static_cast<int>(new_space_visitor.promoted_size()));
-  heap_->IncrementSemiSpaceCopiedObjectSize(
-      static_cast<int>(new_space_visitor.semispace_copied_size()));
-  heap_->IncrementYoungSurvivorsCounter(
-      static_cast<int>(new_space_visitor.promoted_size()) +
-      static_cast<int>(new_space_visitor.semispace_copied_size()));
-  return local_pretenuring_feedback;
+void MarkCompactCollector::EvacuateNewSpaceEpilogue() {
+  newspace_evacuation_candidates_.Rewind(0);
 }
 
 
 void MarkCompactCollector::AddEvacuationSlotsBufferSynchronized(
     SlotsBuffer* evacuation_slots_buffer) {
   base::LockGuard<base::Mutex> lock_guard(&evacuation_slots_buffers_mutex_);
   evacuation_slots_buffers_.Add(evacuation_slots_buffer);
 }
 
 
-int MarkCompactCollector::NumberOfParallelCompactionTasks() {
+class MarkCompactCollector::Evacuator : public Malloced {
+ public:
+  Evacuator(MarkCompactCollector* collector,
+            const List<Page*>& evacuation_candidates,
+            const List<NewSpacePage*>& newspace_evacuation_candidates)
+      : collector_(collector),
+        evacuation_candidates_(evacuation_candidates),
+        newspace_evacuation_candidates_(newspace_evacuation_candidates),
+        compaction_spaces_(collector->heap()),
+        local_slots_buffer_(nullptr),
+        local_store_buffer_(),
+        local_pretenuring_feedback_(HashMap::PointersMatch,
+                                    kInitialLocalPretenuringFeedbackCapacity),
+        new_space_visitor_(collector->heap(), &compaction_spaces_,
+                           &local_slots_buffer_, &local_store_buffer_,
+                           &local_pretenuring_feedback_),
+        old_space_visitor_(collector->heap(), &compaction_spaces_,
+                           &local_slots_buffer_, &local_store_buffer_),
+        duration_(0.0),
+        bytes_compacted_(0),
+        task_id_(0) {}
+
+  // Evacuate the configured set of pages in parallel.
+  inline void EvacuatePages();
+
+  // Merge back locally cached info sequentially. Note that this method needs
+  // to be called from the main thread.
+  inline void Finalize();
+
+  CompactionSpaceCollection* compaction_spaces() { return &compaction_spaces_; }
+
+  uint32_t task_id() { return task_id_; }
+  void set_task_id(uint32_t id) { task_id_ = id; }
+
+ private:
+  static const int kInitialLocalPretenuringFeedbackCapacity = 256;
+
+  Heap* heap() { return collector_->heap(); }
+
+  void ReportCompactionProgress(double duration, intptr_t bytes_compacted) {
+    duration_ += duration;
+    bytes_compacted_ += bytes_compacted;
+  }
+
+  inline bool EvacuateSinglePage(MemoryChunk* p, HeapObjectVisitor* visitor);
+
+  MarkCompactCollector* collector_;
+
+  // Pages to process.
+  const List<Page*>& evacuation_candidates_;
+  const List<NewSpacePage*>& newspace_evacuation_candidates_;
+
+  // Locally cached collector data.
+  CompactionSpaceCollection compaction_spaces_;
+  SlotsBuffer* local_slots_buffer_;
+  LocalStoreBuffer local_store_buffer_;
+  HashMap local_pretenuring_feedback_;
+
+  // Vistors for the corresponding spaces.
+  EvacuateNewSpaceVisitor new_space_visitor_;
+  EvacuateOldSpaceVisitor old_space_visitor_;
+
+  // Book keeping info.
+  double duration_;
+  intptr_t bytes_compacted_;
+
+  // Task id, if this evacuator is executed on a background task instead of
+  // the main thread. Can be used to try to abort the task currently scheduled
+  // to executed to evacuate pages.
+  uint32_t task_id_;
+};
+
+
+bool MarkCompactCollector::Evacuator::EvacuateSinglePage(
+    MemoryChunk* p, HeapObjectVisitor* visitor) {
+  bool aborted = false;
+  if (p->parallel_compaction_state().TrySetValue(
+          MemoryChunk::kCompactingDone, MemoryChunk::kCompactingInProgress)) {
+    if (p->IsEvacuationCandidate() || p->InNewSpace()) {
+      DCHECK_EQ(p->parallel_compaction_state().Value(),
+                MemoryChunk::kCompactingInProgress);
+      int saved_live_bytes = p->LiveBytes();
+      double evacuation_time;
+      bool success;
+      {
+        AlwaysAllocateScope always_allocate(heap()->isolate());
+        TimedScope timed_scope(&evacuation_time);
+        success = collector_->VisitLiveObjects(p, visitor, kClearMarkbits);

[Hannes Payer (out of office), 2016/01/25 16:04:13]

DCHECK that new space abortion cannot be aborted.

[Michael Lippautz, 2016/01/25 16:26:14]

The caller DCHECKs appropriately that we never abort for newspace pages.

(EvacuateSinglePage currently does not care whether it's a newspace or oldspace
page.)

[Hannes Payer (out of office), 2016/01/25 17:07:23]

Acknowledged.

+      }
+      if (success) {
+        ReportCompactionProgress(evacuation_time, saved_live_bytes);
+        p->parallel_compaction_state().SetValue(
+            MemoryChunk::kCompactingFinalize);
+      } else {
+        p->parallel_compaction_state().SetValue(
+            MemoryChunk::kCompactingAborted);
+        aborted = true;
+      }
+    } else {
+      // There could be popular pages in the list of evacuation candidates

[Hannes Payer (out of office), 2016/01/25 16:04:13]

not?

[Michael Lippautz, 2016/01/25 16:26:15]

Done.

+      // which we do compact.
+      p->parallel_compaction_state().SetValue(MemoryChunk::kCompactingDone);
+    }
+  }
+  return !aborted;

[Hannes Payer (out of office), 2016/01/25 16:04:13]

Just use success.

[Michael Lippautz, 2016/01/25 16:26:15]

Can't do that because in theory we could abort an old space page in between
processing many old space pages. This could happen when the sweeper catches up.
Furthermore we need to go over all pages (cannot break out) and mark them
appropriately to ensure proper finalization later on.

[Hannes Payer (out of office), 2016/01/25 17:07:23]

As discussed offline: it should be possible.

[Michael Lippautz, 2016/01/25 17:10:55]

Done. 

+}
+
+
+void MarkCompactCollector::Evacuator::EvacuatePages() {
+  for (NewSpacePage* p : newspace_evacuation_candidates_) {
+    DCHECK(p->InNewSpace());
+    DCHECK_EQ(static_cast<int>(p->parallel_sweeping_state().Value()),
+              MemoryChunk::kSweepingDone);
+    bool success = EvacuateSinglePage(p, &new_space_visitor_);
+    DCHECK(success);
+    USE(success);
+  }
+  for (Page* p : evacuation_candidates_) {
+    DCHECK(p->IsEvacuationCandidate() ||
+           p->IsFlagSet(MemoryChunk::RESCAN_ON_EVACUATION));
+    DCHECK_EQ(static_cast<int>(p->parallel_sweeping_state().Value()),
+              MemoryChunk::kSweepingDone);
+    EvacuateSinglePage(p, &old_space_visitor_);
+  }
+}
+
+
+void MarkCompactCollector::Evacuator::Finalize() {
+  heap()->old_space()->MergeCompactionSpace(compaction_spaces_.Get(OLD_SPACE));
+  heap()->code_space()->MergeCompactionSpace(
+      compaction_spaces_.Get(CODE_SPACE));
+  heap()->tracer()->AddCompactionEvent(duration_, bytes_compacted_);
+  heap()->IncrementPromotedObjectsSize(new_space_visitor_.promoted_size());
+  heap()->IncrementSemiSpaceCopiedObjectSize(
+      new_space_visitor_.semispace_copied_size());
+  heap()->IncrementYoungSurvivorsCounter(
+      new_space_visitor_.promoted_size() +
+      new_space_visitor_.semispace_copied_size());
+  heap()->MergeAllocationSitePretenuringFeedback(local_pretenuring_feedback_);
+  local_store_buffer_.Process(heap()->store_buffer());
+  collector_->AddEvacuationSlotsBufferSynchronized(local_slots_buffer_);
+}
+
+
+class MarkCompactCollector::CompactionTask : public CancelableTask {
+ public:
+  explicit CompactionTask(Heap* heap, Evacuator* evacuator)
+      : CancelableTask(heap->isolate()), evacuator_(evacuator) {
+    evacuator->set_task_id(id());
+  }
+
+  virtual ~CompactionTask() {}
+
+ private:
+  // v8::internal::CancelableTask overrides.
+  void RunInternal() override {
+    evacuator_->EvacuatePages();
+    isolate()
+        ->heap()

[Hannes Payer (out of office), 2016/01/25 16:04:13]

Let's keep a reference to the heap since we are already passing it in. Then we
do not have to call isolate() and go over the isolate.

[Michael Lippautz, 2016/01/25 16:26:15]

Done.

+        ->mark_compact_collector()
+        ->pending_compaction_tasks_semaphore_.Signal();
+  }
+
+  Evacuator* evacuator_;
+
+  DISALLOW_COPY_AND_ASSIGN(CompactionTask);
+};
+
+
+int MarkCompactCollector::NumberOfParallelCompactionTasks(int pages,
+                                                          intptr_t live_bytes) {
   if (!FLAG_parallel_compaction) return 1;
   // Compute the number of needed tasks based on a target compaction time, the
   // profiled compaction speed and marked live memory.
   //
   // The number of parallel compaction tasks is limited by:
   // - #evacuation pages
   // - (#cores - 1)
-  // - a hard limit
   const double kTargetCompactionTimeInMs = 1;
-  const int kMaxCompactionTasks = 8;
+  const int kNumSweepingTasks = 3;
 
   intptr_t compaction_speed =
       heap()->tracer()->CompactionSpeedInBytesPerMillisecond();
-  if (compaction_speed == 0) return 1;
 
-  intptr_t live_bytes = 0;
-  for (Page* page : evacuation_candidates_) {
-    live_bytes += page->LiveBytes();
+  const int cores =

[Hannes Payer (out of office), 2016/01/25 16:04:13]

call it available_cores

[Michael Lippautz, 2016/01/25 16:26:15]

Done.

+      Max(1, base::SysInfo::NumberOfProcessors() - kNumSweepingTasks - 1);
+  int tasks;
+  if (compaction_speed > 0) {
+    tasks = 1 + static_cast<int>(static_cast<double>(live_bytes) /
+                                 compaction_speed / kTargetCompactionTimeInMs);
+  } else {
+    tasks = pages;
   }
-
-  const int cores = Max(1, base::SysInfo::NumberOfProcessors() - 1);
-  const int tasks =
-      1 + static_cast<int>(static_cast<double>(live_bytes) / compaction_speed /
-                           kTargetCompactionTimeInMs);
-  const int tasks_capped_pages = Min(evacuation_candidates_.length(), tasks);
+  const int tasks_capped_pages = Min(pages, tasks);
   const int tasks_capped_cores = Min(cores, tasks_capped_pages);

[Hannes Payer (out of office), 2016/01/25 16:04:13]

just return Min(cores, tasks_capped_pages);

[Michael Lippautz, 2016/01/25 16:26:14]

Done.

-  const int tasks_capped_hard = Min(kMaxCompactionTasks, tasks_capped_cores);
-  return tasks_capped_hard;
+  return tasks_capped_cores;
 }
 
 
 void MarkCompactCollector::EvacuatePagesInParallel() {
-  const int num_pages = evacuation_candidates_.length();
-  if (num_pages == 0) return;
+  int num_pages = 0;
+  intptr_t live_bytes = 0;
+  for (Page* page : evacuation_candidates_) {
+    num_pages++;
+    live_bytes += page->LiveBytes();
+  }
+  for (NewSpacePage* page : newspace_evacuation_candidates_) {
+    num_pages++;
+    live_bytes += page->LiveBytes();
+  }
+  DCHECK_GE(num_pages, 1);
+
 
   // Used for trace summary.
-  intptr_t live_bytes = 0;
   intptr_t compaction_speed = 0;
   if (FLAG_trace_fragmentation) {
-    for (Page* page : evacuation_candidates_) {
-      live_bytes += page->LiveBytes();
-    }
     compaction_speed = heap()->tracer()->CompactionSpeedInBytesPerMillisecond();
   }
-  const int num_tasks = NumberOfParallelCompactionTasks();
+
+  const int num_tasks = NumberOfParallelCompactionTasks(num_pages, live_bytes);
 
   // Set up compaction spaces.
+  Evacuator** evacuators = new Evacuator*[num_tasks];
   CompactionSpaceCollection** compaction_spaces_for_tasks =
       new CompactionSpaceCollection*[num_tasks];
   for (int i = 0; i < num_tasks; i++) {
-    compaction_spaces_for_tasks[i] = new CompactionSpaceCollection(heap());
+    evacuators[i] = new Evacuator(this, evacuation_candidates_,
+                                  newspace_evacuation_candidates_);
+    compaction_spaces_for_tasks[i] = evacuators[i]->compaction_spaces();
   }
-
   heap()->old_space()->DivideUponCompactionSpaces(compaction_spaces_for_tasks,
                                                   num_tasks);
   heap()->code_space()->DivideUponCompactionSpaces(compaction_spaces_for_tasks,
                                                    num_tasks);
+  delete[] compaction_spaces_for_tasks;
 
-  uint32_t* task_ids = new uint32_t[num_tasks - 1];
   // Kick off parallel tasks.
-  StartParallelCompaction(compaction_spaces_for_tasks, task_ids, num_tasks);
+  StartParallelCompaction(evacuators, num_tasks);
   // Wait for unfinished and not-yet-started tasks.
-  WaitUntilCompactionCompleted(task_ids, num_tasks - 1);
-  delete[] task_ids;
+  WaitUntilCompactionCompleted(&evacuators[1], num_tasks - 1);
 
-  double compaction_duration = 0.0;
-  intptr_t compacted_memory = 0;
-  // Merge back memory (compacted and unused) from compaction spaces.
+  // Finalize local evacuators by merging back all locally cached data.
   for (int i = 0; i < num_tasks; i++) {
-    heap()->old_space()->MergeCompactionSpace(
-        compaction_spaces_for_tasks[i]->Get(OLD_SPACE));
-    heap()->code_space()->MergeCompactionSpace(
-        compaction_spaces_for_tasks[i]->Get(CODE_SPACE));
-    compacted_memory += compaction_spaces_for_tasks[i]->bytes_compacted();
-    compaction_duration += compaction_spaces_for_tasks[i]->duration();
-    delete compaction_spaces_for_tasks[i];
+    evacuators[i]->Finalize();
+    delete evacuators[i];
   }
-  delete[] compaction_spaces_for_tasks;
-  heap()->tracer()->AddCompactionEvent(compaction_duration, compacted_memory);
+  delete[] evacuators;
 
-  // Finalize sequentially.
+  // Finalize pages sequentially.
+  for (NewSpacePage* p : newspace_evacuation_candidates_) {
+    DCHECK_EQ(p->parallel_compaction_state().Value(),
+              MemoryChunk::kCompactingFinalize);
+    p->parallel_compaction_state().SetValue(MemoryChunk::kCompactingDone);
+  }
+
   int abandoned_pages = 0;
-  for (int i = 0; i < num_pages; i++) {
-    Page* p = evacuation_candidates_[i];
+  for (Page* p : evacuation_candidates_) {
     switch (p->parallel_compaction_state().Value()) {
       case MemoryChunk::ParallelCompactingState::kCompactingAborted:
         // We have partially compacted the page, i.e., some objects may have
         // moved, others are still in place.
         // We need to:
         // - Leave the evacuation candidate flag for later processing of
         //   slots buffer entries.
         // - Leave the slots buffer there for processing of entries added by
         //   the write barrier.
         // - Rescan the page as slot recording in the migration buffer only
@@ skipping 12 matching lines @@
       case MemoryChunk::kCompactingFinalize:
         DCHECK(p->IsEvacuationCandidate());
         p->SetWasSwept();
         p->Unlink();
         break;
       case MemoryChunk::kCompactingDone:
         DCHECK(p->IsFlagSet(Page::POPULAR_PAGE));
         DCHECK(p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
         break;
       default:
-        // We should not observe kCompactingInProgress, or kCompactingDone.
+        // MemoryChunk::kCompactingInProgress.
         UNREACHABLE();
     }
     p->parallel_compaction_state().SetValue(MemoryChunk::kCompactingDone);
   }
   if (FLAG_trace_fragmentation) {
     PrintIsolate(isolate(),
                  "%8.0f ms: compaction: parallel=%d pages=%d aborted=%d "
                  "tasks=%d cores=%d live_bytes=%" V8_PTR_PREFIX
                  "d compaction_speed=%" V8_PTR_PREFIX "d\n",
                  isolate()->time_millis_since_init(), FLAG_parallel_compaction,
                  num_pages, abandoned_pages, num_tasks,
                  base::SysInfo::NumberOfProcessors(), live_bytes,
                  compaction_speed);
   }
 }
 
 
-void MarkCompactCollector::StartParallelCompaction(
-    CompactionSpaceCollection** compaction_spaces, uint32_t* task_ids,
-    int len) {
+void MarkCompactCollector::StartParallelCompaction(Evacuator** evacuators,
+                                                   int len) {
   compaction_in_progress_ = true;
   for (int i = 1; i < len; i++) {
-    CompactionTask* task = new CompactionTask(heap(), compaction_spaces[i]);
-    task_ids[i - 1] = task->id();
+    CompactionTask* task = new CompactionTask(heap(), evacuators[i]);
     V8::GetCurrentPlatform()->CallOnBackgroundThread(
         task, v8::Platform::kShortRunningTask);
   }
 
-  // Contribute in main thread.
-  EvacuatePages(compaction_spaces[0], &migration_slots_buffer_);
+  // Contribute on main thread.
+  evacuators[0]->EvacuatePages();
 }
 
 
-void MarkCompactCollector::WaitUntilCompactionCompleted(uint32_t* task_ids,
+void MarkCompactCollector::WaitUntilCompactionCompleted(Evacuator** evacuators,
                                                         int len) {
   // Try to cancel compaction tasks that have not been run (as they might be
   // stuck in a worker queue). Tasks that cannot be canceled, have either
   // already completed or are still running, hence we need to wait for their
   // semaphore signal.
   for (int i = 0; i < len; i++) {
-    if (!heap()->isolate()->cancelable_task_manager()->TryAbort(task_ids[i])) {
+    if (!heap()->isolate()->cancelable_task_manager()->TryAbort(
+            evacuators[i]->task_id())) {
       pending_compaction_tasks_semaphore_.Wait();
     }
   }
   compaction_in_progress_ = false;
 }
 
 
-void MarkCompactCollector::EvacuatePages(
-    CompactionSpaceCollection* compaction_spaces,
-    SlotsBuffer** evacuation_slots_buffer) {
-  EvacuateOldSpaceVisitor visitor(heap(), compaction_spaces,
-                                  evacuation_slots_buffer);
-  for (int i = 0; i < evacuation_candidates_.length(); i++) {
-    Page* p = evacuation_candidates_[i];
-    DCHECK(p->IsEvacuationCandidate() ||
-           p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
-    DCHECK(static_cast<int>(p->parallel_sweeping_state().Value()) ==
-           MemoryChunk::kSweepingDone);
-    if (p->parallel_compaction_state().TrySetValue(
-            MemoryChunk::kCompactingDone, MemoryChunk::kCompactingInProgress)) {
-      if (p->IsEvacuationCandidate()) {
-        DCHECK_EQ(p->parallel_compaction_state().Value(),
-                  MemoryChunk::kCompactingInProgress);
-        double start = heap()->MonotonicallyIncreasingTimeInMs();
-        intptr_t live_bytes = p->LiveBytes();
-        AlwaysAllocateScope always_allocate(isolate());
-        if (VisitLiveObjects(p, &visitor, kClearMarkbits)) {
-          p->parallel_compaction_state().SetValue(
-              MemoryChunk::kCompactingFinalize);
-          compaction_spaces->ReportCompactionProgress(
-              heap()->MonotonicallyIncreasingTimeInMs() - start, live_bytes);
-        } else {
-          p->parallel_compaction_state().SetValue(
-              MemoryChunk::kCompactingAborted);
-        }
-      } else {
-        // There could be popular pages in the list of evacuation candidates
-        // which we do compact.
-        p->parallel_compaction_state().SetValue(MemoryChunk::kCompactingDone);
-      }
-    }
-  }
-}
-
-
 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();
       }
     }
@@ skipping 129 matching lines @@
 // Return true if the given code is deoptimized or will be deoptimized.
 bool MarkCompactCollector::WillBeDeoptimized(Code* code) {
   return code->is_optimized_code() && code->marked_for_deoptimization();
 }
 
 
 void MarkCompactCollector::RemoveObjectSlots(Address start_slot,
                                              Address end_slot) {
   // Remove entries by replacing them with an old-space slot containing a smi
   // that is located in an unmovable page.
-  int npages = evacuation_candidates_.length();
-  for (int i = 0; i < npages; i++) {
-    Page* p = evacuation_candidates_[i];
+  for (Page* p : evacuation_candidates_) {
     DCHECK(p->IsEvacuationCandidate() ||
            p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
     if (p->IsEvacuationCandidate()) {
       SlotsBuffer::RemoveObjectSlots(heap_, p->slots_buffer(), start_slot,
                                      end_slot);
     }
   }
 }
 
 
@@ skipping 59 matching lines @@
     DCHECK(Marking::IsBlack(Marking::MarkBitFrom(object)));
     Map* map = object->synchronized_map();
     int size = object->SizeFromMap(map);
     object->IterateBody(map->instance_type(), size, visitor);
   }
 }
 
 
 void MarkCompactCollector::SweepAbortedPages() {
   // Second pass on aborted pages.
-  for (int i = 0; i < evacuation_candidates_.length(); i++) {
-    Page* p = evacuation_candidates_[i];
+  for (Page* p : evacuation_candidates_) {
     if (p->IsFlagSet(Page::COMPACTION_WAS_ABORTED)) {
       p->ClearFlag(MemoryChunk::COMPACTION_WAS_ABORTED);
       PagedSpace* space = static_cast<PagedSpace*>(p->owner());
       switch (space->identity()) {
         case OLD_SPACE:
           Sweep<SWEEP_ONLY, SWEEP_ON_MAIN_THREAD, IGNORE_SKIP_LIST,
                 IGNORE_FREE_SPACE>(space, nullptr, p, nullptr);
           break;
         case CODE_SPACE:
           if (FLAG_zap_code_space) {
@@ skipping 10 matching lines @@
       }
     }
   }
 }
 
 
 void MarkCompactCollector::EvacuateNewSpaceAndCandidates() {
   GCTracer::Scope gc_scope(heap()->tracer(), GCTracer::Scope::MC_EVACUATE);
   Heap::RelocationLock relocation_lock(heap());
 
-  HashMap* local_pretenuring_feedback = nullptr;
   {
     GCTracer::Scope gc_scope(heap()->tracer(),
                              GCTracer::Scope::MC_EVACUATE_NEW_SPACE);
     EvacuationScope evacuation_scope(this);
+
     EvacuateNewSpacePrologue();
-    local_pretenuring_feedback = EvacuateNewSpaceInParallel();
-    heap_->new_space()->set_age_mark(heap_->new_space()->top());
-  }
-
-  {
-    GCTracer::Scope gc_scope(heap()->tracer(),
-                             GCTracer::Scope::MC_EVACUATE_CANDIDATES);
-    EvacuationScope evacuation_scope(this);
     EvacuatePagesInParallel();
-  }
-
-  {
-    heap_->MergeAllocationSitePretenuringFeedback(*local_pretenuring_feedback);
-    delete local_pretenuring_feedback;
+    EvacuateNewSpaceEpilogue();
+    heap()->new_space()->set_age_mark(heap()->new_space()->top());
   }
 
   UpdatePointersAfterEvacuation();
 
   {
     GCTracer::Scope gc_scope(heap()->tracer(),
                              GCTracer::Scope::MC_EVACUATE_CLEAN_UP);
     // After updating all pointers, we can finally sweep the aborted pages,
     // effectively overriding any forward pointers.
     SweepAbortedPages();
@@ skipping 56 matching lines @@
                           &updating_visitor);
     }
     // Update roots.
     heap_->IterateRoots(&updating_visitor, VISIT_ALL_IN_SWEEP_NEWSPACE);
 
     StoreBufferRebuildScope scope(heap_, heap_->store_buffer(),
                                   &Heap::ScavengeStoreBufferCallback);
     heap_->store_buffer()->IteratePointersToNewSpace(&UpdatePointer);
   }
 
-  int npages = evacuation_candidates_.length();
   {
     GCTracer::Scope gc_scope(
         heap()->tracer(),
         GCTracer::Scope::MC_EVACUATE_UPDATE_POINTERS_BETWEEN_EVACUATED);
-    for (int i = 0; i < npages; i++) {
-      Page* p = evacuation_candidates_[i];
+    for (Page* p : evacuation_candidates_) {
       DCHECK(p->IsEvacuationCandidate() ||
              p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
 
       if (p->IsEvacuationCandidate()) {
         UpdateSlotsRecordedIn(p->slots_buffer());
         if (FLAG_trace_fragmentation_verbose) {
           PrintF("  page %p slots buffer: %d\n", reinterpret_cast<void*>(p),
                  SlotsBuffer::SizeOfChain(p->slots_buffer()));
         }
         slots_buffer_allocator_->DeallocateChain(p->slots_buffer_address());
@@ skipping 53 matching lines @@
     heap_->UpdateReferencesInExternalStringTable(
         &UpdateReferenceInExternalStringTableEntry);
 
     EvacuationWeakObjectRetainer evacuation_object_retainer;
     heap()->ProcessAllWeakReferences(&evacuation_object_retainer);
   }
 }
 
 
 void MarkCompactCollector::ReleaseEvacuationCandidates() {
-  int npages = evacuation_candidates_.length();
-  for (int i = 0; i < npages; i++) {
-    Page* p = evacuation_candidates_[i];
+  for (Page* p : evacuation_candidates_) {
     if (!p->IsEvacuationCandidate()) continue;
     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
     space->Free(p->area_start(), p->area_size());
     p->set_scan_on_scavenge(false);
     p->ResetLiveBytes();
     CHECK(p->WasSwept());
     space->ReleasePage(p);
   }
   evacuation_candidates_.Rewind(0);
   compacting_ = false;
@@ skipping 255 matching lines @@
     MarkBit mark_bit = Marking::MarkBitFrom(host);
     if (Marking::IsBlack(mark_bit)) {
       RelocInfo rinfo(isolate(), pc, RelocInfo::CODE_TARGET, 0, host);
       RecordRelocSlot(&rinfo, target);
     }
   }
 }
 
 }  // namespace internal
 }  // namespace v8