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

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

On 2026-09-20 11:57, Gary Guo wrote:
> 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?

Correct.

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

Yes, specifically an ABA which could theoretically prevent forward
progress of synchronize given a steady flow of hazptr acquire/release.

> 
>>
>>>
>>> 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.

Using the wildcard has a few benefits:

1) Prevents this retry loop on the read-side.

2) Prevents comparison of a loaded pointer value against a re-load of
    that value, which causes issues with compiler optimizations (I did a
    ptr_eq() patch in a prior version of the hazard pointer patches to
    handle this).

It does have a downside though: given a very long preemption by a host
VM, the guest VM could technically keep a wildcard present for a long
time in a per-cpu slot, which would prevent hazptr synchronize from
progressing for a long time in the guest VM kernel.

> 
> 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.

So your idea is to use the hazptr load+reload approach (with ptr_eq()
check preventing the compiler from removing the dependency on the
second load), but rather than retry, fallback to the two-phases
wildcard. This way, we get the best of both worlds: guaranteed
progress for the read-side (with the wildcard fallback), and typically
we are immune to long-host-VM preemption delays, because the
wildcard fallback would almost never fire.

I like it. What do you guys think ?

Thanks,

Mathieu

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


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