Implement a lock/unlock-only mutex based on futex

Pthread mutexes are expensive due to their numerous features.  When a
mutex only needs to support lock and unlock, its implementation can be
much simpler.  The implementation in this change is "inspired" by a
similar mutex in mesa.

Expected uses of this mutex are:

- Allowing some OpenGL calls to avoid the share group lock and instead
  lock the specific shared object they operate on.
- Replacing SpinLock in the OpenCL implementation (spin-lock in user
  space is a bad idea [1])
- Generally anywhere we use std::mutex just to do lock/unlock

Tests based on patch authored by Igor Nazarov <i.nazarov@samsung.com>

[1]:https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723

Bug: angleproject:8667
Change-Id: I52278c9d19616338c499bbcef6684746caead6ca
Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/5446558
Reviewed-by: Roman Lavrov <romanl@google.com>
Commit-Queue: Shahbaz Youssefi <syoussefi@chromium.org>

6 files changed, 308 insertions, 0 deletions

diff --git a/BUILD.gn b/BUILD.gn
index 1a2710f81c..6aeb5e2e43 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -285,6 +285,10 @@ config("internal_config") {
   if (angle_standalone || build_with_chromium) {
     defines += [ "ANGLE_OUTSIDE_WEBKIT" ]
   }
+
+  if (is_win && build_with_chromium) {
+    defines += [ "ANGLE_WINDOWS_NO_FUTEX=1" ]
+  }
 }
 
 config("constructor_and_destructor_warnings") {
@@ -1094,6 +1098,11 @@ angle_source_set("libANGLE_no_vulkan") {
       "gdi32.lib",
       "user32.lib",
     ]
+
+    if (!build_with_chromium) {
+      # Needed for futex support
+      libs += [ "synchronization.lib" ]
+    }
   }
 
   if (angle_enable_d3d11) {
diff --git a/src/common/SimpleMutex.cpp b/src/common/SimpleMutex.cpp
new file mode 100644
index 0000000000..4ed0af51a8
--- /dev/null
+++ b/src/common/SimpleMutex.cpp
@@ -0,0 +1,65 @@
+//
+// Copyright 2024 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// SimpleMutex.cpp:
+//   Implementation of SimpleMutex.h.
+
+#include "common/SimpleMutex.h"
+
+#if ANGLE_USE_FUTEX
+
+#    include <limits.h>
+#    include <stdint.h>
+
+#    if defined(ANGLE_PLATFORM_LINUX) || defined(ANGLE_PLATFORM_ANDROID)
+#        include <linux/futex.h>
+#        include <sys/syscall.h>
+#        include <unistd.h>
+#    endif  // defined(ANGLE_PLATFORM_LINUX) || defined(ANGLE_PLATFORM_ANDROID)
+
+#    if defined(ANGLE_PLATFORM_WINDOWS)
+#        include <errno.h>
+#        include <windows.h>
+#    endif  // defined(ANGLE_PLATFORM_WINDOWS)
+
+namespace angle
+{
+namespace priv
+{
+#    if defined(ANGLE_PLATFORM_LINUX) || defined(ANGLE_PLATFORM_ANDROID)
+namespace
+{
+ANGLE_INLINE void SysFutex(void *addr, int op, int val, int val3)
+{
+    syscall(SYS_futex, addr, op, val, nullptr, nullptr, val3);
+}
+}  // anonymous namespace
+
+void MutexOnFutex::futexWait()
+{
+    SysFutex(&mState, FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG, kBlocked, FUTEX_BITSET_MATCH_ANY);
+}
+void MutexOnFutex::futexWake()
+{
+    SysFutex(&mState, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, kLocked, 0);
+}
+#    endif  // defined(ANGLE_PLATFORM_LINUX) || defined(ANGLE_PLATFORM_ANDROID)
+
+#    if defined(ANGLE_PLATFORM_WINDOWS)
+void MutexOnFutex::futexWait()
+{
+    int value = kBlocked;
+    WaitOnAddress(&mState, &value, sizeof(value), INFINITE);
+}
+
+void MutexOnFutex::futexWake()
+{
+    WakeByAddressSingle(&mState);
+}
+#    endif  // defined(ANGLE_PLATFORM_WINDOWS)
+}  // namespace priv
+}  // namespace angle
+
+#endif  // ANGLE_USE_FUTEX
diff --git a/src/common/SimpleMutex.h b/src/common/SimpleMutex.h
new file mode 100644
index 0000000000..a6fd8c2b0a
--- /dev/null
+++ b/src/common/SimpleMutex.h
@@ -0,0 +1,137 @@
+//
+// Copyright 2024 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// SimpleMutex.h:
+//   A simple non-recursive mutex that only supports lock and unlock operations.  As such, it can be
+//   implemented more efficiently than a generic mutex such as std::mutex.  In the uncontended
+//   paths, the implementation boils down to basically an inlined atomic operation and an untaken
+//   branch.  The implementation in this file is inspired by Mesa's src/util/simple_mtx.h, which in
+//   turn is based on "mutex3" in:
+//
+//       "Futexes Are Tricky"
+//       http://www.akkadia.org/drepper/futex.pdf
+//
+//   Given that std::condition_variable only interacts with std::mutex, SimpleMutex cannot be used
+//   with condition variables.
+//
+
+#ifndef COMMON_SIMPLEMUTEX_H_
+#define COMMON_SIMPLEMUTEX_H_
+
+#include "common/debug.h"
+#include "common/platform.h"
+
+#include <atomic>
+#include <mutex>
+
+// Enable futexes on:
+//
+// - Linux and derivatives (Android, ChromeOS, etc)
+// - Windows 8+
+//
+// There is no TSAN support for futex currently, so it is disabled in that case
+#if !defined(ANGLE_WITH_TSAN)
+#    if defined(ANGLE_PLATFORM_LINUX) || defined(ANGLE_PLATFORM_ANDROID)
+// Linux has had futexes for a very long time.  Assume support.
+#        define ANGLE_USE_FUTEX 1
+#    elif defined(ANGLE_PLATFORM_WINDOWS) && !defined(ANGLE_ENABLE_WINDOWS_UWP) && \
+        !defined(ANGLE_WINDOWS_NO_FUTEX)
+// Windows has futexes since version 8, which is already end of life (let alone older versions).
+// Assume support.
+#        define ANGLE_USE_FUTEX 1
+#    endif  // defined(ANGLE_PLATFORM_LINUX) || defined(ANGLE_PLATFORM_ANDROID)
+#endif      // !defined(ANGLE_WITH_TSAN)
+
+namespace angle
+{
+namespace priv
+{
+#if ANGLE_USE_FUTEX
+class MutexOnFutex
+{
+  public:
+    void lock()
+    {
+        uint32_t oldState    = kUnlocked;
+        const bool lockTaken = mState.compare_exchange_strong(oldState, kLocked);
+
+        // In uncontended cases, the lock is acquired and there's nothing to do
+        if (ANGLE_UNLIKELY(!lockTaken))
+        {
+            ASSERT(oldState == kLocked || oldState == kBlocked);
+
+            // If not already marked as such, signal that the mutex is contended.
+            if (oldState != kBlocked)
+            {
+                oldState = mState.exchange(kBlocked, std::memory_order_acq_rel);
+            }
+            // Wait until the lock is acquired
+            while (oldState != kUnlocked)
+            {
+                futexWait();
+                oldState = mState.exchange(kBlocked, std::memory_order_acq_rel);
+            }
+        }
+    }
+    void unlock()
+    {
+        // Unlock the mutex
+        const uint32_t oldState = mState.fetch_add(-1, std::memory_order_acq_rel);
+
+        // If another thread is waiting on this mutex, wake it up
+        if (ANGLE_UNLIKELY(oldState != kLocked))
+        {
+            mState.store(kUnlocked, std::memory_order_relaxed);
+            futexWake();
+        }
+    }
+    void assertLocked() { ASSERT(mState.load(std::memory_order_relaxed) != kUnlocked); }
+
+  private:
+    void futexWait();
+    void futexWake();
+
+    // Note: the ordering of these values is important due to |unlock()|'s atomic decrement.
+    static constexpr uint32_t kUnlocked = 0;
+    static constexpr uint32_t kLocked   = 1;
+    static constexpr uint32_t kBlocked  = 2;
+
+    std::atomic_uint32_t mState = 0;
+};
+#else   // !ANGLE_USE_FUTEX
+class MutexOnStd
+{
+  public:
+    void lock() { mutex.lock(); }
+    void unlock() { mutex.unlock(); }
+    void assertLocked() { ASSERT(isLocked()); }
+
+  private:
+    bool isLocked()
+    {
+        // This works because angle::SimpleMutex does not support recursion
+        const bool acquiredLock = mutex.try_lock();
+        if (acquiredLock)
+        {
+            mutex.unlock();
+        }
+
+        return !acquiredLock;
+    }
+
+    std::mutex mutex;
+};
+#endif  // ANGLE_USE_FUTEX
+}  // namespace priv
+
+#if ANGLE_USE_FUTEX
+using SimpleMutex = priv::MutexOnFutex;
+#else
+using SimpleMutex = priv::MutexOnStd;
+#endif
+
+}  // namespace angle
+
+#endif  // COMMON_SIMPLEMUTEX_H_
diff --git a/src/common/SimpleMutex_unittest.cpp b/src/common/SimpleMutex_unittest.cpp
new file mode 100644
index 0000000000..0b7f909e72
--- /dev/null
+++ b/src/common/SimpleMutex_unittest.cpp
@@ -0,0 +1,94 @@
+//
+// Copyright 2024 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// SimpleMutex_unittest:
+//   Tests of the SimpleMutex class
+//
+
+#include <gtest/gtest.h>
+
+#include "common/SimpleMutex.h"
+
+namespace angle
+{
+namespace
+{
+struct NoOpMutex
+{
+    void lock() {}
+    void unlock() {}
+};
+
+template <typename TestMutex>
+bool runBasicMutexTest()
+{
+    constexpr size_t kThreadCount    = 16;
+    constexpr size_t kIterationCount = 50'000;
+
+    std::array<std::thread, kThreadCount> threads;
+
+    std::mutex mutex;
+    std::condition_variable condVar;
+    size_t readyCount = 0;
+
+    TestMutex testMutex;
+    std::atomic<size_t> testVar;
+
+    for (size_t i = 0; i < kThreadCount; ++i)
+    {
+        threads[i] = std::thread([&]() {
+            // Wait for all threads to start, so the following loop is as simultaneously executed as
+            // possible.
+            {
+                std::unique_lock<std::mutex> lock(mutex);
+                ++readyCount;
+                if (readyCount < kThreadCount)
+                {
+                    condVar.wait(lock, [&]() { return readyCount == kThreadCount; });
+                }
+                else
+                {
+                    condVar.notify_all();
+                }
+            }
+            for (size_t j = 0; j < kIterationCount; ++j)
+            {
+                std::lock_guard<TestMutex> lock(testMutex);
+                const int local    = testVar.load(std::memory_order_relaxed);
+                const int newValue = local + 1;
+                testVar.store(newValue, std::memory_order_relaxed);
+            }
+        });
+    }
+
+    for (size_t i = 0; i < kThreadCount; ++i)
+    {
+        threads[i].join();
+    }
+
+    const bool passed = testVar.load() == kThreadCount * kIterationCount;
+    return passed;
+}
+}  // anonymous namespace
+
+// Tests basic usage of std::mutex.
+TEST(MutexTest, BasicStdMutex)
+{
+    EXPECT_TRUE(runBasicMutexTest<std::mutex>());
+}
+
+// Tests basic usage of angle::SimpleMutex.
+TEST(MutexTest, BasicSimpleMutex)
+{
+    EXPECT_TRUE(runBasicMutexTest<SimpleMutex>());
+}
+
+// Tests failure with NoOpMutex.
+TEST(MutexTest, BasicNoOpMutex)
+{
+    // Technically not _guaranteed_ to calculate the wrong value, but highly likely to do so.
+    EXPECT_FALSE(runBasicMutexTest<NoOpMutex>());
+}
+}  // namespace angle
diff --git a/src/libGLESv2.gni b/src/libGLESv2.gni
index 10565a1821..3f67ef3a27 100644
--- a/src/libGLESv2.gni
+++ b/src/libGLESv2.gni
@@ -19,6 +19,7 @@ libangle_common_headers = [
   "src/common/PackedGLEnums_autogen.h",
   "src/common/PoolAlloc.h",
   "src/common/RingBufferAllocator.h",
+  "src/common/SimpleMutex.h",
   "src/common/Spinlock.h",
   "src/common/SynchronizedValue.h",
   "src/common/WorkerThread.h",
@@ -71,6 +72,7 @@ libangle_common_sources = libangle_common_headers + [
                             "src/common/PackedGLEnums_autogen.cpp",
                             "src/common/PoolAlloc.cpp",
                             "src/common/RingBufferAllocator.cpp",
+                            "src/common/SimpleMutex.cpp",
                             "src/common/WorkerThread.cpp",
                             "src/common/aligned_memory.cpp",
                             "src/common/android_util.cpp",
diff --git a/src/tests/angle_unittests.gni b/src/tests/angle_unittests.gni
index f5ff5ef15c..e51beffcb6 100644
--- a/src/tests/angle_unittests.gni
+++ b/src/tests/angle_unittests.gni
@@ -14,6 +14,7 @@ angle_unittests_sources = [
   "../common/FixedVector_unittest.cpp",
   "../common/Optional_unittest.cpp",
   "../common/PoolAlloc_unittest.cpp",
+  "../common/SimpleMutex_unittest.cpp",
   "../common/WorkerThread_unittest.cpp",
   "../common/aligned_memory_unittest.cpp",
   "../common/angleutils_unittest.cpp",