Encapsulate and protect all accesses to the vtable of Heap objects
[platform/upstream/qtdeclarative.git] / src / qml / memory / qv4mm.cpp
1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the QtQml module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL21$
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 http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://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 2.1 or version 3 as published by the Free
20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and
21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the
22 ** following information to ensure the GNU Lesser General Public License
23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 **
26 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** $QT_END_LICENSE$
31 **
32 ****************************************************************************/
33
34 #include "qv4engine_p.h"
35 #include "qv4object_p.h"
36 #include "qv4objectproto_p.h"
37 #include "qv4mm_p.h"
38 #include "qv4qobjectwrapper_p.h"
39 #include <qqmlengine.h>
40 #include "PageAllocation.h"
41 #include "StdLibExtras.h"
42
43 #include <QTime>
44 #include <QVector>
45 #include <QVector>
46 #include <QMap>
47
48 #include <iostream>
49 #include <cstdlib>
50 #include <algorithm>
51 #include "qv4alloca_p.h"
52 #include "qv4profiling_p.h"
53
54 #ifdef V4_USE_VALGRIND
55 #include <valgrind/valgrind.h>
56 #include <valgrind/memcheck.h>
57 #endif
58
59 #if OS(QNX)
60 #include <sys/storage.h>   // __tls()
61 #endif
62
63 #if USE(PTHREADS) && HAVE(PTHREAD_NP_H)
64 #include <pthread_np.h>
65 #endif
66
67 using namespace WTF;
68
69 QT_BEGIN_NAMESPACE
70
71 using namespace QV4;
72
73 struct MemoryManager::Data
74 {
75     struct ChunkHeader {
76         Heap::Base freeItems;
77         ChunkHeader *nextNonFull;
78         char *itemStart;
79         char *itemEnd;
80         int itemSize;
81     };
82
83     bool gcBlocked;
84     bool aggressiveGC;
85     bool gcStats;
86     ExecutionEngine *engine;
87
88     enum { MaxItemSize = 512 };
89     ChunkHeader *nonFullChunks[MaxItemSize/16];
90     uint nChunks[MaxItemSize/16];
91     uint availableItems[MaxItemSize/16];
92     uint allocCount[MaxItemSize/16];
93     int totalItems;
94     int totalAlloc;
95     uint maxShift;
96     std::size_t maxChunkSize;
97     QVector<PageAllocation> heapChunks;
98
99     struct LargeItem {
100         LargeItem *next;
101         size_t size;
102         void *data;
103
104         Heap::Base *heapObject() {
105             return reinterpret_cast<Heap::Base *>(&data);
106         }
107     };
108
109     LargeItem *largeItems;
110     std::size_t totalLargeItemsAllocated;
111
112     GCDeletable *deletable;
113
114     // statistics:
115 #ifdef DETAILED_MM_STATS
116     QVector<unsigned> allocSizeCounters;
117 #endif // DETAILED_MM_STATS
118
119     Data()
120         : gcBlocked(false)
121         , engine(0)
122         , totalItems(0)
123         , totalAlloc(0)
124         , maxShift(6)
125         , maxChunkSize(32*1024)
126         , largeItems(0)
127         , totalLargeItemsAllocated(0)
128         , deletable(0)
129     {
130         memset(nonFullChunks, 0, sizeof(nonFullChunks));
131         memset(nChunks, 0, sizeof(nChunks));
132         memset(availableItems, 0, sizeof(availableItems));
133         memset(allocCount, 0, sizeof(allocCount));
134         aggressiveGC = !qgetenv("QV4_MM_AGGRESSIVE_GC").isEmpty();
135         gcStats = !qgetenv("QV4_MM_STATS").isEmpty();
136
137         QByteArray overrideMaxShift = qgetenv("QV4_MM_MAXBLOCK_SHIFT");
138         bool ok;
139         uint override = overrideMaxShift.toUInt(&ok);
140         if (ok && override <= 11 && override > 0)
141             maxShift = override;
142
143         QByteArray maxChunkString = qgetenv("QV4_MM_MAX_CHUNK_SIZE");
144         std::size_t tmpMaxChunkSize = maxChunkString.toUInt(&ok);
145         if (ok)
146             maxChunkSize = tmpMaxChunkSize;
147     }
148
149     ~Data()
150     {
151         for (QVector<PageAllocation>::iterator i = heapChunks.begin(), ei = heapChunks.end(); i != ei; ++i) {
152             Q_V4_PROFILE_DEALLOC(engine, 0, i->size(), Profiling::HeapPage);
153             i->deallocate();
154         }
155     }
156 };
157
158 namespace {
159
160 bool sweepChunk(MemoryManager::Data::ChunkHeader *header, uint *itemsInUse, ExecutionEngine *engine)
161 {
162     bool isEmpty = true;
163     Heap::Base *tail = &header->freeItems;
164 //    qDebug("chunkStart @ %p, size=%x, pos=%x", header->itemStart, header->itemSize, header->itemSize>>4);
165 #ifdef V4_USE_VALGRIND
166     VALGRIND_DISABLE_ERROR_REPORTING;
167 #endif
168     for (char *item = header->itemStart; item <= header->itemEnd; item += header->itemSize) {
169         Heap::Base *m = reinterpret_cast<Heap::Base *>(item);
170 //        qDebug("chunk @ %p, size = %lu, in use: %s, mark bit: %s",
171 //               item, m->size, (m->inUse ? "yes" : "no"), (m->markBit ? "true" : "false"));
172
173         Q_ASSERT((qintptr) item % 16 == 0);
174
175         if (m->isMarked()) {
176             Q_ASSERT(m->inUse());
177             m->clearMarkBit();
178             isEmpty = false;
179             ++(*itemsInUse);
180         } else {
181             if (m->inUse()) {
182 //                qDebug() << "-- collecting it." << m << tail << m->nextFree();
183 #ifdef V4_USE_VALGRIND
184                 VALGRIND_ENABLE_ERROR_REPORTING;
185 #endif
186                 if (m->vtable()->destroy)
187                     m->vtable()->destroy(m);
188
189                 memset(m, 0, header->itemSize);
190 #ifdef V4_USE_VALGRIND
191                 VALGRIND_DISABLE_ERROR_REPORTING;
192                 VALGRIND_MEMPOOL_FREE(engine->memoryManager, m);
193 #endif
194                 Q_V4_PROFILE_DEALLOC(engine, m, header->itemSize, Profiling::SmallItem);
195                 ++(*itemsInUse);
196             }
197             // Relink all free blocks to rewrite references to any released chunk.
198             tail->setNextFree(m);
199             tail = m;
200         }
201     }
202     tail->setNextFree(0);
203 #ifdef V4_USE_VALGRIND
204     VALGRIND_ENABLE_ERROR_REPORTING;
205 #endif
206     return isEmpty;
207 }
208
209 } // namespace
210
211 MemoryManager::MemoryManager(ExecutionEngine *engine)
212     : m_d(new Data)
213     , m_persistentValues(new PersistentValueStorage(engine))
214     , m_weakValues(new PersistentValueStorage(engine))
215 {
216 #ifdef V4_USE_VALGRIND
217     VALGRIND_CREATE_MEMPOOL(this, 0, true);
218 #endif
219     m_d->engine = engine;
220 }
221
222 Heap::Base *MemoryManager::allocData(std::size_t size)
223 {
224     if (m_d->aggressiveGC)
225         runGC();
226 #ifdef DETAILED_MM_STATS
227     willAllocate(size);
228 #endif // DETAILED_MM_STATS
229
230     Q_ASSERT(size >= 16);
231     Q_ASSERT(size % 16 == 0);
232
233     size_t pos = size >> 4;
234
235     // doesn't fit into a small bucket
236     if (size >= MemoryManager::Data::MaxItemSize) {
237         if (m_d->totalLargeItemsAllocated > 8 * 1024 * 1024)
238             runGC();
239
240         // we use malloc for this
241         MemoryManager::Data::LargeItem *item = static_cast<MemoryManager::Data::LargeItem *>(
242                 malloc(Q_V4_PROFILE_ALLOC(m_d->engine, size + sizeof(MemoryManager::Data::LargeItem),
243                                           Profiling::LargeItem)));
244         memset(item, 0, size + sizeof(MemoryManager::Data::LargeItem));
245         item->next = m_d->largeItems;
246         item->size = size;
247         m_d->largeItems = item;
248         m_d->totalLargeItemsAllocated += size;
249         return item->heapObject();
250     }
251
252     Heap::Base *m = 0;
253     Data::ChunkHeader *header = m_d->nonFullChunks[pos];
254     if (header) {
255         m = header->freeItems.nextFree();
256         goto found;
257     }
258
259     // try to free up space, otherwise allocate
260     if (m_d->allocCount[pos] > (m_d->availableItems[pos] >> 1) && m_d->totalAlloc > (m_d->totalItems >> 1) && !m_d->aggressiveGC) {
261         runGC();
262         header = m_d->nonFullChunks[pos];
263         if (header) {
264             m = header->freeItems.nextFree();
265             goto found;
266         }
267     }
268
269     // no free item available, allocate a new chunk
270     {
271         // allocate larger chunks at a time to avoid excessive GC, but cap at maximum chunk size (2MB by default)
272         uint shift = ++m_d->nChunks[pos];
273         if (shift > m_d->maxShift)
274             shift = m_d->maxShift;
275         std::size_t allocSize = m_d->maxChunkSize*(size_t(1) << shift);
276         allocSize = roundUpToMultipleOf(WTF::pageSize(), allocSize);
277         PageAllocation allocation = PageAllocation::allocate(
278                     Q_V4_PROFILE_ALLOC(m_d->engine, allocSize, Profiling::HeapPage),
279                     OSAllocator::JSGCHeapPages);
280         m_d->heapChunks.append(allocation);
281         std::sort(m_d->heapChunks.begin(), m_d->heapChunks.end());
282
283         header = reinterpret_cast<Data::ChunkHeader *>(allocation.base());
284         header->itemSize = int(size);
285         header->itemStart = reinterpret_cast<char *>(allocation.base()) + roundUpToMultipleOf(16, sizeof(Data::ChunkHeader));
286         header->itemEnd = reinterpret_cast<char *>(allocation.base()) + allocation.size() - header->itemSize;
287
288         header->nextNonFull = m_d->nonFullChunks[pos];
289         m_d->nonFullChunks[pos] = header;
290
291         Heap::Base *last = &header->freeItems;
292         for (char *item = header->itemStart; item <= header->itemEnd; item += header->itemSize) {
293             Heap::Base *o = reinterpret_cast<Heap::Base *>(item);
294             last->setNextFree(o);
295             last = o;
296
297         }
298         last->setNextFree(0);
299         m = header->freeItems.nextFree();
300         const size_t increase = (header->itemEnd - header->itemStart) / header->itemSize;
301         m_d->availableItems[pos] += uint(increase);
302         m_d->totalItems += int(increase);
303 #ifdef V4_USE_VALGRIND
304         VALGRIND_MAKE_MEM_NOACCESS(allocation.base(), allocSize);
305         VALGRIND_MEMPOOL_ALLOC(this, header, sizeof(Data::ChunkHeader));
306 #endif
307     }
308
309   found:
310 #ifdef V4_USE_VALGRIND
311     VALGRIND_MEMPOOL_ALLOC(this, m, size);
312 #endif
313     Q_V4_PROFILE_ALLOC(m_d->engine, size, Profiling::SmallItem);
314
315     ++m_d->allocCount[pos];
316     ++m_d->totalAlloc;
317     header->freeItems.setNextFree(m->nextFree());
318     if (!header->freeItems.nextFree())
319         m_d->nonFullChunks[pos] = header->nextNonFull;
320     return m;
321 }
322
323 static void drainMarkStack(QV4::ExecutionEngine *engine, Value *markBase)
324 {
325     while (engine->jsStackTop > markBase) {
326         Heap::Base *h = engine->popForGC();
327         Q_ASSERT (h->vtable()->markObjects);
328         h->vtable()->markObjects(h, engine);
329     }
330 }
331
332 void MemoryManager::mark()
333 {
334     Value *markBase = m_d->engine->jsStackTop;
335
336     m_d->engine->markObjects();
337
338     m_persistentValues->mark(m_d->engine);
339
340     collectFromJSStack();
341
342     // Preserve QObject ownership rules within JavaScript: A parent with c++ ownership
343     // keeps all of its children alive in JavaScript.
344
345     // Do this _after_ collectFromStack to ensure that processing the weak
346     // managed objects in the loop down there doesn't make then end up as leftovers
347     // on the stack and thus always get collected.
348     for (PersistentValueStorage::Iterator it = m_weakValues->begin(); it != m_weakValues->end(); ++it) {
349         if (!(*it).isManaged())
350             continue;
351         if ((*it).managed()->d()->vtable() != QObjectWrapper::staticVTable())
352             continue;
353         QObjectWrapper *qobjectWrapper = static_cast<QObjectWrapper*>((*it).managed());
354         if (!qobjectWrapper)
355             continue;
356         QObject *qobject = qobjectWrapper->object();
357         if (!qobject)
358             continue;
359         bool keepAlive = QQmlData::keepAliveDuringGarbageCollection(qobject);
360
361         if (!keepAlive) {
362             if (QObject *parent = qobject->parent()) {
363                 while (parent->parent())
364                     parent = parent->parent();
365
366                 keepAlive = QQmlData::keepAliveDuringGarbageCollection(parent);
367             }
368         }
369
370         if (keepAlive)
371             qobjectWrapper->mark(m_d->engine);
372
373         if (m_d->engine->jsStackTop >= m_d->engine->jsStackLimit)
374             drainMarkStack(m_d->engine, markBase);
375     }
376
377     drainMarkStack(m_d->engine, markBase);
378 }
379
380 void MemoryManager::sweep(bool lastSweep)
381 {
382     if (m_weakValues) {
383         for (PersistentValueStorage::Iterator it = m_weakValues->begin(); it != m_weakValues->end(); ++it) {
384             if (Managed *m = (*it).as<Managed>()) {
385                 if (!m->markBit())
386                     (*it) = Primitive::undefinedValue();
387             }
388         }
389     }
390
391     if (MultiplyWrappedQObjectMap *multiplyWrappedQObjects = m_d->engine->m_multiplyWrappedQObjects) {
392         for (MultiplyWrappedQObjectMap::Iterator it = multiplyWrappedQObjects->begin(); it != multiplyWrappedQObjects->end();) {
393             if (!it.value().isNullOrUndefined())
394                 it = multiplyWrappedQObjects->erase(it);
395             else
396                 ++it;
397         }
398     }
399
400     bool *chunkIsEmpty = (bool *)alloca(m_d->heapChunks.size() * sizeof(bool));
401     uint itemsInUse[MemoryManager::Data::MaxItemSize/16];
402     memset(itemsInUse, 0, sizeof(itemsInUse));
403     memset(m_d->nonFullChunks, 0, sizeof(m_d->nonFullChunks));
404
405     for (int i = 0; i < m_d->heapChunks.size(); ++i) {
406         Data::ChunkHeader *header = reinterpret_cast<Data::ChunkHeader *>(m_d->heapChunks[i].base());
407         chunkIsEmpty[i] = sweepChunk(header, &itemsInUse[header->itemSize >> 4], m_d->engine);
408     }
409
410     QVector<PageAllocation>::iterator chunkIter = m_d->heapChunks.begin();
411     for (int i = 0; i < m_d->heapChunks.size(); ++i) {
412         Q_ASSERT(chunkIter != m_d->heapChunks.end());
413         Data::ChunkHeader *header = reinterpret_cast<Data::ChunkHeader *>(chunkIter->base());
414         const size_t pos = header->itemSize >> 4;
415         const size_t decrease = (header->itemEnd - header->itemStart) / header->itemSize;
416
417         // Release that chunk if it could have been spared since the last GC run without any difference.
418         if (chunkIsEmpty[i] && m_d->availableItems[pos] - decrease >= itemsInUse[pos]) {
419             Q_V4_PROFILE_DEALLOC(m_d->engine, 0, chunkIter->size(), Profiling::HeapPage);
420 #ifdef V4_USE_VALGRIND
421             VALGRIND_MEMPOOL_FREE(this, header);
422 #endif
423             --m_d->nChunks[pos];
424             m_d->availableItems[pos] -= uint(decrease);
425             m_d->totalItems -= int(decrease);
426             chunkIter->deallocate();
427             chunkIter = m_d->heapChunks.erase(chunkIter);
428             continue;
429         } else if (header->freeItems.nextFree()) {
430             header->nextNonFull = m_d->nonFullChunks[pos];
431             m_d->nonFullChunks[pos] = header;
432         }
433         ++chunkIter;
434     }
435
436     Data::LargeItem *i = m_d->largeItems;
437     Data::LargeItem **last = &m_d->largeItems;
438     while (i) {
439         Heap::Base *m = i->heapObject();
440         Q_ASSERT(m->inUse());
441         if (m->isMarked()) {
442             m->clearMarkBit();
443             last = &i->next;
444             i = i->next;
445             continue;
446         }
447         if (m->vtable()->destroy)
448             m->vtable()->destroy(m);
449
450         *last = i->next;
451         free(Q_V4_PROFILE_DEALLOC(m_d->engine, i, i->size + sizeof(Data::LargeItem),
452                                   Profiling::LargeItem));
453         i = *last;
454     }
455
456     GCDeletable *deletable = m_d->deletable;
457     m_d->deletable = 0;
458     while (deletable) {
459         GCDeletable *next = deletable->next;
460         deletable->lastCall = lastSweep;
461         delete deletable;
462         deletable = next;
463     }
464
465     // some execution contexts are allocated on the stack, make sure we clear their markBit as well
466     if (!lastSweep) {
467         Heap::ExecutionContext *ctx = engine()->current;
468         while (ctx) {
469             ctx->clearMarkBit();
470             ctx = ctx->parent;
471         }
472     }
473 }
474
475 bool MemoryManager::isGCBlocked() const
476 {
477     return m_d->gcBlocked;
478 }
479
480 void MemoryManager::setGCBlocked(bool blockGC)
481 {
482     m_d->gcBlocked = blockGC;
483 }
484
485 void MemoryManager::runGC()
486 {
487     if (m_d->gcBlocked) {
488 //        qDebug() << "Not running GC.";
489         return;
490     }
491
492     if (!m_d->gcStats) {
493         mark();
494         sweep();
495     } else {
496         const size_t totalMem = getAllocatedMem();
497
498         QTime t;
499         t.start();
500         mark();
501         int markTime = t.elapsed();
502         t.restart();
503         const size_t usedBefore = getUsedMem();
504         int chunksBefore = m_d->heapChunks.size();
505         sweep();
506         const size_t usedAfter = getUsedMem();
507         int sweepTime = t.elapsed();
508
509         qDebug() << "========== GC ==========";
510         qDebug() << "Marked object in" << markTime << "ms.";
511         qDebug() << "Sweeped object in" << sweepTime << "ms.";
512         qDebug() << "Allocated" << totalMem << "bytes in" << m_d->heapChunks.size() << "chunks.";
513         qDebug() << "Used memory before GC:" << usedBefore;
514         qDebug() << "Used memory after GC:" << usedAfter;
515         qDebug() << "Freed up bytes:" << (usedBefore - usedAfter);
516         qDebug() << "Released chunks:" << (chunksBefore - m_d->heapChunks.size());
517         qDebug() << "======== End GC ========";
518     }
519
520     memset(m_d->allocCount, 0, sizeof(m_d->allocCount));
521     m_d->totalAlloc = 0;
522     m_d->totalLargeItemsAllocated = 0;
523 }
524
525 size_t MemoryManager::getUsedMem() const
526 {
527     size_t usedMem = 0;
528     for (QVector<PageAllocation>::const_iterator i = m_d->heapChunks.cbegin(), ei = m_d->heapChunks.cend(); i != ei; ++i) {
529         Data::ChunkHeader *header = reinterpret_cast<Data::ChunkHeader *>(i->base());
530         for (char *item = header->itemStart; item <= header->itemEnd; item += header->itemSize) {
531             Heap::Base *m = reinterpret_cast<Heap::Base *>(item);
532             Q_ASSERT((qintptr) item % 16 == 0);
533             if (m->inUse())
534                 usedMem += header->itemSize;
535         }
536     }
537     return usedMem;
538 }
539
540 size_t MemoryManager::getAllocatedMem() const
541 {
542     size_t total = 0;
543     for (int i = 0; i < m_d->heapChunks.size(); ++i)
544         total += m_d->heapChunks.at(i).size();
545     return total;
546 }
547
548 size_t MemoryManager::getLargeItemsMem() const
549 {
550     size_t total = 0;
551     for (const Data::LargeItem *i = m_d->largeItems; i != 0; i = i->next)
552         total += i->size;
553     return total;
554 }
555
556 MemoryManager::~MemoryManager()
557 {
558     delete m_persistentValues;
559     delete m_weakValues;
560     m_weakValues = 0;
561
562     sweep(/*lastSweep*/true);
563 #ifdef V4_USE_VALGRIND
564     VALGRIND_DESTROY_MEMPOOL(this);
565 #endif
566 }
567
568 ExecutionEngine *MemoryManager::engine() const
569 {
570     return m_d->engine;
571 }
572
573 void MemoryManager::dumpStats() const
574 {
575 #ifdef DETAILED_MM_STATS
576     std::cerr << "=================" << std::endl;
577     std::cerr << "Allocation stats:" << std::endl;
578     std::cerr << "Requests for each chunk size:" << std::endl;
579     for (int i = 0; i < m_d->allocSizeCounters.size(); ++i) {
580         if (unsigned count = m_d->allocSizeCounters[i]) {
581             std::cerr << "\t" << (i << 4) << " bytes chunks: " << count << std::endl;
582         }
583     }
584 #endif // DETAILED_MM_STATS
585 }
586
587 void MemoryManager::registerDeletable(GCDeletable *d)
588 {
589     d->next = m_d->deletable;
590     m_d->deletable = d;
591 }
592
593 #ifdef DETAILED_MM_STATS
594 void MemoryManager::willAllocate(std::size_t size)
595 {
596     unsigned alignedSize = (size + 15) >> 4;
597     QVector<unsigned> &counters = m_d->allocSizeCounters;
598     if ((unsigned) counters.size() < alignedSize + 1)
599         counters.resize(alignedSize + 1);
600     counters[alignedSize]++;
601 }
602
603 #endif // DETAILED_MM_STATS
604
605 void MemoryManager::collectFromJSStack() const
606 {
607     Value *v = m_d->engine->jsStackBase;
608     Value *top = m_d->engine->jsStackTop;
609     while (v < top) {
610         Managed *m = v->as<Managed>();
611         if (m && m->inUse())
612             // Skip pointers to already freed objects, they are bogus as well
613             m->mark(m_d->engine);
614         ++v;
615     }
616 }
617 QT_END_NAMESPACE