Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #79947

A single linked list using a futex...

Show all headers | View raw

Fwiw, here is some crude Windows code I just coded up for a single 
linked list using a futex. It only supports push and flush operations 
for now. flush will wait if the stack is empty. I was to lazy to 
implement an ABA counter. However, it shows an interesting way to use a 
futex for a lock-free algorihtm.

Can you get it to run? Thanks.
__________________________________________________


// Futex Single Linked List by Chris M. Thomasson
//___________________________________________________



#include <iostream>
#include <thread>
#include <vector>
#include <functional>
#include <cassert>


#define WIN32_LEAN_AND_MEAN
#include <Windows.h>


#define CT_L2_ALIGNMENT 128
#define CT_ITERS 6666666
#define CT_NODES 42


#define CT_WAITBIT 0x1UL


static LONG g_memory_allocations = 0;
static LONG g_memory_deallocations = 0;
static LONG g_futex_signals = 0;
static LONG g_futex_waits = 0;

struct ct_node
{
     ct_node* m_next;

     ct_node() : m_next(NULL)
     {
         InterlockedAdd(&g_memory_allocations, 1);
     }

     ~ct_node()
     {
         InterlockedAdd(&g_memory_deallocations, 1);
     }
};


#define CT_NODE_SET_WAITBIT(mp_ptr) ((ct_node*)(((ULONG_PTR)(mp_ptr)) | 
CT_WAITBIT))
#define CT_NODE_CHECK_WAITBIT(mp_ptr) (((ULONG_PTR)(mp_ptr)) & CT_WAITBIT)
#define CT_NODE_CLEAR_WAITBIT(mp_ptr) ((ct_node*)(((ULONG_PTR)(mp_ptr)) 
& ~CT_WAITBIT))


void ct_node_flush(ct_node* node)
{
     while (node)
     {
         ct_node* next = node->m_next;
         delete node;
         node = next;
     }
}


struct ct_futex_slist
{
     ct_node* alignas(CT_L2_ALIGNMENT) m_head;


     ct_futex_slist() : m_head(nullptr)
     {

     }


     void push(ct_node* node)
     {
         ct_node* head = m_head;

         for (;;)
         {
             ct_node* xchg = CT_NODE_CLEAR_WAITBIT(head);
             node->m_next = xchg;

             ct_node* ret = 
(ct_node*)InterlockedCompareExchangePointer((PVOID*)&m_head, node, head);

             if (ret == head)
             {
                 if (CT_NODE_CHECK_WAITBIT(ret))
                 {
                     InterlockedAdd(&g_futex_signals, 1);
                     WakeByAddressSingle(&m_head);
                 }

                 return;
             }

             head = ret;
         }
     }


     ct_node* flush()
     {
         ct_node* head_raw = 
(ct_node*)InterlockedExchangePointer((PVOID*)&m_head, NULL);
         ct_node* head = CT_NODE_CLEAR_WAITBIT(head_raw);

         if (! head)
         {
             for (;;)
             {
                 head_raw = 
(ct_node*)InterlockedExchangePointer((PVOID*)&m_head, (ct_node*)CT_WAITBIT);
                 head = CT_NODE_CLEAR_WAITBIT(head_raw);

                 if (head)
                 {
                     break;
                 }

                 InterlockedAdd(&g_futex_waits, 1);
                 ct_node* waitbit = (ct_node*)CT_WAITBIT;
                 WaitOnAddress(&m_head, &waitbit, sizeof(PVOID), INFINITE);
             }
         }

         return head;
     }
};


struct ct_shared
{
     ct_futex_slist m_slist;


     ~ct_shared()
     {
         ct_node* head_raw = m_slist.m_head;

         if (CT_NODE_CHECK_WAITBIT(head_raw))
         {
             std::cout << "\n\nWAITBIT LEAK!\n";
         }

         ct_node_flush(head_raw);

         if (g_memory_allocations != g_memory_deallocations)
         {
             std::cout << "\n\nMEMORY LEAK!\n";
         }

         std::cout << "\ng_memory_allocations = " << 
g_memory_allocations << "\n";
         std::cout << "g_memory_deallocations = " << 
g_memory_deallocations << "\n";
         std::cout << "g_futex_waits = " << g_futex_waits << "\n";
         std::cout << "g_futex_signals = " << g_futex_signals << "\n";
     }
};


void ct_thread(ct_shared& shared)
{
     for (unsigned long i = 0; i < CT_ITERS; ++i)
     {
         for (unsigned long n = 0; n < CT_NODES; ++n)
         {
             shared.m_slist.push(new ct_node());
         }

         ct_node* node = shared.m_slist.flush();
         ct_node_flush(node);
     }

     shared.m_slist.push(new ct_node());
}


int main()
{
     unsigned int threads_n = std::thread::hardware_concurrency();

     std::vector<std::thread> threads(threads_n);

     std::cout << "Futex Single Linked List by Chris M. Thomasson\n\n";

     std::cout << "Launching " << threads_n << " threads...\n";
     std::cout.flush();

     {
         ct_shared shared;

         for (unsigned long i = 0; i < threads_n; ++i)
         {
             threads[i] = std::thread(ct_thread, std::ref(shared));
         }

         std::cout << "Processing...\n";
         std::cout.flush();

         for (unsigned long i = 0; i < threads_n; ++i)
         {
             threads[i].join();
         }
     }

     std::cout << "\nCompleted!\n";

     return 0;
}
__________________________________________________



Here is my output:
__________________________________________________
Futex Single Linked List by Chris M. Thomasson

Launching 4 threads...
Processing...

g_memory_allocations = 1119999892
g_memory_deallocations = 1119999892
g_futex_waits = 21965
g_futex_signals = 55630

Completed!
__________________________________________________

Back to comp.lang.c++ | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 19:03 -0700
  Re: A single linked list using a futex... Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-26 04:35 +0200
    Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 19:42 -0700
      Re: A single linked list using a futex... Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-26 04:45 +0200
        Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 19:57 -0700
        Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 22:59 -0700
          Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 22:59 -0700
  Re: A single linked list using a futex... Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-26 08:17 +0200
    Re: A single linked list using a futex... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-25 23:21 -0700

csiph-web