QCache: fix potential crash in trim()

We use raw pointers to the Nodes in the QHash which is
inherently fine, but we are then subject to invalidation when
nodes are moved around during deletion.

In trim() we don't actually need to iterate the linked-list
since the node we are interested in is always chain.prev

Fixes: QTBUG-99710
Task-number: QTBUG-99224
Task-number: QTBUG-99240
Change-Id: I9c2ed69b29e3cadca013113a3553deb44d7382fc
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Jarek Kobus <jaroslaw.kobus@qt.io>
(cherry picked from commit 8c5e31536ac74f643d4dd371d281fd9416864a45)
Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>

2 files changed, 69 insertions, 5 deletions

diff --git a/src/corelib/tools/qcache.h b/src/corelib/tools/qcache.h
index 73a2a51b8a..76d36f0081 100644
--- a/src/corelib/tools/qcache.h
+++ b/src/corelib/tools/qcache.h
@@ -162,11 +162,9 @@ class QCache
 
     void trim(qsizetype m) noexcept(std::is_nothrow_destructible_v<Node>)
     {
-        Chain *n = chain.prev;
-        while (n != &chain && total > m) {
-            Node *u = static_cast<Node *>(n);
-            n = n->prev;
-            unlink(u);
+        while (chain.prev != &chain && total > m) {
+            Node *n = static_cast<Node *>(chain.prev);
+            unlink(n);
         }
     }
 
diff --git a/tests/auto/corelib/tools/qcache/tst_qcache.cpp b/tests/auto/corelib/tools/qcache/tst_qcache.cpp
index eb024e8f9e..d53e8bf880 100644
--- a/tests/auto/corelib/tools/qcache/tst_qcache.cpp
+++ b/tests/auto/corelib/tools/qcache/tst_qcache.cpp
@@ -50,6 +50,7 @@ private slots:
     void largeCache();
     void internalChainOrderAfterEntryUpdate();
     void emplaceLowerCost();
+    void trimWithMovingAcrossSpans();
 };
 
 
@@ -446,5 +447,70 @@ void tst_QCache::emplaceLowerCost()
     QVERIFY(cache.isEmpty());
 }
 
+struct TrivialHashType {
+    int i = -1;
+    size_t hash = 0;
+
+    TrivialHashType(int i, size_t hash) : i(i), hash(hash) {}
+    TrivialHashType(const TrivialHashType &o) noexcept = default;
+    TrivialHashType &operator=(const TrivialHashType &o) noexcept = default;
+    TrivialHashType(TrivialHashType &&o) noexcept : i(o.i), hash(o.hash) {
+        o.i = -1;
+        o.hash = 0;
+    }
+    TrivialHashType &operator=(TrivialHashType &&o) noexcept {
+        i = o.i;
+        hash = o.hash;
+        o.i = -1;
+        o.hash = 0;
+        return *this;
+    }
+
+
+    friend bool operator==(const TrivialHashType &lhs, const TrivialHashType &rhs)
+    {
+        return lhs.i == rhs.i;
+    }
+};
+quint64 qHash(TrivialHashType t, size_t seed = 0)
+{
+    return t.hash;
+}
+
+// During trim(), if the Node we have a pointer to in the function is moved
+// to another span in the hash table, our pointer would end up pointing to
+// garbage memory. Test that this no longer happens
+void tst_QCache::trimWithMovingAcrossSpans()
+{
+    qsizetype numBuckets = [](){
+        QHash<int, int> h;
+        h.reserve(1);
+        // Beholden to QHash internals:
+        return h.capacity() << 1;
+    }();
+
+    QCache<TrivialHashType, int> cache;
+    cache.setMaxCost(1000);
+
+    auto lastBucketInSpan = size_t(numBuckets - 1);
+    // If this fails then the test is no longer valid
+    QCOMPARE(QHashPrivate::GrowthPolicy::bucketForHash(numBuckets, lastBucketInSpan),
+             lastBucketInSpan);
+
+    // Pad some space so we have two spans:
+    for (int i = 2; i < numBuckets; ++i)
+        cache.insert({i, 0}, nullptr);
+
+    // These two are vying for the last bucket in the first span,
+    // when '0' is deleted, '1' is moved across the span boundary,
+    // invalidating any pointer to its Node.
+    cache.insert({0, lastBucketInSpan}, nullptr);
+    cache.insert({1, lastBucketInSpan}, nullptr);
+
+    QCOMPARE(cache.size(), numBuckets);
+    cache.setMaxCost(0);
+    QCOMPARE(cache.size(), 0);
+}
+
 QTEST_APPLESS_MAIN(tst_QCache)
 #include "tst_qcache.moc"