Refactor persistent values

Use a page wise allocation mechanism for persistent
values. This significantly reduces memory consumption
of persistent values and also improves their performance
a lot.

Change-Id: I8499d2ca5bdd871e029f643ae605a94544558bb5
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

1 files changed, 237 insertions, 149 deletions

diff --git a/src/qml/jsruntime/qv4persistent.cpp b/src/qml/jsruntime/qv4persistent.cpp
index 1236d2a469..ff5061d968 100644
--- a/src/qml/jsruntime/qv4persistent.cpp
+++ b/src/qml/jsruntime/qv4persistent.cpp
@@ -34,232 +34,320 @@
 #include "qv4persistent_p.h"
 #include "qv4mm_p.h"
 #include "qv4object_p.h"
+#include "PageAllocation.h"
 
 using namespace QV4;
 
-PersistentValue::PersistentValue(ExecutionEngine *engine, const ValueRef val)
-    : d(new PersistentValuePrivate(val.asReturnedValue(), engine))
+namespace {
+
+struct Page;
+struct Header {
+    WTF::PageAllocation alloc;
+    ExecutionEngine *engine;
+    Page **prev;
+    Page *next;
+    int refCount;
+    int freeList;
+};
+
+enum {
+    PageSize = 4096,
+    NEntries = (PageSize - sizeof(Header))/sizeof(Value)
+};
+struct Page {
+    Header header;
+    Value values[NEntries];
+};
+
+Page *getPage(Value *val) {
+   return reinterpret_cast<Page *>(reinterpret_cast<quintptr>(val) & ~((quintptr)(PageSize - 1)));
+}
+
+
+Page *allocatePage(PersistentValueStorage *storage)
 {
+    PageAllocation page = WTF::PageAllocation::allocate(PageSize);
+    Page *p = reinterpret_cast<Page *>(page.base());
+
+    Q_ASSERT(!((quintptr)p & (PageSize - 1)));
+
+    p->header.engine = storage->engine;
+    p->header.alloc = page;
+    p->header.next = reinterpret_cast<Page *>(storage->firstPage);
+    p->header.prev = reinterpret_cast<Page **>(&storage->firstPage);
+    p->header.refCount = 0;
+    p->header.freeList = 0;
+    if (p->header.next)
+        p->header.next->header.prev = &p->header.next;
+    for (int i = 0; i < NEntries - 1; ++i) {
+        p->values[i].tag = QV4::Value::Empty_Type;
+        p->values[i].int_32 = i + 1;
+    }
+    p->values[NEntries - 1].tag = QV4::Value::Empty_Type;
+    p->values[NEntries - 1].int_32 = -1;
+
+    storage->firstPage = p;
+
+    return p;
+}
+
+
+}
+
+
+PersistentValueStorage::Iterator &PersistentValueStorage::Iterator::operator++() {
+    while (p) {
+        while (index < NEntries - 1) {
+            ++index;
+            if (static_cast<Page *>(p)->values[index].tag != QV4::Value::Empty_Type)
+                return *this;
+        }
+        index = -1;
+        p = static_cast<Page *>(p)->header.next;
+    }
+    index = 0;
+    return *this;
 }
 
-PersistentValue::PersistentValue(ExecutionEngine *engine, ReturnedValue val)
-    : d(new PersistentValuePrivate(val, engine))
+Value &PersistentValueStorage::Iterator::operator *()
 {
+    return static_cast<Page *>(p)->values[index];
 }
 
-PersistentValue::PersistentValue(const PersistentValue &other)
-    : d(other.d)
+PersistentValueStorage::PersistentValueStorage(ExecutionEngine *engine)
+    : engine(engine),
+      firstPage(0)
 {
-    if (d)
-        d->ref();
 }
 
-PersistentValue::~PersistentValue()
+PersistentValueStorage::~PersistentValueStorage()
 {
-    if (d)
-        d->deref();
+    Page *p = static_cast<Page *>(firstPage);
+    while (p) {
+        for (int i = 0; i < NEntries; ++i) {
+            if (!p->values[i].isEmpty())
+                p->values[i] = Encode::undefined();
+        }
+        Page *n = p->header.next;
+        p->header.engine = 0;
+        p->header.prev = 0;
+        p->header.next = 0;
+        Q_ASSERT(p->header.refCount);
+        p = n;
+    }
 }
 
-PersistentValue &PersistentValue::operator=(const PersistentValue &other)
+Value *PersistentValueStorage::allocate()
 {
-    if (d == other.d)
-        return *this;
+    Page *p = static_cast<Page *>(firstPage);
+    while (p) {
+        if (p->header.freeList != -1)
+            break;
+        p = p->header.next;
+    }
+    if (!p)
+        p = allocatePage(this);
 
-    // the memory manager cleans up those with a refcount of 0
+    Value *v = p->values + p->header.freeList;
+    p->header.freeList = v->int_32;
+    ++p->header.refCount;
 
-    if (d)
-        d->deref();
-    d = other.d;
-    if (d)
-        d->ref();
+    v->val = Encode::undefined();
 
-    return *this;
+    return v;
 }
 
