Skip to contentSkip to conversation

Introduce simple hazard pointers for lockdep

PATCH In review Boqun Feng 8 participants 34 messages Jun 25, 2025 – Jul 11, 2025

Subsystems (6)
lore
Share & tools
lore

Boqun Feng

author
#0 lore raw

cover Introduce simple hazard pointers for lockdep

Hi,

This is the official first version of simple hazard pointers following the RFC:

	https://lore.kernel.org/lkml/[email protected]/

I rebase it onto v6.16-rc3 and hope to get more feedback this time.

Thanks a lot for Breno Leitao to try the RFC out and share the numbers.

I did an extra comparison this time, between the shazptr solution and the synchronize_rcu_expedited() solution. In my test, during a 100 times "tc qdisc replace" run:

* IPI rate with the shazptr solution: ~14 per second per core.
* IPI rate with synchronize_rcu_expedited(): ~140 per second per core.

(IPI results were from the 'CAL' line in /proc/interrupt)

This shows that while both solutions have the similar speedup, shazptr solution avoids the introduce of high IPI rate compared to synchronize_rcu_expedited().

Feedback is welcome and please let know if there is any concern or suggestion. Thanks!

Regards,
Boqun

--------------------------------------
Please find the old performance below:

On my system (a 96-cpu VMs), the results of:

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

are (with lockdep enabled):

	(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

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
Signature · 1 line
2.39.5 (Apple Git-154)
author
#1 lore raw

PATCH 1/8 Introduce simple hazard pointers

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

---
 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
include/linux/shazptr.h new file +73 -0
new file mode 100644
index 000000000000..287cd04b4be9
@@ -0,0 +1,73 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Simple hazard pointers
+ *
+ * Copyright (c) 2025, Microsoft Corporation.
+ *
+ * Author: Boqun Feng <[email protected]>
+ *
+ * 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
kernel/locking/Makefile +1 -1
index a114949eeed5..1517076c98ec 100644
@@ -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
kernel/locking/shazptr.c new file +29 -0
new file mode 100644
index 000000000000..991fd1a05cfd
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Simple hazard pointers
+ *
+ * Copyright (c) 2025, Microsoft Corporation.
+ *
+ * Author: Boqun Feng <[email protected]>
+ */
+
+#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);
Signature · 1 line
2.39.5 (Apple Git-154)
maintainer
#2 lore raw

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

Quoted 7 lines · 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.

Quoted 12 lines

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.

Don't we typically name such a thing a tombstone?

Quoted 39 lines

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

---
 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
include/linux/shazptr.h new file +6 -0
new file mode 100644
index 000000000000..287cd04b4be9
@@ -0,0 +1,73 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Simple hazard pointers
+ *
+ * Copyright (c) 2025, Microsoft Corporation.
+ *

include/linux/shazptr.h line 16

Quoted 10 lines
include/linux/shazptr.h new file +10 -0
+ * Author: Boqun Feng <[email protected]>
+ *
+ * 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.

It might be useful to have some example code included here to illustrate how this is supposed to be used etc.

include/linux/shazptr.h line 26

Quoted 10 lines
include/linux/shazptr.h new file +10 -0
+ */
+
+#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))

Right, I typically write that like: ((void *)-1L) or ((void *)~0UL)

include/linux/shazptr.h line 34

Quoted 8 lines
include/linux/shazptr.h new file +8 -0
+
+DECLARE_PER_CPU_SHARED_ALIGNED(void *, shazptr_slots);
+
+/* Represent a held hazard pointer slot */
+struct shazptr_guard {
+	void **slot;
+	bool use_wildcard;
+};

Natural alignment ensures the LSB of that pointer is 0, which is enough space to stick that bool in, no?

include/linux/shazptr.h line 46

Quoted 12 lines
include/linux/shazptr.h new file +12 -0
+
+/*
+ * 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),

What you're trying to say with that comment is that: this_cpu_ptr(), will complain if preemption is not already disabled, and as such this verifies the assumption?

You can also add:

	lockdep_assert_preemption_disabled();

at the start of this function and then all these comments can go in the bin, no?

Quoted 55 lines
include/linux/shazptr.h new file +27 -0
+		.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
kernel/locking/Makefile +1 -1
index a114949eeed5..1517076c98ec 100644
@@ -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
kernel/locking/shazptr.c new file +9 -0
new file mode 100644
index 000000000000..991fd1a05cfd
@@ -0,0 +1,29 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Simple hazard pointers
+ *
+ * Copyright (c) 2025, Microsoft Corporation.
+ *
+ * Author: Boqun Feng <[email protected]>
+ */
+

kernel/locking/shazptr.c line 19

Quoted 10 lines
kernel/locking/shazptr.c new file +10 -0
+#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;
	lockdep_assert_preemption_enabled();
Quoted 13 lines
kernel/locking/shazptr.c new file +10 -0
+
+	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);
Signature · 1 line
2.39.5 (Apple Git-154)
#3 lore raw

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

