- Avoid recursion in the scavenger by remembering weak properties

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>
 
@@ skipping 32 matching lines @@
 }
 
 
 static inline void ForwardTo(uword orignal, uword target) {
   // Make sure forwarding can be encoded.
   ASSERT((target & kForwardingMask) == 0);
   *reinterpret_cast<uword*>(orignal) = 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)
       : ObjectPointerVisitor(isolate),
         scavenger_(scavenger),
         heap_(scavenger->heap_),
         vm_heap_(Dart::vm_isolate()->heap()),
-        visiting_old_pointers_(false) {}
+        delayed_weak_stack_(),
+        visiting_old_pointers_(false),
+        in_scavenge_pointer_(false) {}
 
   void VisitPointers(RawObject** first, RawObject** last) {
     for (RawObject** current = first; current <= last; current++) {
       ScavengePointer(current);
     }
   }
 
-  void VisitingOldPointers(bool value) { visiting_old_pointers_ = value; }
+  GrowableArray<RawObject*>* DelayedWeakStack() {
+    return &delayed_weak_stack_;
+  }
+
+  bool* VisitingOldPointersAddr() { return &visiting_old_pointers_; }
 
   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->SetWatchedBit();
     }
@@ skipping 13 matching lines @@
     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()) return;
     isolate()->store_buffer()->AddPointer(ptr);
   }
 
   void ScavengePointer(RawObject** p) {
+    // ScavengePointer cannot be called recursively.
+    ASSERT(!in_scavenge_pointer_);
+    BoolScope bs(&in_scavenge_pointer_, true);
+
     RawObject* raw_obj = *p;
 
     // Fast exit if the raw object is a Smi or an old object.
     if (!raw_obj->IsHeapObject() || raw_obj->IsOldObject()) {
       return;
     }
 
     uword raw_addr = RawObject::ToAddr(raw_obj);
     // Objects should be contained in the heap.
     // TODO(iposva): Add an appropriate assert here or in the return block
     // below.
     // The scavenger is only interested in objects located in the from space.
     if (!scavenger_->from_->Contains(raw_addr)) {
       return;
     }
 
     // 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()) {
-      // Forward the object by scavenging its watchers.
-      raw_obj->ClearWatchedBit();
-      std::pair<DelaySet::iterator, DelaySet::iterator> ret;
-      // Visit all elements with a key equal to raw_obj.
-      ret = delay_set_.equal_range(raw_obj);
-      for (DelaySet::iterator it = ret.first; it != ret.second; ++it) {
-        // Scavenge the delayed WeakProperty.  These objects have been
-        // forwarded but have not been scavenged because their key
-        // object was not known to be reachable.  Now that the key
-        // object is known to be reachable we can scavenge the key and
-        // value pointers.
-        it->second->VisitPointers(this);
+    } else {
+      if (raw_obj->IsWatched()) {
+        raw_obj->ClearWatchedBit();
+        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);
       }
-      delay_set_.erase(ret.first, ret.second);
-      // Reread the header word to get the new location of the object.
-      header = *reinterpret_cast<uword*>(raw_addr);
-      ASSERT(IsForwarding(header));
-      new_addr = ForwardedAddr(header);
-    } else {
       intptr_t size = raw_obj->Size();
       // 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);
       } else {
         // TODO(iposva): Experiment with less aggressive promotion. For example
         // a coin toss determines if an object is promoted or whether it should
         // survive in this generation.
@@ skipping 28 matching lines @@
     if (visiting_old_pointers_) {
       UpdateStoreBuffer(p, new_obj);
     }
   }
 
   Scavenger* scavenger_;
   Heap* heap_;
   Heap* vm_heap_;
   typedef std::multimap<RawObject*, RawWeakProperty*> DelaySet;
   DelaySet delay_set_;
+  GrowableArray<RawObject*> delayed_weak_stack_;
 
   bool visiting_old_pointers_;
