V4: Fix mark stack overruns

Instead of applying a heuristic on when to call drain() in unrelated
code, we check the stack limit on each push(). If the soft limit is
reached we try to drain. As drain() itself can push again, we try to
limit the stack size by allowing at most 65 recursions of drain(). If
none of that helps, we crash with a meaningful error message.

This allows us to remove all the hacky drain() calls in other parts of
the code.

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

7 files changed, 51 insertions, 62 deletions

diff --git a/src/qml/jsruntime/qv4engine.cpp b/src/qml/jsruntime/qv4engine.cpp
index f1b20ce53b..e9cc789607 100644
--- a/src/qml/jsruntime/qv4engine.cpp
+++ b/src/qml/jsruntime/qv4engine.cpp
@@ -1266,20 +1266,15 @@ QUrl ExecutionEngine::resolvedUrl(const QString &file)
 
 void ExecutionEngine::markObjects(MarkStack *markStack)
 {
-    for (int i = 0; i < NClasses; ++i)
-        if (classes[i]) {
-            classes[i]->mark(markStack);
-            if (markStack->top >= markStack->limit)
-                markStack->drain();
-        }
-    markStack->drain();
+    for (int i = 0; i < NClasses; ++i) {
+        if (Heap::InternalClass *c = classes[i])
+            c->mark(markStack);
+    }
 
     identifierTable->markObjects(markStack);
 
-    for (auto compilationUnit: compilationUnits) {
+    for (auto compilationUnit: compilationUnits)
         compilationUnit->markObjects(markStack);
-        markStack->drain();
-    }
 }
 
 ReturnedValue ExecutionEngine::throwError(const Value &value)
diff --git a/src/qml/jsruntime/qv4persistent.cpp b/src/qml/jsruntime/qv4persistent.cpp
index 79c372348f..f4901e3e4d 100644
--- a/src/qml/jsruntime/qv4persistent.cpp
+++ b/src/qml/jsruntime/qv4persistent.cpp
@@ -240,7 +240,6 @@ void PersistentValueStorage::mark(MarkStack *markStack)
             if (Managed *m = p->values[i].as<Managed>())
                 m->mark(markStack);
         }
-        markStack->drain();
 
         p = p->header.next;
     }
diff --git a/src/qml/jsruntime/qv4qobjectwrapper.cpp b/src/qml/jsruntime/qv4qobjectwrapper.cpp
index 9613d064c4..66b79aa0e8 100644
--- a/src/qml/jsruntime/qv4qobjectwrapper.cpp
+++ b/src/qml/jsruntime/qv4qobjectwrapper.cpp
@@ -638,10 +638,11 @@ void QObjectWrapper::markWrapper(QObject *object, MarkStack *markStack)
     if (!ddata)
         return;
 
-    if (ddata->jsEngineId == markStack->engine->m_engineId)
+    const QV4::ExecutionEngine *engine = markStack->engine();
+    if (ddata->jsEngineId == engine->m_engineId)
         ddata->jsWrapper.markOnce(markStack);
-    else  if (markStack->engine->m_multiplyWrappedQObjects && ddata->hasTaintedV4Object)
-        markStack->engine->m_multiplyWrappedQObjects->mark(object, markStack);
+    else if (engine->m_multiplyWrappedQObjects && ddata->hasTaintedV4Object)
+        engine->m_multiplyWrappedQObjects->mark(object, markStack);
 }
 
 void QObjectWrapper::setProperty(ExecutionEngine *engine, int propertyIndex, const Value &value)
diff --git a/src/qml/jsruntime/qv4value_p.h b/src/qml/jsruntime/qv4value_p.h
index ae12033eb4..42e97b1d36 100644
--- a/src/qml/jsruntime/qv4value_p.h
+++ b/src/qml/jsruntime/qv4value_p.h
@@ -537,29 +537,8 @@ struct ValueArray {
     }
 
     void mark(MarkStack *markStack) {
-        Value *v = values;
-        const Value *end = v + alloc;
-        if (alloc > 32*1024) {
-            // drain from time to time to avoid overflows in the js stack
-            Value::HeapBasePtr *currentBase = markStack->top;
-            while (v < end) {
-                v->mark(markStack);
-                ++v;
-                if (markStack->top >= currentBase + 32*1024) {
-                    Value::HeapBasePtr *oldBase = markStack->base;
-                    markStack->base = currentBase;
-                    markStack->drain();
-                    markStack->base = oldBase;
-                }
-            }
-        } else {
-            while (v < end) {
-                v->mark(markStack);
-                if (markStack->top >= markStack->limit)
-                    markStack->drain();
-                ++v;
-            }
-        }
+        for (Value *v = values, *end = values + alloc; v < end; ++v)
+            v->mark(markStack);
     }
 };
 
