[not for landing, heap] Parallel compaction in main GC pause

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/code-stubs.h"
 #include "src/compilation-cache.h"
 #include "src/cpu-profiler.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.h"
 #include "src/heap/spaces-inl.h"
 #include "src/heap-profiler.h"
 #include "src/ic/ic.h"
 #include "src/ic/stub-cache.h"
 #include "src/v8.h"
 
 namespace v8 {
 namespace internal {
 
 
@@ skipping 16 matching lines @@
 #ifdef DEBUG
       state_(IDLE),
 #endif
       marking_parity_(ODD_MARKING_PARITY),
       compacting_(false),
       was_marked_incrementally_(false),
       sweeping_in_progress_(false),
       parallel_compaction_in_progress_(false),
       pending_sweeper_jobs_semaphore_(0),
       pending_compaction_jobs_semaphore_(0),
+      concurrent_compaction_tasks_active_(0),
       evacuation_(false),
       slots_buffer_allocator_(nullptr),
       migration_slots_buffer_(nullptr),
       heap_(heap),
       marking_deque_memory_(NULL),
       marking_deque_memory_committed_(0),
       code_flusher_(NULL),
       have_code_to_deoptimize_(false) {
 }
 
@@ skipping 396 matching lines @@
   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 v8::Task {
  public:
-  explicit CompactionTask(Heap* heap) : heap_(heap) {}
+  explicit CompactionTask(Heap* heap, CompactionSpaces* compaction_spaces)
+      : heap_(heap), compaction_spaces_(compaction_spaces) {}
 
   virtual ~CompactionTask() {}
 
  private:
   // v8::Task overrides.
   void Run() override {
-    // TODO(mlippautz, hpayer): EvacuatePages is not thread-safe and can just be
-    // called by one thread concurrently.
-    heap_->mark_compact_collector()->EvacuatePages();
+    heap_->mark_compact_collector()->EvacuatePagesUsingCompactionSpace(
+        compaction_spaces_);
     heap_->mark_compact_collector()
         ->pending_compaction_jobs_semaphore_.Signal();
   }
 
   Heap* heap_;
+  CompactionSpaces* compaction_spaces_;
 
   DISALLOW_COPY_AND_ASSIGN(CompactionTask);
 };
 
 
 class MarkCompactCollector::SweeperTask : public v8::Task {
  public:
   SweeperTask(Heap* heap, PagedSpace* space) : heap_(heap), space_(space) {}
 
   virtual ~SweeperTask() {}
@@ skipping 2814 matching lines @@
   while (it.has_next()) {
     NewSpacePage* p = it.next();
     survivors_size += DiscoverAndEvacuateBlackObjectsOnPage(new_space, p);
   }
 
   heap_->IncrementYoungSurvivorsCounter(survivors_size);
   new_space->set_age_mark(new_space->top());
 }
 
 
+bool MarkCompactCollector::EvacuateLiveObjectsFromPageWithoutEmergency(
+    Page* p, PagedSpace* target_space) {
+  AlwaysAllocateScope always_allocate(isolate());
+  DCHECK(p->IsEvacuationCandidate() && !p->WasSwept());
+  p->SetWasSwept();
+
+  int offsets[16];
+
+  for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
+    Address cell_base = it.CurrentCellBase();
+    MarkBit::CellType* cell = it.CurrentCell();
+
+    if (*cell == 0) continue;
+
+    int live_objects = MarkWordToObjectStarts(*cell, offsets);
+    for (int i = 0; i < live_objects; i++) {
+      Address object_addr = cell_base + offsets[i] * kPointerSize;
+      HeapObject* object = HeapObject::FromAddress(object_addr);
+      DCHECK(Marking::IsBlack(Marking::MarkBitFrom(object)));
+
+      int size = object->Size();
+      AllocationAlignment alignment = object->RequiredAlignment();
+      HeapObject* target_object = nullptr;
+      AllocationResult allocation = target_space->AllocateRaw(size, alignment);
+      if (!allocation.To(&target_object)) {
+        return false;
+      }
+      MigrateObject(target_object, object, size, target_space->identity());
+      DCHECK(object->map_word().IsForwardingAddress());
+    }
+
+    // Clear marking bits for current cell.
+    *cell = 0;
+  }
+  p->ResetLiveBytes();
+  return true;
+}
+
+
 void MarkCompactCollector::EvacuateLiveObjectsFromPage(
     Page* p, PagedSpace* target_space) {
   AlwaysAllocateScope always_allocate(isolate());
   DCHECK(p->IsEvacuationCandidate() && !p->WasSwept());
   p->SetWasSwept();
 
   int offsets[16];
 
   for (MarkBitCellIterator it(p); !it.Done(); it.Advance()) {
     Address cell_base = it.CurrentCellBase();
@@ skipping 28 matching lines @@
     }
 
     // Clear marking bits for current cell.
     *cell = 0;
   }
   p->ResetLiveBytes();
 }
 
 
 void MarkCompactCollector::EvacuatePagesInParallel() {
+  // As soon as we have at least 7 pages to evacuate we kick off another task.
+  // We keep a maximum of 2 tasks (including main thread) though.
+  const int num_tasks = Min(1 + evacuation_candidates_.length() / 7, 2);
+  if (num_tasks == 1) {
+    // Use single-threaded version for now.
+    EvacuatePages();
+    return;
+  }
+
+  // Set up compaction spaces.
+  CompactionSpaces** compaction_spaces_for_tasks =
+      new CompactionSpaces*[num_tasks];
+  FreeList** free_lists = new FreeList*[2 * num_tasks];
+  for (int i = 0; i < num_tasks; i++) {
+    compaction_spaces_for_tasks[i] = new CompactionSpaces(heap());
+    free_lists[i] = compaction_spaces_for_tasks[i]->Get(OLD_SPACE)->free_list();
+    free_lists[i + num_tasks] =
+        compaction_spaces_for_tasks[i]->Get(CODE_SPACE)->free_list();
+  }
+  // Move over space to compaction spaces. If enough memory is available or we
+  // want to preserve allocation order, this step can be omitted.
+  heap()->old_space()->free_list()->Divide(free_lists, num_tasks);
+  heap()->code_space()->free_list()->Divide(&free_lists[num_tasks], num_tasks);
+  delete[] free_lists;
+
   parallel_compaction_in_progress_ = true;
-  V8::GetCurrentPlatform()->CallOnBackgroundThread(
-      new CompactionTask(heap()), v8::Platform::kShortRunningTask);
+  // Kick off parallel tasks.
+  for (int i = 1; i < num_tasks; i++) {
+    concurrent_compaction_tasks_active_++;
+    V8::GetCurrentPlatform()->CallOnBackgroundThread(
+        new CompactionTask(heap(), compaction_spaces_for_tasks[i]),
+        v8::Platform::kShortRunningTask);
+  }
+
+  // Contribute in main thread. Counter and signal are in principal not needed.
+  concurrent_compaction_tasks_active_++;
+  EvacuatePagesUsingCompactionSpace(compaction_spaces_for_tasks[0]);
+  pending_compaction_jobs_semaphore_.Signal();
+
+  // Wait together.
+  WaitUntilCompactionCompleted();
+  parallel_compaction_in_progress_ = false;
+
+  // Merge back the compacted memory.
+  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));
+    delete compaction_spaces_for_tasks[i];
+  }
+  delete[] compaction_spaces_for_tasks;
+
+  // Finalize sequentially.
+  const int num_pages = evacuation_candidates_.length();
+  int abandoned_pages = 0;
+  for (int i = 0; i < num_pages; i++) {
+    Page* p = evacuation_candidates_[i];
+    switch (p->parallel_compaction_state().Value()) {
+      case MemoryChunk::ParallelCompactingState::kCompactingAborted:
+        slots_buffer_allocator_->DeallocateChain(p->slots_buffer_address());
+        p->ClearEvacuationCandidate();
+        p->SetFlag(Page::RESCAN_ON_EVACUATION);
+        abandoned_pages++;
+        break;
+      case MemoryChunk::kCompactingFinalize:
+        p->SetWasSwept();
+        p->Unlink();
+        break;
+      case MemoryChunk::kNoEvacuationCandidate:
+        break;
+      default:
+        // We should not observe kCompactingInProgress, or kCompactingDone.
+        UNREACHABLE();
+    }
+    p->parallel_compaction_state().SetValue(MemoryChunk::kCompactingDone);
+  }
+  if (num_pages > 0) {
+    if (FLAG_trace_fragmentation) {
+      if (abandoned_pages != 0) {
+        PrintF(
+            "  Abandon %d out of %d page compactions due to lack of memory\n",
+            abandoned_pages, num_pages);
+      } else {
+        PrintF("  Compacted %d pages\n", num_pages);
+      }
+    }
+  }
 }
 
 
 void MarkCompactCollector::WaitUntilCompactionCompleted() {
-  pending_compaction_jobs_semaphore_.Wait();
-  parallel_compaction_in_progress_ = false;
+  while (concurrent_compaction_tasks_active_ > 0) {
+    pending_compaction_jobs_semaphore_.Wait();
+    concurrent_compaction_tasks_active_--;
+  }
 }
 
 
