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

[Bradley Morgan]

On 9 October 2026 19:21:35 BST, 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>

Hey, looks fine to me! 

Reviewed-by: Bradley Morgan <brads@xxxxxxxxxxxxxx>

(Well needed in my opinion)

>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>
>---
> 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..df2aca9aa26b 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/ptreq.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
>

--- Thanks!
"I'm not a very positive person" - Linus torvalds