Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 7 | #include "src/base/functional.h" |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 17 | IdentityMapBase::~IdentityMapBase() { Clear(); } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 18 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 45 | return static_cast<int>(hasher_(raw_address)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 |