diff options
Diffstat (limited to 'src/corelib/tools/qarraydata.cpp')
| -rw-r--r-- | src/corelib/tools/qarraydata.cpp | 324 |
1 files changed, 152 insertions, 172 deletions
diff --git a/src/corelib/tools/qarraydata.cpp b/src/corelib/tools/qarraydata.cpp index ed7dfe2e41..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,171 +75,192 @@ 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_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared null - /* zero initialized terminator */}; - -static const QArrayData qt_array[3] = { - { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared empty - { { Q_BASIC_ATOMIC_INITIALIZER(0) }, 0, 0, 0, sizeof(QArrayData) }, // unsharable empty - /* zero initialized terminator */}; - -QT_WARNING_POP +/* + 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 const QArrayData &qt_array_empty = qt_array[0]; -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::Grow) { - 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 *reallocateData(QArrayData *header, size_t allocSize, uint options) +static QArrayData *allocateData(qsizetype allocSize) { - header = static_cast<QArrayData *>(::realloc(header, allocSize)); - if (header) - header->capacityReserved = bool(options & QArrayData::CapacityReserved); + QArrayData *header = static_cast<QArrayData *>(::malloc(size_t(allocSize))); + if (header) { + header->ref_.storeRelaxed(1); + header->flags = {}; + header->alloc = 0; + } return header; } -QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment, - size_t capacity, AllocationOptions options) noexcept -{ - // Alignment is a power of two - Q_ASSERT(alignment >= alignof(QArrayData) - && !(alignment & (alignment - 1))); - - // Don't allocate empty headers - if (!(options & RawData) && !capacity) - return const_cast<QArrayData *>(&qt_array_empty); - - size_t headerSize = sizeof(QArrayData); +namespace { +struct AllocationResult { + void *data; + QArrayData *header; +}; +} +using QtPrivate::AlignedQArrayData; - // Allocate extra (alignment - 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! - // Padding is skipped when allocating a header for RawData. - if (!(options & RawData)) - headerSize += (alignment - alignof(QArrayData)); +static inline AllocationResult +allocateHelper(qsizetype objectSize, qsizetype alignment, qsizetype capacity, + QArrayData::AllocationOption option) noexcept +{ + 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); - QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize)); + QArrayData *header = allocateData(allocSize); + void *data = nullptr; if (header) { - quintptr data = (quintptr(header) + sizeof(QArrayData) + alignment - 1) - & ~(alignment - 1); - - header->ref.atomic.storeRelaxed(1); - header->size = 0; - header->alloc = capacity; - header->capacityReserved = bool(options & CapacityReserved); - header->offset = data - quintptr(header); + // find where offset should point to so that data() is aligned to alignment bytes + data = QTypedArrayData<void>::dataStart(header, alignment); + header->alloc = qsizetype(capacity); } - return header; + return { data, header }; } -QArrayData *QArrayData::reallocateUnaligned(QArrayData *data, size_t objectSize, size_t capacity, - AllocationOptions options) noexcept +// Generic size and alignment allocation function +void *QArrayData::allocate(QArrayData **dptr, qsizetype objectSize, qsizetype alignment, + qsizetype capacity, AllocationOption option) noexcept { - Q_ASSERT(data); - Q_ASSERT(data->isMutable()); - Q_ASSERT(!data->ref.isShared()); - - size_t headerSize = sizeof(QArrayData); - size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options); - QArrayData *header = static_cast<QArrayData *>(reallocateData(data, allocSize, options)); - if (header) - header->alloc = capacity; - 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; } -void QArrayData::deallocate(QArrayData *data, size_t objectSize, - size_t alignment) noexcept +// Fixed size and alignment allocation functions +void *QArrayData::allocate1(QArrayData **dptr, qsizetype capacity, AllocationOption option) noexcept { - // Alignment is a power of two - Q_ASSERT(alignment >= alignof(QArrayData) - && !(alignment & (alignment - 1))); - Q_UNUSED(objectSize) Q_UNUSED(alignment) + Q_ASSERT(dptr); - Q_ASSERT_X(data == 0 || !data->ref.isStatic(), "QArrayData::deallocate", - "Static data cannot be deleted"); - ::free(data); + auto r = allocateHelper(1, alignof(AlignedQArrayData), capacity, option); + *dptr = r.header; + return r.data; } -namespace QtPrivate { -/*! - \internal -*/ -QContainerImplHelper::CutResult QContainerImplHelper::mid(int originalLength, int *_position, int *_length) +void *QArrayData::allocate2(QArrayData **dptr, qsizetype capacity, AllocationOption option) noexcept { - int &position = *_position; - int &length = *_length; - if (position > originalLength) - return Null; - - if (position < 0) { - if (length < 0 || length + position >= originalLength) - return Full; - if (length + position <= 0) - return Null; - length += position; - position = 0; - } else if (uint(length) > uint(originalLength - position)) { - length = originalLength - position; - } + Q_ASSERT(dptr); - if (position == 0 && length == originalLength) - return Full; + auto r = allocateHelper(2, alignof(AlignedQArrayData), capacity, option); + *dptr = r.header; + return r.data; +} - return length > 0 ? Subset : Empty; +std::pair<QArrayData *, void *> +QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer, + qsizetype objectSize, qsizetype capacity, AllocationOption option) noexcept +{ + 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 = capacity; + dataPointer = reinterpret_cast<char *>(header) + offset; + } else { + dataPointer = nullptr; + } + return {header, dataPointer}; } + +void QArrayData::deallocate(QArrayData *data, qsizetype objectSize, + qsizetype alignment) noexcept +{ + // Alignment is a power of two + Q_ASSERT(alignment >= qsizetype(alignof(QArrayData)) + && !(alignment & (alignment - 1))); + Q_UNUSED(objectSize); + Q_UNUSED(alignment); + + ::free(data); } QT_END_NAMESPACE |