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