1/****************************************************************************
2**
3** Copyright (C) 2020 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 <QtCore/qbytearray.h> // QBA::value_type
47#include <QtCore/qstring.h> // QString::value_type
48
49#include <stdlib.h>
50
51QT_BEGIN_NAMESPACE
52
53/*
54 * This pair of functions is declared in qtools_p.h and is used by the Qt
55 * containers to allocate memory and grow the memory block during append
56 * operations.
57 *
58 * They take qsizetype parameters and return qsizetype so they will change sizes
59 * according to the pointer width. However, knowing Qt containers store the
60 * container size and element indexes in ints, these functions never return a
61 * size larger than INT_MAX. This is done by casting the element count and
62 * memory block size to int in several comparisons: the check for negative is
63 * very fast on most platforms as the code only needs to check the sign bit.
64 *
65 * These functions return SIZE_MAX on overflow, which can be passed to malloc()
66 * and will surely cause a NULL return (there's no way you can allocate a
67 * memory block the size of your entire VM space).
68 */
69
70/*!
71 \internal
72 \since 5.7
73
74 Returns the memory block size for a container containing \a elementCount
75 elements, each of \a elementSize bytes, plus a header of \a headerSize
76 bytes. That is, this function returns \c
77 {elementCount * elementSize + headerSize}
78
79 but unlike the simple calculation, it checks for overflows during the
80 multiplication and the addition.
81
82 Both \a elementCount and \a headerSize can be zero, but \a elementSize
83 cannot.
84
85 This function returns -1 on overflow or if the memory block size
86 would not fit a qsizetype.
87*/
88qsizetype qCalculateBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype headerSize) noexcept
89{
90 Q_ASSERT(elementSize);
91
92 size_t bytes;
93 if (Q_UNLIKELY(mul_overflow(size_t(elementSize), size_t(elementCount), &bytes)) ||
94 Q_UNLIKELY(add_overflow(bytes, size_t(headerSize), &bytes)))
95 return -1;
96 if (Q_UNLIKELY(qsizetype(bytes) < 0))
97 return -1;
98
99 return qsizetype(bytes);
100}
101
102/*!
103 \internal
104 \since 5.7
105
106 Returns the memory block size and the number of elements that will fit in
107 that block for a container containing \a elementCount elements, each of \a
108 elementSize bytes, plus a header of \a headerSize bytes. This function
109 assumes the container will grow and pre-allocates a growth factor.
110
111 Both \a elementCount and \a headerSize can be zero, but \a elementSize
112 cannot.
113
114 This function returns -1 on overflow or if the memory block size
115 would not fit a qsizetype.
116
117 \note The memory block may contain up to \a elementSize - 1 bytes more than
118 needed.
119*/
120CalculateGrowingBlockSizeResult
121qCalculateGrowingBlockSize(qsizetype elementCount, qsizetype elementSize, qsizetype headerSize) noexcept
122{
123 CalculateGrowingBlockSizeResult result = {
124 qsizetype(-1), qsizetype(-1)
125 };
126
127 qsizetype bytes = qCalculateBlockSize(elementCount, elementSize, headerSize);
128 if (bytes < 0)
129 return result;
130
131 size_t morebytes = static_cast<size_t>(qNextPowerOfTwo(quint64(bytes)));
132 if (Q_UNLIKELY(qsizetype(morebytes) < 0)) {
133 // grow by half the difference between bytes and morebytes
134 // this slows the growth and avoids trying to allocate exactly
135 // 2G of memory (on 32bit), something that many OSes can't deliver
136 bytes += (morebytes - bytes) / 2;
137 } else {
138 bytes = qsizetype(morebytes);
139 }
140
141 result.elementCount = (bytes - headerSize) / elementSize;
142 result.size = result.elementCount * elementSize + headerSize;
143 return result;
144}
145
146/*!
147 \internal
148
149 Returns \a allocSize plus extra reserved bytes necessary to store '\0'.
150 */
151static inline qsizetype reserveExtraBytes(qsizetype allocSize)
152{
153 // We deal with QByteArray and QString only
154 constexpr qsizetype extra = qMax(sizeof(QByteArray::value_type), sizeof(QString::value_type));
155 if (Q_UNLIKELY(allocSize < 0))
156 return -1;
157 if (Q_UNLIKELY(add_overflow(allocSize, extra, &allocSize)))
158 return -1;
159 return allocSize;
160}
161
162static inline qsizetype calculateBlockSize(qsizetype &capacity, qsizetype objectSize, qsizetype headerSize, uint options)
163{
164 // Calculate the byte size
165 // allocSize = objectSize * capacity + headerSize, but checked for overflow
166 // plus padded to grow in size
167 if (options & (QArrayData::GrowsForward | QArrayData::GrowsBackwards)) {
168 auto r = qCalculateGrowingBlockSize(capacity, objectSize, headerSize);
169 capacity = r.elementCount;
170 return r.size;
171 } else {
172 return qCalculateBlockSize(capacity, objectSize, headerSize);
173 }
174}
175
176static QArrayData *allocateData(qsizetype allocSize, uint options)
177{
178 QArrayData *header = static_cast<QArrayData *>(::malloc(size_t(allocSize)));
179 if (header) {
180 header->ref_.storeRelaxed(1);
181 header->flags = options;
182 header->alloc = 0;
183 }
184 return header;
185}
186
187void *QArrayData::allocate(QArrayData **dptr, qsizetype objectSize, qsizetype alignment,
188 qsizetype capacity, ArrayOptions options) noexcept
189{
190 Q_ASSERT(dptr);
191 // Alignment is a power of two
192 Q_ASSERT(alignment >= qsizetype(alignof(QArrayData))
193 && !(alignment & (alignment - 1)));
194
195 if (capacity == 0) {
196 *dptr = nullptr;
197 return nullptr;
198 }
199
200 qsizetype headerSize = sizeof(QArrayData);
201 const qsizetype headerAlignment = alignof(QArrayData);
202
203 if (alignment > headerAlignment) {
204 // Allocate extra (alignment - Q_ALIGNOF(QArrayData)) padding bytes so we
205 // can properly align the data array. This assumes malloc is able to
206 // provide appropriate alignment for the header -- as it should!
207 headerSize += alignment - headerAlignment;
208 }
209 Q_ASSERT(headerSize > 0);
210
211 qsizetype allocSize = calculateBlockSize(capacity, objectSize, headerSize, options);
212 allocSize = reserveExtraBytes(allocSize);
213 if (Q_UNLIKELY(allocSize < 0)) { // handle overflow. cannot allocate reliably
214 *dptr = nullptr;
215 return nullptr;
216 }
217
218 QArrayData *header = allocateData(allocSize, options);
219 void *data = nullptr;
220 if (header) {
221 // find where offset should point to so that data() is aligned to alignment bytes
222 data = QTypedArrayData<void>::dataStart(header, alignment);
223 header->alloc = qsizetype(capacity);
224 }
225
226 *dptr = header;
227 return data;
228}
229
230QPair<QArrayData *, void *>
231QArrayData::reallocateUnaligned(QArrayData *data, void *dataPointer,
232 qsizetype objectSize, qsizetype capacity, ArrayOptions options) noexcept
233{
234 Q_ASSERT(!data || !data->isShared());
235
236 qsizetype headerSize = sizeof(QArrayData);
237 qsizetype allocSize = calculateBlockSize(capacity, objectSize, headerSize, options);
238 qptrdiff offset = dataPointer ? reinterpret_cast<char *>(dataPointer) - reinterpret_cast<char *>(data) : headerSize;
239
240 allocSize = reserveExtraBytes(allocSize);
241 if (Q_UNLIKELY(allocSize < 0)) // handle overflow. cannot reallocate reliably
242 return qMakePair(data, dataPointer);
243
244 QArrayData *header = static_cast<QArrayData *>(::realloc(data, size_t(allocSize)));
245 if (header) {
246 header->flags = options;
247 header->alloc = uint(capacity);
248 dataPointer = reinterpret_cast<char *>(header) + offset;
249 }
250 return qMakePair(static_cast<QArrayData *>(header), dataPointer);
251}
252
253void QArrayData::deallocate(QArrayData *data, qsizetype objectSize,
254 qsizetype alignment) noexcept
255{
256 // Alignment is a power of two
257 Q_ASSERT(alignment >= qsizetype(alignof(QArrayData))
258 && !(alignment & (alignment - 1)));
259 Q_UNUSED(objectSize);
260 Q_UNUSED(alignment);
261
262 ::free(data);
263}
264
265QT_END_NAMESPACE
266