- Removed the kWatchedBit and the associated weak property handling

runtime/vm/scavenger.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/scavenger.h"
 
-#include <algorithm>
-#include <map>
-#include <utility>
-
 #include "vm/dart.h"
 #include "vm/dart_api_state.h"
 #include "vm/isolate.h"
 #include "vm/lockers.h"
 #include "vm/object.h"
 #include "vm/object_id_ring.h"
 #include "vm/safepoint.h"
 #include "vm/stack_frame.h"
 #include "vm/store_buffer.h"
 #include "vm/thread_registry.h"
@@ skipping 34 matching lines @@
 }
 
 
 static inline void ForwardTo(uword original, uword target) {
   // Make sure forwarding can be encoded.
   ASSERT((target & kForwardingMask) == 0);
   *reinterpret_cast<uword*>(original) = target | kForwarded;
 }
 
 
-class BoolScope : public ValueObject {
- public:
-  BoolScope(bool* addr, bool value) : _addr(addr), _value(*addr) {
-    *_addr = value;
-  }
-  ~BoolScope() {
-    *_addr = _value;
-  }
-
- private:
-  bool* _addr;
-  bool _value;
-};
-
-
 class ScavengerVisitor : public ObjectPointerVisitor {
  public:
   explicit ScavengerVisitor(Isolate* isolate,
                             Scavenger* scavenger,
                             SemiSpace* from)
       : ObjectPointerVisitor(isolate),
         thread_(Thread::Current()),
         scavenger_(scavenger),
         from_(from),
         heap_(scavenger->heap_),
         vm_heap_(Dart::vm_isolate()->heap()),
         page_space_(scavenger->heap_->old_space()),
-        delayed_weak_stack_(),
         bytes_promoted_(0),
-        visiting_old_object_(NULL),
-        in_scavenge_pointer_(false) { }
+        visiting_old_object_(NULL) { }
 
   void VisitPointers(RawObject** first, RawObject** last) {
+    ASSERT((visiting_old_object_ != NULL) ||
+           scavenger_->Contains(reinterpret_cast<uword>(first)) ||
+           !heap_->Contains(reinterpret_cast<uword>(first)));
     for (RawObject** current = first; current <= last; current++) {
       ScavengePointer(current);
     }
   }
 
-  GrowableArray<RawObject*>* DelayedWeakStack() {
-    return &delayed_weak_stack_;
-  }
-
   void VisitingOldObject(RawObject* obj) {
     ASSERT((obj == NULL) || obj->IsOldObject());
     visiting_old_object_ = obj;
   }
 
-  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());
-    } else {
-      ASSERT(!raw_key->IsWatched());
-      raw_key->SetWatchedBitUnsynchronized();
-    }
-    delay_set_.insert(std::make_pair(raw_key, raw_weak));
-  }
-
-  void Finalize() {
-    DelaySet::iterator it = delay_set_.begin();
-    for (; it != delay_set_.end(); ++it) {
-      WeakProperty::Clear(it->second);
-    }
-  }
-
   intptr_t bytes_promoted() const { return bytes_promoted_; }
 
  private:
   void UpdateStoreBuffer(RawObject** p, RawObject* obj) {
     uword ptr = reinterpret_cast<uword>(p);
     ASSERT(obj->IsHeapObject());
     ASSERT(!scavenger_->Contains(ptr));
     ASSERT(!heap_->CodeContains(ptr));
     ASSERT(heap_->Contains(ptr));
     // If the newly written object is not a new object, drop it immediately.
     if (!obj->IsNewObject() || visiting_old_object_->IsRemembered()) {
       return;
     }
     visiting_old_object_->SetRememberedBit();
     thread_->StoreBufferAddObjectGC(visiting_old_object_);
   }
 
   void ScavengePointer(RawObject** p) {
     // ScavengePointer cannot be called recursively.
-#ifdef DEBUG
-    ASSERT(!in_scavenge_pointer_);
-    BoolScope bs(&in_scavenge_pointer_, true);
-#endif
-
     RawObject* raw_obj = *p;
 
     if (raw_obj->IsSmiOrOldObject()) {
       return;
     }
 
     uword raw_addr = RawObject::ToAddr(raw_obj);
     // The scavenger is only expects objects located in the from space.
     ASSERT(from_->Contains(raw_addr));
     // Read the header word of the object and determine if the object has
     // already been copied.
     uword header = *reinterpret_cast<uword*>(raw_addr);
     uword new_addr = 0;
     if (IsForwarding(header)) {
       // Get the new location of the object.
       new_addr = ForwardedAddr(header);
     } else {
-      if (raw_obj->IsWatched()) {
-        raw_obj->ClearWatchedBitUnsynchronized();
-        std::pair<DelaySet::iterator, DelaySet::iterator> ret;
-        // Visit all elements with a key equal to this raw_obj.
-        ret = delay_set_.equal_range(raw_obj);
-        for (DelaySet::iterator it = ret.first; it != ret.second; ++it) {
-          // Remember the delayed WeakProperty. These objects have been
-          // forwarded, but have not been scavenged because their key was not
-          // known to be reachable. Now that the key object is known to be
-          // reachable, we need to visit its key and value pointers.
-          delayed_weak_stack_.Add(it->second);
-        }
-        delay_set_.erase(ret.first, ret.second);
-      }
       intptr_t size = raw_obj->Size();
       intptr_t cid = raw_obj->GetClassId();
       ClassTable* class_table = isolate()->class_table();
       // Check whether object should be promoted.
       if (scavenger_->survivor_end_ <= raw_addr) {
         // Not a survivor of a previous scavenge. Just copy the object into the
         // to space.
         new_addr = scavenger_->TryAllocate(size);
         class_table->UpdateLiveNew(cid, size);
       } else {
@@ skipping 37 matching lines @@
       UpdateStoreBuffer(p, new_obj);
     }
   }
 
   Thread* thread_;
   Scavenger* scavenger_;
   SemiSpace* from_;
   Heap* heap_;
   Heap* vm_heap_;
   PageSpace* page_space_;
-  typedef std::multimap<RawObject*, RawWeakProperty*> DelaySet;
-  DelaySet delay_set_;
-  GrowableArray<RawObject*> delayed_weak_stack_;
-  // TODO(cshapiro): use this value to compute survival statistics for
-  // new space growth policy.
+  RawWeakProperty* delayed_weak_properties_;
   intptr_t bytes_promoted_;
   RawObject* visiting_old_object_;
-  bool in_scavenge_pointer_;
+
+  friend class Scavenger;
 
   DISALLOW_COPY_AND_ASSIGN(ScavengerVisitor);
 };
 
 
 class ScavengerWeakVisitor : public HandleVisitor {
  public:
   explicit ScavengerWeakVisitor(Scavenger* scavenger)
       :  HandleVisitor(Thread::Current()),
          scavenger_(scavenger) {
@@ skipping 128 matching lines @@
 }
 
 
 Scavenger::Scavenger(Heap* heap,
                      intptr_t max_semi_capacity_in_words,
                      uword object_alignment)
     : heap_(heap),
       max_semi_capacity_in_words_(max_semi_capacity_in_words),
       object_alignment_(object_alignment),
       scavenging_(false),
+      delayed_weak_properties_(NULL),
       gc_time_micros_(0),
       collections_(0),
       external_size_(0) {
   // Verify assumptions about the first word in objects which the scavenger is
   // going to use for forwarding pointers.
   ASSERT(Object::tags_offset() == 0);
 
   // Set initial size resulting in a total of three different levels.
   const intptr_t initial_semi_capacity_in_words = max_semi_capacity_in_words /
       (FLAG_new_gen_growth_factor * FLAG_new_gen_growth_factor);
@@ skipping 191 matching lines @@
   return true;
 }
 
 
 void Scavenger::IterateWeakRoots(Isolate* isolate, HandleVisitor* visitor) {
   isolate->VisitWeakPersistentHandles(visitor);
 }
 
 
 void Scavenger::ProcessToSpace(ScavengerVisitor* visitor) {
-  GrowableArray<RawObject*>* delayed_weak_stack = visitor->DelayedWeakStack();
-
   // Iterate until all work has been drained.
   while ((resolved_top_ < top_) ||
-         PromotedStackHasMore() ||
-         !delayed_weak_stack->is_empty()) {
+         PromotedStackHasMore()) {
     while (resolved_top_ < top_) {
       RawObject* raw_obj = RawObject::FromAddr(resolved_top_);
       intptr_t class_id = raw_obj->GetClassId();
       if (class_id != kWeakPropertyCid) {
         resolved_top_ += raw_obj->VisitPointers(visitor);
       } else {
         RawWeakProperty* raw_weak = reinterpret_cast<RawWeakProperty*>(raw_obj);
         resolved_top_ += ProcessWeakProperty(raw_weak, visitor);
       }
     }
     {
+      // Visit all the promoted objects and update/scavenge their internal
+      // pointers. Potentially this adds more objects to the to space.
       while (PromotedStackHasMore()) {
         RawObject* raw_object = RawObject::FromAddr(PopFromPromotedStack());
         // Resolve or copy all objects referred to by the current object. This
         // can potentially push more objects on this stack as well as add more
         // objects to be resolved in the to space.
         ASSERT(!raw_object->IsRemembered());
         visitor->VisitingOldObject(raw_object);
         raw_object->VisitPointers(visitor);
       }
       visitor->VisitingOldObject(NULL);
     }
-    while (!delayed_weak_stack->is_empty()) {
-      // Pop the delayed weak object from the stack and visit its pointers.
-      RawObject* weak_property = delayed_weak_stack->RemoveLast();
-      weak_property->VisitPointers(visitor);
+    {
+      // Finished this round of scavenging. Process the pending weak properties
+      // for which the keys have become reachable. Potentially this adds more
+      // objects to the to space.
+      RawWeakProperty* cur_weak = delayed_weak_properties_;
+      delayed_weak_properties_ = NULL;
+      while (cur_weak != NULL) {
+        uword next_weak = cur_weak->ptr()->next_;
+        // Promoted weak properties are not enqueued. So we can guarantee that
+        // we do not need to think about store barriers here.
+        ASSERT(cur_weak->IsNewObject());
+        RawObject* raw_key = cur_weak->ptr()->key_;
+        ASSERT(raw_key->IsHeapObject());
+        // Key still points into from space even if the object has been
+        // promoted to old space by now. The key will be updated accordingly
+        // below when VisitPointers is run.
+        ASSERT(raw_key->IsNewObject());
+        uword raw_addr = RawObject::ToAddr(raw_key);
+        ASSERT(visitor->from_->Contains(raw_addr));
+        uword header = *reinterpret_cast<uword*>(raw_addr);
+        // Reset the next pointer in the weak property.
+        cur_weak->ptr()->next_ = 0;
+        if (IsForwarding(header)) {
+          cur_weak->VisitPointers(visitor);
+        } else {
+          EnqueueWeakProperty(cur_weak);
+        }
+        // Advance to next weak property in the queue.
+        cur_weak = reinterpret_cast<RawWeakProperty*>(next_weak);
+      }
     }
   }
 }
 
 
 void Scavenger::UpdateMaxHeapCapacity() {
   if (heap_ == NULL) {
     // Some unit tests.
     return;
   }
@@ skipping 12 matching lines @@
     return;
   }
   ASSERT(to_ != NULL);
   ASSERT(heap_ != NULL);
   Isolate* isolate = heap_->isolate();
   ASSERT(isolate != NULL);
   isolate->GetHeapNewUsedMaxMetric()->SetValue(UsedInWords() * kWordSize);
 }
 
 
+void Scavenger::EnqueueWeakProperty(RawWeakProperty* raw_weak) {
+  ASSERT(raw_weak->IsHeapObject());
+  ASSERT(raw_weak->IsNewObject());
+  ASSERT(raw_weak->IsWeakProperty());
+  DEBUG_ONLY(
+      uword raw_addr = RawObject::ToAddr(raw_weak);
+      uword header = *reinterpret_cast<uword*>(raw_addr);
+      ASSERT(!IsForwarding(header));
+  )
+  ASSERT(raw_weak->ptr()->next_ == 0);
+  raw_weak->ptr()->next_ = reinterpret_cast<uword>(delayed_weak_properties_);
+  delayed_weak_properties_ = raw_weak;
+}
+
+
 uword Scavenger::ProcessWeakProperty(RawWeakProperty* raw_weak,
                                      ScavengerVisitor* 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->IsNewObject()) {
     uword raw_addr = RawObject::ToAddr(raw_key);
     uword header = *reinterpret_cast<uword*>(raw_addr);
     if (!IsForwarding(header)) {
-      // Key is white.  Delay the weak property.
-      visitor->DelayWeakProperty(raw_weak);
+      // Key is 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(visitor);
 }
 
 
-void Scavenger::ProcessWeakTables() {
+void Scavenger::ProcessWeakReferences() {
+  // Rehash the weak tables now that we know which objects survive this cycle.
   for (int sel = 0;
        sel < Heap::kNumWeakSelectors;
        sel++) {
     WeakTable* table = heap_->GetWeakTable(
         Heap::kNew, static_cast<Heap::WeakSelector>(sel));
     heap_->SetWeakTable(Heap::kNew,
                         static_cast<Heap::WeakSelector>(sel),
                         WeakTable::NewFrom(table));
     intptr_t size = table->size();
     for (intptr_t i = 0; i < size; i++) {
       if (table->IsValidEntryAt(i)) {
         RawObject* raw_obj = table->ObjectAt(i);
         ASSERT(raw_obj->IsHeapObject());
         uword raw_addr = RawObject::ToAddr(raw_obj);
         uword header = *reinterpret_cast<uword*>(raw_addr);
         if (IsForwarding(header)) {
           // The object has survived.  Preserve its record.
           uword new_addr = ForwardedAddr(header);
           raw_obj = RawObject::FromAddr(new_addr);
           heap_->SetWeakEntry(raw_obj,
                               static_cast<Heap::WeakSelector>(sel),
                               table->ValueAt(i));
         }
       }
     }
     // Remove the old table as it has been replaced with the newly allocated
     // table above.
     delete table;
   }
+
+  // The queued weak properties at this point do not refer to reachable keys,
+  // so we clear their key and value fields.
+  {
+    RawWeakProperty* cur_weak = delayed_weak_properties_;
+    delayed_weak_properties_ = NULL;
+    while (cur_weak != NULL) {
+      uword next_weak = cur_weak->ptr()->next_;
+      // Reset the next pointer in the weak property.
+      cur_weak->ptr()->next_ = 0;
+
+      DEBUG_ONLY(
+          RawObject* raw_key = cur_weak->ptr()->key_;
+          uword raw_addr = RawObject::ToAddr(raw_key);
+          uword header = *reinterpret_cast<uword*>(raw_addr);
+          ASSERT(!IsForwarding(header));
+          ASSERT(raw_key->IsHeapObject());
+          ASSERT(raw_key->IsNewObject());  // Key still points into from space.
+      )
+
+      WeakProperty::Clear(cur_weak);
+
+      // Advance to next weak property in the queue.
+      cur_weak = reinterpret_cast<RawWeakProperty*>(next_weak);
+    }
+  }
 }
 
 
 void Scavenger::VisitObjectPointers(ObjectPointerVisitor* visitor) const {
   uword cur = FirstObjectStart();
   while (cur < top_) {
     RawObject* raw_obj = RawObject::FromAddr(cur);
     cur += raw_obj->VisitPointers(visitor);
   }
 }
@@ skipping 68 matching lines @@
     StackZone zone(Thread::Current());
     // Setup the visitor and run the scavenge.
     ScavengerVisitor visitor(isolate, this, from);
     page_space->AcquireDataLock();
     IterateRoots(isolate, &visitor);
     int64_t start = OS::GetCurrentTimeMicros();
     ProcessToSpace(&visitor);
     int64_t middle = OS::GetCurrentTimeMicros();
     ScavengerWeakVisitor weak_visitor(this);
     IterateWeakRoots(isolate, &weak_visitor);
-    visitor.Finalize();
-    ProcessWeakTables();
+    ProcessWeakReferences();
     page_space->ReleaseDataLock();
 
     // Scavenge finished. Run accounting.
     int64_t end = OS::GetCurrentTimeMicros();
     heap_->RecordTime(kProcessToSpace, middle - start);
     heap_->RecordTime(kIterateWeaks, end - middle);
     stats_history_.Add(
         ScavengeStats(start, end,
                       usage_before, GetCurrentUsage(),
                       promo_candidate_words,
@@ skipping 55 matching lines @@
 }
 
 
 void Scavenger::FreeExternal(intptr_t size) {
   ASSERT(size >= 0);
   external_size_ -= size;
   ASSERT(external_size_ >= 0);
 }
 
 }  // namespace dart