blob: 24c5af938c76d69106b7a3736e8a99671eb734d8 [file] [log] [blame]
Elliott Hughes2faa5f12012-01-30 14:42:07 -08001/*
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 */
Brian Carlstrom7e93b502011-08-04 14:16:22 -070016
Brian Carlstromfc0e3212013-07-17 14:40:12 -070017#ifndef ART_RUNTIME_INTERN_TABLE_H_
18#define ART_RUNTIME_INTERN_TABLE_H_
Brian Carlstrom7e93b502011-08-04 14:16:22 -070019
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -070020#include <unordered_set>
Brian Carlstrom7e93b502011-08-04 14:16:22 -070021
Mathieu Chartier14c3bf92015-07-13 14:35:43 -070022#include "atomic.h"
Mathieu Chartierbad02672014-08-25 13:08:22 -070023#include "base/allocator.h"
Mathieu Chartierc2e20622014-11-03 11:41:47 -080024#include "base/hash_set.h"
Ian Rogers719d1a32014-03-06 12:13:39 -080025#include "base/mutex.h"
Hiroshi Yamauchi94f7b492014-07-22 18:08:23 -070026#include "gc_root.h"
Mathieu Chartier14c3bf92015-07-13 14:35:43 -070027#include "gc/weak_root_state.h"
Ian Rogers719d1a32014-03-06 12:13:39 -080028#include "object_callbacks.h"
29
Brian Carlstrom7e93b502011-08-04 14:16:22 -070030namespace art {
Mathieu Chartier893263b2014-03-04 11:07:42 -080031
Mathieu Chartiereb175f72014-10-31 11:49:27 -070032namespace gc {
33namespace space {
34class ImageSpace;
35} // namespace space
36} // namespace gc
37
Mathieu Chartier893263b2014-03-04 11:07:42 -080038enum VisitRootFlags : uint8_t;
39
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080040namespace mirror {
41class String;
42} // namespace mirror
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +010043class Transaction;
Brian Carlstrom7e93b502011-08-04 14:16:22 -070044
Elliott Hughescf4c6c42011-09-01 15:16:42 -070045/**
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 */
Brian Carlstrom7e93b502011-08-04 14:16:22 -070055class InternTable {
56 public:
57 InternTable();
Brian Carlstroma663ea52011-08-19 23:33:41 -070058
Mathieu Chartier14c3bf92015-07-13 14:35:43 -070059 // Interns a potentially new string in the 'strong' table. May cause thread suspension.
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080060 mirror::String* InternStrong(int32_t utf16_length, const char* utf8_data)
Mathieu Chartiered8990a2015-07-23 14:11:16 -070061 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!Roles::uninterruptible_);
Brian Carlstromc74255f2011-09-11 22:47:39 -070062
Mathieu Chartiered8990a2015-07-23 14:11:16 -070063 // Only used by image writer. Special version that may not cause thread suspension since the GC
Mathieu Chartier90ef3db2015-08-04 15:19:41 -070064 // can not 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_);
Mathieu Chartier14c3bf92015-07-13 14:35:43 -070068
69 // Interns a potentially new string in the 'strong' table. May cause thread suspension.
Mathieu Chartiered8990a2015-07-23 14:11:16 -070070 mirror::String* InternStrong(const char* utf8_data) SHARED_REQUIRES(Locks::mutator_lock_)
71 REQUIRES(!Roles::uninterruptible_);
Brian Carlstromc74255f2011-09-11 22:47:39 -070072
Mathieu Chartier14c3bf92015-07-13 14:35:43 -070073 // Interns a potentially new string in the 'strong' table. May cause thread suspension.
Mathieu Chartiered8990a2015-07-23 14:11:16 -070074 mirror::String* InternStrong(mirror::String* s) SHARED_REQUIRES(Locks::mutator_lock_)
75 REQUIRES(!Roles::uninterruptible_);
Brian Carlstroma663ea52011-08-19 23:33:41 -070076
Mathieu Chartier14c3bf92015-07-13 14:35:43 -070077 // Interns a potentially new string in the 'weak' table. May cause thread suspension.
Mathieu Chartiered8990a2015-07-23 14:11:16 -070078 mirror::String* InternWeak(mirror::String* s) SHARED_REQUIRES(Locks::mutator_lock_)
79 REQUIRES(!Roles::uninterruptible_);
Elliott Hughescf4c6c42011-09-01 15:16:42 -070080
Mathieu Chartier90443472015-07-16 20:32:27 -070081 void SweepInternTableWeaks(IsMarkedVisitor* visitor) SHARED_REQUIRES(Locks::mutator_lock_)
82 REQUIRES(!Locks::intern_table_lock_);
Elliott Hughescf4c6c42011-09-01 15:16:42 -070083
Mathieu Chartiered8990a2015-07-23 14:11:16 -070084 bool ContainsWeak(mirror::String* s) SHARED_REQUIRES(Locks::mutator_lock_)
85 REQUIRES(!Locks::intern_table_lock_);
Brian Carlstroma663ea52011-08-19 23:33:41 -070086
Mathieu Chartiereb175f72014-10-31 11:49:27 -070087 // Total number of interned strings.
Mathieu Chartier90443472015-07-16 20:32:27 -070088 size_t Size() const REQUIRES(!Locks::intern_table_lock_);
Mathieu Chartiereb175f72014-10-31 11:49:27 -070089 // Total number of weakly live interned strings.
Mathieu Chartier90443472015-07-16 20:32:27 -070090 size_t StrongSize() const REQUIRES(!Locks::intern_table_lock_);
Mathieu Chartiereb175f72014-10-31 11:49:27 -070091 // Total number of strongly live interned strings.
Mathieu Chartier90443472015-07-16 20:32:27 -070092 size_t WeakSize() const REQUIRES(!Locks::intern_table_lock_);
Elliott Hughescf4c6c42011-09-01 15:16:42 -070093
Mathieu Chartierbb87e0f2015-04-03 11:21:55 -070094 void VisitRoots(RootVisitor* visitor, VisitRootFlags flags)
Mathieu Chartiered8990a2015-07-23 14:11:16 -070095 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_);
Brian Carlstrom7e93b502011-08-04 14:16:22 -070096
Mathieu Chartiered8990a2015-07-23 14:11:16 -070097 void DumpForSigQuit(std::ostream& os) const REQUIRES(!Locks::intern_table_lock_);
Elliott Hughescac6cc72011-11-03 20:31:21 -070098
Mathieu Chartier90443472015-07-16 20:32:27 -070099 void BroadcastForNewInterns() SHARED_REQUIRES(Locks::mutator_lock_);
Mathieu Chartierc11d9b82013-09-19 10:01:59 -0700100
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700101 // Adds all of the resolved image strings from the image space into the intern table. The
102 // advantage of doing this is preventing expensive DexFile::FindStringId calls.
103 void AddImageStringsToTable(gc::space::ImageSpace* image_space)
Mathieu Chartier90443472015-07-16 20:32:27 -0700104 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_);
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700105
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700106 // Copy the post zygote tables to pre zygote to save memory by preventing dirty pages.
107 void SwapPostZygoteWithPreZygote()
Mathieu Chartier90443472015-07-16 20:32:27 -0700108 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_);
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700109
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700110 // Add an intern table which was serialized to the image.
111 void AddImageInternTable(gc::space::ImageSpace* image_space)
Mathieu Chartier90443472015-07-16 20:32:27 -0700112 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(!Locks::intern_table_lock_);
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700113
114 // Read the intern table from memory. The elements aren't copied, the intern hash set data will
115 // point to somewhere within ptr. Only reads the strong interns.
Mathieu Chartier90443472015-07-16 20:32:27 -0700116 size_t ReadFromMemory(const uint8_t* ptr) REQUIRES(!Locks::intern_table_lock_)
117 SHARED_REQUIRES(Locks::mutator_lock_);
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700118
119 // Write the post zygote intern table to a pointer. Only writes the strong interns since it is
120 // expected that there is no weak interns since this is called from the image writer.
Mathieu Chartier90443472015-07-16 20:32:27 -0700121 size_t WriteToMemory(uint8_t* ptr) SHARED_REQUIRES(Locks::mutator_lock_)
122 REQUIRES(!Locks::intern_table_lock_);
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700123
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700124 // Change the weak root state. May broadcast to waiters.
125 void ChangeWeakRootState(gc::WeakRootState new_state)
Mathieu Chartier90443472015-07-16 20:32:27 -0700126 REQUIRES(!Locks::intern_table_lock_);
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700127
Brian Carlstrom7e93b502011-08-04 14:16:22 -0700128 private:
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700129 class StringHashEquals {
130 public:
Mathieu Chartierc2e20622014-11-03 11:41:47 -0800131 std::size_t operator()(const GcRoot<mirror::String>& root) const NO_THREAD_SAFETY_ANALYSIS;
132 bool operator()(const GcRoot<mirror::String>& a, const GcRoot<mirror::String>& b) const
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700133 NO_THREAD_SAFETY_ANALYSIS;
134 };
Mathieu Chartierc2e20622014-11-03 11:41:47 -0800135 class GcRootEmptyFn {
136 public:
137 void MakeEmpty(GcRoot<mirror::String>& item) const {
138 item = GcRoot<mirror::String>();
139 }
140 bool IsEmpty(const GcRoot<mirror::String>& item) const {
141 return item.IsNull();
142 }
143 };
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700144
145 // Table which holds pre zygote and post zygote interned strings. There is one instance for
146 // weak interns and strong interns.
147 class Table {
148 public:
Mathieu Chartier90443472015-07-16 20:32:27 -0700149 mirror::String* Find(mirror::String* s) SHARED_REQUIRES(Locks::mutator_lock_)
150 REQUIRES(Locks::intern_table_lock_);
151 void Insert(mirror::String* s) SHARED_REQUIRES(Locks::mutator_lock_)
152 REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700153 void Remove(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700154 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartierbb87e0f2015-04-03 11:21:55 -0700155 void VisitRoots(RootVisitor* visitor)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700156 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartier97509952015-07-13 14:35:43 -0700157 void SweepWeaks(IsMarkedVisitor* visitor)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700158 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartier90443472015-07-16 20:32:27 -0700159 void SwapPostZygoteWithPreZygote() REQUIRES(Locks::intern_table_lock_);
160 size_t Size() const REQUIRES(Locks::intern_table_lock_);
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700161 // Read pre zygote table is called from ReadFromMemory which happens during runtime creation
162 // when we load the image intern table. Returns how many bytes were read.
163 size_t ReadIntoPreZygoteTable(const uint8_t* ptr)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700164 REQUIRES(Locks::intern_table_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700165 // The image writer calls WritePostZygoteTable through WriteToMemory, it writes the interns in
166 // the post zygote table. Returns how many bytes were written.
167 size_t WriteFromPostZygoteTable(uint8_t* ptr)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700168 REQUIRES(Locks::intern_table_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700169
170 private:
Mathieu Chartierc2e20622014-11-03 11:41:47 -0800171 typedef HashSet<GcRoot<mirror::String>, GcRootEmptyFn, StringHashEquals, StringHashEquals,
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700172 TrackingAllocator<GcRoot<mirror::String>, kAllocatorTagInternTable>> UnorderedSet;
173
Mathieu Chartier97509952015-07-13 14:35:43 -0700174 void SweepWeaks(UnorderedSet* set, IsMarkedVisitor* visitor)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700175 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700176
177 // We call SwapPostZygoteWithPreZygote when we create the zygote to reduce private dirty pages
178 // caused by modifying the zygote intern table hash table. The pre zygote table are the
179 // interned strings which were interned before we created the zygote space. Post zygote is self
180 // explanatory.
181 UnorderedSet pre_zygote_table_;
182 UnorderedSet post_zygote_table_;
183 };
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700184
Mathieu Chartier90ef3db2015-08-04 15:19:41 -0700185 // Insert if non null, otherwise return null. Must be called holding the mutator lock.
186 // If holding_locks is true, then we may also hold other locks. If holding_locks is true, then we
187 // require GC is not running since it is not safe to wait while holding locks.
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700188 mirror::String* Insert(mirror::String* s, bool is_strong, bool holding_locks)
Mathieu Chartier90443472015-07-16 20:32:27 -0700189 REQUIRES(!Locks::intern_table_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700190
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700191 mirror::String* LookupStrong(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700192 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700193 mirror::String* LookupWeak(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700194 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700195 mirror::String* InsertStrong(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700196 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700197 mirror::String* InsertWeak(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700198 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700199 void RemoveStrong(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700200 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700201 void RemoveWeak(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700202 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Elliott Hughescf4c6c42011-09-01 15:16:42 -0700203
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100204 // Transaction rollback access.
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700205 mirror::String* LookupStringFromImage(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700206 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700207 mirror::String* InsertStrongFromTransaction(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700208 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700209 mirror::String* InsertWeakFromTransaction(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700210 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700211 void RemoveStrongFromTransaction(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700212 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700213 void RemoveWeakFromTransaction(mirror::String* s)
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700214 SHARED_REQUIRES(Locks::mutator_lock_) REQUIRES(Locks::intern_table_lock_);
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100215
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700216 size_t ReadFromMemoryLocked(const uint8_t* ptr)
Mathieu Chartier90443472015-07-16 20:32:27 -0700217 REQUIRES(Locks::intern_table_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
Mathieu Chartierd39645e2015-06-09 17:50:29 -0700218
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700219 // Change the weak root state. May broadcast to waiters.
220 void ChangeWeakRootStateLocked(gc::WeakRootState new_state)
Mathieu Chartier90443472015-07-16 20:32:27 -0700221 REQUIRES(Locks::intern_table_lock_);
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700222
223 // Wait until we can read weak roots.
Mathieu Chartier90443472015-07-16 20:32:27 -0700224 void WaitUntilAccessible(Thread* self)
225 REQUIRES(Locks::intern_table_lock_) SHARED_REQUIRES(Locks::mutator_lock_);
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700226
Mathieu Chartiereb175f72014-10-31 11:49:27 -0700227 bool image_added_to_intern_table_ GUARDED_BY(Locks::intern_table_lock_);
Mathieu Chartier893263b2014-03-04 11:07:42 -0800228 bool log_new_roots_ GUARDED_BY(Locks::intern_table_lock_);
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700229 ConditionVariable weak_intern_condition_ GUARDED_BY(Locks::intern_table_lock_);
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -0700230 // Since this contains (strong) roots, they need a read barrier to
231 // enable concurrent intern table (strong) root scan. Do not
232 // directly access the strings in it. Use functions that contain
233 // read barriers.
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100234 Table strong_interns_ GUARDED_BY(Locks::intern_table_lock_);
Mathieu Chartiercdfd39f2014-08-29 18:16:58 -0700235 std::vector<GcRoot<mirror::String>> new_strong_intern_roots_
Mathieu Chartier893263b2014-03-04 11:07:42 -0800236 GUARDED_BY(Locks::intern_table_lock_);
Hiroshi Yamauchia91a4bc2014-06-13 16:44:55 -0700237 // Since this contains (weak) roots, they need a read barrier. Do
238 // not directly access the strings in it. Use functions that contain
239 // read barriers.
Sebastien Hertzd2fe10a2014-01-15 10:20:56 +0100240 Table weak_interns_ GUARDED_BY(Locks::intern_table_lock_);
Mathieu Chartier14c3bf92015-07-13 14:35:43 -0700241 // Weak root state, used for concurrent system weak processing and more.
242 gc::WeakRootState weak_root_state_ GUARDED_BY(Locks::intern_table_lock_);
Mathieu Chartiered8990a2015-07-23 14:11:16 -0700243
244 friend class Transaction;
245 DISALLOW_COPY_AND_ASSIGN(InternTable);
Brian Carlstrom7e93b502011-08-04 14:16:22 -0700246};
247
248} // namespace art
249
Brian Carlstromfc0e3212013-07-17 14:40:12 -0700250#endif // ART_RUNTIME_INTERN_TABLE_H_