Add a weak property type to the virtual machine.

Add a weak property type to the virtual machine.

Weak properties are key-value pairs.  The liveness of the key determines
the liveness of the value.  If the key is reachable the value is traced.
However, if the key is unreachable, the value is subject to finalization.

At present, the sole finalization action is clearing the key and value
fields.  However, it is possible to extend this to invoking callbacks or
other techniques, as well as processing values in topological order.

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

[turnidge, 2012-08-09 18:34:34]

I like the change.  Some comments below.

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

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:7: #include <map>
Do we get to use stl now?  That's helpful.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:152: }
So what we are implementing here is a map from Key to a list of RawWeakProperty
objects (where the list is implemented using the next_ field), right?  We make
sure that we only set the mark on the key once, but then we push all of the
associated WeakProperties onto a stack.

Did you consider dropping the next_ field from RawWeakProperty and just making
it an explicit map from key to list?  It would save a word per RawWeakProperty,
since the next_ field is only used during GC.  This may just be premature
optimization, since there won't be so many RawWeakProperties kicking around, but
wanted to discuss it.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:180: while (raw_weak != WeakProperty::null()) {
Is there are reason that you use WeakProperty::Pop during Finalize but not here?

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:11215: space);
Just to double-check, does Object::Allocate set (key/value/next) to null?

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:11224: return "WeakProperty";
A thought: you could make the ToCString have some info about the key and the
value.  Your call.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.h
File runtime/vm/object.h (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.h#newcode...
runtime/vm/object.h:5382: static void Clear(RawWeakProperty* raw_weak) {
These static functions (Clear/Pop/Push) all are exceptional, in that they take a
Raw type as an argument.  We try not to do this in general, right?  I'm guessing
you are safe since these are really part of the GC implementation.

Would it make sense to move these three functions from WeakProperty to
RawWeakProperty?  That puts them more out of harm's way.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.h#newcode...
runtime/vm/object.h:5387: static RawWeakProperty* Pop(RawWeakProperty** queue) {
Not sure if this is technically a 'queue'.  Seems like its LIFO.  Seems like it
doesn't matter much though.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object_test.cc
File runtime/vm/object_test.cc (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object_test.cc#n...
runtime/vm/object_test.cc:2872: TEST_CASE(WeakProperty_PreserveOne_NewSpace) {
Tests look good to me.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/raw_object.h
File runtime/vm/raw_object.h (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/raw_object.h#new...
runtime/vm/raw_object.h:1529: RawWeakProperty* next_;  // This field is owned by
the garbage collector.
Even more, it is only used during garbage collection.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/scavenger.cc
File runtime/vm/scavenger.cc (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/scavenger.cc#new...
runtime/vm/scavenger.cc:68: void DelayWeakProperty(RawWeakProperty* raw_weak) {
It's a shame about the code duplication between here and gc_marker.cc.  Is this
common for these files?  Is there any simple way to share the code?

I'm pondering whether there could be a WeakPropertyTracker (or whatever) object
that allows you to Process(prop, visitor) and Finalize() that you could use in
each file.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/scavenger.cc#new...
runtime/vm/scavenger.cc:132: while (raw_weak != WeakProperty::null()) {
Ditto comment in other file regarding "Pop".

[Ivan Posva, 2012-08-14 00:26:39]

https://chromiumcodereview.appspot.com/10832199/diff/5001/runtime/vm/raw_obje...
File runtime/vm/raw_object.h (right):

https://chromiumcodereview.appspot.com/10832199/diff/5001/runtime/vm/raw_obje...
runtime/vm/raw_object.h:188: kWatchedBit = 4,
I was wondering whether you considered using the kFreeBit as this watched bit is
only used during marking and reset before sweeping. By definition you will not
be able to reach free objects, so you should be able to reuse that bit location.

[cshapiro, 2012-08-14 04:58:18]

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

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:152: }
I am now using a multimap instead of a map.  As such, the next_ field and the
Push and Pop methods are gone.  Done!

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/gc_marker.cc#new...
runtime/vm/gc_marker.cc:180: while (raw_weak != WeakProperty::null()) {
That was an oversight.  This has been superseded by the use of a multimap.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:11215: space);
Yes, it should.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:11224: return "WeakProperty";
Yes, I could although I cannot think of anything now.  Let me know if I am
missing something obvious.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.h
File runtime/vm/object.h (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.h#newcode...
runtime/vm/object.h:5382: static void Clear(RawWeakProperty* raw_weak) {
Removed.  Done.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object.h#newcode...
runtime/vm/object.h:5387: static RawWeakProperty* Pop(RawWeakProperty** queue) {
True.  This method has been removed.  Done.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object_test.cc
File runtime/vm/object_test.cc (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/object_test.cc#n...
runtime/vm/object_test.cc:2872: TEST_CASE(WeakProperty_PreserveOne_NewSpace) {
Thanks!

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/raw_object.h
File runtime/vm/raw_object.h (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/raw_object.h#new...
runtime/vm/raw_object.h:188: kWatchedBit = 4,
This might be strictly true in old space but the usage of the free bit and the
watched bit overlaps in new space.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/raw_object.h#new...
runtime/vm/raw_object.h:1529: RawWeakProperty* next_;  // This field is owned by
the garbage collector.
Yes.  Removed.

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/scavenger.cc
File runtime/vm/scavenger.cc (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/scavenger.cc#new...
runtime/vm/scavenger.cc:68: void DelayWeakProperty(RawWeakProperty* raw_weak) {
Most of the supporting methods are now gone.  Can you think of a simplification?
 Ideally, more of this code would be shared i.e. the whole scavenge visitor
could be used by the marker as well.  We should look at this together...

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/scavenger.cc#new...
runtime/vm/scavenger.cc:132: while (raw_weak != WeakProperty::null()) {
Yup.  Done.

[Ivan Posva, 2012-08-14 15:23:36]

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/raw_object.h
File runtime/vm/raw_object.h (right):

http://codereview.chromium.org/10832199/diff/5001/runtime/vm/raw_object.h#new...
runtime/vm/raw_object.h:188: kWatchedBit = 4,
On 2012/08/14 04:58:18, cshapiro wrote:
> This might be strictly true in old space but the usage of the free bit and the
> watched bit overlaps in new space.  

We can consolidate the bits later, I was under the impression that I had changed
the scavenger to use the mark bit as well. Apparently not...

[turnidge, 2012-08-16 23:31:46]

lgtm, one small comment.

https://chromiumcodereview.appspot.com/10832199/diff/5003/runtime/vm/scavenge...
File runtime/vm/scavenger.cc (right):

https://chromiumcodereview.appspot.com/10832199/diff/5003/runtime/vm/scavenge...
runtime/vm/scavenger.cc:125: if (raw_obj->IsWatched()) {
Comment here and in similar point in other file -- equal_range is not familiar
to me and probably others.