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

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