Re: Futex Stack Test...

On 5/2/2025 8:02 PM, Bonita Montero wrote:

That's the atomic_stack:
 header:
 #pragma once
#if defined(_MSC_VER)
     #include <Windows.h>
#endif
#include <atomic>
#include "dcas_atomic.h"
 struct atomic_stack
{
     struct link { link *next; };
     atomic_stack();
     atomic_stack( link *pFirstItem );
     void push( link *pItem );
     void push_chain( link *pFirstItem );
     void push_chain( link *pFirstItem, link *pLastItem );
     link *pop();
     link *pop_all();
     operator bool();
private:
     using dcas_pair = typename dcas_atomic::pair_t;
     dcas_atomic m_top;
};
 inline atomic_stack::atomic_stack() :
     atomic_stack( nullptr )
{
}
 inline atomic_stack::atomic_stack( link *pFirstItem ) :
     m_top( dcas_pair( (size_t)pFirstItem, 0 ) )
{
}
 inline void atomic_stack::push_chain( link *pFirstItem )
{
     link *pLastItem = pFirstItem;
     for( ; pLastItem->next; pLastItem = pLastItem->next );
     push_chain( pFirstItem, pLastItem );
}
 inline atomic_stack::operator bool()
{
     return m_top.first();
}
 cpp:
 #include "atomic_stack.h"
 void atomic_stack::push( link *pItem )
{
     dcas_pair cmp( m_top ), niu;
     do
     {
         pItem->next = (link *)cmp.first;
         niu.first = (size_t)pItem;
         niu.second = cmp.second + 1;
     } while( !m_top.compare_exchange( cmp, niu, dcas_release() ) );
}
 void atomic_stack::push_chain( link *pFirstItem, link *pLastItem )
{
     dcas_pair cmp( m_top ), niu;
     do
     {
         pLastItem->next = (link *)cmp.first;
         niu.first = (size_t)pFirstItem;
         niu.second = cmp.second + 1;
     } while( !m_top.compare_exchange( cmp, niu, dcas_release() ) );
}
 typename atomic_stack::link *atomic_stack::pop()
{
     using namespace std;
     dcas_pair cmp, niu;
     link *pItem;
     cmp.first = m_top.first();
     if( !(pItem = (link *)cmp.first) ) [[unlikely]]
         return nullptr;
     cmp.second = m_top.second();
     for( ; ; )
     {
         niu.first = (size_t)pItem->next;
         niu.second = cmp.second + 1;
         if( m_top.compare_exchange( cmp, niu, dcas_acquire() ) ) [[likely]]
             return pItem;
         if( !(pItem = (link *)cmp.first) ) [[unlikely]]
             return nullptr;
     }
}
 typename atomic_stack::link *atomic_stack::pop_all()
{
     using namespace std;
     dcas_pair cmp, niu;
     cmp.first = m_top.first();
     if( !cmp.first ) [[unlikely]]
         return nullptr;
     cmp.second = m_top.second();
     niu.first = (size_t)nullptr;
     do
         niu.second = cmp.second + 1;
     while( !m_top.compare_exchange( cmp, niu, dcas_acquire() ) );
     return (link *)cmp.first;
}

 From a cursory read it seems fine, Bonita. Also, I had a suspicion that Wuns Haerst just "might" be you because the code style itself looked fairly similar to yours. Am I right? Also, I like the push chain. Actually, I was thinking about adding it to my my futex stack test.
Now, its fun to be able to get a lock-free stack with only single word exchange and cas, and have the ability to use it with a futex to allow one to wait on empty conditions.
Wrt DWCAS, it's a god damn shame that C++ tends to make it not lock free: That sucks! Believe it or not, there is a way to make it work with single word exchange for the push and pop. I posted about it before on this group.
Now, there is another issue with a single pop... If you delete a node, it can bite the dust. A proxy collector works well with it, but that is a bit overkill! Uggg ;^o However, iirc, SEH can be used to handle it. Iirc, that is what the SLIST uses on windows? Been a while...
There is no memory issue if you flush, or pop_all. :^)