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