Re: Wait-free Hazard Pointers Using Std Atomics

On 5/29/2025 2:17 PM, jseigh wrote:

On 5/28/25 18:34, Chris M. Thomasson wrote:

On 5/26/2025 2:58 PM, jseigh wrote:

and asymmetric memory barriers of course.
>
https://threadnought.wordpress.com/2025/05/26/wait-free-hazard- pointers- using-std-atomics/
>
Looks like it runs faster without the conditional branch.
>
Not sure it's a new idea.  The only wait-free version of hazard pointers
I've seen so far involves a storage to storage move instruction which
might not be available on all platforms.
>
Joe Seigh

>
Actually wrt:
_______________
hz_ptr.store(INDETERMINATE, std::memory_order_relaxed);
T* local = ptr.load(std::memory_order_relaxed);
hz_ptr.store(local, std::memory_order_relaxed);
_______________
>
For some damn reason, it kind of reminds me of an older way to use only single word exchange to push into a lock-free stack.
>
Iirc, something like this pseudo code for push:
_____________
cur->next = WAIT_STATE;
node* prev = exchange(head, cur);
cur->next = prev;
_____________
>
There is a "window" in there where cur->next will be WAIT_STATE. So, when a thread iterating the list, say after pop all, flush, it can do a couple of spins or do something else during iteration on a cur->next being in WAIT_STATE. It's a way to get exchange on push and pop of a stack.
>
The window is very small. I am having trouble finding on this group where I posted about it before in a working program...
>

 Push may wait-free but pop isn't event lock-free.

Well, yeah in a sense, keep in mind that the fast path for the pop is a single exchange. I guess it depends on how we process the nodes with a stack that can have a window for a next pointer to be in a WAIT_STATE wrt the fun goal (experiment) of having exchange for push and exchange for pop, no CAS, let alone DWCAS. One way, is instead of a worker thread spinning on a WAIT_STATE during iteration, the node has another next pointer so the thread can link the waits into a per-thread stack. Then try something else, or switch processing to another stack. It pushes the node with a WAIT_STATE into a per-thread stack, then tries another stack in the distributed multi-stack. If it does execute a unit of work, that right there can be a natural backoff to trigger it to try the per-thread stack of wait states. However, this would make a node have two node links instead of one. It just might be fun to mock up and run.
Actually, I like my futex stack experiment as is. normal CAS for push, SWAP for pop. It needs to have multiple stacks and distribute across them because popping all from a single stack can mean a thread gets too much work. Push lock-free, pop wait-free.

 Anyway, after some consideration, I'm off on this
wait-free hazard pointer.  The lock-free version is
more than performant.
 Joe Seigh