1 // Copyright 2017 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_MAP_UPDATER_H_ 6 #define V8_OBJECTS_MAP_UPDATER_H_ 7 8 #include "src/common/globals.h" 9 #include "src/handles/handles.h" 10 #include "src/objects/elements-kind.h" 11 #include "src/objects/field-type.h" 12 #include "src/objects/map.h" 13 #include "src/objects/property-details.h" 14 15 namespace v8 { 16 namespace internal { 17 18 // The |MapUpdater| class implements all sorts of map reconfigurations 19 // including changes of elements kind, property attributes, property kind, 20 // property location and field representations/type changes. It ensures that 21 // the reconfigured map and all the intermediate maps are properly integrated 22 // into the existing transition tree. 23 // 24 // To avoid high degrees over polymorphism, and to stabilize quickly, on every 25 // rewrite the new type is deduced by merging the current type with any 26 // potential new (partial) version of the type in the transition tree. 27 // To do this, on each rewrite: 28 // - Search the root of the transition tree using FindRootMap, remember 29 // the integrity level (preventExtensions/seal/freeze) of transitions. 30 // - Find/create a |root_map| with the requested |new_elements_kind|. 31 // - Find |target_map|, the newest matching version of this map using the 32 // "updated" |old_map|'s descriptor array (i.e. whose entry at |modify_index| 33 // is considered to be of |new_kind| and having |new_attributes|) to walk 34 // the transition tree. If there was an integrity level transition on the path 35 // to the old map, use the descriptor array of the map preceding the first 36 // integrity level transition (|integrity_source_map|), and try to replay 37 // the integrity level transition afterwards. 38 // - Merge/generalize the "updated" descriptor array of the |old_map| and 39 // descriptor array of the |target_map|. 40 // - Generalize the |modify_index| descriptor using |new_representation| and 41 // |new_field_type|. 42 // - Walk the tree again starting from the root towards |target_map|. Stop at 43 // |split_map|, the first map whose descriptor array does not match the merged 44 // descriptor array. 45 // - If |target_map| == |split_map|, and there are no integrity level 46 // transitions, |target_map| is in the expected state. Return it. 47 // - Otherwise, invalidate the outdated transition target from |target_map|, and 48 // replace its transition tree with a new branch for the updated descriptors. 49 // - If the |old_map| had integrity level transition, create the new map for it. 50 class V8_EXPORT_PRIVATE MapUpdater { 51 public: 52 MapUpdater(Isolate* isolate, Handle<Map> old_map); 53 54 // Prepares for reconfiguring of a property at |descriptor| to data field 55 // with given |attributes| and |representation|/|field_type| and 56 // performs the steps 1-6. 57 Handle<Map> ReconfigureToDataField(InternalIndex descriptor, 58 PropertyAttributes attributes, 59 PropertyConstness constness, 60 Representation representation, 61 Handle<FieldType> field_type); 62 63 // Prepares for reconfiguring elements kind and performs the steps 1-6. 64 Handle<Map> ReconfigureElementsKind(ElementsKind elements_kind); 65 66 // Prepares for updating deprecated map to most up-to-date non-deprecated 67 // version and performs the steps 1-6. 68 Handle<Map> Update(); 69 70 // As above but does not mutate maps; instead, we attempt to replay existing 71 // transitions to find an updated map. No lock is taken. 72 static base::Optional<Map> TryUpdateNoLock(Isolate* isolate, Map old_map, 73 ConcurrencyMode cmode) 74 V8_WARN_UNUSED_RESULT; 75 76 static Handle<Map> ReconfigureExistingProperty(Isolate* isolate, 77 Handle<Map> map, 78 InternalIndex descriptor, 79 PropertyKind kind, 80 PropertyAttributes attributes, 81 PropertyConstness constness); 82 83 static void GeneralizeField(Isolate* isolate, Handle<Map> map, 84 InternalIndex modify_index, 85 PropertyConstness new_constness, 86 Representation new_representation, 87 Handle<FieldType> new_field_type); 88 89 // Completes inobject slack tracking for the transition tree starting at the 90 // initial map. 91 static void CompleteInobjectSlackTracking(Isolate* isolate, Map initial_map); 92 93 private: 94 enum State { 95 kInitialized, 96 kAtRootMap, 97 kAtTargetMap, 98 kAtIntegrityLevelSource, 99 kEnd 100 }; 101 102 // Updates map to the most up-to-date non-deprecated version. 103 static inline Handle<Map> UpdateMapNoLock(Isolate* isolate, 104 Handle<Map> old_map); 105 106 // Prepares for updating deprecated map to most up-to-date non-deprecated 107 // version and performs the steps 1-6. 108 // Unlike the Update() entry point it doesn't lock the map_updater_access 109 // mutex. 110 Handle<Map> UpdateImpl(); 111 112 // Try to reconfigure property in-place without rebuilding transition tree 113 // and creating new maps. See implementation for details. 114 State TryReconfigureToDataFieldInplace(); 115 116 // Step 1. 117 // - Search the root of the transition tree using FindRootMap. 118 // - Find/create a |root_map_| with requested |new_elements_kind_|. 119 State FindRootMap(); 120 121 // Step 2. 122 // - Find |target_map|, the newest matching version of this map using the 123 // "updated" |old_map|'s descriptor array (i.e. whose entry at 124 // |modify_index| is considered to be of |new_kind| and having 125 // |new_attributes|) to walk the transition tree. If there was an integrity 126 // level transition on the path to the old map, use the descriptor array 127 // of the map preceding the first integrity level transition 128 // (|integrity_source_map|), and try to replay the integrity level 129 // transition afterwards. 130 State FindTargetMap(); 131 132 // Step 3. 133 // - Merge/generalize the "updated" descriptor array of the |old_map_| and 134 // descriptor array of the |target_map_|. 135 // - Generalize the |modified_descriptor_| using |new_representation| and 136 // |new_field_type_|. 137 Handle<DescriptorArray> BuildDescriptorArray(); 138 139 // Step 4. 140 // - Walk the tree again starting from the root towards |target_map|. Stop at 141 // |split_map|, the first map whose descriptor array does not match the 142 // merged descriptor array. 143 Handle<Map> FindSplitMap(Handle<DescriptorArray> descriptors); 144 145 // Step 5. 146 // - If |target_map| == |split_map|, |target_map| is in the expected state. 147 // Return it. 148 // - Otherwise, invalidate the outdated transition target from |target_map|, 149 // and replace its transition tree with a new branch for the updated 150 // descriptors. 151 State ConstructNewMap(); 152 153 // Step 6. 154 // - If the |old_map| had integrity level transition, create the new map 155 // for it. 156 State ConstructNewMapWithIntegrityLevelTransition(); 157 158 // When a requested reconfiguration can not be done the result is a copy 159 // of |old_map_| in dictionary mode. 160 State Normalize(const char* reason); 161 162 // Returns name of a |descriptor| property. 163 inline Name GetKey(InternalIndex descriptor) const; 164 165 // Returns property details of a |descriptor| in "updated" |old_descriptors_| 166 // array. 167 inline PropertyDetails GetDetails(InternalIndex descriptor) const; 168 169 // Returns value of a |descriptor| with kDescriptor location in "updated" 170 // |old_descriptors_| array. 171 inline Object GetValue(InternalIndex descriptor) const; 172 173 // Returns field type for a |descriptor| with kField location in "updated" 174 // |old_descriptors_| array. 175 inline FieldType GetFieldType(InternalIndex descriptor) const; 176 177 // If a |descriptor| property in "updated" |old_descriptors_| has kField 178 // location then returns its field type, otherwise computes the optimal field 179 // type for the descriptor's value and |representation|. The |location| 180 // value must be a pre-fetched location for |descriptor|. 181 inline Handle<FieldType> GetOrComputeFieldType( 182 InternalIndex descriptor, PropertyLocation location, 183 Representation representation) const; 184 185 // If a |descriptor| property in given |descriptors| array has kField 186 // location then returns its field type, otherwise computes the optimal field 187 // type for the descriptor's value and |representation|. 188 // The |location| value must be a pre-fetched location for |descriptor|. 189 inline Handle<FieldType> GetOrComputeFieldType( 190 Handle<DescriptorArray> descriptors, InternalIndex descriptor, 191 PropertyLocation location, Representation representation); 192 193 // Update field type of the given descriptor to new representation and new 194 // type. The type must be prepared for storing in descriptor array: 195 // it must be either a simple type or a map wrapped in a weak cell. 196 static void UpdateFieldType(Isolate* isolate, Handle<Map> map, 197 InternalIndex descriptor_number, 198 Handle<Name> name, 199 PropertyConstness new_constness, 200 Representation new_representation, 201 const MaybeObjectHandle& new_wrapped_type); 202 203 void GeneralizeField(Handle<Map> map, InternalIndex modify_index, 204 PropertyConstness new_constness, 205 Representation new_representation, 206 Handle<FieldType> new_field_type); 207 208 bool TrySaveIntegrityLevelTransitions(); 209 210 Isolate* isolate_; 211 Handle<Map> old_map_; 212 Handle<DescriptorArray> old_descriptors_; 213 Handle<Map> root_map_; 214 Handle<Map> target_map_; 215 Handle<Map> result_map_; 216 int old_nof_; 217 218 // Information about integrity level transitions. 219 bool has_integrity_level_transition_ = false; 220 PropertyAttributes integrity_level_ = NONE; 221 Handle<Symbol> integrity_level_symbol_; 222 Handle<Map> integrity_source_map_; 223 224 State state_ = kInitialized; 225 ElementsKind new_elements_kind_; 226 bool is_transitionable_fast_elements_kind_; 227 228 // If |modified_descriptor_.is_found()|, then the fields below form 229 // an "update" of the |old_map_|'s descriptors. 230 InternalIndex modified_descriptor_ = InternalIndex::NotFound(); 231 PropertyKind new_kind_ = PropertyKind::kData; 232 PropertyAttributes new_attributes_ = NONE; 233 PropertyConstness new_constness_ = PropertyConstness::kMutable; 234 PropertyLocation new_location_ = PropertyLocation::kField; 235 Representation new_representation_ = Representation::None(); 236 237 // Data specific to kField location. 238 Handle<FieldType> new_field_type_; 239 240 // Data specific to kDescriptor location. 241 Handle<Object> new_value_; 242 }; 243 244 } // namespace internal 245 } // namespace v8 246 247 #endif // V8_OBJECTS_MAP_UPDATER_H_ 248