Implement weak references sets and provide an embedding API.

Implement weak references sets and provide an embedding API.

Weak reference sets are similar to "populations" or "weak pairs".
Like these structures, objects in a key set preserve members of an
associated value set.  Unlike these structures, a weak reference set
is not a general associative container.  Weak reference sets exist
for the duration of a garbage collection.

Weak reference sets are proceesed iteratively allowing values of one
weak reference to be keys of a other weak reference sets.  The garbage
collector will process weak reference sets iteratively, revisiting all
unmarked weak reference sets if any one weak reference set is marked.
This process repeates until a fixed-point is reached.

Committed: https://code.google.com/p/dart/source/detail?r=4917

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

LGTM with some comments.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
File runtime/vm/dart_api_impl_test.cc (right):

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
runtime/vm/dart_api_impl_test.cc:1539: EXPECT(Dart_IsNull(weak4));
weak3 and weak4 were already NULL before this test, how do we know that this
test cleared them?

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
runtime/vm/dart_api_impl_test.cc:1553: // No weak references should be
preserved.
Why should weak2, weak3 and weak4 not be preserved?

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
runtime/vm/dart_api_impl_test.cc:1557: EXPECT(Dart_IsNull(weak4));
I am little confused here, weak3, weak4, weak2 were already cleared in the
previous set, you did not restore weak2, weak3 and weak4 before this test, so
how can we be sure that this test actually cleared the weak references?

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h
File runtime/vm/dart_api_state.h (right):

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:361: WeakReference* next() { return next_; }
next() const { ... }

Ditto comment for other accessors in this class.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:362: void set_next(WeakReference* next) { next_ =
next; }
Do next and set_next have to be part of the public API? It looks like you are
only using Pop and Push to access the queue.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:378: static WeakReference* Pop(WeakReference**
queue) {
ASSERT(queue != NULL);

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:387: static void Push(WeakReference* reference,
WeakReference** queue) {
ASSERT(queue != NULL);
ASSERT(reference != NULL);

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:198: return !raw_obj->IsMarked();
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.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:245: state->set_delayed_weak_references(NULL);
This setting could be moved after the 'if (queue != NULL)' check.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:247: break;
Could we return right here, instead of breaking out and repeating the check
again?

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

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
File runtime/vm/dart_api_impl_test.cc (right):

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
runtime/vm/dart_api_impl_test.cc:1539: EXPECT(Dart_IsNull(weak4));
Yes, weak3 and weak4 were null before the GC on line 1532.  They should stay
that way, which is all I am validating.

There is always a possibility of resurrecting values with algorithms like these
so I am ensuring they are still dead.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
runtime/vm/dart_api_impl_test.cc:1553: // No weak references should be
preserved.
The are still null so they should remain null.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_impl_tes...
runtime/vm/dart_api_impl_test.cc:1557: EXPECT(Dart_IsNull(weak4));
Let me add some comments and see if that makes the intent more clear.  Each of
these tests is not supposed to be stand alone, I'm just decaying the number of
live objects each GC.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h
File runtime/vm/dart_api_state.h (right):

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:361: WeakReference* next() { return next_; }
Right.  Done.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:362: void set_next(WeakReference* next) { next_ =
next; }
Done.

In fact, I added this method before I had Push and Pop.  It has not been needed
since and I should have GCed it.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:378: static WeakReference* Pop(WeakReference**
queue) {
Done.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/dart_api_state.h#...
runtime/vm/dart_api_state.h:387: static void Push(WeakReference* reference,
WeakReference** queue) {
Also done.  Thanks!

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:198: return !raw_obj->IsMarked();
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.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:245: state->set_delayed_weak_references(NULL);
True.  I'll do that.

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:247: break;
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:41]

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc
File runtime/vm/gc_marker.cc (right):

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:243: for (;;) {
while (true) {

http://codereview.chromium.org/9531001/diff/2001/runtime/vm/gc_marker.cc#newc...
runtime/vm/gc_marker.cc:247: break;
On 2012/03/03 00:03:23, cshapiro wrote:
> 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.

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.