llint_slow_path_put_by_id can deadlock on a ConcurrentJITLock
[WebKit-https.git] / Source / JavaScriptCore / runtime / Structure.h
1 /*
2  * Copyright (C) 2008, 2009, 2012, 2013 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef Structure_h
27 #define Structure_h
28
29 #include "ClassInfo.h"
30 #include "ConcurrentJITLock.h"
31 #include "IndexingType.h"
32 #include "JSCJSValue.h"
33 #include "JSCell.h"
34 #include "JSType.h"
35 #include "PropertyName.h"
36 #include "PropertyNameArray.h"
37 #include "PropertyOffset.h"
38 #include "Protect.h"
39 #include "PutPropertySlot.h"
40 #include "StructureRareData.h"
41 #include "StructureTransitionTable.h"
42 #include "JSTypeInfo.h"
43 #include "Watchpoint.h"
44 #include "Weak.h"
45 #include <wtf/CompilationThread.h>
46 #include <wtf/PassRefPtr.h>
47 #include <wtf/PrintStream.h>
48 #include <wtf/RefCounted.h>
49 #include <wtf/text/StringImpl.h>
50
51
52 namespace JSC {
53
54 class LLIntOffsetsExtractor;
55 class PropertyNameArray;
56 class PropertyNameArrayData;
57 class PropertyTable;
58 class StructureChain;
59 class SlotVisitor;
60 class JSString;
61 struct DumpContext;
62
63 // The out-of-line property storage capacity to use when first allocating out-of-line
64 // storage. Note that all objects start out without having any out-of-line storage;
65 // this comes into play only on the first property store that exhausts inline storage.
66 static const unsigned initialOutOfLineCapacity = 4;
67
68 // The factor by which to grow out-of-line storage when it is exhausted, after the
69 // initial allocation.
70 static const unsigned outOfLineGrowthFactor = 2;
71
72 class Structure : public JSCell {
73 public:
74     friend class StructureTransitionTable;
75
76     typedef JSCell Base;
77     
78     static Structure* create(VM&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType = NonArray, unsigned inlineCapacity = 0);
79
80 protected:
81     void finishCreation(VM& vm)
82     {
83         Base::finishCreation(vm);
84         ASSERT(m_prototype);
85         ASSERT(m_prototype.isObject() || m_prototype.isNull());
86     }
87
88     void finishCreation(VM& vm, CreatingEarlyCellTag)
89     {
90         Base::finishCreation(vm, this, CreatingEarlyCell);
91         ASSERT(m_prototype);
92         ASSERT(m_prototype.isNull());
93         ASSERT(!vm.structureStructure);
94     }
95
96 public:
97     static void dumpStatistics();
98
99     JS_EXPORT_PRIVATE static Structure* addPropertyTransition(VM&, Structure*, PropertyName, unsigned attributes, JSCell* specificValue, PropertyOffset&, PutPropertySlot::Context = PutPropertySlot::UnknownContext);
100     static Structure* addPropertyTransitionToExistingStructureConcurrently(Structure*, StringImpl* uid, unsigned attributes, JSCell* specificValue, PropertyOffset&);
101     JS_EXPORT_PRIVATE static Structure* addPropertyTransitionToExistingStructure(Structure*, PropertyName, unsigned attributes, JSCell* specificValue, PropertyOffset&);
102     static Structure* removePropertyTransition(VM&, Structure*, PropertyName, PropertyOffset&);
103     JS_EXPORT_PRIVATE static Structure* changePrototypeTransition(VM&, Structure*, JSValue prototype);
104     JS_EXPORT_PRIVATE static Structure* despecifyFunctionTransition(VM&, Structure*, PropertyName);
105     static Structure* attributeChangeTransition(VM&, Structure*, PropertyName, unsigned attributes);
106     static Structure* toCacheableDictionaryTransition(VM&, Structure*);
107     static Structure* toUncacheableDictionaryTransition(VM&, Structure*);
108     static Structure* sealTransition(VM&, Structure*);
109     static Structure* freezeTransition(VM&, Structure*);
110     static Structure* preventExtensionsTransition(VM&, Structure*);
111     static Structure* nonPropertyTransition(VM&, Structure*, NonPropertyTransition);
112
113     bool isSealed(VM&);
114     bool isFrozen(VM&);
115     bool isExtensible() const { return !m_preventExtensions; }
116     bool didTransition() const { return m_didTransition; }
117     bool putWillGrowOutOfLineStorage();
118     JS_EXPORT_PRIVATE size_t suggestedNewOutOfLineStorageCapacity(); 
119
120     Structure* flattenDictionaryStructure(VM&, JSObject*);
121
122     static const bool needsDestruction = true;
123     static const bool hasImmortalStructure = true;
124     static void destroy(JSCell*);
125
126     // These should be used with caution.  
127     JS_EXPORT_PRIVATE PropertyOffset addPropertyWithoutTransition(VM&, PropertyName, unsigned attributes, JSCell* specificValue);
128     PropertyOffset removePropertyWithoutTransition(VM&, PropertyName);
129     void setPrototypeWithoutTransition(VM& vm, JSValue prototype) { m_prototype.set(vm, this, prototype); }
130         
131     bool isDictionary() const { return m_dictionaryKind != NoneDictionaryKind; }
132     bool isUncacheableDictionary() const { return m_dictionaryKind == UncachedDictionaryKind; }
133
134     bool propertyAccessesAreCacheable() { return m_dictionaryKind != UncachedDictionaryKind && !typeInfo().prohibitsPropertyCaching(); }
135
136     // Type accessors.
137     const TypeInfo& typeInfo() const { ASSERT(structure()->classInfo() == info()); return m_typeInfo; }
138     bool isObject() const { return typeInfo().isObject(); }
139
140     IndexingType indexingType() const { return m_indexingType & AllArrayTypes; }
141     IndexingType indexingTypeIncludingHistory() const { return m_indexingType; }
142         
143     bool mayInterceptIndexedAccesses() const
144     {
145         return !!(indexingTypeIncludingHistory() & MayHaveIndexedAccessors);
146     }
147         
148     bool anyObjectInChainMayInterceptIndexedAccesses() const;
149         
150     bool needsSlowPutIndexing() const;
151     NonPropertyTransition suggestedArrayStorageTransition() const;
152         
153     JSGlobalObject* globalObject() const { return m_globalObject.get(); }
154     void setGlobalObject(VM& vm, JSGlobalObject* globalObject) { m_globalObject.set(vm, this, globalObject); }
155         
156     JSValue storedPrototype() const { return m_prototype.get(); }
157     JSObject* storedPrototypeObject() const;
158     Structure* storedPrototypeStructure() const;
159     JSValue prototypeForLookup(ExecState*) const;
160     JSValue prototypeForLookup(JSGlobalObject*) const;
161     JSValue prototypeForLookup(CodeBlock*) const;
162     StructureChain* prototypeChain(VM&, JSGlobalObject*) const;
163     StructureChain* prototypeChain(ExecState*) const;
164     static void visitChildren(JSCell*, SlotVisitor&);
165         
166     // Will just the prototype chain intercept this property access?
167     bool prototypeChainMayInterceptStoreTo(VM&, PropertyName);
168         
169     bool transitionDidInvolveSpecificValue() const { return !!m_specificValueInPrevious; }
170         
171     Structure* previousID() const
172     {
173         ASSERT(structure()->classInfo() == info());
174         if (typeInfo().structureHasRareData())
175             return rareData()->previousID();
176         return previous();
177     }
178     bool transitivelyTransitionedFrom(Structure* structureToFind);
179
180     unsigned outOfLineCapacity() const
181     {
182         ASSERT(checkOffsetConsistency());
183             
184         unsigned outOfLineSize = this->outOfLineSize();
185
186         if (!outOfLineSize)
187             return 0;
188
189         if (outOfLineSize <= initialOutOfLineCapacity)
190             return initialOutOfLineCapacity;
191
192         ASSERT(outOfLineSize > initialOutOfLineCapacity);
193         COMPILE_ASSERT(outOfLineGrowthFactor == 2, outOfLineGrowthFactor_is_two);
194         return WTF::roundUpToPowerOfTwo(outOfLineSize);
195     }
196     unsigned outOfLineSize() const
197     {
198         ASSERT(checkOffsetConsistency());
199         ASSERT(structure()->classInfo() == info());
200             
201         return numberOfOutOfLineSlotsForLastOffset(m_offset);
202     }
203     bool hasInlineStorage() const
204     {
205         return !!m_inlineCapacity;
206     }
207     unsigned inlineCapacity() const
208     {
209         return m_inlineCapacity;
210     }
211     unsigned inlineSize() const
212     {
213         return std::min<unsigned>(m_offset + 1, m_inlineCapacity);
214     }
215     unsigned totalStorageSize() const
216     {
217         return numberOfSlotsForLastOffset(m_offset, m_inlineCapacity);
218     }
219     unsigned totalStorageCapacity() const
220     {
221         ASSERT(structure()->classInfo() == info());
222         return outOfLineCapacity() + inlineCapacity();
223     }
224
225     bool isValidOffset(PropertyOffset offset) const
226     {
227         return JSC::isValidOffset(offset)
228             && offset <= m_offset
229             && (offset < m_inlineCapacity || offset >= firstOutOfLineOffset);
230     }
231     
232     bool couldHaveIndexingHeader() const
233     {
234         return hasIndexedProperties(indexingType())
235             || isTypedView(m_classInfo->typedArrayStorageType);
236     }
237     
238     bool hasIndexingHeader(const JSCell*) const;
239     
240     bool masqueradesAsUndefined(JSGlobalObject* lexicalGlobalObject);
241
242     PropertyOffset get(VM&, PropertyName);
243     PropertyOffset get(VM&, const WTF::String& name);
244     JS_EXPORT_PRIVATE PropertyOffset get(VM&, PropertyName, unsigned& attributes, JSCell*& specificValue);
245
246     PropertyOffset getConcurrently(VM&, StringImpl* uid);
247     PropertyOffset getConcurrently(VM&, StringImpl* uid, unsigned& attributes, JSCell*& specificValue);
248
249     bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
250     bool hasReadOnlyOrGetterSetterPropertiesExcludingProto() const { return m_hasReadOnlyOrGetterSetterPropertiesExcludingProto; }
251     void setHasGetterSetterProperties(bool is__proto__)
252     {
253         m_hasGetterSetterProperties = true;
254         if (!is__proto__)
255             m_hasReadOnlyOrGetterSetterPropertiesExcludingProto = true;
256     }
257     void setContainsReadOnlyProperties()
258     {
259         m_hasReadOnlyOrGetterSetterPropertiesExcludingProto = true;
260     }
261
262     bool hasNonEnumerableProperties() const { return m_hasNonEnumerableProperties; }
263         
264     bool isEmpty() const
265     {
266         ASSERT(checkOffsetConsistency());
267         return !JSC::isValidOffset(m_offset);
268     }
269
270     JS_EXPORT_PRIVATE void despecifyDictionaryFunction(VM&, PropertyName);
271     void disableSpecificFunctionTracking() { m_specificFunctionThrashCount = maxSpecificFunctionThrashCount; }
272
273     void setEnumerationCache(VM&, JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
274     JSPropertyNameIterator* enumerationCache(); // Defined in JSPropertyNameIterator.h.
275     void getPropertyNamesFromStructure(VM&, PropertyNameArray&, EnumerationMode);
276
277     JSString* objectToStringValue()
278     {
279         if (!typeInfo().structureHasRareData())
280             return 0;
281         return rareData()->objectToStringValue();
282     }
283
284     void setObjectToStringValue(VM& vm, const JSCell* owner, JSString* value)
285     {
286         if (!typeInfo().structureHasRareData())
287             allocateRareData(vm);
288         rareData()->setObjectToStringValue(vm, owner, value);
289     }
290
291     bool staticFunctionsReified()
292     {
293         return m_staticFunctionReified;
294     }
295
296     void setStaticFunctionsReified()
297     {
298         m_staticFunctionReified = true;
299     }
300
301     const ClassInfo* classInfo() const { return m_classInfo; }
302
303     static ptrdiff_t prototypeOffset()
304     {
305         return OBJECT_OFFSETOF(Structure, m_prototype);
306     }
307
308     static ptrdiff_t globalObjectOffset()
309     {
310         return OBJECT_OFFSETOF(Structure, m_globalObject);
311     }
312
313     static ptrdiff_t typeInfoFlagsOffset()
314     {
315         return OBJECT_OFFSETOF(Structure, m_typeInfo) + TypeInfo::flagsOffset();
316     }
317
318     static ptrdiff_t typeInfoTypeOffset()
319     {
320         return OBJECT_OFFSETOF(Structure, m_typeInfo) + TypeInfo::typeOffset();
321     }
322         
323     static ptrdiff_t classInfoOffset()
324     {
325         return OBJECT_OFFSETOF(Structure, m_classInfo);
326     }
327         
328     static ptrdiff_t indexingTypeOffset()
329     {
330         return OBJECT_OFFSETOF(Structure, m_indexingType);
331     }
332
333     static Structure* createStructure(VM&);
334         
335     bool transitionWatchpointSetHasBeenInvalidated() const
336     {
337         return m_transitionWatchpointSet.hasBeenInvalidated();
338     }
339         
340     bool transitionWatchpointSetIsStillValid() const
341     {
342         return m_transitionWatchpointSet.isStillValid();
343     }
344         
345     void addTransitionWatchpoint(Watchpoint* watchpoint) const
346     {
347         ASSERT(transitionWatchpointSetIsStillValid());
348         m_transitionWatchpointSet.add(watchpoint);
349     }
350         
351     void notifyTransitionFromThisStructure() const
352     {
353         m_transitionWatchpointSet.notifyWrite();
354     }
355     
356     InlineWatchpointSet& transitionWatchpointSet() const
357     {
358         return m_transitionWatchpointSet;
359     }
360     
361     void dump(PrintStream&) const;
362     void dumpInContext(PrintStream&, DumpContext*) const;
363     void dumpBrief(PrintStream&, const CString&) const;
364     
365     static void dumpContextHeader(PrintStream&);
366     
367     DECLARE_EXPORT_INFO;
368
369 private:
370     friend class LLIntOffsetsExtractor;
371
372     JS_EXPORT_PRIVATE Structure(VM&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType, unsigned inlineCapacity);
373     Structure(VM&);
374     Structure(VM&, const Structure*);
375
376     static Structure* create(VM&, const Structure*);
377     
378     static Structure* addPropertyTransitionToExistingStructureImpl(Structure*, StringImpl* uid, unsigned attributes, JSCell* specificValue, PropertyOffset&);
379
380     // This will return the structure that has a usable property table, that property table,
381     // and the list of structures that we visited before we got to it. If it returns a
382     // non-null structure, it will also lock the structure that it returns; it is your job
383     // to unlock it.
384     void findStructuresAndMapForMaterialization(Vector<Structure*, 8>& structures, Structure*&, PropertyTable*&);
385     
386     typedef enum { 
387         NoneDictionaryKind = 0,
388         CachedDictionaryKind = 1,
389         UncachedDictionaryKind = 2
390     } DictionaryKind;
391     static Structure* toDictionaryTransition(VM&, Structure*, DictionaryKind);
392
393     PropertyOffset putSpecificValue(VM&, PropertyName, unsigned attributes, JSCell* specificValue);
394     PropertyOffset remove(PropertyName);
395
396     void createPropertyMap(const GCSafeConcurrentJITLocker&, VM&, unsigned keyCount = 0);
397     void checkConsistency();
398
399     bool despecifyFunction(VM&, PropertyName);
400     void despecifyAllFunctions(VM&);
401
402     WriteBarrier<PropertyTable>& propertyTable();
403     PropertyTable* takePropertyTableOrCloneIfPinned(VM&, Structure* owner);
404     PropertyTable* copyPropertyTable(VM&, Structure* owner);
405     PropertyTable* copyPropertyTableForPinning(VM&, Structure* owner);
406     JS_EXPORT_PRIVATE void materializePropertyMap(VM&);
407     void materializePropertyMapIfNecessary(VM& vm)
408     {
409         ASSERT(!isCompilationThread());
410         ASSERT(structure()->classInfo() == info());
411         ASSERT(checkOffsetConsistency());
412         if (!propertyTable() && previousID())
413             materializePropertyMap(vm);
414     }
415     void materializePropertyMapIfNecessaryForPinning(VM& vm)
416     {
417         ASSERT(structure()->classInfo() == info());
418         checkOffsetConsistency();
419         if (!propertyTable())
420             materializePropertyMap(vm);
421     }
422
423     void setPreviousID(VM& vm, Structure* transition, Structure* structure)
424     {
425         if (typeInfo().structureHasRareData())
426             rareData()->setPreviousID(vm, transition, structure);
427         else
428             m_previousOrRareData.set(vm, transition, structure);
429     }
430
431     void clearPreviousID()
432     {
433         if (typeInfo().structureHasRareData())
434             rareData()->clearPreviousID();
435         else
436             m_previousOrRareData.clear();
437     }
438
439     int transitionCount() const
440     {
441         // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both.
442         return numberOfSlotsForLastOffset(m_offset, m_inlineCapacity);
443     }
444
445     bool isValid(JSGlobalObject*, StructureChain* cachedPrototypeChain) const;
446     bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
447         
448     void pin();
449
450     Structure* previous() const
451     {
452         ASSERT(!typeInfo().structureHasRareData());
453         return static_cast<Structure*>(m_previousOrRareData.get());
454     }
455
456     StructureRareData* rareData() const
457     {
458         ASSERT(typeInfo().structureHasRareData());
459         return static_cast<StructureRareData*>(m_previousOrRareData.get());
460     }
461         
462     bool checkOffsetConsistency() const;
463
464     void allocateRareData(VM&);
465     void cloneRareDataFrom(VM&, const Structure*);
466
467     static const int s_maxTransitionLength = 64;
468     static const int s_maxTransitionLengthForNonEvalPutById = 512;
469
470     static const unsigned maxSpecificFunctionThrashCount = 3;
471         
472     WriteBarrier<JSGlobalObject> m_globalObject;
473     WriteBarrier<Unknown> m_prototype;
474     mutable WriteBarrier<StructureChain> m_cachedPrototypeChain;
475
476     WriteBarrier<JSCell> m_previousOrRareData;
477
478     RefPtr<StringImpl> m_nameInPrevious;
479     WriteBarrier<JSCell> m_specificValueInPrevious;
480
481     const ClassInfo* m_classInfo;
482
483     StructureTransitionTable m_transitionTable;
484
485     // Should be accessed through propertyTable(). During GC, it may be set to 0 by another thread.
486     WriteBarrier<PropertyTable> m_propertyTableUnsafe;
487
488     mutable InlineWatchpointSet m_transitionWatchpointSet;
489
490     COMPILE_ASSERT(firstOutOfLineOffset < 256, firstOutOfLineOffset_fits);
491
492     // m_offset does not account for anonymous slots
493     PropertyOffset m_offset;
494
495     TypeInfo m_typeInfo;
496     IndexingType m_indexingType;
497     uint8_t m_inlineCapacity;
498     
499     ConcurrentJITLock m_lock;
500     
501     unsigned m_dictionaryKind : 2;
502     bool m_isPinnedPropertyTable : 1;
503     bool m_hasGetterSetterProperties : 1;
504     bool m_hasReadOnlyOrGetterSetterPropertiesExcludingProto : 1;
505     bool m_hasNonEnumerableProperties : 1;
506     unsigned m_attributesInPrevious : 14;
507     unsigned m_specificFunctionThrashCount : 2;
508     unsigned m_preventExtensions : 1;
509     unsigned m_didTransition : 1;
510     unsigned m_staticFunctionReified;
511 };
512
513 } // namespace JSC
514
515 #endif // Structure_h