blob: 14305006e4e52374703f241282421d2a6a231ce5 [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
Ian Rogers700a4022014-05-19 16:49:03 -070019#include <memory>
20
Ian Rogers7dfb28c2013-08-22 08:18:36 -070021#include "gc/space/image_space.h"
22#include "mirror/dex_cache.h"
23#include "mirror/object_array-inl.h"
24#include "mirror/object-inl.h"
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080025#include "mirror/string.h"
26#include "thread.h"
Elliott Hughes814e4032011-08-23 12:07:56 -070027#include "utf.h"
Brian Carlstrom7e93b502011-08-04 14:16:22 -070028
29namespace art {
30
Ian Rogers7dfb28c2013-08-22 08:18:36 -070031InternTable::InternTable()
Mathieu Chartier893263b2014-03-04 11:07:42 -080032 : log_new_roots_(false), allow_new_interns_(true),
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +010033 new_intern_condition_("New intern condition", *Locks::intern_table_lock_) {
Mathieu Chartierc11d9b82013-09-19 10:01:59 -070034}
Elliott Hughesde69d7f2011-08-18 16:49:37 -070035
Brian Carlstroma663ea52011-08-19 23:33:41 -070036size_t InternTable::Size() const {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +010037 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
Elliott Hughescf4c6c42011-09-01 15:16:42 -070038 return strong_interns_.size() + weak_interns_.size();
Brian Carlstroma663ea52011-08-19 23:33:41 -070039}
40
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -070041size_t InternTable::StrongSize() const {
42 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
43 return strong_interns_.size();
44}
45
46size_t InternTable::WeakSize() const {
47 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
48 return weak_interns_.size();
49}
50
Elliott Hughescac6cc72011-11-03 20:31:21 -070051void InternTable::DumpForSigQuit(std::ostream& os) const {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +010052 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
Elliott Hughescac6cc72011-11-03 20:31:21 -070053 os << "Intern table: " << strong_interns_.size() << " strong; "
Ian Rogers7dfb28c2013-08-22 08:18:36 -070054 << weak_interns_.size() << " weak\n";
Elliott Hughescac6cc72011-11-03 20:31:21 -070055}
56
Mathieu Chartier893263b2014-03-04 11:07:42 -080057void InternTable::VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +010058 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
Mathieu Chartier893263b2014-03-04 11:07:42 -080059 if ((flags & kVisitRootFlagAllRoots) != 0) {
Mathieu Chartierb3070522013-09-17 14:18:21 -070060 for (auto& strong_intern : strong_interns_) {
Mathieu Chartier815873e2014-02-13 18:02:13 -080061 callback(reinterpret_cast<mirror::Object**>(&strong_intern.second), arg, 0,
62 kRootInternedString);
Mathieu Chartierb3070522013-09-17 14:18:21 -070063 DCHECK(strong_intern.second != nullptr);
Mathieu Chartierc4621982013-09-16 19:43:47 -070064 }
Mathieu Chartier893263b2014-03-04 11:07:42 -080065 } else if ((flags & kVisitRootFlagNewRoots) != 0) {
66 for (auto& pair : new_strong_intern_roots_) {
67 mirror::String* old_ref = pair.second;
68 callback(reinterpret_cast<mirror::Object**>(&pair.second), arg, 0, kRootInternedString);
69 if (UNLIKELY(pair.second != old_ref)) {
70 // Uh ohes, GC moved a root in the log. Need to search the strong interns and update the
71 // corresponding object. This is slow, but luckily for us, this may only happen with a
72 // concurrent moving GC.
73 for (auto it = strong_interns_.lower_bound(pair.first), end = strong_interns_.end();
74 it != end && it->first == pair.first; ++it) {
75 // If the class stored matches the old class, update it to the new value.
76 if (old_ref == it->second) {
77 it->second = pair.second;
78 }
79 }
80 }
81 }
82 }
83
84 if ((flags & kVisitRootFlagClearRootLog) != 0) {
85 new_strong_intern_roots_.clear();
86 }
87 if ((flags & kVisitRootFlagStartLoggingNewRoots) != 0) {
88 log_new_roots_ = true;
89 } else if ((flags & kVisitRootFlagStopLoggingNewRoots) != 0) {
90 log_new_roots_ = false;
Ian Rogers1d54e732013-05-02 21:10:01 -070091 }
Mathieu Chartier423d2a32013-09-12 17:33:56 -070092 // Note: we deliberately don't visit the weak_interns_ table and the immutable image roots.
Brian Carlstrom7e93b502011-08-04 14:16:22 -070093}
94
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -070095mirror::String* InternTable::LookupStrong(mirror::String* s, int32_t hash_code) {
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -070096 return Lookup(&strong_interns_, s, hash_code);
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -070097}
98
99mirror::String* InternTable::LookupWeak(mirror::String* s, int32_t hash_code) {
100 // Weak interns need a read barrier because they are weak roots.
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -0700101 return Lookup(&weak_interns_, s, hash_code);
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700102}
103
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700104mirror::String* InternTable::Lookup(Table* table, mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100105 Locks::intern_table_lock_->AssertHeld(Thread::Current());
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700106 for (auto it = table->lower_bound(hash_code), end = table->end();
Vladimir Marko53dc70c2014-05-22 12:16:44 +0100107 it != end && it->first == hash_code; ++it) {
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -0700108 mirror::String* existing_string;
109 mirror::String** root = &it->second;
110 existing_string = ReadBarrier::BarrierForRoot<mirror::String, kWithReadBarrier>(root);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700111 if (existing_string->Equals(s)) {
112 return existing_string;
Brian Carlstrom7e93b502011-08-04 14:16:22 -0700113 }
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700114 }
115 return NULL;
116}
117
Mathieu Chartier893263b2014-03-04 11:07:42 -0800118mirror::String* InternTable::InsertStrong(mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100119 Runtime* runtime = Runtime::Current();
120 if (runtime->IsActiveTransaction()) {
121 runtime->RecordStrongStringInsertion(s, hash_code);
122 }
Mathieu Chartier893263b2014-03-04 11:07:42 -0800123 if (log_new_roots_) {
124 new_strong_intern_roots_.push_back(std::make_pair(hash_code, s));
125 }
126 strong_interns_.insert(std::make_pair(hash_code, s));
127 return s;
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100128}
129
Mathieu Chartier893263b2014-03-04 11:07:42 -0800130mirror::String* InternTable::InsertWeak(mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100131 Runtime* runtime = Runtime::Current();
132 if (runtime->IsActiveTransaction()) {
133 runtime->RecordWeakStringInsertion(s, hash_code);
134 }
Mathieu Chartier893263b2014-03-04 11:07:42 -0800135 weak_interns_.insert(std::make_pair(hash_code, s));
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700136 return s;
137}
138
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700139void InternTable::RemoveStrong(mirror::String* s, int32_t hash_code) {
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -0700140 Remove(&strong_interns_, s, hash_code);
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700141}
142
Mathieu Chartier893263b2014-03-04 11:07:42 -0800143void InternTable::RemoveWeak(mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100144 Runtime* runtime = Runtime::Current();
145 if (runtime->IsActiveTransaction()) {
146 runtime->RecordWeakStringRemoval(s, hash_code);
147 }
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -0700148 Remove(&weak_interns_, s, hash_code);
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100149}
150
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700151void InternTable::Remove(Table* table, mirror::String* s, int32_t hash_code) {
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700152 for (auto it = table->lower_bound(hash_code), end = table->end();
Vladimir Marko53dc70c2014-05-22 12:16:44 +0100153 it != end && it->first == hash_code; ++it) {
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -0700154 mirror::String* existing_string;
155 mirror::String** root = &it->second;
156 existing_string = ReadBarrier::BarrierForRoot<mirror::String, kWithReadBarrier>(root);
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700157 if (existing_string == s) {
158 table->erase(it);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700159 return;
160 }
Brian Carlstrom7e93b502011-08-04 14:16:22 -0700161 }
162}
163
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100164// Insert/remove methods used to undo changes made during an aborted transaction.
Mathieu Chartier893263b2014-03-04 11:07:42 -0800165mirror::String* InternTable::InsertStrongFromTransaction(mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100166 DCHECK(!Runtime::Current()->IsActiveTransaction());
167 return InsertStrong(s, hash_code);
168}
Mathieu Chartier893263b2014-03-04 11:07:42 -0800169mirror::String* InternTable::InsertWeakFromTransaction(mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100170 DCHECK(!Runtime::Current()->IsActiveTransaction());
171 return InsertWeak(s, hash_code);
172}
Mathieu Chartier893263b2014-03-04 11:07:42 -0800173void InternTable::RemoveStrongFromTransaction(mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100174 DCHECK(!Runtime::Current()->IsActiveTransaction());
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700175 RemoveStrong(s, hash_code);
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100176}
Mathieu Chartier893263b2014-03-04 11:07:42 -0800177void InternTable::RemoveWeakFromTransaction(mirror::String* s, int32_t hash_code) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100178 DCHECK(!Runtime::Current()->IsActiveTransaction());
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700179 RemoveWeak(s, hash_code);
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100180}
181
Ian Rogers7dfb28c2013-08-22 08:18:36 -0700182static mirror::String* LookupStringFromImage(mirror::String* s)
183 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
184 gc::space::ImageSpace* image = Runtime::Current()->GetHeap()->GetImageSpace();
185 if (image == NULL) {
186 return NULL; // No image present.
187 }
188 mirror::Object* root = image->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches);
189 mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>();
190 const std::string utf8 = s->ToModifiedUtf8();
191 for (int32_t i = 0; i < dex_caches->GetLength(); ++i) {
192 mirror::DexCache* dex_cache = dex_caches->Get(i);
193 const DexFile* dex_file = dex_cache->GetDexFile();
194 // Binary search the dex file for the string index.
195 const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str());
196 if (string_id != NULL) {
197 uint32_t string_idx = dex_file->GetIndexForStringId(*string_id);
198 mirror::String* image = dex_cache->GetResolvedString(string_idx);
199 if (image != NULL) {
200 return image;
201 }
202 }
203 }
204 return NULL;
205}
206
Mathieu Chartierc11d9b82013-09-19 10:01:59 -0700207void InternTable::AllowNewInterns() {
208 Thread* self = Thread::Current();
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100209 MutexLock mu(self, *Locks::intern_table_lock_);
Mathieu Chartierc11d9b82013-09-19 10:01:59 -0700210 allow_new_interns_ = true;
211 new_intern_condition_.Broadcast(self);
212}
213
214void InternTable::DisallowNewInterns() {
215 Thread* self = Thread::Current();
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100216 MutexLock mu(self, *Locks::intern_table_lock_);
Mathieu Chartierc11d9b82013-09-19 10:01:59 -0700217 allow_new_interns_ = false;
218}
219
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800220mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) {
Mathieu Chartierc11d9b82013-09-19 10:01:59 -0700221 Thread* self = Thread::Current();
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100222 MutexLock mu(self, *Locks::intern_table_lock_);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700223
224 DCHECK(s != NULL);
225 uint32_t hash_code = s->GetHashCode();
226
Mathieu Chartierc11d9b82013-09-19 10:01:59 -0700227 while (UNLIKELY(!allow_new_interns_)) {
228 new_intern_condition_.WaitHoldingLocks(self);
229 }
230
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700231 if (is_strong) {
jeffhaob1c6f342012-03-20 17:57:26 -0700232 // Check the strong table for a match.
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700233 mirror::String* strong = LookupStrong(s, hash_code);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700234 if (strong != NULL) {
235 return strong;
236 }
237
Ian Rogers7dfb28c2013-08-22 08:18:36 -0700238 // Check the image for a match.
239 mirror::String* image = LookupStringFromImage(s);
240 if (image != NULL) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100241 return InsertStrong(image, hash_code);
Ian Rogers7dfb28c2013-08-22 08:18:36 -0700242 }
243
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700244 // There is no match in the strong table, check the weak table.
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700245 mirror::String* weak = LookupWeak(s, hash_code);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700246 if (weak != NULL) {
247 // A match was found in the weak table. Promote to the strong table.
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100248 RemoveWeak(weak, hash_code);
249 return InsertStrong(weak, hash_code);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700250 }
251
Ian Rogers7dfb28c2013-08-22 08:18:36 -0700252 // No match in the strong table or the weak table. Insert into the strong
253 // table.
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100254 return InsertStrong(s, hash_code);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700255 }
256
257 // Check the strong table for a match.
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700258 mirror::String* strong = LookupStrong(s, hash_code);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700259 if (strong != NULL) {
260 return strong;
261 }
Ian Rogers7dfb28c2013-08-22 08:18:36 -0700262 // Check the image for a match.
263 mirror::String* image = LookupStringFromImage(s);
jeffhaob1c6f342012-03-20 17:57:26 -0700264 if (image != NULL) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100265 return InsertWeak(image, hash_code);
jeffhaob1c6f342012-03-20 17:57:26 -0700266 }
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700267 // Check the weak table for a match.
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700268 mirror::String* weak = LookupWeak(s, hash_code);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700269 if (weak != NULL) {
270 return weak;
271 }
272 // Insert into the weak table.
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100273 return InsertWeak(s, hash_code);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700274}
275
Mathieu Chartiered0fc1d2014-03-21 14:09:35 -0700276mirror::String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) {
277 DCHECK(utf8_data != nullptr);
Ian Rogers7dfb28c2013-08-22 08:18:36 -0700278 return InternStrong(mirror::String::AllocFromModifiedUtf8(
279 Thread::Current(), utf16_length, utf8_data));
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700280}
281
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800282mirror::String* InternTable::InternStrong(const char* utf8_data) {
Mathieu Chartiered0fc1d2014-03-21 14:09:35 -0700283 DCHECK(utf8_data != nullptr);
284 return InternStrong(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
Brian Carlstromc74255f2011-09-11 22:47:39 -0700285}
286
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800287mirror::String* InternTable::InternStrong(mirror::String* s) {
Mathieu Chartier83c8ee02014-01-28 14:50:23 -0800288 if (s == nullptr) {
289 return nullptr;
Elliott Hughes37d4e6b2011-10-13 12:05:20 -0700290 }
Brian Carlstromc74255f2011-09-11 22:47:39 -0700291 return Insert(s, true);
292}
293
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800294mirror::String* InternTable::InternWeak(mirror::String* s) {
Mathieu Chartier83c8ee02014-01-28 14:50:23 -0800295 if (s == nullptr) {
296 return nullptr;
Elliott Hughes37d4e6b2011-10-13 12:05:20 -0700297 }
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700298 return Insert(s, false);
299}
300
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800301bool InternTable::ContainsWeak(mirror::String* s) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100302 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700303 const mirror::String* found = LookupWeak(s, s->GetHashCode());
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700304 return found == s;
305}
306
Mathieu Chartier83c8ee02014-01-28 14:50:23 -0800307void InternTable::SweepInternTableWeaks(IsMarkedCallback* callback, void* arg) {
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100308 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
Mathieu Chartier02e25112013-08-14 16:14:24 -0700309 for (auto it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) {
Hiroshi Yamauchi1bd48722014-05-23 19:58:15 -0700310 // This does not need a read barrier because this is called by GC.
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800311 mirror::Object* object = it->second;
Mathieu Chartier83c8ee02014-01-28 14:50:23 -0800312 mirror::Object* new_object = callback(object, arg);
Mathieu Chartier6aa3df92013-09-17 15:17:28 -0700313 if (new_object == nullptr) {
314 // TODO: use it = weak_interns_.erase(it) when we get a c++11 stl.
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700315 weak_interns_.erase(it++);
316 } else {
Mathieu Chartier6aa3df92013-09-17 15:17:28 -0700317 it->second = down_cast<mirror::String*>(new_object);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700318 ++it;
319 }
320 }
Brian Carlstroma663ea52011-08-19 23:33:41 -0700321}
322
Brian Carlstrom7e93b502011-08-04 14:16:22 -0700323} // namespace art