In reply to Boqun Feng

On 2025-06-24 23:10, Boqun Feng wrote:
[...]

include/linux/shazptr.h line 66

Quoted 6 lines
include/linux/shazptr.h new file +6 -0
+
+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() */

How is the wildcard ever cleared ?

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author
#4 lore raw

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

Quoted 11 lines · Mathieu Desnoyers

On 2025-06-24 23:10, Boqun Feng wrote:
[...]

include/linux/shazptr.h line 66

Quoted 6 lines
include/linux/shazptr.h new file +6 -0
+
+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() */

How is the wildcard ever cleared ?

The outermost shazptr_guard will have .use_wildcard being false, so it will clear the wildcard. E.g.

	g1 = shazptr_acqure(a); // g1->use_wildcard is false
				// this cpu's hazptr slot is 'a'.
	g2 = shazptr_acqure(b); // g2->use_wildcard is true
				// this cpu's hazptr slot becomes
				// WILDCARD.

	shazptr_clear(g2);	// do nothing
	shazptr_clear(g1);	// clear this cpu's hazptr slot to NULL.

Regards,
Boqun

Quoted 9 lines

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
#5 lore raw

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

In reply to Boqun Feng
Quoted 98 lines · 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

---
  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

include/linux/shazptr.h new file +45 -0
new file mode 100644
index 000000000000..287cd04b4be9
@@ -0,0 +1,73 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * Simple hazard pointers
+ *
+ * Copyright (c) 2025, Microsoft Corporation.
+ *
+ * Author: Boqun Feng <[email protected]>
+ *
+ * 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. */

include/linux/shazptr.h line 55

Quoted 10 lines
include/linux/shazptr.h new file +10 -0
+		.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);
+	}

Is it correct to assume that shazptr cannot be used in a mixed context environment on the same CPU like a task context and an interrupt context trying to acquire it simultaneously because the current check isn't atomic with respect to that?

include/linux/shazptr.h line 67

Quoted 12 lines
include/linux/shazptr.h new file +12 -0
+
+	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() */
+}

Is it better to name it shazptr_release() to be conformant with our current locking convention?

Cheers,
Longman

author
#6 lore raw

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

On Wed, Jun 25, 2025 at 11:52:04AM -0400, Waiman Long wrote:
[...]

Quoted 16 lines
Quoted 16 lines
include/linux/shazptr.h new file +16 -0
+/*
+ * 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);
Quoted 8 lines

include/linux/shazptr.h line 55

Quoted 4 lines
include/linux/shazptr.h new file +4 -0
+	} else {
+		guard.use_wildcard = true;
+		WRITE_ONCE(*guard.slot, SHAZPTR_WILDCARD);
+	}

Is it correct to assume that shazptr cannot be used in a mixed context environment on the same CPU like a task context and an interrupt context trying to acquire it simultaneously because the current check isn't atomic with respect to that?

I think the current implementation actually support mixed context usage, let see (assuming we start in a task context):

	if (likely(!READ_ONCE(*guard.slot))) {

if an interrupt happens here, it's fine because the slot is still empty, as long as the interrupt will eventually clear the slot.

		WRITE_ONCE(*guard.slot, ptr);

if an interrupt happens here, it's fine because the interrupt would notice that the slot is already occupied, hence the interrupt will use a wildcard, and because it uses a wild, it won't clear the slot after it returns. However the task context's shazptr_clear() will eventually clear the slot because its guard's .use_wildcard is false.

	} else {

if an interrupt happens here, it's fine because of the same: interrupt will use wildcard, and it will not clear the slot, and some shazptr_clear() in the task context will eventually clear it.

		guard.use_wildcard = true;
		WRITE_ONCE(*guard.slot, SHAZPTR_WILDCARD);

if an interrupt happens here, it's fine because of the same.

	}

It's similar to why rcu_read_lock() can be just a non-atomic inc.

Quoted 7 lines
Quoted 7 lines
include/linux/shazptr.h new file +7 -0
+
+	smp_mb(); /* Synchronize with smp_mb() at synchronize_shazptr(). */
+
+	return guard;
+}
+
+static inline void shazptr_clear(struct shazptr_guard guard)
Quoted 9 lines

include/linux/shazptr.h line 67

Quoted 5 lines
include/linux/shazptr.h new file +5 -0
+{
+	/* 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() */
+}

Is it better to name it shazptr_release() to be conformant with our current locking convention?

Maybe, but I will need to think about slot reusing between shazptr_acquire() and shazptr_release(), in the general hazptr API, you can hazptr_alloc() a slot, use it and hazptr_clear() and then use it again, eventually hazptr_free(). I would like to keep both hazptr APIs consistent as well. Thanks!

