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