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

[Kunwu Chan <kunwu.chan@gmail.com>]

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) */
+};
+
+/* 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