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/hash_set.h" 22 #include "base/mutex.h" 23 #include "gc/weak_root_state.h" 24 #include "gc_root.h" 25 26 namespace art { 27 28 class IsMarkedVisitor; 29 30 namespace gc { 31 namespace space { 32 class ImageSpace; 33 } // namespace space 34 } // namespace gc 35 36 enum VisitRootFlags : uint8_t; 37 38 namespace linker { 39 class ImageWriter; 40 } // namespace linker 41 42 namespace mirror { 43 class String; 44 } // namespace mirror 45 class Transaction; 46 47 /** 48 * Used to intern strings. 49 * 50 * There are actually two tables: one that holds strong references to its strings, and one that 51 * holds weak references. The former is used for string literals, for which there is an effective 52 * reference from the constant pool. The latter is used for strings interned at runtime via 53 * String.intern. Some code (XML parsers being a prime example) relies on being able to intern 54 * arbitrarily many strings for the duration of a parse without permanently increasing the memory 55 * footprint. 56 */ 57 class InternTable { 58 public: 59 // Modified UTF-8-encoded string treated as UTF16. 60 class Utf8String { 61 public: Utf8String(uint32_t utf16_length,const char * utf8_data,int32_t hash)62 Utf8String(uint32_t utf16_length, const char* utf8_data, int32_t hash) 63 : hash_(hash), utf16_length_(utf16_length), utf8_data_(utf8_data) { } 64 GetHash()65 int32_t GetHash() const { return hash_; } GetUtf16Length()66 uint32_t GetUtf16Length() const { return utf16_length_; } GetUtf8Data()67 const char* GetUtf8Data() const { return utf8_data_; } 68 69 private: 70 int32_t hash_; 71 uint32_t utf16_length_; 72 const char* utf8_data_; 73 }; 74 75 class StringHashEquals { 76 public: 77 std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS; 78 bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const 79 NO_THREAD_SAFETY_ANALYSIS; 80 81 // Utf8String can be used for lookup. operator()82 std::size_t operator()(const Utf8String& key) const { 83 // A cast to prevent undesired sign extension. 84 return static_cast<uint32_t>(key.GetHash()); 85 } 86 87 bool operator()(const GcRoot<mirror::String>& a, const Utf8String& b) const 88 NO_THREAD_SAFETY_ANALYSIS; 89 }; 90 91 class GcRootEmptyFn { 92 public: MakeEmpty(GcRoot<mirror::String> & item)93 void MakeEmpty(GcRoot<mirror::String>& item) const { 94 item = GcRoot<mirror::String>(); 95 } IsEmpty(const GcRoot<mirror::String> & item)96 bool IsEmpty(const GcRoot<mirror::String>& item) const { 97 return item.IsNull(); 98 } 99 }; 100 101 using UnorderedSet = HashSet<GcRoot<mirror::String>, 102 GcRootEmptyFn, 103 StringHashEquals, 104 StringHashEquals, 105 TrackingAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>>; 106 107 InternTable(); 108 109 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 110 ObjPtr<mirror::String> InternStrong(int32_t utf16_length, const char* utf8_data) 111 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_); 112 113 // Only used by image writer. Special version that may not cause thread suspension since the GC 114 // cannot be running while we are doing image writing. Maybe be called while while holding a 115 // lock since there will not be thread suspension. 116 ObjPtr<mirror::String> InternStrongImageString(ObjPtr<mirror::String> s) 117 REQUIRES_SHARED(Locks::mutator_lock_); 118 119 // Only used by image writer. Promote all weak interns to strong interns. 120 void PromoteWeakToStrong() REQUIRES_SHARED(Locks::mutator_lock_); 121 122 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 123 ObjPtr<mirror::String> InternStrong(const char* utf8_data) REQUIRES_SHARED(Locks::mutator_lock_) 124 REQUIRES(!Roles::uninterruptible_); 125 126 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 127 ObjPtr<mirror::String> InternStrong(ObjPtr<mirror::String> s) 128 REQUIRES_SHARED(Locks::mutator_lock_) 129 REQUIRES(!Roles::uninterruptible_); 130 131 // Interns a potentially new string in the 'weak' table. May cause thread suspension. 132 ObjPtr<mirror::String> InternWeak(const char* utf8_data) REQUIRES_SHARED(Locks::mutator_lock_) 133 REQUIRES(!Roles::uninterruptible_); 134 135 // Interns a potentially new string in the 'weak' table. May cause thread suspension. 136 ObjPtr<mirror::String> InternWeak(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 137 REQUIRES(!Roles::uninterruptible_); 138 139 void SweepInternTableWeaks(IsMarkedVisitor* visitor) REQUIRES_SHARED(Locks::mutator_lock_) 140 REQUIRES(!Locks::intern_table_lock_); 141 142 bool ContainsWeak(ObjPtr<mirror::String> s) 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 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 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 // Write the post zygote intern table to a pointer. Only writes the strong interns since it is 203 // expected that there is no weak interns since this is called from the image writer. 204 size_t WriteToMemory(uint8_t* ptr) REQUIRES_SHARED(Locks::mutator_lock_) 205 REQUIRES(!Locks::intern_table_lock_); 206 207 // Change the weak root state. May broadcast to waiters. 208 void ChangeWeakRootState(gc::WeakRootState new_state) 209 REQUIRES(!Locks::intern_table_lock_); 210 211 private: 212 // Table which holds pre zygote and post zygote interned strings. There is one instance for 213 // weak interns and strong interns. 214 class Table { 215 public: 216 class InternalTable { 217 public: 218 InternalTable() = default; InternalTable(UnorderedSet && set,bool is_boot_image)219 InternalTable(UnorderedSet&& set, bool is_boot_image) 220 : set_(std::move(set)), is_boot_image_(is_boot_image) {} 221 Empty()222 bool Empty() const { 223 return set_.empty(); 224 } 225 Size()226 size_t Size() const { 227 return set_.size(); 228 } 229 IsBootImage()230 bool IsBootImage() const { 231 return is_boot_image_; 232 } 233 234 private: 235 UnorderedSet set_; 236 bool is_boot_image_ = false; 237 238 friend class InternTable; 239 friend class Table; 240 ART_FRIEND_TEST(InternTableTest, CrossHash); 241 }; 242 243 Table(); 244 ObjPtr<mirror::String> Find(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 245 REQUIRES(Locks::intern_table_lock_); 246 ObjPtr<mirror::String> Find(const Utf8String& string) REQUIRES_SHARED(Locks::mutator_lock_) 247 REQUIRES(Locks::intern_table_lock_); 248 void Insert(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 249 REQUIRES(Locks::intern_table_lock_); 250 void Remove(ObjPtr<mirror::String> s) 251 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 252 void VisitRoots(RootVisitor* visitor) 253 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 254 void SweepWeaks(IsMarkedVisitor* visitor) 255 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 256 // Add a new intern table that will only be inserted into from now on. 257 void AddNewTable() REQUIRES(Locks::intern_table_lock_); 258 size_t Size() const REQUIRES(Locks::intern_table_lock_); 259 // Read and add an intern table from ptr. 260 // Tables read are inserted at the front of the table array. Only checks for conflicts in 261 // debug builds. Returns how many bytes were read. 262 // NO_THREAD_SAFETY_ANALYSIS for the visitor that may require locks. 263 template <typename Visitor> 264 size_t AddTableFromMemory(const uint8_t* ptr, const Visitor& visitor, bool is_boot_image) 265 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 266 // Write the intern tables to ptr, if there are multiple tables they are combined into a single 267 // one. Returns how many bytes were written. 268 size_t WriteToMemory(uint8_t* ptr) 269 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 270 271 private: 272 void SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) 273 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 274 275 // Add a table to the front of the tables vector. 276 void AddInternStrings(UnorderedSet&& intern_strings, bool is_boot_image) 277 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 278 279 // We call AddNewTable when we create the zygote to reduce private dirty pages caused by 280 // modifying the zygote intern table. The back of table is modified when strings are interned. 281 std::vector<InternalTable> tables_; 282 283 friend class InternTable; 284 friend class linker::ImageWriter; 285 ART_FRIEND_TEST(InternTableTest, CrossHash); 286 }; 287 288 // Insert if non null, otherwise return null. Must be called holding the mutator lock. 289 // If holding_locks is true, then we may also hold other locks. If holding_locks is true, then we 290 // require GC is not running since it is not safe to wait while holding locks. 291 ObjPtr<mirror::String> Insert(ObjPtr<mirror::String> s, bool is_strong, bool holding_locks) 292 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 293 294 // Add a table from memory to the strong interns. 295 template <typename Visitor> 296 size_t AddTableFromMemory(const uint8_t* ptr, const Visitor& visitor, bool is_boot_image) 297 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 298 299 ObjPtr<mirror::String> InsertStrong(ObjPtr<mirror::String> s) 300 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 301 ObjPtr<mirror::String> InsertWeak(ObjPtr<mirror::String> s) 302 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 303 void RemoveStrong(ObjPtr<mirror::String> s) 304 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 305 void RemoveWeak(ObjPtr<mirror::String> s) 306 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 307 308 // Transaction rollback access. 309 ObjPtr<mirror::String> InsertStrongFromTransaction(ObjPtr<mirror::String> s) 310 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 311 ObjPtr<mirror::String> InsertWeakFromTransaction(ObjPtr<mirror::String> s) 312 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 313 void RemoveStrongFromTransaction(ObjPtr<mirror::String> s) 314 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 315 void RemoveWeakFromTransaction(ObjPtr<mirror::String> s) 316 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 317 318 // Change the weak root state. May broadcast to waiters. 319 void ChangeWeakRootStateLocked(gc::WeakRootState new_state) 320 REQUIRES(Locks::intern_table_lock_); 321 322 // Wait until we can read weak roots. 323 void WaitUntilAccessible(Thread* self) 324 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 325 326 bool log_new_roots_ GUARDED_BY(Locks::intern_table_lock_); 327 ConditionVariable weak_intern_condition_ GUARDED_BY(Locks::intern_table_lock_); 328 // Since this contains (strong) roots, they need a read barrier to 329 // enable concurrent intern table (strong) root scan. Do not 330 // directly access the strings in it. Use functions that contain 331 // read barriers. 332 Table strong_interns_ GUARDED_BY(Locks::intern_table_lock_); 333 std::vector<GcRoot<mirror::String>> new_strong_intern_roots_ 334 GUARDED_BY(Locks::intern_table_lock_); 335 // Since this contains (weak) roots, they need a read barrier. Do 336 // not directly access the strings in it. Use functions that contain 337 // read barriers. 338 Table weak_interns_ GUARDED_BY(Locks::intern_table_lock_); 339 // Weak root state, used for concurrent system weak processing and more. 340 gc::WeakRootState weak_root_state_ GUARDED_BY(Locks::intern_table_lock_); 341 342 friend class gc::space::ImageSpace; 343 friend class linker::ImageWriter; 344 friend class Transaction; 345 ART_FRIEND_TEST(InternTableTest, CrossHash); 346 DISALLOW_COPY_AND_ASSIGN(InternTable); 347 }; 348 349 } // namespace art 350 351 #endif // ART_RUNTIME_INTERN_TABLE_H_ 352