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     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 
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