From a6da23bb5f6004e13d22838c7db1246169874930 Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Fri, 6 Apr 2018 16:24:59 +0200 Subject: Garbage collect identifiers Implemented by storing a backpointer to the Heap object in the identifier. Since identifiers now point back to their originating String or Symbol, we can now easily mark all identifiers that are still in use and collect those that aren't. Since Identifiers are 64bit also add support for holding an array index in there. With that an identifier can describe any kind of property that can be accessed in an object. This helps speed up and simplify some code paths. To make this possible, we need to register all IdentifierHash instances with the identifier table, so that we can properly mark those identifiers. Change-Id: Icadbaf5712ab9d252d4e71aa4a520e86b14cd2a0 Reviewed-by: Simon Hausmann --- .../qmldbg_debugger/qv4datacollector.cpp | 2 +- .../qqmlnativedebugservice.cpp | 2 +- src/qml/jsruntime/qv4engine.cpp | 4 +- src/qml/jsruntime/qv4engine_p.h | 5 -- src/qml/jsruntime/qv4global_p.h | 1 + src/qml/jsruntime/qv4identifier.cpp | 48 +++++++++++--- src/qml/jsruntime/qv4identifier_p.h | 35 +++++----- src/qml/jsruntime/qv4identifiertable.cpp | 75 ++++++++++++++++++++-- src/qml/jsruntime/qv4identifiertable_p.h | 20 +++--- src/qml/jsruntime/qv4internalclass.cpp | 10 ++- src/qml/jsruntime/qv4internalclass_p.h | 4 +- src/qml/jsruntime/qv4object.cpp | 2 +- src/qml/jsruntime/qv4string.cpp | 11 +++- src/qml/jsruntime/qv4string_p.h | 9 +++ src/qml/memory/qv4mm.cpp | 3 + src/qml/qml/v8/qv8engine.cpp | 2 +- 16 files changed, 178 insertions(+), 55 deletions(-) (limited to 'src') diff --git a/src/plugins/qmltooling/qmldbg_debugger/qv4datacollector.cpp b/src/plugins/qmltooling/qmldbg_debugger/qv4datacollector.cpp index 9ed96d560f..cc1db7b5ce 100644 --- a/src/plugins/qmltooling/qmldbg_debugger/qv4datacollector.cpp +++ b/src/plugins/qmltooling/qmldbg_debugger/qv4datacollector.cpp @@ -272,7 +272,7 @@ bool QV4DataCollector::collectScope(QJsonObject *dict, int frameNr, int scopeNr) QV4::ScopedValue v(scope); QV4::Heap::InternalClass *ic = ctxt->internalClass(); for (uint i = 0; i < ic->size; ++i) { - QString name = scope.engine->identifierTable->stringForId(ic->nameMap[i])->toQString(); + QString name = ic->nameMap[i].toQString(); names.append(name); v = ctxt->d()->locals[i]; collectedRefs.append(collect(v)); diff --git a/src/plugins/qmltooling/qmldbg_nativedebugger/qqmlnativedebugservice.cpp b/src/plugins/qmltooling/qmldbg_nativedebugger/qqmlnativedebugservice.cpp index 0f064d8371..298608b63e 100644 --- a/src/plugins/qmltooling/qmldbg_nativedebugger/qqmlnativedebugservice.cpp +++ b/src/plugins/qmltooling/qmldbg_nativedebugger/qqmlnativedebugservice.cpp @@ -497,7 +497,7 @@ void NativeDebugger::handleVariables(QJsonObject *response, const QJsonObject &a QV4::Heap::InternalClass *ic = callContext->internalClass(); QV4::ScopedValue v(scope); for (uint i = 0; i < ic->size; ++i) { - QString name = scope.engine->identifierTable->stringForId(ic->nameMap[i])->toQString(); + QString name = ic->nameMap[i].toQString(); v = callContext->d()->locals[i]; collector.collect(&output, QString(), name, v); } diff --git a/src/qml/jsruntime/qv4engine.cpp b/src/qml/jsruntime/qv4engine.cpp index 057a437db7..af752cf243 100644 --- a/src/qml/jsruntime/qv4engine.cpp +++ b/src/qml/jsruntime/qv4engine.cpp @@ -919,8 +919,6 @@ void ExecutionEngine::requireArgumentsAccessors(int n) void ExecutionEngine::markObjects(MarkStack *markStack) { - identifierTable->mark(markStack); - for (int i = 0; i < nArgumentsAccessors; ++i) { const Property &pd = argumentsAccessors[i]; if (Heap::FunctionObject *getter = pd.getter()) @@ -934,6 +932,8 @@ void ExecutionEngine::markObjects(MarkStack *markStack) classes[i]->mark(markStack); markStack->drain(); + identifierTable->markObjects(markStack); + for (auto compilationUnit: compilationUnits) { compilationUnit->markObjects(markStack); markStack->drain(); diff --git a/src/qml/jsruntime/qv4engine_p.h b/src/qml/jsruntime/qv4engine_p.h index 69c62261d2..4316967484 100644 --- a/src/qml/jsruntime/qv4engine_p.h +++ b/src/qml/jsruntime/qv4engine_p.h @@ -157,11 +157,6 @@ public: QV8Engine *v8Engine; QJSEngine *publicEngine; -private: - quintptr currentIdentifier = 0; -public: - Identifier nextIdentifier() { return Identifier{ ++currentIdentifier }; } - enum JSObjects { RootContext, IntegerNull, // Has to come after the RootContext to make the context stack safe diff --git a/src/qml/jsruntime/qv4global_p.h b/src/qml/jsruntime/qv4global_p.h index d9660869f4..6820042406 100644 --- a/src/qml/jsruntime/qv4global_p.h +++ b/src/qml/jsruntime/qv4global_p.h @@ -252,6 +252,7 @@ typedef Scoped ScopedContext; struct PersistentValueStorage; class PersistentValue; class WeakValue; +struct MarkStack; struct IdentifierTable; class RegExpCache; diff --git a/src/qml/jsruntime/qv4identifier.cpp b/src/qml/jsruntime/qv4identifier.cpp index 0bde74b718..1be24917db 100644 --- a/src/qml/jsruntime/qv4identifier.cpp +++ b/src/qml/jsruntime/qv4identifier.cpp @@ -44,6 +44,16 @@ QT_BEGIN_NAMESPACE namespace QV4 { +QString Identifier::toQString() const +{ + if (isArrayIndex()) + return QString::number(asArrayIndex()); + Heap::Base *b = asHeapObject(); + Q_ASSERT(b->internalClass->vtable->isStringOrSymbol); + Heap::StringOrSymbol *s = static_cast(b); + return s->toQString(); +} + static const uchar prime_deltas[] = { 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 @@ -55,14 +65,16 @@ static inline int primeForNumBits(int numBits) } -IdentifierHashData::IdentifierHashData(int numBits) +IdentifierHashData::IdentifierHashData(IdentifierTable *table, int numBits) : size(0) , numBits(numBits) + , identifierTable(table) { refCount.store(1); alloc = primeForNumBits(numBits); entries = (IdentifierHashEntry *)malloc(alloc*sizeof(IdentifierHashEntry)); memset(entries, 0, alloc*sizeof(IdentifierHashEntry)); + identifierTable->addIdentifierHash(this); } IdentifierHashData::IdentifierHashData(IdentifierHashData *other) @@ -74,12 +86,18 @@ IdentifierHashData::IdentifierHashData(IdentifierHashData *other) alloc = other->alloc; entries = (IdentifierHashEntry *)malloc(alloc*sizeof(IdentifierHashEntry)); memcpy(entries, other->entries, alloc*sizeof(IdentifierHashEntry)); + identifierTable->addIdentifierHash(this); +} + +IdentifierHashData::~IdentifierHashData() { + free(entries); + if (identifierTable) + identifierTable->removeIdentifierHash(this); } IdentifierHash::IdentifierHash(ExecutionEngine *engine) { - d = new IdentifierHashData(3); - d->identifierTable = engine->identifierTable; + d = new IdentifierHashData(engine->identifierTable, 3); } void IdentifierHash::detach() @@ -95,6 +113,8 @@ void IdentifierHash::detach() IdentifierHashEntry *IdentifierHash::addEntry(Identifier identifier) { + Q_ASSERT(identifier.isValid()); + // fill up to max 50% bool grow = (d->alloc <= d->size*2); @@ -105,7 +125,7 @@ IdentifierHashEntry *IdentifierHash::addEntry(Identifier identifier) memset(newEntries, 0, newAlloc*sizeof(IdentifierHashEntry)); for (int i = 0; i < d->alloc; ++i) { const IdentifierHashEntry &e = d->entries[i]; - if (!e.identifier) + if (!e.identifier.isValid()) continue; uint idx = e.identifier.id % newAlloc; while (newEntries[idx].identifier.isValid()) { @@ -132,13 +152,13 @@ IdentifierHashEntry *IdentifierHash::addEntry(Identifier identifier) const IdentifierHashEntry *IdentifierHash::lookup(Identifier identifier) const { - if (!d) + if (!d || !identifier.isValid()) return nullptr; Q_ASSERT(d->entries); uint idx = identifier.id % d->alloc; while (1) { - if (!d->entries[idx].identifier) + if (!d->entries[idx].identifier.isValid()) return nullptr; if (d->entries[idx].identifier == identifier) return d->entries + idx; @@ -160,8 +180,9 @@ const IdentifierHashEntry *IdentifierHash::lookup(String *str) const { if (!d) return nullptr; - if (str->d()->identifier.isValid()) - return lookup(str->d()->identifier); + Identifier id = d->identifierTable->identifier(str); + if (id.isValid()) + return lookup(id); return lookup(str->toQString()); } @@ -189,6 +210,17 @@ QString QV4::IdentifierHash::findId(int value) const return QString(); } +void IdentifierHashData::markObjects(MarkStack *markStack) const +{ + IdentifierHashEntry *e = entries; + IdentifierHashEntry *end = e + alloc; + while (e < end) { + if (Heap::Base *o = e->identifier.asHeapObject()) + o->mark(markStack); + ++e; + } +} + } diff --git a/src/qml/jsruntime/qv4identifier_p.h b/src/qml/jsruntime/qv4identifier_p.h index 660cc2db05..b167a149a2 100644 --- a/src/qml/jsruntime/qv4identifier_p.h +++ b/src/qml/jsruntime/qv4identifier_p.h @@ -51,26 +51,30 @@ // #include +#include QT_BEGIN_NAMESPACE namespace QV4 { -namespace Heap { - struct String; -} - -struct String; -struct IdentifierTable; -struct ExecutionEngine; - struct Identifier { - quintptr id; + // id's are either pointers to Heap::String or Heap::Symbol from the Identifier table. + // For Symbol is can simply point to itself. + // This gives us automative GC'ing of identifiers + // In addition, an identifier can have the lowest bit set, and then indicates an array index + quint64 id; + + static Identifier invalid() { return Identifier{ 0 }; } + static Identifier fromArrayIndex(uint idx) { return Identifier{ (quint64(idx) << 1) | 1 }; } + bool isValid() const { return id && !(id & 1); } + uint asArrayIndex() const { return (id & 1) ? (id >> 1) : std::numeric_limits::max(); } + uint isArrayIndex() const { return (id & 1); } + static Identifier fromHeapObject(Heap::Base *b) { return Identifier{ reinterpret_cast(b) }; } + Heap::Base *asHeapObject() const { return (id & 1) ? nullptr : reinterpret_cast(id); } + + Q_QML_EXPORT QString toQString() const; - static Identifier invalid() { return Identifier{0}; } - bool isValid() const { return id != 0; } - bool operator !() const { return id == 0; } bool operator ==(const Identifier &other) const { return id == other.id; } bool operator !=(const Identifier &other) const { return id != other.id; } bool operator <(const Identifier &other) const { return id < other.id; } @@ -84,11 +88,10 @@ struct IdentifierHashEntry { struct IdentifierHashData { - IdentifierHashData(int numBits); + IdentifierHashData(IdentifierTable *table, int numBits); explicit IdentifierHashData(IdentifierHashData *other); - ~IdentifierHashData() { - free(entries); - } + ~IdentifierHashData(); + void markObjects(MarkStack *markStack) const; QBasicAtomicInt refCount; int alloc; diff --git a/src/qml/jsruntime/qv4identifiertable.cpp b/src/qml/jsruntime/qv4identifiertable.cpp index 2cfdd81c87..46c631476a 100644 --- a/src/qml/jsruntime/qv4identifiertable.cpp +++ b/src/qml/jsruntime/qv4identifiertable.cpp @@ -69,6 +69,8 @@ IdentifierTable::~IdentifierTable() { free(entriesByHash); free(entriesById); + for (auto &h : idHashes) + h->identifierTable = nullptr; } void IdentifierTable::addEntry(Heap::String *str) @@ -78,7 +80,7 @@ void IdentifierTable::addEntry(Heap::String *str) if (str->subtype == Heap::String::StringType_ArrayIndex) return; - str->identifier = engine->nextIdentifier(); + str->identifier = Identifier::fromHeapObject(str); bool grow = (alloc <= size*2); @@ -164,8 +166,10 @@ Identifier IdentifierTable::identifierImpl(const Heap::String *str) if (str->identifier.isValid()) return str->identifier; uint hash = str->hashValue(); - if (str->subtype == Heap::String::StringType_ArrayIndex) - return Identifier::invalid(); + if (str->subtype == Heap::String::StringType_ArrayIndex) { + str->identifier = Identifier::fromArrayIndex(hash); + return str->identifier; + } uint idx = hash % alloc; while (Heap::String *e = entriesByHash[idx]) { @@ -183,7 +187,10 @@ Identifier IdentifierTable::identifierImpl(const Heap::String *str) Heap::String *IdentifierTable::stringForId(Identifier i) const { - if (!i) + uint arrayIdx = i.asArrayIndex(); + if (arrayIdx < UINT_MAX) + return engine->newString(QString::number(arrayIdx)); + if (!i.isValid()) return nullptr; uint idx = i.id % alloc; @@ -197,6 +204,66 @@ Heap::String *IdentifierTable::stringForId(Identifier i) const } } +void IdentifierTable::markObjects(MarkStack *markStack) +{ + for (const auto &h : idHashes) + h->markObjects(markStack); +} + +template +int sweepTable(Heap::String **table, int alloc, std::function f) { + int freed = 0; + Key lastKey = 0; + int lastEntry = -1; + int start = 0; + // start at an empty entry so we compress properly + for (; start < alloc; ++start) { + if (!table[start]) + break; + } + + for (int i = 0; i < alloc; ++i) { + int idx = (i + start) % alloc; + Heap::String *entry = table[idx]; + if (!entry) { + lastEntry = -1; + continue; + } + if (entry->isMarked()) { + if (lastEntry >= 0 && lastKey == f(entry)) { + Q_ASSERT(table[lastEntry] == nullptr); + table[lastEntry] = entry; + table[idx] = nullptr; + lastEntry = (lastEntry + 1) % alloc; + Q_ASSERT(table[lastEntry] == nullptr); + } + continue; + } + if (lastEntry == -1) { + lastEntry = idx; + lastKey = f(entry); + } + table[idx] = nullptr; + ++freed; + } + for (int i = 0; i < alloc; ++i) { + Heap::String *entry = table[i]; + if (!entry) + continue; + Q_ASSERT(entry->isMarked()); + } + return freed; +} + +void IdentifierTable::sweep() +{ + int f = sweepTable(entriesByHash, alloc, [](Heap::String *entry) {return entry->hashValue(); }); + int freed = sweepTable(entriesById, alloc, [](Heap::String *entry) {return entry->identifier.id; }); + Q_UNUSED(f); + Q_ASSERT(f == freed); + size -= freed; +} + Identifier IdentifierTable::identifier(const QString &s) { return insertString(s)->identifier; diff --git a/src/qml/jsruntime/qv4identifiertable_p.h b/src/qml/jsruntime/qv4identifiertable_p.h index dce270e337..84e1ef2f4f 100644 --- a/src/qml/jsruntime/qv4identifiertable_p.h +++ b/src/qml/jsruntime/qv4identifiertable_p.h @@ -53,6 +53,7 @@ #include "qv4identifier_p.h" #include "qv4string_p.h" #include "qv4engine_p.h" +#include #include QT_BEGIN_NAMESPACE @@ -69,6 +70,8 @@ struct IdentifierTable Heap::String **entriesByHash; Heap::String **entriesById; + QSet idHashes; + void addEntry(Heap::String *str); public: @@ -94,15 +97,14 @@ public: Q_QML_PRIVATE_EXPORT Heap::String *stringForId(Identifier i) const; - void mark(MarkStack *markStack) { - for (int i = 0; i < alloc; ++i) { - Heap::String *entry = entriesByHash[i]; - if (!entry || entry->isMarked()) - continue; - entry->setMarkBit(); - Q_ASSERT(entry->vtable()->markObjects); - entry->vtable()->markObjects(entry, markStack); - } + void markObjects(MarkStack *markStack); + void sweep(); + + void addIdentifierHash(IdentifierHashData *h) { + idHashes.insert(h); + } + void removeIdentifierHash(IdentifierHashData *h) { + idHashes.remove(h); } }; diff --git a/src/qml/jsruntime/qv4internalclass.cpp b/src/qml/jsruntime/qv4internalclass.cpp index 40b57e76e1..da37fda590 100644 --- a/src/qml/jsruntime/qv4internalclass.cpp +++ b/src/qml/jsruntime/qv4internalclass.cpp @@ -122,7 +122,7 @@ void PropertyHash::detach(bool grow, int classSize) PropertyHashData *dd = new PropertyHashData(grow ? d->numBits + 1 : d->numBits); for (int i = 0; i < d->alloc; ++i) { const Entry &e = d->entries[i]; - if (!e.identifier || e.index >= static_cast(classSize)) + if (!e.identifier.isValid() || e.index >= static_cast(classSize)) continue; uint idx = e.identifier.id % dd->alloc; while (dd->entries[idx].identifier.isValid()) { @@ -294,7 +294,7 @@ Heap::InternalClass *InternalClass::changeMember(Identifier identifier, Property for (uint i = 0; i < size; ++i) { Identifier identifier = nameMap.at(i); PropertyHash::Entry e = { identifier, newClass->size }; - if (!identifier) + if (!identifier.isValid()) e.identifier = nameMap.at(i - 1); newClass->propertyTable.addEntry(e, newClass->size); newClass->nameMap.add(newClass->size, identifier); @@ -630,6 +630,12 @@ void InternalClass::markObjects(Heap::Base *b, MarkStack *stack) ic->prototype->mark(stack); if (ic->parent) ic->parent->mark(stack); + + for (uint i = 0; i < ic->size; ++i) { + Identifier id = ic->nameMap.at(i); + if (Heap::Base *b = id.asHeapObject()) + b->mark(stack); + } } } diff --git a/src/qml/jsruntime/qv4internalclass_p.h b/src/qml/jsruntime/qv4internalclass_p.h index a2c7620910..290251f4ba 100644 --- a/src/qml/jsruntime/qv4internalclass_p.h +++ b/src/qml/jsruntime/qv4internalclass_p.h @@ -134,7 +134,7 @@ inline uint PropertyHash::lookup(Identifier identifier) const while (1) { if (d->entries[idx].identifier == identifier) return d->entries[idx].index; - if (!d->entries[idx].identifier) + if (!d->entries[idx].identifier.isValid()) return UINT_MAX; ++idx; idx %= d->alloc; @@ -258,8 +258,6 @@ struct InternalClassTransition { return id < other.id || (id == other.id && flags < other.flags); } }; -static_assert(sizeof(Identifier) == sizeof(VTable *), "Identifier needs to be one pointer large to map into the union above"); - namespace Heap { struct InternalClass : Base { diff --git a/src/qml/jsruntime/qv4object.cpp b/src/qml/jsruntime/qv4object.cpp index 59540611b1..a896caaecb 100644 --- a/src/qml/jsruntime/qv4object.cpp +++ b/src/qml/jsruntime/qv4object.cpp @@ -531,7 +531,7 @@ void Object::advanceIterator(Managed *m, ObjectIterator *it, Value *name, uint * while (it->memberIndex < o->internalClass()->size) { Identifier n = o->internalClass()->nameMap.at(it->memberIndex); - if (!n) { + if (!n.isValid()) { // accessor properties have a dummy entry with n == 0 ++it->memberIndex; continue; diff --git a/src/qml/jsruntime/qv4string.cpp b/src/qml/jsruntime/qv4string.cpp index d14dfd082f..81044103eb 100644 --- a/src/qml/jsruntime/qv4string.cpp +++ b/src/qml/jsruntime/qv4string.cpp @@ -52,9 +52,17 @@ using namespace QV4; #ifndef V4_BOOTSTRAP +void Heap::StringOrSymbol::markObjects(Heap::Base *that, MarkStack *markStack) +{ + StringOrSymbol *s = static_cast(that); + Heap::Base *id = s->identifier.asHeapObject(); + if (id) + id->mark(markStack); +} + void Heap::String::markObjects(Heap::Base *that, MarkStack *markStack) { - Base::markObjects(that, markStack); + StringOrSymbol::markObjects(that, markStack); String *s = static_cast(that); if (s->subtype < StringType_Complex) return; @@ -250,4 +258,3 @@ uint String::toArrayIndex(const QString &str) { return QV4::String::toArrayIndex(str.constData(), str.constData() + str.length()); } - diff --git a/src/qml/jsruntime/qv4string_p.h b/src/qml/jsruntime/qv4string_p.h index a1763522b5..4e35853f69 100644 --- a/src/qml/jsruntime/qv4string_p.h +++ b/src/qml/jsruntime/qv4string_p.h @@ -68,6 +68,15 @@ struct Q_QML_PRIVATE_EXPORT StringOrSymbol : Base { mutable QStringData *text; mutable Identifier identifier; + static void markObjects(Heap::Base *that, MarkStack *markStack); + + inline QString toQString() const { + if (!text) + return QString(); + QStringDataPtr ptr = { text }; + text->ref.ref(); + return QString(ptr); + } }; struct Q_QML_PRIVATE_EXPORT String : StringOrSymbol { diff --git a/src/qml/memory/qv4mm.cpp b/src/qml/memory/qv4mm.cpp index 06313c3d30..795fb84ec4 100644 --- a/src/qml/memory/qv4mm.cpp +++ b/src/qml/memory/qv4mm.cpp @@ -42,6 +42,7 @@ #include "qv4objectproto_p.h" #include "qv4mm_p.h" #include "qv4qobjectwrapper_p.h" +#include "qv4identifiertable_p.h" #include #include #include @@ -1019,7 +1020,9 @@ void MemoryManager::sweep(bool lastSweep, ClassDestroyStatsCallback classCountPt } } + if (!lastSweep) { + engine->identifierTable->sweep(); blockAllocator.sweep(/*classCountPtr*/); hugeItemAllocator.sweep(classCountPtr); icAllocator.sweep(/*classCountPtr*/); diff --git a/src/qml/qml/v8/qv8engine.cpp b/src/qml/qml/v8/qv8engine.cpp index 81f1f89c92..350d9b09a2 100644 --- a/src/qml/qml/v8/qv8engine.cpp +++ b/src/qml/qml/v8/qv8engine.cpp @@ -241,7 +241,7 @@ static void freeze_recursive(QV4::ExecutionEngine *v4, QV4::Object *object) QV4::ScopedObject o(scope); for (uint i = 0; i < frozen->size; ++i) { - if (!frozen->nameMap.at(i)) + if (!frozen->nameMap.at(i).isValid()) continue; o = *object->propertyData(i); if (o) -- cgit v1.2.3