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
23namespace art {
24
25class IndirectReferenceTableTest : public CommonRuntimeTest {};
26
27static 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
45TEST_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