Re: Futex Stack Test...

On 5/2/2025 4:01 AM, Wuns Haerst wrote:

It's not hard to implement a lock-free stack with DW-CAS,
so no need for futexes. That's my dcas_atomic:
 #pragma once
#include <cstdint>
#include <utility>
#include <atomic>
#include <type_traits>
#include <climits>
#include <bit>
#include <memory>
 #if defined(_MSC_VER)
     #pragma warning(push)
     #pragma warning(disable: 26495)
#endif
#if defined(__llvm__)
     #pragma clang diagnostic push
     #pragma clang diagnostic ignored "-Watomic-alignment"
#endif
 constexpr int
     DCAS_ACQ_REL = (int)std::memory_order::acq_rel,
     DCAS_ACQUIRE = (int)std::memory_order::acquire,
     DCAS_RELAXED = (int)std::memory_order::relaxed,
     DCAS_RELEASE = (int)std::memory_order::release,
     DCAS_SEQ_CST = (int)std::memory_order::seq_cst;
template<int Type>
using dcas_type = std::integral_constant<int, Type>;
using dcas_acq_rel = dcas_type<DCAS_ACQ_REL>;
using dcas_acquire = dcas_type<DCAS_ACQUIRE>;
using dcas_relaxed = dcas_type<DCAS_RELAXED>;
using dcas_release = dcas_type<DCAS_RELEASE>;
using dcas_seq_cst = dcas_type<DCAS_SEQ_CST>;
 struct dcas_atomic
{
     static_assert(sizeof(size_t) == 8 || sizeof(size_t) == 4, "must be 64 or 32 bit architecture");
     struct pair_t { size_t first, second; };
     dcas_atomic() = default;
     dcas_atomic( pair_t const &desired );
     std::atomic<size_t> &first() noexcept;
     std::atomic<size_t> &second() noexcept;
     operator pair_t() noexcept;
     template<int Type>
     bool compare_exchange( pair_t &expected, pair_t const &desired, dcas_type<Type> = dcas_seq_cst() ) noexcept;
     template<int Type>
     pair_t load( dcas_type<Type> = dcas_seq_cst() ) const noexcept;
     template<int Type>
     void store( pair_t const &niu, dcas_type<Type> = dcas_seq_cst() ) noexcept;
private:
#if defined(__GNUC__) || defined(__clang__) && !defined(_MSC_VER)
     #if SIZE_WIDTH == 64
     using dword_t = unsigned __int128;
     #elif SIZE_WIDTH == 32
     using dword_t = unsigned long long;
     #else
         #error unknown architecture
     #endif
#endif
     union alignas(2 * sizeof(size_t)) U
     {
         U() {}
         static_assert(sizeof(std::atomic<size_t>) == sizeof(size_t), "sizeof(atomic<size_t>) must be == sizeof(size_t)");
         std::atomic<size_t> m_atomics[2];
#if defined(_MSC_VER)
     #if defined(_M_X64) || defined(_M_ARM64) || defined(_M_ARM64EC)
         __int64 volatile m_firstAndSecond[2];
     #elif defined(_M_IX86)
         __int64 volatile m_firstAndSecond;
     #else
         #error unknown architecture
     #endif
#elif defined(__GNUC__) || defined(__clang__)
         dword_t volatile m_firstAndSecond;
#endif
     } u;
};
 inline dcas_atomic::dcas_atomic( pair_t const &desired )
{
     u.m_atomics[0].store( desired.first, std::memory_order_relaxed );
     u.m_atomics[1].store( desired.second, std::memory_order_relaxed );
}
 inline std::atomic<size_t> &dcas_atomic::first() noexcept
{
     return u.m_atomics[0];
}
 inline std::atomic<size_t> &dcas_atomic::second() noexcept
{
     return u.m_atomics[1];
}
 inline dcas_atomic::operator pair_t() noexcept
{
     return pair_t( first().load( std::memory_order_relaxed ), second().load( std::memory_order_relaxed ) );
}
 template<int Type>
