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