[RFC PATCH 1/1] hazptr: Implement two-phases wildcard scan

[RFC PATCH 1/1] hazptr: Implement two-phases wildcard scan

[Mathieu Desnoyers]

Implement a two-phases 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 simplificaiton, 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 <mathieu.desnoyers@efficios.com>
---
 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;
 	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.43.0

Re: [RFC PATCH 1/1] hazptr: Implement two-phases wildcard scan

[Mathieu Desnoyers]

On 2026-08-08 13:31, Mathieu Desnoyers wrote:
> Implement a two-phases 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 simplificaiton, use this period flip to drive the hazptr overflow

typo: simplification

Thanks,

Mathieu

> 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 <mathieu.desnoyers@efficios.com>
> ---
>   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;
>   	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);


-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [RFC PATCH 1/1] hazptr: Implement two-phases wildcard scan

[Bradley Morgan]

Hi, thanks for your patch, 
Please bare that this is a brand new file, and I haven't gained the
expertise! (Heh) Yet.

I personally think this is a useful addition.. 

I may be embarrassing myself here, but I have no objections of this 
patch (well, I'm not a maintainer so I can't say *objection* anyway, 
but oh well...)

Reviewed-by: Bradley Morgan <include@grrlz.net>

Thanks!