[RFC PATCH 0/8] Introduce simple hazard pointers for lockdep

[RFC PATCH 0/8] Introduce simple hazard pointers for lockdep

[Boqun Feng]

Hi,

This RFC is mostly a follow-up on discussion:

	https://lore.kernel.org/lkml/20250321-lockdep-v1-1-78b732d195fb@debian.org/

I found that using a hazard pointer variant can speed up the
lockdep_unregister_key(), on my system (a 96-cpu VMs), the results of:

	time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq

are

	(without the patchset)
	real    0m1.039s
	user    0m0.001s
	sys     0m0.069s

	(with the patchset)
	real    0m0.053s
	user    0m0.000s
	sys     0m0.051s

i.e. almost 20x speed-up.

Other comparisons between RCU and shazptr, the rcuscale results (using
default configuration from
tools/testing/selftests/rcutorture/bin/kvm.sh):

RCU:

	Average grace-period duration: 7470.02 microseconds
	Minimum grace-period duration: 3981.6
	50th percentile grace-period duration: 6002.73
	90th percentile grace-period duration: 7008.93
	99th percentile grace-period duration: 10015
	Maximum grace-period duration: 142228

shazptr:

	Average grace-period duration: 0.845825 microseconds
	Minimum grace-period duration: 0.199
	50th percentile grace-period duration: 0.585
	90th percentile grace-period duration: 1.656
	99th percentile grace-period duration: 3.872
	Maximum grace-period duration: 3049.05

shazptr (skip_synchronize_self_scan=1, i.e. always let scan kthread to
wakeup):

	Average grace-period duration: 467.861 microseconds
	Minimum grace-period duration: 92.913
	50th percentile grace-period duration: 440.691
	90th percentile grace-period duration: 460.623
	99th percentile grace-period duration: 650.068
	Maximum grace-period duration: 5775.46

shazptr_wildcard (i.e. readers always use SHAZPTR_WILDCARD):

	Average grace-period duration: 599.569 microseconds
	Minimum grace-period duration: 1.432
	50th percentile grace-period duration: 582.631
	90th percentile grace-period duration: 781.704
	99th percentile grace-period duration: 1160.26
	Maximum grace-period duration: 6727.53

shazptr_wildcard (skip_synchronize_self_scan=1):

	Average grace-period duration: 460.466 microseconds
	Minimum grace-period duration: 303.546
	50th percentile grace-period duration: 424.334
	90th percentile grace-period duration: 482.637
	99th percentile grace-period duration: 600.214
	Maximum grace-period duration: 4126.94
	

Overall it looks promising to me, but I would like to see how it
performs in the environment of Breno. Also as Paul always reminds me:
buggy code usually run faster, so please take a look in case I'm missing
something ;-) Thanks!

The patchset is based on v6.15-rc1.

Boqun Feng (8):
  Introduce simple hazard pointers
  shazptr: Add refscale test
  shazptr: Add refscale test for wildcard
  shazptr: Avoid synchronize_shaptr() busy waiting
  shazptr: Allow skip self scan in synchronize_shaptr()
  rcuscale: Allow rcu_scale_ops::get_gp_seq to be NULL
  rcuscale: Add tests for simple hazard pointers
  locking/lockdep: Use shazptr to protect the key hashlist

 include/linux/shazptr.h  |  73 +++++++++
 kernel/locking/Makefile  |   2 +-
 kernel/locking/lockdep.c |  11 +-
 kernel/locking/shazptr.c | 318 +++++++++++++++++++++++++++++++++++++++
 kernel/rcu/rcuscale.c    |  60 +++++++-
 kernel/rcu/refscale.c    |  77 ++++++++++
 6 files changed, 534 insertions(+), 7 deletions(-)
 create mode 100644 include/linux/shazptr.h
 create mode 100644 kernel/locking/shazptr.c

-- 
2.47.1

[RFC PATCH 1/8] Introduce simple hazard pointers

[Boqun Feng]

As its name suggests, simple hazard pointers (shazptr) is a
simplification of hazard pointers [1]: it has only one hazard pointer
slot per-CPU and is targeted for simple use cases where the read-side
already has preemption disabled. It's a trade-off between full features
of a normal hazard pointer implementation (multiple slots, dynamic slot
allocation, etc.) and the simple use scenario.

Since there's only one slot per-CPU, so shazptr read-side critical
section nesting is a problem that needs to be resolved, because at very
least, interrupts and NMI can introduce nested shazptr read-side
critical sections. A SHAZPTR_WILDCARD is introduced to resolve this:
SHAZPTR_WILDCARD is a special address value that blocks *all* shazptr
waiters. In an interrupt-causing shazptr read-side critical section
nesting case (i.e. an interrupt happens while the per-CPU hazard pointer
slot being used and tries to acquire a hazard pointer itself), the inner
critical section will switch the value of the hazard pointer slot into
SHAZPTR_WILDCARD, and let the outer critical section eventually zero the
slot. The SHAZPTR_WILDCARD still provide the correct protection because
it blocks all the waiters.

It's true that once the wildcard mechanism is activated, shazptr
mechanism may be downgrade to something similar to RCU (and probably
with a worse implementation), which generally has longer wait time and
larger memory footprint compared to a typical hazard pointer
implementation. However, that can only happen with a lot of users using
hazard pointers, and then it's reasonable to introduce the
fully-featured hazard pointer implementation [2] and switch users to it.

Note that shazptr_protect() may be added later, the current potential
usage doesn't require it, and a shazptr_acquire(), which installs the
protected value to hazard pointer slot and proves the smp_mb(), is
enough for now.

