Re: [RFC/WIP PATCH 1/4] hazptr: add shared-scan kthread

[Boqun Feng <boqun@kernel.org>]

On Tue, Sep 22, 2026 at 03:09:47PM +0800, Kunwu Chan wrote:
> Batch concurrent hazptr_synchronize() callers into a shared scan
> cycle, avoiding redundant scans of the per-CPU slots.
> 
> Queue waiters to a kthread and let each scan cycle make one pass
> over all CPUs.  Each waiter tracks per-CPU progress for both
> wildcard generations, allowing multiple waiters to share the same
> scan.
> 
> Flip the wildcard before scanning.  New acquires then use the new
> generation, so the old-generation mask makes forward progress even
> under a steady stream of readers.  Waiters that remain blocked are
> retried after a short delay.
> 
> Fall back to the existing direct two-phase scan if the scan kthread
> is unavailable or waiter state cannot be allocated.
> 
> Signed-off-by: Kunwu Chan <kunwu.chan@gmail.com>
> ---
>  kernel/hazptr.c | 274 ++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 274 insertions(+)
> 
> diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> index d3d1050d92cf..ce553a61b119 100644
> --- a/kernel/hazptr.c
> +++ b/kernel/hazptr.c
> @@ -12,6 +12,10 @@
>  #include <linux/mutex.h>
>  #include <linux/list.h>
>  #include <linux/export.h>
> +#include <linux/completion.h>
> +#include <linux/kthread.h>
> +#include <linux/slab.h>
> +#include <linux/swait.h>
>  
>  /*
>   * The current hazard pointer wildcard. Flips between 1UL and 2UL to guarantee
> @@ -209,12 +213,251 @@ void hazptr_scan_period(void *addr, void *scan_wildcard)
>  	}
>  }
>  
> +/*
> + * Batch hazptr_synchronize() callers through a shared scan kthread.
> + */
> +
> +struct hazptr_waiter {
> +	struct list_head node;
> +	void *addr;
> +	struct completion done;
> +	/*
> +	 * Per-wildcard-generation progress masks.  A CPU bit is
> +	 * cleared when the scan observes neither @addr nor that
> +	 * generation's wildcard on the CPU.
> +	 */
> +	unsigned long *cpu_mask;	/* 2 * BITS_TO_LONGS(nr_cpu_ids) */

This would requires allocation during hazptr_synchronize() and I would
like to avoid that (it's going to introduce a "allocating memory to free
memory" case).

Mathieu brought up a useful data structure for the scan: A Bloom filter:

	https://en.wikipedia.org/wiki/Bloom_filter

, which is basically a bitmap set + k hash functions. Let's say we have
a struct bloom_filter (you can still with a page as the bitmap and k=3)
and put it in hazptr_scan_state. Then the scan would become:

	bloom_filter_clear(); // <- reset the bloom filer.

	for_each_possible_cpu()
          hlist_for_each_entry(b, &list->head, overflow_node) {
	    bloom_filter_set(*b->slot.addr);
	    // ^ add the hazptr_acquire() adress into the bloom filter
	  }
	
	list_for_each_entry(w, &hazptr_scan.scanning, node) {
	  if (!bloom_filter_contains(w->addr)) {
	    list_move(&w->node, &done);
	  }
	}

Of course, there are some additional handling or optimizaiton we can do
with the per-CPU slot and wildcard, but this is the idea. It also makes 
a potential call_hazptr() work.

Willing to give it a try?

Regards,
Boqun

> +};
> +
> +/* Return waiter @w's progress mask for wildcard generation @gen. */
> +static unsigned long *hazptr_waiter_mask(struct hazptr_waiter *w, int gen)
> +{
> +	return w->cpu_mask + gen * BITS_TO_LONGS(nr_cpu_ids);
> +}
> +
> +struct hazptr_scan_state {
> +	struct task_struct *kthread;
> +	struct swait_queue_head wq;
> +	bool wakeup;
> +	struct mutex lock;
> +	struct list_head pending;
> +	struct list_head scanning;	/* kthread only */
> +};
> +static struct hazptr_scan_state hazptr_scan;
> +
> +/*
> + * Check a CPU's overflow lists.  A backup slot can hold a wildcard
> + * because __hazptr_acquire() writes the wildcard to any slot,
> + * including backup slots from hazptr_chain_backup_slot().
> + *
> + * @addr:     address the waiter is waiting on
> + * @old_wc:   wildcard value of the pre-flip generation
> + * @new_wc:   wildcard value of the post-flip generation
> + * @has_old:  set if any overflow slot holds @old_wc
> + * @has_new:  set if any overflow slot holds @new_wc
> + *
> + * Returns true if @addr is present.
> + */
> +static bool hazptr_ovf_list_blocked(int cpu, void *addr,
> +				    void *old_wc, void *new_wc,
> +				    bool *has_old, bool *has_new)
> +{
> +	struct hazptr_overflow_list_flip *ovf = per_cpu_ptr(&percpu_overflow_list_flip, cpu);
> +	bool found_addr = false;
> +	int i;
> +
> +	for (i = 0; i < 2; i++) {
> +		struct hazptr_overflow_list *list = &ovf->array[i];
> +		struct hazptr_backup_slot *b;
> +		unsigned long flags;
> +
> +		raw_spin_lock_irqsave(&list->lock, flags);
> +		hlist_for_each_entry(b, &list->head, overflow_node) {
> +			/* Pairs with smp_store_release in hazptr_release(). */
> +			void *val = smp_load_acquire(&b->slot.addr);
> +
> +			if (val == addr)
> +				found_addr = true;
> +			else if (val == old_wc)
> +				*has_old = true;
> +			else if (val == new_wc)
> +				*has_new = true;
> +		}
> +		raw_spin_unlock_irqrestore(&list->lock, flags);
> +	}
> +	return found_addr;
> +}
> +
> +/*
> + * Move pending waiters to ->scanning, flip the wildcard, then make
> + * one pass over all CPUs.  Clear per-waiter bits for CPUs that no
> + * longer hold the waiter address or the corresponding wildcard.
> + *
> + * After the flip, new acquires use the new wildcard.  The old
> + * generation therefore makes forward progress and is fully cleared
> + * after enough scan cycles.
> + */
> +static void hazptr_scan_do_cycle(void)
> +{
> +	void *old_wc, *new_wc;
> +	unsigned int old_idx, new_idx;
> +	int cpu;
> +	struct hazptr_waiter *w, *n;
> +	LIST_HEAD(done);
> +
> +	mutex_lock(&hazptr_wildcard_lock);
> +
> +	mutex_lock(&hazptr_scan.lock);
> +	list_splice_tail_init(&hazptr_scan.pending, &hazptr_scan.scanning);
> +	mutex_unlock(&hazptr_scan.lock);
> +
> +	if (list_empty(&hazptr_scan.scanning)) {
> +		mutex_unlock(&hazptr_wildcard_lock);
> +		return;
> +	}
> +
> +	old_wc = READ_ONCE(hazptr_wildcard);
> +	new_wc = flip_wildcard(old_wc);
> +	WRITE_ONCE(hazptr_wildcard, new_wc);
> +	old_idx = (unsigned long)old_wc - 1;
> +	new_idx = 1 - old_idx;
> +
> +	/*
> +	 * One pass over all CPUs for the per-CPU slots, checking
> +	 * overflow lists for the remaining waiters.
> +	 */
> +	for_each_possible_cpu(cpu) {
> +		struct hazptr_percpu_slots *slots = per_cpu_ptr(&hazptr_percpu_slots, cpu);
> +		void *vals[NR_HAZPTR_PERCPU_SLOTS];
> +		bool has_old = false, has_new = false;
> +		unsigned int idx;
> +
> +		for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> +			/* Pairs with smp_store_release in hazptr_release(). */
> +			vals[idx] = smp_load_acquire(&slots->items[idx].slot.addr);
> +			if (vals[idx] == old_wc)
> +				has_old = true;
> +			else if (vals[idx] == new_wc)
> +				has_new = true;
> +		}
> +
> +		list_for_each_entry(w, &hazptr_scan.scanning, node) {
> +			bool has_addr = false;
> +
> +			if (!test_bit(cpu, hazptr_waiter_mask(w, old_idx)) &&
> +			    !test_bit(cpu, hazptr_waiter_mask(w, new_idx)))
> +				continue;	/* Both bits already clear. */
> +			for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> +				if (vals[idx] == w->addr) {
> +					has_addr = true;
> +					break;
> +				}
> +			}
> +			if (!has_addr)
> +				has_addr = hazptr_ovf_list_blocked(cpu, w->addr,
> +					old_wc, new_wc, &has_old, &has_new);
> +			if (has_addr)
> +				continue;
> +			if (!has_old)
> +				__clear_bit(cpu, hazptr_waiter_mask(w, old_idx));
> +			if (!has_new)
> +				__clear_bit(cpu, hazptr_waiter_mask(w, new_idx));
> +		}
> +	}
> +
> +	mutex_unlock(&hazptr_wildcard_lock);
> +
> +	/* Complete waiters whose masks are both empty. */
> +	list_for_each_entry_safe(w, n, &hazptr_scan.scanning, node) {
> +		if (bitmap_empty(hazptr_waiter_mask(w, 0), nr_cpu_ids) &&
> +		    bitmap_empty(hazptr_waiter_mask(w, 1), nr_cpu_ids))
> +			list_move(&w->node, &done);
> +	}
> +
> +	list_for_each_entry_safe(w, n, &done, node) {
> +		list_del_init(&w->node);
> +		complete(&w->done);
> +	}
> +}
> +
> +/*
> + * Shared scan kthread for hazptr_synchronize() waiters.
> + */
> +static int hazptr_scan_kthread(void *unused)
> +{
> +	for (;;) {
> +		bool idle;
> +
> +		swait_event_idle_exclusive(hazptr_scan.wq,
> +					   READ_ONCE(hazptr_scan.wakeup));
> +
> +		hazptr_scan_do_cycle();
> +
> +		mutex_lock(&hazptr_scan.lock);
> +		idle = list_empty(&hazptr_scan.pending) &&
> +		      list_empty(&hazptr_scan.scanning);
> +		if (idle)
> +			WRITE_ONCE(hazptr_scan.wakeup, false);
> +		mutex_unlock(&hazptr_scan.lock);
> +
> +		if (idle)
> +			continue;
> +		/* Waiters still blocked: retry after a polling delay. */
> +		schedule_timeout_idle(1);
> +	}
> +	return 0;
> +}
> +
> +/*
> + * Queue @addr for scan-thread processing, then sleep until the scan
> + * thread observes that @addr is no longer held by any hazard pointer.
> + * Returns false if the waiter masks cannot be allocated, in which
> + * case the caller falls back to the direct scan.
> + */
> +static bool hazptr_synchronize_queued(void *addr)
> +{
> +	struct hazptr_waiter waiter = {
> +		.addr = addr,
> +	};
> +	unsigned long *masks;
> +	unsigned int mask_longs = BITS_TO_LONGS(nr_cpu_ids);
> +
> +	masks = kcalloc(2, mask_longs * sizeof(unsigned long), GFP_KERNEL);
> +	if (!masks)
> +		return false;
> +	bitmap_fill(masks, nr_cpu_ids);
> +	bitmap_fill(masks + mask_longs, nr_cpu_ids);
> +	waiter.cpu_mask = masks;
> +
> +	init_completion(&waiter.done);
> +	INIT_LIST_HEAD(&waiter.node);
> +
> +	/* Enqueue and wake the scan kthread. */
> +	mutex_lock(&hazptr_scan.lock);
> +	list_add_tail(&waiter.node, &hazptr_scan.pending);
> +	if (!READ_ONCE(hazptr_scan.wakeup)) {
> +		WRITE_ONCE(hazptr_scan.wakeup, true);
> +		swake_up_one(&hazptr_scan.wq);
> +	}
> +	mutex_unlock(&hazptr_scan.lock);
> +
> +	/* Sleep until the scan thread completes this waiter. */
> +	wait_for_completion(&waiter.done);
> +	kfree(masks);
> +	return true;
> +}
> +
>  /*
>   * hazptr_synchronize: Wait until @addr is released from all slots.
>   *
>   * Wait to observe that each slot contains a value that differs from
>   * @addr before returning.
>   * Should be called from preemptible context.
> + *
> + * If the scan kthread is running, the caller is queued and the scan
> + * thread performs the work, allowing multiple concurrent callers to
> + * share a single scan cycle.  Otherwise, the existing direct
> + * two-phase scan is used as a fallback.
>   */
>  void hazptr_synchronize(void *addr)
>  {
> @@ -235,6 +478,13 @@ void hazptr_synchronize(void *addr)
>  	/* Memory ordering: Store A before Load B. */
>  	smp_mb();
>  
> +	/* Use the scan thread if available. */
> +	/* Pairs with smp_store_release in hazptr_scan_init(). */
> +	if (smp_load_acquire(&hazptr_scan.kthread) &&
> +	    hazptr_synchronize_queued(addr))
> +		return;
> +
> +	/* Fallback: direct two-phase wildcard scan. */
>  	guard(mutex)(&hazptr_wildcard_lock);
>  	scan_wildcard = flip_wildcard(hazptr_wildcard);
>  	hazptr_scan_period(addr, scan_wildcard);
> @@ -282,3 +532,27 @@ void __init hazptr_init(void)
>  		}
>  	}
>  }
> +
> +/*
> + * Initialize the scan kthread.  On failure falls back to the direct
> + * scan (busy-wait) path at synchronize time.
> + * core_initcall ensures the scheduler is ready before kthread_run.
> + */
> +static int __init hazptr_scan_init(void)
> +{
> +	struct task_struct *t;
> +
> +	init_swait_queue_head(&hazptr_scan.wq);
> +	mutex_init(&hazptr_scan.lock);
> +	INIT_LIST_HEAD(&hazptr_scan.pending);
> +	INIT_LIST_HEAD(&hazptr_scan.scanning);
> +
> +	t = kthread_run(hazptr_scan_kthread, NULL, "hazptr_scan");
> +	if (!IS_ERR(t))
> +		/* Pairs with smp_load_acquire in hazptr_synchronize(). */
> +		smp_store_release(&hazptr_scan.kthread, t);
> +	else
> +		pr_warn("hazptr: scan thread failed, using direct scan\n");
> +	return 0;
> +}
> +core_initcall(hazptr_scan_init);
> -- 
> 2.43.0
>