1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifndef nsTArray_h__
8 # error "Don't include this file directly"
9 #endif
10
11 template<class Alloc, class Copy>
nsTArray_base()12 nsTArray_base<Alloc, Copy>::nsTArray_base()
13 : mHdr(EmptyHdr())
14 {
15 MOZ_COUNT_CTOR(nsTArray_base);
16 }
17
18 template<class Alloc, class Copy>
~nsTArray_base()19 nsTArray_base<Alloc, Copy>::~nsTArray_base()
20 {
21 if (mHdr != EmptyHdr() && !UsesAutoArrayBuffer()) {
22 Alloc::Free(mHdr);
23 }
24 MOZ_COUNT_DTOR(nsTArray_base);
25 }
26
27 template<class Alloc, class Copy>
28 const nsTArrayHeader*
GetAutoArrayBufferUnsafe(size_t aElemAlign)29 nsTArray_base<Alloc, Copy>::GetAutoArrayBufferUnsafe(size_t aElemAlign) const
30 {
31 // Assuming |this| points to an nsAutoArray, we want to get a pointer to
32 // mAutoBuf. So just cast |this| to nsAutoArray* and read &mAutoBuf!
33
34 const void* autoBuf =
35 &reinterpret_cast<const AutoTArray<nsTArray<uint32_t>, 1>*>(this)->mAutoBuf;
36
37 // If we're on a 32-bit system and aElemAlign is 8, we need to adjust our
38 // pointer to take into account the extra alignment in the auto array.
39
40 static_assert(sizeof(void*) != 4 ||
41 (MOZ_ALIGNOF(mozilla::AlignedElem<8>) == 8 &&
42 sizeof(AutoTArray<mozilla::AlignedElem<8>, 1>) ==
43 sizeof(void*) + sizeof(nsTArrayHeader) +
44 4 + sizeof(mozilla::AlignedElem<8>)),
45 "auto array padding wasn't what we expected");
46
47 // We don't support alignments greater than 8 bytes.
48 MOZ_ASSERT(aElemAlign <= 4 || aElemAlign == 8,
49 "unsupported alignment.");
50 if (sizeof(void*) == 4 && aElemAlign == 8) {
51 autoBuf = reinterpret_cast<const char*>(autoBuf) + 4;
52 }
53
54 return reinterpret_cast<const Header*>(autoBuf);
55 }
56
57 template<class Alloc, class Copy>
58 bool
UsesAutoArrayBuffer()59 nsTArray_base<Alloc, Copy>::UsesAutoArrayBuffer() const
60 {
61 if (!mHdr->mIsAutoArray) {
62 return false;
63 }
64
65 // This is nuts. If we were sane, we'd pass aElemAlign as a parameter to
66 // this function. Unfortunately this function is called in nsTArray_base's
67 // destructor, at which point we don't know elem_type's alignment.
68 //
69 // We'll fall on our face and return true when we should say false if
70 //
71 // * we're not using our auto buffer,
72 // * aElemAlign == 4, and
73 // * mHdr == GetAutoArrayBuffer(8).
74 //
75 // This could happen if |*this| lives on the heap and malloc allocated our
76 // buffer on the heap adjacent to |*this|.
77 //
78 // However, we can show that this can't happen. If |this| is an auto array
79 // (as we ensured at the beginning of the method), GetAutoArrayBuffer(8)
80 // always points to memory owned by |*this|, because (as we assert below)
81 //
82 // * GetAutoArrayBuffer(8) is at most 4 bytes past GetAutoArrayBuffer(4), and
83 // * sizeof(nsTArrayHeader) > 4.
84 //
85 // Since AutoTArray always contains an nsTArrayHeader,
86 // GetAutoArrayBuffer(8) will always point inside the auto array object,
87 // even if it doesn't point at the beginning of the header.
88 //
89 // Note that this means that we can't store elements with alignment 16 in an
90 // nsTArray, because GetAutoArrayBuffer(16) could lie outside the memory
91 // owned by this AutoTArray. We statically assert that elem_type's
92 // alignment is 8 bytes or less in AutoTArray.
93
94 static_assert(sizeof(nsTArrayHeader) > 4,
95 "see comment above");
96
97 #ifdef DEBUG
98 ptrdiff_t diff = reinterpret_cast<const char*>(GetAutoArrayBuffer(8)) -
99 reinterpret_cast<const char*>(GetAutoArrayBuffer(4));
100 MOZ_ASSERT(diff >= 0 && diff <= 4,
101 "GetAutoArrayBuffer doesn't do what we expect.");
102 #endif
103
104 return mHdr == GetAutoArrayBuffer(4) || mHdr == GetAutoArrayBuffer(8);
105 }
106
107 // defined in nsTArray.cpp
108 bool IsTwiceTheRequiredBytesRepresentableAsUint32(size_t aCapacity,
109 size_t aElemSize);
110
111 template<class Alloc, class Copy>
112 template<typename ActualAlloc>
113 typename ActualAlloc::ResultTypeProxy
EnsureCapacity(size_type aCapacity,size_type aElemSize)114 nsTArray_base<Alloc, Copy>::EnsureCapacity(size_type aCapacity,
115 size_type aElemSize)
116 {
117 // This should be the most common case so test this first
118 if (aCapacity <= mHdr->mCapacity) {
119 return ActualAlloc::SuccessResult();
120 }
121
122 // If the requested memory allocation exceeds size_type(-1)/2, then
123 // our doubling algorithm may not be able to allocate it.
124 // Additionally, if it exceeds uint32_t(-1) then we couldn't fit in the
125 // Header::mCapacity member. Just bail out in cases like that. We don't want
126 // to be allocating 2 GB+ arrays anyway.
127 if (!IsTwiceTheRequiredBytesRepresentableAsUint32(aCapacity, aElemSize)) {
128 ActualAlloc::SizeTooBig((size_t)aCapacity * aElemSize);
129 return ActualAlloc::FailureResult();
130 }
131
132 size_t reqSize = sizeof(Header) + aCapacity * aElemSize;
133
134 if (mHdr == EmptyHdr()) {
135 // Malloc() new data
136 Header* header = static_cast<Header*>(ActualAlloc::Malloc(reqSize));
137 if (!header) {
138 return ActualAlloc::FailureResult();
139 }
140 header->mLength = 0;
141 header->mCapacity = aCapacity;
142 header->mIsAutoArray = 0;
143 mHdr = header;
144
145 return ActualAlloc::SuccessResult();
146 }
147
148 // We increase our capacity so that the allocated buffer grows exponentially,
149 // which gives us amortized O(1) appending. Below the threshold, we use
150 // powers-of-two. Above the threshold, we grow by at least 1.125, rounding up
151 // to the nearest MiB.
152 const size_t slowGrowthThreshold = 8 * 1024 * 1024;
153
154 size_t bytesToAlloc;
155 if (reqSize >= slowGrowthThreshold) {
156 size_t currSize = sizeof(Header) + Capacity() * aElemSize;
157 size_t minNewSize = currSize + (currSize >> 3); // multiply by 1.125
158 bytesToAlloc = reqSize > minNewSize ? reqSize : minNewSize;
159
160 // Round up to the next multiple of MiB.
161 const size_t MiB = 1 << 20;
162 bytesToAlloc = MiB * ((bytesToAlloc + MiB - 1) / MiB);
163 } else {
164 // Round up to the next power of two.
165 bytesToAlloc = mozilla::RoundUpPow2(reqSize);
166 }
167
168 Header* header;
169 if (UsesAutoArrayBuffer() || !Copy::allowRealloc) {
170 // Malloc() and copy
171 header = static_cast<Header*>(ActualAlloc::Malloc(bytesToAlloc));
172 if (!header) {
173 return ActualAlloc::FailureResult();
174 }
175
176 Copy::MoveNonOverlappingRegionWithHeader(header, mHdr, Length(), aElemSize);
177
178 if (!UsesAutoArrayBuffer()) {
179 ActualAlloc::Free(mHdr);
180 }
181 } else {
182 // Realloc() existing data
183 header = static_cast<Header*>(ActualAlloc::Realloc(mHdr, bytesToAlloc));
184 if (!header) {
185 return ActualAlloc::FailureResult();
186 }
187 }
188
189 // How many elements can we fit in bytesToAlloc?
190 size_t newCapacity = (bytesToAlloc - sizeof(Header)) / aElemSize;
191 MOZ_ASSERT(newCapacity >= aCapacity, "Didn't enlarge the array enough!");
192 header->mCapacity = newCapacity;
193
194 mHdr = header;
195
196 return ActualAlloc::SuccessResult();
197 }
198
199 // We don't need use Alloc template parameter specified here because failure to
200 // shrink the capacity will leave the array unchanged.
201 template<class Alloc, class Copy>
202 void
ShrinkCapacity(size_type aElemSize,size_t aElemAlign)203 nsTArray_base<Alloc, Copy>::ShrinkCapacity(size_type aElemSize,
204 size_t aElemAlign)
205 {
206 if (mHdr == EmptyHdr() || UsesAutoArrayBuffer()) {
207 return;
208 }
209
210 if (mHdr->mLength >= mHdr->mCapacity) { // should never be greater than...
211 return;
212 }
213
214 size_type length = Length();
215
216 if (IsAutoArray() && GetAutoArrayBuffer(aElemAlign)->mCapacity >= length) {
217 Header* header = GetAutoArrayBuffer(aElemAlign);
218
219 // Move the data, but don't copy the header to avoid overwriting mCapacity.
220 header->mLength = length;
221 Copy::MoveNonOverlappingRegion(header + 1, mHdr + 1, length, aElemSize);
222
223 nsTArrayFallibleAllocator::Free(mHdr);
224 mHdr = header;
225 return;
226 }
227
228 if (length == 0) {
229 MOZ_ASSERT(!IsAutoArray(), "autoarray should have fit 0 elements");
230 nsTArrayFallibleAllocator::Free(mHdr);
231 mHdr = EmptyHdr();
232 return;
233 }
234
235 size_type size = sizeof(Header) + length * aElemSize;
236 void* ptr = nsTArrayFallibleAllocator::Realloc(mHdr, size);
237 if (!ptr) {
238 return;
239 }
240 mHdr = static_cast<Header*>(ptr);
241 mHdr->mCapacity = length;
242 }
243
244 template<class Alloc, class Copy>
245 template<typename ActualAlloc>
246 void
ShiftData(index_type aStart,size_type aOldLen,size_type aNewLen,size_type aElemSize,size_t aElemAlign)247 nsTArray_base<Alloc, Copy>::ShiftData(index_type aStart,
248 size_type aOldLen, size_type aNewLen,
249 size_type aElemSize, size_t aElemAlign)
250 {
251 if (aOldLen == aNewLen) {
252 return;
253 }
254
255 // Determine how many elements need to be shifted
256 size_type num = mHdr->mLength - (aStart + aOldLen);
257
258 // Compute the resulting length of the array
259 mHdr->mLength += aNewLen - aOldLen;
260 if (mHdr->mLength == 0) {
261 ShrinkCapacity(aElemSize, aElemAlign);
262 } else {
263 // Maybe nothing needs to be shifted
264 if (num == 0) {
265 return;
266 }
267 // Perform shift (change units to bytes first)
268 aStart *= aElemSize;
269 aNewLen *= aElemSize;
270 aOldLen *= aElemSize;
271 char* baseAddr = reinterpret_cast<char*>(mHdr + 1) + aStart;
272 Copy::MoveOverlappingRegion(baseAddr + aNewLen, baseAddr + aOldLen, num, aElemSize);
273 }
274 }
275
276 template<class Alloc, class Copy>
277 template<typename ActualAlloc>
278 bool
InsertSlotsAt(index_type aIndex,size_type aCount,size_type aElemSize,size_t aElemAlign)279 nsTArray_base<Alloc, Copy>::InsertSlotsAt(index_type aIndex, size_type aCount,
280 size_type aElemSize,
281 size_t aElemAlign)
282 {
283 MOZ_ASSERT(aIndex <= Length(), "Bogus insertion index");
284 size_type newLen = Length() + aCount;
285
286 EnsureCapacity<ActualAlloc>(newLen, aElemSize);
287
288 // Check for out of memory conditions
289 if (Capacity() < newLen) {
290 return false;
291 }
292
293 // Move the existing elements as needed. Note that this will
294 // change our mLength, so no need to call IncrementLength.
295 ShiftData<ActualAlloc>(aIndex, 0, aCount, aElemSize, aElemAlign);
296
297 return true;
298 }
299
300 // nsTArray_base::IsAutoArrayRestorer is an RAII class which takes
301 // |nsTArray_base &array| in its constructor. When it's destructed, it ensures
302 // that
303 //
304 // * array.mIsAutoArray has the same value as it did when we started, and
305 // * if array has an auto buffer and mHdr would otherwise point to sEmptyHdr,
306 // array.mHdr points to array's auto buffer.
307
308 template<class Alloc, class Copy>
IsAutoArrayRestorer(nsTArray_base<Alloc,Copy> & aArray,size_t aElemAlign)309 nsTArray_base<Alloc, Copy>::IsAutoArrayRestorer::IsAutoArrayRestorer(
310 nsTArray_base<Alloc, Copy>& aArray,
311 size_t aElemAlign)
312 : mArray(aArray)
313 , mElemAlign(aElemAlign)
314 , mIsAuto(aArray.IsAutoArray())
315 {
316 }
317
318 template<class Alloc, class Copy>
~IsAutoArrayRestorer()319 nsTArray_base<Alloc, Copy>::IsAutoArrayRestorer::~IsAutoArrayRestorer()
320 {
321 // Careful: We don't want to set mIsAutoArray = 1 on sEmptyHdr.
322 if (mIsAuto && mArray.mHdr == mArray.EmptyHdr()) {
323 // Call GetAutoArrayBufferUnsafe() because GetAutoArrayBuffer() asserts
324 // that mHdr->mIsAutoArray is true, which surely isn't the case here.
325 mArray.mHdr = mArray.GetAutoArrayBufferUnsafe(mElemAlign);
326 mArray.mHdr->mLength = 0;
327 } else if (mArray.mHdr != mArray.EmptyHdr()) {
328 mArray.mHdr->mIsAutoArray = mIsAuto;
329 }
330 }
331
332 template<class Alloc, class Copy>
333 template<typename ActualAlloc, class Allocator>
334 typename ActualAlloc::ResultTypeProxy
SwapArrayElements(nsTArray_base<Allocator,Copy> & aOther,size_type aElemSize,size_t aElemAlign)335 nsTArray_base<Alloc, Copy>::SwapArrayElements(nsTArray_base<Allocator,
336 Copy>& aOther,
337 size_type aElemSize,
338 size_t aElemAlign)
339 {
340
341 // EnsureNotUsingAutoArrayBuffer will set mHdr = sEmptyHdr even if we have an
342 // auto buffer. We need to point mHdr back to our auto buffer before we
343 // return, otherwise we'll forget that we have an auto buffer at all!
344 // IsAutoArrayRestorer takes care of this for us.
345
346 IsAutoArrayRestorer ourAutoRestorer(*this, aElemAlign);
347 typename nsTArray_base<Allocator, Copy>::IsAutoArrayRestorer
348 otherAutoRestorer(aOther, aElemAlign);
349
350 // If neither array uses an auto buffer which is big enough to store the
351 // other array's elements, then ensure that both arrays use malloc'ed storage
352 // and swap their mHdr pointers.
353 if ((!UsesAutoArrayBuffer() || Capacity() < aOther.Length()) &&
354 (!aOther.UsesAutoArrayBuffer() || aOther.Capacity() < Length())) {
355
356 if (!EnsureNotUsingAutoArrayBuffer<ActualAlloc>(aElemSize) ||
357 !aOther.template EnsureNotUsingAutoArrayBuffer<ActualAlloc>(aElemSize)) {
358 return ActualAlloc::FailureResult();
359 }
360
361 Header* temp = mHdr;
362 mHdr = aOther.mHdr;
363 aOther.mHdr = temp;
364
365 return ActualAlloc::SuccessResult();
366 }
367
368 // Swap the two arrays by copying, since at least one is using an auto
369 // buffer which is large enough to hold all of the aOther's elements. We'll
370 // copy the shorter array into temporary storage.
371 //
372 // (We could do better than this in some circumstances. Suppose we're
373 // swapping arrays X and Y. X has space for 2 elements in its auto buffer,
374 // but currently has length 4, so it's using malloc'ed storage. Y has length
375 // 2. When we swap X and Y, we don't need to use a temporary buffer; we can
376 // write Y straight into X's auto buffer, write X's malloc'ed buffer on top
377 // of Y, and then switch X to using its auto buffer.)
378
379 if (!ActualAlloc::Successful(EnsureCapacity<ActualAlloc>(aOther.Length(), aElemSize)) ||
380 !Allocator::Successful(aOther.template EnsureCapacity<Allocator>(Length(), aElemSize))) {
381 return ActualAlloc::FailureResult();
382 }
383
384 // The EnsureCapacity calls above shouldn't have caused *both* arrays to
385 // switch from their auto buffers to malloc'ed space.
386 MOZ_ASSERT(UsesAutoArrayBuffer() || aOther.UsesAutoArrayBuffer(),
387 "One of the arrays should be using its auto buffer.");
388
389 size_type smallerLength = XPCOM_MIN(Length(), aOther.Length());
390 size_type largerLength = XPCOM_MAX(Length(), aOther.Length());
391 void* smallerElements;
392 void* largerElements;
393 if (Length() <= aOther.Length()) {
394 smallerElements = Hdr() + 1;
395 largerElements = aOther.Hdr() + 1;
396 } else {
397 smallerElements = aOther.Hdr() + 1;
398 largerElements = Hdr() + 1;
399 }
400
401 // Allocate temporary storage for the smaller of the two arrays. We want to
402 // allocate this space on the stack, if it's not too large. Sounds like a
403 // job for AutoTArray! (One of the two arrays we're swapping is using an
404 // auto buffer, so we're likely not allocating a lot of space here. But one
405 // could, in theory, allocate a huge AutoTArray on the heap.)
406 AutoTArray<nsTArray_Impl<uint8_t, ActualAlloc>, 64> temp;
407 if (!ActualAlloc::Successful(temp.template EnsureCapacity<ActualAlloc>(smallerLength,
408 aElemSize))) {
409 return ActualAlloc::FailureResult();
410 }
411
412 Copy::MoveNonOverlappingRegion(temp.Elements(), smallerElements, smallerLength, aElemSize);
413 Copy::MoveNonOverlappingRegion(smallerElements, largerElements, largerLength, aElemSize);
414 Copy::MoveNonOverlappingRegion(largerElements, temp.Elements(), smallerLength, aElemSize);
415
416 // Swap the arrays' lengths.
417 MOZ_ASSERT((aOther.Length() == 0 || mHdr != EmptyHdr()) &&
418 (Length() == 0 || aOther.mHdr != EmptyHdr()),
419 "Don't set sEmptyHdr's length.");
420 size_type tempLength = Length();
421
422 // Avoid writing to EmptyHdr, since it can trigger false
423 // positives with TSan.
424 if (mHdr != EmptyHdr()) {
425 mHdr->mLength = aOther.Length();
426 }
427 if (aOther.mHdr != EmptyHdr()) {
428 aOther.mHdr->mLength = tempLength;
429 }
430
431 return ActualAlloc::SuccessResult();
432 }
433
434 template<class Alloc, class Copy>
435 template<typename ActualAlloc>
436 bool
EnsureNotUsingAutoArrayBuffer(size_type aElemSize)437 nsTArray_base<Alloc, Copy>::EnsureNotUsingAutoArrayBuffer(size_type aElemSize)
438 {
439 if (UsesAutoArrayBuffer()) {
440
441 // If you call this on a 0-length array, we'll set that array's mHdr to
442 // sEmptyHdr, in flagrant violation of the AutoTArray invariants. It's
443 // up to you to set it back! (If you don't, the AutoTArray will forget
444 // that it has an auto buffer.)
445 if (Length() == 0) {
446 mHdr = EmptyHdr();
447 return true;
448 }
449
450 size_type size = sizeof(Header) + Length() * aElemSize;
451
452 Header* header = static_cast<Header*>(ActualAlloc::Malloc(size));
453 if (!header) {
454 return false;
455 }
456
457 Copy::MoveNonOverlappingRegionWithHeader(header, mHdr, Length(), aElemSize);
458 header->mCapacity = Length();
459 mHdr = header;
460 }
461
462 return true;
463 }
464