- Start using the collected store buffer entries to find

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 "vm/dart.h"
 #include "vm/dart_api_state.h"
 #include "vm/isolate.h"
 #include "vm/object.h"
 #include "vm/stack_frame.h"
+#include "vm/store_buffer.h"
 #include "vm/verifier.h"
 #include "vm/visitor.h"
 
 namespace dart {
 
 // Scavenger uses RawObject::kFreeBit to distinguish forwaded and non-forwarded
 // objects because scavenger can never encounter free list element during
 // evacuation and thus all objects scavenger encounters have
 // kFreeBit cleared.
 enum {
@@ skipping 22 matching lines @@
   *reinterpret_cast<uword*>(orignal) = target | kForwarded;
 }
 
 
 class ScavengerVisitor : public ObjectPointerVisitor {
  public:
   explicit ScavengerVisitor(Isolate* isolate, Scavenger* scavenger)
       : ObjectPointerVisitor(isolate),
         scavenger_(scavenger),
         heap_(scavenger->heap_),
-        vm_heap_(Dart::vm_isolate()->heap()) {}
+        vm_heap_(Dart::vm_isolate()->heap()),
+        visiting_old_pointers_(false) {}
 
   void VisitPointers(RawObject** first, RawObject** last) {
     for (RawObject** current = first; current <= last; current++) {
       ScavengePointer(current);
     }
   }
 
+  void VisitingOldPointers(bool value) { visiting_old_pointers_ = value; }
+
  private:
   void UpdateStoreBuffer(RawObject** p, RawObject* obj) {
-    // TODO(iposva): Implement store buffers.
+    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()) return;
+    isolate()->store_buffer()->AddPointer(ptr);
   }
 
   void ScavengePointer(RawObject** p) {
     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;
     }
 
@@ skipping 45 matching lines @@
       memmove(reinterpret_cast<void*>(new_addr),
               reinterpret_cast<void*>(raw_addr),
               size);
       // Remember forwarding address.
       ForwardTo(raw_addr, new_addr);
     }
     // Update the reference.
     RawObject* new_obj = RawObject::FromAddr(new_addr);
     *p = new_obj;
     // Update the store buffer as needed.
-    UpdateStoreBuffer(p, new_obj);
+    if (visiting_old_pointers_) {
+      UpdateStoreBuffer(p, new_obj);
+    }
   }
 
   Scavenger* scavenger_;
   Heap* heap_;
   Heap* vm_heap_;
 
+  bool visiting_old_pointers_;
+
   DISALLOW_COPY_AND_ASSIGN(ScavengerVisitor);
 };
 
 
 class ScavengerWeakVisitor : public HandleVisitor {
  public:
   explicit ScavengerWeakVisitor(Scavenger* scavenger) : scavenger_(scavenger) {
   }
 
   void VisitHandle(uword addr) {
     FinalizablePersistentHandle* handle =
         reinterpret_cast<FinalizablePersistentHandle*>(addr);
     RawObject** p = reinterpret_cast<RawObject**>(handle);
     if (scavenger_->IsUnreachable(p)) {
       FinalizablePersistentHandle::Finalize(handle);
     }
   }
 
  private:
   Scavenger* scavenger_;
 
   DISALLOW_COPY_AND_ASSIGN(ScavengerWeakVisitor);
 };
 
 
