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 13:24, Boqun Feng wrote:
> On Sun, Sep 27, 2026 at 01:15:39PM -0400, Mathieu Desnoyers wrote:
> [...]
>>>> @@ -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 ?
>>
> 
> No, you got it right, but as I said, we can use it in lockdep since the
> readers are relatively rare, so not an issue here.
> 
>> One honest question: is this pattern something we expect to
>> see often ? If so, then we may want to introduce a notion of
> 
> I honestly don't know. But in my opinion, we'd better focus on finding
> more typical usage of hazptr (i.e. protecting actual object). So ...
> 
>> 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 ?
>>
> 
> ... I will say let's add it only if we have more users of this pattern.
> 

I am concerned about this because many uses of RCU in the Linux
kernel protects linked list traversals. Turning a RCU-protected list
traversal into a hazptr protected traversal is not as simple as
acquiring each hazptr hand in hand.

Your own use-case for lockdep is indeed a linked list traversal,
and you need to use a work-around: protect the address of the
hash bucket head.

I'm just wondering if this work-around will end up being the
"blessed" way for protecting linked list traversals with hazptr,
or whether we should consider alternatives ?

This ties into finding additional usage for hazptr, because linked
lists are so prevalent in the kernel.

Thanks,

Mathieu

> Regards,
> Boqun
> 
>> Thanks,
>>
>> Mathieu
>>
>>>
>>> The rest looks good to me.
>>>
>>> Regards,
>>> Boqun
>>>
>>
>>
>> -- 
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com


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