Implement a 2-pass heap verification algorithm.

runtime/vm/object_set.h

Index: runtime/vm/object_set.h
diff --git a/runtime/vm/object_set.h b/runtime/vm/object_set.h
new file mode 100644
index 0000000000000000000000000000000000000000..bddc2baf9a425b6d5eb42bc101146dd4e1d088c5
--- /dev/null
+++ b/runtime/vm/object_set.h
@@ -0,0 +1,64 @@
+// Copyright (c) 2012, 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.
+
+#ifndef VM_OBJECT_SET_H_
+#define VM_OBJECT_SET_H_
+
+#include "vm/globals.h"
+
+namespace dart {
+
+class ObjectSet {
+ public:
+  ObjectSet(uword start, uword end) : start_(start), end_(end) {
+    ASSERT(start_ <= end_);
+    size_ = SizeFor((end_ - start_) >> kWordSizeLog2);
+    allocation_ = new uword[size_];
+    data_ = &allocation_[-((start >> kWordSizeLog2) / kBitsPerWord)];
+    ASSERT(allocation_ == &data_[(start >> kWordSizeLog2) / kBitsPerWord]);
+    Clear();
+  }
+
+  ~ObjectSet() {
+    delete[] allocation_;
+  }
+
+  bool Contains(RawObject* raw_obj) const {
+    uword raw_addr = RawObject::ToAddr(raw_obj);
+    ASSERT(raw_addr >= start_);
+    ASSERT(raw_addr < end_);
+    uword i = raw_addr >> kWordSizeLog2;
+    uword mask = (static_cast<uword>(1) << (i % kBitsPerWord));
+    return (data_[i / kBitsPerWord] & mask) != 0;
+  }
+
+  void Add(RawObject* raw_obj) {
+    uword raw_addr = RawObject::ToAddr(raw_obj);
+    ASSERT(raw_addr >= start_);
+    ASSERT(raw_addr < end_);
+    uword i = raw_addr >> kWordSizeLog2;
+    data_[i / kBitsPerWord] |= (static_cast<uword>(1) << (i % kBitsPerWord));
+  }
+
+  void Clear() {
+    memset(allocation_, 0, size_);
+  }
+
+ private:
+  static intptr_t SizeFor(intptr_t length) {
+    return 1 + ((length - 1) / kBitsPerWord);
+  }
+
+  uword* data_;
+  uword start_;

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

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.

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

I have sorted these fields in a (hopefully) more logical order.  Also, comments
have been added.  Done.

+  uword end_;
+  uword* allocation_;
+  intptr_t size_;
+
+  DISALLOW_IMPLICIT_CONSTRUCTORS(ObjectSet);
+};
+
+}  // namespace dart
+
+#endif  // VM_OBJECT_SET_H_