Implement futexes for Windows

Windows 8 added this pair of functions that can be used to implement the
same functionality as we have on Linux. For ease of understanding, I'm
calling them "futex" on Windows too.

From Qt 6 our minimum platform is Windows 10 so we can use this
unconditionally.

Change-Id: Ifea6e497f11a461db432ffff1448c6806ecfc36c
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>

5 files changed, 162 insertions, 207 deletions

diff --git a/src/corelib/CMakeLists.txt b/src/corelib/CMakeLists.txt
index ecf8318064..2ce6224a60 100644
--- a/src/corelib/CMakeLists.txt
+++ b/src/corelib/CMakeLists.txt
@@ -456,6 +456,18 @@ qt_internal_extend_target(Core CONDITION QT_FEATURE_animation
         animation/qvariantanimation.cpp animation/qvariantanimation.h animation/qvariantanimation_p.h
 )
 
+# This needs to be done before one below adds kernel32 because the symbols we use
+# from synchronization also appears in kernel32 in the version of MinGW we use in CI.
+# However, when picking the symbols from libkernel32.a it will try to load the symbols
+# from the wrong DLL at runtime and crash!
+qt_internal_extend_target(Core CONDITION QT_FEATURE_thread AND WIN32
+    SOURCES
+        thread/qmutex_win.cpp
+        thread/qwaitcondition_win.cpp
+    LIBRARIES
+        synchronization
+)
+
 qt_internal_extend_target(Core CONDITION WIN32
     SOURCES
         global/qoperatingsystemversion_win.cpp global/qoperatingsystemversion_win_p.h
@@ -659,12 +671,6 @@ qt_internal_extend_target(Core CONDITION QT_FEATURE_thread
         thread/qthreadstorage.cpp
 )
 
-qt_internal_extend_target(Core CONDITION QT_FEATURE_thread AND WIN32
-    SOURCES
-        thread/qmutex_win.cpp
-        thread/qwaitcondition_win.cpp
-)
-
 qt_internal_extend_target(Core CONDITION QT_FEATURE_thread AND UNIX
     SOURCES
         thread/qwaitcondition_unix.cpp
@@ -675,11 +681,6 @@ qt_internal_extend_target(Core CONDITION APPLE AND QT_FEATURE_thread
         thread/qmutex_mac.cpp
 )
 
-qt_internal_extend_target(Core CONDITION LINUX AND QT_FEATURE_thread
-    SOURCES
-        thread/qmutex_linux.cpp
-)
-
 qt_internal_extend_target(Core CONDITION QT_FEATURE_thread AND UNIX AND NOT APPLE AND NOT LINUX
     SOURCES
         thread/qmutex_unix.cpp
@@ -1301,7 +1302,6 @@ else()
 endif()
 
 set_source_files_properties(
-    thread/qmutex_linux.cpp
     thread/qmutex_mac.cpp
     thread/qmutex_unix.cpp
     thread/qmutex_win.cpp
diff --git a/src/corelib/thread/qfutex_p.h b/src/corelib/thread/qfutex_p.h
index e4bfeda5f8..b2ed9d22de 100644
--- a/src/corelib/thread/qfutex_p.h
+++ b/src/corelib/thread/qfutex_p.h
@@ -160,6 +160,36 @@ namespace QtLinuxFutex {
 namespace QtFutex = QtLinuxFutex;
 QT_END_NAMESPACE
 
+#elif defined(Q_OS_WIN)
+#  include <qt_windows.h>
+
+QT_BEGIN_NAMESPACE
+namespace QtWindowsFutex {
+#define QT_ALWAYS_USE_FUTEX
+constexpr inline bool futexAvailable() { return true; }
+
+template <typename Atomic>
+inline void futexWait(Atomic &futex, typename Atomic::Type expectedValue)
+{
+    WaitOnAddress(&futex, &expectedValue, sizeof(expectedValue), INFINITE);
+}
+template <typename Atomic>
+inline bool futexWait(Atomic &futex, typename Atomic::Type expectedValue, qint64 nstimeout)
+{
+    BOOL r = WaitOnAddress(&futex, &expectedValue, sizeof(expectedValue), DWORD(nstimeout / 1000 / 1000));
+    return r || GetLastError() != ERROR_TIMEOUT;
+}
+template <typename Atomic> inline void futexWakeAll(Atomic &futex)
+{
+    WakeByAddressAll(&futex);
+}
+template <typename Atomic> inline void futexWakeOne(Atomic &futex)
+{
+    WakeByAddressSingle(&futex);
+}
+}
+namespace QtFutex = QtWindowsFutex;
+QT_END_NAMESPACE
 #else
 
 QT_BEGIN_NAMESPACE
diff --git a/src/corelib/thread/qmutex.cpp b/src/corelib/thread/qmutex.cpp
index 702cf671cd..ba779280bb 100644
--- a/src/corelib/thread/qmutex.cpp
+++ b/src/corelib/thread/qmutex.cpp
@@ -39,20 +39,28 @@
 **
 ****************************************************************************/
 
+#include "global/qglobal.h"
 #include "qplatformdefs.h"
 #include "qmutex.h"
 #include <qdebug.h>
 #include "qatomic.h"
 #include "qelapsedtimer.h"
+#include "qfutex_p.h"
 #include "qthread.h"
 #include "qmutex_p.h"
 
-#ifndef QT_LINUX_FUTEX
+#ifndef QT_ALWAYS_USE_FUTEX
 #include "private/qfreelist_p.h"
 #endif
 
 QT_BEGIN_NAMESPACE
 
+using namespace QtFutex;
+static inline QMutexPrivate *dummyFutexValue()
+{
+    return reinterpret_cast<QMutexPrivate *>(quintptr(3));
+}
+
 /*
     \class QBasicMutex
     \inmodule QtCore
@@ -134,12 +142,12 @@ void QBasicMutex::destroyInternal(QMutexPrivate *d)
 {
     if (!d)
         return;
-#ifndef QT_LINUX_FUTEX
-    if (d != dummyLocked() && d->possiblyUnlocked.loadRelaxed() && tryLock()) {
-        unlock();
-        return;
+    if (!futexAvailable()) {
+        if (d != dummyLocked() && d->possiblyUnlocked.loadRelaxed() && tryLock()) {
+            unlock();
+            return;
+        }
     }
-#endif
     qWarning("QMutex: destroying locked mutex");
 }
 
@@ -510,8 +518,6 @@ void QRecursiveMutex::unlock() noexcept
 
 */
 
-#ifndef QT_LINUX_FUTEX //linux implementation is in qmutex_linux.cpp
-
 /*
   For a rough introduction on how this works, refer to
   http://woboq.com/blog/internals-of-qmutex-in-qt5.html
@@ -532,12 +538,67 @@ void QRecursiveMutex::unlock() noexcept
   possiblyUnlocked flag.
 */
 
+/*
+ * QBasicMutex implementation with futexes (Linux, Windows 10)
+ *
+ * QBasicMutex contains one pointer value, which can contain one of four
+ * different values:
+ *    0x0       unlocked
+ *    0x1       locked, no waiters
+ *    0x3       locked, at least one waiter
+ *
+ * LOCKING:
+ *
+ * A starts in the 0x0 state, indicating that it's unlocked. When the first
+ * thread attempts to lock it, it will perform a testAndSetAcquire
+ * from 0x0 to 0x1. If that succeeds, the caller concludes that it
+ * successfully locked the mutex. That happens in fastTryLock().
+ *
+ * If that testAndSetAcquire fails, QBasicMutex::lockInternal is called.
+ *
+ * lockInternal will examine the value of the pointer. Otherwise, it will use
+ * futexes to sleep and wait for another thread to unlock. To do that, it needs
+ * to set a pointer value of 0x3, which indicates that thread is waiting. It
+ * does that by a simple fetchAndStoreAcquire operation.
+ *
+ * If the pointer value was 0x0, it means we succeeded in acquiring the mutex.
+ * For other values, it will then call FUTEX_WAIT and with an expected value of
+ * 0x3.
+ *
+ * If the pointer value changed before futex(2) managed to sleep, it will
+ * return -1 / EWOULDBLOCK, in which case we have to start over. And even if we
+ * are woken up directly by a FUTEX_WAKE, we need to acquire the mutex, so we
+ * start over again.
+ *
+ * UNLOCKING:
+ *
+ * To unlock, we need to set a value of 0x0 to indicate it's unlocked. The
+ * first attempt is a testAndSetRelease operation from 0x1 to 0x0. If that
+ * succeeds, we're done.
+ *
+ * If it fails, unlockInternal() is called. The only possibility is that the
+ * mutex value was 0x3, which indicates some other thread is waiting or was
+ * waiting in the past. We then set the mutex to 0x0 and perform a FUTEX_WAKE.
+ */
+
 /*!
     \internal helper for lock()
  */
 void QBasicMutex::lockInternal() QT_MUTEX_LOCK_NOEXCEPT
 {
-    lockInternal(-1);
+    if (futexAvailable()) {
+        // note we must set to dummyFutexValue because there could be other threads
+        // also waiting
+        while (d_ptr.fetchAndStoreAcquire(dummyFutexValue()) != nullptr) {
+            // successfully set the waiting bit, now sleep
+            futexWait(d_ptr, dummyFutexValue());
+
+            // we got woken up, so try to acquire the mutex
+        }
+        Q_ASSERT(d_ptr.loadRelaxed());
+    } else {
+        lockInternal(-1);
+    }
 }
 
 /*!
@@ -545,6 +606,41 @@ void QBasicMutex::lockInternal() QT_MUTEX_LOCK_NOEXCEPT
  */
 bool QBasicMutex::lockInternal(int timeout) QT_MUTEX_LOCK_NOEXCEPT
 {
+    if (timeout == 0)
+        return false;
+
+    if (futexAvailable()) {
+        if (Q_UNLIKELY(timeout < 0)) {
+            lockInternal();
+            return true;
+        }
+
+        QDeadlineTimer deadlineTimer(timeout);
+        // The mutex is already locked, set a bit indicating we're waiting.
+        // Note we must set to dummyFutexValue because there could be other threads
+        // also waiting.
+        if (d_ptr.fetchAndStoreAcquire(dummyFutexValue()) == nullptr)
+            return true;
+
+        qint64 remainingTime = deadlineTimer.remainingTimeNSecs();
+        Q_FOREVER {
+            if (!futexWait(d_ptr, dummyFutexValue(), remainingTime))
+                return false;
+
+            // We got woken up, so must try to acquire the mutex. We must set
+            // to dummyFutexValue() again because there could be other threads
+            // waiting.
+            if (d_ptr.fetchAndStoreAcquire(dummyFutexValue()) == nullptr)
+                return true;
+
+            // calculate the remaining time
+            remainingTime = deadlineTimer.remainingTimeNSecs();
+            if (remainingTime <= 0)
+                return false;
+        }
+    }
+
+#if !defined(QT_ALWAYS_USE_FUTEX)
     while (!fastTryLock()) {
         QMutexPrivate *copy = d_ptr.loadAcquire();
         if (!copy) // if d is 0, the mutex is unlocked
@@ -644,6 +740,9 @@ bool QBasicMutex::lockInternal(int timeout) QT_MUTEX_LOCK_NOEXCEPT
     }
     Q_ASSERT(d_ptr.loadRelaxed() != 0);
     return true;
+#else
+    Q_UNREACHABLE();
+#endif
 }
 
 /*!
@@ -655,6 +754,12 @@ void QBasicMutex::unlockInternal() noexcept
     Q_ASSERT(copy); //we must be locked
     Q_ASSERT(copy != dummyLocked()); // testAndSetRelease(dummyLocked(), 0) failed
 
+    if (futexAvailable()) {
+        d_ptr.storeRelease(nullptr);
+        return futexWakeOne(d_ptr);
+    }
+
+#if !defined(QT_ALWAYS_USE_FUTEX)
     QMutexPrivate *d = reinterpret_cast<QMutexPrivate *>(copy);
 
     // If no one is waiting for the lock anymore, we should reset d to 0x0.
@@ -676,8 +781,12 @@ void QBasicMutex::unlockInternal() noexcept
         d->wakeUp();
     }
     d->deref();
+#else
+    Q_UNUSED(copy);
+#endif
 }
 
+#if !defined(QT_ALWAYS_USE_FUTEX)
 //The freelist management
 namespace {
 struct FreeListConstants : QFreeListDefaultConstants {
@@ -738,8 +847,8 @@ void QMutexPrivate::derefWaiters(int value) noexcept
 
 QT_END_NAMESPACE
 
-#ifdef QT_LINUX_FUTEX
-#  include "qmutex_linux.cpp"
+#if defined(Q_OS_LINUX) && defined(QT_ALWAYS_USE_FUTEX)
+// nothing
 #elif defined(Q_OS_MAC)
 #  include "qmutex_mac.cpp"
 #elif defined(Q_OS_WIN)
diff --git a/src/corelib/thread/qmutex_linux.cpp b/src/corelib/thread/qmutex_linux.cpp
deleted file mode 100644
index ceb9be52a8..0000000000
--- a/src/corelib/thread/qmutex_linux.cpp
+++ /dev/null
@@ -1,179 +0,0 @@
-/****************************************************************************
-**
-** Copyright (C) 2016 The Qt Company Ltd.
-** Copyright (C) 2016 Intel Corporation.
-** Contact: https://www.qt.io/licensing/
-**
-** This file is part of the QtCore module of the Qt Toolkit.
-**
-** $QT_BEGIN_LICENSE:LGPL$
-** 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 Lesser General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU Lesser
-** General Public License version 3 as published by the Free Software
-** Foundation and appearing in the file LICENSE.LGPL3 included in the
-** packaging of this file. Please review the following information to
-** ensure the GNU Lesser General Public License version 3 requirements
-** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
-**
-** GNU General Public License Usage
-** Alternatively, this file may be used under the terms of the GNU
-** General Public License version 2.0 or (at your option) the GNU General
-** Public license version 3 or any later version approved by the KDE Free
-** Qt Foundation. The licenses are as published by the Free Software
-** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
-** 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-2.0.html and
-** https://www.gnu.org/licenses/gpl-3.0.html.
-**
-** $QT_END_LICENSE$
-**
-****************************************************************************/
-
-#include "qplatformdefs.h"
-#include "qmutex.h"
-#include "qatomic.h"
-#include "qmutex_p.h"
-#include "qfutex_p.h"
-
-#ifndef QT_ALWAYS_USE_FUTEX
-# error "Qt build is broken: qmutex_linux.cpp is being built but futex support is not wanted"
-#endif
-
-#ifndef FUTEX_PRIVATE_FLAG
-#  define FUTEX_PRIVATE_FLAG    0
-#endif
-
-QT_BEGIN_NAMESPACE
-
-using namespace QtFutex;
-
-/*
- * QBasicMutex implementation on Linux with futexes
- *
- * QBasicMutex contains one pointer value, which can contain one of four
- * different values:
- *    0x0       unlocked, non-recursive mutex
- *    0x1       locked non-recursive mutex, no waiters
- *    0x3       locked non-recursive mutex, at least one waiter
- *   > 0x3      recursive mutex, points to a QMutexPrivate object
- *
- * LOCKING (non-recursive):
- *
- * A non-recursive mutex starts in the 0x0 state, indicating that it's
- * unlocked. When the first thread attempts to lock it, it will perform a
- * testAndSetAcquire from 0x0 to 0x1. If that succeeds, the caller concludes
- * that it successfully locked the mutex. That happens in fastTryLock().
- *
- * If that testAndSetAcquire fails, QBasicMutex::lockInternal is called.
- *
- * lockInternal will examine the value of the pointer. Otherwise, it will use
- * futexes to sleep and wait for another thread to unlock. To do that, it needs
- * to set a pointer value of 0x3, which indicates that thread is waiting. It
- * does that by a simple fetchAndStoreAcquire operation.
- *
- * If the pointer value was 0x0, it means we succeeded in acquiring the mutex.
- * For other values, it will then call FUTEX_WAIT and with an expected value of
- * 0x3.
- *
- * If the pointer value changed before futex(2) managed to sleep, it will
- * return -1 / EWOULDBLOCK, in which case we have to start over. And even if we
- * are woken up directly by a FUTEX_WAKE, we need to acquire the mutex, so we
- * start over again.
- *
- * UNLOCKING (non-recursive):
- *
- * To unlock, we need to set a value of 0x0 to indicate it's unlocked. The
- * first attempt is a testAndSetRelease operation from 0x1 to 0x0. If that
- * succeeds, we're done.
- *
- * If it fails, unlockInternal() is called. The only possibility is that the
- * mutex value was 0x3, which indicates some other thread is waiting or was
- * waiting in the past. We then set the mutex to 0x0 and perform a FUTEX_WAKE.
- */
-
-static inline QMutexPrivate *dummyFutexValue()
-{
-    return reinterpret_cast<QMutexPrivate *>(quintptr(3));
-}
-
-template <bool IsTimed> static inline
-bool lockInternal_helper(QBasicAtomicPointer<QMutexPrivate> &d_ptr, int timeout = -1, QElapsedTimer *elapsedTimer = nullptr) noexcept
-{
-    if (!IsTimed)
-        timeout = -1;
-
-    // we're here because fastTryLock() has just failed
-    if (timeout == 0)
-        return false;
-
-    // the mutex is locked already, set a bit indicating we're waiting
-    if (d_ptr.fetchAndStoreAcquire(dummyFutexValue()) == nullptr)
-        return true;
-
-    qint64 nstimeout = timeout * Q_INT64_C(1000) * 1000;
-    qint64 remainingTime = nstimeout;
-    forever {
-        // successfully set the waiting bit, now sleep
-        if (IsTimed && nstimeout >= 0) {
-            bool r = futexWait(d_ptr, dummyFutexValue(), remainingTime);
-            if (!r)
-                return false;
-
-            // we got woken up, so try to acquire the mutex
-            // note we must set to dummyFutexValue because there could be other threads
-            // also waiting
-            if (d_ptr.fetchAndStoreAcquire(dummyFutexValue()) == nullptr)
-                return true;
-
-            // recalculate the timeout
-            remainingTime = nstimeout - elapsedTimer->nsecsElapsed();
-            if (remainingTime <= 0)
-                return false;
-        } else {
-            futexWait(d_ptr, dummyFutexValue());
-
-            // we got woken up, so try to acquire the mutex
-            // note we must set to dummyFutexValue because there could be other threads
-            // also waiting
-            if (d_ptr.fetchAndStoreAcquire(dummyFutexValue()) == nullptr)
-                return true;
-        }
-    }
-
-    Q_ASSERT(d_ptr.loadRelaxed());
-    return true;
-}
-
-void QBasicMutex::lockInternal() noexcept
-{
-    lockInternal_helper<false>(d_ptr);
-}
-
-bool QBasicMutex::lockInternal(int timeout) noexcept
-{
-    QElapsedTimer elapsedTimer;
-    elapsedTimer.start();
-    return lockInternal_helper<true>(d_ptr, timeout, &elapsedTimer);
-}
-
-void QBasicMutex::unlockInternal() noexcept
-{
-    QMutexPrivate *d = d_ptr.loadRelaxed();
-    Q_ASSERT(d); //we must be locked
-    Q_ASSERT(d != dummyLocked()); // testAndSetRelease(dummyLocked(), 0) failed
-    Q_UNUSED(d);
-
-    d_ptr.storeRelease(nullptr);
-    futexWakeOne(d_ptr);
-}
-
-QT_END_NAMESPACE
diff --git a/src/corelib/thread/qmutex_p.h b/src/corelib/thread/qmutex_p.h
index 96a979e66b..b7d0bdab9b 100644
--- a/src/corelib/thread/qmutex_p.h
+++ b/src/corelib/thread/qmutex_p.h
@@ -62,9 +62,6 @@
 
 #if defined(Q_OS_MAC)
 # include <mach/semaphore.h>
-#elif defined(Q_OS_LINUX) && !defined(QT_LINUXBASE)
-// use Linux mutexes everywhere except for LSB builds
-#  define QT_LINUX_FUTEX
 #elif defined(Q_OS_UNIX)
 # if _POSIX_VERSION-0 >= 200112L || _XOPEN_VERSION-0 >= 600
 #  include <semaphore.h>
@@ -76,7 +73,6 @@ struct timespec;
 
 QT_BEGIN_NAMESPACE
 
-#if !defined(QT_LINUX_FUTEX)
 class QMutexPrivate
 {
 public:
@@ -134,7 +130,6 @@ public:
     Qt::HANDLE event;
 #endif
 };
-#endif //QT_LINUX_FUTEX
 
 
 #ifdef Q_OS_UNIX