descriptor-array.h 10.1 KB
Newer Older
1 2 3 4 5 6 7 8
// 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_

#include "src/objects.h"
9
#include "src/objects/fixed-array.h"
10
#include "src/objects/struct.h"
11
#include "src/utils.h"
12 13 14 15 16 17 18 19 20 21 22 23

// 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;

24 25 26
// An EnumCache is a pair used to hold keys and indices caches.
class EnumCache : public Tuple2 {
 public:
27 28
  DECL_ACCESSORS(keys, FixedArray)
  DECL_ACCESSORS(indices, FixedArray)
29

30
  DECL_CAST(EnumCache)
31 32 33 34 35

  // Layout description.
  static const int kKeysOffset = kValue1Offset;
  static const int kIndicesOffset = kValue2Offset;

36
  OBJECT_CONSTRUCTORS(EnumCache, Tuple2);
37 38
};

39 40 41 42 43
// 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
44
//     [48:32 bits]: raw_number_of_marked_descriptors (used by GC)
45 46 47 48 49 50 51 52
//     [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
53 54 55
// 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.
56
class DescriptorArray : public 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
  DECL_ACCESSORS(enum_cache, EnumCache)
63 64

  void ClearEnumCache();
65
  inline void CopyEnumCacheFrom(DescriptorArray array);
66 67 68 69
  static void InitializeOrChangeEnumCache(Handle<DescriptorArray> descriptors,
                                          Isolate* isolate,
                                          Handle<FixedArray> keys,
                                          Handle<FixedArray> indices);
70 71

  // Accessors for fetching instance descriptor at descriptor number.
72
  inline Name GetKey(int descriptor_number) const;
73 74
  inline Object GetStrongValue(int descriptor_number);
  inline void SetValue(int descriptor_number, Object value);
75
  inline MaybeObject GetValue(int descriptor_number);
76 77
  inline PropertyDetails GetDetails(int descriptor_number);
  inline int GetFieldIndex(int descriptor_number);
78
  inline FieldType GetFieldType(int descriptor_number);
79

80
  inline Name GetSortedKey(int descriptor_number);
81 82 83 84 85
  inline int GetSortedKeyIndex(int descriptor_number);
  inline void SetSortedKey(int pointer, int descriptor_number);

  // Accessor for complete descriptor.
  inline void Set(int descriptor_number, Descriptor* desc);
86
  inline void Set(int descriptor_number, Name key, MaybeObject value,
87 88 89 90 91 92 93 94 95 96 97 98
                  PropertyDetails details);
  void Replace(int descriptor_number, Descriptor* descriptor);

  // 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);

99 100
  static Handle<DescriptorArray> CopyUpTo(Isolate* isolate,
                                          Handle<DescriptorArray> desc,
101 102 103
                                          int enumeration_index, int slack = 0);

  static Handle<DescriptorArray> CopyUpToAddAttributes(
104
      Isolate* isolate, Handle<DescriptorArray> desc, int enumeration_index,
105 106
      PropertyAttributes attributes, int slack = 0);

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

111 112 113 114
  // Sort the instance descriptors by the hash codes of their keys.
  void Sort();

  // Search the instance descriptors for given name.
115 116
  V8_INLINE int Search(Name name, int number_of_own_descriptors);
  V8_INLINE int Search(Name name, Map map);
117 118 119

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

122
  bool IsEqualUpTo(DescriptorArray desc, int nof_descriptors);
123 124 125

  // Allocates a DescriptorArray, but returns the singleton
  // empty descriptor array object if number_of_descriptors is 0.
126 127 128
  static Handle<DescriptorArray> Allocate(
      Isolate* isolate, int nof_descriptors, int slack,
      PretenureFlag pretenure = NOT_TENURED);
129

130
  void Initialize(EnumCache enum_cache, HeapObject undefined_value,
131
                  int nof_descriptors, int slack);
132

133
  DECL_CAST(DescriptorArray)
134 135 136 137 138

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

  // Layout description.
