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

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

On 2026-09-20 11:55, Boqun Feng wrote:
> On Sun, Sep 20, 2026 at 08:46:55AM -0400, Mathieu Desnoyers wrote:
>> On 2026-09-19 09:28, Boqun Feng wrote:
>>> On Fri, Sep 18, 2026 at 05:00:54PM -0700, 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.
>>>>
>>>> This is performed by flipping between two wildcard values (1UL and 2UL),
>>>> and alternatively scanning for the opposite wildcard while newcoming
>>>> readers use the other one.
>>>>
>>>> There is no possibility to miss a reader because all slots for all
>>>> wildcards are accounted for during a synchronize.
>>>>
>>>> As a simplification, use this period flip to drive the hazptr overflow
>>>> list selection as well, since there is really no point is making the
>>>> overflow list flip use a different state.
>>>>
>>>> Protect the wildcard flip with a mutex.
>>>>
>>>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>>>> Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
>>>> Cc: Boqun Feng <boqun@kernel.org>
>>>> Reviewed-by: Bradley Morgan <include@grrlz.net>
>>>> ---
>>>>    include/linux/hazptr.h |  6 ++-
>>>>    kernel/hazptr.c        | 98 ++++++++++++++++++++++++++++++------------
>>>>    2 files changed, 74 insertions(+), 30 deletions(-)
>>>>
>>>> diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
>>>> index 43998bf43de4..43122c5673bd 100644
>>>> --- a/include/linux/hazptr.h
>>>> +++ b/include/linux/hazptr.h
>>>> @@ -28,7 +28,9 @@
>>>>    /* 4 slots (each sizeof(hazptr_slot_item)) fit in a single 64-byte cache line. */
>>>>    #define NR_HAZPTR_PERCPU_SLOTS	4
>>>> -#define HAZPTR_WILDCARD		((void *) 0x1UL)
>>>> +
>>>> +/* The current hazard pointer wildcard. */
>>>> +extern void *hazptr_wildcard;
>>>>    /*
>>>>     * Hazard pointer slot.
>>>> @@ -243,7 +245,7 @@ void *hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
>>>>    #endif
>>>>    	if (unlikely(slot->addr))
>>>>    		return __hazptr_acquire(ctx, addr_p);
>>>> -	WRITE_ONCE(slot->addr, HAZPTR_WILDCARD);	/* Store B */
>>>> +	WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard));	/* Store B */
>>>>    	/* Memory ordering: Store B before Load A. */
>>>>    	smp_mb();
>>>> diff --git a/kernel/hazptr.c b/kernel/hazptr.c
>>>> index a9d3d68a1525..d3d1050d92cf 100644
>>>> --- a/kernel/hazptr.c
>>>> +++ b/kernel/hazptr.c
>>>> @@ -13,6 +13,17 @@
>>>>    #include <linux/list.h>
>>>>    #include <linux/export.h>
>>>> +/*
>>>> + * 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].
>>>> + */
>>>> +static DEFINE_MUTEX(hazptr_wildcard_lock);	/* Protect the wildcard flip. */
>>>> +void *hazptr_wildcard = (void *) 1UL;
>>>> +EXPORT_SYMBOL_GPL(hazptr_wildcard);
>>>> +
>>>>    struct hazptr_overflow_list {
>>>>    	raw_spinlock_t lock;		/* Lock protecting overflow list and list generation. */
>>>>    	struct hlist_head head;		/* Overflow list head. */
>>>> @@ -28,8 +39,6 @@ struct hazptr_overflow_list {
>>>>     * limited to the number of list elements.
>>>>     */
>>>>    struct hazptr_overflow_list_flip {
>>>> -	struct mutex lock;		/* Mutex protecting add_idx from concurrent updates. */
>>>> -	unsigned int add_idx;		/* Index of current flip-list to add to. */
>>>>    	struct hazptr_overflow_list array[2];
>>>>    };
>>>> @@ -38,6 +47,20 @@ 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
>>>> +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)
>>>>    {
>>>> @@ -72,7 +95,7 @@ void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
>>>>    	 */
>>>>    	if (unlikely(!slot))
>>>>    		slot = hazptr_chain_backup_slot(ctx);
>>>> -	WRITE_ONCE(slot->addr, HAZPTR_WILDCARD);	/* Store B */
>>>> +	WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard));	/* Store B */
>>>>    	/* Memory ordering: Store B before Load A. */
>>>>    	smp_mb();
>>>> @@ -118,7 +141,9 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list
>>>>    		for (;;) {
>>>>    			void *load_addr = smp_load_acquire(&backup_slot->slot.addr);	/* Load B */
>>>> -			if (load_addr != addr && load_addr != HAZPTR_WILDCARD)
>>>> +			/* We don't expect wildcards in overflow list. */
>>>> +			WARN_ON_ONCE(is_wildcard(load_addr));
>>>> +			if (load_addr != addr)
>>>>    				break;
>>>>    			raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
>>>>    			cpu_relax();
>>>> @@ -139,7 +164,7 @@ void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list
>>>>    }
>>>>    static
>>>> -void hazptr_synchronize_cpu_slots(int cpu, void *addr)
>>>> +void hazptr_synchronize_cpu_slots(int cpu, void *addr, void *scan_wildcard)
>>>>    {
>>>>    	struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu);
>>>>    	unsigned int idx;
>>>> @@ -148,7 +173,39 @@ void hazptr_synchronize_cpu_slots(int cpu, void *addr)
>>>>    		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 != HAZPTR_WILDCARD); /* Load B */
>>>> +		smp_cond_load_acquire(&item->slot.addr, VAL != addr && VAL != scan_wildcard); /* Load B */
>>>> +	}
>>>> +}
>>>> +
>>>> +static
>>>> +void hazptr_scan_period(void *addr, void *scan_wildcard)
>>>> +{
>>>> +	unsigned int scan_idx = (unsigned long) scan_wildcard - 1;
>>>> +	int cpu;
>>>> +
>>>> +	/* Scan all CPUs slots. */
>>>> +	for_each_possible_cpu(cpu) {
>>>> +		struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, 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.
>>>> +		 */
>>>> +		hazptr_synchronize_cpu_slots(cpu, addr, scan_wildcard);
>>>> +
>>>> +		/*
>>>> +		 * Scan backup slots in percpu overflow lists.
>>>> +		 * Forward progress is guaranteed by scanning one list
>>>> +		 * while new elements are added into the other list.
>>>> +		 */
>>>> +		hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx], addr);
>>>>    	}
>>>>    }
>>>> @@ -161,7 +218,7 @@ void hazptr_synchronize_cpu_slots(int cpu, void *addr)
>>>>     */
>>>>    void hazptr_synchronize(void *addr)
>>>>    {
>>>> -	int cpu;
>>>> +	void *scan_wildcard;
>>>>    	/*
>>>>    	 * Busy-wait should only be done from preemptible context.
>>>> @@ -177,33 +234,19 @@ void hazptr_synchronize(void *addr)
>>>>    		return;
>>>>    	/* Memory ordering: Store A before Load B. */
>>>>    	smp_mb();
>>>> -	/* Scan all CPUs slots. */
>>>> -	for_each_possible_cpu(cpu) {
>>>> -		struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu);
>>>> -		unsigned int scan_idx;
>>>> -
>>>> -		/* Scan CPU slots. */
>>>> -		hazptr_synchronize_cpu_slots(cpu, addr);
>>>> -		/*
>>>> -		 * Scan backup slots in percpu overflow lists.
>>>> -		 * Forward progress is guaranteed by scanning one list
>>>> -		 * while new elements are added into the other list.
>>>> -		 */
>>>> -		guard(mutex)(&overflow_list_flip->lock);
>>>> -		scan_idx = overflow_list_flip->add_idx ^ 1;
>>>> -		hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx], addr);
>>>> -		/* Flip current list. */
>>>> -		WRITE_ONCE(overflow_list_flip->add_idx, scan_idx);
>>>> -		hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx ^ 1], addr);
>>>> -	}
>>>> +	guard(mutex)(&hazptr_wildcard_lock);
>>>> +	scan_wildcard = flip_wildcard(hazptr_wildcard);
>>>> +	hazptr_scan_period(addr, scan_wildcard);
>>>> +	WRITE_ONCE(hazptr_wildcard, scan_wildcard);	/* Flip the current wildcard. */
>>>> +	hazptr_scan_period(addr, flip_wildcard(scan_wildcard));
>>>>    }
>>>>    EXPORT_SYMBOL_GPL(hazptr_synchronize);
>>>>    struct hazptr_slot *hazptr_chain_backup_slot(struct hazptr_ctx *ctx)
>>>>    {
>>>>    	struct hazptr_overflow_list_flip *overflow_list_flip = this_cpu_ptr(&percpu_overflow_list_flip);
>>>> -	unsigned int list_idx = READ_ONCE(overflow_list_flip->add_idx);
>>>> +	unsigned int list_idx = (unsigned long) READ_ONCE(hazptr_wildcard) - 1;
>>>
>>>
>>> What if this happens?
>>>
>>> 	{ <hazptr_wildcard == 2UL> }
>>>
>>> 	CPU 0				CPU 1
>>> 	=====				=====
>>> 	hazptr_acquire(ctx, &gp):
>>> 	  WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard));	/* Store B */
>>> 	  // slot->addr == 2
>>> 	  smp_mb();
>>>
>>> 	  addr = READ_ONCE(*addr_p);      /* Load A */
>>> 	  // ^ addr == gp == old, i.e not NULL
>>>
>>> 	  				/* unpublish and wait for reader */
>>> 	  				old = gp;
>>> 	  				WRITE_ONCE(gp, NULL);
>>> 					hazptr_synchronize(old):
>>> 					  smp_mb();
>>> 					  guard(mutex)(&hazptr_wildcard_lock);
>>> 					  scan_wildcard = flip_wildcard(hazptr_wildcard);
>>> 					  // ^ scan_wildcard == 1;
>>>
>>> 					  hazptr_scan_period(addr, scan_wildcard);
>>> 					  // ^ will miss reader on CPU 0
>>> 					  // because its slot->addr == 2
>>>                                             WRITE_ONCE(hazptr_wildcard, scan_wildcard);	/* Flip the current wildcard. */
>>>
>>> 	{ <hazptr_wildcard == 1UL> }
>>>
>>> 	  WRITE_ONCE(slot->addr, addr);
>>>
>>> 	hazptr_detach():
>>> 	  hazptr_chain_backup_slot():
>>> 	    list_idx = READ_ONCE(hazptr_wildcard) - 1;
>>> 	    // ^ list_idx == 0
>>>
>>> 	  smp_store_release(&slot->addr, NULL);
>>>             // ^ clear the per-CPU slot
>>> 	    				  // flip_wildcard(scan_wildcard) == 2
>>>                                             hazptr_scan_period(addr, flip_wildcard(scan_wildcard));
>>> 					  // ^ will miss reader on CPU 0
>>> 					  // because it only scans list
>>> 					  // 1.
>>>
>>> If I'm not missing anything, then it means a reader can dodge the
>>> hazptr_synchronize() scan, because its per-CPU slot can appear on
>>> wildchard=1 but its backup slot can be on wildcard=2.
>>
>> The scenario presented here includes a call to hazptr_detach,
>> which moves the slot to the backup list, which is handled by
> 
> But the slot move happens between the two scans in one
> hazptr_synchronize(), so it's moved to the scan list 0 instead of 1,
> after we already finished the the scan of list 0, no? That's why the
> scan can miss it.

