[PATCH 01/28] hazptr: Implement Hazard Pointers

[PATCH 01/28] hazptr: Implement Hazard Pointers

[Paul E. McKenney]

From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

This API provides existence guarantees of objects through Hazard
Pointers [1] (hazptr).

Its main benefit over RCU is that it allows fast reclaim of
HP-protected pointers without needing to wait for a grace period.

This implementation has 4 statically allocated hazard pointer slots per
cpu for the fast path, and relies on a on-stack backup slot allocated by
the hazard pointer user as fallback in case no per-cpu slot is
available.

It integrates with the scheduler to migrate per-CPU slots to the backup
slot on context switch. This ensures that the per-CPU slots won't be
used by blocked or preempted tasks holding on hazard pointers for a long
time.

References:

[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://lpc.events/event/19/contributions/2082/
Link: https://lore.kernel.org/lkml/j3scdl5iymjlxavomgc6u5ndg3svhab6ga23dr36o4f5mt333w@7xslvq6b6hmv/
Link: https://lpc.events/event/18/contributions/1731/
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Nicholas Piggin <npiggin@gmail.com>
Cc: Michael Ellerman <mpe@ellerman.id.au>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Will Deacon <will@kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Boqun Feng <boqun@kernel.org>
Cc: Alan Stern <stern@rowland.harvard.edu>
Cc: John Stultz <jstultz@google.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Frederic Weisbecker <frederic@kernel.org>
Cc: Joel Fernandes <joel@joelfernandes.org>
Cc: Josh Triplett <josh@joshtriplett.org>
Cc: Uladzislau Rezki <urezki@gmail.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Lai Jiangshan <jiangshanlai@gmail.com>
Cc: Zqiang <qiang.zhang1211@gmail.com>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Mark Rutland <mark.rutland@arm.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Vlastimil Babka <vbabka@suse.cz>
Cc: maged.michael@gmail.com
Cc: Mateusz Guzik <mjguzik@gmail.com>
Cc: Jonas Oberhauser <jonas.oberhauser@huaweicloud.com>
Cc: <rcu@vger.kernel.org>
Cc: <linux-mm@kvack.org>
Cc: <lkmm@lists.linux.dev>
Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
---
 include/linux/hazptr.h | 197 +++++++++++++++++++++++++++++++++
 init/main.c            |   2 +
 kernel/Makefile        |   2 +-
 kernel/hazptr.c        | 242 +++++++++++++++++++++++++++++++++++++++++
 kernel/sched/core.c    |   2 +
 5 files changed, 444 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/hazptr.h
 create mode 100644 kernel/hazptr.c

diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
new file mode 100644
index 000000000000..b121f7779cda
--- /dev/null
+++ b/include/linux/hazptr.h
@@ -0,0 +1,197 @@
+// SPDX-License-Identifier: LGPL-2.1-or-later
+//
+// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+
+#ifndef _LINUX_HAZPTR_H
+#define _LINUX_HAZPTR_H
+
+/*
+ * hazptr: Hazard Pointers
+ *
+ * This API provides existence guarantees of objects through hazard
+ * pointers.
+ *
+ * Its main benefit over RCU is that it allows fast reclaim of
+ * HP-protected pointers without needing to wait for a grace period.
+ *
+ * References:
+ *
+ * [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/percpu.h>
+#include <linux/types.h>
+#include <linux/cleanup.h>
+#include <linux/sched.h>
+
+/* 4 slots (each sizeof(hazptr_slot_item)) fit in a single 64-byte cache line. */
+#define NR_HAZPTR_PERCPU_SLOTS	4
+#define HAZPTR_WILDCARD		((void *) 0x1UL)
+
+/*
+ * Hazard pointer slot.
+ */
+struct hazptr_slot {
+	void *addr;
+};
+
+struct hazptr_overflow_list;
+
+struct hazptr_backup_slot {
+	struct hlist_node overflow_node;
+	struct hazptr_slot slot;
+	/* Overflow list where the backup slot is added. */
+	struct hazptr_overflow_list *overflow_list;
+};
+
+struct hazptr_ctx {
+	struct hazptr_slot *slot;
+	/* Backup slot in case all per-CPU slots are used. */
+	struct hazptr_backup_slot backup_slot;
+	struct hlist_node preempt_node;
+};
+
+struct hazptr_slot_ctx {
+	struct hazptr_ctx *ctx;
+};
+
+struct hazptr_slot_item {
+	struct hazptr_slot slot;
+	struct hazptr_slot_ctx ctx;
+};
+
+struct hazptr_percpu_slots {
+	struct hazptr_slot_item items[NR_HAZPTR_PERCPU_SLOTS];
+} ____cacheline_aligned;
+
+DECLARE_PER_CPU(struct hazptr_percpu_slots, hazptr_percpu_slots);
+
+void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p);
+
+/*
+ * hazptr_synchronize: Wait until @addr is released from all slots.
+ *
+ * Wait to observe that each slot contains a value that differs from
+ * @addr before returning.
+ * Should be called from preemptible context.
+ */
+void hazptr_synchronize(void *addr);
+
+/*
+ * hazptr_chain_backup_slot: Chain backup slot into overflow list.
+ *
+ * Set backup slot address to @addr, and chain it into the overflow
+ * list.
+ */
+struct hazptr_slot *hazptr_chain_backup_slot(struct hazptr_ctx *ctx);
+
+/*
+ * hazptr_unchain_backup_slot: Unchain backup slot from overflow list.
+ */
+void hazptr_unchain_backup_slot(struct hazptr_ctx *ctx);
+
+static inline
+bool hazptr_slot_is_backup(struct hazptr_ctx *ctx, struct hazptr_slot *slot)
+{
+	return slot == &ctx->backup_slot.slot;
+}
+
+static inline
+void hazptr_note_context_switch(void)
+{
+	struct hazptr_percpu_slots *percpu_slots = this_cpu_ptr(&hazptr_percpu_slots);
+	unsigned int idx;
+
+	for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
+		struct hazptr_slot_item *item = &percpu_slots->items[idx];
+		struct hazptr_slot *slot = &item->slot, *backup_slot;
+		struct hazptr_ctx *ctx;
+
+		if (!slot->addr)
+			continue;
+		ctx = item->ctx.ctx;
+		backup_slot = hazptr_chain_backup_slot(ctx);
+		/*
+		 * Move hazard pointer from the per-CPU slot to the
+		 * backup slot. This requires hazard pointer
+		 * synchronize to iterate on per-CPU slots with
+		 * load-acquire before iterating on the overflow list.
+		 */
+		WRITE_ONCE(backup_slot->addr, slot->addr);
+		/*
+		 * store-release orders store to backup slot addr before
+		 * store to per-CPU slot addr.
+		 */
+		smp_store_release(&slot->addr, NULL);
+		/* Use the backup slot for context. */
+		ctx->slot = backup_slot;
+	}
+}
+
+/*
+ * hazptr_acquire: Load pointer at address and protect with hazard pointer.
+ *
+ * Load @addr_p, and protect the loaded pointer with hazard pointer.
+ * When using hazptr_acquire from interrupt handlers, the acquired slots
+ * need to be released before returning from the interrupt handler.
+ *
+ * Returns a non-NULL protected address if the loaded pointer is non-NULL.
+ * Returns NULL if the loaded pointer is NULL.
+ *
+ * On success the protected hazptr slot is stored in @ctx->slot.
+ */
+static inline
+void *hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
+{
+	struct hazptr_percpu_slots *percpu_slots;
+	struct hazptr_slot_item *slot_item;
+	struct hazptr_slot *slot;
+	void *addr;
+
+	guard(preempt)();
+	percpu_slots = this_cpu_ptr(&hazptr_percpu_slots);
+	slot_item = &percpu_slots->items[0];
+	slot = &slot_item->slot;
+	if (unlikely(slot->addr))
+		return __hazptr_acquire(ctx, addr_p);
+	WRITE_ONCE(slot->addr, HAZPTR_WILDCARD);	/* Store B */
+
+	/* Memory ordering: Store B before Load A. */
+	smp_mb();
+
+	/*
+	 * Load @addr_p after storing wildcard to the hazard pointer slot.
+	 */
+	addr = READ_ONCE(*addr_p);	/* Load A */
+
+	/*
+	 * We don't care about ordering of Store C. It will simply
+	 * replace the wildcard by a more specific address. If addr is
+	 * NULL, we simply store NULL into the slot.
+	 */
+	WRITE_ONCE(slot->addr, addr);	/* Store C */
+	slot_item->ctx.ctx = ctx;
+	ctx->slot = slot;
+	return addr;
+}
+
+/* Release the protected hazard pointer from @slot. */
+static inline
+void hazptr_release(struct hazptr_ctx *ctx, void *addr)
+{
+	struct hazptr_slot *slot;
+
+	if (!addr)
+		return;
+	guard(preempt)();
+	slot = ctx->slot;
+	smp_store_release(&slot->addr, NULL);
+	if (unlikely(hazptr_slot_is_backup(ctx, slot)))
+		hazptr_unchain_backup_slot(ctx);
+}
+
+void hazptr_init(void);
+
+#endif /* _LINUX_HAZPTR_H */
diff --git a/init/main.c b/init/main.c
index 2613d3f9b3ce..d9d936707c19 100644
--- a/init/main.c
+++ b/init/main.c
@@ -108,6 +108,7 @@
 #include <linux/time_namespace.h>
 #include <linux/unaligned.h>
 #include <linux/vdso_datastore.h>
