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 "gc/space/image_space.h"
20 #include "mirror/dex_cache.h"
21 #include "mirror/object_array-inl.h"
22 #include "mirror/object-inl.h"
23 #include "mirror/string.h"
24 #include "thread.h"
25 #include "UniquePtr.h"
26 #include "utf.h"
27
28 namespace art {
29
InternTable()30 InternTable::InternTable()
31 : intern_table_lock_("InternTable lock"), is_dirty_(false), allow_new_interns_(true),
32 new_intern_condition_("New intern condition", intern_table_lock_) {
33 }
34
Size() const35 size_t InternTable::Size() const {
36 MutexLock mu(Thread::Current(), intern_table_lock_);
37 return strong_interns_.size() + weak_interns_.size();
38 }
39
DumpForSigQuit(std::ostream & os) const40 void InternTable::DumpForSigQuit(std::ostream& os) const {
41 MutexLock mu(Thread::Current(), intern_table_lock_);
42 os << "Intern table: " << strong_interns_.size() << " strong; "
43 << weak_interns_.size() << " weak\n";
44 }
45
VisitRoots(RootVisitor * visitor,void * arg,bool only_dirty,bool clean_dirty)46 void InternTable::VisitRoots(RootVisitor* visitor, void* arg,
47 bool only_dirty, bool clean_dirty) {
48 MutexLock mu(Thread::Current(), intern_table_lock_);
49 if (!only_dirty || is_dirty_) {
50 for (const auto& strong_intern : strong_interns_) {
51 visitor(strong_intern.second, arg);
52 }
53 if (clean_dirty) {
54 is_dirty_ = false;
55 }
56 }
57 // Note: we deliberately don't visit the weak_interns_ table and the immutable
58 // image roots.
59 }
60
Lookup(Table & table,mirror::String * s,uint32_t hash_code)61 mirror::String* InternTable::Lookup(Table& table, mirror::String* s,
62 uint32_t hash_code) {
63 intern_table_lock_.AssertHeld(Thread::Current());
64 for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) {
65 mirror::String* existing_string = it->second;
66 if (existing_string->Equals(s)) {
67 return existing_string;
68 }
69 }
70 return NULL;
71 }
72
Insert(Table & table,mirror::String * s,uint32_t hash_code)73 mirror::String* InternTable::Insert(Table& table, mirror::String* s,
74 uint32_t hash_code) {
75 intern_table_lock_.AssertHeld(Thread::Current());
76 table.insert(std::make_pair(hash_code, s));
77 return s;
78 }
79
Remove(Table & table,const mirror::String * s,uint32_t hash_code)80 void InternTable::Remove(Table& table, const mirror::String* s,
81 uint32_t hash_code) {
82 intern_table_lock_.AssertHeld(Thread::Current());
83 for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) {
84 if (it->second == s) {
85 table.erase(it);
86 return;
87 }
88 }
89 }
90
LookupStringFromImage(mirror::String * s)91 static mirror::String* LookupStringFromImage(mirror::String* s)
92 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
93 gc::space::ImageSpace* image = Runtime::Current()->GetHeap()->GetImageSpace();
94 if (image == NULL) {
95 return NULL; // No image present.
96 }
97 mirror::Object* root = image->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches);
98 mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>();
99 const std::string utf8 = s->ToModifiedUtf8();
100 for (int32_t i = 0; i < dex_caches->GetLength(); ++i) {
101 mirror::DexCache* dex_cache = dex_caches->Get(i);
102 const DexFile* dex_file = dex_cache->GetDexFile();
103 // Binary search the dex file for the string index.
104 const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str());
105 if (string_id != NULL) {
106 uint32_t string_idx = dex_file->GetIndexForStringId(*string_id);
107 mirror::String* image = dex_cache->GetResolvedString(string_idx);
108 if (image != NULL) {
109 return image;
110 }
111 }
112 }
113 return NULL;
114 }
115
AllowNewInterns()116 void InternTable::AllowNewInterns() {
117 Thread* self = Thread::Current();
118 MutexLock mu(self, intern_table_lock_);
119 allow_new_interns_ = true;
120 new_intern_condition_.Broadcast(self);
121 }
122
DisallowNewInterns()123 void InternTable::DisallowNewInterns() {
124 Thread* self = Thread::Current();
125 MutexLock mu(self, intern_table_lock_);
126 allow_new_interns_ = false;
127 }
128
Insert(mirror::String * s,bool is_strong)129 mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) {
130 Thread* self = Thread::Current();
131 MutexLock mu(self, intern_table_lock_);
132
133 DCHECK(s != NULL);
134 uint32_t hash_code = s->GetHashCode();
135
136 while (UNLIKELY(!allow_new_interns_)) {
137 new_intern_condition_.WaitHoldingLocks(self);
138 }
139
140 if (is_strong) {
141 // Check the strong table for a match.
142 mirror::String* strong = Lookup(strong_interns_, s, hash_code);
143 if (strong != NULL) {
144 return strong;
145 }
146
147 // Mark as dirty so that we rescan the roots.
148 is_dirty_ = true;
149
150 // Check the image for a match.
151 mirror::String* image = LookupStringFromImage(s);
152 if (image != NULL) {
153 return Insert(strong_interns_, image, hash_code);
154 }
155
156 // There is no match in the strong table, check the weak table.
157 mirror::String* weak = Lookup(weak_interns_, s, hash_code);
158 if (weak != NULL) {
159 // A match was found in the weak table. Promote to the strong table.
160 Remove(weak_interns_, weak, hash_code);
161 return Insert(strong_interns_, weak, hash_code);
162 }
163
164 // No match in the strong table or the weak table. Insert into the strong
165 // table.
166 return Insert(strong_interns_, s, hash_code);
167 }
168
169 // Check the strong table for a match.
170 mirror::String* strong = Lookup(strong_interns_, s, hash_code);
171 if (strong != NULL) {
172 return strong;
173 }
174 // Check the image for a match.
175 mirror::String* image = LookupStringFromImage(s);
176 if (image != NULL) {
177 return Insert(weak_interns_, image, hash_code);
178 }
179 // Check the weak table for a match.
180 mirror::String* weak = Lookup(weak_interns_, s, hash_code);
181 if (weak != NULL) {
182 return weak;
183 }
184 // Insert into the weak table.
185 return Insert(weak_interns_, s, hash_code);
186 }
187
InternStrong(int32_t utf16_length,const char * utf8_data)188 mirror::String* InternTable::InternStrong(int32_t utf16_length,
189 const char* utf8_data) {
190 return InternStrong(mirror::String::AllocFromModifiedUtf8(
191 Thread::Current(), utf16_length, utf8_data));
192 }
193
InternStrong(const char * utf8_data)194 mirror::String* InternTable::InternStrong(const char* utf8_data) {
195 return InternStrong(
196 mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
197 }
198
InternStrong(mirror::String * s)199 mirror::String* InternTable::InternStrong(mirror::String* s) {
200 if (s == NULL) {
201 return NULL;
202 }
203 return Insert(s, true);
204 }
205
InternWeak(mirror::String * s)206 mirror::String* InternTable::InternWeak(mirror::String* s) {
207 if (s == NULL) {
208 return NULL;
209 }
210 return Insert(s, false);
211 }
212
ContainsWeak(mirror::String * s)213 bool InternTable::ContainsWeak(mirror::String* s) {
214 MutexLock mu(Thread::Current(), intern_table_lock_);
215 const mirror::String* found = Lookup(weak_interns_, s, s->GetHashCode());
216 return found == s;
217 }
218
SweepInternTableWeaks(IsMarkedTester is_marked,void * arg)219 void InternTable::SweepInternTableWeaks(IsMarkedTester is_marked, void* arg) {
220 MutexLock mu(Thread::Current(), intern_table_lock_);
221 // TODO: std::remove_if + lambda.
222 for (auto it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) {
223 mirror::Object* object = it->second;
224 if (!is_marked(object, arg)) {
225 weak_interns_.erase(it++);
226 } else {
227 ++it;
228 }
229 }
230 }
231
232 } // namespace art
233