Re: [PATCH 26/28] hazptr: Implement two-phase wildcard scan
From: Mathieu Desnoyers
Date: Fri Sep 25 2026 - 16:18:22 EST
On 2026-09-25 15:19, Mathieu Desnoyers wrote:
On 2026-09-20 11:57, Gary Guo wrote:Something like this lightly compile tested patch on top of my prior
On Sun Sep 20, 2026 at 4:44 PM BST, Mathieu Desnoyers wrote:
On 2026-09-20 10:46, Gary Guo wrote:
On Sat Sep 19, 2026 at 1:00 AM BST, Paul E. McKenney wrote:
From: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
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.
Hmm, I am not sure that I understand the problem here. The per-CPU slot is
scanned only once per CPU, and patch 1 already introduces flipping of the
overflow list. What prevents the forward progress?
A steady stream of readers acquiring and releasing various hazard
pointers happening concurrently with the percpu slots checks, being
unlucky enough that each of the slot is constantly in a "wildcard"
state, thus preventing forward progress of the synchronize, just with
a steady stream of individually time-bound readers.
Oh, so the issue is that we cannot progress over a single slot, because with
ill-timing a new iteration of the inner loop of "smp_cond_load_acquire" could
see a new reader while waiting for the slot to be released?
Correct.
So, in essence, the flipping is used to prevent ABA problem on percpu slots?
Yes, specifically an ABA which could theoretically prevent forward
progress of synchronize given a steady flow of hazptr acquire/release.
I think having a shared global read by all CPUs sounds really undesirable,
especially that it gets flipped for each hazptr_synchronize -- this means that
in the pathological case where there are a steady stream of hazptr_synchronize
calls, each fast-path hazptr_acquire will have a cache miss reading
hazptr_wildcard.
There is a straightforward optimization we can do if this happen to
cause performance issues: only do the flip when the synchronize
encounters a wildcard retry delay beyond a specified threshold.
So we ensure synchronize observe the absence of both wildcard
values in each cpu slots, and only flip the current wildcard on retry
delay.
Another option would be avoid using WILDCARD if possible. IIRC the wildcard is
used to ensure forward progress on the reader side, so it avoids the possibility
of READ_ONCE(*addr_p) changing before and after protecting.
Using the wildcard has a few benefits:
1) Prevents this retry loop on the read-side.
2) Prevents comparison of a loaded pointer value against a re-load of
that value, which causes issues with compiler optimizations (I did a
ptr_eq() patch in a prior version of the hazard pointer patches to
handle this).
It does have a downside though: given a very long preemption by a host
VM, the guest VM could technically keep a wildcard present for a long
time in a per-cpu slot, which would prevent hazptr synchronize from
progressing for a long time in the guest VM kernel.
One option would be to first use the typical hazard pointer impl that read the
pointer twice, and when that fails, use the wildcard protection. This would mean
that in the common case where the hazptr_acquire does not race with a pointer
update, the WILDCARD protection is not used at all.
So your idea is to use the hazptr load+reload approach (with ptr_eq()
check preventing the compiler from removing the dependency on the
second load), but rather than retry, fallback to the two-phases
wildcard. This way, we get the best of both worlds: guaranteed
progress for the read-side (with the wildcard fallback), and typically
we are immune to long-host-VM preemption delays, because the
wildcard fallback would almost never fire.
I like it. What do you guys think ?
[PATCH v1] hazptr: Fix two-phase hazptr_synchronize race with detach
?
It also depends on my ptr_eq() patch sent in an earlier hazard pointer
series.
diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
index d1670121947a..8a005a1125f1 100644
--- a/include/linux/hazptr.h
+++ b/include/linux/hazptr.h
@@ -233,7 +233,7 @@ void *hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
struct hazptr_percpu_slots *percpu_slots;
struct hazptr_slot_item *slot_item;
struct hazptr_slot *slot;
- void *addr;
+ void *early_addr, *addr;
guard(preempt)();
percpu_slots = this_cpu_ptr(&hazptr_percpu_slots);
@@ -247,22 +247,38 @@ 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, READ_ONCE(hazptr_wildcard)); /* Store B */
+ 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();
-
- /*
- * Load @addr_p after storing wildcard to the hazard pointer slot.
- */
- addr = READ_ONCE(*addr_p); /* Load A */
-
+ 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.
+ * Validate that address did not change between Initial
+ * load and Load A. Use ptr_eq() to make sure that result from
+ * Load A is returned to preserve address dependency.
*/
- WRITE_ONCE(slot->addr, addr); /* Store C */
+ if (unlikely(!ptr_eq(addr, early_addr))) {
+ /*
+ * Address don't match. Use a wildcard rather than a
+ * retry loop to guarantee reader forward progress.
+ */
+ 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..8c4fe0a45304 100644
--- a/kernel/hazptr.c
+++ b/kernel/hazptr.c
@@ -97,7 +97,7 @@ 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);
- void *addr;
+ void *early_addr, *addr;
/*
* If all the per-CPU slots are already in use, fallback
@@ -105,22 +105,38 @@ void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
*/
if (unlikely(!slot))
slot = hazptr_chain_backup_slot(ctx);
- WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard)); /* Store B */
+ 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 */
/*
- * Load @addr_p after storing wildcard to the hazard pointer slot.
+ * Validate that address did not change between Initial
+ * load and Load A. Use ptr_eq() to make sure that result from
+ * Load A is returned to preserve address dependency.
*/
- addr = READ_ONCE(*addr_p); /* Load A */
+ if (unlikely(!ptr_eq(addr, early_addr))) {
+ /*
+ * Address don't match. Use a wildcard rather than a
+ * retry loop to guarantee reader forward progress.
+ */
+ WRITE_ONCE(slot->addr, READ_ONCE(hazptr_wildcard)); /* Store B */
- /*
- * 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 */
+ /* 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 */
+ }
ctx->slot = slot;
if (!addr && hazptr_slot_is_backup(ctx, slot))
hazptr_unchain_backup_slot(ctx);
--
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com