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_IC_STUB_CACHE_H_ 6 #define V8_IC_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: address()22 Address address() const { return address_; } 23 24 private: SCTableReference(Address address)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 MaybeObject* value; 38 Map* map; 39 }; 40 41 void Initialize(); 42 // Access cache for entry hash(name, map). 43 MaybeObject* Set(Name* name, Map* map, MaybeObject* handler); 44 MaybeObject* Get(Name* name, Map* map); 45 // Clear the lookup table (@ mark compact collection). 46 void Clear(); 47 48 enum Table { kPrimary, kSecondary }; 49 key_reference(StubCache::Table table)50 SCTableReference key_reference(StubCache::Table table) { 51 return SCTableReference( 52 reinterpret_cast<Address>(&first_entry(table)->key)); 53 } 54 map_reference(StubCache::Table table)55 SCTableReference map_reference(StubCache::Table table) { 56 return SCTableReference( 57 reinterpret_cast<Address>(&first_entry(table)->map)); 58 } 59 value_reference(StubCache::Table table)60 SCTableReference value_reference(StubCache::Table table) { 61 return SCTableReference( 62 reinterpret_cast<Address>(&first_entry(table)->value)); 63 } 64 first_entry(StubCache::Table table)65 StubCache::Entry* first_entry(StubCache::Table table) { 66 switch (table) { 67 case StubCache::kPrimary: 68 return StubCache::primary_; 69 case StubCache::kSecondary: 70 return StubCache::secondary_; 71 } 72 UNREACHABLE(); 73 } 74 isolate()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 the secondary hash computation. 88 static const int kSecondaryMagic = 0xb16ca6e5; 89 PrimaryOffsetForTesting(Name * name,Map * map)90 static int PrimaryOffsetForTesting(Name* name, Map* map) { 91 return PrimaryOffset(name, map); 92 } 93 SecondaryOffsetForTesting(Name * name,int seed)94 static int SecondaryOffsetForTesting(Name* name, int seed) { 95 return SecondaryOffset(name, seed); 96 } 97 98 // The constructor is made public only for the purposes of testing. 99 explicit StubCache(Isolate* isolate); 100 101 private: 102 // The stub cache has a primary and secondary level. The two levels have 103 // different hashing algorithms in order to avoid simultaneous collisions 104 // in both caches. Unlike a probing strategy (quadratic or otherwise) the 105 // update strategy on updates is fairly clear and simple: Any existing entry 106 // in the primary cache is moved to the secondary cache, and secondary cache 107 // entries are overwritten. 108 109 // Hash algorithm for the primary table. This algorithm is replicated in 110 // assembler for every architecture. Returns an index into the table that 111 // is scaled by 1 << kCacheIndexShift. 112 static int PrimaryOffset(Name* name, Map* map); 113 114 // Hash algorithm for the secondary table. This algorithm is replicated in 115 // assembler for every architecture. Returns an index into the table that 116 // is scaled by 1 << kCacheIndexShift. 117 static int SecondaryOffset(Name* name, int seed); 118 119 // Compute the entry for a given offset in exactly the same way as 120 // we do in generated code. We generate an hash code that already 121 // ends in Name::kHashShift 0s. Then we multiply it so it is a multiple 122 // of sizeof(Entry). This makes it easier to avoid making mistakes 123 // in the hashed offset computations. entry(Entry * table,int offset)124 static Entry* entry(Entry* table, int offset) { 125 const int multiplier = sizeof(*table) >> Name::kHashShift; 126 return reinterpret_cast<Entry*>(reinterpret_cast<Address>(table) + 127 offset * multiplier); 128 } 129 130 private: 131 Entry primary_[kPrimaryTableSize]; 132 Entry secondary_[kSecondaryTableSize]; 133 Isolate* isolate_; 134 135 friend class Isolate; 136 friend class SCTableReference; 137 138 DISALLOW_COPY_AND_ASSIGN(StubCache); 139 }; 140 } // namespace internal 141 } // namespace v8 142 143 #endif // V8_IC_STUB_CACHE_H_ 144