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
48QT_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*/
85size_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*/
125CalculateGrowingBlockSizeResult
126qCalculateGrowingBlockSize(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 = bytes;
147 return result;
148}
149
150// End of qtools_p.h implementation
151
152QT_WARNING_PUSH
153QT_WARNING_DISABLE_GCC("-Wmissing-field-initializers")
154
155const QArrayData QArrayData::shared_null[2] = {
156 { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, sizeof(QArrayData) }, // shared null
157 /* zero initialized terminator */};
158
159static 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
164QT_WARNING_POP
165
166static const QArrayData &qt_array_empty = qt_array[0];
167static const QArrayData &qt_array_unsharable_empty = qt_array[1];
168
169static inline size_t calculateBlockSize(size_t &capacity, size_t objectSize, size_t headerSize,
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
184static QArrayData *reallocateData(QArrayData *header, 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
192QArrayData *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 headerSize = 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 *header = 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
240QArrayData *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 headerSize = sizeof(QArrayData);
248 size_t allocSize = calculateBlockSize(capacity, objectSize, headerSize, options);
249 QArrayData *header = static_cast<QArrayData *>(reallocateData(data, allocSize, options));
250 if (header)
251 header->alloc = capacity;
252 return header;
253}
254
255void 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
273namespace QtPrivate {
274/*!
275 \internal
276*/
277QContainerImplHelper::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
302QT_END_NAMESPACE
303