Merge branch 'non-rcu/next' of https://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git

3 files changed, 414 insertions, 1 deletions

diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
new file mode 100644
index 000000000000..d37792af3493
--- /dev/null
+++ b/include/linux/hazptr.h
@@ -0,0 +1,346 @@
+// 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>
+#include <linux/ptr_eq.h>
+
+/* 4 slots (each sizeof(hazptr_slot_item)) fit in a single 64-byte cache line. */
+#define NR_HAZPTR_PERCPU_SLOTS	4
+
+/*
+ * 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;
+#ifdef CONFIG_HAZPTR_DEBUG
+	bool detach_task, detach_cpu;	/* Whether the ctx has been detached from task/cpu. */
+	int acquire_pid, acquire_cpu;	/* Note the task and cpu number at acquire. */
+	unsigned long acquire_caller;	/* Acquire instruction pointer. */
+#endif
+};
+
+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 for release from hazard-pointer protection
+ *
+ * @addr: The address to be released from hazard-pointer protection
+ *
+ * Wait for the specified @addr to be released from protection from all
+ * hazard pointers.  The caller should make @addr inaccessible to all
+ * hazard-pointer readers before invoking this function.
+ *
+ * Must 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;
+}
+
+/* Internal helper. */
+static inline
+void hazptr_promote_to_backup_slot(struct hazptr_ctx *ctx, struct hazptr_slot *slot)
+{
+	struct hazptr_slot *backup_slot;
+
+	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_detach - Allow a hazard pointer to be released in some other context
+ *
+ * @ctx: The hazard-pointer context to be detached.
+ *
+ * By default, a given hazptr_acquire() and the corresponding
+ * hazptr_release() must run in a single execution context, for example,
+ * the context of a single task or a single interrupt handler.  When you
+ * have acquired a hazard pointer in one context and need to release it
+ * in another, you must invoke hazptr_detach() on that hazard pointer's
+ * context.  It is permissible to invoke hazptr_detach() multiple times
+ * on the same @ctx while it is protecting the same pointer, however,
+ * the first invocation absolutely must be in the same context that did
+ * the hazptr_acquire(), and must take place after the return from that
+ * hazptr_acquire().
+ *
+ * For example, if a hazard pointer is acquired by a task and released
+ * by a timer handler, that task would need to pass the hazard pointer's
+ * context to hazptr_detach() after return from the hazptr_acquire() and
+ * before arming the timer (or at least before the handler had a chance
+ * to access that hazard-pointer context).
+ */
+static inline
+void hazptr_detach(struct hazptr_ctx *ctx)
+{
+	struct hazptr_slot *slot;
+
+	guard(preempt)();
+	slot = ctx->slot;
+	if (!slot->addr)
+		return;
+#ifdef CONFIG_HAZPTR_DEBUG
+	ctx->detach_task = ctx->detach_cpu = true;
+#endif
+	if (unlikely(hazptr_slot_is_backup(ctx, slot)))
+		return;
+	hazptr_promote_to_backup_slot(ctx, 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;
+
+		if (!slot->addr)
+			continue;
+#ifdef CONFIG_HAZPTR_DEBUG
+		WARN_ONCE(item->ctx.ctx->slot != slot,
+			"Hazard Pointer (addr=%p) in per-CPU slot %u recorded with an owner that uses another slot.",
+			slot->addr, idx);
+		item->ctx.ctx->detach_cpu = true;
+#endif
+		hazptr_promote_to_backup_slot(item->ctx.ctx, slot);
+	}
+}
+
+/* Try hazard pointer protection. */
+static inline
+void *__hazptr_try_acquire(struct hazptr_ctx *ctx, void * const *addr_p, struct hazptr_slot *slot)
+{
+	void *early_addr, *addr;
+
+	if (unlikely(slot->addr))
+		return NULL;
+	early_addr = READ_ONCE(*addr_p);	/* Early load. */
+	WRITE_ONCE(slot->addr, early_addr);	/* Store B */
+	/* Memory ordering: Store B before Load A. */
+	smp_mb();
+	addr = READ_ONCE(*addr_p);		/* Load A */
+	/*
+	 * Validate that address did not change between Early load and Load A.
+	 * Use ptr_eq() to make sure that result from Load A is returned to the
+	 * caller to preserve address dependency.
+	 */
+	if (unlikely(!ptr_eq(addr, early_addr))) {
+		WRITE_ONCE(slot->addr, NULL);
+		return NULL;
+	}
+	return addr;
+}
+
+/**
+ * hazptr_acquire - Load pointer at address and protect with hazard pointer.
+ *
+ * @ctx: The hazard-pointer context to be passed to hazptr_release().
+ * @addr_p: Pointer to the pointer that is to be hazard-pointer protected.
+ *
+ * Load @addr_p, and protect the loaded pointer with hazard pointer.
+ * This protection is roughly similar to (but way faster than) that of a
+ * reference counter, and ends with a later call to hazptr_release().
+ *
+ * This protection is unconditional, and has limitations similar to
+ * that of unconditional reference-counter acquisition.  In particular,
+ * although holding a hazard pointer prevents a hazard-pointer-protected
+ * object from being freed, it does not prevent that object from being
+ * removed from a linked data structure, and does not prevent other
+ * hazard-pointer-protected objects referenced by this object from being
+ * both removed and freed.  At which point, invoking hazptr_acquire()
+ * on these dangling pointers would be a bug.  On the other hand, use of
+ * hazptr_acquire() is safe for immortal pointers to objects that do not
+ * themselves contain pointers to hazard-pointer-protected objects.
+ * Other (more complex) use cases are also possible.
+ *
+ * By default, the call to hazptr_release() must be running in the same
+ * execution context as the corresponding hazptr_acquire(), for example,
+ * within the same task or interrupt handler.  When it is necessary to
+ * instead call hazptr_release() from some other context, pass @ctx to
+ * hazptr_detach() in the original context after invoking hazptr_acquire()
+ * but before making the hazard pointer available to that other context.
+ *
+ * It is not permissible to invoke hazptr_acquire() twice on the same @ctx
+ * without an intervening hazptr_release().
+ *
+ * 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;
+#ifdef CONFIG_HAZPTR_DEBUG
+	ctx->detach_cpu = ctx->detach_task = false;
+	ctx->acquire_pid = current->pid;
+	ctx->acquire_cpu = smp_processor_id();
+	ctx->acquire_caller = _THIS_IP_;
+#endif
+	addr = __hazptr_try_acquire(ctx, addr_p, slot);
+	if (unlikely(!addr))
+		return __hazptr_acquire(ctx, addr_p);
+	slot_item->ctx.ctx = ctx;
+	ctx->slot = slot;
+	return addr;
+}
+
+#ifdef CONFIG_HAZPTR_DEBUG
+/* Called with preemption disabled. */
+static inline
+void hazptr_release_debug(struct hazptr_ctx *ctx, void *addr)
+{
+	int pid = current->pid, cpu = smp_processor_id();
+	bool warn_remote_cpu = !ctx->detach_cpu && ctx->acquire_cpu != cpu,
+	     warn_remote_task = !ctx->detach_task && ctx->acquire_pid != pid;
+	struct hazptr_slot *slot = ctx->slot;
+	struct hazptr_slot_item *item;
+
+	WARN_ONCE(warn_remote_cpu || warn_remote_task,
+		"Hazard Pointer (addr=%p) released on remote %s without %s. Acquire: caller=%pS, pid=%d, cpu=%d. Release: pid=%d, cpu=%d.",
+		addr,
+		warn_remote_task ? "task" : "cpu",
+		warn_remote_task ? "being detached from task" : "context switch",
+		(void *) ctx->acquire_caller, ctx->acquire_pid, ctx->acquire_cpu, pid, cpu);
+
+	if (hazptr_slot_is_backup(ctx, slot) || !READ_ONCE(slot->addr))
+		return;
+	/* Whoever claimed a per-CPU slot must be recorded as its owner. */
+	item = container_of(slot, struct hazptr_slot_item, slot);
+	WARN_ONCE(item->ctx.ctx != ctx,
+		"Hazard Pointer (addr=%p) released from a per-CPU slot recorded with another owner. Acquire: caller=%pS, pid=%d, cpu=%d.",
+		addr, (void *) ctx->acquire_caller, ctx->acquire_pid, ctx->acquire_cpu);
+}
+#else
+static inline void hazptr_release_debug(struct hazptr_ctx *ctx, void *addr) { }
+#endif
+
+/**
+ * hazptr_release - Release the specified hazard pointer
+ *
+ * @ctx: The hazard-pointer context that was passed to hazptr_acquire().
+ * @addr_p: The pointer that is to be hazard-pointer unprotected.
+ *
+ * Release the protected hazard pointer recorded in @ctx.
+ *
+ * By default, hazptr_release() must execute in the same execution context
+ * that invoked the corresponding hazptr_acquire(), for example, within the
+ * same task or the same interrupt handler.  However, if this restriction
+ * is problematic for your use case, please see hazptr_detach().
+ *
+ * It is permissible (though unwise from a maintainability viewpoint)
+ * to invoke hazptr_release() twice on the same @ctx without an intervening
+ * hazptr_acquire().
+ */
+static inline
+void hazptr_release(struct hazptr_ctx *ctx, void *addr)
+{
+	struct hazptr_slot *slot;
+
+	if (!addr)
+		return;
+	guard(preempt)();
+	hazptr_release_debug(ctx, addr);
+	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/include/linux/ptr_eq.h b/include/linux/ptr_eq.h
new file mode 100644
index 000000000000..7a2bbf6e64b3
--- /dev/null
+++ b/include/linux/ptr_eq.h
@@ -0,0 +1,63 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _LINUX_PTR_EQ_H
+#define _LINUX_PTR_EQ_H
+
+/*
+ * Compare two addresses while preserving the address dependencies for
+ * later use of the address. It should be used when comparing an address
+ * returned by rcu_dereference().
+ *
+ * This is needed to prevent the compiler CSE and SSA GVN optimizations
+ * from using @a (or @b) in places where the source refers to @b (or @a)
+ * based on the fact that after the comparison, the two are known to be
+ * equal, which does not preserve address dependencies and allows the
+ * following misordering speculations:
+ *
+ * - If @b is a constant, the compiler can issue the loads which depend
+ *   on @a before loading @a.
+ * - If @b is a register populated by a prior load, weakly-ordered
+ *   CPUs can speculate loads which depend on @a before loading @a.
+ *
+ * The same logic applies with @a and @b swapped.
+ *
+ * Return value: true if pointers are equal, false otherwise.
+ *
+ * The compiler barrier() is ineffective at fixing this issue. It does
+ * not prevent the compiler CSE from losing the address dependency:
+ *
+ * int fct_2_volatile_barriers(void)
+ * {
+ *     int *a, *b;
+ *
+ *     do {
+ *         a = READ_ONCE(p);
+ *         asm volatile ("" : : : "memory");
+ *         b = READ_ONCE(p);
+ *     } while (a != b);
+ *     asm volatile ("" : : : "memory");  <-- barrier()
+ *     return *b;
+ * }
+ *
+ * With gcc 14.2 (arm64):
+ *
+ * fct_2_volatile_barriers:
+ *         adrp    x0, .LANCHOR0
+ *         add     x0, x0, :lo12:.LANCHOR0
+ * .L2:
+ *         ldr     x1, [x0]  <-- x1 populated by first load.
+ *         ldr     x2, [x0]
+ *         cmp     x1, x2
+ *         bne     .L2
+ *         ldr     w0, [x1]  <-- x1 is used for access which should depend on b.
+ *         ret
+ *
+ * On weakly-ordered architectures, this lets CPU speculation use the
+ * result from the first load to speculate "ldr w0, [x1]" before
+ * "ldr x2, [x0]".
+ * Based on the RCU documentation, the control dependency does not
+ * prevent the CPU from speculating loads.
+ */
+
+#include <asm/ptr_eq.h>
+
+#endif	/* _LINUX_PTR_EQ_H */
diff --git a/include/linux/torture.h b/include/linux/torture.h
index c9b47d138302..1b6d5be641f8 100644
--- a/include/linux/torture.h
+++ b/include/linux/torture.h
@@ -98,6 +98,7 @@ void torture_shutdown_absorb(const char *title);
 int torture_shutdown_init(int ssecs, void (*cleanup)(void));
 
 /* Task stuttering, which forces load/no-load transitions. */
+bool stutter_will_wait(void);
 bool stutter_wait(const char *title);
 int torture_stutter_init(int s, int sgap);
 
@@ -131,8 +132,11 @@ void _torture_stop_kthread(char *m, struct task_struct **tp);
 #endif
 void torture_sched_set_normal(struct task_struct *t, int nice);
 
-#if IS_ENABLED(CONFIG_RCU_TORTURE_TEST) || IS_MODULE(CONFIG_RCU_TORTURE_TEST) || IS_ENABLED(CONFIG_LOCK_TORTURE_TEST) || IS_MODULE(CONFIG_LOCK_TORTURE_TEST)
+#if IS_ENABLED(CONFIG_RCU_TORTURE_TEST) || IS_ENABLED(CONFIG_LOCK_TORTURE_TEST) || IS_ENABLED(CONFIG_HAZPTR_TORTURE_TEST)
 long torture_sched_setaffinity(pid_t pid, const struct cpumask *in_mask, bool dowarn);
 #endif
 
+/* Atomic per-CPU counters. */
+s64 torture_sum_pcpu_atomic_long(atomic_long_t __percpu *pcp);
+
 #endif /* __LINUX_TORTURE_H */