Regards,
Boqun

Quoted 3 lines

Cheers,
Longman

#7 lore raw

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

Quoted 51 lines · Boqun Feng

On Wed, Jun 25, 2025 at 11:52:04AM -0400, Waiman Long wrote:
[...]

Quoted 16 lines
Quoted 16 lines
include/linux/shazptr.h new file +16 -0
+/*
+ * 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);
Quoted 8 lines

include/linux/shazptr.h line 55

Quoted 4 lines
include/linux/shazptr.h new file +4 -0
+	} else {
+		guard.use_wildcard = true;
+		WRITE_ONCE(*guard.slot, SHAZPTR_WILDCARD);
+	}

Is it correct to assume that shazptr cannot be used in a mixed context environment on the same CPU like a task context and an interrupt context trying to acquire it simultaneously because the current check isn't atomic with respect to that?

I think the current implementation actually support mixed context usage, let see (assuming we start in a task context):

	if (likely(!READ_ONCE(*guard.slot))) {

if an interrupt happens here, it's fine because the slot is still empty, as long as the interrupt will eventually clear the slot.

		WRITE_ONCE(*guard.slot, ptr);

if an interrupt happens here, it's fine because the interrupt would notice that the slot is already occupied, hence the interrupt will use a wildcard, and because it uses a wild, it won't clear the slot after it returns. However the task context's shazptr_clear() will eventually clear the slot because its guard's .use_wildcard is false.

	} else {

if an interrupt happens here, it's fine because of the same: interrupt will use wildcard, and it will not clear the slot, and some shazptr_clear() in the task context will eventually clear it.

		guard.use_wildcard = true;
		WRITE_ONCE(*guard.slot, SHAZPTR_WILDCARD);
Quoted 6 lines

if an interrupt happens here, it's fine because of the same.

	}

It's similar to why rcu_read_lock() can be just a non-atomic inc.

You are right.

Quoted 16 lines
Quoted 16 lines

include/linux/shazptr.h line 67

Quoted 13 lines
include/linux/shazptr.h new file +12 -0
+
+	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() */
+}

Is it better to name it shazptr_release() to be conformant with our current locking convention?

Quoted 5 lines

Maybe, but I will need to think about slot reusing between shazptr_acquire() and shazptr_release(), in the general hazptr API, you can hazptr_alloc() a slot, use it and hazptr_clear() and then use it again, eventually hazptr_free(). I would like to keep both hazptr APIs consistent as well. Thanks!

Thanks for the explanation. Maybe we can reuse the general hazptr API names (alloc/clear/free) even though shazptr_free() will be a no-op for now. Just that the current acquire/clear naming looks odd to me.

Thanks,
Longman

author
#8 lore raw

PATCH 2/8 shazptr: Add refscale test

In reply to Boqun Feng

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

---
 kernel/rcu/refscale.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)
kernel/rcu/refscale.c +39 -0
index f11a7c2af778..154520e4ee4c 100644
@@ -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))
Signature · 1 line
2.39.5 (Apple Git-154)
maintainer
#9 lore raw

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

Quoted 22 lines · Boqun Feng

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

---
 kernel/rcu/refscale.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)
kernel/rcu/refscale.c +1 -0
index f11a7c2af778..154520e4ee4c 100644
@@ -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"

kernel/rcu/refscale.c static const struct ref_scale_ops typesafe_seqlock_ops = { · line 901

Quoted 10 lines
kernel/rcu/refscale.c +8 -0
 };
 
+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();
		scoped_guard (preempt)
			guard(shazptr)(ref_shazptr_read_section);
Quoted 4 lines
kernel/rcu/refscale.c +4 -0
+	}
+}
+
+static void ref_shazptr_delay_section(const int nloops, const int udl, const int ndl)

kernel/rcu/refscale.c static const struct ref_scale_ops typesafe_seqlock_ops = { · line 915

Quoted 10 lines
kernel/rcu/refscale.c +10 -0
+{
+	int i;
+
+	for (i = nloops; i >= 0; i--) {
+		preempt_disable();
+		{
+			guard(shazptr)(ref_shazptr_delay_section);
+			un_delay(udl, ndl);
+		}
+		preempt_enable();
		scoped_guard (preempt) {
			guard(shazptr)(ref_shazptr_delay_section);
			un_delay(udl, ndl);
		}
Quoted 29 lines
kernel/rcu/refscale.c +16 -0
+	}
+}
+
+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))
Signature · 1 line
2.39.5 (Apple Git-154)
author
#10 lore raw

PATCH 3/8 shazptr: Add refscale test for wildcard

In reply to 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.

---
 kernel/rcu/refscale.c | 40 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 39 insertions(+), 1 deletion(-)
kernel/rcu/refscale.c +39 -1
index 154520e4ee4c..fdbb4a2c91fe 100644
@@ -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))
Signature · 1 line
2.39.5 (Apple Git-154)
maintainer
#11 lore raw

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