+  bool in_scavenge_pointer_;
 
   DISALLOW_COPY_AND_ASSIGN(ScavengerVisitor);
 };
 
 
 class ScavengerWeakVisitor : public HandleVisitor {
  public:
   explicit ScavengerWeakVisitor(Scavenger* scavenger) : scavenger_(scavenger) {
   }
 
@@ skipping 113 matching lines @@
 #endif  // defined(DEBUG)
   if (invoke_api_callbacks) {
     isolate->gc_epilogue_callbacks().Invoke();
   }
 }
 
 
 void Scavenger::IterateStoreBuffers(Isolate* isolate,
                                     ScavengerVisitor* visitor) {
   // Iterating through the store buffers.
-  visitor->VisitingOldPointers(true);
+  BoolScope bs(visitor->VisitingOldPointersAddr(), true);
   // Grab the deduplication sets out of the store buffer.
   StoreBuffer::DedupSet* pending = isolate->store_buffer()->DedupSets();
   intptr_t entries = 0;
   intptr_t duplicates = 0;
   while (pending != NULL) {
     StoreBuffer::DedupSet* next = pending->next();
     HashSet* set = pending->set();
     intptr_t count = set->Count();
     intptr_t size = set->Size();
     intptr_t handled = 0;
@@ skipping 35 matching lines @@
       } else {
         duplicates++;
       }
     }
   }
   block->Reset();
   if (FLAG_verbose_gc) {
     OS::PrintErr("StoreBufferBlock: %"Pd", %"Pd" (entries, dups)\n",
                  entries, duplicates);
   }
-  // Done iterating through the store buffers.
-  visitor->VisitingOldPointers(false);
 }
 
 
 void Scavenger::IterateRoots(Isolate* isolate,
                              ScavengerVisitor* visitor,
                              bool visit_prologue_weak_persistent_handles) {
   IterateStoreBuffers(isolate, visitor);
   isolate->VisitObjectPointers(visitor,
                                visit_prologue_weak_persistent_handles,
                                StackFrameIterator::kDontValidateFrames);
@@ skipping 76 matching lines @@
 
 void Scavenger::IterateWeakRoots(Isolate* isolate,
                                  HandleVisitor* visitor,
                                  bool visit_prologue_weak_persistent_handles) {
   isolate->VisitWeakPersistentHandles(visitor,
                                       visit_prologue_weak_persistent_handles);
 }
 
 
 void Scavenger::ProcessToSpace(ScavengerVisitor* visitor) {
+  GrowableArray<RawObject*>* delayed_weak_stack = visitor->DelayedWeakStack();
+
   // Iterate until all work has been drained.
-  while ((resolved_top_ < top_) || PromotedStackHasMore()) {
+  while ((resolved_top_ < top_) ||
+         PromotedStackHasMore() ||
+         !delayed_weak_stack->is_empty()) {
     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);
       }
     }
-    visitor->VisitingOldPointers(true);
-    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.
-      raw_object->VisitPointers(visitor);
+    {
+      BoolScope bs(visitor->VisitingOldPointersAddr(), true);
+      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.
+        raw_object->VisitPointers(visitor);
+      }
     }
-    visitor->VisitingOldPointers(false);
+    while (!delayed_weak_stack->is_empty()) {
+      // Pop the delayed weak object from the stack and visit its pointers.
+      RawObject* weak_property = delayed_weak_stack->Last();
+      delayed_weak_stack->RemoveLast();
+      weak_property->VisitPointers(visitor);
+    }
   }
 }
 
 
 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);
@@ skipping 122 matching lines @@
   PeerTable::iterator it = peer_table_.find(raw_obj);
   return (it == peer_table_.end()) ? NULL : it->second;
 }
 
 
 int64_t Scavenger::PeerCount() const {
   return static_cast<int64_t>(peer_table_.size());
 }
 
 }  // namespace dart