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 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 uintptr_t key = Key(value); 26 LookupOrInsert(key, Hash(key))->value = index; 27 } 28 29 inline Maybe<uint32_t> Get(Type value) const { 30 uintptr_t key = Key(value); 31 Entry* entry = Lookup(key, Hash(key)); 32 if (entry == nullptr) return Nothing<uint32_t>(); 33 return Just(entry->value); 34 } 35 36 private: 37 static uintptr_t Key(Type value) { 38 return reinterpret_cast<uintptr_t>(value); 39 } 40 41 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 int Lookup(HeapObject* obj) { 54 Maybe<uint32_t> maybe_index = map_->Get(obj); 55 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 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 SpaceBits::encode(space) | ChunkIndexBits::encode(chunk_index) | 79 ChunkOffsetBits::encode(chunk_offset >> kObjectAlignmentBits)); 80 } 81 82 static SerializerReference MapReference(uint32_t index) { 83 return SerializerReference(SpaceBits::encode(MAP_SPACE) | 84 ValueIndexBits::encode(index)); 85 } 86 87 static SerializerReference LargeObjectReference(uint32_t index) { 88 return SerializerReference(SpaceBits::encode(LO_SPACE) | 89 ValueIndexBits::encode(index)); 90 } 91 92 static SerializerReference AttachedReference(uint32_t index) { 93 return SerializerReference(SpaceBits::encode(kAttachedReferenceSpace) | 94 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 return static_cast<AllocationSpace>(SpaceBits::decode(bitfield_)); 110 } 111 112 uint32_t chunk_offset() const { 113 DCHECK(is_back_reference()); 114 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 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 return ValueIndexBits::decode(bitfield_); 144 } 145 146 private: 147 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 : no_allocation_(), map_(), attached_reference_index_(0) {} 195 196 SerializerReference Lookup(HeapObject* obj) { 197 Maybe<uint32_t> maybe_index = map_.Get(obj); 198 return maybe_index.IsJust() ? SerializerReference(maybe_index.FromJust()) 199 : 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 SerializerReference AddAttachedReference(HeapObject* attached_reference) { 209 SerializerReference reference = 210 SerializerReference::AttachedReference(attached_reference_index_++); 211 Add(attached_reference, reference); 212 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_ 226
