• A lock-free stack without hazard-pointers

    From Bonita Montero@3:633/10 to All on Tue Mar 31 10:16:52 2026
    Now everything works correctly with Windows and Unix.
    I wrote a framework to catch SIGSEGV thread-specific (see below).

    #pragma once
    #if defined(_WIN32)
    #include <Windows.h>
    #include "inline.hpp"
    #elif defined(__unix__)
    #include "signal_scope.hpp"
    #else
    #error
    #endif
    #include <atomic>
    #include <bit>

    template<typename T>
    struct lockfree_stack
    {
    struct node : T
    {
    using T::T;
    private:
    template<typename T2>
    friend struct lockfree_stack;
    node *next;
    };
    void push( node *nd ) noexcept;
    node *pop() noexcept;
    private:
    // static_assert(std::bit_floor( sizeof(node) ) == sizeof(node));
    struct head { node *ptr; size_t ctr; };
    static constexpr size_t Align = 2 * sizeof(size_t);
    alignas(Align) head m_head = { nullptr, 0 };
    #if defined(_WIN32) && defined(__clang__)
    NOINLINE static node *getNext( node *nd );
    #endif
    };

    template<typename T>
    void lockfree_stack<T>::push( node *nd ) noexcept
    {
    using namespace std;
    if( !nd ) [[unlikely]]
    return;
    atomic_ref<node *> ptr( m_head.ptr );
    atomic_ref<size_t> ctr( m_head.ctr );
    head hdRef( ptr.load( memory_order_relaxed ), ctr.load( memory_order_relaxed ) );
    atomic_ref<head> aHead( m_head );
    do [[unlikely]]
    nd->next = hdRef.ptr;
    while( !aHead.compare_exchange_strong( hdRef, head( nd, hdRef.ctr + 1 ), memory_order_release, memory_order_relaxed ) );
    }

    template<typename T>
    auto lockfree_stack<T>::pop() noexcept -> node *
    {
    using namespace std;
    atomic_ref<node *> ptr( m_head.ptr );
    atomic_ref<size_t> ctr( m_head.ctr );
    auto load = [&] { return head( ptr.load( memory_order_relaxed ), ctr.load( memory_order_relaxed ) ); };
    head hdRef = load();
    atomic_ref<head> aHead( m_head );
    for( ; ; )
    {
    if( !hdRef.ptr ) [[unlikely]]
    return nullptr;
    node *next;
    #if defined(_WIN32)
    __try
    {
    #if !defined(__clang__)
    next = hdRef.ptr->next;
    #else
    next = getNext( hdRef.ptr );
    #endif
    }
    __except( EXCEPTION_EXECUTE_HANDLER )
    {
    hdRef = load();
    continue;
    }
    #elif defined(__unix__)
    if( !try_sig<SIGSEGV>( [&] { next = hdRef.ptr->m_next; } ) )
    {
    hdRef = load();
    continue;
    }
    #endif
    if( aHead.compare_exchange_strong( hdRef, head( next, hdRef.ctr + 1 ),
    memory_order_acquire, memory_order_relaxed ) ) [[likely]]
    return hdRef.ptr;
    }
    }

    #if defined(_WIN32) && defined(__clang__)

    template<typename T>
    NOINLINE auto lockfree_stack<T>::getNext( node *nd ) -> node *
    {
    return nd->next;
    }

    #endif

    --- PyGate Linux v1.5.13
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)
  • From Mr. Man-wai Chang@3:633/10 to All on Tue Apr 7 00:32:59 2026
    On 3/31/2026 4:16 PM, Bonita Montero wrote:
    Now everything works correctly with Windows and Unix.
    I wrote a framework to catch SIGSEGV thread-specific (see below).

    Task like this should be done in plain C? :)

    --

    @~@ Simplicity is Beauty! Remain silent! Drink, Blink, Stretch!
    / v \ May the Force and farces be with you! Live long and prosper!!
    /( _ )\ https://sites.google.com/site/changmw/
    ^ ^ https://github.com/changmw/changmw

    --- PyGate Linux v1.5.13
    * Origin: Dragon's Lair, PyGate NNTP<>Fido Gate (3:633/10)