Refactor delay set to allow more than one marking visitor

runtime/vm/gc_marker.cc

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/gc_marker.h"
 
 #include <map>
 #include <utility>
 #include <vector>
 
 #include "vm/allocation.h"
 #include "vm/dart_api_state.h"
 #include "vm/isolate.h"
 #include "vm/log.h"
 #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"
 
 namespace dart {
 
 // A simple chunked marking stack.
 class MarkingStack : public ValueObject {
  public:
   MarkingStack()
       : head_(new MarkingStackChunk()),
@@ skipping 85 matching lines @@
 
   MarkingStackChunk* head_;
   MarkingStackChunk* empty_chunks_;
   RawObject** marking_stack_;
   uint32_t top_;
 
   DISALLOW_COPY_AND_ASSIGN(MarkingStack);
 };
 
 
+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()),
         heap_(heap),
         vm_heap_(Dart::vm_isolate()->heap()),
         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) {
     for (RawObject** current = first; current <= last; current++) {
       MarkObject(*current, current);
     }
   }
 
   bool visit_function_code() const { return visit_function_code_; }
 
   virtual GrowableArray<RawFunction*>* skipped_code_functions() {
     return &skipped_code_functions_;
   }
 
-  void DelayWeakProperty(RawWeakProperty* raw_weak) {
-    RawObject* raw_key = raw_weak->ptr()->key_;
-    DelaySet::iterator it = delay_set_.find(raw_key);
-    if (it != delay_set_.end()) {
-      ASSERT(raw_key->IsWatched());
+  // 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 {
-      ASSERT(!raw_key->IsWatched());
-      raw_key->SetWatchedBitUnsynchronized();
+      *watched_before = true;
     }
-    delay_set_.insert(std::make_pair(raw_key, raw_weak));
+    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);
+    } else {
+      // Key is gray or black.  Make the weak property black.
+      raw_weak->VisitPointers(this);
+    }
+  }
+
+  // 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) {
     ASSERT((obj == NULL) || obj->IsOldObject());
     visiting_old_object_ = obj;
   }
 
  private:
   void MarkAndPush(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());
     const bool is_watched = raw_obj->IsWatched();
     raw_obj->SetMarkBitUnsynchronized();
     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);
   }
 
   void MarkObject(RawObject* raw_obj, RawObject** p) {
     // Fast exit if the raw object is a Smi.
     if (!raw_obj->IsHeapObject()) {
       return;
     }
 
@@ skipping 59 matching lines @@
         if (FLAG_log_code_drop) {
           unoptimized_code_count++;
         }
       }
     }
     if (FLAG_log_code_drop) {
       ISL_Print("  total detached current: %" Pd "\n", current_code_count);
       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_;
   Heap* heap_;
   Heap* vm_heap_;
   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_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(MarkingVisitor);
 };
 
 
 static bool IsUnreachable(const RawObject* raw_obj) {
   if (!raw_obj->IsHeapObject()) {
     return false;
@@ skipping 132 matching lines @@
     visitor->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(visitor);
     } 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;
        sel++) {
     WeakTable* table = heap_->GetWeakTable(
         Heap::kOld, static_cast<Heap::WeakSelector>(sel));
     intptr_t size = table->size();
     for (intptr_t i = 0; i < size; i++) {
       if (table->IsValidEntryAt(i)) {
         RawObject* raw_obj = table->ObjectAt(i);
@@ skipping 27 matching lines @@
 
 
 void GCMarker::ProcessObjectIdTable(Isolate* isolate) {
   ObjectIdRingClearPointerVisitor visitor(isolate);
   ObjectIdRing* ring = isolate->object_id_ring();
   ASSERT(ring != NULL);
   ring->VisitPointers(&visitor);
 }
 
 
+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,
                            bool collect_code) {
   const bool visit_function_code = !collect_code;
   Prologue(isolate, invoke_api_callbacks);
   // The API prologue/epilogue may create/destroy zones, so we must not
   // depend on zone allocations surviving beyond the epilogue callback.
   {
     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);
   }
   Epilogue(isolate, invoke_api_callbacks);
 }
 
 }  // namespace dart