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 "common_runtime_test.h"
20 #include "mirror/object-inl.h"
21 #include "scoped_thread_state_change.h"
22 
23 namespace art {
24 
25 class IndirectReferenceTableTest : public CommonRuntimeTest {};
26 
CheckDump(IndirectReferenceTable * irt,size_t num_objects,size_t num_unique)27 static void CheckDump(IndirectReferenceTable* irt, size_t num_objects, size_t num_unique)
28     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
29   std::ostringstream oss;
30   irt->Dump(oss);
31   if (num_objects == 0) {
32     EXPECT_EQ(oss.str().find("java.lang.Object"), std::string::npos) << oss.str();
33   } else if (num_objects == 1) {
34     EXPECT_NE(oss.str().find("1 of java.lang.Object"), std::string::npos) << oss.str();
35   } else {
36     EXPECT_NE(oss.str().find(StringPrintf("%zd of java.lang.Object (%zd unique instances)",
37                                           num_objects, num_unique)),
38               std::string::npos)
39                   << "\n Expected number of objects: " << num_objects
40                   << "\n Expected unique objects: " << num_unique << "\n"
41                   << oss.str();
42   }
43 }
44 
TEST_F(IndirectReferenceTableTest,BasicTest)45 TEST_F(IndirectReferenceTableTest, BasicTest) {
46   ScopedObjectAccess soa(Thread::Current());
47   static const size_t kTableInitial = 10;
48   static const size_t kTableMax = 20;
49   IndirectReferenceTable irt(kTableInitial, kTableMax, kGlobal);
50 
51   mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
52   ASSERT_TRUE(c != NULL);
53   mirror::Object* obj0 = c->AllocObject(soa.Self());
54   ASSERT_TRUE(obj0 != NULL);
55   mirror::Object* obj1 = c->AllocObject(soa.Self());
56   ASSERT_TRUE(obj1 != NULL);
57   mirror::Object* obj2 = c->AllocObject(soa.Self());
58   ASSERT_TRUE(obj2 != NULL);
59   mirror::Object* obj3 = c->AllocObject(soa.Self());
60   ASSERT_TRUE(obj3 != NULL);
61 
62   const uint32_t cookie = IRT_FIRST_SEGMENT;
63 
64   CheckDump(&irt, 0, 0);
65 
66   IndirectRef iref0 = (IndirectRef) 0x11110;
67   EXPECT_FALSE(irt.Remove(cookie, iref0)) << "unexpectedly successful removal";
68 
69   // Add three, check, remove in the order in which they were added.
70   iref0 = irt.Add(cookie, obj0);
71   EXPECT_TRUE(iref0 != NULL);
72   CheckDump(&irt, 1, 1);
73   IndirectRef iref1 = irt.Add(cookie, obj1);
74   EXPECT_TRUE(iref1 != NULL);
75   CheckDump(&irt, 2, 2);
76   IndirectRef iref2 = irt.Add(cookie, obj2);
77   EXPECT_TRUE(iref2 != NULL);
78   CheckDump(&irt, 3, 3);
79 
80   EXPECT_EQ(obj0, irt.Get(iref0));
81   EXPECT_EQ(obj1, irt.Get(iref1));
82   EXPECT_EQ(obj2, irt.Get(iref2));
83 
84   EXPECT_TRUE(irt.Remove(cookie, iref0));
85   CheckDump(&irt, 2, 2);
86   EXPECT_TRUE(irt.Remove(cookie, iref1));
87   CheckDump(&irt, 1, 1);
88   EXPECT_TRUE(irt.Remove(cookie, iref2));
89   CheckDump(&irt, 0, 0);
90 
91   // Table should be empty now.
92   EXPECT_EQ(0U, irt.Capacity());
93 
94   // Get invalid entry (off the end of the list).
95   EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref0));
96 
97   // Add three, remove in the opposite order.
98   iref0 = irt.Add(cookie, obj0);
99   EXPECT_TRUE(iref0 != NULL);
100   iref1 = irt.Add(cookie, obj1);
101   EXPECT_TRUE(iref1 != NULL);
102   iref2 = irt.Add(cookie, obj2);
103   EXPECT_TRUE(iref2 != NULL);
104   CheckDump(&irt, 3, 3);
105 
106   ASSERT_TRUE(irt.Remove(cookie, iref2));
107   CheckDump(&irt, 2, 2);
108   ASSERT_TRUE(irt.Remove(cookie, iref1));
109   CheckDump(&irt, 1, 1);
110   ASSERT_TRUE(irt.Remove(cookie, iref0));
111   CheckDump(&irt, 0, 0);
112 
113   // Table should be empty now.
114   ASSERT_EQ(0U, irt.Capacity());
115 
116   // Add three, remove middle / middle / bottom / top.  (Second attempt
117   // to remove middle should fail.)
118   iref0 = irt.Add(cookie, obj0);
119   EXPECT_TRUE(iref0 != NULL);
120   iref1 = irt.Add(cookie, obj1);
121   EXPECT_TRUE(iref1 != NULL);
122   iref2 = irt.Add(cookie, obj2);
123   EXPECT_TRUE(iref2 != NULL);
124   CheckDump(&irt, 3, 3);
125 
126   ASSERT_EQ(3U, irt.Capacity());
127 
128   ASSERT_TRUE(irt.Remove(cookie, iref1));
129   CheckDump(&irt, 2, 2);
130   ASSERT_FALSE(irt.Remove(cookie, iref1));
131   CheckDump(&irt, 2, 2);
132 
133   // Get invalid entry (from hole).
134   EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref1));
135 
136   ASSERT_TRUE(irt.Remove(cookie, iref2));
137   CheckDump(&irt, 1, 1);
138   ASSERT_TRUE(irt.Remove(cookie, iref0));
139   CheckDump(&irt, 0, 0);
140 
141   // Table should be empty now.
142   ASSERT_EQ(0U, irt.Capacity());
143 
144   // Add four entries.  Remove #1, add new entry, verify that table size
145   // is still 4 (i.e. holes are getting filled).  Remove #1 and #3, verify
146   // that we delete one and don't hole-compact the other.
147   iref0 = irt.Add(cookie, obj0);
148   EXPECT_TRUE(iref0 != NULL);
149   iref1 = irt.Add(cookie, obj1);
150   EXPECT_TRUE(iref1 != NULL);
151   iref2 = irt.Add(cookie, obj2);
152   EXPECT_TRUE(iref2 != NULL);
153   IndirectRef iref3 = irt.Add(cookie, obj3);
154   EXPECT_TRUE(iref3 != NULL);
155   CheckDump(&irt, 4, 4);
156 
157   ASSERT_TRUE(irt.Remove(cookie, iref1));
158   CheckDump(&irt, 3, 3);
159 
160   iref1 = irt.Add(cookie, obj1);
161   EXPECT_TRUE(iref1 != NULL);
162 
163   ASSERT_EQ(4U, irt.Capacity()) << "hole not filled";
164   CheckDump(&irt, 4, 4);
165 
166   ASSERT_TRUE(irt.Remove(cookie, iref1));
167   CheckDump(&irt, 3, 3);
168   ASSERT_TRUE(irt.Remove(cookie, iref3));
169   CheckDump(&irt, 2, 2);
170 
171   ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions";
172 
173   ASSERT_TRUE(irt.Remove(cookie, iref2));
174   CheckDump(&irt, 1, 1);
175   ASSERT_TRUE(irt.Remove(cookie, iref0));
176   CheckDump(&irt, 0, 0);
177 
178   ASSERT_EQ(0U, irt.Capacity()) << "not empty after split remove";
179 
180   // Add an entry, remove it, add a new entry, and try to use the original
181   // iref.  They have the same slot number but are for different objects.
182   // With the extended checks in place, this should fail.
183   iref0 = irt.Add(cookie, obj0);
184   EXPECT_TRUE(iref0 != NULL);
185   CheckDump(&irt, 1, 1);
186   ASSERT_TRUE(irt.Remove(cookie, iref0));
187   CheckDump(&irt, 0, 0);
188   iref1 = irt.Add(cookie, obj1);
189   EXPECT_TRUE(iref1 != NULL);
190   CheckDump(&irt, 1, 1);
191   ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded";
192   CheckDump(&irt, 1, 1);
193   ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed";
194   ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty";
195   CheckDump(&irt, 0, 0);
196 
197   // Same as above, but with the same object.  A more rigorous checker
198   // (e.g. with slot serialization) will catch this.
199   iref0 = irt.Add(cookie, obj0);
200   EXPECT_TRUE(iref0 != NULL);
201   CheckDump(&irt, 1, 1);
202   ASSERT_TRUE(irt.Remove(cookie, iref0));
203   CheckDump(&irt, 0, 0);
204   iref1 = irt.Add(cookie, obj0);
205   EXPECT_TRUE(iref1 != NULL);
206   CheckDump(&irt, 1, 1);
207   if (iref0 != iref1) {
208     // Try 0, should not work.
209     ASSERT_FALSE(irt.Remove(cookie, iref0)) << "temporal del succeeded";
210   }
211   ASSERT_TRUE(irt.Remove(cookie, iref1)) << "temporal cleanup failed";
212   ASSERT_EQ(0U, irt.Capacity()) << "temporal del not empty";
213   CheckDump(&irt, 0, 0);
214 
215   // NULL isn't a valid iref.
216   ASSERT_EQ(kInvalidIndirectRefObject, irt.Get(NULL));
217 
218   // Stale lookup.
219   iref0 = irt.Add(cookie, obj0);
220   EXPECT_TRUE(iref0 != NULL);
221   CheckDump(&irt, 1, 1);
222   ASSERT_TRUE(irt.Remove(cookie, iref0));
223   EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref0)) << "stale lookup succeeded";
224   CheckDump(&irt, 0, 0);
225 
226   // Test table resizing.
227   // These ones fit...
228   IndirectRef manyRefs[kTableInitial];
229   for (size_t i = 0; i < kTableInitial; i++) {
230     manyRefs[i] = irt.Add(cookie, obj0);
231     ASSERT_TRUE(manyRefs[i] != NULL) << "Failed adding " << i;
232     CheckDump(&irt, i + 1, 1);
233   }
234   // ...this one causes overflow.
235   iref0 = irt.Add(cookie, obj0);
236   ASSERT_TRUE(iref0 != NULL);
237   ASSERT_EQ(kTableInitial + 1, irt.Capacity());
238   CheckDump(&irt, kTableInitial + 1, 1);
239 
240   for (size_t i = 0; i < kTableInitial; i++) {
241     ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i;
242     CheckDump(&irt, kTableInitial - i, 1);
243   }
244   // Because of removal order, should have 11 entries, 10 of them holes.
245   ASSERT_EQ(kTableInitial + 1, irt.Capacity());
246 
247   ASSERT_TRUE(irt.Remove(cookie, iref0)) << "multi-remove final failed";
248 
249   ASSERT_EQ(0U, irt.Capacity()) << "multi-del not empty";
250   CheckDump(&irt, 0, 0);
251 }
252 
253 }  // namespace art
254