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 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 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
