Elliott Hughes | 2faa5f1 | 2012-01-30 14:42:07 -0800 | [diff] [blame] | 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 | */ |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 16 | |
| 17 | #include "intern_table.h" |
| 18 | |
Alexey Grebenkin | 21f2364 | 2016-12-02 17:44:54 +0300 | [diff] [blame] | 19 | #include "base/hash_set.h" |
Brian Carlstrom | a1ce1fe | 2014-02-24 23:23:58 -0800 | [diff] [blame] | 20 | #include "common_runtime_test.h" |
David Sehr | 0225f8e | 2018-01-31 08:52:24 +0000 | [diff] [blame^] | 21 | #include "dex/utf.h" |
Andreas Gampe | c15a2f4 | 2017-04-21 12:09:39 -0700 | [diff] [blame] | 22 | #include "gc_root-inl.h" |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 23 | #include "handle_scope-inl.h" |
Andreas Gampe | 8cf9cb3 | 2017-07-19 09:28:38 -0700 | [diff] [blame] | 24 | #include "mirror/object.h" |
Ian Rogers | e63db27 | 2014-07-15 15:36:11 -0700 | [diff] [blame] | 25 | #include "mirror/string.h" |
Mathieu Chartier | 0795f23 | 2016-09-27 18:43:30 -0700 | [diff] [blame] | 26 | #include "scoped_thread_state_change-inl.h" |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 27 | |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 28 | namespace art { |
| 29 | |
Brian Carlstrom | a1ce1fe | 2014-02-24 23:23:58 -0800 | [diff] [blame] | 30 | class InternTableTest : public CommonRuntimeTest {}; |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 31 | |
| 32 | TEST_F(InternTableTest, Intern) { |
Ian Rogers | 00f7d0e | 2012-07-19 15:28:27 -0700 | [diff] [blame] | 33 | ScopedObjectAccess soa(Thread::Current()); |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 34 | InternTable intern_table; |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 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"))); |
Andreas Gampe | fa4333d | 2017-02-14 11:10:34 -0800 | [diff] [blame] | 41 | ASSERT_TRUE(foo_1 != nullptr); |
| 42 | ASSERT_TRUE(foo_2 != nullptr); |
| 43 | ASSERT_TRUE(foo_3 != nullptr); |
| 44 | ASSERT_TRUE(bar != nullptr); |
Vladimir Marko | cac5a7e | 2016-02-22 10:39:50 +0000 | [diff] [blame] | 45 | EXPECT_EQ(foo_1.Get(), foo_2.Get()); |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 46 | EXPECT_TRUE(foo_1->Equals("foo")); |
| 47 | EXPECT_TRUE(foo_2->Equals("foo")); |
| 48 | EXPECT_TRUE(foo_3->Equals("foo")); |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 49 | EXPECT_NE(foo_1.Get(), bar.Get()); |
| 50 | EXPECT_NE(foo_2.Get(), bar.Get()); |
| 51 | EXPECT_NE(foo_3.Get(), bar.Get()); |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 52 | } |
| 53 | |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 54 | TEST_F(InternTableTest, Size) { |
Ian Rogers | 00f7d0e | 2012-07-19 15:28:27 -0700 | [diff] [blame] | 55 | ScopedObjectAccess soa(Thread::Current()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 56 | InternTable t; |
| 57 | EXPECT_EQ(0U, t.Size()); |
| 58 | t.InternStrong(3, "foo"); |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 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()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 63 | EXPECT_EQ(1U, t.Size()); |
| 64 | t.InternStrong(3, "bar"); |
| 65 | EXPECT_EQ(2U, t.Size()); |
| 66 | } |
| 67 | |
Alexey Grebenkin | 21f2364 | 2016-12-02 17:44:54 +0300 | [diff] [blame] | 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 | |
Mathieu Chartier | 9750995 | 2015-07-13 14:35:43 -0700 | [diff] [blame] | 87 | class TestPredicate : public IsMarkedVisitor { |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 88 | public: |
Andreas Gampe | bdf7f1c | 2016-08-30 16:38:47 -0700 | [diff] [blame] | 89 | mirror::Object* IsMarked(mirror::Object* s) OVERRIDE REQUIRES_SHARED(Locks::mutator_lock_) { |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 90 | bool erased = false; |
Mathieu Chartier | 02e2511 | 2013-08-14 16:14:24 -0700 | [diff] [blame] | 91 | for (auto it = expected_.begin(), end = expected_.end(); it != end; ++it) { |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 92 | if (*it == s) { |
| 93 | expected_.erase(it); |
| 94 | erased = true; |
| 95 | break; |
| 96 | } |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 97 | } |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 98 | EXPECT_TRUE(erased); |
Mathieu Chartier | 9750995 | 2015-07-13 14:35:43 -0700 | [diff] [blame] | 99 | return nullptr; |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 100 | } |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 101 | |
Ian Rogers | 2dd0e2c | 2013-01-24 12:42:14 -0800 | [diff] [blame] | 102 | void Expect(const mirror::String* s) { |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 103 | expected_.push_back(s); |
| 104 | } |
| 105 | |
| 106 | ~TestPredicate() { |
| 107 | EXPECT_EQ(0U, expected_.size()); |
| 108 | } |
| 109 | |
| 110 | private: |
Ian Rogers | 2dd0e2c | 2013-01-24 12:42:14 -0800 | [diff] [blame] | 111 | mutable std::vector<const mirror::String*> expected_; |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 112 | }; |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 113 | |
Elliott Hughes | c33a32b | 2011-10-11 18:18:07 -0700 | [diff] [blame] | 114 | TEST_F(InternTableTest, SweepInternTableWeaks) { |
Ian Rogers | 00f7d0e | 2012-07-19 15:28:27 -0700 | [diff] [blame] | 115 | ScopedObjectAccess soa(Thread::Current()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 116 | InternTable t; |
| 117 | t.InternStrong(3, "foo"); |
| 118 | t.InternStrong(3, "bar"); |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 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()))); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 126 | |
| 127 | EXPECT_EQ(4U, t.Size()); |
| 128 | |
| 129 | // We should traverse only the weaks... |
Elliott Hughes | 410c0c8 | 2011-09-01 17:58:25 -0700 | [diff] [blame] | 130 | TestPredicate p; |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 131 | p.Expect(s0.Get()); |
| 132 | p.Expect(s1.Get()); |
Ian Rogers | 00f7d0e | 2012-07-19 15:28:27 -0700 | [diff] [blame] | 133 | { |
Ian Rogers | 1f53934 | 2012-10-03 21:09:42 -0700 | [diff] [blame] | 134 | ReaderMutexLock mu(soa.Self(), *Locks::heap_bitmap_lock_); |
Mathieu Chartier | 9750995 | 2015-07-13 14:35:43 -0700 | [diff] [blame] | 135 | t.SweepInternTableWeaks(&p); |
Ian Rogers | 00f7d0e | 2012-07-19 15:28:27 -0700 | [diff] [blame] | 136 | } |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 137 | |
| 138 | EXPECT_EQ(2U, t.Size()); |
| 139 | |
Elliott Hughes | e5448b5 | 2012-01-18 16:44:06 -0800 | [diff] [blame] | 140 | // Just check that we didn't corrupt the map. |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 141 | Handle<mirror::String> still_here( |
| 142 | hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "still here"))); |
| 143 | t.InternWeak(still_here.Get()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 144 | EXPECT_EQ(3U, t.Size()); |
| 145 | } |
| 146 | |
| 147 | TEST_F(InternTableTest, ContainsWeak) { |
Ian Rogers | 00f7d0e | 2012-07-19 15:28:27 -0700 | [diff] [blame] | 148 | ScopedObjectAccess soa(Thread::Current()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 149 | { |
| 150 | // Strongs are never weak. |
| 151 | InternTable t; |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 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()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 158 | } |
| 159 | |
| 160 | { |
| 161 | // Weaks are always weak. |
| 162 | InternTable t; |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 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()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 173 | } |
| 174 | |
| 175 | { |
| 176 | // A weak can be promoted to a strong. |
| 177 | InternTable t; |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 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()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 186 | } |
| 187 | |
| 188 | { |
| 189 | // Interning a weak after a strong gets you the strong. |
| 190 | InternTable t; |
Mathieu Chartier | eb8167a | 2014-05-07 15:43:14 -0700 | [diff] [blame] | 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()); |
Elliott Hughes | cf4c6c4 | 2011-09-01 15:16:42 -0700 | [diff] [blame] | 199 | } |
| 200 | } |
| 201 | |
Vladimir Marko | cac5a7e | 2016-02-22 10:39:50 +0000 | [diff] [blame] | 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"))); |
Andreas Gampe | fa4333d | 2017-02-14 11:10:34 -0800 | [diff] [blame] | 209 | ASSERT_TRUE(foo != nullptr); |
| 210 | ASSERT_TRUE(bar != nullptr); |
| 211 | ASSERT_TRUE(foobar != nullptr); |
Vladimir Marko | cac5a7e | 2016-02-22 10:39:50 +0000 | [diff] [blame] | 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()); |
Mathieu Chartier | 9e86809 | 2016-10-31 14:58:04 -0700 | [diff] [blame] | 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"); |
Vladimir Marko | cac5a7e | 2016-02-22 10:39:50 +0000 | [diff] [blame] | 225 | EXPECT_TRUE(lookup_foox == nullptr); |
Mathieu Chartier | 9e86809 | 2016-10-31 14:58:04 -0700 | [diff] [blame] | 226 | ObjPtr<mirror::String> lookup_fooba = intern_table.LookupStrong(soa.Self(), 5, "fooba"); |
Vladimir Marko | cac5a7e | 2016-02-22 10:39:50 +0000 | [diff] [blame] | 227 | EXPECT_TRUE(lookup_fooba == nullptr); |
Mathieu Chartier | 9e86809 | 2016-10-31 14:58:04 -0700 | [diff] [blame] | 228 | ObjPtr<mirror::String> lookup_foobaR = intern_table.LookupStrong(soa.Self(), 6, "foobaR"); |
Vladimir Marko | cac5a7e | 2016-02-22 10:39:50 +0000 | [diff] [blame] | 229 | EXPECT_TRUE(lookup_foobaR == nullptr); |
| 230 | // Try a hash conflict. |
| 231 | ASSERT_EQ(ComputeUtf16HashFromModifiedUtf8("foobar", 6), |
| 232 | ComputeUtf16HashFromModifiedUtf8("foobbS", 6)); |
Mathieu Chartier | 9e86809 | 2016-10-31 14:58:04 -0700 | [diff] [blame] | 233 | ObjPtr<mirror::String> lookup_foobbS = intern_table.LookupStrong(soa.Self(), 6, "foobbS"); |
Vladimir Marko | cac5a7e | 2016-02-22 10:39:50 +0000 | [diff] [blame] | 234 | EXPECT_TRUE(lookup_foobbS == nullptr); |
| 235 | } |
| 236 | |
Brian Carlstrom | 7e93b50 | 2011-08-04 14:16:22 -0700 | [diff] [blame] | 237 | } // namespace art |