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
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 gcSafeZeroMemory(result->propertyStorage() - propertyCapacity, 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 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
152inline 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
167inline 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
185inline 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
196inline 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 PreciseAllocation 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)->isPreciseAllocation();
213 if (canRealloc) {
214 void* newBase = vm.jsValueGigacageAuxiliarySpace.reallocatePreciseAllocationNonVirtual(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
227inline 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
244inline 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
255inline 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
274inline 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
287