From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- xpcom/glue/nsTArray-inl.h | 463 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 463 insertions(+) create mode 100644 xpcom/glue/nsTArray-inl.h (limited to 'xpcom/glue/nsTArray-inl.h') diff --git a/xpcom/glue/nsTArray-inl.h b/xpcom/glue/nsTArray-inl.h new file mode 100644 index 000000000..af57c9866 --- /dev/null +++ b/xpcom/glue/nsTArray-inl.h @@ -0,0 +1,463 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* vim: set ts=8 sts=2 et sw=2 tw=80: */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef nsTArray_h__ +# error "Don't include this file directly" +#endif + +template +nsTArray_base::nsTArray_base() + : mHdr(EmptyHdr()) +{ + MOZ_COUNT_CTOR(nsTArray_base); +} + +template +nsTArray_base::~nsTArray_base() +{ + if (mHdr != EmptyHdr() && !UsesAutoArrayBuffer()) { + Alloc::Free(mHdr); + } + MOZ_COUNT_DTOR(nsTArray_base); +} + +template +const nsTArrayHeader* +nsTArray_base::GetAutoArrayBufferUnsafe(size_t aElemAlign) const +{ + // Assuming |this| points to an nsAutoArray, we want to get a pointer to + // mAutoBuf. So just cast |this| to nsAutoArray* and read &mAutoBuf! + + const void* autoBuf = + &reinterpret_cast, 1>*>(this)->mAutoBuf; + + // If we're on a 32-bit system and aElemAlign is 8, we need to adjust our + // pointer to take into account the extra alignment in the auto array. + + static_assert(sizeof(void*) != 4 || + (MOZ_ALIGNOF(mozilla::AlignedElem<8>) == 8 && + sizeof(AutoTArray, 1>) == + sizeof(void*) + sizeof(nsTArrayHeader) + + 4 + sizeof(mozilla::AlignedElem<8>)), + "auto array padding wasn't what we expected"); + + // We don't support alignments greater than 8 bytes. + MOZ_ASSERT(aElemAlign <= 4 || aElemAlign == 8, + "unsupported alignment."); + if (sizeof(void*) == 4 && aElemAlign == 8) { + autoBuf = reinterpret_cast(autoBuf) + 4; + } + + return reinterpret_cast(autoBuf); +} + +template +bool +nsTArray_base::UsesAutoArrayBuffer() const +{ + if (!mHdr->mIsAutoArray) { + return false; + } + + // This is nuts. If we were sane, we'd pass aElemAlign as a parameter to + // this function. Unfortunately this function is called in nsTArray_base's + // destructor, at which point we don't know elem_type's alignment. + // + // We'll fall on our face and return true when we should say false if + // + // * we're not using our auto buffer, + // * aElemAlign == 4, and + // * mHdr == GetAutoArrayBuffer(8). + // + // This could happen if |*this| lives on the heap and malloc allocated our + // buffer on the heap adjacent to |*this|. + // + // However, we can show that this can't happen. If |this| is an auto array + // (as we ensured at the beginning of the method), GetAutoArrayBuffer(8) + // always points to memory owned by |*this|, because (as we assert below) + // + // * GetAutoArrayBuffer(8) is at most 4 bytes past GetAutoArrayBuffer(4), and + // * sizeof(nsTArrayHeader) > 4. + // + // Since AutoTArray always contains an nsTArrayHeader, + // GetAutoArrayBuffer(8) will always point inside the auto array object, + // even if it doesn't point at the beginning of the header. + // + // Note that this means that we can't store elements with alignment 16 in an + // nsTArray, because GetAutoArrayBuffer(16) could lie outside the memory + // owned by this AutoTArray. We statically assert that elem_type's + // alignment is 8 bytes or less in AutoTArray. + + static_assert(sizeof(nsTArrayHeader) > 4, + "see comment above"); + +#ifdef DEBUG + ptrdiff_t diff = reinterpret_cast(GetAutoArrayBuffer(8)) - + reinterpret_cast(GetAutoArrayBuffer(4)); + MOZ_ASSERT(diff >= 0 && diff <= 4, + "GetAutoArrayBuffer doesn't do what we expect."); +#endif + + return mHdr == GetAutoArrayBuffer(4) || mHdr == GetAutoArrayBuffer(8); +} + +// defined in nsTArray.cpp +bool IsTwiceTheRequiredBytesRepresentableAsUint32(size_t aCapacity, + size_t aElemSize); + +template +template +typename ActualAlloc::ResultTypeProxy +nsTArray_base::EnsureCapacity(size_type aCapacity, + size_type aElemSize) +{ + // This should be the most common case so test this first + if (aCapacity <= mHdr->mCapacity) { + return ActualAlloc::SuccessResult(); + } + + // If the requested memory allocation exceeds size_type(-1)/2, then + // our doubling algorithm may not be able to allocate it. + // Additionally, if it exceeds uint32_t(-1) then we couldn't fit in the + // Header::mCapacity member. Just bail out in cases like that. We don't want + // to be allocating 2 GB+ arrays anyway. + if (!IsTwiceTheRequiredBytesRepresentableAsUint32(aCapacity, aElemSize)) { + ActualAlloc::SizeTooBig((size_t)aCapacity * aElemSize); + return ActualAlloc::FailureResult(); + } + + size_t reqSize = sizeof(Header) + aCapacity * aElemSize; + + if (mHdr == EmptyHdr()) { + // Malloc() new data + Header* header = static_cast(ActualAlloc::Malloc(reqSize)); + if (!header) { + return ActualAlloc::FailureResult(); + } + header->mLength = 0; + header->mCapacity = aCapacity; + header->mIsAutoArray = 0; + mHdr = header; + + return ActualAlloc::SuccessResult(); + } + + // We increase our capacity so that the allocated buffer grows exponentially, + // which gives us amortized O(1) appending. Below the threshold, we use + // powers-of-two. Above the threshold, we grow by at least 1.125, rounding up + // to the nearest MiB. + const size_t slowGrowthThreshold = 8 * 1024 * 1024; + + size_t bytesToAlloc; + if (reqSize >= slowGrowthThreshold) { + size_t currSize = sizeof(Header) + Capacity() * aElemSize; + size_t minNewSize = currSize + (currSize >> 3); // multiply by 1.125 + bytesToAlloc = reqSize > minNewSize ? reqSize : minNewSize; + + // Round up to the next multiple of MiB. + const size_t MiB = 1 << 20; + bytesToAlloc = MiB * ((bytesToAlloc + MiB - 1) / MiB); + } else { + // Round up to the next power of two. + bytesToAlloc = mozilla::RoundUpPow2(reqSize); + } + + Header* header; + if (UsesAutoArrayBuffer() || !Copy::allowRealloc) { + // Malloc() and copy + header = static_cast(ActualAlloc::Malloc(bytesToAlloc)); + if (!header) { + return ActualAlloc::FailureResult(); + } + + Copy::MoveNonOverlappingRegionWithHeader(header, mHdr, Length(), aElemSize); + + if (!UsesAutoArrayBuffer()) { + ActualAlloc::Free(mHdr); + } + } else { + // Realloc() existing data + header = static_cast(ActualAlloc::Realloc(mHdr, bytesToAlloc)); + if (!header) { + return ActualAlloc::FailureResult(); + } + } + + // How many elements can we fit in bytesToAlloc? + size_t newCapacity = (bytesToAlloc - sizeof(Header)) / aElemSize; + MOZ_ASSERT(newCapacity >= aCapacity, "Didn't enlarge the array enough!"); + header->mCapacity = newCapacity; + + mHdr = header; + + return ActualAlloc::SuccessResult(); +} + +// We don't need use Alloc template parameter specified here because failure to +// shrink the capacity will leave the array unchanged. +template +void +nsTArray_base::ShrinkCapacity(size_type aElemSize, + size_t aElemAlign) +{ + if (mHdr == EmptyHdr() || UsesAutoArrayBuffer()) { + return; + } + + if (mHdr->mLength >= mHdr->mCapacity) { // should never be greater than... + return; + } + + size_type length = Length(); + + if (IsAutoArray() && GetAutoArrayBuffer(aElemAlign)->mCapacity >= length) { + Header* header = GetAutoArrayBuffer(aElemAlign); + + // Move the data, but don't copy the header to avoid overwriting mCapacity. + header->mLength = length; + Copy::MoveNonOverlappingRegion(header + 1, mHdr + 1, length, aElemSize); + + nsTArrayFallibleAllocator::Free(mHdr); + mHdr = header; + return; + } + + if (length == 0) { + MOZ_ASSERT(!IsAutoArray(), "autoarray should have fit 0 elements"); + nsTArrayFallibleAllocator::Free(mHdr); + mHdr = EmptyHdr(); + return; + } + + size_type size = sizeof(Header) + length * aElemSize; + void* ptr = nsTArrayFallibleAllocator::Realloc(mHdr, size); + if (!ptr) { + return; + } + mHdr = static_cast(ptr); + mHdr->mCapacity = length; +} + +template +template +void +nsTArray_base::ShiftData(index_type aStart, + size_type aOldLen, size_type aNewLen, + size_type aElemSize, size_t aElemAlign) +{ + if (aOldLen == aNewLen) { + return; + } + + // Determine how many elements need to be shifted + size_type num = mHdr->mLength - (aStart + aOldLen); + + // Compute the resulting length of the array + mHdr->mLength += aNewLen - aOldLen; + if (mHdr->mLength == 0) { + ShrinkCapacity(aElemSize, aElemAlign); + } else { + // Maybe nothing needs to be shifted + if (num == 0) { + return; + } + // Perform shift (change units to bytes first) + aStart *= aElemSize; + aNewLen *= aElemSize; + aOldLen *= aElemSize; + char* baseAddr = reinterpret_cast(mHdr + 1) + aStart; + Copy::MoveOverlappingRegion(baseAddr + aNewLen, baseAddr + aOldLen, num, aElemSize); + } +} + +template +template +bool +nsTArray_base::InsertSlotsAt(index_type aIndex, size_type aCount, + size_type aElemSize, + size_t aElemAlign) +{ + MOZ_ASSERT(aIndex <= Length(), "Bogus insertion index"); + size_type newLen = Length() + aCount; + + EnsureCapacity(newLen, aElemSize); + + // Check for out of memory conditions + if (Capacity() < newLen) { + return false; + } + + // Move the existing elements as needed. Note that this will + // change our mLength, so no need to call IncrementLength. + ShiftData(aIndex, 0, aCount, aElemSize, aElemAlign); + + return true; +} + +// nsTArray_base::IsAutoArrayRestorer is an RAII class which takes +// |nsTArray_base &array| in its constructor. When it's destructed, it ensures +// that +// +// * array.mIsAutoArray has the same value as it did when we started, and +// * if array has an auto buffer and mHdr would otherwise point to sEmptyHdr, +// array.mHdr points to array's auto buffer. + +template +nsTArray_base::IsAutoArrayRestorer::IsAutoArrayRestorer( + nsTArray_base& aArray, + size_t aElemAlign) + : mArray(aArray) + , mElemAlign(aElemAlign) + , mIsAuto(aArray.IsAutoArray()) +{ +} + +template +nsTArray_base::IsAutoArrayRestorer::~IsAutoArrayRestorer() +{ + // Careful: We don't want to set mIsAutoArray = 1 on sEmptyHdr. + if (mIsAuto && mArray.mHdr == mArray.EmptyHdr()) { + // Call GetAutoArrayBufferUnsafe() because GetAutoArrayBuffer() asserts + // that mHdr->mIsAutoArray is true, which surely isn't the case here. + mArray.mHdr = mArray.GetAutoArrayBufferUnsafe(mElemAlign); + mArray.mHdr->mLength = 0; + } else if (mArray.mHdr != mArray.EmptyHdr()) { + mArray.mHdr->mIsAutoArray = mIsAuto; + } +} + +template +template +typename ActualAlloc::ResultTypeProxy +nsTArray_base::SwapArrayElements(nsTArray_base& aOther, + size_type aElemSize, + size_t aElemAlign) +{ + + // EnsureNotUsingAutoArrayBuffer will set mHdr = sEmptyHdr even if we have an + // auto buffer. We need to point mHdr back to our auto buffer before we + // return, otherwise we'll forget that we have an auto buffer at all! + // IsAutoArrayRestorer takes care of this for us. + + IsAutoArrayRestorer ourAutoRestorer(*this, aElemAlign); + typename nsTArray_base::IsAutoArrayRestorer + otherAutoRestorer(aOther, aElemAlign); + + // If neither array uses an auto buffer which is big enough to store the + // other array's elements, then ensure that both arrays use malloc'ed storage + // and swap their mHdr pointers. + if ((!UsesAutoArrayBuffer() || Capacity() < aOther.Length()) && + (!aOther.UsesAutoArrayBuffer() || aOther.Capacity() < Length())) { + + if (!EnsureNotUsingAutoArrayBuffer(aElemSize) || + !aOther.template EnsureNotUsingAutoArrayBuffer(aElemSize)) { + return ActualAlloc::FailureResult(); + } + + Header* temp = mHdr; + mHdr = aOther.mHdr; + aOther.mHdr = temp; + + return ActualAlloc::SuccessResult(); + } + + // Swap the two arrays by copying, since at least one is using an auto + // buffer which is large enough to hold all of the aOther's elements. We'll + // copy the shorter array into temporary storage. + // + // (We could do better than this in some circumstances. Suppose we're + // swapping arrays X and Y. X has space for 2 elements in its auto buffer, + // but currently has length 4, so it's using malloc'ed storage. Y has length + // 2. When we swap X and Y, we don't need to use a temporary buffer; we can + // write Y straight into X's auto buffer, write X's malloc'ed buffer on top + // of Y, and then switch X to using its auto buffer.) + + if (!ActualAlloc::Successful(EnsureCapacity(aOther.Length(), aElemSize)) || + !Allocator::Successful(aOther.template EnsureCapacity(Length(), aElemSize))) { + return ActualAlloc::FailureResult(); + } + + // The EnsureCapacity calls above shouldn't have caused *both* arrays to + // switch from their auto buffers to malloc'ed space. + MOZ_ASSERT(UsesAutoArrayBuffer() || aOther.UsesAutoArrayBuffer(), + "One of the arrays should be using its auto buffer."); + + size_type smallerLength = XPCOM_MIN(Length(), aOther.Length()); + size_type largerLength = XPCOM_MAX(Length(), aOther.Length()); + void* smallerElements; + void* largerElements; + if (Length() <= aOther.Length()) { + smallerElements = Hdr() + 1; + largerElements = aOther.Hdr() + 1; + } else { + smallerElements = aOther.Hdr() + 1; + largerElements = Hdr() + 1; + } + + // Allocate temporary storage for the smaller of the two arrays. We want to + // allocate this space on the stack, if it's not too large. Sounds like a + // job for AutoTArray! (One of the two arrays we're swapping is using an + // auto buffer, so we're likely not allocating a lot of space here. But one + // could, in theory, allocate a huge AutoTArray on the heap.) + AutoTArray, 64> temp; + if (!ActualAlloc::Successful(temp.template EnsureCapacity(smallerLength, + aElemSize))) { + return ActualAlloc::FailureResult(); + } + + Copy::MoveNonOverlappingRegion(temp.Elements(), smallerElements, smallerLength, aElemSize); + Copy::MoveNonOverlappingRegion(smallerElements, largerElements, largerLength, aElemSize); + Copy::MoveNonOverlappingRegion(largerElements, temp.Elements(), smallerLength, aElemSize); + + // Swap the arrays' lengths. + MOZ_ASSERT((aOther.Length() == 0 || mHdr != EmptyHdr()) && + (Length() == 0 || aOther.mHdr != EmptyHdr()), + "Don't set sEmptyHdr's length."); + size_type tempLength = Length(); + + // Avoid writing to EmptyHdr, since it can trigger false + // positives with TSan. + if (mHdr != EmptyHdr()) { + mHdr->mLength = aOther.Length(); + } + if (aOther.mHdr != EmptyHdr()) { + aOther.mHdr->mLength = tempLength; + } + + return ActualAlloc::SuccessResult(); +} + +template +template +bool +nsTArray_base::EnsureNotUsingAutoArrayBuffer(size_type aElemSize) +{ + if (UsesAutoArrayBuffer()) { + + // If you call this on a 0-length array, we'll set that array's mHdr to + // sEmptyHdr, in flagrant violation of the AutoTArray invariants. It's + // up to you to set it back! (If you don't, the AutoTArray will forget + // that it has an auto buffer.) + if (Length() == 0) { + mHdr = EmptyHdr(); + return true; + } + + size_type size = sizeof(Header) + Length() * aElemSize; + + Header* header = static_cast(ActualAlloc::Malloc(size)); + if (!header) { + return false; + } + + Copy::MoveNonOverlappingRegionWithHeader(header, mHdr, Length(), aElemSize); + header->mCapacity = Length(); + mHdr = header; + } + + return true; +} -- cgit v1.2.3