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
TEST_F(InternTableTest,Intern)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
TEST_F(InternTableTest,Size)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.
TEST_F(InternTableTest,CrossHash)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:
IsMarked(mirror::Object * s)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
Expect(const mirror::String * s)101 void Expect(const mirror::String* s) {
102 expected_.push_back(s);
103 }
104
~TestPredicate()105 ~TestPredicate() {
106 EXPECT_EQ(0U, expected_.size());
107 }
108
109 private:
110 mutable std::vector<const mirror::String*> expected_;
111 };
112
TEST_F(InternTableTest,SweepInternTableWeaks)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
TEST_F(InternTableTest,ContainsWeak)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
TEST_F(InternTableTest,LookupStrong)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