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