[1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
     lock-free objects," in IEEE Transactions on Parallel and
     Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004

Link: https://lore.kernel.org/lkml/20240917143402.930114-1-boqun.feng@gmail.com/ [2]
Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 include/linux/shazptr.h  | 73 ++++++++++++++++++++++++++++++++++++++++
 kernel/locking/Makefile  |  2 +-
 kernel/locking/shazptr.c | 29 ++++++++++++++++
 3 files changed, 103 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/shazptr.h
 create mode 100644 kernel/locking/shazptr.c

diff --git a/include/linux/shazptr.h b/include/linux/shazptr.h
new file mode 100644
index 000000000000..287cd04b4be9
--- /dev/null
+++ b/include/linux/shazptr.h
@@ -0,0 +1,73 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Simple hazard pointers
+ *
+ * Copyright (c) 2025, Microsoft Corporation.
+ *
+ * Author: Boqun Feng <boqun.feng@gmail.com>
+ *
+ * A simple variant of hazard pointers, the users must ensure the preemption
+ * is already disabled when calling a shazptr_acquire() to protect an address.
+ * If one shazptr_acquire() is called after another shazptr_acquire() has been
+ * called without the corresponding shazptr_clear() has been called, the later
+ * shazptr_acquire() must be cleared first.
+ *
+ * The most suitable usage is when only one address need to be protected in a
+ * preemption disabled critical section.
+ */
+
+#ifndef _LINUX_SHAZPTR_H
+#define _LINUX_SHAZPTR_H
+
+#include <linux/cleanup.h>
+#include <linux/percpu.h>
+
+/* Make ULONG_MAX the wildcard value */
+#define SHAZPTR_WILDCARD ((void *)(ULONG_MAX))
+
+DECLARE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
+
+/* Represent a held hazard pointer slot */
+struct shazptr_guard {
+	void **slot;
+	bool use_wildcard;
+};
+
+/*
+ * Acquire a hazptr slot and begin the hazard pointer critical section.
+ *
+ * Must be called with preemption disabled, and preemption must remain disabled
+ * until shazptr_clear().
+ */
+static inline struct shazptr_guard shazptr_acquire(void *ptr)
+{
+	struct shazptr_guard guard = {
+		/* Preemption is disabled. */
+		.slot = this_cpu_ptr(&shazptr_slots),
+		.use_wildcard = false,
+	};
+
+	if (likely(!READ_ONCE(*guard.slot))) {
+		WRITE_ONCE(*guard.slot, ptr);
+	} else {
+		guard.use_wildcard = true;
+		WRITE_ONCE(*guard.slot, SHAZPTR_WILDCARD);
+	}
+
+	smp_mb(); /* Synchronize with smp_mb() at synchronize_shazptr(). */
+
+	return guard;
+}
+
+static inline void shazptr_clear(struct shazptr_guard guard)
+{
+	/* Only clear the slot when the outermost guard is released */
+	if (likely(!guard.use_wildcard))
+		smp_store_release(guard.slot, NULL); /* Pair with ACQUIRE at synchronize_shazptr() */
+}
+
+void synchronize_shazptr(void *ptr);
+
+DEFINE_CLASS(shazptr, struct shazptr_guard, shazptr_clear(_T),
+	     shazptr_acquire(ptr), void *ptr);
+#endif
diff --git a/kernel/locking/Makefile b/kernel/locking/Makefile
index a114949eeed5..1517076c98ec 100644
--- a/kernel/locking/Makefile
+++ b/kernel/locking/Makefile
@@ -3,7 +3,7 @@
 # and is generally not a function of system call inputs.
 KCOV_INSTRUMENT		:= n
 
-obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o
+obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o shazptr.o
 
 # Avoid recursion lockdep -> sanitizer -> ... -> lockdep & improve performance.
 KASAN_SANITIZE_lockdep.o := n
diff --git a/kernel/locking/shazptr.c b/kernel/locking/shazptr.c
new file mode 100644
index 000000000000..991fd1a05cfd
--- /dev/null
+++ b/kernel/locking/shazptr.c
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Simple hazard pointers
+ *
+ * Copyright (c) 2025, Microsoft Corporation.
+ *
+ * Author: Boqun Feng <boqun.feng@gmail.com>
+ */
+
+#include <linux/atomic.h>
+#include <linux/cpumask.h>
+#include <linux/shazptr.h>
+
+DEFINE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
+EXPORT_PER_CPU_SYMBOL_GPL(shazptr_slots);
+
+void synchronize_shazptr(void *ptr)
+{
+	int cpu;
+
+	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
+	for_each_possible_cpu(cpu) {
+		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
+		/* Pair with smp_store_release() in shazptr_clear(). */
+		smp_cond_load_acquire(slot,
+				      VAL != ptr && VAL != SHAZPTR_WILDCARD);
+	}
+}
+EXPORT_SYMBOL_GPL(synchronize_shazptr);
-- 
2.47.1

[RFC PATCH 2/8] shazptr: Add refscale test

[Boqun Feng]

Add the refscale test for shazptr to measure the reader side
performance.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/rcu/refscale.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/kernel/rcu/refscale.c b/kernel/rcu/refscale.c
index f11a7c2af778..154520e4ee4c 100644
--- a/kernel/rcu/refscale.c
+++ b/kernel/rcu/refscale.c
@@ -29,6 +29,7 @@
 #include <linux/reboot.h>
 #include <linux/sched.h>
 #include <linux/seq_buf.h>
+#include <linux/shazptr.h>
 #include <linux/spinlock.h>
 #include <linux/smp.h>
 #include <linux/stat.h>
@@ -890,6 +891,43 @@ static const struct ref_scale_ops typesafe_seqlock_ops = {
 	.name		= "typesafe_seqlock"
 };
 
+static void ref_shazptr_read_section(const int nloops)
+{
+	int i;
+
+	for (i = nloops; i >= 0; i--) {
+		preempt_disable();
+		{ guard(shazptr)(ref_shazptr_read_section); }
+		preempt_enable();
+	}
+}
+
+static void ref_shazptr_delay_section(const int nloops, const int udl, const int ndl)
+{
+	int i;
+
+	for (i = nloops; i >= 0; i--) {
+		preempt_disable();
+		{
+			guard(shazptr)(ref_shazptr_delay_section);
+			un_delay(udl, ndl);
+		}
+		preempt_enable();
+	}
+}
+
+static bool ref_shazptr_init(void)
+{
+	return true;
+}
+
+static const struct ref_scale_ops shazptr_ops = {
+	.init		= ref_shazptr_init,
+	.readsection	= ref_shazptr_read_section,
+	.delaysection	= ref_shazptr_delay_section,
+	.name		= "shazptr"
+};
+
 static void rcu_scale_one_reader(void)
 {
 	if (readdelay <= 0)
@@ -1197,6 +1235,7 @@ ref_scale_init(void)
 		&refcnt_ops, &rwlock_ops, &rwsem_ops, &lock_ops, &lock_irq_ops,
 		&acqrel_ops, &sched_clock_ops, &clock_ops, &jiffies_ops,
 		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops,
+		&shazptr_ops,
 	};
 
 	if (!torture_init_begin(scale_type, verbose))
-- 
2.47.1

[RFC PATCH 3/8] shazptr: Add refscale test for wildcard

[Boqun Feng]

Add the refscale test for shazptr, which starts another shazptr critical
section inside an existing one to measure the reader side performance
when wildcard logic is triggered.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/rcu/refscale.c | 40 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 39 insertions(+), 1 deletion(-)

diff --git a/kernel/rcu/refscale.c b/kernel/rcu/refscale.c
index 154520e4ee4c..fdbb4a2c91fe 100644
--- a/kernel/rcu/refscale.c
+++ b/kernel/rcu/refscale.c
@@ -928,6 +928,44 @@ static const struct ref_scale_ops shazptr_ops = {
 	.name		= "shazptr"
 };
 
+static void ref_shazptr_wc_read_section(const int nloops)
+{
+	int i;
+
+	for (i = nloops; i >= 0; i--) {
+		preempt_disable();
+		{
+			guard(shazptr)(ref_shazptr_read_section);
+			/* Trigger wildcard logic */
+			guard(shazptr)(ref_shazptr_wc_read_section);
+		}
+		preempt_enable();
+	}
+}
+
+static void ref_shazptr_wc_delay_section(const int nloops, const int udl, const int ndl)
+{
+	int i;
+
+	for (i = nloops; i >= 0; i--) {
+		preempt_disable();
+		{
+			guard(shazptr)(ref_shazptr_delay_section);
+			/* Trigger wildcard logic */
+			guard(shazptr)(ref_shazptr_wc_delay_section);
+			un_delay(udl, ndl);
+		}
+		preempt_enable();
+	}
+}
+
+static const struct ref_scale_ops shazptr_wildcard_ops = {
+	.init		= ref_shazptr_init,
+	.readsection	= ref_shazptr_wc_read_section,
+	.delaysection	= ref_shazptr_wc_delay_section,
+	.name		= "shazptr_wildcard"
+};
+
 static void rcu_scale_one_reader(void)
 {
 	if (readdelay <= 0)
@@ -1235,7 +1273,7 @@ ref_scale_init(void)
 		&refcnt_ops, &rwlock_ops, &rwsem_ops, &lock_ops, &lock_irq_ops,
 		&acqrel_ops, &sched_clock_ops, &clock_ops, &jiffies_ops,
 		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops,
-		&shazptr_ops,
+		&shazptr_ops, &shazptr_wildcard_ops,
 	};
 
 	if (!torture_init_begin(scale_type, verbose))
-- 
2.47.1

[RFC PATCH 4/8] shazptr: Avoid synchronize_shaptr() busy waiting

[Boqun Feng]

For a general purpose hazard pointers implemenation, always busy waiting
is not an option. It may benefit some special workload, but overall it
hurts the system performance when more and more users begin to call
synchronize_shazptr(). Therefore avoid busy waiting for hazard pointer
slots changes by using a scan kthread, and each synchronize_shazptr()
queues themselves if a quick scan shows they are blocked by some slots.

A simple optimization is done inside the scan: each
synchronize_shazptr() tracks which CPUs (or CPU groups if nr_cpu_ids >
BITS_PER_LONG) are blocking it and the scan function updates this
information for each synchronize_shazptr() (via shazptr_wait)
individually. In this way, synchronize_shazptr() doesn't need to wait
until a scan result showing all slots are not blocking (as long as the
scan has observed each slot has changed into non-block state once).

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/locking/shazptr.c | 277 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 276 insertions(+), 1 deletion(-)

diff --git a/kernel/locking/shazptr.c b/kernel/locking/shazptr.c
index 991fd1a05cfd..a8559cb559f8 100644
--- a/kernel/locking/shazptr.c
+++ b/kernel/locking/shazptr.c
@@ -7,18 +7,243 @@
  * Author: Boqun Feng <boqun.feng@gmail.com>
  */
 
+#define pr_fmt(fmt) "shazptr: " fmt
+
 #include <linux/atomic.h>
 #include <linux/cpumask.h>
+#include <linux/completion.h>
+#include <linux/kthread.h>
+#include <linux/list.h>
+#include <linux/mutex.h>
 #include <linux/shazptr.h>
+#include <linux/slab.h>
+#include <linux/sort.h>
 
 DEFINE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
 EXPORT_PER_CPU_SYMBOL_GPL(shazptr_slots);
 
-void synchronize_shazptr(void *ptr)
+/* Wait structure for synchronize_shazptr(). */
+struct shazptr_wait {
+	struct list_head list;
+	/* Which groups of CPUs are blocking. */
+	unsigned long blocking_grp_mask;
+	void *ptr;
+	struct completion done;
+};
+
+/* Snapshot for hazptr slot. */
+struct shazptr_snapshot {
+	unsigned long ptr;
+	unsigned long grp_mask;
+};
+
+static inline int
+shazptr_snapshot_cmp(const void *a, const void *b)
+{
+	const struct shazptr_snapshot *snap_a = (struct shazptr_snapshot *)a;
+	const struct shazptr_snapshot *snap_b = (struct shazptr_snapshot *)b;
+
+	if (snap_a->ptr > snap_b->ptr)
+		return 1;
+	else if (snap_a->ptr < snap_b->ptr)
+		return -1;
+	else
+		return 0;
+}
+
+/* *In-place* merge @n together based on ->ptr and accumulate the >grp_mask. */
+static int shazptr_snapshot_merge(struct shazptr_snapshot *snaps, int n)
+{
+	int new, i;
+
+	/* Sort first. */
+	sort(snaps, n, sizeof(*snaps), shazptr_snapshot_cmp, NULL);
+
+	new = 0;
+
+	/* Skip NULLs. */
+	for (i = 0; i < n; i++) {
+		if (snaps[i].ptr)
+			break;
+	}
+
+	while (i < n) {
+		/* Start with a new address. */
+		snaps[new] = snaps[i];
+
+		for (; i < n; i++) {
+			/* Merge if the next one has the same address. */
+			if (snaps[new].ptr == snaps[i].ptr) {
+				snaps[new].grp_mask |= snaps[i].grp_mask;
+			} else
+				break;
+		}
+
+		/*
+		 * Either the end has been reached or need to start with a new
+		 * record.
+		 */
+		new++;
+	}
+
+	return new;
+}
+
+/*
+ * Calculate which group is still blocking @ptr, this assumes the @snaps is
+ * already merged.
+ */
+static unsigned long
+shazptr_snapshot_blocking_grp_mask(struct shazptr_snapshot *snaps,
+				   int n, void *ptr)
+{
+	unsigned long mask = 0;
+
+	if (!n)
+		return mask;
+	else if (snaps[n-1].ptr == (unsigned long)SHAZPTR_WILDCARD) {
+		/*
+		 * Take SHAZPTR_WILDCARD slots, which is ULONG_MAX, into
+		 * consideration if any.
+		 */
+		mask = snaps[n-1].grp_mask;
+	}
+
+	/* TODO: binary search if n is big. */
+	for (int i = 0; i < n; i++) {
+		if (snaps[i].ptr == (unsigned long)ptr) {
+			mask |= snaps[i].grp_mask;
+			break;
+		}
+	}
+
+	return mask;
+}
+
+/* Scan structure for synchronize_shazptr(). */
+struct shazptr_scan {
+	/* The scan kthread */
+	struct task_struct *thread;
+
+	/* Wait queue for the scan kthread */
+	struct swait_queue_head wq;
+
+	/* Whether the scan kthread has been scheduled to scan */
+	bool scheduled;
+
+	/* The lock protecting ->queued and ->scheduled */
+	struct mutex lock;
+
+	/* List of queued synchronize_shazptr() request. */
+	struct list_head queued;
+
+	int cpu_grp_size;
+
+	/* List of scanning synchronize_shazptr() request. */
+	struct list_head scanning;
+
+	/* Buffer used for hazptr slot scan, nr_cpu_ids slots*/
+	struct shazptr_snapshot* snaps;
+};
+
+static struct shazptr_scan shazptr_scan;
+
+static void shazptr_do_scan(struct shazptr_scan *scan)
+{
+	int cpu;
+	int snaps_len;
+	struct shazptr_wait *curr, *next;
+
+	scoped_guard(mutex, &scan->lock) {
+		/* Move from ->queued to ->scanning. */
+		list_splice_tail_init(&scan->queued, &scan->scanning);
+	}
+
+	memset(scan->snaps, nr_cpu_ids, sizeof(struct shazptr_snapshot));
+
+	for_each_possible_cpu(cpu) {
+		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
+		void *val;
+
+		/* Pair with smp_store_release() in shazptr_clear(). */
+		val = smp_load_acquire(slot);
+
+		scan->snaps[cpu].ptr = (unsigned long)val;
+		scan->snaps[cpu].grp_mask = 1UL << (cpu / scan->cpu_grp_size);
+	}
+
+	snaps_len = shazptr_snapshot_merge(scan->snaps, nr_cpu_ids);
+
+	/* Only one thread can access ->scanning, so can be lockless. */
+	list_for_each_entry_safe(curr, next, &scan->scanning, list) {
+		/* Accumulate the shazptr slot scan result. */
+		curr->blocking_grp_mask &=
+			shazptr_snapshot_blocking_grp_mask(scan->snaps,
+							   snaps_len,
+							   curr->ptr);
+
+		if (curr->blocking_grp_mask == 0) {
+			/* All shots are observed as not blocking once. */
+			list_del(&curr->list);
+			complete(&curr->done);
+		}
+	}
+}
+
+static int __noreturn shazptr_scan_kthread(void *unused)
+{
+	for (;;) {
+		swait_event_idle_exclusive(shazptr_scan.wq,
+					   READ_ONCE(shazptr_scan.scheduled));
+
+		shazptr_do_scan(&shazptr_scan);
+
+		scoped_guard(mutex, &shazptr_scan.lock) {
+			if (list_empty(&shazptr_scan.queued) &&
+			    list_empty(&shazptr_scan.scanning))
+				shazptr_scan.scheduled = false;
+		}
+	}
+}
+
+static int __init shazptr_scan_init(void)
+{
+	struct shazptr_scan *scan = &shazptr_scan;
+	struct task_struct *t;
+
+	init_swait_queue_head(&scan->wq);
+	mutex_init(&scan->lock);
+	INIT_LIST_HEAD(&scan->queued);
+	INIT_LIST_HEAD(&scan->scanning);
+	scan->scheduled = false;
+
+	/* Group CPUs into at most BITS_PER_LONG groups. */
+	scan->cpu_grp_size = DIV_ROUND_UP(nr_cpu_ids, BITS_PER_LONG);
+
+	scan->snaps = kcalloc(nr_cpu_ids, sizeof(scan->snaps[0]), GFP_KERNEL);
+
+	if (scan->snaps) {
+		t = kthread_run(shazptr_scan_kthread, NULL, "shazptr_scan");
+		if (!IS_ERR(t)) {
+			smp_store_release(&scan->thread, t);
+			/* Kthread creation succeeds */
+			return 0;
+		} else {
+			kfree(scan->snaps);
+		}
+	}
+
+	pr_info("Failed to create the scan thread, only busy waits\n");
+	return 0;
+}
+core_initcall(shazptr_scan_init);
+
+static void synchronize_shazptr_busywait(void *ptr)
 {
 	int cpu;
 
 	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
+
 	for_each_possible_cpu(cpu) {
 		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
 		/* Pair with smp_store_release() in shazptr_clear(). */
@@ -26,4 +251,54 @@ void synchronize_shazptr(void *ptr)
 				      VAL != ptr && VAL != SHAZPTR_WILDCARD);
 	}
 }
