Line data Source code
1 : // Copyright 2015 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/identity-map.h"
6 :
7 : #include "src/base/functional.h"
8 : #include "src/heap/heap-inl.h"
9 :
10 : namespace v8 {
11 : namespace internal {
12 :
13 : static const int kInitialIdentityMapSize = 4;
14 : static const int kResizeFactor = 4;
15 :
16 723290 : IdentityMapBase::~IdentityMapBase() {
17 : // Clear must be called by the subclass to avoid calling the virtual
18 : // DeleteArray function from the destructor.
19 : DCHECK_NULL(keys_);
20 723290 : }
21 :
22 830140 : void IdentityMapBase::Clear() {
23 830140 : if (keys_) {
24 : DCHECK(!is_iterable());
25 646325 : heap_->UnregisterStrongRoots(keys_);
26 646326 : DeleteArray(keys_);
27 646326 : DeleteArray(values_);
28 646326 : keys_ = nullptr;
29 646326 : values_ = nullptr;
30 646326 : size_ = 0;
31 646326 : capacity_ = 0;
32 646326 : mask_ = 0;
33 : }
34 830141 : }
35 :
36 131757 : void IdentityMapBase::EnableIteration() {
37 131757 : CHECK(!is_iterable());
38 131757 : is_iterable_ = true;
39 131757 : }
40 :
41 131757 : void IdentityMapBase::DisableIteration() {
42 131757 : CHECK(is_iterable());
43 131757 : is_iterable_ = false;
44 131757 : }
45 :
46 27045162 : int IdentityMapBase::ScanKeysFor(Object* address) const {
47 27045162 : int start = Hash(address) & mask_;
48 27045133 : Object* not_mapped = heap_->not_mapped_symbol();
49 78564168 : for (int index = start; index < capacity_; index++) {
50 77429840 : if (keys_[index] == address) return index; // Found.
51 66689920 : if (keys_[index] == not_mapped) return -1; // Not found.
52 : }
53 3805238 : for (int index = 0; index < start; index++) {
54 4824969 : if (keys_[index] == address) return index; // Found.
55 4726172 : if (keys_[index] == not_mapped) return -1; // Not found.
56 : }
57 : return -1;
58 : }
59 :
60 26369109 : int IdentityMapBase::InsertKey(Object* address) {
61 26369109 : Object* not_mapped = heap_->not_mapped_symbol();
62 : while (true) {
63 27347719 : int start = Hash(address) & mask_;
64 27347634 : int limit = capacity_ / 2;
65 : // Search up to {limit} entries.
66 70060093 : for (int index = start; --limit > 0; index = (index + 1) & mask_) {
67 69081483 : if (keys_[index] == address) return index; // Found.
68 69081465 : if (keys_[index] == not_mapped) { // Free entry.
69 26369006 : size_++;
70 : DCHECK_LE(size_, capacity_);
71 26369006 : keys_[index] = address;
72 26369006 : return index;
73 : }
74 : }
75 : // Should only have to resize once, since we grow 4x.
76 978610 : Resize(capacity_ * kResizeFactor);
77 : }
78 978610 : UNREACHABLE();
79 : }
80 :
81 12403 : void* IdentityMapBase::DeleteIndex(int index) {
82 12403 : void* ret_value = values_[index];
83 12403 : Object* not_mapped = heap_->not_mapped_symbol();
84 : DCHECK_NE(keys_[index], not_mapped);
85 12403 : keys_[index] = not_mapped;
86 12403 : values_[index] = nullptr;
87 12403 : size_--;
88 : DCHECK_GE(size_, 0);
89 :
90 12403 : if (size_ * kResizeFactor < capacity_ / kResizeFactor) {
91 111 : Resize(capacity_ / kResizeFactor);
92 111 : return ret_value; // No need to fix collisions as resize reinserts keys.
93 : }
94 :
95 : // Move any collisions to their new correct location.
96 : int next_index = index;
97 : for (;;) {
98 49170 : next_index = (next_index + 1) & mask_;
99 49170 : Object* key = keys_[next_index];
100 49170 : if (key == not_mapped) break;
101 :
102 36878 : int expected_index = Hash(key) & mask_;
103 36878 : if (index < next_index) {
104 36007 : if (index < expected_index && expected_index <= next_index) continue;
105 : } else {
106 : DCHECK_GT(index, next_index);
107 871 : if (index < expected_index || expected_index <= next_index) continue;
108 : }
109 :
110 : DCHECK_EQ(not_mapped, keys_[index]);
111 : DCHECK_NULL(values_[index]);
112 7188 : std::swap(keys_[index], keys_[next_index]);
113 7188 : std::swap(values_[index], values_[next_index]);
114 : index = next_index;
115 : }
116 :
117 : return ret_value;
118 : }
119 :
120 161752 : int IdentityMapBase::Lookup(Object* key) const {
121 161752 : int index = ScanKeysFor(key);
122 219426 : if (index < 0 && gc_counter_ != heap_->gc_count()) {
123 : // Miss; rehash if there was a GC, then lookup again.
124 54 : const_cast<IdentityMapBase*>(this)->Rehash();
125 54 : index = ScanKeysFor(key);
126 : }
127 161752 : return index;
128 : }
129 :
130 26883355 : int IdentityMapBase::LookupOrInsert(Object* key) {
131 : // Perform an optimistic lookup.
132 26883355 : int index = ScanKeysFor(key);
133 26883347 : if (index < 0) {
134 : // Miss; rehash if there was a GC, then insert.
135 32297502 : if (gc_counter_ != heap_->gc_count()) Rehash();
136 16148751 : index = InsertKey(key);
137 : }
138 : DCHECK_GE(index, 0);
139 26883341 : return index;
140 : }
141 :
142 54441275 : int IdentityMapBase::Hash(Object* address) const {
143 54441275 : CHECK_NE(address, heap_->not_mapped_symbol());
144 54441275 : uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
145 54441269 : return static_cast<int>(hasher_(raw_address));
146 : }
147 :
148 : // Searches this map for the given key using the object's address
149 : // as the identity, returning:
150 : // found => a pointer to the storage location for the value
151 : // not found => a pointer to a new storage location for the value
152 26883353 : IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) {
153 26883353 : CHECK(!is_iterable()); // Don't allow insertion while iterable.
154 26883353 : if (capacity_ == 0) {
155 : // Allocate the initial storage for keys and values.
156 646326 : capacity_ = kInitialIdentityMapSize;
157 646326 : mask_ = kInitialIdentityMapSize - 1;
158 1938978 : gc_counter_ = heap_->gc_count();
159 :
160 646326 : keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
161 646326 : Object* not_mapped = heap_->not_mapped_symbol();
162 646326 : for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
163 646326 : values_ = NewPointerArray(capacity_);
164 646326 : memset(values_, 0, sizeof(void*) * capacity_);
165 :
166 646326 : heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
167 : }
168 26883353 : int index = LookupOrInsert(key);
169 26883333 : return &values_[index];
170 : }
171 :
172 : // Searches this map for the given key using the object's address
173 : // as the identity, returning:
174 : // found => a pointer to the storage location for the value
175 : // not found => {nullptr}
176 157057 : IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) const {
177 : // Don't allow find by key while iterable (might rehash).
178 157057 : CHECK(!is_iterable());
179 157057 : if (size_ == 0) return nullptr;
180 : // Remove constness since lookup might have to rehash.
181 149349 : int index = Lookup(key);
182 149349 : return index >= 0 ? &values_[index] : nullptr;
183 : }
184 :
185 : // Deletes the given key from the map using the object's address as the
186 : // identity, returning:
187 : // found => the value
188 : // not found => {nullptr}
189 13603 : void* IdentityMapBase::DeleteEntry(Object* key) {
190 13603 : CHECK(!is_iterable()); // Don't allow deletion by key while iterable.
191 13603 : if (size_ == 0) return nullptr;
192 12403 : int index = Lookup(key);
193 12403 : if (index < 0) return nullptr; // No entry found.
194 12403 : return DeleteIndex(index);
195 : }
196 :
197 146645 : IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const {
198 : DCHECK_LE(0, index);
199 : DCHECK_LT(index, capacity_);
200 : DCHECK_NE(keys_[index], heap_->not_mapped_symbol());
201 146645 : CHECK(is_iterable()); // Must be iterable to access by index;
202 146645 : return &values_[index];
203 : }
204 :
205 271472 : int IdentityMapBase::NextIndex(int index) const {
206 : DCHECK_LE(-1, index);
207 : DCHECK_LE(index, capacity_);
208 271472 : CHECK(is_iterable()); // Must be iterable to access by index;
209 271472 : Object* not_mapped = heap_->not_mapped_symbol();
210 677877 : for (++index; index < capacity_; ++index) {
211 546120 : if (keys_[index] != not_mapped) {
212 : return index;
213 : }
214 : }
215 : return capacity_;
216 : }
217 :
218 195 : void IdentityMapBase::Rehash() {
219 195 : CHECK(!is_iterable()); // Can't rehash while iterating.
220 : // Record the current GC counter.
221 585 : gc_counter_ = heap_->gc_count();
222 : // Assume that most objects won't be moved.
223 : std::vector<std::pair<Object*, void*>> reinsert;
224 : // Search the table looking for keys that wouldn't be found with their
225 : // current hashcode and evacuate them.
226 : int last_empty = -1;
227 : Object* not_mapped = heap_->not_mapped_symbol();
228 21987 : for (int i = 0; i < capacity_; i++) {
229 23259 : if (keys_[i] == not_mapped) {
230 : last_empty = i;
231 : } else {
232 11599 : int pos = Hash(keys_[i]) & mask_;
233 11599 : if (pos <= last_empty || pos > i) {
234 : // Evacuate an entry that is in the wrong place.
235 2934 : reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i]));
236 1467 : keys_[i] = not_mapped;
237 1467 : values_[i] = nullptr;
238 : last_empty = i;
239 1467 : size_--;
240 : }
241 : }
242 : }
243 : // Reinsert all the key/value pairs that were in the wrong place.
244 1857 : for (auto pair : reinsert) {
245 1467 : int index = InsertKey(pair.first);
246 : DCHECK_GE(index, 0);
247 1467 : values_[index] = pair.second;
248 : }
249 195 : }
250 :
251 978745 : void IdentityMapBase::Resize(int new_capacity) {
252 978745 : CHECK(!is_iterable()); // Can't resize while iterating.
253 : // Resize the internal storage and reinsert all the key/value pairs.
254 : DCHECK_GT(new_capacity, size_);
255 978745 : int old_capacity = capacity_;
256 978745 : Object** old_keys = keys_;
257 978745 : void** old_values = values_;
258 :
259 978745 : capacity_ = new_capacity;
260 978745 : mask_ = capacity_ - 1;
261 2936235 : gc_counter_ = heap_->gc_count();
262 978745 : size_ = 0;
263 :
264 978745 : keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
265 978745 : Object* not_mapped = heap_->not_mapped_symbol();
266 978745 : for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
267 978745 : values_ = NewPointerArray(capacity_);
268 978745 : memset(values_, 0, sizeof(void*) * capacity_);
269 :
270 13497594 : for (int i = 0; i < old_capacity; i++) {
271 12518849 : if (old_keys[i] == not_mapped) continue;
272 10218915 : int index = InsertKey(old_keys[i]);
273 : DCHECK_GE(index, 0);
274 10218915 : values_[index] = old_values[i];
275 : }
276 :
277 : // Unregister old keys and register new keys.
278 978745 : heap_->UnregisterStrongRoots(old_keys);
279 978745 : heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
280 :
281 : // Delete old storage;
282 978745 : DeleteArray(old_keys);
283 978745 : DeleteArray(old_values);
284 978745 : }
285 :
286 : } // namespace internal
287 : } // namespace v8
|
