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

          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      589502 : 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      589502 : }
      22             : 
      23      652458 : void IdentityMapBase::Clear() {
      24      652458 :   if (keys_) {
      25             :     DCHECK(!is_iterable());
      26      517892 :     heap_->UnregisterStrongRoots(FullObjectSlot(keys_));
      27      517897 :     DeleteArray(keys_);
      28      517892 :     DeleteArray(values_);
      29      517893 :     keys_ = nullptr;
      30      517893 :     values_ = nullptr;
      31      517893 :     size_ = 0;
      32      517893 :     capacity_ = 0;
      33      517893 :     mask_ = 0;
      34             :   }
      35      652459 : }
      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   122178850 : int IdentityMapBase::ScanKeysFor(Address address) const {
      48   122178850 :   int start = Hash(address) & mask_;
      49   122178817 :   Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
      50   609792652 :   for (int index = start; index < capacity_; index++) {
      51   605319690 :     if (keys_[index] == address) return index;  // Found.
      52   549553895 :     if (keys_[index] == not_mapped) return -1;  // Not found.
      53             :   }
      54    40522803 :   for (int index = 0; index < start; index++) {
      55    44661633 :     if (keys_[index] == address) return index;  // Found.
      56    44099849 :     if (keys_[index] == not_mapped) return -1;  // Not found.
      57             :   }
      58             :   return -1;
      59             : }
      60             : 
      61   172792307 : int IdentityMapBase::InsertKey(Address address) {
      62   172792307 :   Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
      63             :   while (true) {
      64   175600386 :     int start = Hash(address) & mask_;
      65   175598511 :     int limit = capacity_ / 2;
      66             :     // Search up to {limit} entries.
      67   629010293 :     for (int index = start; --limit > 0; index = (index + 1) & mask_) {
      68   626202290 :       if (keys_[index] == address) return index;  // Found.
      69   626204039 :       if (keys_[index] == not_mapped) {           // Free entry.
      70   172792257 :         size_++;
      71             :         DCHECK_LE(size_, capacity_);
      72   172792257 :         keys_[index] = address;
      73   172792257 :         return index;
      74             :       }
      75             :     }
      76             :     // Should only have to resize once, since we grow 4x.
      77     2808003 :     Resize(capacity_ * kResizeFactor);
      78             :   }
      79     2808003 :   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       20590 :   if (capacity_ > kInitialIdentityMapSize &&
      92       10270 :       size_ * kResizeFactor < capacity_ / kResizeFactor) {
      93         125 :     Resize(capacity_ / kResizeFactor);
      94         125 :     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       46815 :     next_index = (next_index + 1) & mask_;
     101       46815 :     Address key = keys_[next_index];
     102       46815 :     if (key == not_mapped) break;
     103             : 
     104       36620 :     int expected_index = Hash(key) & mask_;
     105       36620 :     if (index < next_index) {
     106       35755 :       if (index < expected_index && expected_index <= next_index) continue;
     107             :     } else {
     108             :       DCHECK_GT(index, next_index);
     109         865 :       if (index < expected_index || expected_index <= next_index) continue;
     110             :     }
     111             : 
     112             :     DCHECK_EQ(not_mapped, keys_[index]);
     113             :     DCHECK_NULL(values_[index]);
     114        8260 :     std::swap(keys_[index], keys_[next_index]);
     115        8260 :     std::swap(values_[index], values_[next_index]);
     116             :     index = next_index;
     117             :   }
     118             : 
     119             :   return true;
     120             : }
     121             : 
     122      188270 : int IdentityMapBase::Lookup(Address key) const {
     123      188270 :   int index = ScanKeysFor(key);
     124      263302 :   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      188270 :   return index;
     130             : }
     131             : 
     132   121990564 : int IdentityMapBase::LookupOrInsert(Address key) {
     133             :   // Perform an optimistic lookup.
     134   121990564 :   int index = ScanKeysFor(key);
     135   121990501 :   if (index < 0) {
     136             :     // Miss; rehash if there was a GC, then insert.
     137   131550258 :     if (gc_counter_ != heap_->gc_count()) Rehash();
     138    65775129 :     index = InsertKey(key);
     139             :   }
     140             :   DCHECK_GE(index, 0);
     141   121990470 :   return index;
     142             : }
     143             : 
     144   297819260 : int IdentityMapBase::Hash(Address address) const {
     145   595638943 :   CHECK_NE(address, ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
     146   297819651 :   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   121990545 : IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Address key) {
     154   121990545 :   CHECK(!is_iterable());  // Don't allow insertion while iterable.
     155   121990545 :   if (capacity_ == 0) {
     156             :     // Allocate the initial storage for keys and values.
     157      517891 :     capacity_ = kInitialIdentityMapSize;
     158      517891 :     mask_ = kInitialIdentityMapSize - 1;
     159     1035782 :     gc_counter_ = heap_->gc_count();
     160             : 
     161      517891 :     keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
     162      517897 :     Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
     163      517893 :     for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
     164      517893 :     values_ = NewPointerArray(capacity_);
     165      517892 :     memset(values_, 0, sizeof(void*) * capacity_);
     166             : 
     167             :     heap_->RegisterStrongRoots(FullObjectSlot(keys_),
     168     1035784 :                                FullObjectSlot(keys_ + capacity_));
     169             :   }
     170   121990549 :   int index = LookupOrInsert(key);
     171   121990528 :   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      165729 : IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Address key) const {
     179             :   // Don't allow find by key while iterable (might rehash).
     180      165729 :   CHECK(!is_iterable());
     181      165729 :   if (size_ == 0) return nullptr;
     182             :   // Remove constness since lookup might have to rehash.
     183      159414 :   int index = Lookup(key);
     184      159414 :   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      115592 : bool IdentityMapBase::DeleteEntry(Address key, void** deleted_value) {
     191      115592 :   CHECK(!is_iterable());  // Don't allow deletion by key while iterable.
     192      115592 :   if (size_ == 0) return false;
     193       28856 :   int index = Lookup(key);
     194       28856 :   if (index < 0) return false;  // No entry found.
     195       10320 :   return DeleteIndex(index, deleted_value);
     196             : }
     197             : 
     198       13104 : 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       13104 :   CHECK(is_iterable());  // Must be iterable to access by index;
     203       13104 :   return keys_[index];
     204             : }
     205             : 
     206       24654 : 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       24654 :   CHECK(is_iterable());  // Must be iterable to access by index;
     211       24654 :   return &values_[index];
     212             : }
     213             : 
     214       19045 : int IdentityMapBase::NextIndex(int index) const {
     215             :   DCHECK_LE(-1, index);
     216             :   DCHECK_LE(index, capacity_);
     217       19045 :   CHECK(is_iterable());  // Must be iterable to access by index;
     218       19045 :   Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
     219       25302 :   for (++index; index < capacity_; ++index) {
     220       25136 :     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        6942 :   for (int i = 0; i < capacity_; i++) {
     238        7312 :     if (keys_[i] == not_mapped) {
     239             :       last_empty = i;
     240             :     } else {
     241        4331 :       int pos = Hash(keys_[i]) & mask_;
     242        4331 :       if (pos <= last_empty || pos > i) {
     243             :         // Evacuate an entry that is in the wrong place.
     244        1128 :         reinsert.push_back(std::pair<Address, void*>(keys_[i], values_[i]));
     245         564 :         keys_[i] = not_mapped;
     246         564 :         values_[i] = nullptr;
     247             :         last_empty = i;
     248         564 :         size_--;
     249             :       }
     250             :     }
     251             :   }
     252             :   // Reinsert all the key/value pairs that were in the wrong place.
     253         952 :   for (auto pair : reinsert) {
     254         564 :     int index = InsertKey(pair.first);
     255             :     DCHECK_GE(index, 0);
     256         564 :     values_[index] = pair.second;
     257             :   }
     258         194 : }
     259             : 
     260     2808148 : void IdentityMapBase::Resize(int new_capacity) {
     261     2808148 :   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     2808148 :   int old_capacity = capacity_;
     265     2808148 :   Address* old_keys = keys_;
     266     2808148 :   void** old_values = values_;
     267             : 
     268     2808148 :   capacity_ = new_capacity;
     269     2808148 :   mask_ = capacity_ - 1;
     270     5616296 :   gc_counter_ = heap_->gc_count();
     271     2808148 :   size_ = 0;
     272             : 
     273     2808148 :   keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
     274     2808149 :   Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
     275     2808144 :   for (int i = 0; i < capacity_; i++) keys_[i] = not_mapped;
     276     2808144 :   values_ = NewPointerArray(capacity_);
     277     2808073 :   memset(values_, 0, sizeof(void*) * capacity_);
     278             : 
     279   120700854 :   for (int i = 0; i < old_capacity; i++) {
     280   117892706 :     if (old_keys[i] == not_mapped) continue;
     281   107016822 :     int index = InsertKey(old_keys[i]);
     282             :     DCHECK_GE(index, 0);
     283   107016897 :     values_[index] = old_values[i];
     284             :   }
     285             : 
     286             :   // Unregister old keys and register new keys.
     287     2808148 :   heap_->UnregisterStrongRoots(FullObjectSlot(old_keys));
     288             :   heap_->RegisterStrongRoots(FullObjectSlot(keys_),
     289     5616298 :                              FullObjectSlot(keys_ + capacity_));
     290             : 
     291             :   // Delete old storage;
     292     2808149 :   DeleteArray(old_keys);
     293     2808147 :   DeleteArray(old_values);
     294     2808147 : }
     295             : 
     296             : }  // namespace internal
     297      183867 : }  // namespace v8

Generated by: LCOV version 1.10