Implement weak references sets and provide an embedding API.

runtime/vm/gc_marker.cc

Index: runtime/vm/gc_marker.cc
diff --git a/runtime/vm/gc_marker.cc b/runtime/vm/gc_marker.cc
index 62f1f3a0267c4dbc75ab3c73d6966680556e7707..7dec9604aca2bc45fd27d453946907eb27d179c2 100644
--- a/runtime/vm/gc_marker.cc
+++ b/runtime/vm/gc_marker.cc
@@ -188,6 +188,17 @@ class MarkingVisitor : public ObjectPointerVisitor {
 };
 
 
+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() {
@@ -197,8 +208,7 @@ class MarkingWeakVisitor : public HandleVisitor {
     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);
     }
   }
@@ -226,6 +236,57 @@ void GCMarker::IterateWeakRoots(Isolate* isolate, HandleVisitor* 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()) {
@@ -241,6 +302,7 @@ void GCMarker::MarkObjects(Isolate* isolate, PageSpace* page_space) {
   MarkingVisitor mark(heap_, page_space, &marking_stack);
   IterateRoots(isolate, &mark);
   DrainMarkingStack(isolate, &mark);
+  IterateWeakReferences(isolate, &mark);
   MarkingWeakVisitor mark_weak;
   IterateWeakRoots(isolate, &mark_weak);
 }