A single linked list using a futex...

[Chris M. Thomasson]

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!
__________________________________________________

[Bonita Montero]

That aint lock-free because a futex is a kernel-facility !

[Chris M. Thomasson]

On 5/25/2021 7:35 PM, Bonita Montero wrote:
> That aint lock-free because a futex is a kernel-facility !

It has 100% lock-free fast-paths. The slow paths will wait/signal only
when the algorihtm has to. Can you tell the slow paths apart from the
fast ones?

Adding waiting ability to a lock-free structure can be beneficial. No
polling, we can actually wait.

[Bonita Montero]

> It has 100% lock-free fast-paths. ...

A lock-free algorithm is a algorithm _without any_ kernel-interventon.
Any slow paths make it not lock-free.

[Chris M. Thomasson]

Okay. Well, lets call it a hybrid then. It definitely has lock-free fast
paths. At least it outperforms a mutex/condvar based single linked list.

[Chris M. Thomasson]

On 5/25/2021 7:45 PM, Bonita Montero wrote:

When you get some free time, can you give it a go? compile and run it?
iI am interest in your output. Thanks Bonita.

[Chris M. Thomasson]

God damn typos!

I am interested in your output: Thanks Bonita.

[Bonita Montero]

I'm too lazy to read your code.

> #define CT_L2_ALIGNMENT 128

But this is a false assumption. Except from the Intel Pentium 4 and
the IBM POWER's L4-caches (embedded DRAM) there are AFAIK no caches
that have 128 byte cacheline size. 128 byte cachelines have been pro-
ven to be inefficient below a certain cache-size because the cache-
lines become used too partitially as there's a too less reusage-be-
haviour of the working-set.
Better use this:
https://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size

[Chris M. Thomasson]

Yes, you are correct. std::hardware_constructive_interference_size is
the way to go. Thanks for taking a look at my code to begin with Bonita!

:^)