Re: [PATCH hazptr 4/4] hazptr: Introduce "try acquire" fast path, fallback to overflow list

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

On 2026-09-27 12:40, Boqun Feng wrote:
> On Sun, Sep 27, 2026 at 11:51:31AM -0400, Mathieu Desnoyers wrote:
>> Introduce a "try acquire" hazard pointer fast path, which performs an
>> early load of the address to store it into the hazard pointer slot, and
>> then re-loads that address after a barrier to check whether it has
>> changed meanwhile.
>>
>> On comparison failure, rather than re-try, guarantee forward progress by
>> falling back to the __hazptr_acquire slow path on failure.
>>
>> The acquire slow path attempts a try-acquire for any available per-CPU
>> slot. If that fails, it chains the backup slot into the overflow list,
>> therefore guaranteeing forward progress for both hazard pointer
>> read-side and synchronize:
>>
>> - Readers set the wildcard, and then proceed to set the more
>>    specific address to replace the wildcard.
>>
>> - One synchronize alternates between two overflow list periods,
>>    scanning each one while readers are added to the other period,
>>    thus preventing a steady flow of readers from preventing
>>    synchronize forward progress.
>>
>> With this change, the scan on per-CPU slots don't need to expect a
>> wildcard anymore, because none can be produced by readers. Wildcards are
>> only expected within overflow lists.
>>
> 
> Ok, I was missing something, but I think it's better to call it out.
> Wildcards can only exist in the overflow lists when the context is not
> preemptible. In other words, there won't be a preempted readers blocking
> the synchronize_hazptr() with a wilcard in the overflow list.

Exactly ! Wildcard slots only exist during the short time-frame of the
preempt-off read-side code region (few instructions). And with this
patch, this does not even happen very often, because the fast path don't
rely on the wildcards.

> 
> So no more design trade-off question from me :)
> 

Are you sure ? Scrolling down....

>> @@ -196,16 +197,13 @@ void hazptr_scan_cpu_slots_period(void *addr, void *scan_wildcard)
>>   	for_each_possible_cpu(cpu) {
>>   		/*
>>   		 * Scan CPU slots.
>> -		 * Forward progress against recurring wildcards is guaranteed
>> -		 * by scanning for one wildcard while new elements use the
>> -		 * other wildcard value (1UL vs 2UL).
>>   		 * Forward progress against recurring single hazard pointer
>>   		 * values is guaranteed by the fact that a hazard pointer
>>   		 * is not reclaimed nor reused until the scan for that hazard
>>   		 * pointer completes, which prevents a steady flow of readers
>>   		 * to acquire that same hazard pointer value.
> 
> (Not a comment to this patch, but I think it's worth bringing up)
> 
> I want to point out this is not true for the lockdep use case, because
> the we need to protect a hash list deletion there, and we use the
> address of the hash bucket there. It's proven fine in practice because
> the readers are rare (we only call the reader is_dynamic_key() in
> register_lock_class(), that is every time you have a new lock class to
> register).
> 
> Maybe what we want to say here is that "if the users guarantee no steady
> flow of the same hazard pointer value, we guarantee forward progress".
> Thoughts?

AFAIU, your approach to protect lockdep linked lists is to use the
address of the hash bucket to protect the traversal. As this address is 
invariant (global array item address), that address should be fine
to fulfill hazptr requirements, but it has downsides: rather than
protecting the specific nodes being retired, the whole hash chain is
protected. This means that, as you point out, many readers retiring
nodes from a given bucket (except the first node) could end up holding a
continuous stream of hazptr for a given hazptr value, preventing
progress of hazptr synchronize.

It's also coarser: per-bucket rather than per-node.

Am I missing something here ?

One honest question: is this pattern something we expect to
see often ? If so, then we may want to introduce a notion of
hazptr protection "period" flip (similar to some RCU implementations),
where we tag the low bit of the slot pointer (0 vs 1), and alternate
between the two periods in synchronize. This would prevent a steady-flow
of same-value readers from preventing synchronize forward progress.

Thoughts ?

Thanks,

Mathieu

> 
> The rest looks good to me.
> 
> Regards,
> Boqun
> 


-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com