intern_table.cc revision 815873ecc312b1d231acce71e1a16f42cdaf09f2 
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#include "intern_table.h"
18
19#include "gc/space/image_space.h"
20#include "mirror/dex_cache.h"
21#include "mirror/object_array-inl.h"
22#include "mirror/object-inl.h"
23#include "mirror/string.h"
24#include "thread.h"
25#include "UniquePtr.h"
26#include "utf.h"
27
28namespace art {
29
30InternTable::InternTable()
31    : is_dirty_(false), allow_new_interns_(true),
32      new_intern_condition_("New intern condition", *Locks::intern_table_lock_) {
33}
34
35size_t InternTable::Size() const {
36  MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
37  return strong_interns_.size() + weak_interns_.size();
38}
39
40void InternTable::DumpForSigQuit(std::ostream& os) const {
41  MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
42  os << "Intern table: " << strong_interns_.size() << " strong; "
43     << weak_interns_.size() << " weak\n";
44}
45
46void InternTable::VisitRoots(RootCallback* callback, void* arg,
47                             bool only_dirty, bool clean_dirty) {
48  MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
49  if (!only_dirty || is_dirty_) {
50    for (auto& strong_intern : strong_interns_) {
51      callback(reinterpret_cast<mirror::Object**>(&strong_intern.second), arg, 0,
52               kRootInternedString);
53      DCHECK(strong_intern.second != nullptr);
54    }
55    if (clean_dirty) {
56      is_dirty_ = false;
57    }
58  }
59  // Note: we deliberately don't visit the weak_interns_ table and the immutable image roots.
60}
61
62mirror::String* InternTable::Lookup(Table& table, mirror::String* s, uint32_t hash_code) {
63  Locks::intern_table_lock_->AssertHeld(Thread::Current());
64  for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) {
65    mirror::String* existing_string = it->second;
66    if (existing_string->Equals(s)) {
67      return existing_string;
68    }
69  }
70  return NULL;
71}
72
73mirror::String* InternTable::InsertStrong(mirror::String* s, uint32_t hash_code) {
74  Runtime* runtime = Runtime::Current();
75  if (runtime->IsActiveTransaction()) {
76    runtime->RecordStrongStringInsertion(s, hash_code);
77  }
78  return Insert(strong_interns_, s, hash_code);
79}
80
81mirror::String* InternTable::InsertWeak(mirror::String* s, uint32_t hash_code) {
82  Runtime* runtime = Runtime::Current();
83  if (runtime->IsActiveTransaction()) {
84    runtime->RecordWeakStringInsertion(s, hash_code);
85  }
86  return Insert(weak_interns_, s, hash_code);
87}
88
89mirror::String* InternTable::Insert(Table& table, mirror::String* s, uint32_t hash_code) {
90  Locks::intern_table_lock_->AssertHeld(Thread::Current());
91  table.insert(std::make_pair(hash_code, s));
92  return s;
93}
94
95void InternTable::RemoveWeak(mirror::String* s, uint32_t hash_code) {
96  Runtime* runtime = Runtime::Current();
97  if (runtime->IsActiveTransaction()) {
98    runtime->RecordWeakStringRemoval(s, hash_code);
99  }
100  Remove(weak_interns_, s, hash_code);
101}
102
103void InternTable::Remove(Table& table, mirror::String* s, uint32_t hash_code) {
104  Locks::intern_table_lock_->AssertHeld(Thread::Current());
105  for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) {
106    if (it->second == s) {
107      table.erase(it);
108      return;
109    }
110  }
111}
112
113// Insert/remove methods used to undo changes made during an aborted transaction.
114mirror::String* InternTable::InsertStrongFromTransaction(mirror::String* s, uint32_t hash_code) {
115  DCHECK(!Runtime::Current()->IsActiveTransaction());
116  return InsertStrong(s, hash_code);
117}
118mirror::String* InternTable::InsertWeakFromTransaction(mirror::String* s, uint32_t hash_code) {
119  DCHECK(!Runtime::Current()->IsActiveTransaction());
120  return InsertWeak(s, hash_code);
121}
122void InternTable::RemoveStrongFromTransaction(mirror::String* s, uint32_t hash_code) {
123  DCHECK(!Runtime::Current()->IsActiveTransaction());
124  Remove(strong_interns_, s, hash_code);
125}
126void InternTable::RemoveWeakFromTransaction(mirror::String* s, uint32_t hash_code) {
127  DCHECK(!Runtime::Current()->IsActiveTransaction());
128  Remove(weak_interns_, s, hash_code);
129}
130
131static mirror::String* LookupStringFromImage(mirror::String* s)
132    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
133  gc::space::ImageSpace* image = Runtime::Current()->GetHeap()->GetImageSpace();
134  if (image == NULL) {
135    return NULL;  // No image present.
136  }
137  mirror::Object* root = image->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches);
138  mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>();
139  const std::string utf8 = s->ToModifiedUtf8();
140  for (int32_t i = 0; i < dex_caches->GetLength(); ++i) {
141    mirror::DexCache* dex_cache = dex_caches->Get(i);
142    const DexFile* dex_file = dex_cache->GetDexFile();
143    // Binary search the dex file for the string index.
144    const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str());
145    if (string_id != NULL) {
146      uint32_t string_idx = dex_file->GetIndexForStringId(*string_id);
147      mirror::String* image = dex_cache->GetResolvedString(string_idx);
148      if (image != NULL) {
149        return image;
150      }
151    }
152  }
153  return NULL;
154}
155
156void InternTable::AllowNewInterns() {
157  Thread* self = Thread::Current();
158  MutexLock mu(self, *Locks::intern_table_lock_);
159  allow_new_interns_ = true;
160  new_intern_condition_.Broadcast(self);
161}
162
163void InternTable::DisallowNewInterns() {
164  Thread* self = Thread::Current();
165  MutexLock mu(self, *Locks::intern_table_lock_);
166  allow_new_interns_ = false;
167}
168
169mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) {
170  Thread* self = Thread::Current();
171  MutexLock mu(self, *Locks::intern_table_lock_);
172
173  DCHECK(s != NULL);
174  uint32_t hash_code = s->GetHashCode();
175
176  while (UNLIKELY(!allow_new_interns_)) {
177    new_intern_condition_.WaitHoldingLocks(self);
178  }
179
180  if (is_strong) {
181    // Check the strong table for a match.
182    mirror::String* strong = Lookup(strong_interns_, s, hash_code);
183    if (strong != NULL) {
184      return strong;
185    }
186
187    // Mark as dirty so that we rescan the roots.
188    is_dirty_ = true;
189
190    // Check the image for a match.
191    mirror::String* image = LookupStringFromImage(s);
192    if (image != NULL) {
193      return InsertStrong(image, hash_code);
194    }
195
196    // There is no match in the strong table, check the weak table.
197    mirror::String* weak = Lookup(weak_interns_, s, hash_code);
198    if (weak != NULL) {
199      // A match was found in the weak table. Promote to the strong table.
200      RemoveWeak(weak, hash_code);
201      return InsertStrong(weak, hash_code);
202    }
203
204    // No match in the strong table or the weak table. Insert into the strong
205    // table.
206    return InsertStrong(s, hash_code);
207  }
208
209  // Check the strong table for a match.
210  mirror::String* strong = Lookup(strong_interns_, s, hash_code);
211  if (strong != NULL) {
212    return strong;
213  }
214  // Check the image for a match.
215  mirror::String* image = LookupStringFromImage(s);
216  if (image != NULL) {
217    return InsertWeak(image, hash_code);
218  }
219  // Check the weak table for a match.
220  mirror::String* weak = Lookup(weak_interns_, s, hash_code);
221  if (weak != NULL) {
222    return weak;
223  }
224  // Insert into the weak table.
225  return InsertWeak(s, hash_code);
226}
227
228mirror::String* InternTable::InternStrong(int32_t utf16_length,
229                                          const char* utf8_data) {
230  return InternStrong(mirror::String::AllocFromModifiedUtf8(
231      Thread::Current(), utf16_length, utf8_data));
232}
233
234mirror::String* InternTable::InternStrong(const char* utf8_data) {
235  return InternStrong(
236      mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
237}
238
239mirror::String* InternTable::InternStrong(mirror::String* s) {
240  if (s == nullptr) {
241    return nullptr;
242  }
243  return Insert(s, true);
244}
245
246mirror::String* InternTable::InternWeak(mirror::String* s) {
247  if (s == nullptr) {
248    return nullptr;
249  }
250  return Insert(s, false);
251}
252
253bool InternTable::ContainsWeak(mirror::String* s) {
254  MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
255  const mirror::String* found = Lookup(weak_interns_, s, s->GetHashCode());
256  return found == s;
257}
258
259void InternTable::SweepInternTableWeaks(IsMarkedCallback* callback, void* arg) {
260  MutexLock mu(Thread::Current(), *Locks::intern_table_lock_);
261  for (auto it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) {
262    mirror::Object* object = it->second;
263    mirror::Object* new_object = callback(object, arg);
264    if (new_object == nullptr) {
265      // TODO: use it = weak_interns_.erase(it) when we get a c++11 stl.
266      weak_interns_.erase(it++);
267    } else {
268      it->second = down_cast<mirror::String*>(new_object);
269      ++it;
270    }
271  }
272}
273
274}  // namespace art
275