Incremental garbage collection

Add an incremental mode to the garbage collector, that will
get used for many collections. This should significantly
reduce average stop times for GC.

Make sure that manual calls to gc() still do a full collection,
to ensure consistency and keep tests that rely on gc() working.

Change-Id: I87b13529377b7639ce993dbd99e85ff0a555acd8
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>

10 files changed, 192 insertions, 35 deletions

diff --git a/src/qml/compiler/qv4compileddata.cpp b/src/qml/compiler/qv4compileddata.cpp
index c25a139379..d0dfb81f80 100644
--- a/src/qml/compiler/qv4compileddata.cpp
+++ b/src/qml/compiler/qv4compileddata.cpp
@@ -132,8 +132,10 @@ QV4::Function *CompilationUnit::linkToEngine(ExecutionEngine *engine)
     runtimeStrings = (QV4::Heap::String **)malloc(data->stringTableSize * sizeof(QV4::Heap::String*));
     // memset the strings to 0 in case a GC run happens while we're within the loop below
     memset(runtimeStrings, 0, data->stringTableSize * sizeof(QV4::Heap::String*));
-    for (uint i = 0; i < data->stringTableSize; ++i)
+    for (uint i = 0; i < data->stringTableSize; ++i) {
         runtimeStrings[i] = engine->newIdentifier(data->stringAt(i));
+        runtimeStrings[i]->setMarkBit();
+    }
 
     runtimeRegularExpressions = new QV4::Value[data->regexpTableSize];
     // memset the regexps to 0 in case a GC run happens while we're within the loop below
@@ -147,7 +149,14 @@ QV4::Function *CompilationUnit::linkToEngine(ExecutionEngine *engine)
             flags |= IR::RegExp::RegExp_IgnoreCase;
         if (re->flags & CompiledData::RegExp::RegExp_Multiline)
             flags |= IR::RegExp::RegExp_Multiline;
-        runtimeRegularExpressions[i] = engine->newRegExpObject(data->stringAt(re->stringIndex), flags);
+        QV4::Heap::RegExpObject *ro = engine->newRegExpObject(data->stringAt(re->stringIndex), flags);
+        runtimeRegularExpressions[i] = ro;
+#if WRITEBARRIER(steele)
+        if (engine->memoryManager->nextGCIsIncremental) {
+            ro->setMarkBit();
+            ro->setGrayBit();
+        }
+#endif
     }
 
     if (data->lookupTableSize) {
diff --git a/src/qml/jsapi/qjsengine.cpp b/src/qml/jsapi/qjsengine.cpp
index e4c150057a..b52c859ecb 100644
--- a/src/qml/jsapi/qjsengine.cpp
+++ b/src/qml/jsapi/qjsengine.cpp
@@ -333,7 +333,7 @@ QJSEngine::~QJSEngine()
 */
 void QJSEngine::collectGarbage()
 {
-    d->m_v4Engine->memoryManager->runGC();
+    d->m_v4Engine->memoryManager->runGC(/* forceFullCollection = */ true);
 }
 
 #if QT_DEPRECATED_SINCE(5, 6)
diff --git a/src/qml/jsruntime/qv4engine.cpp b/src/qml/jsruntime/qv4engine.cpp
index ab5ced9f58..899fd499df 100644
--- a/src/qml/jsruntime/qv4engine.cpp
+++ b/src/qml/jsruntime/qv4engine.cpp
@@ -931,23 +931,25 @@ void ExecutionEngine::requireArgumentsAccessors(int n)
     }
 }
 
-void ExecutionEngine::markObjects()
+void ExecutionEngine::markObjects(bool incremental)
 {
-    identifierTable->mark(this);
+    if (!incremental) {
+        identifierTable->mark(this);
 
-    for (int i = 0; i < nArgumentsAccessors; ++i) {
-        const Property &pd = argumentsAccessors[i];
-        if (Heap::FunctionObject *getter = pd.getter())
-            getter->mark(this);
-        if (Heap::FunctionObject *setter = pd.setter())
-            setter->mark(this);
-    }
+        for (int i = 0; i < nArgumentsAccessors; ++i) {
+            const Property &pd = argumentsAccessors[i];
+            if (Heap::FunctionObject *getter = pd.getter())
+                getter->mark(this);
+            if (Heap::FunctionObject *setter = pd.setter())
+                setter->mark(this);
+        }
 
-    classPool->markObjects(this);
+        classPool->markObjects(this);
 
-    for (QSet<CompiledData::CompilationUnit*>::ConstIterator it = compilationUnits.constBegin(), end = compilationUnits.constEnd();
-         it != end; ++it)
-        (*it)->markObjects(this);
+        for (QSet<CompiledData::CompilationUnit*>::ConstIterator it = compilationUnits.constBegin(), end = compilationUnits.constEnd();
+             it != end; ++it)
+            (*it)->markObjects(this);
+    }
 }
 
 ReturnedValue ExecutionEngine::throwError(const Value &value)
