Revision control
++ // Copyright (C) 2025 Intel Corporation.
++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
++ // Qt-Security score:significant reason:default
++
++ #include "qatomicwait_p.h"
++
++ #include <qendian.h>
++ #include "qfutex_p.h"
++ #include "qwaitcondition_p.h"
++
++ #include <array>
++ #include <condition_variable>
++ #include <mutex>
++
++ QT_BEGIN_NAMESPACE
++
++ /*
++ * Implementation details:
++ *
++ * Normally, a call from atomic_notify_one() or atomic_notify_all() corresponds
++ * to a call to cond.notify_one() or cond.notify_all(). This simple
++ * implementation would require that we keep a distinct wait condition variable
++ * per atomic variable, of which there could be an arbitrary number.
++ *
++ * Instead, we have a limited set of std::condition_variable, which are
++ * selected based on the address of the variable being waited/notified on.
++ * Because multiple, distinct variables could be sharing the same condition
++ * variable, we need to perform a cond.notify_all() call in case the lock is
++ * contended by waiters to more than one address, as we can't be sure which one
++ * would be woken up by the cond.notify_one() call.
++ *
++ * We recover some of the performance of notifying a single waker by also
++ * storing the address of the variable that was being waited on. If it matches
++ * the address of the variable being notified, we can perform a notify_one()
++ * call. This also allows us to avoid any system call in case no waiter has yet
++ * joined the queue. In case of contention, we store a sentinel address
++ * instead, indicating there are waiters to multiple variables. The last waiter
++ * to leave a wait queue is responsible for resetting the watched address back
++ * to nullptr.
++ *
++ * Performance details:
++ *
++ * This implementation is designed for systems where neither the Standard
++ * Library's own std::atomic_wait nor operating system futexes are available
++ * (read: usually, not the systems Qt is used most frequently on). Therefore,
++ * it's designed for simplicity, not performance. Simplifications applied
++ * include:
++ * - the total number of possible condition variables
++ * - the hashing algorithm to select a condition variable (simple XOR)
++ * - no attempt to wait for a variable change before calling cond.wait()
++ * (no spinning, no HW-assisted wait)
++ *
++ * Other limitations:
++ *
++ * We only support 8-, 16-, 32- and 64-bit variables and we require bit-exact
++ * comparisons for all bits. This means we do not support objects with padding
++ * bits or without unique representations.
++ */
++
++ namespace {
++ struct QAtomicWaitLocks
++ {
++ // Sentinel address used to indicate this Lock is being used by waiters to
++ // multiple addresses, implying we must make a notify_all() call.
++ static void *contendedWatchAddress() { return reinterpret_cast<void *>(-1); }
++
++ struct Lock {
++ alignas(QtPrivate::IdealMutexAlignment) std::mutex mutex;
++ alignas(QtPrivate::IdealMutexAlignment) std::condition_variable cond;
++
++ // Can assume values:
++ // - nullptr: no waiter is waiting
++ // - contendedWatchAddress(): waiters to distinct addresses
++ // - any other value: all waiters are waiting on the same address
++ const void *watchedAddress = nullptr;
++ qsizetype watcherCount = 0;
++ };
++
++ static constexpr int LockCount = 16;
++ std::array<Lock, LockCount> locks;
++
++ int indexFor(const void *ptr)
++ {
++ static_assert((LockCount & (LockCount - 1)) == 0, "LockCount is not a power of two");
++
++ quintptr value = quintptr(ptr) / sizeof(int);
++ quintptr idx = value % LockCount;
++ #ifndef QATOMICWAIT_USE_FALLBACK
++ // XOR some higher bits too to avoid hashing collisions
++ // (we don't do it in the unit test because we *want* those collisions)
++ idx ^= (value / LockCount) % LockCount;
++ idx ^= (value / LockCount / LockCount) % LockCount;
++ #endif
++ return int(idx);
++ }
++
++ Lock &lockFor(const void *ptr) { return locks[indexFor(ptr)]; }
++ };
++ } // unnamed namespace
++
++ static inline void checkFutexUse()
++ {
++ #if !defined(QATOMICWAIT_USE_FALLBACK)
++ if (QtFutex::futexAvailable()) {
++ // This will disable the code and data on systems where futexes are
++ // always available (currently: FreeBSD, Linux, Windows).
++ qFatal("Implementation should have used futex!");
++ }
++ #endif
++ }
++
++ static QAtomicWaitLocks &atomicLocks() noexcept
++ {
++ checkFutexUse();
++
++ static QAtomicWaitLocks global {};
++ return global;
++ }
++
++ template <typename T> static bool isEqual(const void *address, const void *old)
++ {
++ auto atomic = static_cast<const std::atomic<T> *>(address);
++ auto expected = static_cast<const T *>(old);
++ return atomic->load(std::memory_order_relaxed) == *expected;
++ }
++
++ static bool isEqual(const void *address, const void *old, qsizetype size) noexcept
++ {
++ switch (size) {
++ case 1: return isEqual<quint8 >(address, old);
++ case 2: return isEqual<quint16>(address, old);
++ case 4: return isEqual<quint32>(address, old);
++ case 8: return isEqual<quint64>(address, old);
++ }
++ Q_UNREACHABLE_RETURN(false);
++ }
++
++ void QtPrivate::_q_atomicWait(const void *address, const void *old, qsizetype size) noexcept
++ {
++ auto &locker = atomicLocks().lockFor(address);
++
++ // NOT noexcept; we'll terminate if locking the mutex fails
++ std::unique_lock lock(locker.mutex);
++
++ // is the value still current?
++ if (!isEqual(address, old, size))
++ return; // no, failed to wait
++
++ if (locker.watchedAddress && locker.watchedAddress != address)
++ locker.watchedAddress = QAtomicWaitLocks::contendedWatchAddress();
++ else
++ locker.watchedAddress = address;
++ ++locker.watcherCount;
++
++ do {
++ locker.cond.wait(lock);
++ } while (isEqual(address, old, size));
++
++ if (--locker.watcherCount == 0)
++ locker.watchedAddress = nullptr;
++ }
++
++ void QtPrivate::_q_atomicWake(void *address, WakeMode mode) noexcept
++ {
++ auto &locker = atomicLocks().lockFor(address);
++
++ // NOT noexcept; we'll terminate if locking the mutex fails
++ std::unique_lock lock(locker.mutex);
++
++ // can we wake just one?
++ if (mode == WakeMode::One && locker.watchedAddress == address)
++ locker.cond.notify_one();
++ else if (locker.watchedAddress != nullptr)
++ locker.cond.notify_all();
++ else
++ qt_noop(); // no one was waiting
++ }
++
++ QT_END_NAMESPACE