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         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 
bitmapIndexChunk120     static Q_ALWAYS_INLINE size_t bitmapIndex(size_t index) {
121         return index >> BitShift;
122     }
bitForIndexChunk123     static Q_ALWAYS_INLINE quintptr bitForIndex(size_t index) {
124         return static_cast<quintptr>(1) << (index & (Bits - 1));
125     }
126 
setBitChunk127     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     }
clearBitChunk133     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     }
testBitChunk139     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     }
setBitsChunk145     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(nBits, 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     }
hasNonZeroBitChunk162     static bool hasNonZeroBit(quintptr *bitmap) {
163         for (uint i = 0; i < EntriesInBitmap; ++i)
164             if (bitmap[i])
165                 return true;
166         return false;
167     }
lowestNonZeroBitChunk168     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(b);
173             }
174         }
175         return 0;
176     }
177 
nFreeSlotsChunk178     uint nFreeSlots() const {
179         return AvailableSlots - nUsedSlots();
180     }
nUsedSlotsChunk181     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(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>
asHeapItem210     T *as() { return static_cast<T *>(reinterpret_cast<Heap::Base *>(this)); }
211 
chunkHeapItem212     Chunk *chunk() const {
213         return reinterpret_cast<Chunk *>(reinterpret_cast<quintptr>(this) >> Chunk::ChunkShift << Chunk::ChunkShift);
214     }
215 
isGrayHeapItem216     bool isGray() const {
217         Chunk *c = chunk();
218         uint index = this - c->realBase();
219         return Chunk::testBit(c->grayBitmap, index);
220     }
isBlackHeapItem221     bool isBlack() const {
222         Chunk *c = chunk();
223         uint index = this - c->realBase();
224         return Chunk::testBit(c->blackBitmap, index);
225     }
isInUseHeapItem226     bool isInUse() const {
227         Chunk *c = chunk();
228         uint index = this - c->realBase();
229         return Chunk::testBit(c->objectBitmap, index);
230     }
231 
setAllocatedSlotsHeapItem232     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(c->objectBitmap, index);
238         Chunk::setBits(c->extendsBitmap, index + 1, 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
sizeHeapItem245     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(c->extendsBitmap, end))
252             ++end;
253         return (end - index)*sizeof(HeapItem);
254     }
255 };
256 
realBase()257 inline HeapItem *Chunk::realBase()
258 {
259     return reinterpret_cast<HeapItem *>(this);
260 }
261 
first()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);
~MarkStackMarkStack276     ~MarkStack() { drain(); }
277 
pushMarkStack278     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(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("GC mark stack overrun. Either simplify your application or"
293                    "increase QV4_GC_MAX_STACK_SIZE");
294         }
295     }
296 
engineMarkStack297     ExecutionEngine *engine() const { return m_engine; }
298 
299 private:
popMarkStack300     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