descriptor-array.h 11.2 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2017 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_OBJECTS_DESCRIPTOR_ARRAY_H_
#define V8_OBJECTS_DESCRIPTOR_ARRAY_H_

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 18 19 20 21 22 23 24 25 26 27

// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"

namespace v8 {
namespace internal {

template <typename T>
class Handle;

class Isolate;

28 29
#include "torque-generated/src/objects/descriptor-array-tq.inc"

30
// An EnumCache is a pair used to hold keys and indices caches.
31
class EnumCache : public TorqueGeneratedEnumCache<EnumCache, Struct> {
32
 public:
33 34
  DECL_VERIFIER(EnumCache)

35
  TQ_OBJECT_CONSTRUCTORS(EnumCache)
36 37
};

38 39 40 41 42
// A DescriptorArray is a custom array that holds instance descriptors.
// It has the following layout:
//   Header:
//     [16:0  bits]: number_of_all_descriptors (including slack)
//     [32:16 bits]: number_of_descriptors
43
//     [48:32 bits]: raw_number_of_marked_descriptors (used by GC)
44 45 46 47 48 49 50 51
//     [64:48 bits]: alignment filler
//     [kEnumCacheOffset]: enum cache
//   Elements:
//     [kHeaderSize + 0]: first key (and internalized String)
//     [kHeaderSize + 1]: first descriptor details (see PropertyDetails)
//     [kHeaderSize + 2]: first value for constants / Smi(1) when not used
//   Slack:
//     [kHeaderSize + number of descriptors * 3]: start of slack
52 53 54
// The "value" fields store either values or field types. A field type is either
// FieldType::None(), FieldType::Any() or a weak reference to a Map. All other
// references are strong.
55 56
class DescriptorArray
    : public TorqueGeneratedDescriptorArray<DescriptorArray, HeapObject> {
57
 public:
58 59 60
  DECL_INT16_ACCESSORS(number_of_all_descriptors)
  DECL_INT16_ACCESSORS(number_of_descriptors)
  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 66 67 68
  static void InitializeOrChangeEnumCache(Handle<DescriptorArray> descriptors,
                                          Isolate* isolate,
                                          Handle<FixedArray> keys,
                                          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(PtrComprCageBase cage_base,
73
                     InternalIndex descriptor_number) const;
74
  inline Object GetStrongValue(InternalIndex descriptor_number);
75
  inline Object GetStrongValue(PtrComprCageBase cage_base,
76 77
                               InternalIndex descriptor_number);
  inline MaybeObject GetValue(InternalIndex descriptor_number);
78
  inline MaybeObject GetValue(PtrComprCageBase cage_base,
79 80 81 82
                              InternalIndex descriptor_number);
  inline PropertyDetails GetDetails(InternalIndex descriptor_number);
  inline int GetFieldIndex(InternalIndex descriptor_number);
  inline FieldType GetFieldType(InternalIndex descriptor_number);
83
  inline FieldType GetFieldType(PtrComprCageBase cage_base,
84
                                InternalIndex descriptor_number);
85

86
  inline Name GetSortedKey(int descriptor_number);
87
  inline Name GetSortedKey(PtrComprCageBase cage_base, int descriptor_number);
88 89 90
  inline int GetSortedKeyIndex(int descriptor_number);

  // Accessor for complete descriptor.
91 92
  inline void Set(InternalIndex descriptor_number, Descriptor* desc);
  inline void Set(InternalIndex descriptor_number, Name key, MaybeObject value,
93
                  PropertyDetails details);
94
  void Replace(InternalIndex descriptor_number, Descriptor* descriptor);
95 96 97 98 99 100 101 102 103 104

  // Generalizes constness, representation and field type of all field
  // descriptors.
  void GeneralizeAllFields();

  // Append automatically sets the enumeration index. This should only be used
  // to add descriptors in bulk at the end, followed by sorting the descriptor
  // array.
  inline void Append(Descriptor* desc);

105 106
  static Handle<DescriptorArray> CopyUpTo(Isolate* isolate,
                                          Handle<DescriptorArray> desc,
107 108 109
                                          int enumeration_index, int slack = 0);

  static Handle<DescriptorArray> CopyUpToAddAttributes(
110
      Isolate* isolate, Handle<DescriptorArray> desc, int enumeration_index,
111 112
      PropertyAttributes attributes, int slack = 0);

113 114 115 116
  static Handle<DescriptorArray> CopyForFastObjectClone(
      Isolate* isolate, Handle<DescriptorArray> desc, int enumeration_index,
      int slack = 0);

117
  // Sort the instance descriptors by the hash codes of their keys.
118
  V8_EXPORT_PRIVATE void Sort();
119

120 121 122 123 124 125 126
  // Search the instance descriptors for given name. {concurrent_search} signals
  // if we are doing the search on a background thread. If so, we will sacrifice
  // speed for thread-safety.
  V8_INLINE InternalIndex Search(Name name, int number_of_own_descriptors,
                                 bool concurrent_search = false);
  V8_INLINE InternalIndex Search(Name name, Map map,
                                 bool concurrent_search = false);
127 128 129

  // As the above, but uses DescriptorLookupCache and updates it when
  // necessary.
130
  V8_INLINE InternalIndex SearchWithCache(Isolate* isolate, Name name, Map map);
131

132
  bool IsEqualUpTo(DescriptorArray desc, int nof_descriptors);
133 134 135

  // Allocates a DescriptorArray, but returns the singleton
  // empty descriptor array object if number_of_descriptors is 0.
136
  template <typename IsolateT>
137
  V8_EXPORT_PRIVATE static Handle<DescriptorArray> Allocate(
138
      IsolateT* 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 145 146

  // Constant for denoting key was not found.
  static const int kNotFound = -1;

147
  STATIC_ASSERT(IsAligned(kStartOfWeakFieldsOffset, kTaggedSize));
148 149 150
  STATIC_ASSERT(IsAligned(kHeaderSize, kTaggedSize));

  // Garbage collection support.
151 152 153 154
  DECL_INT16_ACCESSORS(raw_number_of_marked_descriptors)
  // Atomic compare-and-swap operation on the raw_number_of_marked_descriptors.
  int16_t CompareAndSwapRawNumberOfMarkedDescriptors(int16_t expected,
                                                     int16_t value);
155
  int16_t UpdateNumberOfMarkedDescriptors(unsigned mark_compact_epoch,
156 157
                                          int16_t number_of_marked_descriptors);

158
  static constexpr int SizeFor(int number_of_all_descriptors) {
159
    return OffsetOfDescriptorAt(number_of_all_descriptors);
160 161
  }
  static constexpr int OffsetOfDescriptorAt(int descriptor) {
162
    return kDescriptorsOffset + descriptor * kEntrySize * kTaggedSize;
163 164 165 166
  }
  inline ObjectSlot GetFirstPointerSlot();
  inline ObjectSlot GetDescriptorSlot(int descriptor);

167 168 169 170
  static_assert(kEndOfStrongFieldsOffset == kStartOfWeakFieldsOffset,
                "Weak fields follow strong fields.");
  static_assert(kEndOfWeakFieldsOffset == kHeaderSize,
                "Weak fields extend up to the end of the header.");
171 172
  static_assert(kDescriptorsOffset == kHeaderSize,
                "Variable-size array follows header.");
173
  class BodyDescriptor;
174

175 176 177 178 179 180 181
  // Layout of descriptor.
  // Naming is consistent with Dictionary classes for easy templating.
  static const int kEntryKeyIndex = 0;
  static const int kEntryDetailsIndex = 1;
  static const int kEntryValueIndex = 2;
  static const int kEntrySize = 3;

182 183 184 185
  static const int kEntryKeyOffset = kEntryKeyIndex * kTaggedSize;
  static const int kEntryDetailsOffset = kEntryDetailsIndex * kTaggedSize;
  static const int kEntryValueOffset = kEntryValueIndex * kTaggedSize;

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 193
  DECL_VERIFIER(DescriptorArray)

194 195
#ifdef DEBUG
  // 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 201
#endif

202
  static constexpr int ToDetailsIndex(int descriptor_number) {
203
    return (descriptor_number * kEntrySize) + kEntryDetailsIndex;
204 205 206
  }

  // Conversion from descriptor number to array indices.
207
  static constexpr int ToKeyIndex(int descriptor_number) {
208
    return (descriptor_number * kEntrySize) + kEntryKeyIndex;
209 210
  }

211
  static constexpr int ToValueIndex(int descriptor_number) {
212
    return (descriptor_number * kEntrySize) + kEntryValueIndex;
213 214
  }

215 216 217 218
  using EntryKeyField = TaggedField<HeapObject, kEntryKeyOffset>;
  using EntryDetailsField = TaggedField<Smi, kEntryDetailsOffset>;
  using EntryValueField = TaggedField<MaybeObject, kEntryValueOffset>;

219
 private:
220
  friend class WebSnapshotDeserializer;
221
  DECL_INT16_ACCESSORS(filler16bits)
222

223 224 225 226
  inline void SetKey(InternalIndex descriptor_number, Name key);
  inline void SetValue(InternalIndex descriptor_number, MaybeObject value);
  inline void SetDetails(InternalIndex descriptor_number,
                         PropertyDetails details);
227

228 229
  // Transfer a complete descriptor from the src descriptor array to this
  // descriptor array.
230 231 232
  void CopyFrom(InternalIndex index, DescriptorArray src);

  inline void SetSortedKey(int pointer, int descriptor_number);
233 234 235 236

  // Swap first and second descriptor.
  inline void SwapSortedKeys(int first, int second);

237
  TQ_OBJECT_CONSTRUCTORS(DescriptorArray)
238 239
};

240 241 242 243 244 245 246 247 248 249 250
class NumberOfMarkedDescriptors {
 public:
// Bit positions for |bit_field|.
#define BIT_FIELD_FIELDS(V, _) \
  V(Epoch, unsigned, 2, _)     \
  V(Marked, int16_t, 14, _)
  DEFINE_BIT_FIELDS(BIT_FIELD_FIELDS)
#undef BIT_FIELD_FIELDS
  static const int kMaxNumberOfMarkedDescriptors = Marked::kMax;
  // Decodes the raw value of the number of marked descriptors for the
  // given mark compact garbage collection epoch.
251
  static inline int16_t decode(unsigned mark_compact_epoch, int16_t raw_value) {
252 253 254
    unsigned epoch_from_value = Epoch::decode(static_cast<uint16_t>(raw_value));
    int16_t marked_from_value =
        Marked::decode(static_cast<uint16_t>(raw_value));
255
    unsigned actual_epoch = mark_compact_epoch & Epoch::kMask;
256 257 258 259 260 261 262 263 264 265 266 267
    if (actual_epoch == epoch_from_value) return marked_from_value;
    // If the epochs do not match, then either the raw_value is zero (freshly
    // allocated descriptor array) or the epoch from value lags by 1.
    DCHECK_IMPLIES(raw_value != 0,
                   Epoch::decode(epoch_from_value + 1) == actual_epoch);
    // Not matching epochs means that the no descriptors were marked in the
    // current epoch.
    return 0;
  }

  // Encodes the number of marked descriptors for the given mark compact
  // garbage collection epoch.
268
  static inline int16_t encode(unsigned mark_compact_epoch, int16_t value) {
269 270 271 272 273 274 275 276
    // TODO(ulan): avoid casting to int16_t by adding support for uint16_t
    // atomics.
    return static_cast<int16_t>(
        Epoch::encode(mark_compact_epoch & Epoch::kMask) |
        Marked::encode(value));
  }
};

277 278 279 280 281 282
}  // namespace internal
}  // namespace v8

#include "src/objects/object-macros-undef.h"

#endif  // V8_OBJECTS_DESCRIPTOR_ARRAY_H_