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

src/heap/identity-map.h

+// 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.
+
+#ifndef V8_HEAP_IDENTITY_MAP_H_
+#define V8_HEAP_IDENTITY_MAP_H_
+
+#include "src/handles.h"
+
+namespace v8 {
+namespace internal {
+
+class Heap;
+
+// Base class of identity maps contains shared code for all template
+// instantions.
+class IdentityMapBase {
+ public:
+  // Enable or disable concurrent mode for this map. Concurrent mode implies
+  // taking the heap's relocation lock during most operations.
+  void SetConcurrent(bool concurrent) { concurrent_ = concurrent; }
+
+ protected:
+  // Allow Tester to access internals, including changing the address of objects
+  // within the {keys_} array in order to simulate a moving GC.
+  friend class IdentityMapTester;
+
+  typedef void** RawEntry;
+
+  IdentityMapBase(Heap* heap, Zone* zone)
+      : heap_(heap),
+        zone_(zone),
+        concurrent_(false),
+        gc_counter_(-1),
+        size_(0),
+        mask_(0),
+        keys_(nullptr),
+        values_(nullptr) {}
+  ~IdentityMapBase();
+
+  RawEntry GetEntry(Handle<Object> key);
+  RawEntry FindEntry(Handle<Object> key);
+
+ private:
+  // Internal implementation should not be called directly by subclasses.
+  int LookupIndex(Object* address);
+  int InsertIndex(Object* address);
+  void Rehash();
+  void Resize();
+  RawEntry Lookup(Handle<Object> key);
+  RawEntry Insert(Handle<Object> key);
+  int Hash(Object* address);
+
+  Heap* heap_;
+  Zone* zone_;
+  bool concurrent_;
+  int gc_counter_;
+  int size_;
+  int mask_;
+  Object** keys_;
+  void** values_;
+};
+
+// Implements an identity map from object addresses to a given value type {V}.
+// The value type {V} must be reinterpret_cast'able to void*.
+// The map is robust w.r.t. garbage collection through coordination with the
+// supplied {heap}.
+// Note that in general, SMIs are valid keys, but {SMI #0} is _not_ a valid key.
+template <typename V>
+class IdentityMap : public IdentityMapBase {
+ public:
+  IdentityMap(Heap* heap, Zone* zone) : IdentityMapBase(heap, zone) {}
+
+  // 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
+  V* Get(Handle<Object> key) { return reinterpret_cast<V*>(GetEntry(key)); }
+
+  // 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}
+  V* Find(Handle<Object> key) { return reinterpret_cast<V*>(FindEntry(key)); }
+
+  // Set the value for the given key.
+  void Set(Handle<Object> key, V value) {
+    *(reinterpret_cast<V*>(GetEntry(key))) = value;

[Erik Corry, 2015/04/28 13:51:16]

This assignment takes place without holding the lock, but outside the lock,
things can move around.  You could be writing in the old version.

Similar issues with Find and Get.  They are returning pointers into the values
array, which the caller can use without holding the lock.

+  }
+};
+}
+}  // namespace v8::internal
+
+#endif  // V8_HEAP_IDENTITY_MAP_H_