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 class 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. 32 class 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. 58 class 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 SizeFor(int number_of_all_descriptors)161 static constexpr int SizeFor(int number_of_all_descriptors) { 162 return OffsetOfDescriptorAt(number_of_all_descriptors); 163 } OffsetOfDescriptorAt(int descriptor)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 ToDetailsIndex(int descriptor_number)205 static constexpr int ToDetailsIndex(int descriptor_number) { 206 return (descriptor_number * kEntrySize) + kEntryDetailsIndex; 207 } 208 209 // Conversion from descriptor number to array indices. ToKeyIndex(int descriptor_number)210 static constexpr int ToKeyIndex(int descriptor_number) { 211 return (descriptor_number * kEntrySize) + kEntryKeyIndex; 212 } 213 ToValueIndex(int descriptor_number)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 243 class 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. decode(unsigned mark_compact_epoch,int16_t raw_value)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. encode(unsigned mark_compact_epoch,int16_t value)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