+
+static void synchronize_shazptr_normal(void *ptr)
+{
+	int cpu;
+	unsigned long blocking_grp_mask = 0;
+
+	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
+
+	for_each_possible_cpu(cpu) {
+		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
+		void *val;
+
+		/* Pair with smp_store_release() in shazptr_clear(). */
+		val = smp_load_acquire(slot);
+
+		if (val == ptr || val == SHAZPTR_WILDCARD)
+			blocking_grp_mask |= 1UL << (cpu / shazptr_scan.cpu_grp_size);
+	}
+
+	/* Found blocking slots, prepare to wait. */
+	if (blocking_grp_mask) {
+		struct shazptr_scan *scan = &shazptr_scan;
+		struct shazptr_wait wait = {
+			.blocking_grp_mask = blocking_grp_mask,
+		};
+
+		INIT_LIST_HEAD(&wait.list);
+		init_completion(&wait.done);
+
+		scoped_guard(mutex, &scan->lock) {
+			list_add_tail(&wait.list, &scan->queued);
+
+			if (!scan->scheduled) {
+				WRITE_ONCE(scan->scheduled, true);
+				swake_up_one(&shazptr_scan.wq);
+			}
+		}
+
+		wait_for_completion(&wait.done);
+	}
+}
+
+void synchronize_shazptr(void *ptr)
+{
+	/* Busy waiting if the scan kthread has not been created. */
+	if (!smp_load_acquire(&shazptr_scan.thread))
+		synchronize_shazptr_busywait(ptr);
+	else
+		synchronize_shazptr_normal(ptr);
+}
 EXPORT_SYMBOL_GPL(synchronize_shazptr);
-- 
2.47.1

[RFC PATCH 5/8] shazptr: Allow skip self scan in synchronize_shaptr()

[Boqun Feng]

Add a module parameter for shazptr to allow skip the self scan in
synchronize_shaptr(). This can force every synchronize_shaptr() to use
shazptr scan kthread, and help testing the shazptr scan kthread.

Another reason users may want to set this paramter is to reduce the self
scan CPU cost in synchronize_shaptr().

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/locking/shazptr.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

diff --git a/kernel/locking/shazptr.c b/kernel/locking/shazptr.c
index a8559cb559f8..b3f7e8390eb2 100644
--- a/kernel/locking/shazptr.c
+++ b/kernel/locking/shazptr.c
@@ -14,11 +14,17 @@
 #include <linux/completion.h>
 #include <linux/kthread.h>
 #include <linux/list.h>
+#include <linux/moduleparam.h>
 #include <linux/mutex.h>
 #include <linux/shazptr.h>
 #include <linux/slab.h>
 #include <linux/sort.h>
 
+#ifdef MODULE_PARAM_PREFIX
+#undef MODULE_PARAM_PREFIX
+#endif
+#define MODULE_PARAM_PREFIX "shazptr."
+
 DEFINE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
 EXPORT_PER_CPU_SYMBOL_GPL(shazptr_slots);
 
@@ -252,6 +258,10 @@ static void synchronize_shazptr_busywait(void *ptr)
 	}
 }
 
+/* Disabled by default. */
+static int skip_synchronize_self_scan;
+module_param(skip_synchronize_self_scan, int, 0644);
+
 static void synchronize_shazptr_normal(void *ptr)
 {
 	int cpu;
@@ -259,15 +269,19 @@ static void synchronize_shazptr_normal(void *ptr)
 
 	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
 
-	for_each_possible_cpu(cpu) {
-		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
-		void *val;
+	if (unlikely(skip_synchronize_self_scan)) {
+		blocking_grp_mask = ~0UL;
+	} else {
+		for_each_possible_cpu(cpu) {
+			void **slot = per_cpu_ptr(&shazptr_slots, cpu);
+			void *val;
 
-		/* Pair with smp_store_release() in shazptr_clear(). */
-		val = smp_load_acquire(slot);
+			/* Pair with smp_store_release() in shazptr_clear(). */
+			val = smp_load_acquire(slot);
 
-		if (val == ptr || val == SHAZPTR_WILDCARD)
-			blocking_grp_mask |= 1UL << (cpu / shazptr_scan.cpu_grp_size);
+			if (val == ptr || val == SHAZPTR_WILDCARD)
+				blocking_grp_mask |= 1UL << (cpu / shazptr_scan.cpu_grp_size);
+		}
 	}
 
 	/* Found blocking slots, prepare to wait. */
-- 
2.47.1

[RFC PATCH 6/8] rcuscale: Allow rcu_scale_ops::get_gp_seq to be NULL

[Boqun Feng]

For synchronization mechanisms similar to RCU, there could be no "grace
period" concept (e.g. hazard pointers), therefore allow
rcu_scale_ops::get_gp_seq to be a NULL pointer for these cases, and
simply treat started and finished grace period as 0.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/rcu/rcuscale.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/kernel/rcu/rcuscale.c b/kernel/rcu/rcuscale.c
index 0f3059b1b80d..d9bff4b1928b 100644
--- a/kernel/rcu/rcuscale.c
+++ b/kernel/rcu/rcuscale.c
@@ -568,8 +568,10 @@ rcu_scale_writer(void *arg)
 		if (gp_exp) {
 			b_rcu_gp_test_started =
 				cur_ops->exp_completed() / 2;
-		} else {
+		} else if (cur_ops->get_gp_seq) {
 			b_rcu_gp_test_started = cur_ops->get_gp_seq();
+		} else {
+			b_rcu_gp_test_started = 0;
 		}
 	}
 
@@ -625,9 +627,11 @@ rcu_scale_writer(void *arg)
 				if (gp_exp) {
 					b_rcu_gp_test_finished =
 						cur_ops->exp_completed() / 2;
-				} else {
+				} else if (cur_ops->get_gp_seq) {
 					b_rcu_gp_test_finished =
 						cur_ops->get_gp_seq();
+				} else {
+					b_rcu_gp_test_finished = 0;
 				}
 				if (shutdown) {
 					smp_mb(); /* Assign before wake. */
-- 
2.47.1

[RFC PATCH 7/8] rcuscale: Add tests for simple hazard pointers

[Boqun Feng]

Add two rcu_scale_ops to include tests from simple hazard pointers
(shazptr). One is with evenly distributed readers, and the other is with
all WILDCARD readers. This could show the best and worst case scenarios
for the synchronization time of simple hazard pointers.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/rcu/rcuscale.c | 52 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 51 insertions(+), 1 deletion(-)

diff --git a/kernel/rcu/rcuscale.c b/kernel/rcu/rcuscale.c
index d9bff4b1928b..cab42bcc1d26 100644
--- a/kernel/rcu/rcuscale.c
+++ b/kernel/rcu/rcuscale.c
@@ -32,6 +32,7 @@
 #include <linux/freezer.h>
 #include <linux/cpu.h>
 #include <linux/delay.h>
+#include <linux/shazptr.h>
 #include <linux/stat.h>
 #include <linux/srcu.h>
 #include <linux/slab.h>
@@ -429,6 +430,54 @@ static struct rcu_scale_ops tasks_tracing_ops = {
 
 #endif // #else // #ifdef CONFIG_TASKS_TRACE_RCU
 
+static int shazptr_scale_read_lock(void)
+{
+	long cpu = raw_smp_processor_id();
+
+	/* Use cpu + 1 as the key */
+	guard(shazptr)((void *)(cpu + 1));
+
+	return 0;
+}
+
+static int shazptr_scale_wc_read_lock(void)
+{
+	guard(shazptr)(SHAZPTR_WILDCARD);
+
+	return 0;
+}
+
+
+static void shazptr_scale_read_unlock(int idx)
+{
+	/* Do nothing, it's OK since readers are doing back-to-back lock+unlock*/
+}
+
+static void shazptr_scale_sync(void)
+{
+	long cpu = raw_smp_processor_id();
+
+	synchronize_shazptr((void *)(cpu + 1));
+}
+
+static struct rcu_scale_ops shazptr_ops = {
+	.ptype		= RCU_FLAVOR,
+	.readlock	= shazptr_scale_read_lock,
+	.readunlock	= shazptr_scale_read_unlock,
+	.sync		= shazptr_scale_sync,
+	.exp_sync	= shazptr_scale_sync,
+	.name		= "shazptr"
+};
+
+static struct rcu_scale_ops shazptr_wc_ops = {
+	.ptype		= RCU_FLAVOR,
+	.readlock	= shazptr_scale_wc_read_lock,
+	.readunlock	= shazptr_scale_read_unlock,
+	.sync		= shazptr_scale_sync,
+	.exp_sync	= shazptr_scale_sync,
+	.name		= "shazptr_wildcard"
+};
+
 static unsigned long rcuscale_seq_diff(unsigned long new, unsigned long old)
 {
 	if (!cur_ops->gp_diff)
@@ -1090,7 +1139,8 @@ rcu_scale_init(void)
 	long i;
 	long j;
 	static struct rcu_scale_ops *scale_ops[] = {
-		&rcu_ops, &srcu_ops, &srcud_ops, TASKS_OPS TASKS_RUDE_OPS TASKS_TRACING_OPS
+		&rcu_ops, &srcu_ops, &srcud_ops, &shazptr_ops, &shazptr_wc_ops,
+		TASKS_OPS TASKS_RUDE_OPS TASKS_TRACING_OPS
 	};
 
 	if (!torture_init_begin(scale_type, verbose))
-- 
2.47.1

[RFC PATCH 8/8] locking/lockdep: Use shazptr to protect the key hashlist

[Boqun Feng]

Erik Lundgren and Breno Leitao reported [1] a case where
lockdep_unregister_key() can be called from time critical code pathes
where rntl_lock() may be held. And the synchronize_rcu() in it can slow
down operations such as using tc to replace a qdisc in a network device.

In fact the synchronize_rcu() in lockdep_unregister_key() is to wait for
all is_dynamic_key() callers to finish so that removing a key from the
key hashlist, and we can use shazptr to protect the hashlist as well.

Compared to the proposed solution which replaces synchronize_rcu() with
synchronize_rcu_expedited(), using shazptr here can achieve the
same/better synchronization time without the need to send IPI. Hence use
shazptr here.

Reported-by: Erik Lundgren <elundgren@meta.com>
Reported-by: Breno Leitao <leitao@debian.org>
Link: https://lore.kernel.org/lkml/20250321-lockdep-v1-1-78b732d195fb@debian.org/
Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 kernel/locking/lockdep.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 58d78a33ac65..c5781d2dc8c6 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -58,6 +58,7 @@
 #include <linux/context_tracking.h>
 #include <linux/console.h>
 #include <linux/kasan.h>
+#include <linux/shazptr.h>
 
 #include <asm/sections.h>
 
@@ -1265,14 +1266,18 @@ static bool is_dynamic_key(const struct lock_class_key *key)
 
 	hash_head = keyhashentry(key);
 
-	rcu_read_lock();
+	/* Need preemption disable for using shazptr. */
+	guard(preempt)();
+
+	/* Protect the list search with shazptr. */
+	guard(shazptr)(hash_head);
+
 	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
 		if (k == key) {
 			found = true;
 			break;
 		}
 	}
-	rcu_read_unlock();
 
 	return found;
 }
@@ -6614,7 +6619,7 @@ void lockdep_unregister_key(struct lock_class_key *key)
 		call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
 
 	/* Wait until is_dynamic_key() has finished accessing k->hash_entry. */
-	synchronize_rcu();
+	synchronize_shazptr(keyhashentry(key));
 }
 EXPORT_SYMBOL_GPL(lockdep_unregister_key);
 
-- 
2.47.1

Re: [RFC PATCH 0/8] Introduce simple hazard pointers for lockdep

[Breno Leitao]

Hi Boqun,

On Sun, Apr 13, 2025 at 11:00:47PM -0700, Boqun Feng wrote:

> Overall it looks promising to me, but I would like to see how it
> performs in the environment of Breno. Also as Paul always reminds me:
> buggy code usually run faster, so please take a look in case I'm missing
> something ;-) Thanks!

