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