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