Thanks for the patchset. I've confirmed that the wins are large on my
environment, but, at the same magnitute of synchronize_rcu_expedited().

Here are the numbers I got:

	6.15-rc1 (upstream)
		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
		real	0m3.986s
		user	0m0.001s
		sys	0m0.093s

	Your patchset on top of 6.15-rc1
		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
		real	0m0.072s
		user	0m0.001s
		sys	0m0.070s


	My original proposal of using synchronize_rcu_expedited()[1]
		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
		real	0m0.074s
		user	0m0.001s
		sys	0m0.061s

Link: https://lore.kernel.org/all/20250321-lockdep-v1-1-78b732d195fb@debian.org/ [1]

Thanks for working on it,
--breno

Re: [RFC PATCH 0/8] Introduce simple hazard pointers for lockdep

[Uladzislau Rezki]

On Wed, Apr 16, 2025 at 07:14:04AM -0700, Breno Leitao wrote:
> Hi Boqun,
> 
> On Sun, Apr 13, 2025 at 11:00:47PM -0700, Boqun Feng wrote:
> 
> > Overall it looks promising to me, but I would like to see how it
> > performs in the environment of Breno. Also as Paul always reminds me:
> > buggy code usually run faster, so please take a look in case I'm missing
> > something ;-) Thanks!
> 
> Thanks for the patchset. I've confirmed that the wins are large on my
> environment, but, at the same magnitute of synchronize_rcu_expedited().
> 
> Here are the numbers I got:
> 
> 	6.15-rc1 (upstream)
> 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> 		real	0m3.986s
> 		user	0m0.001s
> 		sys	0m0.093s
> 
> 	Your patchset on top of 6.15-rc1
> 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> 		real	0m0.072s
> 		user	0m0.001s
> 		sys	0m0.070s
> 
> 
> 	My original proposal of using synchronize_rcu_expedited()[1]
> 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> 		real	0m0.074s
> 		user	0m0.001s
> 		sys	0m0.061s
> 
> Link: https://lore.kernel.org/all/20250321-lockdep-v1-1-78b732d195fb@debian.org/ [1]
> 
Could you please also do the test of fist scenario with a regular
synchronize_rcu() but switch to its faster variant:

echo 1 > /sys/module/rcutree/parameters/rcu_normal_wake_from_gp

and run the test. If you have a time.

Thank you!

--
Vlad Rezki

Re: [RFC PATCH 0/8] Introduce simple hazard pointers for lockdep

[Breno Leitao]

Hello Vlad,

On Wed, Apr 16, 2025 at 05:04:31PM +0200, Uladzislau Rezki wrote:
> On Wed, Apr 16, 2025 at 07:14:04AM -0700, Breno Leitao wrote:
> > Hi Boqun,
> > 
> > On Sun, Apr 13, 2025 at 11:00:47PM -0700, Boqun Feng wrote:
> > 
> > > Overall it looks promising to me, but I would like to see how it
> > > performs in the environment of Breno. Also as Paul always reminds me:
> > > buggy code usually run faster, so please take a look in case I'm missing
> > > something ;-) Thanks!
> > 
> > Thanks for the patchset. I've confirmed that the wins are large on my
> > environment, but, at the same magnitute of synchronize_rcu_expedited().
> > 
> > Here are the numbers I got:
> > 
> > 	6.15-rc1 (upstream)
> > 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> > 		real	0m3.986s
> > 		user	0m0.001s
> > 		sys	0m0.093s
> > 
> > 	Your patchset on top of 6.15-rc1
> > 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> > 		real	0m0.072s
> > 		user	0m0.001s
> > 		sys	0m0.070s
> > 
> > 
> > 	My original proposal of using synchronize_rcu_expedited()[1]
> > 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> > 		real	0m0.074s
> > 		user	0m0.001s
> > 		sys	0m0.061s
> > 
> > Link: https://lore.kernel.org/all/20250321-lockdep-v1-1-78b732d195fb@debian.org/ [1]
> > 
> Could you please also do the test of fist scenario with a regular
> synchronize_rcu() but switch to its faster variant:
> 
> echo 1 > /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
> 
> and run the test. If you have a time.

Of course, I am more than interesting in this topic. This is what I run:


	# /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq; time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
	real	0m4.150s
	user	0m0.001s
	sys	0m0.076s

	[root@host2 ~]# echo 1 > /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
	[root@host2 ~]# /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq; time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
	real	0m4.225s
	user	0m0.000s
	sys	0m0.106s

	[root@host2 ~]# cat /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
	1
	[root@host2 ~]# echo 0 > /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
	[root@host2 ~]# /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq; time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
	real	0m4.152s
	user	0m0.001s
	sys	0m0.099s

It seems it made very little difference?

Thanks
--breno

Re: [RFC PATCH 0/8] Introduce simple hazard pointers for lockdep

[Uladzislau Rezki]

Hello, Breno!

> Hello Vlad,
> 
> On Wed, Apr 16, 2025 at 05:04:31PM +0200, Uladzislau Rezki wrote:
> > On Wed, Apr 16, 2025 at 07:14:04AM -0700, Breno Leitao wrote:
> > > Hi Boqun,
> > > 
> > > On Sun, Apr 13, 2025 at 11:00:47PM -0700, Boqun Feng wrote:
> > > 
> > > > Overall it looks promising to me, but I would like to see how it
> > > > performs in the environment of Breno. Also as Paul always reminds me:
> > > > buggy code usually run faster, so please take a look in case I'm missing
> > > > something ;-) Thanks!
> > > 
> > > Thanks for the patchset. I've confirmed that the wins are large on my
> > > environment, but, at the same magnitute of synchronize_rcu_expedited().
> > > 
> > > Here are the numbers I got:
> > > 
> > > 	6.15-rc1 (upstream)
> > > 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> > > 		real	0m3.986s
> > > 		user	0m0.001s
> > > 		sys	0m0.093s
> > > 
> > > 	Your patchset on top of 6.15-rc1
> > > 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> > > 		real	0m0.072s
> > > 		user	0m0.001s
> > > 		sys	0m0.070s
> > > 
> > > 
> > > 	My original proposal of using synchronize_rcu_expedited()[1]
> > > 		# time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> > > 		real	0m0.074s
> > > 		user	0m0.001s
> > > 		sys	0m0.061s
> > > 
> > > Link: https://lore.kernel.org/all/20250321-lockdep-v1-1-78b732d195fb@debian.org/ [1]
> > > 
> > Could you please also do the test of fist scenario with a regular
> > synchronize_rcu() but switch to its faster variant:
> > 
> > echo 1 > /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
> > 
> > and run the test. If you have a time.
> 
> Of course, I am more than interesting in this topic. This is what I run:
> 
> 
> 	# /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq; time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> 	real	0m4.150s
> 	user	0m0.001s
> 	sys	0m0.076s
> 
> 	[root@host2 ~]# echo 1 > /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
> 	[root@host2 ~]# /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq; time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> 	real	0m4.225s
> 	user	0m0.000s
> 	sys	0m0.106s
> 
> 	[root@host2 ~]# cat /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
> 	1
> 	[root@host2 ~]# echo 0 > /sys/module/rcutree/parameters/rcu_normal_wake_from_gp
> 	[root@host2 ~]# /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq; time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
> 	real	0m4.152s
> 	user	0m0.001s
> 	sys	0m0.099s
> 
> It seems it made very little difference?
> 
Yep, no difference. In your case you just need to speed up a grace
period completion. So an expedited version really improves your case.

So you do not have a lot of callbacks which may delay a normal GP.

Thank you!

--
Uladzislau Rezki

