intern_table.cc revision 94f7b49578b6aaa80de8ffed230648d601393905
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/space/image_space.h" 22#include "mirror/dex_cache.h" 23#include "mirror/object_array-inl.h" 24#include "mirror/object-inl.h" 25#include "mirror/string.h" 26#include "thread.h" 27#include "utf.h" 28 29namespace art { 30 31InternTable::InternTable() 32 : log_new_roots_(false), allow_new_interns_(true), 33 new_intern_condition_("New intern condition", *Locks::intern_table_lock_) { 34} 35 36size_t InternTable::Size() const { 37 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 38 return strong_interns_.size() + weak_interns_.size(); 39} 40 41size_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 51void InternTable::DumpForSigQuit(std::ostream& os) const { 52 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 53 os << "Intern table: " << strong_interns_.size() << " strong; " 54 << weak_interns_.size() << " weak\n"; 55} 56 57void InternTable::VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags) { 58 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 59 if ((flags & kVisitRootFlagAllRoots) != 0) { 60 for (auto& strong_intern : strong_interns_) { 61 strong_intern.second.VisitRoot(callback, arg, 0, kRootInternedString); 62 DCHECK(!strong_intern.second.IsNull()); 63 } 64 } else if ((flags & kVisitRootFlagNewRoots) != 0) { 65 for (auto& pair : new_strong_intern_roots_) { 66 mirror::String* old_ref = pair.second.Read<kWithoutReadBarrier>(); 67 pair.second.VisitRoot(callback, arg, 0, kRootInternedString); 68 mirror::String* new_ref = pair.second.Read<kWithoutReadBarrier>(); 69 if (UNLIKELY(new_ref != 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.Read<kWithoutReadBarrier>()) { 77 it->second = GcRoot<mirror::String>(new_ref); 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; 91 } 92 // Note: we deliberately don't visit the weak_interns_ table and the immutable image roots. 93} 94 95mirror::String* InternTable::LookupStrong(mirror::String* s, int32_t hash_code) { 96 return Lookup(&strong_interns_, s, hash_code); 97} 98 99mirror::String* InternTable::LookupWeak(mirror::String* s, int32_t hash_code) { 100 // Weak interns need a read barrier because they are weak roots. 101 return Lookup(&weak_interns_, s, hash_code); 102} 103 104mirror::String* InternTable::Lookup(Table* table, mirror::String* s, int32_t hash_code) { 105 Locks::intern_table_lock_->AssertHeld(Thread::Current()); 106 for (auto it = table->lower_bound(hash_code), end = table->end(); 107 it != end && it->first == hash_code; ++it) { 108 mirror::String* existing_string = it->second.Read(); 109 if (existing_string->Equals(s)) { 110 return existing_string; 111 } 112 } 113 return NULL; 114} 115 116mirror::String* InternTable::InsertStrong(mirror::String* s, int32_t hash_code) { 117 Runtime* runtime = Runtime::Current(); 118 if (runtime->IsActiveTransaction()) { 119 runtime->RecordStrongStringInsertion(s, hash_code); 120 } 121 if (log_new_roots_) { 122 new_strong_intern_roots_.push_back(std::make_pair(hash_code, GcRoot<mirror::String>(s))); 123 } 124 strong_interns_.insert(std::make_pair(hash_code, GcRoot<mirror::String>(s))); 125 return s; 126} 127 128mirror::String* InternTable::InsertWeak(mirror::String* s, int32_t hash_code) { 129 Runtime* runtime = Runtime::Current(); 130 if (runtime->IsActiveTransaction()) { 131 runtime->RecordWeakStringInsertion(s, hash_code); 132 } 133 weak_interns_.insert(std::make_pair(hash_code, GcRoot<mirror::String>(s))); 134 return s; 135} 136 137void InternTable::RemoveStrong(mirror::String* s, int32_t hash_code) { 138 Remove(&strong_interns_, s, hash_code); 139} 140 141void InternTable::RemoveWeak(mirror::String* s, int32_t hash_code) { 142 Runtime* runtime = Runtime::Current(); 143 if (runtime->IsActiveTransaction()) { 144 runtime->RecordWeakStringRemoval(s, hash_code); 145 } 146 Remove(&weak_interns_, s, hash_code); 147} 148 149void InternTable::Remove(Table* table, mirror::String* s, int32_t hash_code) { 150 for (auto it = table->lower_bound(hash_code), end = table->end(); 151 it != end && it->first == hash_code; ++it) { 152 mirror::String* existing_string = it->second.Read(); 153 if (existing_string == s) { 154 table->erase(it); 155 return; 156 } 157 } 158} 159 160// Insert/remove methods used to undo changes made during an aborted transaction. 161mirror::String* InternTable::InsertStrongFromTransaction(mirror::String* s, int32_t hash_code) { 162 DCHECK(!Runtime::Current()->IsActiveTransaction()); 163 return InsertStrong(s, hash_code); 164} 165mirror::String* InternTable::InsertWeakFromTransaction(mirror::String* s, int32_t hash_code) { 166 DCHECK(!Runtime::Current()->IsActiveTransaction()); 167 return InsertWeak(s, hash_code); 168} 169void InternTable::RemoveStrongFromTransaction(mirror::String* s, int32_t hash_code) { 170 DCHECK(!Runtime::Current()->IsActiveTransaction()); 171 RemoveStrong(s, hash_code); 172} 173void InternTable::RemoveWeakFromTransaction(mirror::String* s, int32_t hash_code) { 174 DCHECK(!Runtime::Current()->IsActiveTransaction()); 175 RemoveWeak(s, hash_code); 176} 177 178static mirror::String* LookupStringFromImage(mirror::String* s) 179 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 180 gc::space::ImageSpace* image = Runtime::Current()->GetHeap()->GetImageSpace(); 181 if (image == NULL) { 182 return NULL; // No image present. 183 } 184 mirror::Object* root = image->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches); 185 mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>(); 186 const std::string utf8 = s->ToModifiedUtf8(); 187 for (int32_t i = 0; i < dex_caches->GetLength(); ++i) { 188 mirror::DexCache* dex_cache = dex_caches->Get(i); 189 const DexFile* dex_file = dex_cache->GetDexFile(); 190 // Binary search the dex file for the string index. 191 const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str()); 192 if (string_id != NULL) { 193 uint32_t string_idx = dex_file->GetIndexForStringId(*string_id); 194 mirror::String* image = dex_cache->GetResolvedString(string_idx); 195 if (image != NULL) { 196 return image; 197 } 198 } 199 } 200 return NULL; 201} 202 203void InternTable::AllowNewInterns() { 204 Thread* self = Thread::Current(); 205 MutexLock mu(self, *Locks::intern_table_lock_); 206 allow_new_interns_ = true; 207 new_intern_condition_.Broadcast(self); 208} 209 210void InternTable::DisallowNewInterns() { 211 Thread* self = Thread::Current(); 212 MutexLock mu(self, *Locks::intern_table_lock_); 213 allow_new_interns_ = false; 214} 215 216mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) { 217 Thread* self = Thread::Current(); 218 MutexLock mu(self, *Locks::intern_table_lock_); 219 220 DCHECK(s != NULL); 221 uint32_t hash_code = s->GetHashCode(); 222 223 while (UNLIKELY(!allow_new_interns_)) { 224 new_intern_condition_.WaitHoldingLocks(self); 225 } 226 227 if (is_strong) { 228 // Check the strong table for a match. 229 mirror::String* strong = LookupStrong(s, hash_code); 230 if (strong != NULL) { 231 return strong; 232 } 233 234 // Check the image for a match. 235 mirror::String* image = LookupStringFromImage(s); 236 if (image != NULL) { 237 return InsertStrong(image, hash_code); 238 } 239 240 // There is no match in the strong table, check the weak table. 241 mirror::String* weak = LookupWeak(s, hash_code); 242 if (weak != NULL) { 243 // A match was found in the weak table. Promote to the strong table. 244 RemoveWeak(weak, hash_code); 245 return InsertStrong(weak, hash_code); 246 } 247 248 // No match in the strong table or the weak table. Insert into the strong 249 // table. 250 return InsertStrong(s, hash_code); 251 } 252 253 // Check the strong table for a match. 254 mirror::String* strong = LookupStrong(s, hash_code); 255 if (strong != NULL) { 256 return strong; 257 } 258 // Check the image for a match. 259 mirror::String* image = LookupStringFromImage(s); 260 if (image != NULL) { 261 return InsertWeak(image, hash_code); 262 } 263 // Check the weak table for a match. 264 mirror::String* weak = LookupWeak(s, hash_code); 265 if (weak != NULL) { 266 return weak; 267 } 268 // Insert into the weak table. 269 return InsertWeak(s, hash_code); 270} 271 272mirror::String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) { 273 DCHECK(utf8_data != nullptr); 274 return InternStrong(mirror::String::AllocFromModifiedUtf8( 275 Thread::Current(), utf16_length, utf8_data)); 276} 277 278mirror::String* InternTable::InternStrong(const char* utf8_data) { 279 DCHECK(utf8_data != nullptr); 280 return InternStrong(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data)); 281} 282 283mirror::String* InternTable::InternStrong(mirror::String* s) { 284 if (s == nullptr) { 285 return nullptr; 286 } 287 return Insert(s, true); 288} 289 290mirror::String* InternTable::InternWeak(mirror::String* s) { 291 if (s == nullptr) { 292 return nullptr; 293 } 294 return Insert(s, false); 295} 296 297bool InternTable::ContainsWeak(mirror::String* s) { 298 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 299 const mirror::String* found = LookupWeak(s, s->GetHashCode()); 300 return found == s; 301} 302 303void InternTable::SweepInternTableWeaks(IsMarkedCallback* callback, void* arg) { 304 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 305 for (auto it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) { 306 // This does not need a read barrier because this is called by GC. 307 mirror::Object* object = it->second.Read<kWithoutReadBarrier>(); 308 mirror::Object* new_object = callback(object, arg); 309 if (new_object == nullptr) { 310 // TODO: use it = weak_interns_.erase(it) when we get a c++11 stl. 311 weak_interns_.erase(it++); 312 } else { 313 it->second = GcRoot<mirror::String>(down_cast<mirror::String*>(new_object)); 314 ++it; 315 } 316 } 317} 318 319} // namespace art 320