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