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 25826 : 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 12050854 : uintptr_t key = Key(value);
26 24101712 : LookupOrInsert(key, Hash(key))->value = index;
27 : }
28 :
29 56905400 : inline Maybe<uint32_t> Get(Type value) const {
30 : uintptr_t key = Key(value);
31 56905400 : Entry* entry = Lookup(key, Hash(key));
32 56905400 : if (entry == nullptr) return Nothing<uint32_t>();
33 14294259 : return Just(entry->value);
34 : }
35 :
36 : private:
37 : static uintptr_t Key(Type value) {
38 68956254 : return reinterpret_cast<uintptr_t>(value);
39 : }
40 :
41 68956254 : 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 42287017 : int Lookup(HeapObject* obj) {
54 42287017 : Maybe<uint32_t> maybe_index = map_->Get(obj);
55 53685216 : 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 2081515 : 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 1538095 : SpaceBits::encode(space) | ChunkIndexBits::encode(chunk_index) |
79 1538095 : ChunkOffsetBits::encode(chunk_offset >> kObjectAlignmentBits));
80 : }
81 :
82 : static SerializerReference MapReference(uint32_t index) {
83 : return SerializerReference(SpaceBits::encode(MAP_SPACE) |
84 72892 : ValueIndexBits::encode(index));
85 : }
86 :
87 : static SerializerReference LargeObjectReference(uint32_t index) {
88 : return SerializerReference(SpaceBits::encode(LO_SPACE) |
89 42 : ValueIndexBits::encode(index));
90 : }
91 :
92 : static SerializerReference AttachedReference(uint32_t index) {
93 : return SerializerReference(SpaceBits::encode(kAttachedReferenceSpace) |
94 1348 : ValueIndexBits::encode(index));
95 : }
96 :
97 : static SerializerReference DummyReference() {
98 : return SerializerReference(Special(kDummyValue));
99 : }
100 :
101 : bool is_valid() const { return bitfield_ != Special(kInvalidValue); }
102 :
103 : bool is_back_reference() const {
104 : return SpaceBits::decode(bitfield_) <= LAST_SPACE;
105 : }
106 :
107 : AllocationSpace space() const {
108 : DCHECK(is_back_reference());
109 12455 : return static_cast<AllocationSpace>(SpaceBits::decode(bitfield_));
110 : }
111 :
112 : uint32_t chunk_offset() const {
113 : DCHECK(is_back_reference());
114 708761219 : return ChunkOffsetBits::decode(bitfield_) << kObjectAlignmentBits;
115 : }
116 :
117 : uint32_t map_index() const {
118 : DCHECK(is_back_reference());
119 : return ValueIndexBits::decode(bitfield_);
120 : }
121 :
122 : uint32_t large_object_index() const {
123 : DCHECK(is_back_reference());
124 : return ValueIndexBits::decode(bitfield_);
125 : }
126 :
127 : uint32_t chunk_index() const {
128 : DCHECK(is_back_reference());
129 : return ChunkIndexBits::decode(bitfield_);
130 : }
131 :
132 : uint32_t back_reference() const {
133 : DCHECK(is_back_reference());
134 1659272 : return bitfield_ & (ChunkOffsetBits::kMask | ChunkIndexBits::kMask);
135 : }
136 :
137 : bool is_attached_reference() const {
138 : return SpaceBits::decode(bitfield_) == kAttachedReferenceSpace;
139 : }
140 :
141 : int attached_reference_index() const {
142 : DCHECK(is_attached_reference());
143 7092 : return ValueIndexBits::decode(bitfield_);
144 : }
145 :
146 : private:
147 1713884 : explicit SerializerReference(uint32_t bitfield) : bitfield_(bitfield) {}
148 :
149 : inline static uint32_t Special(int value) {
150 : return SpaceBits::encode(kSpecialValueSpace) |
151 : ValueIndexBits::encode(value);
152 : }
153 :
154 : // We use the 32-bit bitfield to encode either a back reference, a special
155 : // value, or an attached reference index.
156 : // Back reference:
157 : // [ Space index ] [ Chunk index ] [ Chunk offset ]
158 : // [ LO_SPACE ] [ large object index ]
159 : // Special value
160 : // [ kSpecialValueSpace ] [ Special value index ]
161 : // Attached reference
162 : // [ kAttachedReferenceSpace ] [ Attached reference index ]
163 :
164 : static const int kChunkOffsetSize = kPageSizeBits - kObjectAlignmentBits;
165 : static const int kChunkIndexSize = 32 - kChunkOffsetSize - kSpaceTagSize;
166 : static const int kValueIndexSize = kChunkOffsetSize + kChunkIndexSize;
167 :
168 : static const int kSpecialValueSpace = LAST_SPACE + 1;
169 : static const int kAttachedReferenceSpace = kSpecialValueSpace + 1;
170 : STATIC_ASSERT(kAttachedReferenceSpace < (1 << kSpaceTagSize));
171 :
172 : static const int kInvalidValue = 0;
173 : static const int kDummyValue = 1;
174 :
175 : // The chunk offset can also be used to encode the index of special values.
176 : class ChunkOffsetBits : public BitField<uint32_t, 0, kChunkOffsetSize> {};
177 : class ChunkIndexBits
178 : : public BitField<uint32_t, ChunkOffsetBits::kNext, kChunkIndexSize> {};
179 : class ValueIndexBits : public BitField<uint32_t, 0, kValueIndexSize> {};
180 : STATIC_ASSERT(ChunkIndexBits::kNext == ValueIndexBits::kNext);
181 : class SpaceBits : public BitField<int, kValueIndexSize, kSpaceTagSize> {};
182 : STATIC_ASSERT(SpaceBits::kNext == 32);
183 :
184 : uint32_t bitfield_;
185 :
186 : friend class SerializerReferenceMap;
187 : };
188 :
189 : // Mapping objects to their location after deserialization.
190 : // This is used during building, but not at runtime by V8.
191 : class SerializerReferenceMap {
192 : public:
193 : SerializerReferenceMap()
194 1694 : : no_allocation_(), map_(), attached_reference_index_(0) {}
195 :
196 3795399 : SerializerReference Lookup(HeapObject* obj) {
197 3795399 : Maybe<uint32_t> maybe_index = map_.Get(obj);
198 3795399 : return maybe_index.IsJust() ? SerializerReference(maybe_index.FromJust())
199 7590798 : : SerializerReference();
200 : }
201 :
202 : void Add(HeapObject* obj, SerializerReference b) {
203 : DCHECK(b.is_valid());
204 : DCHECK(map_.Get(obj).IsNothing());
205 : map_.Set(obj, b.bitfield_);
206 : }
207 :
208 1348 : SerializerReference AddAttachedReference(HeapObject* attached_reference) {
209 : SerializerReference reference =
210 1348 : SerializerReference::AttachedReference(attached_reference_index_++);
211 : Add(attached_reference, reference);
212 1348 : return reference;
213 : }
214 :
215 : private:
216 : DisallowHeapAllocation no_allocation_;
217 : HeapObjectToIndexHashMap map_;
218 : int attached_reference_index_;
219 : DISALLOW_COPY_AND_ASSIGN(SerializerReferenceMap);
220 : };
221 :
222 : } // namespace internal
223 : } // namespace v8
224 :
225 : #endif // V8_ADDRESS_MAP_H_
|