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 <memory>
20
21 #include "dex/utf.h"
22 #include "gc/collector/garbage_collector.h"
23 #include "gc/space/image_space.h"
24 #include "gc/weak_root_state.h"
25 #include "gc_root-inl.h"
26 #include "handle_scope-inl.h"
27 #include "image-inl.h"
28 #include "mirror/dex_cache-inl.h"
29 #include "mirror/object-inl.h"
30 #include "mirror/object_array-inl.h"
31 #include "mirror/string-inl.h"
32 #include "object_callbacks.h"
33 #include "scoped_thread_state_change-inl.h"
34 #include "thread.h"
35
36 namespace art {
37
InternTable()38 InternTable::InternTable()
39 : log_new_roots_(false),
40 weak_intern_condition_("New intern condition", *Locks::intern_table_lock_),
41 weak_root_state_(gc::kWeakRootStateNormal) {
42 }
43
Size() const44 size_t InternTable::Size() const {
45 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
46 return strong_interns_.Size() + weak_interns_.Size();
47 }
48
StrongSize() const49 size_t InternTable::StrongSize() const {
50 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
51 return strong_interns_.Size();
52 }
53
WeakSize() const54 size_t InternTable::WeakSize() const {
55 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
56 return weak_interns_.Size();
57 }
58
DumpForSigQuit(std::ostream & os) const59 void InternTable::DumpForSigQuit(std::ostream& os) const {
60 os << "Intern table: " << StrongSize() << " strong; " << WeakSize() << " weak\n";
61 }
62
VisitRoots(RootVisitor * visitor,VisitRootFlags flags)63 void InternTable::VisitRoots(RootVisitor* visitor, VisitRootFlags flags) {
64 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
65 if ((flags & kVisitRootFlagAllRoots) != 0) {
66 strong_interns_.VisitRoots(visitor);
67 } else if ((flags & kVisitRootFlagNewRoots) != 0) {
68 for (auto& root : new_strong_intern_roots_) {
69 ObjPtr<mirror::String> old_ref = root.Read<kWithoutReadBarrier>();
70 root.VisitRoot(visitor, RootInfo(kRootInternedString));
71 ObjPtr<mirror::String> new_ref = root.Read<kWithoutReadBarrier>();
72 if (new_ref != old_ref) {
73 // The GC moved a root in the log. Need to search the strong interns and update the
74 // corresponding object. This is slow, but luckily for us, this may only happen with a
75 // concurrent moving GC.
76 strong_interns_.Remove(old_ref);
77 strong_interns_.Insert(new_ref);
78 }
79 }
80 }
81 if ((flags & kVisitRootFlagClearRootLog) != 0) {
82 new_strong_intern_roots_.clear();
83 }
84 if ((flags & kVisitRootFlagStartLoggingNewRoots) != 0) {
85 log_new_roots_ = true;
86 } else if ((flags & kVisitRootFlagStopLoggingNewRoots) != 0) {
87 log_new_roots_ = false;
88 }
89 // Note: we deliberately don't visit the weak_interns_ table and the immutable image roots.
90 }
91
LookupWeak(Thread * self,ObjPtr<mirror::String> s)92 ObjPtr<mirror::String> InternTable::LookupWeak(Thread* self, ObjPtr<mirror::String> s) {
93 MutexLock mu(self, *Locks::intern_table_lock_);
94 return LookupWeakLocked(s);
95 }
96
LookupStrong(Thread * self,ObjPtr<mirror::String> s)97 ObjPtr<mirror::String> InternTable::LookupStrong(Thread* self, ObjPtr<mirror::String> s) {
98 MutexLock mu(self, *Locks::intern_table_lock_);
99 return LookupStrongLocked(s);
100 }
101
LookupStrong(Thread * self,uint32_t utf16_length,const char * utf8_data)102 ObjPtr<mirror::String> InternTable::LookupStrong(Thread* self,
103 uint32_t utf16_length,
104 const char* utf8_data) {
105 DCHECK_EQ(utf16_length, CountModifiedUtf8Chars(utf8_data));
106 Utf8String string(utf16_length,
107 utf8_data,
108 ComputeUtf16HashFromModifiedUtf8(utf8_data, utf16_length));
109 MutexLock mu(self, *Locks::intern_table_lock_);
110 return strong_interns_.Find(string);
111 }
112
LookupWeakLocked(ObjPtr<mirror::String> s)113 ObjPtr<mirror::String> InternTable::LookupWeakLocked(ObjPtr<mirror::String> s) {
114 return weak_interns_.Find(s);
115 }
116
LookupStrongLocked(ObjPtr<mirror::String> s)117 ObjPtr<mirror::String> InternTable::LookupStrongLocked(ObjPtr<mirror::String> s) {
118 return strong_interns_.Find(s);
119 }
120
AddNewTable()121 void InternTable::AddNewTable() {
122 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
123 weak_interns_.AddNewTable();
124 strong_interns_.AddNewTable();
125 }
126
InsertStrong(ObjPtr<mirror::String> s)127 ObjPtr<mirror::String> InternTable::InsertStrong(ObjPtr<mirror::String> s) {
128 Runtime* runtime = Runtime::Current();
129 if (runtime->IsActiveTransaction()) {
130 runtime->RecordStrongStringInsertion(s);
131 }
132 if (log_new_roots_) {
133 new_strong_intern_roots_.push_back(GcRoot<mirror::String>(s));
134 }
135 strong_interns_.Insert(s);
136 return s;
137 }
138
InsertWeak(ObjPtr<mirror::String> s)139 ObjPtr<mirror::String> InternTable::InsertWeak(ObjPtr<mirror::String> s) {
140 Runtime* runtime = Runtime::Current();
141 if (runtime->IsActiveTransaction()) {
142 runtime->RecordWeakStringInsertion(s);
143 }
144 weak_interns_.Insert(s);
145 return s;
146 }
147
RemoveStrong(ObjPtr<mirror::String> s)148 void InternTable::RemoveStrong(ObjPtr<mirror::String> s) {
149 strong_interns_.Remove(s);
150 }
151
RemoveWeak(ObjPtr<mirror::String> s)152 void InternTable::RemoveWeak(ObjPtr<mirror::String> s) {
153 Runtime* runtime = Runtime::Current();
154 if (runtime->IsActiveTransaction()) {
155 runtime->RecordWeakStringRemoval(s);
156 }
157 weak_interns_.Remove(s);
158 }
159
160 // Insert/remove methods used to undo changes made during an aborted transaction.
InsertStrongFromTransaction(ObjPtr<mirror::String> s)161 ObjPtr<mirror::String> InternTable::InsertStrongFromTransaction(ObjPtr<mirror::String> s) {
162 DCHECK(!Runtime::Current()->IsActiveTransaction());
163 return InsertStrong(s);
164 }
165
InsertWeakFromTransaction(ObjPtr<mirror::String> s)166 ObjPtr<mirror::String> InternTable::InsertWeakFromTransaction(ObjPtr<mirror::String> s) {
167 DCHECK(!Runtime::Current()->IsActiveTransaction());
168 return InsertWeak(s);
169 }
170
RemoveStrongFromTransaction(ObjPtr<mirror::String> s)171 void InternTable::RemoveStrongFromTransaction(ObjPtr<mirror::String> s) {
172 DCHECK(!Runtime::Current()->IsActiveTransaction());
173 RemoveStrong(s);
174 }
175
RemoveWeakFromTransaction(ObjPtr<mirror::String> s)176 void InternTable::RemoveWeakFromTransaction(ObjPtr<mirror::String> s) {
177 DCHECK(!Runtime::Current()->IsActiveTransaction());
178 RemoveWeak(s);
179 }
180
BroadcastForNewInterns()181 void InternTable::BroadcastForNewInterns() {
182 Thread* self = Thread::Current();
183 MutexLock mu(self, *Locks::intern_table_lock_);
184 weak_intern_condition_.Broadcast(self);
185 }
186
WaitUntilAccessible(Thread * self)187 void InternTable::WaitUntilAccessible(Thread* self) {
188 Locks::intern_table_lock_->ExclusiveUnlock(self);
189 {
190 ScopedThreadSuspension sts(self, kWaitingWeakGcRootRead);
191 MutexLock mu(self, *Locks::intern_table_lock_);
192 while ((!kUseReadBarrier && weak_root_state_ == gc::kWeakRootStateNoReadsOrWrites) ||
193 (kUseReadBarrier && !self->GetWeakRefAccessEnabled())) {
194 weak_intern_condition_.Wait(self);
195 }
196 }
197 Locks::intern_table_lock_->ExclusiveLock(self);
198 }
199
Insert(ObjPtr<mirror::String> s,bool is_strong,bool holding_locks)200 ObjPtr<mirror::String> InternTable::Insert(ObjPtr<mirror::String> s,
201 bool is_strong,
202 bool holding_locks) {
203 if (s == nullptr) {
204 return nullptr;
205 }
206 Thread* const self = Thread::Current();
207 MutexLock mu(self, *Locks::intern_table_lock_);
208 if (kDebugLocking && !holding_locks) {
209 Locks::mutator_lock_->AssertSharedHeld(self);
210 CHECK_EQ(2u, self->NumberOfHeldMutexes()) << "may only safely hold the mutator lock";
211 }
212 while (true) {
213 if (holding_locks) {
214 if (!kUseReadBarrier) {
215 CHECK_EQ(weak_root_state_, gc::kWeakRootStateNormal);
216 } else {
217 CHECK(self->GetWeakRefAccessEnabled());
218 }
219 }
220 // Check the strong table for a match.
221 ObjPtr<mirror::String> strong = LookupStrongLocked(s);
222 if (strong != nullptr) {
223 return strong;
224 }
225 if ((!kUseReadBarrier && weak_root_state_ != gc::kWeakRootStateNoReadsOrWrites) ||
226 (kUseReadBarrier && self->GetWeakRefAccessEnabled())) {
227 break;
228 }
229 // weak_root_state_ is set to gc::kWeakRootStateNoReadsOrWrites in the GC pause but is only
230 // cleared after SweepSystemWeaks has completed. This is why we need to wait until it is
231 // cleared.
232 CHECK(!holding_locks);
233 StackHandleScope<1> hs(self);
234 auto h = hs.NewHandleWrapper(&s);
235 WaitUntilAccessible(self);
236 }
237 if (!kUseReadBarrier) {
238 CHECK_EQ(weak_root_state_, gc::kWeakRootStateNormal);
239 } else {
240 CHECK(self->GetWeakRefAccessEnabled());
241 }
242 // There is no match in the strong table, check the weak table.
243 ObjPtr<mirror::String> weak = LookupWeakLocked(s);
244 if (weak != nullptr) {
245 if (is_strong) {
246 // A match was found in the weak table. Promote to the strong table.
247 RemoveWeak(weak);
248 return InsertStrong(weak);
249 }
250 return weak;
251 }
252 // No match in the strong table or the weak table. Insert into the strong / weak table.
253 return is_strong ? InsertStrong(s) : InsertWeak(s);
254 }
255
InternStrong(int32_t utf16_length,const char * utf8_data)256 ObjPtr<mirror::String> InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) {
257 DCHECK(utf8_data != nullptr);
258 Thread* self = Thread::Current();
259 // Try to avoid allocation.
260 ObjPtr<mirror::String> s = LookupStrong(self, utf16_length, utf8_data);
261 if (s != nullptr) {
262 return s;
263 }
264 return InternStrong(mirror::String::AllocFromModifiedUtf8(
265 self, utf16_length, utf8_data));
266 }
267
InternStrong(const char * utf8_data)268 ObjPtr<mirror::String> InternTable::InternStrong(const char* utf8_data) {
269 DCHECK(utf8_data != nullptr);
270 return InternStrong(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
271 }
272
InternStrongImageString(ObjPtr<mirror::String> s)273 ObjPtr<mirror::String> InternTable::InternStrongImageString(ObjPtr<mirror::String> s) {
274 // May be holding the heap bitmap lock.
275 return Insert(s, true, true);
276 }
277
PromoteWeakToStrong()278 void InternTable::PromoteWeakToStrong() {
279 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
280 DCHECK_EQ(weak_interns_.tables_.size(), 1u);
281 for (GcRoot<mirror::String>& entry : weak_interns_.tables_.front().set_) {
282 DCHECK(LookupStrongLocked(entry.Read()) == nullptr);
283 InsertStrong(entry.Read());
284 }
285 weak_interns_.tables_.front().set_.clear();
286 }
287
InternStrong(ObjPtr<mirror::String> s)288 ObjPtr<mirror::String> InternTable::InternStrong(ObjPtr<mirror::String> s) {
289 return Insert(s, true, false);
290 }
291
InternWeak(const char * utf8_data)292 ObjPtr<mirror::String> InternTable::InternWeak(const char* utf8_data) {
293 DCHECK(utf8_data != nullptr);
294 return InternWeak(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
295 }
296
InternWeak(ObjPtr<mirror::String> s)297 ObjPtr<mirror::String> InternTable::InternWeak(ObjPtr<mirror::String> s) {
298 return Insert(s, false, false);
299 }
300
ContainsWeak(ObjPtr<mirror::String> s)301 bool InternTable::ContainsWeak(ObjPtr<mirror::String> s) {
302 return LookupWeak(Thread::Current(), s) == s;
303 }
304
SweepInternTableWeaks(IsMarkedVisitor * visitor)305 void InternTable::SweepInternTableWeaks(IsMarkedVisitor* visitor) {
306 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
307 weak_interns_.SweepWeaks(visitor);
308 }
309
WriteToMemory(uint8_t * ptr)310 size_t InternTable::WriteToMemory(uint8_t* ptr) {
311 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
312 return strong_interns_.WriteToMemory(ptr);
313 }
314
operator ()(const GcRoot<mirror::String> & root) const315 std::size_t InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& root) const {
316 if (kIsDebugBuild) {
317 Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
318 }
319 // An additional cast to prevent undesired sign extension.
320 return static_cast<size_t>(
321 static_cast<uint32_t>(root.Read<kWithoutReadBarrier>()->GetHashCode()));
322 }
323
operator ()(const GcRoot<mirror::String> & a,const GcRoot<mirror::String> & b) const324 bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
325 const GcRoot<mirror::String>& b) const {
326 if (kIsDebugBuild) {
327 Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
328 }
329 return a.Read<kWithoutReadBarrier>()->Equals(b.Read<kWithoutReadBarrier>());
330 }
331
operator ()(const GcRoot<mirror::String> & a,const Utf8String & b) const332 bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
333 const Utf8String& b) const {
334 if (kIsDebugBuild) {
335 Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
336 }
337 ObjPtr<mirror::String> a_string = a.Read<kWithoutReadBarrier>();
338 uint32_t a_length = static_cast<uint32_t>(a_string->GetLength());
339 if (a_length != b.GetUtf16Length()) {
340 return false;
341 }
342 if (a_string->IsCompressed()) {
343 size_t b_byte_count = strlen(b.GetUtf8Data());
344 size_t b_utf8_length = CountModifiedUtf8Chars(b.GetUtf8Data(), b_byte_count);
345 // Modified UTF-8 single byte character range is 0x01 .. 0x7f
346 // The string compression occurs on regular ASCII with same exact range,
347 // not on extended ASCII which up to 0xff
348 const bool is_b_regular_ascii = (b_byte_count == b_utf8_length);
349 if (is_b_regular_ascii) {
350 return memcmp(b.GetUtf8Data(),
351 a_string->GetValueCompressed(), a_length * sizeof(uint8_t)) == 0;
352 } else {
353 return false;
354 }
355 } else {
356 const uint16_t* a_value = a_string->GetValue();
357 return CompareModifiedUtf8ToUtf16AsCodePointValues(b.GetUtf8Data(), a_value, a_length) == 0;
358 }
359 }
360
WriteToMemory(uint8_t * ptr)361 size_t InternTable::Table::WriteToMemory(uint8_t* ptr) {
362 if (tables_.empty()) {
363 return 0;
364 }
365 UnorderedSet* table_to_write;
366 UnorderedSet combined;
367 if (tables_.size() > 1) {
368 table_to_write = &combined;
369 for (InternalTable& table : tables_) {
370 for (GcRoot<mirror::String>& string : table.set_) {
371 combined.insert(string);
372 }
373 }
374 } else {
375 table_to_write = &tables_.back().set_;
376 }
377 return table_to_write->WriteToMemory(ptr);
378 }
379
Remove(ObjPtr<mirror::String> s)380 void InternTable::Table::Remove(ObjPtr<mirror::String> s) {
381 for (InternalTable& table : tables_) {
382 auto it = table.set_.find(GcRoot<mirror::String>(s));
383 if (it != table.set_.end()) {
384 table.set_.erase(it);
385 return;
386 }
387 }
388 LOG(FATAL) << "Attempting to remove non-interned string " << s->ToModifiedUtf8();
389 }
390
Find(ObjPtr<mirror::String> s)391 ObjPtr<mirror::String> InternTable::Table::Find(ObjPtr<mirror::String> s) {
392 Locks::intern_table_lock_->AssertHeld(Thread::Current());
393 for (InternalTable& table : tables_) {
394 auto it = table.set_.find(GcRoot<mirror::String>(s));
395 if (it != table.set_.end()) {
396 return it->Read();
397 }
398 }
399 return nullptr;
400 }
401
Find(const Utf8String & string)402 ObjPtr<mirror::String> InternTable::Table::Find(const Utf8String& string) {
403 Locks::intern_table_lock_->AssertHeld(Thread::Current());
404 for (InternalTable& table : tables_) {
405 auto it = table.set_.find(string);
406 if (it != table.set_.end()) {
407 return it->Read();
408 }
409 }
410 return nullptr;
411 }
412
AddNewTable()413 void InternTable::Table::AddNewTable() {
414 tables_.push_back(InternalTable());
415 }
416
Insert(ObjPtr<mirror::String> s)417 void InternTable::Table::Insert(ObjPtr<mirror::String> s) {
418 // Always insert the last table, the image tables are before and we avoid inserting into these
419 // to prevent dirty pages.
420 DCHECK(!tables_.empty());
421 tables_.back().set_.insert(GcRoot<mirror::String>(s));
422 }
423
VisitRoots(RootVisitor * visitor)424 void InternTable::Table::VisitRoots(RootVisitor* visitor) {
425 BufferedRootVisitor<kDefaultBufferedRootCount> buffered_visitor(
426 visitor, RootInfo(kRootInternedString));
427 for (InternalTable& table : tables_) {
428 for (auto& intern : table.set_) {
429 buffered_visitor.VisitRoot(intern);
430 }
431 }
432 }
433
SweepWeaks(IsMarkedVisitor * visitor)434 void InternTable::Table::SweepWeaks(IsMarkedVisitor* visitor) {
435 for (InternalTable& table : tables_) {
436 SweepWeaks(&table.set_, visitor);
437 }
438 }
439
SweepWeaks(UnorderedSet * set,IsMarkedVisitor * visitor)440 void InternTable::Table::SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) {
441 for (auto it = set->begin(), end = set->end(); it != end;) {
442 // This does not need a read barrier because this is called by GC.
443 mirror::Object* object = it->Read<kWithoutReadBarrier>();
444 mirror::Object* new_object = visitor->IsMarked(object);
445 if (new_object == nullptr) {
446 it = set->erase(it);
447 } else {
448 *it = GcRoot<mirror::String>(new_object->AsString());
449 ++it;
450 }
451 }
452 }
453
Size() const454 size_t InternTable::Table::Size() const {
455 return std::accumulate(tables_.begin(),
456 tables_.end(),
457 0U,
458 [](size_t sum, const InternalTable& table) {
459 return sum + table.Size();
460 });
461 }
462
ChangeWeakRootState(gc::WeakRootState new_state)463 void InternTable::ChangeWeakRootState(gc::WeakRootState new_state) {
464 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
465 ChangeWeakRootStateLocked(new_state);
466 }
467
ChangeWeakRootStateLocked(gc::WeakRootState new_state)468 void InternTable::ChangeWeakRootStateLocked(gc::WeakRootState new_state) {
469 CHECK(!kUseReadBarrier);
470 weak_root_state_ = new_state;
471 if (new_state != gc::kWeakRootStateNoReadsOrWrites) {
472 weak_intern_condition_.Broadcast(Thread::Current());
473 }
474 }
475
Table()476 InternTable::Table::Table() {
477 Runtime* const runtime = Runtime::Current();
478 InternalTable initial_table;
479 initial_table.set_.SetLoadFactor(runtime->GetHashTableMinLoadFactor(),
480 runtime->GetHashTableMaxLoadFactor());
481 tables_.push_back(std::move(initial_table));
482 }
483
484 } // namespace art
485