Re: [RFC PATCH 1/8] Introduce simple hazard pointers

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:48PM -0700, Boqun Feng wrote:
> As its name suggests, simple hazard pointers (shazptr) is a
> simplification of hazard pointers [1]: it has only one hazard pointer
> slot per-CPU and is targeted for simple use cases where the read-side
> already has preemption disabled. It's a trade-off between full features
> of a normal hazard pointer implementation (multiple slots, dynamic slot
> allocation, etc.) and the simple use scenario.
> 
> Since there's only one slot per-CPU, so shazptr read-side critical
> section nesting is a problem that needs to be resolved, because at very
> least, interrupts and NMI can introduce nested shazptr read-side
> critical sections. A SHAZPTR_WILDCARD is introduced to resolve this:
> SHAZPTR_WILDCARD is a special address value that blocks *all* shazptr
> waiters. In an interrupt-causing shazptr read-side critical section
> nesting case (i.e. an interrupt happens while the per-CPU hazard pointer
> slot being used and tries to acquire a hazard pointer itself), the inner
> critical section will switch the value of the hazard pointer slot into
> SHAZPTR_WILDCARD, and let the outer critical section eventually zero the
> slot. The SHAZPTR_WILDCARD still provide the correct protection because
> it blocks all the waiters.
> 
> It's true that once the wildcard mechanism is activated, shazptr
> mechanism may be downgrade to something similar to RCU (and probably
> with a worse implementation), which generally has longer wait time and
> larger memory footprint compared to a typical hazard pointer
> implementation. However, that can only happen with a lot of users using
> hazard pointers, and then it's reasonable to introduce the
> fully-featured hazard pointer implementation [2] and switch users to it.
> 
> Note that shazptr_protect() may be added later, the current potential
> usage doesn't require it, and a shazptr_acquire(), which installs the
> protected value to hazard pointer slot and proves the smp_mb(), is
> enough for now.
> 
> [1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
>      lock-free objects," in IEEE Transactions on Parallel and
>      Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004
> 
> Link: https://lore.kernel.org/lkml/20240917143402.930114-1-boqun.feng@gmail.com/ [2]
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

That smp_cond_load_acquire() in synchronize_hazptr() will become
painful at some point, but when that situation arises, we will have the
information required to adjust as appropriate.

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  include/linux/shazptr.h  | 73 ++++++++++++++++++++++++++++++++++++++++
>  kernel/locking/Makefile  |  2 +-
>  kernel/locking/shazptr.c | 29 ++++++++++++++++
>  3 files changed, 103 insertions(+), 1 deletion(-)
>  create mode 100644 include/linux/shazptr.h
>  create mode 100644 kernel/locking/shazptr.c
> 
> diff --git a/include/linux/shazptr.h b/include/linux/shazptr.h
> new file mode 100644
> index 000000000000..287cd04b4be9
> --- /dev/null
> +++ b/include/linux/shazptr.h
> @@ -0,0 +1,73 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +/*
> + * Simple hazard pointers
> + *
> + * Copyright (c) 2025, Microsoft Corporation.
> + *
> + * Author: Boqun Feng <boqun.feng@gmail.com>
> + *
> + * A simple variant of hazard pointers, the users must ensure the preemption
> + * is already disabled when calling a shazptr_acquire() to protect an address.
> + * If one shazptr_acquire() is called after another shazptr_acquire() has been
> + * called without the corresponding shazptr_clear() has been called, the later
> + * shazptr_acquire() must be cleared first.
> + *
> + * The most suitable usage is when only one address need to be protected in a
> + * preemption disabled critical section.
> + */
> +
> +#ifndef _LINUX_SHAZPTR_H
> +#define _LINUX_SHAZPTR_H
> +
> +#include <linux/cleanup.h>
> +#include <linux/percpu.h>
> +
> +/* Make ULONG_MAX the wildcard value */
> +#define SHAZPTR_WILDCARD ((void *)(ULONG_MAX))
> +
> +DECLARE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
> +
> +/* Represent a held hazard pointer slot */
> +struct shazptr_guard {
> +	void **slot;
> +	bool use_wildcard;
> +};
> +
> +/*
> + * Acquire a hazptr slot and begin the hazard pointer critical section.
> + *
> + * Must be called with preemption disabled, and preemption must remain disabled
> + * until shazptr_clear().
> + */
> +static inline struct shazptr_guard shazptr_acquire(void *ptr)
> +{
> +	struct shazptr_guard guard = {
> +		/* Preemption is disabled. */
> +		.slot = this_cpu_ptr(&shazptr_slots),
> +		.use_wildcard = false,
> +	};
> +
> +	if (likely(!READ_ONCE(*guard.slot))) {
> +		WRITE_ONCE(*guard.slot, ptr);
> +	} else {
> +		guard.use_wildcard = true;
> +		WRITE_ONCE(*guard.slot, SHAZPTR_WILDCARD);
> +	}
> +
> +	smp_mb(); /* Synchronize with smp_mb() at synchronize_shazptr(). */
> +
> +	return guard;
> +}
> +
> +static inline void shazptr_clear(struct shazptr_guard guard)
> +{
> +	/* Only clear the slot when the outermost guard is released */
> +	if (likely(!guard.use_wildcard))
> +		smp_store_release(guard.slot, NULL); /* Pair with ACQUIRE at synchronize_shazptr() */
> +}
> +
> +void synchronize_shazptr(void *ptr);
> +
> +DEFINE_CLASS(shazptr, struct shazptr_guard, shazptr_clear(_T),
> +	     shazptr_acquire(ptr), void *ptr);
> +#endif
> diff --git a/kernel/locking/Makefile b/kernel/locking/Makefile
> index a114949eeed5..1517076c98ec 100644
> --- a/kernel/locking/Makefile
> +++ b/kernel/locking/Makefile
> @@ -3,7 +3,7 @@
>  # and is generally not a function of system call inputs.
>  KCOV_INSTRUMENT		:= n
>  
> -obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o
> +obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o shazptr.o
>  
>  # Avoid recursion lockdep -> sanitizer -> ... -> lockdep & improve performance.
>  KASAN_SANITIZE_lockdep.o := n
> diff --git a/kernel/locking/shazptr.c b/kernel/locking/shazptr.c
> new file mode 100644
> index 000000000000..991fd1a05cfd
> --- /dev/null
> +++ b/kernel/locking/shazptr.c
> @@ -0,0 +1,29 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +/*
> + * Simple hazard pointers
> + *
> + * Copyright (c) 2025, Microsoft Corporation.
> + *
> + * Author: Boqun Feng <boqun.feng@gmail.com>
> + */
> +
> +#include <linux/atomic.h>
> +#include <linux/cpumask.h>
> +#include <linux/shazptr.h>
> +
> +DEFINE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
> +EXPORT_PER_CPU_SYMBOL_GPL(shazptr_slots);
> +
> +void synchronize_shazptr(void *ptr)
> +{
> +	int cpu;
> +
> +	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
> +	for_each_possible_cpu(cpu) {
> +		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> +		/* Pair with smp_store_release() in shazptr_clear(). */
> +		smp_cond_load_acquire(slot,
> +				      VAL != ptr && VAL != SHAZPTR_WILDCARD);
> +	}
> +}
> +EXPORT_SYMBOL_GPL(synchronize_shazptr);
> -- 
> 2.47.1
> 

Re: [RFC PATCH 2/8] shazptr: Add refscale test

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:49PM -0700, Boqun Feng wrote:
> Add the refscale test for shazptr to measure the reader side
> performance.
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

One nit below, but with or without that changed:

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  kernel/rcu/refscale.c | 39 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 39 insertions(+)
> 
> diff --git a/kernel/rcu/refscale.c b/kernel/rcu/refscale.c
> index f11a7c2af778..154520e4ee4c 100644
> --- a/kernel/rcu/refscale.c
> +++ b/kernel/rcu/refscale.c
> @@ -29,6 +29,7 @@
>  #include <linux/reboot.h>
>  #include <linux/sched.h>
>  #include <linux/seq_buf.h>
> +#include <linux/shazptr.h>
>  #include <linux/spinlock.h>
>  #include <linux/smp.h>
>  #include <linux/stat.h>
> @@ -890,6 +891,43 @@ static const struct ref_scale_ops typesafe_seqlock_ops = {
>  	.name		= "typesafe_seqlock"
>  };
>  
> +static void ref_shazptr_read_section(const int nloops)
> +{
> +	int i;
> +
> +	for (i = nloops; i >= 0; i--) {
> +		preempt_disable();
> +		{ guard(shazptr)(ref_shazptr_read_section); }
> +		preempt_enable();
> +	}
> +}
> +
> +static void ref_shazptr_delay_section(const int nloops, const int udl, const int ndl)
> +{
> +	int i;
> +
> +	for (i = nloops; i >= 0; i--) {
> +		preempt_disable();
> +		{
> +			guard(shazptr)(ref_shazptr_delay_section);
> +			un_delay(udl, ndl);
> +		}
> +		preempt_enable();
> +	}
> +}
> +
> +static bool ref_shazptr_init(void)
> +{
> +	return true;
> +}
> +
> +static const struct ref_scale_ops shazptr_ops = {
> +	.init		= ref_shazptr_init,

You could make this NULL and drop the ref_shazptr_init() function.
As in drop the above .init= initialization along with that function.

Of course, the same is true of the existing rcu_sync_scale_init()
function, so I cannot fault you here.  ;-)

> +	.readsection	= ref_shazptr_read_section,
> +	.delaysection	= ref_shazptr_delay_section,
> +	.name		= "shazptr"
> +};
> +
>  static void rcu_scale_one_reader(void)
>  {
>  	if (readdelay <= 0)
> @@ -1197,6 +1235,7 @@ ref_scale_init(void)
>  		&refcnt_ops, &rwlock_ops, &rwsem_ops, &lock_ops, &lock_irq_ops,
>  		&acqrel_ops, &sched_clock_ops, &clock_ops, &jiffies_ops,
>  		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops,
> +		&shazptr_ops,
>  	};
>  
>  	if (!torture_init_begin(scale_type, verbose))
> -- 
> 2.47.1
> 

Re: [RFC PATCH 3/8] shazptr: Add refscale test for wildcard

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:50PM -0700, Boqun Feng wrote:
> Add the refscale test for shazptr, which starts another shazptr critical
> section inside an existing one to measure the reader side performance
> when wildcard logic is triggered.
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

With or without the same ref_shazptr_init() fix as the preview patch:

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  kernel/rcu/refscale.c | 40 +++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 39 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/rcu/refscale.c b/kernel/rcu/refscale.c
> index 154520e4ee4c..fdbb4a2c91fe 100644
> --- a/kernel/rcu/refscale.c
> +++ b/kernel/rcu/refscale.c
> @@ -928,6 +928,44 @@ static const struct ref_scale_ops shazptr_ops = {
>  	.name		= "shazptr"
>  };
>  
> +static void ref_shazptr_wc_read_section(const int nloops)
> +{
> +	int i;
> +
> +	for (i = nloops; i >= 0; i--) {
> +		preempt_disable();
> +		{
> +			guard(shazptr)(ref_shazptr_read_section);
> +			/* Trigger wildcard logic */
> +			guard(shazptr)(ref_shazptr_wc_read_section);
> +		}
> +		preempt_enable();
> +	}
> +}
> +
> +static void ref_shazptr_wc_delay_section(const int nloops, const int udl, const int ndl)
> +{
> +	int i;
> +
> +	for (i = nloops; i >= 0; i--) {
> +		preempt_disable();
> +		{
> +			guard(shazptr)(ref_shazptr_delay_section);
> +			/* Trigger wildcard logic */
> +			guard(shazptr)(ref_shazptr_wc_delay_section);
> +			un_delay(udl, ndl);
> +		}
> +		preempt_enable();
> +	}
> +}
> +
> +static const struct ref_scale_ops shazptr_wildcard_ops = {
> +	.init		= ref_shazptr_init,
> +	.readsection	= ref_shazptr_wc_read_section,
> +	.delaysection	= ref_shazptr_wc_delay_section,
> +	.name		= "shazptr_wildcard"
> +};
> +
>  static void rcu_scale_one_reader(void)
>  {
>  	if (readdelay <= 0)
> @@ -1235,7 +1273,7 @@ ref_scale_init(void)
>  		&refcnt_ops, &rwlock_ops, &rwsem_ops, &lock_ops, &lock_irq_ops,
>  		&acqrel_ops, &sched_clock_ops, &clock_ops, &jiffies_ops,
>  		&typesafe_ref_ops, &typesafe_lock_ops, &typesafe_seqlock_ops,
> -		&shazptr_ops,
> +		&shazptr_ops, &shazptr_wildcard_ops,
>  	};
>  
>  	if (!torture_init_begin(scale_type, verbose))
> -- 
> 2.47.1
> 

Re: [RFC PATCH 4/8] shazptr: Avoid synchronize_shaptr() busy waiting

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:51PM -0700, Boqun Feng wrote:
> For a general purpose hazard pointers implemenation, always busy waiting
> is not an option. It may benefit some special workload, but overall it
> hurts the system performance when more and more users begin to call
> synchronize_shazptr(). Therefore avoid busy waiting for hazard pointer
> slots changes by using a scan kthread, and each synchronize_shazptr()
> queues themselves if a quick scan shows they are blocked by some slots.
> 
> A simple optimization is done inside the scan: each
> synchronize_shazptr() tracks which CPUs (or CPU groups if nr_cpu_ids >
> BITS_PER_LONG) are blocking it and the scan function updates this
> information for each synchronize_shazptr() (via shazptr_wait)
> individually. In this way, synchronize_shazptr() doesn't need to wait
> until a scan result showing all slots are not blocking (as long as the
> scan has observed each slot has changed into non-block state once).
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

OK, so this patch addresses the aforementioned pain.  ;-)

