futex.h

#pragma once
#include "gaia/config/config.h"
#include "gaia/config/profiler.h"
 
#include <atomic>
#include <mutex>
 
#include "gaia/core/utility.h"
#include "gaia/mt/event.h"
 
namespace gaia {
  namespace mt {
    namespace detail {
      inline static constexpr uint32_t WaitMaskAll = 0x7FFFFFFF;
      inline static constexpr uint32_t WaitMaskAny = ~0u;
 
      struct FutexWaitNode {
        FutexWaitNode* pNext = nullptr;
        const std::atomic_uint32_t* pFutexValue = nullptr;
        uint32_t waitMask = WaitMaskAny;
        Event evt;
      };
 
      struct FutexBucket {
        GAIA_PROF_MUTEX(std::mutex, mtx);
        FutexWaitNode* pFirst = nullptr;
 
        // Since there shouldn't be that many threads waiting at any one time, this seems like a good
        // number of hash table buckets. Making it prime number for better spread.
        static constexpr uint32_t BUCKET_SIZE = 37;
 
        static FutexBucket& get(const std::atomic_uint32_t* pFutexValue) {
          static FutexBucket s_buckets[BUCKET_SIZE];
          return s_buckets[(uintptr_t(pFutexValue) >> 2) % BUCKET_SIZE];
        }
      };
 
      inline thread_local FutexWaitNode t_WaitNode;
 
    } // namespace detail
 
    struct Futex {
      enum class Result {
        Change,
        WakeUp
      };
 
      static Result wait(const std::atomic_uint32_t* pFutexValue, uint32_t expected, uint32_t waitMask) {
        GAIA_PROF_SCOPE(futex::wait);
 
        GAIA_ASSERT(waitMask != 0);
 
        auto& bucket = detail::FutexBucket::get(pFutexValue);
        auto& node = detail::t_WaitNode;
        node.pFutexValue = pFutexValue;
        node.waitMask = waitMask;
 
        {
          auto& mtx = GAIA_PROF_EXTRACT_MUTEX(bucket.mtx);
          core::lock_scope lock(mtx);
          GAIA_PROF_LOCK_MARK(bucket.mtx);
 
          const uint32_t futexValue = pFutexValue->load(std::memory_order_relaxed);
          if (futexValue != expected)
            return Result::Change;
 
          node.pNext = bucket.pFirst;
          bucket.pFirst = &node;
        }
 
        node.evt.wait();
        return Result::WakeUp;
      }
 
      static uint32_t
      wake(const std::atomic_uint32_t* pFutexValue, uint32_t wakeCount, uint32_t wakeMask = detail::WaitMaskAny) {
        GAIA_PROF_SCOPE(futex::wake);
 
        GAIA_ASSERT(wakeMask != 0);
 
        auto& bucket = detail::FutexBucket::get(pFutexValue);
        auto& mtx = GAIA_PROF_EXTRACT_MUTEX(bucket.mtx);
        core::lock_scope lock(mtx);
        GAIA_PROF_LOCK_MARK(bucket.mtx);
 
        uint32_t numAwoken = 0;
        auto** ppNode = &bucket.pFirst;
        for (auto* pNode = *ppNode; numAwoken < wakeCount && pNode != nullptr; pNode = *ppNode) {
          if (pNode->pFutexValue == pFutexValue && (pNode->waitMask & wakeMask) != 0) {
            ++numAwoken;
 
            // Unlink the node
            *ppNode = pNode->pNext;
            pNode->pNext = nullptr;
 
            pNode->evt.set();
          } else {
            ppNode = &pNode->pNext;
          }
        }
 
        return numAwoken;
      }
    };
  } // namespace mt
} // namespace gaia