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