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 | |
15 | QT_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 | */ |
52 | qsizetype qCalculateBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype ) 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 | */ |
84 | CalculateGrowingBlockSizeResult |
85 | qCalculateGrowingBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype ) 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 | */ |
118 | static inline CalculateGrowingBlockSizeResult |
119 | calculateBlockSize(qsizetype capacity, qsizetype objectSize, qsizetype , 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 = 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 | |
137 | static QArrayData *allocateData(qsizetype allocSize) |
138 | { |
139 | QArrayData * = 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 | namespace { |
149 | struct AllocationResult { |
150 | void *data; |
151 | QArrayData *; |
152 | }; |
153 | } |
154 | using QtPrivate::AlignedQArrayData; |
155 | |
156 | static inline AllocationResult |
157 | allocateHelper(qsizetype objectSize, qsizetype alignment, qsizetype capacity, |
158 | QArrayData::AllocationOption option) noexcept |
159 | { |
160 | if (capacity == 0) |
161 | return {}; |
162 | |
163 | qsizetype = sizeof(AlignedQArrayData); |
164 | const qsizetype = alignof(AlignedQArrayData); |
165 | |
166 | if (alignment > headerAlignment) { |
167 | // Allocate extra (alignment - Q_ALIGNOF(AlignedQArrayData)) padding |
168 | // bytes so we can properly align the data array. This assumes malloc is |
169 | // able to provide appropriate alignment for the header -- as it should! |
170 | // Effectively, we allocate one QTypedArrayData<T>::AlignmentDummy. |
171 | headerSize += alignment - headerAlignment; |
172 | } |
173 | Q_ASSERT(headerSize > 0); |
174 | |
175 | auto blockSize = calculateBlockSize(capacity, objectSize, headerSize, option); |
176 | capacity = blockSize.elementCount; |
177 | qsizetype allocSize = blockSize.size; |
178 | if (Q_UNLIKELY(allocSize < 0)) // handle overflow. cannot allocate reliably |
179 | return {}; |
180 | |
181 | QArrayData * = allocateData(allocSize); |
182 | void *data = nullptr; |
183 | if (header) { |
184 | // find where offset should point to so that data() is aligned to alignment bytes |
185 | data = QTypedArrayData<void>::dataStart(data: header, alignment); |
186 | header->alloc = qsizetype(capacity); |
187 | } |
188 | |
189 | return { .data: data, .header: header }; |
190 | } |
191 | |
192 | // Generic size and alignment allocation function |
193 | void *QArrayData::allocate(QArrayData **dptr, qsizetype objectSize, qsizetype alignment, |
194 | qsizetype capacity, AllocationOption option) noexcept |
195 | { |
196 | Q_ASSERT(dptr); |
197 | // Alignment is a power of two |
198 | Q_ASSERT(alignment >= qsizetype(alignof(QArrayData)) |
199 | && !(alignment & (alignment - 1))); |
200 | |
201 | auto r = allocateHelper(objectSize, alignment, capacity, option); |
202 | *dptr = r.header; |
203 | return r.data; |
204 | } |
205 | |
206 | // Fixed size and alignment allocation functions |
207 | void *QArrayData::allocate1(QArrayData **dptr, qsizetype capacity, AllocationOption option) noexcept |
208 | { |
209 | Q_ASSERT(dptr); |
210 | |
211 | auto r = allocateHelper(objectSize: 1, alignment: alignof(AlignedQArrayData), capacity, option); |
212 | *dptr = r.header; |
213 | return r.data; |
214 | } |
215 | |
216 | void *QArrayData::allocate2(QArrayData **dptr, qsizetype capacity, AllocationOption option) noexcept |
217 | { |
218 | Q_ASSERT(dptr); |
219 | |
220 | auto r = allocateHelper(objectSize: 2, alignment: alignof(AlignedQArrayData), capacity, option); |
221 | *dptr = r.header; |
222 | return r.data; |
223 | } |
224 | |
225 | std::pair<QArrayData *, void *> |
226 | QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer, |
227 | qsizetype objectSize, qsizetype capacity, AllocationOption option) noexcept |
228 | { |
229 | Q_ASSERT(!data || !data->isShared()); |
230 | |
231 | const qsizetype = sizeof(AlignedQArrayData); |
232 | auto r = calculateBlockSize(capacity, objectSize, headerSize, option); |
233 | qsizetype allocSize = r.size; |
234 | capacity = r.elementCount; |
235 | if (Q_UNLIKELY(allocSize < 0)) |
236 | return {}; |
237 | |
238 | const qptrdiff offset = dataPointer |
239 | ? reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data) |
240 | : headerSize; |
241 | Q_ASSERT(offset > 0); |
242 | Q_ASSERT(offset <= allocSize); // equals when all free space is at the beginning |
243 | |
244 | QArrayData * = static_cast<QArrayData *>(::realloc(ptr: data, size: size_t(allocSize))); |
245 | if (header) { |
246 | header->alloc = capacity; |
247 | dataPointer = reinterpret_cast<char *>(header) + offset; |
248 | } else { |
249 | dataPointer = nullptr; |
250 | } |
251 | return {header, dataPointer}; |
252 | } |
253 | |
254 | void QArrayData::deallocate(QArrayData *data, qsizetype objectSize, |
255 | qsizetype alignment) noexcept |
256 | { |
257 | // Alignment is a power of two |
258 | Q_ASSERT(alignment >= qsizetype(alignof(QArrayData)) |
259 | && !(alignment & (alignment - 1))); |
260 | Q_UNUSED(objectSize); |
261 | Q_UNUSED(alignment); |
262 | |
263 | ::free(ptr: data); |
264 | } |
265 | |
266 | QT_END_NAMESPACE |
267 | |