Fix invalid object property key conversions

Different property names are mapped to the same property key through a
the identifier hash table. In the case of QTBUG-69280 we map a for-in
loop "for (var prop in testCase)" in TestCase.qml to an internal
iterator object, which signals whether it's finished or not by setting a
"done" property on the iterator result object to a boolean. On the
setter side, the property is specified via

  result->put(engine->newString("done"))

and on the getter side the code uses

  result->get(engine->id_done())

For this to work, the newly created string has to map to the same
identifier, otherwise we end up with differing property keys and wrong
values.

The test failure of QTBUG-69280 reproduced a scenario where two strings,
"pathChanged" and "done", mapped to the same index in the hash table
after a rehashing (growing), despite different string hash values. As a
consequence of the hash collision they had adjacent entries in the hash
table, with "pathChanged" coming first.

A subsequent garbage collection run ended up with "pathChanged" being
not marked and subject to removal from the identifier table.
IdentifierTable::sweep() wiped the entry for "pathChanged" and lastEntry
to the now free index and also remembered the exact string hash value.
In the next iteration, sweep() looked at the entry for "done", which
should move to the now free slot, as both strings map to the same index.
However sweep() didn't do that because the comparison of string hash
values failed.

The fix is to compare table indices (covered by
sweepFirstEntryInSameBucketWithDifferingHash) and respect bucket boundaries
(covered by dontSweepAcrossBucketBoundaries).

However it may happen that entries that would map to the same bucket end
up after another bucket because of the insertion order. This would lead
to

    Q_ASSERT(table[lastIdx] == nullptr);

failing right after

    lastIdx = (lastIdx + 1) % alloc;

Instead the determination of the next free slot must follow the same
logic as in addEntry, by finding the first null entry. This is covered
by sweepAcrossBucketBoundariesIfFirstBucketFull.

Task-number: QTBUG-69280
Change-Id: I284f53418d0a75e2edb631f8bacca8c5a596e603
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Ulf Hermann <ulf.hermann@qt.io>

5 files changed, 330 insertions, 12 deletions

diff --git a/src/qml/jsruntime/qv4identifiertable.cpp b/src/qml/jsruntime/qv4identifiertable.cpp
index c1457b2769..0412695404 100644
--- a/src/qml/jsruntime/qv4identifiertable.cpp
+++ b/src/qml/jsruntime/qv4identifiertable.cpp
@@ -54,10 +54,10 @@ static inline int primeForNumBits(int numBits)
 }
 
 
-IdentifierTable::IdentifierTable(ExecutionEngine *engine)
+IdentifierTable::IdentifierTable(ExecutionEngine *engine, int numBits)
     : engine(engine)
     , size(0)
