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

4 files changed, 338 insertions, 3 deletions

diff --git a/include/linux/hazptr.h b/include/linux/hazptr.h
new file mode 100644
index 000000000000..43122c5673bd
--- /dev/null
+++ b/include/linux/hazptr.h
@@ -0,0 +1,323 @@
+// 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
+
+/* The current hazard pointer wildcard. */
+extern void *hazptr_wildcard;
+
+/*
+ * 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)();
+#ifdef CONFIG_HAZPTR_DEBUG
+	ctx->detach_task = ctx->detach_cpu = true;
+#endif
+	slot = ctx->slot;
+	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
+		item->ctx.ctx->detach_cpu = true;
+#endif
+		hazptr_promote_to_backup_slot(item->ctx.ctx, slot);
+	}
+}
+
+/**
+ * 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
+	if (unlikely(slot->addr))
+		return __hazptr_acquire(ctx, addr_p);
+	WRITE_ONCE(slot->addr, READ_ONCE(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;
+}
+
+#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;
+
+	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);
+}
+#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/hrtimer.h b/include/linux/hrtimer.h
index 29072d89e5cb..4e4ce747373c 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -72,7 +72,7 @@ enum hrtimer_mode {
  */
 struct hrtimer_sleeper {
 	struct hrtimer timer;
-	struct task_struct *task;
+	struct task_struct __private *task;
 };
 
 static inline void hrtimer_set_expires(struct hrtimer *timer, ktime_t time)
@@ -320,6 +320,14 @@ extern int schedule_hrtimeout_range_clock(ktime_t *expires,
 					  const enum hrtimer_mode mode,
 					  clockid_t clock_id);
 extern int schedule_hrtimeout(ktime_t *expires, const enum hrtimer_mode mode);
+static inline struct task_struct *hrtimer_sleeper_task_get(struct hrtimer_sleeper *sl)
+{
+	return READ_ONCE(ACCESS_PRIVATE(sl, task));
+}
+static inline void hrtimer_sleeper_task_set(struct hrtimer_sleeper *sl, struct task_struct *t)
+{
+	WRITE_ONCE(ACCESS_PRIVATE(sl, task), t);
+}
 
 /* Soft interrupt function to run the hrtimer queues: */
 extern void hrtimer_run_queues(void);
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 */
diff --git a/include/linux/wait.h b/include/linux/wait.h
index dce055e6add3..00cdce75837e 100644
--- a/include/linux/wait.h
+++ b/include/linux/wait.h
@@ -556,7 +556,7 @@ do {										\
 	}									\
 										\
 	__ret = ___wait_event(wq_head, condition, state, 0, 0,			\
-		if (!__t.task) {						\
+		if (!hrtimer_sleeper_task_get(&__t)) {				\
 			__ret = -ETIME;						\
 			break;							\
 		}								\