139 140 141 142 143 144 145
#define DESCRIPTOR_ARRAY_FIELDS(V)                    \
  V(kNumberOfAllDescriptorsOffset, kUInt16Size)       \
  V(kNumberOfDescriptorsOffset, kUInt16Size)          \
  V(kRawNumberOfMarkedDescriptorsOffset, kUInt16Size) \
  V(kFiller16BitsOffset, kUInt16Size)                 \
  V(kPointersStartOffset, 0)                          \
  V(kEnumCacheOffset, kTaggedSize)                    \
146 147 148
  V(kHeaderSize, 0)

  DEFINE_FIELD_OFFSET_CONSTANTS(HeapObject::kHeaderSize,
149 150
                                DESCRIPTOR_ARRAY_FIELDS)
#undef DESCRIPTOR_ARRAY_FIELDS
151

152 153 154 155
  STATIC_ASSERT(IsAligned(kPointersStartOffset, kTaggedSize));
  STATIC_ASSERT(IsAligned(kHeaderSize, kTaggedSize));

  // Garbage collection support.
156 157 158 159 160 161 162
  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);
  int16_t UpdateNumberOfMarkedDescriptors(unsigned mark_compact_epoch,
                                          int16_t number_of_marked_descriptors);

163 164 165 166 167 168 169 170 171 172 173 174 175
  static constexpr int SizeFor(int number_of_all_descriptors) {
    return offset(number_of_all_descriptors * kEntrySize);
  }
  static constexpr int OffsetOfDescriptorAt(int descriptor) {
    return offset(descriptor * kEntrySize);
  }
  inline ObjectSlot GetFirstPointerSlot();
  inline ObjectSlot GetDescriptorSlot(int descriptor);
  inline ObjectSlot GetKeySlot(int descriptor);
  inline MaybeObjectSlot GetValueSlot(int descriptor);

  typedef FlexibleWeakBodyDescriptor<kPointersStartOffset> BodyDescriptor;

176 177 178 179 180 181 182 183
  // 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;

  // Print all the descriptors.
184
  void PrintDescriptors(std::ostream& os);
185 186
  void PrintDescriptorDetails(std::ostream& os, int descriptor,
                              PropertyDetails::PrintMode mode);
187

188
  DECL_PRINTER(DescriptorArray)
189 190
  DECL_VERIFIER(DescriptorArray)

191 192
#ifdef DEBUG
  // Is the descriptor array sorted and without duplicates?
193
  bool IsSortedNoDuplicates(int valid_descriptors = -1);
194 195

  // Are two DescriptorArrays equal?
196
  bool IsEqualTo(DescriptorArray other);
197 198
#endif

199
  static constexpr int ToDetailsIndex(int descriptor_number) {
200
    return (descriptor_number * kEntrySize) + kEntryDetailsIndex;
201 202 203
  }

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

208
  static constexpr int ToValueIndex(int descriptor_number) {
209
    return (descriptor_number * kEntrySize) + kEntryValueIndex;
210 211 212
  }

 private:
213 214 215
  DECL_INT16_ACCESSORS(filler16bits)
  // Low-level per-element accessors.
  static constexpr int offset(int index) {
216
    return kHeaderSize + index * kTaggedSize;
217 218
  }
  inline int length() const;
219 220
  inline MaybeObject get(int index) const;
  inline void set(int index, MaybeObject value);
221

222 223
  // Transfer a complete descriptor from the src descriptor array to this
  // descriptor array.
224
  void CopyFrom(int index, DescriptorArray src);
225 226 227 228

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

229
  OBJECT_CONSTRUCTORS(DescriptorArray, HeapObject);
230 231
};

232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268
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.
  static inline int16_t decode(unsigned mark_compact_epoch, int16_t raw_value) {
    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));
    unsigned actual_epoch = mark_compact_epoch & Epoch::kMask;
    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.
  static inline int16_t encode(unsigned mark_compact_epoch, int16_t value) {
    // 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));
  }
};

269 270 271 272 273 274
}  // namespace internal
}  // namespace v8

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

#endif  // V8_OBJECTS_DESCRIPTOR_ARRAY_H_