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   // Get invalid entry (off the end of the list).
110   EXPECT_TRUE(irt.Get(iref0) == nullptr);
111 
112   // Add three, remove in the opposite order.
113   iref0 = irt.Add(cookie, obj0.Get(), &error_msg);
114   EXPECT_TRUE(iref0 != nullptr);
115   iref1 = irt.Add(cookie, obj1.Get(), &error_msg);
116   EXPECT_TRUE(iref1 != nullptr);
117   iref2 = irt.Add(cookie, obj2.Get(), &error_msg);
118   EXPECT_TRUE(iref2 != nullptr);
119   CheckDump(&irt, 3, 3);
120 
121   ASSERT_TRUE(irt.Remove(cookie, iref2));
122   CheckDump(&irt, 2, 2);
123   ASSERT_TRUE(irt.Remove(cookie, iref1));
124   CheckDump(&irt, 1, 1);
125   ASSERT_TRUE(irt.Remove(cookie, iref0));
126   CheckDump(&irt, 0, 0);
127 
128   // Table should be empty now.
129   ASSERT_EQ(0U, irt.Capacity());
130 
131   // Add three, remove middle / middle / bottom / top.  (Second attempt
132   // to remove middle should fail.)
133   iref0 = irt.Add(cookie, obj0.Get(), &error_msg);
134   EXPECT_TRUE(iref0 != nullptr);
135   iref1 = irt.Add(cookie, obj1.Get(), &error_msg);
136   EXPECT_TRUE(iref1 != nullptr);
137   iref2 = irt.Add(cookie, obj2.Get(), &error_msg);
138   EXPECT_TRUE(iref2 != nullptr);
139   CheckDump(&irt, 3, 3);
140 
141   ASSERT_EQ(3U, irt.Capacity());
142 
143   ASSERT_TRUE(irt.Remove(cookie, iref1));
144   CheckDump(&irt, 2, 2);
145   ASSERT_FALSE(irt.Remove(cookie, iref1));
146   CheckDump(&irt, 2, 2);
147 
148   // Get invalid entry (from hole).
149   EXPECT_TRUE(irt.Get(iref1) == nullptr);
150 
151   ASSERT_TRUE(irt.Remove(cookie, iref2));
152   CheckDump(&irt, 1, 1);
153   ASSERT_TRUE(irt.Remove(cookie, iref0));
154   CheckDump(&irt, 0, 0);
155 
156   // Table should be empty now.
157   ASSERT_EQ(0U, irt.Capacity());
158 
159   // Add four entries.  Remove #1, add new entry, verify that table size
160   // is still 4 (i.e. holes are getting filled).  Remove #1 and #3, verify
161   // that we delete one and don't hole-compact the other.
162   iref0 = irt.Add(cookie, obj0.Get(), &error_msg);
163   EXPECT_TRUE(iref0 != nullptr);
164   iref1 = irt.Add(cookie, obj1.Get(), &error_msg);
165   EXPECT_TRUE(iref1 != nullptr);
166   iref2 = irt.Add(cookie, obj2.Get(), &error_msg);
167   EXPECT_TRUE(iref2 != nullptr);
168   IndirectRef iref3 = irt.Add(cookie, obj3.Get(), &error_msg);
169   EXPECT_TRUE(iref3 != nullptr);
170   CheckDump(&irt, 4, 4);
171 
172   ASSERT_TRUE(irt.Remove(cookie, iref1));
173   CheckDump(&irt, 3, 3);
174 
175   iref1 = irt.Add(cookie, obj1.Get(), &error_msg);
176   EXPECT_TRUE(iref1 != nullptr);
177 
178   ASSERT_EQ(4U, irt.Capacity()) << "hole not filled";
179   CheckDump(&irt, 4, 4);
180 
181   ASSERT_TRUE(irt.Remove(cookie, iref1));
182   CheckDump(&irt, 3, 3);
183   ASSERT_TRUE(irt.Remove(cookie, iref3));
184   CheckDump(&irt, 2, 2);
185 
186   ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions";
187 
188   ASSERT_TRUE(irt.Remove(cookie, iref2));
189   CheckDump(&irt, 1, 1);
190   ASSERT_TRUE(irt.Remove(cookie, iref0));
191   CheckDump(&irt, 0, 0);
192 
193   ASSERT_EQ(0U, irt.Capacity()) << "not empty after split remove";
194 
195   // Add an entry, remove it, add a new entry, and try to use the original
196   // iref.  They have the same slot number but are for different objects.
197   // With the extended checks in place, this should fail.
198   iref0 = irt.Add(cookie, obj0.Get(), &error_msg);
199   EXPECT_TRUE(iref0 != nullptr);
200   CheckDump(&irt, 1, 1);
201   ASSERT_TRUE(irt.Remove(cookie, iref0));
202   CheckDump(&irt, 0, 0);
203   iref1 = irt.Add(cookie, obj1.Get(), &error_msg);
204   EXPECT_TRUE(iref1 != nullptr);
205   CheckDump(&irt, 1, 1);
206   ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded";
207   CheckDump(&irt, 1, 1);
208   ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed";
209   ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty";
210   CheckDump(&irt, 0, 0);
211 
212   // Same as above, but with the same object.  A more rigorous checker
213   // (e.g. with slot serialization) will catch this.
214   iref0 = irt.Add(cookie, obj0.Get(), &error_msg);
215   EXPECT_TRUE(iref0 != nullptr);
216   CheckDump(&irt, 1, 1);
217   ASSERT_TRUE(irt.Remove(cookie, iref0));
218   CheckDump(&irt, 0, 0);
219   iref1 = irt.Add(cookie, obj0.Get(), &error_msg);
220   EXPECT_TRUE(iref1 != nullptr);
221   CheckDump(&irt, 1, 1);
222   if (iref0 != iref1) {
223     // Try 0, should not work.
224     ASSERT_FALSE(irt.Remove(cookie, iref0)) << "temporal del succeeded";
225   }
226   ASSERT_TRUE(irt.Remove(cookie, iref1)) << "temporal cleanup failed";
227   ASSERT_EQ(0U, irt.Capacity()) << "temporal del not empty";
228   CheckDump(&irt, 0, 0);
229 
230   // null isn't a valid iref.
231   ASSERT_TRUE(irt.Get(nullptr) == nullptr);
232 
233   // Stale lookup.
234   iref0 = irt.Add(cookie, obj0.Get(), &error_msg);
235   EXPECT_TRUE(iref0 != nullptr);
236   CheckDump(&irt, 1, 1);
237   ASSERT_TRUE(irt.Remove(cookie, iref0));
238   EXPECT_TRUE(irt.Get(iref0) == nullptr) << "stale lookup succeeded";
239   CheckDump(&irt, 0, 0);
240 
241   // Test table resizing.
242   // These ones fit...
243   static const size_t kTableInitial = kTableMax / 2;
244   IndirectRef manyRefs[kTableInitial];
245   for (size_t i = 0; i < kTableInitial; i++) {
246     manyRefs[i] = irt.Add(cookie, obj0.Get(), &error_msg);
247     ASSERT_TRUE(manyRefs[i] != nullptr) << "Failed adding " << i;
248     CheckDump(&irt, i + 1, 1);
249   }
250   // ...this one causes overflow.
251   iref0 = irt.Add(cookie, obj0.Get(), &error_msg);
252   ASSERT_TRUE(iref0 != nullptr);
253   ASSERT_EQ(kTableInitial + 1, irt.Capacity());
254   CheckDump(&irt, kTableInitial + 1, 1);
255 
256   for (size_t i = 0; i < kTableInitial; i++) {
257     ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i;
258     CheckDump(&irt, kTableInitial - i, 1);
259   }
260   // Because of removal order, should have 11 entries, 10 of them holes.
261   ASSERT_EQ(kTableInitial + 1, irt.Capacity());
262 
263   ASSERT_TRUE(irt.Remove(cookie, iref0)) << "multi-remove final failed";
264 
265   ASSERT_EQ(0U, irt.Capacity()) << "multi-del not empty";
266   CheckDump(&irt, 0, 0);
267 }
268 
TEST_F(IndirectReferenceTableTest,Holes)269 TEST_F(IndirectReferenceTableTest, Holes) {
270   // Test the explicitly named cases from the IRT implementation:
271   //
272   // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference
273   // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference
274   // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove
275   //    reference
276   // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference
277   // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove
278   //    reference
279 
280   ScopedObjectAccess soa(Thread::Current());
281   static const size_t kTableMax = 10;
282 
283   StackHandleScope<6> hs(soa.Self());
284   Handle<mirror::Class> c = hs.NewHandle(
285       class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;"));
286   ASSERT_TRUE(c != nullptr);
287   Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
288   ASSERT_TRUE(obj0 != nullptr);
289   Handle<mirror::Object> obj1 = hs.NewHandle(c->AllocObject(soa.Self()));
290   ASSERT_TRUE(obj1 != nullptr);
291   Handle<mirror::Object> obj2 = hs.NewHandle(c->AllocObject(soa.Self()));
292   ASSERT_TRUE(obj2 != nullptr);
293   Handle<mirror::Object> obj3 = hs.NewHandle(c->AllocObject(soa.Self()));
294   ASSERT_TRUE(obj3 != nullptr);
295   Handle<mirror::Object> obj4 = hs.NewHandle(c->AllocObject(soa.Self()));
296   ASSERT_TRUE(obj4 != nullptr);
297 
298   std::string error_msg;
299 
300   // 1) Segment with holes (current_num_holes_ > 0), push new segment, add/remove reference.
301   {
302     IndirectReferenceTable irt(kTableMax,
303                                kGlobal,
304                                IndirectReferenceTable::ResizableCapacity::kNo,
305                                &error_msg);
306     ASSERT_TRUE(irt.IsValid()) << error_msg;
307 
308     const IRTSegmentState cookie0 = kIRTFirstSegment;
309 
310     CheckDump(&irt, 0, 0);
311 
312     IndirectRef iref0 = irt.Add(cookie0, obj0.Get(), &error_msg);
313     IndirectRef iref1 = irt.Add(cookie0, obj1.Get(), &error_msg);
314     IndirectRef iref2 = irt.Add(cookie0, obj2.Get(), &error_msg);
315 
316     EXPECT_TRUE(irt.Remove(cookie0, iref1));
317 
318     // New segment.
319     const IRTSegmentState cookie1 = irt.GetSegmentState();
320 
321     IndirectRef iref3 = irt.Add(cookie1, obj3.Get(), &error_msg);
322 
323     // Must not have filled the previous hole.
324     EXPECT_EQ(irt.Capacity(), 4u);
325     EXPECT_TRUE(irt.Get(iref1) == nullptr);
326     CheckDump(&irt, 3, 3);
327 
328     UNUSED(iref0, iref1, iref2, iref3);
329   }
330 
331   // 2) Segment with holes (current_num_holes_ > 0), pop segment, add/remove reference
332   {
333     IndirectReferenceTable irt(kTableMax,
334                                kGlobal,
335                                IndirectReferenceTable::ResizableCapacity::kNo,
336                                &error_msg);
337     ASSERT_TRUE(irt.IsValid()) << error_msg;
338 
339     const IRTSegmentState cookie0 = kIRTFirstSegment;
340 
341     CheckDump(&irt, 0, 0);
342 
343     IndirectRef iref0 = irt.Add(cookie0, obj0.Get(), &error_msg);
344 
345     // New segment.
346     const IRTSegmentState cookie1 = irt.GetSegmentState();
347 
348     IndirectRef iref1 = irt.Add(cookie1, obj1.Get(), &error_msg);
349     IndirectRef iref2 = irt.Add(cookie1, obj2.Get(), &error_msg);
350     IndirectRef iref3 = irt.Add(cookie1, obj3.Get(), &error_msg);
351 
352     EXPECT_TRUE(irt.Remove(cookie1, iref2));
353 
354     // Pop segment.
355     irt.SetSegmentState(cookie1);
356 
357     IndirectRef iref4 = irt.Add(cookie1, obj4.Get(), &error_msg);
358 
359     EXPECT_EQ(irt.Capacity(), 2u);
360     EXPECT_TRUE(irt.Get(iref2) == nullptr);
361     CheckDump(&irt, 2, 2);
362 
363     UNUSED(iref0, iref1, iref2, iref3, iref4);
364   }
365 
366   // 3) Segment with holes (current_num_holes_ > 0), push new segment, pop segment, add/remove
367   //    reference.
368   {
369     IndirectReferenceTable irt(kTableMax,
370                                kGlobal,
371                                IndirectReferenceTable::ResizableCapacity::kNo,
372                                &error_msg);
373     ASSERT_TRUE(irt.IsValid()) << error_msg;
374 
375     const IRTSegmentState cookie0 = kIRTFirstSegment;
376 
377     CheckDump(&irt, 0, 0);
378 
379     IndirectRef iref0 = irt.Add(cookie0, obj0.Get(), &error_msg);
380 
381     // New segment.
382     const IRTSegmentState cookie1 = irt.GetSegmentState();
383 
384     IndirectRef iref1 = irt.Add(cookie1, obj1.Get(), &error_msg);
385     IndirectRef iref2 = irt.Add(cookie1, obj2.Get(), &error_msg);
386 
387     EXPECT_TRUE(irt.Remove(cookie1, iref1));
388 
389     // New segment.
390     const IRTSegmentState cookie2 = irt.GetSegmentState();
391 
392     IndirectRef iref3 = irt.Add(cookie2, obj3.Get(), &error_msg);
393 
394     // Pop segment.
395     irt.SetSegmentState(cookie2);
396 
397     IndirectRef iref4 = irt.Add(cookie1, obj4.Get(), &error_msg);
398 
399     EXPECT_EQ(irt.Capacity(), 3u);
400     EXPECT_TRUE(irt.Get(iref1) == nullptr);
401     CheckDump(&irt, 3, 3);
402 
403     UNUSED(iref0, iref1, iref2, iref3, iref4);
404   }
405 
406   // 4) Empty segment, push new segment, create a hole, pop a segment, add/remove a reference.
407   {
408     IndirectReferenceTable irt(kTableMax,
409                                kGlobal,
410                                IndirectReferenceTable::ResizableCapacity::kNo,
411                                &error_msg);
412     ASSERT_TRUE(irt.IsValid()) << error_msg;
413 
414     const IRTSegmentState cookie0 = kIRTFirstSegment;
415 
416     CheckDump(&irt, 0, 0);
417 
418     IndirectRef iref0 = irt.Add(cookie0, obj0.Get(), &error_msg);
419 
420     // New segment.
421     const IRTSegmentState cookie1 = irt.GetSegmentState();
422 
423     IndirectRef iref1 = irt.Add(cookie1, obj1.Get(), &error_msg);
424     EXPECT_TRUE(irt.Remove(cookie1, iref1));
425 
426     // Emptied segment, push new one.
427     const IRTSegmentState cookie2 = irt.GetSegmentState();
428 
429     IndirectRef iref2 = irt.Add(cookie1, obj1.Get(), &error_msg);
430     IndirectRef iref3 = irt.Add(cookie1, obj2.Get(), &error_msg);
431     IndirectRef iref4 = irt.Add(cookie1, obj3.Get(), &error_msg);
432 
433     EXPECT_TRUE(irt.Remove(cookie1, iref3));
434 
435     // Pop segment.
436     UNUSED(cookie2);
437     irt.SetSegmentState(cookie1);
438 
439     IndirectRef iref5 = irt.Add(cookie1, obj4.Get(), &error_msg);
440 
441     EXPECT_EQ(irt.Capacity(), 2u);
442     EXPECT_TRUE(irt.Get(iref3) == nullptr);
443     CheckDump(&irt, 2, 2);
444 
445     UNUSED(iref0, iref1, iref2, iref3, iref4, iref5);
446   }
447 
448   // 5) Base segment, push new segment, create a hole, pop a segment, push new segment, add/remove
449   //    reference
450   {
451     IndirectReferenceTable irt(kTableMax,
452                                kGlobal,
453                                IndirectReferenceTable::ResizableCapacity::kNo,
454                                &error_msg);
455     ASSERT_TRUE(irt.IsValid()) << error_msg;
456 
457     const IRTSegmentState cookie0 = kIRTFirstSegment;
458 
459     CheckDump(&irt, 0, 0);
460 
461     IndirectRef iref0 = irt.Add(cookie0, obj0.Get(), &error_msg);
462 
463     // New segment.
464     const IRTSegmentState cookie1 = irt.GetSegmentState();
465 
466     IndirectRef iref1 = irt.Add(cookie1, obj1.Get(), &error_msg);
467     IndirectRef iref2 = irt.Add(cookie1, obj1.Get(), &error_msg);
468     IndirectRef iref3 = irt.Add(cookie1, obj2.Get(), &error_msg);
469 
470     EXPECT_TRUE(irt.Remove(cookie1, iref2));
471 
472     // Pop segment.
473     irt.SetSegmentState(cookie1);
474 
475     // Push segment.
476     const IRTSegmentState cookie1_second = irt.GetSegmentState();
477     UNUSED(cookie1_second);
478 
479     IndirectRef iref4 = irt.Add(cookie1, obj3.Get(), &error_msg);
480 
481     EXPECT_EQ(irt.Capacity(), 2u);
482     EXPECT_TRUE(irt.Get(iref3) == nullptr);
483     CheckDump(&irt, 2, 2);
484 
485     UNUSED(iref0, iref1, iref2, iref3, iref4);
486   }
487 }
488 
TEST_F(IndirectReferenceTableTest,Resize)489 TEST_F(IndirectReferenceTableTest, Resize) {
490   ScopedObjectAccess soa(Thread::Current());
491   static const size_t kTableMax = 512;
492 
493   StackHandleScope<2> hs(soa.Self());
494   Handle<mirror::Class> c = hs.NewHandle(
495       class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;"));
496   ASSERT_TRUE(c != nullptr);
497   Handle<mirror::Object> obj0 = hs.NewHandle(c->AllocObject(soa.Self()));
498   ASSERT_TRUE(obj0 != nullptr);
499 
500   std::string error_msg;
501   IndirectReferenceTable irt(kTableMax,
502                              kLocal,
503                              IndirectReferenceTable::ResizableCapacity::kYes,
504                              &error_msg);
505   ASSERT_TRUE(irt.IsValid()) << error_msg;
506 
507   CheckDump(&irt, 0, 0);
508   const IRTSegmentState cookie = kIRTFirstSegment;
509 
510   for (size_t i = 0; i != kTableMax + 1; ++i) {
511     irt.Add(cookie, obj0.Get(), &error_msg);
512   }
513 
514   EXPECT_EQ(irt.Capacity(), kTableMax + 1);
515 }
516 
517 }  // namespace art
518