From 0a78d918f0f411e0da2242a84a396f169154f5d6 Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Fri, 5 Jun 2015 00:41:36 +0200 Subject: Replace qAllocMore with a pair of more useful functions The first is "exact", not "more": qCalculateBlockSize. It ensures that there's no overflow in multiplying, adding the header size or when converting back to an int. The second is the replacement for qAllocMore: it calculates the block size like the first, but increases the block size to accommodate future appends. The number of elements that fit in the block is also returned. Task-number: QTBUG-41230 Change-Id: I52dd43c12685407bb9a6ffff13f5da09f816e667 Reviewed-by: Lars Knoll --- src/corelib/tools/qbytearray.cpp | 112 +++++++++++++++++++++++++++++++++++---- 1 file changed, 102 insertions(+), 10 deletions(-) (limited to 'src/corelib/tools/qbytearray.cpp') diff --git a/src/corelib/tools/qbytearray.cpp b/src/corelib/tools/qbytearray.cpp index 2efe3c1a86..c9d6f4e411 100644 --- a/src/corelib/tools/qbytearray.cpp +++ b/src/corelib/tools/qbytearray.cpp @@ -46,6 +46,7 @@ #include "qlocale.h" #include "qlocale_p.h" #include "qlocale_tools_p.h" +#include "private/qnumeric_p.h" #include "qstringalgorithms_p.h" #include "qscopedpointer.h" #include "qbytearray_p.h" @@ -128,17 +129,104 @@ int qFindByteArray( const char *haystack0, int haystackLen, int from, const char *needle0, int needleLen); +/* + * This pair of functions is declared in qtools_p.h and is used by the Qt + * containers to allocate memory and grow the memory block during append + * operations. + * + * They take size_t parameters and return size_t so they will change sizes + * according to the pointer width. However, knowing Qt containers store the + * container size and element indexes in ints, these functions never return a + * size larger than INT_MAX. This is done by casting the element count and + * memory block size to int in several comparisons: the check for negative is + * very fast on most platforms as the code only needs to check the sign bit. + * + * These functions return SIZE_MAX on overflow, which can be passed to malloc() + * and will surely cause a NULL return (there's no way you can allocate a + * memory block the size of your entire VM space). + */ + +/*! + \internal + \since 5.7 -int qAllocMore(int alloc, int extra) Q_DECL_NOTHROW + Returns the memory block size for a container containing \a elementCount + elements, each of \a elementSize bytes, plus a header of \a headerSize + bytes. That is, this function returns \c + {elementCount * elementSize + headerSize} + + but unlike the simple calculation, it checks for overflows during the + multiplication and the addition. + + Both \a elementCount and \a headerSize can be zero, but \a elementSize + cannot. + + This function returns SIZE_MAX (~0) on overflow or if the memory block size + would not fit an int. +*/ +size_t qCalculateBlockSize(size_t elementCount, size_t elementSize, size_t headerSize) Q_DECL_NOTHROW { - Q_ASSERT(alloc >= 0 && extra >= 0 && extra <= MaxAllocSize); - Q_ASSERT_X(alloc <= MaxAllocSize - extra, "qAllocMore", "Requested size is too large!"); + unsigned count = unsigned(elementCount); + unsigned size = unsigned(elementSize); + unsigned header = unsigned(headerSize); + Q_ASSERT(elementSize); + Q_ASSERT(size == elementSize); + Q_ASSERT(header == headerSize); + + if (Q_UNLIKELY(count != elementCount)) + return std::numeric_limits::max(); + + unsigned bytes; + if (Q_UNLIKELY(mul_overflow(size, count, &bytes)) || + Q_UNLIKELY(add_overflow(bytes, header, &bytes))) + return std::numeric_limits::max(); + if (Q_UNLIKELY(int(bytes) < 0)) // catches bytes >= 2GB + return std::numeric_limits::max(); + + return bytes; +} + +/*! + \internal + \since 5.7 - unsigned nalloc = qNextPowerOfTwo(alloc + extra); + Returns the memory block size and the number of elements that will fit in + that block for a container containing \a elementCount elements, each of \a + elementSize bytes, plus a header of \a headerSize bytes. This function + assumes the container will grow and pre-allocates a growth factor. - Q_ASSERT(nalloc > unsigned(alloc + extra)); + Both \a elementCount and \a headerSize can be zero, but \a elementSize + cannot. + + This function returns SIZE_MAX (~0) on overflow or if the memory block size + would not fit an int. + + \note The memory block may contain up to \a elementSize - 1 bytes more than + needed. +*/ +CalculateGrowingBlockSizeResult +qCalculateGrowingBlockSize(size_t elementCount, size_t elementSize, size_t headerSize) Q_DECL_NOTHROW +{ + CalculateGrowingBlockSizeResult result = { + std::numeric_limits::max(),std::numeric_limits::max() + }; + + unsigned bytes = unsigned(qCalculateBlockSize(elementCount, elementSize, headerSize)); + if (int(bytes) < 0) // catches std::numeric_limits::max() + return result; + + unsigned morebytes = qNextPowerOfTwo(bytes); + if (Q_UNLIKELY(int(morebytes) < 0)) { + // catches morebytes == 2GB + // grow by half the difference between bytes and morebytes + bytes += (morebytes - bytes) / 2; + } else { + bytes = morebytes; + } - return nalloc - extra; + result.elementCount = (bytes - unsigned(headerSize)) / unsigned(elementSize); + result.size = bytes; + return result; } /***************************************************************************** @@ -1618,12 +1706,16 @@ void QByteArray::reallocData(uint alloc, Data::AllocationOptions options) Data::deallocate(d); d = x; } else { + size_t blockSize; if (options & Data::Grow) { - if (alloc > MaxByteArraySize) - qBadAlloc(); - alloc = qAllocMore(alloc, sizeof(Data)); + auto r = qCalculateGrowingBlockSize(alloc, sizeof(QChar), sizeof(Data)); + blockSize = r.size; + alloc = uint(r.elementCount); + } else { + blockSize = qCalculateBlockSize(alloc, sizeof(QChar), sizeof(Data)); } - Data *x = static_cast(::realloc(d, sizeof(Data) + alloc)); + + Data *x = static_cast(::realloc(d, blockSize)); Q_CHECK_PTR(x); x->alloc = alloc; x->capacityReserved = (options & Data::CapacityReserved) ? 1 : 0; -- cgit v1.2.3