1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_IC_STUB_CACHE_H_
#define V8_IC_STUB_CACHE_H_
#include "src/objects/name.h"
#include "src/objects/tagged-value.h"
namespace v8 {
namespace internal {
// The stub cache is used for megamorphic property accesses.
// It maps (map, name, type) to property access handlers. The cache does not
// need explicit invalidation when a prototype chain is modified, since the
// handlers verify the chain.
class SCTableReference {
public:
Address address() const { return address_; }
private:
explicit SCTableReference(Address address) : address_(address) {}
Address address_;
friend class StubCache;
};
class V8_EXPORT_PRIVATE StubCache {
public:
struct Entry {
// {key} is a tagged Name pointer, may be cleared by setting to empty
// string.
StrongTaggedValue key;
// {value} is a tagged heap object reference (weak or strong), equivalent
// to a MaybeObject's payload.
TaggedValue value;
// {map} is a tagged Map pointer, may be cleared by setting to Smi::zero().
StrongTaggedValue map;
};
void Initialize();
// Access cache for entry hash(name, map).
void Set(Name name, Map map, MaybeObject handler);
MaybeObject Get(Name name, Map map);
// Clear the lookup table (@ mark compact collection).
void Clear();
enum Table { kPrimary, kSecondary };
SCTableReference key_reference(StubCache::Table table) {
return SCTableReference(
reinterpret_cast<Address>(&first_entry(table)->key));
}
SCTableReference map_reference(StubCache::Table table) {
return SCTableReference(
reinterpret_cast<Address>(&first_entry(table)->map));
}
SCTableReference value_reference(StubCache::Table table) {
return SCTableReference(
reinterpret_cast<Address>(&first_entry(table)->value));
}
StubCache::Entry* first_entry(StubCache::Table table) {
switch (table) {
case StubCache::kPrimary:
return StubCache::primary_;
case StubCache::kSecondary:
return StubCache::secondary_;
}
UNREACHABLE();
}
Isolate* isolate() { return isolate_; }
// Ideally we would set kCacheIndexShift to Name::kHashShift, such that
// the bit field inside the hash field gets shifted out implicitly. However,
// sizeof(Entry) needs to be a multiple of 1 << kCacheIndexShift, and it
// isn't clear whether letting one bit of the bit field leak into the index
// computation is bad enough to warrant an additional shift to get rid of it.
static const int kCacheIndexShift = 2;
// The purpose of the static assert is to make us reconsider this choice
// if the bit field ever grows even more.
STATIC_ASSERT(kCacheIndexShift == Name::kHashShift - 1);
static const int kPrimaryTableBits = 11;
static const int kPrimaryTableSize = (1 << kPrimaryTableBits);
static const int kSecondaryTableBits = 9;
static const int kSecondaryTableSize = (1 << kSecondaryTableBits);
// We compute the hash code for a map as follows:
// <code> = <address> ^ (<address> >> kMapKeyShift)
static const int kMapKeyShift = kPrimaryTableBits + kCacheIndexShift;
// Some magic number used in the secondary hash computation.
static const int kSecondaryMagic = 0xb16ca6e5;
static int PrimaryOffsetForTesting(Name name, Map map);
static int SecondaryOffsetForTesting(Name name, int seed);
// The constructor is made public only for the purposes of testing.
explicit StubCache(Isolate* isolate);
private:
// The stub cache has a primary and secondary level. The two levels have
// different hashing algorithms in order to avoid simultaneous collisions
// in both caches. Unlike a probing strategy (quadratic or otherwise) the
// update strategy on updates is fairly clear and simple: Any existing entry
// in the primary cache is moved to the secondary cache, and secondary cache
// entries are overwritten.
// Hash algorithm for the primary table. This algorithm is replicated in
// assembler for every architecture. Returns an index into the table that
// is scaled by 1 << kCacheIndexShift.
static int PrimaryOffset(Name name, Map map);
// Hash algorithm for the secondary table. This algorithm is replicated in
// assembler for every architecture. Returns an index into the table that
// is scaled by 1 << kCacheIndexShift.
static int SecondaryOffset(Name name, int seed);
// Compute the entry for a given offset in exactly the same way as
// we do in generated code. We generate an hash code that already
// ends in Name::kHashShift 0s. Then we multiply it so it is a multiple
// of sizeof(Entry). This makes it easier to avoid making mistakes
// in the hashed offset computations.
static Entry* entry(Entry* table, int offset) {
// The size of {Entry} must be a multiple of 1 << kCacheIndexShift.
STATIC_ASSERT((sizeof(*table) >> kCacheIndexShift) << kCacheIndexShift ==
sizeof(*table));
const int multiplier = sizeof(*table) >> kCacheIndexShift;
return reinterpret_cast<Entry*>(reinterpret_cast<Address>(table) +
offset * multiplier);
}
private:
Entry primary_[kPrimaryTableSize];
Entry secondary_[kSecondaryTableSize];
Isolate* isolate_;
friend class Isolate;
friend class SCTableReference;
DISALLOW_COPY_AND_ASSIGN(StubCache);
};
} // namespace internal
} // namespace v8
#endif // V8_IC_STUB_CACHE_H_
|