diff --git a/src/qml/jsruntime/qv4engine_p.h b/src/qml/jsruntime/qv4engine_p.h
index 6de087a4e2..395a7c7250 100644
--- a/src/qml/jsruntime/qv4engine_p.h
+++ b/src/qml/jsruntime/qv4engine_p.h
@@ -450,7 +450,7 @@ public:
 
     void requireArgumentsAccessors(int n);
 
-    void markObjects();
+    void markObjects(bool incremental);
 
     void initRootContext();
 
diff --git a/src/qml/jsruntime/qv4identifiertable.cpp b/src/qml/jsruntime/qv4identifiertable.cpp
index 3def6defbf..d3ef238716 100644
--- a/src/qml/jsruntime/qv4identifiertable.cpp
+++ b/src/qml/jsruntime/qv4identifiertable.cpp
@@ -81,6 +81,7 @@ void IdentifierTable::addEntry(Heap::String *str)
     str->identifier = new Identifier;
     str->identifier->string = str->toQString();
     str->identifier->hashValue = hash;
+    str->setMarkBit();
 
     bool grow = (alloc <= size*2);
 
diff --git a/src/qml/memory/qv4mm.cpp b/src/qml/memory/qv4mm.cpp
index 8f4f2f4aa8..f3ee397d22 100644
--- a/src/qml/memory/qv4mm.cpp
+++ b/src/qml/memory/qv4mm.cpp
@@ -282,7 +282,7 @@ void Chunk::sweep()
             }
         }
         objectBitmap[i] = blackBitmap[i];
-        blackBitmap[i] = 0;
+        grayBitmap[i] = 0;
         extendsBitmap[i] = e;
         o += Chunk::Bits;
     }
@@ -321,13 +321,56 @@ void Chunk::freeAll()
             }
         }
         objectBitmap[i] = 0;
-        blackBitmap[i] = 0;
+        grayBitmap[i] = 0;
         extendsBitmap[i] = e;
         o += Chunk::Bits;
     }
     //    DEBUG << "swept chunk" << this << "freed" << slotsFreed << "slots.";
 }
 
+void Chunk::resetBlackBits()
+{
+    memset(blackBitmap, 0, sizeof(blackBitmap));
+}
+
+#ifndef QT_NO_DEBUG
+static uint nGrayItems = 0;
+#endif
+
+void Chunk::collectGrayItems(ExecutionEngine *engine)
+{
+    //    DEBUG << "sweeping chunk" << this << (*freeList);
+    HeapItem *o = realBase();
+    for (uint i = 0; i < Chunk::EntriesInBitmap; ++i) {
+#if WRITEBARRIER(none)
+        Q_ASSERT((grayBitmap[i] | blackBitmap[i]) == blackBitmap[i]); // check that we don't have gray only objects
+#endif
+        quintptr toMark = blackBitmap[i] & grayBitmap[i]; // correct for a Steele type barrier
+        Q_ASSERT((toMark & objectBitmap[i]) == toMark); // check all black objects are marked as being used
+        //        DEBUG << hex << "   index=" << i << toFree;
+        while (toMark) {
+            uint index = qCountTrailingZeroBits(toMark);
+            quintptr bit = (static_cast<quintptr>(1) << index);
+
+            toMark ^= bit; // mask out marked slot
+            //            DEBUG << "       index" << hex << index << toFree;
+
+            HeapItem *itemToFree = o + index;
+            Heap::Base *b = *itemToFree;
+            Q_ASSERT(b->inUse());
+            engine->pushForGC(b);
+#ifndef QT_NO_DEBUG
+            ++nGrayItems;
+//            qDebug() << "adding gray item" << b << "to mark stack";
+#endif
+        }
+        grayBitmap[i] = 0;
+        o += Chunk::Bits;
+    }
+    //    DEBUG << "swept chunk" << this << "freed" << slotsFreed << "slots.";
+
+}
+
 void Chunk::sortIntoBins(HeapItem **bins, uint nBins)
 {
 //    qDebug() << "sortIntoBins:";
@@ -557,6 +600,19 @@ void BlockAllocator::freeAll()
     }
 }
 
