Refactor delay set to allow more than one marking visitor

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 234bf973476eb04b5b2b17c9dc278fa104761486..a416692e6cf3b002fa420f14eb72520c77ea64a0 100644
--- a/runtime/vm/gc_marker.cc
+++ b/runtime/vm/gc_marker.cc
@@ -15,6 +15,7 @@
 #include "vm/pages.h"
 #include "vm/raw_object.h"
 #include "vm/stack_frame.h"
+#include "vm/thread_pool.h"
 #include "vm/visitor.h"
 #include "vm/object_id_ring.h"
 
@@ -120,12 +121,63 @@ class MarkingStack : public ValueObject {
 };
 
 
+class DelaySet {
+ private:
+  typedef std::multimap<RawObject*, RawWeakProperty*> Map;
+  typedef std::pair<RawObject*, RawWeakProperty*> MapEntry;
+
+ public:
+  DelaySet() : mutex_(new Mutex()) {}
+  ~DelaySet() { delete mutex_; }
+
+  // Returns 'true' if this inserted a new key (not just updated the value).
+  bool Insert(RawWeakProperty* raw_weak) {
+    MutexLocker ml(mutex_);
+    RawObject* raw_key = raw_weak->ptr()->key_;
+    bool new_key = (delay_set_.find(raw_key) == delay_set_.end());
+    delay_set_.insert(std::make_pair(raw_key, raw_weak));
+    return new_key;
+  }
+
+  void ClearAll() {
+    MutexLocker ml(mutex_);
+    Map::iterator it = delay_set_.begin();
+    for (; it != delay_set_.end(); ++it) {
+      WeakProperty::Clear(it->second);
+    }
+  }
+
+  // Visit all values with a key equal to raw_obj.
+  void VisitValuesForKey(RawObject* raw_obj, ObjectPointerVisitor* visitor) {
+    // Extract the range into a temporary vector to iterate over it
+    // while delay_set_ may be modified.
+    std::vector<MapEntry> temp_copy;
+    {
+      MutexLocker ml(mutex_);
+      std::pair<Map::iterator, Map::iterator> ret =
+          delay_set_.equal_range(raw_obj);
+      temp_copy.insert(temp_copy.end(), ret.first, ret.second);
+      delay_set_.erase(ret.first, ret.second);
+    }
+    for (std::vector<MapEntry>::iterator it = temp_copy.begin();
+         it != temp_copy.end(); ++it) {
+      it->second->VisitPointers(visitor);
+    }
+  }
+
+ private:
+  Map delay_set_;
+  Mutex* mutex_;
+};
+
+
 class MarkingVisitor : public ObjectPointerVisitor {
  public:
   MarkingVisitor(Isolate* isolate,
                  Heap* heap,
                  PageSpace* page_space,
                  MarkingStack* marking_stack,
+                 DelaySet* delay_set,
                  bool visit_function_code)
       : ObjectPointerVisitor(isolate),
         thread_(Thread::Current()),
@@ -134,12 +186,18 @@ class MarkingVisitor : public ObjectPointerVisitor {
         class_table_(isolate->class_table()),
         page_space_(page_space),
         marking_stack_(marking_stack),
+        delay_set_(delay_set),
         visiting_old_object_(NULL),
         visit_function_code_(visit_function_code) {
     ASSERT(heap_ != vm_heap_);
     ASSERT(thread_->isolate() == isolate);
   }
 
+  ~MarkingVisitor() {
+    // 'Finalize' should be explicitly called before destruction.
+    ASSERT(marking_stack_ == NULL);
+  }
+
   MarkingStack* marking_stack() const { return marking_stack_; }
 
   void VisitPointers(RawObject** first, RawObject** last) {
@@ -154,26 +212,45 @@ class MarkingVisitor : public ObjectPointerVisitor {
     return &skipped_code_functions_;
   }
 
-  void DelayWeakProperty(RawWeakProperty* raw_weak) {
+  // 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;
+    }
+    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_;
-    DelaySet::iterator it = delay_set_.find(raw_key);
-    if (it != delay_set_.end()) {
-      ASSERT(raw_key->IsWatched());
+    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);
     } else {
-      ASSERT(!raw_key->IsWatched());
-      raw_key->SetWatchedBitUnsynchronized();
+      // Key is gray or black.  Make the weak property black.
+      raw_weak->VisitPointers(this);
     }
-    delay_set_.insert(std::make_pair(raw_key, raw_weak));
   }
 
+  // Called when all marking is complete.
   void Finalize() {
-    DelaySet::iterator it = delay_set_.begin();
-    for (; it != delay_set_.end(); ++it) {
-      WeakProperty::Clear(it->second);
-    }
     if (!visit_function_code_) {
       DetachCode();
     }
+    // Fail fast on attempts to mark after finalizing.
+    marking_stack_ = NULL;
   }
 
   void VisitingOldObject(RawObject* obj) {
@@ -195,17 +272,7 @@ class MarkingVisitor : public ObjectPointerVisitor {
     raw_obj->ClearRememberedBitUnsynchronized();
     raw_obj->ClearWatchedBitUnsynchronized();
     if (is_watched) {
-      std::pair<DelaySet::iterator, DelaySet::iterator> ret;
-      // Visit all elements with a key equal to raw_obj.
-      ret = delay_set_.equal_range(raw_obj);
-      // Create a copy of the range in a temporary vector to iterate over it
-      // while delay_set_ may be modified.
-      std::vector<DelaySetEntry> temp_copy(ret.first, ret.second);
-      delay_set_.erase(ret.first, ret.second);
-      for (std::vector<DelaySetEntry>::iterator it = temp_copy.begin();
-           it != temp_copy.end(); ++it) {
-        it->second->VisitPointers(this);
-      }
+      delay_set_->VisitValuesForKey(raw_obj, this);
     }
     marking_stack_->Push(raw_obj);
   }
@@ -285,6 +352,8 @@ class MarkingVisitor : public ObjectPointerVisitor {
       ISL_Print("  total detached unoptimized: %" Pd "\n",
                 unoptimized_code_count);
     }
+    // Clean up (even if the array is currently Zone-allocated).
+    skipped_code_functions_.Clear();
   }
 
   Thread* thread_;
@@ -293,10 +362,8 @@ class MarkingVisitor : public ObjectPointerVisitor {
   ClassTable* class_table_;
   PageSpace* page_space_;
   MarkingStack* marking_stack_;
+  DelaySet* delay_set_;
   RawObject* visiting_old_object_;
-  typedef std::multimap<RawObject*, RawWeakProperty*> DelaySet;
-  typedef std::pair<RawObject*, RawWeakProperty*> DelaySetEntry;
-  DelaySet delay_set_;
   const bool visit_function_code_;
   GrowableArray<RawFunction*> skipped_code_functions_;
 
@@ -449,29 +516,13 @@ void GCMarker::DrainMarkingStack(Isolate* isolate,
     } else {
       RawWeakProperty* raw_weak = reinterpret_cast<RawWeakProperty*>(raw_obj);
       marked_bytes_ += raw_weak->Size();
-      ProcessWeakProperty(raw_weak, visitor);
+      visitor->ProcessWeakProperty(raw_weak);
     }
   }
   visitor->VisitingOldObject(NULL);
 }
 
 