inline bool dcas_atomic::compare_exchange( pair_t &expected, pair_t const &desired, dcas_type<Type> ) noexcept
{
     using namespace std;
     static_assert(Type == DCAS_ACQ_REL || Type == DCAS_ACQUIRE || Type == DCAS_RELAXED || Type == DCAS_RELEASE || Type == DCAS_SEQ_CST);
#if defined(_MSC_VER)
     #if defined(_M_X64) || defined(_M_ARM64) || defined(_M_ARM64EC)
     __int64 expectedA[2];
     expectedA[0] = (__int64)expected.first;
     expectedA[1] = (__int64)expected.second;
     char fRet;
     #if defined(_M_X64)
     fRet = _InterlockedCompareExchange128( u.m_firstAndSecond, desired.second, desired.first, expectedA );
     #else
     if constexpr( Type == DCAS_ACQ_REL || Type == DCAS_SEQ_CST )
         fRet = _InterlockedCompareExchange128( u.m_firstAndSecond, desired.second, desired.first, expectedA );
     else if constexpr( Type == DCAS_ACQUIRE )
         fRet = _InterlockedCompareExchange128_acq( u.m_firstAndSecond, desired.second, desired.first, expectedA );
     else if constexpr( Type == DCAS_RELAXED )
         fRet = _InterlockedCompareExchange128_nf( u.m_firstAndSecond, desired.second, desired.first, expectedA );
     else
         fRet = _InterlockedCompareExchange128_rel( u.m_firstAndSecond, desired.second, desired.first, expectedA );
     #endif
     if( fRet )
         return true;
     expected.first = expectedA[0];
     expected.second = expectedA[1];
     return false;
     #elif defined(_M_IX86)
     auto compose = []( pair_t const &p ) -> uint64_t { return p.first | (uint64_t)p.second << 32; };
     uint64_t
         cDesired = compose( desired ),
         cExpected = compose( expected ),
         cResult = _InterlockedCompareExchange64( &u.m_firstAndSecond, cDesired, cExpected );
     if( cResult == cExpected ) [[likely]]
         return true;
     expected.first = (uint32_t)cResult;
     expected.second = (uint32_t)(cResult >> 32);
     return false;
     #else
         #error unspupported Windows-platform
     #endif
#elif defined(__GNUC__) || defined(__clang__)
     constexpr auto
         pair_t::*FIRST = std::endian::native == std::endian::little ? &pair_t::first : &pair_t::second,
         pair_t::*SECOND = std::endian::native == std::endian::little ? &pair_t::second : &pair_t::first;
     auto compose = []( pair_t const &p ) -> dword_t    { return (dword_t)(p.*FIRST) | (dword_t)(p.*SECOND) << SIZE_WIDTH; };
     dword_t
         dwExpected = compose( expected ),
         dwDesired = compose( desired );
     bool ret;
     if constexpr( Type == DCAS_ACQ_REL )
         ret = __atomic_compare_exchange_n( &u.m_firstAndSecond, &dwExpected, dwDesired, true, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED );
     else if constexpr( Type == DCAS_ACQUIRE )
         ret = __atomic_compare_exchange_n( &u.m_firstAndSecond, &dwExpected, dwDesired, true, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED );
     else if constexpr( Type == DCAS_RELAXED )
         ret = __atomic_compare_exchange_n( &u.m_firstAndSecond, &dwExpected, dwDesired, true, __ATOMIC_RELAXED, __ATOMIC_RELAXED );
     else if constexpr( Type == DCAS_RELEASE )
         ret = __atomic_compare_exchange_n( &u.m_firstAndSecond, &dwExpected, dwDesired, true, __ATOMIC_RELEASE, __ATOMIC_RELAXED );
     else
         ret = __atomic_compare_exchange_n( &u.m_firstAndSecond, &dwExpected, dwDesired, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED );
     if( ret ) [[likely]]
         return true;
     expected.*FIRST = (size_t)dwExpected;
     expected.*SECOND = (size_t)(dwExpected >> SIZE_WIDTH);
     return false;
#else
     #error unspupported platform
#endif
}
 template<int Type>
inline typename dcas_atomic::pair_t dcas_atomic::load( dcas_type<Type> ) const noexcept
{
     using namespace std;
     static_assert(Type == DCAS_ACQ_REL || Type == DCAS_ACQUIRE || Type == DCAS_RELAXED || Type == DCAS_RELEASE || Type == DCAS_SEQ_CST);
     pair_t cmp( 0, 0 );
     const_cast<dcas_atomic *>(this)->compare_exchange( cmp, cmp, dcas_type<Type>() );
     return cmp;
}
 template<int Type>
inline void dcas_atomic::store( pair_t const &niu, dcas_type<Type> ) noexcept
{
     using namespace std;
     static_assert(Type == DCAS_ACQ_REL || Type == DCAS_ACQUIRE || Type == DCAS_RELAXED || Type == DCAS_RELEASE || Type == DCAS_SEQ_CST);
     pair_t cmp( *this );
     while( !this->compare_exchange( cmp, niu, dcas_type<Type>() ) );
}
 #if defined(_MSC_VER)
     #pragma warning(pop)
#endif
#if defined(__llvm__)
     #pragma clang diagnostic pop
#endif

Hard to read that mess. Where is your push and pop, and where are you bumping the ABA counter?