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-inl.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 
Remove(ObjPtr<mirror::String> s)310 void InternTable::Table::Remove(ObjPtr<mirror::String> s) {
311   for (InternalTable& table : tables_) {
312     auto it = table.set_.find(GcRoot<mirror::String>(s));
313     if (it != table.set_.end()) {
314       table.set_.erase(it);
315       return;
316     }
317   }
318   LOG(FATAL) << "Attempting to remove non-interned string " << s->ToModifiedUtf8();
319 }
320 
Find(ObjPtr<mirror::String> s)321 ObjPtr<mirror::String> InternTable::Table::Find(ObjPtr<mirror::String> s) {
322   Locks::intern_table_lock_->AssertHeld(Thread::Current());
323   for (InternalTable& table : tables_) {
324     auto it = table.set_.find(GcRoot<mirror::String>(s));
325     if (it != table.set_.end()) {
326       return it->Read();
327     }
328   }
329   return nullptr;
330 }
331 
Find(const Utf8String & string)332 ObjPtr<mirror::String> InternTable::Table::Find(const Utf8String& string) {
333   Locks::intern_table_lock_->AssertHeld(Thread::Current());
334   for (InternalTable& table : tables_) {
335     auto it = table.set_.find(string);
336     if (it != table.set_.end()) {
337       return it->Read();
338     }
339   }
340   return nullptr;
341 }
342 
AddNewTable()343 void InternTable::Table::AddNewTable() {
344   tables_.push_back(InternalTable());
345 }
346 
Insert(ObjPtr<mirror::String> s)347 void InternTable::Table::Insert(ObjPtr<mirror::String> s) {
348   // Always insert the last table, the image tables are before and we avoid inserting into these
349   // to prevent dirty pages.
350   DCHECK(!tables_.empty());
351   tables_.back().set_.insert(GcRoot<mirror::String>(s));
352 }
353 
VisitRoots(RootVisitor * visitor)354 void InternTable::Table::VisitRoots(RootVisitor* visitor) {
355   BufferedRootVisitor<kDefaultBufferedRootCount> buffered_visitor(
356       visitor, RootInfo(kRootInternedString));
357   for (InternalTable& table : tables_) {
358     for (auto& intern : table.set_) {
359       buffered_visitor.VisitRoot(intern);
360     }
361   }
362 }
363 
SweepWeaks(IsMarkedVisitor * visitor)364 void InternTable::Table::SweepWeaks(IsMarkedVisitor* visitor) {
365   for (InternalTable& table : tables_) {
366     SweepWeaks(&table.set_, visitor);
367   }
368 }
369 
SweepWeaks(UnorderedSet * set,IsMarkedVisitor * visitor)370 void InternTable::Table::SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) {
371   for (auto it = set->begin(), end = set->end(); it != end;) {
372     // This does not need a read barrier because this is called by GC.
373     mirror::Object* object = it->Read<kWithoutReadBarrier>();
374     mirror::Object* new_object = visitor->IsMarked(object);
375     if (new_object == nullptr) {
376       it = set->erase(it);
377     } else {
378       *it = GcRoot<mirror::String>(new_object->AsString());
379       ++it;
380     }
381   }
382 }
383 
Size() const384 size_t InternTable::Table::Size() const {
385   return std::accumulate(tables_.begin(),
386                          tables_.end(),
387                          0U,
388                          [](size_t sum, const InternalTable& table) {
389                            return sum + table.Size();
390                          });
391 }
392 
ChangeWeakRootState(gc::WeakRootState new_state)393 void InternTable::ChangeWeakRootState(gc::WeakRootState new_state) {
394   MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
395   ChangeWeakRootStateLocked(new_state);
396 }
397 
ChangeWeakRootStateLocked(gc::WeakRootState new_state)398 void InternTable::ChangeWeakRootStateLocked(gc::WeakRootState new_state) {
399   CHECK(!kUseReadBarrier);
400   weak_root_state_ = new_state;
401   if (new_state != gc::kWeakRootStateNoReadsOrWrites) {
402     weak_intern_condition_.Broadcast(Thread::Current());
403   }
404 }
405 
Table()406 InternTable::Table::Table() {
407   Runtime* const runtime = Runtime::Current();
408   InternalTable initial_table;
409   initial_table.set_.SetLoadFactor(runtime->GetHashTableMinLoadFactor(),
410                                    runtime->GetHashTableMaxLoadFactor());
411   tables_.push_back(std::move(initial_table));
412 }
413 
414 }  // namespace art
415