Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups: comp.lang.c++
Subject: Futex Stack Test...
Date: Mon, 17 Feb 2025 15:17:46 -0800
Organization: A noiseless patient Spider
Lines: 336
Message-ID: <vp0g2q$1bu96$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 18 Feb 2025 00:17:49 +0100 (CET)
Injection-Info: dont-email.me; posting-host="606ea67ab153053e6953209e514ec0eb";
	logging-data="1440038"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18Iol0+620mCHrM8396aTR7Hut+m34kENc="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:iQ5WC4sIPvicsbMbTdBKN5GRdFc=
Content-Language: en-US
Bytes: 8484

This is a little C++20 test using a futex to allow one to wait on a 
lock-free stack. The main stack logic is in struct ct_stack. Well, can 
you get to compile and run? Thanks...

I still need to check my algorithm out in Relacy. I think it might be 
able to model futex.


My code:
______________________________________
#include <iostream>
#include <thread>
#include <atomic>
#include <algorithm>
#include <cassert>


#define CT_THREAD_N (42)
#define CT_WORK_N (10000000)
#define CT_WAIT ((ct_node*)0xDEADBEEF)


struct ct_node
{
     ct_node* m_next = { nullptr };

     ct_node()
     {
         //std::cout << "(" << this << ")::ct_node::ct_node()\n";
     }

     ~ct_node()
     {
         //std::cout << "(" << this << ")::ct_node::~ct_node()\n";
     }
};


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

     void
     push(
         ct_node* node
     ) {
         ct_node* head = m_head.load(std::memory_order_relaxed);

         do
         {
             if (head == CT_WAIT)
             {
                 node->m_next = nullptr;
             }

             else
             {
                 node->m_next = head;
             }

         } while (! m_head.compare_exchange_weak(
             head,
             node,
             std::memory_order_release)
           );

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

     ct_node*
     flush_wait()
     {
         ct_node* head = nullptr;

         for (;;)
         {
             head = m_head.exchange(nullptr, std::memory_order_acquire);

             while (! head || head == CT_WAIT)
             {
                 // slow path...
                 head = m_head.exchange(CT_WAIT, std::memory_order_acquire);

                 if (! head || head == CT_WAIT)
                 {
                     m_head.wait(CT_WAIT, std::memory_order_relaxed);
                     continue;
                 }
             }

             break;
         }

         assert(head && head != CT_WAIT);

         return head;
     }
};


struct ct_work : public ct_node
{
     unsigned long m_state = { 0 };
};


struct ct_shared
{
     ct_stack m_stack_in;
     ct_stack m_stack_out;

     ct_shared()
     {
         std::cout << "ct_shared::ct_shared()\n" << std::endl;
     }

     ~ct_shared()
     {
         assert(! m_stack_in.m_head || m_stack_in.m_head == CT_WAIT);
         assert(! m_stack_out.m_head || m_stack_out.m_head == CT_WAIT);

         std::cout << "ct_shared::~ct_shared()\n" << std::endl;
     }
};


void
ct_thread(
     ct_shared& shared
) {
     unsigned long state = 0;

     while (! state)
     {
         ct_work* head = (ct_work*)shared.m_stack_in.flush_wait();

         while (head)
         {
             ct_work* next = (ct_work*)head->m_next;

             if (head->m_state == 666)
             {
                 // Shutdown detected...
                 state = 1;
                 shared.m_stack_in.push(head);
             }

             else
             {
                 shared.m_stack_out.push(head);
             }

             head = next;
         }
     }

     //std::cout << "shutdown..." << std::endl;
}


int
main()
{
     {
         std::cout << "Futex Stack Test\n";
         std::cout << "by: Chris M. Thomasson\n";
         std::cout << "version: (0.0.1)\n";
         std::cout << "_________________________________\n" << std::endl;
     }

     unsigned long g_ct_work_alloations = 0;
     unsigned long g_ct_work_dealloations = 0;

     {
         std::cout << "CT_THREAD_N = " << CT_THREAD_N << std::endl;
         std::cout << "CT_WORK_N = " << CT_WORK_N << std::endl;
         std::cout << "CT_WAIT = " << CT_WAIT << std::endl;
========== REMAINDER OF ARTICLE TRUNCATED ==========