Object ID Ring with tests

runtime/vm/object_id_ring_test.cc

Index: runtime/vm/object_id_ring_test.cc
diff --git a/runtime/vm/object_id_ring_test.cc b/runtime/vm/object_id_ring_test.cc
new file mode 100644
index 0000000000000000000000000000000000000000..423261ef2b1341578eec85022dc80cb057324969
--- /dev/null
+++ b/runtime/vm/object_id_ring_test.cc
@@ -0,0 +1,172 @@
+// Copyright (c) 2013, 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.
+
+#include "platform/assert.h"
+#include "vm/globals.h"
+#include "vm/object_id_ring.h"
+#include "vm/unit_test.h"
+#include "vm/dart_api_impl.h"
+
+namespace dart {
+
+
+class ObjectIdRingTestHelper {
+ public:
+  static ObjectIdRing* CreateRing(Isolate* isolate, intptr_t capacity) {
+    ObjectIdRing* ring = new ObjectIdRing(isolate, capacity);
+    SetSmallMaxSerial(ring);
+    return ring;
+  }
+
+  static void SetSmallMaxSerial(ObjectIdRing* ring) {
+    ring->max_serial_ = ring->capacity_ * 2;
+  }
+
+  static void ExpectIdIsValid(ObjectIdRing* ring, intptr_t id) {
+    EXPECT(ring->IsValidId(id));
+  }
+
+  static void ExpectIdIsInvalid(ObjectIdRing* ring, intptr_t id) {
+    EXPECT(!ring->IsValidId(id));
+  }
+};
+
+
+// Test that serial number wrapping works.
+UNIT_TEST_CASE(ObjectIdRingSerialWrapTest) {
+  ObjectIdRing* ring = ObjectIdRingTestHelper::CreateRing(NULL, 2);
+  intptr_t id;
+  id = ring->GetIdForObject(Object::null());
+  EXPECT_EQ(0, id);
+  id = ring->GetIdForObject(Object::null());
+  EXPECT_EQ(1, id);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 0);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 1);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 2);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 3);
+  id = ring->GetIdForObject(Object::null());
+  EXPECT_EQ(2, id);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 0);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 1);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 2);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 3);
+  id = ring->GetIdForObject(Object::null());
+  EXPECT_EQ(3, id);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 0);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 1);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 2);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 3);
+  id = ring->GetIdForObject(Object::null());
+  EXPECT_EQ(0, id);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 0);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 1);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 2);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 3);
+  id = ring->GetIdForObject(Object::null());
+  EXPECT_EQ(1, id);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 0);
+  ObjectIdRingTestHelper::ExpectIdIsValid(ring, 1);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 2);
+  ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 3);
+}
+
+
+// Test that the ring table is updated when the scavenger moves an object.
+TEST_CASE(ObjectIdRingScavengeMoveTest) {
+  const char* kScriptChars =
+  "main() {\n"
+  "  return [1, 2, 3];\n"
+  "}\n";
+  Dart_Handle lib = TestCase::LoadTestScript(kScriptChars, NULL);
+  Dart_Handle result = Dart_Invoke(lib, NewString("main"), 0, NULL);
+  intptr_t list_length = 0;
+  EXPECT_VALID(result);
+  EXPECT(!Dart_IsNull(result));
+  EXPECT(Dart_IsList(result));
+  EXPECT_VALID(Dart_ListLength(result, &list_length));
+  EXPECT_EQ(3, list_length);
+  Isolate* isolate = Isolate::Current();
+  Heap* heap = isolate->heap();
+  ObjectIdRing* ring = isolate->get_object_id_ring();
+  RawObject* raw_obj = Api::UnwrapHandle(result);
+  // Located in new heap.
+  EXPECT(raw_obj->IsNewObject());
+  EXPECT_NE(Object::null(), raw_obj);
+  intptr_t raw_obj_id1 = ring->GetIdForObject(raw_obj);
+  EXPECT_EQ(0, raw_obj_id1);
+  intptr_t raw_obj_id2 = ring->GetIdForObject(raw_obj);
+  EXPECT_EQ(1, raw_obj_id2);
+  intptr_t raw_obj_id3 = ring->GetIdForObject(Object::null());
+  RawObject* raw_obj1 = ring->GetObjectForId(raw_obj_id1);
+  RawObject* raw_obj2 = ring->GetObjectForId(raw_obj_id2);
+  RawObject* raw_obj3 = ring->GetObjectForId(raw_obj_id3);
+  EXPECT_NE(Object::null(), raw_obj1);
+  EXPECT_NE(Object::null(), raw_obj2);
+  EXPECT_EQ(Object::null(), raw_obj3);
+  EXPECT_EQ(RawObject::ToAddr(raw_obj), RawObject::ToAddr(raw_obj1));
+  EXPECT_EQ(RawObject::ToAddr(raw_obj), RawObject::ToAddr(raw_obj2));
+  // Force a scavenge.
+  heap->CollectGarbage(Heap::kNew);
+  RawObject* raw_object_moved1 = ring->GetObjectForId(raw_obj_id1);
+  RawObject* raw_object_moved2 = ring->GetObjectForId(raw_obj_id2);
+  RawObject* raw_object_moved3 = ring->GetObjectForId(raw_obj_id3);
+  EXPECT_NE(Object::null(), raw_object_moved1);
+  EXPECT_NE(Object::null(), raw_object_moved2);
+  EXPECT_EQ(Object::null(), raw_object_moved3);
+  EXPECT_EQ(RawObject::ToAddr(raw_object_moved1),
+            RawObject::ToAddr(raw_object_moved2));
+  // Test that objects have moved.
+  EXPECT_NE(RawObject::ToAddr(raw_obj1), RawObject::ToAddr(raw_object_moved1));
+  EXPECT_NE(RawObject::ToAddr(raw_obj2), RawObject::ToAddr(raw_object_moved2));
+  // Test that we still point at the same list.
+  Dart_Handle moved_handle = Api::NewHandle(isolate, raw_object_moved1);
+  EXPECT_VALID(moved_handle);
+  EXPECT(!Dart_IsNull(moved_handle));
+  EXPECT(Dart_IsList(moved_handle));
+  EXPECT_VALID(Dart_ListLength(moved_handle, &list_length));
+  EXPECT_EQ(3, list_length);
+}
+
+
+// Test that the ring table is updated with nulls when the old GC collects.
+TEST_CASE(ObjectIdRingOldGCTest) {
+  const char* kScriptChars =
+  "main() {\n"
+  "  return [1, 2, 3];\n"
+  "}\n";
+  Dart_Handle lib = TestCase::LoadTestScript(kScriptChars, NULL);
+  Dart_Handle result = Dart_Invoke(lib, NewString("main"), 0, NULL);
+  intptr_t list_length = 0;
+  EXPECT_VALID(result);
+  EXPECT(!Dart_IsNull(result));
+  EXPECT(Dart_IsList(result));
+  EXPECT_VALID(Dart_ListLength(result, &list_length));
+  EXPECT_EQ(3, list_length);
+  Isolate* isolate = Isolate::Current();
+  Heap* heap = isolate->heap();
+  ObjectIdRing* ring = isolate->get_object_id_ring();
+  RawObject* raw_obj = Api::UnwrapHandle(result);
+  // Located in new heap.
+  EXPECT(raw_obj->IsNewObject());
+  EXPECT_NE(Object::null(), raw_obj);
+  intptr_t raw_obj_id1 = ring->GetIdForObject(raw_obj);
+  EXPECT_EQ(0, raw_obj_id1);
+  intptr_t raw_obj_id2 = ring->GetIdForObject(raw_obj);
+  EXPECT_EQ(1, raw_obj_id2);
+  RawObject* raw_obj1 = ring->GetObjectForId(raw_obj_id1);
+  RawObject* raw_obj2 = ring->GetObjectForId(raw_obj_id2);
+  EXPECT_NE(Object::null(), raw_obj1);
+  EXPECT_NE(Object::null(), raw_obj2);
+  EXPECT_EQ(RawObject::ToAddr(raw_obj), RawObject::ToAddr(raw_obj1));
+  EXPECT_EQ(RawObject::ToAddr(raw_obj), RawObject::ToAddr(raw_obj2));
+  // Force a GC.
+  heap->CollectGarbage(Heap::kOld);
+  RawObject* raw_object_moved1 = ring->GetObjectForId(raw_obj_id1);
+  RawObject* raw_object_moved2 = ring->GetObjectForId(raw_obj_id2);
+  // Objects should now be null.
+  EXPECT_EQ(Object::null(), raw_object_moved1);
+  EXPECT_EQ(Object::null(), raw_object_moved2);
+}
+
+}  // namespace dart