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