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 "common_test.h" 18 19 #include "indirect_reference_table.h" 20 21 namespace art { 22 23 class IndirectReferenceTableTest : public CommonTest { 24 }; 25 26 static 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 44 TEST_F(IndirectReferenceTableTest, BasicTest) { 45 ScopedObjectAccess soa(Thread::Current()); 46 static const size_t kTableInitial = 10; 47 static const size_t kTableMax = 20; 48 IndirectReferenceTable irt(kTableInitial, kTableMax, kGlobal); 49 50 mirror::Class* c = class_linker_->FindSystemClass("Ljava/lang/Object;"); 51 ASSERT_TRUE(c != NULL); 52 mirror::Object* obj0 = c->AllocObject(soa.Self()); 53 ASSERT_TRUE(obj0 != NULL); 54 mirror::Object* obj1 = c->AllocObject(soa.Self()); 55 ASSERT_TRUE(obj1 != NULL); 56 mirror::Object* obj2 = c->AllocObject(soa.Self()); 57 ASSERT_TRUE(obj2 != NULL); 58 mirror::Object* obj3 = c->AllocObject(soa.Self()); 59 ASSERT_TRUE(obj3 != NULL); 60 61 const uint32_t cookie = IRT_FIRST_SEGMENT; 62 63 CheckDump(&irt, 0, 0); 64 65 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); 71 CheckDump(&irt, 1, 1); 72 IndirectRef iref1 = irt.Add(cookie, obj1); 73 EXPECT_TRUE(iref1 != NULL); 74 CheckDump(&irt, 2, 2); 75 IndirectRef iref2 = irt.Add(cookie, obj2); 76 EXPECT_TRUE(iref2 != NULL); 77 CheckDump(&irt, 3, 3); 78 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)); 84 CheckDump(&irt, 2, 2); 85 EXPECT_TRUE(irt.Remove(cookie, iref1)); 86 CheckDump(&irt, 1, 1); 87 EXPECT_TRUE(irt.Remove(cookie, iref2)); 88 CheckDump(&irt, 0, 0); 89 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); 103 CheckDump(&irt, 3, 3); 104 105 ASSERT_TRUE(irt.Remove(cookie, iref2)); 106 CheckDump(&irt, 2, 2); 107 ASSERT_TRUE(irt.Remove(cookie, iref1)); 108 CheckDump(&irt, 1, 1); 109 ASSERT_TRUE(irt.Remove(cookie, iref0)); 110 CheckDump(&irt, 0, 0); 111 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); 123 CheckDump(&irt, 3, 3); 124 125 ASSERT_EQ(3U, irt.Capacity()); 126 127 ASSERT_TRUE(irt.Remove(cookie, iref1)); 128 CheckDump(&irt, 2, 2); 129 ASSERT_FALSE(irt.Remove(cookie, iref1)); 130 CheckDump(&irt, 2, 2); 131 132 // Get invalid entry (from hole). 133 EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref1)); 134 135 ASSERT_TRUE(irt.Remove(cookie, iref2)); 136 CheckDump(&irt, 1, 1); 137 ASSERT_TRUE(irt.Remove(cookie, iref0)); 138 CheckDump(&irt, 0, 0); 139 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); 154 CheckDump(&irt, 4, 4); 155 156 ASSERT_TRUE(irt.Remove(cookie, iref1)); 157 CheckDump(&irt, 3, 3); 158 159 iref1 = irt.Add(cookie, obj1); 160 EXPECT_TRUE(iref1 != NULL); 161 162 ASSERT_EQ(4U, irt.Capacity()) << "hole not filled"; 163 CheckDump(&irt, 4, 4); 164 165 ASSERT_TRUE(irt.Remove(cookie, iref1)); 166 CheckDump(&irt, 3, 3); 167 ASSERT_TRUE(irt.Remove(cookie, iref3)); 168 CheckDump(&irt, 2, 2); 169 170 ASSERT_EQ(3U, irt.Capacity()) << "should be 3 after two deletions"; 171 172 ASSERT_TRUE(irt.Remove(cookie, iref2)); 173 CheckDump(&irt, 1, 1); 174 ASSERT_TRUE(irt.Remove(cookie, iref0)); 175 CheckDump(&irt, 0, 0); 176 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); 184 CheckDump(&irt, 1, 1); 185 ASSERT_TRUE(irt.Remove(cookie, iref0)); 186 CheckDump(&irt, 0, 0); 187 iref1 = irt.Add(cookie, obj1); 188 EXPECT_TRUE(iref1 != NULL); 189 CheckDump(&irt, 1, 1); 190 ASSERT_FALSE(irt.Remove(cookie, iref0)) << "mismatched del succeeded"; 191 CheckDump(&irt, 1, 1); 192 ASSERT_TRUE(irt.Remove(cookie, iref1)) << "switched del failed"; 193 ASSERT_EQ(0U, irt.Capacity()) << "switching del not empty"; 194 CheckDump(&irt, 0, 0); 195 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); 200 CheckDump(&irt, 1, 1); 201 ASSERT_TRUE(irt.Remove(cookie, iref0)); 202 CheckDump(&irt, 0, 0); 203 iref1 = irt.Add(cookie, obj0); 204 EXPECT_TRUE(iref1 != NULL); 205 CheckDump(&irt, 1, 1); 206 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"; 212 CheckDump(&irt, 0, 0); 213 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); 220 CheckDump(&irt, 1, 1); 221 ASSERT_TRUE(irt.Remove(cookie, iref0)); 222 EXPECT_EQ(kInvalidIndirectRefObject, irt.Get(iref0)) << "stale lookup succeeded"; 223 CheckDump(&irt, 0, 0); 224 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; 231 CheckDump(&irt, i + 1, 1); 232 } 233 // ...this one causes overflow. 234 iref0 = irt.Add(cookie, obj0); 235 ASSERT_TRUE(iref0 != NULL); 236 ASSERT_EQ(kTableInitial + 1, irt.Capacity()); 237 CheckDump(&irt, kTableInitial + 1, 1); 238 239 for (size_t i = 0; i < kTableInitial; i++) { 240 ASSERT_TRUE(irt.Remove(cookie, manyRefs[i])) << "failed removing " << i; 241 CheckDump(&irt, kTableInitial - i, 1); 242 } 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"; 249 CheckDump(&irt, 0, 0); 250 } 251 252 } // namespace art 253
