summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/corelib/tools/qarraydata.cpp34
-rw-r--r--src/corelib/tools/qbytearray.cpp112
-rw-r--r--src/corelib/tools/qlist.cpp29
-rw-r--r--src/corelib/tools/qstring.cpp11
-rw-r--r--src/corelib/tools/qtools_p.h14
-rw-r--r--src/gui/text/qfragmentmap_p.h9
-rw-r--r--tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp88
-rw-r--r--tests/benchmarks/corelib/tools/qvector/outofline.cpp2
8 files changed, 217 insertions, 82 deletions
diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp
index 36f1997a6c..55af7256be 100644
--- a/src/corelib/tools/qarraydata.cpp
+++ b/src/corelib/tools/qarraydata.cpp
@@ -1,6 +1,7 @@
/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2016 Intel Corporation.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
@@ -87,29 +88,20 @@ QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment,
if (!(options & RawData))
headerSize += (alignment - Q_ALIGNOF(QArrayData));
- // Allocate additional space if array is growing
- if (options & Grow) {
-
- // Guard against integer overflow when multiplying.
- if (capacity > std::numeric_limits<size_t>::max() / objectSize)
- return 0;
-
- size_t alloc;
- if (mul_overflow(objectSize, capacity, &alloc))
- return 0;
-
- // Make sure qAllocMore won't overflow qAllocMore.
- if (headerSize > size_t(MaxAllocSize) || alloc > size_t(MaxAllocSize) - headerSize)
- return 0;
-
- capacity = qAllocMore(int(alloc), int(headerSize)) / int(objectSize);
- }
+ if (headerSize > size_t(MaxAllocSize))
+ return 0;
+ // Calculate the byte size
+ // allocSize = objectSize * capacity + headerSize, but checked for overflow
+ // plus padded to grow in size
size_t allocSize;
- if (mul_overflow(objectSize, capacity, &allocSize))
- return 0;
- if (add_overflow(allocSize, headerSize, &allocSize))
- return 0;
+ if (options & Grow) {
+ auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize);
+ capacity = r.elementCount;
+ allocSize = r.size;
+ } else {
+ allocSize = qCalculateBlockSize(capacity, objectSize, headerSize);
+ }
QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize));
if (header) {
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;
diff --git a/src/corelib/tools/qlist.cpp b/src/corelib/tools/qlist.cpp
index 7dd02bf954..1762da2c8f 100644
--- a/src/corelib/tools/qlist.cpp
+++ b/src/corelib/tools/qlist.cpp
@@ -60,15 +60,6 @@ QT_BEGIN_NAMESPACE
const QListData::Data QListData::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, { 0 } };
-static int grow(int size)
-{
- if (size_t(size) > (MaxAllocSize - QListData::DataHeaderSize) / sizeof(void *))
- qBadAlloc();
- // dear compiler: don't optimize me out.
- volatile int x = qAllocMore(size * sizeof(void *), QListData::DataHeaderSize) / sizeof(void *);
- return x;
-}
-
/*!
* Detaches the QListData by allocating new memory for a list which will be bigger
* than the copied one and is expected to grow further.
@@ -84,12 +75,12 @@ QListData::Data *QListData::detach_grow(int *idx, int num)
Data *x = d;
int l = x->end - x->begin;
int nl = l + num;
- int alloc = grow(nl);
- Data* t = static_cast<Data *>(::malloc(DataHeaderSize + alloc * sizeof(void *)));
+ auto blockInfo = qCalculateGrowingBlockSize(nl, sizeof(void *), DataHeaderSize);
+ Data* t = static_cast<Data *>(::malloc(blockInfo.size));
Q_CHECK_PTR(t);
+ t->alloc = int(uint(blockInfo.elementCount));
t->ref.initializeOwned();
- t->alloc = alloc;
// The space reservation algorithm's optimization is biased towards appending:
// Something which looks like an append will put the data at the beginning,
// while something which looks like a prepend will put it in the middle
@@ -99,12 +90,12 @@ QListData::Data *QListData::detach_grow(int *idx, int num)
int bg;
if (*idx < 0) {
*idx = 0;
- bg = (alloc - nl) >> 1;
+ bg = (t->alloc - nl) >> 1;
} else if (*idx > l) {
*idx = l;
bg = 0;
} else if (*idx < (l >> 1)) {
- bg = (alloc - nl) >> 1;
+ bg = (t->alloc - nl) >> 1;
} else {
bg = 0;
}
@@ -126,7 +117,7 @@ QListData::Data *QListData::detach_grow(int *idx, int num)
QListData::Data *QListData::detach(int alloc)
{
Data *x = d;
- Data* t = static_cast<Data *>(::malloc(DataHeaderSize + alloc * sizeof(void *)));
+ Data* t = static_cast<Data *>(::malloc(qCalculateBlockSize(alloc, sizeof(void*), DataHeaderSize)));
Q_CHECK_PTR(t);
t->ref.initializeOwned();
@@ -146,7 +137,7 @@ QListData::Data *QListData::detach(int alloc)
void QListData::realloc(int alloc)
{
Q_ASSERT(!d->ref.isShared());
- Data *x = static_cast<Data *>(::realloc(d, DataHeaderSize + alloc * sizeof(void *)));
+ Data *x = static_cast<Data *>(::realloc(d, qCalculateBlockSize(alloc, sizeof(void *), DataHeaderSize)));
Q_CHECK_PTR(x);
d = x;
@@ -158,12 +149,12 @@ void QListData::realloc(int alloc)
void QListData::realloc_grow(int growth)
{
Q_ASSERT(!d->ref.isShared());
- int alloc = grow(d->alloc + growth);
- Data *x = static_cast<Data *>(::realloc(d, DataHeaderSize + alloc * sizeof(void *)));
+ auto r = qCalculateGrowingBlockSize(d->alloc + growth, sizeof(void *), DataHeaderSize);
+ Data *x = static_cast<Data *>(::realloc(d, r.size));
Q_CHECK_PTR(x);
d = x;
- d->alloc = alloc;
+ d->alloc = int(uint(r.elementCount));
}
void QListData::dispose(Data *d)
diff --git a/src/corelib/tools/qstring.cpp b/src/corelib/tools/qstring.cpp
index cf36be1f7c..85da174366 100644
--- a/src/corelib/tools/qstring.cpp
+++ b/src/corelib/tools/qstring.cpp
@@ -1760,10 +1760,13 @@ void QString::resize(int size, QChar fillChar)
void QString::reallocData(uint alloc, bool grow)
{
+ size_t blockSize;
if (grow) {
- if (alloc > (uint(MaxAllocSize) - sizeof(Data)) / sizeof(QChar))
- qBadAlloc();
- alloc = qAllocMore(alloc * sizeof(QChar), sizeof(Data)) / sizeof(QChar);
+ auto r = qCalculateGrowingBlockSize(alloc, sizeof(QChar), sizeof(Data));
+ blockSize = r.size;
+ alloc = uint(r.elementCount);
+ } else {
+ blockSize = qCalculateBlockSize(alloc, sizeof(QChar), sizeof(Data));
}
if (d->ref.isShared() || IS_RAW_DATA(d)) {
@@ -1777,7 +1780,7 @@ void QString::reallocData(uint alloc, bool grow)
Data::deallocate(d);
d = x;
} else {
- Data *p = static_cast<Data *>(::realloc(d, sizeof(Data) + alloc * sizeof(QChar)));
+ Data *p = static_cast<Data *>(::realloc(d, blockSize));
Q_CHECK_PTR(p);
d = p;
d->alloc = alloc;
diff --git a/src/corelib/tools/qtools_p.h b/src/corelib/tools/qtools_p.h
index 5ec153c818..09adee5586 100644
--- a/src/corelib/tools/qtools_p.h
+++ b/src/corelib/tools/qtools_p.h
@@ -52,7 +52,7 @@
//
#include "QtCore/qglobal.h"
-#include <limits>
+#include <limits.h>
QT_BEGIN_NAMESPACE
@@ -88,11 +88,19 @@ Q_DECL_CONSTEXPR inline int fromOct(uint c) Q_DECL_NOTHROW
// We typically need an extra bit for qNextPowerOfTwo when determining the next allocation size.
enum {
- MaxAllocSize = (1 << (std::numeric_limits<int>::digits - 1)) - 1
+ MaxAllocSize = INT_MAX
+};
+
+struct CalculateGrowingBlockSizeResult {
+ size_t size;
+ size_t elementCount;
};
// implemented in qbytearray.cpp
-int Q_CORE_EXPORT qAllocMore(int alloc, int extra) Q_DECL_NOTHROW;
+size_t Q_CORE_EXPORT Q_DECL_CONST_FUNCTION
+qCalculateBlockSize(size_t elementCount, size_t elementSize, size_t headerSize = 0) Q_DECL_NOTHROW;
+CalculateGrowingBlockSizeResult Q_CORE_EXPORT Q_DECL_CONST_FUNCTION
+qCalculateGrowingBlockSize(size_t elementCount, size_t elementSize, size_t headerSize = 0) Q_DECL_NOTHROW ;
QT_END_NAMESPACE
diff --git a/src/gui/text/qfragmentmap_p.h b/src/gui/text/qfragmentmap_p.h
index 4cf17aadc7..b54d7261d0 100644
--- a/src/gui/text/qfragmentmap_p.h
+++ b/src/gui/text/qfragmentmap_p.h
@@ -255,14 +255,11 @@ uint QFragmentMapData<Fragment>::createFragment()
uint freePos = head->freelist;
if (freePos == head->allocated) {
// need to create some free space
- if (freePos >= uint(MaxAllocSize) / fragmentSize)
- qBadAlloc();
- uint needed = qAllocMore((freePos+1)*fragmentSize, 0);
- Q_ASSERT(needed/fragmentSize > head->allocated);
- Fragment *newFragments = (Fragment *)realloc(fragments, needed);
+ auto blockInfo = qCalculateGrowingBlockSize(freePos + 1, fragmentSize);
+ Fragment *newFragments = (Fragment *)realloc(fragments, blockInfo.size);
Q_CHECK_PTR(newFragments);
fragments = newFragments;
- head->allocated = needed/fragmentSize;
+ head->allocated = quint32(blockInfo.elementCount);
F(freePos).right = 0;
}
diff --git a/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp b/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp
index 910d7abf51..a460afcfa2 100644
--- a/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp
+++ b/tests/auto/corelib/tools/qbytearray/tst_qbytearray.cpp
@@ -107,7 +107,7 @@ private slots:
void number();
void toInt_data();
void toInt();
- void qAllocMore();
+ void blockSizeCalculations();
void resizeAfterFromRawData();
void appendAfterFromRawData();
@@ -1346,28 +1346,80 @@ void tst_QByteArray::toULongLong()
QCOMPARE(b, ok);
}
-// global function defined in qbytearray.cpp
-void tst_QByteArray::qAllocMore()
+static bool checkSize(size_t value, uint min)
{
- using QT_PREPEND_NAMESPACE(qAllocMore);
+ return value >= min && value <= INT_MAX;
+}
+// global functions defined in qbytearray.cpp
+void tst_QByteArray::blockSizeCalculations()
+{
// Not very important, but please behave :-)
- QVERIFY(qAllocMore(0, 0) >= 0);
-
- for (int i = 1; i < 1 << 8; i <<= 1)
- QVERIFY(qAllocMore(i, 0) >= i);
-
- for (int i = 1 << 8; i < 1 << 30; i <<= 1) {
- const int alloc = qAllocMore(i, 0);
+ QCOMPARE(qCalculateBlockSize(0, 1), size_t(0));
+ QVERIFY(qCalculateGrowingBlockSize(0, 1).size <= MaxAllocSize);
+ QVERIFY(qCalculateGrowingBlockSize(0, 1).elementCount <= MaxAllocSize);
+
+ // boundary condition
+ QCOMPARE(qCalculateBlockSize(MaxAllocSize, 1), size_t(MaxAllocSize));
+ QCOMPARE(qCalculateBlockSize(MaxAllocSize/2, 2), size_t(MaxAllocSize) - 1);
+ QCOMPARE(qCalculateBlockSize(MaxAllocSize/2, 2, 1), size_t(MaxAllocSize));
+ QCOMPARE(qCalculateGrowingBlockSize(MaxAllocSize, 1).size, size_t(MaxAllocSize));
+ QCOMPARE(qCalculateGrowingBlockSize(MaxAllocSize, 1).elementCount, size_t(MaxAllocSize));
+ QCOMPARE(qCalculateGrowingBlockSize(MaxAllocSize/2, 2, 1).size, size_t(MaxAllocSize));
+ QCOMPARE(qCalculateGrowingBlockSize(MaxAllocSize/2, 2, 1).elementCount, size_t(MaxAllocSize)/2);
+
+ // error conditions
+ QCOMPARE(qCalculateBlockSize(uint(MaxAllocSize) + 1, 1), size_t(~0));
+ QCOMPARE(qCalculateBlockSize(size_t(-1), 1), size_t(~0));
+ QCOMPARE(qCalculateBlockSize(MaxAllocSize, 1, 1), size_t(~0));
+ QCOMPARE(qCalculateBlockSize(MaxAllocSize/2 + 1, 2), size_t(~0));
+ QCOMPARE(qCalculateGrowingBlockSize(uint(MaxAllocSize) + 1, 1).size, size_t(~0));
+ QCOMPARE(qCalculateGrowingBlockSize(MaxAllocSize/2 + 1, 2).size, size_t(~0));
+
+ // overflow conditions
+ // on 32-bit platforms, (1 << 16) * (1 << 16) = (1 << 32) which is zero
+ QCOMPARE(qCalculateBlockSize(1 << 16, 1 << 16), size_t(~0));
+ QCOMPARE(qCalculateBlockSize(MaxAllocSize/4, 16), size_t(~0));
+ // on 32-bit platforms, (1 << 30) * 3 + (1 << 30) would overflow to zero
+ QCOMPARE(qCalculateBlockSize(1U << 30, 3, 1U << 30), size_t(~0));
+
+ // exact block sizes
+ for (int i = 1; i < 1 << 31; i <<= 1) {
+ QCOMPARE(qCalculateBlockSize(0, 1, i), size_t(i));
+ QCOMPARE(qCalculateBlockSize(i, 1), size_t(i));
+ QCOMPARE(qCalculateBlockSize(i + i/2, 1), size_t(i + i/2));
+ }
+ for (int i = 1; i < 1 << 30; i <<= 1) {
+ QCOMPARE(qCalculateBlockSize(i, 2), 2 * size_t(i));
+ QCOMPARE(qCalculateBlockSize(i, 2, 1), 2 * size_t(i) + 1);
+ QCOMPARE(qCalculateBlockSize(i, 2, 16), 2 * size_t(i) + 16);
+ }
- QVERIFY(alloc >= i);
- QCOMPARE(qAllocMore(i - 8, 8), alloc - 8);
- QCOMPARE(qAllocMore(i - 16, 16), alloc - 16);
- QCOMPARE(qAllocMore(i - 24, 24), alloc - 24);
- QCOMPARE(qAllocMore(i - 32, 32), alloc - 32);
+ // growing sizes
+ for (int i = 1; i < 1 << 31; i <<= 1) {
+ QVERIFY(checkSize(qCalculateGrowingBlockSize(i, 1).size, i));
+ QVERIFY(checkSize(qCalculateGrowingBlockSize(i, 1).elementCount, i));
+ QVERIFY(checkSize(qCalculateGrowingBlockSize(i, 1, 16).size, i));
+ QVERIFY(checkSize(qCalculateGrowingBlockSize(i, 1, 16).elementCount, i));
+ QVERIFY(checkSize(qCalculateGrowingBlockSize(i, 1, 24).size, i));
+ QVERIFY(checkSize(qCalculateGrowingBlockSize(i, 1, 16).elementCount, i));
+ }
- QVERIFY(qAllocMore(i - 1, 0) >= i - 1);
- QVERIFY(qAllocMore(i + 1, 0) >= i + 1);
+ // growth should be limited
+ for (int elementSize = 1; elementSize < (1<<8); elementSize <<= 1) {
+ size_t alloc = 1;
+ forever {
+ QVERIFY(checkSize(qCalculateGrowingBlockSize(alloc, elementSize).size, alloc * elementSize));
+ size_t newAlloc = qCalculateGrowingBlockSize(alloc, elementSize).elementCount;
+ QVERIFY(checkSize(newAlloc, alloc));
+ if (newAlloc == alloc)
+ break; // no growth, we're at limit
+ alloc = newAlloc;
+ }
+ QVERIFY(checkSize(alloc, size_t(MaxAllocSize) / elementSize));
+
+ // the next allocation should be invalid
+ QCOMPARE(qCalculateGrowingBlockSize(alloc + 1, elementSize).size, size_t(~0));
}
}
diff --git a/tests/benchmarks/corelib/tools/qvector/outofline.cpp b/tests/benchmarks/corelib/tools/qvector/outofline.cpp
index efd3df2308..76a4edaa10 100644
--- a/tests/benchmarks/corelib/tools/qvector/outofline.cpp
+++ b/tests/benchmarks/corelib/tools/qvector/outofline.cpp
@@ -97,5 +97,5 @@ void QVectorData::free(QVectorData *x, int alignment)
int QVectorData::grow(int sizeOfHeader, int size, int sizeOfT)
{
- return qAllocMore(size * sizeOfT, sizeOfHeader) / sizeOfT;
+ return qCalculateGrowingBlockSize(size, sizeOfT, sizeOfHeader).elementCount;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-08 01:59:31 +0000