1/*
2 * Copyright (C) 2012-2018 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 "ArrayStorage.h"
29#include "Butterfly.h"
30#include "JSObject.h"
31#include "Structure.h"
32#include "VM.h"
33
34namespace JSC {
35
36template<typename T>
37const 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
43template<typename T>
44typename 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
50ALWAYS_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
58ALWAYS_INLINE unsigned Butterfly::availableContiguousVectorLength(Structure* structure, unsigned vectorLength)
59{
60 return availableContiguousVectorLength(structure ? structure->outOfLineCapacity() : 0, vectorLength);
61}
62
63ALWAYS_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
72ALWAYS_INLINE unsigned Butterfly::optimalContiguousVectorLength(Structure* structure, unsigned vectorLength)
73{
74 return optimalContiguousVectorLength(structure ? structure->outOfLineCapacity() : 0, vectorLength);
75}
76
77inline 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
89inline 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
98inline 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 memset(result->propertyStorage() - propertyCapacity, 0, propertyCapacity * sizeof(EncodedJSValue));
108 return result;
109}
110
111inline 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
119inline 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
126inline void* Butterfly::base(Structure* structure)
127{
128 return base(indexingHeader()->preCapacity(structure), structure->outOfLineCapacity());
129}
130
131inline 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 memcpy(
143 result->propertyStorage() - oldPropertyCapacity,
144 oldButterfly->propertyStorage() - oldPropertyCapacity,
145 totalSize(0, oldPropertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes));
146 memset(
147 result->propertyStorage() - newPropertyCapacity,
148 0,
149 (newPropertyCapacity - oldPropertyCapacity) * sizeof(EncodedJSValue));
150 return result;
151}
152
153inline Butterfly* Butterfly::createOrGrowArrayRight(
154 Butterfly* oldButterfly, VM& vm, JSObject* intendedOwner, Structure* oldStructure,
155 size_t propertyCapacity, bool hadIndexingHeader, size_t oldIndexingPayloadSizeInBytes,
156 size_t newIndexingPayloadSizeInBytes)
157{
158 if (!oldButterfly) {
159 return create(
160 vm, intendedOwner, 0, propertyCapacity, true, IndexingHeader(),
161 newIndexingPayloadSizeInBytes);
162 }
163 return oldButterfly->growArrayRight(
164 vm, intendedOwner, oldStructure, propertyCapacity, hadIndexingHeader,
165 oldIndexingPayloadSizeInBytes, newIndexingPayloadSizeInBytes);
166}
167
168inline Butterfly* Butterfly::growArrayRight(
169 VM& vm, JSObject* intendedOwner, Structure* oldStructure, size_t propertyCapacity,
170 bool hadIndexingHeader, size_t oldIndexingPayloadSizeInBytes,
171 size_t newIndexingPayloadSizeInBytes)
172{
173 ASSERT_UNUSED(oldStructure, !indexingHeader()->preCapacity(oldStructure));
174 ASSERT_UNUSED(intendedOwner, hadIndexingHeader == oldStructure->hasIndexingHeader(intendedOwner));
175 void* theBase = base(0, propertyCapacity);
176 size_t oldSize = totalSize(0, propertyCapacity, hadIndexingHeader, oldIndexingPayloadSizeInBytes);
177 size_t newSize = totalSize(0, propertyCapacity, true, newIndexingPayloadSizeInBytes);
178 void* newBase = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(vm, newSize, nullptr, AllocationFailureMode::ReturnNull);
179 if (!newBase)
180 return nullptr;
181 // FIXME: This probably shouldn't be a memcpy.
182 memcpy(newBase, theBase, oldSize);
183 return fromBase(newBase, 0, propertyCapacity);
184}
185
186inline Butterfly* Butterfly::growArrayRight(
187 VM& vm, JSObject* intendedOwner, Structure* oldStructure,
188 size_t newIndexingPayloadSizeInBytes)
189{
190 return growArrayRight(
191 vm, intendedOwner, oldStructure, oldStructure->outOfLineCapacity(),
192 oldStructure->hasIndexingHeader(intendedOwner),
193 indexingHeader()->indexingPayloadSizeInBytes(oldStructure),
194 newIndexingPayloadSizeInBytes);
195}
196
197inline Butterfly* Butterfly::reallocArrayRightIfPossible(
198 VM& vm, GCDeferralContext& deferralContext, JSObject* intendedOwner, Structure* oldStructure, size_t propertyCapacity,
199 bool hadIndexingHeader, size_t oldIndexingPayloadSizeInBytes,
200 size_t newIndexingPayloadSizeInBytes)
201{
202 ASSERT_UNUSED(oldStructure, !indexingHeader()->preCapacity(oldStructure));
203 ASSERT_UNUSED(intendedOwner, hadIndexingHeader == oldStructure->hasIndexingHeader(intendedOwner));
204
205 void* theBase = base(0, propertyCapacity);
206 size_t oldSize = totalSize(0, propertyCapacity, hadIndexingHeader, oldIndexingPayloadSizeInBytes);
207 size_t newSize = totalSize(0, propertyCapacity, true, newIndexingPayloadSizeInBytes);
208 ASSERT(newSize >= oldSize);
209
210 // 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.
211 // This is because during deallocation concurrent collector can access butterfly and DFG concurrent compilers accesses properties.
212 // 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!
213 bool canRealloc = !propertyCapacity && !vm.heap.mutatorShouldBeFenced() && bitwise_cast<HeapCell*>(theBase)->isLargeAllocation();
214 if (canRealloc) {
215 void* newBase = vm.jsValueGigacageAuxiliarySpace.reallocateLargeAllocationNonVirtual(vm, bitwise_cast<HeapCell*>(theBase), newSize, &deferralContext, AllocationFailureMode::ReturnNull);
216 if (!newBase)
217 return nullptr;
218 return fromBase(newBase, 0, propertyCapacity);
219 }
220
221 void* newBase = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(vm, newSize, &deferralContext, AllocationFailureMode::ReturnNull);
222 if (!newBase)
223 return nullptr;
224 memcpy(newBase, theBase, oldSize);
225 return fromBase(newBase, 0, propertyCapacity);
226}
227
228inline Butterfly* Butterfly::resizeArray(
229 VM& vm, JSObject* intendedOwner, size_t propertyCapacity, bool oldHasIndexingHeader,
230 size_t oldIndexingPayloadSizeInBytes, size_t newPreCapacity, bool newHasIndexingHeader,
231 size_t newIndexingPayloadSizeInBytes)
232{
233 Butterfly* result = createUninitialized(vm, intendedOwner, newPreCapacity, propertyCapacity, newHasIndexingHeader, newIndexingPayloadSizeInBytes);
234 // FIXME: This could be made much more efficient if we used the property size,
235 // not the capacity.
236 void* to = result->propertyStorage() - propertyCapacity;
237 void* from = propertyStorage() - propertyCapacity;
238 size_t size = std::min(
239 totalSize(0, propertyCapacity, oldHasIndexingHeader, oldIndexingPayloadSizeInBytes),
240 totalSize(0, propertyCapacity, newHasIndexingHeader, newIndexingPayloadSizeInBytes));
241 memcpy(to, from, size);
242 return result;
243}
244
245inline Butterfly* Butterfly::resizeArray(
246 VM& vm, JSObject* intendedOwner, Structure* structure, size_t newPreCapacity,
247 size_t newIndexingPayloadSizeInBytes)
248{
249 bool hasIndexingHeader = structure->hasIndexingHeader(intendedOwner);
250 return resizeArray(
251 vm, intendedOwner, structure->outOfLineCapacity(), hasIndexingHeader,
252 indexingHeader()->indexingPayloadSizeInBytes(structure), newPreCapacity,
253 hasIndexingHeader, newIndexingPayloadSizeInBytes);
254}
255
256inline Butterfly* Butterfly::unshift(Structure* structure, size_t numberOfSlots)
257{
258 ASSERT(hasAnyArrayStorage(structure->indexingType()));
259 ASSERT(numberOfSlots <= indexingHeader()->preCapacity(structure));
260 unsigned propertyCapacity = structure->outOfLineCapacity();
261 // FIXME: It would probably be wise to rewrite this as a loop since (1) we know in which
262 // direction we're moving memory so we don't need the extra check of memmove and (2) we're
263 // moving a small amount of memory in the common case so the throughput of memmove won't
264 // amortize the overhead of calling it. And no, we cannot rely on the C++ compiler to
265 // inline memmove (particularly since the size argument is likely to be variable), nor can
266 // we rely on the compiler to recognize the ordering of the pointer arguments (since
267 // propertyCapacity is variable and could cause wrap-around as far as the compiler knows).
268 memmove(
269 propertyStorage() - numberOfSlots - propertyCapacity,
270 propertyStorage() - propertyCapacity,
271 sizeof(EncodedJSValue) * propertyCapacity + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
272 return IndexingHeader::fromEndOf(propertyStorage() - numberOfSlots)->butterfly();
273}
274
275inline Butterfly* Butterfly::shift(Structure* structure, size_t numberOfSlots)
276{
277 ASSERT(hasAnyArrayStorage(structure->indexingType()));
278 unsigned propertyCapacity = structure->outOfLineCapacity();
279 // FIXME: See comment in unshift(), above.
280 memmove(
281 propertyStorage() - propertyCapacity + numberOfSlots,
282 propertyStorage() - propertyCapacity,
283 sizeof(EncodedJSValue) * propertyCapacity + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
284 return IndexingHeader::fromEndOf(propertyStorage() + numberOfSlots)->butterfly();
285}
286
287} // namespace JSC
288