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    : intern_table_lock_("InternTable lock"), is_dirty_(false), allow_new_interns_(true),
32      new_intern_condition_("New intern condition", intern_table_lock_) {
33}
34
35size_t InternTable::Size() const {
36  MutexLock mu(Thread::Current(), 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(), intern_table_lock_);
42  os << "Intern table: " << strong_interns_.size() << " strong; "
43     << weak_interns_.size() << " weak\n";
44}
45
46void InternTable::VisitRoots(RootVisitor* visitor, void* arg,
47                             bool only_dirty, bool clean_dirty) {
48  MutexLock mu(Thread::Current(), intern_table_lock_);
49  if (!only_dirty || is_dirty_) {
50    for (const auto& strong_intern : strong_interns_) {
51      visitor(strong_intern.second, arg);
52    }
53    if (clean_dirty) {
54      is_dirty_ = false;
55    }
56  }
57  // Note: we deliberately don't visit the weak_interns_ table and the immutable
58  // image roots.
59}
60
61mirror::String* InternTable::Lookup(Table& table, mirror::String* s,
62                                    uint32_t hash_code) {
63  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::Insert(Table& table, mirror::String* s,
74                                    uint32_t hash_code) {
75  intern_table_lock_.AssertHeld(Thread::Current());
76  table.insert(std::make_pair(hash_code, s));
77  return s;
78}
79
80void InternTable::Remove(Table& table, const mirror::String* s,
81                         uint32_t hash_code) {
82  intern_table_lock_.AssertHeld(Thread::Current());
83  for (auto it = table.find(hash_code), end = table.end(); it != end; ++it) {
84    if (it->second == s) {
85      table.erase(it);
86      return;
87    }
88  }
89}
90
91static mirror::String* LookupStringFromImage(mirror::String* s)
92    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
93  gc::space::ImageSpace* image = Runtime::Current()->GetHeap()->GetImageSpace();
94  if (image == NULL) {
95    return NULL;  // No image present.
96  }
97  mirror::Object* root = image->GetImageHeader().GetImageRoot(ImageHeader::kDexCaches);
98  mirror::ObjectArray<mirror::DexCache>* dex_caches = root->AsObjectArray<mirror::DexCache>();
99  const std::string utf8 = s->ToModifiedUtf8();
100  for (int32_t i = 0; i < dex_caches->GetLength(); ++i) {
101    mirror::DexCache* dex_cache = dex_caches->Get(i);
102    const DexFile* dex_file = dex_cache->GetDexFile();
103    // Binary search the dex file for the string index.
104    const DexFile::StringId* string_id = dex_file->FindStringId(utf8.c_str());
105    if (string_id != NULL) {
106      uint32_t string_idx = dex_file->GetIndexForStringId(*string_id);
107      mirror::String* image = dex_cache->GetResolvedString(string_idx);
108      if (image != NULL) {
109        return image;
110      }
111    }
112  }
113  return NULL;
114}
115
116void InternTable::AllowNewInterns() {
117  Thread* self = Thread::Current();
118  MutexLock mu(self, intern_table_lock_);
119  allow_new_interns_ = true;
120  new_intern_condition_.Broadcast(self);
121}
122
123void InternTable::DisallowNewInterns() {
124  Thread* self = Thread::Current();
125  MutexLock mu(self, intern_table_lock_);
126  allow_new_interns_ = false;
127}
128
129mirror::String* InternTable::Insert(mirror::String* s, bool is_strong) {
130  Thread* self = Thread::Current();
131  MutexLock mu(self, intern_table_lock_);
132
133  DCHECK(s != NULL);
134  uint32_t hash_code = s->GetHashCode();
135
136  while (UNLIKELY(!allow_new_interns_)) {
137    new_intern_condition_.WaitHoldingLocks(self);
138  }
139
140  if (is_strong) {
141    // Check the strong table for a match.
142    mirror::String* strong = Lookup(strong_interns_, s, hash_code);
143    if (strong != NULL) {
144      return strong;
145    }
146
147    // Mark as dirty so that we rescan the roots.
148    is_dirty_ = true;
149
150    // Check the image for a match.
151    mirror::String* image = LookupStringFromImage(s);
152    if (image != NULL) {
153      return Insert(strong_interns_, image, hash_code);
154    }
155
156    // There is no match in the strong table, check the weak table.
157    mirror::String* weak = Lookup(weak_interns_, s, hash_code);
158    if (weak != NULL) {
159      // A match was found in the weak table. Promote to the strong table.
160      Remove(weak_interns_, weak, hash_code);
161      return Insert(strong_interns_, weak, hash_code);
162    }
163
164    // No match in the strong table or the weak table. Insert into the strong
165    // table.
166    return Insert(strong_interns_, s, hash_code);
167  }
168
169  // Check the strong table for a match.
170  mirror::String* strong = Lookup(strong_interns_, s, hash_code);
171  if (strong != NULL) {
172    return strong;
173  }
174  // Check the image for a match.
175  mirror::String* image = LookupStringFromImage(s);
176  if (image != NULL) {
177    return Insert(weak_interns_, image, hash_code);
178  }
179  // Check the weak table for a match.
180  mirror::String* weak = Lookup(weak_interns_, s, hash_code);
181  if (weak != NULL) {
182    return weak;
183  }
184  // Insert into the weak table.
185  return Insert(weak_interns_, s, hash_code);
186}
187
188mirror::String* InternTable::InternStrong(int32_t utf16_length,
189                                          const char* utf8_data) {
190  return InternStrong(mirror::String::AllocFromModifiedUtf8(
191      Thread::Current(), utf16_length, utf8_data));
192}
193
194mirror::String* InternTable::InternStrong(const char* utf8_data) {
195  return InternStrong(
196      mirror::String::AllocFromModifiedUtf8(Thread::Current(), utf8_data));
197}
198
199mirror::String* InternTable::InternStrong(mirror::String* s) {
200  if (s == NULL) {
201    return NULL;
202  }
203  return Insert(s, true);
204}
205
206mirror::String* InternTable::InternWeak(mirror::String* s) {
207  if (s == NULL) {
208    return NULL;
209  }
210  return Insert(s, false);
211}
212
213bool InternTable::ContainsWeak(mirror::String* s) {
214  MutexLock mu(Thread::Current(), intern_table_lock_);
215  const mirror::String* found = Lookup(weak_interns_, s, s->GetHashCode());
216  return found == s;
217}
218
219void InternTable::SweepInternTableWeaks(IsMarkedTester is_marked, void* arg) {
220  MutexLock mu(Thread::Current(), intern_table_lock_);
221  // TODO: std::remove_if + lambda.
222  for (auto it = weak_interns_.begin(), end = weak_interns_.end(); it != end;) {
223    mirror::Object* object = it->second;
224    if (!is_marked(object, arg)) {
225      weak_interns_.erase(it++);
226    } else {
227      ++it;
228    }
229  }
230}
231
232}  // namespace art
233