Release the VM of unused heap chunks

This changes the way that available items are linked together to
allow releasing chunks not containing any inUse item after being
swept. Instead of putting a freed item at the top of the stack and
make it link to the item previously at the top, relink all
items !inUse to point to the previously visited unused item during
sweeping.

This allows any chunk to be released in the process while making sure
that no previous or next item will link to an address in that chunk.

The performance penality of relinking the list has been measured
to be ~0.6% with v8-bench.js tst_QJSEngine::largeSweep. In exchange,
this helps keeping the amount of chunks to sweep lower after peaks
of heap allocation, even though that ability will be restrained by
heap fragmentation in long running applications.

Task-number: QTBUG-41099
Change-Id: I81a70f0a930b679a1bef47e630b23dab5f6d1218
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

2 files changed, 98 insertions, 45 deletions

diff --git a/src/qml/jsruntime/qv4mm.cpp b/src/qml/jsruntime/qv4mm.cpp
index 1c46932383..c66a436454 100644
--- a/src/qml/jsruntime/qv4mm.cpp
+++ b/src/qml/jsruntime/qv4mm.cpp
@@ -162,6 +162,65 @@ bool operator<(const MemoryManager::Data::Chunk &a, const MemoryManager::Data::C
 
 } // namespace QV4
 
+namespace {
+
+struct ChunkSweepData {
+    ChunkSweepData() : tail(&head), head(0), isEmpty(true) { }
+    Heap::Base **tail;
+    Heap::Base *head;
+    bool isEmpty;
+};
+
+void sweepChunk(const MemoryManager::Data::Chunk &chunk, ChunkSweepData *sweepData, uint *itemsInUse, ExecutionEngine *engine)
+{
+    char *chunkStart = reinterpret_cast<char*>(chunk.memory.base());
+    std::size_t itemSize = chunk.chunkSize;
+//    qDebug("chunkStart @ %p, size=%x, pos=%x", chunkStart, chunk.chunkSize, chunk.chunkSize>>4);
+
+#ifdef V4_USE_VALGRIND
+    VALGRIND_DISABLE_ERROR_REPORTING;
+#endif
+    for (char *item = chunkStart, *chunkEnd = item + chunk.memory.size() - itemSize; item <= chunkEnd; item += itemSize) {
+        Heap::Base *m = reinterpret_cast<Heap::Base *>(item);
+//        qDebug("chunk @ %p, size = %lu, in use: %s, mark bit: %s",
+//               item, m->size, (m->inUse ? "yes" : "no"), (m->markBit ? "true" : "false"));
+
+        Q_ASSERT((qintptr) item % 16 == 0);
+
+        if (m->markBit) {
+            Q_ASSERT(m->inUse);
+            m->markBit = 0;
+            sweepData->isEmpty = false;
+            ++(*itemsInUse);
+        } else {
+            if (m->inUse) {
+//                qDebug() << "-- collecting it." << m << sweepData->tail << m->nextFree();
+#ifdef V4_USE_VALGRIND
+                VALGRIND_ENABLE_ERROR_REPORTING;
+#endif
+                if (m->internalClass->vtable->destroy)
+                    m->internalClass->vtable->destroy(m);
+
+                memset(m, 0, itemSize);
+#ifdef V4_USE_VALGRIND
+                VALGRIND_DISABLE_ERROR_REPORTING;
+                VALGRIND_MEMPOOL_FREE(this, m);
+#endif
+                Q_V4_PROFILE_DEALLOC(engine, m, itemSize, Profiling::SmallItem);
+                ++(*itemsInUse);
+            }
+            // Relink all free blocks to rewrite references to any released chunk.
+            *sweepData->tail = m;
+            sweepData->tail = m->nextFreeRef();
+        }
+    }
+#ifdef V4_USE_VALGRIND
+    VALGRIND_ENABLE_ERROR_REPORTING;
+#endif
+}
+
+} // namespace
+
 MemoryManager::MemoryManager()
     : m_d(new Data)
     , m_persistentValues(0)
@@ -362,8 +421,43 @@ void MemoryManager::sweep(bool lastSweep)
         }
     }
 