Quoted 20 lines · Boqun Feng
kernel/rcu/refscale.c +20 -0
+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--) {

kernel/rcu/refscale.c static const struct ref_scale_ops shazptr_ops = { · line 960

Quoted 10 lines
kernel/rcu/refscale.c +10 -0
+		preempt_disable();
+		{
+			guard(shazptr)(ref_shazptr_delay_section);
+			/* Trigger wildcard logic */
+			guard(shazptr)(ref_shazptr_wc_delay_section);
+			un_delay(udl, ndl);
+		}
+		preempt_enable();
+	}
+}

Same as the last one, scoped_guard (preempt) can replace the preempt things and the scope.

author
#12 lore raw

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

In reply to 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).

---
 kernel/locking/shazptr.c | 277 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 276 insertions(+), 1 deletion(-)
kernel/locking/shazptr.c +276 -1
index 991fd1a05cfd..a8559cb559f8 100644
@@ -7,18 +7,243 @@
  * Author: Boqun Feng <[email protected]>
  */
 
+#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);
Signature · 1 line
2.39.5 (Apple Git-154)
maintainer
#13 lore raw

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

Quoted 15 lines · Boqun Feng
kernel/locking/shazptr.c +15 -0
+/* 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. */

kernel/locking/shazptr.c line 147

Quoted 10 lines
kernel/locking/shazptr.c +10 -0
+	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;
+};

I find this style very hard to read, also the order of things is weird.

struct shazptr_scan {
	struct task_struct	*thread;
	struct swait_queue_head wq;
	struct list_head	scanning;

	struct mutex		lock;
	struct list_head	queued;    /* __guarded_by(lock) */
	bool			scheduled; /* __guarded_by(lock) */

	struct shazptr_snapshot snaps[0] __counted_by(nr_cpu_ids);
};

(the __guarded_by() thing will come with Thread-Safety support that Google is still cooking in clang)

Quoted 1 line

+static struct shazptr_scan shazptr_scan;

And then make this a pointer, and allocate the whole thing as a single data structure with however much snaps data you need.

maintainer
#14 lore raw

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

In reply to Boqun Feng

Response is a bit weird because non-linear editing..

kernel/locking/shazptr.c line 197

Quoted 8 lines · Boqun Feng
kernel/locking/shazptr.c +7 -0
+	/* Whether the scan kthread has been scheduled to scan */
+	bool scheduled;
 
