Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups: comp.lang.c++
Subject: Re: Wait-free Hazard Pointers Using Std Atomics
Date: Sun, 1 Jun 2025 13:19:32 -0700
Organization: A noiseless patient Spider
Lines: 87
Message-ID: <101ickl$2erne$3@dont-email.me>
References: <1012o73$276nn$1@dont-email.me> <101830t$3faku$1@dont-email.me>
 <101aisl$2cjp$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 01 Jun 2025 22:19:33 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="37fd7e71eeb0e1879eb9fea5fde6a77a";
	logging-data="2584302"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18l4+tLtfErgr3ckNnLgy84H1SbQG4nFj4="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:70Jjvak77vzhcQf3O8BsJ0QxuvQ=
Content-Language: en-US
In-Reply-To: <101aisl$2cjp$1@dont-email.me>

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, the fast path of the "special" stack pop is a simple exchange, so 
that action should be wait-free? I need to code this up, but I am 
thinking along the lines of, wrt integrating the single exchange push 
with the futex, might be something like this crude pseudo-code. I just 
need to implement it.

cur->next = WAIT_STATE;

node* prev = head.exchange(cur);

if (! prev || prev == WAIT_FUTEX)
{
     cur->next = nullptr;
}

else
{
     cur->next = prev;
}

// now, wait state is cleared.

if (prev == WAIT_FUTEX)
    signal_futex;


Now during iteration on flush, we can detect a WAIT_STATE while 
iterating through the flushed stack. It might work. Just is just off the 
top of my head.


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