+#include <linux/hazptr.h>
 #include <net/net_namespace.h>
 
 #include <asm/io.h>
@@ -1075,6 +1076,7 @@ void start_kernel(void)
 	workqueue_init_early();
 
 	rcu_init();
+	hazptr_init();
 	kvfree_rcu_init();
 
 	/* Trace events are available after this */
diff --git a/kernel/Makefile b/kernel/Makefile
index 1e1a31673577..8961c8660d0d 100644
--- a/kernel/Makefile
+++ b/kernel/Makefile
@@ -7,7 +7,7 @@ obj-y     = fork.o exec_domain.o exec_state.o panic.o \
 	    cpu.o exit.o softirq.o resource.o \
 	    sysctl.o capability.o ptrace.o user.o \
 	    signal.o sys.o umh.o workqueue.o pid.o task_work.o \
-	    extable.o params.o \
+	    extable.o params.o hazptr.o \
 	    kthread.o sys_ni.o nsproxy.o nstree.o nscommon.o \
 	    notifier.o ksysfs.o cred.o reboot.o \
 	    async.o range.o smpboot.o ucount.o regset.o ksyms_common.o
diff --git a/kernel/hazptr.c b/kernel/hazptr.c
new file mode 100644
index 000000000000..a9d3d68a1525
--- /dev/null
+++ b/kernel/hazptr.c
@@ -0,0 +1,242 @@
+// SPDX-License-Identifier: LGPL-2.1-or-later
+//
+// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+
+/*
+ * hazptr: Hazard Pointers
+ */
+
+#include <linux/hazptr.h>
+#include <linux/percpu.h>
+#include <linux/spinlock.h>
+#include <linux/mutex.h>
+#include <linux/list.h>
+#include <linux/export.h>
+
+struct hazptr_overflow_list {
+	raw_spinlock_t lock;		/* Lock protecting overflow list and list generation. */
+	struct hlist_head head;		/* Overflow list head. */
+	uint64_t gen;			/* Overflow list generation. */
+};
+
+/*
+ * Flip between two lists to guarantee list scan forward progress even
+ * with frequent generation counter increments. The list additions are
+ * always done on a different list than the one used for scan. The scan
+ * successively iterates on both lists. Therefore, only list removals
+ * can cause the iteration to retry, and the number of removals is
+ * limited to the number of list elements.
+ */
+struct hazptr_overflow_list_flip {
+	struct mutex lock;		/* Mutex protecting add_idx from concurrent updates. */
+	unsigned int add_idx;		/* Index of current flip-list to add to. */
+	struct hazptr_overflow_list array[2];
+};
+
+static DEFINE_PER_CPU(struct hazptr_overflow_list_flip, percpu_overflow_list_flip);
+
+DEFINE_PER_CPU(struct hazptr_percpu_slots, hazptr_percpu_slots);
+EXPORT_PER_CPU_SYMBOL_GPL(hazptr_percpu_slots);
+
+static
+struct hazptr_slot *hazptr_get_free_percpu_slot(struct hazptr_ctx *ctx)
+{
+	struct hazptr_percpu_slots *percpu_slots = this_cpu_ptr(&hazptr_percpu_slots);
+	unsigned int idx;
+
+	for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
+		struct hazptr_slot_item *item = &percpu_slots->items[idx];
+		struct hazptr_slot *slot = &item->slot;
+
+		if (!slot->addr) {
+			item->ctx.ctx = ctx;
+			return slot;
+		}
+	}
+	/* All slots are in use. */
+	return NULL;
+}
+
+/*
+ * Hazard pointer acquire slow path.
+ * Called with preemption disabled.
+ */
+void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
+{
+	struct hazptr_slot *slot = hazptr_get_free_percpu_slot(ctx);
+	void *addr;
+
+	/*
+	 * If all the per-CPU slots are already in use, fallback
+	 * to the backup slot.
+	 */
+	if (unlikely(!slot))
+		slot = hazptr_chain_backup_slot(ctx);
+	WRITE_ONCE(slot->addr, HAZPTR_WILDCARD);	/* Store B */
+
+	/* Memory ordering: Store B before Load A. */
+	smp_mb();
+
+	/*
+	 * Load @addr_p after storing wildcard to the hazard pointer slot.
+	 */
+	addr = READ_ONCE(*addr_p);	/* Load A */
+
+	/*
+	 * We don't care about ordering of Store C. It will simply
+	 * replace the wildcard by a more specific address. If addr is
+	 * NULL, we simply store NULL into the slot.
+	 */
+	WRITE_ONCE(slot->addr, addr);	/* Store C */
+	ctx->slot = slot;
+	if (!addr && hazptr_slot_is_backup(ctx, slot))
+		hazptr_unchain_backup_slot(ctx);
+	return addr;
+}
+EXPORT_SYMBOL_GPL(__hazptr_acquire);
+
+/*
+ * Perform piecewise iteration on overflow list waiting until "addr" is
+ * not present. Raw spinlock is released and taken between each list
+ * item and busy loop iteration. The overflow list generation is checked
+ * each time the lock is taken to validate that the list has not changed
+ * before resuming iteration or busy wait. If the generation has
+ * changed, retry the entire list traversal.
+ */
+static
+void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list, void *addr)
+{
+	struct hazptr_backup_slot *backup_slot;
+	uint64_t snapshot_gen;
+	unsigned long flags;
+
+	raw_spin_lock_irqsave(&overflow_list->lock, flags);
+retry:
+	snapshot_gen = overflow_list->gen;
+	hlist_for_each_entry(backup_slot, &overflow_list->head, overflow_node) {
+		/* Busy-wait if node is found. */
+		for (;;) {
+			void *load_addr = smp_load_acquire(&backup_slot->slot.addr);	/* Load B */
+
+			if (load_addr != addr && load_addr != HAZPTR_WILDCARD)
+				break;
+			raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
+			cpu_relax();
+			raw_spin_lock_irqsave(&overflow_list->lock, flags);
+			if (overflow_list->gen != snapshot_gen)
+				goto retry;
+		}
+		raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
+		/*
+		 * Release raw spinlock, validate generation after
+		 * re-acquiring the lock.
+		 */
+		raw_spin_lock_irqsave(&overflow_list->lock, flags);
+		if (overflow_list->gen != snapshot_gen)
+			goto retry;
+	}
+	raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
+}
+
+static
+void hazptr_synchronize_cpu_slots(int cpu, void *addr)
+{
+	struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu);
+	unsigned int idx;
+
+	for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
+		struct hazptr_slot_item *item = &percpu_slots->items[idx];
+
+		/* Busy-wait if node is found. */
+		smp_cond_load_acquire(&item->slot.addr, VAL != addr && VAL != HAZPTR_WILDCARD); /* Load B */
+	}
+}
+
+/*
+ * hazptr_synchronize: Wait until @addr is released from all slots.
+ *
+ * Wait to observe that each slot contains a value that differs from
+ * @addr before returning.
+ * Should be called from preemptible context.
+ */
+void hazptr_synchronize(void *addr)
+{
+	int cpu;
+
+	/*
+	 * Busy-wait should only be done from preemptible context.
+	 */
+	lockdep_assert_preemption_enabled();
+
+	/*
+	 * Store A precedes hazptr_scan(): it unpublishes addr (sets it to
+	 * NULL or to a different value), and thus hides it from hazard
+	 * pointer readers.
+	 */
+	if (!addr)
+		return;
+	/* Memory ordering: Store A before Load B. */
+	smp_mb();
+	/* Scan all CPUs slots. */
+	for_each_possible_cpu(cpu) {
+		struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu);
+		unsigned int scan_idx;
+
+		/* Scan CPU slots. */
+		hazptr_synchronize_cpu_slots(cpu, addr);
+
+		/*
+		 * Scan backup slots in percpu overflow lists.
+		 * Forward progress is guaranteed by scanning one list
+		 * while new elements are added into the other list.
+		 */
+		guard(mutex)(&overflow_list_flip->lock);
+		scan_idx = overflow_list_flip->add_idx ^ 1;
+		hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx], addr);
+		/* Flip current list. */
+		WRITE_ONCE(overflow_list_flip->add_idx, scan_idx);
+		hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx ^ 1], addr);
+	}
+}
+EXPORT_SYMBOL_GPL(hazptr_synchronize);
+
+struct hazptr_slot *hazptr_chain_backup_slot(struct hazptr_ctx *ctx)
+{
+	struct hazptr_overflow_list_flip *overflow_list_flip = this_cpu_ptr(&percpu_overflow_list_flip);
+	unsigned int list_idx = READ_ONCE(overflow_list_flip->add_idx);
+	struct hazptr_overflow_list *overflow_list = &overflow_list_flip->array[list_idx];
+	struct hazptr_slot *slot = &ctx->backup_slot.slot;
+
+	slot->addr = NULL;
+	guard(raw_spinlock_irqsave)(&overflow_list->lock);
+	overflow_list->gen++;
+	hlist_add_head(&ctx->backup_slot.overflow_node, &overflow_list->head);
+	ctx->backup_slot.overflow_list = overflow_list;
+	return slot;
+}
+EXPORT_SYMBOL_GPL(hazptr_chain_backup_slot);
+
+void hazptr_unchain_backup_slot(struct hazptr_ctx *ctx)
+{
+	struct hazptr_overflow_list *overflow_list = ctx->backup_slot.overflow_list;
+
+	guard(raw_spinlock_irqsave)(&overflow_list->lock);
+	overflow_list->gen++;
+	hlist_del(&ctx->backup_slot.overflow_node);
+}
+EXPORT_SYMBOL_GPL(hazptr_unchain_backup_slot);
+
+void __init hazptr_init(void)
+{
+	int cpu;
+
+	for_each_possible_cpu(cpu) {
+		struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu);
+
+		mutex_init(&overflow_list_flip->lock);
+		for (int i = 0; i < 2; i++) {
+			raw_spin_lock_init(&overflow_list_flip->array[i].lock);
+			INIT_HLIST_HEAD(&overflow_list_flip->array[i].head);
+		}
+	}
+}
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index f78275192036..b77152edafd9 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -59,6 +59,7 @@
 #include <linux/profile.h>
 #include <linux/psi.h>
 #include <linux/rcuwait_api.h>
