On Sun, Sep 27, 2026 at 08:16:20PM +0200, Boqun Feng wrote:
> 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.
This sort of tradeoff is made in hazard-pointer use cases in other
projects, with use of explicit counts of the incoming links to a given
node being one such trick. The explicit count counts the links, and
hazard pointers counts the readers. This approach usually ends up
also restricting the order in which nodes can be removed.
Just like SRCU partitions the readers coming from the RCU end. ;-)
> > > > 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.
The usual hazard-pointers linked-list traversal includes a retry check
at each node. So yes, we should first be looking for hazard-pointer
use cases where RCU doesn't have such a great advantage. ;-)
> > 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
Me too! The easiest cases will be those having a try-acquire rather
than an unconditional acquisition.
Thanx, Paul
> 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