-PersistentValue &PersistentValue::operator=(const WeakValue &other)
+void PersistentValueStorage::free(Value *v)
 {
-    QV4::ExecutionEngine *engine = other.engine();
-    if (!d)
-        d = new PersistentValuePrivate(other.value(), engine);
-    else
-        d = d->detach(other.value());
-    return *this;
+    if (!v)
+        return;
+
+    Page *p = getPage(v);
+
+    v->tag = QV4::Value::Empty_Type;
+    v->int_32 = p->header.freeList;
+    p->header.freeList = v - p->values;
+    if (!--p->header.refCount) {
+        if (p->header.prev)
+            *p->header.prev = p->header.next;
+        if (p->header.next)
+            p->header.next->header.prev = p->header.prev;
+        p->header.alloc.deallocate();
+    }
 }
 
-PersistentValue &PersistentValue::operator=(Object *object)
+static void drainMarkStack(QV4::ExecutionEngine *engine, Value *markBase)
 {
-    QV4::ExecutionEngine *engine = object->engine();
-    if (!d)
-        d = new PersistentValuePrivate(object->asReturnedValue(), engine);
-    else
-        d = d->detach(object->asReturnedValue());
-    return *this;
+    while (engine->jsStackTop > markBase) {
+        Heap::Base *h = engine->popForGC();
+        Q_ASSERT (h->gcGetInternalClass()->vtable->markObjects);
+        h->gcGetInternalClass()->vtable->markObjects(h, engine);
+    }
 }
 
-void PersistentValue::set(ExecutionEngine *engine, const ValueRef val)
+void PersistentValueStorage::mark(ExecutionEngine *e)
 {
-    if (!d)
-        d = new PersistentValuePrivate(val.asReturnedValue(), engine);
-    else
-        d = d->detach(val.asReturnedValue());
+    Value *markBase = e->jsStackTop;
+
+    Page *p = static_cast<Page *>(firstPage);
+    while (p) {
+        for (int i = 0; i < NEntries; ++i) {
+            if (Managed *m = p->values[i].asManaged())
+                m->mark(e);
+        }
+        drainMarkStack(e, markBase);
+
+        p = p->header.next;
+    }
 }
 
-void PersistentValue::set(ExecutionEngine *engine, ReturnedValue val)
+ExecutionEngine *PersistentValueStorage::getEngine(Value *v)
 {
-    if (!d)
-        d = new PersistentValuePrivate(val, engine);
-    else
-        d = d->detach(val);
+    return getPage(v)->header.engine;
 }
 
-void PersistentValue::set(ExecutionEngine *engine, Heap::Base *obj)
+
+PersistentValue::PersistentValue(const PersistentValue &other)
+    : val(0)
 {
-    if (!d)
-        d = new PersistentValuePrivate(obj->asReturnedValue(), engine);
-    else
-        d = d->detach(obj->asReturnedValue());
+    if (other.val) {
+        val = other.engine()->memoryManager->m_persistentValues->allocate();
+        *val = *other.val;
+    }
 }
 
-WeakValue::WeakValue(const WeakValue &other)
-    : d(other.d)
+PersistentValue::PersistentValue(ExecutionEngine *engine, const ValueRef value)
 {
-    if (d)
-        d->ref();
+    val = engine->memoryManager->m_persistentValues->allocate();
+    *val = value;
 }
 
-WeakValue &WeakValue::operator=(const WeakValue &other)
+PersistentValue::PersistentValue(ExecutionEngine *engine, ReturnedValue value)
 {
-    if (d == other.d)
-        return *this;
+    val = engine->memoryManager->m_persistentValues->allocate();
+    *val = value;
+}
+
+PersistentValue::~PersistentValue()
+{
+    PersistentValueStorage::free(val);
+}
 
-    // the memory manager cleans up those with a refcount of 0
+PersistentValue &PersistentValue::operator=(const PersistentValue &other)
+{
+    if (!val) {
+        if (!other.val)
+            return *this;
+        val = other.engine()->memoryManager->m_persistentValues->allocate();
+    }
 
-    if (d)
-        d->deref();
-    d = other.d;
-    if (d)
-        d->ref();
+    Q_ASSERT(engine() == other.engine());
 
+    *val = *other.val;
     return *this;
 }
 
-WeakValue::~WeakValue()
+PersistentValue &PersistentValue::operator=(const WeakValue &other)
 {
-    if (d)
-        d->deref();
+    if (!val) {
+        if (!other.valueRef())
+            return *this;
+        val = other.engine()->memoryManager->m_persistentValues->allocate();
+    }
+
+    Q_ASSERT(engine() == other.engine());
+
+    *val = *other.valueRef();
+    return *this;
 }
 
