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

[Kunwu Chan <kunwu.chan@gmail.com>]

On Sun, 27 Sep 2026 18:40:53 +0200 Boqun Feng <boqun@kernel.org> wrote:

> On Sun, Sep 27, 2026 at 11:51:31AM -0400, Mathieu Desnoyers wrote:
> > Introduce a "try acquire" hazard pointer fast path, which performs an
> > early load of the address to store it into the hazard pointer slot, and
> > then re-loads that address after a barrier to check whether it has
> > changed meanwhile.
> > 
> > On comparison failure, rather than re-try, guarantee forward progress by
> > falling back to the __hazptr_acquire slow path on failure.
> > 
> > The acquire slow path attempts a try-acquire for any available per-CPU
> > slot. If that fails, it chains the backup slot into the overflow list,
> > therefore guaranteeing forward progress for both hazard pointer
> > read-side and synchronize:
> > 
> > - Readers set the wildcard, and then proceed to set the more
> >   specific address to replace the wildcard.
> > 
> > - One synchronize alternates between two overflow list periods,
> >   scanning each one while readers are added to the other period,
> >   thus preventing a steady flow of readers from preventing
> >   synchronize forward progress.
> > 
> > With this change, the scan on per-CPU slots don't need to expect a
> > wildcard anymore, because none can be produced by readers. Wildcards are
> > only expected within overflow lists.
> > 
> 
> Ok, I was missing something, but I think it's better to call it out.
> Wildcards can only exist in the overflow lists when the context is not
> preemptible. In other words, there won't be a preempted readers blocking
> the synchronize_hazptr() with a wilcard in the overflow list.
> 
> So no more design trade-off question from me :)
> 
> Regards,
> Boqun
> 
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > Cc: Paul E. McKenney <paulmck@kernel.org>
> > Cc: Boqun Feng <boqun@kernel.org>
> > Cc: Bradley Morgan <brads@mainlining.org>
> > Cc: Gary Guo <gary@garyguo.net>
> > Cc: <rcu@vger.kernel.org>
> > Cc: <lkmm@lists.linux.dev>
> > ---
> >  include/linux/hazptr.h |  47 +++++++++++--------
> >  kernel/hazptr.c        | 103 ++++++++++++++++++++---------------------
> >  2 files changed, 76 insertions(+), 74 deletions(-)
> > 
> > diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
> > index d1670121947a..fcf017ca2255 100644
> > --- a/include/linux/hazptr.h
> > +++ b/include/linux/hazptr.h
> > @@ -29,9 +29,6 @@
> >  /* 4 slots (each sizeof(hazptr_slot_item)) fit in a single 64-byte cache line. */
> >  #define NR_HAZPTR_PERCPU_SLOTS	4
> >  
> > -/* The current hazard pointer wildcard. */
> > -extern void *hazptr_wildcard;
> > -
> >  /*
> >   * Hazard pointer slot.
> >   */
> > @@ -190,6 +187,31 @@ void hazptr_note_context_switch(void)
> >  	}
> >  }
> >  
> > +/* Try hazard pointer protection. */
> > +static inline
> > +void *__hazptr_try_acquire(struct hazptr_ctx *ctx, void * const *addr_p, struct hazptr_slot *slot)
> > +{
> > +	void *early_addr, *addr;
> > +
> > +	if (unlikely(slot->addr))
> > +		return NULL;
> > +	early_addr = READ_ONCE(*addr_p);	/* Early load. */
> > +	WRITE_ONCE(slot->addr, early_addr);	/* Store B */
> > +	/* Memory ordering: Store B before Load A. */
> > +	smp_mb();
> > +	addr = READ_ONCE(*addr_p);		/* Load A */
> > +	/*
> > +	 * Validate that address did not change between Early load and Load A.
> > +	 * Use ptr_eq() to make sure that result from Load A is returned to the
> > +	 * caller to preserve address dependency.
> > +	 */
> > +	if (unlikely(!ptr_eq(addr, early_addr))) {
> > +		WRITE_ONCE(slot->addr, NULL);
> > +		return NULL;
> > +	}
> > +	return addr;
> > +}
> > +
> >  /**
> >   * hazptr_acquire - Load pointer at address and protect with hazard pointer.
> >   *
> > @@ -245,24 +267,9 @@ void *hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
> >  	ctx->acquire_cpu = smp_processor_id();
> >  	ctx->acquire_caller = _THIS_IP_;
> >  #endif
> > -	if (unlikely(slot->addr))
> > +	addr = __hazptr_try_acquire(ctx, addr_p, slot);
> > +	if (unlikely(!addr))
> >  		return __hazptr_acquire(ctx, addr_p);
> > -	WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard));	/* Store B */
> > -
> > -	/* Memory ordering: Store B before Load A. */
> > -	smp_mb();
> > -
> > -	/*
> > -	 * Load @addr_p after storing wildcard to the hazard pointer slot.
> > -	 */
> > -	addr = READ_ONCE(*addr_p);	/* Load A */
> > -
> > -	/*
> > -	 * We don't care about ordering of Store C. It will simply
> > -	 * replace the wildcard by a more specific address. If addr is
> > -	 * NULL, we simply store NULL into the slot.
> > -	 */
> > -	WRITE_ONCE(slot->addr, addr);	/* Store C */
> >  	slot_item->ctx.ctx = ctx;
> >  	ctx->slot = slot;
> >  	return addr;
> > diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> > index 13faa5ba7677..3ca73b56a5c2 100644
> > --- a/kernel/hazptr.c
> > +++ b/kernel/hazptr.c
> > @@ -13,17 +13,9 @@
> >  #include <linux/list.h>
> >  #include <linux/export.h>
> >  
> > -static DEFINE_MUTEX(hazptr_phase_lock);	/* Protect the wildcard and list phase flip. */
> > +#define HAZPTR_WILDCARD	((void *) 1UL)
> >  
> > -/*
> > - * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
> > - * hazptr_synchronize forward progress even with a steady stream of readers.
> > - * This wildcard value is used by acquire to temporarily tag the per-CPU slots.
> > - * This also affects the overflow list selection: the current list used by
> > - * readers is array[(unsigned long) hazptr_wildcard - 1].
> > - */
> > -void *hazptr_wildcard = (void *) 1UL;
> > -EXPORT_SYMBOL_GPL(hazptr_wildcard);
> > +static DEFINE_MUTEX(hazptr_phase_lock);	/* Protect the list phase flip. */
> >  
> >  /* The current overflow list phase. */
> >  static unsigned int hazptr_overflow_list_phase;
> > @@ -41,6 +33,10 @@ struct hazptr_overflow_list {
> >   * successively iterates on both lists. Therefore, only list removals
> >   * can cause the iteration to retry, and the number of removals is
> >   * limited to the number of list elements.
> > + *
> > + * Due to the overflow list raw spin lock, the hazard pointer readers are
> > + * blocking, starvation-free with bounded waiting, assuming bounded critical
> > + * sections and no NMI or virtualization-induced holder preemption.
> >   */
> >  struct hazptr_overflow_list_flip {
> >  	struct hazptr_overflow_list array[2];
> > @@ -51,26 +47,12 @@ static DEFINE_PER_CPU(struct hazptr_overflow_list_flip, percpu_overflow_list_fli
> >  DEFINE_PER_CPU(struct hazptr_percpu_slots, hazptr_percpu_slots);
> >  EXPORT_PER_CPU_SYMBOL_GPL(hazptr_percpu_slots);
> >  
> > -static
> > -void *flip_wildcard(void *wildcard)
> > -{
> > -	return ((unsigned long) wildcard == 1UL) ? (void *) 2UL : (void *) 1UL;
> > -}
> > -
> >  static
> >  unsigned int flip_list_phase(unsigned int phase)
> >  {
> >  	return 1 - phase;
> >  }
> >  
> > -static
> > -bool is_wildcard(void *addr)
> > -{
> > -	if ((unsigned long) addr == 1UL || (unsigned long) addr == 2UL)
> > -		return true;
> > -	return false;
> > -}
> > -
> >  static
> >  struct hazptr_slot *hazptr_get_free_percpu_slot(struct hazptr_ctx *ctx)
> >  {
> > @@ -96,16 +78,36 @@ struct hazptr_slot *hazptr_get_free_percpu_slot(struct hazptr_ctx *ctx)
> >   */
> >  void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
> >  {
> > -	struct hazptr_slot *slot = hazptr_get_free_percpu_slot(ctx);
> > +	struct hazptr_slot *slot;
> >  	void *addr;
> >  
> >  	/*
> > -	 * If all the per-CPU slots are already in use, fallback
> > -	 * to the backup slot.
> > +	 * In case we are called due to nested use of hazard pointers,
> > +	 * try a slot protection with per-CPU slots.
> >  	 */
> > -	if (unlikely(!slot))
> > -		slot = hazptr_chain_backup_slot(ctx);
> > -	WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard));	/* Store B */
> > +	slot = hazptr_get_free_percpu_slot(ctx);
> > +	if (likely(slot)) {
> > +		addr = __hazptr_try_acquire(ctx, addr_p, slot);
> > +		if (addr) {
> > +			ctx->slot = slot;
> > +			return addr;
> > +		}
> > +	}
> > +
> > +	/*
> > +	 * The backup slot overflow list guarantees forward progress of both
> > +	 * hazard pointer readers and synchronize:
> > +	 *
> > +	 * - Readers set the wildcard, and then proceed to set the more
> > +	 *   specific address to replace the wildcard.
> > +	 *
> > +	 * - One synchronize alternates between two overflow list periods,
> > +	 *   scanning each one while readers are added to the other period,
> > +	 *   thus preventing a steady flow of readers from preventing
> > +	 *   synchronize forward progress.
> > +	 */
> > +	slot = hazptr_chain_backup_slot(ctx);
> > +	WRITE_ONCE(slot->addr, HAZPTR_WILDCARD);	/* Store B */
> >  
> >  	/* Memory ordering: Store B before Load A. */
> >  	smp_mb();
> > @@ -121,20 +123,21 @@ void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
> >  	 * NULL, we simply store NULL into the slot.
> >  	 */
> >  	WRITE_ONCE(slot->addr, addr);	/* Store C */
> > +
> >  	ctx->slot = slot;
> > -	if (!addr && hazptr_slot_is_backup(ctx, slot))
> > +	if (!addr)
> >  		hazptr_unchain_backup_slot(ctx);
> >  	return addr;
> >  }
> >  EXPORT_SYMBOL_GPL(__hazptr_acquire);
> >  
> >  /*
> > - * Perform piecewise iteration on overflow list waiting until "addr" is
> > - * not present. Raw spinlock is released and taken between each list
> > - * item and busy loop iteration. The overflow list generation is checked
> > - * each time the lock is taken to validate that the list has not changed
> > - * before resuming iteration or busy wait. If the generation has
> > - * changed, retry the entire list traversal.
> > + * Perform piecewise iteration on overflow list waiting until "addr" and
> > + * wildcard are not present. Raw spinlock is released and taken between each
> > + * list item and busy loop iteration. The overflow list generation is checked
> > + * each time the lock is taken to validate that the list has not changed before
> > + * resuming iteration or busy wait. If the generation has changed, retry the
> > + * entire list traversal.
> >   */
> >  static
> >  void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list, void *addr)
> > @@ -147,13 +150,11 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list
> >  retry:
> >  	snapshot_gen = overflow_list->gen;
> >  	hlist_for_each_entry(backup_slot, &overflow_list->head, overflow_node) {
> > -		/* Busy-wait if node is found. */
> > +		/* Busy-wait if addr or wildcard are found. */
> >  		for (;;) {
> >  			void *load_addr = smp_load_acquire(&backup_slot->slot.addr);	/* Load B */
> >  
> > -			/* We don't expect wildcards in overflow list. */
> > -			WARN_ON_ONCE(is_wildcard(load_addr));
> > -			if (load_addr != addr)
> > +			if (load_addr != addr && load_addr != HAZPTR_WILDCARD)
> >  				break;
> >  			raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
> >  			cpu_relax();
> > @@ -174,7 +175,7 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list
> >  }
> >  
> >  static
> > -void hazptr_synchronize_cpu_slots(int cpu, void *addr, void *scan_wildcard)
> > +void hazptr_synchronize_cpu_slots(int cpu, void *addr)
> >  {
> >  	struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu);
> >  	unsigned int idx;
> > @@ -182,13 +183,13 @@ void hazptr_synchronize_cpu_slots(int cpu, void *addr, void *scan_wildcard)
> >  	for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> >  		struct hazptr_slot_item *item = &percpu_slots->items[idx];
> >  
> > -		/* Busy-wait if node is found. */
> > -		smp_cond_load_acquire(&item->slot.addr, VAL != addr && VAL != scan_wildcard); /* Load B */
> > +		/* Busy-wait if addr is found. */
> > +		smp_cond_load_acquire(&item->slot.addr, VAL != addr); /* Load B */
> >  	}
> >  }
> >  
> >  static
> > -void hazptr_scan_cpu_slots_period(void *addr, void *scan_wildcard)
> > +void hazptr_scan_cpu_slots(void *addr)
> >  {
> >  	int cpu;
> >  
> > @@ -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?

Thanks Mathieu, and thanks Boqun for the review.

I hit the same ordering requirement in the shared-scan
implementation I'm working on. hazptr_promote_to_backup_slot()
links the backup slot into the overflow list before clearing the
per-CPU slot, so the scan has to cover all per-CPU slots before
the overflow lists. My series carries the same ordering fix in
the scan-kthread path.

For the lockdep case, I've tested the conversion with the
wq_churn/LOCKDEP torture scenario and PROVE_LOCKING enabled.
The hazard pointer is the hash bucket address there, so I agree
that the forward-progress guarantee should be stated conditional
on there being no steady flow of the same hazard pointer value.

I'm also working on the scan-thread side, where concurrent
hazptr_synchronize() callers share one scan cycle, based on 
the scan-kthread approach from your shazptr series [1].                                                 
[1] https://lore.kernel.org/lkml/20250625031101.12555-1-boqun.feng@gmail.com/

The v2 series is testing, I'll include the rcuscale results 
in the cover letter.

Thanks,
Kunwu

> 
> The rest looks good to me.
> 
> Regards,
> Boqun
> 
> >  		 */
> > -		hazptr_synchronize_cpu_slots(cpu, addr, scan_wildcard);
> > +		hazptr_synchronize_cpu_slots(cpu, addr);
> >  	}
> >  }
> >  
> > @@ -237,7 +235,6 @@ void hazptr_scan_overflow_list_period(void *addr, unsigned int scan_idx)
> >  void hazptr_synchronize(void *addr)
> >  {
> >  	unsigned int scan_list_phase;
> > -	void *scan_wildcard;
> >  
> >  	/*
> >  	 * Busy-wait should only be done from preemptible context.
> > @@ -251,16 +248,14 @@ void hazptr_synchronize(void *addr)
> >  	 */
> >  	if (!addr)
> >  		return;
> > +
> >  	/* Memory ordering: Store A before Load B. */
> >  	smp_mb();
> >  
> >  	guard(mutex)(&hazptr_phase_lock);
> >  
> >  	/* Scan per-CPU slots. */
> > -	scan_wildcard = flip_wildcard(hazptr_wildcard);
> > -	hazptr_scan_cpu_slots_period(addr, scan_wildcard);
> > -	WRITE_ONCE(hazptr_wildcard, scan_wildcard);			/* Flip the current wildcard. */
> > -	hazptr_scan_cpu_slots_period(addr, flip_wildcard(scan_wildcard));
> > +	hazptr_scan_cpu_slots(addr);
> >  
> >  	/*
> >  	 * Scan overflow lists *after* scanning per-CPU slots. See
> > -- 
> > 2.43.0
> > 
>