+#include <linux/hazptr.h>
 #include <linux/rseq.h>
 #include <linux/sched/wake_q.h>
 #include <linux/scs.h>
@@ -7123,6 +7124,7 @@ static void __sched notrace __schedule(int sched_mode)
 	local_irq_disable();
 	rcu_note_context_switch(preempt);
 	migrate_disable_switch(rq, prev);
+	hazptr_note_context_switch();
 
 	/*
 	 * Make sure that signal_pending_state()->signal_pending() below
-- 
2.40.1

Re: [PATCH 01/28] hazptr: Implement Hazard Pointers

[Linus Torvalds]

On Fri, 18 Sept 2026 at 17:01, Paul E. McKenney <paulmck@kernel.org> wrote:
>
> Its main benefit over RCU is that it allows fast reclaim of
> HP-protected pointers without needing to wait for a grace period.

So last time I looked at this was some time ago, but the thing I was
missing then seems to still be missing: actual real numbers.

And no, I most *definitely* do not mean the pointless "do this in a tight loop".

That's just garbage. Honestly, when I see those numbers it just makes
me go "I don't want to merge things that even mention this kind of
stupid load". It's worse than irrelevant - it's an actively
misleading.

So I want to see a real load where this is actually visible not a
"loop a billion times on a hot-cache thing that doesn't do anything".

               Linus

Re: [PATCH 01/28] hazptr: Implement Hazard Pointers

[Linus Torvalds]

On Sat, 19 Sept 2026 at 09:35, Bradley Morgan <brads@mainlining.org> wrote:
>
> I think hazard pointers are good, what test do YOU suggest we do here?

I want to see a single real-world example of "look, this speeds this
real load up by 10%, and the kernel code was actually cleaned up in
the process because hazard pointers are great".

Not a microbenchmark that tests just the hazard pointers themselves,
but a real kernel feature that has been converted to hazard pointers,
and in the process actually shows improvement.

The ONLY reason for hazard pointers to ever be merged is if they
actually buy us something real.

So I want to see that 'real" thing.

I want to see how easy/hard it is to actually convert a real current
user, and I want to see how it actually results in measurable
improvements in performance.

Something *core*. Something that everybody uses. Because I'm not in
the least interested in a new subtle feature that interacts with the
scheduler and is only used for some random driver or (to pick the only
example I have ever seen) AppArmor.

Now, obviously, the thing that would impress me is something like the
dcache. If *that* can be converted, and it shows real improvements on
some real benchmark, then I'm sold.

Now, I don't really expect that kind of major test-case, but I do
expect *something* meaningful. Not a driver. Not a test module. Real
code.

IOW: "Show me the money".

Because the kernel is *not* some kind of acadmic project. Never has been.

I simply don't want to merge something that is touted as an
alterantive to RCU - which we obviously depend on very very heavily -
without something *major* that actually uses it and shows the
real-world advantages.

The discussion about hazard pointers in the kernel has been around for
a few years by now. If there isn't some real core feature that was
converted to show that, then I think that's already a failure
indication.

I'm hoping that those patches and numbers already exist, and I just
haven't seen them.

                  Linus

Re: [PATCH 01/28] hazptr: Implement Hazard Pointers

[Mathieu Desnoyers]

On 2026-09-19 13:00, Linus Torvalds wrote:
> On Sat, 19 Sept 2026 at 09:35, Bradley Morgan <brads@mainlining.org> wrote:
>>
>> I think hazard pointers are good, what test do YOU suggest we do here?
> 
> I want to see a single real-world example of "look, this speeds this
> real load up by 10%, and the kernel code was actually cleaned up in
> the process because hazard pointers are great".
> 
> Not a microbenchmark that tests just the hazard pointers themselves,
> but a real kernel feature that has been converted to hazard pointers,
> and in the process actually shows improvement.
> 
> The ONLY reason for hazard pointers to ever be merged is if they
> actually buy us something real.
> 
> So I want to see that 'real" thing.
AFAIR, Boqun wanted to use hazard pointers to cleanup/speed up an
hot lockdep reclaim path. Boqun, Paul, how is this effort going ?

I suspect we should wait until that lockdep user of hazptr is ready for
upstreaming and propose both at the same time, because a synchronization
infrastructure without any significant in tree user is not really
relevant, right ?

Thanks,

Mathieu

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

Re: [PATCH 01/28] hazptr: Implement Hazard Pointers

[Mathieu Desnoyers]

On 2026-09-19 13:00, Linus Torvalds wrote:
[...]
> Now, obviously, the thing that would impress me is something like the
> dcache. If *that* can be converted, and it shows real improvements on
> some real benchmark, then I'm sold.

[ Side-discussion, not related to hazard pointers. ]

Talking about dcache improvements:

I've been working on scalability of rename, directory move, and
directory listing, basically killing dcache global locks, seqlocks
and rwlocks which significantly limit dcache update and read-side
scalability.

Those improvements are based on RCU, not hazard pointers, and on a new
"RCU pseudo-transaction" concept I've invented earlier this year.
I'm preparing a paper and I plan to present it at LPC in Prague.
My benchmark results are on a userspace port of the Linux kernel dentry
cache at this point, so it's not ready for anything close to upstream at
this stage.

Cheers,

Mathieu

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

Re: [PATCH 01/28] hazptr: Implement Hazard Pointers

[Paul E. McKenney]

On Sat, Sep 19, 2026 at 05:41:06PM +0100, Bradley Morgan wrote:
> On 19 September 2026 01:00:29 BST, "Paul E. McKenney" <paulmck@kernel.org>
> wrote:
> >From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> >
> >This API provides existence guarantees of objects through Hazard
> >Pointers [1] (hazptr).
> >
> >Its main benefit over RCU is that it allows fast reclaim of
> >HP-protected pointers without needing to wait for a grace period.
> >
> >This implementation has 4 statically allocated hazard pointer slots per
> >cpu for the fast path, and relies on a on-stack backup slot allocated by
> >the hazard pointer user as fallback in case no per-cpu slot is
> >available.
> >
> >It integrates with the scheduler to migrate per-CPU slots to the backup
> >slot on context switch. This ensures that the per-CPU slots won't be
> >used by blocked or preempted tasks holding on hazard pointers for a long
> >time.
> >
> >References:
> >
> >[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
> 
> Sorry for the quick reply, could we add some sort of a maintainers entry
> here?
> 
> I feel as when in like 10 years, there's a huge bug in hazptr, and mat
> can't respond cuz he changes email, then that's not good.

Maged's hazard-pointers implementation works just fine, within its area
of applicability.  As I recall, Boqun and/or Mathieu departed from
it a bit to simplify the lockdep use case.  From the perspective of
this one use case, this simplification is more a restriction than bug.
But Maged would no doubt be quick to point out that from the perspective
of other use cases, this is a bug rather than a simplification.  So it
will likely need to be fixed sooner rather than later.

And Maged is aware of this effort, in fact, I had lunch with him earlier
this week [1].  Every time that I have asked, he has indicated that he
has absolutely no interest in becoming a Linux-kernel maintainer.  ;-)

Which is fair, given that Maged has other fish to fry.

							Thanx, Paul

[1] https://cppcon2026.sched.com/event/2RT65/interesting-upcoming-low-latency-networking-concurrency-and-parallelism-features-from-kona-2025-croydon-2026-and-brno-2026

> >Link: https://lpc.events/event/19/contributions/2082/
> >Link: https://lore.kernel.org/lkml/j3scdl5iymjlxavomgc6u5ndg3svhab6ga23dr36o4f5mt333w@7xslvq6b6hmv/
> >Link: https://lpc.events/event/18/contributions/1731/
> >Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> >Cc: Nicholas Piggin <npiggin@gmail.com>
> >Cc: Michael Ellerman <mpe@ellerman.id.au>
> >Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> >Cc: Sebastian Andrzej Siewior <bigeasy@linutronix.de>
> >Cc: "Paul E. McKenney" <paulmck@kernel.org>
> >Cc: Will Deacon <will@kernel.org>
> >Cc: Peter Zijlstra <peterz@infradead.org>
> >Cc: Boqun Feng <boqun@kernel.org>
> >Cc: Alan Stern <stern@rowland.harvard.edu>
> >Cc: John Stultz <jstultz@google.com>
> >Cc: Linus Torvalds <torvalds@linux-foundation.org>
> >Cc: Andrew Morton <akpm@linux-foundation.org>
> >Cc: Frederic Weisbecker <frederic@kernel.org>
> >Cc: Joel Fernandes <joel@joelfernandes.org>
> >Cc: Josh Triplett <josh@joshtriplett.org>
> >Cc: Uladzislau Rezki <urezki@gmail.com>
> >Cc: Steven Rostedt <rostedt@goodmis.org>
> >Cc: Lai Jiangshan <jiangshanlai@gmail.com>
> >Cc: Zqiang <qiang.zhang1211@gmail.com>
> >Cc: Ingo Molnar <mingo@redhat.com>
> >Cc: Waiman Long <longman@redhat.com>
> >Cc: Mark Rutland <mark.rutland@arm.com>
> >Cc: Thomas Gleixner <tglx@linutronix.de>
> >Cc: Vlastimil Babka <vbabka@suse.cz>
> >Cc: maged.michael@gmail.com
> >Cc: Mateusz Guzik <mjguzik@gmail.com>
> >Cc: Jonas Oberhauser <jonas.oberhauser@huaweicloud.com>
> >Cc: <rcu@vger.kernel.org>
> >Cc: <linux-mm@kvack.org>
> >Cc: <lkmm@lists.linux.dev>
> >Signed-off-by: Paul E. McKenney <paulmck@kernel.org>
> >---
> > include/linux/hazptr.h | 197 +++++++++++++++++++++++++++++++++
> > init/main.c            |   2 +
> > kernel/Makefile        |   2 +-
> > kernel/hazptr.c        | 242 +++++++++++++++++++++++++++++++++++++++++
> > kernel/sched/core.c    |   2 +
> > 5 files changed, 444 insertions(+), 1 deletion(-)
> > create mode 100644 include/linux/hazptr.h
> > create mode 100644 kernel/hazptr.c
> >
> >diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
> >new file mode 100644
> >index 000000000000..b121f7779cda
> >--- /dev/null
> >+++ b/include/linux/hazptr.h
> >@@ -0,0 +1,197 @@
> >+// SPDX-License-Identifier: LGPL-2.1-or-later
> >+//
> >+// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> >+
> >+#ifndef _LINUX_HAZPTR_H
> >+#define _LINUX_HAZPTR_H
> >+
> >+/*
> >+ * hazptr: Hazard Pointers
> >+ *
> >+ * This API provides existence guarantees of objects through hazard
> >+ * pointers.
> >+ *
> >+ * Its main benefit over RCU is that it allows fast reclaim of
> >+ * HP-protected pointers without needing to wait for a grace period.
> >+ *
> >+ * References:
> >+ *
> >+ * [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/percpu.h>
> >+#include <linux/types.h>
> >+#include <linux/cleanup.h>
> >+#include <linux/sched.h>
> >+
> >+/* 4 slots (each sizeof(hazptr_slot_item)) fit in a single 64-byte cache line. */
> >+#define NR_HAZPTR_PERCPU_SLOTS	4
> >+#define HAZPTR_WILDCARD		((void *) 0x1UL)
> >+
> >+/*
> >+ * Hazard pointer slot.
> >+ */
> >+struct hazptr_slot {
> >+	void *addr;
> >+};
> >+
> >+struct hazptr_overflow_list;
> >+
> >+struct hazptr_backup_slot {
> >+	struct hlist_node overflow_node;
> >+	struct hazptr_slot slot;
> >+	/* Overflow list where the backup slot is added. */
> >+	struct hazptr_overflow_list *overflow_list;
> >+};
> >+
> >+struct hazptr_ctx {
> >+	struct hazptr_slot *slot;
> >+	/* Backup slot in case all per-CPU slots are used. */
> >+	struct hazptr_backup_slot backup_slot;
> >+	struct hlist_node preempt_node;
> >+};
> >+
> >+struct hazptr_slot_ctx {
> >+	struct hazptr_ctx *ctx;
> >+};
> >+
> >+struct hazptr_slot_item {
> >+	struct hazptr_slot slot;
> >+	struct hazptr_slot_ctx ctx;
> >+};
> >+
> >+struct hazptr_percpu_slots {
> >+	struct hazptr_slot_item items[NR_HAZPTR_PERCPU_SLOTS];
> >+} ____cacheline_aligned;
> >+
> >+DECLARE_PER_CPU(struct hazptr_percpu_slots, hazptr_percpu_slots);
> >+
> >+void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p);
> >+
> >+/*
> >+ * hazptr_synchronize: Wait until @addr is released from all slots.
> >+ *
> >+ * Wait to observe that each slot contains a value that differs from
> >+ * @addr before returning.
> >+ * Should be called from preemptible context.
> >+ */
> >+void hazptr_synchronize(void *addr);
> >+
> >+/*
> >+ * hazptr_chain_backup_slot: Chain backup slot into overflow list.
> >+ *
> >+ * Set backup slot address to @addr, and chain it into the overflow
> >+ * list.
> >+ */
> >+struct hazptr_slot *hazptr_chain_backup_slot(struct hazptr_ctx *ctx);
> >+
> >+/*
> >+ * hazptr_unchain_backup_slot: Unchain backup slot from overflow list.
> >+ */
> >+void hazptr_unchain_backup_slot(struct hazptr_ctx *ctx);
> >+
> >+static inline
> >+bool hazptr_slot_is_backup(struct hazptr_ctx *ctx, struct hazptr_slot *slot)
> >+{
> >+	return slot == &ctx->backup_slot.slot;
> >+}
> >+
> >+static inline
> >+void hazptr_note_context_switch(void)
> >+{
> >+	struct hazptr_percpu_slots *percpu_slots = this_cpu_ptr(&hazptr_percpu_slots);
> >+	unsigned int idx;
> >+
> >+	for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> >+		struct hazptr_slot_item *item = &percpu_slots->items[idx];
> >+		struct hazptr_slot *slot = &item->slot, *backup_slot;
> >+		struct hazptr_ctx *ctx;
> >+
> >+		if (!slot->addr)
> >+			continue;
> >+		ctx = item->ctx.ctx;
> >+		backup_slot = hazptr_chain_backup_slot(ctx);
> >+		/*
> >+		 * Move hazard pointer from the per-CPU slot to the
> >+		 * backup slot. This requires hazard pointer
> >+		 * synchronize to iterate on per-CPU slots with
> >+		 * load-acquire before iterating on the overflow list.
> >+		 */
> >+		WRITE_ONCE(backup_slot->addr, slot->addr);
> >+		/*
> >+		 * store-release orders store to backup slot addr before
> >+		 * store to per-CPU slot addr.
> >+		 */
> >+		smp_store_release(&slot->addr, NULL);
> >+		/* Use the backup slot for context. */
> >+		ctx->slot = backup_slot;
> >+	}
> >+}
> >+
> >+/*
> >+ * hazptr_acquire: Load pointer at address and protect with hazard pointer.
> >+ *
> >+ * Load @addr_p, and protect the loaded pointer with hazard pointer.
> >+ * When using hazptr_acquire from interrupt handlers, the acquired slots
> >+ * need to be released before returning from the interrupt handler.
> >+ *
> >+ * Returns a non-NULL protected address if the loaded pointer is non-NULL.
> >+ * Returns NULL if the loaded pointer is NULL.
> >+ *
> >+ * On success the protected hazptr slot is stored in @ctx->slot.
> >+ */
> >+static inline
> >+void *hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
> >+{
> >+	struct hazptr_percpu_slots *percpu_slots;
> >+	struct hazptr_slot_item *slot_item;
> >+	struct hazptr_slot *slot;
> >+	void *addr;
> >+
> >+	guard(preempt)();
> >+	percpu_slots = this_cpu_ptr(&hazptr_percpu_slots);
> >+	slot_item = &percpu_slots->items[0];
> >+	slot = &slot_item->slot;
> >+	if (unlikely(slot->addr))
> >+		return __hazptr_acquire(ctx, addr_p);
> >+	WRITE_ONCE(slot->addr, HAZPTR_WILDCARD);	/* Store B */
> >+
> >+	/* Memory ordering: Store B before Load A. */
> >+	smp_mb();
> >+
> >+	/*
> >+	 * Load @addr_p after storing wildcard to the hazard pointer slot.
> >+	 */
> >+	addr = READ_ONCE(*addr_p);	/* Load A */
> >+
> >+	/*
> >+	 * We don't care about ordering of Store C. It will simply
> >+	 * replace the wildcard by a more specific address. If addr is
> >+	 * NULL, we simply store NULL into the slot.
> >+	 */
> >+	WRITE_ONCE(slot->addr, addr);	/* Store C */
> >+	slot_item->ctx.ctx = ctx;
> >+	ctx->slot = slot;
> >+	return addr;
> >+}
> >+
> >+/* Release the protected hazard pointer from @slot. */
> >+static inline
> >+void hazptr_release(struct hazptr_ctx *ctx, void *addr)
> >+{
> >+	struct hazptr_slot *slot;
> >+
> >+	if (!addr)
> >+		return;
> >+	guard(preempt)();
> >+	slot = ctx->slot;
> >+	smp_store_release(&slot->addr, NULL);
> >+	if (unlikely(hazptr_slot_is_backup(ctx, slot)))
> >+		hazptr_unchain_backup_slot(ctx);
> >+}
> >+
> >+void hazptr_init(void);
> >+
> >+#endif /* _LINUX_HAZPTR_H */
> >diff --git a/init/main.c b/init/main.c
> >index 2613d3f9b3ce..d9d936707c19 100644
> >--- a/init/main.c
> >+++ b/init/main.c
> >@@ -108,6 +108,7 @@
> > #include <linux/time_namespace.h>
> > #include <linux/unaligned.h>
> > #include <linux/vdso_datastore.h>
> >+#include <linux/hazptr.h>
> > #include <net/net_namespace.h>
> > 
> > #include <asm/io.h>
> >@@ -1075,6 +1076,7 @@ void start_kernel(void)
> > 	workqueue_init_early();
> > 
> > 	rcu_init();
> >+	hazptr_init();
> > 	kvfree_rcu_init();
> > 
> > 	/* Trace events are available after this */
> >diff --git a/kernel/Makefile b/kernel/Makefile
> >index 1e1a31673577..8961c8660d0d 100644
> >--- a/kernel/Makefile
> >+++ b/kernel/Makefile
> >@@ -7,7 +7,7 @@ obj-y     = fork.o exec_domain.o exec_state.o panic.o \
> > 	    cpu.o exit.o softirq.o resource.o \
> > 	    sysctl.o capability.o ptrace.o user.o \
> > 	    signal.o sys.o umh.o workqueue.o pid.o task_work.o \
> >-	    extable.o params.o \
> >+	    extable.o params.o hazptr.o \
> > 	    kthread.o sys_ni.o nsproxy.o nstree.o nscommon.o \
> > 	    notifier.o ksysfs.o cred.o reboot.o \
> > 	    async.o range.o smpboot.o ucount.o regset.o ksyms_common.o
> >diff --git a/kernel/hazptr.c b/kernel/hazptr.c
> >new file mode 100644
> >index 000000000000..a9d3d68a1525
> >--- /dev/null
> >+++ b/kernel/hazptr.c
> >@@ -0,0 +1,242 @@
> >+// SPDX-License-Identifier: LGPL-2.1-or-later
> >+//
> >+// SPDX-FileCopyrightText: 2024 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> >+
> >+/*
> >+ * hazptr: Hazard Pointers
> >+ */
> >+
> >+#include <linux/hazptr.h>
> >+#include <linux/percpu.h>
> >+#include <linux/spinlock.h>
> >+#include <linux/mutex.h>
> >+#include <linux/list.h>
> >+#include <linux/export.h>
> >+
> >+struct hazptr_overflow_list {
> >+	raw_spinlock_t lock;		/* Lock protecting overflow list and list generation. */
> >+	struct hlist_head head;		/* Overflow list head. */
> >+	uint64_t gen;			/* Overflow list generation. */
> >+};
> >+
> >+/*
> >+ * Flip between two lists to guarantee list scan forward progress even
> >+ * with frequent generation counter increments. The list additions are
> >+ * always done on a different list than the one used for scan. The scan
> >+ * successively iterates on both lists. Therefore, only list removals
> >+ * can cause the iteration to retry, and the number of removals is
> >+ * limited to the number of list elements.
> >+ */
> >+struct hazptr_overflow_list_flip {
> >+	struct mutex lock;		/* Mutex protecting add_idx from concurrent updates. */
> >+	unsigned int add_idx;		/* Index of current flip-list to add to. */
> >+	struct hazptr_overflow_list array[2];
> >+};
> >+
> >+static DEFINE_PER_CPU(struct hazptr_overflow_list_flip, percpu_overflow_list_flip);
> >+
> >+DEFINE_PER_CPU(struct hazptr_percpu_slots, hazptr_percpu_slots);
> >+EXPORT_PER_CPU_SYMBOL_GPL(hazptr_percpu_slots);
> >+
> >+static
> >+struct hazptr_slot *hazptr_get_free_percpu_slot(struct hazptr_ctx *ctx)
> >+{
> >+	struct hazptr_percpu_slots *percpu_slots = this_cpu_ptr(&hazptr_percpu_slots);
> >+	unsigned int idx;
> >+
> >+	for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> >+		struct hazptr_slot_item *item = &percpu_slots->items[idx];
> >+		struct hazptr_slot *slot = &item->slot;
> >+
> >+		if (!slot->addr) {
> >+			item->ctx.ctx = ctx;
> >+			return slot;
> >+		}
> >+	}
> >+	/* All slots are in use. */
> >+	return NULL;
> >+}
> >+
> >+/*
> >+ * Hazard pointer acquire slow path.
> >+ * Called with preemption disabled.
> >+ */
> >+void *__hazptr_acquire(struct hazptr_ctx *ctx, void * const *addr_p)
> >+{
> >+	struct hazptr_slot *slot = hazptr_get_free_percpu_slot(ctx);
> >+	void *addr;
> >+
> >+	/*
> >+	 * If all the per-CPU slots are already in use, fallback
> >+	 * to the backup slot.
> >+	 */
> >+	if (unlikely(!slot))
> >+		slot = hazptr_chain_backup_slot(ctx);
> >+	WRITE_ONCE(slot->addr, HAZPTR_WILDCARD);	/* Store B */
> >+
> >+	/* Memory ordering: Store B before Load A. */
> >+	smp_mb();
> >+
> >+	/*
> >+	 * Load @addr_p after storing wildcard to the hazard pointer slot.
> >+	 */
> >+	addr = READ_ONCE(*addr_p);	/* Load A */
> >+
> >+	/*
> >+	 * We don't care about ordering of Store C. It will simply
> >+	 * replace the wildcard by a more specific address. If addr is
> >+	 * NULL, we simply store NULL into the slot.
> >+	 */
> >+	WRITE_ONCE(slot->addr, addr);	/* Store C */
> >+	ctx->slot = slot;
> >+	if (!addr && hazptr_slot_is_backup(ctx, slot))
> >+		hazptr_unchain_backup_slot(ctx);
> >+	return addr;
> >+}
> >+EXPORT_SYMBOL_GPL(__hazptr_acquire);
> >+
> >+/*
> >+ * Perform piecewise iteration on overflow list waiting until "addr" is
> >+ * not present. Raw spinlock is released and taken between each list
> >+ * item and busy loop iteration. The overflow list generation is checked
> >+ * each time the lock is taken to validate that the list has not changed
> >+ * before resuming iteration or busy wait. If the generation has
> >+ * changed, retry the entire list traversal.
> >+ */
> >+static
> >+void hazptr_synchronize_overflow_list(struct hazptr_overflow_list *overflow_list, void *addr)
> >+{
> >+	struct hazptr_backup_slot *backup_slot;
> >+	uint64_t snapshot_gen;
> >+	unsigned long flags;
> >+
> >+	raw_spin_lock_irqsave(&overflow_list->lock, flags);
> >+retry:
> >+	snapshot_gen = overflow_list->gen;
> >+	hlist_for_each_entry(backup_slot, &overflow_list->head, overflow_node) {
> >+		/* Busy-wait if node is found. */
> >+		for (;;) {
> >+			void *load_addr = smp_load_acquire(&backup_slot->slot.addr);	/* Load B */
> >+
> >+			if (load_addr != addr && load_addr != HAZPTR_WILDCARD)
> >+				break;
> >+			raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
> >+			cpu_relax();
> >+			raw_spin_lock_irqsave(&overflow_list->lock, flags);
> >+			if (overflow_list->gen != snapshot_gen)
> >+				goto retry;
> >+		}
> >+		raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
> >+		/*
> >+		 * Release raw spinlock, validate generation after
> >+		 * re-acquiring the lock.
> >+		 */
> >+		raw_spin_lock_irqsave(&overflow_list->lock, flags);
> >+		if (overflow_list->gen != snapshot_gen)
> >+			goto retry;
> >+	}
> >+	raw_spin_unlock_irqrestore(&overflow_list->lock, flags);
> >+}
> >+
> >+static
> >+void hazptr_synchronize_cpu_slots(int cpu, void *addr)
> >+{
> >+	struct hazptr_percpu_slots *percpu_slots = per_cpu_ptr(&hazptr_percpu_slots, cpu);
> >+	unsigned int idx;
> >+
> >+	for (idx = 0; idx < NR_HAZPTR_PERCPU_SLOTS; idx++) {
> >+		struct hazptr_slot_item *item = &percpu_slots->items[idx];
> >+
> >+		/* Busy-wait if node is found. */
> >+		smp_cond_load_acquire(&item->slot.addr, VAL != addr && VAL != HAZPTR_WILDCARD); /* Load B */
> >+	}
> >+}
> >+
> >+/*
> >+ * hazptr_synchronize: Wait until @addr is released from all slots.
> >+ *
> >+ * Wait to observe that each slot contains a value that differs from
> >+ * @addr before returning.
> >+ * Should be called from preemptible context.
> >+ */
> >+void hazptr_synchronize(void *addr)
> >+{
> >+	int cpu;
> >+
> >+	/*
> >+	 * Busy-wait should only be done from preemptible context.
> >+	 */
> >+	lockdep_assert_preemption_enabled();
> >+
> >+	/*
> >+	 * Store A precedes hazptr_scan(): it unpublishes addr (sets it to
> >+	 * NULL or to a different value), and thus hides it from hazard
> >+	 * pointer readers.
> >+	 */
> >+	if (!addr)
> >+		return;
> >+	/* Memory ordering: Store A before Load B. */
> >+	smp_mb();
> >+	/* Scan all CPUs slots. */
> >+	for_each_possible_cpu(cpu) {
> >+		struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu);
> >+		unsigned int scan_idx;
> >+
> >+		/* Scan CPU slots. */
> >+		hazptr_synchronize_cpu_slots(cpu, addr);
> >+
> >+		/*
> >+		 * Scan backup slots in percpu overflow lists.
> >+		 * Forward progress is guaranteed by scanning one list
> >+		 * while new elements are added into the other list.
> >+		 */
> >+		guard(mutex)(&overflow_list_flip->lock);
> >+		scan_idx = overflow_list_flip->add_idx ^ 1;
> >+		hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx], addr);
> >+		/* Flip current list. */
> >+		WRITE_ONCE(overflow_list_flip->add_idx, scan_idx);
> >+		hazptr_synchronize_overflow_list(&overflow_list_flip->array[scan_idx ^ 1], addr);
> >+	}
> >+}
> >+EXPORT_SYMBOL_GPL(hazptr_synchronize);
> >+
> >+struct hazptr_slot *hazptr_chain_backup_slot(struct hazptr_ctx *ctx)
> >+{
> >+	struct hazptr_overflow_list_flip *overflow_list_flip = this_cpu_ptr(&percpu_overflow_list_flip);
> >+	unsigned int list_idx = READ_ONCE(overflow_list_flip->add_idx);
> >+	struct hazptr_overflow_list *overflow_list = &overflow_list_flip->array[list_idx];
> >+	struct hazptr_slot *slot = &ctx->backup_slot.slot;
> >+
> >+	slot->addr = NULL;
> >+	guard(raw_spinlock_irqsave)(&overflow_list->lock);
> >+	overflow_list->gen++;
> >+	hlist_add_head(&ctx->backup_slot.overflow_node, &overflow_list->head);
> >+	ctx->backup_slot.overflow_list = overflow_list;
> >+	return slot;
> >+}
> >+EXPORT_SYMBOL_GPL(hazptr_chain_backup_slot);
> >+
> >+void hazptr_unchain_backup_slot(struct hazptr_ctx *ctx)
> >+{
> >+	struct hazptr_overflow_list *overflow_list = ctx->backup_slot.overflow_list;
> >+
> >+	guard(raw_spinlock_irqsave)(&overflow_list->lock);
> >+	overflow_list->gen++;
> >+	hlist_del(&ctx->backup_slot.overflow_node);
> >+}
> >+EXPORT_SYMBOL_GPL(hazptr_unchain_backup_slot);
> >+
> >+void __init hazptr_init(void)
> >+{
> >+	int cpu;
> >+
> >+	for_each_possible_cpu(cpu) {
> >+		struct hazptr_overflow_list_flip *overflow_list_flip = per_cpu_ptr(&percpu_overflow_list_flip, cpu);
> >+
> >+		mutex_init(&overflow_list_flip->lock);
> >+		for (int i = 0; i < 2; i++) {
> >+			raw_spin_lock_init(&overflow_list_flip->array[i].lock);
> >+			INIT_HLIST_HEAD(&overflow_list_flip->array[i].head);
> >+		}
> >+	}
> >+}
> >diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> >index f78275192036..b77152edafd9 100644
> >--- a/kernel/sched/core.c
> >+++ b/kernel/sched/core.c
> >@@ -59,6 +59,7 @@
> > #include <linux/profile.h>
> > #include <linux/psi.h>
> > #include <linux/rcuwait_api.h>
> >+#include <linux/hazptr.h>
> > #include <linux/rseq.h>
> > #include <linux/sched/wake_q.h>
> > #include <linux/scs.h>
> >@@ -7123,6 +7124,7 @@ static void __sched notrace __schedule(int sched_mode)
> > 	local_irq_disable();
> > 	rcu_note_context_switch(preempt);
> > 	migrate_disable_switch(rq, prev);
> >+	hazptr_note_context_switch();
> > 
> > 	/*
> > 	 * Make sure that signal_pending_state()->signal_pending() below
> >
> 
> --- Thanks!
> "I'm not a very positive person" - Linus torvalds

Re: [PATCH 01/28] hazptr: Implement Hazard Pointers

[Boqun Feng]

On Sat, Sep 19, 2026 at 01:09:15PM -0400, Mathieu Desnoyers wrote:
> On 2026-09-19 13:00, Linus Torvalds wrote:
> > On Sat, 19 Sept 2026 at 09:35, Bradley Morgan <brads@mainlining.org> wrote:
> > > 
> > > I think hazard pointers are good, what test do YOU suggest we do here?
> > 
> > I want to see a single real-world example of "look, this speeds this
> > real load up by 10%, and the kernel code was actually cleaned up in
> > the process because hazard pointers are great".
> > 
> > Not a microbenchmark that tests just the hazard pointers themselves,
> > but a real kernel feature that has been converted to hazard pointers,
> > and in the process actually shows improvement.
> > 
> > The ONLY reason for hazard pointers to ever be merged is if they
> > actually buy us something real.
> > 
> > So I want to see that 'real" thing.
> AFAIR, Boqun wanted to use hazard pointers to cleanup/speed up an

Right, that's why I send this series:

	https://lore.kernel.org/lkml/20250625031101.12555-1-boqun.feng@gmail.com/

The gist of that work is basically:

	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, i.e. using RCU)
		real    0m1.039s
		user    0m0.001s
		sys     0m0.069s

		(with the patchset, i.e. using hazptr)
		real    0m0.053s
		user    0m0.000s
		sys     0m0.051s

i.e. almost 20x speed-up.

One important thing that I want to point out is in that series, I
avoided the busy-waiting in hazptr_synchronize() and made multiple
hazptr_synchronize()s share the same scan. And I do want to see this in
the new code. But unfortunately with the new implementation, we don't
have that part yet. And that's what holds me from trying lockdep
integration for this new implementation.

I could have improved my skill of time management, because I know at
certain point I said "I will finish the scan thread work for your
implementation", but it'll be helpful if you or someone can help get
that done.

> hot lockdep reclaim path. Boqun, Paul, how is this effort going ?
> 
> I suspect we should wait until that lockdep user of hazptr is ready for
> upstreaming and propose both at the same time, because a synchronization
> infrastructure without any significant in tree user is not really
> relevant, right ?
> 

The other thing we could also do is what I did in shazptr, getting the
numbers with rcuscale, that can tell use the actual waiting time for a
hazptr_synchronize().

Regards,
Boqun

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

Re: [PATCH 01/28] hazptr: Implement Hazard Pointers

[Paul E. McKenney]

On Sat, Sep 19, 2026 at 10:00:06AM -0700, Linus Torvalds wrote:
> On Sat, 19 Sept 2026 at 09:35, Bradley Morgan <brads@mainlining.org> wrote:
> >
> > I think hazard pointers are good, what test do YOU suggest we do here?
> 
> I want to see a single real-world example of "look, this speeds this
> real load up by 10%, and the kernel code was actually cleaned up in
> the process because hazard pointers are great".
> 
> Not a microbenchmark that tests just the hazard pointers themselves,
> but a real kernel feature that has been converted to hazard pointers,
> and in the process actually shows improvement.
> 
> The ONLY reason for hazard pointers to ever be merged is if they
> actually buy us something real.
> 
> So I want to see that 'real" thing.
> 
> I want to see how easy/hard it is to actually convert a real current
> user, and I want to see how it actually results in measurable
> improvements in performance.
> 
> Something *core*. Something that everybody uses. Because I'm not in
> the least interested in a new subtle feature that interacts with the
> scheduler and is only used for some random driver or (to pick the only
> example I have ever seen) AppArmor.

Just a historical note for those who were not around at the time.

Linus had a similar healthy skepticism of RCU back in the day, and
we (well, mostly Dipankar Sarma) did deliver the required use cases
and performance results.  It took about two years, with the earliest
discussions at OLS 2000.

And I won't be sending a hazard-pointer pull request to Linus unless and
until we have something convincing.  And if I turn out to be easier to
convince than Linus is, I am sure that he will let me know.  ;-)

> Now, obviously, the thing that would impress me is something like the
> dcache. If *that* can be converted, and it shows real improvements on
> some real benchmark, then I'm sold.

And yes, the reason that I am pushing this is that some corner cases are
stressing RCU a bit, and perhaps hazard pointers can do a better job of
addressing these situations.  And maybe dcache is one of those corner
cases, but it would not be first on my list, in part because hazard
pointers tends to have a bit higher read-side overhead than does RCU.
And I don't see a way that hazard pointers could eliminate dcache's use
of seqlock.

The most obvious potential hazard-pointers use case is where someone
wanted to use per-CPU reference counts, but couldn't due to the high
memory footprint of all those per-CPU counters.  With a key word being
"potential" because I don't know of such a use case.

But if one shows up on an emergency basis, I want at least a prototype
of a ready solution.  After all, the Linux kernel is a *lot* less
bug-tolerant than it was in the early RCU days.

> Now, I don't really expect that kind of major test-case, but I do
> expect *something* meaningful. Not a driver. Not a test module. Real
> code.
> 
> IOW: "Show me the money".
> 
> Because the kernel is *not* some kind of acadmic project. Never has been.
> 
> I simply don't want to merge something that is touted as an
> alterantive to RCU - which we obviously depend on very very heavily -
> without something *major* that actually uses it and shows the
> real-world advantages.
> 
> The discussion about hazard pointers in the kernel has been around for
> a few years by now. If there isn't some real core feature that was
> converted to show that, then I think that's already a failure
> indication.

That is of course completely fair.

And there are a couple of potential hazard-pointers use cases that have a
reasonable chance of working out.  If something compelling does show up,
you will of course see a pull request.  If not, maybe I maintain hazard
pointers out of tree for a few more years and then drop it.  (At which
point, Murphy being who he is, a use case would promptly appear.)

> I'm hoping that those patches and numbers already exist, and I just
> haven't seen them.

There are some, but not yet compelling.  This is still a work in progress.

So why bother you with premature hazard-pointer patches?

Because if a hazard-pointers-shaped problem does show up in the kernel
somewhere outside of my admittedly narrow field of view, it would be
good if you were aware.

							Thanx, Paul