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 "base/dchecked_vector.h" 21 #include "base/gc_visited_arena_pool.h" 22 #include "base/hash_set.h" 23 #include "base/macros.h" 24 #include "base/mutex.h" 25 #include "gc/weak_root_state.h" 26 #include "gc_root.h" 27 28 namespace art HIDDEN { 29 30 class IsMarkedVisitor; 31 32 namespace gc { 33 namespace space { 34 class ImageSpace; 35 } // namespace space 36 } // namespace gc 37 38 enum VisitRootFlags : uint8_t; 39 40 namespace linker { 41 class ImageWriter; 42 } // namespace linker 43 44 namespace mirror { 45 class String; 46 } // namespace mirror 47 class Transaction; 48 49 /** 50 * Used to intern strings. 51 * 52 * There are actually two tables: one that holds strong references to its strings, and one that 53 * holds weak references. The former is used for string literals, for which there is an effective 54 * reference from the constant pool. The latter is used for strings interned at runtime via 55 * String.intern. Some code (XML parsers being a prime example) relies on being able to intern 56 * arbitrarily many strings for the duration of a parse without permanently increasing the memory 57 * footprint. 58 */ 59 class InternTable { 60 public: 61 // Modified UTF-8-encoded string treated as UTF16. 62 class Utf8String { 63 public: Utf8String(uint32_t utf16_length,const char * utf8_data)64 Utf8String(uint32_t utf16_length, const char* utf8_data) 65 : utf16_length_(utf16_length), utf8_data_(utf8_data) { } 66 GetHash()67 uint32_t GetHash() const { return Hash(utf16_length_, utf8_data_); } GetUtf16Length()68 uint32_t GetUtf16Length() const { return utf16_length_; } GetUtf8Data()69 const char* GetUtf8Data() const { return utf8_data_; } 70 71 static uint32_t Hash(uint32_t utf16_length, const char* utf8_data); 72 73 private: 74 uint32_t utf16_length_; 75 const char* utf8_data_; 76 }; 77 78 class StringHash { 79 public: 80 // NO_THREAD_SAFETY_ANALYSIS: Used from unannotated `HashSet<>` functions. 81 size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS; 82 83 // Utf8String can be used for lookup. While we're passing the hash explicitly to all 84 // `HashSet<>` functions, they `DCHECK()` the supplied hash against the hash we provide here. operator()85 size_t operator()(const Utf8String& key) const { 86 static_assert(std::is_same_v<uint32_t, decltype(key.GetHash())>); 87 return key.GetHash(); 88 } 89 }; 90 91 class StringEquals { 92 public: 93 // NO_THREAD_SAFETY_ANALYSIS: Used from unannotated `HashSet<>` functions. 94 bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const 95 NO_THREAD_SAFETY_ANALYSIS; 96 97 // Utf8String can be used for lookup. 98 // NO_THREAD_SAFETY_ANALYSIS: Used from unannotated `HashSet<>` functions. 99 bool operator()(const GcRoot<mirror::String>& a, const Utf8String& b) const 100 NO_THREAD_SAFETY_ANALYSIS; 101 }; 102 103 class GcRootEmptyFn { 104 public: MakeEmpty(GcRoot<mirror::String> & item)105 void MakeEmpty(GcRoot<mirror::String>& item) const { 106 item = GcRoot<mirror::String>(); 107 } IsEmpty(const GcRoot<mirror::String> & item)108 bool IsEmpty(const GcRoot<mirror::String>& item) const { 109 return item.IsNull(); 110 } 111 }; 112 113 using UnorderedSet = 114 HashSet<GcRoot<mirror::String>, 115 GcRootEmptyFn, 116 StringHash, 117 StringEquals, 118 GcRootArenaAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>>; 119 120 EXPORT InternTable(); 121 122 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 123 EXPORT ObjPtr<mirror::String> InternStrong(uint32_t utf16_length, const char* utf8_data) 124 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_); 125 126 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 127 EXPORT ObjPtr<mirror::String> InternStrong(const char* utf8_data) 128 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_); 129 130 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 131 EXPORT ObjPtr<mirror::String> InternStrong(ObjPtr<mirror::String> s) 132 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_); 133 134 // Interns a potentially new string in the 'weak' table. May cause thread suspension. 135 ObjPtr<mirror::String> InternWeak(const char* utf8_data) REQUIRES_SHARED(Locks::mutator_lock_) 136 REQUIRES(!Roles::uninterruptible_); 137 138 // Interns a potentially new string in the 'weak' table. May cause thread suspension. 139 ObjPtr<mirror::String> InternWeak(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 140 REQUIRES(!Roles::uninterruptible_); 141 142 void SweepInternTableWeaks(IsMarkedVisitor* visitor) REQUIRES_SHARED(Locks::mutator_lock_) 143 REQUIRES(!Locks::intern_table_lock_); 144 145 // Lookup a strong intern, returns null if not found. 146 ObjPtr<mirror::String> LookupStrong(Thread* self, ObjPtr<mirror::String> s) 147 REQUIRES(!Locks::intern_table_lock_) 148 REQUIRES_SHARED(Locks::mutator_lock_); 149 ObjPtr<mirror::String> LookupStrong(Thread* self, uint32_t utf16_length, const char* utf8_data) 150 REQUIRES(!Locks::intern_table_lock_) 151 REQUIRES_SHARED(Locks::mutator_lock_); 152 ObjPtr<mirror::String> LookupStrongLocked(ObjPtr<mirror::String> s) 153 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 154 155 // Lookup a weak intern, returns null if not found. 156 ObjPtr<mirror::String> LookupWeak(Thread* self, ObjPtr<mirror::String> s) 157 REQUIRES(!Locks::intern_table_lock_) 158 REQUIRES_SHARED(Locks::mutator_lock_); 159 ObjPtr<mirror::String> LookupWeakLocked(ObjPtr<mirror::String> s) 160 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 161 162 // Total number of interned strings. 163 EXPORT size_t Size() const REQUIRES(!Locks::intern_table_lock_); 164 165 // Total number of weakly live interned strings. 166 size_t StrongSize() const REQUIRES(!Locks::intern_table_lock_); 167 168 // Total number of strongly live interned strings. 169 size_t WeakSize() const REQUIRES(!Locks::intern_table_lock_); 170 171 EXPORT void VisitRoots(RootVisitor* visitor, VisitRootFlags flags) 172 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 173 174 // Visit all of the interns in the table. 175 template <typename Visitor> 176 void VisitInterns(const Visitor& visitor, 177 bool visit_boot_images, 178 bool visit_non_boot_images) 179 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 180 181 // Count the number of intern strings in the table. 182 size_t CountInterns(bool visit_boot_images, bool visit_non_boot_images) const 183 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 184 185 void DumpForSigQuit(std::ostream& os) const REQUIRES(!Locks::intern_table_lock_); 186 187 void BroadcastForNewInterns(); 188 189 // Add all of the strings in the image's intern table into this intern table. This is required so 190 // the intern table is correct. 191 // The visitor arg type is UnorderedSet 192 template <typename Visitor> 193 void AddImageStringsToTable(gc::space::ImageSpace* image_space, 194 const Visitor& visitor) 195 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 196 197 // Add a new intern table for inserting to, previous intern tables are still there but no 198 // longer inserted into and ideally unmodified. This is done to prevent dirty pages. 199 void AddNewTable() 200 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 201 202 // Change the weak root state. May broadcast to waiters. 203 void ChangeWeakRootState(gc::WeakRootState new_state) 204 REQUIRES(!Locks::intern_table_lock_); 205 206 private: 207 // Table which holds pre zygote and post zygote interned strings. There is one instance for 208 // weak interns and strong interns. 209 class Table { 210 public: 211 class InternalTable { 212 public: 213 InternalTable() = default; InternalTable(UnorderedSet && set,bool is_boot_image)214 InternalTable(UnorderedSet&& set, bool is_boot_image) 215 : set_(std::move(set)), is_boot_image_(is_boot_image) {} 216 Empty()217 bool Empty() const { 218 return set_.empty(); 219 } 220 Size()221 size_t Size() const { 222 return set_.size(); 223 } 224 IsBootImage()225 bool IsBootImage() const { 226 return is_boot_image_; 227 } 228 229 private: 230 UnorderedSet set_; 231 bool is_boot_image_ = false; 232 233 friend class InternTable; 234 friend class linker::ImageWriter; 235 friend class Table; 236 ART_FRIEND_TEST(InternTableTest, CrossHash); 237 }; 238 239 Table(); 240 ObjPtr<mirror::String> Find(ObjPtr<mirror::String> s, 241 uint32_t hash, 242 size_t num_searched_frozen_tables = 0u) 243 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 244 ObjPtr<mirror::String> Find(const Utf8String& string, uint32_t hash) 245 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 246 void Insert(ObjPtr<mirror::String> s, uint32_t hash) 247 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 248 void Remove(ObjPtr<mirror::String> s, uint32_t hash) 249 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 250 void VisitRoots(RootVisitor* visitor) 251 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 252 void SweepWeaks(IsMarkedVisitor* visitor) 253 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 254 // Add a new intern table that will only be inserted into from now on. 255 void AddNewTable() REQUIRES(Locks::intern_table_lock_); 256 size_t Size() const REQUIRES(Locks::intern_table_lock_); 257 // Read and add an intern table from ptr. 258 // Tables read are inserted at the front of the table array. Only checks for conflicts in 259 // debug builds. Returns how many bytes were read. 260 // NO_THREAD_SAFETY_ANALYSIS for the visitor that may require locks. 261 template <typename Visitor> 262 size_t AddTableFromMemory(const uint8_t* ptr, const Visitor& visitor, bool is_boot_image) 263 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 264 265 private: 266 void SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) 267 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 268 269 // Add a table to the front of the tables vector. 270 void AddInternStrings(UnorderedSet&& intern_strings, bool is_boot_image) 271 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 272 273 // We call AddNewTable when we create the zygote to reduce private dirty pages caused by 274 // modifying the zygote intern table. The back of table is modified when strings are interned. 275 dchecked_vector<InternalTable> tables_; 276 277 friend class InternTable; 278 friend class linker::ImageWriter; 279 ART_FRIEND_TEST(InternTableTest, CrossHash); 280 }; 281 282 // Insert if non null, otherwise return null. Must be called holding the mutator lock. 283 ObjPtr<mirror::String> Insert(ObjPtr<mirror::String> s, 284 uint32_t hash, 285 bool is_strong, 286 size_t num_searched_strong_frozen_tables = 0u) 287 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 288 289 // Add a table from memory to the strong interns. 290 template <typename Visitor> 291 size_t AddTableFromMemory(const uint8_t* ptr, const Visitor& visitor, bool is_boot_image) 292 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 293 294 // Note: Transaction rollback calls these helper functions directly. 295 EXPORT ObjPtr<mirror::String> InsertStrong(ObjPtr<mirror::String> s, uint32_t hash) 296 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 297 ObjPtr<mirror::String> InsertWeak(ObjPtr<mirror::String> s, uint32_t hash) 298 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 299 void RemoveStrong(ObjPtr<mirror::String> s, uint32_t hash) 300 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 301 void RemoveWeak(ObjPtr<mirror::String> s, uint32_t hash) 302 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 303 304 // Change the weak root state. May broadcast to waiters. 305 void ChangeWeakRootStateLocked(gc::WeakRootState new_state) 306 REQUIRES(Locks::intern_table_lock_); 307 308 // Wait until we can read weak roots. 309 void WaitUntilAccessible(Thread* self) 310 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 311 312 bool log_new_roots_ GUARDED_BY(Locks::intern_table_lock_); 313 ConditionVariable weak_intern_condition_ GUARDED_BY(Locks::intern_table_lock_); 314 // Since this contains (strong) roots, they need a read barrier to 315 // enable concurrent intern table (strong) root scan. Do not 316 // directly access the strings in it. Use functions that contain 317 // read barriers. 318 Table strong_interns_ GUARDED_BY(Locks::intern_table_lock_); 319 dchecked_vector<GcRoot<mirror::String>> new_strong_intern_roots_ 320 GUARDED_BY(Locks::intern_table_lock_); 321 // Since this contains (weak) roots, they need a read barrier. Do 322 // not directly access the strings in it. Use functions that contain 323 // read barriers. 324 Table weak_interns_ GUARDED_BY(Locks::intern_table_lock_); 325 // Weak root state, used for concurrent system weak processing and more. 326 gc::WeakRootState weak_root_state_ GUARDED_BY(Locks::intern_table_lock_); 327 328 friend class gc::space::ImageSpace; 329 friend class linker::ImageWriter; 330 friend class Transaction; 331 ART_FRIEND_TEST(InternTableTest, CrossHash); 332 DISALLOW_COPY_AND_ASSIGN(InternTable); 333 }; 334 335 } // namespace art 336 337 #endif // ART_RUNTIME_INTERN_TABLE_H_ 338