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