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