+void MarkCompactCollector::EvacuatePagesUsingCompactionSpace(
+    CompactionSpaces* compaction_spaces) {
+  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()) ==
+           MemoryChunk::SWEEPING_DONE);
+
+    if (!p->parallel_compaction_state().TrySetValue(
+            MemoryChunk::kCompactingDone, MemoryChunk::kCompactingInProgress)) {
+      continue;
+    }
+
+    // In principal reading IsEvacuationCandidate() should be fine, however,
+    // we avoid reading the state when we don't have exclusive access.
+    if (p->IsEvacuationCandidate()) {
+      DCHECK_EQ(p->parallel_compaction_state().Value(),
+                MemoryChunk::kCompactingInProgress);
+      if (EvacuateLiveObjectsFromPageWithoutEmergency(
+              p, compaction_spaces->Get(p->owner()->identity()))) {
+        p->parallel_compaction_state().SetValue(
+            MemoryChunk::kCompactingFinalize);
+      } else {
+        p->parallel_compaction_state().SetValue(
+            MemoryChunk::kCompactingAborted);
+      }
+    } else {
+      p->parallel_compaction_state().SetValue(
+          MemoryChunk::kNoEvacuationCandidate);
+    }
+  }
+}
+
+
 void MarkCompactCollector::EvacuatePages() {
   int npages = evacuation_candidates_.length();
   int abandoned_pages = 0;
   for (int i = 0; i < npages; i++) {
     Page* p = evacuation_candidates_[i];
     DCHECK(p->IsEvacuationCandidate() ||
            p->IsFlagSet(Page::RESCAN_ON_EVACUATION));
     DCHECK(static_cast<int>(p->parallel_sweeping()) ==
            MemoryChunk::SWEEPING_DONE);
     PagedSpace* space = static_cast<PagedSpace*>(p->owner());
@@ skipping 228 matching lines @@
     EvacuationScope evacuation_scope(this);
     EvacuateNewSpace();
   }
 
   {
     GCTracer::Scope gc_scope(heap()->tracer(),
                              GCTracer::Scope::MC_EVACUATE_PAGES);
     EvacuationScope evacuation_scope(this);
     if (FLAG_parallel_compaction) {
       EvacuatePagesInParallel();
-      WaitUntilCompactionCompleted();
     } else {
       EvacuatePages();
     }
   }
 
   // Second pass: find pointers to new space and update them.
   PointersUpdatingVisitor updating_visitor(heap());
 
   {
     GCTracer::Scope gc_scope(heap()->tracer(),
@@ skipping 871 matching lines @@
     MarkBit mark_bit = Marking::MarkBitFrom(host);
     if (Marking::IsBlack(mark_bit)) {
       RelocInfo rinfo(pc, RelocInfo::CODE_TARGET, 0, host);
       RecordRelocSlot(&rinfo, target);
     }
   }
 }
 
 }  // namespace internal
 }  // namespace v8