indirect_reference_table_test.cc revision 3481ba2c4e4f3aa80d8c6d50a9f85dacb56b508b
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 24namespace art { 25 26class IndirectReferenceTableTest : public CommonRuntimeTest {}; 27 28static void CheckDump(IndirectReferenceTable* irt, size_t num_objects, size_t num_unique) 29 SHARED_LOCKS_REQUIRED(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 46TEST_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 // nullptr 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