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 "src/assert-scope.h"
9 #include "src/hashmap.h"
10 #include "src/objects.h"
11 
12 namespace v8 {
13 namespace internal {
14 
15 class AddressMapBase {
16  protected:
SetValue(HashMap::Entry * entry,uint32_t v)17   static void SetValue(HashMap::Entry* entry, uint32_t v) {
18     entry->value = reinterpret_cast<void*>(v);
19   }
20 
GetValue(HashMap::Entry * entry)21   static uint32_t GetValue(HashMap::Entry* entry) {
22     return static_cast<uint32_t>(reinterpret_cast<intptr_t>(entry->value));
23   }
24 
LookupEntry(HashMap * map,HeapObject * obj,bool insert)25   inline static HashMap::Entry* LookupEntry(HashMap* map, HeapObject* obj,
26                                             bool insert) {
27     if (insert) {
28       map->LookupOrInsert(Key(obj), Hash(obj));
29     }
30     return map->Lookup(Key(obj), Hash(obj));
31   }
32 
33  private:
Hash(HeapObject * obj)34   static uint32_t Hash(HeapObject* obj) {
35     return static_cast<int32_t>(reinterpret_cast<intptr_t>(obj->address()));
36   }
37 
Key(HeapObject * obj)38   static void* Key(HeapObject* obj) {
39     return reinterpret_cast<void*>(obj->address());
40   }
41 };
42 
43 
44 class RootIndexMap : public AddressMapBase {
45  public:
46   explicit RootIndexMap(Isolate* isolate);
47 
48   static const int kInvalidRootIndex = -1;
49 
Lookup(HeapObject * obj)50   int Lookup(HeapObject* obj) {
51     HashMap::Entry* entry = LookupEntry(map_, obj, false);
52     if (entry) return GetValue(entry);
53     return kInvalidRootIndex;
54   }
55 
56  private:
57   HashMap* map_;
58 
59   DISALLOW_COPY_AND_ASSIGN(RootIndexMap);
60 };
61 
62 
63 class BackReference {
64  public:
BackReference(uint32_t bitfield)65   explicit BackReference(uint32_t bitfield) : bitfield_(bitfield) {}
66 
BackReference()67   BackReference() : bitfield_(kInvalidValue) {}
68 
SourceReference()69   static BackReference SourceReference() { return BackReference(kSourceValue); }
70 
GlobalProxyReference()71   static BackReference GlobalProxyReference() {
72     return BackReference(kGlobalProxyValue);
73   }
74 
LargeObjectReference(uint32_t index)75   static BackReference LargeObjectReference(uint32_t index) {
76     return BackReference(SpaceBits::encode(LO_SPACE) |
77                          ChunkOffsetBits::encode(index));
78   }
79 
DummyReference()80   static BackReference DummyReference() { return BackReference(kDummyValue); }
81 
Reference(AllocationSpace space,uint32_t chunk_index,uint32_t chunk_offset)82   static BackReference Reference(AllocationSpace space, uint32_t chunk_index,
83                                  uint32_t chunk_offset) {
84     DCHECK(IsAligned(chunk_offset, kObjectAlignment));
85     DCHECK_NE(LO_SPACE, space);
86     return BackReference(
87         SpaceBits::encode(space) | ChunkIndexBits::encode(chunk_index) |
88         ChunkOffsetBits::encode(chunk_offset >> kObjectAlignmentBits));
89   }
90 
is_valid()91   bool is_valid() const { return bitfield_ != kInvalidValue; }
is_source()92   bool is_source() const { return bitfield_ == kSourceValue; }
is_global_proxy()93   bool is_global_proxy() const { return bitfield_ == kGlobalProxyValue; }
94 
space()95   AllocationSpace space() const {
96     DCHECK(is_valid());
97     return SpaceBits::decode(bitfield_);
98   }
99 
chunk_offset()100   uint32_t chunk_offset() const {
101     DCHECK(is_valid());
102     return ChunkOffsetBits::decode(bitfield_) << kObjectAlignmentBits;
103   }
104 
large_object_index()105   uint32_t large_object_index() const {
106     DCHECK(is_valid());
107     DCHECK(chunk_index() == 0);
108     return ChunkOffsetBits::decode(bitfield_);
109   }
110 
chunk_index()111   uint32_t chunk_index() const {
112     DCHECK(is_valid());
113     return ChunkIndexBits::decode(bitfield_);
114   }
115 
reference()116   uint32_t reference() const {
117     DCHECK(is_valid());
118     return bitfield_ & (ChunkOffsetBits::kMask | ChunkIndexBits::kMask);
119   }
120 
bitfield()121   uint32_t bitfield() const { return bitfield_; }
122 
123  private:
124   static const uint32_t kInvalidValue = 0xFFFFFFFF;
125   static const uint32_t kSourceValue = 0xFFFFFFFE;
126   static const uint32_t kGlobalProxyValue = 0xFFFFFFFD;
127   static const uint32_t kDummyValue = 0xFFFFFFFC;
128   static const int kChunkOffsetSize = kPageSizeBits - kObjectAlignmentBits;
129   static const int kChunkIndexSize = 32 - kChunkOffsetSize - kSpaceTagSize;
130 
131  public:
132   static const int kMaxChunkIndex = (1 << kChunkIndexSize) - 1;
133 
134  private:
135   class ChunkOffsetBits : public BitField<uint32_t, 0, kChunkOffsetSize> {};
136   class ChunkIndexBits
137       : public BitField<uint32_t, ChunkOffsetBits::kNext, kChunkIndexSize> {};
138   class SpaceBits
139       : public BitField<AllocationSpace, ChunkIndexBits::kNext, kSpaceTagSize> {
140   };
141 
142   uint32_t bitfield_;
143 };
144 
145 
146 // Mapping objects to their location after deserialization.
147 // This is used during building, but not at runtime by V8.
148 class BackReferenceMap : public AddressMapBase {
149  public:
BackReferenceMap()150   BackReferenceMap()
151       : no_allocation_(), map_(new HashMap(HashMap::PointersMatch)) {}
152 
~BackReferenceMap()153   ~BackReferenceMap() { delete map_; }
154 
Lookup(HeapObject * obj)155   BackReference Lookup(HeapObject* obj) {
156     HashMap::Entry* entry = LookupEntry(map_, obj, false);
157     return entry ? BackReference(GetValue(entry)) : BackReference();
158   }
159 
Add(HeapObject * obj,BackReference b)160   void Add(HeapObject* obj, BackReference b) {
161     DCHECK(b.is_valid());
162     DCHECK_NULL(LookupEntry(map_, obj, false));
163     HashMap::Entry* entry = LookupEntry(map_, obj, true);
164     SetValue(entry, b.bitfield());
165   }
166 
AddSourceString(String * string)167   void AddSourceString(String* string) {
168     Add(string, BackReference::SourceReference());
169   }
170 
AddGlobalProxy(HeapObject * global_proxy)171   void AddGlobalProxy(HeapObject* global_proxy) {
172     Add(global_proxy, BackReference::GlobalProxyReference());
173   }
174 
175  private:
176   DisallowHeapAllocation no_allocation_;
177   HashMap* map_;
178   DISALLOW_COPY_AND_ASSIGN(BackReferenceMap);
179 };
180 
181 }  // namespace internal
182 }  // namespace v8
183 
184 #endif  // V8_ADDRESS_MAP_H_
185