-void WeakValue::set(ExecutionEngine *e, const ValueRef val)
+PersistentValue &PersistentValue::operator=(Object *object)
 {
-    if (!d)
-        d = new PersistentValuePrivate(val.asReturnedValue(), e, /*weak*/true);
-    else
-        d = d->detach(val.asReturnedValue(), /*weak*/true);
+    if (!object) {
+        PersistentValueStorage::free(val);
+        return *this;
+    }
+    if (!val)
+        val = object->engine()->memoryManager->m_persistentValues->allocate();
+
+    *val = object;
+    return *this;
 }
 
-void WeakValue::set(ExecutionEngine *e, ReturnedValue val)
+void PersistentValue::set(ExecutionEngine *engine, const ValueRef value)
 {
-    if (!d)
-        d = new PersistentValuePrivate(val, e, /*weak*/true);
-    else
-        d = d->detach(val, /*weak*/true);
+    if (!val)
+        val = engine->memoryManager->m_persistentValues->allocate();
+    *val = value;
 }
 
-void WeakValue::set(ExecutionEngine *e, Heap::Base *obj)
+void PersistentValue::set(ExecutionEngine *engine, ReturnedValue value)
 {
-    if (!d)
-        d = new PersistentValuePrivate(obj->asReturnedValue(), e, /*weak*/true);
-    else
-        d = d->detach(obj->asReturnedValue(), /*weak*/true);
+    if (!val)
+        val = engine->memoryManager->m_persistentValues->allocate();
+    *val = value;
 }
 
-void WeakValue::markOnce(ExecutionEngine *e)
+void PersistentValue::set(ExecutionEngine *engine, Heap::Base *obj)
 {
-    if (!d)
-        return;
-    d->value.mark(e);
+    if (!val)
+        val = engine->memoryManager->m_persistentValues->allocate();
+    *val = obj;
 }
 
-PersistentValuePrivate::PersistentValuePrivate(ReturnedValue v, ExecutionEngine *e, bool weak)
-    : refcount(1)
-    , weak(weak)
-    , engine(e)
-    , prev(0)
-    , next(0)
+WeakValue::WeakValue(const WeakValue &other)
+    : val(0)
 {
-    value.val = v;
-    init();
+    if (other.val) {
+        val = other.engine()->memoryManager->m_weakValues->allocate();
+        *val = *other.val;
+    }
 }
 
-void PersistentValuePrivate::init()
+WeakValue &WeakValue::operator=(const WeakValue &other)
 {
-    if (!engine) {
-        Managed *m = value.asManaged();
-        if (!m)
-            return;
-
-        engine = m->engine();
-    }
-    if (engine && !prev) {
-        PersistentValuePrivate **listRoot = weak ? &engine->memoryManager->m_weakValues : &engine->memoryManager->m_persistentValues;
-
-        prev = listRoot;
-        next = *listRoot;
-        *prev = this;
-        if (next)
-            next->prev = &this->next;
+    if (!val) {
+        if (!other.val)
+            return *this;
+        val = other.engine()->memoryManager->m_weakValues->allocate();
     }
+
+    Q_ASSERT(engine() == other.engine());
+
+    *val = *other.val;
+    return *this;
 }
 
-PersistentValuePrivate::~PersistentValuePrivate()
+WeakValue::~WeakValue()
 {
+    PersistentValueStorage::free(val);
 }
 
-void PersistentValuePrivate::removeFromList()
+void WeakValue::set(ExecutionEngine *engine, const ValueRef value)
 {
-    if (prev) {
-        if (next)
-            next->prev = prev;
-        *prev = next;
-        next = 0;
-        prev = 0;
-    }
+    if (!val)
+        val = engine->memoryManager->m_weakValues->allocate();
+    *val = value;
 }
 
-void PersistentValuePrivate::deref()
+void WeakValue::set(ExecutionEngine *engine, ReturnedValue value)
 {
-    // if engine is not 0, they are registered with the memory manager
-    // and will get cleaned up in the next gc run
-    if (!--refcount) {
-        removeFromList();
-        delete this;
-    }
+    if (!val)
+        val = engine->memoryManager->m_weakValues->allocate();
+    *val = value;
 }
 
-PersistentValuePrivate *PersistentValuePrivate::detach(const QV4::ReturnedValue val, bool weak)
+void WeakValue::set(ExecutionEngine *engine, Heap::Base *obj)
 {
-    if (refcount == 1) {
-        value.val = val;
-
-        Managed *m = value.asManaged();
-        if (!prev) {
-            if (m) {
-                ExecutionEngine *engine = m->engine();
-                if (engine) {
-                    PersistentValuePrivate **listRoot = weak ? &engine->memoryManager->m_weakValues : &engine->memoryManager->m_persistentValues;
-                    prev = listRoot;
-                    next = *listRoot;
-                    *prev = this;
-                    if (next)
-                        next->prev = &this->next;
-                }
-            }
-        } else if (!m)
-            removeFromList();
-
-        return this;
-    }
-    --refcount;
-    return new PersistentValuePrivate(val, engine, weak);
+    if (!val)
+        val = engine->memoryManager->m_weakValues->allocate();
+    *val = obj;
+}
+
+void WeakValue::markOnce(ExecutionEngine *e)
+{
+    if (!val)
+        return;
+    val->mark(e);
 }