48606056d2f5022ca4681ae6640fe5482fcd36c7
[WebKit-https.git] / Source / JavaScriptCore / runtime / ButterflyInlines.h
1 /*
2  * Copyright (C) 2012-2019 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 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 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 #pragma once
27
28 #include "ArrayStorageInlines.h"
29 #include "Butterfly.h"
30 #include "JSObject.h"
31 #include "Structure.h"
32 #include "VM.h"
33
34 namespace JSC {
35
36 template<typename T>
37 const typename ContiguousData<T>::Data ContiguousData<T>::at(const JSCell* owner, size_t index) const
38 {
39     ASSERT(index < m_length);
40     return Data(m_data[index], owner->indexingMode());
41 }
42
43 template<typename T>
44 typename ContiguousData<T>::Data ContiguousData<T>::at(const JSCell* owner, size_t index)
45 {
46     ASSERT(index < m_length);
47     return Data(m_data[index], owner->indexingMode());
48 }
49
50 ALWAYS_INLINE unsigned Butterfly::availableContiguousVectorLength(size_t propertyCapacity, unsigned vectorLength)
51 {
52     size_t cellSize = totalSize(0, propertyCapacity, true, sizeof(EncodedJSValue) * vectorLength);
53     cellSize = MarkedSpace::optimalSizeFor(cellSize);
54     vectorLength = (cellSize - totalSize(0, propertyCapacity, true, 0)) / sizeof(EncodedJSValue);
55     return vectorLength;
56 }
57
58 ALWAYS_INLINE unsigned Butterfly::availableContiguousVectorLength(Structure* structure, unsigned vectorLength)
59 {
60     return availableContiguousVectorLength(structure ? structure->outOfLineCapacity() : 0, vectorLength);
61 }
62
63 ALWAYS_INLINE unsigned Butterfly::optimalContiguousVectorLength(size_t propertyCapacity, unsigned vectorLength)
64 {
65     if (!vectorLength)
66         vectorLength = BASE_CONTIGUOUS_VECTOR_LEN_EMPTY;
67     else
68         vectorLength = std::max(BASE_CONTIGUOUS_VECTOR_LEN, vectorLength);
69     return availableContiguousVectorLength(propertyCapacity, vectorLength);
70 }
71
72 ALWAYS_INLINE unsigned Butterfly::optimalContiguousVectorLength(Structure* structure, unsigned vectorLength)
73 {
74     return optimalContiguousVectorLength(structure ? structure->outOfLineCapacity() : 0, vectorLength);
75 }
76
77 inline Butterfly* Butterfly::tryCreateUninitialized(VM& vm, JSObject*, size_t preCapacity, size_t propertyCapacity, bool hasIndexingHeader, size_t indexingPayloadSizeInBytes, GCDeferralContext* deferralContext)
78 {
79     size_t size = totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
80     void* base = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(vm, size, deferralContext, AllocationFailureMode::ReturnNull);
81     if (UNLIKELY(!base))
82         return nullptr;
83
84     Butterfly* result = fromBase(base, preCapacity, propertyCapacity);
85
86     return result;
87 }
88
89 inline Butterfly* Butterfly::createUninitialized(VM& vm, JSObject*, size_t preCapacity, size_t propertyCapacity, bool hasIndexingHeader, size_t indexingPayloadSizeInBytes)
90 {
91     size_t size = totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
92     void* base = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(vm, size, nullptr, AllocationFailureMode::Assert);
93     Butterfly* result = fromBase(base, preCapacity, propertyCapacity);
94
95     return result;
96 }
97
98 inline Butterfly* Butterfly::tryCreate(VM& vm, JSObject*, size_t preCapacity, size_t propertyCapacity, bool hasIndexingHeader, const IndexingHeader& indexingHeader, size_t indexingPayloadSizeInBytes)
99 {
100     size_t size = totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
101     void* base = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(vm, size, nullptr, AllocationFailureMode::ReturnNull);
102     if (!base)
103         return nullptr;
104     Butterfly* result = fromBase(base, preCapacity, propertyCapacity);
105     if (hasIndexingHeader)
106         *result->indexingHeader() = indexingHeader;
107     gcSafeZeroMemory(result->propertyStorage() - propertyCapacity, propertyCapacity * sizeof(EncodedJSValue));
108     return result;
109 }
110
111 inline Butterfly* Butterfly::create(VM& vm, JSObject* intendedOwner, size_t preCapacity, size_t propertyCapacity, bool hasIndexingHeader, const IndexingHeader& indexingHeader, size_t indexingPayloadSizeInBytes)
112 {
113     Butterfly* result = tryCreate(vm, intendedOwner, preCapacity, propertyCapacity, hasIndexingHeader, indexingHeader, indexingPayloadSizeInBytes);
114
115     RELEASE_ASSERT(result);
116     return result;
117 }
118
119 inline Butterfly* Butterfly::create(VM& vm, JSObject* intendedOwner, Structure* structure)
120 {
121     return create(
122         vm, intendedOwner, 0, structure->outOfLineCapacity(),
123         structure->hasIndexingHeader(intendedOwner), IndexingHeader(), 0);
124 }
125
126 inline void* Butterfly::base(Structure* structure)
127 {
128     return base(indexingHeader()->preCapacity(structure), structure->outOfLineCapacity());
129 }
130
131 inline Butterfly* Butterfly::createOrGrowPropertyStorage(
132     Butterfly* oldButterfly, VM& vm, JSObject* intendedOwner, Structure* structure, size_t oldPropertyCapacity, size_t newPropertyCapacity)
133 {
134     RELEASE_ASSERT(newPropertyCapacity > oldPropertyCapacity);
135     if (!oldButterfly)
136         return create(vm, intendedOwner, 0, newPropertyCapacity, false, IndexingHeader(), 0);
137
138     size_t preCapacity = oldButterfly->indexingHeader()->preCapacity(structure);
139     size_t indexingPayloadSizeInBytes = oldButterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
140     bool hasIndexingHeader = structure->hasIndexingHeader(intendedOwner);
141     Butterfly* result = createUninitialized(vm, intendedOwner, preCapacity, newPropertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
142     gcSafeMemcpy(
143         result->propertyStorage() - oldPropertyCapacity,
144         oldButterfly->propertyStorage() - oldPropertyCapacity,
145         totalSize(0, oldPropertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes));
146     gcSafeZeroMemory(
147         result->propertyStorage() - newPropertyCapacity,
148         (newPropertyCapacity - oldPropertyCapacity) * sizeof(EncodedJSValue));
149     return result;
150 }
151
152 inline Butterfly* Butterfly::createOrGrowArrayRight(
153     Butterfly* oldButterfly, VM& vm, JSObject* intendedOwner, Structure* oldStructure,
154     size_t propertyCapacity, bool hadIndexingHeader, size_t oldIndexingPayloadSizeInBytes,
155     size_t newIndexingPayloadSizeInBytes)
156 {
157     if (!oldButterfly) {
158         return create(
159             vm, intendedOwner, 0, propertyCapacity, true, IndexingHeader(),
160             newIndexingPayloadSizeInBytes);
161     }
162     return oldButterfly->growArrayRight(
163         vm, intendedOwner, oldStructure, propertyCapacity, hadIndexingHeader,
164         oldIndexingPayloadSizeInBytes, newIndexingPayloadSizeInBytes);
165 }
166
167 inline Butterfly* Butterfly::growArrayRight(
168     VM& vm, JSObject* intendedOwner, Structure* oldStructure, size_t propertyCapacity,
169     bool hadIndexingHeader, size_t oldIndexingPayloadSizeInBytes,
170     size_t newIndexingPayloadSizeInBytes)
171 {
172     ASSERT_UNUSED(oldStructure, !indexingHeader()->preCapacity(oldStructure));
173     ASSERT_UNUSED(intendedOwner, hadIndexingHeader == oldStructure->hasIndexingHeader(intendedOwner));
174     void* theBase = base(0, propertyCapacity);
175     size_t oldSize = totalSize(0, propertyCapacity, hadIndexingHeader, oldIndexingPayloadSizeInBytes);
176     size_t newSize = totalSize(0, propertyCapacity, true, newIndexingPayloadSizeInBytes);
177     void* newBase = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(vm, newSize, nullptr, AllocationFailureMode::ReturnNull);
178     if (!newBase)
179         return nullptr;
180     // FIXME: This probably shouldn't be a memcpy.
181     gcSafeMemcpy(static_cast<JSValue*>(newBase), static_cast<JSValue*>(theBase), oldSize);
182     return fromBase(newBase, 0, propertyCapacity);
183 }
184
185 inline Butterfly* Butterfly::growArrayRight(
186     VM& vm, JSObject* intendedOwner, Structure* oldStructure,
187     size_t newIndexingPayloadSizeInBytes)
188 {
189     return growArrayRight(
190         vm, intendedOwner, oldStructure, oldStructure->outOfLineCapacity(),
191         oldStructure->hasIndexingHeader(intendedOwner), 
192         indexingHeader()->indexingPayloadSizeInBytes(oldStructure),
193         newIndexingPayloadSizeInBytes);
194 }
195
196 inline Butterfly* Butterfly::reallocArrayRightIfPossible(
197     VM& vm, GCDeferralContext& deferralContext, JSObject* intendedOwner, Structure* oldStructure, size_t propertyCapacity,
198     bool hadIndexingHeader, size_t oldIndexingPayloadSizeInBytes,
199     size_t newIndexingPayloadSizeInBytes)
200 {
201     ASSERT_UNUSED(oldStructure, !indexingHeader()->preCapacity(oldStructure));
202     ASSERT_UNUSED(intendedOwner, hadIndexingHeader == oldStructure->hasIndexingHeader(intendedOwner));
203
204     void* theBase = base(0, propertyCapacity);
205     size_t oldSize = totalSize(0, propertyCapacity, hadIndexingHeader, oldIndexingPayloadSizeInBytes);
206     size_t newSize = totalSize(0, propertyCapacity, true, newIndexingPayloadSizeInBytes);
207     ASSERT(newSize >= oldSize);
208
209     // We can eagerly destroy butterfly backed by LargeAllocation if (1) concurrent collector is not active and (2) the butterfly does not contain any property storage.
210     // This is because during deallocation concurrent collector can access butterfly and DFG concurrent compilers accesses properties.
211     // Objects with no properties are common in arrays, and we are focusing on very large array crafted by repeating Array#push, so... that's fine!
212     bool canRealloc = !propertyCapacity && !vm.heap.mutatorShouldBeFenced() && bitwise_cast<HeapCell*>(theBase)->isLargeAllocation();
213     if (canRealloc) {
214         void* newBase = vm.jsValueGigacageAuxiliarySpace.reallocateLargeAllocationNonVirtual(vm, bitwise_cast<HeapCell*>(theBase), newSize, &deferralContext, AllocationFailureMode::ReturnNull);
215         if (!newBase)
216             return nullptr;
217         return fromBase(newBase, 0, propertyCapacity);
218     }
219
220     void* newBase = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(vm, newSize, &deferralContext, AllocationFailureMode::ReturnNull);
221     if (!newBase)
222         return nullptr;
223     gcSafeMemcpy(static_cast<JSValue*>(newBase), static_cast<JSValue*>(theBase), oldSize);
224     return fromBase(newBase, 0, propertyCapacity);
225 }
226
227 inline Butterfly* Butterfly::resizeArray(
228     VM& vm, JSObject* intendedOwner, size_t propertyCapacity, bool oldHasIndexingHeader,
229     size_t oldIndexingPayloadSizeInBytes, size_t newPreCapacity, bool newHasIndexingHeader,
230     size_t newIndexingPayloadSizeInBytes)
231 {
232     Butterfly* result = createUninitialized(vm, intendedOwner, newPreCapacity, propertyCapacity, newHasIndexingHeader, newIndexingPayloadSizeInBytes);
233     // FIXME: This could be made much more efficient if we used the property size,
234     // not the capacity.
235     void* to = result->propertyStorage() - propertyCapacity;
236     void* from = propertyStorage() - propertyCapacity;
237     size_t size = std::min(
238         totalSize(0, propertyCapacity, oldHasIndexingHeader, oldIndexingPayloadSizeInBytes),
239         totalSize(0, propertyCapacity, newHasIndexingHeader, newIndexingPayloadSizeInBytes));
240     gcSafeMemcpy(static_cast<JSValue*>(to), static_cast<JSValue*>(from), size);
241     return result;
242 }
243
244 inline Butterfly* Butterfly::resizeArray(
245     VM& vm, JSObject* intendedOwner, Structure* structure, size_t newPreCapacity,
246     size_t newIndexingPayloadSizeInBytes)
247 {
248     bool hasIndexingHeader = structure->hasIndexingHeader(intendedOwner);
249     return resizeArray(
250         vm, intendedOwner, structure->outOfLineCapacity(), hasIndexingHeader,
251         indexingHeader()->indexingPayloadSizeInBytes(structure), newPreCapacity,
252         hasIndexingHeader, newIndexingPayloadSizeInBytes);
253 }
254
255 inline Butterfly* Butterfly::unshift(Structure* structure, size_t numberOfSlots)
256 {
257     ASSERT(hasAnyArrayStorage(structure->indexingType()));
258     ASSERT(numberOfSlots <= indexingHeader()->preCapacity(structure));
259     unsigned propertyCapacity = structure->outOfLineCapacity();
260     // FIXME: It would probably be wise to rewrite this as a loop since (1) we know in which
261     // direction we're moving memory so we don't need the extra check of memmove and (2) we're
262     // moving a small amount of memory in the common case so the throughput of memmove won't
263     // amortize the overhead of calling it. And no, we cannot rely on the C++ compiler to
264     // inline memmove (particularly since the size argument is likely to be variable), nor can
265     // we rely on the compiler to recognize the ordering of the pointer arguments (since
266     // propertyCapacity is variable and could cause wrap-around as far as the compiler knows).
267     gcSafeMemmove(
268         propertyStorage() - numberOfSlots - propertyCapacity,
269         propertyStorage() - propertyCapacity,
270         sizeof(EncodedJSValue) * propertyCapacity + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
271     return IndexingHeader::fromEndOf(propertyStorage() - numberOfSlots)->butterfly();
272 }
273
274 inline Butterfly* Butterfly::shift(Structure* structure, size_t numberOfSlots)
275 {
276     ASSERT(hasAnyArrayStorage(structure->indexingType()));
277     unsigned propertyCapacity = structure->outOfLineCapacity();
278     // FIXME: See comment in unshift(), above.
279     gcSafeMemmove(
280         propertyStorage() - propertyCapacity + numberOfSlots,
281         propertyStorage() - propertyCapacity,
282         sizeof(EncodedJSValue) * propertyCapacity + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
283     return IndexingHeader::fromEndOf(propertyStorage() + numberOfSlots)->butterfly();
284 }
285
286 } // namespace JSC