1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtQml module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39#ifndef QV4MMDEFS_P_H
40#define QV4MMDEFS_P_H
41
42//
43// W A R N I N G
44// -------------
45//
46// This file is not part of the Qt API. It exists purely as an
47// implementation detail. This header file may change from version to
48// version without notice, or even be removed.
49//
50// We mean it.
51//
52
53#include <private/qv4global_p.h>
54#include <private/qv4runtimeapi_p.h>
55#include <QtCore/qalgorithms.h>
56#include <QtCore/qmath.h>
57#include <qdebug.h>
58
59QT_BEGIN_NAMESPACE
60
61namespace QV4 {
62
63struct MarkStack;
64
65typedef void(*ClassDestroyStatsCallback)(const char *);
66
67/*
68 * Chunks are the basic structure containing GC managed objects.
69 *
70 * Chunks are 64k aligned in memory, so that retrieving the Chunk pointer from a Heap object
71 * is a simple masking operation. Each Chunk has 4 bitmaps for managing purposes,
72 * and 32byte wide slots for the objects following afterwards.
73 *
74 * The gray and black bitmaps are used for mark/sweep.
75 * The object bitmap has a bit set if this location represents the start of a Heap object.
76 * The extends bitmap denotes the extend of an object. It has a cleared bit at the start of the object
77 * and a set bit for all following slots used by the object.
78 *
79 * Free memory has both used and extends bits set to 0.
80 *
81 * This gives the following operations when allocating an object of size s:
82 * Find s/Alignment consecutive free slots in the chunk. Set the object bit for the first
83 * slot to 1. Set the extends bits for all following slots to 1.
84 *
85 * All used slots can be found by object|extents.
86 *
87 * When sweeping, simply copy the black bits over to the object bits.
88 *
89 */
90struct HeapItem;
91struct Chunk {
92 enum {
93 ChunkSize = 64*1024,
94 ChunkShift = 16,
95 SlotSize = 32,
96 SlotSizeShift = 5,
97 NumSlots = ChunkSize/SlotSize,
98 BitmapSize = NumSlots/8,
99 HeaderSize = 4*BitmapSize,
100 DataSize = ChunkSize - HeaderSize,
101 AvailableSlots = DataSize/SlotSize,
102#if QT_POINTER_SIZE == 8
103 Bits = 64,
104 BitShift = 6,
105#else
106 Bits = 32,
107 BitShift = 5,
108#endif
109 EntriesInBitmap = BitmapSize/sizeof(quintptr)
110 };
111 quintptr grayBitmap[BitmapSize/sizeof(quintptr)];
112 quintptr blackBitmap[BitmapSize/sizeof(quintptr)];
113 quintptr objectBitmap[BitmapSize/sizeof(quintptr)];
114 quintptr extendsBitmap[BitmapSize/sizeof(quintptr)];
115 char data[ChunkSize - HeaderSize];
116
117 HeapItem *realBase();
118 HeapItem *first();
119
120 static Q_ALWAYS_INLINE size_t bitmapIndex(size_t index) {
121 return index >> BitShift;
122 }
123 static Q_ALWAYS_INLINE quintptr bitForIndex(size_t index) {
124 return static_cast<quintptr>(1) << (index & (Bits - 1));
125 }
126
127 static void setBit(quintptr *bitmap, size_t index) {
128// Q_ASSERT(index >= HeaderSize/SlotSize && index < ChunkSize/SlotSize);
129 bitmap += bitmapIndex(index);
130 quintptr bit = bitForIndex(index);
131 *bitmap |= bit;
132 }
133 static void clearBit(quintptr *bitmap, size_t index) {
134// Q_ASSERT(index >= HeaderSize/SlotSize && index < ChunkSize/SlotSize);
135 bitmap += bitmapIndex(index);
136 quintptr bit = bitForIndex(index);
137 *bitmap &= ~bit;
138 }
139 static bool testBit(quintptr *bitmap, size_t index) {
140// Q_ASSERT(index >= HeaderSize/SlotSize && index < ChunkSize/SlotSize);
141 bitmap += bitmapIndex(index);
142 quintptr bit = bitForIndex(index);
143 return (*bitmap & bit);
144 }
145 static void setBits(quintptr *bitmap, size_t index, size_t nBits) {
146// Q_ASSERT(index >= HeaderSize/SlotSize && index + nBits <= ChunkSize/SlotSize);
147 if (!nBits)
148 return;
149 bitmap += index >> BitShift;
150 index &= (Bits - 1);
151 while (1) {
152 size_t bitsToSet = qMin(a: nBits, b: Bits - index);
153 quintptr mask = static_cast<quintptr>(-1) >> (Bits - bitsToSet) << index;
154 *bitmap |= mask;
155 nBits -= bitsToSet;
156 if (!nBits)
157 return;
158 index = 0;
159 ++bitmap;
160 }
161 }
162 static bool hasNonZeroBit(quintptr *bitmap) {
163 for (uint i = 0; i < EntriesInBitmap; ++i)
164 if (bitmap[i])
165 return true;
166 return false;
167 }
168 static uint lowestNonZeroBit(quintptr *bitmap) {
169 for (uint i = 0; i < EntriesInBitmap; ++i) {
170 if (bitmap[i]) {
171 quintptr b = bitmap[i];
172 return i*Bits + qCountTrailingZeroBits(v: b);
173 }
174 }
175 return 0;
176 }
177
178 uint nFreeSlots() const {
179 return AvailableSlots - nUsedSlots();
180 }
181 uint nUsedSlots() const {
182 uint usedSlots = 0;
183 for (uint i = 0; i < EntriesInBitmap; ++i) {
184 quintptr used = objectBitmap[i] | extendsBitmap[i];
185 usedSlots += qPopulationCount(v: used);
186 }
187 return usedSlots;
188 }
189
190 bool sweep(ClassDestroyStatsCallback classCountPtr);
191 void resetBlackBits();
192 void collectGrayItems(QV4::MarkStack *markStack);
193 bool sweep(ExecutionEngine *engine);
194 void freeAll(ExecutionEngine *engine);
195
196 void sortIntoBins(HeapItem **bins, uint nBins);
197};
198
199struct HeapItem {
200 union {
201 struct {
202 HeapItem *next;
203 size_t availableSlots;
204 } freeData;
205 quint64 payload[Chunk::SlotSize/sizeof(quint64)];
206 };
207 operator Heap::Base *() { return reinterpret_cast<Heap::Base *>(this); }
208
209 template<typename T>
210 T *as() { return static_cast<T *>(reinterpret_cast<Heap::Base *>(this)); }
211
212 Chunk *chunk() const {
213 return reinterpret_cast<Chunk *>(reinterpret_cast<quintptr>(this) >> Chunk::ChunkShift << Chunk::ChunkShift);
214 }
215
216 bool isGray() const {
217 Chunk *c = chunk();
218 uint index = this - c->realBase();
219 return Chunk::testBit(bitmap: c->grayBitmap, index);
220 }
221 bool isBlack() const {
222 Chunk *c = chunk();
223 uint index = this - c->realBase();
224 return Chunk::testBit(bitmap: c->blackBitmap, index);
225 }
226 bool isInUse() const {
227 Chunk *c = chunk();
228 uint index = this - c->realBase();
229 return Chunk::testBit(bitmap: c->objectBitmap, index);
230 }
231
232 void setAllocatedSlots(size_t nSlots) {
233// Q_ASSERT(size && !(size % sizeof(HeapItem)));
234 Chunk *c = chunk();
235 size_t index = this - c->realBase();
236// Q_ASSERT(!Chunk::testBit(c->objectBitmap, index));
237 Chunk::setBit(bitmap: c->objectBitmap, index);
238 Chunk::setBits(bitmap: c->extendsBitmap, index: index + 1, nBits: nSlots - 1);
239// for (uint i = index + 1; i < nBits - 1; ++i)
240// Q_ASSERT(Chunk::testBit(c->extendsBitmap, i));
241// Q_ASSERT(!Chunk::testBit(c->extendsBitmap, index));
242 }
243
244 // Doesn't report correctly for huge items
245 size_t size() const {
246 Chunk *c = chunk();
247 uint index = this - c->realBase();
248 Q_ASSERT(Chunk::testBit(c->objectBitmap, index));
249 // ### optimize me
250 uint end = index + 1;
251 while (end < Chunk::NumSlots && Chunk::testBit(bitmap: c->extendsBitmap, index: end))
252 ++end;
253 return (end - index)*sizeof(HeapItem);
254 }
255};
256
257inline HeapItem *Chunk::realBase()
258{
259 return reinterpret_cast<HeapItem *>(this);
260}
261
262inline HeapItem *Chunk::first()
263{
264 return reinterpret_cast<HeapItem *>(data);
265}
266
267Q_STATIC_ASSERT(sizeof(Chunk) == Chunk::ChunkSize);
268Q_STATIC_ASSERT((1 << Chunk::ChunkShift) == Chunk::ChunkSize);
269Q_STATIC_ASSERT(1 << Chunk::SlotSizeShift == Chunk::SlotSize);
270Q_STATIC_ASSERT(sizeof(HeapItem) == Chunk::SlotSize);
271Q_STATIC_ASSERT(QT_POINTER_SIZE*8 == Chunk::Bits);
272Q_STATIC_ASSERT((1 << Chunk::BitShift) == Chunk::Bits);
273
274struct Q_QML_PRIVATE_EXPORT MarkStack {
275 MarkStack(ExecutionEngine *engine);
276 ~MarkStack() { drain(); }
277
278 void push(Heap::Base *m) {
279 *(m_top++) = m;
280
281 if (m_top < m_softLimit)
282 return;
283
284 // If at or above soft limit, partition the remaining space into at most 64 segments and
285 // allow one C++ recursion of drain() per segment, plus one for the fence post.
286 const quintptr segmentSize = qNextPowerOfTwo(v: quintptr(m_hardLimit - m_softLimit) / 64u);
287 if (m_drainRecursion * segmentSize <= quintptr(m_top - m_softLimit)) {
288 ++m_drainRecursion;
289 drain();
290 --m_drainRecursion;
291 } else if (m_top == m_hardLimit) {
292 qFatal(msg: "GC mark stack overrun. Either simplify your application or"
293 "increase QV4_GC_MAX_STACK_SIZE");
294 }
295 }
296
297 ExecutionEngine *engine() const { return m_engine; }
298
299private:
300 Heap::Base *pop() { return *(--m_top); }
301 void drain();
302
303 Heap::Base **m_top = nullptr;
304 Heap::Base **m_base = nullptr;
305 Heap::Base **m_softLimit = nullptr;
306 Heap::Base **m_hardLimit = nullptr;
307 ExecutionEngine *m_engine = nullptr;
308 quintptr m_drainRecursion = 0;
309};
310
311// Some helper to automate the generation of our
312// functions used for marking objects
313
314#define HEAP_OBJECT_OFFSET_MEMBER_EXPANSION(c, gcType, type, name) \
315 HEAP_OBJECT_OFFSET_MEMBER_EXPANSION_##gcType(c, type, name)
316
317#define HEAP_OBJECT_OFFSET_MEMBER_EXPANSION_Pointer(c, type, name) Pointer<type, 0> name;
318#define HEAP_OBJECT_OFFSET_MEMBER_EXPANSION_NoMark(c, type, name) type name;
319#define HEAP_OBJECT_OFFSET_MEMBER_EXPANSION_HeapValue(c, type, name) HeapValue<0> name;
320#define HEAP_OBJECT_OFFSET_MEMBER_EXPANSION_ValueArray(c, type, name) type<0> name;
321
322#define HEAP_OBJECT_MEMBER_EXPANSION(c, gcType, type, name) \
323 HEAP_OBJECT_MEMBER_EXPANSION_##gcType(c, type, name)
324
325#define HEAP_OBJECT_MEMBER_EXPANSION_Pointer(c, type, name) \
326 Pointer<type, offsetof(c##OffsetStruct, name) + baseOffset> name;
327#define HEAP_OBJECT_MEMBER_EXPANSION_NoMark(c, type, name) \
328 type name;
329#define HEAP_OBJECT_MEMBER_EXPANSION_HeapValue(c, type, name) \
330 HeapValue<offsetof(c##OffsetStruct, name) + baseOffset> name;
331#define HEAP_OBJECT_MEMBER_EXPANSION_ValueArray(c, type, name) \
332 type<offsetof(c##OffsetStruct, name) + baseOffset> name;
333
334#define HEAP_OBJECT_MARKOBJECTS_EXPANSION(c, gcType, type, name) \
335 HEAP_OBJECT_MARKOBJECTS_EXPANSION_##gcType(c, type, name)
336#define HEAP_OBJECT_MARKOBJECTS_EXPANSION_Pointer(c, type, name) \
337 if (o->name) o->name.heapObject()->mark(stack);
338#define HEAP_OBJECT_MARKOBJECTS_EXPANSION_NoMark(c, type, name)
339#define HEAP_OBJECT_MARKOBJECTS_EXPANSION_HeapValue(c, type, name) \
340 o->name.mark(stack);
341#define HEAP_OBJECT_MARKOBJECTS_EXPANSION_ValueArray(c, type, name) \
342 o->name.mark(stack);
343
344
345#define DECLARE_HEAP_OBJECT_BASE(name, base) \
346 struct name##OffsetStruct { \
347 name##Members(name, HEAP_OBJECT_OFFSET_MEMBER_EXPANSION) \
348 }; \
349 struct name##SizeStruct : base, name##OffsetStruct {}; \
350 struct name##Data { \
351 typedef base SuperClass; \
352 static Q_CONSTEXPR size_t baseOffset = sizeof(name##SizeStruct) - sizeof(name##OffsetStruct); \
353 name##Members(name, HEAP_OBJECT_MEMBER_EXPANSION) \
354 }; \
355 Q_STATIC_ASSERT(sizeof(name##SizeStruct) == sizeof(name##Data) + name##Data::baseOffset); \
356
357#define DECLARE_HEAP_OBJECT(name, base) \
358 DECLARE_HEAP_OBJECT_BASE(name, base) \
359 struct name : base, name##Data
360#define DECLARE_EXPORTED_HEAP_OBJECT(name, base) \
361 DECLARE_HEAP_OBJECT_BASE(name, base) \
362 struct Q_QML_EXPORT name : base, name##Data
363
364#define DECLARE_MARKOBJECTS(class) \
365 static void markObjects(Heap::Base *b, MarkStack *stack) { \
366 class *o = static_cast<class *>(b); \
367 class##Data::SuperClass::markObjects(o, stack); \
368 class##Members(class, HEAP_OBJECT_MARKOBJECTS_EXPANSION) \
369 }
370
371}
372
373QT_END_NAMESPACE
374
375#endif
376

source code of qtdeclarative/src/qml/memory/qv4mmdefs_p.h