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