- 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);

[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) {
     isolate->gc_epilogue_callbacks().Invoke();
   }
 }
 
 
 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);
 }
 
 
 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