1// Copyright (C) 2021 The Qt Company Ltd.
2// Copyright (C) 2016 Intel Corporation.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#include <QtCore/qarraydata.h>
6#include <QtCore/private/qnumeric_p.h>
7#include <QtCore/private/qtools_p.h>
8#include <QtCore/qmath.h>
9
10#include <QtCore/qbytearray.h> // QBA::value_type
11#include <QtCore/qstring.h> // QString::value_type
12
13#include <stdlib.h>
14
15QT_BEGIN_NAMESPACE
16
17/*
18 * This pair of functions is declared in qtools_p.h and is used by the Qt
19 * containers to allocate memory and grow the memory block during append
20 * operations.
21 *
22 * They take qsizetype parameters and return qsizetype so they will change sizes
23 * according to the pointer width. However, knowing Qt containers store the
24 * container size and element indexes in ints, these functions never return a
25 * size larger than INT_MAX. This is done by casting the element count and
26 * memory block size to int in several comparisons: the check for negative is
27 * very fast on most platforms as the code only needs to check the sign bit.
28 *
29 * These functions return SIZE_MAX on overflow, which can be passed to malloc()
30 * and will surely cause a NULL return (there's no way you can allocate a
31 * memory block the size of your entire VM space).
32 */
33
34/*!
35 \internal
36 \since 5.7
37
38 Returns the memory block size for a container containing \a elementCount
39 elements, each of \a elementSize bytes, plus a header of \a headerSize
40 bytes. That is, this function returns \c
41 {elementCount * elementSize + headerSize}
42
43 but unlike the simple calculation, it checks for overflows during the
44 multiplication and the addition.
45
46 Both \a elementCount and \a headerSize can be zero, but \a elementSize
47 cannot.
48
49 This function returns -1 on overflow or if the memory block size
50 would not fit a qsizetype.
51*/
52qsizetype qCalculateBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype headerSize) noexcept
53{
54 Q_ASSERT(elementSize);
55
56 size_t bytes;
57 if (Q_UNLIKELY(qMulOverflow(size_t(elementSize), size_t(elementCount), &bytes)) ||
58 Q_UNLIKELY(qAddOverflow(bytes, size_t(headerSize), &bytes)))
59 return -1;
60 if (Q_UNLIKELY(qsizetype(bytes) < 0))
61 return -1;
62
63 return qsizetype(bytes);
64}
65
66/*!
67 \internal
68 \since 5.7
69
70 Returns the memory block size and the number of elements that will fit in
71 that block for a container containing \a elementCount elements, each of \a
72 elementSize bytes, plus a header of \a headerSize bytes. This function
73 assumes the container will grow and pre-allocates a growth factor.
74
75 Both \a elementCount and \a headerSize can be zero, but \a elementSize
76 cannot.
77
78 This function returns -1 on overflow or if the memory block size
79 would not fit a qsizetype.
80
81 \note The memory block may contain up to \a elementSize - 1 bytes more than
82 needed.
83*/
84CalculateGrowingBlockSizeResult
85qCalculateGrowingBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype headerSize) noexcept
86{
87 CalculateGrowingBlockSizeResult result = {
88 .size: qsizetype(-1), .elementCount: qsizetype(-1)
89 };
90
91 qsizetype bytes = qCalculateBlockSize(elementCount, elementSize, headerSize);
92 if (bytes < 0)
93 return result;
94
95 size_t morebytes = static_cast<size_t>(qNextPowerOfTwo(v: quint64(bytes)));
96 if (Q_UNLIKELY(qsizetype(morebytes) < 0)) {
97 // grow by half the difference between bytes and morebytes
98 // this slows the growth and avoids trying to allocate exactly
99 // 2G of memory (on 32bit), something that many OSes can't deliver
100 bytes += (morebytes - bytes) / 2;
101 } else {
102 bytes = qsizetype(morebytes);
103 }
104
105 result.elementCount = (bytes - headerSize) / elementSize;
106 result.size = result.elementCount * elementSize + headerSize;
107 return result;
108}
109
110/*
111 Calculate the byte size for a block of \a capacity objects of size \a
112 objectSize, with a header of size \a headerSize. If the \a option is
113 QArrayData::Grow, the capacity itself adjusted up, preallocating room for
114 more elements to be added later; otherwise, it is an exact calculation.
115
116 Returns a structure containing the size in bytes and elements available.
117*/
118static inline CalculateGrowingBlockSizeResult
119calculateBlockSize(qsizetype capacity, qsizetype objectSize, qsizetype headerSize, QArrayData::AllocationOption option)
120{
121 // Adjust the header size up to account for the trailing null for QString
122 // and QByteArray. This is not checked for overflow because headers sizes
123 // should not be anywhere near the overflow limit.
124 constexpr qsizetype FooterSize = qMax(a: sizeof(QString::value_type), b: sizeof(QByteArray::value_type));
125 if (objectSize <= FooterSize)
126 headerSize += FooterSize;
127
128 // allocSize = objectSize * capacity + headerSize, but checked for overflow
129 // plus padded to grow in size
130 if (option == QArrayData::Grow) {
131 return qCalculateGrowingBlockSize(elementCount: capacity, elementSize: objectSize, headerSize);
132 } else {
133 return { .size: qCalculateBlockSize(elementCount: capacity, elementSize: objectSize, headerSize), .elementCount: capacity };
134 }
135}
136
137static QArrayData *allocateData(qsizetype allocSize)
138{
139 QArrayData *header = static_cast<QArrayData *>(::malloc(size: size_t(allocSize)));
140 if (header) {
141 header->ref_.storeRelaxed(newValue: 1);
142 header->flags = {};
143 header->alloc = 0;
144 }
145 return header;
146}
147
148
149namespace {
150// QArrayData with strictest alignment requirements supported by malloc()
151struct alignas(std::max_align_t) AlignedQArrayData : QArrayData
152{
153};
154}
155
156
157void *QArrayData::allocate(QArrayData **dptr, qsizetype objectSize, qsizetype alignment,
158 qsizetype capacity, QArrayData::AllocationOption option) noexcept
159{
160 Q_ASSERT(dptr);
161 // Alignment is a power of two
162 Q_ASSERT(alignment >= qsizetype(alignof(QArrayData))
163 && !(alignment & (alignment - 1)));
164
165 if (capacity == 0) {
166 *dptr = nullptr;
167 return nullptr;
168 }
169
170 qsizetype headerSize = sizeof(AlignedQArrayData);
171 const qsizetype headerAlignment = alignof(AlignedQArrayData);
172
173 if (alignment > headerAlignment) {
174 // Allocate extra (alignment - Q_ALIGNOF(AlignedQArrayData)) padding
175 // bytes so we can properly align the data array. This assumes malloc is
176 // able to provide appropriate alignment for the header -- as it should!
177 headerSize += alignment - headerAlignment;
178 }
179 Q_ASSERT(headerSize > 0);
180
181 auto blockSize = calculateBlockSize(capacity, objectSize, headerSize, option);
182 capacity = blockSize.elementCount;
183 qsizetype allocSize = blockSize.size;
184 if (Q_UNLIKELY(allocSize < 0)) { // handle overflow. cannot allocate reliably
185 *dptr = nullptr;
186 return nullptr;
187 }
188
189 QArrayData *header = allocateData(allocSize);
190 void *data = nullptr;
191 if (header) {
192 // find where offset should point to so that data() is aligned to alignment bytes
193 data = QTypedArrayData<void>::dataStart(data: header, alignment);
194 header->alloc = qsizetype(capacity);
195 }
196
197 *dptr = header;
198 return data;
199}
200
201QPair<QArrayData *, void *>
202QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer,
203 qsizetype objectSize, qsizetype capacity, AllocationOption option) noexcept
204{
205 Q_ASSERT(!data || !data->isShared());
206
207 const qsizetype headerSize = sizeof(AlignedQArrayData);
208 auto r = calculateBlockSize(capacity, objectSize, headerSize, option);
209 qsizetype allocSize = r.size;
210 capacity = r.elementCount;
211 if (Q_UNLIKELY(allocSize < 0))
212 return qMakePair<QArrayData *, void *>(value1: nullptr, value2: nullptr);
213
214 const qptrdiff offset = dataPointer
215 ? reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data)
216 : headerSize;
217 Q_ASSERT(offset > 0);
218 Q_ASSERT(offset <= allocSize); // equals when all free space is at the beginning
219
220 QArrayData *header = static_cast<QArrayData *>(::realloc(ptr: data, size: size_t(allocSize)));
221 if (header) {
222 header->alloc = capacity;
223 dataPointer = reinterpret_cast<char *>(header) + offset;
224 } else {
225 dataPointer = nullptr;
226 }
227 return qMakePair(value1: static_cast<QArrayData *>(header), value2&: dataPointer);
228}
229
230void QArrayData::deallocate(QArrayData *data, qsizetype objectSize,
231 qsizetype alignment) noexcept
232{
233 // Alignment is a power of two
234 Q_ASSERT(alignment >= qsizetype(alignof(QArrayData))
235 && !(alignment & (alignment - 1)));
236 Q_UNUSED(objectSize);
237 Q_UNUSED(alignment);
238
239 ::free(ptr: data);
240}
241
242QT_END_NAMESPACE
243

source code of qtbase/src/corelib/tools/qarraydata.cpp