Parallel marking.

runtime/vm/gc_marker.cc

Index: runtime/vm/gc_marker.cc
diff --git a/runtime/vm/gc_marker.cc b/runtime/vm/gc_marker.cc
index 0df41177730edde525bf83f910d73ef19df78ccd..fe0a30da4764fb4176e5df573489d9c8745fc77c 100644
--- a/runtime/vm/gc_marker.cc
+++ b/runtime/vm/gc_marker.cc
@@ -23,9 +23,11 @@
 
 namespace dart {
 
-DEFINE_FLAG(int, marker_tasks, 1,
+DEFINE_FLAG(int, marker_tasks, 2,
             "The number of tasks to spawn during old gen GC marking (0 means "
             "perform all marking on main thread).");
+DEFINE_FLAG(bool, log_marker_tasks, false,
+            "Log debugging information for old gen GC marking tasks.");
 
 class DelaySet {
  private:
@@ -36,24 +38,30 @@ class DelaySet {
   DelaySet() : mutex_(new Mutex()) {}
   ~DelaySet() { delete mutex_; }
 
-  // Returns 'true' if this inserted a new key (not just added a value).
-  bool Insert(RawWeakProperty* raw_weak) {
+  // Atomically inserts raw_weak if its key is white, so that any future call to
+  // VisitValuesForKey is guaranteed to include its value. Returns true on
+  // success, and false if the key is not white.

[Ivan Posva, 2015/10/08 19:56:12]

Please also note the precondition that this thread did successfully add the
watched bit atomically, which means the mark bit cannot be set without observing
the watched bit. This information is crucial to understanding how this algorithm
works.

[koda, 2015/10/08 21:32:08]

Done.

+  bool InsertIfWhite(RawWeakProperty* raw_weak) {
     MutexLocker ml(mutex_);
     RawObject* raw_key = raw_weak->ptr()->key_;
-    bool new_key = (delay_set_.find(raw_key) == delay_set_.end());
+    if (raw_key->IsMarked()) return false;
+    // The key was white *after* acquiring the lock. Thus any future call to
+    // VisitValuesForKey is guaranteed to include the entry inserted below.
     delay_set_.insert(std::make_pair(raw_key, raw_weak));
-    return new_key;
+    return true;
   }
 
   void ClearReferences() {
     MutexLocker ml(mutex_);
     for (Map::iterator it = delay_set_.begin(); it != delay_set_.end(); ++it) {
+      ASSERT(!it->first->IsMarked());
       WeakProperty::Clear(it->second);
     }
   }
 
-  // Visit all values with a key equal to raw_obj.
+  // Visit all values with a key equal to raw_obj, which must already be marked.
   void VisitValuesForKey(RawObject* raw_obj, ObjectPointerVisitor* visitor) {
+    ASSERT(raw_obj->IsMarked());
     // Extract the range into a temporary vector to iterate over it
     // while delay_set_ may be modified.
     std::vector<MapEntry> temp_copy;
@@ -140,9 +148,67 @@ class SkippedCodeFunctions : public ZoneAllocated {
 };
 
 
-class MarkingVisitor : public ObjectPointerVisitor {
+class WorkList : public ValueObject {

[Ivan Posva, 2015/10/08 19:56:12]

Thanks!

Maybe rename to MarkerWorkList?

[koda, 2015/10/08 21:32:07]

Done.

  public:
-  MarkingVisitor(Isolate* isolate,
+  explicit WorkList(MarkingStack* marking_stack)
+      : marking_stack_(marking_stack) {
+    work_ = marking_stack_->PopEmptyBlock();
+  }
+
+  ~WorkList() {
+    ASSERT(work_ == NULL);
+    ASSERT(marking_stack_ == NULL);
+  }
+
+  // Returns NULL if no more work was found.
+  RawObject* Pop() {
+    ASSERT(work_ != NULL);
+    if (work_->IsEmpty()) {
+      // TODO(koda): Track over/underflow events and use in heuristics to
+      // distribute work and prevent degenerate flip-flopping.
+      MarkingStack::Block* new_work = marking_stack_->PopNonEmptyBlock();
+      if (new_work == NULL) {
+        return NULL;
+      }
+      marking_stack_->PushBlock(work_);
+      work_ = new_work;
+    }
+    return work_->Pop();
+  }
+
+  void Push(RawObject* raw_obj) {
+    if (work_->IsFull()) {
+      // TODO(koda): Track over/underflow events and use in heuristics to
+      // distribute work and prevent degenerate flip-flopping.
+      marking_stack_->PushBlock(work_);
+      work_ = marking_stack_->PopEmptyBlock();
+    }
+    work_->Push(raw_obj);
+  }
+
+  void AbandonWork() {
+    marking_stack_->PushBlock(work_);
+    work_ = marking_stack_->PopEmptyBlock();
+  }
+
+  void Finalize() {
+    ASSERT(work_->IsEmpty());
+    marking_stack_->PushBlock(work_);
+    work_ = NULL;
+    // Fail fast on attempts to mark after finalizing.
+    marking_stack_ = NULL;
+  }
+
+ private:
+  MarkingStack::Block* work_;
+  MarkingStack* marking_stack_;
+};
+
+
+template<bool sync>
+class MarkingVisitorBase : public ObjectPointerVisitor {
+ public:
+  MarkingVisitorBase(Isolate* isolate,
                  Heap* heap,
                  PageSpace* page_space,
                  MarkingStack* marking_stack,
@@ -190,9 +256,6 @@ class MarkingVisitor : public ObjectPointerVisitor {
     do {
       VisitingOldObject(raw_obj);
       const intptr_t class_id = raw_obj->GetClassId();
-      // Currently, classes are considered roots (see issue 18284), so at this
-      // point, they should all be marked.
-      ASSERT(isolate()->class_table()->At(class_id)->IsMarked());
       if (class_id != kWeakPropertyCid) {
         marked_bytes_ += raw_obj->VisitPointers(this);
       } else {
@@ -221,32 +284,35 @@ class MarkingVisitor : public ObjectPointerVisitor {
     skipped_code_functions_->Add(func);
   }
 
-  // Returns the mark bit. Sets the watch bit if unmarked. (The prior value of
-  // the watched bit is returned in 'watched_before' for validation purposes.)
-  // TODO(koda): When synchronizing header bits, this goes in a single CAS loop.
-  static bool EnsureWatchedIfWhite(RawObject* obj, bool* watched_before) {
-    if (obj->IsMarked()) {
-      return false;
-    }
-    if (!obj->IsWatched()) {
-      *watched_before = false;
-      obj->SetWatchedBitUnsynchronized();
-    } else {
-      *watched_before = true;
+  // If unmarked, sets the watch bit and returns true.
+  // If marked, does nothing and returns false.
+  static bool EnsureWatchedIfWhite(RawObject* obj) {
+    if (!sync) {
+      if (obj->IsMarked()) return false;
+      if (!obj->IsWatched()) obj->SetWatchedBitUnsynchronized();
+      return true;
     }
+    uword tags = obj->ptr()->tags_;
+    uword old_tags;
+    do {
+      old_tags = tags;
+      if (RawObject::MarkBit::decode(tags)) return false;
+      if (RawObject::WatchedBit::decode(tags)) return true;
+      uword new_tags = RawObject::WatchedBit::update(true, old_tags);
+      tags = AtomicOperations::CompareAndSwapWord(
+          &obj->ptr()->tags_, old_tags, new_tags);
+    } while (tags != old_tags);
     return true;
   }
 
   void ProcessWeakProperty(RawWeakProperty* raw_weak) {
     // The fate of the weak property is determined by its key.
     RawObject* raw_key = raw_weak->ptr()->key_;
-    bool watched_before = false;
     if (raw_key->IsHeapObject() &&
         raw_key->IsOldObject() &&
-        EnsureWatchedIfWhite(raw_key, &watched_before)) {
-      // Key is white.  Delay the weak property.
-      bool new_key = delay_set_->Insert(raw_weak);
-      ASSERT(new_key == !watched_before);
+        EnsureWatchedIfWhite(raw_key) &&
+        delay_set_->InsertIfWhite(raw_weak)) {
+      // Key was white.  Delayed the weak property.
     } else {
       // Key is gray or black.  Make the weak property black.
       raw_weak->VisitPointers(this);
@@ -266,68 +332,23 @@ class MarkingVisitor : public ObjectPointerVisitor {
     visiting_old_object_ = obj;
   }
 
- private:
-  class WorkList : public ValueObject {
-   public:
-    explicit WorkList(MarkingStack* marking_stack)
-        : marking_stack_(marking_stack) {
-      work_ = marking_stack_->PopEmptyBlock();
-    }
-
-    ~WorkList() {
-      ASSERT(work_ == NULL);
-      ASSERT(marking_stack_ == NULL);
-    }
-
-    // Returns NULL if no more work was found.
-    RawObject* Pop() {
-      ASSERT(work_ != NULL);
-      if (work_->IsEmpty()) {
-        // TODO(koda): Track over/underflow events and use in heuristics to
-        // distribute work and prevent degenerate flip-flopping.
-        MarkingStack::Block* new_work = marking_stack_->PopNonEmptyBlock();
-        if (new_work == NULL) {
-          return NULL;
-        }
-        marking_stack_->PushBlock(work_);
-        work_ = new_work;
-      }
-      return work_->Pop();
-    }
-
-    void Push(RawObject* raw_obj) {
-      if (work_->IsFull()) {
-        // TODO(koda): Track over/underflow events and use in heuristics to
-        // distribute work and prevent degenerate flip-flopping.
-        marking_stack_->PushBlock(work_);
-        work_ = marking_stack_->PopEmptyBlock();
-      }
-      work_->Push(raw_obj);
-    }
-
-    void Finalize() {
-      ASSERT(work_->IsEmpty());
-      marking_stack_->PushBlock(work_);
-      work_ = NULL;
-      // Fail fast on attempts to mark after finalizing.
-      marking_stack_ = NULL;
-    }
-
-   private:
-    MarkingStack::Block* work_;
-    MarkingStack* marking_stack_;
-  };
+  void AbandonWork() {

[Ivan Posva, 2015/10/08 19:56:12]

Please document where this is used.

[koda, 2015/10/08 21:32:07]

Removed.

+    work_list_.AbandonWork();
+  }
 
-  void MarkAndPush(RawObject* raw_obj) {
+ private:
+  void PushMarked(RawObject* raw_obj) {
     ASSERT(raw_obj->IsHeapObject());
     ASSERT((FLAG_verify_before_gc || FLAG_verify_before_gc) ?
            page_space_->Contains(RawObject::ToAddr(raw_obj)) :
            true);
 
-    // Mark the object and push it on the marking stack.
-    ASSERT(!raw_obj->IsMarked());
+    // Push the marked object on the marking stack.
+    ASSERT(raw_obj->IsMarked());
     const bool is_watched = raw_obj->IsWatched();
-    raw_obj->SetMarkBitUnsynchronized();
+    // We acquired the mark bit => no other task is modifying the header.
+    // TODO(koda): For concurrent mutator, this needs synchronization. Consider
+    // clearing these bits already in the CAS for the mark bit.
     raw_obj->ClearRememberedBitUnsynchronized();
     raw_obj->ClearWatchedBitUnsynchronized();
     if (is_watched) {
@@ -336,6 +357,15 @@ class MarkingVisitor : public ObjectPointerVisitor {
     work_list_.Push(raw_obj);
   }
 
+  static bool TryAcquireMarkBit(RawObject* raw_obj) {
+    if (!sync) {
+      if (raw_obj->IsMarked()) return false;
+      raw_obj->SetMarkBitUnsynchronized();
+      return true;
+    }
+    return raw_obj->TryAcquireMarkBit();
+  }
+
   void MarkObject(RawObject* raw_obj, RawObject** p) {
     // Fast exit if the raw object is a Smi.
     if (!raw_obj->IsHeapObject()) {
@@ -347,15 +377,19 @@ class MarkingVisitor : public ObjectPointerVisitor {
       return;
     }
 
-    // Skip over new objects, but verify consistency of heap while at it.
+    // TODO(koda): Investigate performance impact of alternative branching:
+    // if (smi or new) <-- can be done as single compare + conditional jump
+    //   if (smi) return;
+    //   else ...
+    // if (marked) return;
+    // ...
     if (raw_obj->IsNewObject()) {
-      // TODO(iposva): Add consistency check.
-      if ((visiting_old_object_ != NULL) &&
-          !visiting_old_object_->IsRemembered()) {
-        ASSERT(p != NULL);
-        visiting_old_object_->SetRememberedBitUnsynchronized();
-        thread_->StoreBufferAddObjectGC(visiting_old_object_);
-      }
+      ProcessNewSpaceObject(raw_obj, p);
+      return;
+    }
+
+    if (!TryAcquireMarkBit(raw_obj)) {
+      // Already marked.
       return;
     }
     if (RawObject::IsVariableSizeClassId(raw_obj->GetClassId())) {
@@ -364,7 +398,32 @@ class MarkingVisitor : public ObjectPointerVisitor {
       UpdateLiveOld(raw_obj->GetClassId(), 0);
     }
 
-    MarkAndPush(raw_obj);
+    PushMarked(raw_obj);
+  }
+
+  static bool TryAcquireRememberedBit(RawObject* raw_obj) {
+    if (!sync) {
+      if (raw_obj->IsRemembered()) return false;
+      raw_obj->SetRememberedBitUnsynchronized();
+      return true;
+    }
+    return raw_obj->TryAcquireRememberedBit();
+  }
+
+  void ProcessNewSpaceObject(RawObject* raw_obj, RawObject** p) {
+    // TODO(iposva): Add consistency check.
+    if ((visiting_old_object_ != NULL) &&
+        TryAcquireRememberedBit(visiting_old_object_)) {
+      // NOTE: We pass in the pointer to the address we are visiting
+      // allows us to get a distance from the object start. At some
+      // point we might want to store exact addresses in store buffers
+      // for locations far enough from the header, so that we do not
+      // need to walk big objects only to find the single new
+      // reference in the last word during scavenge. This doesn't seem
+      // to be a problem though currently.
+      ASSERT(p != NULL);
+      thread_->StoreBufferAddObjectGC(visiting_old_object_);
+    }
   }
 
   void UpdateLiveOld(intptr_t class_id, intptr_t size) {
@@ -386,10 +445,14 @@ class MarkingVisitor : public ObjectPointerVisitor {
   SkippedCodeFunctions* skipped_code_functions_;
   uintptr_t marked_bytes_;
 
-  DISALLOW_IMPLICIT_CONSTRUCTORS(MarkingVisitor);
+  DISALLOW_IMPLICIT_CONSTRUCTORS(MarkingVisitorBase);
 };
 
 
+typedef MarkingVisitorBase<false> UnsyncMarkingVisitor;
+typedef MarkingVisitorBase<true> SyncMarkingVisitor;
+
+
 static bool IsUnreachable(const RawObject* raw_obj) {
   if (!raw_obj->IsHeapObject()) {
     return false;
@@ -442,11 +505,20 @@ void GCMarker::Epilogue(Isolate* isolate, bool invoke_api_callbacks) {
 
 void GCMarker::IterateRoots(Isolate* isolate,
                             ObjectPointerVisitor* visitor,
-                            bool visit_prologue_weak_persistent_handles) {
-  isolate->VisitObjectPointers(visitor,
-                               visit_prologue_weak_persistent_handles,
-                               StackFrameIterator::kDontValidateFrames);
-  heap_->new_space()->VisitObjectPointers(visitor);
+                            bool visit_prologue_weak_persistent_handles,
+                            intptr_t slice_index, intptr_t num_slices) {
+  ASSERT(0 <= slice_index && slice_index < num_slices);
+  if (slice_index == 0 || num_slices <= 1) {

[Ivan Posva, 2015/10/08 19:56:12]

()

[koda, 2015/10/08 21:32:07]

Done x2.

+    isolate->VisitObjectPointers(visitor,
+                                 visit_prologue_weak_persistent_handles,
+                                 StackFrameIterator::kDontValidateFrames);
+  }
+  if (slice_index == 1 || num_slices <= 1) {
+    heap_->new_space()->VisitObjectPointers(visitor);
+  }
+
+  // For now, we just distinguish two parts of the root set, so any remaining
+  // slices are empty.
 }
 
 
@@ -460,8 +532,9 @@ void GCMarker::IterateWeakRoots(Isolate* isolate,
 }
 
 
+template<class MarkingVisitorType>
 void GCMarker::IterateWeakReferences(Isolate* isolate,
-                                     MarkingVisitor* visitor) {
+                                     MarkingVisitorType* visitor) {
   ApiState* state = isolate->api_state();
   ASSERT(state != NULL);
   while (true) {
@@ -576,7 +649,10 @@ class MarkTask : public ThreadPool::Task {
            DelaySet* delay_set,
            ThreadBarrier* barrier,
            bool collect_code,
-           bool visit_prologue_weak_persistent_handles)
+           bool visit_prologue_weak_persistent_handles,
+           intptr_t task_index,
+           intptr_t num_tasks,
+           uintptr_t* num_busy)
       : marker_(marker),
         isolate_(isolate),
         heap_(heap),
@@ -586,7 +662,10 @@ class MarkTask : public ThreadPool::Task {
         barrier_(barrier),
         collect_code_(collect_code),
         visit_prologue_weak_persistent_handles_(
-            visit_prologue_weak_persistent_handles) {
+            visit_prologue_weak_persistent_handles),
+        task_index_(task_index),
+        num_tasks_(num_tasks),
+        num_busy_(num_busy) {
   }
 
   virtual void Run() {
@@ -596,20 +675,47 @@ class MarkTask : public ThreadPool::Task {
       Zone* zone = stack_zone.GetZone();
       SkippedCodeFunctions* skipped_code_functions =
         collect_code_ ? new(zone) SkippedCodeFunctions() : NULL;
-      MarkingVisitor visitor(isolate_, heap_, page_space_, marking_stack_,
-                             delay_set_, skipped_code_functions);
-      // Phase 1: Populate and drain marking stack in task.
-      // TODO(koda): Split root iteration work among multiple tasks.
+      SyncMarkingVisitor visitor(isolate_, heap_, page_space_, marking_stack_,
+                                 delay_set_, skipped_code_functions);
+      // Phase 1: Iterate over roots and drain marking stack in tasks.
       marker_->IterateRoots(isolate_, &visitor,
-                            visit_prologue_weak_persistent_handles_);
-      visitor.DrainMarkingStack();
+                            visit_prologue_weak_persistent_handles_,
+                            task_index_, num_tasks_);
+      do {
+        visitor.DrainMarkingStack();
+
+        // I can't find more work right now. If no other task is busy,
+        // then there will never be more work (NB: 1 is *before* decrement).
+        if (AtomicOperations::FetchAndDecrement(num_busy_) == 1) break;
+
+        // Wait for some work to appear.
+        // TODO(iposva): Replace busy-waiting with a solution using Monitor,
+        // and redraw the boundaries between stack/visitor/task as needed.
+        while (marking_stack_->IsEmpty() &&
+               AtomicOperations::LoadRelaxed(num_busy_) > 0) {
+        }
+
+        // If no tasks are busy, there will never be more work.
+        if (AtomicOperations::LoadRelaxed(num_busy_) == 0) break;
+
+        // I saw some work; get busy and compete for it.
+        AtomicOperations::FetchAndIncrement(num_busy_);
+      } while (true);
+      ASSERT(AtomicOperations::LoadRelaxed(num_busy_) == 0);
       barrier_->Sync();
+
       // Phase 2: Weak processing and follow-up marking on main thread.
       barrier_->Sync();
+
       // Phase 3: Finalize results from all markers (detach code, etc.).
+      if (FLAG_log_marker_tasks) {
+        THR_Print("Task %" Pd " marked %" Pd " bytes.\n",
+                  task_index_, visitor.marked_bytes());
+      }
       marker_->FinalizeResultsFrom(&visitor);
     }
     Thread::ExitIsolateAsHelper(true);
+
     // This task is done. Notify the original thread.
     barrier_->Exit();
   }
@@ -624,12 +730,16 @@ class MarkTask : public ThreadPool::Task {
   ThreadBarrier* barrier_;
   bool collect_code_;
   bool visit_prologue_weak_persistent_handles_;
+  const intptr_t task_index_;
+  const intptr_t num_tasks_;
+  uintptr_t* num_busy_;
 
   DISALLOW_COPY_AND_ASSIGN(MarkTask);
 };
 
 
-void GCMarker::FinalizeResultsFrom(MarkingVisitor* visitor) {
+template<class MarkingVisitorType>
+void GCMarker::FinalizeResultsFrom(MarkingVisitorType* visitor) {
   {
     MutexLocker ml(&stats_mutex_);
     marked_bytes_ += visitor->marked_bytes();
@@ -667,9 +777,10 @@ void GCMarker::MarkObjects(Isolate* isolate,
       // Mark everything on main thread.
       SkippedCodeFunctions* skipped_code_functions =
           collect_code ? new(zone) SkippedCodeFunctions() : NULL;
-      MarkingVisitor mark(isolate, heap_, page_space, &marking_stack,
-                          &delay_set, skipped_code_functions);
-      IterateRoots(isolate, &mark, visit_prologue_weak_persistent_handles);
+      UnsyncMarkingVisitor mark(isolate, heap_, page_space, &marking_stack,
+                                &delay_set, skipped_code_functions);
+      IterateRoots(isolate, &mark, visit_prologue_weak_persistent_handles,
+                   0, 1);
       mark.DrainMarkingStack();
       IterateWeakReferences(isolate, &mark);
       MarkingWeakVisitor mark_weak;
@@ -678,32 +789,37 @@ void GCMarker::MarkObjects(Isolate* isolate,
       // All marking done; detach code, etc.
       FinalizeResultsFrom(&mark);
     } else {
-      if (num_tasks > 1) {
-        // TODO(koda): Support multiple:
-        // 1. non-concurrent tasks, after splitting root iteration work, then
-        // 2. concurrent tasks, after synchronizing headers.
-        FATAL("Multiple marking tasks not yet supported");
+      ThreadBarrier barrier(num_tasks + 1);
+      // Used to coordinate draining among tasks; all start out as 'busy'.
+      uintptr_t num_busy = num_tasks;
+      // Phase 1: Iterate over roots and drain marking stack in tasks.
+      for (intptr_t i = 0; i < num_tasks; ++i) {
+        MarkTask* mark_task =
+            new MarkTask(this, isolate, heap_, page_space, &marking_stack,
+                         &delay_set, &barrier, collect_code,
+                         visit_prologue_weak_persistent_handles,
+                         i, num_tasks, &num_busy);
+        ThreadPool* pool = Dart::thread_pool();
+        pool->Run(mark_task);
       }
-      ThreadBarrier barrier(num_tasks + 1);  // +1 for the main thread.
-      // Phase 1: Populate and drain marking stack in task.
-      MarkTask* mark_task =
-          new MarkTask(this, isolate, heap_, page_space, &marking_stack,
-                       &delay_set, &barrier, collect_code,
-                       visit_prologue_weak_persistent_handles);
-      ThreadPool* pool = Dart::thread_pool();
-      pool->Run(mark_task);
       barrier.Sync();
+
       // Phase 2: Weak processing and follow-up marking on main thread.
       SkippedCodeFunctions* skipped_code_functions =
           collect_code ? new(zone) SkippedCodeFunctions() : NULL;
-      MarkingVisitor mark(isolate, heap_, page_space, &marking_stack,
-                          &delay_set, skipped_code_functions);
+      SyncMarkingVisitor mark(isolate, heap_, page_space, &marking_stack,
+                              &delay_set, skipped_code_functions);
       IterateWeakReferences(isolate, &mark);
       MarkingWeakVisitor mark_weak;
       IterateWeakRoots(isolate, &mark_weak,
                        !visit_prologue_weak_persistent_handles);
       barrier.Sync();
+
       // Phase 3: Finalize results from all markers (detach code, etc.).
+      if (FLAG_log_marker_tasks) {
+        THR_Print("Main thread marked %" Pd " bytes.\n",
+                  mark.marked_bytes());
+      }
       FinalizeResultsFrom(&mark);
       barrier.Exit();
     }