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 : #ifndef V8_ADDRESS_MAP_H_
6 : #define V8_ADDRESS_MAP_H_
7 :
8 : #include "include/v8.h"
9 : #include "src/assert-scope.h"
10 : #include "src/base/hashmap.h"
11 : #include "src/objects.h"
12 :
13 : namespace v8 {
14 : namespace internal {
15 :
16 : template <typename Type>
17 19550 : class PointerToIndexHashMap
18 : : public base::TemplateHashMapImpl<uintptr_t, uint32_t,
19 : base::KeyEqualityMatcher<intptr_t>,
20 : base::DefaultAllocationPolicy> {
21 : public:
22 : typedef base::TemplateHashMapEntry<uintptr_t, uint32_t> Entry;
23 :
24 : inline void Set(Type value, uint32_t index) {
25 9784992 : uintptr_t key = Key(value);
26 19569984 : LookupOrInsert(key, Hash(key))->value = index;
27 : }
28 :
29 52900763 : inline Maybe<uint32_t> Get(Type value) const {
30 : uintptr_t key = Key(value);
31 52900763 : Entry* entry = Lookup(key, Hash(key));
32 52900763 : if (entry == nullptr) return Nothing<uint32_t>();
33 11075864 : return Just(entry->value);
34 : }
35 :
36 : private:
37 : static uintptr_t Key(Type value) {
38 62685755 : return reinterpret_cast<uintptr_t>(value);
39 : }
40 :
41 62685755 : static uint32_t Hash(uintptr_t key) { return static_cast<uint32_t>(key); }
42 : };
43 :
44 : class AddressToIndexHashMap : public PointerToIndexHashMap<Address> {};
45 : class HeapObjectToIndexHashMap : public PointerToIndexHashMap<HeapObject*> {};
46 :
47 : class RootIndexMap {
48 : public:
49 : explicit RootIndexMap(Isolate* isolate);
50 :
51 : static const int kInvalidRootIndex = -1;
52 :
53 40922465 : int Lookup(HeapObject* obj) {
54 40922465 : Maybe<uint32_t> maybe_index = map_->Get(obj);
55 49993757 : return maybe_index.IsJust() ? maybe_index.FromJust() : kInvalidRootIndex;
56 : }
57 :
58 : private:
59 : HeapObjectToIndexHashMap* map_;
60 :
61 : DISALLOW_COPY_AND_ASSIGN(RootIndexMap);
62 : };
63 :
64 : class SerializerReference {
65 : public:
66 1700934 : SerializerReference() : bitfield_(Special(kInvalidValue)) {}
67 :
68 : static SerializerReference FromBitfield(uint32_t bitfield) {
69 : return SerializerReference(bitfield);
70 : }
71 :
72 : static SerializerReference BackReference(AllocationSpace space,
73 : uint32_t chunk_index,
74 : uint32_t chunk_offset) {
75 : DCHECK(IsAligned(chunk_offset, kObjectAlignment));
76 : DCHECK_NE(LO_SPACE, space);
77 : return SerializerReference(
78 1338799 : SpaceBits::encode(space) | ChunkIndexBits::encode(chunk_index) |
79 1451660 : ChunkOffsetBits::encode(chunk_offset >> kObjectAlignmentBits));
80 : }
81 :
82 : static SerializerReference MapReference(uint32_t index) {
83 : return SerializerReference(SpaceBits::encode(MAP_SPACE) |
84 59747 : ValueIndexBits::encode(index));
85 : }
86 :
87 : static SerializerReference OffHeapBackingStoreReference(uint32_t index) {
88 : return SerializerReference(SpaceBits::encode(kExternalSpace) |
89 30 : ValueIndexBits::encode(index));
90 : }
91 :
92 : static SerializerReference LargeObjectReference(uint32_t index) {
93 : return SerializerReference(SpaceBits::encode(LO_SPACE) |
94 40 : ValueIndexBits::encode(index));
95 : }
96 :
97 : static SerializerReference AttachedReference(uint32_t index) {
98 : return SerializerReference(SpaceBits::encode(kAttachedReferenceSpace) |
99 775 : ValueIndexBits::encode(index));
100 : }
101 :
102 : static SerializerReference DummyReference() {
103 : return SerializerReference(Special(kDummyValue));
104 : }
105 :
106 0 : bool is_valid() const { return bitfield_ != Special(kInvalidValue); }
107 :
108 : bool is_back_reference() const {
109 : return SpaceBits::decode(bitfield_) <= LAST_SPACE;
110 : }
111 :
112 : AllocationSpace space() const {
113 : DCHECK(is_back_reference());
114 3843 : return static_cast<AllocationSpace>(SpaceBits::decode(bitfield_));
115 : }
116 :
117 : uint32_t chunk_offset() const {
118 : DCHECK(is_back_reference());
119 243483400 : return ChunkOffsetBits::decode(bitfield_) << kObjectAlignmentBits;
120 : }
121 :
122 : uint32_t map_index() const {
123 : DCHECK(is_back_reference());
124 : return ValueIndexBits::decode(bitfield_);
125 : }
126 :
127 : bool is_off_heap_backing_store_reference() const {
128 : return SpaceBits::decode(bitfield_) == kExternalSpace;
129 : }
130 :
131 : uint32_t off_heap_backing_store_index() const {
132 : DCHECK(is_off_heap_backing_store_reference());
133 : return ValueIndexBits::decode(bitfield_);
134 : }
135 :
136 : uint32_t large_object_index() const {
137 : DCHECK(is_back_reference());
138 : return ValueIndexBits::decode(bitfield_);
139 : }
140 :
141 : uint32_t chunk_index() const {
142 : DCHECK(is_back_reference());
143 : return ChunkIndexBits::decode(bitfield_);
144 : }
145 :
146 : uint32_t back_reference() const {
147 : DCHECK(is_back_reference());
148 729019 : return bitfield_ & (ChunkOffsetBits::kMask | ChunkIndexBits::kMask);
149 : }
150 :
151 : bool is_attached_reference() const {
152 : return SpaceBits::decode(bitfield_) == kAttachedReferenceSpace;
153 : }
154 :
155 : int attached_reference_index() const {
156 : DCHECK(is_attached_reference());
157 2204 : return ValueIndexBits::decode(bitfield_);
158 : }
159 :
160 : private:
161 729998 : explicit SerializerReference(uint32_t bitfield) : bitfield_(bitfield) {}
162 :
163 : inline static uint32_t Special(int value) {
164 : return SpaceBits::encode(kSpecialValueSpace) |
165 : ValueIndexBits::encode(value);
166 : }
167 :
168 : // We use the 32-bit bitfield to encode either a back reference, a special
169 : // value, or an attached reference index.
170 : // Back reference:
171 : // [ Space index ] [ Chunk index ] [ Chunk offset ]
172 : // [ LO_SPACE ] [ large object index ]
173 : // Special value
174 : // [ kSpecialValueSpace ] [ Special value index ]
175 : // Attached reference
176 : // [ kAttachedReferenceSpace ] [ Attached reference index ]
177 : // External
178 : // [ kExternalSpace ] [ External reference index ]
179 :
180 : static const int kChunkOffsetSize = kPageSizeBits - kObjectAlignmentBits;
181 : static const int kChunkIndexSize = 32 - kChunkOffsetSize - kSpaceTagSize;
182 : static const int kValueIndexSize = kChunkOffsetSize + kChunkIndexSize;
183 :
184 : static const int kSpecialValueSpace = LAST_SPACE + 1;
185 : static const int kAttachedReferenceSpace = kSpecialValueSpace + 1;
186 : static const int kExternalSpace = kAttachedReferenceSpace + 1;
187 : STATIC_ASSERT(kExternalSpace < (1 << kSpaceTagSize));
188 :
189 : static const int kInvalidValue = 0;
190 : static const int kDummyValue = 1;
191 :
192 : // The chunk offset can also be used to encode the index of special values.
193 : class ChunkOffsetBits : public BitField<uint32_t, 0, kChunkOffsetSize> {};
194 : class ChunkIndexBits
195 : : public BitField<uint32_t, ChunkOffsetBits::kNext, kChunkIndexSize> {};
196 : class ValueIndexBits : public BitField<uint32_t, 0, kValueIndexSize> {};
197 : STATIC_ASSERT(ChunkIndexBits::kNext == ValueIndexBits::kNext);
198 : class SpaceBits : public BitField<int, kValueIndexSize, kSpaceTagSize> {};
199 : STATIC_ASSERT(SpaceBits::kNext == 32);
200 :
201 : uint32_t bitfield_;
202 :
203 : friend class SerializerReferenceMap;
204 : };
205 :
206 : // Mapping objects to their location after deserialization.
207 : // This is used during building, but not at runtime by V8.
208 : class SerializerReferenceMap {
209 : public:
210 : SerializerReferenceMap()
211 1782 : : no_allocation_(), map_(), attached_reference_index_(0) {}
212 :
213 2430932 : SerializerReference Lookup(void* obj) {
214 2430932 : Maybe<uint32_t> maybe_index = map_.Get(obj);
215 2430932 : return maybe_index.IsJust() ? SerializerReference(maybe_index.FromJust())
216 4861864 : : SerializerReference();
217 : }
218 :
219 : void Add(void* obj, SerializerReference b) {
220 : DCHECK(b.is_valid());
221 : DCHECK(map_.Get(obj).IsNothing());
222 : map_.Set(obj, b.bitfield_);
223 : }
224 :
225 775 : SerializerReference AddAttachedReference(HeapObject* attached_reference) {
226 : SerializerReference reference =
227 775 : SerializerReference::AttachedReference(attached_reference_index_++);
228 : Add(attached_reference, reference);
229 775 : return reference;
230 : }
231 :
232 : private:
233 : DisallowHeapAllocation no_allocation_;
234 : PointerToIndexHashMap<void*> map_;
235 : int attached_reference_index_;
236 : DISALLOW_COPY_AND_ASSIGN(SerializerReferenceMap);
237 : };
238 :
239 : } // namespace internal
240 : } // namespace v8
241 :
242 : #endif // V8_ADDRESS_MAP_H_
|
