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

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