1 /****************************************************************************
2 **
3 ** Copyright (C) 2020 The Qt Company Ltd.
4 ** Copyright (C) 2020 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 */
qCalculateBlockSize(size_t elementCount,size_t elementSize,size_t headerSize)85 size_t qCalculateBlockSize(size_t elementCount, size_t elementSize, size_t headerSize) noexcept
86 {
87 unsigned count = unsigned(elementCount);
88 unsigned size = unsigned(elementSize);
89 unsigned header = 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
qCalculateGrowingBlockSize(size_t elementCount,size_t elementSize,size_t headerSize)126 qCalculateGrowingBlockSize(size_t elementCount, size_t elementSize, size_t headerSize) 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 = result.elementCount * elementSize + headerSize;
147 return result;
148 }
149
150 // End of qtools_p.h implementation
151
152 const QArrayData QArrayData::shared_null[2] = {
153 { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared null
154 { { Q_BASIC_ATOMIC_INITIALIZER(0) }, 0, 0, 0, 0 } /* zero initialized terminator */
155 };
156
157 static const QArrayData qt_array[3] = {
158 { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared empty
159 { { Q_BASIC_ATOMIC_INITIALIZER(0) }, 0, 0, 0, sizeof(QArrayData) }, // unsharable empty
160 { { Q_BASIC_ATOMIC_INITIALIZER(0) }, 0, 0, 0, 0 } /* zero initialized terminator */
161 };
162
163 static const QArrayData &qt_array_empty = qt_array[0];
164 static const QArrayData &qt_array_unsharable_empty = qt_array[1];
165
calculateBlockSize(size_t & capacity,size_t objectSize,size_t headerSize,uint options)166 static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, size_t headerSize,
167 uint options)
168 {
169 // Calculate the byte size
170 // allocSize = objectSize * capacity + headerSize, but checked for overflow
171 // plus padded to grow in size
172 if (options & QArrayData::Grow) {
173 auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize);
174 capacity = r.elementCount;
175 return r.size;
176 } else {
177 return qCalculateBlockSize(capacity, objectSize, headerSize);
178 }
179 }
180
reallocateData(QArrayData * header,size_t allocSize,uint options)181 static QArrayData *reallocateData(QArrayData *header, size_t allocSize, uint options)
182 {
183 header = static_cast<QArrayData *>(::realloc(header, allocSize));
184 if (header)
185 header->capacityReserved = bool(options & QArrayData::CapacityReserved);
186 return header;
187 }
188
allocate(size_t objectSize,size_t alignment,size_t capacity,AllocationOptions options)189 QArrayData *QArrayData::allocate(size_t objectSize, size_t alignment,
190 size_t capacity, AllocationOptions options) noexcept
191 {
192 // Alignment is a power of two
193 Q_ASSERT(alignment >= Q_ALIGNOF(QArrayData)
194 && !(alignment & (alignment - 1)));
195
196 // Don't allocate empty headers
197 if (!(options & RawData) && !capacity) {
198 #if !defined(QT_NO_UNSHARABLE_CONTAINERS)
199 if (options & Unsharable)
200 return const_cast<QArrayData *>(&qt_array_unsharable_empty);
201 #endif
202 return const_cast<QArrayData *>(&qt_array_empty);
203 }
204
205 size_t headerSize = sizeof(QArrayData);
206
207 // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we
208 // can properly align the data array. This assumes malloc is able to
209 // provide appropriate alignment for the header -- as it should!
210 // Padding is skipped when allocating a header for RawData.
211 if (!(options & RawData))
212 headerSize += (alignment - Q_ALIGNOF(QArrayData));
213
214 if (headerSize > size_t(MaxAllocSize))
215 return nullptr;
216
217 size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options);
218 QArrayData *header = static_cast<QArrayData *>(::malloc(allocSize));
219 if (header) {
220 quintptr data = (quintptr(header) + sizeof(QArrayData) + alignment - 1)
221 & ~(alignment - 1);
222
223 #if !defined(QT_NO_UNSHARABLE_CONTAINERS)
224 header->ref.atomic.storeRelaxed(bool(!(options & Unsharable)));
225 #else
226 header->ref.atomic.storeRelaxed(1);
227 #endif
228 header->size = 0;
229 header->alloc = capacity;
230 header->capacityReserved = bool(options & CapacityReserved);
231 header->offset = data - quintptr(header);
232 }
233
234 return header;
235 }
236
reallocateUnaligned(QArrayData * data,size_t objectSize,size_t capacity,AllocationOptions options)237 QArrayData *QArrayData::reallocateUnaligned(QArrayData *data, size_t objectSize, size_t capacity,
238 AllocationOptions options) noexcept
239 {
240 Q_ASSERT(data);
241 Q_ASSERT(data->isMutable());
242 Q_ASSERT(!data->ref.isShared());
243
244 size_t headerSize = sizeof(QArrayData);
245 size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options);
246 QArrayData *header = static_cast<QArrayData *>(reallocateData(data, allocSize, options));
247 if (header)
248 header->alloc = capacity;
249 return header;
250 }
251
deallocate(QArrayData * data,size_t objectSize,size_t alignment)252 void QArrayData::deallocate(QArrayData *data, size_t objectSize,
253 size_t alignment) noexcept
254 {
255 // Alignment is a power of two
256 Q_ASSERT(alignment >= Q_ALIGNOF(QArrayData)
257 && !(alignment & (alignment - 1)));
258 Q_UNUSED(objectSize) Q_UNUSED(alignment)
259
260 #if !defined(QT_NO_UNSHARABLE_CONTAINERS)
261 if (data == &qt_array_unsharable_empty)
262 return;
263 #endif
264
265 Q_ASSERT_X(data == nullptr || !data->ref.isStatic(), "QArrayData::deallocate",
266 "Static data cannot be deleted");
267 ::free(data);
268 }
269
270 namespace QtPrivate {
271 /*!
272 \internal
273 */
mid(int originalLength,int * _position,int * _length)274 QContainerImplHelper::CutResult QContainerImplHelper::mid(int originalLength, int *_position, int *_length)
275 {
276 int &position = *_position;
277 int &length = *_length;
278 if (position > originalLength)
279 return Null;
280
281 if (position < 0) {
282 if (length < 0 || length + position >= originalLength)
283 return Full;
284 if (length + position <= 0)
285 return Null;
286 length += position;
287 position = 0;
288 } else if (uint(length) > uint(originalLength - position)) {
289 length = originalLength - position;
290 }
291
292 if (position == 0 && length == originalLength)
293 return Full;
294
295 return length > 0 ? Subset : Empty;
296 }
297 }
298
299 QT_END_NAMESPACE
300