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

[Boqun Feng <boqun@kernel.org>]

On Sun, Sep 27, 2026 at 01:36:54PM -0400, Mathieu Desnoyers wrote:
> 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.
> 

I actually don't think converting RCU usage into hazptr would be a good
starting point for finding good hazptr usage. RCU readers are faster,
and a lot of existing RCU users do want the reader side to be as fast as
possible. So even though this is a problem, but I don't think that's an
urgent problem to resolve. Of course, if one can find a faster hazptr
reader implemenation, then it may be a different story.

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

So the lockdep usage is IMO a very special case, but it does show the
advantages of hazptr.

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

It depends on how many uses of the linked list traversals really care
about the reader side performance. I'm not sure we can easily find
another one like lockdep. Hence I think we should only add the
optimization when we find more of such a usage. Make sense?

Personally, I also want to see a refcount-like usage for hazptr, that'll
be very exciting for me :D

Regards,
Boqun

> 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