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

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