intern_table.cc revision 1bd4872773184fb9f5f152c7bbf9856a8235d2af
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 41void InternTable::DumpForSigQuit(std::ostream& os) const { 42 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 43 os << "Intern table: " << strong_interns_.size() << " strong; " 44 << weak_interns_.size() << " weak\n"; 45} 46 47void InternTable::VisitRoots(RootCallback* callback, void* arg, VisitRootFlags flags) { 48 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 49 if ((flags & kVisitRootFlagAllRoots) != 0) { 50 for (auto& strong_intern : strong_interns_) { 51 callback(reinterpret_cast<mirror::Object**>(&strong_intern.second), arg, 0, 52 kRootInternedString); 53 DCHECK(strong_intern.second != nullptr); 54 } 55 } else if ((flags & kVisitRootFlagNewRoots) != 0) { 56 for (auto& pair : new_strong_intern_roots_) { 57 mirror::String* old_ref = pair.second; 58 callback(reinterpret_cast<mirror::Object**>(&pair.second), arg, 0, kRootInternedString); 59 if (UNLIKELY(pair.second != old_ref)) { 60 // Uh ohes, GC moved a root in the log. Need to search the strong interns and update the 61 // corresponding object. This is slow, but luckily for us, this may only happen with a 62 // concurrent moving GC. 63 for (auto it = strong_interns_.lower_bound(pair.first), end = strong_interns_.end(); 64 it != end && it->first == pair.first; ++it) { 65 // If the class stored matches the old class, update it to the new value. 66 if (old_ref == it->second) { 67 it->second = pair.second; 68 } 69 } 70 } 71 } 72 } 73 74 if ((flags & kVisitRootFlagClearRootLog) != 0) { 75 new_strong_intern_roots_.clear(); 76 } 77 if ((flags & kVisitRootFlagStartLoggingNewRoots) != 0) { 78 log_new_roots_ = true; 79 } else if ((flags & kVisitRootFlagStopLoggingNewRoots) != 0) { 80 log_new_roots_ = false; 81 } 82 // Note: we deliberately don't visit the weak_interns_ table and the immutable image roots. 83} 84 85mirror::String* InternTable::LookupStrong(mirror::String* s, int32_t hash_code) { 86 return Lookup<kWithoutReadBarrier>(&strong_interns_, s, hash_code); 87} 88 89mirror::String* InternTable::LookupWeak(mirror::String* s, int32_t hash_code) { 90 // Weak interns need a read barrier because they are weak roots. 91 return Lookup<kWithReadBarrier>(&weak_interns_, s, hash_code); 92} 93 94template<ReadBarrierOption kReadBarrierOption> 95mirror::String* InternTable::Lookup(Table* table, mirror::String* s, int32_t hash_code) { 96 CHECK_EQ(table == &weak_interns_, kReadBarrierOption == kWithReadBarrier) 97 << "Only weak_interns_ needs a read barrier."; 98 Locks::intern_table_lock_->AssertHeld(Thread::Current()); 99 for (auto it = table->lower_bound(hash_code), end = table->end(); 100 it != end && it->first == hash_code; ++it) { 101 mirror::String** weak_root = &it->second; 102 mirror::String* existing_string = 103 ReadBarrier::BarrierForWeakRoot<mirror::String, kReadBarrierOption>(weak_root); 104 if (existing_string->Equals(s)) { 105 return existing_string; 106 } 107 } 108 return NULL; 109} 110 111mirror::String* InternTable::InsertStrong(mirror::String* s, int32_t hash_code) { 112 Runtime* runtime = Runtime::Current(); 113 if (runtime->IsActiveTransaction()) { 114 runtime->RecordStrongStringInsertion(s, hash_code); 115 } 116 if (log_new_roots_) { 117 new_strong_intern_roots_.push_back(std::make_pair(hash_code, s)); 118 } 119 strong_interns_.insert(std::make_pair(hash_code, s)); 120 return s; 121} 122 123mirror::String* InternTable::InsertWeak(mirror::String* s, int32_t hash_code) { 124 Runtime* runtime = Runtime::Current(); 125 if (runtime->IsActiveTransaction()) { 126 runtime->RecordWeakStringInsertion(s, hash_code); 127 } 128 weak_interns_.insert(std::make_pair(hash_code, s)); 129 return s; 130} 131 132void InternTable::RemoveStrong(mirror::String* s, int32_t hash_code) { 133 Remove<kWithoutReadBarrier>(&strong_interns_, s, hash_code); 134} 135 136void InternTable::RemoveWeak(mirror::String* s, int32_t hash_code) { 137 Runtime* runtime = Runtime::Current(); 138 if (runtime->IsActiveTransaction()) { 139 runtime->RecordWeakStringRemoval(s, hash_code); 140 } 141 Remove<kWithReadBarrier>(&weak_interns_, s, hash_code); 142} 143 144template<ReadBarrierOption kReadBarrierOption> 145void InternTable::Remove(Table* table, mirror::String* s, int32_t hash_code) { 146 CHECK_EQ(table == &weak_interns_, kReadBarrierOption == kWithReadBarrier) 147 << "Only weak_interns_ needs a read barrier."; 148 for (auto it = table->lower_bound(hash_code), end = table->end(); 149 it != end && it->first == hash_code; ++it) { 150 mirror::String** weak_root = &it->second; 151 mirror::String* existing_string = 152 ReadBarrier::BarrierForWeakRoot<mirror::String, kReadBarrierOption>(weak_root); 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; 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 = down_cast<mirror::String*>(new_object); 314 ++it; 315 } 316 } 317} 318 319} // namespace art 320