Path: ...!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups: comp.lang.c++
Subject: Ported my proxy collector...
Date: Mon, 16 Sep 2024 16:08:51 -0700
Organization: A noiseless patient Spider
Lines: 431
Message-ID: <vcadq3$340q3$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 17 Sep 2024 01:08:52 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="2d41bb0e6a21724e79465d793e720c2a";
	logging-data="3277635"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+baTLE9flW4Fn3jFzfT723iuC6/v7w56k="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:aJlqeESUdBmiAaTmDTVOwcPEj6c=
Content-Language: en-US
Bytes: 11033

This is a just quick port form Relacy to C++. The collector has the 
ability to allow a lock-free stack, queues, ect... to be used without 
any DWCAS on a pop operation. Also, it takes care of memory management 
issues with the nodes...

Well here is my crude test code. Keep in mind that the 
g_debug_alloc/free global's are only there for debugging purposes at 
this early stage. They can be removed. This is akin to a poor mans RCU, 
in a sense... Well, can you compile and run it when you get some really 
free time to burn?

Thanks everybody. :^)
_________________________________________


#include <cassert>
#include <iostream>
#include <atomic>
#include <thread>


#define CT_READERS 10
#define CT_WRITERS 10
#define CT_THREADS (CT_WRITERS + CT_READERS)
#define CT_ITERS 10000000
#define CT_COLLECT 10240


// These are for debug and some statistics only...
static std::atomic<unsigned long> g_debug_alloc(0);
static std::atomic<unsigned long> g_debug_free(0);


// Chris M. Thomassons single target proxy collector:
// https://pastebin.com/raw/f71480694

namespace ct_proxy
{
     struct node
     {
         std::atomic<node*> m_next;
         node* m_defer_next;

         node()
         {
             // debug only!
             g_debug_alloc.fetch_add(1);
         }

         ~node()
         {
             // debug only!
             g_debug_free.fetch_add(1);
         }
     };


     class proxy
     {
         static void prv_destroy(node* n)
         {
             while (n)
             {
                 node* next = n->m_defer_next;
                 delete n;
                 n = next;
             }
         }



     public:
         class collector
         {
             friend class proxy;



         private:
             std::atomic<node*> m_defer;
             std::atomic<unsigned int> m_count;



         public:
             collector()
             :   m_defer(nullptr),
                 m_count(0)
             {

             }


             ~collector()
             {
                 prv_destroy(m_defer.load(std::memory_order_relaxed));
             }
         };



     private:
         std::atomic<unsigned int> m_current;
         std::atomic<bool> m_quiesce;
         node* m_defer;
         collector m_collectors[2];



     public:
         proxy()
         :   m_current(0),
             m_quiesce(false),
             m_defer(nullptr)
         {

         }

         ~proxy()
         {
             prv_destroy(m_defer);
         }



     private:
         void prv_quiesce_begin()
         {
             // Try to begin the quiescence process.
             if (! m_quiesce.exchange(true, std::memory_order_acquire))
             {
                 // advance the current collector and grab the old one.
                 unsigned int old = 
m_current.load(std::memory_order_relaxed) & 0xFU;
                 old = m_current.exchange((old + 1) & 1, 
std::memory_order_acq_rel);
                 collector& c = m_collectors[old & 0xFU];

                 // decode reference count.
                 unsigned int refs = old & 0xFFFFFFF0U;

                 // verify reference count and previous collector index.
                 assert(! (refs & 0x10U) && (old & 0xFU) == (&c - 
m_collectors));

                 // increment and generate an odd reference count.
                 if (c.m_count.fetch_add(refs + 0x10U, 
std::memory_order_release) == -(int)refs)
                 {
                     // odd reference count and drop-to-zero condition 
detected!
                     prv_quiesce_complete(c);
                 }
             }
         }


         void prv_quiesce_complete(collector& c)
         {
             // the collector `c' is now in a quiescent state! :^)
             std::atomic_thread_fence(std::memory_order_acquire);

             // maintain the back link and obtain "fresh" objects from
             // this collection.
             node* n = m_defer;
             m_defer = c.m_defer.load(std::memory_order_relaxed);
             c.m_defer.store(0, std::memory_order_relaxed);

             // verify and reset the reference count.
             assert(c.m_count.load(std::memory_order_relaxed) == 0x10U);
             c.m_count.store(0, std::memory_order_relaxed);

             // release the quiesce lock.
             m_quiesce.store(false, std::memory_order_release);

             // destroy nodes.
             prv_destroy(n);
         }



========== REMAINDER OF ARTICLE TRUNCATED ==========