+static int __noreturn shazptr_scan_kthread(void *unused)
+{
+	for (;;) {
+		swait_event_idle_exclusive(shazptr_scan.wq,
+					   READ_ONCE(shazptr_scan.scheduled));

This seems weird; why use a whole wait-queue, in exclusive mode no less, for something that is one known thread.

Also, I think this thing needs to be FREEZABLE, otherwise suspend might have issues.

Why not just write it like:

		for (;;) {
			set_current_state(TASK_IDLE | TASK_FREEZABLE);
			if (!list_empty(&scan->queue))
				break;
			schedule();
		}
		__set_current_state(TASK_RUNNABLE);

		for (;;) {
			scoped_guard (mutex, scan->lock) {
				if (list_empty(scan->queued) &&
				    list_empty(scan->scanning))
					break;
			}

			shazptr_do_scan(scan);
		}

kernel/locking/shazptr.c line 204

Quoted 6 lines
kernel/locking/shazptr.c +6 -0
+		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;

This condition, why can't we directly use this condition instead of scheduled?

Quoted 16 lines
kernel/locking/shazptr.c +13 -0
+		}
+	}
+}
 
 
+static void synchronize_shazptr_normal(void *ptr)
+{
 
+
+	/* 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,
+		};
+

kernel/locking/shazptr.c void synchronize_shazptr(void *ptr) · line 289

Quoted 10 lines
kernel/locking/shazptr.c +10 -0
+		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);
+			}

Or perhaps; just write this like:

			bool was_empty = list_empty(&scan->queued);
			list_add_tail(&wait.list, &scan->queued);
			if (was_empty)
				wake_up_process(scan->thread);
Quoted 5 lines
kernel/locking/shazptr.c +5 -0
+		}
+
+		wait_for_completion(&wait.done);
+	}
+}
#15 lore raw

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

In reply to Boqun Feng
Quoted 10 lines · Boqun Feng
kernel/locking/shazptr.c +10 -0
+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;

kernel/locking/shazptr.c void synchronize_shazptr(void *ptr) · line 274

Quoted 10 lines
kernel/locking/shazptr.c +10 -0
+
+		/* 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) {

synchronize_rcu() here would be enough since all users have preemption disabled. But I guess this defeats the performance purpose? (If so this might need a comment somewhere).

I guess blocking_grp_mask is to avoid allocating a cpumask (again for performance purpose? So I guess synchronize_shazptr_normal() has some perf expectations?)

One possibility is to have the ptr contained in:

struct hazptr {
void *ptr;
struct cpumask scan_mask
};

And then the caller could simply scan itself those remaining CPUs without relying on the kthread.

But I'm sure there are good reasons for now doing that :-)

Thanks.

Signature · 2 lines
Frederic Weisbecker
SUSE Labs
author
#16 lore raw

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

Quoted 17 lines · Frederic Weisbecker
Quoted 16 lines · Boqun Feng
kernel/locking/shazptr.c +16 -0
+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);
Quoted 9 lines

kernel/locking/shazptr.c void synchronize_shazptr(void *ptr) · line 274

Quoted 4 lines
kernel/locking/shazptr.c +4 -0
+	}
+
+	/* Found blocking slots, prepare to wait. */
+	if (blocking_grp_mask) {

synchronize_rcu() here would be enough since all users have preemption disabled. But I guess this defeats the performance purpose? (If so this might need a comment somewhere).

synchronize_shazptr_normal() cannot wait for a whole grace period, because the point of hazard pointers is to avoid waiting for unrelated readers.

Quoted 2 lines

I guess blocking_grp_mask is to avoid allocating a cpumask (again for performance purpose? So I guess synchronize_shazptr_normal() has some perf

If we are talking about {k,v}malloc allocation:
synchronize_shazptr_normal() would mostly be used in cleanup/free path similar to synchronize_rcu(), therefor I would like to avoid "allocating memory to free memory".

Quoted 9 lines

expectations?)

One possibility is to have the ptr contained in:

struct hazptr {
void *ptr;
struct cpumask scan_mask
};

You mean updaters passing a struct hazptr * into synchronize_shazptr_normal()? That may be a good idea, if multiple updaters can share the same struct hazptr *, we can add that later, but...

Quoted 2 lines

And then the caller could simply scan itself those remaining CPUs without relying on the kthread.

.. this is a bad idea, sure, we can always burn some CPU time to scan, but local optimization doesn't mean global optimization, if in the future, we have a lots of synchronize_shazptr_normal()s happening at the same time, the self busy-waiting scan would become problematic.

Regards,
Boqun

Quoted 8 lines

But I'm sure there are good reasons for now doing that :-)

Thanks.

Signature · 2 lines
Frederic Weisbecker
SUSE Labs
#17 lore raw

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

Quoted 28 lines · Boqun Feng
Quoted 17 lines · Frederic Weisbecker
Quoted 16 lines · Boqun Feng
kernel/locking/shazptr.c +16 -0
+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);
Quoted 9 lines

kernel/locking/shazptr.c void synchronize_shazptr(void *ptr) · line 274

Quoted 4 lines
kernel/locking/shazptr.c +4 -0
+	}
+
+	/* Found blocking slots, prepare to wait. */
+	if (blocking_grp_mask) {

synchronize_rcu() here would be enough since all users have preemption disabled. But I guess this defeats the performance purpose? (If so this might need a comment somewhere).

Quoted 3 lines

synchronize_shazptr_normal() cannot wait for a whole grace period, because the point of hazard pointers is to avoid waiting for unrelated readers.

Fair enough!

Quoted 8 lines
Quoted 3 lines

I guess blocking_grp_mask is to avoid allocating a cpumask (again for performance purpose? So I guess synchronize_shazptr_normal() has some perf

If we are talking about {k,v}malloc allocation:
synchronize_shazptr_normal() would mostly be used in cleanup/free path similar to synchronize_rcu(), therefor I would like to avoid "allocating memory to free memory".

Good point!

Quoted 16 lines
Quoted 10 lines

expectations?)

One possibility is to have the ptr contained in:

struct hazptr {
void *ptr;
struct cpumask scan_mask
};

You mean updaters passing a struct hazptr * into synchronize_shazptr_normal()? That may be a good idea, if multiple updaters can share the same struct hazptr *, we can add that later, but...

Quoted 7 lines
Quoted 2 lines

And then the caller could simply scan itself those remaining CPUs without relying on the kthread.

.. this is a bad idea, sure, we can always burn some CPU time to scan, but local optimization doesn't mean global optimization, if in the future, we have a lots of synchronize_shazptr_normal()s happening at the same time, the self busy-waiting scan would become problematic.

Ok.

Thanks.

Signature · 2 lines
Frederic Weisbecker
SUSE Labs
author
#18 lore raw

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

In reply to 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().

---
 kernel/locking/shazptr.c | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)
kernel/locking/shazptr.c +21 -7
index a8559cb559f8..b3f7e8390eb2 100644
@@ -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. */
Signature · 1 line
2.39.5 (Apple Git-154)
author
#19 lore raw

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

In reply to 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.

---
 kernel/rcu/rcuscale.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)
