diff options
author | MÃ¥rten Nordheim <marten.nordheim@qt.io> | 2021-10-26 15:04:19 +0200 |
---|---|---|
committer | Marc Mutz <marc.mutz@qt.io> | 2021-11-25 08:52:39 +0000 |
commit | 8f8775adf3c4fbba1bd3c120a228351d46f50127 (patch) | |
tree | 52655d992735025a9d0d1c421838f5a7c67a7f00 | |
parent | a92619d950fdbf803cdc8c8ca8e75c1c82abb23f (diff) |
QHash: fix thread race around references and detaching
If we detach from a shared hash while holding a reference to a key from
said shared hash then there is no guarantee for how long the reference
is valid (given a multi-thread environment).
Pick-to: 6.2
Change-Id: Ifb610753d24faca63e2c0eb8836c78d55a229001
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Marc Mutz <marc.mutz@qt.io>
-rw-r--r-- | src/corelib/tools/qhash.h | 111 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qhash/tst_qhash.cpp | 56 |
2 files changed, 136 insertions, 31 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index 0d5fa52111..24fd24e603 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -888,9 +888,10 @@ public: { if (isEmpty()) // prevents detaching shared null return false; + auto it = d->find(key); detach(); + it = d->detachedIterator(it); - auto it = d->find(key); if (it.isUnused()) return false; d->erase(it); @@ -905,9 +906,10 @@ public: { if (isEmpty()) // prevents detaching shared null return T(); + auto it = d->find(key); detach(); + it = d->detachedIterator(it); - auto it = d->find(key); if (it.isUnused()) return T(); T value = it.node()->takeValue(); @@ -986,6 +988,7 @@ public: T &operator[](const Key &key) { + const auto copy = isDetached() ? QHash() : *this; // keep 'key' alive across the detach detach(); auto result = d->findOrInsert(key); Q_ASSERT(!result.it.atEnd()); @@ -1178,8 +1181,9 @@ public: { if (isEmpty()) // prevents detaching shared null return end(); - detach(); auto it = d->find(key); + detach(); + it = d->detachedIterator(it); if (it.isUnused()) it = d->end(); return iterator(it); @@ -1227,14 +1231,15 @@ public: template <typename ...Args> iterator emplace(Key &&key, Args &&... args) { + if (isDetached()) { + if (d->shouldGrow()) // Construct the value now so that no dangling references are used + return emplace_helper(std::move(key), T(std::forward<Args>(args)...)); + return emplace_helper(std::move(key), std::forward<Args>(args)...); + } + // else: we must detach + const auto copy = *this; // keep 'args' alive across the detach/growth detach(); - - auto result = d->findOrInsert(key); - if (!result.initialized) - Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); - else - result.it.node()->emplaceValue(std::forward<Args>(args)...); - return iterator(result.it); + return emplace_helper(std::move(key), std::forward<Args>(args)...); } float load_factor() const noexcept { return d ? d->loadFactor() : 0; } @@ -1243,6 +1248,18 @@ public: static size_t max_bucket_count() noexcept { return QHashPrivate::GrowthPolicy::maxNumBuckets(); } inline bool empty() const noexcept { return isEmpty(); } + +private: + template <typename ...Args> + iterator emplace_helper(Key &&key, Args &&... args) + { + auto result = d->findOrInsert(key); + if (!result.initialized) + Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); + else + result.it.node()->emplaceValue(std::forward<Args>(args)...); + return iterator(result.it); + } }; @@ -1416,9 +1433,10 @@ public: { if (isEmpty()) // prevents detaching shared null return 0; + auto it = d->find(key); detach(); + it = d->detachedIterator(it); - auto it = d->find(key); if (it.isUnused()) return 0; qsizetype n = Node::freeChain(it.node()); @@ -1436,9 +1454,10 @@ public: { if (isEmpty()) // prevents detaching shared null return T(); + auto it = d->find(key); detach(); + it = d->detachedIterator(it); - auto it = d->find(key); if (it.isUnused()) return T(); Chain *e = it.node()->value; @@ -1524,6 +1543,7 @@ public: T &operator[](const Key &key) { + const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach detach(); auto result = d->findOrInsert(key); Q_ASSERT(!result.it.atEnd()); @@ -1784,8 +1804,10 @@ public: { if (isEmpty()) return end(); - detach(); auto it = d->find(key); + detach(); + it = d->detachedIterator(it); + if (it.isUnused()) it = d->end(); return iterator(it); @@ -1817,15 +1839,15 @@ public: template <typename ...Args> iterator emplace(Key &&key, Args &&... args) { + if (isDetached()) { + if (d->shouldGrow()) // Construct the value now so that no dangling references are used + return emplace_helper(std::move(key), T(std::forward<Args>(args)...)); + return emplace_helper(std::move(key), std::forward<Args>(args)...); + } + // else: we must detach + const auto copy = *this; // keep 'args' alive across the detach/growth detach(); - - auto result = d->findOrInsert(key); - if (!result.initialized) - Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); - else - result.it.node()->insertMulti(std::forward<Args>(args)...); - ++m_size; - return iterator(result.it); + return emplace_helper(std::move(key), std::forward<Args>(args)...); } @@ -1850,16 +1872,15 @@ public: template <typename ...Args> iterator emplaceReplace(Key &&key, Args &&... args) { - detach(); - - auto result = d->findOrInsert(key); - if (!result.initialized) { - ++m_size; - Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); - } else { - result.it.node()->emplaceValue(std::forward<Args>(args)...); + if (isDetached()) { + if (d->shouldGrow()) // Construct the value now so that no dangling references are used + return emplaceReplace_helper(std::move(key), T(std::forward<Args>(args)...)); + return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...); } - return iterator(result.it); + // else: we must detach + const auto copy = *this; // keep 'args' alive across the detach/growth + detach(); + return emplaceReplace_helper(std::move(key), std::forward<Args>(args)...); } inline QMultiHash &operator+=(const QMultiHash &other) @@ -1881,9 +1902,10 @@ public: { if (isEmpty()) // prevents detaching shared null return 0; + auto it = d->find(key); detach(); + it = d->detachedIterator(it); - auto it = d->find(key); if (it.isUnused()) return 0; qsizetype n = 0; @@ -1944,6 +1966,7 @@ public: { if (isEmpty()) return end(); + const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key'/'value' alive across the detach detach(); auto it = constFind(key, value); return iterator(it.i, it.e); @@ -2001,6 +2024,7 @@ public: QPair<iterator, iterator> equal_range(const Key &key) { + const auto copy = isDetached() ? QMultiHash() : *this; // keep 'key' alive across the detach detach(); auto pair = qAsConst(*this).equal_range(key); return qMakePair(iterator(pair.first.i), iterator(pair.second.i)); @@ -2031,6 +2055,31 @@ private: delete d; d = dd; } + + template<typename... Args> + iterator emplace_helper(Key &&key, Args &&...args) + { + auto result = d->findOrInsert(key); + if (!result.initialized) + Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); + else + result.it.node()->insertMulti(std::forward<Args>(args)...); + ++m_size; + return iterator(result.it); + } + + template<typename... Args> + iterator emplaceReplace_helper(Key &&key, Args &&...args) + { + auto result = d->findOrInsert(key); + if (!result.initialized) { + Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...); + ++m_size; + } else { + result.it.node()->emplaceValue(std::forward<Args>(args)...); + } + return iterator(result.it); + } }; Q_DECLARE_ASSOCIATIVE_FORWARD_ITERATOR(Hash) diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp index 7e297c0119..7cc4d3d0f0 100644 --- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp +++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp @@ -36,6 +36,8 @@ #include <unordered_set> #include <string> +#include <qsemaphore.h> + class tst_QHash : public QObject { Q_OBJECT @@ -97,6 +99,8 @@ private slots: void reserveShared(); void QTBUG98265(); + + void detachAndReferences(); }; struct IdentityTracker { @@ -2627,5 +2631,57 @@ void tst_QHash::QTBUG98265() QVERIFY(a != b); } + +/* + Calling functions which take a const-ref argument for a key with a reference + to a key inside the hash itself should keep the key valid as long as it is + needed. If not users may get hard-to-debug races where CoW should've + shielded them. +*/ +void tst_QHash::detachAndReferences() +{ +#if !QT_CONFIG(cxx11_future) + QSKIP("This test requires cxx11_future") +#else + // Repeat a few times because it's not a guarantee + for (int i = 0; i < 50; ++i) { + QHash<char, char> hash; + hash.insert('a', 'a'); + hash.insert('b', 'a'); + hash.insert('c', 'a'); + hash.insert('d', 'a'); + hash.insert('e', 'a'); + hash.insert('f', 'a'); + hash.insert('g', 'a'); + + QSemaphore sem; + QSemaphore sem2; + std::thread th([&sem, &sem2, hash]() mutable { + sem.release(); + sem2.acquire(); + hash.reserve(100); // [2]: ...then this rehashes directly, without detaching + }); + + // The key is a reference to an entry in the hash. If we were already + // detached then no problem occurs! The problem happens because _after_ + // we detach but before using the key the other thread resizes and + // rehashes, leaving our const-ref dangling. + auto it = hash.constBegin(); + const auto &key = it.key(); // [3]: leaving our const-refs dangling + auto kCopy = key; + const auto &value = it.value(); + auto vCopy = value; + sem2.release(); + sem.acquire(); + hash.insert(key, value); // [1]: this detaches first... + + th.join(); + QCOMPARE(hash.size(), 7); + QVERIFY(hash.contains(kCopy)); + QCOMPARE(hash.value(kCopy), vCopy); + } +#endif +} + QTEST_APPLESS_MAIN(tst_QHash) #include "tst_qhash.moc" |