Re: [PATCH 26/28] hazptr: Implement two-phase wildcard scan

["Gary Guo" <gary@garyguo.net>]

On Sun Sep 20, 2026 at 4:44 PM BST, Mathieu Desnoyers wrote:
> On 2026-09-20 10:46, Gary Guo wrote:
>> On Sat Sep 19, 2026 at 1:00 AM BST, Paul E. McKenney wrote:
>>> From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>>>
>>> Implement a two-phase wildcard scan to guarantee forward progress of
>>> synchronize_hazptr() even if there is a steady stream of ill-timed
>>> readers which populate wildcards into per-CPU slots.
>> 
>> Hmm, I am not sure that I understand the problem here. The per-CPU slot is
>> scanned only once per CPU, and patch 1 already introduces flipping of the
>> overflow list. What prevents the forward progress?
>
> A steady stream of readers acquiring and releasing various hazard
> pointers happening concurrently with the percpu slots checks, being
> unlucky enough that each of the slot is constantly in a "wildcard"
> state, thus preventing forward progress of the synchronize, just with
> a steady stream of individually time-bound readers.

Oh, so the issue is that we cannot progress over a single slot, because with
ill-timing a new iteration of the inner loop of "smp_cond_load_acquire" could
see a new reader while waiting for the slot to be released?

So, in essence, the flipping is used to prevent ABA problem on percpu slots?

>
>> 
>> I think having a shared global read by all CPUs sounds really undesirable,
>> especially that it gets flipped for each hazptr_synchronize -- this means that
>> in the pathological case where there are a steady stream of hazptr_synchronize
>> calls, each fast-path hazptr_acquire will have a cache miss reading
>> hazptr_wildcard.
>
> There is a straightforward optimization we can do if this happen to
> cause performance issues: only do the flip when the synchronize
> encounters a wildcard retry delay beyond a specified threshold.
> So we ensure synchronize observe the absence of both wildcard
> values in each cpu slots, and only flip the current wildcard on retry
> delay.

Another option would be avoid using WILDCARD if possible. IIRC the wildcard is
used to ensure forward progress on the reader side, so it avoids the possibility
of READ_ONCE(*addr_p) changing before and after protecting.

One option would be to first use the typical hazard pointer impl that read the
pointer twice, and when that fails, use the wildcard protection. This would mean
that in the common case where the hazptr_acquire does not race with a pointer
update, the WILDCARD protection is not used at all.

Best,
Gary

>
> This would prevent the common "frequent" synchronize case you
> mention from causing cache misses on the read-side.
>
> But I preferred to keep it simple and wait until we hit this
> level of synchronize call throughput until adding that extra
> complexity.
>
> Thanks,
>
> Mathieu