Line data Source code
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>
12 186087 : nsTArray_base<Alloc, Copy>::nsTArray_base()
13 186087 : : mHdr(EmptyHdr())
14 : {
15 186085 : MOZ_COUNT_CTOR(nsTArray_base);
16 186085 : }
17 :
18 : template<class Alloc, class Copy>
19 140825 : nsTArray_base<Alloc, Copy>::~nsTArray_base()
20 : {
21 140825 : if (mHdr != EmptyHdr() && !UsesAutoArrayBuffer()) {
22 366 : Alloc::Free(mHdr);
23 : }
24 140826 : MOZ_COUNT_DTOR(nsTArray_base);
25 140827 : }
26 :
27 : template<class Alloc, class Copy>
28 : const nsTArrayHeader*
29 463925 : 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 463925 : &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 463925 : 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 463925 : return reinterpret_cast<const Header*>(autoBuf);
55 : }
56 :
57 : template<class Alloc, class Copy>
58 : bool
59 192381 : nsTArray_base<Alloc, Copy>::UsesAutoArrayBuffer() const
60 : {
61 192381 : if (!mHdr->mIsAutoArray) {
62 66228 : 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 252306 : ptrdiff_t diff = reinterpret_cast<const char*>(GetAutoArrayBuffer(8)) -
99 252306 : reinterpret_cast<const char*>(GetAutoArrayBuffer(4));
100 126153 : MOZ_ASSERT(diff >= 0 && diff <= 4,
101 : "GetAutoArrayBuffer doesn't do what we expect.");
102 : #endif
103 :
104 126153 : 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
114 225639 : 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 225639 : if (aCapacity <= mHdr->mCapacity) {
119 191164 : 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 34475 : if (!IsTwiceTheRequiredBytesRepresentableAsUint32(aCapacity, aElemSize)) {
128 0 : ActualAlloc::SizeTooBig((size_t)aCapacity * aElemSize);
129 0 : return ActualAlloc::FailureResult();
130 : }
131 :
132 34476 : size_t reqSize = sizeof(Header) + aCapacity * aElemSize;
133 :
134 34476 : if (mHdr == EmptyHdr()) {
135 : // Malloc() new data
136 17920 : Header* header = static_cast<Header*>(ActualAlloc::Malloc(reqSize));
137 17920 : if (!header) {
138 0 : return ActualAlloc::FailureResult();
139 : }
140 17920 : header->mLength = 0;
141 17920 : header->mCapacity = aCapacity;
142 17920 : header->mIsAutoArray = 0;
143 17920 : mHdr = header;
144 :
145 17920 : 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 16556 : const size_t slowGrowthThreshold = 8 * 1024 * 1024;
153 :
154 : size_t bytesToAlloc;
155 16556 : if (reqSize >= slowGrowthThreshold) {
156 0 : size_t currSize = sizeof(Header) + Capacity() * aElemSize;
157 0 : size_t minNewSize = currSize + (currSize >> 3); // multiply by 1.125
158 0 : bytesToAlloc = reqSize > minNewSize ? reqSize : minNewSize;
159 :
160 : // Round up to the next multiple of MiB.
161 0 : const size_t MiB = 1 << 20;
162 0 : bytesToAlloc = MiB * ((bytesToAlloc + MiB - 1) / MiB);
163 : } else {
164 : // Round up to the next power of two.
165 16556 : bytesToAlloc = mozilla::RoundUpPow2(reqSize);
166 : }
167 :
168 : Header* header;
169 16556 : if (UsesAutoArrayBuffer() || !Copy::allowRealloc) {
170 : // Malloc() and copy
171 4545 : header = static_cast<Header*>(ActualAlloc::Malloc(bytesToAlloc));
172 4545 : if (!header) {
173 0 : return ActualAlloc::FailureResult();
174 : }
175 :
176 4545 : Copy::MoveNonOverlappingRegionWithHeader(header, mHdr, Length(), aElemSize);
177 :
178 4545 : if (!UsesAutoArrayBuffer()) {
179 9 : ActualAlloc::Free(mHdr);
180 : }
181 : } else {
182 : // Realloc() existing data
183 12011 : header = static_cast<Header*>(ActualAlloc::Realloc(mHdr, bytesToAlloc));
184 12011 : if (!header) {
185 0 : return ActualAlloc::FailureResult();
186 : }
187 : }
188 :
189 : // How many elements can we fit in bytesToAlloc?
190 16556 : size_t newCapacity = (bytesToAlloc - sizeof(Header)) / aElemSize;
191 16556 : MOZ_ASSERT(newCapacity >= aCapacity, "Didn't enlarge the array enough!");
192 16556 : header->mCapacity = newCapacity;
193 :
194 16556 : mHdr = header;
195 :
196 16556 : 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
203 40041 : nsTArray_base<Alloc, Copy>::ShrinkCapacity(size_type aElemSize,
204 : size_t aElemAlign)
205 : {
206 40041 : if (mHdr == EmptyHdr() || UsesAutoArrayBuffer()) {
207 28296 : return;
208 : }
209 :
210 11747 : if (mHdr->mLength >= mHdr->mCapacity) { // should never be greater than...
211 19 : return;
212 : }
213 :
214 11728 : size_type length = Length();
215 :
216 11728 : if (IsAutoArray() && GetAutoArrayBuffer(aElemAlign)->mCapacity >= length) {
217 1056 : Header* header = GetAutoArrayBuffer(aElemAlign);
218 :
219 : // Move the data, but don't copy the header to avoid overwriting mCapacity.
220 1056 : header->mLength = length;
221 1056 : Copy::MoveNonOverlappingRegion(header + 1, mHdr + 1, length, aElemSize);
222 :
223 1056 : nsTArrayFallibleAllocator::Free(mHdr);
224 1056 : mHdr = header;
225 1056 : return;
226 : }
227 :
228 10672 : if (length == 0) {
229 10672 : MOZ_ASSERT(!IsAutoArray(), "autoarray should have fit 0 elements");
230 10672 : nsTArrayFallibleAllocator::Free(mHdr);
231 10673 : mHdr = EmptyHdr();
232 10673 : return;
233 : }
234 :
235 0 : size_type size = sizeof(Header) + length * aElemSize;
236 0 : void* ptr = nsTArrayFallibleAllocator::Realloc(mHdr, size);
237 0 : if (!ptr) {
238 0 : return;
239 : }
240 0 : mHdr = static_cast<Header*>(ptr);
241 0 : mHdr->mCapacity = length;
242 : }
243 :
244 : template<class Alloc, class Copy>
245 : template<typename ActualAlloc>
246 : void
247 78519 : nsTArray_base<Alloc, Copy>::ShiftData(index_type aStart,
248 : size_type aOldLen, size_type aNewLen,
249 : size_type aElemSize, size_t aElemAlign)
250 : {
251 78519 : if (aOldLen == aNewLen) {
252 22612 : return;
253 : }
254 :
255 : // Determine how many elements need to be shifted
256 55907 : size_type num = mHdr->mLength - (aStart + aOldLen);
257 :
258 : // Compute the resulting length of the array
259 55907 : mHdr->mLength += aNewLen - aOldLen;
260 55907 : if (mHdr->mLength == 0) {
261 39295 : ShrinkCapacity(aElemSize, aElemAlign);
262 : } else {
263 : // Maybe nothing needs to be shifted
264 16612 : if (num == 0) {
265 14367 : return;
266 : }
267 : // Perform shift (change units to bytes first)
268 2245 : aStart *= aElemSize;
269 2245 : aNewLen *= aElemSize;
270 2245 : aOldLen *= aElemSize;
271 2245 : char* baseAddr = reinterpret_cast<char*>(mHdr + 1) + aStart;
272 2245 : Copy::MoveOverlappingRegion(baseAddr + aNewLen, baseAddr + aOldLen, num, aElemSize);
273 : }
274 : }
275 :
276 : template<class Alloc, class Copy>
277 : template<typename ActualAlloc>
278 : bool
279 2180 : nsTArray_base<Alloc, Copy>::InsertSlotsAt(index_type aIndex, size_type aCount,
280 : size_type aElemSize,
281 : size_t aElemAlign)
282 : {
283 2180 : if (MOZ_UNLIKELY(aIndex > Length())) {
284 0 : InvalidArrayIndex_CRASH(aIndex, Length());
285 : }
286 :
287 2180 : size_type newLen = Length() + aCount;
288 :
289 2180 : EnsureCapacity<ActualAlloc>(newLen, aElemSize);
290 :
291 : // Check for out of memory conditions
292 2180 : if (Capacity() < newLen) {
293 0 : return false;
294 : }
295 :
296 : // Move the existing elements as needed. Note that this will
297 : // change our mLength, so no need to call IncrementLength.
298 2180 : ShiftData<ActualAlloc>(aIndex, 0, aCount, aElemSize, aElemAlign);
299 :
300 2180 : return true;
301 : }
302 :
303 : // nsTArray_base::IsAutoArrayRestorer is an RAII class which takes
304 : // |nsTArray_base &array| in its constructor. When it's destructed, it ensures
305 : // that
306 : //
307 : // * array.mIsAutoArray has the same value as it did when we started, and
308 : // * if array has an auto buffer and mHdr would otherwise point to sEmptyHdr,
309 : // array.mHdr points to array's auto buffer.
310 :
311 : template<class Alloc, class Copy>
312 40814 : nsTArray_base<Alloc, Copy>::IsAutoArrayRestorer::IsAutoArrayRestorer(
313 : nsTArray_base<Alloc, Copy>& aArray,
314 : size_t aElemAlign)
315 : : mArray(aArray)
316 : , mElemAlign(aElemAlign)
317 40814 : , mIsAuto(aArray.IsAutoArray())
318 : {
319 40814 : }
320 :
321 : template<class Alloc, class Copy>
322 40814 : nsTArray_base<Alloc, Copy>::IsAutoArrayRestorer::~IsAutoArrayRestorer()
323 : {
324 : // Careful: We don't want to set mIsAutoArray = 1 on sEmptyHdr.
325 40814 : if (mIsAuto && mArray.mHdr == mArray.EmptyHdr()) {
326 : // Call GetAutoArrayBufferUnsafe() because GetAutoArrayBuffer() asserts
327 : // that mHdr->mIsAutoArray is true, which surely isn't the case here.
328 1821 : mArray.mHdr = mArray.GetAutoArrayBufferUnsafe(mElemAlign);
329 1821 : mArray.mHdr->mLength = 0;
330 38993 : } else if (mArray.mHdr != mArray.EmptyHdr()) {
331 20265 : mArray.mHdr->mIsAutoArray = mIsAuto;
332 : }
333 40814 : }
334 :
335 : template<class Alloc, class Copy>
336 : template<typename ActualAlloc, class Allocator>
337 : typename ActualAlloc::ResultTypeProxy
338 20407 : nsTArray_base<Alloc, Copy>::SwapArrayElements(nsTArray_base<Allocator,
339 : Copy>& aOther,
340 : size_type aElemSize,
341 : size_t aElemAlign)
342 : {
343 :
344 : // EnsureNotUsingAutoArrayBuffer will set mHdr = sEmptyHdr even if we have an
345 : // auto buffer. We need to point mHdr back to our auto buffer before we
346 : // return, otherwise we'll forget that we have an auto buffer at all!
347 : // IsAutoArrayRestorer takes care of this for us.
348 :
349 40814 : IsAutoArrayRestorer ourAutoRestorer(*this, aElemAlign);
350 : typename nsTArray_base<Allocator, Copy>::IsAutoArrayRestorer
351 40814 : otherAutoRestorer(aOther, aElemAlign);
352 :
353 : // If neither array uses an auto buffer which is big enough to store the
354 : // other array's elements, then ensure that both arrays use malloc'ed storage
355 : // and swap their mHdr pointers.
356 45329 : if ((!UsesAutoArrayBuffer() || Capacity() < aOther.Length()) &&
357 12461 : (!aOther.UsesAutoArrayBuffer() || aOther.Capacity() < Length())) {
358 :
359 24922 : if (!EnsureNotUsingAutoArrayBuffer<ActualAlloc>(aElemSize) ||
360 12461 : !aOther.template EnsureNotUsingAutoArrayBuffer<ActualAlloc>(aElemSize)) {
361 0 : return ActualAlloc::FailureResult();
362 : }
363 :
364 12461 : Header* temp = mHdr;
365 12461 : mHdr = aOther.mHdr;
366 12461 : aOther.mHdr = temp;
367 :
368 12461 : return ActualAlloc::SuccessResult();
369 : }
370 :
371 : // Swap the two arrays by copying, since at least one is using an auto
372 : // buffer which is large enough to hold all of the aOther's elements. We'll
373 : // copy the shorter array into temporary storage.
374 : //
375 : // (We could do better than this in some circumstances. Suppose we're
376 : // swapping arrays X and Y. X has space for 2 elements in its auto buffer,
377 : // but currently has length 4, so it's using malloc'ed storage. Y has length
378 : // 2. When we swap X and Y, we don't need to use a temporary buffer; we can
379 : // write Y straight into X's auto buffer, write X's malloc'ed buffer on top
380 : // of Y, and then switch X to using its auto buffer.)
381 :
382 23838 : if (!ActualAlloc::Successful(EnsureCapacity<ActualAlloc>(aOther.Length(), aElemSize)) ||
383 15892 : !Allocator::Successful(aOther.template EnsureCapacity<Allocator>(Length(), aElemSize))) {
384 0 : return ActualAlloc::FailureResult();
385 : }
386 :
387 : // The EnsureCapacity calls above shouldn't have caused *both* arrays to
388 : // switch from their auto buffers to malloc'ed space.
389 7946 : MOZ_ASSERT(UsesAutoArrayBuffer() || aOther.UsesAutoArrayBuffer(),
390 : "One of the arrays should be using its auto buffer.");
391 :
392 7946 : size_type smallerLength = XPCOM_MIN(Length(), aOther.Length());
393 7946 : size_type largerLength = XPCOM_MAX(Length(), aOther.Length());
394 : void* smallerElements;
395 : void* largerElements;
396 7946 : if (Length() <= aOther.Length()) {
397 7946 : smallerElements = Hdr() + 1;
398 7946 : largerElements = aOther.Hdr() + 1;
399 : } else {
400 0 : smallerElements = aOther.Hdr() + 1;
401 0 : largerElements = Hdr() + 1;
402 : }
403 :
404 : // Allocate temporary storage for the smaller of the two arrays. We want to
405 : // allocate this space on the stack, if it's not too large. Sounds like a
406 : // job for AutoTArray! (One of the two arrays we're swapping is using an
407 : // auto buffer, so we're likely not allocating a lot of space here. But one
408 : // could, in theory, allocate a huge AutoTArray on the heap.)
409 15892 : AutoTArray<nsTArray_Impl<uint8_t, ActualAlloc>, 64> temp;
410 7946 : if (!ActualAlloc::Successful(temp.template EnsureCapacity<ActualAlloc>(smallerLength,
411 : aElemSize))) {
412 0 : return ActualAlloc::FailureResult();
413 : }
414 :
415 7946 : Copy::MoveNonOverlappingRegion(temp.Elements(), smallerElements, smallerLength, aElemSize);
416 7946 : Copy::MoveNonOverlappingRegion(smallerElements, largerElements, largerLength, aElemSize);
417 7946 : Copy::MoveNonOverlappingRegion(largerElements, temp.Elements(), smallerLength, aElemSize);
418 :
419 : // Swap the arrays' lengths.
420 7946 : MOZ_ASSERT((aOther.Length() == 0 || mHdr != EmptyHdr()) &&
421 : (Length() == 0 || aOther.mHdr != EmptyHdr()),
422 : "Don't set sEmptyHdr's length.");
423 7946 : size_type tempLength = Length();
424 :
425 : // Avoid writing to EmptyHdr, since it can trigger false
426 : // positives with TSan.
427 7946 : if (mHdr != EmptyHdr()) {
428 7946 : mHdr->mLength = aOther.Length();
429 : }
430 7946 : if (aOther.mHdr != EmptyHdr()) {
431 7946 : aOther.mHdr->mLength = tempLength;
432 : }
433 :
434 7946 : return ActualAlloc::SuccessResult();
435 : }
436 :
437 : template<class Alloc, class Copy>
438 : template<typename ActualAlloc>
439 : bool
440 24922 : nsTArray_base<Alloc, Copy>::EnsureNotUsingAutoArrayBuffer(size_type aElemSize)
441 : {
442 24922 : if (UsesAutoArrayBuffer()) {
443 :
444 : // If you call this on a 0-length array, we'll set that array's mHdr to
445 : // sEmptyHdr, in flagrant violation of the AutoTArray invariants. It's
446 : // up to you to set it back! (If you don't, the AutoTArray will forget
447 : // that it has an auto buffer.)
448 1821 : if (Length() == 0) {
449 1821 : mHdr = EmptyHdr();
450 1821 : return true;
451 : }
452 :
453 0 : size_type size = sizeof(Header) + Length() * aElemSize;
454 :
455 0 : Header* header = static_cast<Header*>(ActualAlloc::Malloc(size));
456 0 : if (!header) {
457 0 : return false;
458 : }
459 :
460 0 : Copy::MoveNonOverlappingRegionWithHeader(header, mHdr, Length(), aElemSize);
461 0 : header->mCapacity = Length();
462 0 : mHdr = header;
463 : }
464 :
465 23101 : return true;
466 : }
|