-void GCMarker::ProcessWeakProperty(RawWeakProperty* raw_weak,
-                                   MarkingVisitor* visitor) {
-  // The fate of the weak property is determined by its key.
-  RawObject* raw_key = raw_weak->ptr()->key_;
-  if (raw_key->IsHeapObject() &&
-      raw_key->IsOldObject() &&
-      !raw_key->IsMarked()) {
-    // Key is white.  Delay the weak property.
-    visitor->DelayWeakProperty(raw_weak);
-  } else {
-    // Key is gray or black.  Make the weak property black.
-    raw_weak->VisitPointers(visitor);
-  }
-}
-
-
 void GCMarker::ProcessWeakTables(PageSpace* page_space) {
   for (int sel = 0;
        sel < Heap::kNumWeakSelectors;
@@ -519,6 +570,43 @@ void GCMarker::ProcessObjectIdTable(Isolate* isolate) {
 }
 
 
+class DrainTask : public ThreadPool::Task {
+ public:
+  DrainTask(GCMarker* marker,
+            Isolate* isolate,
+            PageSpace* page_space,
+            MarkingVisitor* visitor)
+      : marker_(marker),
+        isolate_(isolate),
+        page_space_(page_space),
+        visitor_(visitor) {
+    MonitorLocker ml(page_space->tasks_lock());
+    page_space->set_tasks(page_space->tasks() + 1);
+    ml.NotifyAll();

[Ivan Posva, 2015/06/16 17:21:00]

Why NotifyAll()? Do you really intend to wakeup all threads that are waiting on
the number of tasks to change?

Also please add a comment explaining who is waiting for these notifications.

[koda, 2015/06/16 19:41:44]

Removed.

+  }
+
+  virtual ~DrainTask() {}
+
+  virtual void Run() {
+    Thread::EnterIsolateAsHelper(isolate_);
+    marker_->DrainMarkingStack(isolate_, visitor_);
+    // This task is done. Notify the original thread.
+    {
+      MonitorLocker ml(page_space_->tasks_lock());
+      page_space_->set_tasks(page_space_->tasks() - 1);
+      ml.NotifyAll();

[Ivan Posva, 2015/06/16 17:21:00]

ditto

[koda, 2015/06/16 19:41:43]

Changed to Notify.

+    }
+    Thread::ExitIsolateAsHelper();
+  }
+
+ private:
+  GCMarker* marker_;
+  Isolate* isolate_;
+  PageSpace* page_space_;
+  MarkingVisitor* visitor_;
+};
+
+
 void GCMarker::MarkObjects(Isolate* isolate,
                            PageSpace* page_space,
                            bool invoke_api_callbacks,
@@ -530,14 +618,40 @@ void GCMarker::MarkObjects(Isolate* isolate,
   {
     StackZone zone(isolate);
     MarkingStack marking_stack;
-    MarkingVisitor mark(
-        isolate, heap_, page_space, &marking_stack, visit_function_code);
-    IterateRoots(isolate, &mark, !invoke_api_callbacks);
-    DrainMarkingStack(isolate, &mark);
-    IterateWeakReferences(isolate, &mark);
+    DelaySet delay_set;
+    const int kNumMarkers = 2;
+    GrowableArray<MarkingVisitor*> markers;
+    for (int i = 0; i < kNumMarkers; ++i) {

[Ivan Posva, 2015/06/16 17:21:00]

It would be much more readable if the DrainTask would stack allocate its own
MarkingVisitor instead of trying to account for them here.

[koda, 2015/06/16 19:41:44]

Yes, but ThreadPool deletes each Task after it has Run, so we'd need a callback
or other method to coordinate the detaching of code (kept in each visitor) after
*all* marking has completed. It can be done by the GCMarker (pull/push from/to
each visitor via callback), but I was saving this for a future CL. Note that
marked_words_ will need to be summed up in the GCMarker from each visitor (e.g.,
by pull or push via callback).

+      markers.Add(new MarkingVisitor(
+          isolate, heap_, page_space, &marking_stack, &delay_set,
+          visit_function_code));
+    }
+    // Arbitrarily pick a visitor for the roots.
+    MarkingVisitor* roots_visitor = markers[0];
+    // No parallelism/concurrcy yet, but use a separate visitor to drain the
+    // marking stack on a separate thread, just to show we can.
+    MarkingVisitor* main_visitor = markers[1];
+    IterateRoots(isolate, roots_visitor, !invoke_api_callbacks);
+    Dart::thread_pool()->Run(
+        new DrainTask(this, isolate, page_space, main_visitor));
+    // Wait for task to finish.
+    // TODO(koda): Implement counting barrier utility class and use it here.
+    {
+      MonitorLocker locker(page_space->tasks_lock());
+      while (page_space->tasks() > 1) {
+        locker.Wait();
+      }
+    }
+    IterateWeakReferences(isolate, roots_visitor);
     MarkingWeakVisitor mark_weak;
     IterateWeakRoots(isolate, &mark_weak, invoke_api_callbacks);
-    mark.Finalize();
+    // All marking is done.
+    for (int i = 0; i < kNumMarkers; ++i) {
+      MarkingVisitor* marker = markers.RemoveLast();
+      marker->Finalize();
+      delete marker;
+    }
+    delay_set.ClearAll();

[Ivan Posva, 2015/06/16 17:21:00]

ClearAll is ambiguous. How about ClearReferences()?

[koda, 2015/06/16 19:41:44]

Done.

     ProcessWeakTables(page_space);
     ProcessObjectIdTable(isolate);
   }