blob: 9b42e59028a1295f830f058fc2aa9c996571cbe8 [file] [log] [blame]
Elliott Hughes6c1a3942011-08-17 15:00:06 -07001/*
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
Elliott Hughes6c1a3942011-08-17 15:00:06 -070017#include "indirect_reference_table.h"
Brian Carlstroma1ce1fe2014-02-24 23:23:58 -080018
19#include "common_runtime_test.h"
Hiroshi Yamauchi967a0ad2013-09-10 16:24:21 -070020#include "mirror/object-inl.h"
Elliott Hughes6c1a3942011-08-17 15:00:06 -070021
Elliott Hughes6c1a3942011-08-17 15:00:06 -070022namespace art {
23
Brian Carlstroma1ce1fe2014-02-24 23:23:58 -080024class IndirectReferenceTableTest : public CommonRuntimeTest {};
Elliott Hughes6c1a3942011-08-17 15:00:06 -070025
Ian Rogers63818dc2012-09-26 12:23:04 -070026static void CheckDump(IndirectReferenceTable* irt, size_t num_objects, size_t num_unique)
27 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
28 std::ostringstream oss;
29 irt->Dump(oss);
30 if (num_objects == 0) {
31 EXPECT_EQ(oss.str().find("java.lang.Object"), std::string::npos) << oss.str();
32 } else if (num_objects == 1) {
33 EXPECT_NE(oss.str().find("1 of java.lang.Object"), std::string::npos) << oss.str();
34 } else {
35 EXPECT_NE(oss.str().find(StringPrintf("%zd of java.lang.Object (%zd unique instances)",
36 num_objects, num_unique)),
37 std::string::npos)
38 << "\n Expected number of objects: " << num_objects
39 << "\n Expected unique objects: " << num_unique << "\n"
40 << oss.str();
41 }
42}
43
Elliott Hughes6c1a3942011-08-17 15:00:06 -070044TEST_F(IndirectReferenceTableTest, BasicTest) {
Ian Rogers00f7d0e2012-07-19 15:28:27 -070045 ScopedObjectAccess soa(Thread::Current());
Elliott Hughes6c1a3942011-08-17 15:00:06 -070046 static const size_t kTableInitial = 10;
47 static const size_t kTableMax = 20;
48 IndirectReferenceTable irt(kTableInitial, kTableMax, kGlobal);
49
Ian Rogers98379392014-02-24 16:53:16 -080050 mirror::Class* c = class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Object;");
Elliott Hughes6c1a3942011-08-17 15:00:06 -070051 ASSERT_TRUE(c != NULL);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080052 mirror::Object* obj0 = c->AllocObject(soa.Self());
Elliott Hughes6c1a3942011-08-17 15:00:06 -070053 ASSERT_TRUE(obj0 != NULL);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080054 mirror::Object* obj1 = c->AllocObject(soa.Self());
Elliott Hughes6c1a3942011-08-17 15:00:06 -070055 ASSERT_TRUE(obj1 != NULL);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080056 mirror::Object* obj2 = c->AllocObject(soa.Self());
Elliott Hughes6c1a3942011-08-17 15:00:06 -070057 ASSERT_TRUE(obj2 != NULL);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080058 mirror::Object* obj3 = c->AllocObject(soa.Self());
Elliott Hughes6c1a3942011-08-17 15:00:06 -070059 ASSERT_TRUE(obj3 != NULL);
60
61 const uint32_t cookie = IRT_FIRST_SEGMENT;
62
Ian Rogers63818dc2012-09-26 12:23:04 -070063 CheckDump(&irt, 0, 0);
64
Elliott Hughes6c1a3942011-08-17 15:00:06 -070065 IndirectRef iref0 = (IndirectRef) 0x11110;
66 EXPECT_FALSE(irt.Remove(cookie, iref0)) << "unexpectedly successful removal";
67
68 // Add three, check, remove in the order in which they were added.
69 iref0 = irt.Add(cookie, obj0);
70 EXPECT_TRUE(iref0 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -070071 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -070072 IndirectRef iref1 = irt.Add(cookie, obj1);
73 EXPECT_TRUE(iref1 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -070074 CheckDump(&irt, 2, 2);
Elliott Hughes6c1a3942011-08-17 15:00:06 -070075 IndirectRef iref2 = irt.Add(cookie, obj2);
76 EXPECT_TRUE(iref2 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -070077 CheckDump(&irt, 3, 3);
Elliott Hughes6c1a3942011-08-17 15:00:06 -070078
79 EXPECT_EQ(obj0, irt.Get(iref0));
80 EXPECT_EQ(obj1, irt.Get(iref1));
81 EXPECT_EQ(obj2, irt.Get(iref2));
82
83 EXPECT_TRUE(irt.Remove(cookie, iref0));
Ian Rogers63818dc2012-09-26 12:23:04 -070084 CheckDump(&irt, 2, 2);
Elliott Hughes6c1a3942011-08-17 15:00:06 -070085 EXPECT_TRUE(irt.Remove(cookie, iref1));
Ian Rogers63818dc2012-09-26 12:23:04 -070086 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -070087 EXPECT_TRUE(irt.Remove(cookie, iref2));
Ian Rogers63818dc2012-09-26 12:23:04 -070088 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -070089
90 // Table should be empty now.
91 EXPECT_EQ(0U, irt.Capacity());
92
93 // Get invalid entry (off the end of the list).
94 EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref0));
95
96 // Add three, remove in the opposite order.
97 iref0 = irt.Add(cookie, obj0);
98 EXPECT_TRUE(iref0 != NULL);
99 iref1 = irt.Add(cookie, obj1);
100 EXPECT_TRUE(iref1 != NULL);
101 iref2 = irt.Add(cookie, obj2);
102 EXPECT_TRUE(iref2 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700103 CheckDump(&irt, 3, 3);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700104
105 ASSERT_TRUE(irt.Remove(cookie, iref2));
Ian Rogers63818dc2012-09-26 12:23:04 -0700106 CheckDump(&irt, 2, 2);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700107 ASSERT_TRUE(irt.Remove(cookie, iref1));
Ian Rogers63818dc2012-09-26 12:23:04 -0700108 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700109 ASSERT_TRUE(irt.Remove(cookie, iref0));
Ian Rogers63818dc2012-09-26 12:23:04 -0700110 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700111
112 // Table should be empty now.
113 ASSERT_EQ(0U, irt.Capacity());
114
115 // Add three, remove middle / middle / bottom / top. (Second attempt
116 // to remove middle should fail.)
117 iref0 = irt.Add(cookie, obj0);
118 EXPECT_TRUE(iref0 != NULL);
119 iref1 = irt.Add(cookie, obj1);
120 EXPECT_TRUE(iref1 != NULL);
121 iref2 = irt.Add(cookie, obj2);
122 EXPECT_TRUE(iref2 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700123 CheckDump(&irt, 3, 3);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700124
125 ASSERT_EQ(3U, irt.Capacity());
126
127 ASSERT_TRUE(irt.Remove(cookie, iref1));
Ian Rogers63818dc2012-09-26 12:23:04 -0700128 CheckDump(&irt, 2, 2);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700129 ASSERT_FALSE(irt.Remove(cookie, iref1));
Ian Rogers63818dc2012-09-26 12:23:04 -0700130 CheckDump(&irt, 2, 2);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700131
132 // Get invalid entry (from hole).
133 EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref1));
134
135 ASSERT_TRUE(irt.Remove(cookie, iref2));
Ian Rogers63818dc2012-09-26 12:23:04 -0700136 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700137 ASSERT_TRUE(irt.Remove(cookie, iref0));
Ian Rogers63818dc2012-09-26 12:23:04 -0700138 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700139
140 // Table should be empty now.
141 ASSERT_EQ(0U, irt.Capacity());
142
143 // Add four entries. Remove #1, add new entry, verify that table size
144 // is still 4 (i.e. holes are getting filled). Remove #1 and #3, verify
145 // that we delete one and don't hole-compact the other.
146 iref0 = irt.Add(cookie, obj0);
147 EXPECT_TRUE(iref0 != NULL);
148 iref1 = irt.Add(cookie, obj1);
149 EXPECT_TRUE(iref1 != NULL);
150 iref2 = irt.Add(cookie, obj2);
151 EXPECT_TRUE(iref2 != NULL);
152 IndirectRef iref3 = irt.Add(cookie, obj3);
153 EXPECT_TRUE(iref3 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700154 CheckDump(&irt, 4, 4);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700155
156 ASSERT_TRUE(irt.Remove(cookie, iref1));
Ian Rogers63818dc2012-09-26 12:23:04 -0700157 CheckDump(&irt, 3, 3);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700158
159 iref1 = irt.Add(cookie, obj1);
160 EXPECT_TRUE(iref1 != NULL);
161
162 ASSERT_EQ(4U, irt.Capacity()) << "hole not filled";
Ian Rogers63818dc2012-09-26 12:23:04 -0700163 CheckDump(&irt, 4, 4);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700164
165 ASSERT_TRUE(irt.Remove(cookie, iref1));
Ian Rogers63818dc2012-09-26 12:23:04 -0700166 CheckDump(&irt, 3, 3);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700167 ASSERT_TRUE(irt.Remove(cookie, iref3));
Ian Rogers63818dc2012-09-26 12:23:04 -0700168 CheckDump(&irt, 2, 2);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700169
170 ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions";
171
172 ASSERT_TRUE(irt.Remove(cookie, iref2));
Ian Rogers63818dc2012-09-26 12:23:04 -0700173 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700174 ASSERT_TRUE(irt.Remove(cookie, iref0));
Ian Rogers63818dc2012-09-26 12:23:04 -0700175 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700176
177 ASSERT_EQ(0U, irt.Capacity()) << "not empty after split remove";
178
179 // Add an entry, remove it, add a new entry, and try to use the original
180 // iref. They have the same slot number but are for different objects.
181 // With the extended checks in place, this should fail.
182 iref0 = irt.Add(cookie, obj0);
183 EXPECT_TRUE(iref0 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700184 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700185 ASSERT_TRUE(irt.Remove(cookie, iref0));
Ian Rogers63818dc2012-09-26 12:23:04 -0700186 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700187 iref1 = irt.Add(cookie, obj1);
188 EXPECT_TRUE(iref1 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700189 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700190 ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded";
Ian Rogers63818dc2012-09-26 12:23:04 -0700191 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700192 ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed";
193 ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty";
Ian Rogers63818dc2012-09-26 12:23:04 -0700194 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700195
196 // Same as above, but with the same object. A more rigorous checker
197 // (e.g. with slot serialization) will catch this.
198 iref0 = irt.Add(cookie, obj0);
199 EXPECT_TRUE(iref0 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700200 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700201 ASSERT_TRUE(irt.Remove(cookie, iref0));
Ian Rogers63818dc2012-09-26 12:23:04 -0700202 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700203 iref1 = irt.Add(cookie, obj0);
204 EXPECT_TRUE(iref1 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700205 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700206 if (iref0 != iref1) {
207 // Try 0, should not work.
208 ASSERT_FALSE(irt.Remove(cookie, iref0)) << "temporal del succeeded";
209 }
210 ASSERT_TRUE(irt.Remove(cookie, iref1)) << "temporal cleanup failed";
211 ASSERT_EQ(0U, irt.Capacity()) << "temporal del not empty";
Ian Rogers63818dc2012-09-26 12:23:04 -0700212 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700213
214 // NULL isn't a valid iref.
215 ASSERT_EQ(kInvalidIndirectRefObject, irt.Get(NULL));
216
217 // Stale lookup.
218 iref0 = irt.Add(cookie, obj0);
219 EXPECT_TRUE(iref0 != NULL);
Ian Rogers63818dc2012-09-26 12:23:04 -0700220 CheckDump(&irt, 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700221 ASSERT_TRUE(irt.Remove(cookie, iref0));
222 EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref0)) << "stale lookup succeeded";
Ian Rogers63818dc2012-09-26 12:23:04 -0700223 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700224
225 // Test table resizing.
226 // These ones fit...
227 IndirectRef manyRefs[kTableInitial];
228 for (size_t i = 0; i < kTableInitial; i++) {
229 manyRefs[i] = irt.Add(cookie, obj0);
230 ASSERT_TRUE(manyRefs[i] != NULL) << "Failed adding " << i;
Ian Rogers63818dc2012-09-26 12:23:04 -0700231 CheckDump(&irt, i + 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700232 }
233 // ...this one causes overflow.
234 iref0 = irt.Add(cookie, obj0);
235 ASSERT_TRUE(iref0 != NULL);
236 ASSERT_EQ(kTableInitial + 1, irt.Capacity());
Ian Rogers63818dc2012-09-26 12:23:04 -0700237 CheckDump(&irt, kTableInitial + 1, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700238
239 for (size_t i = 0; i < kTableInitial; i++) {
240 ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i;
Ian Rogers63818dc2012-09-26 12:23:04 -0700241 CheckDump(&irt, kTableInitial - i, 1);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700242 }
243 // Because of removal order, should have 11 entries, 10 of them holes.
244 ASSERT_EQ(kTableInitial + 1, irt.Capacity());
245
246 ASSERT_TRUE(irt.Remove(cookie, iref0)) << "multi-remove final failed";
247
248 ASSERT_EQ(0U, irt.Capacity()) << "multi-del not empty";
Ian Rogers63818dc2012-09-26 12:23:04 -0700249 CheckDump(&irt, 0, 0);
Elliott Hughes6c1a3942011-08-17 15:00:06 -0700250}
251
252} // namespace art