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 #include "src/zone-containers.h" 10 11 namespace v8 { 12 namespace internal { 13 14 static const int kInitialIdentityMapSize = 4; 15 static const int kResizeFactor = 4; 16 17 IdentityMapBase::~IdentityMapBase() { Clear(); } 18 19 void IdentityMapBase::Clear() { 20 if (keys_) { 21 heap_->UnregisterStrongRoots(keys_); 22 keys_ = nullptr; 23 values_ = nullptr; 24 size_ = 0; 25 mask_ = 0; 26 } 27 } 28 29 IdentityMapBase::RawEntry IdentityMapBase::Lookup(Object* key) { 30 int index = LookupIndex(key); 31 return index >= 0 ? &values_[index] : nullptr; 32 } 33 34 35 IdentityMapBase::RawEntry IdentityMapBase::Insert(Object* key) { 36 int index = InsertIndex(key); 37 DCHECK_GE(index, 0); 38 return &values_[index]; 39 } 40 41 42 int IdentityMapBase::Hash(Object* address) { 43 CHECK_NE(address, heap_->not_mapped_symbol()); 44 uintptr_t raw_address = reinterpret_cast<uintptr_t>(address); 45 return static_cast<int>(hasher_(raw_address)); 46 } 47 48 49 int IdentityMapBase::LookupIndex(Object* address) { 50 int start = Hash(address) & mask_; 51 Object* not_mapped = heap_->not_mapped_symbol(); 52 for (int index = start; index < size_; index++) { 53 if (keys_[index] == address) return index; // Found. 54 if (keys_[index] == not_mapped) return -1; // Not found. 55 } 56 for (int index = 0; index < start; index++) { 57 if (keys_[index] == address) return index; // Found. 58 if (keys_[index] == not_mapped) return -1; // Not found. 59 } 60 return -1; 61 } 62 63 64 int IdentityMapBase::InsertIndex(Object* address) { 65 Object* not_mapped = heap_->not_mapped_symbol(); 66 while (true) { 67 int start = Hash(address) & mask_; 68 int limit = size_ / 2; 69 // Search up to {limit} entries. 70 for (int index = start; --limit > 0; index = (index + 1) & mask_) { 71 if (keys_[index] == address) return index; // Found. 72 if (keys_[index] == not_mapped) { // Free entry. 73 keys_[index] = address; 74 return index; 75 } 76 } 77 Resize(); // Should only have to resize once, since we grow 4x. 78 } 79 UNREACHABLE(); 80 return -1; 81 } 82 83 84 // Searches this map for the given key using the object's address 85 // as the identity, returning: 86 // found => a pointer to the storage location for the value 87 // not found => a pointer to a new storage location for the value 88 IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) { 89 RawEntry result; 90 if (size_ == 0) { 91 // Allocate the initial storage for keys and values. 92 size_ = kInitialIdentityMapSize; 93 mask_ = kInitialIdentityMapSize - 1; 94 gc_counter_ = heap_->gc_count(); 95 96 keys_ = zone_->NewArray<Object*>(size_); 97 Object* not_mapped = heap_->not_mapped_symbol(); 98 for (int i = 0; i < size_; i++) keys_[i] = not_mapped; 99 values_ = zone_->NewArray<void*>(size_); 100 memset(values_, 0, sizeof(void*) * size_); 101 102 heap_->RegisterStrongRoots(keys_, keys_ + size_); 103 result = Insert(key); 104 } else { 105 // Perform an optimistic lookup. 106 result = Lookup(key); 107 if (result == nullptr) { 108 // Miss; rehash if there was a GC, then insert. 109 if (gc_counter_ != heap_->gc_count()) Rehash(); 110 result = Insert(key); 111 } 112 } 113 return result; 114 } 115 116 117 // Searches this map for the given key using the object's address 118 // as the identity, returning: 119 // found => a pointer to the storage location for the value 120 // not found => {nullptr} 121 IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) { 122 if (size_ == 0) return nullptr; 123 124 RawEntry result = Lookup(key); 125 if (result == nullptr && gc_counter_ != heap_->gc_count()) { 126 Rehash(); // Rehash is expensive, so only do it in case of a miss. 127 result = Lookup(key); 128 } 129 return result; 130 } 131 132 133 void IdentityMapBase::Rehash() { 134 // Record the current GC counter. 135 gc_counter_ = heap_->gc_count(); 136 // Assume that most objects won't be moved. 137 ZoneVector<std::pair<Object*, void*>> reinsert(zone_); 138 // Search the table looking for keys that wouldn't be found with their 139 // current hashcode and evacuate them. 140 int last_empty = -1; 141 Object* not_mapped = heap_->not_mapped_symbol(); 142 for (int i = 0; i < size_; i++) { 143 if (keys_[i] == not_mapped) { 144 last_empty = i; 145 } else { 146 int pos = Hash(keys_[i]) & mask_; 147 if (pos <= last_empty || pos > i) { 148 // Evacuate an entry that is in the wrong place. 149 reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i])); 150 keys_[i] = not_mapped; 151 values_[i] = nullptr; 152 last_empty = i; 153 } 154 } 155 } 156 // Reinsert all the key/value pairs that were in the wrong place. 157 for (auto pair : reinsert) { 158 int index = InsertIndex(pair.first); 159 DCHECK_GE(index, 0); 160 DCHECK_NE(heap_->not_mapped_symbol(), values_[index]); 161 values_[index] = pair.second; 162 } 163 } 164 165 166 void IdentityMapBase::Resize() { 167 // Grow the internal storage and reinsert all the key/value pairs. 168 int old_size = size_; 169 Object** old_keys = keys_; 170 void** old_values = values_; 171 172 size_ = size_ * kResizeFactor; 173 mask_ = size_ - 1; 174 gc_counter_ = heap_->gc_count(); 175 176 CHECK_LE(size_, (1024 * 1024 * 16)); // that would be extreme... 177 178 keys_ = zone_->NewArray<Object*>(size_); 179 Object* not_mapped = heap_->not_mapped_symbol(); 180 for (int i = 0; i < size_; i++) keys_[i] = not_mapped; 181 values_ = zone_->NewArray<void*>(size_); 182 memset(values_, 0, sizeof(void*) * size_); 183 184 for (int i = 0; i < old_size; i++) { 185 if (old_keys[i] == not_mapped) continue; 186 int index = InsertIndex(old_keys[i]); 187 DCHECK_GE(index, 0); 188 values_[index] = old_values[i]; 189 } 190 191 // Unregister old keys and register new keys. 192 heap_->UnregisterStrongRoots(old_keys); 193 heap_->RegisterStrongRoots(keys_, keys_ + size_); 194 } 195 } // namespace internal 196 } // namespace v8 197
