- Start using the collected store buffer entries to find

vm/scavenger.cc

Index: vm/scavenger.cc
===================================================================
--- vm/scavenger.cc	(revision 9751)
+++ vm/scavenger.cc	(working copy)
@@ -9,6 +9,7 @@
 #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"
 
@@ -51,7 +52,8 @@
       : 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++) {
@@ -59,9 +61,18 @@
     }
   }
 
+  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) {
@@ -127,13 +138,17 @@
     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);
 };
 
@@ -159,6 +174,29 @@
 };
 
 
+// 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),
@@ -229,6 +267,9 @@
   survivor_end_ = top_;
 
 #if defined(DEBUG)
+  VerifyStoreBufferPointerVisitor verify_store_buffer_visitor(isolate, to_);
+  heap_->IterateOldPointers(&verify_store_buffer_visitor);

[siva, 2012/07/19 17:36:06]

This verification doesn't quite ensure that the store buffers have the correct
data right.

Would it make sense to have a verification step in Scavenger::Prologue which
will iterate old pointers and if it has a new object ensure that it exists in
the store buffer.

[Ivan Posva, 2012/07/20 15:37:46]

Discussed offline: Suggestion would work and has the same effect as the
currently implemented algorithm. The advantage of doing it after the Scavenge is
not having to search in the store buffers.

+
   memset(from_->pointer(), 0xf3, from_->size());
 #endif  // defined(DEBUG)
   if (invoke_api_callbacks) {
@@ -238,12 +279,67 @@
 
 
 void Scavenger::IterateRoots(Isolate* isolate,
-                             ObjectPointerVisitor* visitor,
+                             ScavengerVisitor* visitor,
                              bool visit_prologue_weak_persistent_handles) {
+  // Iterating though the store buffers.

[siva, 2012/07/19 17:36:06]

spelling!!

[Ivan Posva, 2012/07/20 15:37:46]

Done.

+  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++;
+    }
+  }

[siva, 2012/07/19 17:36:06]

Instead of processing this StoreBufferBlock separately here would it make sense
to just call ProcessBuffer at the start of this function (that way all the
duplicates in this block would get deduped) and accounted for in the earlier
loop.

[Ivan Posva, 2012/07/20 15:37:46]

The number of addresses visited here is limited so I would rather keep it as it
is. Also I want to avoid adding more addresses to the dedup sets as growth in
them would trigger the interrupt again.

+  if (FLAG_verbose_gc) {
+    OS::PrintErr("StoreBufferBlock: %d, %d (entries, dups)\n",
+                 entries, duplicates);
+  }
+  // Done iterating through the store buffers.
+  visitor->VisitingOldPointers(false);
+
   isolate->VisitObjectPointers(visitor,
                                visit_prologue_weak_persistent_handles,
                                StackFrameIterator::kDontValidateFrames);
-  heap_->IterateOldPointers(visitor);
 }
 
 
@@ -270,7 +366,7 @@
 
 
 void Scavenger::IterateWeakReferences(Isolate* isolate,
-                                      ObjectPointerVisitor* visitor) {
+                                      ScavengerVisitor* visitor) {
   ApiState* state = isolate->api_state();
   ASSERT(state != NULL);
   while (true) {
@@ -329,13 +425,14 @@
 }
 
 
-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
@@ -343,6 +440,7 @@
       // objects to be resolved in the to space.
       raw_object->VisitPointers(visitor);
     }
+    visitor->VisitingOldPointers(false);
   }
 }
 
@@ -387,6 +485,9 @@
     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.