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