One question below, might be worth a comment beyond the second paragraph
of the commit log.  Nevertheless:

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  kernel/locking/shazptr.c | 277 ++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 276 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/locking/shazptr.c b/kernel/locking/shazptr.c
> index 991fd1a05cfd..a8559cb559f8 100644
> --- a/kernel/locking/shazptr.c
> +++ b/kernel/locking/shazptr.c
> @@ -7,18 +7,243 @@
>   * Author: Boqun Feng <boqun.feng@gmail.com>
>   */
>  
> +#define pr_fmt(fmt) "shazptr: " fmt
> +
>  #include <linux/atomic.h>
>  #include <linux/cpumask.h>
> +#include <linux/completion.h>
> +#include <linux/kthread.h>
> +#include <linux/list.h>
> +#include <linux/mutex.h>
>  #include <linux/shazptr.h>
> +#include <linux/slab.h>
> +#include <linux/sort.h>
>  
>  DEFINE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
>  EXPORT_PER_CPU_SYMBOL_GPL(shazptr_slots);
>  
> -void synchronize_shazptr(void *ptr)
> +/* Wait structure for synchronize_shazptr(). */
> +struct shazptr_wait {
> +	struct list_head list;
> +	/* Which groups of CPUs are blocking. */
> +	unsigned long blocking_grp_mask;
> +	void *ptr;
> +	struct completion done;
> +};
> +
> +/* Snapshot for hazptr slot. */
> +struct shazptr_snapshot {
> +	unsigned long ptr;
> +	unsigned long grp_mask;

The point of ->grp_mask is to avoid being fooled by CPUs that assert the
wildcard after having been found not to be holding a hazard pointer on
the current object?  And to avoid being delayed by CPUs that picked up
a pointer, were preempted/interrupted for a long time, then do a doomed
store into their hazard pointer?  Or is there something else subtle
that I am missing that somehow allows a given object to reappear in a
hazard pointer?

> +};
> +
> +static inline int
> +shazptr_snapshot_cmp(const void *a, const void *b)
> +{
> +	const struct shazptr_snapshot *snap_a = (struct shazptr_snapshot *)a;
> +	const struct shazptr_snapshot *snap_b = (struct shazptr_snapshot *)b;
> +
> +	if (snap_a->ptr > snap_b->ptr)
> +		return 1;
> +	else if (snap_a->ptr < snap_b->ptr)
> +		return -1;
> +	else
> +		return 0;
> +}
> +
> +/* *In-place* merge @n together based on ->ptr and accumulate the >grp_mask. */
> +static int shazptr_snapshot_merge(struct shazptr_snapshot *snaps, int n)
> +{
> +	int new, i;
> +
> +	/* Sort first. */
> +	sort(snaps, n, sizeof(*snaps), shazptr_snapshot_cmp, NULL);
> +
> +	new = 0;
> +
> +	/* Skip NULLs. */
> +	for (i = 0; i < n; i++) {
> +		if (snaps[i].ptr)
> +			break;
> +	}
> +
> +	while (i < n) {
> +		/* Start with a new address. */
> +		snaps[new] = snaps[i];
> +
> +		for (; i < n; i++) {
> +			/* Merge if the next one has the same address. */
> +			if (snaps[new].ptr == snaps[i].ptr) {
> +				snaps[new].grp_mask |= snaps[i].grp_mask;
> +			} else
> +				break;
> +		}
> +
> +		/*
> +		 * Either the end has been reached or need to start with a new
> +		 * record.
> +		 */
> +		new++;
> +	}
> +
> +	return new;
> +}
> +
> +/*
> + * Calculate which group is still blocking @ptr, this assumes the @snaps is
> + * already merged.
> + */
> +static unsigned long
> +shazptr_snapshot_blocking_grp_mask(struct shazptr_snapshot *snaps,
> +				   int n, void *ptr)
> +{
> +	unsigned long mask = 0;
> +
> +	if (!n)
> +		return mask;
> +	else if (snaps[n-1].ptr == (unsigned long)SHAZPTR_WILDCARD) {
> +		/*
> +		 * Take SHAZPTR_WILDCARD slots, which is ULONG_MAX, into
> +		 * consideration if any.
> +		 */
> +		mask = snaps[n-1].grp_mask;
> +	}
> +
> +	/* TODO: binary search if n is big. */
> +	for (int i = 0; i < n; i++) {
> +		if (snaps[i].ptr == (unsigned long)ptr) {
> +			mask |= snaps[i].grp_mask;
> +			break;
> +		}
> +	}
> +
> +	return mask;
> +}
> +
> +/* Scan structure for synchronize_shazptr(). */
> +struct shazptr_scan {
> +	/* The scan kthread */
> +	struct task_struct *thread;
> +
> +	/* Wait queue for the scan kthread */
> +	struct swait_queue_head wq;
> +
> +	/* Whether the scan kthread has been scheduled to scan */
> +	bool scheduled;
> +
> +	/* The lock protecting ->queued and ->scheduled */
> +	struct mutex lock;
> +
> +	/* List of queued synchronize_shazptr() request. */
> +	struct list_head queued;
> +
> +	int cpu_grp_size;
> +
> +	/* List of scanning synchronize_shazptr() request. */
> +	struct list_head scanning;
> +
> +	/* Buffer used for hazptr slot scan, nr_cpu_ids slots*/
> +	struct shazptr_snapshot* snaps;
> +};
> +
> +static struct shazptr_scan shazptr_scan;
> +
> +static void shazptr_do_scan(struct shazptr_scan *scan)
> +{
> +	int cpu;
> +	int snaps_len;
> +	struct shazptr_wait *curr, *next;
> +
> +	scoped_guard(mutex, &scan->lock) {
> +		/* Move from ->queued to ->scanning. */
> +		list_splice_tail_init(&scan->queued, &scan->scanning);
> +	}
> +
> +	memset(scan->snaps, nr_cpu_ids, sizeof(struct shazptr_snapshot));
> +
> +	for_each_possible_cpu(cpu) {
> +		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> +		void *val;
> +
> +		/* Pair with smp_store_release() in shazptr_clear(). */
> +		val = smp_load_acquire(slot);
> +
> +		scan->snaps[cpu].ptr = (unsigned long)val;
> +		scan->snaps[cpu].grp_mask = 1UL << (cpu / scan->cpu_grp_size);
> +	}
> +
> +	snaps_len = shazptr_snapshot_merge(scan->snaps, nr_cpu_ids);
> +
> +	/* Only one thread can access ->scanning, so can be lockless. */
> +	list_for_each_entry_safe(curr, next, &scan->scanning, list) {
> +		/* Accumulate the shazptr slot scan result. */
> +		curr->blocking_grp_mask &=
> +			shazptr_snapshot_blocking_grp_mask(scan->snaps,
> +							   snaps_len,
> +							   curr->ptr);
> +
> +		if (curr->blocking_grp_mask == 0) {
> +			/* All shots are observed as not blocking once. */
> +			list_del(&curr->list);
> +			complete(&curr->done);
> +		}
> +	}
> +}
> +
> +static int __noreturn shazptr_scan_kthread(void *unused)
> +{
> +	for (;;) {
> +		swait_event_idle_exclusive(shazptr_scan.wq,
> +					   READ_ONCE(shazptr_scan.scheduled));
> +
> +		shazptr_do_scan(&shazptr_scan);
> +
> +		scoped_guard(mutex, &shazptr_scan.lock) {
> +			if (list_empty(&shazptr_scan.queued) &&
> +			    list_empty(&shazptr_scan.scanning))
> +				shazptr_scan.scheduled = false;
> +		}
> +	}
> +}
> +
> +static int __init shazptr_scan_init(void)
> +{
> +	struct shazptr_scan *scan = &shazptr_scan;
> +	struct task_struct *t;
> +
> +	init_swait_queue_head(&scan->wq);
> +	mutex_init(&scan->lock);
> +	INIT_LIST_HEAD(&scan->queued);
> +	INIT_LIST_HEAD(&scan->scanning);
> +	scan->scheduled = false;
> +
> +	/* Group CPUs into at most BITS_PER_LONG groups. */
> +	scan->cpu_grp_size = DIV_ROUND_UP(nr_cpu_ids, BITS_PER_LONG);
> +
> +	scan->snaps = kcalloc(nr_cpu_ids, sizeof(scan->snaps[0]), GFP_KERNEL);
> +
> +	if (scan->snaps) {
> +		t = kthread_run(shazptr_scan_kthread, NULL, "shazptr_scan");
> +		if (!IS_ERR(t)) {
> +			smp_store_release(&scan->thread, t);
> +			/* Kthread creation succeeds */
> +			return 0;
> +		} else {
> +			kfree(scan->snaps);
> +		}
> +	}
> +
> +	pr_info("Failed to create the scan thread, only busy waits\n");
> +	return 0;
> +}
> +core_initcall(shazptr_scan_init);
> +
> +static void synchronize_shazptr_busywait(void *ptr)
>  {
>  	int cpu;
>  
>  	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
> +
>  	for_each_possible_cpu(cpu) {
>  		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
>  		/* Pair with smp_store_release() in shazptr_clear(). */
> @@ -26,4 +251,54 @@ void synchronize_shazptr(void *ptr)
>  				      VAL != ptr && VAL != SHAZPTR_WILDCARD);
>  	}
>  }
> +
> +static void synchronize_shazptr_normal(void *ptr)
> +{
> +	int cpu;
> +	unsigned long blocking_grp_mask = 0;
> +
> +	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
> +
> +	for_each_possible_cpu(cpu) {
> +		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> +		void *val;
> +
> +		/* Pair with smp_store_release() in shazptr_clear(). */
> +		val = smp_load_acquire(slot);
> +
> +		if (val == ptr || val == SHAZPTR_WILDCARD)
> +			blocking_grp_mask |= 1UL << (cpu / shazptr_scan.cpu_grp_size);
> +	}
> +
> +	/* Found blocking slots, prepare to wait. */
> +	if (blocking_grp_mask) {
> +		struct shazptr_scan *scan = &shazptr_scan;
> +		struct shazptr_wait wait = {
> +			.blocking_grp_mask = blocking_grp_mask,
> +		};
> +
> +		INIT_LIST_HEAD(&wait.list);
> +		init_completion(&wait.done);
> +
> +		scoped_guard(mutex, &scan->lock) {
> +			list_add_tail(&wait.list, &scan->queued);
> +
> +			if (!scan->scheduled) {
> +				WRITE_ONCE(scan->scheduled, true);
> +				swake_up_one(&shazptr_scan.wq);
> +			}
> +		}
> +
> +		wait_for_completion(&wait.done);
> +	}
> +}
> +
> +void synchronize_shazptr(void *ptr)
> +{
> +	/* Busy waiting if the scan kthread has not been created. */
> +	if (!smp_load_acquire(&shazptr_scan.thread))
> +		synchronize_shazptr_busywait(ptr);
> +	else
> +		synchronize_shazptr_normal(ptr);
> +}
>  EXPORT_SYMBOL_GPL(synchronize_shazptr);
> -- 
> 2.47.1
> 

Re: [RFC PATCH 5/8] shazptr: Allow skip self scan in synchronize_shaptr()

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:52PM -0700, Boqun Feng wrote:
> Add a module parameter for shazptr to allow skip the self scan in
> synchronize_shaptr(). This can force every synchronize_shaptr() to use
> shazptr scan kthread, and help testing the shazptr scan kthread.
> 
> Another reason users may want to set this paramter is to reduce the self
> scan CPU cost in synchronize_shaptr().
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

One nit below, but nevertheless:

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  kernel/locking/shazptr.c | 28 +++++++++++++++++++++-------
>  1 file changed, 21 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/locking/shazptr.c b/kernel/locking/shazptr.c
> index a8559cb559f8..b3f7e8390eb2 100644
> --- a/kernel/locking/shazptr.c
> +++ b/kernel/locking/shazptr.c
> @@ -14,11 +14,17 @@
>  #include <linux/completion.h>
>  #include <linux/kthread.h>
>  #include <linux/list.h>
> +#include <linux/moduleparam.h>
>  #include <linux/mutex.h>
>  #include <linux/shazptr.h>
>  #include <linux/slab.h>
>  #include <linux/sort.h>
>  
> +#ifdef MODULE_PARAM_PREFIX
> +#undef MODULE_PARAM_PREFIX
> +#endif
> +#define MODULE_PARAM_PREFIX "shazptr."

I do not believe that you need this when the desired MODULE_PARAM_PREFIX
matches the name of the file, as it does in this case.  For example,
kernel/rcu/tree.c needs this to get the "rcutree." prefix, but
kernel/rcu/refscale.c can do without it.