diff --git a/src/qml/memory/qv4mm.cpp b/src/qml/memory/qv4mm.cpp
index 35b2ff2749..3ed1bc48fd 100644
--- a/src/qml/memory/qv4mm.cpp
+++ b/src/qml/memory/qv4mm.cpp
@@ -848,16 +848,18 @@ Heap::Object *MemoryManager::allocObjectWithMemberData(const QV4::VTable *vtable
 static uint markStackSize = 0;
 
 MarkStack::MarkStack(ExecutionEngine *engine)
-    : engine(engine)
+    : m_engine(engine)
 {
-    base = (Heap::Base **)engine->gcStack->base();
-    top = base;
-    limit = base + engine->maxGCStackSize()/sizeof(Heap::Base)*3/4;
+    m_base = (Heap::Base **)engine->gcStack->base();
+    m_top = m_base;
+    const size_t size = engine->maxGCStackSize() / sizeof(Heap::Base);
+    m_hardLimit = m_base + size;
+    m_softLimit = m_base + size * 3 / 4;
 }
 
 void MarkStack::drain()
 {
-    while (top > base) {
+    while (m_top > m_base) {
         Heap::Base *h = pop();
         ++markStackSize;
         Q_ASSERT(h); // at this point we should only have Heap::Base objects in this area on the stack. If not, weird things might happen.
@@ -904,20 +906,15 @@ void MemoryManager::collectRoots(MarkStack *markStack)
 
         if (keepAlive)
             qobjectWrapper->mark(markStack);
-
-        if (markStack->top >= markStack->limit)
-            markStack->drain();
     }
 }
 
 void MemoryManager::mark()
 {
     markStackSize = 0;
-
     MarkStack markStack(engine);
     collectRoots(&markStack);
-
-    markStack.drain();
+    // dtor of MarkStack drains
 }
 
 void MemoryManager::sweep(bool lastSweep, ClassDestroyStatsCallback classCountPtr)
@@ -1220,8 +1217,6 @@ void MemoryManager::collectFromJSStack(MarkStack *markStack) const
             Q_ASSERT(m->inUse());
             // Skip pointers to already freed objects, they are bogus as well
             m->mark(markStack);
-            if (markStack->top >= markStack->limit)
-                markStack->drain();
         }
         ++v;
     }
diff --git a/src/qml/memory/qv4mmdefs_p.h b/src/qml/memory/qv4mmdefs_p.h
index 8a53492822..117e8f4360 100644
--- a/src/qml/memory/qv4mmdefs_p.h
+++ b/src/qml/memory/qv4mmdefs_p.h
@@ -53,6 +53,7 @@
 #include <private/qv4global_p.h>
 #include <private/qv4runtimeapi_p.h>
 #include <QtCore/qalgorithms.h>
+#include <QtCore/qmath.h>
 #include <qdebug.h>
 
 QT_BEGIN_NAMESPACE
@@ -270,22 +271,41 @@ Q_STATIC_ASSERT(sizeof(HeapItem) == Chunk::SlotSize);
 Q_STATIC_ASSERT(QT_POINTER_SIZE*8 == Chunk::Bits);
 Q_STATIC_ASSERT((1 << Chunk::BitShift) == Chunk::Bits);
 
-struct MarkStack {
+struct Q_QML_PRIVATE_EXPORT MarkStack {
     MarkStack(ExecutionEngine *engine);
-    Heap::Base **top = nullptr;
-    Heap::Base **base = nullptr;
-    Heap::Base **limit = nullptr;
-    ExecutionEngine *engine;
+    ~MarkStack() { drain(); }
+
     void push(Heap::Base *m) {
-        *top = m;
-        ++top;
-    }
-    Heap::Base *pop() {
-        --top;
-        return *top;
+        *(m_top++) = m;
+
+        if (m_top < m_softLimit)
+            return;
+
+        // If at or above soft limit, partition the remaining space into at most 64 segments and
+        // allow one C++ recursion of drain() per segment, plus one for the fence post.
+        const quintptr segmentSize = qNextPowerOfTwo(quintptr(m_hardLimit - m_softLimit) / 64u);
+        if (m_drainRecursion * segmentSize <= quintptr(m_top - m_softLimit)) {
+            ++m_drainRecursion;
+            drain();
+            --m_drainRecursion;
+        } else if (m_top == m_hardLimit) {
+            qFatal("GC mark stack overrun. Either simplify your application or"
+                   "increase QV4_GC_MAX_STACK_SIZE");
+        }
     }
+
+    ExecutionEngine *engine() const { return m_engine; }
+
+private:
+    Heap::Base *pop() { return *(--m_top); }
     void drain();
 
+    Heap::Base **m_top = nullptr;
+    Heap::Base **m_base = nullptr;
+    Heap::Base **m_softLimit = nullptr;
+    Heap::Base **m_hardLimit = nullptr;
+    ExecutionEngine *m_engine = nullptr;
+    quintptr m_drainRecursion = 0;
 };
 
 // Some helper to automate the generation of our
diff --git a/src/qml/qml/qqmlvmemetaobject.cpp b/src/qml/qml/qqmlvmemetaobject.cpp
index edf9657f53..aa9f4bc1bd 100644
--- a/src/qml/qml/qqmlvmemetaobject.cpp
+++ b/src/qml/qml/qqmlvmemetaobject.cpp
@@ -1238,7 +1238,7 @@ void QQmlVMEMetaObject::ensureQObjectWrapper()
 
 void QQmlVMEMetaObject::mark(QV4::MarkStack *markStack)
 {
-    if (engine != markStack->engine)
+    if (engine != markStack->engine())
         return;
 
     propertyAndMethodStorage.markOnce(markStack);