kernel/rcu/rcuscale.c +6 -2
index b521d0455992..45413a73d61e 100644
@@ -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. */
Signature · 1 line
2.39.5 (Apple Git-154)
author
#20 lore raw

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

In reply to 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.

---
 kernel/rcu/rcuscale.c | 52 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 51 insertions(+), 1 deletion(-)
kernel/rcu/rcuscale.c +51 -1
index 45413a73d61e..357431bf802b 100644
@@ -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))
Signature · 1 line
2.39.5 (Apple Git-154)
author
#21 lore raw

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

In reply to 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.

---
 kernel/locking/lockdep.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
kernel/locking/lockdep.c +8 -3
index dd2bbf73718b..5c205dd425f8 100644
@@ -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>
 
@@ -1267,14 +1268,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;
 }
@@ -6620,7 +6625,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);
 
Signature · 1 line
2.39.5 (Apple Git-154)
maintainer
#22 lore raw

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

kernel/locking/lockdep.c static bool is_dynamic_key(const struct lock_class_key *key) · line 1275

Quoted 5 lines · Boqun Feng
kernel/locking/lockdep.c +5 -0
+	/* Need preemption disable for using shazptr. */
+	guard(preempt)();
+
+	/* Protect the list search with shazptr. */
+	guard(shazptr)(hash_head);

OK, this is the end of the series, and so far every single user is doing both a preempt and a shazptr guard. Why can't we simplify this and have the shazptr guard imply preempt-disable?

author
#23 lore raw

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

Quoted 11 lines · Peter Zijlstra

kernel/locking/lockdep.c static bool is_dynamic_key(const struct lock_class_key *key) · line 1275

Quoted 5 lines · Boqun Feng
kernel/locking/lockdep.c +5 -0
+	/* Need preemption disable for using shazptr. */
+	guard(preempt)();
+
+	/* Protect the list search with shazptr. */
+	guard(shazptr)(hash_head);

OK, this is the end of the series, and so far every single user is doing both a preempt and a shazptr guard. Why can't we simplify this and have the shazptr guard imply preempt-disable?

You're right. The background story is that in the beginning, the hazard pointer protection was placed at the callsites of is_dynamic_key(): one in register_lock_class() and one in lockdep_init_map_type(), and in register_lock_class() I could use the fact that it's called with irq disabled to save the preempt-disable.

So given the current users, it makes sense to fold the preempt disabling into shazptr guard.

Regards,
Boqun

Tested-by on v1 8/8
#24 lore raw

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

In reply to Boqun Feng

Hello Boqun,

Quoted 14 lines · 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.

Quoted 4 lines

First of all, thanks for working to fix the origianl issue. I've been able to test this in my host, and the gain is impressive.

Before:

         # time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
         real    0m13.195s
         user    0m0.001s
         sys     0m2.746s

With your patch:

	#  time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
	real	0m0.135s
	user	0m0.002s
	sys	0m0.116s

	#  time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq
	real	0m0.127s
	user	0m0.001s
	sys	0m0.112s

Please add the following to the series:

author
#25 lore raw

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

Quoted 44 lines · Breno Leitao

Hello Boqun,

Quoted 14 lines · 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.

Quoted 4 lines

First of all, thanks for working to fix the origianl issue. I've been able to test this in my host, and the gain is impressive.

Before:

         # time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
         real    0m13.195s
         user    0m0.001s
         sys     0m2.746s

With your patch:

	#  time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1234: mq
	real	0m0.135s
	user	0m0.002s
	sys	0m0.116s

	#  time /usr/sbin/tc qdisc replace dev eth0 root handle 0x1: mq
	real	0m0.127s
	user	0m0.001s
	sys	0m0.112s
Quoted 3 lines

Please add the following to the series:

Thanks! Will apply ;-)

Regards,
Boqun

#26 lore raw
In reply to Boqun Feng
Quoted 4 lines · Boqun Feng

Hi,

This is the official first version of simple hazard pointers following the RFC:

Can you please put an explanation of what hazard pointers are prominently into this cover letter?

author
#27 lore raw
Quoted 9 lines · Christoph Hellwig
Quoted 4 lines · Boqun Feng

Hi,

This is the official first version of simple hazard pointers following the RFC:

Can you please put an explanation of what hazard pointers are prominently into this cover letter?

Sure, I will put one for the future version, here is the gist:

Hazard pointers provide the similar synchronzation behavior as RCU:
readers are cheap, updaters need to wait for existing readers to go before they can free the objects.

The difference between hazard pointers and RCU is that instead of waiting for a grace period, which all the readers have to exit the RCU read-side critical sections, the updaters of hazard pointers only need to wait for the readers that are accessing the objects they are about to free. For example, if we have 2 readers accessing different objects and 1 updater is freeing one of them:

