1 // Copyright 2012 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_TRANSITIONS_H_ 6 #define V8_OBJECTS_TRANSITIONS_H_ 7 8 #include "src/common/checks.h" 9 #include "src/objects/descriptor-array.h" 10 #include "src/objects/elements-kind.h" 11 #include "src/objects/map.h" 12 #include "src/objects/maybe-object.h" 13 #include "src/objects/name.h" 14 #include "src/objects/objects.h" 15 16 // Has to be the last include (doesn't have include guards): 17 #include "src/objects/object-macros.h" 18 19 namespace v8 { 20 namespace internal { 21 22 // TransitionsAccessor is a helper class to encapsulate access to the various 23 // ways a Map can store transitions to other maps in its respective field at 24 // Map::kTransitionsOrPrototypeInfo. 25 // It caches state information internally, which becomes stale when a Map's 26 // transitions storage changes or when a GC cycle clears dead transitions; 27 // so while a TransitionsAccessor instance can be used for several read-only 28 // operations in a row (provided no GC happens between them), it must be 29 // discarded and recreated after "Insert" and "UpdateHandler" operations. 30 // 31 // Internal details: a Map's field either holds an in-place weak reference to a 32 // transition target, or a StoreIC handler for a transitioning store (which in 33 // turn points to its target map), or a TransitionArray for several target maps 34 // and/or handlers as well as prototype and ElementsKind transitions. Property 35 // details (and in case of inline target storage, the key) are retrieved from 36 // the target map's descriptor array. Stored transitions are weak in the GC 37 // sense: both single transitions stored inline and TransitionArray fields are 38 // cleared when the map they refer to is not otherwise reachable. 39 class V8_EXPORT_PRIVATE TransitionsAccessor { 40 public: 41 // For concurrent access, use the other constructor. 42 inline TransitionsAccessor(Isolate* isolate, Map map, 43 DisallowHeapAllocation* no_gc); 44 // {concurrent_access} signals that the TransitionsAccessor will only be used 45 // in background threads. It acquires a reader lock for critical paths, as 46 // well as blocking the accessor from modifying the TransitionsArray. 47 inline TransitionsAccessor(Isolate* isolate, Handle<Map> map, 48 bool concurrent_access = false); 49 // Insert a new transition into |map|'s transition array, extending it 50 // as necessary. 51 // Requires the constructor that takes a Handle<Map> to have been used. 52 // This TransitionsAccessor instance is unusable after this operation. 53 void Insert(Handle<Name> name, Handle<Map> target, SimpleTransitionFlag flag); 54 55 Map SearchTransition(Name name, PropertyKind kind, 56 PropertyAttributes attributes); 57 58 Map SearchSpecial(Symbol name); 59 // Returns true for non-property transitions like elements kind, or 60 // or frozen/sealed transitions. 61 static bool IsSpecialTransition(ReadOnlyRoots roots, Name name); 62 63 enum RequestedLocation { kAnyLocation, kFieldOnly }; 64 MaybeHandle<Map> FindTransitionToDataProperty( 65 Handle<Name> name, RequestedLocation requested_location = kAnyLocation); 66 FindTransitionToField(Handle<Name> name)67 MaybeHandle<Map> FindTransitionToField(Handle<Name> name) { 68 return FindTransitionToDataProperty(name, kFieldOnly); 69 } 70 71 inline Handle<String> ExpectedTransitionKey(); 72 inline Handle<Map> ExpectedTransitionTarget(); 73 74 int NumberOfTransitions(); 75 // The size of transition arrays are limited so they do not end up in large 76 // object space. Otherwise ClearNonLiveReferences would leak memory while 77 // applying in-place right trimming. 78 static const int kMaxNumberOfTransitions = 1024 + 512; 79 bool CanHaveMoreTransitions(); 80 inline Name GetKey(int transition_number); 81 inline Map GetTarget(int transition_number); 82 static inline PropertyDetails GetTargetDetails(Name name, Map target); 83 84 static bool IsMatchingMap(Map target, Name name, PropertyKind kind, 85 PropertyAttributes attributes); 86 87 bool HasIntegrityLevelTransitionTo( 88 Map to, Symbol* out_symbol = nullptr, 89 PropertyAttributes* out_integrity_level = nullptr); 90 91 // ===== ITERATION ===== 92 using TraverseCallback = void (*)(Map map, void* data); 93 94 // Traverse the transition tree in postorder. TraverseTransitionTree(TraverseCallback callback,void * data)95 void TraverseTransitionTree(TraverseCallback callback, void* data) { 96 // Make sure that we do not allocate in the callback. 97 DisallowHeapAllocation no_allocation; 98 TraverseTransitionTreeInternal(callback, data, &no_allocation); 99 } 100 101 // ===== PROTOTYPE TRANSITIONS ===== 102 // When you set the prototype of an object using the __proto__ accessor you 103 // need a new map for the object (the prototype is stored in the map). In 104 // order not to multiply maps unnecessarily we store these as transitions in 105 // the original map. That way we can transition to the same map if the same 106 // prototype is set, rather than creating a new map every time. The 107 // transitions are in the form of a map where the keys are prototype objects 108 // and the values are the maps they transition to. 109 void PutPrototypeTransition(Handle<Object> prototype, Handle<Map> target_map); 110 Handle<Map> GetPrototypeTransition(Handle<Object> prototype); 111 112 // During the first-time Map::Update and Map::TryUpdate, the migration target 113 // map could be cached in the raw_transitions slot of the old map that is 114 // deprecated from the map transition tree. The next time old map is updated, 115 // we will check this cache slot as a shortcut to get the migration target 116 // map. 117 void SetMigrationTarget(Map migration_target); 118 Map GetMigrationTarget(); 119 120 #if DEBUG || OBJECT_PRINT 121 void PrintTransitions(std::ostream& os); 122 static void PrintOneTransition(std::ostream& os, Name key, Map target); 123 void PrintTransitionTree(); 124 void PrintTransitionTree(std::ostream& os, int level, 125 DisallowHeapAllocation* no_gc); 126 #endif 127 #if DEBUG 128 void CheckNewTransitionsAreConsistent(TransitionArray old_transitions, 129 Object transitions); 130 bool IsConsistentWithBackPointers(); 131 bool IsSortedNoDuplicates(); 132 #endif 133 134 protected: 135 // Allow tests to use inheritance to access internals. 136 enum Encoding { 137 kPrototypeInfo, 138 kUninitialized, 139 kMigrationTarget, 140 kWeakRef, 141 kFullTransitionArray, 142 }; 143 144 inline void Reload(); 145 encoding()146 inline Encoding encoding() { 147 DCHECK(!needs_reload_); 148 return encoding_; 149 } 150 151 inline int Capacity(); 152 153 inline TransitionArray transitions(); 154 155 private: 156 friend class MarkCompactCollector; // For HasSimpleTransitionTo. 157 friend class TransitionArray; 158 159 inline PropertyDetails GetSimpleTargetDetails(Map transition); 160 161 static inline Name GetSimpleTransitionKey(Map transition); 162 163 static inline Map GetTargetFromRaw(MaybeObject raw); 164 MarkNeedsReload()165 void MarkNeedsReload() { 166 #if DEBUG 167 needs_reload_ = true; 168 #endif 169 } 170 171 inline void Initialize(); 172 173 inline Map GetSimpleTransition(); 174 bool HasSimpleTransitionTo(Map map); 175 176 void ReplaceTransitions(MaybeObject new_transitions); 177 178 inline Map GetTargetMapFromWeakRef(); 179 180 void EnsureHasFullTransitionArray(); 181 void SetPrototypeTransitions(Handle<WeakFixedArray> proto_transitions); 182 WeakFixedArray GetPrototypeTransitions(); 183 184 void TraverseTransitionTreeInternal(TraverseCallback callback, void* data, 185 DisallowHeapAllocation* no_gc); 186 187 Isolate* isolate_; 188 Handle<Map> map_handle_; 189 Map map_; 190 MaybeObject raw_transitions_; 191 Encoding encoding_; 192 bool concurrent_access_; 193 #if DEBUG 194 bool needs_reload_; 195 #endif 196 197 DISALLOW_IMPLICIT_CONSTRUCTORS(TransitionsAccessor); 198 }; 199 200 // TransitionArrays are fixed arrays used to hold map transitions for property, 201 // constant, and element changes. 202 // The TransitionArray class exposes a very low-level interface. Most clients 203 // should use TransitionsAccessors. 204 // TransitionArrays have the following format: 205 // [0] Link to next TransitionArray (for weak handling support) (strong ref) 206 // [1] Smi(0) or WeakFixedArray of prototype transitions (strong ref) 207 // [2] Number of transitions (can be zero after trimming) 208 // [3] First transition key (strong ref) 209 // [4] First transition target (weak ref) 210 // ... 211 // [3 + number of transitions * kTransitionSize]: start of slack 212 class TransitionArray : public WeakFixedArray { 213 public: 214 DECL_CAST(TransitionArray) 215 216 inline WeakFixedArray GetPrototypeTransitions(); 217 inline bool HasPrototypeTransitions(); 218 219 // Accessors for fetching instance transition at transition number. 220 inline void SetKey(int transition_number, Name value); 221 inline Name GetKey(int transition_number); 222 inline HeapObjectSlot GetKeySlot(int transition_number); 223 224 inline Map GetTarget(int transition_number); 225 inline void SetRawTarget(int transition_number, MaybeObject target); 226 inline MaybeObject GetRawTarget(int transition_number); 227 inline HeapObjectSlot GetTargetSlot(int transition_number); 228 inline bool GetTargetIfExists(int transition_number, Isolate* isolate, 229 Map* target); 230 231 // Required for templatized Search interface. 232 inline Name GetKey(InternalIndex index); 233 static constexpr int kNotFound = -1; 234 235 inline Name GetSortedKey(int transition_number); GetSortedKeyIndex(int transition_number)236 int GetSortedKeyIndex(int transition_number) { return transition_number; } 237 inline int number_of_entries() const; 238 #ifdef DEBUG 239 V8_EXPORT_PRIVATE bool IsSortedNoDuplicates(); 240 #endif 241 242 V8_EXPORT_PRIVATE void Sort(); 243 244 void PrintInternal(std::ostream& os); 245 246 DECL_PRINTER(TransitionArray) 247 DECL_VERIFIER(TransitionArray) 248 249 // Layout for full transition arrays. 250 static const int kPrototypeTransitionsIndex = 0; 251 static const int kTransitionLengthIndex = 1; 252 static const int kFirstIndex = 2; 253 254 // Layout of map transition entries in full transition arrays. 255 static const int kEntryKeyIndex = 0; 256 static const int kEntryTargetIndex = 1; 257 static const int kEntrySize = 2; 258 259 // Conversion from transition number to array indices. ToKeyIndex(int transition_number)260 static int ToKeyIndex(int transition_number) { 261 return kFirstIndex + (transition_number * kEntrySize) + kEntryKeyIndex; 262 } 263 ToTargetIndex(int transition_number)264 static int ToTargetIndex(int transition_number) { 265 return kFirstIndex + (transition_number * kEntrySize) + kEntryTargetIndex; 266 } 267 268 inline int SearchNameForTesting(Name name, 269 int* out_insertion_index = nullptr); 270 271 inline Map SearchAndGetTargetForTesting(PropertyKind kind, Name name, 272 PropertyAttributes attributes); 273 274 private: 275 friend class Factory; 276 friend class MarkCompactCollector; 277 friend class TransitionsAccessor; 278 279 inline void SetNumberOfTransitions(int number_of_transitions); 280 281 inline int Capacity(); 282 283 // ===== PROTOTYPE TRANSITIONS ===== 284 // Cache format: 285 // 0: finger - index of the first free cell in the cache 286 // 1 + i: target map 287 static const int kProtoTransitionHeaderSize = 1; 288 static const int kMaxCachedPrototypeTransitions = 256; 289 290 inline void SetPrototypeTransitions(WeakFixedArray prototype_transitions); 291 292 static inline int NumberOfPrototypeTransitions( 293 WeakFixedArray proto_transitions); 294 static void SetNumberOfPrototypeTransitions(WeakFixedArray proto_transitions, 295 int value); 296 297 static const int kProtoTransitionNumberOfEntriesOffset = 0; 298 STATIC_ASSERT(kProtoTransitionHeaderSize == 1); 299 300 // Returns the fixed array length required to hold number_of_transitions 301 // transitions. LengthFor(int number_of_transitions)302 static int LengthFor(int number_of_transitions) { 303 return ToKeyIndex(number_of_transitions); 304 } 305 306 // Search a transition for a given kind, property name and attributes. 307 int Search(PropertyKind kind, Name name, PropertyAttributes attributes, 308 int* out_insertion_index = nullptr); 309 310 V8_EXPORT_PRIVATE Map SearchAndGetTarget(PropertyKind kind, Name name, 311 PropertyAttributes attributes); 312 313 // Search a non-property transition (like elements kind, observe or frozen 314 // transitions). 315 inline int SearchSpecial(Symbol symbol, int* out_insertion_index = nullptr); 316 // Search a first transition for a given property name. 317 inline int SearchName(Name name, int* out_insertion_index = nullptr); 318 int SearchDetails(int transition, PropertyKind kind, 319 PropertyAttributes attributes, int* out_insertion_index); 320 Map SearchDetailsAndGetTarget(int transition, PropertyKind kind, 321 PropertyAttributes attributes); 322 323 inline int number_of_transitions() const; 324 325 static bool CompactPrototypeTransitionArray(Isolate* isolate, 326 WeakFixedArray array); 327 328 static Handle<WeakFixedArray> GrowPrototypeTransitionArray( 329 Handle<WeakFixedArray> array, int new_capacity, Isolate* isolate); 330 331 // Compares two tuples <key, kind, attributes>, returns -1 if 332 // tuple1 is "less" than tuple2, 0 if tuple1 equal to tuple2 and 1 otherwise. 333 static inline int CompareKeys(Name key1, uint32_t hash1, PropertyKind kind1, 334 PropertyAttributes attributes1, Name key2, 335 uint32_t hash2, PropertyKind kind2, 336 PropertyAttributes attributes2); 337 338 // Compares keys, returns -1 if key1 is "less" than key2, 339 // 0 if key1 equal to key2 and 1 otherwise. 340 static inline int CompareNames(Name key1, uint32_t hash1, Name key2, 341 uint32_t hash2); 342 343 // Compares two details, returns -1 if details1 is "less" than details2, 344 // 0 if details1 equal to details2 and 1 otherwise. 345 static inline int CompareDetails(PropertyKind kind1, 346 PropertyAttributes attributes1, 347 PropertyKind kind2, 348 PropertyAttributes attributes2); 349 350 inline void Set(int transition_number, Name key, MaybeObject target); 351 352 OBJECT_CONSTRUCTORS(TransitionArray, WeakFixedArray); 353 }; 354 355 } // namespace internal 356 } // namespace v8 357 358 #include "src/objects/object-macros-undef.h" 359 360 #endif // V8_OBJECTS_TRANSITIONS_H_ 361