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 StringHash { 76 public: 77 std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS; 78 79 // Utf8String can be used for lookup. operator()80 std::size_t operator()(const Utf8String& key) const { 81 // A cast to prevent undesired sign extension. 82 return static_cast<uint32_t>(key.GetHash()); 83 } 84 }; 85 86 class StringEquals { 87 public: 88 bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const 89 NO_THREAD_SAFETY_ANALYSIS; 90 91 // Utf8String can be used for lookup. 92 bool operator()(const GcRoot<mirror::String>& a, const Utf8String& b) const 93 NO_THREAD_SAFETY_ANALYSIS; 94 }; 95 96 class GcRootEmptyFn { 97 public: MakeEmpty(GcRoot<mirror::String> & item)98 void MakeEmpty(GcRoot<mirror::String>& item) const { 99 item = GcRoot<mirror::String>(); 100 } IsEmpty(const GcRoot<mirror::String> & item)101 bool IsEmpty(const GcRoot<mirror::String>& item) const { 102 return item.IsNull(); 103 } 104 }; 105 106 using UnorderedSet = HashSet<GcRoot<mirror::String>, 107 GcRootEmptyFn, 108 StringHash, 109 StringEquals, 110 TrackingAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>>; 111 112 InternTable(); 113 114 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 115 ObjPtr<mirror::String> InternStrong(int32_t utf16_length, const char* utf8_data) 116 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_); 117 118 // Only used by image writer. Special version that may not cause thread suspension since the GC 119 // cannot be running while we are doing image writing. Maybe be called while while holding a 120 // lock since there will not be thread suspension. 121 ObjPtr<mirror::String> InternStrongImageString(ObjPtr<mirror::String> s) 122 REQUIRES_SHARED(Locks::mutator_lock_); 123 124 // Only used by image writer. Promote all weak interns to strong interns. 125 void PromoteWeakToStrong() REQUIRES_SHARED(Locks::mutator_lock_); 126 127 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 128 ObjPtr<mirror::String> InternStrong(const char* utf8_data) REQUIRES_SHARED(Locks::mutator_lock_) 129 REQUIRES(!Roles::uninterruptible_); 130 131 // Interns a potentially new string in the 'strong' table. May cause thread suspension. 132 ObjPtr<mirror::String> InternStrong(ObjPtr<mirror::String> s) 133 REQUIRES_SHARED(Locks::mutator_lock_) 134 REQUIRES(!Roles::uninterruptible_); 135 136 // Interns a potentially new string in the 'weak' table. May cause thread suspension. 137 ObjPtr<mirror::String> InternWeak(const char* utf8_data) REQUIRES_SHARED(Locks::mutator_lock_) 138 REQUIRES(!Roles::uninterruptible_); 139 140 // Interns a potentially new string in the 'weak' table. May cause thread suspension. 141 ObjPtr<mirror::String> InternWeak(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 142 REQUIRES(!Roles::uninterruptible_); 143 144 void SweepInternTableWeaks(IsMarkedVisitor* visitor) REQUIRES_SHARED(Locks::mutator_lock_) 145 REQUIRES(!Locks::intern_table_lock_); 146 147 bool ContainsWeak(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 148 REQUIRES(!Locks::intern_table_lock_); 149 150 // Lookup a strong intern, returns null if not found. 151 ObjPtr<mirror::String> LookupStrong(Thread* self, ObjPtr<mirror::String> s) 152 REQUIRES(!Locks::intern_table_lock_) 153 REQUIRES_SHARED(Locks::mutator_lock_); 154 ObjPtr<mirror::String> LookupStrong(Thread* self, uint32_t utf16_length, const char* utf8_data) 155 REQUIRES(!Locks::intern_table_lock_) 156 REQUIRES_SHARED(Locks::mutator_lock_); 157 ObjPtr<mirror::String> LookupStrongLocked(ObjPtr<mirror::String> s) 158 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 159 160 // Lookup a weak intern, returns null if not found. 161 ObjPtr<mirror::String> LookupWeak(Thread* self, ObjPtr<mirror::String> s) 162 REQUIRES(!Locks::intern_table_lock_) 163 REQUIRES_SHARED(Locks::mutator_lock_); 164 ObjPtr<mirror::String> LookupWeakLocked(ObjPtr<mirror::String> s) 165 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 166 167 // Total number of interned strings. 168 size_t Size() const REQUIRES(!Locks::intern_table_lock_); 169 170 // Total number of weakly live interned strings. 171 size_t StrongSize() const REQUIRES(!Locks::intern_table_lock_); 172 173 // Total number of strongly live interned strings. 174 size_t WeakSize() const REQUIRES(!Locks::intern_table_lock_); 175 176 void VisitRoots(RootVisitor* visitor, VisitRootFlags flags) 177 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 178 179 // Visit all of the interns in the table. 180 template <typename Visitor> 181 void VisitInterns(const Visitor& visitor, 182 bool visit_boot_images, 183 bool visit_non_boot_images) 184 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 185 186 // Count the number of intern strings in the table. 187 size_t CountInterns(bool visit_boot_images, bool visit_non_boot_images) const 188 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 189 190 void DumpForSigQuit(std::ostream& os) const REQUIRES(!Locks::intern_table_lock_); 191 192 void BroadcastForNewInterns(); 193 194 // Add all of the strings in the image's intern table into this intern table. This is required so 195 // the intern table is correct. 196 // The visitor arg type is UnorderedSet 197 template <typename Visitor> 198 void AddImageStringsToTable(gc::space::ImageSpace* image_space, 199 const Visitor& visitor) 200 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_); 201 202 // Add a new intern table for inserting to, previous intern tables are still there but no 203 // longer inserted into and ideally unmodified. This is done to prevent dirty pages. 204 void AddNewTable() 205 REQUIRES_SHARED(Locks::mutator_lock_) 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 linker::ImageWriter; 240 friend class Table; 241 ART_FRIEND_TEST(InternTableTest, CrossHash); 242 }; 243 244 Table(); 245 ObjPtr<mirror::String> Find(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 246 REQUIRES(Locks::intern_table_lock_); 247 ObjPtr<mirror::String> Find(const Utf8String& string) REQUIRES_SHARED(Locks::mutator_lock_) 248 REQUIRES(Locks::intern_table_lock_); 249 void Insert(ObjPtr<mirror::String> s) REQUIRES_SHARED(Locks::mutator_lock_) 250 REQUIRES(Locks::intern_table_lock_); 251 void Remove(ObjPtr<mirror::String> s) 252 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 253 void VisitRoots(RootVisitor* visitor) 254 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 255 void SweepWeaks(IsMarkedVisitor* visitor) 256 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 257 // Add a new intern table that will only be inserted into from now on. 258 void AddNewTable() REQUIRES(Locks::intern_table_lock_); 259 size_t Size() const REQUIRES(Locks::intern_table_lock_); 260 // Read and add an intern table from ptr. 261 // Tables read are inserted at the front of the table array. Only checks for conflicts in 262 // debug builds. Returns how many bytes were read. 263 // NO_THREAD_SAFETY_ANALYSIS for the visitor that may require locks. 264 template <typename Visitor> 265 size_t AddTableFromMemory(const uint8_t* ptr, const Visitor& visitor, bool is_boot_image) 266 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 267 268 private: 269 void SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor) 270 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 271 272 // Add a table to the front of the tables vector. 273 void AddInternStrings(UnorderedSet&& intern_strings, bool is_boot_image) 274 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 275 276 // We call AddNewTable when we create the zygote to reduce private dirty pages caused by 277 // modifying the zygote intern table. The back of table is modified when strings are interned. 278 std::vector<InternalTable> tables_; 279 280 friend class InternTable; 281 friend class linker::ImageWriter; 282 ART_FRIEND_TEST(InternTableTest, CrossHash); 283 }; 284 285 // Insert if non null, otherwise return null. Must be called holding the mutator lock. 286 // If holding_locks is true, then we may also hold other locks. If holding_locks is true, then we 287 // require GC is not running since it is not safe to wait while holding locks. 288 ObjPtr<mirror::String> Insert(ObjPtr<mirror::String> s, bool is_strong, bool holding_locks) 289 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 290 291 // Add a table from memory to the strong interns. 292 template <typename Visitor> 293 size_t AddTableFromMemory(const uint8_t* ptr, const Visitor& visitor, bool is_boot_image) 294 REQUIRES(!Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 295 296 ObjPtr<mirror::String> InsertStrong(ObjPtr<mirror::String> s) 297 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 298 ObjPtr<mirror::String> InsertWeak(ObjPtr<mirror::String> s) 299 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 300 void RemoveStrong(ObjPtr<mirror::String> s) 301 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 302 void RemoveWeak(ObjPtr<mirror::String> s) 303 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 304 305 // Transaction rollback access. 306 ObjPtr<mirror::String> InsertStrongFromTransaction(ObjPtr<mirror::String> s) 307 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 308 ObjPtr<mirror::String> InsertWeakFromTransaction(ObjPtr<mirror::String> s) 309 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 310 void RemoveStrongFromTransaction(ObjPtr<mirror::String> s) 311 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 312 void RemoveWeakFromTransaction(ObjPtr<mirror::String> s) 313 REQUIRES_SHARED(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_); 314 315 // Change the weak root state. May broadcast to waiters. 316 void ChangeWeakRootStateLocked(gc::WeakRootState new_state) 317 REQUIRES(Locks::intern_table_lock_); 318 319 // Wait until we can read weak roots. 320 void WaitUntilAccessible(Thread* self) 321 REQUIRES(Locks::intern_table_lock_) REQUIRES_SHARED(Locks::mutator_lock_); 322 323 bool log_new_roots_ GUARDED_BY(Locks::intern_table_lock_); 324 ConditionVariable weak_intern_condition_ GUARDED_BY(Locks::intern_table_lock_); 325 // Since this contains (strong) roots, they need a read barrier to 326 // enable concurrent intern table (strong) root scan. Do not 327 // directly access the strings in it. Use functions that contain 328 // read barriers. 329 Table strong_interns_ GUARDED_BY(Locks::intern_table_lock_); 330 std::vector<GcRoot<mirror::String>> new_strong_intern_roots_ 331 GUARDED_BY(Locks::intern_table_lock_); 332 // Since this contains (weak) roots, they need a read barrier. Do 333 // not directly access the strings in it. Use functions that contain 334 // read barriers. 335 Table weak_interns_ GUARDED_BY(Locks::intern_table_lock_); 336 // Weak root state, used for concurrent system weak processing and more. 337 gc::WeakRootState weak_root_state_ GUARDED_BY(Locks::intern_table_lock_); 338 339 friend class gc::space::ImageSpace; 340 friend class linker::ImageWriter; 341 friend class Transaction; 342 ART_FRIEND_TEST(InternTableTest, CrossHash); 343 DISALLOW_COPY_AND_ASSIGN(InternTable); 344 }; 345 346 } // namespace art 347 348 #endif // ART_RUNTIME_INTERN_TABLE_H_ 349