1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2019 The Qt Company Ltd. |
4 | ** Copyright (C) 2016 Intel Corporation. |
5 | ** Contact: https://www.qt.io/licensing/ |
6 | ** |
7 | ** This file is part of the QtCore module of the Qt Toolkit. |
8 | ** |
9 | ** $QT_BEGIN_LICENSE:LGPL$ |
10 | ** Commercial License Usage |
11 | ** Licensees holding valid commercial Qt licenses may use this file in |
12 | ** accordance with the commercial license agreement provided with the |
13 | ** Software or, alternatively, in accordance with the terms contained in |
14 | ** a written agreement between you and The Qt Company. For licensing terms |
15 | ** and conditions see https://www.qt.io/terms-conditions. For further |
16 | ** information use the contact form at https://www.qt.io/contact-us. |
17 | ** |
18 | ** GNU Lesser General Public License Usage |
19 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
20 | ** General Public License version 3 as published by the Free Software |
21 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
22 | ** packaging of this file. Please review the following information to |
23 | ** ensure the GNU Lesser General Public License version 3 requirements |
24 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
25 | ** |
26 | ** GNU General Public License Usage |
27 | ** Alternatively, this file may be used under the terms of the GNU |
28 | ** General Public License version 2.0 or (at your option) the GNU General |
29 | ** Public license version 3 or any later version approved by the KDE Free |
30 | ** Qt Foundation. The licenses are as published by the Free Software |
31 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
32 | ** included in the packaging of this file. Please review the following |
33 | ** information to ensure the GNU General Public License requirements will |
34 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
35 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
36 | ** |
37 | ** $QT_END_LICENSE$ |
38 | ** |
39 | ****************************************************************************/ |
40 | |
41 | #include <QtCore/qarraydata.h> |
42 | #include <QtCore/private/qnumeric_p.h> |
43 | #include <QtCore/private/qtools_p.h> |
44 | #include <QtCore/qmath.h> |
45 | |
46 | #include <stdlib.h> |
47 | |
48 | QT_BEGIN_NAMESPACE |
49 | |
50 | /* |
51 | * This pair of functions is declared in qtools_p.h and is used by the Qt |
52 | * containers to allocate memory and grow the memory block during append |
53 | * operations. |
54 | * |
55 | * They take size_t parameters and return size_t so they will change sizes |
56 | * according to the pointer width. However, knowing Qt containers store the |
57 | * container size and element indexes in ints, these functions never return a |
58 | * size larger than INT_MAX. This is done by casting the element count and |
59 | * memory block size to int in several comparisons: the check for negative is |
60 | * very fast on most platforms as the code only needs to check the sign bit. |
61 | * |
62 | * These functions return SIZE_MAX on overflow, which can be passed to malloc() |
63 | * and will surely cause a NULL return (there's no way you can allocate a |
64 | * memory block the size of your entire VM space). |
65 | */ |
66 | |
67 | /*! |
68 | \internal |
69 | \since 5.7 |
70 | |
71 | Returns the memory block size for a container containing \a elementCount |
72 | elements, each of \a elementSize bytes, plus a header of \a headerSize |
73 | bytes. That is, this function returns \c |
74 | {elementCount * elementSize + headerSize} |
75 | |
76 | but unlike the simple calculation, it checks for overflows during the |
77 | multiplication and the addition. |
78 | |
79 | Both \a elementCount and \a headerSize can be zero, but \a elementSize |
80 | cannot. |
81 | |
82 | This function returns SIZE_MAX (~0) on overflow or if the memory block size |
83 | would not fit an int. |
84 | */ |
85 | size_t qCalculateBlockSize(size_t elementCount, size_t elementSize, size_t ) noexcept |
86 | { |
87 | unsigned count = unsigned(elementCount); |
88 | unsigned size = unsigned(elementSize); |
89 | unsigned = unsigned(headerSize); |
90 | Q_ASSERT(elementSize); |
91 | Q_ASSERT(size == elementSize); |
92 | Q_ASSERT(header == headerSize); |
93 | |
94 | if (Q_UNLIKELY(count != elementCount)) |
95 | return std::numeric_limits<size_t>::max(); |
96 | |
97 | unsigned bytes; |
98 | if (Q_UNLIKELY(mul_overflow(size, count, &bytes)) || |
99 | Q_UNLIKELY(add_overflow(bytes, header, &bytes))) |
100 | return std::numeric_limits<size_t>::max(); |
101 | if (Q_UNLIKELY(int(bytes) < 0)) // catches bytes >= 2GB |
102 | return std::numeric_limits<size_t>::max(); |
103 | |
104 | return bytes; |
105 | } |
106 | |
107 | /*! |
108 | \internal |
109 | \since 5.7 |
110 | |
111 | Returns the memory block size and the number of elements that will fit in |
112 | that block for a container containing \a elementCount elements, each of \a |
113 | elementSize bytes, plus a header of \a headerSize bytes. This function |
114 | assumes the container will grow and pre-allocates a growth factor. |
115 | |
116 | Both \a elementCount and \a headerSize can be zero, but \a elementSize |
117 | cannot. |
118 | |
119 | This function returns SIZE_MAX (~0) on overflow or if the memory block size |
120 | would not fit an int. |
121 | |
122 | \note The memory block may contain up to \a elementSize - 1 bytes more than |
123 | needed. |
124 | */ |
125 | CalculateGrowingBlockSizeResult |
126 | qCalculateGrowingBlockSize(size_t elementCount, size_t elementSize, size_t ) noexcept |
127 | { |
128 | CalculateGrowingBlockSizeResult result = { |
129 | std::numeric_limits<size_t>::max(),std::numeric_limits<size_t>::max() |
130 | }; |
131 | |
132 | unsigned bytes = unsigned(qCalculateBlockSize(elementCount, elementSize, headerSize)); |
133 | if (int(bytes) < 0) // catches std::numeric_limits<size_t>::max() |
134 | return result; |
135 | |
136 | unsigned morebytes = qNextPowerOfTwo(bytes); |
137 | if (Q_UNLIKELY(int(morebytes) < 0)) { |
138 | // catches morebytes == 2GB |
139 | // grow by half the difference between bytes and morebytes |
140 | bytes += (morebytes - bytes) / 2; |
141 | } else { |
142 | bytes = morebytes; |
143 | } |
144 | |
145 | result.elementCount = (bytes - unsigned(headerSize)) / unsigned(elementSize); |
146 | result.size = bytes; |
147 | return result; |
148 | } |
149 | |
150 | // End of qtools_p.h implementation |
151 | |
152 | QT_WARNING_PUSH |
153 | QT_WARNING_DISABLE_GCC("-Wmissing-field-initializers" ) |
154 | |
155 | const QArrayData QArrayData::shared_null[2] = { |
156 | { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared null |
157 | /* zero initialized terminator */}; |
158 | |
159 | static const QArrayData qt_array[3] = { |
160 | { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared empty |
161 | { { Q_BASIC_ATOMIC_INITIALIZER(0) }, 0, 0, 0, sizeof(QArrayData) }, // unsharable empty |
162 | /* zero initialized terminator */}; |
163 | |
164 | QT_WARNING_POP |
165 | |
166 | static const QArrayData &qt_array_empty = qt_array[0]; |
167 | static const QArrayData &qt_array_unsharable_empty = qt_array[1]; |
168 | |
169 | static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, size_t , |
170 | uint options) |
171 | { |
172 | // Calculate the byte size |
173 | // allocSize = objectSize * capacity + headerSize, but checked for overflow |
174 | // plus padded to grow in size |
175 | if (options & QArrayData::Grow) { |
176 | auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize); |
177 | capacity = r.elementCount; |
178 | return r.size; |
179 | } else { |
180 | return qCalculateBlockSize(capacity, objectSize, headerSize); |
181 | } |
182 | } |
183 | |
184 | static QArrayData *reallocateData(QArrayData *, size_t allocSize, uint options) |
185 | { |
186 | header = static_cast<QArrayData *>(::realloc(header, allocSize)); |
187 | if (header) |
188 | header->capacityReserved = bool(options & QArrayData::CapacityReserved); |
189 | return header; |
190 | } |
191 | |
192 | QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment, |
193 | size_t capacity, AllocationOptions options) noexcept |
194 | { |
195 | // Alignment is a power of two |
196 | Q_ASSERT(alignment >= Q_ALIGNOF(QArrayData) |
197 | && !(alignment & (alignment - 1))); |
198 | |
199 | // Don't allocate empty headers |
200 | if (!(options & RawData) && !capacity) { |
201 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
202 | if (options & Unsharable) |
203 | return const_cast<QArrayData *>(&qt_array_unsharable_empty); |
204 | #endif |
205 | return const_cast<QArrayData *>(&qt_array_empty); |
206 | } |
207 | |
208 | size_t = sizeof(QArrayData); |
209 | |
210 | // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we |
211 | // can properly align the data array. This assumes malloc is able to |
212 | // provide appropriate alignment for the header -- as it should! |
213 | // Padding is skipped when allocating a header for RawData. |
214 | if (!(options & RawData)) |
215 | headerSize += (alignment - Q_ALIGNOF(QArrayData)); |
216 | |
217 | if (headerSize > size_t(MaxAllocSize)) |
218 | return nullptr; |
219 | |
220 | size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options); |
221 | QArrayData * = static_cast<QArrayData *>(::malloc(allocSize)); |
222 | if (header) { |
223 | quintptr data = (quintptr(header) + sizeof(QArrayData) + alignment - 1) |
224 | & ~(alignment - 1); |
225 | |
226 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
227 | header->ref.atomic.storeRelaxed(bool(!(options & Unsharable))); |
228 | #else |
229 | header->ref.atomic.storeRelaxed(1); |
230 | #endif |
231 | header->size = 0; |
232 | header->alloc = capacity; |
233 | header->capacityReserved = bool(options & CapacityReserved); |
234 | header->offset = data - quintptr(header); |
235 | } |
236 | |
237 | return header; |
238 | } |
239 | |
240 | QArrayData *QArrayData::reallocateUnaligned(QArrayData *data, size_t objectSize, size_t capacity, |
241 | AllocationOptions options) noexcept |
242 | { |
243 | Q_ASSERT(data); |
244 | Q_ASSERT(data->isMutable()); |
245 | Q_ASSERT(!data->ref.isShared()); |
246 | |
247 | size_t = sizeof(QArrayData); |
248 | size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options); |
249 | QArrayData * = static_cast<QArrayData *>(reallocateData(data, allocSize, options)); |
250 | if (header) |
251 | header->alloc = capacity; |
252 | return header; |
253 | } |
254 | |
255 | void QArrayData::deallocate(QArrayData *data, size_t objectSize, |
256 | size_t alignment) noexcept |
257 | { |
258 | // Alignment is a power of two |
259 | Q_ASSERT(alignment >= Q_ALIGNOF(QArrayData) |
260 | && !(alignment & (alignment - 1))); |
261 | Q_UNUSED(objectSize) Q_UNUSED(alignment) |
262 | |
263 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
264 | if (data == &qt_array_unsharable_empty) |
265 | return; |
266 | #endif |
267 | |
268 | Q_ASSERT_X(data == 0 || !data->ref.isStatic(), "QArrayData::deallocate" , |
269 | "Static data cannot be deleted" ); |
270 | ::free(data); |
271 | } |
272 | |
273 | namespace QtPrivate { |
274 | /*! |
275 | \internal |
276 | */ |
277 | QContainerImplHelper::CutResult QContainerImplHelper::mid(int originalLength, int *_position, int *_length) |
278 | { |
279 | int &position = *_position; |
280 | int &length = *_length; |
281 | if (position > originalLength) |
282 | return Null; |
283 | |
284 | if (position < 0) { |
285 | if (length < 0 || length + position >= originalLength) |
286 | return Full; |
287 | if (length + position <= 0) |
288 | return Null; |
289 | length += position; |
290 | position = 0; |
291 | } else if (uint(length) > uint(originalLength - position)) { |
292 | length = originalLength - position; |
293 | } |
294 | |
295 | if (position == 0 && length == originalLength) |
296 | return Full; |
297 | |
298 | return length > 0 ? Subset : Empty; |
299 | } |
300 | } |
301 | |
302 | QT_END_NAMESPACE |
303 | |