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