1// Copyright 2017 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_OBJECTS_DESCRIPTOR_ARRAY_H_
6#define V8_OBJECTS_DESCRIPTOR_ARRAY_H_
7
8#include "src/objects.h"
9#include "src/objects/fixed-array.h"
10#include "src/objects/struct.h"
11#include "src/utils.h"
12
13// Has to be the last include (doesn't have include guards):
14#include "src/objects/object-macros.h"
15
16namespace v8 {
17namespace internal {
18
19template <typename T>
20class Handle;
21
22class Isolate;
23
24// An EnumCache is a pair used to hold keys and indices caches.
25class EnumCache : public Tuple2 {
26 public:
27 DECL_ACCESSORS(keys, FixedArray)
28 DECL_ACCESSORS(indices, FixedArray)
29
30 DECL_CAST(EnumCache)
31
32 // Layout description.
33 static const int kKeysOffset = kValue1Offset;
34 static const int kIndicesOffset = kValue2Offset;
35
36 OBJECT_CONSTRUCTORS(EnumCache, Tuple2);
37};
38
39// A DescriptorArray is a custom array that holds instance descriptors.
40// It has the following layout:
41// Header:
42// [16:0 bits]: number_of_all_descriptors (including slack)
43// [32:16 bits]: number_of_descriptors
44// [48:32 bits]: raw_number_of_marked_descriptors (used by GC)
45// [64:48 bits]: alignment filler
46// [kEnumCacheOffset]: enum cache
47// Elements:
48// [kHeaderSize + 0]: first key (and internalized String)
49// [kHeaderSize + 1]: first descriptor details (see PropertyDetails)
50// [kHeaderSize + 2]: first value for constants / Smi(1) when not used
51// Slack:
52// [kHeaderSize + number of descriptors * 3]: start of slack
53// The "value" fields store either values or field types. A field type is either
54// FieldType::None(), FieldType::Any() or a weak reference to a Map. All other
55// references are strong.
56class DescriptorArray : public HeapObject {
57 public:
58 DECL_INT16_ACCESSORS(number_of_all_descriptors)
59 DECL_INT16_ACCESSORS(number_of_descriptors)
60 inline int16_t number_of_slack_descriptors() const;
61 inline int number_of_entries() const;
62 DECL_ACCESSORS(enum_cache, EnumCache)
63
64 void ClearEnumCache();
65 inline void CopyEnumCacheFrom(DescriptorArray array);
66 static void InitializeOrChangeEnumCache(Handle<DescriptorArray> descriptors,
67 Isolate* isolate,
68 Handle<FixedArray> keys,
69 Handle<FixedArray> indices);
70
71 // Accessors for fetching instance descriptor at descriptor number.
72 inline Name GetKey(int descriptor_number) const;
73 inline Object GetStrongValue(int descriptor_number);
74 inline void SetValue(int descriptor_number, Object value);
75 inline MaybeObject GetValue(int descriptor_number);
76 inline PropertyDetails GetDetails(int descriptor_number);
77 inline int GetFieldIndex(int descriptor_number);
78 inline FieldType GetFieldType(int descriptor_number);
79
80 inline Name GetSortedKey(int descriptor_number);
81 inline int GetSortedKeyIndex(int descriptor_number);
82 inline void SetSortedKey(int pointer, int descriptor_number);
83
84 // Accessor for complete descriptor.
85 inline void Set(int descriptor_number, Descriptor* desc);
86 inline void Set(int descriptor_number, Name key, MaybeObject value,
87 PropertyDetails details);
88 void Replace(int descriptor_number, Descriptor* descriptor);
89
90 // Generalizes constness, representation and field type of all field
91 // descriptors.
92 void GeneralizeAllFields();
93
94 // Append automatically sets the enumeration index. This should only be used
95 // to add descriptors in bulk at the end, followed by sorting the descriptor
96 // array.
97 inline void Append(Descriptor* desc);
98
99 static Handle<DescriptorArray> CopyUpTo(Isolate* isolate,
100 Handle<DescriptorArray> desc,
101 int enumeration_index, int slack = 0);
102
103 static Handle<DescriptorArray> CopyUpToAddAttributes(
104 Isolate* isolate, Handle<DescriptorArray> desc, int enumeration_index,
105 PropertyAttributes attributes, int slack = 0);
106
107 static Handle<DescriptorArray> CopyForFastObjectClone(
108 Isolate* isolate, Handle<DescriptorArray> desc, int enumeration_index,
109 int slack = 0);
110
111 // Sort the instance descriptors by the hash codes of their keys.
112 void Sort();
113
114 // Search the instance descriptors for given name.
115 V8_INLINE int Search(Name name, int number_of_own_descriptors);
116 V8_INLINE int Search(Name name, Map map);
117
118 // As the above, but uses DescriptorLookupCache and updates it when
119 // necessary.
120 V8_INLINE int SearchWithCache(Isolate* isolate, Name name, Map map);
121
122 bool IsEqualUpTo(DescriptorArray desc, int nof_descriptors);
123
124 // Allocates a DescriptorArray, but returns the singleton
125 // empty descriptor array object if number_of_descriptors is 0.
126 V8_EXPORT_PRIVATE static Handle<DescriptorArray> Allocate(
127 Isolate* isolate, int nof_descriptors, int slack,
128 AllocationType allocation = AllocationType::kYoung);
129
130 void Initialize(EnumCache enum_cache, HeapObject undefined_value,
131 int nof_descriptors, int slack);
132
133 DECL_CAST(DescriptorArray)
134
135 // Constant for denoting key was not found.
136 static const int kNotFound = -1;
137
138 // Layout description.
139#define DESCRIPTOR_ARRAY_FIELDS(V) \
140 V(kNumberOfAllDescriptorsOffset, kUInt16Size) \
141 V(kNumberOfDescriptorsOffset, kUInt16Size) \
142 V(kRawNumberOfMarkedDescriptorsOffset, kUInt16Size) \
143 V(kFiller16BitsOffset, kUInt16Size) \
144 V(kPointersStartOffset, 0) \
145 V(kEnumCacheOffset, kTaggedSize) \
146 V(kHeaderSize, 0)
147
148 DEFINE_FIELD_OFFSET_CONSTANTS(HeapObject::kHeaderSize,
149 DESCRIPTOR_ARRAY_FIELDS)
150#undef DESCRIPTOR_ARRAY_FIELDS
151
152 STATIC_ASSERT(IsAligned(kPointersStartOffset, kTaggedSize));
153 STATIC_ASSERT(IsAligned(kHeaderSize, kTaggedSize));
154
155 // Garbage collection support.
156 DECL_INT16_ACCESSORS(raw_number_of_marked_descriptors)
157 // Atomic compare-and-swap operation on the raw_number_of_marked_descriptors.
158 int16_t CompareAndSwapRawNumberOfMarkedDescriptors(int16_t expected,
159 int16_t value);
160 int16_t UpdateNumberOfMarkedDescriptors(unsigned mark_compact_epoch,
161 int16_t number_of_marked_descriptors);
162
163 static constexpr int SizeFor(int number_of_all_descriptors) {
164 return offset(number_of_all_descriptors * kEntrySize);
165 }
166 static constexpr int OffsetOfDescriptorAt(int descriptor) {
167 return offset(descriptor * kEntrySize);
168 }
169 inline ObjectSlot GetFirstPointerSlot();
170 inline ObjectSlot GetDescriptorSlot(int descriptor);
171 inline ObjectSlot GetKeySlot(int descriptor);
172 inline MaybeObjectSlot GetValueSlot(int descriptor);
173
174 using BodyDescriptor = FlexibleWeakBodyDescriptor<kPointersStartOffset>;
175
176 // Layout of descriptor.
177 // Naming is consistent with Dictionary classes for easy templating.
178 static const int kEntryKeyIndex = 0;
179 static const int kEntryDetailsIndex = 1;
180 static const int kEntryValueIndex = 2;
181 static const int kEntrySize = 3;
182
183 // Print all the descriptors.
184 void PrintDescriptors(std::ostream& os);
185 void PrintDescriptorDetails(std::ostream& os, int descriptor,
186 PropertyDetails::PrintMode mode);
187
188 DECL_PRINTER(DescriptorArray)
189 DECL_VERIFIER(DescriptorArray)
190
191#ifdef DEBUG
192 // Is the descriptor array sorted and without duplicates?
193 V8_EXPORT_PRIVATE bool IsSortedNoDuplicates(int valid_descriptors = -1);
194
195 // Are two DescriptorArrays equal?
196 bool IsEqualTo(DescriptorArray other);
197#endif
198
199 static constexpr int ToDetailsIndex(int descriptor_number) {
200 return (descriptor_number * kEntrySize) + kEntryDetailsIndex;
201 }
202
203 // Conversion from descriptor number to array indices.
204 static constexpr int ToKeyIndex(int descriptor_number) {
205 return (descriptor_number * kEntrySize) + kEntryKeyIndex;
206 }
207
208 static constexpr int ToValueIndex(int descriptor_number) {
209 return (descriptor_number * kEntrySize) + kEntryValueIndex;
210 }
211
212 private:
213 DECL_INT16_ACCESSORS(filler16bits)
214 // Low-level per-element accessors.
215 static constexpr int offset(int index) {
216 return kHeaderSize + index * kTaggedSize;
217 }
218 inline int length() const;
219 inline MaybeObject get(int index) const;
220 inline void set(int index, MaybeObject value);
221
222 // Transfer a complete descriptor from the src descriptor array to this
223 // descriptor array.
224 void CopyFrom(int index, DescriptorArray src);
225
226 // Swap first and second descriptor.
227 inline void SwapSortedKeys(int first, int second);
228
229 OBJECT_CONSTRUCTORS(DescriptorArray, HeapObject);
230};
231
232class NumberOfMarkedDescriptors {
233 public:
234// Bit positions for |bit_field|.
235#define BIT_FIELD_FIELDS(V, _) \
236 V(Epoch, unsigned, 2, _) \
237 V(Marked, int16_t, 14, _)
238 DEFINE_BIT_FIELDS(BIT_FIELD_FIELDS)
239#undef BIT_FIELD_FIELDS
240 static const int kMaxNumberOfMarkedDescriptors = Marked::kMax;
241 // Decodes the raw value of the number of marked descriptors for the
242 // given mark compact garbage collection epoch.
243 static inline int16_t decode(unsigned mark_compact_epoch, int16_t raw_value) {
244 unsigned epoch_from_value = Epoch::decode(static_cast<uint16_t>(raw_value));
245 int16_t marked_from_value =
246 Marked::decode(static_cast<uint16_t>(raw_value));
247 unsigned actual_epoch = mark_compact_epoch & Epoch::kMask;
248 if (actual_epoch == epoch_from_value) return marked_from_value;
249 // If the epochs do not match, then either the raw_value is zero (freshly
250 // allocated descriptor array) or the epoch from value lags by 1.
251 DCHECK_IMPLIES(raw_value != 0,
252 Epoch::decode(epoch_from_value + 1) == actual_epoch);
253 // Not matching epochs means that the no descriptors were marked in the
254 // current epoch.
255 return 0;
256 }
257
258 // Encodes the number of marked descriptors for the given mark compact
259 // garbage collection epoch.
260 static inline int16_t encode(unsigned mark_compact_epoch, int16_t value) {
261 // TODO(ulan): avoid casting to int16_t by adding support for uint16_t
262 // atomics.
263 return static_cast<int16_t>(
264 Epoch::encode(mark_compact_epoch & Epoch::kMask) |
265 Marked::encode(value));
266 }
267};
268
269} // namespace internal
270} // namespace v8
271
272#include "src/objects/object-macros-undef.h"
273
274#endif // V8_OBJECTS_DESCRIPTOR_ARRAY_H_
275