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 <[email protected]>
> > >
> > > 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 <[email protected]>
> > > Signed-off-by: Paul E. McKenney <[email protected]>
> > > Cc: Boqun Feng <[email protected]>
> > > Reviewed-by: Bradley Morgan <[email protected]>
> > > ---
> > > 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.
> 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()?
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
