src/identity-map.cc

// 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