using RCU:

	Reader 1		Reader 2		Updater
	========		========		=======
	rcu_read_lock();
	r = rcu_dereference(a);
				rcu_read_lock();
				r = rcu_dereference(b);
							synchronize_rcu();
	rcu_read_unlock();
				rcu_read_unlock();
							<synchronize_rcu() returns>
							free(a);

The updater will need to wait for reader 2 to finish before it can free 'a', however when using hazard pointers:

	Reader 1		Reader 2		Updater
	========		========		=======
	g = shazptr_acquire(a);
				g = shazptr_acqurie(b);
							synchronize_shazptr(a);
	shazptr_clear(g);
							<synchronize_shazptr(a) returns>
							free(a);

				shazptr_clear(g); // <- updater doesn't
						  //    need to wait for
						  //    this.

The updater's wait can finish immediately if no one is accessing 'a', in other words it doesn't need to wait for reader 2.

This means for a particular workload, hazard pointers may have smaller memory footprint and less updater wait time compared to RCU, while still have the similar performance on the reader side.

That being said, it does come with some cost, the readers would need to provide their own hazard pointer slots (allocating memory) in general cases. And in the simple hazard pointer implementation in this series, although readers don't need to provide their own hazard pointer slots, they need to disable the preemption to use the hazard pointer, and the performance would downgrade (to a naive SRCU implementation probably) if they want to protect multiple objects in one read-side critical section.

Regards,
Boqun

#28 lore raw
Quoted 1 line · Boqun Feng

Sure, I will put one for the future version, here is the gist:

Thanks a lot!

Quoted 2 lines

The updater's wait can finish immediately if no one is accessing 'a', in other words it doesn't need to wait for reader 2.

So basically it is the RCU concept, but limited to protecting exactly one pointer update per critical section with no ability for the read to e.g. acquire a refcount on the objected pointed to by that pointer?

#29 lore raw
Quoted 11 lines · Christoph Hellwig
Quoted 1 line · Boqun Feng

Sure, I will put one for the future version, here is the gist:

Thanks a lot!

Quoted 2 lines

The updater's wait can finish immediately if no one is accessing 'a', in other words it doesn't need to wait for reader 2.

So basically it is the RCU concept, but limited to protecting exactly one pointer update per critical section with no ability for the read to e.g. acquire a refcount on the objected pointed to by that pointer?

FWIW, hazard pointers can be chained with other existence guarantee mechanisms. I've done prototypes that use hazard pointers chained with a reference counter in the object to implement something similar to smart pointers. Let me know if you are interested in the details.

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author
#30 lore raw
In reply to Christoph Hellwig
Quoted 11 lines · Christoph Hellwig
Quoted 1 line · Boqun Feng

Sure, I will put one for the future version, here is the gist:

Thanks a lot!

Quoted 2 lines

The updater's wait can finish immediately if no one is accessing 'a', in other words it doesn't need to wait for reader 2.

So basically it is the RCU concept, but limited to protecting exactly one pointer update per critical section with no ability for the read to e.g. acquire a refcount on the objected pointed to by that pointer?

For the current simple hazard pointer, yes. But simple hazard pointers is easily to extend so support reading:

	{ gp is a global pointer }

	Reader				Updater
	======				=======
	g = shazptr_acquire(p):
	      WRITE_ONCE(*this_cpu_ptr(slot), gp);
	      smp_mb();
	
	if (READ_ONCE(gp) == *this_cpu_ptr(slot)) {
	    // still being protected.
	    <can read gp here>
					to_free = READ_ONCE(gp);
					WRITE_ONCE(gp, new);
					synchronize_shazptr(to_free):
					  smp_mb();
					  // wait on the slot of reader
					  // CPU being 0.
					  READ_ONCE(per_cpu(reader, slot));
	}

	shazptr_clear(g):
	  WRITE_ONCE(*this_cpu_ptr(slot), NULL); // unblock synchronize_shazptr()

Usually the shazptr_acqurie() + "pointer comparison"* is called shazptr_try_protect().

I will add a document about this in the next version along with other bits of hazard pointers.

[*]: The pointer comparison is more complicated topic, but Mathieu has
figured out how to do it correctly:

https://lore.kernel.org/lkml/[email protected]/

Regards,
Boqun

maintainer
#31 lore raw
Quoted 43 lines · Boqun Feng
Quoted 11 lines · Christoph Hellwig
Quoted 1 line · Boqun Feng

Sure, I will put one for the future version, here is the gist:

Thanks a lot!

Quoted 2 lines

The updater's wait can finish immediately if no one is accessing 'a', in other words it doesn't need to wait for reader 2.

So basically it is the RCU concept, but limited to protecting exactly one pointer update per critical section with no ability for the read to e.g. acquire a refcount on the objected pointed to by that pointer?

