1// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/object_id_ring.h"
6#include "platform/assert.h"
7#include "vm/dart_api_impl.h"
8#include "vm/dart_api_state.h"
9#include "vm/globals.h"
10#include "vm/symbols.h"
11#include "vm/unit_test.h"
12
13namespace dart {
14
15#ifndef PRODUCT
16
17class ObjectIdRingTestHelper {
18 public:
19 static void SetCapacityAndMaxSerial(ObjectIdRing* ring,
20 int32_t capacity,
21 int32_t max_serial) {
22 ring->SetCapacityAndMaxSerial(capacity, max_serial);
23 }
24
25 static void ExpectIdIsValid(ObjectIdRing* ring, intptr_t id) {
26 EXPECT(ring->IsValidId(id));
27 }
28
29 static void ExpectIdIsInvalid(ObjectIdRing* ring, intptr_t id) {
30 EXPECT(!ring->IsValidId(id));
31 }
32
33 static void ExpectIndexId(ObjectIdRing* ring, intptr_t index, intptr_t id) {
34 EXPECT_EQ(id, ring->IdOfIndex(index));
35 }
36
37 static void ExpectInvalidIndex(ObjectIdRing* ring, intptr_t index) {
38 EXPECT_EQ(-1, ring->IdOfIndex(index));
39 }
40
41 static ObjectPtr MakeString(const char* s) {
42 return Symbols::New(Thread::Current(), s);
43 }
44
45 static void ExpectString(ObjectPtr obj, const char* s) {
46 String& str = String::Handle();
47 str ^= obj;
48 EXPECT(str.Equals(s));
49 }
50};
51
52// Test that serial number wrapping works.
53ISOLATE_UNIT_TEST_CASE(ObjectIdRingSerialWrapTest) {
54 Isolate* isolate = Isolate::Current();
55 ObjectIdRing* ring = isolate->EnsureObjectIdRing();
56 ObjectIdRingTestHelper::SetCapacityAndMaxSerial(ring, 2, 4);
57 intptr_t id;
58 ObjectIdRing::LookupResult kind = ObjectIdRing::kInvalid;
59 id = ring->GetIdForObject(ObjectIdRingTestHelper::MakeString("0"));
60 EXPECT_EQ(0, id);
61 ObjectIdRingTestHelper::ExpectIndexId(ring, 0, 0);
62 ObjectIdRingTestHelper::ExpectInvalidIndex(ring, 1);
63 id = ring->GetIdForObject(ObjectIdRingTestHelper::MakeString("1"));
64 EXPECT_EQ(1, id);
65 ObjectIdRingTestHelper::ExpectIndexId(ring, 0, 0);
66 ObjectIdRingTestHelper::ExpectIndexId(ring, 1, 1);
67 // Test that id 1 gives us the "1" string.
68 ObjectIdRingTestHelper::ExpectString(ring->GetObjectForId(id, &kind), "1");
69 EXPECT_EQ(ObjectIdRing::kValid, kind);
70 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 0);
71 ObjectIdRingTestHelper::ExpectIndexId(ring, 0, 0);
72 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 1);
73 ObjectIdRingTestHelper::ExpectIndexId(ring, 1, 1);
74 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 2);
75 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 3);
76 // We have wrapped, index 0 is being reused.
77 id = ring->GetIdForObject(ObjectIdRingTestHelper::MakeString("2"));
78 EXPECT_EQ(2, id);
79 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 0);
80 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 1);
81 // Index 0 has id 2.
82 ObjectIdRingTestHelper::ExpectIndexId(ring, 0, 2);
83 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 2);
84 // Index 1 has id 1.
85 ObjectIdRingTestHelper::ExpectIndexId(ring, 1, 1);
86 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 3);
87 id = ring->GetIdForObject(ObjectIdRingTestHelper::MakeString("3"));
88 EXPECT_EQ(3, id);
89 // Index 0 has id 2.
90 ObjectIdRingTestHelper::ExpectIndexId(ring, 0, 2);
91 // Index 1 has id 3.
92 ObjectIdRingTestHelper::ExpectIndexId(ring, 1, 3);
93 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 0);
94 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 1);
95 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 2);
96 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 3);
97 id = ring->GetIdForObject(ObjectIdRingTestHelper::MakeString("4"));
98 EXPECT_EQ(0, id);
99 // Index 0 has id 0.
100 ObjectIdRingTestHelper::ExpectIndexId(ring, 0, 0);
101 // Index 1 has id 3.
102 ObjectIdRingTestHelper::ExpectIndexId(ring, 1, 3);
103 ObjectIdRingTestHelper::ExpectString(ring->GetObjectForId(id, &kind), "4");
104 EXPECT_EQ(ObjectIdRing::kValid, kind);
105 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 0);
106 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 1);
107 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 2);
108 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 3);
109 id = ring->GetIdForObject(ObjectIdRingTestHelper::MakeString("5"));
110 EXPECT_EQ(1, id);
111 // Index 0 has id 0.
112 ObjectIdRingTestHelper::ExpectIndexId(ring, 0, 0);
113 // Index 1 has id 1.
114 ObjectIdRingTestHelper::ExpectIndexId(ring, 1, 1);
115 ObjectIdRingTestHelper::ExpectString(ring->GetObjectForId(id, &kind), "5");
116 EXPECT_EQ(ObjectIdRing::kValid, kind);
117 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 0);
118 ObjectIdRingTestHelper::ExpectIdIsValid(ring, 1);
119 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 2);
120 ObjectIdRingTestHelper::ExpectIdIsInvalid(ring, 3);
121}
122
123// Test that the ring table is updated when the scavenger moves an object.
124TEST_CASE(ObjectIdRingScavengeMoveTest) {
125 const char* kScriptChars =
126 "main() {\n"
127 " return [1, 2, 3];\n"
128 "}\n";
129 Dart_Handle lib = TestCase::LoadTestScript(kScriptChars, NULL);
130 Dart_Handle result = Dart_Invoke(lib, NewString("main"), 0, NULL);
131 Dart_Handle moved_handle;
132 intptr_t list_length = 0;
133 EXPECT_VALID(result);
134 EXPECT(!Dart_IsNull(result));
135 EXPECT(Dart_IsList(result));
136 EXPECT_VALID(Dart_ListLength(result, &list_length));
137 EXPECT_EQ(3, list_length);
138
139 Isolate* isolate = thread->isolate();
140 ObjectIdRing* ring = isolate->EnsureObjectIdRing();
141 ObjectIdRing::LookupResult kind = ObjectIdRing::kInvalid;
142
143 {
144 TransitionNativeToVM to_vm(thread);
145 ObjectPtr raw_obj = Api::UnwrapHandle(result);
146 // Located in new heap.
147 EXPECT(raw_obj->IsNewObject());
148 EXPECT_NE(Object::null(), raw_obj);
149 intptr_t raw_obj_id1 = ring->GetIdForObject(raw_obj);
150 EXPECT_EQ(0, raw_obj_id1);
151 // Get id 0 again.
152 EXPECT_EQ(raw_obj_id1,
153 ring->GetIdForObject(raw_obj, ObjectIdRing::kReuseId));
154 // Add to ring a second time.
155 intptr_t raw_obj_id2 = ring->GetIdForObject(raw_obj);
156 EXPECT_EQ(1, raw_obj_id2);
157 // Get id 0 again.
158 EXPECT_EQ(raw_obj_id1,
159 ring->GetIdForObject(raw_obj, ObjectIdRing::kReuseId));
160 ObjectPtr raw_obj1 = ring->GetObjectForId(raw_obj_id1, &kind);
161 EXPECT_EQ(ObjectIdRing::kValid, kind);
162 ObjectPtr raw_obj2 = ring->GetObjectForId(raw_obj_id2, &kind);
163 EXPECT_EQ(ObjectIdRing::kValid, kind);
164 EXPECT_NE(Object::null(), raw_obj1);
165 EXPECT_NE(Object::null(), raw_obj2);
166 EXPECT_EQ(ObjectLayout::ToAddr(raw_obj), ObjectLayout::ToAddr(raw_obj1));
167 EXPECT_EQ(ObjectLayout::ToAddr(raw_obj), ObjectLayout::ToAddr(raw_obj2));
168 // Force a scavenge.
169 GCTestHelper::CollectNewSpace();
170 ObjectPtr raw_object_moved1 = ring->GetObjectForId(raw_obj_id1, &kind);
171 EXPECT_EQ(ObjectIdRing::kValid, kind);
172 ObjectPtr raw_object_moved2 = ring->GetObjectForId(raw_obj_id2, &kind);
173 EXPECT_EQ(ObjectIdRing::kValid, kind);
174 EXPECT_NE(Object::null(), raw_object_moved1);
175 EXPECT_NE(Object::null(), raw_object_moved2);
176 EXPECT_EQ(ObjectLayout::ToAddr(raw_object_moved1),
177 ObjectLayout::ToAddr(raw_object_moved2));
178 // Test that objects have moved.
179 EXPECT_NE(ObjectLayout::ToAddr(raw_obj1),
180 ObjectLayout::ToAddr(raw_object_moved1));
181 EXPECT_NE(ObjectLayout::ToAddr(raw_obj2),
182 ObjectLayout::ToAddr(raw_object_moved2));
183 // Test that we still point at the same list.
184 moved_handle = Api::NewHandle(thread, raw_object_moved1);
185 // Test id reuse.
186 EXPECT_EQ(raw_obj_id1,
187 ring->GetIdForObject(raw_object_moved1, ObjectIdRing::kReuseId));
188 }
189 EXPECT_VALID(moved_handle);
190 EXPECT(!Dart_IsNull(moved_handle));
191 EXPECT(Dart_IsList(moved_handle));
192 EXPECT_VALID(Dart_ListLength(moved_handle, &list_length));
193 EXPECT_EQ(3, list_length);
194}
195
196// Test that the ring table is updated with nulls when the old GC collects.
197ISOLATE_UNIT_TEST_CASE(ObjectIdRingOldGCTest) {
198 Isolate* isolate = thread->isolate();
199 ObjectIdRing* ring = isolate->EnsureObjectIdRing();
200
201 ObjectIdRing::LookupResult kind = ObjectIdRing::kInvalid;
202 intptr_t raw_obj_id1 = -1;
203 intptr_t raw_obj_id2 = -1;
204 {
205 HandleScope handle_scope(thread);
206 const String& str = String::Handle(String::New("old", Heap::kOld));
207 EXPECT(!str.IsNull());
208 EXPECT_EQ(3, str.Length());
209
210 ObjectPtr raw_obj = Object::RawCast(str.raw());
211 // Verify that it is located in old heap.
212 EXPECT(raw_obj->IsOldObject());
213 EXPECT_NE(Object::null(), raw_obj);
214 raw_obj_id1 = ring->GetIdForObject(raw_obj);
215 EXPECT_EQ(0, raw_obj_id1);
216 raw_obj_id2 = ring->GetIdForObject(raw_obj);
217 EXPECT_EQ(1, raw_obj_id2);
218 ObjectPtr raw_obj1 = ring->GetObjectForId(raw_obj_id1, &kind);
219 EXPECT_EQ(ObjectIdRing::kValid, kind);
220 ObjectPtr raw_obj2 = ring->GetObjectForId(raw_obj_id2, &kind);
221 EXPECT_EQ(ObjectIdRing::kValid, kind);
222 EXPECT_NE(Object::null(), raw_obj1);
223 EXPECT_NE(Object::null(), raw_obj2);
224 EXPECT_EQ(ObjectLayout::ToAddr(raw_obj), ObjectLayout::ToAddr(raw_obj1));
225 EXPECT_EQ(ObjectLayout::ToAddr(raw_obj), ObjectLayout::ToAddr(raw_obj2));
226 // Exit scope. Freeing String handle.
227 }
228 // Force a GC. No reference exist to the old string anymore. It should be
229 // collected and the object id ring will now return the null object for
230 // those ids.
231 GCTestHelper::CollectOldSpace();
232 ObjectPtr raw_object_moved1 = ring->GetObjectForId(raw_obj_id1, &kind);
233 EXPECT_EQ(ObjectIdRing::kCollected, kind);
234 EXPECT_EQ(Object::null(), raw_object_moved1);
235 ObjectPtr raw_object_moved2 = ring->GetObjectForId(raw_obj_id2, &kind);
236 EXPECT_EQ(ObjectIdRing::kCollected, kind);
237 EXPECT_EQ(Object::null(), raw_object_moved2);
238}
239
240// Test that the ring table correctly reports an entry as expired when it is
241// overridden by new entries.
242ISOLATE_UNIT_TEST_CASE(ObjectIdRingExpiredEntryTest) {
243 Isolate* isolate = Isolate::Current();
244 ObjectIdRing* ring = isolate->EnsureObjectIdRing();
245
246 // Insert an object and check we can look it up.
247 String& obj = String::Handle(String::New("I will expire"));
248 intptr_t obj_id = ring->GetIdForObject(obj.raw());
249 ObjectIdRing::LookupResult kind = ObjectIdRing::kInvalid;
250 ObjectPtr obj_lookup = ring->GetObjectForId(obj_id, &kind);
251 EXPECT_EQ(ObjectIdRing::kValid, kind);
252 EXPECT_EQ(obj.raw(), obj_lookup);
253
254 // Insert as many new objects as the ring size to bump out our first entry.
255 Object& new_obj = Object::Handle();
256 for (intptr_t i = 0; i < ObjectIdRing::kDefaultCapacity; i++) {
257 new_obj = String::New("Bump");
258 intptr_t new_obj_id = ring->GetIdForObject(new_obj.raw());
259 ObjectIdRing::LookupResult kind = ObjectIdRing::kInvalid;
260 ObjectPtr new_obj_lookup = ring->GetObjectForId(new_obj_id, &kind);
261 EXPECT_EQ(ObjectIdRing::kValid, kind);
262 EXPECT_EQ(new_obj.raw(), new_obj_lookup);
263 }
264
265 // Check our first entry reports it has expired.
266 obj_lookup = ring->GetObjectForId(obj_id, &kind);
267 EXPECT_EQ(ObjectIdRing::kExpired, kind);
268 EXPECT_NE(obj.raw(), obj_lookup);
269 EXPECT_EQ(Object::null(), obj_lookup);
270}
271
272#endif // !PRODUCT
273
274} // namespace dart
275