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
12namespace v8 {
13namespace internal {
14
15class AddressMapBase {
16 protected:
17  static void SetValue(HashMap::Entry* entry, uint32_t v) {
18    entry->value = reinterpret_cast<void*>(v);
19  }
20
21  static uint32_t GetValue(HashMap::Entry* entry) {
22    return static_cast<uint32_t>(reinterpret_cast<intptr_t>(entry->value));
23  }
24
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:
34  static uint32_t Hash(HeapObject* obj) {
35    return static_cast<int32_t>(reinterpret_cast<intptr_t>(obj->address()));
36  }
37
38  static void* Key(HeapObject* obj) {
39    return reinterpret_cast<void*>(obj->address());
40  }
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    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
63class BackReference {
64 public:
65  explicit BackReference(uint32_t bitfield) : bitfield_(bitfield) {}
66
67  BackReference() : bitfield_(kInvalidValue) {}
68
69  static BackReference SourceReference() { return BackReference(kSourceValue); }
70
71  static BackReference GlobalProxyReference() {
72    return BackReference(kGlobalProxyValue);
73  }
74
75  static BackReference LargeObjectReference(uint32_t index) {
76    return BackReference(SpaceBits::encode(LO_SPACE) |
77                         ChunkOffsetBits::encode(index));
78  }
79
80  static BackReference DummyReference() { return BackReference(kDummyValue); }
81
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
91  bool is_valid() const { return bitfield_ != kInvalidValue; }
92  bool is_source() const { return bitfield_ == kSourceValue; }
93  bool is_global_proxy() const { return bitfield_ == kGlobalProxyValue; }
94
95  AllocationSpace space() const {
96    DCHECK(is_valid());
97    return SpaceBits::decode(bitfield_);
98  }
99
100  uint32_t chunk_offset() const {
101    DCHECK(is_valid());
102    return ChunkOffsetBits::decode(bitfield_) << kObjectAlignmentBits;
103  }
104
105  uint32_t large_object_index() const {
106    DCHECK(is_valid());
107    DCHECK(chunk_index() == 0);
108    return ChunkOffsetBits::decode(bitfield_);
109  }
110
111  uint32_t chunk_index() const {
112    DCHECK(is_valid());
113    return ChunkIndexBits::decode(bitfield_);
114  }
115
116  uint32_t reference() const {
117    DCHECK(is_valid());
118    return bitfield_ & (ChunkOffsetBits::kMask | ChunkIndexBits::kMask);
119  }
120
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.
148class BackReferenceMap : public AddressMapBase {
149 public:
150  BackReferenceMap()
151      : no_allocation_(), map_(new HashMap(HashMap::PointersMatch)) {}
152
153  ~BackReferenceMap() { delete map_; }
154
155  BackReference Lookup(HeapObject* obj) {
156    HashMap::Entry* entry = LookupEntry(map_, obj, false);
157    return entry ? BackReference(GetValue(entry)) : BackReference();
158  }
159
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
167  void AddSourceString(String* string) {
168    Add(string, BackReference::SourceReference());
169  }
170
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