> +
>  DEFINE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
>  EXPORT_PER_CPU_SYMBOL_GPL(shazptr_slots);
>  
> @@ -252,6 +258,10 @@ static void synchronize_shazptr_busywait(void *ptr)
>  	}
>  }
>  
> +/* Disabled by default. */
> +static int skip_synchronize_self_scan;
> +module_param(skip_synchronize_self_scan, int, 0644);
> +
>  static void synchronize_shazptr_normal(void *ptr)
>  {
>  	int cpu;
> @@ -259,15 +269,19 @@ static void synchronize_shazptr_normal(void *ptr)
>  
>  	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
>  
> -	for_each_possible_cpu(cpu) {
> -		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> -		void *val;
> +	if (unlikely(skip_synchronize_self_scan)) {
> +		blocking_grp_mask = ~0UL;
> +	} else {
> +		for_each_possible_cpu(cpu) {
> +			void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> +			void *val;
>  
> -		/* Pair with smp_store_release() in shazptr_clear(). */
> -		val = smp_load_acquire(slot);
> +			/* Pair with smp_store_release() in shazptr_clear(). */
> +			val = smp_load_acquire(slot);
>  
> -		if (val == ptr || val == SHAZPTR_WILDCARD)
> -			blocking_grp_mask |= 1UL << (cpu / shazptr_scan.cpu_grp_size);
> +			if (val == ptr || val == SHAZPTR_WILDCARD)
> +				blocking_grp_mask |= 1UL << (cpu / shazptr_scan.cpu_grp_size);
> +		}
>  	}
>  
>  	/* Found blocking slots, prepare to wait. */
> -- 
> 2.47.1
> 

Re: [RFC PATCH 6/8] rcuscale: Allow rcu_scale_ops::get_gp_seq to be NULL

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:53PM -0700, Boqun Feng wrote:
> For synchronization mechanisms similar to RCU, there could be no "grace
> period" concept (e.g. hazard pointers), therefore allow
> rcu_scale_ops::get_gp_seq to be a NULL pointer for these cases, and
> simply treat started and finished grace period as 0.
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  kernel/rcu/rcuscale.c | 8 ++++++--
>  1 file changed, 6 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/rcu/rcuscale.c b/kernel/rcu/rcuscale.c
> index 0f3059b1b80d..d9bff4b1928b 100644
> --- a/kernel/rcu/rcuscale.c
> +++ b/kernel/rcu/rcuscale.c
> @@ -568,8 +568,10 @@ rcu_scale_writer(void *arg)
>  		if (gp_exp) {
>  			b_rcu_gp_test_started =
>  				cur_ops->exp_completed() / 2;
> -		} else {
> +		} else if (cur_ops->get_gp_seq) {
>  			b_rcu_gp_test_started = cur_ops->get_gp_seq();
> +		} else {
> +			b_rcu_gp_test_started = 0;
>  		}
>  	}
>  
> @@ -625,9 +627,11 @@ rcu_scale_writer(void *arg)
>  				if (gp_exp) {
>  					b_rcu_gp_test_finished =
>  						cur_ops->exp_completed() / 2;
> -				} else {
> +				} else if (cur_ops->get_gp_seq) {
>  					b_rcu_gp_test_finished =
>  						cur_ops->get_gp_seq();
> +				} else {
> +					b_rcu_gp_test_finished = 0;
>  				}
>  				if (shutdown) {
>  					smp_mb(); /* Assign before wake. */
> -- 
> 2.47.1
> 

Re: [RFC PATCH 7/8] rcuscale: Add tests for simple hazard pointers

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:54PM -0700, Boqun Feng wrote:
> Add two rcu_scale_ops to include tests from simple hazard pointers
> (shazptr). One is with evenly distributed readers, and the other is with
> all WILDCARD readers. This could show the best and worst case scenarios
> for the synchronization time of simple hazard pointers.
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

Cute trick using the CPU number plus one as a stand-in for a pointer.  ;-)

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  kernel/rcu/rcuscale.c | 52 ++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 51 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/rcu/rcuscale.c b/kernel/rcu/rcuscale.c
> index d9bff4b1928b..cab42bcc1d26 100644
> --- a/kernel/rcu/rcuscale.c
> +++ b/kernel/rcu/rcuscale.c
> @@ -32,6 +32,7 @@
>  #include <linux/freezer.h>
>  #include <linux/cpu.h>
>  #include <linux/delay.h>
> +#include <linux/shazptr.h>
>  #include <linux/stat.h>
>  #include <linux/srcu.h>
>  #include <linux/slab.h>
> @@ -429,6 +430,54 @@ static struct rcu_scale_ops tasks_tracing_ops = {
>  
>  #endif // #else // #ifdef CONFIG_TASKS_TRACE_RCU
>  
> +static int shazptr_scale_read_lock(void)
> +{
> +	long cpu = raw_smp_processor_id();
> +
> +	/* Use cpu + 1 as the key */
> +	guard(shazptr)((void *)(cpu + 1));
> +
> +	return 0;
> +}
> +
> +static int shazptr_scale_wc_read_lock(void)
> +{
> +	guard(shazptr)(SHAZPTR_WILDCARD);
> +
> +	return 0;
> +}
> +
> +
> +static void shazptr_scale_read_unlock(int idx)
> +{
> +	/* Do nothing, it's OK since readers are doing back-to-back lock+unlock*/
> +}
> +
> +static void shazptr_scale_sync(void)
> +{
> +	long cpu = raw_smp_processor_id();
> +
> +	synchronize_shazptr((void *)(cpu + 1));
> +}
> +
> +static struct rcu_scale_ops shazptr_ops = {
> +	.ptype		= RCU_FLAVOR,
> +	.readlock	= shazptr_scale_read_lock,
> +	.readunlock	= shazptr_scale_read_unlock,
> +	.sync		= shazptr_scale_sync,
> +	.exp_sync	= shazptr_scale_sync,
> +	.name		= "shazptr"
> +};
> +
> +static struct rcu_scale_ops shazptr_wc_ops = {
> +	.ptype		= RCU_FLAVOR,
> +	.readlock	= shazptr_scale_wc_read_lock,
> +	.readunlock	= shazptr_scale_read_unlock,
> +	.sync		= shazptr_scale_sync,
> +	.exp_sync	= shazptr_scale_sync,
> +	.name		= "shazptr_wildcard"
> +};
> +
>  static unsigned long rcuscale_seq_diff(unsigned long new, unsigned long old)
>  {
>  	if (!cur_ops->gp_diff)
> @@ -1090,7 +1139,8 @@ rcu_scale_init(void)
>  	long i;
>  	long j;
>  	static struct rcu_scale_ops *scale_ops[] = {
> -		&rcu_ops, &srcu_ops, &srcud_ops, TASKS_OPS TASKS_RUDE_OPS TASKS_TRACING_OPS
> +		&rcu_ops, &srcu_ops, &srcud_ops, &shazptr_ops, &shazptr_wc_ops,
> +		TASKS_OPS TASKS_RUDE_OPS TASKS_TRACING_OPS
>  	};
>  
>  	if (!torture_init_begin(scale_type, verbose))
> -- 
> 2.47.1
> 

Re: [RFC PATCH 8/8] locking/lockdep: Use shazptr to protect the key hashlist

[Paul E. McKenney]

On Sun, Apr 13, 2025 at 11:00:55PM -0700, Boqun Feng wrote:
> Erik Lundgren and Breno Leitao reported [1] a case where
> lockdep_unregister_key() can be called from time critical code pathes
> where rntl_lock() may be held. And the synchronize_rcu() in it can slow
> down operations such as using tc to replace a qdisc in a network device.
> 
> In fact the synchronize_rcu() in lockdep_unregister_key() is to wait for
> all is_dynamic_key() callers to finish so that removing a key from the
> key hashlist, and we can use shazptr to protect the hashlist as well.
> 
> Compared to the proposed solution which replaces synchronize_rcu() with
> synchronize_rcu_expedited(), using shazptr here can achieve the
> same/better synchronization time without the need to send IPI. Hence use
> shazptr here.
> 
> Reported-by: Erik Lundgren <elundgren@meta.com>
> Reported-by: Breno Leitao <leitao@debian.org>
> Link: https://lore.kernel.org/lkml/20250321-lockdep-v1-1-78b732d195fb@debian.org/
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

From an RCU and shazptr viewpoint:

Reviewed-by: Paul E. McKenney <paulmck@kernel.org>

> ---
>  kernel/locking/lockdep.c | 11 ++++++++---
>  1 file changed, 8 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 58d78a33ac65..c5781d2dc8c6 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -58,6 +58,7 @@
>  #include <linux/context_tracking.h>
>  #include <linux/console.h>
>  #include <linux/kasan.h>
> +#include <linux/shazptr.h>
>  
>  #include <asm/sections.h>
>  
> @@ -1265,14 +1266,18 @@ static bool is_dynamic_key(const struct lock_class_key *key)
>  
>  	hash_head = keyhashentry(key);
>  
> -	rcu_read_lock();
> +	/* Need preemption disable for using shazptr. */
> +	guard(preempt)();
> +
> +	/* Protect the list search with shazptr. */
> +	guard(shazptr)(hash_head);
> +
>  	hlist_for_each_entry_rcu(k, hash_head, hash_entry) {
>  		if (k == key) {
>  			found = true;
>  			break;
>  		}
>  	}
> -	rcu_read_unlock();
>  
>  	return found;
>  }
> @@ -6614,7 +6619,7 @@ void lockdep_unregister_key(struct lock_class_key *key)
>  		call_rcu(&delayed_free.rcu_head, free_zapped_rcu);
>  
>  	/* Wait until is_dynamic_key() has finished accessing k->hash_entry. */
> -	synchronize_rcu();
> +	synchronize_shazptr(keyhashentry(key));
>  }
>  EXPORT_SYMBOL_GPL(lockdep_unregister_key);
>  
> -- 
> 2.47.1
> 

Re: [RFC PATCH 4/8] shazptr: Avoid synchronize_shaptr() busy waiting

[Boqun Feng]

On Thu, Jul 10, 2025 at 05:56:00PM -0700, Paul E. McKenney wrote:
> On Sun, Apr 13, 2025 at 11:00:51PM -0700, Boqun Feng wrote:
> > For a general purpose hazard pointers implemenation, always busy waiting
> > is not an option. It may benefit some special workload, but overall it
> > hurts the system performance when more and more users begin to call
> > synchronize_shazptr(). Therefore avoid busy waiting for hazard pointer
> > slots changes by using a scan kthread, and each synchronize_shazptr()
> > queues themselves if a quick scan shows they are blocked by some slots.
> > 
> > A simple optimization is done inside the scan: each
> > synchronize_shazptr() tracks which CPUs (or CPU groups if nr_cpu_ids >
> > BITS_PER_LONG) are blocking it and the scan function updates this
> > information for each synchronize_shazptr() (via shazptr_wait)
> > individually. In this way, synchronize_shazptr() doesn't need to wait
> > until a scan result showing all slots are not blocking (as long as the
> > scan has observed each slot has changed into non-block state once).
> > 
> > Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
> 
> OK, so this patch addresses the aforementioned pain.  ;-)
> 
> One question below, might be worth a comment beyond the second paragraph
> of the commit log.  Nevertheless:
> 
> Reviewed-by: Paul E. McKenney <paulmck@kernel.org>
> 

Thanks!

