1 /*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "indirect_reference_table-inl.h"
18
19 #include "android-base/stringprintf.h"
20
21 #include "class_linker-inl.h"
22 #include "common_runtime_test.h"
23 #include "mirror/object-inl.h"
24 #include "scoped_thread_state_change-inl.h"
25
26 namespace art {
27
28 using android::base::StringPrintf;
29
30 class IndirectReferenceTableTest : public CommonRuntimeTest {};
31
CheckDump(IndirectReferenceTable * irt,size_t num_objects,size_t num_unique)32 static void CheckDump(IndirectReferenceTable* irt, size_t num_objects, size_t num_unique)
33 REQUIRES_SHARED(Locks::mutator_lock_) {
34 std::ostringstream oss;
35 irt->Dump(oss);
36 if (num_objects == 0) {
37 EXPECT_EQ(oss.str().find("java.lang.Object"), std::string::npos) << oss.str();
38 } else if (num_objects == 1) {
39 EXPECT_NE(oss.str().find("1 of java.lang.Object"), std::string::npos) << oss.str();
40 } else {
41 EXPECT_NE(oss.str().find(StringPrintf("%zd of java.lang.Object (%zd unique instances)",
42 num_objects, num_unique)),
43 std::string::npos)
44 << "\n Expected number of objects: " << num_objects
45 << "\n Expected unique objects: " << num_unique << "\n"
46 << oss.str();
47 }
48 }
49
TEST_F(IndirectReferenceTableTest,BasicTest)50 TEST_F(IndirectReferenceTableTest, BasicTest) {
51 // This will lead to error messages in the log.
52 ScopedLogSeverity sls(LogSeverity::FATAL);
53
54 ScopedObjectAccess soa(Thread::Current());
55 static const size_t kTableMax = 20;
56 std::string error_msg;
57 IndirectReferenceTable irt(kTableMax,
58 kGlobal,
59 IndirectReferenceTable::ResizableCapacity::kNo,
60 &error_msg);
61 ASSERT_TRUE(irt.IsValid()) << error_msg;
62
63 mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
64 StackHandleScope<4> hs(soa.Self());
65 ASSERT_TRUE(c != nullptr);
66 Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
67 ASSERT_TRUE(obj0 != nullptr);
68 Handle<mirror::Object> obj1 = hs.NewHandle(c->AllocObject(soa.Self()));
69 ASSERT_TRUE(obj1 != nullptr);
70 Handle<mirror::Object> obj2 = hs.NewHandle(c->AllocObject(soa.Self()));
71 ASSERT_TRUE(obj2 != nullptr);
72 Handle<mirror::Object> obj3 = hs.NewHandle(c->AllocObject(soa.Self()));
73 ASSERT_TRUE(obj3 != nullptr);
74
75 const IRTSegmentState cookie = kIRTFirstSegment;
76
77 CheckDump(&irt, 0, 0);
78
79 IndirectRef iref0 = (IndirectRef) 0x11110;
80 EXPECT_FALSE(irt.Remove(cookie, iref0)) << "unexpectedly successful removal";
81
82 // Add three, check, remove in the order in which they were added.
83 iref0 = irt.Add(cookie, obj0.Get());
84 EXPECT_TRUE(iref0 != nullptr);
85 CheckDump(&irt, 1, 1);
86 IndirectRef iref1 = irt.Add(cookie, obj1.Get());
87 EXPECT_TRUE(iref1 != nullptr);
88 CheckDump(&irt, 2, 2);
89 IndirectRef iref2 = irt.Add(cookie, obj2.Get());
90 EXPECT_TRUE(iref2 != nullptr);
91 CheckDump(&irt, 3, 3);
92
93 EXPECT_OBJ_PTR_EQ(obj0.Get(), irt.Get(iref0));
94 EXPECT_OBJ_PTR_EQ(obj1.Get(), irt.Get(iref1));
95 EXPECT_OBJ_PTR_EQ(obj2.Get(), irt.Get(iref2));
96
97 EXPECT_TRUE(irt.Remove(cookie, iref0));
98 CheckDump(&irt, 2, 2);
99 EXPECT_TRUE(irt.Remove(cookie, iref1));
100 CheckDump(&irt, 1, 1);
101 EXPECT_TRUE(irt.Remove(cookie, iref2));
102 CheckDump(&irt, 0, 0);
103
104 // Table should be empty now.
105 EXPECT_EQ(0U, irt.Capacity());
106
107 // Get invalid entry (off the end of the list).
108 EXPECT_TRUE(irt.Get(iref0) == nullptr);
109
110 // Add three, remove in the opposite order.
111 iref0 = irt.Add(cookie, obj0.Get());
112 EXPECT_TRUE(iref0 != nullptr);
113 iref1 = irt.Add(cookie, obj1.Get());
114 EXPECT_TRUE(iref1 != nullptr);
115 iref2 = irt.Add(cookie, obj2.Get());
116 EXPECT_TRUE(iref2 != nullptr);
117 CheckDump(&irt, 3, 3);
118
119 ASSERT_TRUE(irt.Remove(cookie, iref2));
120 CheckDump(&irt, 2, 2);
121 ASSERT_TRUE(irt.Remove(cookie, iref1));
122 CheckDump(&irt, 1, 1);
123 ASSERT_TRUE(irt.Remove(cookie, iref0));
124 CheckDump(&irt, 0, 0);
125
126 // Table should be empty now.
127 ASSERT_EQ(0U, irt.Capacity());
128
129 // Add three, remove middle / middle / bottom / top. (Second attempt
130 // to remove middle should fail.)
131 iref0 = irt.Add(cookie, obj0.Get());
132 EXPECT_TRUE(iref0 != nullptr);
133 iref1 = irt.Add(cookie, obj1.Get());
134 EXPECT_TRUE(iref1 != nullptr);
135 iref2 = irt.Add(cookie, obj2.Get());
136 EXPECT_TRUE(iref2 != nullptr);
137 CheckDump(&irt, 3, 3);
138
139 ASSERT_EQ(3U, irt.Capacity());
140
141 ASSERT_TRUE(irt.Remove(cookie, iref1));
142 CheckDump(&irt, 2, 2);
143 ASSERT_FALSE(irt.Remove(cookie, iref1));
144 CheckDump(&irt, 2, 2);
145
146 // Get invalid entry (from hole).
147 EXPECT_TRUE(irt.Get(iref1) == nullptr);
148
149 ASSERT_TRUE(irt.Remove(cookie, iref2));
150 CheckDump(&irt, 1, 1);
151 ASSERT_TRUE(irt.Remove(cookie, iref0));
152 CheckDump(&irt, 0, 0);
153
154 // Table should be empty now.
155 ASSERT_EQ(0U, irt.Capacity());
156
157 // Add four entries. Remove #1, add new entry, verify that table size
158 // is still 4 (i.e. holes are getting filled). Remove #1 and #3, verify
159 // that we delete one and don't hole-compact the other.
160 iref0 = irt.Add(cookie, obj0.Get());
161 EXPECT_TRUE(iref0 != nullptr);
162 iref1 = irt.Add(cookie, obj1.Get());
163 EXPECT_TRUE(iref1 != nullptr);
164 iref2 = irt.Add(cookie, obj2.Get());
165 EXPECT_TRUE(iref2 != nullptr);
166 IndirectRef iref3 = irt.Add(cookie, obj3.Get());
167 EXPECT_TRUE(iref3 != nullptr);
168 CheckDump(&irt, 4, 4);
169
170 ASSERT_TRUE(irt.Remove(cookie, iref1));
171 CheckDump(&irt, 3, 3);
172
173 iref1 = irt.Add(cookie, obj1.Get());
174 EXPECT_TRUE(iref1 != nullptr);
175
176 ASSERT_EQ(4U, irt.Capacity()) << "hole not filled";
177 CheckDump(&irt, 4, 4);
178
179 ASSERT_TRUE(irt.Remove(cookie, iref1));
180 CheckDump(&irt, 3, 3);
181 ASSERT_TRUE(irt.Remove(cookie, iref3));
182 CheckDump(&irt, 2, 2);
183
184 ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions";
185
186 ASSERT_TRUE(irt.Remove(cookie, iref2));
187 CheckDump(&irt, 1, 1);
188 ASSERT_TRUE(irt.Remove(cookie, iref0));
189 CheckDump(&irt, 0, 0);
190
191 ASSERT_EQ(0U, irt.Capacity()) << "not empty after split remove";
192
193 // Add an entry, remove it, add a new entry, and try to use the original
194 // iref. They have the same slot number but are for different objects.
195 // With the extended checks in place, this should fail.
196 iref0 = irt.Add(cookie, obj0.Get());
197 EXPECT_TRUE(iref0 != nullptr);
198 CheckDump(&irt, 1, 1);
199 ASSERT_TRUE(irt.Remove(cookie, iref0));
200 CheckDump(&irt, 0, 0);
201 iref1 = irt.Add(cookie, obj1.Get());
202 EXPECT_TRUE(iref1 != nullptr);
203 CheckDump(&irt, 1, 1);
204 ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded";
205 CheckDump(&irt, 1, 1);
206 ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed";
207 ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty";
208 CheckDump(&irt, 0, 0);
209
210 // Same as above, but with the same object. A more rigorous checker
211 // (e.g. with slot serialization) will catch this.
212 iref0 = irt.Add(cookie, obj0.Get());
213 EXPECT_TRUE(iref0 != nullptr);
214 CheckDump(&irt, 1, 1);
215 ASSERT_TRUE(irt.Remove(cookie, iref0));
216 CheckDump(&irt, 0, 0);
217 iref1 = irt.Add(cookie, obj0.Get());
218 EXPECT_TRUE(iref1 != nullptr);
219 CheckDump(&irt, 1, 1);
220 if (iref0 != iref1) {
221 // Try 0, should not work.
222 ASSERT_FALSE(irt.Remove(cookie, iref0)) << "temporal del succeeded";
223 }
224 ASSERT_TRUE(irt.Remove(cookie, iref1)) << "temporal cleanup failed";
225 ASSERT_EQ(0U, irt.Capacity()) << "temporal del not empty";
226 CheckDump(&irt, 0, 0);
227
228 // null isn't a valid iref.
229 ASSERT_TRUE(irt.Get(nullptr) == nullptr);
230
231 // Stale lookup.
232 iref0 = irt.Add(cookie, obj0.Get());
233 EXPECT_TRUE(iref0 != nullptr);
234 CheckDump(&irt, 1, 1);
235 ASSERT_TRUE(irt.Remove(cookie, iref0));
236 EXPECT_TRUE(irt.Get(iref0) == nullptr) << "stale lookup succeeded";
237 CheckDump(&irt, 0, 0);
238
239 // Test table resizing.
240 // These ones fit...
241 static const size_t kTableInitial = kTableMax / 2;
242 IndirectRef manyRefs[kTableInitial];
243 for (size_t i = 0; i < kTableInitial; i++) {
244 manyRefs[i] = irt.Add(cookie, obj0.Get());
245 ASSERT_TRUE(manyRefs[i] != nullptr) << "Failed adding " << i;
246 CheckDump(&irt, i + 1, 1);
247 }
248 // ...this one causes overflow.
249 iref0 = irt.Add(cookie, obj0.Get());
250 ASSERT_TRUE(iref0 != nullptr);
251 ASSERT_EQ(kTableInitial + 1, irt.Capacity());
252 CheckDump(&irt, kTableInitial + 1, 1);
253
254 for (size_t i = 0; i < kTableInitial; i++) {
255 ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i;
256 CheckDump(&irt, kTableInitial - i, 1);
257 }
258 // Because of removal order, should have 11 entries, 10 of them holes.
259 ASSERT_EQ(kTableInitial + 1, irt.Capacity());
260
261 ASSERT_TRUE(irt.Remove(cookie, iref0)) << "multi-remove final failed";
262
263 ASSERT_EQ(0U, irt.Capacity()) << "multi-del not empty";
264 CheckDump(&irt, 0, 0);
265 }
266
TEST_F(IndirectReferenceTableTest,Holes)267 TEST_F(IndirectReferenceTableTest, Holes) {
268 // Test the explicitly named cases from the IRT implementation:
269 //
270 // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference
271 // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference
272 // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove
273 // reference
274 // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference
275 // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove
276 // reference
277
278 ScopedObjectAccess soa(Thread::Current());
279 static const size_t kTableMax = 10;
280
281 mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
282 StackHandleScope<5> hs(soa.Self());
283 ASSERT_TRUE(c != nullptr);
284 Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
285 ASSERT_TRUE(obj0 != nullptr);
286 Handle<mirror::Object> obj1 = hs.NewHandle(c->AllocObject(soa.Self()));
287 ASSERT_TRUE(obj1 != nullptr);
288 Handle<mirror::Object> obj2 = hs.NewHandle(c->AllocObject(soa.Self()));
289 ASSERT_TRUE(obj2 != nullptr);
290 Handle<mirror::Object> obj3 = hs.NewHandle(c->AllocObject(soa.Self()));
291 ASSERT_TRUE(obj3 != nullptr);
292 Handle<mirror::Object> obj4 = hs.NewHandle(c->AllocObject(soa.Self()));
293 ASSERT_TRUE(obj4 != nullptr);
294
295 std::string error_msg;
296
297 // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference.
298 {
299 IndirectReferenceTable irt(kTableMax,
300 kGlobal,
301 IndirectReferenceTable::ResizableCapacity::kNo,
302 &error_msg);
303 ASSERT_TRUE(irt.IsValid()) << error_msg;
304
305 const IRTSegmentState cookie0 = kIRTFirstSegment;
306
307 CheckDump(&irt, 0, 0);
308
309 IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
310 IndirectRef iref1 = irt.Add(cookie0, obj1.Get());
311 IndirectRef iref2 = irt.Add(cookie0, obj2.Get());
312
313 EXPECT_TRUE(irt.Remove(cookie0, iref1));
314
315 // New segment.
316 const IRTSegmentState cookie1 = irt.GetSegmentState();
317
318 IndirectRef iref3 = irt.Add(cookie1, obj3.Get());
319
320 // Must not have filled the previous hole.
321 EXPECT_EQ(irt.Capacity(), 4u);
322 EXPECT_TRUE(irt.Get(iref1) == nullptr);
323 CheckDump(&irt, 3, 3);
324
325 UNUSED(iref0, iref1, iref2, iref3);
326 }
327
328 // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference
329 {
330 IndirectReferenceTable irt(kTableMax,
331 kGlobal,
332 IndirectReferenceTable::ResizableCapacity::kNo,
333 &error_msg);
334 ASSERT_TRUE(irt.IsValid()) << error_msg;
335
336 const IRTSegmentState cookie0 = kIRTFirstSegment;
337
338 CheckDump(&irt, 0, 0);
339
340 IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
341
342 // New segment.
343 const IRTSegmentState cookie1 = irt.GetSegmentState();
344
345 IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
346 IndirectRef iref2 = irt.Add(cookie1, obj2.Get());
347 IndirectRef iref3 = irt.Add(cookie1, obj3.Get());
348
349 EXPECT_TRUE(irt.Remove(cookie1, iref2));
350
351 // Pop segment.
352 irt.SetSegmentState(cookie1);
353
354 IndirectRef iref4 = irt.Add(cookie1, obj4.Get());
355
356 EXPECT_EQ(irt.Capacity(), 2u);
357 EXPECT_TRUE(irt.Get(iref2) == nullptr);
358 CheckDump(&irt, 2, 2);
359
360 UNUSED(iref0, iref1, iref2, iref3, iref4);
361 }
362
363 // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove
364 // reference.
365 {
366 IndirectReferenceTable irt(kTableMax,
367 kGlobal,
368 IndirectReferenceTable::ResizableCapacity::kNo,
369 &error_msg);
370 ASSERT_TRUE(irt.IsValid()) << error_msg;
371
372 const IRTSegmentState cookie0 = kIRTFirstSegment;
373
374 CheckDump(&irt, 0, 0);
375
376 IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
377
378 // New segment.
379 const IRTSegmentState cookie1 = irt.GetSegmentState();
380
381 IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
382 IndirectRef iref2 = irt.Add(cookie1, obj2.Get());
383
384 EXPECT_TRUE(irt.Remove(cookie1, iref1));
385
386 // New segment.
387 const IRTSegmentState cookie2 = irt.GetSegmentState();
388
389 IndirectRef iref3 = irt.Add(cookie2, obj3.Get());
390
391 // Pop segment.
392 irt.SetSegmentState(cookie2);
393
394 IndirectRef iref4 = irt.Add(cookie1, obj4.Get());
395
396 EXPECT_EQ(irt.Capacity(), 3u);
397 EXPECT_TRUE(irt.Get(iref1) == nullptr);
398 CheckDump(&irt, 3, 3);
399
400 UNUSED(iref0, iref1, iref2, iref3, iref4);
401 }
402
403 // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference.
404 {
405 IndirectReferenceTable irt(kTableMax,
406 kGlobal,
407 IndirectReferenceTable::ResizableCapacity::kNo,
408 &error_msg);
409 ASSERT_TRUE(irt.IsValid()) << error_msg;
410
411 const IRTSegmentState cookie0 = kIRTFirstSegment;
412
413 CheckDump(&irt, 0, 0);
414
415 IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
416
417 // New segment.
418 const IRTSegmentState cookie1 = irt.GetSegmentState();
419
420 IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
421 EXPECT_TRUE(irt.Remove(cookie1, iref1));
422
423 // Emptied segment, push new one.
424 const IRTSegmentState cookie2 = irt.GetSegmentState();
425
426 IndirectRef iref2 = irt.Add(cookie1, obj1.Get());
427 IndirectRef iref3 = irt.Add(cookie1, obj2.Get());
428 IndirectRef iref4 = irt.Add(cookie1, obj3.Get());
429
430 EXPECT_TRUE(irt.Remove(cookie1, iref3));
431
432 // Pop segment.
433 UNUSED(cookie2);
434 irt.SetSegmentState(cookie1);
435
436 IndirectRef iref5 = irt.Add(cookie1, obj4.Get());
437
438 EXPECT_EQ(irt.Capacity(), 2u);
439 EXPECT_TRUE(irt.Get(iref3) == nullptr);
440 CheckDump(&irt, 2, 2);
441
442 UNUSED(iref0, iref1, iref2, iref3, iref4, iref5);
443 }
444
445 // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove
446 // reference
447 {
448 IndirectReferenceTable irt(kTableMax,
449 kGlobal,
450 IndirectReferenceTable::ResizableCapacity::kNo,
451 &error_msg);
452 ASSERT_TRUE(irt.IsValid()) << error_msg;
453
454 const IRTSegmentState cookie0 = kIRTFirstSegment;
455
456 CheckDump(&irt, 0, 0);
457
458 IndirectRef iref0 = irt.Add(cookie0, obj0.Get());
459
460 // New segment.
461 const IRTSegmentState cookie1 = irt.GetSegmentState();
462
463 IndirectRef iref1 = irt.Add(cookie1, obj1.Get());
464 IndirectRef iref2 = irt.Add(cookie1, obj1.Get());
465 IndirectRef iref3 = irt.Add(cookie1, obj2.Get());
466
467 EXPECT_TRUE(irt.Remove(cookie1, iref2));
468
469 // Pop segment.
470 irt.SetSegmentState(cookie1);
471
472 // Push segment.
473 const IRTSegmentState cookie1_second = irt.GetSegmentState();
474 UNUSED(cookie1_second);
475
476 IndirectRef iref4 = irt.Add(cookie1, obj3.Get());
477
478 EXPECT_EQ(irt.Capacity(), 2u);
479 EXPECT_TRUE(irt.Get(iref3) == nullptr);
480 CheckDump(&irt, 2, 2);
481
482 UNUSED(iref0, iref1, iref2, iref3, iref4);
483 }
484 }
485
TEST_F(IndirectReferenceTableTest,Resize)486 TEST_F(IndirectReferenceTableTest, Resize) {
487 ScopedObjectAccess soa(Thread::Current());
488 static const size_t kTableMax = 512;
489
490 mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
491 StackHandleScope<1> hs(soa.Self());
492 ASSERT_TRUE(c != nullptr);
493 Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
494 ASSERT_TRUE(obj0 != nullptr);
495
496 std::string error_msg;
497 IndirectReferenceTable irt(kTableMax,
498 kLocal,
499 IndirectReferenceTable::ResizableCapacity::kYes,
500 &error_msg);
501 ASSERT_TRUE(irt.IsValid()) << error_msg;
502
503 CheckDump(&irt, 0, 0);
504 const IRTSegmentState cookie = kIRTFirstSegment;
505
506 for (size_t i = 0; i != kTableMax + 1; ++i) {
507 irt.Add(cookie, obj0.Get());
508 }
509
510 EXPECT_EQ(irt.Capacity(), kTableMax + 1);
511 }
512
513 } // namespace art
514