+// Visitor used to verify that all old->new references have been added to the
+// StoreBuffers.
+class VerifyStoreBufferPointerVisitor : public ObjectPointerVisitor {
+ public:
+  VerifyStoreBufferPointerVisitor(Isolate* isolate, MemoryRegion* to)
+      : ObjectPointerVisitor(isolate), to_(to) {}
+
+  void VisitPointers(RawObject** first, RawObject** last) {
+    for (RawObject** current = first; current <= last; current++) {
+      RawObject* obj = *current;
+      if (obj->IsHeapObject() && obj->IsNewObject()) {
+        ASSERT(to_->Contains(RawObject::ToAddr(obj)));
+      }
+    }
+  }
+
+ private:
+  MemoryRegion* to_;
+
+  DISALLOW_COPY_AND_ASSIGN(VerifyStoreBufferPointerVisitor);
+};
+
+
 Scavenger::Scavenger(Heap* heap, intptr_t max_capacity, uword object_alignment)
     : heap_(heap),
       object_alignment_(object_alignment),
       count_(0),
       scavenging_(false) {
   // Verify assumptions about the first word in objects which the scavenger is
   // going to use for forwarding pointers.
   ASSERT(Object::tags_offset() == 0);
   ASSERT(kForwardingMask == (1 << RawObject::kFreeBit));
 
@@ skipping 50 matching lines @@
   end_ = to_->end();
 }
 
 
 void Scavenger::Epilogue(Isolate* isolate, bool invoke_api_callbacks) {
   // All objects in the to space have been copied from the from space at this
   // moment.
   survivor_end_ = top_;
 
 #if defined(DEBUG)
+  VerifyStoreBufferPointerVisitor verify_store_buffer_visitor(isolate, to_);
+  heap_->IterateOldPointers(&verify_store_buffer_visitor);
+
   memset(from_->pointer(), 0xf3, from_->size());
 #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);
+  // 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;
+    entries += count;
+    for (intptr_t i = 0; i < size; i++) {
+      RawObject** pointer = reinterpret_cast<RawObject**>(set->At(i));
+      if (pointer != NULL) {
+        RawObject* value = *pointer;
+        // Skip entries that have been overwritten with Smis.
+        if (value->IsHeapObject()) {
+          if (from_->Contains(RawObject::ToAddr(value))) {
+            visitor->VisitPointer(pointer);
+          } else {
+            duplicates++;
+          }
+        }
+        handled++;
+        if (handled == count) {
+          break;
+        }
+      }
+    }
+    delete pending;
+    pending = next;
+  }
+  if (FLAG_verbose_gc) {
+    OS::PrintErr("StoreBuffer: %d, %d (entries, dups)\n",
+                 entries, duplicates);
+  }
+  StoreBufferBlock* block = isolate->store_buffer_block();
+  entries = block->Count();
+  duplicates = 0;
+  for (intptr_t i = 0; i < entries; i++) {
+    RawObject** pointer = reinterpret_cast<RawObject**>(block->At(i));
+    if (from_->Contains(RawObject::ToAddr(*pointer))) {
+      visitor->VisitPointer(pointer);
+    } else {
+      duplicates++;
+    }
+  }
+  block->Reset();
+  if (FLAG_verbose_gc) {
+    OS::PrintErr("StoreBufferBlock: %d, %d (entries, dups)\n",
+                 entries, duplicates);
+  }
+  // Done iterating through the store buffers.
+  visitor->VisitingOldPointers(false);
+}
+
+
 void Scavenger::IterateRoots(Isolate* isolate,
-                             ObjectPointerVisitor* visitor,
+                             ScavengerVisitor* visitor,
                              bool visit_prologue_weak_persistent_handles) {
+  IterateStoreBuffers(isolate, visitor);
   isolate->VisitObjectPointers(visitor,
                                visit_prologue_weak_persistent_handles,
                                StackFrameIterator::kDontValidateFrames);
-  heap_->IterateOldPointers(visitor);
 }
 
 
 bool Scavenger::IsUnreachable(RawObject** p) {
   RawObject* raw_obj = *p;
   if (!raw_obj->IsHeapObject()) {
     return false;
   }
   if (!raw_obj->IsNewObject()) {
     return false;
   }
   uword raw_addr = RawObject::ToAddr(raw_obj);
   if (!from_->Contains(raw_addr)) {
     return false;
   }
   uword header = *reinterpret_cast<uword*>(raw_addr);
   if (IsForwarding(header)) {
     uword new_addr = ForwardedAddr(header);
     *p = RawObject::FromAddr(new_addr);
     return false;
   }
   return true;
 }
 
 
 void Scavenger::IterateWeakReferences(Isolate* isolate,
-                                      ObjectPointerVisitor* visitor) {
+                                      ScavengerVisitor* visitor) {
   ApiState* state = isolate->api_state();
   ASSERT(state != NULL);
   while (true) {
     WeakReference* queue = state->delayed_weak_references();
     if (queue == NULL) {
       // The delay queue is empty therefore no clean-up is required.
       return;
     }
     state->set_delayed_weak_references(NULL);
     while (queue != NULL) {
@@ skipping 38 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(ObjectPointerVisitor* visitor) {
+void Scavenger::ProcessToSpace(ScavengerVisitor* visitor) {
   // Iterate until all work has been drained.
   while ((resolved_top_ < top_) || PromotedStackHasMore()) {
     while (resolved_top_ < top_) {
       RawObject* raw_obj = RawObject::FromAddr(resolved_top_);
       resolved_top_ += raw_obj->VisitPointers(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);
     }
+    visitor->VisitingOldPointers(false);
   }
 }
 
 
 void Scavenger::VisitObjectPointers(ObjectPointerVisitor* visitor) const {
   uword cur = FirstObjectStart();
   while (cur < top_) {
     RawObject* raw_obj = RawObject::FromAddr(cur);
     cur += raw_obj->VisitPointers(visitor);
   }
@@ skipping 24 matching lines @@
   had_promotion_failure_ = false;
   Isolate* isolate = Isolate::Current();
   NoHandleScope no_handles(isolate);
 
   if (FLAG_verify_before_gc) {
     OS::PrintErr("Verifying before Scavenge...");
     heap_->Verify();
     OS::PrintErr(" done.\n");
   }
 
+  if (FLAG_verbose_gc) {
+    OS::PrintErr("Start scavenge\n");
+  }
   Timer timer(FLAG_verbose_gc, "Scavenge");
   timer.Start();
   // Setup the visitor and run a scavenge.
   ScavengerVisitor visitor(isolate, this);
   Prologue(isolate, invoke_api_callbacks);
   IterateRoots(isolate, &visitor, !invoke_api_callbacks);
   ProcessToSpace(&visitor);
   IterateWeakReferences(isolate, &visitor);
   ScavengerWeakVisitor weak_visitor(this);
   IterateWeakRoots(isolate, &weak_visitor, invoke_api_callbacks);
   Epilogue(isolate, invoke_api_callbacks);
   timer.Stop();
   if (FLAG_verbose_gc) {
     OS::PrintErr("Scavenge[%d]: %dus\n", count_, timer.TotalElapsedTime());
   }
 
   if (FLAG_verify_after_gc) {
     OS::PrintErr("Verifying after Scavenge...");
     heap_->Verify();
     OS::PrintErr(" done.\n");
   }
 
   count_++;
   // Done scavenging. Reset the marker.
   ASSERT(scavenging_);
   scavenging_ = false;
 }
 
 }  // namespace dart