-    , numBits(8)
+    , numBits(numBits)
 {
     alloc = primeForNumBits(numBits);
     entriesByHash = (Heap::StringOrSymbol **)malloc(alloc*sizeof(Heap::StringOrSymbol *));
@@ -255,7 +255,8 @@ void IdentifierTable::markObjects(MarkStack *markStack)
 template <typename Key>
 int sweepTable(Heap::StringOrSymbol **table, int alloc, std::function<Key(Heap::StringOrSymbol *)> f) {
     int freed = 0;
-    Key lastKey = 0;
+    uint lastKey = 0;
+
     int lastEntry = -1;
     int start = 0;
     // start at an empty entry so we compress properly
@@ -272,18 +273,21 @@ int sweepTable(Heap::StringOrSymbol **table, int alloc, std::function<Key(Heap::
             continue;
         }
         if (entry->isMarked()) {
-            if (lastEntry >= 0 && lastKey == f(entry)) {
+            if (lastEntry >= 0 && lastKey == (f(entry) % alloc)) {
                 Q_ASSERT(table[lastEntry] == nullptr);
                 table[lastEntry] = entry;
                 table[idx] = nullptr;
-                lastEntry = (lastEntry + 1) % alloc;
-                Q_ASSERT(table[lastEntry] == nullptr);
+
+                // find next free slot just like in addEntry()
+                do {
+                    lastEntry = (lastEntry + 1) % alloc;
+                } while (table[lastEntry] != nullptr);
             }
             continue;
         }
         if (lastEntry == -1) {
             lastEntry = idx;
-            lastKey = f(entry);
+            lastKey = f(entry) % alloc;
         }
         table[idx] = nullptr;
         ++freed;
@@ -299,7 +303,7 @@ int sweepTable(Heap::StringOrSymbol **table, int alloc, std::function<Key(Heap::
 
 void IdentifierTable::sweep()
 {
-    int f = sweepTable<int>(entriesByHash, alloc, [](Heap::StringOrSymbol *entry) {return entry->hashValue(); });
+    int f = sweepTable<uint>(entriesByHash, alloc, [](Heap::StringOrSymbol *entry) {return entry->hashValue(); });
     int freed = sweepTable<quint64>(entriesById, alloc, [](Heap::StringOrSymbol *entry) {return entry->identifier.id(); });
     Q_UNUSED(f);
     Q_ASSERT(f == freed);
diff --git a/src/qml/jsruntime/qv4identifiertable_p.h b/src/qml/jsruntime/qv4identifiertable_p.h
index 4f1656dddf..3674ece84f 100644
--- a/src/qml/jsruntime/qv4identifiertable_p.h
+++ b/src/qml/jsruntime/qv4identifiertable_p.h
@@ -60,7 +60,7 @@ QT_BEGIN_NAMESPACE
 
 namespace QV4 {
 
-struct IdentifierTable
+struct Q_QML_PRIVATE_EXPORT IdentifierTable
 {
     ExecutionEngine *engine;
 
@@ -76,7 +76,7 @@ struct IdentifierTable
 
 public:
 
-    IdentifierTable(ExecutionEngine *engine);
+    IdentifierTable(ExecutionEngine *engine, int numBits = 8);
     ~IdentifierTable();
 
     Heap::String *insertString(const QString &s);
@@ -97,8 +97,8 @@ public:
     PropertyKey asPropertyKeyImpl(const Heap::String *str);
 
     Heap::StringOrSymbol *resolveId(PropertyKey i) const;
-    Q_QML_PRIVATE_EXPORT Heap::String *stringForId(PropertyKey i) const;
-    Q_QML_PRIVATE_EXPORT Heap::Symbol *symbolForId(PropertyKey i) const;
+    Heap::String *stringForId(PropertyKey i) const;
+    Heap::Symbol *symbolForId(PropertyKey i) const;
 
     void markObjects(MarkStack *markStack);
     void sweep();
diff --git a/tests/auto/qml/qml.pro b/tests/auto/qml/qml.pro
index 3433b56864..1bd23573b0 100644
--- a/tests/auto/qml/qml.pro
+++ b/tests/auto/qml/qml.pro
@@ -71,6 +71,7 @@ PRIVATETESTS += \
     qqmlobjectmodel \
     qv4assembler \
     qv4mm \
+    qv4identifiertable \
     ecmascripttests \
     bindingdependencyapi
 
diff --git a/tests/auto/qml/qv4identifiertable/qv4identifiertable.pro b/tests/auto/qml/qv4identifiertable/qv4identifiertable.pro
new file mode 100644
index 0000000000..64dc822367
--- /dev/null
+++ b/tests/auto/qml/qv4identifiertable/qv4identifiertable.pro
@@ -0,0 +1,8 @@
+CONFIG += testcase
+TARGET = tst_qv4identifiertable
+macos:CONFIG -= app_bundle
+
+SOURCES += tst_qv4identifiertable.cpp
+
+QT += qml qml-private testlib
+
diff --git a/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp b/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp
new file mode 100644
index 0000000000..b2908ac5bb
--- /dev/null
+++ b/tests/auto/qml/qv4identifiertable/tst_qv4identifiertable.cpp
@@ -0,0 +1,305 @@
+/****************************************************************************
+**
+** Copyright (C) 2016 basysKom GmbH.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:GPL-EXCEPT$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3 as published by the Free Software
+** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <qtest.h>
+#include <QQmlEngine>
+#include <private/qv4identifiertable_p.h>
+
+class tst_qv4identifiertable : public QObject
+{
+    Q_OBJECT
+
+private slots:
+    void sweepFirstEntryInBucket();
+    void sweepCenterEntryInBucket();
+    void sweepLastEntryInBucket();
+    void sweepFirstEntryInSameBucketWithDifferingHash();
+    void dontSweepAcrossBucketBoundaries();
+    void sweepAcrossBucketBoundariesIfFirstBucketFull();
+};
+
+void tst_qv4identifiertable::sweepFirstEntryInBucket()
+{
+    QV4::ExecutionEngine engine;
+    QV4::IdentifierTable table(&engine, /*numBits*/1);
+
+    auto entry1 = engine.newString(QStringLiteral("one"));
+    auto entry2 = engine.newString(QStringLiteral("two"));
+    auto entry3 = engine.newString(QStringLiteral("three"));
+
+    entry1->createHashValue();
+    entry2->createHashValue();
+    entry3->createHashValue();
+
+    // All strings go into the same bucket
+    entry1->stringHash = 0;
+    entry2->stringHash = 0;
+    entry3->stringHash = 0;
+
+    // trigger insertion
+    table.asPropertyKey(entry1);
+    table.asPropertyKey(entry2);
+    table.asPropertyKey(entry3);
+
+    QCOMPARE(table.size, 3);
+    QCOMPARE(table.alloc, 5);
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], entry3);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+
+    // first entry not marked
+    entry2->setMarkBit();
+    entry3->setMarkBit();
+
+    table.sweep();
+
+    QCOMPARE(table.entriesByHash[0], entry2);
+    QCOMPARE(table.entriesByHash[1], entry3);
+    QCOMPARE(table.entriesByHash[2], nullptr);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+}
+
+void tst_qv4identifiertable::sweepCenterEntryInBucket()
+{
+    QV4::ExecutionEngine engine;
+    QV4::IdentifierTable table(&engine, /*numBits*/1);
+
+    auto entry1 = engine.newString(QStringLiteral("one"));
+    auto entry2 = engine.newString(QStringLiteral("two"));
+    auto entry3 = engine.newString(QStringLiteral("three"));
+
+    entry1->createHashValue();
+    entry2->createHashValue();
+    entry3->createHashValue();
+
+    // All strings go into the same bucket
+    entry1->stringHash = 0;
+    entry2->stringHash = 0;
+    entry3->stringHash = 0;
+
+    // trigger insertion
+    table.asPropertyKey(entry1);
+    table.asPropertyKey(entry2);
+    table.asPropertyKey(entry3);
+
+    QCOMPARE(table.size, 3);
+    QCOMPARE(table.alloc, 5);
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], entry3);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+
+    entry1->setMarkBit();
+    // second entry not marked
+    entry3->setMarkBit();
+
+    table.sweep();
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry3);
+    QCOMPARE(table.entriesByHash[2], nullptr);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+}
+
+void tst_qv4identifiertable::sweepLastEntryInBucket()
+{
+    QV4::ExecutionEngine engine;
+    QV4::IdentifierTable table(&engine, /*numBits*/1);
+
+    auto entry1 = engine.newString(QStringLiteral("one"));
+    auto entry2 = engine.newString(QStringLiteral("two"));
+    auto entry3 = engine.newString(QStringLiteral("three"));
+
+    entry1->createHashValue();
+    entry2->createHashValue();
+    entry3->createHashValue();
+
+    // All strings go into the same bucket
+    entry1->stringHash = 0;
+    entry2->stringHash = 0;
+    entry3->stringHash = 0;
+
+    // trigger insertion
+    table.asPropertyKey(entry1);
+    table.asPropertyKey(entry2);
+    table.asPropertyKey(entry3);
+
+    QCOMPARE(table.size, 3);
+    QCOMPARE(table.alloc, 5);
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], entry3);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+
+    entry1->setMarkBit();
+    entry2->setMarkBit();
+    // third entry not marked
+
+    table.sweep();
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], nullptr);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+}
+
+void tst_qv4identifiertable::sweepFirstEntryInSameBucketWithDifferingHash()
+{
+    QV4::ExecutionEngine engine;
+    QV4::IdentifierTable table(&engine, /*numBits*/1);
+
+    auto entry1 = engine.newString(QStringLiteral("one"));
+    auto entry2 = engine.newString(QStringLiteral("two"));
+
+    entry1->createHashValue();
+    entry2->createHashValue();
+
+    // First and second entry have differing hash but end up in the
+    // same bucket after modulo alloc.
+    entry1->stringHash = 0;
+    entry2->stringHash = 5;
+
+    // trigger insertion
+    table.asPropertyKey(entry1);
+    table.asPropertyKey(entry2);
+
+    QCOMPARE(table.size, 2);
+    QCOMPARE(table.alloc, 5);
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], nullptr);
+
+    // first entry not marked
+    entry2->setMarkBit();
+
+    table.sweep();
+
+    QCOMPARE(table.entriesByHash[0], entry2);
+    QCOMPARE(table.entriesByHash[1], nullptr);
+    QCOMPARE(table.entriesByHash[2], nullptr);
+}
+
+void tst_qv4identifiertable::dontSweepAcrossBucketBoundaries()
+{
+    QV4::ExecutionEngine engine;
+    QV4::IdentifierTable table(&engine, /*numBits*/1);
+
+    auto entry1 = engine.newString(QStringLiteral("one"));
+    auto entry2 = engine.newString(QStringLiteral("two"));
+    auto entry3 = engine.newString(QStringLiteral("three"));
+
+    entry1->createHashValue();
+    entry2->createHashValue();
+    entry3->createHashValue();
+
+    // Different buckets for both entries.
+    entry1->stringHash = 0;
+    entry2->stringHash = 1;
+
+    // trigger insertion
+    table.asPropertyKey(entry1);
+    table.asPropertyKey(entry2);
+
+    QCOMPARE(table.size, 2);
+    QCOMPARE(table.alloc, 5);
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], nullptr);
+
+    // first entry not marked
+    entry2->setMarkBit();
+
+    table.sweep();
+
+    QCOMPARE(table.entriesByHash[0], nullptr);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], nullptr);
+}
+
+void tst_qv4identifiertable::sweepAcrossBucketBoundariesIfFirstBucketFull()
+{
+    QV4::ExecutionEngine engine;
+    QV4::IdentifierTable table(&engine, /*numBits*/3);
+
+    auto entry1 = engine.newString(QStringLiteral("one"));
+    auto entry2 = engine.newString(QStringLiteral("two"));
+    auto entry3 = engine.newString(QStringLiteral("three"));
+    auto entry4 = engine.newString(QStringLiteral("four"));
+
+    entry1->createHashValue();
+    entry2->createHashValue();
+    entry3->createHashValue();
+    entry4->createHashValue();
+
+    // First, third and fourth entry have the same bucket (after modulo) and
+    // would typically end up in order [entry1, entry3, entry4, entry2]. However
+    // since null termination isn't guaranteed, an insertion order of
+    // entry1, entry2, entry3 and entry4 results in a
+    // table [entry1, entry2, entry3, entry4].
+    entry1->stringHash = 0;
+    entry2->stringHash = 1;
+    entry3->stringHash = 11;
+    entry4->stringHash = 11;
+
+    // trigger insertion
+    table.asPropertyKey(entry1);
+    table.asPropertyKey(entry2);
+    table.asPropertyKey(entry3);
+    table.asPropertyKey(entry4);
+
+    QCOMPARE(table.size, 4);
+    QCOMPARE(table.alloc, 11);
+
+    QCOMPARE(table.entriesByHash[0], entry1);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], entry3);
+    QCOMPARE(table.entriesByHash[3], entry4);
+    QCOMPARE(table.entriesByHash[4], nullptr);
+
+    // first entry not marked
+    entry2->setMarkBit();
+    entry3->setMarkBit();
+    entry4->setMarkBit();
+
+    table.sweep();
+
+    QCOMPARE(table.entriesByHash[0], entry3);
+    QCOMPARE(table.entriesByHash[1], entry2);
+    QCOMPARE(table.entriesByHash[2], entry4);
+    QCOMPARE(table.entriesByHash[3], nullptr);
+}
+
+QTEST_MAIN(tst_qv4identifiertable)
+
+#include "tst_qv4identifiertable.moc"