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 545700 : 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 545700 : }
21 :
22 664299 : void IdentityMapBase::Clear() {
23 664299 : if (keys_) {
24 : DCHECK(!is_iterable());
25 400863 : heap_->UnregisterStrongRoots(keys_);
26 400864 : DeleteArray(keys_);
27 400864 : DeleteArray(values_);
28 400864 : keys_ = nullptr;
29 400864 : values_ = nullptr;
30 400864 : size_ = 0;
31 400864 : capacity_ = 0;
32 400864 : mask_ = 0;
33 : }
34 664300 : }
35 :
36 154 : void IdentityMapBase::EnableIteration() {
37 154 : CHECK(!is_iterable());
38 154 : is_iterable_ = true;
39 154 : }
40 :
41 154 : void IdentityMapBase::DisableIteration() {
42 154 : CHECK(is_iterable());
43 154 : is_iterable_ = false;
44 154 : }
45 :
46 25970439 : int IdentityMapBase::ScanKeysFor(Object* address) const {
47 25970439 : int start = Hash(address) & mask_;
48 25970347 : Object* not_mapped = heap_->not_mapped_symbol();
49 82247229 : for (int index = start; index < capacity_; index++) {
50 80936762 : if (keys_[index] == address) return index; // Found.
51 69802378 : if (keys_[index] == not_mapped) return -1; // Not found.
52 : }
53 5908412 : for (int index = 0; index < start; index++) {
54 7114693 : if (keys_[index] == address) return index; // Found.
55 6888508 : if (keys_[index] == not_mapped) return -1; // Not found.
56 : }
57 : return -1;
58 : }
59 :
60 23342517 : int IdentityMapBase::InsertKey(Object* address) {
61 23342517 : Object* not_mapped = heap_->not_mapped_symbol();
62 : while (true) {
63 24159071 : int start = Hash(address) & mask_;
64 24159104 : int limit = capacity_ / 2;
65 : // Search up to {limit} entries.
66 70991085 : for (int index = start; --limit > 0; index = (index + 1) & mask_) {
67 70174531 : if (keys_[index] == address) return index; // Found.
68 70174478 : if (keys_[index] == not_mapped) { // Free entry.
69 23342497 : keys_[index] = address;
70 23342497 : return index;
71 : }
72 : }
73 : // Should only have to resize once, since we grow 4x.
74 816554 : Resize(capacity_ * kResizeFactor);
75 : }
76 : UNREACHABLE();
77 816554 : return -1;
78 : }
79 :
80 14469 : void* IdentityMapBase::DeleteIndex(int index) {
81 14469 : void* ret_value = values_[index];
82 14469 : Object* not_mapped = heap_->not_mapped_symbol();
83 : DCHECK_NE(keys_[index], not_mapped);
84 14469 : keys_[index] = not_mapped;
85 14469 : values_[index] = nullptr;
86 14469 : size_--;
87 : DCHECK_GE(size_, 0);
88 :
89 14469 : if (size_ * kResizeFactor < capacity_ / kResizeFactor) {
90 129 : Resize(capacity_ / kResizeFactor);
91 129 : return ret_value; // No need to fix collisions as resize reinserts keys.
92 : }
93 :
94 : // Move any collisions to their new correct location.
95 : int next_index = index;
96 : for (;;) {
97 57285 : next_index = (next_index + 1) & mask_;
98 57285 : Object* key = keys_[next_index];
99 57285 : if (key == not_mapped) break;
100 :
101 42945 : int expected_index = Hash(key) & mask_;
102 42945 : if (index < next_index) {
103 41923 : if (index < expected_index && expected_index <= next_index) continue;
104 : } else {
105 : DCHECK_GT(index, next_index);
106 1022 : if (index < expected_index || expected_index <= next_index) continue;
107 : }
108 :
109 : DCHECK_EQ(not_mapped, keys_[index]);
110 : DCHECK_NULL(values_[index]);
111 8379 : std::swap(keys_[index], keys_[next_index]);
112 8379 : std::swap(values_[index], values_[next_index]);
113 : index = next_index;
114 : }
115 :
116 : return ret_value;
117 : }
118 :
119 203412 : int IdentityMapBase::Lookup(Object* key) const {
120 203412 : int index = ScanKeysFor(key);
121 272190 : if (index < 0 && gc_counter_ != heap_->gc_count()) {
122 : // Miss; rehash if there was a GC, then lookup again.
123 63 : const_cast<IdentityMapBase*>(this)->Rehash();
124 63 : index = ScanKeysFor(key);
125 : }
126 203412 : return index;
127 : }
128 :
129 25766972 : int IdentityMapBase::LookupOrInsert(Object* key) {
130 : // Perform an optimistic lookup.
131 25766972 : int index = ScanKeysFor(key);
132 25766949 : if (index < 0) {
133 : // Miss; rehash if there was a GC, then insert.
134 29082076 : if (gc_counter_ != heap_->gc_count()) Rehash();
135 14541038 : index = InsertKey(key);
136 14541014 : size_++;
137 : DCHECK_LE(size_, capacity_);
138 : }
139 : DCHECK_GE(index, 0);
140 25766925 : return index;
141 : }
142 :
143 50187154 : int IdentityMapBase::Hash(Object* address) const {
144 50187154 : CHECK_NE(address, heap_->not_mapped_symbol());
145 50187154 : uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
146 50187151 : return static_cast<int>(hasher_(raw_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 25766972 : IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) {
154 25766972 : CHECK(!is_iterable()); // Don't allow insertion while iterable.
155 25766972 : if (capacity_ == 0) {
156 : // Allocate the initial storage for keys and values.
157 400864 : capacity_ = kInitialIdentityMapSize;
158 400864 : mask_ = kInitialIdentityMapSize - 1;
159 1202592 : gc_counter_ = heap_->gc_count();
160 :
161 400864 : keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
162 400864 : Object* not_mapped = heap_->not_mapped_symbol();
163 400864 : for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
164 400864 : values_ = NewPointerArray(capacity_);
165 400864 : memset(values_, 0, sizeof(void*) * capacity_);
166 :
167 400864 : heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
168 : }
169 25766972 : int index = LookupOrInsert(key);
170 25766866 : return &values_[index];
171 : }
172 :
173 : // Searches this map for the given key using the object's address
174 : // as the identity, returning:
175 : // found => a pointer to the storage location for the value
176 : // not found => {nullptr}
177 199000 : IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) const {
178 : // Don't allow find by key while iterable (might rehash).
179 199000 : CHECK(!is_iterable());
180 199000 : if (size_ == 0) return nullptr;
181 : // Remove constness since lookup might have to rehash.
182 188942 : int index = Lookup(key);
183 188942 : return index >= 0 ? &values_[index] : nullptr;
184 : }
185 :
186 : // Deletes the given key from the map using the object's address as the
187 : // identity, returning:
188 : // found => the value
189 : // not found => {nullptr}
190 15876 : void* IdentityMapBase::DeleteEntry(Object* key) {
191 15876 : CHECK(!is_iterable()); // Don't allow deletion by key while iterable.
192 15876 : if (size_ == 0) return nullptr;
193 14470 : int index = Lookup(key);
194 14470 : if (index < 0) return nullptr; // No entry found.
195 14469 : return DeleteIndex(index);
196 : }
197 :
198 16170 : IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const {
199 : DCHECK_LE(0, index);
200 : DCHECK_LT(index, capacity_);
201 : DCHECK_NE(keys_[index], heap_->not_mapped_symbol());
202 16170 : CHECK(is_iterable()); // Must be iterable to access by index;
203 16170 : return &values_[index];
204 : }
205 :
206 8239 : int IdentityMapBase::NextIndex(int index) const {
207 : DCHECK_LE(-1, index);
208 : DCHECK_LE(index, capacity_);
209 8239 : CHECK(is_iterable()); // Must be iterable to access by index;
210 8239 : Object* not_mapped = heap_->not_mapped_symbol();
211 19754 : for (++index; index < capacity_; ++index) {
212 19600 : if (keys_[index] != not_mapped) {
213 : return index;
214 : }
215 : }
216 : return capacity_;
217 : }
218 :
219 118 : void IdentityMapBase::Rehash() {
220 118 : CHECK(!is_iterable()); // Can't rehash while iterating.
221 : // Record the current GC counter.
222 354 : gc_counter_ = heap_->gc_count();
223 : // Assume that most objects won't be moved.
224 : std::vector<std::pair<Object*, void*>> reinsert;
225 : // Search the table looking for keys that wouldn't be found with their
226 : // current hashcode and evacuate them.
227 : int last_empty = -1;
228 : Object* not_mapped = heap_->not_mapped_symbol();
229 24998 : for (int i = 0; i < capacity_; i++) {
230 28432 : if (keys_[i] == not_mapped) {
231 : last_empty = i;
232 : } else {
233 14959 : int pos = Hash(keys_[i]) & mask_;
234 14959 : if (pos <= last_empty || pos > i) {
235 : // Evacuate an entry that is in the wrong place.
236 7104 : reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i]));
237 3552 : keys_[i] = not_mapped;
238 3552 : values_[i] = nullptr;
239 : last_empty = i;
240 : }
241 : }
242 : }
243 : // Reinsert all the key/value pairs that were in the wrong place.
244 3788 : for (auto pair : reinsert) {
245 3552 : int index = InsertKey(pair.first);
246 : DCHECK_GE(index, 0);
247 3552 : values_[index] = pair.second;
248 : }
249 118 : }
250 :
251 816711 : void IdentityMapBase::Resize(int new_capacity) {
252 816711 : 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 816711 : int old_capacity = capacity_;
256 816711 : Object** old_keys = keys_;
257 816711 : void** old_values = values_;
258 :
259 816711 : capacity_ = new_capacity;
260 816711 : mask_ = capacity_ - 1;
261 2450133 : gc_counter_ = heap_->gc_count();
262 :
263 816711 : keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
264 816711 : Object* not_mapped = heap_->not_mapped_symbol();
265 816711 : for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
266 816711 : values_ = NewPointerArray(capacity_);
267 816711 : memset(values_, 0, sizeof(void*) * capacity_);
268 :
269 11478884 : for (int i = 0; i < old_capacity; i++) {
270 10662173 : if (old_keys[i] == not_mapped) continue;
271 8797965 : int index = InsertKey(old_keys[i]);
272 : DCHECK_GE(index, 0);
273 8797965 : values_[index] = old_values[i];
274 : }
275 :
276 : // Unregister old keys and register new keys.
277 816711 : heap_->UnregisterStrongRoots(old_keys);
278 816711 : heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
279 :
280 : // Delete old storage;
281 816711 : DeleteArray(old_keys);
282 816711 : DeleteArray(old_values);
283 816711 : }
284 :
285 : } // namespace internal
286 : } // namespace v8
|
