• Relacy version of my futex lock-free stack...

    From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sat Nov 14 20:26:00 2026
    From Newsgroup: comp.lang.c++

    Okay. I finally found some time to port my old experimental lock-free
    stack that can be waited on via a futex. When you get some free time to
    burn, check out my code. Even get Relacy working, and run the sucker!

    Its neat to me that my old code passes Relacy. Makes me feel pretty
    good. Now, take notice how I am only using one producer here that does a
    fancy shutdown using a "handoff", akin to pass the buck. It only uses
    flush for the consumers. No ABA, no memory usage issues, everything rocks!

    Here is my relacy test unit: (ct_stack_futex.hpp) __________________________________

    #pragma once

    #include <relacy/relacy.hpp>
    #include <cstdio>
    #include <cstddef>


    namespace ct
    {
    namespace futex_test
    {
    constexpr unsigned long CT_THREADS_WORKERS = 5;
    constexpr unsigned long CT_THREADS = 1 + CT_THREADS_WORKERS; // thread 0 = producer/collector
    constexpr unsigned long CT_WORK_N = 42;
    constexpr unsigned long CT_STATE_SHUTDOWN = 666;

    struct ct_node
    {
    VAR_T(ct_node*) m_next = { nullptr };
    };

    struct ct_work : ct_node
    {
    VAR_T(unsigned long) m_state = { 0 };
    };

    // Sentinel stored in the head: "consumer is (about to be) asleep".
    // Never dereferenced.
    inline ct_node*
    ct_wait()
    {
    return reinterpret_cast<ct_node*>(0xDEADBEEF);
    }

    inline bool
    ct_is_empty(
    ct_node* head
    ) {
    return ! head || head == ct_wait();
    }

    inline ct_work*
    ct_make_work(
    unsigned long state = 0
    ) {
    ct_work* w = new ct_work;
    VAR(w->m_state) = state;
    return w;
    }

    // Walk a detached list. 'next' is read BEFORE fn runs, because
    fn may
    // delete the node or push it onto another stack.
    template<typename fn_t>
    void
    ct_drain(
    ct_node* head,
    fn_t&& fn
    ) {
    while (head)
    {
    ct_node* next = VAR(head->m_next);
    fn(static_cast<ct_work*>(head));
    head = next;
    }
    }

    struct ct_stack
    {
    rl::atomic<ct_node*> m_head = { nullptr };

    void
    push(
    ct_node* node
    ) {
    ct_node* head = m_head.load(rl::mo_relaxed, $);

    do
    {
    VAR(node->m_next) = (head == ct_wait()) ? nullptr :
    head;

    } while (! m_head.compare_exchange_weak(
    head,
    node,
    rl::mo_release, // needed for sure
    rl::mo_relaxed,
    $)
    );

    if (head == ct_wait())
    {
    // slow path...
    m_head.notify_one($);
    }
    }

    ct_node*
    flush_wait()
    {
    ct_node* head = m_head.exchange(nullptr,
    rl::mo_acquire, $);

    while (ct_is_empty(head))
    {
    // slow path...
    head = m_head.exchange(ct_wait(), rl::mo_acquire, $);

    if (ct_is_empty(head))
    {
    m_head.wait(ct_wait(), rl::mo_relaxed, $);
    }
    }

    RL_ASSERT(! ct_is_empty(head));

    return head;
    }
    };

    struct state
    {
    ct_stack m_in;
    ct_stack m_out;

    void
    after()
    {
    // Everything has stopped, hence relaxed. The shutdown
    nodes
    // were pushed back onto m_in by the workers, so free them.
    ct_node* head = m_in.m_head.load(rl::mo_relaxed, $);

    if (! ct_is_empty(head))
    {
    ct_drain(head, [](ct_work* w) { delete w; });
    }

    // m_out must be empty or ct_wait()
    RL_ASSERT(ct_is_empty(m_out.m_head.load(rl::mo_relaxed,
    $)));
    }
    };

    // the actual test unit...
    struct futex_test_v000
    : rl::test_suite<futex_test_v000, CT_THREADS>
    {
    state m_state = {};

    void before() {}
    void after() { m_state.after(); }

    void
    thread_main()
    {
    for (unsigned long i = 0; i < CT_WORK_N; ++i)
    {
    m_state.m_in.push(ct_make_work());
    }

    for (unsigned long wn = 0; wn < CT_WORK_N; )
    {
    ct_drain(m_state.m_out.flush_wait(), [&](ct_work* w)
    {
    delete w;
    ++wn;
    });
    }

    // Send shutdown state, one per worker...
    for (unsigned long i = 0; i < CT_THREADS_WORKERS; ++i)
    {
    m_state.m_in.push(ct_make_work(CT_STATE_SHUTDOWN));
    }
    }

    void
    thread_worker()
    {
    bool shutdown = false;

    while (! shutdown)
    {
    ct_drain(m_state.m_in.flush_wait(), [&](ct_work* w)
    {
    if (VAR(w->m_state) == CT_STATE_SHUTDOWN)
    {
    // Re-push so the next worker sees it too.
    shutdown = true;
    m_state.m_in.push(w);
    }

    else
    {
    m_state.m_out.push(w);
    }
    });
    }
    }

    void
    thread(
    unsigned int tidx
    ) {
    if (tidx == 0)
    {
    thread_main();
    }

    else
    {
    thread_worker();
    }
    }
    };
    }
    }

    namespace ct
    {
    namespace futex_test
    {
    namespace test
    {
    inline void
    manifest(
    rl::test_params& p
    ) {
    rl::simulate<ct::futex_test::futex_test_v000>(p);
    }
    }
    }
    }
    __________________________________




    My driver code ct_main.cpp:
    __________________________________
    #include <relacy/relacy.hpp>
    #include <cstdio>
    #include <cstddef>
    #include <cstdlib>
    #include <string>
    #include <iostream>


    // tests
    #include "ct_smr_proxy.hpp"
    #include "ct_proxy_test.hpp"
    #include "ct_smr_test.hpp"
    #include "ct_multex_test.hpp"
    #include "ct_stack_futex.hpp"


    #include <cstdio>
    #include <cstddef>
    #include <cstdlib>
    #include <string>
    #include <vector>


    int
    main(
    int argc,
    char** argv
    ) {
    {
    rl::test_params p;

    p.iteration_count = argc > 1 ? (unsigned)atoi(argv[1]) : 5000000;
    p.execution_depth_limit = 1000000;

    if (argc > 2) {
    std::string m = argv[2];
    if (m == "full") p.search_type = rl::sched_full;
    else if (m == "bound") { p.search_type = rl::sched_bound; p.context_bound = argc > 3 ? atoi(argv[3]) : 2; }
    }


    {
    //ct::proxy_test::test::manifest(p);
    // ct::multex_test::test::manifest(p);
    //ct::smr_test::test::manifest(p);
    //ct::smr_proxy::test::manifest(p);

    {
    std::printf("CT_WORK_N = %lu, CT_THREADS = %lu\n",
    ct::futex_test::CT_WORK_N,
    ct::futex_test::CT_THREADS);

    //p.search_type = rl::sched_bound;
    //p.context_bound = 2;

    ct::futex_test::test::manifest(p);
    }

    }
    }

    return 0;
    }
    __________________________________
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sun Nov 15 00:20:55 2026
    From Newsgroup: comp.lang.c++

    On 11/14/2026 8:26 PM, Chris M. Thomasson wrote:
    Okay. I finally found some time to port my old experimental lock-free
    stack that can be waited on via a futex. When you get some free time to burn, check out my code. Even get Relacy working, and run the sucker!

    Its neat to me that my old code passes Relacy. Makes me feel pretty
    good. Now, take notice how I am only using one producer here that does a fancy shutdown using a "handoff", akin to pass the buck. It only uses
    flush for the consumers. No ABA, no memory usage issues, everything rocks!

    Here is my relacy test unit: (ct_stack_futex.hpp)[...]

    Distributing this might be a little interesting! Makes me want to use an eventcount over a futex.
    --- Synchronet 3.22a-Linux NewsLink 1.2