> > ---
> >  kernel/locking/shazptr.c | 277 ++++++++++++++++++++++++++++++++++++++-
> >  1 file changed, 276 insertions(+), 1 deletion(-)
> > 
> > diff --git a/kernel/locking/shazptr.c b/kernel/locking/shazptr.c
> > index 991fd1a05cfd..a8559cb559f8 100644
> > --- a/kernel/locking/shazptr.c
> > +++ b/kernel/locking/shazptr.c
> > @@ -7,18 +7,243 @@
> >   * Author: Boqun Feng <boqun.feng@gmail.com>
> >   */
> >  
> > +#define pr_fmt(fmt) "shazptr: " fmt
> > +
> >  #include <linux/atomic.h>
> >  #include <linux/cpumask.h>
> > +#include <linux/completion.h>
> > +#include <linux/kthread.h>
> > +#include <linux/list.h>
> > +#include <linux/mutex.h>
> >  #include <linux/shazptr.h>
> > +#include <linux/slab.h>
> > +#include <linux/sort.h>
> >  
> >  DEFINE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
> >  EXPORT_PER_CPU_SYMBOL_GPL(shazptr_slots);
> >  
> > -void synchronize_shazptr(void *ptr)
> > +/* Wait structure for synchronize_shazptr(). */
> > +struct shazptr_wait {
> > +	struct list_head list;
> > +	/* Which groups of CPUs are blocking. */
> > +	unsigned long blocking_grp_mask;
> > +	void *ptr;
> > +	struct completion done;
> > +};
> > +
> > +/* Snapshot for hazptr slot. */
> > +struct shazptr_snapshot {
> > +	unsigned long ptr;
> > +	unsigned long grp_mask;
> 
> The point of ->grp_mask is to avoid being fooled by CPUs that assert the
> wildcard after having been found not to be holding a hazard pointer on
> the current object?  And to avoid being delayed by CPUs that picked up

Mostly for this.

> a pointer, were preempted/interrupted for a long time, then do a doomed
> store into their hazard pointer?  Or is there something else subtle
> that I am missing that somehow allows a given object to reappear in a
> hazard pointer?
> 

Also notice that the hazptr pointer usage in lockdep is not a typical
one: I used the hashlist head as the protected pointer, that means after
synchronize_shazptr() finishes there could still be new reader
protecting the same key. So I need this grp_mask trick to avoid readers
starving updaters.

Will add some comment explaining this.

Regards,
Boqun

> > +};
> > +
> > +static inline int
> > +shazptr_snapshot_cmp(const void *a, const void *b)
> > +{
> > +	const struct shazptr_snapshot *snap_a = (struct shazptr_snapshot *)a;
> > +	const struct shazptr_snapshot *snap_b = (struct shazptr_snapshot *)b;
> > +
> > +	if (snap_a->ptr > snap_b->ptr)
> > +		return 1;
> > +	else if (snap_a->ptr < snap_b->ptr)
> > +		return -1;
> > +	else
> > +		return 0;
> > +}
> > +
> > +/* *In-place* merge @n together based on ->ptr and accumulate the >grp_mask. */
> > +static int shazptr_snapshot_merge(struct shazptr_snapshot *snaps, int n)
> > +{
> > +	int new, i;
> > +
> > +	/* Sort first. */
> > +	sort(snaps, n, sizeof(*snaps), shazptr_snapshot_cmp, NULL);
> > +
> > +	new = 0;
> > +
> > +	/* Skip NULLs. */
> > +	for (i = 0; i < n; i++) {
> > +		if (snaps[i].ptr)
> > +			break;
> > +	}
> > +
> > +	while (i < n) {
> > +		/* Start with a new address. */
> > +		snaps[new] = snaps[i];
> > +
> > +		for (; i < n; i++) {
> > +			/* Merge if the next one has the same address. */
> > +			if (snaps[new].ptr == snaps[i].ptr) {
> > +				snaps[new].grp_mask |= snaps[i].grp_mask;
> > +			} else
> > +				break;
> > +		}
> > +
> > +		/*
> > +		 * Either the end has been reached or need to start with a new
> > +		 * record.
> > +		 */
> > +		new++;
> > +	}
> > +
> > +	return new;
> > +}
> > +
> > +/*
> > + * Calculate which group is still blocking @ptr, this assumes the @snaps is
> > + * already merged.
> > + */
> > +static unsigned long
> > +shazptr_snapshot_blocking_grp_mask(struct shazptr_snapshot *snaps,
> > +				   int n, void *ptr)
> > +{
> > +	unsigned long mask = 0;
> > +
> > +	if (!n)
> > +		return mask;
> > +	else if (snaps[n-1].ptr == (unsigned long)SHAZPTR_WILDCARD) {
> > +		/*
> > +		 * Take SHAZPTR_WILDCARD slots, which is ULONG_MAX, into
> > +		 * consideration if any.
> > +		 */
> > +		mask = snaps[n-1].grp_mask;
> > +	}
> > +
> > +	/* TODO: binary search if n is big. */
> > +	for (int i = 0; i < n; i++) {
> > +		if (snaps[i].ptr == (unsigned long)ptr) {
> > +			mask |= snaps[i].grp_mask;
> > +			break;
> > +		}
> > +	}
> > +
> > +	return mask;
> > +}
> > +
> > +/* Scan structure for synchronize_shazptr(). */
> > +struct shazptr_scan {
> > +	/* The scan kthread */
> > +	struct task_struct *thread;
> > +
> > +	/* Wait queue for the scan kthread */
> > +	struct swait_queue_head wq;
> > +
> > +	/* Whether the scan kthread has been scheduled to scan */
> > +	bool scheduled;
> > +
> > +	/* The lock protecting ->queued and ->scheduled */
> > +	struct mutex lock;
> > +
> > +	/* List of queued synchronize_shazptr() request. */
> > +	struct list_head queued;
> > +
> > +	int cpu_grp_size;
> > +
> > +	/* List of scanning synchronize_shazptr() request. */
> > +	struct list_head scanning;
> > +
> > +	/* Buffer used for hazptr slot scan, nr_cpu_ids slots*/
> > +	struct shazptr_snapshot* snaps;
> > +};
> > +
> > +static struct shazptr_scan shazptr_scan;
> > +
> > +static void shazptr_do_scan(struct shazptr_scan *scan)
> > +{
> > +	int cpu;
> > +	int snaps_len;
> > +	struct shazptr_wait *curr, *next;
> > +
> > +	scoped_guard(mutex, &scan->lock) {
> > +		/* Move from ->queued to ->scanning. */
> > +		list_splice_tail_init(&scan->queued, &scan->scanning);
> > +	}
> > +
> > +	memset(scan->snaps, nr_cpu_ids, sizeof(struct shazptr_snapshot));
> > +
> > +	for_each_possible_cpu(cpu) {
> > +		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> > +		void *val;
> > +
> > +		/* Pair with smp_store_release() in shazptr_clear(). */
> > +		val = smp_load_acquire(slot);
> > +
> > +		scan->snaps[cpu].ptr = (unsigned long)val;
> > +		scan->snaps[cpu].grp_mask = 1UL << (cpu / scan->cpu_grp_size);
> > +	}
> > +
> > +	snaps_len = shazptr_snapshot_merge(scan->snaps, nr_cpu_ids);
> > +
> > +	/* Only one thread can access ->scanning, so can be lockless. */
> > +	list_for_each_entry_safe(curr, next, &scan->scanning, list) {
> > +		/* Accumulate the shazptr slot scan result. */
> > +		curr->blocking_grp_mask &=
> > +			shazptr_snapshot_blocking_grp_mask(scan->snaps,
> > +							   snaps_len,
> > +							   curr->ptr);
> > +
> > +		if (curr->blocking_grp_mask == 0) {
> > +			/* All shots are observed as not blocking once. */
> > +			list_del(&curr->list);
> > +			complete(&curr->done);
> > +		}
> > +	}
> > +}
> > +
> > +static int __noreturn shazptr_scan_kthread(void *unused)
> > +{
> > +	for (;;) {
> > +		swait_event_idle_exclusive(shazptr_scan.wq,
> > +					   READ_ONCE(shazptr_scan.scheduled));
> > +
> > +		shazptr_do_scan(&shazptr_scan);
> > +
> > +		scoped_guard(mutex, &shazptr_scan.lock) {
> > +			if (list_empty(&shazptr_scan.queued) &&
> > +			    list_empty(&shazptr_scan.scanning))
> > +				shazptr_scan.scheduled = false;
> > +		}
> > +	}
> > +}
> > +
> > +static int __init shazptr_scan_init(void)
> > +{
> > +	struct shazptr_scan *scan = &shazptr_scan;
> > +	struct task_struct *t;
> > +
> > +	init_swait_queue_head(&scan->wq);
> > +	mutex_init(&scan->lock);
> > +	INIT_LIST_HEAD(&scan->queued);
> > +	INIT_LIST_HEAD(&scan->scanning);
> > +	scan->scheduled = false;
> > +
> > +	/* Group CPUs into at most BITS_PER_LONG groups. */
> > +	scan->cpu_grp_size = DIV_ROUND_UP(nr_cpu_ids, BITS_PER_LONG);
> > +
> > +	scan->snaps = kcalloc(nr_cpu_ids, sizeof(scan->snaps[0]), GFP_KERNEL);
> > +
> > +	if (scan->snaps) {
> > +		t = kthread_run(shazptr_scan_kthread, NULL, "shazptr_scan");
> > +		if (!IS_ERR(t)) {
> > +			smp_store_release(&scan->thread, t);
> > +			/* Kthread creation succeeds */
> > +			return 0;
> > +		} else {
> > +			kfree(scan->snaps);
> > +		}
> > +	}
> > +
> > +	pr_info("Failed to create the scan thread, only busy waits\n");
> > +	return 0;
> > +}
> > +core_initcall(shazptr_scan_init);
> > +
> > +static void synchronize_shazptr_busywait(void *ptr)
> >  {
> >  	int cpu;
> >  
> >  	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
> > +
> >  	for_each_possible_cpu(cpu) {
> >  		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> >  		/* Pair with smp_store_release() in shazptr_clear(). */
> > @@ -26,4 +251,54 @@ void synchronize_shazptr(void *ptr)
> >  				      VAL != ptr && VAL != SHAZPTR_WILDCARD);
> >  	}
> >  }
> > +
> > +static void synchronize_shazptr_normal(void *ptr)
> > +{
> > +	int cpu;
> > +	unsigned long blocking_grp_mask = 0;
> > +
> > +	smp_mb(); /* Synchronize with the smp_mb() in shazptr_acquire(). */
> > +
> > +	for_each_possible_cpu(cpu) {
> > +		void **slot = per_cpu_ptr(&shazptr_slots, cpu);
> > +		void *val;
> > +
> > +		/* Pair with smp_store_release() in shazptr_clear(). */
> > +		val = smp_load_acquire(slot);
> > +
> > +		if (val == ptr || val == SHAZPTR_WILDCARD)
> > +			blocking_grp_mask |= 1UL << (cpu / shazptr_scan.cpu_grp_size);
> > +	}
> > +
> > +	/* Found blocking slots, prepare to wait. */
> > +	if (blocking_grp_mask) {
> > +		struct shazptr_scan *scan = &shazptr_scan;
> > +		struct shazptr_wait wait = {
> > +			.blocking_grp_mask = blocking_grp_mask,
> > +		};
> > +
> > +		INIT_LIST_HEAD(&wait.list);
> > +		init_completion(&wait.done);
> > +
> > +		scoped_guard(mutex, &scan->lock) {
> > +			list_add_tail(&wait.list, &scan->queued);
> > +
> > +			if (!scan->scheduled) {
> > +				WRITE_ONCE(scan->scheduled, true);
> > +				swake_up_one(&shazptr_scan.wq);
> > +			}
> > +		}
> > +
> > +		wait_for_completion(&wait.done);
> > +	}
> > +}
> > +
> > +void synchronize_shazptr(void *ptr)
> > +{
> > +	/* Busy waiting if the scan kthread has not been created. */
> > +	if (!smp_load_acquire(&shazptr_scan.thread))
> > +		synchronize_shazptr_busywait(ptr);
> > +	else
> > +		synchronize_shazptr_normal(ptr);
> > +}
> >  EXPORT_SYMBOL_GPL(synchronize_shazptr);
> > -- 
> > 2.47.1
> >