• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "gc_root-inl.h"
22 #include "gc/collector/garbage_collector.h"
23 #include "gc/space/image_space.h"
24 #include "gc/weak_root_state.h"
25 #include "image-inl.h"
26 #include "mirror/dex_cache-inl.h"
27 #include "mirror/object_array-inl.h"
28 #include "mirror/object-inl.h"
29 #include "mirror/string-inl.h"
30 #include "thread.h"
31 #include "utf.h"
32 
33 namespace art {
34 
InternTable()35 InternTable::InternTable()
36     : images_added_to_intern_table_(false),
37       log_new_roots_(false),
38       weak_intern_condition_("New intern condition", *Locks::intern_table_lock_),
39       weak_root_state_(gc::kWeakRootStateNormal) {
40 }
41 
Size() const42 size_t InternTable::Size() const {
43   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
44   return strong_interns_.Size() + weak_interns_.Size();
45 }
46 
StrongSize() const47 size_t InternTable::StrongSize() const {
48   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
49   return strong_interns_.Size();
50 }
51 
WeakSize() const52 size_t InternTable::WeakSize() const {
53   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
54   return weak_interns_.Size();
55 }
56 
DumpForSigQuit(std::ostream & os) const57 void InternTable::DumpForSigQuit(std::ostream& os) const {
58   os << "Intern table: " << StrongSize() << " strong; " << WeakSize() << " weak\n";
59 }
60 
VisitRoots(RootVisitor * visitor,VisitRootFlags flags)61 void InternTable::VisitRoots(RootVisitor* visitor, VisitRootFlags flags) {
62   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
63   if ((flags & kVisitRootFlagAllRoots) != 0) {
64     strong_interns_.VisitRoots(visitor);
65   } else if ((flags & kVisitRootFlagNewRoots) != 0) {
66     for (auto& root : new_strong_intern_roots_) {
67       mirror::String* old_ref = root.Read<kWithoutReadBarrier>();
68       root.VisitRoot(visitor, RootInfo(kRootInternedString));
69       mirror::String* new_ref = root.Read<kWithoutReadBarrier>();
70       if (new_ref != old_ref) {
71         // The GC moved a root in the log. Need to search the strong interns and update the
72         // corresponding object. This is slow, but luckily for us, this may only happen with a
73         // concurrent moving GC.
74         strong_interns_.Remove(old_ref);
75         strong_interns_.Insert(new_ref);
76       }
77     }
78   }
79   if ((flags & kVisitRootFlagClearRootLog) != 0) {
80     new_strong_intern_roots_.clear();
81   }
82   if ((flags & kVisitRootFlagStartLoggingNewRoots) != 0) {
83     log_new_roots_ = true;
84   } else if ((flags & kVisitRootFlagStopLoggingNewRoots) != 0) {
85     log_new_roots_ = false;
86   }
87   // Note: we deliberately don't visit the weak_interns_ table and the immutable image roots.
88 }
89 
LookupWeak(Thread * self,mirror::String * s)90 mirror::String* InternTable::LookupWeak(Thread* self, mirror::String* s) {
91   MutexLock mu(self, *Locks::intern_table_lock_);
92   return LookupWeakLocked(s);
93 }
94 
LookupStrong(Thread * self,mirror::String * s)95 mirror::String* InternTable::LookupStrong(Thread* self, mirror::String* s) {
96   MutexLock mu(self, *Locks::intern_table_lock_);
97   return LookupStrongLocked(s);
98 }
99 
LookupStrong(Thread * self,uint32_t utf16_length,const char * utf8_data)100 mirror::String* InternTable::LookupStrong(Thread* self,
101                                           uint32_t utf16_length,
102                                           const char* utf8_data) {
103   DCHECK_EQ(utf16_length, CountModifiedUtf8Chars(utf8_data));
104   Utf8String string(utf16_length,
105                     utf8_data,
106                     ComputeUtf16HashFromModifiedUtf8(utf8_data, utf16_length));
107   MutexLock mu(self, *Locks::intern_table_lock_);
108   return strong_interns_.Find(string);
109 }
110 
LookupWeakLocked(mirror::String * s)111 mirror::String* InternTable::LookupWeakLocked(mirror::String* s) {
112   return weak_interns_.Find(s);
113 }
114 
LookupStrongLocked(mirror::String * s)115 mirror::String* InternTable::LookupStrongLocked(mirror::String* s) {
116   return strong_interns_.Find(s);
117 }
118 
AddNewTable()119 void InternTable::AddNewTable() {
120   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
121   weak_interns_.AddNewTable();
122   strong_interns_.AddNewTable();
123 }
124 
InsertStrong(mirror::String * s)125 mirror::String* InternTable::InsertStrong(mirror::String* s) {
126   Runtime* runtime = Runtime::Current();
127   if (runtime->IsActiveTransaction()) {
128     runtime->RecordStrongStringInsertion(s);
129   }
130   if (log_new_roots_) {
131     new_strong_intern_roots_.push_back(GcRoot<mirror::String>(s));
132   }
133   strong_interns_.Insert(s);
134   return s;
135 }
136 
InsertWeak(mirror::String * s)137 mirror::String* InternTable::InsertWeak(mirror::String* s) {
138   Runtime* runtime = Runtime::Current();
139   if (runtime->IsActiveTransaction()) {
140     runtime->RecordWeakStringInsertion(s);
141   }
142   weak_interns_.Insert(s);
143   return s;
144 }
145 
RemoveStrong(mirror::String * s)146 void InternTable::RemoveStrong(mirror::String* s) {
147   strong_interns_.Remove(s);
148 }
149 
RemoveWeak(mirror::String * s)150 void InternTable::RemoveWeak(mirror::String* s) {
151   Runtime* runtime = Runtime::Current();
152   if (runtime->IsActiveTransaction()) {
153     runtime->RecordWeakStringRemoval(s);
154   }
155   weak_interns_.Remove(s);
156 }
157 
158 // Insert/remove methods used to undo changes made during an aborted transaction.
InsertStrongFromTransaction(mirror::String * s)159 mirror::String* InternTable::InsertStrongFromTransaction(mirror::String* s) {
160   DCHECK(!Runtime::Current()->IsActiveTransaction());
161   return InsertStrong(s);
162 }
InsertWeakFromTransaction(mirror::String * s)163 mirror::String* InternTable::InsertWeakFromTransaction(mirror::String* s) {
164   DCHECK(!Runtime::Current()->IsActiveTransaction());
165   return InsertWeak(s);
166 }
RemoveStrongFromTransaction(mirror::String * s)167 void InternTable::RemoveStrongFromTransaction(mirror::String* s) {
168   DCHECK(!Runtime::Current()->IsActiveTransaction());
169   RemoveStrong(s);
170 }
RemoveWeakFromTransaction(mirror::String * s)171 void InternTable::RemoveWeakFromTransaction(mirror::String* s) {
172   DCHECK(!Runtime::Current()->IsActiveTransaction());
173   RemoveWeak(s);
174 }
175 
AddImagesStringsToTable(const std::vector<gc::space::ImageSpace * > & image_spaces)176 void InternTable::AddImagesStringsToTable(const std::vector<gc::space::ImageSpace*>& image_spaces) {
177   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
178   for (gc::space::ImageSpace* image_space : image_spaces) {
179     const ImageHeader* const header = &image_space->GetImageHeader();
180     // Check if we have the interned strings section.
181     const ImageSection& section = header->GetImageSection(ImageHeader::kSectionInternedStrings);
182     if (section.Size() > 0) {
183       AddTableFromMemoryLocked(image_space->Begin() + section.Offset());
184     } else {
185       // TODO: Delete this logic?
186       mirror::Object* root = header->GetImageRoot(ImageHeader::kDexCaches);
187       mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>();
188       for (int32_t i = 0; i < dex_caches->GetLength(); ++i) {
189         mirror::DexCache* dex_cache = dex_caches->Get(i);
190         const size_t num_strings = dex_cache->NumStrings();
191         for (size_t j = 0; j < num_strings; ++j) {
192           mirror::String* image_string = dex_cache->GetResolvedString(j);
193           if (image_string != nullptr) {
194             mirror::String* found = LookupStrongLocked(image_string);
195             if (found == nullptr) {
196               InsertStrong(image_string);
197             } else {
198               DCHECK_EQ(found, image_string);
199             }
200           }
201         }
202       }
203     }
204   }
205   images_added_to_intern_table_ = true;
206 }
207 
LookupStringFromImage(mirror::String * s)208 mirror::String* InternTable::LookupStringFromImage(mirror::String* s) {
209   DCHECK(!images_added_to_intern_table_);
210   const std::vector<gc::space::ImageSpace*>& image_spaces =
211       Runtime::Current()->GetHeap()->GetBootImageSpaces();
212   if (image_spaces.empty()) {
213     return nullptr;  // No image present.
214   }
215   const std::string utf8 = s->ToModifiedUtf8();
216   for (gc::space::ImageSpace* image_space : image_spaces) {
217     mirror::Object* root = image_space->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches);
218     mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>();
219     for (int32_t i = 0; i < dex_caches->GetLength(); ++i) {
220       mirror::DexCache* dex_cache = dex_caches->Get(i);
221       const DexFile* dex_file = dex_cache->GetDexFile();
222       // Binary search the dex file for the string index.
223       const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str());
224       if (string_id != nullptr) {
225         uint32_t string_idx = dex_file->GetIndexForStringId(*string_id);
226         // GetResolvedString() contains a RB.
227         mirror::String* image_string = dex_cache->GetResolvedString(string_idx);
228         if (image_string != nullptr) {
229           return image_string;
230         }
231       }
232     }
233   }
234   return nullptr;
235 }
236 
BroadcastForNewInterns()237 void InternTable::BroadcastForNewInterns() {
238   CHECK(kUseReadBarrier);
239   Thread* self = Thread::Current();
240   MutexLock mu(self, *Locks::intern_table_lock_);
241   weak_intern_condition_.Broadcast(self);
242 }
243 
WaitUntilAccessible(Thread * self)244 void InternTable::WaitUntilAccessible(Thread* self) {
245   Locks::intern_table_lock_->ExclusiveUnlock(self);
246   {
247     ScopedThreadSuspension sts(self, kWaitingWeakGcRootRead);
248     MutexLock mu(self, *Locks::intern_table_lock_);
249     while (weak_root_state_ == gc::kWeakRootStateNoReadsOrWrites) {
250       weak_intern_condition_.Wait(self);
251     }
252   }
253   Locks::intern_table_lock_->ExclusiveLock(self);
254 }
255 
Insert(mirror::String * s,bool is_strong,bool holding_locks)256 mirror::String* InternTable::Insert(mirror::String* s, bool is_strong, bool holding_locks) {
257   if (s == nullptr) {
258     return nullptr;
259   }
260   Thread* const self = Thread::Current();
261   MutexLock mu(self, *Locks::intern_table_lock_);
262   if (kDebugLocking && !holding_locks) {
263     Locks::mutator_lock_->AssertSharedHeld(self);
264     CHECK_EQ(2u, self->NumberOfHeldMutexes()) << "may only safely hold the mutator lock";
265   }
266   while (true) {
267     if (holding_locks) {
268       if (!kUseReadBarrier) {
269         CHECK_EQ(weak_root_state_, gc::kWeakRootStateNormal);
270       } else {
271         CHECK(self->GetWeakRefAccessEnabled());
272       }
273     }
274     // Check the strong table for a match.
275     mirror::String* strong = LookupStrongLocked(s);
276     if (strong != nullptr) {
277       return strong;
278     }
279     if ((!kUseReadBarrier && weak_root_state_ != gc::kWeakRootStateNoReadsOrWrites) ||
280         (kUseReadBarrier && self->GetWeakRefAccessEnabled())) {
281       break;
282     }
283     // weak_root_state_ is set to gc::kWeakRootStateNoReadsOrWrites in the GC pause but is only
284     // cleared after SweepSystemWeaks has completed. This is why we need to wait until it is
285     // cleared.
286     CHECK(!holding_locks);
287     StackHandleScope<1> hs(self);
288     auto h = hs.NewHandleWrapper(&s);
289     WaitUntilAccessible(self);
290   }
291   if (!kUseReadBarrier) {
292     CHECK_EQ(weak_root_state_, gc::kWeakRootStateNormal);
293   } else {
294     CHECK(self->GetWeakRefAccessEnabled());
295   }
296   // There is no match in the strong table, check the weak table.
297   mirror::String* weak = LookupWeakLocked(s);
298   if (weak != nullptr) {
299     if (is_strong) {
300       // A match was found in the weak table. Promote to the strong table.
301       RemoveWeak(weak);
302       return InsertStrong(weak);
303     }
304     return weak;
305   }
306   // Check the image for a match.
307   if (!images_added_to_intern_table_) {
308     mirror::String* const image_string = LookupStringFromImage(s);
309     if (image_string != nullptr) {
310       return is_strong ? InsertStrong(image_string) : InsertWeak(image_string);
311     }
312   }
313   // No match in the strong table or the weak table. Insert into the strong / weak table.
314   return is_strong ? InsertStrong(s) : InsertWeak(s);
315 }
316 
InternStrong(int32_t utf16_length,const char * utf8_data)317 mirror::String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) {
318   DCHECK(utf8_data != nullptr);
319   return InternStrong(mirror::String::AllocFromModifiedUtf8(
320       Thread::Current(), utf16_length, utf8_data));
321 }
322 
InternStrong(const char * utf8_data)323 mirror::String* InternTable::InternStrong(const char* utf8_data) {
324   DCHECK(utf8_data != nullptr);
325   return InternStrong(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
326 }
327 
InternStrongImageString(mirror::String * s)328 mirror::String* InternTable::InternStrongImageString(mirror::String* s) {
329   // May be holding the heap bitmap lock.
330   return Insert(s, true, true);
331 }
332 
InternStrong(mirror::String * s)333 mirror::String* InternTable::InternStrong(mirror::String* s) {
334   return Insert(s, true, false);
335 }
336 
InternWeak(mirror::String * s)337 mirror::String* InternTable::InternWeak(mirror::String* s) {
338   return Insert(s, false, false);
339 }
340 
ContainsWeak(mirror::String * s)341 bool InternTable::ContainsWeak(mirror::String* s) {
342   return LookupWeak(Thread::Current(), s) == s;
343 }
344 
SweepInternTableWeaks(IsMarkedVisitor * visitor)345 void InternTable::SweepInternTableWeaks(IsMarkedVisitor* visitor) {
346   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
347   weak_interns_.SweepWeaks(visitor);
348 }
349 
AddTableFromMemory(const uint8_t * ptr)350 size_t InternTable::AddTableFromMemory(const uint8_t* ptr) {
351   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
352   return AddTableFromMemoryLocked(ptr);
353 }
354 
AddTableFromMemoryLocked(const uint8_t * ptr)355 size_t InternTable::AddTableFromMemoryLocked(const uint8_t* ptr) {
356   return strong_interns_.AddTableFromMemory(ptr);
357 }
358 
WriteToMemory(uint8_t * ptr)359 size_t InternTable::WriteToMemory(uint8_t* ptr) {
360   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
361   return strong_interns_.WriteToMemory(ptr);
362 }
363 
operator ()(const GcRoot<mirror::String> & root) const364 std::size_t InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& root) const {
365   if (kIsDebugBuild) {
366     Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
367   }
368   return static_cast<size_t>(root.Read()->GetHashCode());
369 }
370 
operator ()(const GcRoot<mirror::String> & a,const GcRoot<mirror::String> & b) const371 bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
372                                                const GcRoot<mirror::String>& b) const {
373   if (kIsDebugBuild) {
374     Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
375   }
376   return a.Read()->Equals(b.Read());
377 }
378 
operator ()(const GcRoot<mirror::String> & a,const Utf8String & b) const379 bool InternTable::StringHashEquals::operator()(const GcRoot<mirror::String>& a,
380                                                const Utf8String& b) const {
381   if (kIsDebugBuild) {
382     Locks::mutator_lock_->AssertSharedHeld(Thread::Current());
383   }
384   mirror::String* a_string = a.Read();
385   uint32_t a_length = static_cast<uint32_t>(a_string->GetLength());
386   if (a_length != b.GetUtf16Length()) {
387     return false;
388   }
389   const uint16_t* a_value = a_string->GetValue();
390   return CompareModifiedUtf8ToUtf16AsCodePointValues(b.GetUtf8Data(), a_value, a_length) == 0;
391 }
392 
AddTableFromMemory(const uint8_t * ptr)393 size_t InternTable::Table::AddTableFromMemory(const uint8_t* ptr) {
394   size_t read_count = 0;
395   UnorderedSet set(ptr, /*make copy*/false, &read_count);
396   if (set.Empty()) {
397     // Avoid inserting empty sets.
398     return read_count;
399   }
400   // TODO: Disable this for app images if app images have intern tables.
401   static constexpr bool kCheckDuplicates = true;
402   if (kCheckDuplicates) {
403     for (GcRoot<mirror::String>& string : set) {
404       CHECK(Find(string.Read()) == nullptr) << "Already found " << string.Read()->ToModifiedUtf8();
405     }
406   }
407   // Insert at the front since we add new interns into the back.
408   tables_.insert(tables_.begin(), std::move(set));
409   return read_count;
410 }
411 
WriteToMemory(uint8_t * ptr)412 size_t InternTable::Table::WriteToMemory(uint8_t* ptr) {
413   if (tables_.empty()) {
414     return 0;
415   }
416   UnorderedSet* table_to_write;
417   UnorderedSet combined;
418   if (tables_.size() > 1) {
419     table_to_write = &combined;
420     for (UnorderedSet& table : tables_) {
421       for (GcRoot<mirror::String>& string : table) {
422         combined.Insert(string);
423       }
424     }
425   } else {
426     table_to_write = &tables_.back();
427   }
428   return table_to_write->WriteToMemory(ptr);
429 }
430 
Remove(mirror::String * s)431 void InternTable::Table::Remove(mirror::String* s) {
432   for (UnorderedSet& table : tables_) {
433     auto it = table.Find(GcRoot<mirror::String>(s));
434     if (it != table.end()) {
435       table.Erase(it);
436       return;
437     }
438   }
439   LOG(FATAL) << "Attempting to remove non-interned string " << s->ToModifiedUtf8();
440 }
441 
Find(mirror::String * s)442 mirror::String* InternTable::Table::Find(mirror::String* s) {
443   Locks::intern_table_lock_->AssertHeld(Thread::Current());
444   for (UnorderedSet& table : tables_) {
445     auto it = table.Find(GcRoot<mirror::String>(s));
446     if (it != table.end()) {
447       return it->Read();
448     }
449   }
450   return nullptr;
451 }
452 
Find(const Utf8String & string)453 mirror::String* InternTable::Table::Find(const Utf8String& string) {
454   Locks::intern_table_lock_->AssertHeld(Thread::Current());
455   for (UnorderedSet& table : tables_) {
456     auto it = table.Find(string);
457     if (it != table.end()) {
458       return it->Read();
459     }
460   }
461   return nullptr;
462 }
463 
AddNewTable()464 void InternTable::Table::AddNewTable() {
465   tables_.push_back(UnorderedSet());
466 }
467 
Insert(mirror::String * s)468 void InternTable::Table::Insert(mirror::String* s) {
469   // Always insert the last table, the image tables are before and we avoid inserting into these
470   // to prevent dirty pages.
471   DCHECK(!tables_.empty());
472   tables_.back().Insert(GcRoot<mirror::String>(s));
473 }
474 
VisitRoots(RootVisitor * visitor)475 void InternTable::Table::VisitRoots(RootVisitor* visitor) {
476   BufferedRootVisitor<kDefaultBufferedRootCount> buffered_visitor(
477       visitor, RootInfo(kRootInternedString));
478   for (UnorderedSet& table : tables_) {
479     for (auto& intern : table) {
480       buffered_visitor.VisitRoot(intern);
481     }
482   }
483 }
484 
SweepWeaks(IsMarkedVisitor * visitor)485 void InternTable::Table::SweepWeaks(IsMarkedVisitor* visitor) {
486   for (UnorderedSet& table : tables_) {
487     SweepWeaks(&table, visitor);
488   }
489 }
490 
SweepWeaks(UnorderedSet * set,IsMarkedVisitor * visitor)491 void InternTable::Table::SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) {
492   for (auto it = set->begin(), end = set->end(); it != end;) {
493     // This does not need a read barrier because this is called by GC.
494     mirror::Object* object = it->Read<kWithoutReadBarrier>();
495     mirror::Object* new_object = visitor->IsMarked(object);
496     if (new_object == nullptr) {
497       it = set->Erase(it);
498     } else {
499       *it = GcRoot<mirror::String>(new_object->AsString());
500       ++it;
501     }
502   }
503 }
504 
Size() const505 size_t InternTable::Table::Size() const {
506   return std::accumulate(tables_.begin(),
507                          tables_.end(),
508                          0U,
509                          [](size_t sum, const UnorderedSet& set) {
510                            return sum + set.Size();
511                          });
512 }
513 
ChangeWeakRootState(gc::WeakRootState new_state)514 void InternTable::ChangeWeakRootState(gc::WeakRootState new_state) {
515   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
516   ChangeWeakRootStateLocked(new_state);
517 }
518 
ChangeWeakRootStateLocked(gc::WeakRootState new_state)519 void InternTable::ChangeWeakRootStateLocked(gc::WeakRootState new_state) {
520   CHECK(!kUseReadBarrier);
521   weak_root_state_ = new_state;
522   if (new_state != gc::kWeakRootStateNoReadsOrWrites) {
523     weak_intern_condition_.Broadcast(Thread::Current());
524   }
525 }
526 
Table()527 InternTable::Table::Table() {
528   Runtime* const runtime = Runtime::Current();
529   // Initial table.
530   tables_.push_back(UnorderedSet());
531   tables_.back().SetLoadFactor(runtime->GetHashTableMinLoadFactor(),
532                                runtime->GetHashTableMaxLoadFactor());
533 }
534 
535 }  // namespace art
536