+void BlockAllocator::resetBlackBits()
+{
+    for (auto c : chunks)
+        c->resetBlackBits();
+}
+
+void BlockAllocator::collectGrayItems(ExecutionEngine *engine)
+{
+    for (auto c : chunks)
+        c->collectGrayItems(engine);
+
+}
+
 #if MM_DEBUG
 void BlockAllocator::stats() {
     DEBUG << "MM stats:";
@@ -609,7 +665,6 @@ static void freeHugeChunk(ChunkAllocator *chunkAllocator, const HugeItemAllocato
 void HugeItemAllocator::sweep() {
     auto isBlack = [this] (const HugeChunk &c) {
         bool b = c.chunk->first()->isBlack();
-        Chunk::clearBit(c.chunk->blackBitmap, c.chunk->first() - c.chunk->realBase());
         if (!b)
             freeHugeChunk(chunkAllocator, c);
         return !b;
@@ -619,6 +674,24 @@ void HugeItemAllocator::sweep() {
     chunks.erase(newEnd, chunks.end());
 }
 
+void HugeItemAllocator::resetBlackBits()
+{
+    for (auto c : chunks)
+        Chunk::clearBit(c.chunk->blackBitmap, c.chunk->first() - c.chunk->realBase());
+}
+
+void HugeItemAllocator::collectGrayItems(ExecutionEngine *engine)
+{
+    for (auto c : chunks)
+        // Correct for a Steele type barrier
+        if (Chunk::testBit(c.chunk->blackBitmap, c.chunk->first() - c.chunk->realBase()) &&
+            Chunk::testBit(c.chunk->grayBitmap, c.chunk->first() - c.chunk->realBase())) {
+            HeapItem *i = c.chunk->first();
+            Heap::Base *b = *i;
+            b->mark(engine);
+        }
+}
+
 void HugeItemAllocator::freeAll()
 {
     for (auto &c : chunks) {
@@ -663,7 +736,8 @@ Heap::Base *MemoryManager::allocString(std::size_t unmanagedSize)
 
     unmanagedHeapSize += unmanagedSize;
     if (unmanagedHeapSize > unmanagedHeapSizeGCLimit) {
-        runGC();
+        if (!didGCRun)
+            runGC();
 
         if (3*unmanagedHeapSizeGCLimit <= 4*unmanagedHeapSize)
             // more than 75% full, raise limit
@@ -681,6 +755,7 @@ Heap::Base *MemoryManager::allocString(std::size_t unmanagedSize)
         m = blockAllocator.allocate(stringSize, true);
     }
 
+//    qDebug() << "allocated string" << m;
     memset(m, 0, stringSize);
     return *m;
 }
@@ -705,8 +780,11 @@ Heap::Base *MemoryManager::allocData(std::size_t size)
 
 //    qDebug() << "unmanagedHeapSize:" << unmanagedHeapSize << "limit:" << unmanagedHeapSizeGCLimit << "unmanagedSize:" << unmanagedSize;
 
-    if (size > Chunk::DataSize)
-        return *hugeItemAllocator.allocate(size);
+    if (size > Chunk::DataSize) {
+        HeapItem *h = hugeItemAllocator.allocate(size);
+//        qDebug() << "allocating huge item" << h;
+        return *h;
+    }
 
     HeapItem *m = blockAllocator.allocate(size);
     if (!m) {
@@ -716,6 +794,7 @@ Heap::Base *MemoryManager::allocData(std::size_t size)
     }
 
     memset(m, 0, size);
+//    qDebug() << "allocating data" << m;
     return *m;
 }
 
@@ -740,6 +819,7 @@ Heap::Object *MemoryManager::allocObjectWithMemberData(std::size_t size, uint nM
         o->memberData->init();
 //        qDebug() << "    got" << o->memberData << o->memberData->size;
     }
+//    qDebug() << "allocating object with memberData" << o << o->memberData.operator->();
     return o;
 }
 
@@ -794,7 +874,13 @@ void MemoryManager::mark()
 {
     Value *markBase = engine->jsStackTop;
 
-    engine->markObjects();
+    if (nextGCIsIncremental) {
+        // need to collect all gray items and push them onto the mark stack
+        blockAllocator.collectGrayItems(engine);
+        hugeItemAllocator.collectGrayItems(engine);
+    }
+
+    engine->markObjects(nextGCIsIncremental);
 
     collectFromJSStack();
 
@@ -836,6 +922,12 @@ void MemoryManager::mark()
 
 void MemoryManager::sweep(bool lastSweep)
 {
+    if (lastSweep && nextGCIsIncremental) {
+        // ensure we properly clean up on destruction even if the GC is in incremental mode
+        blockAllocator.resetBlackBits();
+        hugeItemAllocator.resetBlackBits();
+    }
+
     for (PersistentValueStorage::Iterator it = m_weakValues->begin(); it != m_weakValues->end(); ++it) {
         Managed *m = (*it).managed();
         if (!m || m->markBit())
@@ -915,14 +1007,22 @@ size_t dumpBins(BlockAllocator *b, bool printOutput = true)
     return totalFragmentedSlots*Chunk::SlotSize;
 }
 
-void MemoryManager::runGC()
+void MemoryManager::runGC(bool forceFullCollection)
 {
     if (gcBlocked) {
 //        qDebug() << "Not running GC.";
         return;
     }
 
+    if (forceFullCollection) {
+        // do a full GC
+        blockAllocator.resetBlackBits();
+        hugeItemAllocator.resetBlackBits();
+        nextGCIsIncremental = false;
+    }
+
     QScopedValueRollback<bool> gcBlocker(gcBlocked, true);
+//    qDebug() << "runGC";
 
     if (!gcStats) {
 //        uint oldUsed = allocator.usedMem();
@@ -940,10 +1040,15 @@ void MemoryManager::runGC()
 #ifndef QT_NO_DEBUG
         qDebug() << "    Triggered by alloc request of" << lastAllocRequestedSlots << "slots.";
 #endif
+        qDebug() << "Incremental:" << nextGCIsIncremental;
         qDebug() << "Allocated" << totalMem << "bytes in" << blockAllocator.chunks.size() << "chunks";
         qDebug() << "Fragmented memory before GC" << (totalMem - usedBefore);
         dumpBins(&blockAllocator);
 
+#ifndef QT_NO_DEBUG
+        nGrayItems = 0;
+#endif
+
         QElapsedTimer t;
         t.start();
         mark();
@@ -960,6 +1065,10 @@ void MemoryManager::runGC()
             qDebug() << "   unmanaged heap limit:" << unmanagedHeapSizeGCLimit;
         }
         size_t memInBins = dumpBins(&blockAllocator);
+#ifndef QT_NO_DEBUG
+        if (nextGCIsIncremental)
+            qDebug() << "  number of gray items:" << nGrayItems;
+#endif
         qDebug() << "Marked object in" << markTime << "ms.";
         qDebug() << "Sweeped object in" << sweepTime << "ms.";
         qDebug() << "Used memory before GC:" << usedBefore;
@@ -980,6 +1089,34 @@ void MemoryManager::runGC()
         // ensure we don't 'loose' any memory
         Q_ASSERT(blockAllocator.allocatedMem() == getUsedMem() + dumpBins(&blockAllocator, false));
     }
+
+#if WRITEBARRIER(steele)
+    static int count = 0;
+    ++count;
+    if (aggressiveGC) {
+        nextGCIsIncremental = (count % 256);
+    } else {
+        size_t total = blockAllocator.totalSlots();
+        size_t usedSlots = blockAllocator.usedSlotsAfterLastSweep;
+        if (!nextGCIsIncremental) {
+            // always try an incremental GC after a full one, unless there is anyway lots of memory pressure
+            nextGCIsIncremental = usedSlots * 4 < total * 3;
+            count = 0;
+        } else {
+            if (count > 16)
+                nextGCIsIncremental = false;
+            else
+                nextGCIsIncremental = usedSlots * 4 < total * 3; // less than 75% full
+        }
+    }
+#else
+    nextGCIsIncremental = false;
+#endif
+    if (!nextGCIsIncremental) {
+        // do a full GC
+        blockAllocator.resetBlackBits();
+        hugeItemAllocator.resetBlackBits();
+    }
 }
 
 size_t MemoryManager::getUsedMem() const
diff --git a/src/qml/memory/qv4mm_p.h b/src/qml/memory/qv4mm_p.h
index 3e542b0aa3..f91175e78a 100644
--- a/src/qml/memory/qv4mm_p.h
+++ b/src/qml/memory/qv4mm_p.h
@@ -155,6 +155,8 @@ struct BlockAllocator {
 
     void sweep();
     void freeAll();
+    void resetBlackBits();
+    void collectGrayItems(ExecutionEngine *engine);
 
     // bump allocations
     HeapItem *nextFree = 0;
@@ -176,6 +178,8 @@ struct HugeItemAllocator {
     HeapItem *allocate(size_t size);
     void sweep();
     void freeAll();
+    void resetBlackBits();
+    void collectGrayItems(ExecutionEngine *engine);
 
     size_t usedMem() const {
         size_t used = 0;
@@ -418,7 +422,7 @@ public:
         return t->d();
     }
 
-    void runGC();
+    void runGC(bool forceFullCollection = false);
 
     void dumpStats() const;
 
@@ -463,6 +467,7 @@ public:
     bool gcBlocked = false;
     bool aggressiveGC = false;
     bool gcStats = false;
+    bool nextGCIsIncremental = false;
 };
 
 }
diff --git a/src/qml/memory/qv4mmdefs_p.h b/src/qml/memory/qv4mmdefs_p.h
index 987e669040..75f567b9e5 100644
--- a/src/qml/memory/qv4mmdefs_p.h
+++ b/src/qml/memory/qv4mmdefs_p.h
@@ -176,6 +176,8 @@ struct Chunk {
 
     void sweep();
     void freeAll();
+    void resetBlackBits();
+    void collectGrayItems(ExecutionEngine *engine);
 
     void sortIntoBins(HeapItem **bins, uint nBins);
 };
diff --git a/src/qml/memory/qv4writebarrier_p.h b/src/qml/memory/qv4writebarrier_p.h
index 838ed7a456..de9c63c2ea 100644
--- a/src/qml/memory/qv4writebarrier_p.h
+++ b/src/qml/memory/qv4writebarrier_p.h
@@ -55,8 +55,8 @@
 
 QT_BEGIN_NAMESPACE
 
-#define WRITEBARRIER_steele -1
-#define WRITEBARRIER_none 1
+#define WRITEBARRIER_steele 1
+#define WRITEBARRIER_none -1
 
 #define WRITEBARRIER(x) (1/WRITEBARRIER_##x == 1)
 
@@ -87,8 +87,9 @@ static Q_CONSTEXPR inline bool isRequired() {
 
 inline void write(EngineBase *engine, Heap::Base *base, Value *slot, Value value)
 {
+    Q_UNUSED(engine);
     *slot = value;
-    if (engine->writeBarrierActive && isRequired<Unknown>()) {
+    if (isRequired<Unknown>()) {
         fence();
         base->setGrayBit();
     }
@@ -96,8 +97,9 @@ inline void write(EngineBase *engine, Heap::Base *base, Value *slot, Value value
 
 inline void write(EngineBase *engine, Heap::Base *base, Value *slot, Heap::Base *value)
 {
+    Q_UNUSED(engine);
     *slot = value;
-    if (engine->writeBarrierActive && isRequired<Object>()) {
+    if (isRequired<Object>()) {
         fence();
         base->setGrayBit();
     }
@@ -105,11 +107,10 @@ inline void write(EngineBase *engine, Heap::Base *base, Value *slot, Heap::Base
 
 inline void write(EngineBase *engine, Heap::Base *base, Heap::Base **slot, Heap::Base *value)
 {
+    Q_UNUSED(engine);
     *slot = value;
-    if (engine->writeBarrierActive) {
-        fence();
-        base->setGrayBit();
-    }
+    fence();
+    base->setGrayBit();
 }
 
 #elif WRITEBARRIER(none)
diff --git a/src/qml/qml/v8/qqmlbuiltinfunctions.cpp b/src/qml/qml/v8/qqmlbuiltinfunctions.cpp
index d359a0f62f..ec40c7846d 100644
--- a/src/qml/qml/v8/qqmlbuiltinfunctions.cpp
+++ b/src/qml/qml/v8/qqmlbuiltinfunctions.cpp
@@ -2019,7 +2019,7 @@ void GlobalExtensions::method_qsTrIdNoOp(const BuiltinFunction *, Scope &scope,
 
 void GlobalExtensions::method_gc(const BuiltinFunction *, Scope &scope, CallData *)
 {
-    scope.engine->memoryManager->runGC();
+    scope.engine->memoryManager->runGC(/* forceFullCollection = */ true);
 
     scope.result = QV4::Encode::undefined();
 }