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