-    for (QVector<Data::Chunk>::iterator i = m_d->heapChunks.begin(), ei = m_d->heapChunks.end(); i != ei; ++i)
-        sweep(reinterpret_cast<char*>(i->memory.base()), i->memory.size(), i->chunkSize);
+    QVarLengthArray<ChunkSweepData> chunkSweepData(m_d->heapChunks.size());
+    uint itemsInUse[MemoryManager::Data::MaxItemSize/16];
+    memset(itemsInUse, 0, sizeof(itemsInUse));
+
+    for (int i = 0; i < m_d->heapChunks.size(); ++i) {
+        const MemoryManager::Data::Chunk &chunk = m_d->heapChunks[i];
+        sweepChunk(chunk, &chunkSweepData[i], &itemsInUse[chunk.chunkSize >> 4], m_d->engine);
+    }
+
+    Heap::Base** tails[MemoryManager::Data::MaxItemSize/16];
+    memset(m_d->smallItems, 0, sizeof(m_d->smallItems));
+    for (int pos = 0; pos < MemoryManager::Data::MaxItemSize/16; ++pos)
+        tails[pos] = &m_d->smallItems[pos];
+
+    QVector<Data::Chunk>::iterator chunkIter = m_d->heapChunks.begin();
+    for (int i = 0; i < chunkSweepData.size(); ++i) {
+        Q_ASSERT(chunkIter != m_d->heapChunks.end());
+        const size_t pos = chunkIter->chunkSize >> 4;
+        const size_t decrease = chunkIter->memory.size()/chunkIter->chunkSize - 1;
+
+        // Release that chunk if it could have been spared since the last GC run without any difference.
+        if (chunkSweepData[i].isEmpty && m_d->availableItems[pos] - decrease >= itemsInUse[pos]) {
+            Q_V4_PROFILE_DEALLOC(m_d->engine, 0, chunkIter->memory.size(), Profiling::HeapPage);
+            --m_d->nChunks[pos];
+            m_d->availableItems[pos] -= uint(decrease);
+            m_d->totalItems -= int(decrease);
+            chunkIter->memory.deallocate();
+            chunkIter = m_d->heapChunks.erase(chunkIter);
+            continue;
+        } else if (chunkSweepData[i].head) {
+            *tails[pos] = chunkSweepData[i].head;
+            tails[pos] = chunkSweepData[i].tail;
+        }
+        ++chunkIter;
+    }
+    for (int pos = 0; pos < MemoryManager::Data::MaxItemSize/16; ++pos)
+        *tails[pos] = 0;
 
     Data::LargeItem *i = m_d->largeItems;
     Data::LargeItem **last = &m_d->largeItems;
@@ -395,48 +489,6 @@ void MemoryManager::sweep(bool lastSweep)
     }
 }
 
-void MemoryManager::sweep(char *chunkStart, std::size_t chunkSize, size_t size)
-{
-//    qDebug("chunkStart @ %p, size=%x, pos=%x (%x)", chunkStart, size, size>>4, m_d->smallItems[size >> 4]);
-    Heap::Base **f = &m_d->smallItems[size >> 4];
-
-#ifdef V4_USE_VALGRIND
-    VALGRIND_DISABLE_ERROR_REPORTING;
-#endif
-    for (char *chunk = chunkStart, *chunkEnd = chunk + chunkSize - size; chunk <= chunkEnd; chunk += size) {
-        Heap::Base *m = reinterpret_cast<Heap::Base *>(chunk);
-//        qDebug("chunk @ %p, size = %lu, in use: %s, mark bit: %s",
-//               chunk, m->size, (m->inUse ? "yes" : "no"), (m->markBit ? "true" : "false"));
-
-        Q_ASSERT((qintptr) chunk % 16 == 0);
-
-        if (m->inUse) {
-            if (m->markBit) {
-                m->markBit = 0;
-            } else {
-//                qDebug() << "-- collecting it." << m << *f << m->nextFree();
-#ifdef V4_USE_VALGRIND
-                VALGRIND_ENABLE_ERROR_REPORTING;
-#endif
-                if (m->internalClass->vtable->destroy)
-                    m->internalClass->vtable->destroy(m);
-
-                memset(m, 0, size);
-                m->setNextFree(*f);
-#ifdef V4_USE_VALGRIND
-                VALGRIND_DISABLE_ERROR_REPORTING;
-                VALGRIND_MEMPOOL_FREE(this, m);
-#endif
-                Q_V4_PROFILE_DEALLOC(m_d->engine, m, size, Profiling::SmallItem);
-                *f = m;
-            }
-        }
-    }
-#ifdef V4_USE_VALGRIND
-    VALGRIND_ENABLE_ERROR_REPORTING;
-#endif
-}
-
 bool MemoryManager::isGCBlocked() const
 {
     return m_d->gcBlocked;
@@ -466,6 +518,7 @@ void MemoryManager::runGC()
         int markTime = t.elapsed();
         t.restart();
         int usedBefore = getUsedMem();
+        int chunksBefore = m_d->heapChunks.size();
         sweep();
         int usedAfter = getUsedMem();
         int sweepTime = t.elapsed();
@@ -477,6 +530,7 @@ void MemoryManager::runGC()
         qDebug() << "Used memory before GC:" << usedBefore;
         qDebug() << "Used memory after GC:" << usedAfter;
         qDebug() << "Freed up bytes:" << (usedBefore - usedAfter);
+        qDebug() << "Released chunks:" << (chunksBefore - m_d->heapChunks.size());
         qDebug() << "======== End GC ========";
     }
 
diff --git a/src/qml/jsruntime/qv4mm_p.h b/src/qml/jsruntime/qv4mm_p.h
index 829429d790..5c21294ad0 100644
--- a/src/qml/jsruntime/qv4mm_p.h
+++ b/src/qml/jsruntime/qv4mm_p.h
@@ -172,7 +172,6 @@ private:
     void collectFromJSStack() const;
     void mark();
     void sweep(bool lastSweep = false);
-    void sweep(char *chunkStart, std::size_t chunkSize, size_t size);
 
 protected:
     QScopedPointer<Data> m_d;