1 /* 2 * Copyright (C) 2011 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 "intern_table.h" 18 19 #include "base/hash_set.h" 20 #include "common_runtime_test.h" 21 #include "dex/utf.h" 22 #include "gc_root-inl.h" 23 #include "handle_scope-inl.h" 24 #include "mirror/object.h" 25 #include "mirror/string.h" 26 #include "scoped_thread_state_change-inl.h" 27 28 namespace art { 29 30 class InternTableTest : public CommonRuntimeTest {}; 31 32 TEST_F(InternTableTest, Intern) { 33 ScopedObjectAccess soa(Thread::Current()); 34 InternTable intern_table; 35 StackHandleScope<4> hs(soa.Self()); 36 Handle<mirror::String> foo_1(hs.NewHandle(intern_table.InternStrong(3, "foo"))); 37 Handle<mirror::String> foo_2(hs.NewHandle(intern_table.InternStrong(3, "foo"))); 38 Handle<mirror::String> foo_3( 39 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo"))); 40 Handle<mirror::String> bar(hs.NewHandle(intern_table.InternStrong(3, "bar"))); 41 ASSERT_TRUE(foo_1 != nullptr); 42 ASSERT_TRUE(foo_2 != nullptr); 43 ASSERT_TRUE(foo_3 != nullptr); 44 ASSERT_TRUE(bar != nullptr); 45 EXPECT_EQ(foo_1.Get(), foo_2.Get()); 46 EXPECT_TRUE(foo_1->Equals("foo")); 47 EXPECT_TRUE(foo_2->Equals("foo")); 48 EXPECT_TRUE(foo_3->Equals("foo")); 49 EXPECT_NE(foo_1.Get(), bar.Get()); 50 EXPECT_NE(foo_2.Get(), bar.Get()); 51 EXPECT_NE(foo_3.Get(), bar.Get()); 52 } 53 54 TEST_F(InternTableTest, Size) { 55 ScopedObjectAccess soa(Thread::Current()); 56 InternTable t; 57 EXPECT_EQ(0U, t.Size()); 58 t.InternStrong(3, "foo"); 59 StackHandleScope<1> hs(soa.Self()); 60 Handle<mirror::String> foo( 61 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo"))); 62 t.InternWeak(foo.Get()); 63 EXPECT_EQ(1U, t.Size()); 64 t.InternStrong(3, "bar"); 65 EXPECT_EQ(2U, t.Size()); 66 } 67 68 // Check if table indexes match on 64 and 32 bit machines. 69 // This is done by ensuring hash values are the same on every machine and limited to 32-bit wide. 70 // Otherwise cross compilation can cause a table to be filled on host using one indexing algorithm 71 // and later on a device with different sizeof(size_t) can use another indexing algorithm. 72 // Thus the table may provide wrong data. 73 TEST_F(InternTableTest, CrossHash) { 74 ScopedObjectAccess soa(Thread::Current()); 75 InternTable t; 76 77 // A string that has a negative hash value. 78 GcRoot<mirror::String> str(mirror::String::AllocFromModifiedUtf8(soa.Self(), "00000000")); 79 80 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 81 for (InternTable::Table::UnorderedSet& table : t.strong_interns_.tables_) { 82 // The negative hash value shall be 32-bit wide on every host. 83 ASSERT_TRUE(IsUint<32>(table.hashfn_(str))); 84 } 85 } 86 87 class TestPredicate : public IsMarkedVisitor { 88 public: 89 mirror::Object* IsMarked(mirror::Object* s) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) { 90 bool erased = false; 91 for (auto it = expected_.begin(), end = expected_.end(); it != end; ++it) { 92 if (*it == s) { 93 expected_.erase(it); 94 erased = true; 95 break; 96 } 97 } 98 EXPECT_TRUE(erased); 99 return nullptr; 100 } 101 102 void Expect(const mirror::String* s) { 103 expected_.push_back(s); 104 } 105 106 ~TestPredicate() { 107 EXPECT_EQ(0U, expected_.size()); 108 } 109 110 private: 111 mutable std::vector<const mirror::String*> expected_; 112 }; 113 114 TEST_F(InternTableTest, SweepInternTableWeaks) { 115 ScopedObjectAccess soa(Thread::Current()); 116 InternTable t; 117 t.InternStrong(3, "foo"); 118 t.InternStrong(3, "bar"); 119 StackHandleScope<5> hs(soa.Self()); 120 Handle<mirror::String> hello( 121 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "hello"))); 122 Handle<mirror::String> world( 123 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "world"))); 124 Handle<mirror::String> s0(hs.NewHandle(t.InternWeak(hello.Get()))); 125 Handle<mirror::String> s1(hs.NewHandle(t.InternWeak(world.Get()))); 126 127 EXPECT_EQ(4U, t.Size()); 128 129 // We should traverse only the weaks... 130 TestPredicate p; 131 p.Expect(s0.Get()); 132 p.Expect(s1.Get()); 133 { 134 ReaderMutexLock mu(soa.Self(), *Locks::heap_bitmap_lock_); 135 t.SweepInternTableWeaks(&p); 136 } 137 138 EXPECT_EQ(2U, t.Size()); 139 140 // Just check that we didn't corrupt the map. 141 Handle<mirror::String> still_here( 142 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "still here"))); 143 t.InternWeak(still_here.Get()); 144 EXPECT_EQ(3U, t.Size()); 145 } 146 147 TEST_F(InternTableTest, ContainsWeak) { 148 ScopedObjectAccess soa(Thread::Current()); 149 { 150 // Strongs are never weak. 151 InternTable t; 152 StackHandleScope<2> hs(soa.Self()); 153 Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternStrong(3, "foo"))); 154 EXPECT_FALSE(t.ContainsWeak(interned_foo_1.Get())); 155 Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternStrong(3, "foo"))); 156 EXPECT_FALSE(t.ContainsWeak(interned_foo_2.Get())); 157 EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get()); 158 } 159 160 { 161 // Weaks are always weak. 162 InternTable t; 163 StackHandleScope<4> hs(soa.Self()); 164 Handle<mirror::String> foo_1( 165 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo"))); 166 Handle<mirror::String> foo_2( 167 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo"))); 168 EXPECT_NE(foo_1.Get(), foo_2.Get()); 169 Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternWeak(foo_1.Get()))); 170 Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternWeak(foo_2.Get()))); 171 EXPECT_TRUE(t.ContainsWeak(interned_foo_2.Get())); 172 EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get()); 173 } 174 175 { 176 // A weak can be promoted to a strong. 177 InternTable t; 178 StackHandleScope<3> hs(soa.Self()); 179 Handle<mirror::String> foo( 180 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo"))); 181 Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternWeak(foo.Get()))); 182 EXPECT_TRUE(t.ContainsWeak(interned_foo_1.Get())); 183 Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternStrong(3, "foo"))); 184 EXPECT_FALSE(t.ContainsWeak(interned_foo_2.Get())); 185 EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get()); 186 } 187 188 { 189 // Interning a weak after a strong gets you the strong. 190 InternTable t; 191 StackHandleScope<3> hs(soa.Self()); 192 Handle<mirror::String> interned_foo_1(hs.NewHandle(t.InternStrong(3, "foo"))); 193 EXPECT_FALSE(t.ContainsWeak(interned_foo_1.Get())); 194 Handle<mirror::String> foo( 195 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "foo"))); 196 Handle<mirror::String> interned_foo_2(hs.NewHandle(t.InternWeak(foo.Get()))); 197 EXPECT_FALSE(t.ContainsWeak(interned_foo_2.Get())); 198 EXPECT_EQ(interned_foo_1.Get(), interned_foo_2.Get()); 199 } 200 } 201 202 TEST_F(InternTableTest, LookupStrong) { 203 ScopedObjectAccess soa(Thread::Current()); 204 InternTable intern_table; 205 StackHandleScope<3> hs(soa.Self()); 206 Handle<mirror::String> foo(hs.NewHandle(intern_table.InternStrong(3, "foo"))); 207 Handle<mirror::String> bar(hs.NewHandle(intern_table.InternStrong(3, "bar"))); 208 Handle<mirror::String> foobar(hs.NewHandle(intern_table.InternStrong(6, "foobar"))); 209 ASSERT_TRUE(foo != nullptr); 210 ASSERT_TRUE(bar != nullptr); 211 ASSERT_TRUE(foobar != nullptr); 212 ASSERT_TRUE(foo->Equals("foo")); 213 ASSERT_TRUE(bar->Equals("bar")); 214 ASSERT_TRUE(foobar->Equals("foobar")); 215 ASSERT_NE(foo.Get(), bar.Get()); 216 ASSERT_NE(foo.Get(), foobar.Get()); 217 ASSERT_NE(bar.Get(), foobar.Get()); 218 ObjPtr<mirror::String> lookup_foo = intern_table.LookupStrong(soa.Self(), 3, "foo"); 219 EXPECT_OBJ_PTR_EQ(lookup_foo, foo.Get()); 220 ObjPtr<mirror::String> lookup_bar = intern_table.LookupStrong(soa.Self(), 3, "bar"); 221 EXPECT_OBJ_PTR_EQ(lookup_bar, bar.Get()); 222 ObjPtr<mirror::String> lookup_foobar = intern_table.LookupStrong(soa.Self(), 6, "foobar"); 223 EXPECT_OBJ_PTR_EQ(lookup_foobar, foobar.Get()); 224 ObjPtr<mirror::String> lookup_foox = intern_table.LookupStrong(soa.Self(), 4, "foox"); 225 EXPECT_TRUE(lookup_foox == nullptr); 226 ObjPtr<mirror::String> lookup_fooba = intern_table.LookupStrong(soa.Self(), 5, "fooba"); 227 EXPECT_TRUE(lookup_fooba == nullptr); 228 ObjPtr<mirror::String> lookup_foobaR = intern_table.LookupStrong(soa.Self(), 6, "foobaR"); 229 EXPECT_TRUE(lookup_foobaR == nullptr); 230 // Try a hash conflict. 231 ASSERT_EQ(ComputeUtf16HashFromModifiedUtf8("foobar", 6), 232 ComputeUtf16HashFromModifiedUtf8("foobbS", 6)); 233 ObjPtr<mirror::String> lookup_foobbS = intern_table.LookupStrong(soa.Self(), 6, "foobbS"); 234 EXPECT_TRUE(lookup_foobbS == nullptr); 235 } 236 237 } // namespace art 238
