Implement weak references sets and provide an embedding API.

runtime/vm/gc_marker.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/gc_marker.h"
 
 #include "vm/allocation.h"
 #include "vm/dart_api_state.h"
 #include "vm/isolate.h"
 #include "vm/pages.h"
@@ skipping 170 matching lines @@
 
   Heap* heap_;
   Heap* vm_heap_;
   PageSpace* page_space_;
   MarkingStack* marking_stack_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(MarkingVisitor);
 };
 
 
+bool IsUnreachable(const RawObject* raw_obj) {
+  if (!raw_obj->IsHeapObject()) {
+    return false;
+  }
+  if (!raw_obj->IsOldObject()) {
+    return false;
+  }
+  return !raw_obj->IsMarked();

[siva, 2012/03/02 18:30:33]

Not sure if it matters but this seems slightly more expensive than the old code,
which was checking for IsOldObject only if the object was not marked.

[cshapiro, 2012/03/03 00:03:23]

I think this ordering is preferable as IsMarked() requires the object header to
be loaded whereas the IsHeapObject() and IsOldObject() check operate on the
pointer.  With this ordering, we exhaust the "edge" checks before doing the
potentially more costly "node" check.

+}
+
+
 class MarkingWeakVisitor : public HandleVisitor {
  public:
   MarkingWeakVisitor() {
   }
 
   void VisitHandle(uword addr) {
     WeakPersistentHandle* handle =
         reinterpret_cast<WeakPersistentHandle*>(addr);
     RawObject* raw_obj = handle->raw();
-    if (!raw_obj->IsHeapObject()) return;
-    if (!raw_obj->IsMarked() && raw_obj->IsOldObject()) {
+    if (IsUnreachable(raw_obj)) {
       WeakPersistentHandle::Finalize(handle);
     }
   }
 
  private:
   DISALLOW_COPY_AND_ASSIGN(MarkingWeakVisitor);
 };
 
 
 void GCMarker::Prologue(Isolate* isolate) {
   // Nothing to do at the moment.
 }
 
 
 void GCMarker::IterateRoots(Isolate* isolate, ObjectPointerVisitor* visitor) {
   isolate->VisitObjectPointers(visitor,
                                StackFrameIterator::kDontValidateFrames);
   heap_->IterateNewPointers(visitor);
   heap_->IterateCodePointers(visitor);
 }
 
 
 void GCMarker::IterateWeakRoots(Isolate* isolate, HandleVisitor* visitor) {
   isolate->VisitWeakPersistentHandles(visitor);
 }
 
 
+void GCMarker::IterateWeakReferences(Isolate* isolate,
+                                     MarkingVisitor* visitor) {
+  ApiState* state = isolate->api_state();
+  ASSERT(state != NULL);
+  for (;;) {

[Ivan Posva, 2012/03/05 19:04:42]

while (true) {

+    WeakReference* queue = state->delayed_weak_references();
+    state->set_delayed_weak_references(NULL);

[siva, 2012/03/02 18:30:33]

This setting could be moved after the 'if (queue != NULL)' check.

[cshapiro, 2012/03/03 00:03:23]

True.  I'll do that.

+    if (queue == NULL) {
+      break;

[siva, 2012/03/02 18:30:33]

Could we return right here, instead of breaking out and repeating the check
again?

[cshapiro, 2012/03/03 00:03:23]

Probably not as that would cause a space leak.  The "queue" variable is a copy
of the delay queue head.  After setting the delay queue head in the ApiState to
NULL on 245 we may have delayed a weak reference set in an intervening iteration
of the for loop. As such, state->delayed_weak_references() may not be NULL.  The
cleanup loop below is required to delete these objects.

[Ivan Posva, 2012/03/05 19:04:42]

I am not quite sure I follow your argument here. If you break out of the loop at
243 here, then the result of the check on 280 is guaranteed to be false as you
just set the delayed weak references to null at 245.

+    }
+    while (queue != NULL) {
+      WeakReference* reference = WeakReference::Pop(&queue);
+      ASSERT(reference != NULL);
+      bool is_unreachable = true;
+      // Test each key object for reachability.  If a key object is
+      // reachable, all value objects should be marked.
+      for (intptr_t k = 0; k < reference->num_keys(); ++k) {
+        if (!IsUnreachable(*reference->get_key(k))) {
+          for (intptr_t v = 0; v < reference->num_values(); ++v) {
+            visitor->VisitPointer(reference->get_value(v));
+          }
+          is_unreachable = false;
+          delete reference;
+          break;
+        }
+      }
+      // If all key objects are unreachable put the reference on a
+      // delay queue.  This reference will be revisited if another
+      // reference is marked.
+      if (is_unreachable) {
+        state->DelayWeakReference(reference);
+      }
+    }
+    if (!visitor->marking_stack()->IsEmpty()) {
+      DrainMarkingStack(isolate, visitor);
+    } else {
+      // Break out of the loop if there has been no forward process.
+      break;
+    }
+  }
+  // Deallocate any unmarked references on the delay queue.
+  if (state->delayed_weak_references() != NULL) {
+    WeakReference* queue = state->delayed_weak_references();
+    state->set_delayed_weak_references(NULL);
+    while (queue != NULL) {
+      delete WeakReference::Pop(&queue);
+    }
+  }
+}
+
+
 void GCMarker::DrainMarkingStack(Isolate* isolate,
                                  MarkingVisitor* visitor) {
   while (!visitor->marking_stack()->IsEmpty()) {
     RawObject* raw_obj = visitor->marking_stack()->Pop();
     raw_obj->VisitPointers(visitor);
   }
 }
 
 
 void GCMarker::MarkObjects(Isolate* isolate, PageSpace* page_space) {
   MarkingStack marking_stack;
   Prologue(isolate);
   MarkingVisitor mark(heap_, page_space, &marking_stack);
   IterateRoots(isolate, &mark);
   DrainMarkingStack(isolate, &mark);
+  IterateWeakReferences(isolate, &mark);
   MarkingWeakVisitor mark_weak;
   IterateWeakRoots(isolate, &mark_weak);
 }
 
 }  // namespace dart