// Copyright 2015 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_ADDRESS_MAP_H_ #define V8_ADDRESS_MAP_H_ #include "include/v8.h" #include "src/assert-scope.h" #include "src/base/hashmap.h" #include "src/objects.h" namespace v8 { namespace internal { template <typename Type> class PointerToIndexHashMap : public base::TemplateHashMapImpl<uintptr_t, uint32_t, base::KeyEqualityMatcher<intptr_t>, base::DefaultAllocationPolicy> { public: typedef base::TemplateHashMapEntry<uintptr_t, uint32_t> Entry; inline void Set(Type value, uint32_t index) { uintptr_t key = Key(value); LookupOrInsert(key, Hash(key))->value = index; } inline Maybe<uint32_t> Get(Type value) const { uintptr_t key = Key(value); Entry* entry = Lookup(key, Hash(key)); if (entry == nullptr) return Nothing<uint32_t>(); return Just(entry->value); } private: static uintptr_t Key(Type value) { return reinterpret_cast<uintptr_t>(value); } static uint32_t Hash(uintptr_t key) { return static_cast<uint32_t>(key); } }; class AddressToIndexHashMap : public PointerToIndexHashMap<Address> {}; class HeapObjectToIndexHashMap : public PointerToIndexHashMap<HeapObject*> {}; class RootIndexMap { public: explicit RootIndexMap(Isolate* isolate); static const int kInvalidRootIndex = -1; int Lookup(HeapObject* obj) { Maybe<uint32_t> maybe_index = map_->Get(obj); return maybe_index.IsJust() ? maybe_index.FromJust() : kInvalidRootIndex; } private: HeapObjectToIndexHashMap* map_; DISALLOW_COPY_AND_ASSIGN(RootIndexMap); }; class SerializerReference { public: SerializerReference() : bitfield_(Special(kInvalidValue)) {} static SerializerReference FromBitfield(uint32_t bitfield) { return SerializerReference(bitfield); } static SerializerReference BackReference(AllocationSpace space, uint32_t chunk_index, uint32_t chunk_offset) { DCHECK(IsAligned(chunk_offset, kObjectAlignment)); DCHECK_NE(LO_SPACE, space); return SerializerReference( SpaceBits::encode(space) | ChunkIndexBits::encode(chunk_index) | ChunkOffsetBits::encode(chunk_offset >> kObjectAlignmentBits)); } static SerializerReference MapReference(uint32_t index) { return SerializerReference(SpaceBits::encode(MAP_SPACE) | ValueIndexBits::encode(index)); } static SerializerReference LargeObjectReference(uint32_t index) { return SerializerReference(SpaceBits::encode(LO_SPACE) | ValueIndexBits::encode(index)); } static SerializerReference AttachedReference(uint32_t index) { return SerializerReference(SpaceBits::encode(kAttachedReferenceSpace) | ValueIndexBits::encode(index)); } static SerializerReference DummyReference() { return SerializerReference(Special(kDummyValue)); } bool is_valid() const { return bitfield_ != Special(kInvalidValue); } bool is_back_reference() const { return SpaceBits::decode(bitfield_) <= LAST_SPACE; } AllocationSpace space() const { DCHECK(is_back_reference()); return static_cast<AllocationSpace>(SpaceBits::decode(bitfield_)); } uint32_t chunk_offset() const { DCHECK(is_back_reference()); return ChunkOffsetBits::decode(bitfield_) << kObjectAlignmentBits; } uint32_t map_index() const { DCHECK(is_back_reference()); return ValueIndexBits::decode(bitfield_); } uint32_t large_object_index() const { DCHECK(is_back_reference()); return ValueIndexBits::decode(bitfield_); } uint32_t chunk_index() const { DCHECK(is_back_reference()); return ChunkIndexBits::decode(bitfield_); } uint32_t back_reference() const { DCHECK(is_back_reference()); return bitfield_ & (ChunkOffsetBits::kMask | ChunkIndexBits::kMask); } bool is_attached_reference() const { return SpaceBits::decode(bitfield_) == kAttachedReferenceSpace; } int attached_reference_index() const { DCHECK(is_attached_reference()); return ValueIndexBits::decode(bitfield_); } private: explicit SerializerReference(uint32_t bitfield) : bitfield_(bitfield) {} inline static uint32_t Special(int value) { return SpaceBits::encode(kSpecialValueSpace) | ValueIndexBits::encode(value); } // We use the 32-bit bitfield to encode either a back reference, a special // value, or an attached reference index. // Back reference: // [ Space index ] [ Chunk index ] [ Chunk offset ] // [ LO_SPACE ] [ large object index ] // Special value // [ kSpecialValueSpace ] [ Special value index ] // Attached reference // [ kAttachedReferenceSpace ] [ Attached reference index ] static const int kChunkOffsetSize = kPageSizeBits - kObjectAlignmentBits; static const int kChunkIndexSize = 32 - kChunkOffsetSize - kSpaceTagSize; static const int kValueIndexSize = kChunkOffsetSize + kChunkIndexSize; static const int kSpecialValueSpace = LAST_SPACE + 1; static const int kAttachedReferenceSpace = kSpecialValueSpace + 1; STATIC_ASSERT(kAttachedReferenceSpace < (1 << kSpaceTagSize)); static const int kInvalidValue = 0; static const int kDummyValue = 1; // The chunk offset can also be used to encode the index of special values. class ChunkOffsetBits : public BitField<uint32_t, 0, kChunkOffsetSize> {}; class ChunkIndexBits : public BitField<uint32_t, ChunkOffsetBits::kNext, kChunkIndexSize> {}; class ValueIndexBits : public BitField<uint32_t, 0, kValueIndexSize> {}; STATIC_ASSERT(ChunkIndexBits::kNext == ValueIndexBits::kNext); class SpaceBits : public BitField<int, kValueIndexSize, kSpaceTagSize> {}; STATIC_ASSERT(SpaceBits::kNext == 32); uint32_t bitfield_; friend class SerializerReferenceMap; }; // Mapping objects to their location after deserialization. // This is used during building, but not at runtime by V8. class SerializerReferenceMap { public: SerializerReferenceMap() : no_allocation_(), map_(), attached_reference_index_(0) {} SerializerReference Lookup(HeapObject* obj) { Maybe<uint32_t> maybe_index = map_.Get(obj); return maybe_index.IsJust() ? SerializerReference(maybe_index.FromJust()) : SerializerReference(); } void Add(HeapObject* obj, SerializerReference b) { DCHECK(b.is_valid()); DCHECK(map_.Get(obj).IsNothing()); map_.Set(obj, b.bitfield_); } SerializerReference AddAttachedReference(HeapObject* attached_reference) { SerializerReference reference = SerializerReference::AttachedReference(attached_reference_index_++); Add(attached_reference, reference); return reference; } private: DisallowHeapAllocation no_allocation_; HeapObjectToIndexHashMap map_; int attached_reference_index_; DISALLOW_COPY_AND_ASSIGN(SerializerReferenceMap); }; } // namespace internal } // namespace v8 #endif // V8_ADDRESS_MAP_H_