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 | |
59 | QT_BEGIN_NAMESPACE |
60 | |
61 | namespace QV4 { |
62 | |
63 | struct MarkStack; |
64 | |
65 | typedef 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 | */ |
90 | struct HeapItem; |
91 | struct 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 | = 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 | |
199 | struct 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 | |
257 | inline HeapItem *Chunk::realBase() |
258 | { |
259 | return reinterpret_cast<HeapItem *>(this); |
260 | } |
261 | |
262 | inline HeapItem *Chunk::first() |
263 | { |
264 | return reinterpret_cast<HeapItem *>(data); |
265 | } |
266 | |
267 | Q_STATIC_ASSERT(sizeof(Chunk) == Chunk::ChunkSize); |
268 | Q_STATIC_ASSERT((1 << Chunk::ChunkShift) == Chunk::ChunkSize); |
269 | Q_STATIC_ASSERT(1 << Chunk::SlotSizeShift == Chunk::SlotSize); |
270 | Q_STATIC_ASSERT(sizeof(HeapItem) == Chunk::SlotSize); |
271 | Q_STATIC_ASSERT(QT_POINTER_SIZE*8 == Chunk::Bits); |
272 | Q_STATIC_ASSERT((1 << Chunk::BitShift) == Chunk::Bits); |
273 | |
274 | struct 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 | |
299 | private: |
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 | |
373 | QT_END_NAMESPACE |
374 | |
375 | #endif |
376 | |