blob: b64ca7dafb9d581d9624ab86aadaf2bb68bb8734 [file] [log] [blame]
Elliott Hughes2faa5f12012-01-30 14:42:07 -08001/*
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 Carlstrom7e93b502011-08-04 14:16:22 -070016
17#include "intern_table.h"
18
Alexey Grebenkin21f23642016-12-02 17:44:54 +030019#include "base/hash_set.h"
Brian Carlstroma1ce1fe2014-02-24 23:23:58 -080020#include "common_runtime_test.h"
David Sehr0225f8e2018-01-31 08:52:24 +000021#include "dex/utf.h"
Andreas Gampec15a2f42017-04-21 12:09:39 -070022#include "gc_root-inl.h"
Mathieu Chartiereb8167a2014-05-07 15:43:14 -070023#include "handle_scope-inl.h"
Andreas Gampe8cf9cb32017-07-19 09:28:38 -070024#include "mirror/object.h"
Ian Rogerse63db272014-07-15 15:36:11 -070025#include "mirror/string.h"
Mathieu Chartier0795f232016-09-27 18:43:30 -070026#include "scoped_thread_state_change-inl.h"
Brian Carlstrom7e93b502011-08-04 14:16:22 -070027
Brian Carlstrom7e93b502011-08-04 14:16:22 -070028namespace art {
29
Brian Carlstroma1ce1fe2014-02-24 23:23:58 -080030class InternTableTest : public CommonRuntimeTest {};
Brian Carlstrom7e93b502011-08-04 14:16:22 -070031
32TEST_F(InternTableTest, Intern) {
Ian Rogers00f7d0e2012-07-19 15:28:27 -070033 ScopedObjectAccess soa(Thread::Current());
Brian Carlstrom7e93b502011-08-04 14:16:22 -070034 InternTable intern_table;
Mathieu Chartiereb8167a2014-05-07 15:43:14 -070035 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 Gampefa4333d2017-02-14 11:10:34 -080041 ASSERT_TRUE(foo_1 != nullptr);
42 ASSERT_TRUE(foo_2 != nullptr);
43 ASSERT_TRUE(foo_3 != nullptr);
44 ASSERT_TRUE(bar != nullptr);
Vladimir Markocac5a7e2016-02-22 10:39:50 +000045 EXPECT_EQ(foo_1.Get(), foo_2.Get());
Brian Carlstrom7e93b502011-08-04 14:16:22 -070046 EXPECT_TRUE(foo_1->Equals("foo"));
47 EXPECT_TRUE(foo_2->Equals("foo"));
48 EXPECT_TRUE(foo_3->Equals("foo"));
Mathieu Chartiereb8167a2014-05-07 15:43:14 -070049 EXPECT_NE(foo_1.Get(), bar.Get());
50 EXPECT_NE(foo_2.Get(), bar.Get());
51 EXPECT_NE(foo_3.Get(), bar.Get());
Brian Carlstrom7e93b502011-08-04 14:16:22 -070052}
53
Elliott Hughescf4c6c42011-09-01 15:16:42 -070054TEST_F(InternTableTest, Size) {
Ian Rogers00f7d0e2012-07-19 15:28:27 -070055 ScopedObjectAccess soa(Thread::Current());
Elliott Hughescf4c6c42011-09-01 15:16:42 -070056 InternTable t;
57 EXPECT_EQ(0U, t.Size());
58 t.InternStrong(3, "foo");
Mathieu Chartiereb8167a2014-05-07 15:43:14 -070059 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 Hughescf4c6c42011-09-01 15:16:42 -070063 EXPECT_EQ(1U, t.Size());
64 t.InternStrong(3, "bar");
65 EXPECT_EQ(2U, t.Size());
66}
67
Alexey Grebenkin21f23642016-12-02 17:44:54 +030068// 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.
73TEST_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_);
Mathieu Chartier8cc418e2018-10-31 10:54:30 -070081 for (InternTable::Table::InternalTable& table : t.strong_interns_.tables_) {
Alexey Grebenkin21f23642016-12-02 17:44:54 +030082 // The negative hash value shall be 32-bit wide on every host.
Mathieu Chartier8cc418e2018-10-31 10:54:30 -070083 ASSERT_TRUE(IsUint<32>(table.set_.hashfn_(str)));
Alexey Grebenkin21f23642016-12-02 17:44:54 +030084 }
85}
86
Mathieu Chartier97509952015-07-13 14:35:43 -070087class TestPredicate : public IsMarkedVisitor {
Elliott Hughes410c0c82011-09-01 17:58:25 -070088 public:
Roland Levillainbbc6e7e2018-08-24 16:58:47 +010089 mirror::Object* IsMarked(mirror::Object* s) override REQUIRES_SHARED(Locks::mutator_lock_) {
Elliott Hughes410c0c82011-09-01 17:58:25 -070090 bool erased = false;
Mathieu Chartier02e25112013-08-14 16:14:24 -070091 for (auto it = expected_.begin(), end = expected_.end(); it != end; ++it) {
Elliott Hughes410c0c82011-09-01 17:58:25 -070092 if (*it == s) {
93 expected_.erase(it);
94 erased = true;
95 break;
96 }
Elliott Hughescf4c6c42011-09-01 15:16:42 -070097 }
Elliott Hughes410c0c82011-09-01 17:58:25 -070098 EXPECT_TRUE(erased);
Mathieu Chartier97509952015-07-13 14:35:43 -070099 return nullptr;
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700100 }
Elliott Hughes410c0c82011-09-01 17:58:25 -0700101
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800102 void Expect(const mirror::String* s) {
Elliott Hughes410c0c82011-09-01 17:58:25 -0700103 expected_.push_back(s);
104 }
105
106 ~TestPredicate() {
107 EXPECT_EQ(0U, expected_.size());
108 }
109
110 private:
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800111 mutable std::vector<const mirror::String*> expected_;
Elliott Hughes410c0c82011-09-01 17:58:25 -0700112};
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700113
Elliott Hughesc33a32b2011-10-11 18:18:07 -0700114TEST_F(InternTableTest, SweepInternTableWeaks) {
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700115 ScopedObjectAccess soa(Thread::Current());
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700116 InternTable t;
117 t.InternStrong(3, "foo");
118 t.InternStrong(3, "bar");
Mathieu Chartiereb8167a2014-05-07 15:43:14 -0700119 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 Hughescf4c6c42011-09-01 15:16:42 -0700126
127 EXPECT_EQ(4U, t.Size());
128
129 // We should traverse only the weaks...
Elliott Hughes410c0c82011-09-01 17:58:25 -0700130 TestPredicate p;
Mathieu Chartiereb8167a2014-05-07 15:43:14 -0700131 p.Expect(s0.Get());
132 p.Expect(s1.Get());
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700133 {
Ian Rogers1f539342012-10-03 21:09:42 -0700134 ReaderMutexLock mu(soa.Self(), *Locks::heap_bitmap_lock_);
Mathieu Chartier97509952015-07-13 14:35:43 -0700135 t.SweepInternTableWeaks(&p);
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700136 }
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700137
138 EXPECT_EQ(2U, t.Size());
139
Elliott Hughese5448b52012-01-18 16:44:06 -0800140 // Just check that we didn't corrupt the map.
Mathieu Chartiereb8167a2014-05-07 15:43:14 -0700141 Handle<mirror::String> still_here(
142 hs.NewHandle(mirror::String::AllocFromModifiedUtf8(soa.Self(), "still here")));
143 t.InternWeak(still_here.Get());
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700144 EXPECT_EQ(3U, t.Size());
145}
146
147TEST_F(InternTableTest, ContainsWeak) {
Ian Rogers00f7d0e2012-07-19 15:28:27 -0700148 ScopedObjectAccess soa(Thread::Current());
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700149 {
150 // Strongs are never weak.
151 InternTable t;
Mathieu Chartiereb8167a2014-05-07 15:43:14 -0700152 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 Hughescf4c6c42011-09-01 15:16:42 -0700158 }
159
160 {
161 // Weaks are always weak.
162 InternTable t;
Mathieu Chartiereb8167a2014-05-07 15:43:14 -0700163 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 Hughescf4c6c42011-09-01 15:16:42 -0700173 }
174
175 {
176 // A weak can be promoted to a strong.
177 InternTable t;
Mathieu Chartiereb8167a2014-05-07 15:43:14 -0700178 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 Hughescf4c6c42011-09-01 15:16:42 -0700186 }
187
188 {
189 // Interning a weak after a strong gets you the strong.
190 InternTable t;
Mathieu Chartiereb8167a2014-05-07 15:43:14 -0700191 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 Hughescf4c6c42011-09-01 15:16:42 -0700199 }
200}
201
Vladimir Markocac5a7e2016-02-22 10:39:50 +0000202TEST_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 Gampefa4333d2017-02-14 11:10:34 -0800209 ASSERT_TRUE(foo != nullptr);
210 ASSERT_TRUE(bar != nullptr);
211 ASSERT_TRUE(foobar != nullptr);
Vladimir Markocac5a7e2016-02-22 10:39:50 +0000212 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 Chartier9e868092016-10-31 14:58:04 -0700218 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 Markocac5a7e2016-02-22 10:39:50 +0000225 EXPECT_TRUE(lookup_foox == nullptr);
Mathieu Chartier9e868092016-10-31 14:58:04 -0700226 ObjPtr<mirror::String> lookup_fooba = intern_table.LookupStrong(soa.Self(), 5, "fooba");
Vladimir Markocac5a7e2016-02-22 10:39:50 +0000227 EXPECT_TRUE(lookup_fooba == nullptr);
Mathieu Chartier9e868092016-10-31 14:58:04 -0700228 ObjPtr<mirror::String> lookup_foobaR = intern_table.LookupStrong(soa.Self(), 6, "foobaR");
Vladimir Markocac5a7e2016-02-22 10:39:50 +0000229 EXPECT_TRUE(lookup_foobaR == nullptr);
230 // Try a hash conflict.
231 ASSERT_EQ(ComputeUtf16HashFromModifiedUtf8("foobar", 6),
232 ComputeUtf16HashFromModifiedUtf8("foobbS", 6));
Mathieu Chartier9e868092016-10-31 14:58:04 -0700233 ObjPtr<mirror::String> lookup_foobbS = intern_table.LookupStrong(soa.Self(), 6, "foobbS");
Vladimir Markocac5a7e2016-02-22 10:39:50 +0000234 EXPECT_TRUE(lookup_foobbS == nullptr);
235}
236
Brian Carlstrom7e93b502011-08-04 14:16:22 -0700237} // namespace art