For the current simple hazard pointer, yes. But simple hazard pointers is easily to extend so support reading:

	{ gp is a global pointer }

	Reader				Updater
	======				=======
	g = shazptr_acquire(p):
	      WRITE_ONCE(*this_cpu_ptr(slot), gp);
	      smp_mb();
	
	if (READ_ONCE(gp) == *this_cpu_ptr(slot)) {
	    // still being protected.
	    <can read gp here>
					to_free = READ_ONCE(gp);
					WRITE_ONCE(gp, new);
					synchronize_shazptr(to_free):
					  smp_mb();
					  // wait on the slot of reader
					  // CPU being 0.
					  READ_ONCE(per_cpu(reader, slot));
	}

	shazptr_clear(g):
	  WRITE_ONCE(*this_cpu_ptr(slot), NULL); // unblock synchronize_shazptr()

Usually the shazptr_acqurie() + "pointer comparison"* is called shazptr_try_protect().

Quoted 7 lines

I will add a document about this in the next version along with other bits of hazard pointers.

[*]: The pointer comparison is more complicated topic, but Mathieu has
figured out how to do it correctly:

https://lore.kernel.org/lkml/[email protected]/

It might be helpful to add that, at a high level, hazard pointers are a scalable replacement for reference counting. At a similarly high level, RCU is a scalable replacement for reader-writer locking. At lower levels, there is considerable overlap in applicability, so that you can use RCU to replace many reference-counting use cases and hazard pointers to replace many reader-writer-locking use cases..

Plus, as both Mathieu and Boqun pointed out, both RCU and hazard pointers can be combined with other synchronization mechanisms, including each other.

Thanx, Paul

#32 lore raw
In reply to Boqun Feng
Quoted 18 lines · Boqun Feng

Hi,

This is the official first version of simple hazard pointers following the RFC:

	https://lore.kernel.org/lkml/[email protected]/

I rebase it onto v6.16-rc3 and hope to get more feedback this time.

Thanks a lot for Breno Leitao to try the RFC out and share the numbers.

I did an extra comparison this time, between the shazptr solution and the synchronize_rcu_expedited() solution. In my test, during a 100 times "tc qdisc replace" run:

* IPI rate with the shazptr solution: ~14 per second per core.
* IPI rate with synchronize_rcu_expedited(): ~140 per second per core.

Quoted 8 lines

(IPI results were from the 'CAL' line in /proc/interrupt)

This shows that while both solutions have the similar speedup, shazptr solution avoids the introduce of high IPI rate compared to synchronize_rcu_expedited().

Feedback is welcome and please let know if there is any concern or suggestion. Thanks!

Hi Boqun,

What is unclear to me is what is the delta wrt:

https://lore.kernel.org/lkml/[email protected]/

and whether this helper against compiler optimizations would still be needed here:

https://lore.kernel.org/lkml/[email protected]/

Thanks,

Mathieu

Quoted 95 lines

Regards,
Boqun

--------------------------------------
Please find the old performance below:

On my system (a 96-cpu VMs), the results of:

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

are (with lockdep enabled):

	(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

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com
author
#33 lore raw
Quoted 25 lines · Mathieu Desnoyers
Quoted 24 lines · Boqun Feng

Hi,

This is the official first version of simple hazard pointers following the RFC:

	https://lore.kernel.org/lkml/[email protected]/

I rebase it onto v6.16-rc3 and hope to get more feedback this time.

Thanks a lot for Breno Leitao to try the RFC out and share the numbers.

I did an extra comparison this time, between the shazptr solution and the synchronize_rcu_expedited() solution. In my test, during a 100 times "tc qdisc replace" run:

* IPI rate with the shazptr solution: ~14 per second per core.
* IPI rate with synchronize_rcu_expedited(): ~140 per second per core.

(IPI results were from the 'CAL' line in /proc/interrupt)

This shows that while both solutions have the similar speedup, shazptr solution avoids the introduce of high IPI rate compared to synchronize_rcu_expedited().

Quoted 9 lines
Quoted 2 lines

Feedback is welcome and please let know if there is any concern or suggestion. Thanks!

Hi Boqun,

What is unclear to me is what is the delta wrt:

https://lore.kernel.org/lkml/[email protected]/

shazptr is more close to the general hazptr I proposed earlier:

	https://lore.kernel.org/lkml/[email protected]/

, it's aimed as a global facility therefore no hazptr_domain is needed, plus it supports non-busy waiting synchronize_shazptr() at the beginning.

Quoted 4 lines

and whether this helper against compiler optimizations would still be needed here:

https://lore.kernel.org/lkml/[email protected]/

For the current user, no, but eventually we are going to need it.

Regards,
Boqun

Quoted 105 lines

Thanks,

Mathieu

Quoted 95 lines

Regards,
Boqun

--------------------------------------
Please find the old performance below:

On my system (a 96-cpu VMs), the results of:

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

are (with lockdep enabled):

	(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

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

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com