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..af7db5949a397b0704d322d47ed3c24f04c4ed43 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, 4,
             "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:
@@ -140,9 +142,10 @@ class SkippedCodeFunctions : public ZoneAllocated {
 };
 
 
-class MarkingVisitor : public ObjectPointerVisitor {
+template<bool sync>
+class MarkingVisitorBase : public ObjectPointerVisitor {
  public:
-  MarkingVisitor(Isolate* isolate,
+  MarkingVisitorBase(Isolate* isolate,
                  Heap* heap,
                  PageSpace* page_space,
                  MarkingStack* marking_stack,
@@ -221,32 +224,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)) {
+        EnsureWatchedIfWhite(raw_key)) {
       // Key is white.  Delay the weak property.
-      bool new_key = delay_set_->Insert(raw_weak);
-      ASSERT(new_key == !watched_before);
+      delay_set_->Insert(raw_weak);

[Ivan Posva, 2015/10/01 11:22:44]

There is a race here:
- This thread (A) observes the mark bit on the key unset, successfully sets the
watch bit. Alternatively this thread observes the watch bit set.
- Thread B marks the key object and observes the watch bit set.
- Thread B proceeds to grab (under lock) the registered weaks for the key and
visits them, removing them from the delay set in the process.
- Thread A succeeds in adding the weak to the delay set.
...

There are also couple of assertions missing at least in the DelaySet class, such
as ensuring that the cleared properties do indeed point to unmarked keys.

[koda, 2015/10/01 20:30:11]

Good catch; fixed by re-checking mark bit after acquiring lock for insertion.

     } else {
       // Key is gray or black.  Make the weak property black.
       raw_weak->VisitPointers(this);
@@ -267,6 +273,7 @@ class MarkingVisitor : public ObjectPointerVisitor {
   }
 
  private:
+  // TODO(koda): Independent of sync; move out.

[Ivan Posva, 2015/10/01 11:22:44]

Please do this in this CL. The class can be local to this .cc file.

[koda, 2015/10/01 20:30:11]

Done.

   class WorkList : public ValueObject {
    public:
     explicit WorkList(MarkingStack* marking_stack)
@@ -318,16 +325,18 @@ class MarkingVisitor : public ObjectPointerVisitor {
     MarkingStack* marking_stack_;
   };
 
-  void MarkAndPush(RawObject* raw_obj) {
+  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 +345,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()) {
@@ -343,19 +361,19 @@ class MarkingVisitor : public ObjectPointerVisitor {
     }
 
     // Fast exit if the raw object is marked.
+    // TODO(koda): Reduce number of branches in generated code by combining
+    // new/smi check.

[Ivan Posva, 2015/10/01 11:22:44]

Comment on wrong line. This is the IsMarked check.

Regarding the comment: In case of new you will need to do special handling which
you do not need for smi. I was wondering how you would like to combine them
without adding an extra branch in the smi case?

[koda, 2015/10/01 20:30:10]

Moved and expanded comment to clarify: The total number of branch instructions
generated would not change, but the code path taken to identify a marked old
object would involve fewer instructions.

It's not clear whether it's a win, but it might be worth investigating in the
future.

     if (raw_obj->IsMarked()) {
       return;
     }
 
-    // Skip over new objects, but verify consistency of heap while at it.
     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 +382,25 @@ 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_)) {
+      ASSERT(p != NULL);  // TODO(koda): Why?

[Ivan Posva, 2015/10/01 17:02:54]

Because 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. I don't think this is a problem though currently.

[koda, 2015/10/01 20:30:11]

Thanks for clarifying; added comment.

+      thread_->StoreBufferAddObjectGC(visiting_old_object_);
+    }
   }
 
   void UpdateLiveOld(intptr_t class_id, intptr_t size) {
@@ -386,10 +422,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;

[Ivan Posva, 2015/10/01 11:22:44]

What is the performance impact of making the sync a property of the visitor
instead of duplicating the code?

[koda, 2015/10/01 20:30:11]

I will investigate and update this thread.

+typedef MarkingVisitorBase<true> SyncMarkingVisitor;
+
+
 static bool IsUnreachable(const RawObject* raw_obj) {
   if (!raw_obj->IsHeapObject()) {
     return false;
@@ -442,11 +482,19 @@ 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) {
+    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 +508,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 +625,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 +638,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,17 +651,39 @@ 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 in tasks.
       marker_->IterateRoots(isolate_, &visitor,
-                            visit_prologue_weak_persistent_handles_);
-      visitor.DrainMarkingStack();
+                            visit_prologue_weak_persistent_handles_,
+                            task_index_, num_tasks_);
+      // Phase 2: Drain marking stack from tasks.

[Ivan Posva, 2015/10/01 17:02:54]

Shouldn't phase 2 start after a barrier?

[koda, 2015/10/01 20:30:11]

Obsolete after combining the phases.

+      ASSERT(AtomicOperations::LoadRelaxed(num_busy_) ==
+             static_cast<uword>(num_tasks_));

[Ivan Posva, 2015/10/01 17:02:54]

This looks like you want to add a LoadRelaxed(intrptr_t*) as well.

[koda, 2015/10/01 20:30:11]

Obsolete after combining the phases.

+      barrier_->Sync();

[Ivan Posva, 2015/10/01 17:02:54]

Is this barrier really necessary? The tasks that do not visit roots can start
draining the marking stacks.

[koda, 2015/10/01 20:30:10]

It was necessary to support the ASSERT in DrainMarkingStack that the classes
have already been marked. However, the added value of that assertion is very
limited.

Combined the phases and removed the ASSERT.

+      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;
+        // Busy wait for some work to appear.
+        while (marking_stack_->IsEmpty() &&

[Ivan Posva, 2015/10/01 17:02:55]

How do you plan to fix the busy looping?

[koda, 2015/10/01 20:30:11]

We can replace the mutex inside marking_stack_ with a monitor that is notified
whenever more work is added.

+               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.

[Ivan Posva, 2015/10/01 17:02:55]

Style comment: It is hard to read these blocks of contiguous comments and one
line statements. Maybe visually breaking them with new lines?

[koda, 2015/10/01 20:30:11]

Done.

+        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.
+      // Phase 3: Weak processing and follow-up marking on main thread.
       barrier_->Sync();
-      // Phase 3: Finalize results from all markers (detach code, etc.).
+      // Phase 4: 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);
@@ -624,12 +701,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 +748,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 +760,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 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.
+      // Phase 2: Drain marking stack from tasks.
+      barrier.Sync();
+      // Phase 3: 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.).
+      // Phase 4: 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();
     }