diff options
Diffstat (limited to 'src/corelib/tools/qarraydata.cpp')
| -rw-r--r-- | src/corelib/tools/qarraydata.cpp | 298 |
1 files changed, 140 insertions, 158 deletions
diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp index b72ca20131..6aebd4306a 100644 --- a/src/corelib/tools/qarraydata.cpp +++ b/src/corelib/tools/qarraydata.cpp @@ -1,48 +1,15 @@ -/**************************************************************************** -** -** Copyright (C) 2019 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. -** -** $QT_BEGIN_LICENSE:LGPL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 3 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL3 included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 3 requirements -** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 2.0 or (at your option) the GNU General -** Public license version 3 or any later version approved by the KDE Free -** Qt Foundation. The licenses are as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -** included in the packaging of this file. Please review the following -** information to ensure the GNU General Public License requirements will -** be met: https://www.gnu.org/licenses/gpl-2.0.html and -** https://www.gnu.org/licenses/gpl-3.0.html. -** -** $QT_END_LICENSE$ -** -****************************************************************************/ +// Copyright (C) 2021 The Qt Company Ltd. +// Copyright (C) 2016 Intel Corporation. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only #include <QtCore/qarraydata.h> #include <QtCore/private/qnumeric_p.h> #include <QtCore/private/qtools_p.h> #include <QtCore/qmath.h> +#include <QtCore/qbytearray.h> // QBA::value_type +#include <QtCore/qstring.h> // QString::value_type + #include <stdlib.h> QT_BEGIN_NAMESPACE @@ -52,7 +19,7 @@ QT_BEGIN_NAMESPACE * 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 + * They take qsizetype parameters and return qsizetype 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 @@ -79,29 +46,21 @@ QT_BEGIN_NAMESPACE 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. + This function returns -1 on overflow or if the memory block size + would not fit a qsizetype. */ -size_t qCalculateBlockSize(size_t elementCount, size_t elementSize, size_t headerSize) noexcept +qsizetype qCalculateBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype headerSize) noexcept { - 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(); + size_t bytes; + if (Q_UNLIKELY(qMulOverflow(size_t(elementSize), size_t(elementCount), &bytes)) || + Q_UNLIKELY(qAddOverflow(bytes, size_t(headerSize), &bytes))) + return -1; + if (Q_UNLIKELY(qsizetype(bytes) < 0)) + return -1; - return bytes; + return qsizetype(bytes); } /*! @@ -116,168 +75,191 @@ size_t qCalculateBlockSize(size_t elementCount, size_t elementSize, size_t heade 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. + This function returns -1 on overflow or if the memory block size + would not fit a qsizetype. \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) noexcept +qCalculateGrowingBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype headerSize) noexcept { CalculateGrowingBlockSizeResult result = { - std::numeric_limits<size_t>::max(),std::numeric_limits<size_t>::max() + qsizetype(-1), qsizetype(-1) }; - unsigned bytes = unsigned(qCalculateBlockSize(elementCount, elementSize, headerSize)); - if (int(bytes) < 0) // catches std::numeric_limits<size_t>::max() + qsizetype bytes = qCalculateBlockSize(elementCount, elementSize, headerSize); + if (bytes < 0) return result; - unsigned morebytes = qNextPowerOfTwo(bytes); - if (Q_UNLIKELY(int(morebytes) < 0)) { - // catches morebytes == 2GB + size_t morebytes = static_cast<size_t>(qNextPowerOfTwo(quint64(bytes))); + if (Q_UNLIKELY(qsizetype(morebytes) < 0)) { // grow by half the difference between bytes and morebytes + // this slows the growth and avoids trying to allocate exactly + // 2G of memory (on 32bit), something that many OSes can't deliver bytes += (morebytes - bytes) / 2; } else { - bytes = morebytes; + bytes = qsizetype(morebytes); } - result.elementCount = (bytes - unsigned(headerSize)) / unsigned(elementSize); + result.elementCount = (bytes - headerSize) / elementSize; result.size = result.elementCount * elementSize + headerSize; return result; } -// End of qtools_p.h implementation - -QT_WARNING_PUSH -QT_WARNING_DISABLE_GCC("-Wmissing-field-initializers") - -const QArrayData QArrayData::shared_null[2] = { - { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }, // shared null - /* zero initialized terminator */}; - -static const QArrayData emptyNotNullShared[2] = { - { Q_BASIC_ATOMIC_INITIALIZER(-1), QArrayData::StaticDataFlags, 0 }, // shared empty - /* zero initialized terminator */}; - -QT_WARNING_POP - -static const QArrayData &qt_array_empty = emptyNotNullShared[0]; +/* + Calculate the byte size for a block of \a capacity objects of size \a + objectSize, with a header of size \a headerSize. If the \a option is + QArrayData::Grow, the capacity itself adjusted up, preallocating room for + more elements to be added later; otherwise, it is an exact calculation. -static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, size_t headerSize, - uint options) + Returns a structure containing the size in bytes and elements available. +*/ +static inline CalculateGrowingBlockSizeResult +calculateBlockSize(qsizetype capacity, qsizetype objectSize, qsizetype headerSize, QArrayData::AllocationOption option) { - // Calculate the byte size + // Adjust the header size up to account for the trailing null for QString + // and QByteArray. This is not checked for overflow because headers sizes + // should not be anywhere near the overflow limit. + constexpr qsizetype FooterSize = qMax(sizeof(QString::value_type), sizeof(QByteArray::value_type)); + if (objectSize <= FooterSize) + headerSize += FooterSize; + // allocSize = objectSize * capacity + headerSize, but checked for overflow // plus padded to grow in size - if (options & QArrayData::GrowsForward) { - auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize); - capacity = r.elementCount; - return r.size; + if (option == QArrayData::Grow) { + return qCalculateGrowingBlockSize(capacity, objectSize, headerSize); } else { - return qCalculateBlockSize(capacity, objectSize, headerSize); + return { qCalculateBlockSize(capacity, objectSize, headerSize), capacity }; } } -static QArrayData *allocateData(size_t allocSize, uint options) +static QArrayData *allocateData(qsizetype allocSize) { - QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize)); + QArrayData *header = static_cast<QArrayData *>(::malloc(size_t(allocSize))); if (header) { header->ref_.storeRelaxed(1); - header->flags = options; + header->flags = {}; header->alloc = 0; } return header; } -static QArrayData *reallocateData(QArrayData *header, size_t allocSize, uint options) -{ - header = static_cast<QArrayData *>(::realloc(header, allocSize)); - if (header) - header->flags = options; - return header; +namespace { +struct AllocationResult { + void *data; + QArrayData *header; +}; } +using QtPrivate::AlignedQArrayData; -void *QArrayData::allocate(QArrayData **dptr, size_t objectSize, size_t alignment, - size_t capacity, ArrayOptions options) noexcept +static inline AllocationResult +allocateHelper(qsizetype objectSize, qsizetype alignment, qsizetype capacity, + QArrayData::AllocationOption option) noexcept { - Q_ASSERT(dptr); - // Alignment is a power of two - Q_ASSERT(alignment >= alignof(QArrayData) - && !(alignment & (alignment - 1))); - - if (capacity == 0) { - // optimization for empty headers - *dptr = const_cast<QArrayData *>(&qt_array_empty); - return sharedNullData(); - } - - size_t headerSize = sizeof(QArrayData); - - if (alignment > alignof(QArrayData)) { - // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we - // can properly align the data array. This assumes malloc is able to - // provide appropriate alignment for the header -- as it should! - headerSize += alignment - alignof(QArrayData); + if (capacity == 0) + return {}; + + qsizetype headerSize = sizeof(AlignedQArrayData); + const qsizetype headerAlignment = alignof(AlignedQArrayData); + + if (alignment > headerAlignment) { + // Allocate extra (alignment - Q_ALIGNOF(AlignedQArrayData)) padding + // bytes so we can properly align the data array. This assumes malloc is + // able to provide appropriate alignment for the header -- as it should! + // Effectively, we allocate one QTypedArrayData<T>::AlignmentDummy. + headerSize += alignment - headerAlignment; } + Q_ASSERT(headerSize > 0); - if (headerSize > size_t(MaxAllocSize)) - return nullptr; + auto blockSize = calculateBlockSize(capacity, objectSize, headerSize, option); + capacity = blockSize.elementCount; + qsizetype allocSize = blockSize.size; + if (Q_UNLIKELY(allocSize < 0)) // handle overflow. cannot allocate reliably + return {}; - size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options); - options |= AllocatedDataType | MutableData; - options &= ~ImmutableHeader; - QArrayData *header = allocateData(allocSize, options); - quintptr data = 0; + QArrayData *header = allocateData(allocSize); + void *data = nullptr; if (header) { // find where offset should point to so that data() is aligned to alignment bytes - data = (quintptr(header) + sizeof(QArrayData) + alignment - 1) - & ~(alignment - 1); - header->alloc = uint(capacity); + data = QTypedArrayData<void>::dataStart(header, alignment); + header->alloc = qsizetype(capacity); } - *dptr = header; - return reinterpret_cast<void *>(data); + return { data, header }; } -QArrayData *QArrayData::prepareRawData(ArrayOptions options) Q_DECL_NOTHROW +// Generic size and alignment allocation function +void *QArrayData::allocate(QArrayData **dptr, qsizetype objectSize, qsizetype alignment, + qsizetype capacity, AllocationOption option) noexcept { - QArrayData *header = allocateData(sizeof(QArrayData), (options & ~DataTypeBits) | RawDataType); - if (header) - header->alloc = 0; - return header; + Q_ASSERT(dptr); + // Alignment is a power of two + Q_ASSERT(alignment >= qsizetype(alignof(QArrayData)) + && !(alignment & (alignment - 1))); + + auto r = allocateHelper(objectSize, alignment, capacity, option); + *dptr = r.header; + return r.data; +} + +// Fixed size and alignment allocation functions +void *QArrayData::allocate1(QArrayData **dptr, qsizetype capacity, AllocationOption option) noexcept +{ + Q_ASSERT(dptr); + + auto r = allocateHelper(1, alignof(AlignedQArrayData), capacity, option); + *dptr = r.header; + return r.data; } -QPair<QArrayData *, void *> +void *QArrayData::allocate2(QArrayData **dptr, qsizetype capacity, AllocationOption option) noexcept +{ + Q_ASSERT(dptr); + + auto r = allocateHelper(2, alignof(AlignedQArrayData), capacity, option); + *dptr = r.header; + return r.data; +} + +std::pair<QArrayData *, void *> QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer, - size_t objectSize, size_t capacity, ArrayOptions options) noexcept + qsizetype objectSize, qsizetype capacity, AllocationOption option) noexcept { - Q_ASSERT(data); - Q_ASSERT(data->isMutable()); - Q_ASSERT(!data->isShared()); - - size_t headerSize = sizeof(QArrayData); - size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options); - qptrdiff offset = reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data); - options |= AllocatedDataType | MutableData; - QArrayData *header = reallocateData(data, allocSize, options); + Q_ASSERT(!data || !data->isShared()); + + const qsizetype headerSize = sizeof(AlignedQArrayData); + auto r = calculateBlockSize(capacity, objectSize, headerSize, option); + qsizetype allocSize = r.size; + capacity = r.elementCount; + if (Q_UNLIKELY(allocSize < 0)) + return {}; + + const qptrdiff offset = dataPointer + ? reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data) + : headerSize; + Q_ASSERT(offset > 0); + Q_ASSERT(offset <= allocSize); // equals when all free space is at the beginning + + QArrayData *header = static_cast<QArrayData *>(::realloc(data, size_t(allocSize))); if (header) { - header->alloc = uint(capacity); + header->alloc = capacity; dataPointer = reinterpret_cast<char *>(header) + offset; + } else { + dataPointer = nullptr; } - return qMakePair(static_cast<QArrayData *>(header), dataPointer); + return {header, dataPointer}; } -void QArrayData::deallocate(QArrayData *data, size_t objectSize, - size_t alignment) noexcept +void QArrayData::deallocate(QArrayData *data, qsizetype objectSize, + qsizetype alignment) noexcept { // Alignment is a power of two - Q_ASSERT(alignment >= alignof(QArrayData) + Q_ASSERT(alignment >= qsizetype(alignof(QArrayData)) && !(alignment & (alignment - 1))); - Q_UNUSED(objectSize) Q_UNUSED(alignment) + Q_UNUSED(objectSize); + Q_UNUSED(alignment); - Q_ASSERT_X(data == nullptr || !data->isStatic(), "QArrayData::deallocate", - "Static data cannot be deleted"); ::free(data); } |