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/base/hashmap.h"
10#include "src/objects.h"
11
12namespace v8 {
13namespace internal {
14
15class AddressMapBase {
16 protected:
17  static void SetValue(base::HashMap::Entry* entry, uint32_t v) {
18    entry->value = reinterpret_cast<void*>(v);
19  }
20
21  static uint32_t GetValue(base::HashMap::Entry* entry) {
22    return static_cast<uint32_t>(reinterpret_cast<intptr_t>(entry->value));
23  }
24
25  inline static base::HashMap::Entry* LookupEntry(base::HashMap* map,
26                                                  HeapObject* obj,
27                                                  bool insert) {
28    if (insert) {
29      map->LookupOrInsert(Key(obj), Hash(obj));
30    }
31    return map->Lookup(Key(obj), Hash(obj));
32  }
33
34 private:
35  static uint32_t Hash(HeapObject* obj) {
36    return static_cast<int32_t>(reinterpret_cast<intptr_t>(obj->address()));
37  }
38
39  static void* Key(HeapObject* obj) {
40    return reinterpret_cast<void*>(obj->address());
41  }
42};
43
44class RootIndexMap : public AddressMapBase {
45 public:
46  explicit RootIndexMap(Isolate* isolate);
47
48  static const int kInvalidRootIndex = -1;
49
50  int Lookup(HeapObject* obj) {
51    base::HashMap::Entry* entry = LookupEntry(map_, obj, false);
52    if (entry) return GetValue(entry);
53    return kInvalidRootIndex;
54  }
55
56 private:
57  base::HashMap* map_;
58
59  DISALLOW_COPY_AND_ASSIGN(RootIndexMap);
60};
61
62class SerializerReference {
63 public:
64  SerializerReference() : bitfield_(Special(kInvalidValue)) {}
65
66  static SerializerReference FromBitfield(uint32_t bitfield) {
67    return SerializerReference(bitfield);
68  }
69
70  static SerializerReference BackReference(AllocationSpace space,
71                                           uint32_t chunk_index,
72                                           uint32_t chunk_offset) {
73    DCHECK(IsAligned(chunk_offset, kObjectAlignment));
74    DCHECK_NE(LO_SPACE, space);
75    return SerializerReference(
76        SpaceBits::encode(space) | ChunkIndexBits::encode(chunk_index) |
77        ChunkOffsetBits::encode(chunk_offset >> kObjectAlignmentBits));
78  }
79
80  static SerializerReference LargeObjectReference(uint32_t index) {
81    return SerializerReference(SpaceBits::encode(LO_SPACE) |
82                               ValueIndexBits::encode(index));
83  }
84
85  static SerializerReference AttachedReference(uint32_t index) {
86    return SerializerReference(SpaceBits::encode(kAttachedReferenceSpace) |
87                               ValueIndexBits::encode(index));
88  }
89
90  static SerializerReference DummyReference() {
91    return SerializerReference(Special(kDummyValue));
92  }
93
94  bool is_valid() const { return bitfield_ != Special(kInvalidValue); }
95
96  bool is_back_reference() const {
97    return SpaceBits::decode(bitfield_) <= LAST_SPACE;
98  }
99
100  AllocationSpace space() const {
101    DCHECK(is_back_reference());
102    return static_cast<AllocationSpace>(SpaceBits::decode(bitfield_));
103  }
104
105  uint32_t chunk_offset() const {
106    DCHECK(is_back_reference());
107    return ChunkOffsetBits::decode(bitfield_) << kObjectAlignmentBits;
108  }
109
110  uint32_t large_object_index() const {
111    DCHECK(is_back_reference());
112    DCHECK(chunk_index() == 0);
113    return ChunkOffsetBits::decode(bitfield_);
114  }
115
116  uint32_t chunk_index() const {
117    DCHECK(is_back_reference());
118    return ChunkIndexBits::decode(bitfield_);
119  }
120
121  uint32_t back_reference() const {
122    DCHECK(is_back_reference());
123    return bitfield_ & (ChunkOffsetBits::kMask | ChunkIndexBits::kMask);
124  }
125
126  bool is_attached_reference() const {
127    return SpaceBits::decode(bitfield_) == kAttachedReferenceSpace;
128  }
129
130  int attached_reference_index() const {
131    DCHECK(is_attached_reference());
132    return ValueIndexBits::decode(bitfield_);
133  }
134
135 private:
136  explicit SerializerReference(uint32_t bitfield) : bitfield_(bitfield) {}
137
138  inline static uint32_t Special(int value) {
139    return SpaceBits::encode(kSpecialValueSpace) |
140           ValueIndexBits::encode(value);
141  }
142
143  // We use the 32-bit bitfield to encode either a back reference, a special
144  // value, or an attached reference index.
145  // Back reference:
146  //   [ Space index             ] [ Chunk index ] [ Chunk offset ]
147  //   [ LO_SPACE                ] [ large object index           ]
148  // Special value
149  //   [ kSpecialValueSpace      ] [ Special value index          ]
150  // Attached reference
151  //   [ kAttachedReferenceSpace ] [ Attached reference index     ]
152
153  static const int kChunkOffsetSize = kPageSizeBits - kObjectAlignmentBits;
154  static const int kChunkIndexSize = 32 - kChunkOffsetSize - kSpaceTagSize;
155  static const int kValueIndexSize = kChunkOffsetSize + kChunkIndexSize;
156
157  static const int kSpecialValueSpace = LAST_SPACE + 1;
158  static const int kAttachedReferenceSpace = kSpecialValueSpace + 1;
159  STATIC_ASSERT(kAttachedReferenceSpace < (1 << kSpaceTagSize));
160
161  static const int kInvalidValue = 0;
162  static const int kDummyValue = 1;
163
164  // The chunk offset can also be used to encode the index of special values.
165  class ChunkOffsetBits : public BitField<uint32_t, 0, kChunkOffsetSize> {};
166  class ChunkIndexBits
167      : public BitField<uint32_t, ChunkOffsetBits::kNext, kChunkIndexSize> {};
168  class ValueIndexBits : public BitField<uint32_t, 0, kValueIndexSize> {};
169  STATIC_ASSERT(ChunkIndexBits::kNext == ValueIndexBits::kNext);
170  class SpaceBits : public BitField<int, kValueIndexSize, kSpaceTagSize> {};
171  STATIC_ASSERT(SpaceBits::kNext == 32);
172
173  uint32_t bitfield_;
174
175  friend class SerializerReferenceMap;
176};
177
178// Mapping objects to their location after deserialization.
179// This is used during building, but not at runtime by V8.
180class SerializerReferenceMap : public AddressMapBase {
181 public:
182  SerializerReferenceMap()
183      : no_allocation_(),
184        map_(base::HashMap::PointersMatch),
185        attached_reference_index_(0) {}
186
187  SerializerReference Lookup(HeapObject* obj) {
188    base::HashMap::Entry* entry = LookupEntry(&map_, obj, false);
189    return entry ? SerializerReference(GetValue(entry)) : SerializerReference();
190  }
191
192  void Add(HeapObject* obj, SerializerReference b) {
193    DCHECK(b.is_valid());
194    DCHECK_NULL(LookupEntry(&map_, obj, false));
195    base::HashMap::Entry* entry = LookupEntry(&map_, obj, true);
196    SetValue(entry, b.bitfield_);
197  }
198
199  SerializerReference AddAttachedReference(HeapObject* attached_reference) {
200    SerializerReference reference =
201        SerializerReference::AttachedReference(attached_reference_index_++);
202    Add(attached_reference, reference);
203    return reference;
204  }
205
206 private:
207  DisallowHeapAllocation no_allocation_;
208  base::HashMap map_;
209  int attached_reference_index_;
210  DISALLOW_COPY_AND_ASSIGN(SerializerReferenceMap);
211};
212
213}  // namespace internal
214}  // namespace v8
215
216#endif  // V8_ADDRESS_MAP_H_
217