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 | |
22 | QT_BEGIN_NAMESPACE |
23 | |
24 | namespace QV4 { |
25 | |
26 | struct MarkStack; |
27 | |
28 | typedef 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 | */ |
53 | struct HeapItem; |
54 | struct 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 | = 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 | |
160 | struct 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 | |
213 | inline HeapItem *Chunk::realBase() |
214 | { |
215 | return reinterpret_cast<HeapItem *>(this); |
216 | } |
217 | |
218 | inline HeapItem *Chunk::first() |
219 | { |
220 | return reinterpret_cast<HeapItem *>(data); |
221 | } |
222 | |
223 | Q_STATIC_ASSERT(sizeof(Chunk) == Chunk::ChunkSize); |
224 | Q_STATIC_ASSERT((1 << Chunk::ChunkShift) == Chunk::ChunkSize); |
225 | Q_STATIC_ASSERT(1 << Chunk::SlotSizeShift == Chunk::SlotSize); |
226 | Q_STATIC_ASSERT(sizeof(HeapItem) == Chunk::SlotSize); |
227 | Q_STATIC_ASSERT(QT_POINTER_SIZE*8 == Chunk::Bits); |
228 | Q_STATIC_ASSERT((1 << Chunk::BitShift) == Chunk::Bits); |
229 | |
230 | struct 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 | |
255 | private: |
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 | |
329 | QT_END_NAMESPACE |
330 | |
331 | #endif |
332 | |