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