// Copyright 2015 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "src/identity-map.h" #include "src/base/functional.h" #include "src/heap/heap-inl.h" #include "src/zone-containers.h" namespace v8 { namespace internal { static const int kInitialIdentityMapSize = 4; static const int kResizeFactor = 4; IdentityMapBase::~IdentityMapBase() { Clear(); } void IdentityMapBase::Clear() { if (keys_) { heap_->UnregisterStrongRoots(keys_); keys_ = nullptr; values_ = nullptr; size_ = 0; mask_ = 0; } } IdentityMapBase::RawEntry IdentityMapBase::Lookup(Object* key) { int index = LookupIndex(key); return index >= 0 ? &values_[index] : nullptr; } IdentityMapBase::RawEntry IdentityMapBase::Insert(Object* key) { int index = InsertIndex(key); DCHECK_GE(index, 0); return &values_[index]; } int IdentityMapBase::Hash(Object* address) { CHECK_NE(address, heap_->not_mapped_symbol()); uintptr_t raw_address = reinterpret_cast<uintptr_t>(address); return static_cast<int>(hasher_(raw_address)); } int IdentityMapBase::LookupIndex(Object* address) { int start = Hash(address) & mask_; Object* not_mapped = heap_->not_mapped_symbol(); for (int index = start; index < size_; index++) { if (keys_[index] == address) return index; // Found. if (keys_[index] == not_mapped) return -1; // Not found. } for (int index = 0; index < start; index++) { if (keys_[index] == address) return index; // Found. if (keys_[index] == not_mapped) return -1; // Not found. } return -1; } int IdentityMapBase::InsertIndex(Object* address) { Object* not_mapped = heap_->not_mapped_symbol(); while (true) { int start = Hash(address) & mask_; int limit = size_ / 2; // Search up to {limit} entries. for (int index = start; --limit > 0; index = (index + 1) & mask_) { if (keys_[index] == address) return index; // Found. if (keys_[index] == not_mapped) { // Free entry. keys_[index] = address; return index; } } Resize(); // Should only have to resize once, since we grow 4x. } UNREACHABLE(); return -1; } // Searches this map for the given key using the object's address // as the identity, returning: // found => a pointer to the storage location for the value // not found => a pointer to a new storage location for the value IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) { RawEntry result; if (size_ == 0) { // Allocate the initial storage for keys and values. size_ = kInitialIdentityMapSize; mask_ = kInitialIdentityMapSize - 1; gc_counter_ = heap_->gc_count(); keys_ = zone_->NewArray<Object*>(size_); Object* not_mapped = heap_->not_mapped_symbol(); for (int i = 0; i < size_; i++) keys_[i] = not_mapped; values_ = zone_->NewArray<void*>(size_); memset(values_, 0, sizeof(void*) * size_); heap_->RegisterStrongRoots(keys_, keys_ + size_); result = Insert(key); } else { // Perform an optimistic lookup. result = Lookup(key); if (result == nullptr) { // Miss; rehash if there was a GC, then insert. if (gc_counter_ != heap_->gc_count()) Rehash(); result = Insert(key); } } return result; } // Searches this map for the given key using the object's address // as the identity, returning: // found => a pointer to the storage location for the value // not found => {nullptr} IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) { if (size_ == 0) return nullptr; RawEntry result = Lookup(key); if (result == nullptr && gc_counter_ != heap_->gc_count()) { Rehash(); // Rehash is expensive, so only do it in case of a miss. result = Lookup(key); } return result; } void IdentityMapBase::Rehash() { // Record the current GC counter. gc_counter_ = heap_->gc_count(); // Assume that most objects won't be moved. ZoneVector<std::pair<Object*, void*>> reinsert(zone_); // Search the table looking for keys that wouldn't be found with their // current hashcode and evacuate them. int last_empty = -1; Object* not_mapped = heap_->not_mapped_symbol(); for (int i = 0; i < size_; i++) { if (keys_[i] == not_mapped) { last_empty = i; } else { int pos = Hash(keys_[i]) & mask_; if (pos <= last_empty || pos > i) { // Evacuate an entry that is in the wrong place. reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i])); keys_[i] = not_mapped; values_[i] = nullptr; last_empty = i; } } } // Reinsert all the key/value pairs that were in the wrong place. for (auto pair : reinsert) { int index = InsertIndex(pair.first); DCHECK_GE(index, 0); DCHECK_NE(heap_->not_mapped_symbol(), values_[index]); values_[index] = pair.second; } } void IdentityMapBase::Resize() { // Grow the internal storage and reinsert all the key/value pairs. int old_size = size_; Object** old_keys = keys_; void** old_values = values_; size_ = size_ * kResizeFactor; mask_ = size_ - 1; gc_counter_ = heap_->gc_count(); CHECK_LE(size_, (1024 * 1024 * 16)); // that would be extreme... keys_ = zone_->NewArray<Object*>(size_); Object* not_mapped = heap_->not_mapped_symbol(); for (int i = 0; i < size_; i++) keys_[i] = not_mapped; values_ = zone_->NewArray<void*>(size_); memset(values_, 0, sizeof(void*) * size_); for (int i = 0; i < old_size; i++) { if (old_keys[i] == not_mapped) continue; int index = InsertIndex(old_keys[i]); DCHECK_GE(index, 0); values_[index] = old_values[i]; } // Unregister old keys and register new keys. heap_->UnregisterStrongRoots(old_keys); heap_->RegisterStrongRoots(keys_, keys_ + size_); } } // namespace internal } // namespace v8