On 19 September 2026 01:00:29 BST, "Paul E. McKenney" <[email protected]> wrote: >From: Mathieu Desnoyers <[email protected]> > >This API provides existence guarantees of objects through Hazard >Pointers [1] (hazptr). >
Hi, could I add my tag here? >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 <[email protected]> >Cc: Nicholas Piggin <[email protected]> >Cc: Michael Ellerman <[email protected]> >Cc: Greg Kroah-Hartman <[email protected]> >Cc: Sebastian Andrzej Siewior <[email protected]> >Cc: "Paul E. McKenney" <[email protected]> >Cc: Will Deacon <[email protected]> >Cc: Peter Zijlstra <[email protected]> >Cc: Boqun Feng <[email protected]> >Cc: Alan Stern <[email protected]> >Cc: John Stultz <[email protected]> >Cc: Linus Torvalds <[email protected]> >Cc: Andrew Morton <[email protected]> >Cc: Frederic Weisbecker <[email protected]> >Cc: Joel Fernandes <[email protected]> >Cc: Josh Triplett <[email protected]> >Cc: Uladzislau Rezki <[email protected]> >Cc: Steven Rostedt <[email protected]> >Cc: Lai Jiangshan <[email protected]> >Cc: Zqiang <[email protected]> >Cc: Ingo Molnar <[email protected]> >Cc: Waiman Long <[email protected]> >Cc: Mark Rutland <[email protected]> >Cc: Thomas Gleixner <[email protected]> >Cc: Vlastimil Babka <[email protected]> >Cc: [email protected] >Cc: Mateusz Guzik <[email protected]> >Cc: Jonas Oberhauser <[email protected]> >Cc: <[email protected]> >Cc: <[email protected]> >Cc: <[email protected]> >Signed-off-by: Paul E. McKenney <[email protected]> >--- > 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 ><[email protected]> >+ >+#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 ><[email protected]> >+ >+/* >+ * 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! https://lore.kernel.org/all/[email protected]/