Just to be clear, there are really two mechanisms combined here:

1) The per-cpu slots scan (fast path), now made two-phases.

2) A two-phases overflow list scan, for "detached" slots.

If we look at hazptr_promote_to_backup_slot():

          * Move hazard pointer from the per-CPU slot to the
          * backup slot. This requires hazard pointer
          * synchronize to iterate on per-CPU slots with
          * load-acquire before iterating on the overflow list.

This means synchronize needs to observe the per-cpu slots
*before* it observes the overflow list.

Now your point: because my current implementation observes
each phase separately, for each cpu, your concern is that
a detached per-cpu slot being moved to an overflow list of
a different phase could be missed.

Indeed, when hazptr_chain_backup_slot is invoked, it re-loads
hazptr_wildcard, and therefore its phase is completely
independent of the phase used for the per-cpu counter.

I think you're onto something. The safe approach out of this
would be to restructure hazptr_synchronize() to scan for
both per-cpu slots phases _first_ and then scan for the
overflow lists. This could be done by separating the
scan_wildcard into separate words: one driving the fast-path
"wildcard", the other for the overflow list phase selection.

> 
>> hazptr_synchronize() _after_ scanning the per-cpu slots
>> for address and both wildcard values. So the synchronize
>> algorithm on the right column should be completed to show the
>> role of the backup slot handling as well.
>>
> 
> I don't think I see the enough explanantion here, maybe you can
> elaborate more? Especially when the hazptr_detach() happens in-between
> these two hazptr_scan_period()?

As I explained above, I think you've found a hole. Does my
analysis and proposed solution make sense ?

Thanks,

Mathieu

> 
> Regards,
> BOqun
> 
>> Thanks,
>>
>> Mathieu
>>
>>
>>>
>>> Thoughts?
>>>
>>> Regards,
>>> Boqun
>>>
>>>>    	struct hazptr_overflow_list *overflow_list = &overflow_list_flip->array[list_idx];
>>>>    	struct hazptr_slot *slot = &ctx->backup_slot.slot;
>>>> @@ -233,7 +276,6 @@ void __init hazptr_init(void)
>>>>    	for_each_possible_cpu(cpu) {
>>>>    		struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu);
>>>> -		mutex_init(&overflow_list_flip->lock);
>>>>    		for (int i = 0; i < 2; i++) {
>>>>    			raw_spin_lock_init(&overflow_list_flip->array[i].lock);
>>>>    			INIT_HLIST_HEAD(&overflow_list_flip->array[i].head);
>>>> -- 
>>>> 2.40.1
>>>>
>>
>>
>> -- 
>> Mathieu Desnoyers
>> EfficiOS Inc.
>> https://www.efficios.com


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