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

[KunWu Chan]

Hi Mathieu,

I checked the try-acquire protocol and the changes to
wildcard handling.

The Store B / smp_mb() / Load A sequence checks that the
early and verification loads return the same pointer
value, with ptr_eq() used for the comparison.

With wildcard handling removed from per-CPU slots, the
per-CPU scan no longer needs the two-phase wildcard
check. The overflow-list scan still handles
HAZPTR_WILDCARD.

Reviewed-by: Kunwu Chan <chentao@xxxxxxxxxx>

Thanks,
Kunwu

On Mon, Oct 12, 2026 at 3:49 AM Mathieu Desnoyers
<mathieu.desnoyers@xxxxxxxxxxxx> 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.
>
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
> Suggested-by: Gary Guo <gary@xxxxxxxxxxx>
> Link: https://lore.kernel.org/lkmm/DLK9MW1N86KD.2GRWUAD2NX4FU@xxxxxxxxxxx/
> Reviewed-by: Gary Guo <gary@xxxxxxxxxxx>
> Cc: Paul E. McKenney <paulmck@xxxxxxxxxx>
> Cc: Boqun Feng <boqun@xxxxxxxxxx>
> Cc: Bradley Morgan <brads@xxxxxxxxxxxxxx>
> Cc: Gary Guo <gary@xxxxxxxxxxx>
> Cc: <rcu@xxxxxxxxxxxxxxx>
> Cc: <lkmm@xxxxxxxxxxxxxxx>
> Cc: Lian Wang <lianux.mm@xxxxxxxxx>
> Cc: Kunwu Chan <kunwu.chan@xxxxxxxxx>
> ---
> Changes since v2:
> - Adapt include to rename from ptreq.h to ptr_eq.h.
> ---
>  include/linux/hazptr.h |  48 +++++++++++--------
>  kernel/hazptr.c        | 103 ++++++++++++++++++++---------------------
>  2 files changed, 77 insertions(+), 74 deletions(-)
>
> diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
> index d1670121947a..90d8d5a3d244 100644
> --- a/include/linux/hazptr.h
> +++ b/include/linux/hazptr.h
> @@ -25,13 +25,11 @@
>  #include <linux/types.h>
>  #include <linux/cleanup.h>
>  #include <linux/sched.h>
> +#include <linux/ptr_eq.h>
>
>  /* 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 +188,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 +268,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.
>                  */
> -               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
>