LCOV - code coverage report
Current view: top level - src - identity-map.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 153 153 100.0 %
Date: 2019-03-21 Functions: 19 20 95.0 %

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

Generated by: LCOV version 1.10