Implement IdentityMap<V>, a robust, GC-safe object-identity HashMap.

src/heap/identity-map.cc

Index: src/heap/identity-map.cc
diff --git a/src/heap/identity-map.cc b/src/heap/identity-map.cc
new file mode 100644
index 0000000000000000000000000000000000000000..6bed98dfaac6ba2f67fcddbb14c24ef95b009496
--- /dev/null
+++ b/src/heap/identity-map.cc
@@ -0,0 +1,190 @@
+// 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/v8.h"
+
+#include "src/heap/heap.h"
+#include "src/heap/identity-map.h"
+
+namespace v8 {
+namespace internal {
+
+static const int kInitialIdentityMapSize = 32;
+
+IdentityMapBase::~IdentityMapBase() {
+  if (keys_) {
+    Heap::OptionalRelocationLock lock(heap_, concurrent_);
+    heap_->UnregisterStrongRoots(keys_);
+  }
+}
+
+
+IdentityMapBase::RawEntry IdentityMapBase::Lookup(Handle<Object> handle) {
+  AllowHandleDereference for_lookup;
+  int index = LookupIndex(*handle);
+  return index >= 0 ? &values_[index] : nullptr;
+}
+
+
+IdentityMapBase::RawEntry IdentityMapBase::Insert(Handle<Object> handle) {
+  AllowHandleDereference for_lookup;
+  int index = InsertIndex(*handle);
+  DCHECK_GE(index, 0);
+  return &values_[index];
+}
+
+
+int IdentityMapBase::Hash(Object* address) {
+  uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
+  CHECK_NE(0, raw_address);  // cannot store Smi 0 as a key here, sorry.

[Hannes Payer (out of office), 2015/04/27 15:06:32]

Cannot

[titzer, 2015/04/27 16:32:50]

Done.

+  // xor some of the upper bits, since the lower 2 or 3 are usually aligned.

[Erik Corry, 2015/04/27 15:39:13]

Xor

Also see comments below with missing caps and full stops (periods to you!)

[titzer, 2015/04/27 16:32:50]

Done.

+  return static_cast<int>((raw_address >> 11) ^ raw_address);
+}
+
+
+int IdentityMapBase::LookupIndex(Object* address) {
+  int start = Hash(address) & mask_;
+  for (int index = start; index < size_; index++) {
+    if (keys_[index] == address) return index;  // found
+    if (keys_[index] == nullptr) return -1;     // not found
+  }
+  for (int index = 0; index < start; index++) {
+    if (keys_[index] == address) return index;  // found
+    if (keys_[index] == nullptr) return -1;     // not found
+  }
+  return -1;
+}
+
+
+int IdentityMapBase::InsertIndex(Object* address) {
+  while (true) {
+    int start = Hash(address) & mask_;
+    int limit = size_ / 2;
+    for (int index = start; index < size_; index++) {

[Erik Corry, 2015/04/27 15:39:13]

For hashes that are near the end of the array we will resize immediately (by
4x!), rather than wrap around and search a bit more.

[titzer, 2015/04/27 16:32:51]

Good catch. I wrap the search now.

+      if (keys_[index] == address) return index;  // found
+      if (keys_[index] == nullptr) {              // free entry
+        keys_[index] = address;
+        return index;
+      }
+      if (--limit == 0) break;  // searched too far; resize to insert.

[Hannes Payer (out of office), 2015/04/27 15:06:32]

Searched

[titzer, 2015/04/27 16:32:51]

Done.

+    }
+    Resize();  // Should only have to resize once, since we grow 4x.

[Hannes Payer (out of office), 2015/04/27 15:06:32]

4 = kResizeFactor

[Erik Corry, 2015/04/27 15:39:13]

That's very aggressive.  Was 2x too slow?
Also this heuristic for growing will make the timing of the growing dependent on
ASLR, which is rather unpredictable for my taste.

[titzer, 2015/04/27 16:32:50]

4x guarantees that there are no chains that size_ / 2 the next time through the
loop, because now size_ is 4x as big.

The backstory here is that we expect these tables to be sparse and rather than
go for a complex hashing scheme, start with one that's much easier to get right.
Thus I wanted to avoid doing buckets and chains which would require a more
complex interface to the GC.

I considered doing cuckoo hashing (e.g. after a collision, use some more bits
from the hash for the next search location). Without any data about the
collision frequency, the complexity doesn't seem justified yet.

[Erik Corry, 2015/04/28 09:32:34]

Rather than cuckoo I would go with Robin Hood hashes, but I agree it's not
necessarily worth it.

+  }
+  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(Handle<Object> handle) {
+  Heap::OptionalRelocationLock lock(heap_, concurrent_);
+  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_);
+    memset(keys_, 0, sizeof(Object*) * size_);
+    values_ = zone_->NewArray<void*>(size_);
+    memset(values_, 0, sizeof(void*) * size_);
+
+    heap_->RegisterStrongRoots(keys_, keys_ + size_);
+    result = Insert(handle);
+  } else {
+    // Perform an optimistic lookup.
+    result = Lookup(handle);
+    if (result == nullptr) {
+      // Miss; rehash if there was a GC, then insert.
+      if (gc_counter_ != heap_->gc_count()) Rehash();
+      result = Insert(handle);
+    }
+  }
+  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(Handle<Object> handle) {
+  if (size_ == 0) return nullptr;
+
+  Heap::OptionalRelocationLock lock(heap_, concurrent_);
+  RawEntry result = Lookup(handle);
+  if (result == nullptr && gc_counter_ != heap_->gc_count()) {
+    Rehash();  // Rehash is expensive, so only do it in case of a miss.
+    result = Lookup(handle);
+  }
+  return result;
+}
+
+
+void IdentityMapBase::Rehash() {

[Hannes Payer (out of office), 2015/04/27 15:06:32]

Can we assert here that we have the relocation lock?

[titzer, 2015/04/27 16:32:50]

Unfortunately that API appears to have been refactored away...

+  // 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;
+  for (int i = 0; i < size_; i++) {
+    if (keys_[i] == nullptr) {
+      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] = nullptr;
+        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_NULL(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_ * 4;

[Hannes Payer (out of office), 2015/04/27 15:06:32]

4 = kResizeFactor; make this a constant

[titzer, 2015/04/27 16:32:50]

Done.

+  mask_ = size_ - 1;
+  gc_counter_ = heap_->gc_count();
+
+  CHECK_LE(size_, (1024 * 1024 * 16));  // that would be extreme...
+
+  keys_ = zone_->NewArray<Object*>(size_);
+  memset(keys_, 0, sizeof(Object*) * size_);
+  values_ = zone_->NewArray<void*>(size_);
+  memset(values_, 0, sizeof(void*) * size_);
+
+  for (int i = 0; i < old_size; i++) {
+    if (old_keys[i] == nullptr) 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 v8::internal