intern_table.cc revision 700a402244a1a423da4f3ba8032459f4b65fa18f
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::Lookup(Table& table, mirror::String* s, int32_t hash_code) { 86 Locks::intern_table_lock_->AssertHeld(Thread::Current()); 87 for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) { 88 mirror::String* existing_string = it->second; 89 if (existing_string->Equals(s)) { 90 return existing_string; 91 } 92 } 93 return NULL; 94} 95 96mirror::String* InternTable::InsertStrong(mirror::String* s, int32_t hash_code) { 97 Runtime* runtime = Runtime::Current(); 98 if (runtime->IsActiveTransaction()) { 99 runtime->RecordStrongStringInsertion(s, hash_code); 100 } 101 if (log_new_roots_) { 102 new_strong_intern_roots_.push_back(std::make_pair(hash_code, s)); 103 } 104 strong_interns_.insert(std::make_pair(hash_code, s)); 105 return s; 106} 107 108mirror::String* InternTable::InsertWeak(mirror::String* s, int32_t hash_code) { 109 Runtime* runtime = Runtime::Current(); 110 if (runtime->IsActiveTransaction()) { 111 runtime->RecordWeakStringInsertion(s, hash_code); 112 } 113 weak_interns_.insert(std::make_pair(hash_code, s)); 114 return s; 115} 116 117void InternTable::RemoveWeak(mirror::String* s, int32_t hash_code) { 118 Runtime* runtime = Runtime::Current(); 119 if (runtime->IsActiveTransaction()) { 120 runtime->RecordWeakStringRemoval(s, hash_code); 121 } 122 Remove(weak_interns_, s, hash_code); 123} 124 125void InternTable::Remove(Table& table, mirror::String* s, int32_t hash_code) { 126 for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) { 127 if (it->second == s) { 128 table.erase(it); 129 return; 130 } 131 } 132} 133 134// Insert/remove methods used to undo changes made during an aborted transaction. 135mirror::String* InternTable::InsertStrongFromTransaction(mirror::String* s, int32_t hash_code) { 136 DCHECK(!Runtime::Current()->IsActiveTransaction()); 137 return InsertStrong(s, hash_code); 138} 139mirror::String* InternTable::InsertWeakFromTransaction(mirror::String* s, int32_t hash_code) { 140 DCHECK(!Runtime::Current()->IsActiveTransaction()); 141 return InsertWeak(s, hash_code); 142} 143void InternTable::RemoveStrongFromTransaction(mirror::String* s, int32_t hash_code) { 144 DCHECK(!Runtime::Current()->IsActiveTransaction()); 145 Remove(strong_interns_, s, hash_code); 146} 147void InternTable::RemoveWeakFromTransaction(mirror::String* s, int32_t hash_code) { 148 DCHECK(!Runtime::Current()->IsActiveTransaction()); 149 Remove(weak_interns_, s, hash_code); 150} 151 152static mirror::String* LookupStringFromImage(mirror::String* s) 153 SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { 154 gc::space::ImageSpace* image = Runtime::Current()->GetHeap()->GetImageSpace(); 155 if (image == NULL) { 156 return NULL; // No image present. 157 } 158 mirror::Object* root = image->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches); 159 mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>(); 160 const std::string utf8 = s->ToModifiedUtf8(); 161 for (int32_t i = 0; i < dex_caches->GetLength(); ++i) { 162 mirror::DexCache* dex_cache = dex_caches->Get(i); 163 const DexFile* dex_file = dex_cache->GetDexFile(); 164 // Binary search the dex file for the string index. 165 const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str()); 166 if (string_id != NULL) { 167 uint32_t string_idx = dex_file->GetIndexForStringId(*string_id); 168 mirror::String* image = dex_cache->GetResolvedString(string_idx); 169 if (image != NULL) { 170 return image; 171 } 172 } 173 } 174 return NULL; 175} 176 177void InternTable::AllowNewInterns() { 178 Thread* self = Thread::Current(); 179 MutexLock mu(self, *Locks::intern_table_lock_); 180 allow_new_interns_ = true; 181 new_intern_condition_.Broadcast(self); 182} 183 184void InternTable::DisallowNewInterns() { 185 Thread* self = Thread::Current(); 186 MutexLock mu(self, *Locks::intern_table_lock_); 187 allow_new_interns_ = false; 188} 189 190mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) { 191 Thread* self = Thread::Current(); 192 MutexLock mu(self, *Locks::intern_table_lock_); 193 194 DCHECK(s != NULL); 195 uint32_t hash_code = s->GetHashCode(); 196 197 while (UNLIKELY(!allow_new_interns_)) { 198 new_intern_condition_.WaitHoldingLocks(self); 199 } 200 201 if (is_strong) { 202 // Check the strong table for a match. 203 mirror::String* strong = Lookup(strong_interns_, s, hash_code); 204 if (strong != NULL) { 205 return strong; 206 } 207 208 // Check the image for a match. 209 mirror::String* image = LookupStringFromImage(s); 210 if (image != NULL) { 211 return InsertStrong(image, hash_code); 212 } 213 214 // There is no match in the strong table, check the weak table. 215 mirror::String* weak = Lookup(weak_interns_, s, hash_code); 216 if (weak != NULL) { 217 // A match was found in the weak table. Promote to the strong table. 218 RemoveWeak(weak, hash_code); 219 return InsertStrong(weak, hash_code); 220 } 221 222 // No match in the strong table or the weak table. Insert into the strong 223 // table. 224 return InsertStrong(s, hash_code); 225 } 226 227 // Check the strong table for a match. 228 mirror::String* strong = Lookup(strong_interns_, s, hash_code); 229 if (strong != NULL) { 230 return strong; 231 } 232 // Check the image for a match. 233 mirror::String* image = LookupStringFromImage(s); 234 if (image != NULL) { 235 return InsertWeak(image, hash_code); 236 } 237 // Check the weak table for a match. 238 mirror::String* weak = Lookup(weak_interns_, s, hash_code); 239 if (weak != NULL) { 240 return weak; 241 } 242 // Insert into the weak table. 243 return InsertWeak(s, hash_code); 244} 245 246mirror::String* InternTable::InternStrong(int32_t utf16_length, const char* utf8_data) { 247 DCHECK(utf8_data != nullptr); 248 return InternStrong(mirror::String::AllocFromModifiedUtf8( 249 Thread::Current(), utf16_length, utf8_data)); 250} 251 252mirror::String* InternTable::InternStrong(const char* utf8_data) { 253 DCHECK(utf8_data != nullptr); 254 return InternStrong(mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data)); 255} 256 257mirror::String* InternTable::InternStrong(mirror::String* s) { 258 if (s == nullptr) { 259 return nullptr; 260 } 261 return Insert(s, true); 262} 263 264mirror::String* InternTable::InternWeak(mirror::String* s) { 265 if (s == nullptr) { 266 return nullptr; 267 } 268 return Insert(s, false); 269} 270 271bool InternTable::ContainsWeak(mirror::String* s) { 272 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 273 const mirror::String* found = Lookup(weak_interns_, s, s->GetHashCode()); 274 return found == s; 275} 276 277void InternTable::SweepInternTableWeaks(IsMarkedCallback* callback, void* arg) { 278 MutexLock mu(Thread::Current(), *Locks::intern_table_lock_); 279 for (auto it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) { 280 mirror::Object* object = it->second; 281 mirror::Object* new_object = callback(object, arg); 282 if (new_object == nullptr) { 283 // TODO: use it = weak_interns_.erase(it) when we get a c++11 stl. 284 weak_interns_.erase(it++); 285 } else { 286 it->second = down_cast<mirror::String*>(new_object); 287 ++it; 288 } 289 } 290} 291 292} // namespace art 293