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.h"
9 : #include "src/roots-inl.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 :
14 : static const int kInitialIdentityMapSize = 4;
15 : static const int kResizeFactor = 2;
16 :
17 734428 : IdentityMapBase::~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 734428 : }
22 :
23 796951 : void IdentityMapBase::Clear() {
24 796951 : if (keys_) {
25 : DCHECK(!is_iterable());
26 526477 : heap_->UnregisterStrongRoots(FullObjectSlot(keys_));
27 526477 : DeleteArray(keys_);
28 526475 : DeleteArray(values_);
29 526475 : keys_ = nullptr;
30 526475 : values_ = nullptr;
31 526475 : size_ = 0;
32 526475 : capacity_ = 0;
33 526475 : mask_ = 0;
34 : }
35 796949 : }
36 :
37 166 : void IdentityMapBase::EnableIteration() {
38 166 : CHECK(!is_iterable());
39 166 : is_iterable_ = true;
40 166 : }
41 :
42 166 : void IdentityMapBase::DisableIteration() {
43 166 : CHECK(is_iterable());
44 166 : is_iterable_ = false;
45 166 : }
46 :
47 165859659 : int IdentityMapBase::ScanKeysFor(Address address) const {
48 165859659 : int start = Hash(address) & mask_;
49 165849154 : Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
50 1122447362 : for (int index = start; index < capacity_; index++) {
51 638163346 : if (keys_[index] == address) return index; // Found.
52 538153517 : if (keys_[index] == not_mapped) return -1; // Not found.
53 : }
54 116515852 : for (int index = 0; index < start; index++) {
55 60941448 : if (keys_[index] == address) return index; // Found.
56 60089119 : if (keys_[index] == not_mapped) return -1; // Not found.
57 : }
58 : return -1;
59 : }
60 :
61 173399160 : int IdentityMapBase::InsertKey(Address address) {
62 173399160 : Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
63 2829509 : while (true) {
64 176228669 : int start = Hash(address) & mask_;
65 176224280 : int limit = capacity_ / 2;
66 : // Search up to {limit} entries.
67 1069952356 : for (int index = start; --limit > 0; index = (index + 1) & mask_) {
68 620258811 : if (keys_[index] == address) return index; // Found.
69 620263083 : if (keys_[index] == not_mapped) { // Free entry.
70 173399045 : size_++;
71 : DCHECK_LE(size_, capacity_);
72 173399045 : keys_[index] = address;
73 173399045 : return index;
74 : }
75 : }
76 : // Should only have to resize once, since we grow 4x.
77 2829507 : Resize(capacity_ * kResizeFactor);
78 : }
79 : UNREACHABLE();
80 : }
81 :
82 10320 : bool IdentityMapBase::DeleteIndex(int index, void** deleted_value) {
83 10320 : if (deleted_value != nullptr) *deleted_value = values_[index];
84 10320 : Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
85 : DCHECK_NE(keys_[index], not_mapped);
86 10320 : keys_[index] = not_mapped;
87 10320 : values_[index] = nullptr;
88 10320 : size_--;
89 : DCHECK_GE(size_, 0);
90 :
91 20585 : if (capacity_ > kInitialIdentityMapSize &&
92 10265 : size_ * kResizeFactor < capacity_ / kResizeFactor) {
93 120 : Resize(capacity_ / kResizeFactor);
94 120 : 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 46794 : next_index = (next_index + 1) & mask_;
101 46794 : Address key = keys_[next_index];
102 46794 : if (key == not_mapped) break;
103 :
104 36594 : int expected_index = Hash(key) & mask_;
105 36594 : if (index < next_index) {
106 35724 : if (index < expected_index && expected_index <= next_index) continue;
107 : } else {
108 : DCHECK_GT(index, next_index);
109 870 : if (index < expected_index || expected_index <= next_index) continue;
110 : }
111 :
112 : DCHECK_EQ(not_mapped, keys_[index]);
113 : DCHECK_NULL(values_[index]);
114 8244 : std::swap(keys_[index], keys_[next_index]);
115 8244 : std::swap(values_[index], values_[next_index]);
116 : index = next_index;
117 : }
118 :
119 : return true;
120 : }
121 :
122 186598 : int IdentityMapBase::Lookup(Address key) const {
123 186598 : int index = ScanKeysFor(key);
124 259734 : if (index < 0 && gc_counter_ != heap_->gc_count()) {
125 : // Miss; rehash if there was a GC, then lookup again.
126 45 : const_cast<IdentityMapBase*>(this)->Rehash();
127 45 : index = ScanKeysFor(key);
128 : }
129 186598 : return index;
130 : }
131 :
132 165673183 : int IdentityMapBase::LookupOrInsert(Address key) {
133 : // Perform an optimistic lookup.
134 165673183 : int index = ScanKeysFor(key);
135 165672600 : if (index < 0) {
136 : // Miss; rehash if there was a GC, then insert.
137 129831922 : if (gc_counter_ != heap_->gc_count()) Rehash();
138 64915961 : index = InsertKey(key);
139 : }
140 : DCHECK_GE(index, 0);
141 165672571 : return index;
142 : }
143 :
144 342126730 : int IdentityMapBase::Hash(Address address) const {
145 684253460 : CHECK_NE(address, ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
146 342126794 : 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
153 165673197 : IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Address key) {
154 165673197 : CHECK(!is_iterable()); // Don't allow insertion while iterable.
155 165673197 : if (capacity_ == 0) {
156 : // Allocate the initial storage for keys and values.
157 526470 : capacity_ = kInitialIdentityMapSize;
158 526470 : mask_ = kInitialIdentityMapSize - 1;
159 1052940 : gc_counter_ = heap_->gc_count();
160 :
161 526470 : keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
162 526470 : Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
163 2632346 : for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
164 526470 : values_ = NewPointerArray(capacity_);
165 526471 : memset(values_, 0, sizeof(void*) * capacity_);
166 :
167 1579417 : heap_->RegisterStrongRoots(FullObjectSlot(keys_),
168 1052942 : FullObjectSlot(keys_ + capacity_));
169 : }
170 165673202 : int index = LookupOrInsert(key);
171 165672496 : 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}
178 165847 : IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Address key) const {
179 : // Don't allow find by key while iterable (might rehash).
180 165847 : CHECK(!is_iterable());
181 165847 : if (size_ == 0) return nullptr;
182 : // Remove constness since lookup might have to rehash.
183 159534 : int index = Lookup(key);
184 159534 : 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).
190 116040 : bool IdentityMapBase::DeleteEntry(Address key, void** deleted_value) {
191 116040 : CHECK(!is_iterable()); // Don't allow deletion by key while iterable.
192 116040 : if (size_ == 0) return false;
193 27064 : int index = Lookup(key);
194 27064 : if (index < 0) return false; // No entry found.
195 10320 : return DeleteIndex(index, deleted_value);
196 : }
197 :
198 12992 : Address 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 12992 : CHECK(is_iterable()); // Must be iterable to access by index;
203 12992 : return keys_[index];
204 : }
205 :
206 24542 : IdentityMapBase::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 24542 : CHECK(is_iterable()); // Must be iterable to access by index;
211 24542 : return &values_[index];
212 : }
213 :
214 18933 : int IdentityMapBase::NextIndex(int index) const {
215 : DCHECK_LE(-1, index);
216 : DCHECK_LE(index, capacity_);
217 18933 : CHECK(is_iterable()); // Must be iterable to access by index;
218 18933 : Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
219 25270 : for (++index; index < capacity_; ++index) {
220 25104 : if (keys_[index] != not_mapped) {
221 : return index;
222 : }
223 : }
224 : return capacity_;
225 : }
226 :
227 199 : void IdentityMapBase::Rehash() {
228 199 : CHECK(!is_iterable()); // Can't rehash while iterating.
229 : // Record the current GC counter.
230 398 : 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 19415 : for (int i = 0; i < capacity_; i++) {
238 9608 : if (keys_[i] == not_mapped) {
239 : last_empty = i;
240 : } else {
241 5862 : int pos = Hash(keys_[i]) & mask_;
242 5862 : if (pos <= last_empty || pos > i) {
243 : // Evacuate an entry that is in the wrong place.
244 1228 : reinsert.push_back(std::pair<Address, void*>(keys_[i], values_[i]));
245 614 : keys_[i] = not_mapped;
246 614 : values_[i] = nullptr;
247 : last_empty = i;
248 614 : size_--;
249 : }
250 : }
251 : }
252 : // Reinsert all the key/value pairs that were in the wrong place.
253 813 : for (auto pair : reinsert) {
254 614 : int index = InsertKey(pair.first);
255 : DCHECK_GE(index, 0);
256 614 : values_[index] = pair.second;
257 : }
258 199 : }
259 :
260 2829647 : void IdentityMapBase::Resize(int new_capacity) {
261 2829647 : 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 2829647 : int old_capacity = capacity_;
265 2829647 : Address* old_keys = keys_;
266 2829647 : void** old_values = values_;
267 :
268 2829647 : capacity_ = new_capacity;
269 2829647 : mask_ = capacity_ - 1;
270 5659294 : gc_counter_ = heap_->gc_count();
271 2829647 : size_ = 0;
272 :
273 2829647 : keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
274 2829644 : Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
275 240189788 : for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
276 2829644 : values_ = NewPointerArray(capacity_);
277 2829662 : memset(values_, 0, sizeof(void*) * capacity_);
278 :
279 240233322 : for (int i = 0; i < old_capacity; i++) {
280 118701843 : if (old_keys[i] == not_mapped) continue;
281 108483219 : int index = InsertKey(old_keys[i]);
282 : DCHECK_GE(index, 0);
283 108483206 : values_[index] = old_values[i];
284 : }
285 :
286 : // Unregister old keys and register new keys.
287 2829649 : heap_->UnregisterStrongRoots(FullObjectSlot(old_keys));
288 8488950 : heap_->RegisterStrongRoots(FullObjectSlot(keys_),
289 5659300 : FullObjectSlot(keys_ + capacity_));
290 :
291 : // Delete old storage;
292 2829650 : DeleteArray(old_keys);
293 2829650 : DeleteArray(old_values);
294 2829649 : }
295 :
296 : } // namespace internal
297 122036 : } // namespace v8
|
