identity-map.cc 10.9 KB
Newer Older
1 2 3 4
// 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.

5
#include "src/utils/identity-map.h"
6

7
#include "src/base/functional.h"
8
#include "src/base/logging.h"
9
#include "src/heap/heap.h"
10
#include "src/roots/roots-inl.h"
11 12 13 14 15

namespace v8 {
namespace internal {

static const int kInitialIdentityMapSize = 4;
16
static const int kResizeFactor = 2;
17

18 19 20 21 22
IdentityMapBase::~IdentityMapBase() {
  // Clear must be called by the subclass to avoid calling the virtual
  // DeleteArray function from the destructor.
  DCHECK_NULL(keys_);
}
23 24 25

void IdentityMapBase::Clear() {
  if (keys_) {
26
    DCHECK(!is_iterable());
27 28
    DCHECK_NOT_NULL(strong_roots_entry_);
    heap_->UnregisterStrongRoots(strong_roots_entry_);
29
    DeletePointerArray(reinterpret_cast<uintptr_t*>(keys_), capacity_);
30
    DeletePointerArray(values_, capacity_);
31
    keys_ = nullptr;
32
    strong_roots_entry_ = nullptr;
33 34
    values_ = nullptr;
    size_ = 0;
35
    capacity_ = 0;
36 37
    mask_ = 0;
  }
38 39
}

40 41 42
void IdentityMapBase::EnableIteration() {
  CHECK(!is_iterable());
  is_iterable_ = true;
43 44
}

45 46 47
void IdentityMapBase::DisableIteration() {
  CHECK(is_iterable());
  is_iterable_ = false;
48 49
}

50 51
int IdentityMapBase::ScanKeysFor(Address address, uint32_t hash) const {
  int start = hash & mask_;
52
  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
53
  for (int index = start; index < capacity_; index++) {
54
    if (keys_[index] == address) return index;  // Found.
55
    if (keys_[index] == not_mapped) return -1;  // Not found.
56 57 58
  }
  for (int index = 0; index < start; index++) {
    if (keys_[index] == address) return index;  // Found.
59
    if (keys_[index] == not_mapped) return -1;  // Not found.
60 61 62 63
  }
  return -1;
}

64 65 66 67 68 69 70 71 72
std::pair<int, bool> IdentityMapBase::InsertKey(Address address,
                                                uint32_t hash) {
  DCHECK_EQ(gc_counter_, heap_->gc_count());

  // Grow the map if we reached >= 80% occupancy.
  if (size_ + size_ / 4 >= capacity_) {
    Resize(capacity_ * kResizeFactor);
  }

73
  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
74 75 76 77 78

  int start = hash & mask_;
  // Guaranteed to terminate since size_ < capacity_, there must be at least
  // one empty slot.
  int index = start;
79
  while (true) {
80 81 82 83 84 85
    if (keys_[index] == address) return {index, true};  // Found.
    if (keys_[index] == not_mapped) {                   // Free entry.
      size_++;
      DCHECK_LE(size_, capacity_);
      keys_[index] = address;
      return {index, false};
86
    }
87 88 89
    index = (index + 1) & mask_;
    // We should never loop back to the start.
    DCHECK_NE(index, start);
90 91 92
  }
}

93
bool IdentityMapBase::DeleteIndex(int index, uintptr_t* deleted_value) {
94
  if (deleted_value != nullptr) *deleted_value = values_[index];
95
  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
96 97
  DCHECK_NE(keys_[index], not_mapped);
  keys_[index] = not_mapped;
98
  values_[index] = 0;
99 100 101
  size_--;
  DCHECK_GE(size_, 0);

102 103
  if (capacity_ > kInitialIdentityMapSize &&
      size_ * kResizeFactor < capacity_ / kResizeFactor) {
104
    Resize(capacity_ / kResizeFactor);
105
    return true;  // No need to fix collisions as resize reinserts keys.
106 107 108 109 110 111
  }

  // Move any collisions to their new correct location.
  int next_index = index;
  for (;;) {
    next_index = (next_index + 1) & mask_;
112
    Address key = keys_[next_index];
113 114 115 116 117 118 119 120 121
    if (key == not_mapped) break;

    int expected_index = Hash(key) & mask_;
    if (index < next_index) {
      if (index < expected_index && expected_index <= next_index) continue;
    } else {
      DCHECK_GT(index, next_index);
      if (index < expected_index || expected_index <= next_index) continue;
    }
122

123
    DCHECK_EQ(not_mapped, keys_[index]);
124
    DCHECK_EQ(values_[index], 0);
125 126 127 128 129
    std::swap(keys_[index], keys_[next_index]);
    std::swap(values_[index], values_[next_index]);
    index = next_index;
  }

130
  return true;
131 132
}

133
int IdentityMapBase::Lookup(Address key) const {
134 135
  uint32_t hash = Hash(key);
  int index = ScanKeysFor(key, hash);
136 137 138
  if (index < 0 && gc_counter_ != heap_->gc_count()) {
    // Miss; rehash if there was a GC, then lookup again.
    const_cast<IdentityMapBase*>(this)->Rehash();
139
    index = ScanKeysFor(key, hash);
140 141 142 143
  }
  return index;
}

144 145
std::pair<int, bool> IdentityMapBase::LookupOrInsert(Address key) {
  uint32_t hash = Hash(key);
146
  // Perform an optimistic lookup.
147 148
  int index = ScanKeysFor(key, hash);
  bool already_exists;
149 150 151
  if (index < 0) {
    // Miss; rehash if there was a GC, then insert.
    if (gc_counter_ != heap_->gc_count()) Rehash();
152 153 154
    std::tie(index, already_exists) = InsertKey(key, hash);
  } else {
    already_exists = true;
155 156
  }
  DCHECK_GE(index, 0);
157
  return {index, already_exists};
158 159
}

160
uint32_t IdentityMapBase::Hash(Address address) const {
161
  CHECK_NE(address, ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
162
  return static_cast<uint32_t>(hasher_(address));
163 164 165 166
}

// Searches this map for the given key using the object's address
// as the identity, returning:
167 168 169 170
//    found => a pointer to the storage location for the value, true
//    not found => a pointer to a new storage location for the value, false
IdentityMapFindResult<uintptr_t> IdentityMapBase::FindOrInsertEntry(
    Address key) {
171
  CHECK(!is_iterable());  // Don't allow insertion while iterable.
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
  if (capacity_ == 0) {
    return {InsertEntry(key), false};
  }
  auto lookup_result = LookupOrInsert(key);
  return {&values_[lookup_result.first], lookup_result.second};
}

// 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(Address key) const {
  // Don't allow find by key while iterable (might rehash).
  CHECK(!is_iterable());
  if (size_ == 0) return nullptr;
  int index = Lookup(key);
  return index >= 0 ? &values_[index] : nullptr;
}

// Inserts the given key using the object's address as the identity, returning
// a pointer to the new storage location for the value.
IdentityMapBase::RawEntry IdentityMapBase::InsertEntry(Address key) {
  // Don't allow find by key while iterable (might rehash).
  CHECK(!is_iterable());
196
  if (capacity_ == 0) {
197
    // Allocate the initial storage for keys and values.
198
    capacity_ = kInitialIdentityMapSize;
199 200 201
    mask_ = kInitialIdentityMapSize - 1;
    gc_counter_ = heap_->gc_count();

202
    keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
203
    Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
204 205
    for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
    values_ = NewPointerArray(capacity_);
206
    memset(values_, 0, sizeof(uintptr_t) * capacity_);
207

208 209 210
    strong_roots_entry_ =
        heap_->RegisterStrongRoots("IdentityMapBase", FullObjectSlot(keys_),
                                   FullObjectSlot(keys_ + capacity_));
211 212 213
  } else {
    // Rehash if there was a GC, then insert.
    if (gc_counter_ != heap_->gc_count()) Rehash();
214 215
  }

216 217 218 219 220
  int index;
  bool already_exists;
  std::tie(index, already_exists) = InsertKey(key, Hash(key));
  DCHECK(!already_exists);
  return &values_[index];
221 222
}

223
// Deletes the given key from the map using the object's address as the
224 225
// identity, returning true iff the key was found (in which case, the value
// argument will be set to the deleted entry's value).
226
bool IdentityMapBase::DeleteEntry(Address key, uintptr_t* deleted_value) {
227
  CHECK(!is_iterable());  // Don't allow deletion by key while iterable.
228
  if (size_ == 0) return false;
229
  int index = Lookup(key);
230 231
  if (index < 0) return false;  // No entry found.
  return DeleteIndex(index, deleted_value);
232 233
}

234
Address IdentityMapBase::KeyAtIndex(int index) const {
235 236
  DCHECK_LE(0, index);
  DCHECK_LT(index, capacity_);
237
  DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
238 239 240 241
  CHECK(is_iterable());  // Must be iterable to access by index;
  return keys_[index];
}

242 243 244
IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const {
  DCHECK_LE(0, index);
  DCHECK_LT(index, capacity_);
245
  DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
246 247 248 249 250 251 252 253
  CHECK(is_iterable());  // Must be iterable to access by index;
  return &values_[index];
}

int IdentityMapBase::NextIndex(int index) const {
  DCHECK_LE(-1, index);
  DCHECK_LE(index, capacity_);
  CHECK(is_iterable());  // Must be iterable to access by index;
254
  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
255
  for (++index; index < capacity_; ++index) {
256 257 258 259 260 261
    if (keys_[index] != not_mapped) {
      return index;
    }
  }
  return capacity_;
}
262 263

void IdentityMapBase::Rehash() {
264
  CHECK(!is_iterable());  // Can't rehash while iterating.
265 266 267
  // Record the current GC counter.
  gc_counter_ = heap_->gc_count();
  // Assume that most objects won't be moved.
268
  std::vector<std::pair<Address, uintptr_t>> reinsert;
269 270 271
  // Search the table looking for keys that wouldn't be found with their
  // current hashcode and evacuate them.
  int last_empty = -1;
272
  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
273
  for (int i = 0; i < capacity_; i++) {
274
    if (keys_[i] == not_mapped) {
275 276 277 278 279
      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.
280
        reinsert.push_back(std::pair<Address, uintptr_t>(keys_[i], values_[i]));
281
        keys_[i] = not_mapped;
282
        values_[i] = 0;
283
        last_empty = i;
284
        size_--;
285 286 287 288 289
      }
    }
  }
  // Reinsert all the key/value pairs that were in the wrong place.
  for (auto pair : reinsert) {
290
    int index = InsertKey(pair.first, Hash(pair.first)).first;
291 292 293 294 295
    DCHECK_GE(index, 0);
    values_[index] = pair.second;
  }
}

296 297 298 299 300
void IdentityMapBase::Resize(int new_capacity) {
  CHECK(!is_iterable());  // Can't resize while iterating.
  // Resize the internal storage and reinsert all the key/value pairs.
  DCHECK_GT(new_capacity, size_);
  int old_capacity = capacity_;
301
  Address* old_keys = keys_;
302
  uintptr_t* old_values = values_;
303

304 305
  capacity_ = new_capacity;
  mask_ = capacity_ - 1;
306
  gc_counter_ = heap_->gc_count();
307
  size_ = 0;
308

309
  keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
310
  Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
311 312
  for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
  values_ = NewPointerArray(capacity_);
313
  memset(values_, 0, sizeof(uintptr_t) * capacity_);
314

315
  for (int i = 0; i < old_capacity; i++) {
316
    if (old_keys[i] == not_mapped) continue;
317
    int index = InsertKey(old_keys[i], Hash(old_keys[i])).first;
318 319 320 321 322
    DCHECK_GE(index, 0);
    values_[index] = old_values[i];
  }

  // Unregister old keys and register new keys.
323 324 325
  DCHECK_NOT_NULL(strong_roots_entry_);
  heap_->UpdateStrongRoots(strong_roots_entry_, FullObjectSlot(keys_),
                           FullObjectSlot(keys_ + capacity_));
326 327

  // Delete old storage;
328
  DeletePointerArray(reinterpret_cast<uintptr_t*>(old_keys), old_capacity);
329
  DeletePointerArray(old_values, old_capacity);
330
}
331

332 333
}  // namespace internal
}  // namespace v8