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 <lars.knoll@qt.io>

1 files changed, 102 insertions, 10 deletions

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<size_t>::max();
+
+    unsigned bytes;
+    if (Q_UNLIKELY(mul_overflow(size, count, &bytes)) ||
+            Q_UNLIKELY(add_overflow(bytes, header, &bytes)))
+        return std::numeric_limits<size_t>::max();
+    if (Q_UNLIKELY(int(bytes) < 0))     // catches bytes >= 2GB
+        return std::numeric_limits<size_t>::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<size_t>::max(),std::numeric_limits<size_t>::max()
+    };
+
+    unsigned bytes = unsigned(qCalculateBlockSize(elementCount, elementSize, headerSize));
+    if (int(bytes) < 0)     // catches std::numeric_limits<size_t>::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<Data *>(::realloc(d, sizeof(Data) + alloc));
+
+        Data *x = static_cast<Data *>(::realloc(d, blockSize));
         Q_CHECK_PTR(x);
         x->alloc = alloc;
         x->capacityReserved = (options & Data::CapacityReserved) ? 1 : 0;