Line data    Source code

       1             : // Copyright 2012 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             : #ifndef V8_STUB_CACHE_H_
       6             : #define V8_STUB_CACHE_H_
       7             : 
       8             : #include "src/macro-assembler.h"
       9             : #include "src/objects/name.h"
      10             : 
      11             : namespace v8 {
      12             : namespace internal {
      13             : 
      14             : // The stub cache is used for megamorphic property accesses.
      15             : // It maps (map, name, type) to property access handlers. The cache does not
      16             : // need explicit invalidation when a prototype chain is modified, since the
      17             : // handlers verify the chain.
      18             : 
      19             : 
      20             : class SCTableReference {
      21             :  public:
      22         322 :   Address address() const { return address_; }
      23             : 
      24             :  private:
      25             :   explicit SCTableReference(Address address) : address_(address) {}
      26             : 
      27             :   Address address_;
      28             : 
      29             :   friend class StubCache;
      30             : };
      31             : 
      32             : 
      33             : class StubCache {
      34             :  public:
      35             :   struct Entry {
      36             :     Name* key;
      37             :     Object* value;
      38             :     Map* map;
      39             :   };
      40             : 
      41             :   void Initialize();
      42             :   // Access cache for entry hash(name, map).
      43             :   Object* Set(Name* name, Map* map, Object* handler);
      44             :   Object* Get(Name* name, Map* map);
      45             :   // Clear the lookup table (@ mark compact collection).
      46             :   void Clear();
      47             : 
      48             :   enum Table { kPrimary, kSecondary };
      49             : 
      50             :   SCTableReference key_reference(StubCache::Table table) {
      51             :     return SCTableReference(
      52      221566 :         reinterpret_cast<Address>(&first_entry(table)->key));
      53             :   }
      54             : 
      55             :   SCTableReference map_reference(StubCache::Table table) {
      56             :     return SCTableReference(
      57      221244 :         reinterpret_cast<Address>(&first_entry(table)->map));
      58             :   }
      59             : 
      60             :   SCTableReference value_reference(StubCache::Table table) {
      61             :     return SCTableReference(
      62      221244 :         reinterpret_cast<Address>(&first_entry(table)->value));
      63             :   }
      64             : 
      65      664054 :   StubCache::Entry* first_entry(StubCache::Table table) {
      66      664054 :     switch (table) {
      67             :       case StubCache::kPrimary:
      68      332027 :         return StubCache::primary_;
      69             :       case StubCache::kSecondary:
      70      332027 :         return StubCache::secondary_;
      71             :     }
      72           0 :     UNREACHABLE();
      73             :   }
      74             : 
      75             :   Isolate* isolate() { return isolate_; }
      76             : 
      77             :   // Setting the entry size such that the index is shifted by Name::kHashShift
      78             :   // is convenient; shifting down the length field (to extract the hash code)
      79             :   // automatically discards the hash bit field.
      80             :   static const int kCacheIndexShift = Name::kHashShift;
      81             : 
      82             :   static const int kPrimaryTableBits = 11;
      83             :   static const int kPrimaryTableSize = (1 << kPrimaryTableBits);
      84             :   static const int kSecondaryTableBits = 9;
      85             :   static const int kSecondaryTableSize = (1 << kSecondaryTableBits);
      86             : 
      87             :   // Some magic number used in primary and secondary hash computations.
      88             :   static const int kPrimaryMagic = 0x3d532433;
      89             :   static const int kSecondaryMagic = 0xb16ca6e5;
      90             : 
      91             :   static int PrimaryOffsetForTesting(Name* name, Map* map) {
      92        1320 :     return PrimaryOffset(name, map);
      93             :   }
      94             : 
      95             :   static int SecondaryOffsetForTesting(Name* name, int seed) {
      96         660 :     return SecondaryOffset(name, seed);
      97             :   }
      98             : 
      99             :   // The constructor is made public only for the purposes of testing.
     100             :   explicit StubCache(Isolate* isolate);
     101             : 
     102             :  private:
     103             :   // The stub cache has a primary and secondary level.  The two levels have
     104             :   // different hashing algorithms in order to avoid simultaneous collisions
     105             :   // in both caches.  Unlike a probing strategy (quadratic or otherwise) the
     106             :   // update strategy on updates is fairly clear and simple:  Any existing entry
     107             :   // in the primary cache is moved to the secondary cache, and secondary cache
     108             :   // entries are overwritten.
     109             : 
     110             :   // Hash algorithm for the primary table.  This algorithm is replicated in
     111             :   // assembler for every architecture.  Returns an index into the table that
     112             :   // is scaled by 1 << kCacheIndexShift.
     113             :   static int PrimaryOffset(Name* name, Map* map);
     114             : 
     115             :   // Hash algorithm for the secondary table.  This algorithm is replicated in
     116             :   // assembler for every architecture.  Returns an index into the table that
     117             :   // is scaled by 1 << kCacheIndexShift.
     118             :   static int SecondaryOffset(Name* name, int seed);
     119             : 
     120             :   // Compute the entry for a given offset in exactly the same way as
     121             :   // we do in generated code.  We generate an hash code that already
     122             :   // ends in Name::kHashShift 0s.  Then we multiply it so it is a multiple
     123             :   // of sizeof(Entry).  This makes it easier to avoid making mistakes
     124             :   // in the hashed offset computations.
     125             :   static Entry* entry(Entry* table, int offset) {
     126             :     const int multiplier = sizeof(*table) >> Name::kHashShift;
     127             :     return reinterpret_cast<Entry*>(reinterpret_cast<Address>(table) +
     128     1301635 :                                     offset * multiplier);
     129             :   }
     130             : 
     131             :  private:
     132             :   Entry primary_[kPrimaryTableSize];
     133             :   Entry secondary_[kSecondaryTableSize];
     134             :   Isolate* isolate_;
     135             : 
     136             :   friend class Isolate;
     137             :   friend class SCTableReference;
     138             : 
     139             :   DISALLOW_COPY_AND_ASSIGN(StubCache);
     140             : };
     141             : }  // namespace internal
     142             : }  // namespace v8
     143             : 
     144             : #endif  // V8_STUB_CACHE_H_