Home | History | Annotate | Download | only in src 
      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 
      7 #include "src/base/functional.h"
      8 #include "src/heap/heap-inl.h"
      9 
     10 namespace v8 {
     11 namespace internal {
     12 
     13 static const int kInitialIdentityMapSize = 4;
     14 static const int kResizeFactor = 2;
     15 
     16 IdentityMapBase::~IdentityMapBase() {
     17   // Clear must be called by the subclass to avoid calling the virtual
     18   // DeleteArray function from the destructor.
     19   DCHECK_NULL(keys_);
     20 }
     21 
     22 void IdentityMapBase::Clear() {
     23   if (keys_) {
     24     DCHECK(!is_iterable());
     25     heap_->UnregisterStrongRoots(keys_);
     26     DeleteArray(keys_);
     27     DeleteArray(values_);
     28     keys_ = nullptr;
     29     values_ = nullptr;
     30     size_ = 0;
     31     capacity_ = 0;
     32     mask_ = 0;
     33   }
     34 }
     35 
     36 void IdentityMapBase::EnableIteration() {
     37   CHECK(!is_iterable());
     38   is_iterable_ = true;
     39 }
     40 
     41 void IdentityMapBase::DisableIteration() {
     42   CHECK(is_iterable());
     43   is_iterable_ = false;
     44 }
     45 
     46 int IdentityMapBase::ScanKeysFor(Object* address) const {
     47   int start = Hash(address) & mask_;
     48   Object* not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol();
     49   for (int index = start; index < capacity_; index++) {
     50     if (keys_[index] == address) return index;  // Found.
     51     if (keys_[index] == not_mapped) return -1;  // Not found.
     52   }
     53   for (int index = 0; index < start; index++) {
     54     if (keys_[index] == address) return index;  // Found.
     55     if (keys_[index] == not_mapped) return -1;  // Not found.
     56   }
     57   return -1;
     58 }
     59 
     60 int IdentityMapBase::InsertKey(Object* address) {
     61   Object* not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol();
     62   while (true) {
     63     int start = Hash(address) & mask_;
     64     int limit = capacity_ / 2;
     65     // Search up to {limit} entries.
     66     for (int index = start; --limit > 0; index = (index + 1) & mask_) {
     67       if (keys_[index] == address) return index;  // Found.
     68       if (keys_[index] == not_mapped) {           // Free entry.
     69         size_++;
     70         DCHECK_LE(size_, capacity_);
     71         keys_[index] = address;
     72         return index;
     73       }
     74     }
     75     // Should only have to resize once, since we grow 4x.
     76     Resize(capacity_ * kResizeFactor);
     77   }
     78   UNREACHABLE();
     79 }
     80 
     81 bool IdentityMapBase::DeleteIndex(int index, void** deleted_value) {
     82   if (deleted_value != nullptr) *deleted_value = values_[index];
     83   Object* not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol();
     84   DCHECK_NE(keys_[index], not_mapped);
     85   keys_[index] = not_mapped;
     86   values_[index] = nullptr;
     87   size_--;
     88   DCHECK_GE(size_, 0);
     89 
     90   if (capacity_ > kInitialIdentityMapSize &&
     91       size_ * kResizeFactor < capacity_ / kResizeFactor) {
     92     Resize(capacity_ / kResizeFactor);
     93     return true;  // No need to fix collisions as resize reinserts keys.
     94   }
     95 
     96   // Move any collisions to their new correct location.
     97   int next_index = index;
     98   for (;;) {
     99     next_index = (next_index + 1) & mask_;
    100     Object* key = keys_[next_index];
    101     if (key == not_mapped) break;
    102 
    103     int expected_index = Hash(key) & mask_;
    104     if (index < next_index) {
    105       if (index < expected_index && expected_index <= next_index) continue;
    106     } else {
    107       DCHECK_GT(index, next_index);
    108       if (index < expected_index || expected_index <= next_index) continue;
    109     }
    110 
    111     DCHECK_EQ(not_mapped, keys_[index]);
    112     DCHECK_NULL(values_[index]);
    113     std::swap(keys_[index], keys_[next_index]);
    114     std::swap(values_[index], values_[next_index]);
    115     index = next_index;
    116   }
    117 
    118   return true;
    119 }
    120 
    121 int IdentityMapBase::Lookup(Object* key) const {
    122   int index = ScanKeysFor(key);
    123   if (index < 0 && gc_counter_ != heap_->gc_count()) {
    124     // Miss; rehash if there was a GC, then lookup again.
    125     const_cast<IdentityMapBase*>(this)->Rehash();
    126     index = ScanKeysFor(key);
    127   }
    128   return index;
    129 }
    130 
    131 int IdentityMapBase::LookupOrInsert(Object* key) {
    132   // Perform an optimistic lookup.
    133   int index = ScanKeysFor(key);
    134   if (index < 0) {
    135     // Miss; rehash if there was a GC, then insert.
    136     if (gc_counter_ != heap_->gc_count()) Rehash();
    137     index = InsertKey(key);
    138   }
    139   DCHECK_GE(index, 0);
    140   return index;
    141 }
    142 
    143 int IdentityMapBase::Hash(Object* address) const {
    144   CHECK_NE(address, ReadOnlyRoots(heap_).not_mapped_symbol());
    145   uintptr_t raw_address = reinterpret_cast<uintptr_t>(address);
    146   return static_cast<int>(hasher_(raw_address));
    147 }
    148 
    149 // Searches this map for the given key using the object's address
    150 // as the identity, returning:
    151 //    found => a pointer to the storage location for the value
    152 //    not found => a pointer to a new storage location for the value
    153 IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Object* key) {
    154   CHECK(!is_iterable());  // Don't allow insertion while iterable.
    155   if (capacity_ == 0) {
    156     // Allocate the initial storage for keys and values.
    157     capacity_ = kInitialIdentityMapSize;
    158     mask_ = kInitialIdentityMapSize - 1;
    159     gc_counter_ = heap_->gc_count();
    160 
    161     keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
    162     Object* not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol();
    163     for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
    164     values_ = NewPointerArray(capacity_);
    165     memset(values_, 0, sizeof(void*) * capacity_);
    166 
    167     heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
    168   }
    169   int index = LookupOrInsert(key);
    170   return &values_[index];
    171 }
    172 
    173 // Searches this map for the given key using the object's address
    174 // as the identity, returning:
    175 //    found => a pointer to the storage location for the value
    176 //    not found => {nullptr}
    177 IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Object* key) const {
    178   // Don't allow find by key while iterable (might rehash).
    179   CHECK(!is_iterable());
    180   if (size_ == 0) return nullptr;
    181   // Remove constness since lookup might have to rehash.
    182   int index = Lookup(key);
    183   return index >= 0 ? &values_[index] : nullptr;
    184 }
    185 
    186 // Deletes the given key from the map using the object's address as the
    187 // identity, returning true iff the key was found (in which case, the value
    188 // argument will be set to the deleted entry's value).
    189 bool IdentityMapBase::DeleteEntry(Object* key, void** deleted_value) {
    190   CHECK(!is_iterable());  // Don't allow deletion by key while iterable.
    191   if (size_ == 0) return false;
    192   int index = Lookup(key);
    193   if (index < 0) return false;  // No entry found.
    194   return DeleteIndex(index, deleted_value);
    195 }
    196 
    197 Object* IdentityMapBase::KeyAtIndex(int index) const {
    198   DCHECK_LE(0, index);
    199   DCHECK_LT(index, capacity_);
    200   DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol());
    201   CHECK(is_iterable());  // Must be iterable to access by index;
    202   return keys_[index];
    203 }
    204 
    205 IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const {
    206   DCHECK_LE(0, index);
    207   DCHECK_LT(index, capacity_);
    208   DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol());
    209   CHECK(is_iterable());  // Must be iterable to access by index;
    210   return &values_[index];
    211 }
    212 
    213 int IdentityMapBase::NextIndex(int index) const {
    214   DCHECK_LE(-1, index);
    215   DCHECK_LE(index, capacity_);
    216   CHECK(is_iterable());  // Must be iterable to access by index;
    217   Object* not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol();
    218   for (++index; index < capacity_; ++index) {
    219     if (keys_[index] != not_mapped) {
    220       return index;
    221     }
    222   }
    223   return capacity_;
    224 }
    225 
    226 void IdentityMapBase::Rehash() {
    227   CHECK(!is_iterable());  // Can't rehash while iterating.
    228   // Record the current GC counter.
    229   gc_counter_ = heap_->gc_count();
    230   // Assume that most objects won't be moved.
    231   std::vector<std::pair<Object*, void*>> reinsert;
    232   // Search the table looking for keys that wouldn't be found with their
    233   // current hashcode and evacuate them.
    234   int last_empty = -1;
    235   Object* not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol();
    236   for (int i = 0; i < capacity_; i++) {
    237     if (keys_[i] == not_mapped) {
    238       last_empty = i;
    239     } else {
    240       int pos = Hash(keys_[i]) & mask_;
    241       if (pos <= last_empty || pos > i) {
    242         // Evacuate an entry that is in the wrong place.
    243         reinsert.push_back(std::pair<Object*, void*>(keys_[i], values_[i]));
    244         keys_[i] = not_mapped;
    245         values_[i] = nullptr;
    246         last_empty = i;
    247         size_--;
    248       }
    249     }
    250   }
    251   // Reinsert all the key/value pairs that were in the wrong place.
    252   for (auto pair : reinsert) {
    253     int index = InsertKey(pair.first);
    254     DCHECK_GE(index, 0);
    255     values_[index] = pair.second;
    256   }
    257 }
    258 
    259 void IdentityMapBase::Resize(int new_capacity) {
    260   CHECK(!is_iterable());  // Can't resize while iterating.
    261   // Resize the internal storage and reinsert all the key/value pairs.
    262   DCHECK_GT(new_capacity, size_);
    263   int old_capacity = capacity_;
    264   Object** old_keys = keys_;
    265   void** old_values = values_;
    266 
    267   capacity_ = new_capacity;
    268   mask_ = capacity_ - 1;
    269   gc_counter_ = heap_->gc_count();
    270   size_ = 0;
    271 
    272   keys_ = reinterpret_cast<Object**>(NewPointerArray(capacity_));
    273   Object* not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol();
    274   for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
    275   values_ = NewPointerArray(capacity_);
    276   memset(values_, 0, sizeof(void*) * capacity_);
    277 
    278   for (int i = 0; i < old_capacity; i++) {
    279     if (old_keys[i] == not_mapped) continue;
    280     int index = InsertKey(old_keys[i]);
    281     DCHECK_GE(index, 0);
    282     values_[index] = old_values[i];
    283   }
    284 
    285   // Unregister old keys and register new keys.
    286   heap_->UnregisterStrongRoots(old_keys);
    287   heap_->RegisterStrongRoots(keys_, keys_ + capacity_);
    288 
    289   // Delete old storage;
    290   DeleteArray(old_keys);
    291   DeleteArray(old_values);
    292 }
    293 
    294 }  // namespace internal
    295 }  // namespace v8
    296