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 #ifndef ART_RUNTIME_INTERN_TABLE_H_ 18 #define ART_RUNTIME_INTERN_TABLE_H_ 19 20 #include <unordered_set> 21 22 #include "base/atomic.h" 23 #include "base/allocator.h" 24 #include "base/hash_set.h" 25 #include "base/mutex.h" 26 #include "gc/weak_root_state.h" 27 #include "gc_root.h" 28 29 namespace art { 30 31 class IsMarkedVisitor; 32 33 namespace gc { 34 namespace space { 35 class ImageSpace; 36 } // namespace space 37 } // namespace gc 38 39 enum VisitRootFlags : uint8_t; 40 41 namespace linker { 42 class OatWriter; 43 } // namespace linker 44 45 namespace mirror { 46 class String; 47 } // namespace mirror 48 class Transaction; 49 50 /** 51 * Used to intern strings. 52 * 53 * There are actually two tables: one that holds strong references to its strings, and one that 54 * holds weak references. The former is used for string literals, for which there is an effective 55 * reference from the constant pool. The latter is used for strings interned at runtime via 56 * String.intern. Some code (XML parsers being a prime example) relies on being able to intern 57 * arbitrarily many strings for the duration of a parse without permanently increasing the memory 58 * footprint. 59 */ 60 class InternTable { 61 public: 62 InternTable(); 63 64 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 65 ObjPtr<mirror::String> InternStrong(int32_t utf16_length, const char* utf8_data) 66 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_); 67 68 // Only used by image writer. Special version that may not cause thread suspension since the GC 69 // cannot be running while we are doing image writing. Maybe be called while while holding a 70 // lock since there will not be thread suspension. 71 ObjPtr<mirror::String> InternStrongImageString(ObjPtr<mirror::String> s) 72 REQUIRES_SHARED(Locks::mutator_lock_); 73 74 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 75 ObjPtr<mirror::String> InternStrong(const char* utf8_data) REQUIRES_SHARED(Locks::mutator_lock_) 76 REQUIRES(!Roles::uninterruptible_); 77 78 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 79 ObjPtr<mirror::String> InternStrong(ObjPtr<mirror::String> s) 80 REQUIRES_SHARED(Locks::mutator_lock_) 81 REQUIRES(!Roles::uninterruptible_); 82 83 // Interns a potentially new string in the 'weak' table. May cause thread suspension. 84 ObjPtr<mirror::String> InternWeak(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 85 REQUIRES(!Roles::uninterruptible_); 86 87 void SweepInternTableWeaks(IsMarkedVisitor* visitor) REQUIRES_SHARED(Locks::mutator_lock_) 88 REQUIRES(!Locks::intern_table_lock_); 89 90 bool ContainsWeak(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 91 REQUIRES(!Locks::intern_table_lock_); 92 93 // Lookup a strong intern, returns null if not found. 94 ObjPtr<mirror::String> LookupStrong(Thread* self, ObjPtr<mirror::String> s) 95 REQUIRES(!Locks::intern_table_lock_) 96 REQUIRES_SHARED(Locks::mutator_lock_); 97 ObjPtr<mirror::String> LookupStrong(Thread* self, uint32_t utf16_length, const char* utf8_data) 98 REQUIRES(!Locks::intern_table_lock_) 99 REQUIRES_SHARED(Locks::mutator_lock_); 100 101 // Lookup a weak intern, returns null if not found. 102 ObjPtr<mirror::String> LookupWeak(Thread* self, ObjPtr<mirror::String> s) 103 REQUIRES(!Locks::intern_table_lock_) 104 REQUIRES_SHARED(Locks::mutator_lock_); 105 106 // Total number of interned strings. 107 size_t Size() const REQUIRES(!Locks::intern_table_lock_); 108 109 // Total number of weakly live interned strings. 110 size_t StrongSize() const REQUIRES(!Locks::intern_table_lock_); 111 112 // Total number of strongly live interned strings. 113 size_t WeakSize() const REQUIRES(!Locks::intern_table_lock_); 114 115 void VisitRoots(RootVisitor* visitor, VisitRootFlags flags) 116 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 117 118 void DumpForSigQuit(std::ostream& os) const REQUIRES(!Locks::intern_table_lock_); 119 120 void BroadcastForNewInterns(); 121 122 // Adds all of the resolved image strings from the image spaces into the intern table. The 123 // advantage of doing this is preventing expensive DexFile::FindStringId calls. Sets 124 // images_added_to_intern_table_ to true. 125 void AddImagesStringsToTable(const std::vector<gc::space::ImageSpace*>& image_spaces) 126 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 127 128 // Add a new intern table for inserting to, previous intern tables are still there but no 129 // longer inserted into and ideally unmodified. This is done to prevent dirty pages. 130 void AddNewTable() 131 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 132 133 // Read the intern table from memory. The elements aren't copied, the intern hash set data will 134 // point to somewhere within ptr. Only reads the strong interns. 135 size_t AddTableFromMemory(const uint8_t* ptr) REQUIRES(!Locks::intern_table_lock_) 136 REQUIRES_SHARED(Locks::mutator_lock_); 137 138 // Write the post zygote intern table to a pointer. Only writes the strong interns since it is 139 // expected that there is no weak interns since this is called from the image writer. 140 size_t WriteToMemory(uint8_t* ptr) REQUIRES_SHARED(Locks::mutator_lock_) 141 REQUIRES(!Locks::intern_table_lock_); 142 143 // Change the weak root state. May broadcast to waiters. 144 void ChangeWeakRootState(gc::WeakRootState new_state) 145 REQUIRES(!Locks::intern_table_lock_); 146 147 private: 148 // Modified UTF-8-encoded string treated as UTF16. 149 class Utf8String { 150 public: 151 Utf8String(uint32_t utf16_length, const char* utf8_data, int32_t hash) 152 : hash_(hash), utf16_length_(utf16_length), utf8_data_(utf8_data) { } 153 154 int32_t GetHash() const { return hash_; } 155 uint32_t GetUtf16Length() const { return utf16_length_; } 156 const char* GetUtf8Data() const { return utf8_data_; } 157 158 private: 159 int32_t hash_; 160 uint32_t utf16_length_; 161 const char* utf8_data_; 162 }; 163 164 class StringHashEquals { 165 public: 166 std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS; 167 bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const 168 NO_THREAD_SAFETY_ANALYSIS; 169 170 // Utf8String can be used for lookup. 171 std::size_t operator()(const Utf8String& key) const { 172 // A cast to prevent undesired sign extension. 173 return static_cast<uint32_t>(key.GetHash()); 174 } 175 176 bool operator()(const GcRoot<mirror::String>& a, const Utf8String& b) const 177 NO_THREAD_SAFETY_ANALYSIS; 178 }; 179 class GcRootEmptyFn { 180 public: 181 void MakeEmpty(GcRoot<mirror::String>& item) const { 182 item = GcRoot<mirror::String>(); 183 } 184 bool IsEmpty(const GcRoot<mirror::String>& item) const { 185 return item.IsNull(); 186 } 187 }; 188 189 // Table which holds pre zygote and post zygote interned strings. There is one instance for 190 // weak interns and strong interns. 191 class Table { 192 public: 193 Table(); 194 ObjPtr<mirror::String> Find(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 195 REQUIRES(Locks::intern_table_lock_); 196 ObjPtr<mirror::String> Find(const Utf8String& string) REQUIRES_SHARED(Locks::mutator_lock_) 197 REQUIRES(Locks::intern_table_lock_); 198 void Insert(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 199 REQUIRES(Locks::intern_table_lock_); 200 void Remove(ObjPtr<mirror::String> s) 201 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 202 void VisitRoots(RootVisitor* visitor) 203 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 204 void SweepWeaks(IsMarkedVisitor* visitor) 205 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 206 // Add a new intern table that will only be inserted into from now on. 207 void AddNewTable() REQUIRES(Locks::intern_table_lock_); 208 size_t Size() const REQUIRES(Locks::intern_table_lock_); 209 // Read and add an intern table from ptr. 210 // Tables read are inserted at the front of the table array. Only checks for conflicts in 211 // debug builds. Returns how many bytes were read. 212 size_t AddTableFromMemory(const uint8_t* ptr) 213 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 214 // Write the intern tables to ptr, if there are multiple tables they are combined into a single 215 // one. Returns how many bytes were written. 216 size_t WriteToMemory(uint8_t* ptr) 217 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 218 219 private: 220 typedef HashSet<GcRoot<mirror::String>, GcRootEmptyFn, StringHashEquals, StringHashEquals, 221 TrackingAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>> UnorderedSet; 222 223 void SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) 224 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 225 226 // We call AddNewTable when we create the zygote to reduce private dirty pages caused by 227 // modifying the zygote intern table. The back of table is modified when strings are interned. 228 std::vector<UnorderedSet> tables_; 229 230 friend class linker::OatWriter; // for boot image string table slot address lookup. 231 ART_FRIEND_TEST(InternTableTest, CrossHash); 232 }; 233 234 // Insert if non null, otherwise return null. Must be called holding the mutator lock. 235 // If holding_locks is true, then we may also hold other locks. If holding_locks is true, then we 236 // require GC is not running since it is not safe to wait while holding locks. 237 ObjPtr<mirror::String> Insert(ObjPtr<mirror::String> s, bool is_strong, bool holding_locks) 238 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 239 240 ObjPtr<mirror::String> LookupStrongLocked(ObjPtr<mirror::String> s) 241 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 242 ObjPtr<mirror::String> LookupWeakLocked(ObjPtr<mirror::String> s) 243 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 244 ObjPtr<mirror::String> InsertStrong(ObjPtr<mirror::String> s) 245 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 246 ObjPtr<mirror::String> InsertWeak(ObjPtr<mirror::String> s) 247 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 248 void RemoveStrong(ObjPtr<mirror::String> s) 249 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 250 void RemoveWeak(ObjPtr<mirror::String> s) 251 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 252 253 // Transaction rollback access. 254 ObjPtr<mirror::String> InsertStrongFromTransaction(ObjPtr<mirror::String> s) 255 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 256 ObjPtr<mirror::String> InsertWeakFromTransaction(ObjPtr<mirror::String> s) 257 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 258 void RemoveStrongFromTransaction(ObjPtr<mirror::String> s) 259 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 260 void RemoveWeakFromTransaction(ObjPtr<mirror::String> s) 261 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 262 263 size_t AddTableFromMemoryLocked(const uint8_t* ptr) 264 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 265 266 // Change the weak root state. May broadcast to waiters. 267 void ChangeWeakRootStateLocked(gc::WeakRootState new_state) 268 REQUIRES(Locks::intern_table_lock_); 269 270 // Wait until we can read weak roots. 271 void WaitUntilAccessible(Thread* self) 272 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 273 274 bool log_new_roots_ GUARDED_BY(Locks::intern_table_lock_); 275 ConditionVariable weak_intern_condition_ GUARDED_BY(Locks::intern_table_lock_); 276 // Since this contains (strong) roots, they need a read barrier to 277 // enable concurrent intern table (strong) root scan. Do not 278 // directly access the strings in it. Use functions that contain 279 // read barriers. 280 Table strong_interns_ GUARDED_BY(Locks::intern_table_lock_); 281 std::vector<GcRoot<mirror::String>> new_strong_intern_roots_ 282 GUARDED_BY(Locks::intern_table_lock_); 283 // Since this contains (weak) roots, they need a read barrier. Do 284 // not directly access the strings in it. Use functions that contain 285 // read barriers. 286 Table weak_interns_ GUARDED_BY(Locks::intern_table_lock_); 287 // Weak root state, used for concurrent system weak processing and more. 288 gc::WeakRootState weak_root_state_ GUARDED_BY(Locks::intern_table_lock_); 289 290 friend class linker::OatWriter; // for boot image string table slot address lookup. 291 friend class Transaction; 292 ART_FRIEND_TEST(InternTableTest, CrossHash); 293 DISALLOW_COPY_AND_ASSIGN(InternTable); 294 }; 295 296 } // namespace art 297 298 #endif // ART_RUNTIME_INTERN_TABLE_H_ 299
