- Removed the kWatchedBit and the associated weak property handling

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/store_buffer.h"
 #include "vm/thread_barrier.h"
 #include "vm/thread_pool.h"
 #include "vm/thread_registry.h"
 #include "vm/timeline.h"
 #include "vm/visitor.h"
 #include "vm/object_id_ring.h"
 
 namespace dart {
 
 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:
-  typedef std::multimap<RawObject*, RawWeakProperty*> Map;
-  typedef std::pair<RawObject*, RawWeakProperty*> MapEntry;
-
- public:
-  DelaySet() : mutex_(new Mutex()) {}
-  ~DelaySet() { delete mutex_; }
-
-  // After atomically setting the watched bit on a white key (see
-  // EnsureWatchedIfWhitewhich; this means the mark bit cannot be set
-  // without observing the watched bit), this method atomically
-  // inserts raw_weak if its key is *still* white, so that any future
-  // call to VisitValuesForKey is guaranteed to include its
-  // value. Returns true on success, and false if the key is no longer white.
-  bool InsertIfWhite(RawWeakProperty* raw_weak) {
-    MutexLocker ml(mutex_);
-    RawObject* raw_key = raw_weak->ptr()->key_;
-    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 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, 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;
-    {
-      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 SkippedCodeFunctions : public ZoneAllocated {
  public:
   SkippedCodeFunctions() {}
 
   void Add(RawFunction* func) {
     skipped_code_functions_.Add(func);
   }
 
   void DetachCode() {
     intptr_t unoptimized_code_count = 0;
@@ skipping 103 matching lines @@
 };
 
 
 template<bool sync>
 class MarkingVisitorBase : public ObjectPointerVisitor {
  public:
   MarkingVisitorBase(Isolate* isolate,
                  Heap* heap,
                  PageSpace* page_space,
                  MarkingStack* marking_stack,
-                 DelaySet* delay_set,
                  SkippedCodeFunctions* skipped_code_functions)
       : ObjectPointerVisitor(isolate),
         thread_(Thread::Current()),
         heap_(heap),
         vm_heap_(Dart::vm_isolate()->heap()),
         class_stats_count_(isolate->class_table()->NumCids()),
         class_stats_size_(isolate->class_table()->NumCids()),
         page_space_(page_space),
         work_list_(marking_stack),
-        delay_set_(delay_set),
+        delayed_weak_properties_(NULL),
         visiting_old_object_(NULL),
         skipped_code_functions_(skipped_code_functions),
         marked_bytes_(0) {
     ASSERT(heap_ != vm_heap_);
     ASSERT(thread_->isolate() == isolate);
     class_stats_count_.SetLength(isolate->class_table()->NumCids());
     class_stats_size_.SetLength(isolate->class_table()->NumCids());
     for (intptr_t i = 0; i < class_stats_count_.length(); ++i) {
       class_stats_count_[i] = 0;
       class_stats_size_[i] = 0;
@@ skipping 11 matching lines @@
   }
 
   // Returns true if some non-zero amount of work was performed.
   bool DrainMarkingStack() {
     RawObject* raw_obj = work_list_.Pop();
     if (raw_obj == NULL) {
       ASSERT(visiting_old_object_ == NULL);
       return false;
     }
     do {
-      VisitingOldObject(raw_obj);
-      const intptr_t class_id = raw_obj->GetClassId();
-      if (class_id != kWeakPropertyCid) {
-        marked_bytes_ += raw_obj->VisitPointers(this);
-      } else {
-        RawWeakProperty* raw_weak = reinterpret_cast<RawWeakProperty*>(raw_obj);
-        marked_bytes_ += raw_weak->Size();
-        ProcessWeakProperty(raw_weak);
+      do {
+        // First drain the marking stacks.
+        VisitingOldObject(raw_obj);
+        const intptr_t class_id = raw_obj->GetClassId();
+        if (class_id != kWeakPropertyCid) {
+          marked_bytes_ += raw_obj->VisitPointers(this);
+        } else {
+          RawWeakProperty* raw_weak =
+              reinterpret_cast<RawWeakProperty*>(raw_obj);
+          marked_bytes_ += ProcessWeakProperty(raw_weak);
+        }
+        raw_obj = work_list_.Pop();
+      } while (raw_obj != NULL);
+
+      // Marking stack is empty.
+      // Process all the pending weak properties in this visitor.
+      RawWeakProperty* cur_weak = delayed_weak_properties_;
+      delayed_weak_properties_ = NULL;
+      while (cur_weak != NULL) {
+        uword next_weak = cur_weak->ptr()->next_;
+        RawObject* raw_key = cur_weak->ptr()->key_;
+        // Reset the next pointer in the weak property.
+        cur_weak->ptr()->next_ = 0;
+        if (raw_key->IsMarked()) {
+          // The key is marked so we make sure to properly visit all pointers
+          // originating from this weak property.
+          VisitingOldObject(cur_weak);
+          cur_weak->VisitPointers(this);
+        } else {
+          // Requeue this weak property to be handled later.
+          EnqueueWeakProperty(cur_weak);
+        }
+        // Advance to next weak property in the queue.
+        cur_weak = reinterpret_cast<RawWeakProperty*>(next_weak);
       }
+
+      // Check whether any further work was pushed either by other markers or
+      // by the handling of weak properties.
       raw_obj = work_list_.Pop();
     } while (raw_obj != NULL);
     VisitingOldObject(NULL);
     return true;
   }
 
   void VisitPointers(RawObject** first, RawObject** last) {
     for (RawObject** current = first; current <= last; current++) {
       MarkObject(*current, current);
     }
   }
 
   bool visit_function_code() const {
     return skipped_code_functions_ == NULL;
   }
 
   virtual void add_skipped_code_function(RawFunction* func) {
     ASSERT(!visit_function_code());
     skipped_code_functions_->Add(func);
   }
 
-  // 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 EnqueueWeakProperty(RawWeakProperty* raw_weak) {
+    ASSERT(raw_weak->IsHeapObject());
+    ASSERT(raw_weak->IsOldObject());
+    ASSERT(raw_weak->IsWeakProperty());
+    ASSERT(raw_weak->IsMarked());
+    ASSERT(raw_weak->ptr()->next_ == 0);
+    raw_weak->ptr()->next_ = reinterpret_cast<uword>(delayed_weak_properties_);
+    delayed_weak_properties_ = raw_weak;
   }
 
-  void ProcessWeakProperty(RawWeakProperty* raw_weak) {
+  intptr_t ProcessWeakProperty(RawWeakProperty* raw_weak) {
     // 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() &&
-        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);
+        !raw_key->IsMarked()) {
+      // Key was white. Enqueue the weak property.
+      EnqueueWeakProperty(raw_weak);
+      return raw_weak->Size();
     }
+    // Key is gray or black. Make the weak property black.
+    return raw_weak->VisitPointers(this);
   }
 
   // Called when all marking is complete.
   void Finalize() {
     work_list_.Finalize();
+    // Detach code from functions.
     if (skipped_code_functions_ != NULL) {
       skipped_code_functions_->DetachCode();
     }
+    // Clear pending weak properties.
+    RawWeakProperty* cur_weak = delayed_weak_properties_;
+    delayed_weak_properties_ = NULL;
+    intptr_t weak_properties_cleared = 0;
+    while (cur_weak != NULL) {
+      uword next_weak = cur_weak->ptr()->next_;
+      cur_weak->ptr()->next_ = 0;
+      WeakProperty::Clear(cur_weak);
+      weak_properties_cleared++;
+      // Advance to next weak property in the queue.
+      cur_weak = reinterpret_cast<RawWeakProperty*>(next_weak);
+    }
   }
 
   void VisitingOldObject(RawObject* obj) {
     ASSERT((obj == NULL) || obj->IsOldObject());
     visiting_old_object_ = 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);
 
     // Push the marked object on the marking stack.
     ASSERT(raw_obj->IsMarked());
-    const bool is_watched = raw_obj->IsWatched();
     // 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) {
-      delay_set_->VisitValuesForKey(raw_obj, this);
-    }
     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();
@@ skipping 66 matching lines @@
     class_stats_size_[class_id] += size;
   }
 
   Thread* thread_;
   Heap* heap_;
   Heap* vm_heap_;
   GrowableArray<intptr_t> class_stats_count_;
   GrowableArray<intptr_t> class_stats_size_;
   PageSpace* page_space_;
   MarkerWorkList work_list_;
-  DelaySet* delay_set_;
+  RawWeakProperty* delayed_weak_properties_;
   RawObject* visiting_old_object_;
   SkippedCodeFunctions* skipped_code_functions_;
   uintptr_t marked_bytes_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(MarkingVisitorBase);
 };
 
 
 typedef MarkingVisitorBase<false> UnsyncMarkingVisitor;
 typedef MarkingVisitorBase<true> SyncMarkingVisitor;
@@ skipping 123 matching lines @@
 }
 
 
 class MarkTask : public ThreadPool::Task {
  public:
   MarkTask(GCMarker* marker,
            Isolate* isolate,
            Heap* heap,
            PageSpace* page_space,
            MarkingStack* marking_stack,
-           DelaySet* delay_set,
            ThreadBarrier* barrier,
            bool collect_code,
            intptr_t task_index,
            intptr_t num_tasks,
            uintptr_t* num_busy)
       : marker_(marker),
         isolate_(isolate),
         heap_(heap),
         page_space_(page_space),
         marking_stack_(marking_stack),
-        delay_set_(delay_set),
         barrier_(barrier),
         collect_code_(collect_code),
         task_index_(task_index),
         num_tasks_(num_tasks),
         num_busy_(num_busy) {
   }
 
   virtual void Run() {
     bool result =
         Thread::EnterIsolateAsHelper(isolate_, Thread::kMarkerTask, true);
     ASSERT(result);
     {
       Thread* thread = Thread::Current();
       TIMELINE_FUNCTION_GC_DURATION(thread, "MarkTask");
       StackZone stack_zone(thread);
       Zone* zone = stack_zone.GetZone();
       SkippedCodeFunctions* skipped_code_functions =
           collect_code_ ? new(zone) SkippedCodeFunctions() : NULL;
       SyncMarkingVisitor visitor(isolate_, heap_, page_space_, marking_stack_,
-                                 delay_set_, skipped_code_functions);
+                                 skipped_code_functions);
       // Phase 1: Iterate over roots and drain marking stack in tasks.
       marker_->IterateRoots(isolate_, &visitor, 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.
@@ skipping 27 matching lines @@
     // This task is done. Notify the original thread.
     barrier_->Exit();
   }
 
  private:
   GCMarker* marker_;
   Isolate* isolate_;
   Heap* heap_;
   PageSpace* page_space_;
   MarkingStack* marking_stack_;
-  DelaySet* delay_set_;
   ThreadBarrier* barrier_;
   bool collect_code_;
   const intptr_t task_index_;
   const intptr_t num_tasks_;
   uintptr_t* num_busy_;
 
   DISALLOW_COPY_AND_ASSIGN(MarkTask);
 };
 
 
@@ skipping 21 matching lines @@
                            PageSpace* page_space,
                            bool invoke_api_callbacks,
                            bool 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 stack_zone(Thread::Current());
     Zone* zone = stack_zone.GetZone();
     MarkingStack marking_stack;
-    DelaySet delay_set;
     marked_bytes_ = 0;
     const int num_tasks = FLAG_marker_tasks;
     if (num_tasks == 0) {
       // Mark everything on main thread.
       SkippedCodeFunctions* skipped_code_functions =
           collect_code ? new(zone) SkippedCodeFunctions() : NULL;
       UnsyncMarkingVisitor mark(isolate, heap_, page_space, &marking_stack,
-                                &delay_set, skipped_code_functions);
+                                skipped_code_functions);
       IterateRoots(isolate, &mark, 0, 1);
       mark.DrainMarkingStack();
       MarkingWeakVisitor mark_weak;
       IterateWeakRoots(isolate, &mark_weak);
       // All marking done; detach code, etc.
       FinalizeResultsFrom(&mark);
     } else {
       ThreadBarrier barrier(num_tasks + 1,
                             heap_->barrier(),
                             heap_->barrier_done());
       // 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,
+                         &barrier, collect_code,
                          i, num_tasks, &num_busy);
         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;
-      SyncMarkingVisitor mark(isolate, heap_, page_space, &marking_stack,
-                              &delay_set, skipped_code_functions);
+      // Phase 2: Weak processing on main thread.
       MarkingWeakVisitor mark_weak;
       IterateWeakRoots(isolate, &mark_weak);
       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();
     }
-    delay_set.ClearReferences();
     ProcessWeakTables(page_space);
     ProcessObjectIdTable(isolate);
   }
   Epilogue(isolate, invoke_api_callbacks);
 }
 
 }  // namespace dart