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