[heap] Implement simple concurrent marking deque.

src/heap/concurrent-marking.cc

Index: src/heap/concurrent-marking.cc
diff --git a/src/heap/concurrent-marking.cc b/src/heap/concurrent-marking.cc
index 2a3377da3e3f703818ded8368720c485a14a3903..618cb1139b1b7db55090c85f77b83aaba779c9d9 100644
--- a/src/heap/concurrent-marking.cc
+++ b/src/heap/concurrent-marking.cc
@@ -7,6 +7,7 @@
 #include <stack>
 #include <unordered_map>
 
+#include "src/heap/concurrent-marking-deque.h"
 #include "src/heap/heap-inl.h"
 #include "src/heap/heap.h"
 #include "src/heap/marking.h"
@@ -21,43 +22,13 @@
 namespace v8 {
 namespace internal {
 
-class ConcurrentMarkingMarkbits {
- public:
-  ConcurrentMarkingMarkbits() {}
-  ~ConcurrentMarkingMarkbits() {
-    for (auto chunk_bitmap : bitmap_) {
-      FreeBitmap(chunk_bitmap.second);
-    }
-  }
-  bool Mark(HeapObject* obj) {
-    Address address = obj->address();
-    MemoryChunk* chunk = MemoryChunk::FromAddress(address);
-    if (bitmap_.count(chunk) == 0) {
-      bitmap_[chunk] = AllocateBitmap();
-    }
-    MarkBit mark_bit =
-        bitmap_[chunk]->MarkBitFromIndex(chunk->AddressToMarkbitIndex(address));
-    if (mark_bit.Get()) return false;
-    mark_bit.Set();
-    return true;
-  }
-
-  Bitmap* AllocateBitmap() {
-    return static_cast<Bitmap*>(calloc(1, Bitmap::kSize));
-  }
-
-  void FreeBitmap(Bitmap* bitmap) { free(bitmap); }
-
- private:
-  std::unordered_map<MemoryChunk*, Bitmap*> bitmap_;
-};
-
 class ConcurrentMarkingVisitor final
     : public HeapVisitor<int, ConcurrentMarkingVisitor> {
  public:
   using BaseClass = HeapVisitor<int, ConcurrentMarkingVisitor>;
 
-  ConcurrentMarkingVisitor() : bytes_marked_(0) {}
+  explicit ConcurrentMarkingVisitor(ConcurrentMarkingDeque* deque)
+      : deque_(deque) {}
 
   void VisitPointers(HeapObject* host, Object** start, Object** end) override {
     for (Object** p = start; p < end; p++) {
@@ -154,84 +125,71 @@ class ConcurrentMarkingVisitor final
   }
 
   void MarkObject(HeapObject* obj) {
-    if (markbits_.Mark(obj)) {
-      marking_stack_.push(obj);
-    }
-  }
-
-  void MarkTransitively() {
-    while (!marking_stack_.empty()) {
-      HeapObject* obj = marking_stack_.top();
-      marking_stack_.pop();
-      bytes_marked_ += IterateBody(obj);
-    }
+    deque_->Push(obj, MarkingThread::kConcurrent, TargetDeque::kShared);
   }
 
-  size_t bytes_marked() { return bytes_marked_; }
-
  private:
-  size_t bytes_marked_;
-  std::stack<HeapObject*> marking_stack_;
-  ConcurrentMarkingMarkbits markbits_;
+  ConcurrentMarkingDeque* deque_;
 };
 
 class ConcurrentMarking::Task : public CancelableTask {
  public:
-  Task(Heap* heap, std::vector<HeapObject*>* root_set,
+  Task(Isolate* isolate, ConcurrentMarking* concurrent_marking,
        base::Semaphore* on_finish)
-      : CancelableTask(heap->isolate()),
-        heap_(heap),
-        on_finish_(on_finish),
-        root_set_(root_set) {}
+      : CancelableTask(isolate),
+        concurrent_marking_(concurrent_marking),
+        on_finish_(on_finish) {}
 
   virtual ~Task() {}
 
  private:
   // v8::internal::CancelableTask overrides.
   void RunInternal() override {
-    double time_ms = heap_->MonotonicallyIncreasingTimeInMs();
-    {
-      TimedScope scope(&time_ms);
-      for (HeapObject* obj : *root_set_) {
-        marking_visitor_.MarkObject(obj);
-      }
-      marking_visitor_.MarkTransitively();
-    }
-    if (FLAG_trace_concurrent_marking) {
-      heap_->isolate()->PrintWithTimestamp(
-          "concurrently marked %dKB in %.2fms\n",
-          static_cast<int>(marking_visitor_.bytes_marked() / KB), time_ms);
-    }
+    concurrent_marking_->Run();
     on_finish_->Signal();
   }
 
-  Heap* heap_;
+  ConcurrentMarking* concurrent_marking_;
   base::Semaphore* on_finish_;
-  ConcurrentMarkingVisitor marking_visitor_;
-  std::vector<HeapObject*>* root_set_;
   DISALLOW_COPY_AND_ASSIGN(Task);
 };
 
-ConcurrentMarking::ConcurrentMarking(Heap* heap)
-    : heap_(heap), pending_task_semaphore_(0), is_task_pending_(false) {
+ConcurrentMarking::ConcurrentMarking(Heap* heap, ConcurrentMarkingDeque* deque)
+    : heap_(heap),
+      pending_task_semaphore_(0),
+      deque_(deque),
+      visitor_(new ConcurrentMarkingVisitor(deque_)),
+      is_task_pending_(false) {
   // Concurrent marking does not work with double unboxing.
   STATIC_ASSERT(!(V8_CONCURRENT_MARKING && V8_DOUBLE_FIELDS_UNBOXING));
   // The runtime flag should be set only if the compile time flag was set.
   CHECK(!FLAG_concurrent_marking || V8_CONCURRENT_MARKING);
 }
 
-ConcurrentMarking::~ConcurrentMarking() {}
+ConcurrentMarking::~ConcurrentMarking() { delete visitor_; }
 
-void ConcurrentMarking::AddRoot(HeapObject* object) {
-  root_set_.push_back(object);
+void ConcurrentMarking::Run() {
+  double time_ms = heap_->MonotonicallyIncreasingTimeInMs();
+  size_t bytes_marked = 0;
+  {
+    TimedScope scope(&time_ms);
+    HeapObject* object;
+    while ((object = deque_->Pop(MarkingThread::kConcurrent)) != nullptr) {
+      bytes_marked += visitor_->IterateBody(object);
+    }
+  }
+  if (FLAG_trace_concurrent_marking) {
+    heap_->isolate()->PrintWithTimestamp("concurrently marked %dKB in %.2fms\n",
+                                         static_cast<int>(bytes_marked / KB),
+                                         time_ms);
+  }
 }
 
 void ConcurrentMarking::StartTask() {
   if (!FLAG_concurrent_marking) return;
   is_task_pending_ = true;
-
   V8::GetCurrentPlatform()->CallOnBackgroundThread(
-      new Task(heap_, &root_set_, &pending_task_semaphore_),
+      new Task(heap_->isolate(), this, &pending_task_semaphore_),
       v8::Platform::kShortRunningTask);
 }
 
@@ -239,7 +197,6 @@ void ConcurrentMarking::WaitForTaskToComplete() {
   if (!FLAG_concurrent_marking) return;
   pending_task_semaphore_.Wait();
   is_task_pending_ = false;
-  root_set_.clear();
 }
 
 void ConcurrentMarking::EnsureTaskCompleted() {