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

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

On 2026-09-25 15:19, Mathieu Desnoyers wrote:
> On 2026-09-20 11:57, Gary Guo wrote:
>> 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@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.
>>>>
>>>> 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 ?
> 
Something like this lightly compile tested patch on top of my prior
[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