Implement a 2-pass heap verification algorithm.

Implement a 2-pass heap verification algorithm.

The previous algorithm would visit each pointer in the heap and verify it
without regard for whether the pointer had already been visited.

The new algorithm computes the set of allocated objects and verifies each
object in the set.  In a second pass, each pointer is visited and tested
for membership in the set.

BUG=2606
Committed: https://code.google.com/p/dart/source/detail?r=9532

[cshapiro, 2012-06-28 05:07:39]

I have yet to finish running my benchmark (verify takes forever on the old
algorithm) but it seems that the new algorithm is 2-3 orders of magnitude faster
than the old.

[Ivan Posva, 2012-06-29 22:20:41]

Cosmetic comments only. At least the major ones should be addressed, otherwise
LGTM.

-Ivan

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.cc
File runtime/vm/heap.cc (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.cc#...
runtime/vm/heap.cc:257: ObjectSet* Heap::GetAllocatedObjects() const {
GenerateAllocatedObjectSet or similar to indicate that we need to do work to
fill out this set. Get sounds too much like it is premade already.

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.h
File runtime/vm/heap.h (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.h#n...
runtime/vm/heap.h:84: void VisitObjects(ObjectVisitor* visitor);
It is unclear why these are named different. We already have IterateXObjects and
IterateXPointers. We should move these down next to them and name them
consistently.

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/object_s...
File runtime/vm/object_set.h (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/object_s...
runtime/vm/object_set.h:54: uword start_;
start_, end_ and to some extent size_ are only needed for debugging, can we
separate them out from data_ and allocation_ which are essentially equivalent
with both of them pointing into the "same" memory.

Short comments explaining what all of these fields are your be nice.

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/scavenger.h
File runtime/vm/scavenger.h (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/scavenge...
runtime/vm/scavenger.h:77: void StartEndAddress(uword* start, uword* end) const
{
The more I read this name the more I am convinced that could be a better name,
alas I do not have a better solution at this time.

[cshapiro, 2012-07-10 21:48:17]

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.cc
File runtime/vm/heap.cc (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.cc#...
runtime/vm/heap.cc:257: ObjectSet* Heap::GetAllocatedObjects() const {
That is reasonable.  Renamed.  Done.

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.h
File runtime/vm/heap.h (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/heap.h#n...
runtime/vm/heap.h:84: void VisitObjects(ObjectVisitor* visitor);
VisitObjects -> IterateObjects
VisitObjectPointers -> IteratePointers

Each signature is above the space-specific iterators for the sake of
consistency.

Done.

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/object_s...
File runtime/vm/object_set.h (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/object_s...
runtime/vm/object_set.h:54: uword start_;
I have sorted these fields in a (hopefully) more logical order.  Also, comments
have been added.  Done.

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/scavenger.h
File runtime/vm/scavenger.h (right):

https://chromiumcodereview.appspot.com/10696029/diff/3001/runtime/vm/scavenge...
runtime/vm/scavenger.h:77: void StartEndAddress(uword* start, uword* end) const
{
Yeah, I agree.  It's kind of wonky.  I am happy to rename this if we can think
of something better.

[Ivan Posva, 2012-07-10 22:01:36]

Still LGTM. -ip