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