Introduce QHashSeed and switch to size_t seeds

Commit 37e0953613ef9a3db137bc8d3076441d9ae317d9 added a to-do, but we
can actually change the type, since we've documented since Qt 5.10 that
setting a non-zero value (aside from -1) with qSetGlobalQHashSeed was
not allowed. Storing a value to be reset later is simply not supported.

Change-Id: Id2983978ad544ff79911fffd1671f7b5de284bab
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>

7 files changed, 382 insertions, 36 deletions

diff --git a/src/corelib/tools/qduplicatetracker_p.h b/src/corelib/tools/qduplicatetracker_p.h
index c7c63e1000..914ca35815 100644
--- a/src/corelib/tools/qduplicatetracker_p.h
+++ b/src/corelib/tools/qduplicatetracker_p.h
@@ -67,7 +67,7 @@ class QDuplicateTracker {
 #ifdef __cpp_lib_memory_resource
     template <typename HT>
     struct QHasher {
-        size_t storedSeed = qGlobalQHashSeed();
+        size_t storedSeed = QHashSeed::globalSeed();
         size_t operator()(const HT &t) const {
             return QHashPrivate::calculateHash(t, storedSeed);
         }
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index 39f5ded796..e8858b6507 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -722,23 +722,24 @@ size_t qHash(QLatin1String key, size_t seed) noexcept
 /*!
     \internal
 */
-static uint qt_create_qhash_seed()
+static size_t qt_create_qhash_seed()
 {
-    uint seed = 0;
+    size_t seed = 0;
 
 #ifndef QT_BOOTSTRAPPED
     QByteArray envSeed = qgetenv("QT_HASH_SEED");
     if (!envSeed.isEmpty()) {
-        uint seed = envSeed.toUInt();
+        seed = envSeed.toUInt();
         if (seed) {
             // can't use qWarning here (reentrancy)
             fprintf(stderr, "QT_HASH_SEED: forced seed value is not 0; ignored.\n");
-            seed = 0;
         }
-        return seed;
+        seed = 1;   // QHashSeed::globalSeed subtracts 1
+    } else if (sizeof(seed) > sizeof(uint)) {
+        seed = QRandomGenerator::system()->generate64();
+    } else {
+        seed = QRandomGenerator::system()->generate();
     }
-
-    seed = QRandomGenerator::system()->generate();
 #endif // QT_BOOTSTRAPPED
 
     return seed;
@@ -746,30 +747,125 @@ static uint qt_create_qhash_seed()
 
 /*
     The QHash seed itself.
+
+    We store the seed value plus one, so the value zero is used to indicate the
+    seed is not initialized. This is corrected before passing to the user.
 */
-// ### Qt 7: this should use size_t, not int.
-static QBasicAtomicInt qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(-1);
+static QBasicAtomicInteger<size_t> qt_qhash_seed = Q_BASIC_ATOMIC_INITIALIZER(0);
 
 /*!
     \internal
+    \threadsafe
+
+    Initializes the seed and returns it
+*/
+static size_t qt_initialize_qhash_seed()
+{
+    size_t theirSeed;               // another thread's seed
+    size_t ourSeed = qt_create_qhash_seed();
+    if (qt_qhash_seed.testAndSetRelaxed(0, ourSeed, theirSeed))
+        return ourSeed;
+    return theirSeed;
+}
+
+/*!
+    \class QHashSeed
+    \relates QHash
+    \since 6.2
+
+    The QHashSeed class is used to convey the QHash seed. This is used
+    internally by QHash and provides three static member functions to allow
+    users to obtain the hash and to reset it.
 
-    Seed == -1 means it that it was not initialized yet.
+    QHash and the qHash() functions implement what is called as "salted hash".
+    The intent is that different applications and different instances of the
+    same application will produce different hashing values for the same input,
+    thus causing the ordering of elements in QHash to be unpredictable by
+    external observers. This improves the applications' resilience against
+    attacks that attempt to force hashing tables into degenerate mode.
 
-    We let qt_create_qhash_seed return any unsigned integer,
-    but convert it to signed in order to initialize the seed.
+    Most applications will not need to deal directly with the hash seed, as
+    QHash will do so when needed. However, applications may wish to use this
+    for their own purposes in the same way as QHash does: as an
+    application-global random value (but see \l QRandomGenerator too). Note
+    that the global hash seed may change during the application's lifetime, if
+    the resetRandomGlobalSeed() function is called. Users of the global hash
+    need to store the value they are using and not rely on getting it again.
 
-    We don't actually care about the fact that different calls to
-    qt_create_qhash_seed() might return different values,
-    as long as in the end everyone uses the very same value.
+    This class also implements functionality to set the hash seed to a
+    deterministic value, which the qHash() functions will take to mean that
+    they should use a fixed hashing function on their data too. This
+    functionality is only meant to be used in debugging applications. This
+    behavior can also be controlled by setting the \c QT_HASH_SEED environment
+    variable to the value zero (any other value is ignored).
+
+    \sa QHash, QRandomGenerator
 */
-static void qt_initialize_qhash_seed()
+
+/*!
+    \fn QHashSeed::QHashSeed(size_t data)
+
+    Constructs a new QHashSeed object using \a data as the seed.
+ */
+
+/*!
+    \fn QHashSeed::operator size_t() const
+
+    Converts the returned hash seed into a \c size_t.
+ */
+
+/*!
+    \threadsafe
+
+    Returns the current global QHash seed. The value returned by this function
+    will be zero if setDeterministicGlobalSeed() has been called or if the
+    \c{QT_HASH_SEED} environment variable is set to zero.
+ */
+QHashSeed QHashSeed::globalSeed()
 {
-    if (qt_qhash_seed.loadRelaxed() == -1) {
-        int x(qt_create_qhash_seed() & INT_MAX);
-        qt_qhash_seed.testAndSetRelaxed(-1, x);
-    }
+    size_t seed = qt_qhash_seed.loadRelaxed();
+    if (Q_UNLIKELY(seed == 0))
+        seed = qt_initialize_qhash_seed();
+
+    return { seed - 1 };
+}
+
+/*!
+    \threadsafe
+
+    Forces the Qt hash seed to a deterministic value (zero) and asks the
+    qHash() functions to use a pre-determined hashing function. This mode is
+    only useful for debugging and should not be used in production code.
+
+    Regular operation can be restored by calling resetRandomGlobalSeed().
+ */
+void QHashSeed::setDeterministicGlobalSeed()
+{
+    qt_qhash_seed.storeRelease(1);
 }
 
+/*!
+    \threadsafe
+
+    Reseeds the Qt hashing seed to a new, random value. Calling this function
+    is not necessary, but long-running applications may want to do so after a
+    long period of time in which information about its hash may have been
+    exposed to potential attackers.
+
+    If the environment variable \c QT_HASH_SEED is set to zero, calling this
+    function will result in a no-op.
+
+    Qt never calls this function during the execution of the application, but
+    unless the \c QT_HASH_SEED variable is set to 0, the hash seed returned by
+    globalSeed() will be a random value as if this function had been called.
+ */
+void QHashSeed::resetRandomGlobalSeed()
+{
+    size_t seed = qt_create_qhash_seed();
+    qt_qhash_seed.storeRelaxed(seed + 1);
+}
+
+
 /*! \relates QHash
     \since 5.6
 
@@ -778,12 +874,11 @@ static void qt_initialize_qhash_seed()
     The seed is set in any newly created QHash. See \l{qHash} about how this seed
     is being used by QHash.
 
-    \sa qSetGlobalQHashSeed
+    \sa qSetGlobalQHashSeed, QHashSeed::globalSeed()
  */
 int qGlobalQHashSeed()
 {
-    qt_initialize_qhash_seed();
-    return qt_qhash_seed.loadRelaxed();
+    return int(QHashSeed::globalSeed() & INT_MAX);
 }
 
 /*! \relates QHash
@@ -807,21 +902,18 @@ int qGlobalQHashSeed()
     If the environment variable \c QT_HASH_SEED is set, calling this function will
     result in a no-op.
 
-    \sa qGlobalQHashSeed
+    \sa qGlobalQHashSeed, QHashSeed
  */
 void qSetGlobalQHashSeed(int newSeed)
 {
-    if (qEnvironmentVariableIsSet("QT_HASH_SEED"))
-        return;
-    if (newSeed == -1) {
-        int x(qt_create_qhash_seed() & INT_MAX);
-        qt_qhash_seed.storeRelaxed(x);
+    if (Q_LIKELY(newSeed == 0 || newSeed == -1)) {
+        if (newSeed == 0)
+            QHashSeed::setDeterministicGlobalSeed();
+        else
+            QHashSeed::resetRandomGlobalSeed();
     } else {
-        if (newSeed) {
-            // can't use qWarning here (reentrancy)
-            fprintf(stderr, "qSetGlobalQHashSeed: forced seed value is not 0; ignoring call\n");
-        }
-        qt_qhash_seed.storeRelaxed(0);
+        // can't use qWarning here (reentrancy)
+        fprintf(stderr, "qSetGlobalQHashSeed: forced seed value is not 0; ignoring call\n");
     }
 }
 
@@ -1442,7 +1534,7 @@ size_t qHash(long double key, size_t seed) noexcept
     where you temporarily need deterministic behavior, for example for debugging or
     regression testing. To disable the randomization, define the environment
     variable \c QT_HASH_SEED to have the value 0. Alternatively, you can call
-    the qSetGlobalQHashSeed() function with the value 0.
+    the QHashSeed::setDeterministicGlobalSeed() function.
 
     \sa QHashIterator, QMutableHashIterator, QMap, QSet
 */
diff --git a/src/corelib/tools/qhashfunctions.h b/src/corelib/tools/qhashfunctions.h
index 835fed9589..83c9f35f3f 100644
--- a/src/corelib/tools/qhashfunctions.h
+++ b/src/corelib/tools/qhashfunctions.h
@@ -68,6 +68,18 @@ class QLatin1String;
 Q_CORE_EXPORT int qGlobalQHashSeed();
 Q_CORE_EXPORT void qSetGlobalQHashSeed(int newSeed);
 
+struct QHashSeed
+{
+    constexpr QHashSeed(size_t d = 0) : data(d) {}
+    constexpr operator size_t() const noexcept { return data; }
+
+    static Q_CORE_EXPORT QHashSeed globalSeed() Q_DECL_PURE_FUNCTION;
+    static Q_CORE_EXPORT void setDeterministicGlobalSeed();
+    static Q_CORE_EXPORT void resetRandomGlobalSeed();
+private:
+    size_t data;
+};
+
 namespace QHashPrivate {
 
 Q_DECL_CONST_FUNCTION constexpr size_t hash(size_t key, size_t seed) noexcept
diff --git a/tests/auto/corelib/tools/CMakeLists.txt b/tests/auto/corelib/tools/CMakeLists.txt
index a7d3889251..8b6723874b 100644
--- a/tests/auto/corelib/tools/CMakeLists.txt
+++ b/tests/auto/corelib/tools/CMakeLists.txt
@@ -16,6 +16,7 @@ add_subdirectory(qflatmap)
 add_subdirectory(qfreelist)
 add_subdirectory(qhash)
 add_subdirectory(qhashfunctions)
+add_subdirectory(qhashseed)
 add_subdirectory(qline)
 add_subdirectory(qlist)
 add_subdirectory(qmakearray)
diff --git a/tests/auto/corelib/tools/qhashseed/CMakeLists.txt b/tests/auto/corelib/tools/qhashseed/CMakeLists.txt
new file mode 100644
index 0000000000..bc40c63b3e
--- /dev/null
+++ b/tests/auto/corelib/tools/qhashseed/CMakeLists.txt
@@ -0,0 +1,14 @@
+#####################################################################
+## tst_qhashseed Test:
+#####################################################################
+
+qt_internal_add_test(tst_qhashseed
+    SOURCES
+        tst_qhashseed.cpp
+)
+
+qt_internal_add_executable(tst_qhashseed_helper
+    OUTPUT_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/"
+    SOURCES
+        tst_qhashseed_helper.cpp
+)
diff --git a/tests/auto/corelib/tools/qhashseed/tst_qhashseed.cpp b/tests/auto/corelib/tools/qhashseed/tst_qhashseed.cpp
new file mode 100644
index 0000000000..1e3a7572d0
--- /dev/null
+++ b/tests/auto/corelib/tools/qhashseed/tst_qhashseed.cpp
@@ -0,0 +1,188 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 Intel Corporation.
+** 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>
+
+#include <qhashfunctions.h>
+#include <qprocess.h>
+
+class tst_QHashSeed : public QObject
+{
+    Q_OBJECT
+public:
+    static void initMain();
+
+private Q_SLOTS:
+    void initTestCase();
+    void environmentVariable_data();
+    void environmentVariable();
+    void deterministicSeed();
+    void reseeding();
+    void quality();
+#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
+    void compatibilityApi();
+    void deterministicSeed_compat();
+#endif
+};
+
+void tst_QHashSeed::initMain()
+{
+    qunsetenv("QT_HASH_SEED");
+}
+
+void tst_QHashSeed::initTestCase()
+{
+    // in case the qunsetenv above didn't work
+    if (qEnvironmentVariableIsSet("QT_HASH_SEED"))
+        QSKIP("QT_HASH_SEED environment variable is set, please don't do that");
+}
+
+void tst_QHashSeed::environmentVariable_data()
+{
+#if defined(Q_OS_ANDROID) && !defined(Q_OS_ANDROID_EMBEDDED)
+    QSKIP("This test needs a helper binary, so is excluded from this platform.");
+#endif
+
+    QTest::addColumn<QByteArray>("envVar");
+    QTest::addColumn<bool>("isZero");
+    QTest::newRow("unset-environment") << QByteArray() << false;
+    QTest::newRow("empty-environment") << QByteArray("") << false;
+    QTest::newRow("zero-seed") << QByteArray("0") << true;
+}
+
+void tst_QHashSeed::environmentVariable()
+{
+    QFETCH(QByteArray, envVar);
+    QFETCH(bool, isZero);
+    QProcessEnvironment env = QProcessEnvironment::systemEnvironment();
+    if (envVar.isNull())
+        env.remove("QT_HASH_SEED");
+    else
+        env.insert("QT_HASH_SEED", envVar);
+
+    QProcess helper;
+    helper.setProcessEnvironment(env);
+    helper.setProgram("./tst_qhashseed_helper");
+    helper.start();
+    QVERIFY2(helper.waitForStarted(5000), qPrintable(helper.errorString()));
+    QVERIFY2(helper.waitForFinished(5000), qPrintable(helper.errorString()));
+    QCOMPARE(helper.exitStatus(), 0);
+
+    QByteArray line1 = helper.readLine().trimmed();
+    QByteArray line2 = helper.readLine().trimmed();
+    QCOMPARE(line2, line1);
+    QCOMPARE(line1 == "0", isZero);
+}
+
+void tst_QHashSeed::deterministicSeed()
+{
+    QHashSeed::setDeterministicGlobalSeed();
+    QCOMPARE(size_t(QHashSeed::globalSeed()), size_t(0));
+
+    // now reset
+    QHashSeed::resetRandomGlobalSeed();
+    QVERIFY(QHashSeed::globalSeed() != 0);
+}
+
+void tst_QHashSeed::reseeding()
+{
+    constexpr int Iterations = 4;
+    size_t seeds[Iterations];
+    for (int i = 0; i < Iterations; ++i) {
+        seeds[i] = QHashSeed::globalSeed();
+        QHashSeed::resetRandomGlobalSeed();
+    }
+
+    // verify that they are all different
+    QString fmt = QStringLiteral("seeds[%1] = 0x%3, seeds[%2] = 0x%4");
+    for (int i = 0; i < Iterations; ++i) {
+        for (int j = i + 1; j < Iterations; ++j) {
+            QVERIFY2(seeds[i] != seeds[j],
+                     qPrintable(fmt.arg(i).arg(j).arg(seeds[i], 16).arg(seeds[j], 16)));
+        }
+    }
+}
+
+void tst_QHashSeed::quality()
+{
+    constexpr int Iterations = 16;
+    int oneThird = 0;
+    size_t ored = 0;
+
+    for (int i = 0; i < Iterations; ++i) {
+        size_t seed = QHashSeed::globalSeed();
+        ored |= seed;
+        int bits = qPopulationCount(quintptr(seed));
+        QVERIFY2(bits > 0, QByteArray::number(bits));   // mandatory
+
+        if (bits >= std::numeric_limits<size_t>::digits / 3)
+            ++oneThird;
+    }
+
+    // report out
+    qInfo() << "Number of seeds with at least one third of the bits set:"
+            << oneThird << '/' << Iterations;
+    qInfo() << "Number of bits in OR'ed value:" << qPopulationCount(quintptr(ored))
+            << '/' << std::numeric_limits<size_t>::digits;
+    if (std::numeric_limits<size_t>::digits > 32) {
+        quint32 upper = quint64(ored) >> 32;
+        qInfo() << "Number of bits in the upper half:" << qPopulationCount(upper) << "/ 32";
+        QVERIFY(qPopulationCount(upper) > (32/3));
+    }
+
+    // at least one third of the seeds must have one third of all the bits set
+    QVERIFY(oneThird > (16/3));
+}
+
+#if QT_VERSION < QT_VERSION_CHECK(7, 0, 0)
+QT_WARNING_DISABLE_DEPRECATED
+void tst_QHashSeed::compatibilityApi()
+{
+    int oldSeed = qGlobalQHashSeed();
+    size_t newSeed = QHashSeed::globalSeed();
+
+    QCOMPARE(size_t(oldSeed), newSeed & size_t(INT_MAX));
+}
+
+void tst_QHashSeed::deterministicSeed_compat()
+{
+    // same as above, but using the compat API
+    qSetGlobalQHashSeed(0);
+    QCOMPARE(size_t(QHashSeed::globalSeed()), size_t(0));
+    QCOMPARE(qGlobalQHashSeed(), 0);
+
+    // now reset
+    qSetGlobalQHashSeed(-1);
+    QVERIFY(QHashSeed::globalSeed() != 0);
+    QVERIFY(qGlobalQHashSeed() != 0);
+    QVERIFY(qGlobalQHashSeed() != -1);  // possible, but extremely unlikely
+}
+#endif // Qt 7
+
+QTEST_MAIN(tst_QHashSeed)
+#include "tst_qhashseed.moc"
diff --git a/tests/auto/corelib/tools/qhashseed/tst_qhashseed_helper.cpp b/tests/auto/corelib/tools/qhashseed/tst_qhashseed_helper.cpp
new file mode 100644
index 0000000000..752228e5a1
--- /dev/null
+++ b/tests/auto/corelib/tools/qhashseed/tst_qhashseed_helper.cpp
@@ -0,0 +1,39 @@
+/****************************************************************************
+**
+** Copyright (C) 2021 Intel Corporation.
+** 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 <qhashfunctions.h>
+#include <stdio.h>
+
+int main()
+{
+    // appless:
+    QHashSeed seed1 = QHashSeed::globalSeed();
+    QHashSeed seed2 = QHashSeed::globalSeed();
+    printf("%zu\n%zu\n", size_t(seed1), size_t(seed2));
+    return 0;
+}